數(shù)學(xué)建模規(guī)劃問(wèn)題的經(jīng)典案例(PPT)

1、建立優(yōu)化模型的一般步驟建立優(yōu)化模型的一般步驟1.1.確定決策變量確定決策變量2.2.確定目標(biāo)函數(shù)的表達(dá)式確定目標(biāo)函數(shù)的表達(dá)式3.3.尋找約束條件尋找約束條件例例1 1：設(shè)某廠生產(chǎn)電腦和手機(jī)兩種產(chǎn)品，這兩種產(chǎn)品的生產(chǎn)需要設(shè)某廠生產(chǎn)電腦和手機(jī)兩種產(chǎn)品，這兩種產(chǎn)品的生產(chǎn)需要逐次經(jīng)過(guò)兩條裝配線進(jìn)行裝配。電腦在第一條裝配線每臺(tái)需要逐次經(jīng)過(guò)兩條裝配線進(jìn)行裝配。電腦在第一條裝配線每臺(tái)需要2 2小時(shí)，在第二條裝配線每臺(tái)需要小時(shí)，在第二條裝配線每臺(tái)需要3 3小時(shí)；手機(jī)在第一條裝配線每小時(shí)；手機(jī)在第一條裝配線每臺(tái)需要臺(tái)需要4 4小時(shí)，在第二條裝配線每臺(tái)需要小時(shí)，在第二條裝配線每臺(tái)需要1 1小時(shí)。第一條裝配線每小時(shí)

2、。第一條裝配線每天有天有8080個(gè)可用工時(shí)，第一條裝配線每天有個(gè)可用工時(shí)，第一條裝配線每天有6060個(gè)可用工時(shí)，電腦和個(gè)可用工時(shí)，電腦和手機(jī)每臺(tái)的利潤(rùn)分別為手機(jī)每臺(tái)的利潤(rùn)分別為100100元和元和8080元。問(wèn)怎樣制定生產(chǎn)計(jì)劃？元。問(wèn)怎樣制定生產(chǎn)計(jì)劃？分析：分析： 目標(biāo)是利潤(rùn)目標(biāo)是利潤(rùn)L；而利潤(rùn)是由電腦的產(chǎn)量；而利潤(rùn)是由電腦的產(chǎn)量x和手機(jī)的產(chǎn)量和手機(jī)的產(chǎn)量y決定決定yxL80100 2.4 案例案例假設(shè)：假設(shè)：1 1、兩種產(chǎn)品的銷量不受限制、兩種產(chǎn)品的銷量不受限制2 2、原材料供應(yīng)不受限制、原材料供應(yīng)不受限制約束條件：約束條件：裝配線裝配線1 1的工時(shí)限制的工時(shí)限制裝配線裝配線2 2的工時(shí)限制

