數(shù)學(xué)規(guī)劃模型清華大學(xué)學(xué)習(xí)教案

1、數(shù)學(xué)規(guī)劃數(shù)學(xué)規(guī)劃(guhu)模型清華大學(xué)模型清華大學(xué)第一頁，共93頁。數(shù)學(xué)規(guī)劃數(shù)學(xué)規(guī)劃(guhu)(guhu)模型模型 實(shí)際問題實(shí)際問題(wnt)中中的優(yōu)化模型的優(yōu)化模型mixgtsxxxxfzMaxMiniTn, 2 , 1, 0)(. .),(),()(1或x決策決策(juc)變量變量f(x)目標(biāo)函數(shù)目標(biāo)函數(shù)gi(x) 0約束條件約束條件多元函數(shù)多元函數(shù)條件極值條件極值 決策變量個(gè)數(shù)決策變量個(gè)數(shù)n和和約束條件個(gè)數(shù)約束條件個(gè)數(shù)m較大較大 最優(yōu)解在可行域最優(yōu)解在可行域的邊界上取得的邊界上取得 數(shù)數(shù)學(xué)學(xué)規(guī)規(guī)劃劃線性規(guī)劃線性規(guī)劃非線性規(guī)非線性規(guī)劃劃整數(shù)規(guī)劃整數(shù)規(guī)劃重點(diǎn)在模型的建立和結(jié)果的分析重點(diǎn)在

2、模型的建立和結(jié)果的分析第1頁/共93頁第二頁，共93頁。企業(yè)企業(yè)(qy)生產(chǎn)生產(chǎn)計(jì)劃計(jì)劃4.1 奶制品的生產(chǎn)奶制品的生產(chǎn)(shngchn)與銷售與銷售 空間空間(kngjin)層次層次工廠級(jí)：根據(jù)外部需求和內(nèi)部設(shè)備、人力、原料等條件，工廠級(jí)：根據(jù)外部需求和內(nèi)部設(shè)備、人力、原料等條件，以最大利潤為目標(biāo)制訂產(chǎn)品生產(chǎn)計(jì)劃；以最大利潤為目標(biāo)制訂產(chǎn)品生產(chǎn)計(jì)劃；車間級(jí)：根據(jù)生產(chǎn)計(jì)劃、工藝流程、資源約束及費(fèi)用參數(shù)車間級(jí)：根據(jù)生產(chǎn)計(jì)劃、工藝流程、資源約束及費(fèi)用參數(shù)等，以最小成本為目標(biāo)制訂生產(chǎn)批量計(jì)劃。等，以最小成本為目標(biāo)制訂生產(chǎn)批量計(jì)劃。時(shí)間層次時(shí)間層次若短時(shí)間內(nèi)外部需求和內(nèi)部資源等不隨時(shí)間變化，若短時(shí)間內(nèi)外

3、部需求和內(nèi)部資源等不隨時(shí)間變化，可制訂可制訂單階段生產(chǎn)計(jì)劃單階段生產(chǎn)計(jì)劃，否則應(yīng)制訂多階段生產(chǎn)計(jì)劃。，否則應(yīng)制訂多階段生產(chǎn)計(jì)劃。本節(jié)課題本節(jié)課題第2頁/共93頁第三頁，共93頁。例例1 加工加工(ji gng)奶制品的生產(chǎn)奶制品的生產(chǎn)計(jì)劃計(jì)劃1桶牛奶 3公斤A1 12小時(shí) 8小時(shí) 4公斤A2 或獲利24元/公斤 獲利16元/公斤 50桶牛奶桶牛奶(ni ni) 時(shí)間時(shí)間(shjin)480小時(shí)小時(shí) 至多加工至多加工100公斤公斤A1 制訂生產(chǎn)計(jì)劃，使每天獲利最大制訂生產(chǎn)計(jì)劃，使每天獲利最大 35元可買到元可買到1桶牛奶，買嗎？若買，每天最多買多少桶牛奶，買嗎？若買，每天最多買多少? 可聘用臨時(shí)

4、工人，付出的工資最多是每小時(shí)幾元可聘用臨時(shí)工人，付出的工資最多是每小時(shí)幾元? A1的獲利增加到的獲利增加到 30元元/公斤，應(yīng)否改變生產(chǎn)計(jì)劃？公斤，應(yīng)否改變生產(chǎn)計(jì)劃？ 每天：每天：第3頁/共93頁第四頁，共93頁。1桶牛奶 3公斤A1 12小時(shí) 8小時(shí) 4公斤A2 或獲利24元/公斤 獲利16元/公斤 x1桶牛奶桶牛奶(ni ni)生產(chǎn)生產(chǎn)A1 x2桶牛奶桶牛奶(ni ni)生產(chǎn)生產(chǎn)A2 獲利獲利(hu l) 243x1 獲利獲利 164 x2 原料供應(yīng)原料供應(yīng) 5021 xx勞動(dòng)時(shí)間勞動(dòng)時(shí)間 48081221 xx加工能力加工能力 10031x決策變量決策變量 目標(biāo)函數(shù)目標(biāo)函數(shù) 216472

5、xxzMax每天獲利每天獲利約束條件約束條件非負(fù)約束非負(fù)約束 0,21xx線性線性規(guī)劃規(guī)劃模型模型(LP)時(shí)間時(shí)間480小小時(shí)時(shí) 至多加工至多加工100公斤公斤A1 50桶牛奶桶牛奶 每每天天第4頁/共93頁第五頁，共93頁。模型分析模型分析(fnx)(fnx)與假設(shè)與假設(shè) 比比例例(bl)性性 可可加加性性 連續(xù)性連續(xù)性 xi對目標(biāo)對目標(biāo)(mbio)函數(shù)的函數(shù)的“貢獻(xiàn)貢獻(xiàn)”與與xi取值成正比取值成正比 xi對約束條件的對約束條件的“貢獻(xiàn)貢獻(xiàn)”與與xi取值取值成正比成正比 xi對目標(biāo)函數(shù)的對目標(biāo)函數(shù)的“貢貢獻(xiàn)獻(xiàn)”與與xj取值無關(guān)取值無關(guān) xi對約束條件的對約束條件的“貢貢獻(xiàn)獻(xiàn)”與與xj取值無關(guān)

6、取值無關(guān) xi取值連續(xù)取值連續(xù) A1,A2每公斤的獲利是與各每公斤的獲利是與各自產(chǎn)量無關(guān)的常數(shù)自產(chǎn)量無關(guān)的常數(shù)每桶牛奶加工出每桶牛奶加工出A1,A2的數(shù)量和時(shí)的數(shù)量和時(shí)間是與各自產(chǎn)量無關(guān)的常數(shù)間是與各自產(chǎn)量無關(guān)的常數(shù)A1,A2每公斤的獲利是與相互產(chǎn)每公斤的獲利是與相互產(chǎn)量無關(guān)的常數(shù)量無關(guān)的常數(shù)每桶牛奶加工出每桶牛奶加工出A1,A2的數(shù)量和時(shí)的數(shù)量和時(shí)間是與相互產(chǎn)量無關(guān)的常數(shù)間是與相互產(chǎn)量無關(guān)的常數(shù)加工加工A1,A2的牛奶桶數(shù)是實(shí)數(shù)的牛奶桶數(shù)是實(shí)數(shù) 線性規(guī)劃模線性規(guī)劃模型型第5頁/共93頁第六頁，共93頁。模型模型(mxng)(mxng)求求解解 圖解法圖解法 x1x20ABCDl1l2l3l4

7、l55021 xx48081221 xx10031x0,21xx約約束束條條件件50:211 xxl480812:212 xxl1003:13xl0:, 0:2514xlxl216472xxzMax目標(biāo)目標(biāo)(mbi(mbio)o)函函數(shù)數(shù) Z=0Z=2400Z=3600z=c (常數(shù)常數(shù)(chngsh) 等值線等值線c在在B(20,30)點(diǎn)得到最優(yōu)解點(diǎn)得到最優(yōu)解目標(biāo)函數(shù)和約束條件是線性函數(shù)目標(biāo)函數(shù)和約束條件是線性函數(shù) 可行域?yàn)橹本€段圍成的凸多邊形可行域?yàn)橹本€段圍成的凸多邊形 目標(biāo)函數(shù)的等值線為直線目標(biāo)函數(shù)的等值線為直線 最優(yōu)解一定在凸多最優(yōu)解一定在凸多邊形的某個(gè)頂點(diǎn)取邊形的某個(gè)頂點(diǎn)取得。得。

