第05章-生產(chǎn)與服務運作管理中的優(yōu)化問題

1、 優(yōu)化建模優(yōu)化建模生產(chǎn)與服務運作管理中的優(yōu)化問題生產(chǎn)與服務運作管理中的優(yōu)化問題優(yōu)化建模與優(yōu)化建模與LINDO/LINGOLINDO/LINGO軟件軟件第第5 5章章 優(yōu)化建模優(yōu)化建模內(nèi)容提要內(nèi)容提要5.1 5.1 生產(chǎn)與銷售計劃問題生產(chǎn)與銷售計劃問題5.2 5.2 有瓶頸設備的多級生產(chǎn)計劃問題有瓶頸設備的多級生產(chǎn)計劃問題5.3 5.3 下料問題下料問題5.4 5.4 面試順序與消防車調(diào)度問題面試順序與消防車調(diào)度問題5.5 5.5 飛機定位和飛行計劃問題飛機定位和飛行計劃問題 優(yōu)化建模優(yōu)化建模5.1 生產(chǎn)與銷售計劃問題生產(chǎn)與銷售計劃問題 優(yōu)化建模優(yōu)化建模5.1.15.1.1問題實例問題實例 例例

2、5.15.1某公司用兩種原油（某公司用兩種原油（A A和和B B）混合加工成兩種）混合加工成兩種汽油（甲和乙）。甲、乙兩種汽油含原油汽油（甲和乙）。甲、乙兩種汽油含原油A A的最低的最低比例分別為比例分別為50%50%和和60%60%，每噸售價分別為，每噸售價分別為48004800元和元和56005600元。該公司現(xiàn)有原油元。該公司現(xiàn)有原油A A和和B B的庫存量分別為的庫存量分別為500500噸和噸和10001000噸，還可以從市場上買到不超過噸，還可以從市場上買到不超過15001500噸噸的原油的原油A A。原油。原油A A的市場價為：購買量不超過的市場價為：購買量不超過500500噸噸時

3、的單價為時的單價為1000010000元元/ /噸；購買量超過噸；購買量超過500500噸但不超噸但不超過過10001000噸時，超過噸時，超過500500噸的部分噸的部分80008000元元/ /噸；購買噸；購買量超過量超過10001000噸時，超過噸時，超過10001000噸的部分噸的部分60006000元元/ /噸。噸。該公司應如何安排原油的采購和加工。該公司應如何安排原油的采購和加工。 優(yōu)化建模優(yōu)化建模5.1.25.1.2建立模型建立模型問題分析問題分析 安排原油采購、加工的目標是利潤最大，題目中給安排原油采購、加工的目標是利潤最大，題目中給出的是兩種汽油的售價和原油出的是兩種汽油的售

4、價和原油A A的采購價，利潤為的采購價，利潤為銷售汽油的收入與購買原油銷售汽油的收入與購買原油A A的支出之差。這里的的支出之差。這里的難點在于原油難點在于原油A A的采購價與購買量的關系比較復雜，的采購價與購買量的關系比較復雜，是分段函數(shù)關系，能否及如何用線性規(guī)劃、整數(shù)規(guī)是分段函數(shù)關系，能否及如何用線性規(guī)劃、整數(shù)規(guī)劃模型加以處理是關鍵所在。劃模型加以處理是關鍵所在。 優(yōu)化建模優(yōu)化建模模型建立設原油模型建立設原油A A的購買量為的購買量為x x（噸），根據(jù)題目所給數(shù)據(jù)，（噸），根據(jù)題目所給數(shù)據(jù)，采購的支出采購的支出c(x)c(x)可表為如下的分段線性函數(shù)（以下價格以可表為如下的分段線性函數(shù)（以

