第二講線性規(guī)劃模型

1、2022-4-301第二講第二講 線性規(guī)劃模型線性規(guī)劃模型統(tǒng)計與應(yīng)用數(shù)學(xué)系統(tǒng)計與應(yīng)用數(shù)學(xué)系張耀峰張耀峰The model of linear programmingThe model of linear programming2022-4-302第第二二講講 線性規(guī)劃模型線性規(guī)劃模型1.1 優(yōu)化的思想優(yōu)化的思想1.2 什么是線性規(guī)劃模型什么是線性規(guī)劃模型1.3 如何使用如何使用Lingo軟件求解軟件求解 線性規(guī)劃問題線性規(guī)劃問題1.4 案例解析案例解析2022-4-3031.1 優(yōu)化的思想優(yōu)化的思想2022-4-304燒水燒水 小明同學(xué)，燒一壺水要小明同學(xué)，燒一壺水要8分鐘，灌開水要分鐘，灌開

2、水要1分鐘，分鐘，取牛奶和報紙要取牛奶和報紙要5分鐘（不能間斷），整理書包要分鐘（不能間斷），整理書包要6分鐘（可間斷），為了盡快做完這些事，怎樣安排才分鐘（可間斷），為了盡快做完這些事，怎樣安排才能使時間最少？最少需要幾分鐘？能使時間最少？最少需要幾分鐘？ 例例1、如何安排早上的時間？、如何安排早上的時間？取牛奶和報紙取牛奶和報紙收拾書包收拾書包灌水灌水收拾書包收拾書包5891202022-4-305例例2、怎么排隊才合理呢？、怎么排隊才合理呢？ 碼頭上現(xiàn)在同時有碼頭上現(xiàn)在同時有3艘貨船需要卸貨，但是只艘貨船需要卸貨，但是只能一條一條地卸貨，并且每艘船卸貨所需的時間能一條一條地卸貨，并且每艘

3、船卸貨所需的時間各不相同，分別為各不相同，分別為4小時、小時、8小時和小時和1小時。按照怎小時。按照怎樣的順序卸貨能使樣的順序卸貨能使3艘貨船等候的總時間最少呢？艘貨船等候的總時間最少呢？ 2022-4-306方案卸貨順序船1的等候時間船2的等候時間船3的等候時間總的等候時間1船1船2船388+48+4+1332船1船3船288+1+48+1303船2船1船34+844+8+1294船2船3船14+1+844+1225船3船1船21+81+8+41236船3船2船11+4+81+41192022-4-3071.2 什么是線性規(guī)劃模型什么是線性規(guī)劃模型2022-4-308例例3 3 運輸問題運輸