8、第6頁/共93頁第七頁，共93頁。模型模型(mxng)(mxng)求解求解 軟件軟件(run (run jin)jin)實(shí)現(xiàn)實(shí)現(xiàn) LINDO 6.1 max 72x1+64x2st2）x1+x2503）12x1+8x24804）3x1100end OBJECTIVE FUNCTION VALUE 1) 3360.000 VARIABLE VALUE REDUCED COST X1 20.000000 0.000000 X2 30.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 48.000000 3) 0.000000

9、2.000000 4) 40.000000 0.000000 NO. ITERATIONS= 2DO RANGE (SENSITIVITY) ANALYSIS? No20桶牛奶生產(chǎn)桶牛奶生產(chǎn)(shngchn)A1, 30桶生產(chǎn)桶生產(chǎn)(shngchn)A2，利潤，利潤3360元。元。 第7頁/共93頁第八頁，共93頁。結(jié)果結(jié)果(ji (ji gu)gu)解釋解釋 OBJECTIVE FUNCTION VALUE 1) 3360.000 VARIABLE VALUE REDUCED COST X1 20.000000 0.000000 X2 30.000000 0.000000 ROW SLACK

10、 OR SURPLUS DUAL PRICES 2) 0.000000 48.000000 3) 0.000000 2.000000 4) 40.000000 0.000000 NO. ITERATIONS= 2原料原料(yunlio)無無剩余剩余時(shí)間時(shí)間(shjin)無剩余無剩余加工能力剩余加工能力剩余40max 72x1+64x2st2）x1+x2503）12x1+8x24804）3x1100end三三種種資資源源“資源資源” 剩余為零的約束為緊約束（有效約束）剩余為零的約束為緊約束（有效約束） 第8頁/共93頁第九頁，共93頁。結(jié)果結(jié)果(ji (ji gu)gu)解釋解釋 OBJECTI

11、VE FUNCTION VALUE 1) 3360.000 VARIABLE VALUE REDUCED COST X1 20.000000 0.000000 X2 30.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 48.000000 3) 0.000000 2.000000 4) 40.000000 0.000000 NO. ITERATIONS= 2最優(yōu)解下最優(yōu)解下“資源資源”增加增加1單位時(shí)單位時(shí)“效益效益(xioy)”的增量的增量 原料增加原料增加1單位單位, 利潤利潤(lrn)增增長長48 時(shí)間增加時(shí)間增加

12、1單位單位, 利潤增長利潤增長2 加工能力增長不影響利潤加工能力增長不影響利潤影子價(jià)格影子價(jià)格 35元可買到元可買到1桶牛奶，要買嗎？桶牛奶，要買嗎？35 48, 應(yīng)該買！應(yīng)該買！ 聘用臨時(shí)工人付出的工資最多每小時(shí)幾元？聘用臨時(shí)工人付出的工資最多每小時(shí)幾元？ 2元！元！第9頁/共93頁第十頁，共93頁。RANGES IN WHICH THE BASIS IS UNCHANGED: OBJ COEFFICIENT RANGES VARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE X1 72.000000 24.000000 8.

13、000000 X2 64.000000 8.000000 16.000000 RIGHTHAND SIDE RANGES ROW CURRENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASE 2 50.000000 10.000000 6.666667 3 480.000000 53.333332 80.000000 4 100.000000 INFINITY 40.000000最優(yōu)解不變時(shí)目標(biāo)函最優(yōu)解不變時(shí)目標(biāo)函數(shù)系數(shù)允許變化數(shù)系數(shù)允許變化(binhu)范圍范圍 DO RANGE(SENSITIVITY) ANALYSIS? Yesx1系數(shù)系數(shù)(xsh)

