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

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

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

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

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

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

6、變量。網(wǎng)絡的最大通車量網(wǎng)絡的最大通車量求通過該公路求通過該公路.1沿該弧的車流量沿該弧的車流量到到為從為從發(fā)出的車流量發(fā)出的車流量表示從節(jié)點表示從節(jié)點用用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各段上的流量限制各段上的流量限制工廠定期訂購原料，存入倉庫供生產(chǎn)之用；工廠定期訂購原料，存入倉庫供生產(chǎn)之用；車間一次加工出一批零件，供裝配線每天生產(chǎn)之用；車間一次加工出一批零件，供裝配線每天生產(chǎn)之用；商店成批購進各種商品，放在貨柜里以備零售；商店成批購進各種商品，放在貨柜里以備零售；水庫在雨季蓄水，用于旱季的灌溉和發(fā)電。水庫在雨季蓄水，用于旱季的灌溉和發(fā)電。存貯模型存貯模型存貯量多少合適？存貯量多少合適？存貯量過大，存貯費用太高；存貯量太小，會導致一存貯量過大，存貯費用太高；存貯量太小，會導致一次性訂購費用增加，

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

26、規(guī)劃模型線性規(guī)劃模型模型求解模型求解 圖解法圖解法 x1x20ABCDl1l2l3l4l55021 xx48081221 xx10031 x0,21 xx約約束束條條件件50:211 xxl480812:212 xxl1003:13 xl0:, 0:2514 xlxl216472xxzMax 目標目標函數(shù)函數(shù) Z=0Z=2400Z=3600z=c (常數(shù)常數(shù)) 等值線等值線c在在B(20,30)點得到最優(yōu)解點得到最優(yōu)解目標函數(shù)和約束條件是線性函數(shù)目標函數(shù)和約束條件是線性函數(shù) 可行域為直線段圍成的凸多邊形可行域為直線段圍成的凸多邊形 目標函數(shù)的等值線為直線目標函數(shù)的等值線為直線 最優(yōu)解一定在凸多

27、邊最優(yōu)解一定在凸多邊形的某個頂點取得。形的某個頂點取得。 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模型求解模型求解 軟件實現(xiàn)軟件實現(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，利潤，利潤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：結果解釋結果解釋 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原料無剩余原料無剩余時間無剩余時間無剩余加工能力剩余加工能力剩余40max

30、 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 2.000000 4) 40.00000

31、0 0.000000 NO. ITERATIONS= 2最優(yōu)解下最優(yōu)解下“資源資源”增加增加1單位時單位時“效益效益”的增的增量量 原料增加原料增加1單位單位, 利潤增長利潤增長48 時間增加時間增加1單位單位, 利潤增長利潤增長2 加工能力增長不影響利潤加工能力增長不影響利潤影子價格影子價格 35元可買到元可買到1桶牛奶，要買嗎？桶牛奶，要買嗎？35 48, 應該買！應該買！ 聘用臨時工人付出的工資最多每小時幾元？聘用臨時工人付出的工資最多每小時幾元？ 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)解不變時目

33、標函最優(yōu)解不變時目標函數(shù)系數(shù)允許變化范圍數(shù)系數(shù)允許變化范圍 DO RANGE(SENSITIVITY) ANALYSIS? Yesx1系數(shù)范圍系數(shù)范圍(64,96) x2系數(shù)范圍系數(shù)范圍(48,72) A1獲利增加到獲利增加到 30元元/千克，應否改變生產(chǎn)計劃千克，應否改變生產(chǎn)計劃 x1系數(shù)由系數(shù)由24 3=72增加增加為為30 3=90，在在允許范圍內(nèi)允許范圍內(nèi) 不變！不變！(約束條件不變約束條件不變)結果解釋結果解釋 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影子價格有意義時約束右端的允許變化范圍影子價格有意義時約束

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

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

37、若每公斤B1的獲利下降的獲利下降10，計劃應該變化嗎？，計劃應該變化嗎？例例2 奶制品的生產(chǎn)銷售計劃奶制品的生產(chǎn)銷售計劃 在例在例1基礎上深加工基礎上深加工1桶桶牛奶牛奶 3千克千克A1 12小時小時 8小時小時 4公斤公斤A2 或或獲利獲利24元元/公斤公斤 獲利獲利16元元/公斤公斤 0.8千克千克B12小時小時,3元元1千克千克獲利獲利44元元/千克千克 0.75千克千克B22小時小時,3元元1千克千克獲利獲利32元元/千克千克 制訂生產(chǎn)計劃，使每天凈利潤最大制訂生產(chǎn)計劃，使每天凈利潤最大 50桶牛奶桶牛奶, 480小時小時 至多至多100公斤公斤A1 若投資若投資30元可增加元可增加1

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