5、下價格以千元千元/ /噸為單位）：噸為單位）：500)1(1000 630001000)(500 81000500)(0 10)(xxxxxxxc(1)(1)設原油設原油A A用于生產(chǎn)甲、乙兩種汽油的數(shù)量分別為用于生產(chǎn)甲、乙兩種汽油的數(shù)量分別為x x1111和和x x1212（噸），（噸），原油原油B B用于生產(chǎn)甲、乙兩種汽油的數(shù)量分別為用于生產(chǎn)甲、乙兩種汽油的數(shù)量分別為x x2121和和x x2222（噸），（噸），則總的收入為則總的收入為4.8(4.8(x x1111+ +x x2121)+5.6()+5.6(x x1212+ +x x2222) )（千元）。（千元）。于是本例的目標函數(shù)（

6、利潤）為于是本例的目標函數(shù)（利潤）為)()(6 . 5)(8 . 422122111xcxxxxzMax(2)(2) 優(yōu)化建模優(yōu)化建模約束條件包括加工兩種汽油用的原油約束條件包括加工兩種汽油用的原油A A、原油、原油B B庫存量的限制，庫存量的限制，和原油和原油A A購買量的限制，以及兩種汽油含原油購買量的限制，以及兩種汽油含原油A A的比例限制，的比例限制，它們表示為它們表示為xxx5001211（3）10002221 xx（4）1500 x（5）5 . 0211111 xxx（6）6 . 0221212 xxx（7）0,22211211xxxxx（8）由于（由于（1 1）式中的）式中的c

7、c( (x x) )不是線性函數(shù)，（不是線性函數(shù)，（1 1） （8 8）給出的是）給出的是一個非線性規(guī)劃。而且，對于這樣用分段函數(shù)定義的一個非線性規(guī)劃。而且，對于這樣用分段函數(shù)定義的c c( (x x) )，一般的非線性規(guī)劃軟件也難以輸入和求解。能不能想辦法一般的非線性規(guī)劃軟件也難以輸入和求解。能不能想辦法將該模型化簡，從而用現(xiàn)成的軟件求解呢？將該模型化簡，從而用現(xiàn)成的軟件求解呢？ 優(yōu)化建模優(yōu)化建模5.1.3 求解模型 3 3種解法種解法第第1種解法種解法 將原油將原油A的采購量的采購量x分解為三個量，即用分解為三個量，即用x1，x2，x3分別表示以價格分別表示以價格10、8、6千元千元/噸采

8、購的原油噸采購的原油A的噸的噸數(shù)，總支出為數(shù)，總支出為c(x) = 10 x1+8x2+6x3，且，且321xxxx(9)這時目標函數(shù)（這時目標函數(shù)（2）變?yōu)榫€性函數(shù)：）變?yōu)榫€性函數(shù)：)6810()(6 . 5)(8 . 432122122111xxxxxxxzMax(10)應該注意到，只有當以應該注意到，只有當以10千元千元/噸的價格購買噸的價格購買x1=500（噸）時，才能以（噸）時，才能以8千元千元/噸的價格購買噸的價格購買x2（0），這個條件可以表示為），這個條件可以表示為0)500(21xx(11) 優(yōu)化建模優(yōu)化建模同理，只有當以同理，只有當以8 8千元千元/ /噸的價格購買噸的價格

9、購買x x2 2=500=500（噸）時，（噸）時，才能以才能以6 6千元千元/ /噸的價格購買噸的價格購買x x3 3（00），于是），于是0)500(32xx(12)(12)此外，此外，x x1 1，x x2 2，x x3 3的取值范圍是的取值范圍是500,0321xxx(13)(13) 優(yōu)化建模優(yōu)化建模由于有非線性約束由于有非線性約束(11),(12)(11),(12)，(3)(13)(3)(13)構(gòu)成非線性構(gòu)成非線性規(guī)劃模型。規(guī)劃模型。LINGOLINGO程序：程序：Model:Max= 4.8*x11 + 4.8*x21 + 5.6*x12 + 5.6*x22 - 10*x1 - 8

10、*x2 - 6*x3;x11+x12 x + 500;x21+x22 0; 0.4*x12 - 0.6*x22 0;x=x1+x2+x3; (x1 - 500) * x2=0; (x2 - 500) * x3=0; bnd(0,x1, 500);bnd(0,x2, 500);bnd(0,x3,500);end 優(yōu)化建模優(yōu)化建模 將文件存儲并命名為將文件存儲并命名為exam0501a.lg4exam0501a.lg4，執(zhí)行菜單命令執(zhí)行菜單命令“LINGO|Solve”LINGO|Solve”，運行該程序得到：，運行該程序得到： Local optimal solution found. Obje

11、ctive value: 4800.000 Total solver iterations: 26 Variable Value Reduced Cost X11 500.0000 0.000000 X21 500.0000 0.000000 X12 0.000000 0.000000 X22 0.000000 0.000000 X1 0.000000 0.000000 X2 0.000000 0.000000 X3 0.000000 0.000000 X 0.000000 0.000000 優(yōu)化建模優(yōu)化建模最優(yōu)解最優(yōu)解: : 用庫存的用庫存的500500噸原油噸原油A A、500500噸原油

12、噸原油B B生產(chǎn)生產(chǎn)10001000噸汽油甲，不購買新的原油噸汽油甲，不購買新的原油A A，利潤為，利潤為48004800（千元）（千元） 但是此時但是此時LINGOLINGO得到的結(jié)果只是一個得到的結(jié)果只是一個局部最優(yōu)解局部最優(yōu)解可以用菜單命令可以用菜單命令“LINGO|Options”LINGO|Options”在在“Global Global Solver”Solver”選項卡上啟動全局優(yōu)化（選項卡上啟動全局優(yōu)化（Use Global Use Global SolverSolver）選項，然后重新執(zhí)行菜單命令）選項，然后重新執(zhí)行菜單命令“LINGO|Solve” , LINGO|Solv

13、e” , 得到：得到： Global optimal solution found.Global optimal solution found. Objective value: 5000.002 Objective value: 5000.002 Extended solver steps: 3 Extended solver steps: 3 Total solver iterations: 187 Total solver iterations: 187 優(yōu)化建模優(yōu)化建模Variable Value Reduced CostX11 0.000000 0.000000X21 0.00000

14、0 0.000000X12 1500.000 0.000000X22 1000.000 0.000000X1 500.0000 0.000000X2 499.9990 0.000000X3 0.9536707E-03 0.000000X 1000.000 0.000000此時此時LINGOLINGO得到的結(jié)果是一個得到的結(jié)果是一個全局最優(yōu)解全局最優(yōu)解（Global optimal solutionGlobal optimal solution）：購買）：購買10001000噸原油噸原油A A，與庫存的與庫存的500500噸原油噸原油A A和和10001000噸原油噸原油B B一起，共生產(chǎn)一起，

15、共生產(chǎn)25002500噸汽油乙，利潤為噸汽油乙，利潤為50005000（千元），高于剛剛得（千元），高于剛剛得到的局部最優(yōu)解對應的利潤到的局部最優(yōu)解對應的利潤48004800（千元）。（千元）。 優(yōu)化建模優(yōu)化建模第第2 2種解法種解法: : 引入引入0-10-1變量將（變量將（1111）和（）和（1212）轉(zhuǎn)化為線性約束）轉(zhuǎn)化為線性約束令令y1=1，y2=1，y3=1分別表示以分別表示以10千元千元/噸、噸、8千元千元/噸、噸、6千元千元/噸的價格采購原油噸的價格采購原油A，則約束（，則約束（11）和（和（12）可以替換為）可以替換為112500500yxy223500500yxy33500y

16、x (14)(15)(16) y1，y2，y3 =0或或1(17) 優(yōu)化建模優(yōu)化建模（3 3） （1010），（），（1313） （1717）構(gòu)成混合整數(shù)線性）構(gòu)成混合整數(shù)線性規(guī)劃模型，將它輸入規(guī)劃模型，將它輸入LINDOLINDO軟件：軟件： 優(yōu)化建模優(yōu)化建模Max 4.8x11+4.8x21+5.6x12+5.6x22-10 x1-8x2-6x3stx-x1-x2-x3=0 x11+x12-x500 x21+x220 0.4x12-0.6x220 x1-500y10 x2-500y20 x3-500y30 x2-500y30 endint y1int y2int y3 優(yōu)化建模優(yōu)化建模運行

17、該程序得到：OBJECTIVE FUNCTION VALUE 1) 5000.000 VARIABLE VALUE REDUCED COST Y1 1.000000 0.000000 Y2 1.000000 2200.000000 Y3 1.000000 1200.000000 X11 0.000000 0.800000 X21 0.000000 0.800000 X12 1500.000000 0.000000 X22 1000.000000 0.000000 X1 500.000000 0.000000 X2 500.000000 0.000000 X3 0.000000 0.400000