14、范范圍圍(64,96) x2系數(shù)系數(shù)(xsh)范圍范圍(48,72) A1獲利增加到獲利增加到 30元元/千克，應(yīng)否改變生產(chǎn)計(jì)劃千克，應(yīng)否改變生產(chǎn)計(jì)劃 x1系數(shù)由系數(shù)由24 3=72增增加加為為30 3=90，在，在允許范圍內(nèi)允許范圍內(nèi) 不變！不變！(約束條件不變約束條件不變)第10頁/共93頁第十一頁，共93頁。結(jié)果結(jié)果(ji (ji gu)gu)解解釋釋 RANGES IN WHICH THE BASIS IS UNCHANGED: OBJ COEFFICIENT RANGES VARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECRE

15、ASE X1 72.000000 24.000000 8.000000 X2 64.000000 8.000000 16.000000 RIGHTHAND SIDE RANGES ROW CURRENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASE 2 50.000000 10.000000 6.666667 3 480.000000 53.333332 80.000000 4 100.000000 INFINITY 40.000000影子價(jià)格有意義時(shí)約束右端的影子價(jià)格有意義時(shí)約束右端的(dund)允許允許變化范圍變化范圍 原料原料(yunlio)最多增加

16、最多增加10 時(shí)間最多增加時(shí)間最多增加53 35元可買到元可買到1桶牛奶，每天最多買多少？桶牛奶，每天最多買多少？最多買最多買10桶桶!(目標(biāo)函數(shù)不變目標(biāo)函數(shù)不變)第11頁/共93頁第十二頁，共93頁。例例2 奶制品的生產(chǎn)銷售奶制品的生產(chǎn)銷售(xioshu)計(jì)劃計(jì)劃 在例在例1基礎(chǔ)基礎(chǔ)(jch)上上深加工深加工1桶桶牛奶牛奶 3千克千克A1 12小時(shí)小時(shí) 8小時(shí)小時(shí) 4公斤公斤A2 或或獲利獲利24元元/公公斤斤 獲利獲利16元元/公斤公斤 0.8千克千克B12小時(shí)小時(shí),3元元1千千克克獲利獲利44元元/千千克克 0.75千克千克B22小時(shí)小時(shí),3元元1千千克克獲利獲利32元元/千千克克 制訂

17、生產(chǎn)制訂生產(chǎn)(shngchn)(shngchn)計(jì)劃，使每計(jì)劃，使每天凈利潤最大天凈利潤最大 30元可增加元可增加1桶牛奶，桶牛奶，3元可增加元可增加1小時(shí)時(shí)間，應(yīng)否投資？現(xiàn)小時(shí)時(shí)間，應(yīng)否投資？現(xiàn)投資投資150元，可賺回多少？元，可賺回多少？50桶牛奶桶牛奶, 480小時(shí)小時(shí) 至多至多100公斤公斤A1 B1，B2的獲利經(jīng)常有的獲利經(jīng)常有10%的波動(dòng)，對計(jì)劃有無影響？的波動(dòng)，對計(jì)劃有無影響？第12頁/共93頁第十三頁，共93頁。1桶桶牛奶牛奶 3千克千克 A1 12小時(shí)小時(shí) 8小時(shí)小時(shí) 4千克千克 A2 或或獲利獲利24元元/千克千克 獲利獲利16元元/kg 0.8千克千克 B12小時(shí)小時(shí),3

18、元元1千克千克獲利獲利44元元/千克千克 0.75千克千克 B22小時(shí)小時(shí),3元元1千克千克獲利獲利32元元/千克千克 出售出售(chshu)x1 千克千克 A1, x2 千克千克 A2， X3千克千克(qink) B1, x4千千克克(qink) B2原料原料(yunlio)供供應(yīng)應(yīng) 勞動(dòng)勞動(dòng)時(shí)間時(shí)間 加工能力加工能力 決策決策變量變量 目標(biāo)目標(biāo)函數(shù)函數(shù) 利潤利潤約束約束條件條件非負(fù)約束非負(fù)約束 0,61xx x5千克千克 A1加工加工B1， x6千克千克 A2加工加工B26543213332441624xxxxxxzMax50436251xxxx48022)(2)(4656251xxxxx

19、x10051 xx附加約束附加約束 5380 x.x64750 x.x 第13頁/共93頁第十四頁，共93頁。模型模型(mxng)(mxng)求解求解 軟件軟件(run (run jin)jin)實(shí)實(shí)現(xiàn)現(xiàn) LINDO 6.1 5043)26251xxxx48022)(2)(4)3656251xxxxxx OBJECTIVE FUNCTION VALUE 1) 3460.800 VARIABLE VALUE REDUCED COST X1 0.000000 1.680000 X2 168.000000 0.000000 X3 19.200001 0.000000 X4 0.000000 0.00

20、0000 X5 24.000000 0.000000 X6 0.000000 1.520000ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 3.160000 3) 0.000000 3.260000 4) 76.000000 0.000000 5) 0.000000 44.000000 6) 0.000000 32.000000 NO. ITERATIONS= 2600334) 26521xxxx44804624) 36521xxxxDO RANGE (SENSITIVITY) ANALYSIS? No第14頁/共93頁第十五頁，共93頁。 OBJE

21、CTIVE FUNCTION VALUE 1) 3460.800 VARIABLE VALUE REDUCED COST X1 0.000000 1.680000 X2 168.000000 0.000000 X3 19.200001 0.000000 X4 0.000000 0.000000 X5 24.000000 0.000000 X6 0.000000 1.520000ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 3.160000 3) 0.000000 3.260000 4) 76.000000 0.000000 5) 0.000000 4