3、的工時(shí)限制8042yx603 yx0 , 0 yx變量約束變量約束建立模型建立模型yxL80100max 0 ,06038042 s.t.yxyxyx模型求解：模型求解：8042 yx603 yxcyx 801001243657例例2 2：最短路線問(wèn)題的數(shù)學(xué)建模實(shí)例最短路線問(wèn)題的數(shù)學(xué)建模實(shí)例1415121013209128810變量變量 否則否則的路通過(guò)的路通過(guò)到到從從01jixij模型模型)(1210898131012151420min6757564745363425241312總路程總路程xxxxxxxxxxxz . .ts.111312出發(fā)的一輛車出發(fā)的一輛車考慮從節(jié)點(diǎn)考慮從節(jié)點(diǎn) xx;

4、 0252412 xxx; 047453424 xxxx; 0675636 xxx1675747 xxx; 057564525 xxxx; 0363413 xxx. 7 , 2 , 1,10 ji，xij或或取取12436579810例例3 3：最短路線問(wèn)題算例最短路線問(wèn)題算例1001502001751254002503002002751752752003501501009-101008-101506-9-103005-8-104007-8-102752-6-106004-6-105003-5-106001-4-10650最短路線為最短路線為:1-4-6-9-10，長(zhǎng)度：，長(zhǎng)度：650沿該弧的

5、運(yùn)量沿該弧的運(yùn)量到到表示節(jié)點(diǎn)表示節(jié)點(diǎn)設(shè)設(shè)jixij12436571415121013209128810變量變量模型模型例例4 4：最小費(fèi)用流問(wèn)題最小費(fèi)用流問(wèn)題)(1210898131012151420min6757564745363425241312總運(yùn)費(fèi)總運(yùn)費(fèi)xxxxxxxxxxxz . .ts.1312考慮從產(chǎn)地出發(fā)的運(yùn)量考慮從產(chǎn)地出發(fā)的運(yùn)量Qxx ; 0252412 xxx; 047453424 xxxx; 0675636 xxxQxxx 675747; 057564525 xxxx; 0363413 xxx. 7 , 2 , 1,0 ji，xij例例5 5：最大流量問(wèn)題最大流量問(wèn)題變量

6、變量。網(wǎng)絡(luò)的最大通車量網(wǎng)絡(luò)的最大通車量求通過(guò)該公路求通過(guò)該公路.1沿該弧的車流量沿該弧的車流量到到為從為從發(fā)出的車流量發(fā)出的車流量表示從節(jié)點(diǎn)表示從節(jié)點(diǎn)用用jixvij模型模型vmax. .ts.1312vxx ; 0252412 xxx; 047453424 xxxx; 0675636 xxxvxxx 675747; 057564525 xxxx; 0363413 xxx0. v各段上的流量限制各段上的流量限制12436571415121013209128810模型模型vmax. .ts.1312vxx ; 0252412 xxx; 047453424 xxxx; 0675636 xxxvxx

7、x 675747; 057564525 xxxx; 0363413 xxx0. v各段上的流量限制各段上的流量限制工廠定期訂購(gòu)原料，存入倉(cāng)庫(kù)供生產(chǎn)之用；工廠定期訂購(gòu)原料，存入倉(cāng)庫(kù)供生產(chǎn)之用；車間一次加工出一批零件，供裝配線每天生產(chǎn)之用；車間一次加工出一批零件，供裝配線每天生產(chǎn)之用；商店成批購(gòu)進(jìn)各種商品，放在貨柜里以備零售；商店成批購(gòu)進(jìn)各種商品，放在貨柜里以備零售；水庫(kù)在雨季蓄水，用于旱季的灌溉和發(fā)電。水庫(kù)在雨季蓄水，用于旱季的灌溉和發(fā)電。存貯模型存貯模型存貯量多少合適？存貯量多少合適？存貯量過(guò)大，存貯費(fèi)用太高；存貯量太小，會(huì)導(dǎo)致一存貯量過(guò)大，存貯費(fèi)用太高；存貯量太小，會(huì)導(dǎo)致一次性訂購(gòu)費(fèi)用增加，

8、或不能及時(shí)滿足需求。次性訂購(gòu)費(fèi)用增加，或不能及時(shí)滿足需求。問(wèn)題問(wèn)題1 1 不允許缺貨的存貯模型不允許缺貨的存貯模型 配件廠為裝配線生產(chǎn)若干種部件，輪換生產(chǎn)不配件廠為裝配線生產(chǎn)若干種部件，輪換生產(chǎn)不同的部件時(shí)因更換設(shè)備要付生產(chǎn)準(zhǔn)備費(fèi)（與生產(chǎn)數(shù)同的部件時(shí)因更換設(shè)備要付生產(chǎn)準(zhǔn)備費(fèi)（與生產(chǎn)數(shù)量無(wú)關(guān)），同一部件的產(chǎn)量大于需求時(shí)因積壓資金、量無(wú)關(guān)），同一部件的產(chǎn)量大于需求時(shí)因積壓資金、占用倉(cāng)庫(kù)要付存貯費(fèi)。今已知某一部件的日需求量占用倉(cāng)庫(kù)要付存貯費(fèi)。今已知某一部件的日需求量100件，生產(chǎn)準(zhǔn)備費(fèi)件，生產(chǎn)準(zhǔn)備費(fèi)5000元，存貯費(fèi)每日每件元，存貯費(fèi)每日每件1元。元。如果生產(chǎn)能力遠(yuǎn)大于需求，并且不允許出現(xiàn)缺貨，如果

9、生產(chǎn)能力遠(yuǎn)大于需求，并且不允許出現(xiàn)缺貨，試安排該產(chǎn)品的生產(chǎn)計(jì)劃，即多少天生產(chǎn)一次（稱試安排該產(chǎn)品的生產(chǎn)計(jì)劃，即多少天生產(chǎn)一次（稱為生產(chǎn)周期），每次產(chǎn)量多少，可使總費(fèi)用最小。為生產(chǎn)周期），每次產(chǎn)量多少，可使總費(fèi)用最小。問(wèn)題分析問(wèn)題分析若每天生產(chǎn)一次，每次若每天生產(chǎn)一次，每次100件，無(wú)存貯費(fèi)，生產(chǎn)件，無(wú)存貯費(fèi)，生產(chǎn)準(zhǔn)備費(fèi)準(zhǔn)備費(fèi)5000元，每天費(fèi)用元，每天費(fèi)用5000元；元；若若10天生產(chǎn)一次，每次天生產(chǎn)一次，每次1000件，存貯費(fèi)件，存貯費(fèi)900+800+100=4500元，生產(chǎn)準(zhǔn)備費(fèi)元，生產(chǎn)準(zhǔn)備費(fèi)5000元，元，總計(jì)總計(jì)9500元，平均每天費(fèi)用元，平均每天費(fèi)用950元；元；若若50天生產(chǎn)一次，

10、每次天生產(chǎn)一次，每次5000件，存貯費(fèi)件，存貯費(fèi)4900+4800+100=122500元，生產(chǎn)準(zhǔn)備費(fèi)元，生產(chǎn)準(zhǔn)備費(fèi)5000元，總計(jì)元，總計(jì)127500元，平均每天費(fèi)用元，平均每天費(fèi)用2550元；元；尋找生產(chǎn)周期、產(chǎn)量、需求量、生產(chǎn)準(zhǔn)備費(fèi)和尋找生產(chǎn)周期、產(chǎn)量、需求量、生產(chǎn)準(zhǔn)備費(fèi)和存貯費(fèi)之間的關(guān)系，使每天的費(fèi)用最少。存貯費(fèi)之間的關(guān)系，使每天的費(fèi)用最少。模型假設(shè)模型假設(shè)1 連續(xù)化，即設(shè)生產(chǎn)周期連續(xù)化，即設(shè)生產(chǎn)周期 T 和產(chǎn)量和產(chǎn)量 Q 均為連續(xù)量；均為連續(xù)量；2 產(chǎn)品每日的需求量為常數(shù)產(chǎn)品每日的需求量為常數(shù) r ；3 每次生產(chǎn)準(zhǔn)備費(fèi)每次生產(chǎn)準(zhǔn)備費(fèi) C1，每日每件產(chǎn)品存貯費(fèi)，每日每件產(chǎn)品存貯費(fèi) C2

11、；4 生產(chǎn)能力為無(wú)限大（相對(duì)于需求量），當(dāng)存貯量生產(chǎn)能力為無(wú)限大（相對(duì)于需求量），當(dāng)存貯量 降到零時(shí)，降到零時(shí)，Q件產(chǎn)品立即生產(chǎn)出來(lái)供給需求，即件產(chǎn)品立即生產(chǎn)出來(lái)供給需求，即 不允許缺貨。不允許缺貨。模型建立模型建立總費(fèi)用與變量的關(guān)系總費(fèi)用與變量的關(guān)系總費(fèi)用總費(fèi)用=生產(chǎn)準(zhǔn)備費(fèi)生產(chǎn)準(zhǔn)備費(fèi)+存貯費(fèi)存貯費(fèi)存貯費(fèi)存貯費(fèi)=存貯單價(jià)存貯單價(jià)*存貯量存貯量存貯量存貯量=？設(shè)設(shè) t 時(shí)刻的存貯量為時(shí)刻的存貯量為 q(t) ，t = 0時(shí)生產(chǎn)時(shí)生產(chǎn) Q 件，件，存貯量存貯量 q(0) = Q , q(t) 以需求速率以需求速率 r 線性遞減，線性遞減，直至直至q(T) = 0，如圖。，如圖。q(t) = Q-

12、r t， Q = r T 。otqQTrA不允許缺貨模型的存貯量不允許缺貨模型的存貯量q(t) 存貯量的計(jì)算存貯量的計(jì)算一個(gè)周期內(nèi)存貯量一個(gè)周期內(nèi)存貯量dttqT0)(一個(gè)周期內(nèi)存貯費(fèi)一個(gè)周期內(nèi)存貯費(fèi)dttqcT02)(2QT (A的面積的面積)一個(gè)周期的總費(fèi)用一個(gè)周期的總費(fèi)用dttqccCT 021)(2222121rTccQTcc 每天平均費(fèi)用每天平均費(fèi)用2)(21rTcTcTCTC 2)(min 21rTcTcTCT 滿足滿足求求模型求解模型求解用微分法用微分法02)(221 rcTcTCrccT212 212crcrTQ 每天平均最小費(fèi)用每天平均最小費(fèi)用rccC212 思考思考1 建模

13、中未考慮生產(chǎn)費(fèi)用（這應(yīng)是最大一筆費(fèi)建模中未考慮生產(chǎn)費(fèi)用（這應(yīng)是最大一筆費(fèi) 用），在什么情況下才可以不考慮它？用），在什么情況下才可以不考慮它？2 建模時(shí)作了建模時(shí)作了“生產(chǎn)能力無(wú)限大生產(chǎn)能力無(wú)限大”的簡(jiǎn)化假設(shè)，的簡(jiǎn)化假設(shè)，如如 果生產(chǎn)能力有限，是大于需求量的一個(gè)常果生產(chǎn)能力有限，是大于需求量的一個(gè)常數(shù)，如何建模？數(shù)，如何建模？結(jié)果解釋結(jié)果解釋rccT212 212crcrTQ rccC212 當(dāng)準(zhǔn)備費(fèi)當(dāng)準(zhǔn)備費(fèi) c1 增加時(shí)，生產(chǎn)周期和產(chǎn)量都變大；增加時(shí)，生產(chǎn)周期和產(chǎn)量都變大；當(dāng)存貯費(fèi)當(dāng)存貯費(fèi) c2 增加時(shí)，生產(chǎn)周期和產(chǎn)量都變??；增加時(shí)，生產(chǎn)周期和產(chǎn)量都變?。划?dāng)日需求費(fèi)當(dāng)日需求費(fèi) r 增加時(shí)，生

