數(shù)學建模與模擬

1939年

數(shù)學家康托洛維奇

《生產(chǎn)組織與計劃中的數(shù)學問題》1947年

數(shù)學家喬治.丹契克、馮.諾伊曼提出線性規(guī)劃的一般模型及理論。線性規(guī)劃是運籌學的重要分支，也是運籌學的基本部分。線性規(guī)劃的數(shù)學理論是成

、豐富的，其解法

而簡單，求出的解是精確的全局最優(yōu)解。23數(shù)學建模與模擬§1線性規(guī)劃模型基礎(chǔ)建立線性規(guī)劃模型有三個步驟：.找出待定的未知變量（決策變量），并用代數(shù)符號表示它們。.找出問題中所有的限制或約束，寫出未知變量的線性方程或線性不等式。.找到模型的目標或者判據(jù)，寫成決策變量的線性函數(shù)，以便求出其最大值或者最小值。數(shù)學建模與模擬線性規(guī)劃問題的一些應用生產(chǎn)計劃問題問題合理下料問題投資

組合問題分派問題生產(chǎn)工藝優(yōu)化問題的經(jīng)濟效益費最省

或者利潤最大？或利潤最大如何合理使用有限的人力，物力和

，使得收到最好將物資從供應點運送到需求點，如何調(diào)配

，使得運按照進一步的工藝要求，確定下料方案，使用料最省，如何確定投資

的分配，使得總體風險最小，凈收益或，如何確定不同任務(wù)的資源分派，使得總或總成本最小。如何確定工藝的最優(yōu)流程或設(shè)計模式，使得損失最小，或凈利潤最大。4數(shù)學建模與模擬線性規(guī)劃模型的一般形式目標函數(shù)和所有的約束條件都是設(shè)計變量的線性函數(shù)。nnmin(

or

max)

z

f

(

x)

c

j

x

jj

1s.t

.

aij

x

jj

1

(or

)bi

,

i

1,2,...,

m.目標函數(shù)約束條件5決策變量：x1,x2,…,xnaij,bj,ci

(i=1,2…m;j=1,2…n)均為常數(shù).6數(shù)學建模與模擬§2線性規(guī)劃的幾何特征設(shè)

X?

(

x?1

,

x?2

,,x?n

)

滿足線性規(guī)劃問題全部約束條件，則稱之為此線性規(guī)劃問題的一個可行解；稱由所有可行解組成的集合為該線性規(guī)劃問題的可行域，用D表示；使目標函數(shù)值達到最優(yōu)的可行解X

*

(

x*

,

x*

,,

x*

)1

2

n稱為此線性規(guī)劃問題的一個最優(yōu)解；稱最優(yōu)解X

*

(x*

,x*

,,x*

)

的目標函數(shù)值1

2

nf

*

CT

X*為該線性規(guī)劃問題的最優(yōu)值。數(shù)學建模與模擬可行域為凸集：幾個典型的凸集（區(qū)域）幾個典型的非凸集（區(qū)域）78數(shù)學建模與模擬命題1若線性規(guī)劃有最優(yōu)解，則必在可行域邊界達到；若可行域為有界閉集，則最優(yōu)解必在的某一頂點達到。命題2

線性規(guī)劃問題的目標函數(shù)(關(guān)于不同的目標值是一族平行直線,目標值的大小描述了直線離原點的遠近.)命題3線性規(guī)劃問題的最優(yōu)解一定在可行解集的某個極點上達到(穿過可行域的目標直線組中最遠離(或接近)原點的直線所穿過的凸多邊形的頂點).數(shù)學建模與模擬圖解法：(解兩個變量的線性規(guī)劃問題)在平面上畫出可行域（凸多邊形），計算目標函數(shù)在各極點(多邊形頂點)處的值。比較后，取最值點為最優(yōu)解。9數(shù)學建模與模

101x2504030201010203040x1例用圖解法求解下線性規(guī)劃問題max Z

= 50x1

+

30x2s.t.4x1

+

3x2

1202x1

+

x2

50x1,

x2

0x2由

4x1+3x2

120x1

0 x2

0

圍成的區(qū)域4x1+3x2=

1202x1+x2

=

50由2x1+x2

50x1

0

x2

0圍成的區(qū)域數(shù)學建模與模擬11同時滿足：2x1+x2

