根據“全部用完,沒有剩余”的原則,將所有的方案列舉如下:
註:設各個方案中使用長度為8或12的材料分別為Xi(i=1,2,3…13),詳細方案見表:
根數長度 1 2 3 4 5 6 7 8 9 10 11 12 13
6.2 0 0 1 0 0 0 0 1 0 0 0 1 0
3.6 0 0 0 0 0 0 2 1 0 2 0 0 1
2.8 0 0 1 2 1 1 0 0 0 0 2 0 3
1.85 4 0 0 1 2 0 2 0 5 0 0 0 0
0.75 1 16 4 0 2 4 0 0 0 2 1 7 0
0.55 7 0 0 1 0 4 2 4 5 6 3 1 0
使用的原材料 12 12 12 8 8 8 12 12 12 12 8 12 12
損失 0 0 0 0 0 0 0 0 0 0 0 0 0
2、由上表可列出以下數學模型:
MINZ=0X1+0X2+0X3+0X4+0X5+0X6+0X7+0X8+0X9+0X10+0X11
+0X12+0X13
X3+X8+X12>=90
X2+2X7+X8+2X10>=120
3X2+X3+2X4+X5+X6+2X11>=136
5X1+X4+2X5+2X7+4X9>=310
4X3+2X5+4X6+X9+2X10+X11+7X12+16X13>=215
5X1+X4+4X6+2X7+4X8+7X9+6X10+3X11+X12>=320
X1、X2……X13為非負整數
3、編寫LINDO代碼如下
MIN0X1+0X2+0X3+0X4+0X5+0X6+0X7+0X8+0X9+0X10+0X11
+0X12+0X13
ST
X3+X8+X12>=90
X2+2X7+X8+2X10>=120
3X2+X3+2X4+X5+X6+2X11>=136
5X1+X4+2X5+2X7+4X9>=310
4X3+2X5+4X6+X9+2X10+X11+7X12+16X13>=215
5X1+X4+4X6+2X7+4X8+7X9+6X10+3X11+X12>=320
END
GIN X1
GIN X2
GIN X3
GIN X4
GIN X5
GIN X6
GIN X7
GIN X8
GIN X9
GIN X10
GIN X11
GIN X12
GIN X13
4、在WINDOWS版的LINDO系統中,從LINDO菜單下選用SOLVE命令,則可以得到如下結果:
SET X2 TO <= 27 AT 1, BND= 0.0000E+00 TWIN= 0.0000E+00 43
SET X11 TO <= 0 AT 2, BND= 0.0000E+00 TWIN= 0.0000E+00 45
SET X4 TO <= 41 AT 3, BND= 0.0000E+00 TWIN= 0.0000E+00 50
SET X4 TO <= 0 AT 4, BND= 0.0000E+00 TWIN= 0.0000E+00 53
NEW INTEGER SOLUTION OF 0.000000000E+00 AT BRANCH 8 PIVOT 53
BOUND ON OPTIMUM: 0.0000000E+00
DELETE X4 AT LEVEL 4
DELETE X4 AT LEVEL 3
DELETE X11 AT LEVEL 2
DELETE X2 AT LEVEL 1
ENUMERATION COMPLETE. BRANCHES= 8 PIVOTS= 53
LAST INTEGER SOLUTION IS THE BEST FOUND
RE-INSTALLING BEST SOLUTION...
OBJECTIVE FUNCTION VALUE
1) 0.0000000E+00
VARIABLE VALUE REDUCED COST
X1 62.000000 0.000000
X2 27.000000 0.000000
X3 55.000000 0.000000
X4 0.000000 0.000000
X5 0.000000 0.000000
X6 0.000000 0.000000
X7 0.000000 0.000000
X8 93.000000 0.000000
X9 0.000000 0.000000
X10 0.000000 0.000000
X11 0.000000 0.000000
X12 0.000000 0.000000
X13 0.000000 0.000000
ROW SLACK OR SURPLUS DUAL PRICES
2) 58.000000 0.000000
3) 0.000000 0.000000
4) 0.000000 0.000000
5) 0.000000 0.000000
6) 5.000000 0.000000
7) 362.000000 0.000000
NO. ITERATIONS= 53
BRANCHES= 8 DETERM.= 1.000E 0
5、運行結果分析:
(1).本次計算用到53次叠代。
(2).材料浪費率為0,即材料利用率為100%。
(3).、最優解變量:
VARIABLE VALUE REDUCED COST
X1 62.000000 0.000000
X2 27.000000 0.000000
X3 55.000000 0.000000
X4 0.000000 0.000000
X5 0.000000 0.000000
X6 0.000000 0.000000
X7 0.000000 0.000000
X8 93.000000 0.000000
X9 0.000000 0.000000
X10 0.000000 0.000000
X11 0.000000 0.000000
X12 0.000000 0.000000
X13 0.000000 0. 000000
第二列,即“VALUE”給出最優解中各變量(VARIABLE)的值:
X1 = 62.000000;x2=27.000000;x3=55.000000; x8=93.000000;
x4=x5=x6=x7=x9=x10=x11=x12=x13=0
第三列,即“REDUCED COST” 給出最優單純形表中第0行中變量的系數 . 其中基變量的reduced cost值應為0,對於非基變量, 相應的 reduced cost值表示當該非基變量增加壹個單位時目標函數減少的量。本例中此值均為0。
(4)、分析結果的下半部分:
ROW SLACK OR SURPLUS DUAL PRICES
2) 58.000000 0.000000
3) 0.000000 0.000000
4) 0.000000 0.000000
5) 0.000000 0.000000
6) 5.000000 0.000000
7) 362.000000 0.000000
第二列,即“SLACK OR SURPLUS” 給出松馳變量的值: 第3、4、5行松馳變量均為0, 說明對於最優解來講,兩個約束(第3、4、5行)均取等號。
第三列,即“DUAL PRICES” 給出對偶價格的值: 各行對偶價格均為0.000000。
6、最後結果:
長度為8米的根數為:0
長度為12米的根數為:62+27+55+93=237
材料利用率為100%。