優(yōu)化建模與LINGO第05章課件

1、生產(chǎn)與服務(wù)運(yùn)作管理中的優(yōu)化問題優(yōu)化建模與LINDO/LINGO軟件第5章內(nèi)容提要5.1 生產(chǎn)與銷售計劃問題5.2 有瓶頸設(shè)備的多級生產(chǎn)計劃問題5.3 下料問題5.4 面試順序與消防車調(diào)度問題5.5 飛機(jī)定位和飛行計劃問題5.1 生產(chǎn)與銷售計劃問題5.1.1問題實例例5.1某公司用兩種原油（A和B）混合加工成兩種汽油（甲和乙）。甲、乙兩種汽油含原油A的最低比例分別為50%和60%，每噸售價分別為4800元和5600元。該公司現(xiàn)有原油A和B的庫存量分別為500噸和1000噸，還可以從市場上買到不超過1500噸的原油A。原油A的市場價為：購買量不超過500噸時的單價為10000元/噸；購買量超過50

2、0噸但不超過1000噸時，超過500噸的部分8000元/噸；購買量超過1000噸時，超過1000噸的部分6000元/噸。該公司應(yīng)如何安排原油的采購和加工。5.1.2建立模型問題分析 安排原油采購、加工的目標(biāo)是利潤最大，題目中給出的是兩種汽油的售價和原油A的采購價，利潤為銷售汽油的收入與購買原油A的支出之差。這里的難點(diǎn)在于原油A的采購價與購買量的關(guān)系比較復(fù)雜，是分段函數(shù)關(guān)系，能否及如何用線性規(guī)劃、整數(shù)規(guī)劃模型加以處理是關(guān)鍵所在。模型建立設(shè)原油A的購買量為x（噸），根據(jù)題目所給數(shù)據(jù)，采購的支出c(x)可表為如下的分段線性函數(shù)（以下價格以千元/噸為單位）：(1)設(shè)原油A用于生產(chǎn)甲、乙兩種汽油的數(shù)量分

3、別為x11和x12（噸），原油B用于生產(chǎn)甲、乙兩種汽油的數(shù)量分別為x21和x22（噸），則總的收入為4.8(x11+x21)+5.6(x12+x22)（千元）。于是本例的目標(biāo)函數(shù)（利潤）為(2)約束條件包括加工兩種汽油用的原油A、原油B庫存量的限制，和原油A購買量的限制，以及兩種汽油含原油A的比例限制，它們表示為（3）（4）（5）（6）（7）（8）由于（1）式中的c(x)不是線性函數(shù)，（1）（8）給出的是一個非線性規(guī)劃。而且，對于這樣用分段函數(shù)定義的c(x)，一般的非線性規(guī)劃軟件也難以輸入和求解。能不能想辦法將該模型化簡，從而用現(xiàn)成的軟件求解呢？5.1.3 求解模型 3種解法第1種解法 將原油

4、A的采購量x分解為三個量，即用x1，x2，x3分別表示以價格10、8、6千元/噸采購的原油A的噸數(shù)，總支出為c(x) = 10 x1+8x2+6x3，且(9)這時目標(biāo)函數(shù)（2）變?yōu)榫€性函數(shù)：(10)應(yīng)該注意到，只有當(dāng)以10千元/噸的價格購買x1=500（噸）時，才能以8千元/噸的價格購買x2（0），這個條件可以表示為(11)同理，只有當(dāng)以8千元/噸的價格購買x2=500（噸）時，才能以6千元/噸的價格購買x3（0），于是(12)此外，x1，x2，x3的取值范圍是(13)由于有非線性約束(11),(12)，(3)(13)構(gòu)成非線性規(guī)劃模型。LINGO程序：Model:Max= 4.8*x11 +

5、 4.8*x21 + 5.6*x12 + 5.6*x22 - 10*x1 - 8*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 將文件存儲并命名為exam0501a.lg4，執(zhí)行菜單命令“LINGO|Solve”，運(yùn)行該程序得到： Local optimal solution found. Objective value: 4800.

6、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)解: 用庫存的500噸原油A、500噸原油B生產(chǎn)1000噸汽油甲，不購買新的原油A，利潤為4800（千元） 但是此時LINGO得到的結(jié)果

7、只是一個局部最優(yōu)解可以用菜單命令“LINGO|Options”在“Global Solver”選項卡上啟動全局優(yōu)化（Use Global Solver）選項，然后重新執(zhí)行菜單命令“LINGO|Solve” , 得到： Global optimal solution found. Objective value: 5000.002 Extended solver steps: 3 Total solver iterations: 187Variable Value Reduced CostX11 0.000000 0.000000X21 0.000000 0.000000X12 1500.000