504x1+3x2

120x1

0 x2

0的區(qū)域——可行域x2504030201010203040x14x1+3x2

1202x1+x2

50可行域數(shù)學建模與模擬12可行域x25040302010102040x1O(0，0)Q1（25，0）30Q2（15，20）3Q

（0，40）可行域是由約束條件圍成的區(qū)域，該區(qū)域內(nèi)的每一點都是可行解，它的全體組成問題的解集合。該問題的可行域是由O，Q1，Q2，Q3作為頂點的凸多邊形數(shù)學建模與模擬x25010Max

Z

= 50x1

+

30x24030目標函數(shù)是以Z作為參數(shù)的一組平行線2051310203040x1X

2

30

3

X1Z數(shù)學建模與模擬x2504030201Max

Z

=

50x +30x21230

3X

5

X

Z沿著其法線方向(50,30)向右上方移動時，Z值不斷增加.1230

3當直線

X

5

X

Z10可行域1410203040x1數(shù)學建模與模擬x25040302010當該直線移到Q2點時，Z（目標函數(shù)）值達到最大，最大值是：Q2（15，20）Max

Z

=50*15+30*20=1350最優(yōu)解是

Q2（15，20）1510203040x1數(shù)學建模與模擬16用求解線性規(guī)劃一般線性規(guī)劃的數(shù)學模型min

f

=

cxs.t.Ax

bAeq

x

=

beqLB

x

UB求解程序[x,f]=linprog(c,A,b,Aeq,beq,LB,UB)數(shù)學建模與模擬7具體命令X

=

linprog(c,A,b)X=

linprog(c,A,b,Aeq,beq)X

=

linprog(c,A,b,Aeq,beq,lb,ub)X

=

linprog(c,A,b,Aeq,beq,lb,ub,X0)[X,

fval]

=

linprog(…)min

z=cXs.

t. AX

≤

bmin

z

=cXs.

t. AX

≤bAeqX· =beqmin

z

=cXs.

t.

AX≤bAeqX· =

beqlb

≤X

≤

ubX0為初始值點返回最優(yōu)解X以及X處的目標函數(shù)值fval數(shù)學建模與模擬18例

min z

=

6x1+3x2+4x3s.t.

x1+x2+x3=120x1

≥

300

≤

x2

≤50x3

≥

20解：改寫為

min

z

=

C?[x1

x2

x3

]?s.t.

A?[x1

x2

x3

]?

≤

bAeq?[x1

x2

x3

]?

=

beqLB

≤

[x1

x2

x3

]?b

=

50C=[6

3

4]LB=[30 0

20]?A

01

0Aeq

=[1

1

1]beq

=

12019數(shù)學建模與模擬用命令X=linprog(c,A,b,Aeq,beq,lB,UB)編寫M文件xxgh1.m

：C=

[6

3

4];A=

[0

1

0];b=

[50];Aeq=

[1

1

1];beq=

[120];LB=

[30;

0;

20];UB=

[];[x,fval]=

linprog(C,A,b,Aeq,beq,LB,UB);運行程序xxgh1.m結(jié)果為x=

30.0000 40.0000

50.0000fval=

490.0000數(shù)學建模與模擬工廠級：根據(jù)外部需求和

設(shè)備、人力、原料等條件，以最大利潤為目標制訂產(chǎn)品生產(chǎn)計劃.車間級：根據(jù)生產(chǎn)計劃、工藝流程、資源約束及費用參數(shù)等，以最小成本為目標制訂生產(chǎn)批量計劃?！?建模實例1：奶制品的加工企業(yè)生產(chǎn)計劃問題空間層次時間層次若短時間內(nèi)外部需求和資源等不隨時間變化，可制訂單階段生產(chǎn)計劃，否則應制訂多階段生產(chǎn)計劃。本節(jié)課題單階段生產(chǎn)計劃20問題一奶制品用牛奶生產(chǎn)A1,A2兩種奶制品，1桶牛奶可以在設(shè)備甲上用12小時加工成

3

公斤A1

，或

在設(shè)備乙上用8小時加工成4公斤A2.根據(jù)市場需求，生產(chǎn)

的A1,

A2全部能夠售出，且每公斤

A1

獲利24元，每公斤