14、產(chǎn)周期變小而產(chǎn)量變大。增加時(shí)，生產(chǎn)周期變小而產(chǎn)量變大。這些定性結(jié)果符合常識(shí)，而定量關(guān)系（平方根，系這些定性結(jié)果符合常識(shí)，而定量關(guān)系（平方根，系數(shù)數(shù)2 等）憑常識(shí)是無(wú)法得出的，只能由數(shù)學(xué)建模得等）憑常識(shí)是無(wú)法得出的，只能由數(shù)學(xué)建模得到。到。rccT212 rccC212 1000 10 ,100 , 1 ,5000 21 CTrcc，得得當(dāng)當(dāng)這里得到的費(fèi)用這里得到的費(fèi)用C與前面計(jì)算得與前面計(jì)算得950元有微小差別，元有微小差別，你能解釋嗎？你能解釋嗎？在本例中在本例中敏感性分析敏感性分析討論參數(shù)討論參數(shù)rcc, 21有微小變化時(shí)對(duì)生產(chǎn)周期有微小變化時(shí)對(duì)生產(chǎn)周期T 影響。影響。由相對(duì)變化量衡量對(duì)參

15、數(shù)的敏感程度。由相對(duì)變化量衡量對(duì)參數(shù)的敏感程度。T 對(duì)對(duì)c1 的敏感程度記為的敏感程度記為),(1cTS111),(ccTTcTS TcdcdT11 Tcrccrc12122221 2121),(2 cTS21),( rTS意義是當(dāng)準(zhǔn)備費(fèi)增加意義是當(dāng)準(zhǔn)備費(fèi)增加1%時(shí)，生產(chǎn)周期增加時(shí)，生產(chǎn)周期增加0.5% ；而存貯費(fèi)增加而存貯費(fèi)增加1%時(shí)，生產(chǎn)周期減少時(shí)，生產(chǎn)周期減少0.5% ；日需求量增加日需求量增加1%時(shí)，生產(chǎn)周期減少時(shí)，生產(chǎn)周期減少0.5% 。21),(1 cTS21),(2 cTS21),( rTS當(dāng)當(dāng)rcc, 21有微小變化對(duì)生產(chǎn)周期影響不太大。有微小變化對(duì)生產(chǎn)周期影響不太大。模型假設(shè)

16、模型假設(shè)1 連續(xù)化，即設(shè)生產(chǎn)周期連續(xù)化，即設(shè)生產(chǎn)周期 T 和產(chǎn)量和產(chǎn)量 Q 均為連續(xù)量；均為連續(xù)量；2 產(chǎn)品每日的需求量為常數(shù)產(chǎn)品每日的需求量為常數(shù) r ；3 每次生產(chǎn)準(zhǔn)備費(fèi)每次生產(chǎn)準(zhǔn)備費(fèi) C1，每日每件產(chǎn)品存貯費(fèi)，每日每件產(chǎn)品存貯費(fèi) C2；4 生產(chǎn)能力為無(wú)限大（相對(duì)于需求量），允許缺生產(chǎn)能力為無(wú)限大（相對(duì)于需求量），允許缺 貨，每天每件產(chǎn)品缺貨損失費(fèi)貨，每天每件產(chǎn)品缺貨損失費(fèi)C3 ，但缺貨數(shù)量需，但缺貨數(shù)量需 在下次生產(chǎn)（訂貨）時(shí)補(bǔ)足。在下次生產(chǎn)（訂貨）時(shí)補(bǔ)足。問(wèn)題問(wèn)題2 允許缺貨的存貯模型允許缺貨的存貯模型模型建立模型建立總費(fèi)用總費(fèi)用=生產(chǎn)準(zhǔn)備費(fèi)生產(chǎn)準(zhǔn)備費(fèi)+存貯費(fèi)存貯費(fèi)+缺貨損失費(fèi)缺貨損失

17、費(fèi)存貯費(fèi)存貯費(fèi)=存貯單價(jià)存貯單價(jià)*存貯量存貯量缺貨損失費(fèi)缺貨損失費(fèi)=缺貨單價(jià)缺貨單價(jià)*缺貨量缺貨量存貯量存貯量=？，缺貨量？，缺貨量=？因存貯量不足造成缺貨，因此因存貯量不足造成缺貨，因此 q(t) 可取負(fù)值，可取負(fù)值， q(t) 以需求速率以需求速率 r 線性遞減，直至線性遞減，直至q(T1) = 0，如，如圖。圖。q(t) = Q-r t， Q = r T1 。otqQTrA允許缺貨模型的存貯量允許缺貨模型的存貯量q q( (t t) ) RT1B一個(gè)周期內(nèi)缺貨損失費(fèi)一個(gè)周期內(nèi)缺貨損失費(fèi)一個(gè)周期內(nèi)存貯費(fèi)一個(gè)周期內(nèi)存貯費(fèi)dttqcT 102)(212QTc 一個(gè)周期的總費(fèi)用一個(gè)周期的總費(fèi)用r

18、QrTcrQccC2)(223221 每天平均費(fèi)用每天平均費(fèi)用dttqcTT 1)(32)(13TTQrTc rQrTc2)(23 rQc222 rTQrTcrTQcTcQTC2)(2),(23221 ,滿足滿足求求QT模型求解模型求解用微分法用微分法 令令332212cccrccT 323212ccccrcQ 每天平均最小費(fèi)用每天平均最小費(fèi)用),(QTCC rTQrTcrTQcTcQTC2)(2),(min23221 0),( , 0),( QQTCTQTC每個(gè)周期的供貨量每個(gè)周期的供貨量TrR 332212cccrccrR 332ccc 與不允許缺貨模型相比較，有與不允許缺貨模型相比較，有

19、QRQQTT ,/ ,QRQQTT ,/ ,結(jié)果解釋結(jié)果解釋QRQQTT , , , 1 即允許缺貨時(shí)，即允許缺貨時(shí)，周期和供貨量增加，周期初的存貯量減少。周期和供貨量增加，周期初的存貯量減少。2）缺貨損失費(fèi)愈大，）缺貨損失費(fèi)愈大， 愈小，愈小， 愈接近愈接近 ， 愈接近愈接近 。1）TTRQ , Q332ccc 3），時(shí)，時(shí)，當(dāng)當(dāng)13 cQRQQTT , ,不允許缺貨模型可視為允許缺貨模型的特例。不允許缺貨模型可視為允許缺貨模型的特例。企業(yè)生產(chǎn)計(jì)劃企業(yè)生產(chǎn)計(jì)劃奶制品的生產(chǎn)與銷售奶制品的生產(chǎn)與銷售 空間層次空間層次工廠級(jí)：根據(jù)外部需求和內(nèi)部設(shè)備、人力、原料等工廠級(jí)：根據(jù)外部需求和內(nèi)部設(shè)備、人力

20、、原料等條件，以最大利潤(rùn)為目標(biāo)制訂產(chǎn)品生產(chǎn)計(jì)劃；條件，以最大利潤(rùn)為目標(biāo)制訂產(chǎn)品生產(chǎn)計(jì)劃；車間級(jí)：根據(jù)生產(chǎn)計(jì)劃、工藝流程、資源約束及費(fèi)車間級(jí)：根據(jù)生產(chǎn)計(jì)劃、工藝流程、資源約束及費(fèi)用參數(shù)等，以最小成本為目標(biāo)制訂生產(chǎn)批量計(jì)劃。用參數(shù)等，以最小成本為目標(biāo)制訂生產(chǎn)批量計(jì)劃。時(shí)間層次時(shí)間層次若短時(shí)間內(nèi)外部需求和內(nèi)部資源等不隨時(shí)間變化，可若短時(shí)間內(nèi)外部需求和內(nèi)部資源等不隨時(shí)間變化，可制訂制訂單階段生產(chǎn)計(jì)劃單階段生產(chǎn)計(jì)劃，否則應(yīng)制訂多階段生產(chǎn)計(jì)劃。，否則應(yīng)制訂多階段生產(chǎn)計(jì)劃。本節(jié)課題本節(jié)課題 一奶制品加工廠用牛奶生產(chǎn)一奶制品加工廠用牛奶生產(chǎn)A1、A2兩種奶制品，一桶牛兩種奶制品，一桶牛奶可以在甲類設(shè)備上用奶可

21、以在甲類設(shè)備上用12小時(shí)加工成小時(shí)加工成3公斤公斤A1，或者在乙類設(shè)，或者在乙類設(shè)備上用備上用8個(gè)小時(shí)加工成個(gè)小時(shí)加工成4公斤公斤A2。根據(jù)市場(chǎng)需求，生產(chǎn)的。根據(jù)市場(chǎng)需求，生產(chǎn)的A1，A2全部都能售出，且每公斤全部都能售出，且每公斤A1獲利獲利24元，每公斤元，每公斤A2獲利獲利16元。元。現(xiàn)在加工廠每天能得到現(xiàn)在加工廠每天能得到50桶牛奶的供應(yīng)，每天正式工人總的勞桶牛奶的供應(yīng)，每天正式工人總的勞動(dòng)時(shí)間為動(dòng)時(shí)間為480小時(shí)，并且甲類設(shè)備每天之多能加工小時(shí)，并且甲類設(shè)備每天之多能加工100公斤公斤A1，乙類設(shè)備沒(méi)有加工能力限制。試為該廠制訂一個(gè)生產(chǎn)計(jì)劃，使乙類設(shè)備沒(méi)有加工能力限制。試為該廠制訂一

22、個(gè)生產(chǎn)計(jì)劃，使每天獲利最大，并進(jìn)一步討論一以下每天獲利最大，并進(jìn)一步討論一以下3個(gè)附加問(wèn)題：個(gè)附加問(wèn)題：例例1 加工奶制品的生產(chǎn)計(jì)劃加工奶制品的生產(chǎn)計(jì)劃 35元可買到元可買到1桶牛奶，買嗎？若買，每天最多買多少桶牛奶，買嗎？若買，每天最多買多少? 可聘用臨時(shí)工人，付出的工資最多是每小時(shí)幾元可聘用臨時(shí)工人，付出的工資最多是每小時(shí)幾元? A1的獲利增加到的獲利增加到 30元元/公斤，應(yīng)否改變生產(chǎn)計(jì)劃？公斤，應(yīng)否改變生產(chǎn)計(jì)劃？ 例例1 加工奶制品的生產(chǎn)計(jì)劃加工奶制品的生產(chǎn)計(jì)劃1桶桶牛奶牛奶 3公斤公斤A1 12小時(shí)小時(shí) 8小時(shí)小時(shí) 4公斤公斤A2 或或獲利獲利24元元/公斤公斤 獲利獲利16元元/公

23、斤公斤 50桶牛奶桶牛奶 時(shí)間時(shí)間480小時(shí)小時(shí) 至多加工至多加工100公斤公斤A1 制訂生產(chǎn)計(jì)劃，使每天獲利最大制訂生產(chǎn)計(jì)劃，使每天獲利最大 35元可買到元可買到1桶牛奶，買嗎？若買，每天最多買多少桶牛奶，買嗎？若買，每天最多買多少? 可聘用臨時(shí)工人，付出的工資最多是每小時(shí)幾元可聘用臨時(shí)工人，付出的工資最多是每小時(shí)幾元? A1的獲利增加到的獲利增加到 30元元/公斤，應(yīng)否改變生產(chǎn)計(jì)劃？公斤，應(yīng)否改變生產(chǎn)計(jì)劃？ 每天：每天：1桶桶牛奶牛奶 3公斤公斤A1 12小時(shí)小時(shí) 8小時(shí)小時(shí) 4公斤公斤A2 或或獲利獲利24元元/公斤公斤 獲利獲利16元元/公斤公斤 x1桶牛奶生產(chǎn)桶牛奶生產(chǎn)A1 x2桶牛

24、奶生產(chǎn)桶牛奶生產(chǎn)A2 獲利獲利 243x1 獲利獲利 164 x2 原料供應(yīng)原料供應(yīng) 5021 xx勞動(dòng)時(shí)間勞動(dòng)時(shí)間 48081221 xx加工能力加工能力 10031x決策變量決策變量 目標(biāo)函數(shù)目標(biāo)函數(shù) 216472xxzMax每天獲利每天獲利約束條件約束條件非負(fù)約束非負(fù)約束 0,21xx線性線性規(guī)劃規(guī)劃模型模型(LP)時(shí)間時(shí)間480小時(shí)小時(shí) 至多加工至多加工100公斤公斤A1 50桶牛奶桶牛奶 每天每天模型分析與假設(shè)模型分析與假設(shè) 比比例例性性 可可加加性性 連續(xù)性連續(xù)性 xi對(duì)目標(biāo)函數(shù)的對(duì)目標(biāo)函數(shù)的“貢獻(xiàn)貢獻(xiàn)”與與xi取值取值成正比成正比 xi對(duì)約束條件的對(duì)約束條件的“貢獻(xiàn)貢獻(xiàn)”與與xi

25、取值取值成正比成正比 xi對(duì)目標(biāo)函數(shù)的對(duì)目標(biāo)函數(shù)的“貢獻(xiàn)貢獻(xiàn)”與與xj取值取值無(wú)關(guān)無(wú)關(guān) xi對(duì)約束條件的對(duì)約束條件的“貢獻(xiàn)貢獻(xiàn)”與與xj取值取值無(wú)關(guān)無(wú)關(guān) xi取值連續(xù)取值連續(xù) A1,A2每公斤的獲利是與各每公斤的獲利是與各自產(chǎn)量無(wú)關(guān)的常數(shù)自產(chǎn)量無(wú)關(guān)的常數(shù)每桶牛奶加工出每桶牛奶加工出A1,A2的數(shù)量和的數(shù)量和時(shí)間是與各自產(chǎn)量無(wú)關(guān)的常數(shù)時(shí)間是與各自產(chǎn)量無(wú)關(guān)的常數(shù)A1,A2每公斤的獲利是與相每公斤的獲利是與相互產(chǎn)量無(wú)關(guān)的常數(shù)互產(chǎn)量無(wú)關(guān)的常數(shù)每桶牛奶加工出每桶牛奶加工出A1,A2的數(shù)量和的數(shù)量和時(shí)間是與相互產(chǎn)量無(wú)關(guān)的常數(shù)時(shí)間是與相互產(chǎn)量無(wú)關(guān)的常數(shù)加工加工A1,A2的牛奶桶數(shù)是實(shí)數(shù)的牛奶桶數(shù)是實(shí)數(shù) 線性

26、規(guī)劃模型線性規(guī)劃模型模型求解模型求解 圖解法圖解法 x1x20ABCDl1l2l3l4l55021 xx48081221 xx10031 x0,21 xx約約束束條條件件50:211 xxl480812:212 xxl1003:13 xl0:, 0:2514 xlxl216472xxzMax 目標(biāo)目標(biāo)函數(shù)函數(shù) Z=0Z=2400Z=3600z=c (常數(shù)常數(shù)) 等值線等值線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)解一定在凸多