8、 0.000000X22 1000.000 0.000000X1 500.0000 0.000000X2 499.9990 0.000000X3 0.9536707E-03 0.000000X 1000.000 0.000000此時LINGO得到的結(jié)果是一個全局最優(yōu)解（Global optimal solution）：購買1000噸原油A，與庫存的500噸原油A和1000噸原油B一起，共生產(chǎn)2500噸汽油乙，利潤為5000（千元），高于剛剛得到的局部最優(yōu)解對應(yīng)的利潤4800（千元）。第2種解法: 引入0-1變量將（11）和（12）轉(zhuǎn)化為線性約束令y1=1，y2=1，y3=1分別表示以10千元/

9、噸、8千元/噸、6千元/噸的價格采購原油A，則約束（11）和（12）可以替換為(14)(15)(16) y1，y2，y3 =0或1(17)（3）（10），（13）（17）構(gòu)成混合整數(shù)線性規(guī)劃模型，將它輸入LINDO軟件：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ùn)行該程序得到：OBJECTIVE FUNCTION VALUE

10、 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 X 1000.000000 0.000000這個結(jié)果與前面

11、非線性規(guī)劃模型用全局優(yōu)化得到的結(jié)果相同。第3種解法 直接處理分段線性函數(shù)c(x)。（1）式表示的函數(shù)c(x)如圖5-1。c(x)x1200090005000050010001500圖5-1 分段線性函數(shù)c(x)圖形記x軸上的分點(diǎn)為b1=0, b2=500, b3=1000, b4=1500。當(dāng)x在第1個小區(qū)間 b1, b2時，記x= z1b1+z2b2，z1+z2=1，z1, z20, 因為c(x)在b1, b2是線性的，所以c(x)= z1c(b1)+z2c(b2)。同樣，當(dāng)x在第2個小區(qū)間 b2, b3時，x= z2b2+z3b3，z2+z3=1，z2, z30, c(x)= z2c(b2

12、)+z3c(b3)。當(dāng)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)，當(dāng)x在第k個小區(qū)間時，yk=1，否則，yk=0。這樣, z1, z2, z3, z4, y1, y2, y3應(yīng)滿足(18)(19)(20)此時x和c(x)可以統(tǒng)一地表示為（2）（10），（18）（22）也構(gòu)成一個混合整數(shù)線性規(guī)劃模型，可以用LINDO求解。不過，我們還是將它輸入LINGO軟件，因為其擴(kuò)展性更好（即當(dāng)分段函數(shù)的分段數(shù)更多時，只需要對下面程序作很小的改動）。輸入的

13、LINGO模型如下：(22)輸入的LINGO模型如下：Model:SETS:Points/1.4/: b, c, y, z;! 端點(diǎn)數(shù)為4，即分段數(shù)為3;ENDSETSDATA:b=0 500 1000 1500;c=0 5000 9000 12000;y=,0;! 增加的虛擬變量y(4)=0;ENDDATAMax= 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#e

14、q#1: z(i) = y(i);for(Points(i)|i#ne#1: z(i) 0時取值1, 否則取值0.在上述數(shù)學(xué)符號中，只有為決策變量; 其余均為已知的計劃參數(shù)。目標(biāo)函數(shù) 這個問題的目標(biāo)是使生產(chǎn)準(zhǔn)備費(fèi)用和庫存費(fèi)用的總和最小。因此，目標(biāo)函數(shù)應(yīng)該是每個項目在每個時段上的生產(chǎn)準(zhǔn)備費(fèi)用和庫存費(fèi)用的總和，即(28)約束條件這個問題中的約束有這么幾類：每個項目的物流應(yīng)該守恒、資源能力限制應(yīng)該滿足、每時段生產(chǎn)某項目前必須經(jīng)過生產(chǎn)準(zhǔn)備和非負(fù)約束 （對Yi,j是0-1約束）。(29)資源能力限制比較容易理解，即(30)所謂物流守恒（假設(shè)Ii,0 =0） (31)每時段生產(chǎn)某項目前必須經(jīng)過生產(chǎn)準(zhǔn)備，也

15、就是說當(dāng)Xit=0時Yit=0；Xit0時Yit=1。這本來是一個非線性約束，但是通過引入?yún)?shù)M（很大的正數(shù)，表示每個項目每個時段的最大產(chǎn)量）可以化成線性約束，即： 總結(jié): 這個問題的優(yōu)化模型就是在約束（29）（30）（31）下使目標(biāo)函數(shù)（28）達(dá)到最小。 5.2.3 求解模型本例生產(chǎn)項目總數(shù)N=7(A、B、C、D、E、F、G) ，計劃期長度T=6（周），瓶頸資源種類數(shù)K=1。只有A有外部需求，所以di,t中只有d1,t可以取非零需求，即表5-1中的第2行的數(shù)據(jù)，其他全部為零。 參數(shù)si,t 、 hi,t只與項目i有關(guān)，而不隨時段t變化，所以可以略去下標(biāo)t，其數(shù)值就是表5-1中的最后兩行數(shù)據(jù)。