22、4.000000 6) 0.000000 32.000000 NO. ITERATIONS= 2結(jié)果結(jié)果(ji (ji gu)gu)解釋解釋每天銷售每天銷售168 千克千克(qink)A2和和19.2 千克千克(qink)B1， 利潤利潤3460.8（元）（元）8桶牛奶桶牛奶(ni ni)加工成加工成A1，42桶牛奶桶牛奶(ni ni)加加工成工成A2，將得到的將得到的24千克千克A1全部全部加工成加工成B1 除加工能力外均除加工能力外均為緊約束為緊約束第15頁/共93頁第十六頁，共93頁。結(jié)果結(jié)果(ji (ji gu)gu)解釋解釋 OBJECTIVE FUNCTION VALUE 1) 3

23、460.800 VARIABLE VALUE REDUCED COST X1 0.000000 1.680000 X2 168.000000 0.000000 X3 19.200001 0.000000 X4 0.000000 0.000000 X5 24.000000 0.000000 X6 0.000000 1.520000ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 3.160000 3) 0.000000 3.260000 4) 76.000000 0.000000 5) 0.000000 44.000000 6) 0.000000 32.0

24、00000增加增加1桶牛奶使利潤桶牛奶使利潤(lrn)增長增長3.1612=37.925043)26251xxxx600334) 26521xxxx4增加增加(zngji)1小時(shí)時(shí)小時(shí)時(shí)間使利潤增長間使利潤增長3.26 30元可增加元可增加1桶牛奶，桶牛奶，3元可增加元可增加1小時(shí)時(shí)間，應(yīng)小時(shí)時(shí)間，應(yīng)否投資？現(xiàn)投資否投資？現(xiàn)投資150元，可賺回多少？元，可賺回多少？投資投資150元增加元增加5桶牛奶，桶牛奶，可賺回可賺回189.6元。（大于元。（大于增加時(shí)間的利潤增長）增加時(shí)間的利潤增長）第16頁/共93頁第十七頁，共93頁。結(jié)果結(jié)果(ji (ji gu)gu)解釋解釋B1,B2的獲利有的獲利

25、有10%的波動(dòng)，對計(jì)劃有無的波動(dòng)，對計(jì)劃有無(yu w)影影響響 RANGES IN WHICH THE BASIS IS UNCHANGED: OBJ COEFFICIENT RANGES VARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE X1 24.000000 1.680000 INFINITY X2 16.000000 8.150000 2.100000 X3 44.000000 19.750002 3.166667 X4 32.000000 2.026667 INFINITY X5 -3.000000 15.800

26、000 2.533334 X6 -3.000000 1.520000 INFINITY DO RANGE (SENSITIVITY) ANALYSIS? YesB1獲利下降獲利下降10%，超，超出出X3 系數(shù)允許系數(shù)允許(ynx)范圍范圍B2獲利上升獲利上升10%，超，超出出X4 系數(shù)允許范圍系數(shù)允許范圍波動(dòng)對計(jì)劃有影響波動(dòng)對計(jì)劃有影響生產(chǎn)計(jì)劃應(yīng)重新制訂：如將生產(chǎn)計(jì)劃應(yīng)重新制訂：如將x3的系數(shù)改為的系數(shù)改為39.6計(jì)計(jì)算，會(huì)發(fā)現(xiàn)結(jié)果有很大變化。算，會(huì)發(fā)現(xiàn)結(jié)果有很大變化。 第17頁/共93頁第十八頁，共93頁。4.2 自來水輸送自來水輸送(sh sn)與與貨機(jī)裝運(yùn)貨機(jī)裝運(yùn)生產(chǎn)生產(chǎn)(shngchn

27、)、生活物資從若干供應(yīng)點(diǎn)運(yùn)送到一些、生活物資從若干供應(yīng)點(diǎn)運(yùn)送到一些需求點(diǎn)，怎樣安排輸送方案使運(yùn)費(fèi)最小，或利潤最大；需求點(diǎn)，怎樣安排輸送方案使運(yùn)費(fèi)最小，或利潤最大；運(yùn)輸運(yùn)輸(ynsh)問題問題各種類型的貨物裝箱，由于受體積、重量等限制，如何各種類型的貨物裝箱，由于受體積、重量等限制，如何搭配裝載，使獲利最高，或裝箱數(shù)量最少。搭配裝載，使獲利最高，或裝箱數(shù)量最少。第18頁/共93頁第十九頁，共93頁。其他費(fèi)用其他費(fèi)用:450:450元元/ /千噸千噸(qin dn) (qin dn) 應(yīng)如何分配水庫供水量，公司應(yīng)如何分配水庫供水量，公司(n s)(n s)才能獲才能獲利最多？利最多？ 若水庫供水量

28、都提高一倍，公司利潤可增加若水庫供水量都提高一倍，公司利潤可增加(zngji)(zngji)到多少？到多少？ 元元/千噸千噸甲甲乙乙丙丙丁丁A160130220170B140130190150C190200230/引水管理費(fèi)引水管理費(fèi)收入：收入：900元元/千噸千噸 支支出出A：50B：60C：50甲：甲：30；50乙：乙：70；70丙：丙：10；20丁：?。?0；40水庫供水量水庫供水量(千噸千噸)小區(qū)基本用水量小區(qū)基本用水量(千噸千噸)小區(qū)額外用水量小區(qū)額外用水量(千噸千噸)（以天計(jì)）（以天計(jì)）第19頁/共93頁第二十頁，共93頁?？偣┧浚嚎偣┧浚?60確定確定(qudng)送水方案使

29、送水方案使利潤最大利潤最大問題問題(wnt)分分析析A：50B：60C：50甲：甲：30；50乙：乙：70；70丙：丙：10；20丁：?。?0；40 總需求量總需求量(300)每個(gè)水庫每個(gè)水庫(shuk)(shuk)最大供水量都最大供水量都提高一倍提高一倍利潤利潤(lrn) = 收入收入(900) 其它費(fèi)用其它費(fèi)用(450) 引水管理費(fèi)引水管理費(fèi)利潤利潤(元元/千噸千噸)甲甲乙乙丙丙丁丁A290320230280B310320260300C260250220/3332312423222114131211220250260300260320310280230320290 xxxxxxxxxxxZ