4、問題。問問如如何何調(diào)調(diào)運運使使運運費費最最低低如如下下公公里里單單位位距距離離兩兩個個糧糧庫庫到到三三個個糧糧站站的的噸噸大大米米分分別別為為三三個個糧糧站站至至少少需需要要噸噸噸噸為為兩兩個個糧糧庫庫現(xiàn)現(xiàn)存存大大米米分分別別調(diào)調(diào)運運大大米米向向三三個個糧糧站站有有兩兩個個糧糧庫庫,):(,5 , 4 , 2,8 ,4, 32121BBBAA2022-4-309解：設(shè)解：設(shè)A1,A2調(diào)運到三個糧站的大米分別為調(diào)運到三個糧站的大米分別為x11，x12， x13， x21， x22， x23噸。噸。題設(shè)量可總到下表：題設(shè)量可總到下表：84庫庫存存量量x23x22x21A2542需要量需要量x13x

5、12x11A1B3B2B1糧庫糧庫糧站糧站距離及運量距離及運量121224308242022-4-3010結(jié)合存量限制和需量限制得數(shù)學(xué)模型結(jié)合存量限制和需量限制得數(shù)學(xué)模型：23222113121124123082412xxxxxxf min 054284232221131211231322122111232221131211xxxxxxxxxxxxxxxxxxts,.目標(biāo)目標(biāo)函數(shù)函數(shù)約束約束條件條件決策決策變量變量2022-4-30111.3如何使用如何使用Lingo軟件求解線性規(guī)劃問題軟件求解線性規(guī)劃問題2022-4-3012程序編寫程序編寫model:min=12*x11+24*x12+8

6、*x13+30*x21+12*x22+24*x23 ;x11+x12+x134 ;x21+x22+x232 ;x12+x224 ;x13+x235 ;end2022-4-3013運行結(jié)果運行結(jié)果 Global optimal solution found. Objective value: 160.0000 Total solver iterations: 5 Variable Value Reduced Cost X11 2.000000 0.000000 X12 0.000000 28.00000 X13 2.000000 0.000000 X21 0.000000 2.000000 X2

7、2 4.000000 0.000000 X23 3.000000 0.000000 Row Slack or Surplus Dual Price 1 160.0000 -1.000000 2 0.000000 16.00000 3 1.000000 0.000000 4 0.000000 -28.00000 5 0.000000 -12.00000 6 0.000000 -24.000002022-4-3014 例例4 生產(chǎn)計劃問題生產(chǎn)計劃問題某工廠計劃安排生產(chǎn)某工廠計劃安排生產(chǎn)，兩種產(chǎn)兩種產(chǎn)品，已知每種單位產(chǎn)品的利潤，生產(chǎn)單位產(chǎn)品所需設(shè)備品，已知每種單位產(chǎn)品的利潤，生產(chǎn)單位產(chǎn)品所需設(shè)備臺時

8、及臺時及A,B兩種原材料的消耗，現(xiàn)有原材料和設(shè)備臺時的兩種原材料的消耗，現(xiàn)有原材料和設(shè)備臺時的定額如表所示，問：定額如表所示，問：）怎么安排生產(chǎn)使得工廠獲利最大？）怎么安排生產(chǎn)使得工廠獲利最大？）產(chǎn)品）產(chǎn)品的單位利潤降低到的單位利潤降低到1.8萬元，要不要改變生產(chǎn)萬元，要不要改變生產(chǎn)計劃，如果降低到計劃，如果降低到1萬元呢？萬元呢？）產(chǎn)品）產(chǎn)品的單位利潤增大到的單位利潤增大到5萬，要不要改變生產(chǎn)計劃萬，要不要改變生產(chǎn)計劃）如果產(chǎn)品）如果產(chǎn)品，的單位利潤同時降低了的單位利潤同時降低了1萬元，要不萬元，要不要改變生產(chǎn)計劃？要改變生產(chǎn)計劃？ 產(chǎn)品產(chǎn)品最大資源量設(shè)備128臺時原材料A4016kg原材料

9、B0412kg單位產(chǎn)品利潤232022-4-30152022-4-3016程序編寫程序編寫model:title 生產(chǎn)計劃問題生產(chǎn)計劃問題;maxfmax=2*x1+3*x2;Ax1+2*x28;B4*x116;TIME4*x212;END2022-4-3017運行結(jié)果運行結(jié)果 Model Title: 生產(chǎn)計劃問題生產(chǎn)計劃問題 Variable Value Reduced Cost X1 4.000000 0.000000 X2 2.000000 0.000000 Row Slack or Surplus Dual Price MAXF 14.00000 1.000000 A 0.00000

10、0 1.500000 B 0.000000 0.1250000 TIME 4.000000 0.000000 對問題對問題1，安排是生產(chǎn)產(chǎn)品，安排是生產(chǎn)產(chǎn)品4單位，產(chǎn)品單位，產(chǎn)品2單位，單位，最大盈利為最大盈利為14萬元萬元 。2022-4-3018 線性模型敏感性分析要使用敏感性分析要使用敏感性分析必須要在這里選擇必須要在這里選擇Prices & Ranges然后然后保存保存退出退出路徑：路徑：LINGOOptionsGeneral Solver(通用求解程序通用求解程序)選項卡選項卡2022-4-3019要調(diào)出敏感性分析的結(jié)果，要調(diào)出敏感性分析的結(jié)果，必須必須先求解先求解后再后再在程序窗在

11、程序窗口下口下點擊點擊LINGORange， 2022-4-3020 Ranges in which the basis is unchanged: Objective Coefficient Ranges Current Allowable Allowable Variable Coefficient Increase Decrease X1 2.000000 INFINITY 0.5000000 X2 3.000000 1.000000 3.000000 Righthand Side Ranges Row Current Allowable Allowable RHS Increase D

12、ecrease A 8.000000 2.000000 4.000000 B 16.00000 16.00000 8.000000 TIME 12.00000 INFINITY 4.000000 當(dāng)前變量系數(shù)允許增加量允許減少量2022-4-3021 對問題對問題4，因為兩個系數(shù)同時改變了，所以只，因為兩個系數(shù)同時改變了，所以只有更有更 改程序的數(shù)據(jù)，重新運行得：不改變生產(chǎn)計改程序的數(shù)據(jù)，重新運行得：不改變生產(chǎn)計劃，但是最大利潤降低到劃，但是最大利潤降低到6萬元萬元. 對問題對問題2，產(chǎn)品，產(chǎn)品的單位利潤降低到的單位利潤降低到1.8萬元，萬元，在（在（1.5，）之間，所以不改變生產(chǎn)計劃。如果降

13、）之間，所以不改變生產(chǎn)計劃。如果降低到低到1萬元，不在（萬元，不在（1.5，）內(nèi)，要改變生產(chǎn)計劃。）內(nèi)，要改變生產(chǎn)計劃。在程序中將目標(biāo)函數(shù)的系數(shù)在程序中將目標(biāo)函數(shù)的系數(shù)“2”改為改為“1”，可得新，可得新的計劃為安排是生產(chǎn)產(chǎn)品的計劃為安排是生產(chǎn)產(chǎn)品2單位，產(chǎn)品單位，產(chǎn)品3單位，單位，最大盈利為最大盈利為11萬元萬元. 對問題對問題3，要改變生產(chǎn)計劃，更改程序得新，要改變生產(chǎn)計劃，更改程序得新計劃為生產(chǎn)產(chǎn)品計劃為生產(chǎn)產(chǎn)品2單位，產(chǎn)品單位，產(chǎn)品3單位，最大盈單位，最大盈利為利為19萬元萬元.2022-4-3022例例5 加工奶制品的生產(chǎn)計劃加工奶制品的生產(chǎn)計劃1桶牛奶 3公斤A1 12小時 8小時

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

15、牛奶生產(chǎn)A1 x2桶牛奶生產(chǎn)桶牛奶生產(chǎn)A2 獲利獲利 243x1 獲利獲利 164 x2 原料供應(yīng)原料供應(yīng) 5021 xx勞動時間勞動時間 48081221 xx加工能力加工能力 10031x決策變量決策變量 目標(biāo)函數(shù)目標(biāo)函數(shù) 216472xxzMax每天獲利每天獲利約束條件約束條件非負(fù)約束非負(fù)約束 0,21xx線性線性規(guī)劃規(guī)劃模型模型(LP)時間時間480小時小時 至多加工至多加工100公斤公斤A1 50桶牛奶桶牛奶 每天每天2022-4-3024模型求解模型求解 OBJECTIVE FUNCTION VALUE 1) 3360.000 VARIABLE VALUE REDUCED COST

