线性规划问题及其数学模型

第二章 线性规划的对偶理论与灵敏度分析习题

1. 写出下列线性规划问题的对偶问题。

(1)⎪⎪⎩⎪⎪

⎨

⎧≥=++≤++≥++++=无约束

3213213213213

21,0,5343

32243422min x x x x x x x x x x x x x x x z (2) ⎪⎪⎩⎪⎪

⎨

⎧≤≥≤++≥-+-=++++=0

,0,8374355

22365max 3213213213213

21x x x x x x x x x x x x x x x z 无约束

(3)⎪⎪

⎪⎪⎩

⎪⎪⎪

⎪⎨⎧==≥=====∑∑∑∑====)

,,1;,,1(0)

,,1(),,1(min 1

111n j m i x n j b x m i a x x c z ij m

i j ij n

j i ij m

i ij

n

j ij (4)⎪⎪⎪⎪⎩⎪⎪⎪⎪⎨⎧=≥++==<=<=∑∑∑===),,,,1(0),,2,1()

,,1(min 1

211111n n j x m m m i b x a m m i b x a x c z j n j i j ij n

j i j ij n

j j

j 无约束 2. 判断下列说法是否正确，为什么?

(1)如果线性规划的原问题存在可行解，则其对偶问题也一定存在可行解； (2)如果线性规划的对偶问题无可行解，则原问题也一定无可行解； ( 3)在互为对偶的一对原问题与对偶问题中，不管原问题是求极大或极小，原问题可行解的目标函数值一定不超过其对偶问题可行解的目标函数值；

(4)任何线性规划问题具有唯一的对偶问题。

3. 已知某求极大化线性规划问题用单纯形法求解时的初始单纯形表及最终单纯形表如下表所示，求表中各括弧内未知数的值。

⎪⎩⎪

⎨⎧=≥-≤+-+-≥++++++=)4,,1(0322326532min 432143214

321 j x x x x x x x x x x x x x z j

(1)写出其对偶问题；(2)用图解法求解对偶问题；(3)利用(2)的结果及根据对偶问题性质写出原问题最优解。

5. 给出线性规划问题

⎪⎪⎩⎪⎪

⎨

⎧≤≥≥++=+-≤-+++=无约束

321321321321321,0,0221222max x x x x x x x x x x x x x x x z (1)写出其对偶问题；(2)利用对偶问题性质证明原问题目标函数值z ≤1。

6. 已知线性规划问题

⎪⎩⎪⎨⎧≥≤-+-≤++-+=0,,122

max 3

213213212

1x x x x x x x x x x x z

试根据对偶问题性质证明上述线性规划问题目标函数值无界。 7. 给出线性规划问题

⎪⎪⎪⎩⎪

⎪⎪

⎨⎧=≥≤++≤++≤+≤+++++=)

4,,1(09

6628342max 3

21432214214321 j x x x x x x x x x x x x x x x x z j

要求：（1）写出其对偶问题；（2）已知原问题最优解为X *

=(2,2,4,0)，试根据对

偶理论，直接求出对偶问题的最优解。

8. 已知线性规划问题A 和B 如下：

问题A 问题B

()

⎪

⎪⎪⎪⎩⎪⎪⎪⎪⎨⎧=≥≤≤≤=∑∑∑∑====n j x y b x a y b x a y b x a x c z j n

j j j n

j j j n

j j j n

j j

j ,,10max 3133212

21

1111 对偶变量

()

⎪

⎪⎪⎪⎩⎪⎪⎪⎪⎨⎧=≥+≤+≤≤=∑∑∑∑====n j x y b b x a a y b x a y b x a x c z j n

j j j j n j j j n

j j j n

j j

j ,,10ˆ3)3(ˆ51

51ˆ55max 311313212

211

1

11

对偶变量

试分别写出i y

ˆ同)3,2,1(=i y i 间的关系式。 9. 用对偶单纯形法求解下列线性规划问题。

（1）⎪⎩⎪

⎨⎧=≥≥+≥+++=)3,2,1(05

223318124min 32213

21j x x x x x x x x z j

（2）⎪⎩⎪

⎨⎧=≥≥++≥++++=)3,2,1(010*********min 3214213

21j x x x x x x x x x x z j

10. 考虑如下线性规划问题：

⎪⎪⎩

⎪⎪⎨

⎧=≥≥++≥++≥++++=)3,2,1(03222434223804060min 321321321321j x x x x x x x x x x x x x z j

要求：(1)写出其对偶问题；(2)用对偶单纯形法求解原问题；(3)用单纯形法求解其对偶问题；(4)对比(2)与(3)中每步计算得到的结果。

11. 已知线性规划问题：

⎪⎩⎪

⎨⎧=≥≤+-≤+++-=)3,2,1(0426

2max 2

2321321j x x x x x x x x x z j

先用单纯形法求出最优解，再分析在下列条件单独变化的情况下最优解的变化。

(1)目标函数变为max z ＝2x 1+3x 2+x 3；

(2)约束右端项由⎪⎪⎭⎫ ⎝⎛46变为⎪⎪⎭

⎫

⎝⎛43。

(3)增添一个新的约束条件-x 1+2x 3≥2。

12. 给出线性规划问题

⎪⎪⎪

⎩

⎪⎪

⎪⎨⎧=≥≤++≤++++=)3,2,1(03373431

131313132max 221321321j x x x x x x x x x x z j 用单纯形法求解得最终单纯形表见下表。

(1)目标函数中变量x 3的系数变为6；

(2)分别确定目标函数中变量x l 和x 2的系数c 1、c 2在什么范围内变动时最优解不 变；

（3）约束条件右端项由⎪⎪⎭⎫

⎝⎛31变为⎪⎪⎭

⎫ ⎝⎛32；

（4）增加一个新的变量7,11,666=⎪⎪⎭

⎫

⎝⎛=c P x ；