运筹学练习参考答案

线性规划问题

1、某工厂生产I、II、III三种产品，分别经过A、B、C三种设备加工。已知生产单位各种产品所需的设备台时、设备的现有加工能力及每件产品的预期利润见下表： I II III 设备能力（台时） A 1 1 1 100 B 10 4 5 600 C 2 2 6 300 10 6 4 单位利润（元） （1） 求获利最大的产品生产计划； （2） 产品III每件的利润增加到多大时才值得安排生产；

（3） 如有一种新产品，加工一件需设备A、B、C的台时各为1，4，3小

时，预期每件的利润为8元，是否值得安排生产。

解：（1）设x1，x2，x3分别为I、II、III三种产品的产量，z表示利润。该问题的线性规划模型为：

maxz?10x1?6x2?4x3?x1?x2?x3?100?10x?4x?5x?600?123s..t??2x1?2x2?6x3?300??x1,x2,x3?0用单纯形法求上述线性规划问题。化为标准形式：

maxz?10x1?6x2?4x3?0x4?0x5?0x6? x1 ?x2 ?x3?x4 ?100?10x?4x?5x ?x ?600?1235s..t?? 2x1?2x2?6x3 ?x6?300?xj?0,j?1,2,?,6?cj? 10 6 4 x1 x2 cB xB x3 b x 0 4100 1 1 1 x 0 5600 [10] 4 5 x 0 6300 2 2 6 ?j 0 10 6 4 x 0 440 0 [0.6] 0.5 x 10 160 1 0.4 0.5 x 0 6180 0 1.2 5 ?j -600 0 2 -1

0 x4 1 0 0 0 1 0 0 0 0 x5 0 1 0 0 0 x6 ? 0 100 0 60 1 150 0 -0.1 0 200/3 0.1 0 150 -0.2 1 150 -1 0 1

6 10 0 x2 x1 200/3 100/3 100 -2200/3 0 1 0 0 1 0 0 0 5/6 5/3 -1/6 0 1/6 -2/3 1/6 0 4 -2 0 1 x6 ?j -8/3 -10/3 -2/3 0 所以最优解为x* =(100/3，200/3，0，0，0，100)T，即产品I、II、III的产量分别为：100/3，200/3，0；最优解目标函数值z* =2200/3

（2）设产品III每件的利润为c3

?3?c3?CBB?1P3?c3?CBP3??5/6????c?6,10,01/6??3 ???c3?20/3?0?c3?20/3?4???产品III每件的利润增加到20/3时才值得安排生产。

（3）设x7为新产品的产量。

?1?102??7?c7?cBB?1P7?8?(,,0)?4??2?0?值得投产 33??3????5/3?1/60??1??1???4???0? P7??B?1P7???2/31/60???????3??1????01???2???cj? cB xB 6 10 0 b 200/3 100/3 100 -2200/3 200/3 100/3 100/3 -2600/3 10 x1 0 1 0 0 0 1 0 0 6 x2 1 0 0 0 1 0 -1 4 x3 5/6 1/6 4 0 x4 5/3 -2/3 -2 0 x5 -1/6 1/6 0 0 x6 0 0 1 0 0 0 1 0 8 x7 ? x2 x1 [1] 200/3 0 1 2 1 0 0 0 - 100 x6 ?j 8 10 0 -8/3 -10/3 -2/3 5/6 1/6 5/3 -2/3 -1/6 1/6 x7 x1 x6 19/6 -11/3 1/6 ?j -2 -13/3 -20/3 -1/3 所以最优解为x* =(100/3，0，0，0，0，200/3)T，即产品I的产量：100/3，新产品的产量：200/3；最优解目标函数值z* =2600/3

2

2、已知下列线性规划问题：

maxz?6x1?3x2?3x3?3x1?x2?x3?60?2x?2x?4x?20 ?123s..t??3x1?3x2?3x3?60??x,x,x?0123求：（1）用单纯形法求解，并指出问题属于哪一类解； （2）写出该问题的对偶问题，并求出对偶问题的最优解；

解：（1）将原问题划为标准形得：

maxz?6x1?3x2?3x3?0x4?0x5?0x6??3x1 ?x2?x3?x4 ?60s..t?2x1?2x?4x ?x ?20

?235?3x1?3x2?3x3 ?x6?60??xj?0,j?1,2,?,6

cj 6 -3 3 0 0 0 cB xB b x1 x2 x3 x4 x5 x6 ? 0 x4 60 3 1 1 1 0 0 20 0 x5 20 [2] -2 4 0 1 0 10 0 x6 60 3 -3 3 0 0 1 20 ?j 0 6 -3 3 0 0 0 0 x4 30 0 4 -5 1 -3/2 0 15/2 6 x1 10 1 -1 2 0 1/2 0 - 0 x6 30 0 [6] -9 0 -3/2 1 5 ?j -60 0 3 -9 0 -3 0 0 x4 10 0 0 1 1 -1/2 -2/3 6 x1 15 1 0 1/2 0 1/4 1/6 -3 x2 5 0 1 -3/2 0 -1/4 1/6 ?j -75 0 0 -9/2 0 -9/4 -1/2 最优解为x* =(15，5，0，10，0，0)T 最优解目标函数值z* =75 非基变量的检验数<0, 为唯一最优解.

3

（2）该问题的对偶问题为：

minw?60y1?20y2?60y3?3y1?2y2?3y3?6?y?2y?3y??3?123s..t??y1?4y2?3y3?3??y1,y2,y3?0

对偶问题的最优解：y* =(0，9/4，1/2)

3、已知线性规划问题：

maxz?x1?2x2?2x1?x2?8?s..t? x2?4?x,x?0?12 求：（1）用图解法求解； （2）写出其对偶问题；

（3）根据互补松弛定理，写出对偶问题的最优解。

解：（1）图解法

x2ABx2?4OC2x1?x2?8x1由上图可知：在B(2,4)处，目标函数达到最大值。

即最优解为x*=(2,4)T 最优解目标函数值z*=10 为唯一最优解 （2）该问题的对偶问题为：

minw?8y1?4y2?2y1?1 ?s..t?y1?y2?2?y?0,y?02?1（3）原问题的最优解x*=(2,4)T代入约束条件，可知约束条件取等式，因为x1*，x2*不为0，在对偶问题中相应的约束条件为紧约束，

???即2y1?1,y1?y2?2

对偶问题的最优解及最优目标函数值为：y??(1/2,3/2)

w??10

4