16、由于只有一種資源，參數(shù)Ck,t可以略去下標(biāo)k，其數(shù)值就是表5-1中的第3行的數(shù)據(jù)；而ak,I,t只與項目i有關(guān)，而不隨時段t變化，所以可以同時略去下標(biāo)k和t，即a2=5，a3=8（其他ai為0）。從圖6-2中容易得到項目i的直接后繼項目集合S(i)和消耗系數(shù)。準(zhǔn)備以下的數(shù)據(jù)文件（文本文件exam0502.LDT，可以看到其中也可以含有注釋語句）：! 項目集合;ABCDEFG! 計劃期集合;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! 能力;10000050005

17、00010001000! 生產(chǎn)準(zhǔn)備費(fèi);4005001000300200400100! 庫存費(fèi);120.61.00.040.030.040.04! 對能力的消耗系數(shù)；0580000! 項目間的消耗系數(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 0 0 00 11 0 0 0 0 00 0 13 0 0 0 00 0 15 0 0 0 0! 數(shù)據(jù)結(jié)束;對本例，A的外部總需求為240，所以任何項目的產(chǎn)量不會超過24071525000（從圖6-2可以知道，這里715已經(jīng)是每件產(chǎn)品A對任意一個項目的最大的消耗系數(shù)了）

18、，所以取M=25000就已經(jīng)足夠了。本例中的具體模型可以如下輸入LINGO軟件：MODEL:TITLE 瓶頸設(shè)備的多級生產(chǎn)計劃;! 從文本文件exam0502.LDT中讀取數(shù)據(jù);SETS:! PART = 項目集合, Setup = 生產(chǎn)準(zhǔn)備費(fèi)，Hold = 單件庫存成本， A = 對瓶頸資源的消耗系數(shù);PART/ FILE( exam0502.LDT)/ : Setup, Hold, A;! TIME = 計劃期集合，Capacity = 瓶頸設(shè)備的能力;TIME / FILE( exam0502.LDT)/ : Capacity;! USES = 項目結(jié)構(gòu)關(guān)系，Req = 項目之間的消耗系

19、數(shù);USES( PART, PART) : Req;! PXT = 項目與時間的派生集合，Demand = 外部需求, X = 產(chǎn)量（批量）, Y = 0/1變量，INV = 庫存;PXT( PART, TIME): Demand, X, Y, Inv;ENDSETS! 目標(biāo)函數(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

20、): Req(i,j)*X(j,t) );FOR( PXT(i, t) | t #eq# 1 : Ba0 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) ); ! 其他約束;M = 25000;FOR( PXT(i,t): X(i,t) = 50 x2 + 2x4 + x5 + 3x6 = 20 x3 + x5 + 2x7 = 15endgin 7求解可以得到最優(yōu)解如下： OBJE

21、CTIVE FUNCTION VALUE 1) 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 即按照模式2切割12根原料鋼管，按照模式5切割15根原料鋼管，共27根，總余料量為27米。顯然，在總余料量最小的目標(biāo)下，最優(yōu)解將是使用余料盡可能小的切割模式（模式2和5的余料為1米

22、），這會導(dǎo)致切割原料鋼管的總根數(shù)較多。2. 將（33）（36）構(gòu)成的整數(shù)線性規(guī)劃模型（加上整數(shù)約束）輸入LINDO：Title 鋼管下料 - 最小化鋼管根數(shù)Min x1 + x2 + x3 + x4 + x5 + x6 + x7 s.t. 4x1 + 3x2 + 2x3 + x4 + x5 = 50 x2 + 2x4 + x5 + 3x6 = 20 x3 + x5 + 2x7 = 15endgin 7求解，可以得到最優(yōu)解如下：OBJECTIVE FUNCTION VALUE 1) 25.00000 VARIABLE VALUE REDUCED COST X1 0.000000 1.000000

23、 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.000000即按照模式2切割15根原料鋼管，按模式5切割5根，按模式7切割5根，共27根，可算出總余料量為35米。與上面得到的結(jié)果相比，總余料量增加了8米，但是所用的原料鋼管的總根數(shù)減少了2根。在余料沒有什么用途的情況下，通常選擇總根數(shù)最少為目標(biāo)。問題2）的求解問題分析 按照解問題1）的思路，可以通過枚舉法首先確定哪些切割模式是可行的。但由于需求的鋼管規(guī)格

24、增加到4種，所以枚舉法的工作量較大。下面介紹的整數(shù)非線性規(guī)劃模型，可以同時確定切割模式和切割計劃，是帶有普遍性的方法。同1）類似，一個合理的切割模式的余料不應(yīng)該大于或等于客戶需要的鋼管的最小尺寸（本題中為4米），切割計劃中只使用合理的切割模式，而由于本題中參數(shù)都是整數(shù)，所以合理的切割模式的余量不能大于3米。此外，這里我們僅選擇總根數(shù)最少為目標(biāo)進(jìn)行求解。 模型建立決策變量 由于不同切割模式不能超過3種，可以用xi 表示按照第i種模式（i=1, 2, 3）切割的原料鋼管的根數(shù)，顯然它們應(yīng)當(dāng)是非負(fù)整數(shù)。設(shè)所使用的第i種切割模式下每根原料鋼管生產(chǎn)4米長、5米長、6米長和8米長的鋼管數(shù)量分別為r1i,