27、邊最優(yōu)解一定在凸多邊形的某個(gè)頂點(diǎn)取得。形的某個(gè)頂點(diǎn)取得。 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 2.000000 4) 40.000000 0.000000 NO. ITERATIONS= 2模型求解模型求解 軟件實(shí)現(xiàn)軟件實(shí)現(xiàn) LINDO 6.1 max 72x1+64x2st2）x1

28、+x2503）12x1+8x24804）3x1100endDO RANGE (SENSITIVITY) ANALYSIS? No20桶牛奶生產(chǎn)桶牛奶生產(chǎn)A1, 30桶生產(chǎn)桶生產(chǎn)A2，利潤(rùn)，利潤(rùn)3360元。元。 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 2.000000 4) 40.0000

29、00 0.000000 NO. ITERATIONS= 2：結(jié)果解釋結(jié)果解釋 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 2.000000 4) 40.000000 0.000000 NO. ITERATIONS= 2原料無(wú)剩余原料無(wú)剩余時(shí)間無(wú)剩余時(shí)間無(wú)剩余加工能力剩余加工能力剩余40max

30、 72x1+64x2st2）x1+x2503）12x1+8x24804）3x1100end三三種種資資源源“資源資源” 剩余為零的約束為緊約束（有效約束）剩余為零的約束為緊約束（有效約束） 結(jié)果解釋結(jié)果解釋 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 2.000000 4) 40.00000