18、 X 1000.000000 0.000000這個結(jié)果與前面非線性規(guī)劃模型用全局優(yōu)化得到的結(jié)果相同。這個結(jié)果與前面非線性規(guī)劃模型用全局優(yōu)化得到的結(jié)果相同。 優(yōu)化建模優(yōu)化建模第第3 3種解法種解法 直接處理分段線性函數(shù)c(x)。（1）式表示的函數(shù)c(x)如圖5-1。c(x)x1200090005000050010001500圖圖5-1 分段線性函數(shù)分段線性函數(shù)c(x)圖形圖形 優(yōu)化建模優(yōu)化建模記x軸上的分點為b1=0, b2=500, b3=1000, b4=1500。當x在第1個小區(qū)間 b1, b2時，記x= z1b1+z2b2，z1+z2=1，z1, z20, 因為c(x)在b1, b2是線

19、性的，所以c(x)= z1c(b1)+z2c(b2)。同樣，當x在第2個小區(qū)間 b2, b3時，x= z2b2+z3b3，z2+z3=1，z2, z30, c(x)= z2c(b2)+z3c(b3)。當x在第3個小區(qū)間 b3, b4時，x= z3b3+z4b4，z3+z4=1，z3, z40, c(x)= z3c(b3)+z4c(b4)。為了表示x在哪個小區(qū)間，引入0-1變量yk(k=1,2,3)，當x在第k個小區(qū)間時，yk=1，否則，yk=0。這樣, z1, z2, z3, z4, y1, y2, y3應滿足3432321211,yzyyzyyzyz)4 , 3 , 2 , 1(0, 143

20、21kzzzzzk10, 1321321或yyyyyy(18)(19)(20) 優(yōu)化建模優(yōu)化建模此時x和c(x)可以統(tǒng)一地表示為4324433221115001000500zzzbzbzbzbzx（2）（10），（18）（22）也構(gòu)成一個混合整數(shù)線性規(guī)劃模型，可以用LINDO求解。不過，我們還是將它輸入LINGO軟件，因為其擴展性更好（即當分段函數(shù)的分段數(shù)更多時，只需要對下面程序作很小的改動）。輸入的LINGO模型如下：432443322111200090005000)()()()()(zzzbczbczbczbczxc(22) 優(yōu)化建模優(yōu)化建模輸入的LINGO模型如下：Model:SETS:

21、Points/1.4/: b, c, y, z;! 端點數(shù)為4，即分段數(shù)為3;ENDSETSDATA:b=0 500 1000 1500;c=0 5000 9000 12000;y=,0;! 增加的虛擬變量y(4)=0;ENDDATA 優(yōu)化建模優(yōu)化建模Max= 4.8*x11 + 4.8*x21 + 5.6*x12 + 5.6*x22 - sum(Points: c*z);x11+x12 x + 500;x21+x22 0; 0.4*x12 - 0.6*x22 0;sum(Points: b*z)=x;for(Points(i)|i#eq#1: z(i) = y(i);for(Points(i

22、)|i#ne#1: z(i) 0時取值時取值1, 否則取值否則取值0.在上述數(shù)學符號中，只有在上述數(shù)學符號中，只有Xi t ,Ii t ,Yi t ,為決策變量為決策變量; 其余均為已知的計劃參數(shù)。其余均為已知的計劃參數(shù)。 優(yōu)化建模優(yōu)化建模 優(yōu)化建模優(yōu)化建模目標函數(shù)目標函數(shù) 這個問題的目標是使生產(chǎn)準備費用和庫存費用這個問題的目標是使生產(chǎn)準備費用和庫存費用的總和最小。因此，目標函數(shù)應該是每個項的總和最小。因此，目標函數(shù)應該是每個項目在每個時段上的生產(chǎn)準備費用和庫存費用目在每個時段上的生產(chǎn)準備費用和庫存費用的總和，即的總和，即NiTttitititiIhYs11,)(28)約束條件約束條件這個問題

23、中的約束有這么幾類：每個項目的物流這個問題中的約束有這么幾類：每個項目的物流應該守恒、資源能力限制應該滿足、每時段生應該守恒、資源能力限制應該滿足、每時段生產(chǎn)某項目前必須經(jīng)過生產(chǎn)準備和非負約束產(chǎn)某項目前必須經(jīng)過生產(chǎn)準備和非負約束 （對（對Yi,j是是0-1約束）。約束）。 優(yōu)化建模優(yōu)化建模TtNiXrdIXIiSjtjjititititi, 1, 1)(,1,(29)資源能力限制比較容易理解，即資源能力限制比較容易理解，即TtKkCXaNitktitik, 1, 11,(30)所謂物流守恒（假設所謂物流守恒（假設Ii,0 =0） 優(yōu)化建模優(yōu)化建模(31)TtNiIYMYXtitititi, 1

24、, 10,1 , 0,0,每時段生產(chǎn)某項目前必須經(jīng)過生產(chǎn)準備，也就是說當每時段生產(chǎn)某項目前必須經(jīng)過生產(chǎn)準備，也就是說當Xit=0時時Yit=0；Xit0時時Yit=1。這本來是一個非線性約束，。這本來是一個非線性約束，但是通過引入?yún)?shù)但是通過引入?yún)?shù)M（很大的正數(shù)，表示每個項目每個（很大的正數(shù)，表示每個項目每個時段的最大產(chǎn)量）可以化成線性約束，即：時段的最大產(chǎn)量）可以化成線性約束，即： 總結(jié)總結(jié): : 這個問題的優(yōu)化模型就是在約束（這個問題的優(yōu)化模型就是在約束（2929）（）（3030）（3131）下使目標函數(shù)（）下使目標函數(shù)（2828）達到最小。）達到最小。 優(yōu)化建模優(yōu)化建模5.2.3 5.