30、Max供應(yīng)供應(yīng)限制限制B, C 類似處理類似處理50:A14131211xxxx10014131211xxxx問題討論問題討論 確定送水方案確定送水方案使利潤最大使利潤最大需求約束可以不變需求約束可以不變第23頁/共93頁第二十四頁，共93頁。求解求解(qi (qi ji)ji) OBJECTIVE FUNCTION VALUE 1) 88700.00 VARIABLE VALUE REDUCED COST X11 0.000000 20.000000 X12 100.000000 0.000000 X13 0.000000 40.000000 X14 0.000000 20.000000 X

31、21 30.000000 0.000000 X22 40.000000 0.000000 X23 0.000000 10.000000 X24 50.000000 0.000000 X31 50.000000 0.000000 X32 0.000000 20.000000 X33 30.000000 0.000000 這類問題一般這類問題一般(ybn)稱為稱為“運(yùn)運(yùn)輸問題輸問題”(Transportation Problem)總利潤總利潤(lrn) 88700(lrn) 88700（元）（元） A(100)B(120)C(100)甲甲(30;50)乙乙(70;70)丙丙(10;20)丁丁(10

32、;40)4010050305030第24頁/共93頁第二十五頁，共93頁。如何裝運(yùn)如何裝運(yùn)(zhungyn)，使本次，使本次飛行獲利最飛行獲利最大？大？ 三個(gè)貨艙最大載重三個(gè)貨艙最大載重(zizhng)(噸噸),最大容積最大容積(米米3) 重量（噸）重量（噸）空間空間(米米3/噸）噸）利潤（元利潤（元/噸）噸）貨物貨物1184803100貨物貨物2156503800貨物貨物3235803500貨物貨物4123902850三個(gè)貨艙中實(shí)際載重必須與其最大三個(gè)貨艙中實(shí)際載重必須與其最大載載重成比例重成比例 前倉：前倉：10；6800中倉：中倉：16；8700后倉：后倉：8；5300飛機(jī)平飛機(jī)平衡衡第

33、25頁/共93頁第二十六頁，共93頁。決策決策(ju(jucc)變量變量 xij-第第i 種貨物種貨物(huw)裝入第裝入第j 個(gè)貨艙的重個(gè)貨艙的重量量(噸）噸）i=1,2,3,4, j=1,2,3 (分別代表前、中、后倉分別代表前、中、后倉)模型模型(mxn(mxng)g)假設(shè)假設(shè) 每種貨物可以分割到任意小；每種貨物可以分割到任意小；貨機(jī)裝運(yùn)貨機(jī)裝運(yùn)每種貨物可以在一個(gè)或多個(gè)貨艙中任意分布；每種貨物可以在一個(gè)或多個(gè)貨艙中任意分布；多種貨物可以混裝，并保證不留空隙；多種貨物可以混裝，并保證不留空隙； 模型建立模型建立 第26頁/共93頁第二十七頁，共93頁。貨艙貨艙(hucng)容積容積 目標(biāo)函

34、目標(biāo)函數(shù)數(shù)(hn(hnsh)sh)( (利潤利潤) )約束約束條件條件 )(2850)(3500)(3800)(3100434241333231232221131211xxxxxxxxxxxxZMax680039058065048041312111xxxx870039058065048042322212xxxx530039058065048043332313xxxx貨機(jī)貨機(jī)(hu (hu j)j)裝運(yùn)裝運(yùn)模型建立模型建立 貨貨艙艙重重量量 1041312111xxxx1642322212xxxx843332313xxxx10；680016；87008；5300 xij-第第i 種貨物裝入第種貨

35、物裝入第j 個(gè)貨艙的重量個(gè)貨艙的重量第27頁/共93頁第二十八頁，共93頁。約約束束條條件件平衡平衡(pnghng)要求要求 81610433323134232221241312111xxxxxxxxxxxx貨物貨物(huw)供應(yīng)供應(yīng) 18131211xxx15232221xxx23333231xxx12434241xxx貨機(jī)貨機(jī)(hu j)(hu j)裝運(yùn)裝運(yùn)模型建立模型建立 10；680016；87008；5300 xij-第第i 種貨物裝入第種貨物裝入第j 個(gè)貨艙的重量個(gè)貨艙的重量第28頁/共93頁第二十九頁，共93頁。OBJECTIVEFUNCTIONVALUE1)121515.8VA

36、RIABLEVALUEREDUCEDCOSTX110.000000400.000000X120.00000057.894737X130.000000400.000000X2110.0000000.000000X220.000000239.473679X235.0000000.000000X310.0000000.000000X3212.9473690.000000X333.0000000.000000X410.000000650.000000X423.0526320.000000X430.000000650.000000貨物貨物(huw)2(huw)2：前倉：前倉10,10,后后倉倉5 5；

37、貨物貨物(huw)3: (huw)3: 中倉中倉13, 13, 后倉后倉3 3；貨物；貨物(huw)4: (huw)4: 中倉中倉3 3。貨機(jī)貨機(jī)(hu (hu j)j)裝運(yùn)裝運(yùn)模型模型(mxn(mxng)g)求解求解 最大利潤約最大利潤約121516元元貨物貨物供應(yīng)點(diǎn)供應(yīng)點(diǎn)貨艙貨艙需求點(diǎn)需求點(diǎn)平衡要求平衡要求運(yùn)輸運(yùn)輸問題問題運(yùn)輸問題的擴(kuò)展運(yùn)輸問題的擴(kuò)展第29頁/共93頁第三十頁，共93頁。 如果生產(chǎn)某一類型汽車如果生產(chǎn)某一類型汽車(qch)(qch)，則至少要生產(chǎn)，則至少要生產(chǎn)8080輛，輛， 那么最優(yōu)的生產(chǎn)計(jì)劃應(yīng)作何改變？那么最優(yōu)的生產(chǎn)計(jì)劃應(yīng)作何改變？汽車廠生產(chǎn)三種汽車廠生產(chǎn)三種(sn z

38、hn)類型的汽車，已知各類型每類型的汽車，已知各類型每輛車對鋼材、勞動(dòng)時(shí)間的需求，利潤及工廠每月的現(xiàn)有輛車對鋼材、勞動(dòng)時(shí)間的需求，利潤及工廠每月的現(xiàn)有量。量。 小型小型 中型中型 大型大型 現(xiàn)有量現(xiàn)有量鋼材（噸）鋼材（噸） 1.5 3 5 600勞動(dòng)時(shí)間（小時(shí)）勞動(dòng)時(shí)間（小時(shí)） 280 250 400 60000利潤（萬元）利潤（萬元） 2 3 4 制訂月生產(chǎn)計(jì)劃，使工廠的利潤最大。制訂月生產(chǎn)計(jì)劃，使工廠的利潤最大。4.3 汽車生產(chǎn)與原油采購汽車生產(chǎn)與原油采購第30頁/共93頁第三十一頁，共93頁。設(shè)每月生產(chǎn)小、中、大型汽設(shè)每月生產(chǎn)小、中、大型汽車的數(shù)量車的數(shù)量(shling)(shling)

39、分別分別為為x1, x2, x3x1, x2, x3321432xxxzMax600535 . 1.321xxxts60000400250280321xxx0,321xxx汽車廠生產(chǎn)汽車廠生產(chǎn)(shngchn)(shngchn)計(jì)劃計(jì)劃 模型模型(mxn(mxng)g)建立建立 小型小型 中型中型 大型大型 現(xiàn)有現(xiàn)有量量鋼材鋼材 1.5 3 5 600時(shí)間時(shí)間 280 250 400 60000利潤利潤 2 3 4 線線性性規(guī)規(guī)劃劃模模型型(LP)第31頁/共93頁第三十二頁，共93頁。模型模型(m(mxnxng)g)求求解解 3） 模型中增加條件：模型中增加條件：x1, x2, x3 均為整

40、數(shù)，重新均為整數(shù)，重新(chngxn)求解。求解。 OBJECTIVEFUNCTIONVALUE1)632.2581VARIABLEVALUEREDUCEDCOSTX164.5161290.000000X2167.7419280.000000X30.0000000.946237ROWSLACKORSURPLUSDUALPRICES2)0.0000000.7311833)0.0000000.003226結(jié)果結(jié)果(ji gu)為為小數(shù)，怎么辦？小數(shù)，怎么辦？1）舍去小數(shù)：?。┥崛バ?shù)：取x1=64，x2=167，算出目標(biāo)函數(shù)值，算出目標(biāo)函數(shù)值z=629，與，與LP最優(yōu)值最優(yōu)值632.2581相差不