16、 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= 220桶牛奶生產(chǎn)桶牛奶生產(chǎn)A1, 30桶生產(chǎn)桶生產(chǎn)A2，利潤，利潤3360元。元。 max=72*x1+64*x2;x1+x250;12*x1+8*x2480;3*x1100;2022-4-3025模型求解模型求解 reduced cost值表值表示當(dāng)該非基變量示當(dāng)該非基變量增加一

17、個單位時增加一個單位時（其他非基變量（其他非基變量保持不變）目標(biāo)保持不變）目標(biāo)函數(shù)減少的量函數(shù)減少的量(對對max型問題型問題) 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= 22022-4-3026

18、 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原料無剩余原料無剩余時間無剩余時間無剩余加工能力剩余加工能力剩余40max 72x1+64x2st2）x1+x2503）12x1+8x24804）3x1100end三三種種資資源源結(jié)果解

19、釋結(jié)果解釋 2022-4-3027 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結(jié)果解釋結(jié)果解釋 最優(yōu)解下最優(yōu)解下“資源資源”增增加加1單位時單位時“效益效益”的的增量增量 原料增原料增1單位單位, 利潤增利潤增48 時間加時間加1

20、單位單位, 利潤增利潤增2 能力增減不影響利潤能力增減不影響利潤影子價格影子價格 35元可買到元可買到1桶牛奶，要買嗎？桶牛奶，要買嗎？ 35 sum(yuefen(i)|i#le#j:d);sum(yuefen:x)= sum(yuefen:d);for(yuefen:xa);end 2022-4-3034露天礦里鏟位已分成礦石和巖石露天礦里鏟位已分成礦石和巖石: 平均鐵含量不低于平均鐵含量不低于25%的為礦石，否則為巖石。每個鏟位的礦石、巖石數(shù)的為礦石，否則為巖石。每個鏟位的礦石、巖石數(shù)量，以及礦石的平均鐵含量（稱為品位）都是已知的。量，以及礦石的平均鐵含量（稱為品位）都是已知的。每個鏟位

21、至多安置一臺電鏟，電鏟平均裝車時間每個鏟位至多安置一臺電鏟，電鏟平均裝車時間5分鐘分鐘卡車在等待時所耗費的能量也是相當(dāng)可觀的，原則上卡車在等待時所耗費的能量也是相當(dāng)可觀的，原則上在安排時不應(yīng)發(fā)生卡車等待的情況。在安排時不應(yīng)發(fā)生卡車等待的情況。 例例7、 露天礦生產(chǎn)的車輛安排露天礦生產(chǎn)的車輛安排(CUMCM-2003B) 礦石卸點需要的鐵含量要求都為礦石卸點需要的鐵含量要求都為29.5% 1%(品位限品位限制），搭配量在一個班次（制），搭配量在一個班次（8小時）內(nèi)滿足品位限制即小時）內(nèi)滿足品位限制即可。卸點在一個班次內(nèi)不變。卡車載重量為可。卸點在一個班次內(nèi)不變?？ㄜ囕d重量為154噸，平噸，平均時

22、速均時速28km,平均卸車時間為平均卸車時間為3分鐘。分鐘。問題：出動幾臺電鏟，分別在哪些鏟位上；出動幾輛問題：出動幾臺電鏟，分別在哪些鏟位上；出動幾輛卡車，分別在哪些路線上各運輸多少次卡車，分別在哪些路線上各運輸多少次 ?2022-4-3035平面示意圖2022-4-3036問題數(shù)據(jù)問題數(shù)據(jù) 距離鏟位1鏟位2鏟位3鏟位4鏟位5鏟位6鏟位7鏟位8鏟位9鏟位10礦石漏5.265.194.214.002.952.742.461.900.641.27倒裝1.900.991.901.131.272.251.482.043.093.51巖場5.895.615.614.563.513.652.462.46

23、1.060.57巖石漏0.641.761.271.832.742.604.213.725.056.10倒裝4.423.863.723.162.252.810.781.621.270.50鏟位1鏟位2鏟位3鏟位4鏟位5鏟位6鏟位7鏟位8鏟位9鏟位10礦石量095105100105110125105130135125巖石量125110135105115135105115135125鐵含量30%28%29%32%31%33%32%31%33%31%2022-4-3037問題分析問題分析 與典型的運輸問題明顯有以下不同：與典型的運輸問題明顯有以下不同：這是運輸?shù)V石與巖石兩種物資的問題；這是運輸?shù)V石與巖