25、2.3 求解模型求解模型本例生產(chǎn)項目總數(shù)本例生產(chǎn)項目總數(shù)N=7(A、B、C、D、E、F、G) ，計，計劃期長度劃期長度T=6（周），瓶頸資源種類數(shù)（周），瓶頸資源種類數(shù)K=1。只有。只有A有外部需求，所以有外部需求，所以di,t中只有中只有d1,t可以取非零需求，即可以取非零需求，即表表5-1中的第中的第2行的數(shù)據(jù)，其他全部為零。行的數(shù)據(jù)，其他全部為零。 參數(shù)參數(shù)si,t 、 hi,t只與項目只與項目i有關，而不隨時段有關，而不隨時段t變化，所以可以略去變化，所以可以略去下標下標t，其數(shù)值就是表，其數(shù)值就是表5-1中的最后兩行數(shù)據(jù)。中的最后兩行數(shù)據(jù)。由于只有一種資源，參數(shù)由于只有一種資源，參數(shù)

26、Ck,t可以略去下標可以略去下標k，其數(shù)值，其數(shù)值就是表就是表5-1中的第中的第3行的數(shù)據(jù)；而行的數(shù)據(jù)；而ak,I,t只與項目只與項目i有關，有關，而不隨時段而不隨時段t變化，所以可以同時略去下標變化，所以可以同時略去下標k和和t，即，即a2=5，a3=8（其他（其他ai為為0）。從圖）。從圖6-2中容易得到項中容易得到項目目i的直接后繼項目集合的直接后繼項目集合S(i)和消耗系數(shù)。和消耗系數(shù)。 優(yōu)化建模優(yōu)化建模準備以下的數(shù)據(jù)文件（文本文件準備以下的數(shù)據(jù)文件（文本文件exam0502.LDT，可，可以看到其中也可以含有注釋語句）：以看到其中也可以含有注釋語句）：! 項目集合;ABCDEFG!

27、計劃期集合;123456! 需求;400100090100 0 0 0 0 00 0 0 0 0 00 0 0 0 0 00 0 0 0 0 00 0 0 0 0 00 0 0 0 0 0 優(yōu)化建模優(yōu)化建模! 能力;1000005000 5000 1000 1000! 生產(chǎn)準備費;4005001000 300200400100! 庫存費;120.61.00.04 0.03 0.04 0.04! 對能力的消耗系數(shù)；0580000 優(yōu)化建模優(yōu)化建模! 項目間的消耗系數(shù): req(i,j)表示j用到多少i;0 0 0 0 0 0 05 0 0 0 0 0 07 0 0 0 0 0 00 9 0 0

28、0 0 00 11 0 0 0 0 00 0 13 0 0 0 00 0 15 0 0 0 0! 數(shù)據(jù)結(jié)束; 優(yōu)化建模優(yōu)化建模對本例，對本例，A的外部總需求為的外部總需求為240，所以任何項目，所以任何項目的產(chǎn)量不會超過的產(chǎn)量不會超過24071525000（從圖（從圖6-2可以知道，這里可以知道，這里715已經(jīng)是每件產(chǎn)品已經(jīng)是每件產(chǎn)品A對任對任意一個項目的最大的消耗系數(shù)了），所以取意一個項目的最大的消耗系數(shù)了），所以取M=25000就已經(jīng)足夠了。就已經(jīng)足夠了。本例中的具體模型可以如下輸入本例中的具體模型可以如下輸入LINGO軟件：軟件：MODEL:TITLE 瓶頸設備的多級生產(chǎn)計劃;! 從文本

29、文件exam0502.LDT中讀取數(shù)據(jù); 優(yōu)化建模優(yōu)化建模SETS:! PART = 項目集合, Setup = 生產(chǎn)準備費，Hold = 單件庫存成本， A = 對瓶頸資源的消耗系數(shù);PART/ FILE( exam0502.LDT)/ : Setup, Hold, A;! TIME = 計劃期集合，Capacity = 瓶頸設備的能力;TIME / FILE( exam0502.LDT)/ : Capacity;! USES = 項目結(jié)構(gòu)關系，Req = 項目之間的消耗系數(shù);USES( PART, PART) : Req;! PXT = 項目與時間的派生集合，Demand = 外部需求,

