内容发布更新时间 : 2025/11/1 6:09:48星期一 下面是文章的全部内容请认真阅读。

y8 -p 1 1 0 0 0 0 1 1 0 8 0 0 0 6 1 0 5 22 6、用对偶单纯形方法，求解下面问题。 （1）minf=5 X1+3 X2+4 X3 2 X1+3 X2+2 X3≥6 4 X1+3 X2+5 X3≥10 X1 ，X2 ，X3≥0 （2）maxZ= -X1-3 X2-3 X3 2 X1-3 X2+ X3≥4 X1+2 X2+2 X3≤8 2 X2- X3≤2

X1 ，X2 ，X3≥0 解：（1）先将此问题化成下列形式：

maxZ=-5 X1-3 X2-4 X3 -2 X1-3 X2-2 X3+X4=-6 -4 X1-3 X2-5 X3+ X5=-10 Xi≥0（i =1,2,3,4,5）

建立此问题的初始单纯形表并进行运算如下：

Cj -5 -4 X2 -3 -3 -4 1 -4 X2 -3 X3 -2 -5 -3 4/5 -3 X3 0 1 0 0 X4 1 0 0 0 X4 1 0 0 0 X5 0 1 0 0 X5 -2/5 -1/5 -4/5 1/2 CB 0 0 XB X4 X5 b -6 -10 X1 -2 -4 -5 5/4 -5 ?

j ? Cj CB 0 -4 XB X4 X3 b X1 -2 -2/5 -9/5 2 5/4 3/5 -9/5 -3/5 9/2 1/3 ?

j ? Cj -5 -4 X2 1 0 0 -3 X3 0 1 0 0 X4 0 X5 CB -3 -4 XB X2 X3 b X1 10/9 2/9 4/3 2/3 -5/3 -5/9 2/9 1/3 -1/3 -1/3 -2/3 ?j

原问题的对偶规划问题为：

MaxP=6Y1+Y2 2Y1+4Y2≤5 3Y1+3Y2≤3 2Y1+5Y2≤4 Y1 ，Y2≥0

最终表中

b

列数字全为非负，检验数全为非正，所以得出原问题最优解与最优

值分别为：

X*=（0，10/9，4/3）T

f*=3×（10/9）+4×（4/3）=26/3

对偶问题的最优解与最优值分别为：

Y*=（1/3，2/3）T

P*=6×（1/3）+10×（2/3）=26/3= f*

(2) 先将此问题化成下列形式：

maxZ=-X1-3X2-2X3 -2 X1+3 X2-X3+X4=-4 X1+2X2+2 X3+ X5=8 2 X2-X3+X6=2

Xi≥0（i =1,2,3,4,5,6）

建立此问题的初始单纯形表并进行运算如下：

Cj -1 -3 X2 3 2 2 -3 -2 X3 -1 2 -1 -2 2 0 X4 1 0 0 0 0 X5 0 1 0 0 0 X6 0 0 1 0 CB 0 0 0 XB X4 X5 X6 b -4 8 2 X1 -2 1 0 -1 1/2 ?j ?

Cj -1 -3 X2 -2 X3 0 X4 0 X5 0 1 0 0 0 X6 0 0 1 0 CB -1 0 0 XB X1 X5 X6 b 2 6 2 X1 1 0 0 0 -3/2 1/2 -1/2 7/2 3/2 2 -1 1/2 0 ?j -9/2 -3/2 -1/2

原问题的对偶规划问题为：

MinP=-4Y1+8 Y2+2Y3 -2 Y1+ Y2≥-1

3 Y1+2 Y2+2Y3≥-3 -Y1+2 Y2- Y3≥-2 Y1 ，Y2 ，Y3≥0

最终表中

b

列数字全为非负，检验数全为非正，所以得出原问题最优解与最优

值分别为：

X*=（2，0，0）T Z*=-1×2=-2

对偶问题的最优解与最优值分别为：

Y*=（1/2，0,0）T

P*=-4×（1/2）=-2= Z*

7．已知线性规划问题：

maxz?10x1?24x2?20x3?20x4?25x5?x1?x2?2x3?3x4?5x5?19?s..t?2x1?4x2?3x3?2x4?x5?7?x?0(j?1,25)?j

写出其对偶问题，并求一个对偶问题的可行解。

minp?19y1?7y2?y1?2y2?10?y?4y?242?1?解：其对偶问题为?2y?3y2?20 s..t?1?3y1?2y2?20?5y1?y2?25???y1?0,y2?0**在可行域中任取可行解：y1?5,y2?5。

8、考虑下面线性规划

maxZ=2X1+3X2

2 X1+2X2+X3 =12 X1+2X2 + X4=8 4X1 +X5=16 4X2 +X6=12

Xj≥0，j =1,2,…,6

其最优单纯形表如表3-7所示，试分析如下问题： （1） 当C2=5时，求新最优解。 （2） 当b3=4时，求新最优解。

（3） 增加一个约束2X1 +2.4X2≤12，对最优解有何影响。

表3-7 基变量 X3 X1 X6 X2 0 4 4 2 -14 X1 0 1 0 0 0 X2 0 0 0 1 0 解：由最优单纯形表所示结果及灵敏度变动思想求解最优解不变的C2变动范围： （-3/2）/（1/3）≤△C2≤（-1/8）/（-1/8） -3≤△C2≤1

X3 1 0 0 0 0 X4 -1 0 -2 X5 -1/4 1/4 1/2 X6 0 0 1 0 0 1/2 -1/8 -3/2 -1/8 ?j 即 0≤C2≤4

而题设条件为： 新C2=5，超出变动范围，故最优解发生变动，需重新求解。

C2值发生变动后，影响?j的值，故新的?j值分别为：

??4=（-3/2）-(1/2)×（5-3）=-5/2 =（-1/8）-(-1/8)×（5-3）=1/8

5继续上述最优单纯形表的计算：

Cj 2 5 X2 0 0 0 1 0 0 X3 1 0 0 0 0 0 X4 -1 0 -2 1/2 -5/2 0 X5 -1/4 1/4 1/2 -1/8 1/8 0 X6 0 0 1 0 0 CB 0 2 0 5 XB X3 X1 X6 X2 b 0 4 4 2 X1 0 1 0 0 0 ? 16 8 ?

j Cj 2 5 X2 0 0 0 1 0 0 X3 1 0 0 0 0 0 X4 -2 1 -4 0 -2 0 X5 0 0 1 0 0 0 X6 1/2 -1/2 2 1/4 -1/4 CB 0 2 0 5 XB X3 X1 X5 X2 b 2 2 8 3 X1 0 1 0 0 0 ?j

新最优解和最优值分别为：

X*=（2，3）T

Z*=2×2+5×3=19

（2）由最优单纯形表所示结果及灵敏度变动思想求解最优解不变的围：

b3变动范