24、石兩種物資的問題；屬于產(chǎn)量大于銷量的不平衡運輸問題；屬于產(chǎn)量大于銷量的不平衡運輸問題；為了完成品位約束，礦石要搭配運輸；為了完成品位約束，礦石要搭配運輸；產(chǎn)地、銷地均有單位時間的流量限制；產(chǎn)地、銷地均有單位時間的流量限制；運輸車輛只有一種，每次滿載運輸，運輸車輛只有一種，每次滿載運輸，154噸噸/車次；車次；鏟位數(shù)多于鏟車數(shù)意味著要最優(yōu)的選擇不多于鏟位數(shù)多于鏟車數(shù)意味著要最優(yōu)的選擇不多于7個個產(chǎn)地作為最后結(jié)果中的產(chǎn)地；產(chǎn)地作為最后結(jié)果中的產(chǎn)地；1. 最后求出各條路線上的派出車輛數(shù)及安排。最后求出各條路線上的派出車輛數(shù)及安排。近似處理：近似處理：先求出產(chǎn)位、卸點每條線路上的運輸量先求出產(chǎn)位、卸點

25、每條線路上的運輸量(MIP模型模型)然后求出各條路線上的派出車輛數(shù)及安排然后求出各條路線上的派出車輛數(shù)及安排2022-4-3038模型假設(shè)模型假設(shè)v卡車在一個班次中不應(yīng)發(fā)生等待或熄火后再啟動卡車在一個班次中不應(yīng)發(fā)生等待或熄火后再啟動的情況；的情況；v在鏟位或卸點處由兩條路線以上造成的沖突問題在鏟位或卸點處由兩條路線以上造成的沖突問題面前，我們認(rèn)為只要平均時間能完成任務(wù)，就認(rèn)面前，我們認(rèn)為只要平均時間能完成任務(wù)，就認(rèn)為不沖突。我們不排時地進(jìn)行討論；為不沖突。我們不排時地進(jìn)行討論；v空載與重載的速度都是空載與重載的速度都是28km/h，耗油相差很大；，耗油相差很大；v卡車可提前退出系統(tǒng)，等等?？ㄜ?/p>

