最全运筹学习题及答案

第 25 页 共 64 页

x2 cj?zj 2 1/2 -3 1 0 0 0 -1 0 2 -4 解：

（1）初始单纯形表的增广矩阵是：

?aC1=?11?a21a12a22a13a2310b1?

01b2??最终单纯形表的增广矩阵为

?1010.5?0.51.5?C2=? ?22??0.510?1C2是

C1作初等变换得来的，将的单位矩阵。有： C2作初等变换，使得C2的第四列和第五列

的矩阵成为

C2a11=9/2； a12=1； a13=4； a21=5/2； a22=1； a23=2； b1=9； b2=5

由检验计算得：

c1=-3； c2=c3=0

2.7已知线性规划问题 Max z=2x1+x2+5x3+6x4 s.t. 2x1+x3+x4?8 2x1+2x2+x3+2x4?12 xj?0，j=1,…4

*?1，试应用对偶问题对偶变量y1，y2，其对偶问题的最优解是y1*=4，y2的性质，求原问题的最优解。

解：

对偶问题是：

Min w=8y1+12y2 s.t. 2y1+2y2?2 2y2?1

第 26 页 共 64 页

y1+y2?5 y1+2y2?6 y1，y2?0

?，Y?是原问题和对偶问题的可行解，那么，Y?X=0互补松弛性可知，如XS

和

?=0，当且仅当X?是最优解。 ?，YYSX设 X,Y是原问题和对偶问题的可行解，YS=（y3，有： Y

y4，y5，y6）

XS

=0; 且 YSX=0

x5=x6=0，原问题约束条件取等号，x3=4；x4=4 最优解X=（0，0，4，4)T

目标函数最优值为44。

2.8试用对偶单纯形法求解下列线性规划问题。 （1）min z=x1+x2 2x1+x2?4 x1+7x2?7 x1,x2?0

(2) min z=3x1+2x2+x3+4x4 2x1+4x2+5x3+x4 ?0 3x1- x2+7x3-2x4 ?2 5x1+2x2+x3+10x4 ?15

x1 ,x2, x3, x4 ?0

解： （1）

取w=-z，标准形式：

第 27 页 共 64 页

Max w=-x1-x2+0x3+0x4 s.t.

-2x1-x2+x3=-4 -x1-7x2+x4=-7 x1，x2，x3，x4?0 单纯形法求解（略）： 最优解：

X=（21/13，10/13，0，0)T 目标函数最优值为31/13。

（2）令：w=-z，转化为标准形式： Max w=-3x1-2x2-x3-4x4+0x5+0x6+0x7 s.t.

-2x1-4x2-5x3-x4+x5=0 -3x1+x2-7x3+2x4+x6=-2 -5x1-2x2-x3-6x4+x7=-15

x1，x2，x3，x4，x5，x6，x7?0 单纯形法略 原问题最优解：

X=（3，0，0，0，6，7，0)T 目标函数最优值为9。 2.9现有线性规划问题 max z=- 5x1+5x2+13x3 - x1+x2+3x3 ?20 12 x1+4x2+10x3 ?90

x1 ，x2， x3 ?0

先用单纯形法求出最优解，然后分析在下列各种条件下，最优解分别有什么变化？

（1） 约束条件1的右端常数20变为30

第 28 页 共 64 页

（2） 约束条件2的右端常数90变为70 （3） 目标函数中x3的系数变为8

??1?（4） x1的系数向量变为??

?12?（5） 增加一个约束条件2x1+3x2+5x3?50 （6） 将约束条件2变为10x1+5x2+10x3?100 解：

把原问题化成标准型的：

Max z=-5 x1+5 x2+13 x3+0 x4+0 x5 s.t

- x1+ x2+3 x3+ x5=20 12 x1+4 x2+10 x3+ x5=90

x1，x2，x3，x4，x5?0

单纯形法解得： 最优解：

X=（0，20，0，0，10)T 目标函数最优值为100。

非基变量x1的检验数等于0，原线性问题有无穷多最优解。 （1）约束条件?的右端常数变为30 有 ?b??B?1?b 因此 b??b??b? 单纯形法解得： 最优解：

X=（0，0，9，3，0)T 目标函数最优值为117。

2右端常数变为70 （2）约束条件○有 ?b??B?1?b 因此 b??b??b?

单纯形法解得，最优解： X=（0，5，5，0，0)T