案例1玻璃下料问题Word下载.docx

案例1玻璃下料问题Word下载.docx

《案例1玻璃下料问题Word下载.docx》由会员分享，可在线阅读，更多相关《案例1玻璃下料问题Word下载.docx（24页珍藏版）》请在冰点文库上搜索。

1.25m2（45块）；

1.3×

0.75m2（100块）

问：

如何切割用料最省?

表2-1各裁截方案所得不同规格的玻璃数目

所需

数目

x1

x2

x3

x4

x5

x6

x7

x8

x9

x10

x11

x12

x13

x14

x15

x16

0.75

20

4

2

3

1

0.85×

0.8

30

1.2

50

100

0.9

15

1.1×

0.85

35

1.25×

0.95

45

余料

0.225

0.625

0.3125

0.375

0.26

0.25

0.32

0.27

0.305

0.28

0.42

0.5925

0.075

minz=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.075x16

s.t.

4x1+2x4+2x5+2x8+2x9+3x11+3x13+x14+x15+2x16=20

2x10+2x12+2x14=30

x2+x5+x7+x12=50

x2+3x6+2x10=100

x9+x11+2x16=15

2x8+x9+x13+x14+x15=35

2x3+x4+x7+x15=45

x1,x2,x3,x4,x5,x6>

=0，且为整数

引入人工变量x17,x18,x19,x20,x21,x22,x23

用两阶段法计算下列问题:

第一阶段：

计算minZ1=x17+x18+x19+x20+x21+x22+x23

4x1+2x4+2x5+2x8+2x9+3x11+3x13+x14+x15+2x16+x17=20

2x10+2x12+2x14+x18=30

x2+x5+x7+x12+x19=50

x2+3x6+2x10+x20=100

x9+x11+2x16+x21=15

2x8+x9+x13+x14+x15+x22=35

2x3+x4+x7+x15+x23=45

xj>

=0，j＝1，2，…，23

根据上面的表达式可得计算表如下：

cj－>

CB

XB

b

X7

x17

x18

x19

x20

x21

x22

x23

θi（x1）

θi（x8）

5

（1）行*

-

（2）行

（3）行

（4）行

（5）行

17.5

（6）行

（7）行

_Z1

295

-4

-2

-3

注：

θi＝bi/aik|aik>

0;

-Z=∑cibi,I=1,2,…,m;

σj=cj-∑ciaij,I=1,2,…,m;

j=1,2,…,n

*为下一次迭代主元所在的行。

第一次迭代

第一步：

求目标函数为最小，则取σj为最小的值所对应得变量x1,x8、x9、x10、x11、x13、x14、x16为入基变量。

第二步：

选x1为入基变量，求θi＝bi/ai1|ai1>

0得：

Minθi对应得x17为出基变量，a1，1为主元做旋转运算：

第三步：

主元所在的行/4，完成一次迭代，见下表。

θi（x10）

0.5

0.3

（1）行

（2）行*

275

-1

第二次迭代

求目标函数为最小，则取σj为最小的值所对应得变量x10，选x10为入基变量，求θi

选x10为入基变量，求θi＝bi/ai10|ai10>

Minθi＝15对应得x18为出基变量

a2，10为主元做旋转运算

（1）x20所在的行－主元所在的行，

（2）主元所在的行/2；

完成二次迭代，见下表。

θi（x6）

70

23.33

（4）行*

215

第三次迭代

求目标函数为最小，则取σj为最小的值所对应得变量x6为入基变量，求θi

选x6为入基变量，求θi＝bi/ai6|ai3>

Minθi对应得x20为出基变量，

以a4,6为主元做旋转运算：

（1）主元所在的行/3，完成第三次迭代，见下表。

θi（x3）

23

-0

22.5

（7）行*

145

第四次迭代

求目标函数为最小，则取σj为最小的值所对应得变量x3、x7、x8、x9、x16为入基变量，求θi

以x3为入基变量，求θi＝bi/ai3|ai3>

Minθi＝4.33对应的x23出基变量

以a7,3为主元做旋转运算：

（1）主元所在的行/2，完成第四次迭代，见下表。

θi（x16）

10

7.5

（5）行*

第五次迭代

求目标函数为最小，则取σj为最小的值所对应得变量x8、x9、x16为入基变量，求θi

以x16为入基变量，求θi＝bi/ai16|ai16>

Minθi＝7.5对应的x21出基变量

以a5,16为主元做旋转运算：

（1）主元所在的行/2，

（2）x1所在的行×

2－主元所在的行，完成第五次迭代，见下表。

1.3

2.5

（1）行*

85

第六次迭代

求目标函数为最小，则取σj为最小的值所对应得变量x8为入基变量，求θi

以x8为入基变量，求θi＝bi/ai8|ai8>

Minθi＝2.5对应的x1为出基变量

以a1,8为主元做旋转运算：

（1）主元所在的行×

（2）x22所在的行－主元所在的行×

2；

，完成第六次迭代，见下表。

θi（x2）

1.5

（3）行*

80

第七次迭代

求目标函数为最小，则取σj为最小的值所对应得变量x2、x7、x12为入基变量，求θi

以x2为入基变量，求θi＝bi/ai2|ai2>

Minθi＝50对应的x19为出基变量

以a3,2为主元做旋转运算：

（1）x6所在的行－主元所在的行×

0.33，完成第七次迭代，见下表。