26、可提前退出系統(tǒng)，等等。如理解為嚴(yán)格不等待，難以用數(shù)學(xué)規(guī)劃模型來解如理解為嚴(yán)格不等待，難以用數(shù)學(xué)規(guī)劃模型來解 個別參數(shù)隊找到了可行解個別參數(shù)隊找到了可行解 （略）（略）2022-4-3039符號符號vxij ：從：從i鏟位到鏟位到j(luò)號卸點的石料運量號卸點的石料運量 （車）（車） 單位：單位： 噸；噸；vcij ：從：從i號鏟位到號鏟位到j(luò)號卸點的距離號卸點的距離 公里；公里；vTij :從從i號鏟位到號號鏟位到號j卸點路線上運行一個周期平均時間卸點路線上運行一個周期平均時間 分；分；vAij ：從號鏟位到號卸點最多能同時運行的卡車數(shù)：從號鏟位到號卸點最多能同時運行的卡車數(shù) 輛；輛；vBij ：從

27、號鏟位到號卸點路線上一輛車最多可運行的次數(shù)：從號鏟位到號卸點路線上一輛車最多可運行的次數(shù) 次；次；vpi：i號鏟位的礦石鐵含量號鏟位的礦石鐵含量 p=(30,28,29,32,31,33,32,31,33,31) %vqj : j號卸點任務(wù)需求，號卸點任務(wù)需求，q=(1.2,1.3,1.3,1.9,1.3)*10000 噸噸vcki ：i號鏟位的鐵礦石儲量號鏟位的鐵礦石儲量 萬噸萬噸vcyi ：i號鏟位的巖石儲量號鏟位的巖石儲量 萬噸萬噸vfi :描述第描述第i號鏟位是否使用的號鏟位是否使用的0-1變量，取變量，取1為使用；為使用；0為關(guān)閉。為關(guān)閉。532平均速度距離到j(luò)iTij5ijijTAijijijTAB5) 1(608(近似近似)2022-4-3040優(yōu)化模型優(yōu)化模型cxijijij10151min5 , 1,10, 1,jiBAxijijij10, 1, 5/60851ifxijij5 , 1,208101jiijx10, 1,154/10000154/1000043521icyxxckxxxii