31、0 0.000000 NO. ITERATIONS= 2最優(yōu)解下最優(yōu)解下“資源資源”增加增加1單位時(shí)單位時(shí)“效益效益”的增的增量量 原料增加原料增加1單位單位, 利潤(rùn)增長(zhǎng)利潤(rùn)增長(zhǎng)48 時(shí)間增加時(shí)間增加1單位單位, 利潤(rùn)增長(zhǎng)利潤(rùn)增長(zhǎng)2 加工能力增長(zhǎng)不影響利潤(rùn)加工能力增長(zhǎng)不影響利潤(rùn)影子價(jià)格影子價(jià)格 35元可買到元可買到1桶牛奶，要買嗎？桶牛奶，要買嗎？35 48, 應(yīng)該買！應(yīng)該買！ 聘用臨時(shí)工人付出的工資最多每小時(shí)幾元？聘用臨時(shí)工人付出的工資最多每小時(shí)幾元？ 2元！元！RANGES IN WHICH THE BASIS IS UNCHANGED: OBJ COEFFICIENT RANGES VA

32、RIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE 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最優(yōu)解不變時(shí)目

33、標(biāo)函最優(yōu)解不變時(shí)目標(biāo)函數(shù)系數(shù)允許變化范圍數(shù)系數(shù)允許變化范圍 DO RANGE(SENSITIVITY) ANALYSIS? Yesx1系數(shù)范圍系數(shù)范圍(64,96) x2系數(shù)范圍系數(shù)范圍(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) 不變！不變！(約束條件不變約束條件不變)結(jié)果解釋結(jié)果解釋 RANGES IN WHICH THE BASIS IS UNCHANGED: OBJ COEFFICIENT RANGES VARIABLE CURRENT ALLOWAB