30、X = 產(chǎn)量（批量）, Y = 0/1變量，INV = 庫存;PXT( PART, TIME): Demand, X, Y, Inv;ENDSETS 優(yōu)化建模優(yōu)化建模! 目標函數(shù);OBJ Min = sum(PXT(i,t): setup(i)*Y(i,t) + hold(i)*Inv(i,t) );! 物流平衡方程;FOR( PXT(i, t) | t #NE# 1 : Bal Inv(i,t-1)+X(i,t)-Inv(i,t) = Demand(i, t) + SUM( USES(i,j): Req(i,j)*X(j,t) );FOR( PXT(i, t) | t #eq# 1 : Ba

31、0 X(i,t)-Inv(i,t) = Demand(i, t) + SUM( USES(i,j): Req(i,j)*X(j,t) );! 能力約束;FOR( TIME(t): Cap SUM( PART(i): A(i)*X(i,t) ) Capacity(t) ); 優(yōu)化建模優(yōu)化建模! 其他約束;M = 25000;FOR( PXT(i,t): X(i,t) = 50 x2 + 2x4 + x5 + 3x6 = 20 x3 + x5 + 2x7 = 15endgin 7 優(yōu)化建模優(yōu)化建模求解可以得到最優(yōu)解如下：求解可以得到最優(yōu)解如下： OBJECTIVE FUNCTION VALUE 1

32、) 27.00000 VARIABLE VALUE REDUCED COST X1 0.000000 3.000000 X2 12.000000 1.000000 X3 0.000000 3.000000 X4 0.000000 3.000000 X5 15.000000 1.000000 X6 0.000000 1.000000 X7 0.000000 3.000000 優(yōu)化建模優(yōu)化建模即按照模式即按照模式2 2切割切割1212根原料鋼管，按照模式根原料鋼管，按照模式5 5切切割割1515根原料鋼管，共根原料鋼管，共2727根，總余料量為根，總余料量為2727米。米。顯然，在總余料量最小的目

33、標下，最優(yōu)解將是顯然，在總余料量最小的目標下，最優(yōu)解將是使用余料盡可能小的切割模式（模式使用余料盡可能小的切割模式（模式2 2和和5 5的余的余料為料為1 1米），這會導致切割原料鋼管的總根數(shù)較米），這會導致切割原料鋼管的總根數(shù)較多。多。 優(yōu)化建模優(yōu)化建模2. 2. 將（將（3333） （3636）構(gòu)成的整數(shù)線性規(guī)劃模型）構(gòu)成的整數(shù)線性規(guī)劃模型（加上整數(shù)約束）輸入（加上整數(shù)約束）輸入LINDOLINDO：Title 鋼管下料鋼管下料 - 最小化鋼管根數(shù)最小化鋼管根數(shù)Min x1 + x2 + x3 + x4 + x5 + x6 + x7 s.t. 4x1 + 3x2 + 2x3 + x4 +

34、x5 = 50 x2 + 2x4 + x5 + 3x6 = 20 x3 + x5 + 2x7 = 15endgin 7 優(yōu)化建模優(yōu)化建模求解，可以得到最優(yōu)解如下：求解，可以得到最優(yōu)解如下：OBJECTIVE FUNCTION VALUE 1) 25.00000 VARIABLE VALUE REDUCED COST X1 0.000000 1.000000 X2 15.000000 1.000000 X3 0.000000 1.000000 X4 0.000000 1.000000 X5 5.000000 1.000000 X6 0.000000 1.000000 X7 5.000000 1.

35、000000 優(yōu)化建模優(yōu)化建模即按照模式即按照模式2切割切割15根原料鋼管，按模式根原料鋼管，按模式5切割切割5根，按模根，按模式式7切割切割5根，共根，共27根，可算出總余料量為根，可算出總余料量為35米。與上面米。與上面得到的結(jié)果相比，總余料量增加了得到的結(jié)果相比，總余料量增加了8米，但是所用的原料米，但是所用的原料鋼管的總根數(shù)減少了鋼管的總根數(shù)減少了2根。在余料沒有什么用途的情況下，根。在余料沒有什么用途的情況下，通常選擇總根數(shù)最少為目標。通常選擇總根數(shù)最少為目標。 優(yōu)化建模優(yōu)化建模問題問題2）的求解）的求解問題分析問題分析 按照解問題按照解問題1）的思路，可以通過枚舉法首先確）的思路，

36、可以通過枚舉法首先確定哪些切割模式是可行的。但由于需求的鋼管規(guī)格增加到定哪些切割模式是可行的。但由于需求的鋼管規(guī)格增加到4種，所以枚舉法的工作量較大。下面介紹的整數(shù)非線性種，所以枚舉法的工作量較大。下面介紹的整數(shù)非線性規(guī)劃模型，可以同時確定切割模式和切割計劃，是帶有普規(guī)劃模型，可以同時確定切割模式和切割計劃，是帶有普遍性的方法。遍性的方法。同同1）類似，一個合理的切割模式的余料不應該大于或等）類似，一個合理的切割模式的余料不應該大于或等于客戶需要的鋼管的最小尺寸（本題中為于客戶需要的鋼管的最小尺寸（本題中為4米），切割計米），切割計劃中只使用合理的切割模式，而由于本題中參數(shù)都是整數(shù)，劃中只使用

37、合理的切割模式，而由于本題中參數(shù)都是整數(shù)，所以合理的切割模式的余量不能大于所以合理的切割模式的余量不能大于3米。此外，這里我米。此外，這里我們僅選擇總根數(shù)最少為目標進行求解。們僅選擇總根數(shù)最少為目標進行求解。 優(yōu)化建模優(yōu)化建模模型建立模型建立決策變量決策變量 由于不同切割模式不能超過由于不同切割模式不能超過3種，可以用種，可以用xi 表示表示按照第按照第i種模式（種模式（i=1, 2, 3）切割的原料鋼管的根數(shù)，顯）切割的原料鋼管的根數(shù)，顯然它們應當是非負整數(shù)。然它們應當是非負整數(shù)。設設所使用的第所使用的第i種切割模式下種切割模式下每根原料鋼管生產(chǎn)每根原料鋼管生產(chǎn)4米長、米長、5米長、米長、6

38、米長和米長和8米長的鋼米長的鋼管數(shù)量分別為管數(shù)量分別為r1i, r2i, r3i, r4i（非負整數(shù)非負整數(shù)）。）。 決策目標決策目標 以切割原料鋼管的總根數(shù)最少為目標，即目標為以切割原料鋼管的總根數(shù)最少為目標，即目標為321xxxMin（37） 優(yōu)化建模優(yōu)化建模約束條件約束條件 為滿足客戶的需求，應有為滿足客戶的需求，應有50313212111xrxrxr(38)10323222121xrxrxr20333232131xrxrxrxrxr(39)(40)(41) 優(yōu)化建模優(yōu)化建模每一種切割模式必須可行、合理，所以每根原料鋼管的每一種切割模式必須可行、合理，所以每根原