25、r2i, r3i, r4i（非負(fù)整數(shù)）。 決策目標(biāo) 以切割原料鋼管的總根數(shù)最少為目標(biāo)，即目標(biāo)為（37）約束條件 為滿足客戶的需求，應(yīng)有(38)(39)(40)(41)每一種切割模式必須可行、合理，所以每根原料鋼管的成品量不能超過19米，也不能少于16米（余量不能大于3米），于是(42)(43)(44)模型求解（37）（44）構(gòu)成這個問題的優(yōu)化模型。由于在（38）（41）式中出現(xiàn)了決策變量的乘積，所以這是一個整數(shù)非線性規(guī)劃模型，雖然用LINGO軟件可以直接求解，但我們發(fā)現(xiàn)在較低版本的LINGO軟件中需要運(yùn)行很長時間也難以得到最優(yōu)解。為了減少運(yùn)行時間，可以增加一些顯然的約束條件，從而縮小可行解的搜

26、索范圍。例如，由于3種切割模式的排列順序是無關(guān)緊要的，所以不妨增加以下約束：（45）又例如，我們注意到所需原料鋼管的總根數(shù)有著明顯的上界和下界。首先，無論如何，原料鋼管的總根數(shù)不可能少于 （根）其次，考慮一種非常特殊的生產(chǎn)計劃：第一種切割模式下只生產(chǎn)4米鋼管，一根原料鋼管切割成4根4米鋼管，為滿足50根4米鋼管的需求，需要13根原料鋼管；第二種切割模式下只生產(chǎn)5米、6米鋼管，一根原料鋼管切割成1根5米鋼管和2根6米鋼管，為滿足10根5米和20根6米鋼管的需求，需要10根原料鋼管；第三種切割模式下只生產(chǎn)8米鋼管，一根原料鋼管切割成2根8米鋼管，為滿足15根8米鋼管的需求，需要8根原料鋼管。于是滿