41、大。相差不大。2）試探：如取）試探：如取x1=65，x2=167；x1=64，x2=168等，計(jì)算函數(shù)值等，計(jì)算函數(shù)值z，通過比較可能得到更優(yōu)的解。通過比較可能得到更優(yōu)的解。 但必須檢驗(yàn)它們是否滿足約束條件。為什么？但必須檢驗(yàn)它們是否滿足約束條件。為什么？第32頁/共93頁第三十三頁，共93頁。IP可用可用LINDO直接直接(zhji)求解求解整數(shù)整數(shù)(zhngsh)(zhngsh)規(guī)劃規(guī)劃(Integer (Integer Programming,Programming,簡記簡記IP)IP)“gin 3”表示表示(biosh)“前前3個(gè)變個(gè)變量為整數(shù)量為整數(shù)”，等價(jià)于：，等價(jià)于：gin x1

42、gin x2gin x3 IP 的最優(yōu)解的最優(yōu)解x1=64，x2=168，x3=0，最優(yōu)值，最優(yōu)值z=632 max2x1+3x2+4x3st1.5x1+3x2+5x3600280 x1+250 x2+400 x360000endgin3OBJECTIVEFUNCTIONVALUE1)632.0000VARIABLEVALUEREDUCEDCOSTX164.000000-2.000000X2168.000000-3.000000X30.000000-4.000000321432xxxzMax600535 . 1.321xxxts60000400250280321xxx為非負(fù)整數(shù)321,xxx模

43、型求解模型求解 IP 結(jié)果輸出結(jié)果輸出第33頁/共93頁第三十四頁，共93頁。其中其中3 3個(gè)子模型應(yīng)去掉，然后逐一個(gè)子模型應(yīng)去掉，然后逐一求解，比較求解，比較(bjio)(bjio)目標(biāo)函數(shù)值，目標(biāo)函數(shù)值，再加上整數(shù)約束，得最優(yōu)解：再加上整數(shù)約束，得最優(yōu)解：80, 0, 0321xxx0,80, 0321xxx80,80, 0321xxx0, 0,80321xxx0,80,80321xxx80, 0,80321xxx80,80,80321xxx0,321xxx方法方法1：分解：分解(fnji)為為8個(gè)個(gè)LP子子模型模型 汽車廠生產(chǎn)汽車廠生產(chǎn)(shngchn)(shngchn)計(jì)計(jì)劃劃 若生產(chǎn)

44、某類汽車，則至少生產(chǎn)若生產(chǎn)某類汽車，則至少生產(chǎn)8080輛，求生產(chǎn)計(jì)劃。輛，求生產(chǎn)計(jì)劃。321432xxxzMax600535 . 1.321xxxts60000400250280321xxxx1, ,x2, x3=0 或或 80 x1=80，x2= 150，x3=0，最優(yōu)值，最優(yōu)值z=610第34頁/共93頁第三十五頁，共93頁。LINDO中對中對0-1變量變量(binling)的限定：的限定：int y1int y2int y3 方法方法2：引入：引入0-1變量變量(binling)，化為整數(shù)，化為整數(shù)規(guī)劃規(guī)劃 M為大的正數(shù)為大的正數(shù)(zhngsh)，可取，可取1000 OBJECTIVEF