A2獲利16元.

現(xiàn)在

每天能得到50桶牛奶的供應，

每天正式工人總的勞動時間為480小時，并且設(shè)備甲每天最多能夠加工100公斤的A1,設(shè)備乙的加工能力沒有限制。請為該廠制定一個生產(chǎn)計劃，使每天獲利最大。1桶牛奶3公斤A112小時8小時4公斤A2或獲利24元/公斤獲利16元/公斤50桶牛奶

時間480小時

至多加工100公斤A1每天：制訂生產(chǎn)計劃，使每天獲利最大問題分析x1桶牛奶生產(chǎn)A1x2桶牛奶生產(chǎn)A2決策變量A1:獲利

24×3x1A2:獲利

16×4x2目標函數(shù)Max

z

72x1

64x2每天獲利約束條件原料供應勞動時間加工能力非負約束x1

x2

5012x1

8x2

4803x1

100x1

,

x2

0線性規(guī)劃模型

(LP)求什么？優(yōu)化什么？限制條件有哪些？數(shù)學建模與模擬23線性規(guī)劃模型Max z

=

72x1

+

64x2s.t. x1+

x2

≤

5012x1+8x2

≤

4803x1≤

100x1≥

0,

x2≥

0模型分析與假設(shè)比例性xi對目標函數(shù)的“貢獻”與xi取值成正比xi對約束條件的“貢獻”與xi取值成正比xi對目標函數(shù)的“貢獻”與xj取值無關(guān)xi對約束條件的“貢獻”與xj取值無關(guān)A1,A2每公斤的獲利是與各自產(chǎn)量無關(guān)的常數(shù)每桶牛奶加工出A1,A2的數(shù)量和時間是與各自產(chǎn)量無關(guān)的常數(shù)A1,A2每公斤的獲利是與相互產(chǎn)量無關(guān)的常數(shù)每桶牛奶加工出A1,A2的數(shù)量和時間是與相互產(chǎn)量無關(guān)的常數(shù)線性規(guī)劃模型可加性連續(xù)性xi取值連續(xù)加工A1,A2的牛奶桶數(shù)是實數(shù)圖解法x120xABDl1l2l5x1

x2

5012x1

8x2

4803x1

100x1

,

x2

0約束條件l4l1

:

x1

x2

50l2

:12x1

8x2

480l3

:

3x1

100l4

:

x1

0,

l5

:

x2

0目標函數(shù)Z=0Z=2400C

Z=3600l3Max z

72x1

64x2z=c

(常數(shù))~等值線c在B(20,30)點得到最優(yōu)解目標函數(shù)和約束條件是線性函數(shù)可行域為直線段圍成的凸多邊形目標函數(shù)的等值線為直線最優(yōu)解一定在凸多邊形的某個頂點取得。模型求解數(shù)學建模與模擬實現(xiàn)Max

z

=

72x1+64x2Min

z=

-72x1-64x2s.t. x1+x2

≤

50s.t.x1+x2

≤

5012x1+8x2

≤

48012x1+8x2

≤

4803x1≤

1003x1≤

100x1≥

0,

x2≥

0x1≥

0,

x2≥

0求解得：x

=fval

=20.0000

30.0000-3.3600e+00320桶牛奶生產(chǎn)A1,30桶生產(chǎn)A2，利潤3360元。2627數(shù)學建模與模擬xxgh2.mc

=[-72-64];A

=

[11;

128;

3

0];b

=

[50;

480;100];Aeq

=

[];beq

=

[];vlb

=[00];ulb=[];[x,fval]=linprog(c,A,b,Aeq,beq,vlb,ulb);Min

z

=

-72x1-64x2s.t.x1+x2

≤

5012x1+8x2

≤

4803x1≤

100x1≥

0,

x2≥

028數(shù)學建模與模擬§4建模實例2：奶制品的生產(chǎn)銷售計劃問題例1中給出的A1,A2兩種奶制品的生產(chǎn)條件、利潤，以及工廠的“資源”限制都不變。為增加工廠的獲利，開發(fā)了奶產(chǎn)品的深加工技術(shù)：用2小時和3元加工費，可將1公斤A1加工成0.8公斤高級奶制品B1，也可將1公斤A2加工成0.75公斤高級奶制品B2