27、足要求的這種生產(chǎn)計劃共需13+10+8=31根原料鋼管，這就得到了最優(yōu)解的一個上界。所以可增加以下約束：(46)將（37）（46）構(gòu)成的模型輸入LINGO如下：將（37）（46）構(gòu)成的模型輸入LINGO如下：model:Title 鋼管下料 - 最小化鋼管根數(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*

28、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 = 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 經(jīng)過LINGO求解，得到輸出如下： Local optimal solut

29、ion found. Objective value: 28.00000 Extended solver steps: 72 Total solver iterations: 3404 Model Title: 鋼管下料-最小化鋼管根數(shù)的LINGO模型 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.000000R2

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

31、 如果充分利用LINGO建模語言的能力，使用集合和屬性的概念，可以編寫以下LINGO程序，這種方法更具有一般的通用性，并有利于輸入更大規(guī)模的下料問題的優(yōu)化模型：model:Title 鋼管下料 - 最小化鋼管根數(shù)的LINGO模型;SETS: NEEDS/1.4/:LENGTH,NUM; ! 定義基本集合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 1

32、5;CAPACITY=19;ENDDATAmin=SUM(CUTS(I): X(I) );!目標(biāo)函數(shù);FOR(NEEDS(I): SUM(CUTS(J): X(J)*R(I,J) ) NUM(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(PATTERN

33、S(I,J): GIN(R(I,J) );end求解這個模型，得到的結(jié)果與前面的結(jié)果完全相同。5.3.2易拉罐下料問題例5.4 某公司采用一套沖壓設(shè)備生產(chǎn)一種罐裝飲料的易拉罐，這種易拉罐是用鍍錫板沖壓制成的（參見圖5-3）。易拉罐為圓柱形，包括罐身、上蓋和下底，罐身高10厘米，上蓋和下底的直徑均為5厘米。該公司使用兩種不同規(guī)格的鍍錫板原料，規(guī)格1的鍍錫板為正方形，邊長24厘米；規(guī)格2的鍍錫板為長方形，長、寬分別為32和28厘米。由于生產(chǎn)設(shè)備和生產(chǎn)工藝的限制，對于規(guī)格1的鍍鍍錫板原料，只可以按照圖2中的模式1、2或3進(jìn)行沖壓；對于規(guī)格2的鍍錫板原料只能按照模式4進(jìn)行沖壓。使用模式1、2、3、4進(jìn)

34、行每次沖壓所需要的時間分別為1.5、2、1、3（秒）。模式1模式2模式3模式4上蓋下底罐身圖5-3 易拉罐下料模式該工廠每周工作40小時，每周可供使用的規(guī)格1、2的鍍錫板原料分別為5萬張和2萬張。目前每只易拉罐的利潤為0.10元，原料余料損失為0.001元 / 厘米2（如果周末有罐身、上蓋或下底不能配套組裝成易拉罐出售，也看作是原料余料損失）。工廠應(yīng)如何安排每周的生產(chǎn)？已知上蓋和下底的直徑d=5厘米，可得其面積為 19.6厘米2表5-4 4種沖壓模式的特征罐身個數(shù)底、蓋個數(shù)余料損失（厘米2）沖壓時間（秒）模式1110222.61.5模式224183.32模式3016261.81模式445169

35、.53問題的目標(biāo)顯然應(yīng)是易拉罐的利潤扣除原料余料損失后的凈利潤最大，約束條件除每周工作時間和原料數(shù)量外，還要考慮罐身和底、蓋的配套組裝。模型建立決策變量 用xi 表示按照第i種模式的沖壓次數(shù)（i=1, 2, 3, 4），y1表示一周生產(chǎn)的易拉罐個數(shù)。為計算不能配套組裝的罐身和底、蓋造成的原料損失，用y2表示不配套的罐身個數(shù)，y3表示不配套的底、蓋個數(shù)。雖然實際上xi和y1，y2，y3應(yīng)該是整數(shù)。但是由于生產(chǎn)量相當(dāng)大，可以把它們看成是實數(shù)，從而用線性規(guī)劃模型處理。決策目標(biāo) 假設(shè)每周生產(chǎn)的易拉罐能夠全部售出，公司每周的銷售利潤是0.1y1。原料余料損失包括兩部分：4種沖壓模式下的余料損失，和不配套

36、的罐身和底、蓋造成的原料損失。按照前面的計算及表2的結(jié)果，總損失為0.001(222.6x1 + 183.3x2 + 261.8x3 + 169.5x4 + 157.1y2 +19.6y3)。 于是，決策目標(biāo)為(47)約束條件 時間約束：每周工作時間不超過40小時=144000（秒），由表2最后一列得(48)原料約束：每周可供使用的規(guī)格1、2的鍍錫板原料分別為50000張和20000張，即(49)(50) 配套約束： 由表2一周生產(chǎn)的罐身個數(shù)為x1 + 2x2 + 4x4, 一周生產(chǎn)的底、蓋個數(shù)為10 x1 + 4x2 + 16x3+ 5x4，因為應(yīng)盡可能將它們配套組裝成易拉罐銷售。所以y1滿

37、足 (51)這時不配套的罐身個數(shù)y2，和不配套的底、蓋個數(shù)y3應(yīng)為 (52) (53)（47）（53）就是我們得到的模型，其中（51）是一個非線性關(guān)系，不易直接處理， 但是它可以等價為以下兩個線性不等式： (54) (55)模型求解將模型（47）（50）和（52）（55）直接輸入LINDO（輸入LINGO也可以），求解時LINDO發(fā)出警告信息（程序和警告信息參見圖5-4）。 圖中錯誤編號“66”的含義（參見第4章的錯誤代碼表）是：模型中數(shù)據(jù)不平衡，所以發(fā)出警告信息（注意，只是警告信息，所以仍然可以繼續(xù)求解）。求解結(jié)果是： OBJECTIVE FUNCTION VALUE 1) 4298.337

38、 VARIABLE VALUE REDUCED COST Y1 160250.000000 0.000000 X1 0.000000 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圖5-4 模型中數(shù)據(jù)不平衡的警告信息這個結(jié)果可靠嗎？由于LINDO警告模型中數(shù)據(jù)之間的數(shù)量級差別太大，所以我們可以進(jìn)行預(yù)處理，縮小數(shù)據(jù)之間的差別。實際上，約束（48）（50）中右端項的數(shù)值過大（與左端的系數(shù)相比較），L

39、INDO在計算中容易產(chǎn)生比較大的誤差，所以出現(xiàn)此警告信息。為了解決這一問題，可以將所有決策變量擴(kuò)大10000倍（相當(dāng)于xi以萬次為單位，yi以萬件為單位）。此時，目標(biāo)（47）可以保持不變（記住得到的結(jié)果單位為萬元就可以了），而約束（48）（50）改為 (56)(57) (58)將模型（47）和（52）（58）輸入LINDO:! 易拉罐下料：均衡數(shù)據(jù)Max 0.100y1 - 0.2226x1 - 0.1833x2 - 0.2618x3 - 0.1695 x4 - 0.1571y2 - 0.0196y3 s.t.1.5x1 + 2.0 x2 + 1.0 x3 +3.0 x4 = 14.4 x1

40、+ x2 + x3 = 5 x4 =010 x1 + 4x2 + 16x3+ 5x4 - 2y1 =0 x1 + 2x2 + 4x4 - y1 - y2 =010 x1 + 4x2 + 16x3+ 5x4 - 2y1 - y3=0end求解得到： OBJECTIVE FUNCTION VALUE 1) 0.4298337 VARIABLE VALUE REDUCED COST Y1 16.025000 0.000000 X1 0.000000 0.000050 X2 4.012500 0.000000 X3 0.375000 0.000000 X4 2.000000 0.000000 Y2 0

41、.000000 0.223331 Y3 0.000000 0.036484即模式1不使用，模式2使用40125次，模式3使用3750次，模式4使用20000次，可生產(chǎn)易拉罐160250個，罐身和底、蓋均無剩余，凈利潤為4298元。5.4 面試順序與消防車調(diào)度問題面試順序問題 例5.5 有4名同學(xué)到一家公司參加三個階段的面試：公司要求每個同學(xué)都必須首先找公司秘書初試，然后到部門主管處復(fù)試，最后到經(jīng)理處參加面試，并且不允許插隊（即在任何一個階段4名同學(xué)的順序是一樣的）。由于4名同學(xué)的專業(yè)背景不同，所以每人在三個階段的面試時間也不同，如表5-5所示（單位：分鐘）。這4名同學(xué)約定他們?nèi)棵嬖囃暌院笠黄?/p>

42、離開公司。假定現(xiàn)在時間是早晨8：00，請問他們最早何時能離開公司？ 表5-5 面試時間要求秘書初試主管復(fù)試經(jīng)理面試同學(xué)甲131520同學(xué)乙102018同學(xué)丙201010同學(xué)丁81015建立模型 實際上，這個問題就是要安排4名同學(xué)的面試順序，使完成全部面試所花費(fèi)的時間最少。 記tij為第i名同學(xué)參加第j階段面試需要的時間(已知)，令xij表示第i名同學(xué)參加第j階段面試的開始時刻(不妨記早上8：00面試開始為0時刻)(i=1, 2, 3, 4；j=1, 2, 3)，T為完成全部面試所花費(fèi)的最少時間。 優(yōu)化目標(biāo)為 a. 時間先后次序約束(每人只有參加完前一個階段的面試后才能進(jìn)入下一個階段)： xij

43、+ tij xi，j+1 (i=1, 2, 3, 4；j=1, 2) b.每個階段j同一時間只能面試1名同學(xué)：用0-1變量yik表示第k名同學(xué)是否排在第i名同學(xué)前面(1表示是，0表示否)，則 xij+ tijxkjTyik (i, k=1, 2, 3, 4; j=1, 2, 3; ik) xkj+ tkjxijT(1yik) (i, k=1, 2, 3, 4; j=1, 2, 3; ik) 約束條件： 可以將非線性的優(yōu)化目標(biāo)改寫為如下線性優(yōu)化目標(biāo)： Min T s.t. T x13+ t13 T x23+ t23 T x33+ t33 T x43+ t43 Min T s.t. xij+ ti

44、j xi, j+1 (i=1, 2, 3, 4；j=1, 2) xij+ tijxkjTyik (i, k=1, 2, 3, 4; j=1, 2, 3; ik) xkj+ tkjxijT(1yik) (i, k=1, 2, 3, 4; j=1, 2, 3; i= x13+ t13;T = x23+ t23;T = x33+ t33;T = x43+ t43;x11+ t11 = x12;x12+ t12 = x13;x21+ t21 = x22;x22+ t22 = x23;x31+ t31 = x32;x32+ t32 = x33;x41+ t41 = x42;x42+ t42 = x43;

45、求解模型這個模型可以如下輸入LINGO： x11+ t11 - x21= T*y12;x21+ t21 - x11= T*(1-y12);x12+ t12 - x22= T*y12;x22+ t22 - x12= T*(1-y12);x13+ t13 - x23= T*y12;x23+ t23 - x13= T*(1-y12);x11+ t11 - x31= T*y13;x31+ t31 - x11= T*(1-y13); x12+ t12 - x32= T*y12;x32+ t32 - x12= T*(1-y13);x13+ t13 - x33= T*y13;x33+ t33 - x13=

46、T*(1-y13);x11+ t11 - x41= T*y14;x41+ t41 - x11= T*(1-y14);x12+ t12 - x42= T*y14;x42+ t42 - x12= T*(1-y14);x13+ t13 - x43= T*y14;x43+ t43 - x13= T*(1-y14);x21+ t21 - x31= T*y23;x31+ t31 - x21= T*(1-y23);x22+ t22 - x32= T*y23;x32+ t32 - x32= T*(1-y23);x23+ t23 - x33= T*y23;x33+ t33 - x23= T*(1-y23);x2

47、1+ t21 - x41= T*y24;x41+ t41 - x21= T*(1-y24);x22+ t22 - x42= T*y24;x42+ t42 - x22= T*(1-y24);x23+ t23 - x43= T*y24;x43+ t43 - x23= T*(1-y24);x31+ t31 - x41= T*y34; x41+ t41 - x31= T*(1-y34);x32+ t32 - x42= T*y34;x42+ t42 - x32= T*(1-y34);x33+ t33 - x43= T*y34;x43+ t43 - x33= max(PXS(i,j)|j#EQ#size(

48、stage): x(i,j)+t(i,j);! 只有參加完前一個階段的面試后才能進(jìn)入下一個階段;for(PXS(i,j)|j#LT#size(stage):ORDERx(i,j)+t(i,j)x(i,j+1);! 同一時間只能面試1名同學(xué);for(Stage(j): for(PXP(i,k):SORT1x(i, j)+t(i, j)-x(k,j)MAXT*Y(i,k) ); for(PXP(i,k):SORT2x(k,j)+t(k,j)-x(i, j)MAXT*(1-Y(i,k) ););for(PXP: bin(y);End 求解這個模型，得到的結(jié)果與前面的完全相同。 可以很清楚地看到，使用

49、LINGO建模語言的集合和屬性概念，得到的模型具有非常好的結(jié)構(gòu)性，反映了相應(yīng)的優(yōu)化模型的本質(zhì)，目標(biāo)、決策變量、約束一清二楚，容易閱讀和理解，而且還可以讓數(shù)據(jù)與程序完全分離，這種優(yōu)越性是LINDO軟件無法與之相比的。 消防車調(diào)度問題 例5.6 某市消防中心同時接到了三處火警報告。根據(jù)當(dāng)前的火勢，三處火警地點(diǎn)分別需要2輛、2輛和3輛消防車前往滅火。三處火警地點(diǎn)的損失將依賴于消防車到達(dá)的及時程度：記tij為第j輛消防車到達(dá)火警地點(diǎn)i的時間(分鐘)，則三處火警地點(diǎn)的損失分別為: 6t11+4t12，7t21+3t22，9t31+8t32+5t33。 目前可供消防中心調(diào)度的消防車正好有7輛，分別屬于三個

50、消防站(可用消防車數(shù)量分別為3輛、2輛、2輛)。消防車從三個消防站到三個火警地點(diǎn)所需要的時間如表5-6所示。該公司應(yīng)如何調(diào)度消防車，才能使總損失最?。?如果三處火警地點(diǎn)的損失分別為:4t11+6t12，3t21+7t22，5t31+8t32+9t33，調(diào)度方案是否需要改變？消防站到三個火警地點(diǎn)所需要的時間時間(分鐘)火警地點(diǎn)1火警地點(diǎn)2火警地點(diǎn)3消防站1679消防站25811消防站36910 問題分析 本題考慮的是為每個火警地點(diǎn)分配消防車的問題，初步看來與線性規(guī)劃中經(jīng)典的運(yùn)輸問題有些類似。本題的問題可以看成是指派問題和運(yùn)輸問題的一種變形，我們下面首先把它變成一個運(yùn)輸問題建模求解。 決策變量 為

51、了用運(yùn)輸問題建模求解，很自然地把3個消防站看成供應(yīng)點(diǎn)。如果直接把3個火警地點(diǎn)看成需求點(diǎn)，我們卻不能很方便地描述消防車到達(dá)的先后次序，因此難以確定損失的大小。下面我們把7輛車的需求分別看成7個需求點(diǎn)(分別對應(yīng)于到達(dá)時間t11, t12, t21, t22, t31, t32, t33)。用xi j表示消防站i是否向第j個需求點(diǎn)派車(1表示派車，0表示不派車)，則共有21個0-1變量。 決策目標(biāo) 題目中給出的損失函數(shù)都是消防車到達(dá)時間的線性函數(shù)，所以由所給數(shù)據(jù)進(jìn)行簡單的計算可知，如果消防站1向第6個需求點(diǎn)派車(即消防站1向火警地點(diǎn)3派車但該消防車是到達(dá)火警地點(diǎn)3的第二輛車)，則由此引起的損失為8*

52、9=72。同理計算，可以得到損失矩陣(元素分別記為ci j)。 ci j火警地點(diǎn)1火警地點(diǎn)2火警地點(diǎn)3j=1j=2j=3j=4j=5j=6j=7消防站i=136244921817245消防站i=230205624998855消防站i=336246327908050于是，使總損失最小的決策目標(biāo)為 約束條件 約束條件有兩類：一類是消防站擁有的消防車的數(shù)量限制，另一類是各需求點(diǎn)對消防車的需求量限制。 消防站擁有的消防車的數(shù)量限制可以表示為 x11+x12+x13+x14+x15+x16+x17=3 x21+x22+x23+x24+x25+x26+x27 =2 x31+x32+x33+x34+x35+

53、x36+x37=2 各需求點(diǎn)對消防車的需求量限制可以表示為 模型求解 將如上構(gòu)成的線性規(guī)劃模型輸入LINDO： ! 消防車問題Min 36x11+24x12+49x13+21x14+81x15+72x16+45x17 +30 x21+20 x22+56x23+24x24+99x25+88x26+55x27 +36x31+24x32+63x33+27x34+90 x35+80 x36+50 x37 SUBJECT TO x11+x12+x13+x14+x15+x16+x17 = 3 x21+x22+x23+x24+x25+x26+x27 = 2 x31+x32+x33+x34+x35+x36+x

54、37 = 2 x11+x21+x31 =1 x12+x22+x32 =1 x13+x23+x33 = 1 x14+x24+x34 =1 x15+x25+x35 =1 x16+x26+x36 = 1 x17+x27+x37 = 1 END 求解得到如下結(jié)果： OBJECTIVE FUNCTION VALUE 1) 329.0000VARIABLE VALUE REDUCED COST X11 0.000000 10.000000 X12 0.000000 8.000000 X13 1.000000 0.000000 X14 0.000000 2.000000 X15 1.000000 0.000

55、000 X16 1.000000 0.000000 X17 0.000000 3.000000 X21 1.000000 0.000000 X22 1.000000 0.000000 X23 0.000000 3.000000 X24 0.000000 1.000000 X25 0.000000 14.000000 X26 0.000000 12.000000 X27 0.000000 9.000000 VARIABLE VALUE REDUCED COST X31 0.000000 2.000000 X32 0.000000 0.000000 X33 0.000000 6.000000 X3

56、4 1.000000 0.000000 X35 0.000000 1.000000 X36 0.000000 0.000000 X37 1.000000 0.000000 也就是說，消防站1應(yīng)向火警地點(diǎn)2派1輛車，向火警地點(diǎn)3派2輛車；消防站2應(yīng)向火警地點(diǎn)1派2輛車；消防站3應(yīng)向火警地點(diǎn)2、3各派1輛車。最小總損失為329。 討論 1) 這個問題本質(zhì)上仍然和經(jīng)典的運(yùn)輸問題類似，可以把每輛車到達(dá)火場看作需求點(diǎn)，消防站可作供應(yīng)點(diǎn)。在上面模型中，我們雖然假設(shè)xij為0-1變量，但求解時是采用線性規(guī)劃求解的，也就是說沒有加上xij為0-1變量或整數(shù)變量的限制條件，但求解得到的結(jié)果中xij正好是0-1變

57、量。這一結(jié)果不是偶然的，而是運(yùn)輸問題特有的一種性質(zhì)。 2) 在上面模型中，我們沒有考慮消防車到達(dá)各火警地點(diǎn)的先后次序約束，但得到的結(jié)果正好滿足所有的先后次序約束。這一結(jié)果卻并不總是必然的，而只是巧合。 如對例題后半部分的情形，結(jié)果就不是這樣了。顯然，此時只需要修改損失矩陣(元素仍然分別記為cij)ci j火警地點(diǎn)1火警地點(diǎn)2火警地點(diǎn)3j=1j=2j=3j=4j=5j=6j=7消防站i=124362149457281消防站i=220302456558899消防站i=324362763508090 此時將重新構(gòu)成的線性規(guī)劃模型輸入LINDO求解, 可以得到新的最優(yōu)解: x14=x16=x17=x2