39、料鋼管的成品量不能超過成品量不能超過19米，也不能少于米，也不能少于16米（余量不能大于米（余量不能大于3米），于是米），于是1986541641312111rrrr(42)1986541642322212rrrr(43)1986541643332313rrrr(44) 優(yōu)化建模優(yōu)化建模模型求解模型求解（37）（44）構(gòu)成這個問題的優(yōu)化模型。由于在（）構(gòu)成這個問題的優(yōu)化模型。由于在（38）（41）式中出現(xiàn)了決策變量的乘積，所以這是一個整數(shù)非）式中出現(xiàn)了決策變量的乘積，所以這是一個整數(shù)非線性規(guī)劃模型，雖然用線性規(guī)劃模型，雖然用LINGO軟件可以直接求解，但我軟件可以直接求解，但我們發(fā)現(xiàn)在較低版本

40、的們發(fā)現(xiàn)在較低版本的LINGO軟件中需要運行很長時間也軟件中需要運行很長時間也難以得到最優(yōu)解。為了減少運行時間，可以增加一些顯然難以得到最優(yōu)解。為了減少運行時間，可以增加一些顯然的約束條件，從而縮小可行解的搜索范圍。的約束條件，從而縮小可行解的搜索范圍。例如，由于例如，由于3種切割模式的排列順序是無關緊要的，所以不種切割模式的排列順序是無關緊要的，所以不妨增加以下約束：妨增加以下約束：321xxx（45） 優(yōu)化建模優(yōu)化建模又例如，我們注意到所需原料鋼管的總根數(shù)有著明顯的又例如，我們注意到所需原料鋼管的總根數(shù)有著明顯的上界和下界。首先，無論如何，原料鋼管的總根數(shù)不上界和下界。首先，無論如何，原料

41、鋼管的總根數(shù)不可能少于可能少于 2619158206105504（根）（根）其次，考慮一種非常特殊的生產(chǎn)計劃：第一種切割模式下其次，考慮一種非常特殊的生產(chǎn)計劃：第一種切割模式下只生產(chǎn)只生產(chǎn)4米鋼管，一根原料鋼管切割成米鋼管，一根原料鋼管切割成4根根4米鋼管，為滿米鋼管，為滿足足50根根4米鋼管的需求，需要米鋼管的需求，需要13根原料鋼管；第二種切割根原料鋼管；第二種切割模式下只生產(chǎn)模式下只生產(chǎn)5米、米、6米鋼管，一根原料鋼管切割成米鋼管，一根原料鋼管切割成1根根5米鋼管和米鋼管和2根根6米鋼管，為滿足米鋼管，為滿足10根根5米和米和20根根6米鋼管的米鋼管的需求，需要需求，需要10根原料鋼管；

42、根原料鋼管； 優(yōu)化建模優(yōu)化建模第三種切割模式下只生產(chǎn)第三種切割模式下只生產(chǎn)8米鋼管，一根原料鋼管切割成米鋼管，一根原料鋼管切割成2根根8米鋼管，為滿足米鋼管，為滿足15根根8米鋼管的需求，需要米鋼管的需求，需要8根原料鋼根原料鋼管。于是滿足要求的這種生產(chǎn)計劃共需管。于是滿足要求的這種生產(chǎn)計劃共需13+10+8=31根原根原料鋼管，這就得到了最優(yōu)解的一個上界。所以可增加以料鋼管，這就得到了最優(yōu)解的一個上界。所以可增加以下約束：下約束：3126321xxx(46)將（37）（46）構(gòu)成的模型輸入LINGO如下： 優(yōu)化建模優(yōu)化建模將（37）（46）構(gòu)成的模型輸入LINGO如下：model:Title

43、 鋼管下料鋼管下料 - 最小化鋼管根數(shù)的最小化鋼管根數(shù)的LINGO模型模型;min=x1+x2+x3;x1*r11+x2*r12+x3*r13 =50;x1*r21+x2*r22+x3*r23 =10;x1*r31+x2*r32+x3*r33 =20;x1*r41+x2*r42+x3*r43 =15;4*r11+5*r21+6*r31+8*r41 =19;4*r12+5*r22+6*r32+8*r42 =19;4*r13+5*r23+6*r33+8*r43 =16;4*r12+5*r22+6*r32+8*r42 =16;4*r13+5*r23+6*r33+8*r43 =16;x1+x2+x3

44、= 26;x1+x2+x3 =x2;x2=x3;gin(x1); gin(x2); gin(x3);gin(r11);gin(r12);gin(r13);gin(r21);gin(r22);gin(r23);gin(r31);gin(r32);gin(r33);gin(r41);gin(r42);gin(r43);end 優(yōu)化建模優(yōu)化建模經(jīng)過經(jīng)過LINGO求解，得到輸出如下：求解，得到輸出如下： Local optimal solution found. Objective value: 28.00000 Extended solver steps: 72 Total solver itera

45、tions: 3404 Model Title: 鋼管下料鋼管下料-最小化鋼管根數(shù)的最小化鋼管根數(shù)的LINGO模型模型 優(yōu)化建模優(yōu)化建模 Variable Value Reduced CostX1 10.00000 1.000000X2 10.00000 1.000000X3 8.000000 1.000000R11 2.000000 0.000000R12 3.000000 0.000000R13 0.000000 0.000000R21 1.000000 0.000000R22 0.000000 0.000000R23 0.000000 0.000000R31 1.000000 0.000

46、000R32 1.000000 0.000000R33 0.000000 0.000000R41 0.000000 0.000000R42 0.000000 0.000000R43 2.000000 0.000000 優(yōu)化建模優(yōu)化建模即按照模式即按照模式1、2、3分別切割分別切割10、10、8根原料鋼管，使用根原料鋼管，使用原料鋼管總根數(shù)為原料鋼管總根數(shù)為28根。第一種切割模式下一根原料鋼管根。第一種切割模式下一根原料鋼管切割成切割成3根根4米鋼管和米鋼管和1根根6米鋼管；第二種切割模式下一根米鋼管；第二種切割模式下一根原料鋼管切割成原料鋼管切割成2根根4米鋼管、米鋼管、1根根5米鋼管和米鋼管

