最全运筹学习题及答案(7)

第 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

第 29 页 共 64 页

目标函数最优值为90。

（3）x3的系数变成8，x3是非基变量，检验数小于0，所以最优解不变。

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

?5?x1是非基变量，检验数等于-5，所以最优解不变。

3 （5）解：加入约束条件○用对偶单纯形表计算得： X=（0，25/2，5/2，0，15，0)T 目标函数最优值为95。 （6）改变约束条件，P3,P4,P5没有变化， 线性规划问题的最优解不变。 2.10已知某工厂计划生产I,II,III三种产品，各产品在ABC设备上加工，数据如下表， 设备代号 每月设备 I II III 有效台时 A 8 2 10 300 B 10 5 8 400 C 2 13 10 420 单位产品利润3 2 2.9 /千元 （1）如何充分发挥设备能力，使生产盈利最大？ （2）如果为了增加产量，可借用其他工厂的设备B，每月可借用60台时，租金为1.8万元，问借用是否合算？ （3）若另有两种新产品IV,V，其中IV为10台时，单位产品利润2.1千元；新产品V需用设备A为4台时，B为4台时，C为12台时，单位产品盈利1.87千元。如A,B,C设备台时不增加，分别回答这两种新产品投产在经济上是否划算？ （4）对产品工艺重新进行设计，改进结构，改进后生产每件产品I，需要设备A为9台时，设备B为12台时，设备C为4台时，单位产品利润4.5千元，问这对原计划有何影响？

解：

（1）设：产品三种产品的产量分别为，x1，x2，x3，建立数学模型： Max z=3x1+2x2+2.9x3 s.t.

第 30 页 共 64 页

8x1+2x2+10x3?300 10x1+5x2+8x3?400 2x1+13x2+10x3?420

x1,x2,x3?0

把上述问题化为标准型，用单纯形法解得： 最优解：

X=（338/15，116/5，22/3，0，0，0)T

目标函数最优值为2029/15。 （2）

设备B的影子价格为4/15千元/台时，借用设备的租金为0.3千元每台时。 所以，借用B设备不合算。 （3）

设备?V,V生产的产量为x7，x8，系数向量分别为： P7?(12,5,10)T P8?(4,4,12)T 检验数?7=-0.06，所以生产?V不合算，

?8=37/300，生产V合算。 单纯形法计算得： 最优解： X=（107/4，31/2，0，0，0，0，55/4)T 目标函数最优值为10957/80。

（4）改进后,检验数?1?=253/300，大于零。

所以，改进技术可以带来更好的效益。

2.11分析下列参数规划中当t变化时最优解的变化情况。 （1）Max z(t)=(3-6t) x1+(2-2t) x2+(5-5t) x3 (t?0) s.t.

x1+2x2+x3 ?430

3x1+2x3 ?460