58、1=x22=x33=x35=1其他變量為0(最小總損失仍為329)。實際上, 損失矩陣中只是1、2列交換了位置，3、4列交換了位置，5、7列交換了位置，因此不用重新求解就可以直接看出以上新的最優(yōu)解。 但是，以上新的最優(yōu)解卻是不符合實際情況的。例如，x14=x33=1表明火警地點(diǎn)2的第一輛消防車來自消防站3，第二輛消防車來自消防站1，但這是不合理的，因為火警地點(diǎn)2與消防站3有9分鐘的距離，大于與消防站1的7分鐘的距離。分配給火警地點(diǎn)3的消防車也有類似的不合理問題。 為了解決這一問題，我們必須考慮消防車到達(dá)各火警地點(diǎn)的先后次序約束，也就是說必須在簡單的運(yùn)輸問題模型中增加一些新的約束，以保證以上的不

59、合理問題不再出現(xiàn)。 首先考慮火警地點(diǎn)2。由于消防站1的消防車到達(dá)所需時間(7分鐘)小于消防站2的消防車到達(dá)所需時間(8分鐘)，并都小于消防站3的消防車到達(dá)所需時間(9分鐘)，因此火警地點(diǎn)2的第2輛消防車如果來自消防站1，則火警地點(diǎn)2的第1輛消防車也一定來自消防站1；火警地點(diǎn)2的第2輛消防車如果來自消防站2，則火警地點(diǎn)2的第1輛消防車一定來自消防站1或2。因此，必須增加以下約束：x14x13x24x13 +x23x16 x15x17 x16x36 x15+x352x37 x15+x16+x35+x36 同理，對火警地點(diǎn)1，必須增加以下約束：x22x21對火警地點(diǎn)3，必須增加以下約束： 此時將重新

60、構(gòu)成的線性規(guī)劃模型輸入LINDO軟件如下： ! 消防車調(diào)度Min 36x12+24x11+49x14+21x13+81x17+72x16+45x15 +30 x22+20 x21+56x24+24x23+99x27+88x26+55x25 +36x32+24x31+63x34+27x33+90 x37+80 x36+50 x35 SUBJECT TO x11+x12+x13+x14+x15+x16+x17 = 3 x21+x22+x23+x24+x25+x26+x27 = 2 x31+x32+x33+x34+x35+x36+x37 = 2 x11+x21+x31 = 1 x12+x22+x32