案例1玻璃下料问题.docx

1、案例1玻璃下料问题案例一：玻璃下料问题已知玻璃尺寸有:21.5 m2；2.21.5 m2；2.21.65 m2；2.11.65 m2需要切割尺寸及数量:10.75 m2 (20块)；1.050.90 m2 (15块)；0.80.85 m2 (30块)；1.100.85 m2 (35块)；1.51.20 m2 (50块)；0.951.25 m2 (45块)；1.30.75 m2 (100块)问：如何切割用料最省?表2-1 各裁截方案所得不同规格的玻璃数目所需数目x1x2x3x4x5x6x7x8x9x10x11x12x13x14x15x1610.752042222331120.850.830222

2、1.51.25011111.30.751001321.050.9151121.10.8535211111.250.95452111余料00.2250.6250.312500.3750.31250.260.250.320.270.3050.280.420.59250.075minz=0.225x2+0.625x3+0.3125x4+0.375x6+0.3125x7+0.26x8+0.25x9+0.32x10+0.27x11+0.305x12+0.28+x13+0.42x14+0.5925x15+0.075x16s.t.4x1+2x4+2x5+2x8+2x9+3x11+3x13+x14+x15+2

3、x16=202x10+2x12+2x14=30x2+x5+x7+x12=50x2+3x6+2x10=100x9+x11+2x16=152x8+x9+x13+x14+x15=352x3+x4+x7+x15=45x1,x2,x3,x4,x5,x6=0，且为整数引入人工变量x17,x18,x19,x20,x21,x22,x23用两阶段法计算下列问题:第一阶段：计算minZ1=x17+x18+x19+x20+x21+x22+x23s.t.4x1+ 2x4+2x5 +2x8+2x9 +3x11 +3x13+x14+x15+2x16+x17 =20 2x10 +2x12 +2x14 +x18 =30x2

4、+x5 +x7 +x12 +x19 =50x2 +3x6 +2x10 +x20 =100 x9 +x11 +2x16 +x21 =15 2x8+x9 +x13 +x14 +x15 +x22 =35 2x3+x4 +x7 +x15 +x23 =45xj=0，j1，2，23根据上面的表达式可得计算表如下：cj00000000000000001111111CBXBbx1x2x3x4x5x6X7x8x9x10x11x12x13x14x15x16x17x18x19x20x21x22x23i(x1)i(x8)1x1720400220022030311210000005(1) 行*1x18300000000

5、0020202000100000-(2)行1x195001001010000100000010000-(3)行1x201000100030002000000000100-(4)行1x211500000000101000020000100-(5)行1x223500000002100011100000010-17.5(6)行1x234500210010000000100000001-(7)行_Z1295-4-2-2-3-3-3-2-4-4-4-4-3-4-40-40000000注：ibi/aik | aik0;-Z=cibi,I=1,2,m;j=cj-ciaij,I=1,2,m; j=1,2,n*

6、为下一次迭代主元所在的行。第一次迭代第一步：求目标函数为最小，则取j为最小的值所对应得变量x1,x8、x9、x10、x11、x13、x14、x16为入基变量。第二步：选x1为入基变量，求ibi/ai1 | ai10得：Mini对应得x17为出基变量，a1，1为主元做旋转运算：第三步：主元所在的行/4，完成一次迭代，见下表。cj00000000000000001111111CBXBbx1x2x3x4x5x6x7x8x9x10x11x12x13x14x15x16x17x18x19x20x21x22x23i(x10)0x151000.50.5000.50.500.800.80.30.30.50.30

7、00000-(1)行1x18300000000002020200010000015(2)行*1x195001001010000100000010000(3)行1x20100010003000200000000010050(4)行1x211500000000101000020000100-(5)行1x223500000002100011100000010-(6)行1x234500210010000000100000001-(7)行_Z12750-2-2-1-1-3-2-2-2-4-1-3-1-30-21000000第二次迭代第一步：求目标函数为最小，则取j为最小的值所对应得变量x10，选x10为

8、入基变量，求i第二步：选x10为入基变量，求ibi/ai10 | ai100得：Mini15对应得x18为出基变量第三步：a2，10为主元做旋转运算（1） x20所在的行主元所在的行，（2） 主元所在的行/2；完成二次迭代，见下表。cj00000000000000001111111CBXBbx1x2x3x4x5x6x7x8x9x10x11x12x13x14x15x16x17x18x19x20x21x22x23i(x6)0x151000.50.5000.50.500.800.80.30.30.50.3000000-(1)行0x1015000000000101010000.500000-(2)行1