39、千克千克獲利獲利32元元/千克千克 出售出售x1 千克千克 A1, x2 千克千克 A2， X3千克千克 B1, x4千克千克 B2原料原料供應供應 勞動勞動時間時間 加工能力加工能力 決策決策變量變量 目標目標函數(shù)函數(shù) 利潤利潤約束約束條件條件非負約束非負約束 0,61xx x5千克千克 A1加工加工B1， x6千克千克 A2加工加工B26543213332441624xxxxxxzMax50436251xxxx48022)(2)(4656251xxxxxx10051 xx附加約束附加約束 5380 x.x64750 x.x 模型求解模型求解 軟件實現(xiàn)軟件實現(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結果解釋結果解釋每天銷售每天銷售168 千克千克A2和和19.2 千克千克B1， 利潤利潤3460.8（元）（元）8桶牛奶加工成桶牛奶加工成A1，42桶桶牛奶加工成牛奶加工成A

43、2，將得到的將得到的24千克千克A1全部全部加工成加工成B1 除加工能力外均除加工能力外均為緊約束為緊約束結果解釋結果解釋 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桶牛奶使利潤增桶牛奶使利潤增長長3.1612=37.925043)26251xxxx600334) 26521xxxx4增加增加1小時時間使利小時時間使利潤增長潤增長3.26 30元可增加元可增加1桶牛奶，桶牛奶，3元可增加元可增加1小時時間，小時時間，應否投資？現(xiàn)投資應否投資？現(xiàn)投資150元，可賺回多少？元，可賺回多少？投資投資150元增加元增加5桶牛奶，桶牛奶，可賺回可賺回189.6元。（大

45、于元。（大于增加時間的利潤增長）增加時間的利潤增長）結果解釋結果解釋B1,B2的獲利有的獲利有10%的波動，對計劃有無影響的波動，對計劃有無影響 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ù)允許范圍波動對計劃有影響波動對計劃有影響生產(chǎn)計劃應重新制訂：如將生產(chǎn)計劃應重新制訂：如將x3的系數(shù)改為的系數(shù)改為39.6計算，會發(fā)現(xiàn)結果有很大變化。計算，會發(fā)現(xiàn)結果有很大變化。 自來水輸送與貨機裝運自來水輸送與貨機裝運生產(chǎn)、生活物資

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

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

49、大供水量都提高一倍每個水庫最大供水量都提高一倍利潤利潤 = 收入收入(900) 其它費用其它費用(450) 引水管理費引水管理費利潤利潤(元元/千噸千噸)甲甲乙乙丙丙丁丁A290320230280B310320260300C260250220/3332312423222114131211220250260300260320310280230320290 xxxxxxxxxxxZMax供應供應限制限制B, C 類似處理類似處理50:A14131211xxxx10014131211xxxx問題討論問題討論 確定送水方案使利潤最大確定送水方案使利潤最大需求約束可以不變需求約束可以不變求解求解 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 這類問題一般稱為這類問題一般稱為“運輸問題運輸問題”(Transportation Problem)總利潤總利潤 88700（元）（元） A(100)B(120)C(100)甲甲(30;50)乙乙(70;70)丙丙(10;20)丁丁(10;40)4010050305030如何裝運，如何裝運，使本次飛行使本次飛行獲利最大？獲利最大？ 三個貨艙三個貨艙最大最大載載重重( (噸噸),),最大容積最大容積( (米米3 3) ) 例例2 貨機裝運貨機裝運 重量（噸）重量（噸）空間空間( 米米3/噸）噸）利潤（元利潤（元/噸）噸）貨物貨物1184803100貨物貨物2156

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

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

54、16；87008；5300 xij-第第i 種貨物裝入第種貨物裝入第j 個貨艙的重量個貨艙的重量約束約束條件條件平衡平衡要求要求 81610433323134232221241312111xxxxxxxxxxxx 貨物貨物供應供應 18131211 xxx15232221 xxx23333231 xxx12434241 xxx貨機裝運貨機裝運模型建立模型建立 10；680016；87008；5300 xij-第第i 種貨物裝入第種貨物裝入第j 個貨艙的重量個貨艙的重量 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：前倉：前倉10,后倉后倉5；

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

57、 400 60000利潤利潤 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結果為小數(shù)，結果為小數(shù)，怎么辦？怎么辦？1）舍去小數(shù)：?。┥崛バ?shù)：取x1=64，x2=167，算出目標函數(shù)值，算出目標函數(shù)值z=629，與，與LP最優(yōu)值最優(yōu)值632.2581相差不大。相差不大。2）試探：如?。┰囂剑喝缛1=65，x2=167；x1=64，x2=168等，計算函數(shù)等，計算函數(shù)值值z，通過比較可能得到更優(yōu)的解。，通過比較可能得到更優(yōu)的解。 但必須檢驗它們是否滿足約束條件。為什么？但必須檢驗它們是否滿足約束條件。為什么？IP可用可用LINDO直接求解直接求解整數(shù)規(guī)劃整數(shù)規(guī)劃(Integer Programming,簡記簡記IP)“gin 3”表示表示“前前3個變量為個變量為整

59、數(shù)整數(shù)”，等價于：，等價于：gin x1gin x2gin x3 IP 的最優(yōu)解的最優(yōu)解x1=64，x2=168，x3=0，最優(yōu)值，最優(yōu)值z=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為非負整數(shù)為非負整數(shù)321,xxx模型求解模型求解 IP 結果輸出結果輸出其中其中3個子模型應去掉，然后個子模型應去掉，然后逐一求解，比較目標函數(shù)值，逐一求解，比較目標函數(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個個LP子模型子模型 汽車廠生產(chǎn)計劃汽車廠生產(chǎn)計劃 若生產(chǎn)某類汽車，則至少生產(chǎn)若生