第三章 线性规划的对偶理论(管理运筹学,李军)

3 线性规划的对偶问题

1． 试从经济角度解释对偶变量的含义。

答：假设有一企业欲将另一个企业拥有的资源收买过来，至少应付出多少代价，才能使此企业愿意放弃生产活动，出让资源。显然后者放弃自己组织生产活动的条件时，对同等数量资源出让的代价不低于该企业自己组织生产活动是的产值。

2． 判断下列说法是否正确

（1） 任何线性规划问题都存在其对偶问题 （正确）

（2） 如果原问题存在可行解，则其对偶问题也一定存在可行解；（错）（3） 当原问题为无界解时，对偶问题也为无界解；（错） （4） 当对偶问题无可行解时，原问题一定具有无界解；（错）

（5） 若原问题有无穷多最优解，则对偶问题也一定具有无穷多最优解

3写出下列线性规划问题的对偶问题：

（1）minw 2x1 2x2 4x3

x1 + 2x2 + x3 2

2x1 + x2 +3x3 6 x1 +4x2 +6x3 5

x1,x2,x3 0

解：

maxw y1 6y2 5y3y1 2y2 y3 22y1 y2 4y3 2

y1 3y2 6y3 4y1 0,y2 0,y3 0

（2）max 2x1 3x2 x3

x1 + 2x2 + x3 10

3x1 +2x3 15 x1 +2x2 + x3 12

x1 0,x2 0,x3无约束

（错）

解：

minw 10y1 15y212 y3y1 3y2 y3 2

2

y1 2

y3 3y1 2y2 y3 1y1 0,y2 0,y3无约束

4. 用对偶单纯形法求解下述线性规划问题

（1）minw 4x1 12x2 18x3 （2）minw x1 2x2 3x3 4x4

x1 +3x3 3 x1 +2x2 +2x3 +3x4 30

2x2 +2x3 5 2x1 +x2 +3x3 +2x4 20

x1,x2,x3 0 x1,x2,x3,x4 0

（1） 转换化成标准形式：

minw 4x1 12x2 18x3x1 3x3 x4 32x2 2x3 x5 5x1~5 0

X=(0,2/3,1,0,0)

(2)转化为标准形式

minw x1 2x2 3x3 x4x1 2x2 2x3 3x4 x5 302x1 x2 3x3 2x4 x6 20x1~6 0

X＝(30,0,0,0,0,40) minz=30

5 （1）由最终单纯形表可知，为保持原最优解不变应有：

2 1 ( 3C1 5) 0 4 (C1 1) 0 5 ( C

1 2) 0

13

解不等式组得：C 6, 3

13

(3)因为原材料的市场价格0.8小于原材料的影子价格1，所以，可以买进原材料。假设买进

1 1 85 3 45 3 原材料100单位，则此公司拥有原材料的总额为130。b´＝ 3 12 130 111 55

将b´反映进单纯形表中： 最终的单纯形表

1 1 33 3

(4)x1 x2 3x3 20为非基变量， 2 1 3, 5 1 0

12 2 55

所以，最优解不变。

（5）将原问题的最优解X=（5，0，3，0，0）代入不等式x1 x2 3x3 20中，不等式仍然成立，故最优解不变。

（6）将原问题的最优解X=（5，0，3，0，0）代入不等式3x1 x2 2x3 20中，不等式不成立，所以最优解将发生变化。将新的约束条件反映进单纯形表中：

X* （40/9，0，8/3，5/3，0，0）

Maxz=80/3