9、x195001001010000100000010000-(3)行1x207001000300000-20-2000-10100023.33(4)行*1x211500000000101000020000100-(5)行1x223500000002100011100000010-(6)行1x234500210010000000100000001-(7)行_Z12150-2-2-1-1-3-2-2-20-11-110-21200000第三次迭代第一步：求目标函数为最小，则取j为最小的值所对应得变量x6为入基变量，求i第二步：选x6为入基变量，求ibi/ai6 | ai30得：Mini对应得x20为

10、出基变量，第三步：以a4,6为主元做旋转运算：（1） 主元所在的行/3，完成第三次迭代，见下表。cj00000000000000001111111CBXBbx1x2x3x4x5x6x7x8x9x10x11x12x13x14x15x16x17x18x19x20x21x22x23i(x3)0x151000.50.5000.50.500.800.80.30.30.50.3000000-(1)行0x1015000000000101010000.500000-(2)行1x195001001010000100000010000-(3)行0x62300.3000100000-10-1000-000.3000

11、-(4)行1x211500000000101000020000100-(5)行1x223500000002100011100000010-(6)行1x23450021001000000010000000122.5(7)行*_Z11450-1-2-1-10-2-2-20-1-1-1-10-21101000第四次迭代第一步：求目标函数为最小，则取j为最小的值所对应得变量x3、x7、x8、x9、x16为入基变量，求i第二步：以x3为入基变量，求ibi/ai3 | ai30得：Mini4.33对应的x23出基变量第三步：以a7,3为主元做旋转运算：（1）主元所在的行/2，完成第四次迭代，见下表。cj0

12、0000000000000001111111CBXBbx1x2x3x4x5x6x7x8x9x10x11x12x13x14x15x16x17x18x19x20x21x22x23i(x16)0x151000.50.5000.50.500.800.80.30.30.50.300000010(1)行0x1015000000000101010000.500000(2)行1x195001001010000100000010000(3)行0x62300.3000100000-10-1000-000.3000(4)行1x2115000000001010000200001007.5(5)行*1x22350000

13、0002100011100000010(6)行0x3230010.5000.500000000.500000000.5(7)行_Z11000-100-10-1-2-20-1-1-1-10-21101001第五次迭代第一步：求目标函数为最小，则取j为最小的值所对应得变量x8、x9、x16为入基变量，求i第二步：以x16为入基变量，求ibi/ai16 | ai160得：Mini7.5对应的x21出基变量第三步：以a5,16为主元做旋转运算：（1） 主元所在的行/2，（2） x1所在的行2主元所在的行，完成第五次迭代，见下表。cj00000000000000001111111CBXBbx1x2x3x

14、4x5x6x7x8x9x10x11x12x13x14x15x16x17x18x19x20x21x22x23i(x8)0x11.31000.50.5000.50.300.500.80.30.300.3000-0002.5(1)行*0x1015000000000101010000.500000(2)行1x195001001010000100000010000(3)行0x62300.3000100000-10-1000-000.3000(4)行0x167.5000000000.500.50000100000.500(5)行1x22350000000210001110000001017.5(6)行0x

15、3230010.5000.500000000.500000000.5(7)行_Z1850-100-10-1-2-100-1-1-1001101101第六次迭代第一步：求目标函数为最小，则取j为最小的值所对应得变量x8为入基变量，求i第二步：以x8为入基变量，求ibi/ai8 | ai80得：Mini2.5对应的x1为出基变量第三步：以a1,8为主元做旋转运算：（1） 主元所在的行2（2） x22所在的行主元所在的行2；，完成第六次迭代，见下表。cj00000000000000001111111CBXBbx1x2x3x4x5x6x7x8x9x10x11x12x13x14x15x16x17x18x

16、19x20x21x22x23i(x2)0x82.5200110010.50101.50.50.500.5000-100(1)行0x1015000000000101010000.500000(2)行1x19500100101000010000001000050(3)行*0x62300.3000100000-10-1000-000.300070(4)行0x167.5000000000.500.50000100000.500(5)行1x2230-400-2-200000-20-2000-1000110(6)行0x3230010.5000.500000000.500000000.5(7)行_Z1804-10210-10002-120002101001第七次迭代第一步：求目标函数为最小，则取j为最小的值所对应得变量x2、x7、x12为入基变量，求i第二步：以x2为入基变量，求ibi/ai2 | ai20得：Mini50对应的x19为出基变量第三步：以a3,2为主元做旋转运算：（1） x6所在的行主元所在的行0.33，完成第七次迭代，见下表。cj00000000000000001