45、UNCTIONVALUE1)610.0000VARIABLEVALUEREDUCEDCOSTX180.000000-2.000000X2150.000000-3.000000X30.000000-4.000000Y11.0000000.000000Y21.0000000.000000Y30.0000000.000000 若生產(chǎn)某類汽車，則至少生產(chǎn)若生產(chǎn)某類汽車，則至少生產(chǎn)8080輛，求生產(chǎn)計(jì)劃。輛，求生產(chǎn)計(jì)劃。x1=0 或 80 x2=0 或 80 x3=0 或 801 , 0,80,11111yyxMyx1 , 0,80,22222yyxMyx1 , 0,80,33333yyxMyx最優(yōu)解同

46、前最優(yōu)解同前 第35頁/共93頁第三十六頁，共93頁。NLP雖然可用現(xiàn)成的數(shù)學(xué)軟件求解雖然可用現(xiàn)成的數(shù)學(xué)軟件求解(qi ji)(如如LINGO, MATLAB)，但是其結(jié)果常依賴于初值的選擇。，但是其結(jié)果常依賴于初值的選擇。 方法方法(fngf)3：化為非線：化為非線性規(guī)劃性規(guī)劃 非線性規(guī)劃非線性規(guī)劃(guhu)(guhu)（Non- Linear ProgrammingNon- Linear Programming，簡記，簡記NLPNLP） 實(shí)踐表明，本例僅當(dāng)初值非常接近上面方法算出實(shí)踐表明，本例僅當(dāng)初值非常接近上面方法算出的最優(yōu)解時(shí)，才能得到正確的結(jié)果。的最優(yōu)解時(shí)，才能得到正確的結(jié)果。 若

47、生產(chǎn)某類汽車，則至少生產(chǎn)若生產(chǎn)某類汽車，則至少生產(chǎn)8080輛，求生產(chǎn)計(jì)劃。輛，求生產(chǎn)計(jì)劃。 x1=0 或 80 x2=0 或 80 x3=0 或 800)80(11xx0)80(22xx0)80(33xx第36頁/共93頁第三十七頁，共93頁。應(yīng)如何安排原油的采購應(yīng)如何安排原油的采購(cigu)(cigu)和加工和加工 ？ 市場上可買到不超過市場上可買到不超過15001500噸的原油噸的原油(yunyu)A(yunyu)A： 購買量不超過購買量不超過500500噸時(shí)的單價(jià)為噸時(shí)的單價(jià)為1000010000元元/ /噸；噸； 購買量超過購買量超過500500噸但不超過噸但不超過10001000噸

48、時(shí)，超過噸時(shí)，超過500500噸的噸的 部分部分80008000元元/ /噸；噸； 購買量超過購買量超過10001000噸時(shí)，超過噸時(shí)，超過10001000噸的部分噸的部分60006000元元/ /噸。噸。 售價(jià)售價(jià)4800元元/噸噸 售價(jià)售價(jià)5600元元/噸噸庫存庫存500噸噸 庫存庫存1000噸噸 汽油甲汽油甲(A 50%) 原油原油A 原油原油B 汽油乙汽油乙 (A 60%) 第37頁/共93頁第三十八頁，共93頁。決策決策(ju(jucc)變量變量 目標(biāo)目標(biāo)(mb(mbio)io)函數(shù)函數(shù)問題問題(w(wnt)nt)分析分析 利潤：銷售汽油的收入利潤：銷售汽油的收入 - - 購買原油購

49、買原油A的支出的支出 難點(diǎn)：原油難點(diǎn)：原油A的購價(jià)與購買量的關(guān)系較復(fù)雜的購價(jià)與購買量的關(guān)系較復(fù)雜)()(6 . 5)( 8 . 422122111xcxxxxzMax甲甲(A 50%) A B 乙乙(A 60%) 購買購買xx11x12x21x224.8千元千元/噸噸 5.6千元千元/噸噸原油原油A的購買量的購買量, ,原油原油A, B生產(chǎn)生產(chǎn)汽油汽油甲甲,乙的數(shù)量乙的數(shù)量c(x) 購買原油購買原油A的支出的支出利潤利潤(千元千元)c(x)如何表述？如何表述？第38頁/共93頁第三十九頁，共93頁。原油原油(yunyu)供應(yīng)供應(yīng) 約束約束條件條件xxx500121110002221 xx150

50、0 x500)1(1000 300061000)(500 1000 8500)(0 10)(xxxxxxxc x 500噸單價(jià)噸單價(jià)(dnji)為為10千元千元/噸；噸； 500噸噸 x 1000噸，超過噸，超過500噸的噸的8千元千元/噸；噸；1000噸噸 x 1500噸，超過噸，超過1000噸的噸的6千元千元/噸。噸。 目標(biāo)目標(biāo)(m(mbibio)o)函函數(shù)數(shù)購買購買x A B x11x12x21x22庫存庫存500噸噸 庫存庫存1000噸噸 第39頁/共93頁第四十頁，共93頁。 目標(biāo)函數(shù)中目標(biāo)函數(shù)中c(x)不是線性函數(shù)，是非線性規(guī)劃；不是線性函數(shù)，是非線性規(guī)劃； 對于用分段對于用分段(

51、fn dun)函數(shù)定義的函數(shù)定義的c(x)，一般的非線性規(guī)劃，一般的非線性規(guī)劃軟件也難以輸入和求解；軟件也難以輸入和求解； 想辦法將模型化簡，用現(xiàn)成的軟件求解。想辦法將模型化簡，用現(xiàn)成的軟件求解。 汽油含原油汽油含原油(yunyu)A的的比例限制比例限制 5 . 0211111 xxx6 . 0221212 xxx2111xx 221232xx 約束約束條件條件甲甲(A 50%) A B 乙乙(A 60%) x11x12x21x22第40頁/共93頁第四十一頁，共93頁。x1 , x2 , x3 以價(jià)格以價(jià)格(jig)10, 8, 6(千元千元/噸噸)采購采購A的噸數(shù)的噸數(shù)目標(biāo)目標(biāo)(m(mbi

52、bio)o)函函數(shù)數(shù) 只有只有(zhyu)(zhyu)當(dāng)以當(dāng)以1010千元千元/ /噸的價(jià)格購買噸的價(jià)格購買x1=500(x1=500(噸噸) )時(shí)，才時(shí)，才能以能以8 8千元千元/ /噸的價(jià)格購買噸的價(jià)格購買x2x2方法方法1 )6810()( 6 . 5)( 8 . 432122122111xxxxxxxzMax0)500(32xx500,0321xxx非線性規(guī)劃模型非線性規(guī)劃模型，可以用，可以用LINGO求解求解模型求解模型求解x= x1+x2+x3, c(x) = 10 x1+8x2+6x3 500噸噸 x 1000噸，超過噸，超過500噸的噸的8千千元元/ /噸噸增加約增加約束束0)

53、500(21xxx= x1+x2+x3, c(x) = 10 x1+8x2+6x3 第41頁/共93頁第四十二頁，共93頁。方法方法(fngf)1：LINGO求解求解Model:Max=4.8*x11+4.8*x21+5.6*x12+5.6*x22-10*x1-8*x2-6*x3;x11+x12x+500;x21+x220;2*x12-3*x220;x=x1+x2+x3;(x1-500)*x2=0;(x2-500)*x3=0;x1500;x2500;x30;x110;x120;x210;x220;x10;x20;x30;endObjectivevalue:4800.000VariableVal

54、ueReducedCostX11500.00000.0000000E+00X 2 1 5 0 0 . 0 0 0 00.0000000E+00X 1 2 0 . 0 0 0 0 0 0 0 E + 0 00.0000000E+00X220.0000000E+000.0000000E+00X10.1021405E-1310.00000X20.0000000E+008.000000X30.0000000E+006.000000X0.0000000E+000.0000000E+00LINGO得到得到(d do)的是局部最優(yōu)解，的是局部最優(yōu)解，還能得到還能得到(d do)更好的解嗎？更好的解嗎？ 用庫

55、存用庫存(kcn)(kcn)的的500500噸原油噸原油A A、500500噸原油噸原油B B生產(chǎn)汽油甲，不購買新的生產(chǎn)汽油甲，不購買新的原油原油A A，利潤為，利潤為4,8004,800千元。千元。 第42頁/共93頁第四十三頁，共93頁。y1, y2 , y3=1 以價(jià)格以價(jià)格(jig)10, 8, 6(千元千元/噸噸)采購采購A增增加加(zngji)約約束束方法方法(fng(fngf)2 f)2 0-1線性規(guī)劃模型線性規(guī)劃模型，可用，可用LINDO求解求解112500500yxy223500500yxy33500yx y1, ,y2, ,y3=0或或1OBJECTIVEFUNCTIONV

56、ALUE1)5000.000VARIABLEVALUEREDUCEDCOSTY 1 1 . 0 0 0 0 0 00.000000Y21.0000002200.000000Y31.0000001200.000000X 1 1 0 . 0 0 0 0 0 00.800000X210.0000000.800000X121500.0000000.000000X221000.0000000.000000X1500.0000000.000000X2500.0000000.000000X 3 0 . 0 0 0 0 0 00.400000X1000.0000000.000000購買購買1000噸原油噸原油

57、A，與庫，與庫存的存的500噸原油噸原油A和和1000噸噸原油原油B一起，生產(chǎn)汽油一起，生產(chǎn)汽油乙，利潤為乙，利潤為5,000千元千元 。x1 , x2 , x3 以價(jià)格以價(jià)格10, 8, 6(千元千元/ /噸噸) )采購采購A的噸數(shù)的噸數(shù)y=0 x=0 x0 y=1優(yōu)于方法優(yōu)于方法1的結(jié)果的結(jié)果第43頁/共93頁第四十四頁，共93頁。b1 b2 b3 b4方法方法(fng(fngf)3 f)3 b1 x b2，x= z1b1+z2b2，z1+z2=1，z1, z2 0, c(x)= z1c(b1)+z2c(b2).c(x)x1200090005000050010001500b2 x b3，x