34、LE ALLOWABLE COEF INCREASE DECREASE 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í)約束

35、右端的允許變化范圍 原料最多增加原料最多增加10 時(shí)間最多增加時(shí)間最多增加53 35元可買到元可買到1桶牛奶，每天最多買多少？桶牛奶，每天最多買多少？最多買最多買10桶桶!(目標(biāo)函數(shù)不變目標(biāo)函數(shù)不變)例例2 奶制品的生產(chǎn)銷售計(jì)劃奶制品的生產(chǎn)銷售計(jì)劃 例例1給出的給出的A1、A2兩種奶制品的生產(chǎn)條件、利潤(rùn)、及兩種奶制品的生產(chǎn)條件、利潤(rùn)、及工廠的工廠的“資源資源”限制都不變，為增加工廠的獲利，開(kāi)限制都不變，為增加工廠的獲利，開(kāi)發(fā)了奶制品的深加工技術(shù)：用發(fā)了奶制品的深加工技術(shù)：用2小時(shí)和小時(shí)和3元加工費(fèi)可將元加工費(fèi)可將1公斤公斤A1加工成加工成0.8公斤的高級(jí)奶制品公斤的高級(jí)奶制品B1，也可將，也可

36、將1公斤公斤A2加工成加工成0.75公斤的高級(jí)奶制品公斤的高級(jí)奶制品B2，每公斤，每公斤B1能獲利能獲利44元，每公斤元，每公斤B2能獲利能獲利32元。試為該廠制定一個(gè)生產(chǎn)元。試為該廠制定一個(gè)生產(chǎn)銷售計(jì)劃，使每天的凈利潤(rùn)最大，并討論以下問(wèn)題：銷售計(jì)劃，使每天的凈利潤(rùn)最大，并討論以下問(wèn)題： 若投資若投資30元可增加元可增加1桶牛奶，投資桶牛奶，投資3元可增加元可增加1小時(shí)勞小時(shí)勞動(dòng)時(shí)間，應(yīng)否應(yīng)做這些投資？現(xiàn)每天投資動(dòng)時(shí)間，應(yīng)否應(yīng)做這些投資？現(xiàn)每天投資150元，可賺元，可賺回多少？回多少？ B1，B2的獲利經(jīng)常有的獲利經(jīng)常有10%的波動(dòng)，對(duì)定制的計(jì)劃有無(wú)的波動(dòng)，對(duì)定制的計(jì)劃有無(wú)影響？若每公斤影響？

37、若每公斤B1的獲利下降的獲利下降10，計(jì)劃應(yīng)該變化嗎？，計(jì)劃應(yīng)該變化嗎？例例2 奶制品的生產(chǎn)銷售計(jì)劃奶制品的生產(chǎn)銷售計(jì)劃 在例在例1基礎(chǔ)上深加工基礎(chǔ)上深加工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元元/千克千克 制訂生產(chǎn)計(jì)劃，使每天凈利潤(rùn)最大制訂生產(chǎn)計(jì)劃，使每天凈利潤(rùn)最大 50桶牛奶桶牛奶, 480小時(shí)小時(shí) 至多至多100公斤公斤A1 若投資若投資30元可增加元可增加1

38、桶牛奶，投資桶牛奶，投資3元可增加元可增加1小時(shí)勞小時(shí)勞動(dòng)時(shí)間，應(yīng)否應(yīng)做這些投資？現(xiàn)每天投資動(dòng)時(shí)間，應(yīng)否應(yīng)做這些投資？現(xiàn)每天投資150元，可賺元，可賺回多少？回多少？ B1，B2的獲利經(jīng)常有的獲利經(jīng)常有10%的波動(dòng)，對(duì)定制的計(jì)劃有無(wú)的波動(dòng)，對(duì)定制的計(jì)劃有無(wú)影響？若每公斤影響？若每公斤B1的獲利下降的獲利下降10，計(jì)劃應(yīng)該變化嗎？，計(jì)劃應(yīng)該變化嗎？1桶桶牛奶牛奶 3千克千克 A1 12小時(shí)小時(shí) 8小時(shí)小時(shí) 4千克千克 A2 或或獲利獲利24元元/千克千克 獲利獲利16元元/kg 0.8千克千克 B12小時(shí)小時(shí),3元元1千克千克獲利獲利44元元/千克千克 0.75千克千克 B22小時(shí)小時(shí),3元元1

39、千克千克獲利獲利32元元/千克千克 出售出售x1 千克千克 A1, x2 千克千克 A2， X3千克千克 B1, x4千克千克 B2原料原料供應(yīng)供應(yīng) 勞動(dòng)勞動(dòng)時(shí)間時(shí)間 加工能力加工能力 決策決策變量變量 目標(biāo)目標(biāo)函數(shù)函數(shù) 利潤(rùn)利潤(rùn)約束約束條件條件非負(fù)約束非負(fù)約束 0,61xx x5千克千克 A1加工加工B1， x6千克千克 A2加工加工B26543213332441624xxxxxxzMax50436251xxxx48022)(2)(4656251xxxxxx10051 xx附加約束附加約束 5380 x.x64750 x.x 模型求解模型求解 軟件實(shí)現(xiàn)軟件實(shí)現(xiàn) LINDO 6.1 5043)

40、 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.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.26

41、0000 4) 76.000000 0.000000 5) 0.000000 44.000000 6) 0.000000 32.000000 NO. ITERATIONS= 2600334) 26521xxxx44804624) 36521xxxxDO RANGE (SENSITIVITY) ANALYSIS? No 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.0000

42、00 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.000000 NO. ITERATIONS= 2結(jié)果解釋結(jié)果解釋每天銷售每天銷售168 千克千克A2和和19.2 千克千克B1， 利潤(rùn)利潤(rùn)3460.8（元）（元）8桶牛奶加工成桶牛奶加工成A1，42桶桶牛奶加工成牛奶加工成A

43、2，將得到的將得到的24千克千克A1全部全部加工成加工成B1 除加工能力外均除加工能力外均為緊約束為緊約束結(jié)果解釋結(jié)果解釋 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.000000 X5 24.000000 0.000000 X6 0.000000 1.520000ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000

