7将线性规划模型化为标准形式

Min Z =x1+2x2+3x3

?-2x1?x2?x3?9???3x1?x2?2x3?4 ?

?4x1?2x2?3x3??6?x?0，x?0,x无约束23?1

解：令Z’ = -z，引进松弛变量x4?0,引进剩余变量x5?0,得到一下等价的标准形式。

?-2x1?x2?x3?x4?9???3x1?x2?2x3?x5?4 ?

?4x1?2x2?3x3??6?x?0,x,x,x?0,245?1

x2’=-x2 x3=x3’-x3’’ Z’ = -min Z = -x1-2x2-3x3

''''?-2x1?x2?x3?x3?x4?9?''' ??3x1?x2??x5?4 ?2?x3?x3?'''????64x?2x?3x?x1233?8.maxZ=3x1?3x2?4x3?3x1?4x2?5x3?x4?40??6x1?4x2?3x3?x5?66??xj?0,j?1,2,3,4,5Cj CB 0 0 4 0 4 3 XB X4 X5 σj x3 x5 σj x3 x1 σj 2 10 8 42 b 40 60

3 x1 3 6 3 3/5 21/5 3/5 0 1 0 3 x2 4 4 3 4/5 8/5 -1/5 4/7 8/21 -3/7 4 x3 5 3 4 1 0 0 1 0 0 0 x4 1 0 0 1/5 -3/5 -4/5 4/35 1/7 -31/35 0 x5 0 1 0 0 1 0 -1/7 5/21 -1/7 θi 8 20 40/3 60/7 ?最优解为（10,0，2,0,0），目标函数maxZ=38.

9用单纯形法求解线性规划问题：

Max Z =70x1+120x2

?9x1?4x2?360? ?4x1?6x2?200

??3x1?10x2?300

解： Max Z =70x1+120x2

?9x1?4x2?x3?360? ?4x?6x?x?200 124??3x1?10x2?x5?300

单纯形表如下

Max Z =3908.

10.maxZ?4x1?3x2?2x1+2x2?3000??5x1?2.5x2?4000??x1?500?x,x?0?12解：引入松弛变量x3,x4,x5(x3,x4,x5?0)?2x1?2x2?x3?3000??5x1?2.5x2+x4?4000??x1?x5?500?x?0,j?1,2,3,4,5?jCj CB 0 0 0 XB X3 X4 X5 Cj-Zj b 3000 4000 500 4 x1 2 5 [1] 4 3 x2 2 2.5 0 3 0 x3 1 0 0 0 0 x4 0 1 0 0 0 x5 0 0 1 0 θi 1500 800 500 ?1?c1?z1?4?(0?2?0?5?0?1)?4?2?c2?z2?3?(0?2+0?2.5+0?0)?3检验数>0,max(?1,?2)?max(4,3)?4,?对应的x1为换入变量.?30004000500??min??,,??500,?x5为换出变量.51?min?2

Cj CB 0 0 0 XB X3 X4 X1 Cj-Zj b 2000 1500 500 4 x1 0 0 1 0 3 x2 2 2.5 0 0 0 x3 1 0 0 0 0 x4 0 1 0 0 0 x5 -2 -5 1 -4 θi 非基变量检验数?0，?得到最优解：x1?500,x2?0,x3?2000,x4?1500,x5?0,?目标函数的maxZ=4?1?c1?z1?4?(0?2?0?5?0?1)?4?500?3?0?2000.11.解：（1）引入松弛变量X4，X5，X6，将原问题标准化，得

max Z=10X1+6X2+4X3 X1+X2+X3+X4=100 10 X1+4X2+5X3+X5=600 2 X1+2X2+6X3+X6=300 X1,X2,X3,X4,X5,X6≥0 得到初始单纯形表：

Cj CB 0 0 0 XB X4 X5 X6 Cj-Zj b 100 600 300 10 X1 1 [10] 2 10 6 X2 1 4 2 6 4 X3 1 5 6 4 0 X4 1 0 0 0 0 X5 0 1 0 0 0 X6 0 0 1 0 θ 100 60 150 （2）其中ρ1 =C1-Z1=10-（0×1+0×10+0×2）=10，同理求得其他 根据ρθ

min

max

=max{10,6,4}=10,对应的X1为换入变量，计算θ得到，

=min{100/1,600/10,300/2}=60,X5为换出变量，进行旋转运算。

（3）重复（2）过程得到如下迭代过程

Cj CB 0 10 0 XB X4 X1 X6 Cj-Zj 6 10 0 X2 X1 X6 Cj-Zj 200/3 100/3 100 b 40 60 180 10 X1 0 1 0 0 0 1 0 0 *

6 X2 [3/5] 2/5 6/5 2 1 0 0 0 4 X3 1/2 1/2 5 -1 5/6 1/6 4 -8/3 0 X4 1 0 0 0 5/3 -2/3 -2 -10/3 0 X5 -1/10 1/10 1/5 -1 -1/6 1/6 0 -2/3 T

0 X6 0 0 1 0 0 0 1 0 θ 200/3 150 150 200/3 150 150 ρj ≤0，迭代已得到最优解，X=（100/3，200/3，0，0，0，100） ， Z =10×100/3+6×200/3+4×0 =2200/3。

*

12解：（1）引入松弛变量X3，X4，X5将原问题标准化，得

max Z=2X1+X2 5X2+X3=15 6X1+2X2+ X4=24 X1+2X2+ X5=5 X1,X2,X3,X4,X5≥0 得到初始单纯形表：

Cj CB 0 0 0 XB X3 X4 X5 Cj-Zj b 15 24 5 2 X1 0 [6] 1 2 1 X2 5 2 1 1 0 X3 1 0 0 0 0 X4 0 1 0 0 0 X5 0 0 1 0 θ - 4 5 （2）其中ρ1 =C1-Z1=2-（0×1+0×10+0×2）=2，同理求得其他 根据ρθ

min

max

=max{2,1,0}=2,对应的X1为换入变量，计算θ得到，

=min{-,24/6,5/1}=4, X4为换出变量，进行旋转运算。

（3）重复（2）过程得到如下迭代过程

Cj CB 0 2 0 XB X3 X1 X5 Cj-Zj 0 2 1 X3 X1 X2 Cj-Zj 15/2 17/2 3/2 b 15 4 1 10 X1 0 1 0 0 0 1 0 0 *

6 X2 5 1/3 [2/3] 1/3 0 0 1 0 4 X3 1 0 0 0 1 0 0 0 0 X4 0 1/6 -1/6 -1/3 5/4 1/4 -1/4 -1/4 T

0 X5 0 0 1 0 -15/2 -1/2 3/2 -1/2 θ 3 12 3/2 ρj ≤0，迭代已得到最优解，X=（7/2，3/2，0，0，0） ， Z =2×7/2+3/2 =17/2。

*