58、= z2b2+z3b3， z2+z3=1，z2, z3 0, c(x)= z2c(b2)+z3c(b3). b3 x b4，x= z3b3+z4b4，z3+z4=1，z3, z4 0, c(x)= z3c(b3)+z4c(b4). 500)1(1000 300061000)(500 1000 8500)(0 10)(xxxxxxxc 直接直接(zhji)處理處理分段線性函處理處理分段線性函數(shù)數(shù)c(x) 第44頁/共93頁第四十五頁，共93頁。IP模型，模型，LINDO求求解，得到解，得到(d do)的的結(jié)果與方法結(jié)果與方法2相同相同.處理分段線性函數(shù)處理分段線性函數(shù)(hnsh)，方法，方法3更

59、具一般性更具一般性44332211bzbzbzbzx)()()()()(44332211bczbczbczbczxcbkxbk+1yk=1,否則否則(fuz),yk=03432321211,yzyyzyyzyz)4 , 3 , 2 , 1(0, 14321kzzzzzk10, 1321321或yyyyyy方法方法3 bk x bk+1 , ,x= zkbk+z k+1 bk+1zk+zk+1 =1，zk, zk+1 0, c(x)= zkc(bk)+zk+1 c(bk+1 ).c(x)x1200090005000050010001500b1 b2 b3 b4對于對于k=1,2,3第45頁/共9

60、3頁第四十六頁，共93頁。分派分派(fnpi)問題問題4.4 接力接力(jil)隊(duì)選拔和選課策隊(duì)選拔和選課策略略若干項(xiàng)任務(wù)分給一些候選人來完成，每人的專長不同，完成每若干項(xiàng)任務(wù)分給一些候選人來完成，每人的專長不同，完成每項(xiàng)任務(wù)取得項(xiàng)任務(wù)取得(qd)的效益或需要的資源就不同，如何分派任務(wù)使的效益或需要的資源就不同，如何分派任務(wù)使獲得的總效益最大，或付出的總資源最少。獲得的總效益最大，或付出的總資源最少。若干種策略供選擇，不同的策略得到的收益或付出的成本若干種策略供選擇，不同的策略得到的收益或付出的成本不同，各個(gè)策略之間有相互制約關(guān)系，如何在滿足一定條不同，各個(gè)策略之間有相互制約關(guān)系，如何在滿足一