44、 3.160000 3) 0.000000 3.260000 4) 76.000000 0.000000 5) 0.000000 44.000000 6) 0.000000 32.000000增加增加1桶牛奶使利潤(rùn)增桶牛奶使利潤(rùn)增長(zhǎng)長(zhǎng)3.1612=37.925043)26251xxxx600334) 26521xxxx4增加增加1小時(shí)時(shí)間使利小時(shí)時(shí)間使利潤(rùn)增長(zhǎng)潤(rùn)增長(zhǎng)3.26 30元可增加元可增加1桶牛奶，桶牛奶，3元可增加元可增加1小時(shí)時(shí)間，小時(shí)時(shí)間，應(yīng)否投資？現(xiàn)投資應(yīng)否投資？現(xiàn)投資150元，可賺回多少？元，可賺回多少？投資投資150元增加元增加5桶牛奶，桶牛奶，可賺回可賺回189.6元。（大

45、于元。（大于增加時(shí)間的利潤(rùn)增長(zhǎng)）增加時(shí)間的利潤(rùn)增長(zhǎng)）結(jié)果解釋結(jié)果解釋B1,B2的獲利有的獲利有10%的波動(dòng)，對(duì)計(jì)劃有無(wú)影響的波動(dòng)，對(duì)計(jì)劃有無(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.0000

46、00 2.026667 INFINITY X5 -3.000000 15.800000 2.533334 X6 -3.000000 1.520000 INFINITY DO RANGE (SENSITIVITY) ANALYSIS? YesB1獲利下降獲利下降10%，超，超出出X3 系數(shù)允許范圍系數(shù)允許范圍B2獲利上升獲利上升10%，超，超出出X4 系數(shù)允許范圍系數(shù)允許范圍波動(dòng)對(duì)計(jì)劃有影響波動(dòng)對(duì)計(jì)劃有影響生產(chǎn)計(jì)劃應(yīng)重新制訂：如將生產(chǎn)計(jì)劃應(yīng)重新制訂：如將x3的系數(shù)改為的系數(shù)改為39.6計(jì)算，會(huì)發(fā)現(xiàn)結(jié)果有很大變化。計(jì)算，會(huì)發(fā)現(xiàn)結(jié)果有很大變化。 自來(lái)水輸送與貨機(jī)裝運(yùn)自來(lái)水輸送與貨機(jī)裝運(yùn)生產(chǎn)、生活物資

47、從若干供應(yīng)點(diǎn)運(yùn)送到一些需求點(diǎn)，生產(chǎn)、生活物資從若干供應(yīng)點(diǎn)運(yùn)送到一些需求點(diǎn)，怎樣安排輸送方案使運(yùn)費(fèi)最小，或利潤(rùn)最大；怎樣安排輸送方案使運(yùn)費(fèi)最小，或利潤(rùn)最大；運(yùn)輸問(wèn)題運(yùn)輸問(wèn)題各種類型的貨物裝箱，由于受體積、重量等限制，各種類型的貨物裝箱，由于受體積、重量等限制，如何搭配裝載，使獲利最高，或裝箱數(shù)量最少。如何搭配裝載，使獲利最高，或裝箱數(shù)量最少。其他費(fèi)用其他費(fèi)用:450元元/千噸千噸 應(yīng)如何分配水庫(kù)供水量，公司才能獲利最多？應(yīng)如何分配水庫(kù)供水量，公司才能獲利最多？ 若水庫(kù)供水量都提高一倍，公司利潤(rùn)可增加到多少？若水庫(kù)供水量都提高一倍，公司利潤(rùn)可增加到多少？ 元元/千噸千噸甲甲乙乙丙丙丁丁A16013

48、0220170B140130190150C190200230/引水管理費(fèi)引水管理費(fèi)例例1 自來(lái)水輸送自來(lái)水輸送收入：收入：900元元/千噸千噸 支出支出A：50B：60C：50甲：甲：30；50乙：乙：70；70丙：丙：10；20?。憾。?0；40水庫(kù)供水量水庫(kù)供水量(千噸千噸)小區(qū)基本用水量小區(qū)基本用水量(千噸千噸)小區(qū)額外用水量小區(qū)額外用水量(千噸千噸)（以天計(jì)）（以天計(jì)）總供水量：總供水量：160確定送水方案使利潤(rùn)最大確定送水方案使利潤(rùn)最大問(wèn)題問(wèn)題分析分析A：50B：60C：50甲：甲：30；50乙：乙：70；70丙：丙：10；20?。憾。?0；40 總需求量總需求量(300)每個(gè)水庫(kù)最

49、大供水量都提高一倍每個(gè)水庫(kù)最大供水量都提高一倍利潤(rùn)利潤(rùn) = 收入收入(900) 其它費(fèi)用其它費(fèi)用(450) 引水管理費(fèi)引水管理費(fèi)利潤(rùn)利潤(rùn)(元元/千噸千噸)甲甲乙乙丙丙丁丁A290320230280B310320260300C260250220/3332312423222114131211220250260300260320310280230320290 xxxxxxxxxxxZMax供應(yīng)供應(yīng)限制限制B, C 類似處理類似處理50:A14131211xxxx10014131211xxxx問(wèn)題討論問(wèn)題討論 確定送水方案使利潤(rùn)最大確定送水方案使利潤(rùn)最大需求約束可以不變需求約束可以不變求解求解 OBJ

50、ECTIVE 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 X21 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.

51、000000 0.000000 這類問(wèn)題一般稱為這類問(wèn)題一般稱為“運(yùn)輸問(wèn)題運(yùn)輸問(wèn)題”(Transportation Problem)總利潤(rùn)總利潤(rùn) 88700（元）（元） A(100)B(120)C(100)甲甲(30;50)乙乙(70;70)丙丙(10;20)丁丁(10;40)4010050305030如何裝運(yùn)，如何裝運(yùn)，使本次飛行使本次飛行獲利最大？獲利最大？ 三個(gè)貨艙三個(gè)貨艙最大最大載載重重( (噸噸),),最大容積最大容積( (米米3 3) ) 例例2 貨機(jī)裝運(yùn)貨機(jī)裝運(yùn) 重量（噸）重量（噸）空間空間( 米米3/噸）噸）利潤(rùn)（元利潤(rùn)（元/噸）噸）貨物貨物1184803100貨物貨物2156

52、503800貨物貨物3235803500貨物貨物4123902850三個(gè)貨艙中實(shí)際載重必須與其最大載重成比例三個(gè)貨艙中實(shí)際載重必須與其最大載重成比例 前倉(cāng)：前倉(cāng)：10；6800中倉(cāng)：中倉(cāng)：16；8700后倉(cāng)：后倉(cāng)：8；5300飛機(jī)平衡飛機(jī)平衡決策決策變量變量 xij-第第i 種貨物裝入第種貨物裝入第j 個(gè)貨艙的重量個(gè)貨艙的重量(噸）噸）i=1,2,3,4, j=1,2,3 (分別代表前、中、后倉(cāng)分別代表前、中、后倉(cāng))模型假設(shè)模型假設(shè) 每種貨物可以分割到任意??；每種貨物可以分割到任意小；貨機(jī)裝運(yùn)貨機(jī)裝運(yùn)每種貨物可以在一個(gè)或多個(gè)貨艙中任意分布；每種貨物可以在一個(gè)或多個(gè)貨艙中任意分布；多種貨物可以混

53、裝，并保證不留空隙；多種貨物可以混裝，并保證不留空隙； 模型建立模型建立 貨艙貨艙容積容積 目標(biāo)目標(biāo)函數(shù)函數(shù)( (利潤(rùn)利潤(rùn))約束約束條件條件 )(2850)(3500)(3800)(3100434241333231232221131211xxxxxxxxxxxxZMax 680039058065048041312111 xxxx870039058065048042322212 xxxx530039058065048043332313 xxxx貨機(jī)裝運(yùn)貨機(jī)裝運(yùn)模型建立模型建立 貨艙貨艙重量重量 1041312111 xxxx1642322212 xxxx843332313 xxxx10；6800

54、16；87008；5300 xij-第第i 種貨物裝入第種貨物裝入第j 個(gè)貨艙的重量個(gè)貨艙的重量約束約束條件條件平衡平衡要求要求 81610433323134232221241312111xxxxxxxxxxxx 貨物貨物供應(yīng)供應(yīng) 18131211 xxx15232221 xxx23333231 xxx12434241 xxx貨機(jī)裝運(yùn)貨機(jī)裝運(yùn)模型建立模型建立 10；680016；87008；5300 xij-第第i 種貨物裝入第種貨物裝入第j 個(gè)貨艙的重量個(gè)貨艙的重量 OBJECTIVE FUNCTION VALUE 1) 121515.8 VARIABLE VALUE REDUCED COS

55、T X11 0.000000 400.000000 X12 0.000000 57.894737 X13 0.000000 400.000000 X21 10.000000 0.000000 X22 0.000000 239.473679 X23 5.000000 0.000000 X31 0.000000 0.000000 X32 12.947369 0.000000 X33 3.000000 0.000000 X41 0.000000 650.000000 X42 3.052632 0.000000 X43 0.000000 650.000000 貨物貨物2：前倉(cāng)：前倉(cāng)10,后倉(cāng)后倉(cāng)5；

56、貨物貨物3: 中倉(cāng)中倉(cāng)13, 后倉(cāng)后倉(cāng)3；貨物貨物4: 中倉(cāng)中倉(cāng)3。貨機(jī)裝運(yùn)貨機(jī)裝運(yùn)模型求解模型求解 最大利潤(rùn)約最大利潤(rùn)約121516元元貨物貨物供應(yīng)點(diǎn)供應(yīng)點(diǎn)貨艙貨艙需求點(diǎn)需求點(diǎn)平衡要求平衡要求運(yùn)輸運(yùn)輸問(wèn)題問(wèn)題運(yùn)輸問(wèn)題的擴(kuò)展運(yùn)輸問(wèn)題的擴(kuò)展設(shè)每月生產(chǎn)小、中、大型設(shè)每月生產(chǎn)小、中、大型汽車的數(shù)量分別為汽車的數(shù)量分別為x1, x2, x3321432xxxzMax600535 . 1.321xxxts60000400250280321xxx0,321xxx汽車廠生產(chǎn)計(jì)劃汽車廠生產(chǎn)計(jì)劃 模型建立模型建立 小型小型 中型中型 大型大型 現(xiàn)有量現(xiàn)有量鋼材鋼材 1.5 3 5 600時(shí)間時(shí)間 280 250

57、 400 60000利潤(rùn)利潤(rùn) 2 3 4 線性線性規(guī)劃規(guī)劃模型模型(LP)模型模型求解求解 3） 模型中增加條件：模型中增加條件：x1, x2, x3 均為整數(shù)，重新求解。均為整數(shù)，重新求解。 OBJECTIVE FUNCTION VALUE 1) 632.2581VARIABLE VALUE REDUCED COST X1 64.516129 0.000000 X2 167.741928 0.000000 X3 0.000000 0.946237 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 0.731183 3) 0.000000 0.00322

58、6結(jié)果為小數(shù)，結(jié)果為小數(shù)，怎么辦？怎么辦？1）舍去小數(shù)：?。┥崛バ?shù)：取x1=64，x2=167，算出目標(biāo)函數(shù)值，算出目標(biāo)函數(shù)值z(mì)=629，與，與LP最優(yōu)值最優(yōu)值632.2581相差不大。相差不大。2）試探：如取）試探：如取x1=65，x2=167；x1=64，x2=168等，計(jì)算函數(shù)等，計(jì)算函數(shù)值值z(mì)，通過(guò)比較可能得到更優(yōu)的解。，通過(guò)比較可能得到更優(yōu)的解。 但必須檢驗(yàn)它們是否滿足約束條件。為什么？但必須檢驗(yàn)它們是否滿足約束條件。為什么？IP可用可用LINDO直接求解直接求解整數(shù)規(guī)劃整數(shù)規(guī)劃(Integer Programming,簡(jiǎn)記簡(jiǎn)記IP)“gin 3”表示表示“前前3個(gè)變量為個(gè)變量為整

59、數(shù)整數(shù)”，等價(jià)于：，等價(jià)于：gin x1gin x2gin x3 IP 的最優(yōu)解的最優(yōu)解x1=64，x2=168，x3=0，最優(yōu)值，最優(yōu)值z(mì)=632 max 2x1+3x2+4x3st1.5x1+3x2+5x3600280 x1+250 x2+400 x360000endgin 3 OBJECTIVE FUNCTION VALUE 1) 632.0000VARIABLE VALUE REDUCED COST X1 64.000000 -2.000000 X2 168.000000 -3.000000 X3 0.000000 -4.000000 321432xxxzMax600535 . 1.3

60、21xxxts60000400250280321 xxx為非負(fù)整數(shù)為非負(fù)整數(shù)321,xxx模型求解模型求解 IP 結(jié)果輸出結(jié)果輸出其中其中3個(gè)子模型應(yīng)去掉，然后個(gè)子模型應(yīng)去掉，然后逐一求解，比較目標(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：分解為：分解為8個(gè)個(gè)LP子模型子模型 汽車廠生產(chǎn)計(jì)劃汽車廠生產(chǎn)計(jì)劃 若生產(chǎn)某類汽車，則至少生產(chǎn)若生