，每公斤B1能獲利44元，每公斤B2能獲利32元。請為該廠制訂一個生產(chǎn)銷售計劃，使每天的凈利潤最大。數(shù)學建模與模擬1桶牛奶3千克A112小時8小時4公斤A2或獲利24元/公斤獲利16元/公斤制訂生產(chǎn)計劃，使每天凈利潤最大50桶牛奶,480小時至多100公斤A10.8千克B11千克2小時,3元獲利44元/千克0.75千克B21千克2小時,3元獲利32元/千克291桶牛奶3千克A112小時8小時4千克A2或獲利24元/千克獲利16元/千克0.8千克B11千克2小時,3元獲利44元/千克0.75千克B21千克2小時,3元獲利32元/千克原料供應勞動時間加工能力決策變量目標函數(shù)約束條件非負約束售出x1

千克A1,

x2

千克A2，

x3千克B1,

x4千克B2x5千克A1加工B1，x6千克A2加工B2Max z

24x1

16x2

44x3

32x4

50x1

x5

x2

x63

4

2x5

2x6

4804(x1

x5

)

2(x26

3x5

3x6

x1

x5

100x3

0.8x5

x

)附加約束x4

0.75x6x1,x6

0線性規(guī)劃模型

3x6

3x5Max z

24x1

16x2

44x3

32x43

4

50x1

x5

x2

x64(x1

x5

)

2(x2

x6

)

2x5

2x6

480x1

x5

100x3

0.8x5x4

0.75x6x1,x6

0s.t模型求解將線性規(guī)劃模型標準化用

求解求解結(jié)果x

=0

168

19.2

0

24

0fval

=

-3460.8000每天銷售168千克A2和19.2千克B1，利潤3460.8（元）8桶牛奶加工成A1，42桶牛奶加工成A2，將得到的24千克A1全部加工成B1結(jié)果解釋數(shù)學建模與模擬§5建模實例3：自來水的輸送問題背景煤炭、鋼鐵、水電等生活、生產(chǎn)物資從若干供應點運送到一些需求點。希望節(jié)約成本，創(chuàng)造更大的利潤。怎樣安排運送方案才能使得運費最小，或者利潤最大？33數(shù)學建模與模擬問題現(xiàn)有甲、乙、丙，丁四個居民區(qū)，自來水由A、B、C三個水庫供應。四個區(qū)每天必須得到的基本生活水量分別為30，70，10，10千噸，但由于水源緊張，三個水庫每天最多只能分別供應50，60，50千噸自來水。由于地理環(huán)境的不同，各水庫向不同生活區(qū)送水所需的引水

不同（見下頁表格），而其他

都為450元/千噸。根據(jù)公司規(guī)定，各區(qū)用戶按照同一標準水費為900元/千噸。此外每個區(qū)都向公司申請了額外用水量，分別為50，70，20，40千噸。請為自來水公司設(shè)計供水量分配方案，使其獲利最多。34問題

為自來水公司設(shè)計供水分配方案，使其獲利最多。A：50B：60C：50甲：30；50乙：70；70丙：10；20?。?0；40(水庫供水量千噸)(小區(qū)基本用水量千噸)(小區(qū)額外用水量千噸)（以天計）元/千噸甲乙丙丁A160130220170B140130190150C190200230/引水其他費用:450元/千噸：900元/千噸建模分析確定送水方案使利潤最大甲：30；50乙：70；70丙：10；20?。?0；40A：50B：60C：50總供水量：160

<

總需求量：120+180=300總收入900160=144,000(元)收入支出引水其他費用:450元/千噸其他支出450160=72,000(元)使引水最小水費：900元/千噸模型建立供應限制約束條件需求限制線性規(guī)劃模型(LP)x11x21x31

x32

x12

x13

x14

50

x22

x23

x24

60

x33

5011

21

3130

x

x

x

8070

x12

x22

x32

x

x

x

301

0

x

24

5

0x

1

4目標函數(shù)決策變量確定3個水庫向4個小區(qū)的供水量水庫i

向j

區(qū)的日供水量為

xij（x34=0）Min Z

160x11

130x12

220x13

170x14140x21

130x22

190x23

150x24

190x31

200x32

230x33數(shù)學建模與模擬38模型x11x21x31

x32

x12

x13

x14

50