47、和1根根6米鋼管；米鋼管；第三種切割模式下一根原料鋼管切割成第三種切割模式下一根原料鋼管切割成2根根8米鋼管。米鋼管。 如果充分利用如果充分利用LINGO建模語言的能力，使用集合和屬性建模語言的能力，使用集合和屬性的概念，可以編寫以下的概念，可以編寫以下LINGO程序，這種方法更具有一程序，這種方法更具有一般的通用性，并有利于輸入更大規(guī)模的下料問題的優(yōu)化模般的通用性，并有利于輸入更大規(guī)模的下料問題的優(yōu)化模型：型： 優(yōu)化建模優(yōu)化建模model:Title 鋼管下料鋼管下料 - 最小化鋼管根數(shù)的最小化鋼管根數(shù)的LINGO模型模型;SETS: NEEDS/1.4/:LENGTH,NUM; ! 定義基

48、本集合定義基本集合NEEDS及其屬性及其屬性LENGTH,NUM;CUTS/1.3/:X; ! 定義基本集合定義基本集合CUTS及其屬性及其屬性X;PATTERNS(NEEDS,CUTS):R; ! 定義派生集合定義派生集合PATTERNS（這是一個稠密集合）及其屬性（這是一個稠密集合）及其屬性R;ENDSETSDATA:LENGTH=4 5 6 8;NUM=50 10 20 15;CAPACITY=19;ENDDATAmin=SUM(CUTS(I): X(I) ); 優(yōu)化建模優(yōu)化建模!目標函數(shù)目標函數(shù);FOR(NEEDS(I): SUM(CUTS(J): X(J)*R(I,J) ) NUM(

49、I) ); !滿足需求約束滿足需求約束;FOR(CUTS(J): SUM(NEEDS(I): LENGTH(I)*R(I,J) ) CAPACITY -MIN(NEEDS(I):LENGTH(I) ); !合理切割模式約束合理切割模式約束;SUM(CUTS(I): X(I) ) 26; SUM(CUTS(I): X(I) ) X(I+1) ); !人為增加約束人為增加約束;FOR(CUTS(J): GIN(X(J) ) ;FOR(PATTERNS(I,J): GIN(R(I,J) );end求解這個模型，得到的結(jié)果與前面的結(jié)果完全相同。求解這個模型，得到的結(jié)果與前面的結(jié)果完全相同。 優(yōu)化建模優(yōu)

50、化建模5.3.2易拉罐下料問題易拉罐下料問題例例5.4 某公司采用一套沖壓設備生產(chǎn)一種罐裝飲料某公司采用一套沖壓設備生產(chǎn)一種罐裝飲料的易拉罐，這種易拉罐是用鍍錫板沖壓制成的（參見的易拉罐，這種易拉罐是用鍍錫板沖壓制成的（參見圖圖5-3）。易拉罐為圓柱形，包括罐身、上蓋和下底，）。易拉罐為圓柱形，包括罐身、上蓋和下底，罐身高罐身高10厘米，上蓋和下底的直徑均為厘米，上蓋和下底的直徑均為5厘米。該公厘米。該公司使用兩種不同規(guī)格的鍍錫板原料，規(guī)格司使用兩種不同規(guī)格的鍍錫板原料，規(guī)格1的鍍錫板的鍍錫板為正方形，邊長為正方形，邊長24厘米；規(guī)格厘米；規(guī)格2的鍍錫板為長方形，的鍍錫板為長方形，長、寬分別為

51、長、寬分別為32和和28厘米。由于生產(chǎn)設備和生產(chǎn)工藝厘米。由于生產(chǎn)設備和生產(chǎn)工藝的限制，對于規(guī)格的限制，對于規(guī)格1的鍍鍍錫板原料，只可以按照圖的鍍鍍錫板原料，只可以按照圖2中的模式中的模式1、2或或3進行沖壓；對于規(guī)格進行沖壓；對于規(guī)格2的鍍錫板原料的鍍錫板原料只能按照模式只能按照模式4進行沖壓。使用模式進行沖壓。使用模式1、2、3、4進行進行每次沖壓所需要的時間分別為每次沖壓所需要的時間分別為1.5、2、1、3（秒）。（秒）。 優(yōu)化建模優(yōu)化建模模式1模式2模式3模式4上蓋下底罐身圖5-3 易拉罐下料模式 優(yōu)化建模優(yōu)化建模該工廠每周工作該工廠每周工作40小時，每周可供使用的規(guī)格小時，每周可供使

52、用的規(guī)格1、2的鍍錫板的鍍錫板原料分別為原料分別為5萬張和萬張和2萬張。目前每只易拉罐的利潤為萬張。目前每只易拉罐的利潤為0.10元，元，原料余料損失為原料余料損失為0.001元元 / 厘米厘米2（如果周末有罐身、上蓋或（如果周末有罐身、上蓋或下底不能配套組裝成易拉罐出售，也看作是原料余料損失）。下底不能配套組裝成易拉罐出售，也看作是原料余料損失）。工廠應如何安排每周的生產(chǎn)？工廠應如何安排每周的生產(chǎn)？已知上蓋和下底的直徑已知上蓋和下底的直徑d=5厘米，可得其面積為厘米，可得其面積為 4/2ds 19.6厘米厘米2 優(yōu)化建模優(yōu)化建模表表5-4 4種沖壓模式的特征種沖壓模式的特征罐身個數(shù)底、蓋個數(shù)

53、余料損失（厘米2）沖壓時間（秒）模式1110222.61.5模式224183.32模式3016261.81模式445169.53問題的目標顯然應是易拉罐的利潤扣除原料余料損失后的凈利潤最大，約束條件除每周工作時間和原料數(shù)量外，還要考慮罐身和底、蓋的配套組裝。 優(yōu)化建模優(yōu)化建模模型建立模型建立決策變量決策變量 用用xi 表示按照第表示按照第i種模式的沖壓次數(shù)（種模式的沖壓次數(shù)（i=1, 2, 3, 4），），y1表示表示一周生產(chǎn)的易拉罐個數(shù)。為計算不能配套組裝的罐身和底、蓋造成的一周生產(chǎn)的易拉罐個數(shù)。為計算不能配套組裝的罐身和底、蓋造成的原料損失，用原料損失，用y2表示不配套的罐身個數(shù)，表示不配

54、套的罐身個數(shù)，y3表示不配套的底、蓋個數(shù)。表示不配套的底、蓋個數(shù)。雖然實際上雖然實際上xi和和y1，y2，y3應該是整數(shù)。但是由于生產(chǎn)量相當大，可以應該是整數(shù)。但是由于生產(chǎn)量相當大，可以把它們看成是實數(shù)，從而用線性規(guī)劃模型處理。把它們看成是實數(shù)，從而用線性規(guī)劃模型處理。決策目標決策目標 假設每周生產(chǎn)的易拉罐能夠全部售出，公司每周的銷假設每周生產(chǎn)的易拉罐能夠全部售出，公司每周的銷售利潤是售利潤是0.1y1。原料余料損失包括兩部分：。原料余料損失包括兩部分：4種沖壓模式下的余種沖壓模式下的余料損失，和不配套的罐身和底、蓋造成的原料損失。按照前面料損失，和不配套的罐身和底、蓋造成的原料損失。按照前面

55、的計算及表的計算及表2的結(jié)果，總損失為的結(jié)果，總損失為0.001(222.6x1 + 183.3x2 + 261.8x3 + 169.5x4 + 157.1y2 +19.6y3)。 優(yōu)化建模優(yōu)化建模于是，決策目標為于是，決策目標為)6 .191 .1575 .1698 .2613 .1836 .222(001. 01 . 03243211yyxxxxyMax(47)約束條件約束條件 時間約束：每周工作時間不超過時間約束：每周工作時間不超過40小時小時=144000（秒），由表（秒），由表2最后一列得最后一列得144000325 . 14321xxxx(48)原料約束：原料約束：每周可供使用的規(guī)

56、格每周可供使用的規(guī)格1、2的鍍錫板原料分別為的鍍錫板原料分別為50000張和張和20000張，即張，即50000321xxx(49)200004x(50) 優(yōu)化建模優(yōu)化建模 配套約束：配套約束： 由表由表2一周生產(chǎn)的罐身個數(shù)為一周生產(chǎn)的罐身個數(shù)為x1 + 2x2 + 4x4, 一周一周生產(chǎn)的底、蓋個數(shù)為生產(chǎn)的底、蓋個數(shù)為10 x1 + 4x2 + 16x3+ 5x4，因為應盡可能，因為應盡可能將它們配套組裝成易拉罐銷售。所以將它們配套組裝成易拉罐銷售。所以y1滿足滿足2/ )516410(,42min43214211xxxxxxxy (51)這時不配套的罐身個數(shù)這時不配套的罐身個數(shù)y2，和不配

57、套的底、蓋個數(shù)，和不配套的底、蓋個數(shù)y3應為應為1421242yxxxy (52)1432132516410yxxxxy (53) 優(yōu)化建模優(yōu)化建模（47）（53）就是我們得到的模型，其中（）就是我們得到的模型，其中（51）是一個非線性關系，）是一個非線性關系，不易直接處理，不易直接處理， 但是它可以等價為以下兩個線性不等式：但是它可以等價為以下兩個線性不等式：421142xxxy (54)2/ )516410(43211xxxxy (55)模型求解模型求解將模型（將模型（47）（50）和（）和（52）（55）直接輸入）直接輸入LINDO（輸入（輸入LINGO也可以），求解時也可以），求解時L

58、INDO發(fā)出警告信息（程序和警告信發(fā)出警告信息（程序和警告信息參見圖息參見圖5-4）。）。 圖中錯誤編號圖中錯誤編號“66”的含義（參見第的含義（參見第4章的錯誤章的錯誤代碼表）是：模型中數(shù)據(jù)不平衡，所以發(fā)出警告信息（注意，只代碼表）是：模型中數(shù)據(jù)不平衡，所以發(fā)出警告信息（注意，只是警告信息，所以仍然可以繼續(xù)求解）。求解結(jié)果是：是警告信息，所以仍然可以繼續(xù)求解）。求解結(jié)果是： 優(yōu)化建模優(yōu)化建模 OBJECTIVE FUNCTION VALUE 1) 4298.337 VARIABLE VALUE REDUCED COST Y1 160250.000000 0.000000 X1 0.00000

59、0 0.000050 X2 40125.000000 0.000000 X3 3750.000000 0.000000 X4 20000.000000 0.000000 Y2 0.000000 0.223331 Y3 0.000000 0.036484 優(yōu)化建模優(yōu)化建模圖圖5-4 模型中數(shù)據(jù)不平衡的警告信息模型中數(shù)據(jù)不平衡的警告信息 優(yōu)化建模優(yōu)化建模這個結(jié)果可靠嗎？由于這個結(jié)果可靠嗎？由于LINDO警告模型中數(shù)據(jù)之間的數(shù)警告模型中數(shù)據(jù)之間的數(shù)量級差別太大，所以我們可以進行預處理，縮小數(shù)據(jù)之量級差別太大，所以我們可以進行預處理，縮小數(shù)據(jù)之間的差別。實際上，約束（間的差別。實際上，約束（48）（5

60、0）中右端項的數(shù)值）中右端項的數(shù)值過大（與左端的系數(shù)相比較），過大（與左端的系數(shù)相比較），LINDO在計算中容易產(chǎn)在計算中容易產(chǎn)生比較大的誤差，所以出現(xiàn)此警告信息。生比較大的誤差，所以出現(xiàn)此警告信息。為了解決這一問題，可以將所有決策變量擴大為了解決這一問題，可以將所有決策變量擴大10000倍倍（相當于（相當于xi以萬次為單位，以萬次為單位，yi以萬件為單位）。此時，目以萬件為單位）。此時，目標（標（47）可以保持不變（記住得到的結(jié)果單位為萬元就）可以保持不變（記住得到的結(jié)果單位為萬元就可以了），而約束（可以了），而約束（48）（50）改為）改為4 .14325 . 14321xxxx (56)