x22

x23

x24

60

50

x33Min Z

160x11

130x12

220x13

170x14140x21

130x22

190x23

150x24

190x31

200x32

230x33S.

t.30

x11

x

21

x31

8070

x12

x22

x32

1401

0

10

x13

x

23

x33

305

0x

1

4

x

24i

1, 3,

j

1,

4.ijx

0,求解模型求解clearC=[160

130

220

170

140

130

190

150

190

200

230];A=

[1

0

0

0

1

00

01

0

0

;01

0

0

0

1

0

0

0

1

0

;00

1

0

0

0

1

0

0

0

1

;00

0

1

0

0

01

0

0

0;-1

00

0

-1

00

0

-1

0

0;0

-1

0

0

0

-1

00

0

-1

0

;0

0

-1

0

0

0

-1

0

0

0

-1;0

0

0

-1

00

0

-1

0

0

0];b=

[80;140;30;50;-30;-70;-10;-10];Aeq=

[1

1

1

1

0

00

0

0

0

0

;

0

0

0

0

1

11

1

0

00;

0

0

0

0

00

0

0

11

1];beq=

[50;60;50];LB=

zeros(11,1);UB=[];[x,fval]=

linprog(C,A,b,Aeq,beq,LB,UB);數(shù)學建模與模擬用求解得x =[0 50

00

0

50 0

10

40 010]fval=

24400.00模型求解A(50)B(60)C(50)甲(30;50)乙(70;70)丙(10;20)丁(10;40)5050401010利潤=總收入-其它費用-引水=144000-72000-24400=47600（元）40數(shù)學建模與模擬每個水庫最大供水量都提高一倍，各小區(qū)需求量不變。試建立模型確定此時公司的供水方案。利潤(元/千噸)甲乙丙丁A290320230280B310320260300C260250220/問題總供水量(320)>總需求量(300)確定送水方案使利潤最大利潤

=

收入(900)

–其它費用(450) –引水41目標函數(shù)Max Z

290x11

320x12

230x13

280x14310x21

320x22

260x23

300x24

260x31

250x32

220x33供應限制A

:

x11

x12

x13

x14

50

x13

x14

100x11

x12B,

C

類似處理

需求約束可以不變42決策變量數(shù)學建模與模擬確定3個水庫向4個小區(qū)的供水量水庫i

向j

區(qū)的日供水量為

xij（x34=0）數(shù)學建模與模擬分配結(jié)果總利潤88700（元）這類問題一般稱為“

問題”(Transportation

Problem)A(100)C(100)甲(30;50)乙(70;70)丙(10;20)丁(10;40)305010030B(120)

405043數(shù)學建模與模擬§6建模實例4：貨機裝運問題問題背景空地

物流公司中，航空貨運業(yè)務(wù)極其重要。現(xiàn)在，我國的航空貨運正處于飛速發(fā)展的階段，例如，在建設(shè)亞太

樞紐港的進程中，

航空物流吞吐量每年以20%的速度增長。航空貨運有著高效便捷的特點，為航空貨物提供全方位配送服務(wù)是現(xiàn)代物流公司打造安全、暢通、便捷的現(xiàn)代化物流系統(tǒng)中非常重要的組成部分。44數(shù)學建模與模擬前倉：10；6800中倉：16；8700后倉：8；5300問題45某駕貨機有三個貨艙：前倉、中倉、后倉。三個貨艙所能裝載的貨物的最大重量和體積都有限制，而且為了保持飛機的平衡，三個貨艙中的實際裝載貨物重量必須與其最大容許重量成比例。現(xiàn)有四類貨物需要裝運，試建立模型安排裝運，使得該貨機本次飛行獲利最大。三個貨艙最大載重(噸),最大容積(米3)如何裝運，使本次飛行獲利最大？重量（噸）空間(米3/噸）利潤（元/噸）貨物1184803100貨物2156503800貨物3235803500貨物4123902850三個貨艙中實際載重必須與其最大載重成比例飛機平衡裝運貨物信息數(shù)學建模與模擬建模假設(shè)每種貨物可以分割到任意??；每種貨物可以在一個或多個貨艙中任意分布；多種貨物可以混裝，

不留空隙；47數(shù)學建模與模擬模型建立決策變量xij--第i

種貨物裝