发布时间 : 星期日 文章线性规划问题及其数学模型更新完毕开始阅读
第二章 线性规划的对偶理论与灵敏度分析习题
1. 写出下列线性规划问题的对偶问题。
minz?2x1?2x2?4x3?x1?3x2?4x3?2? (1)?2x1?x2?3x3?3??x1?4x2?3x3?5??x1,x2?0,x3无约束minz???cijxiji?1j?1mnmaxz?5x1?6x2?3x3?x1?2x2?2x3?5? (2) ??x1?5x2?x3?3
??4x1?7x2?3x3?8??x1无约束,x2?0,x3?0minz??cjxjj?1n?n?naijxj?bi(i?1,?,m1?m)(3)??xij?ai(i?1,?,m) (4)?? j?1j?1?????n?m??aijxj?bi(i?m1?1,m2?2,?,m)??xij?bj(j?1,?,n)?j?1?i?1?x?0无约束(j?1,?,n,?,n)?xij?0(i?1,?,m;j?1,?,n)1?j?????2. 判断下列说法是否正确，为什么?
(1)如果线性规划的原问题存在可行解，则其对偶问题也一定存在可行解； (2)如果线性规划的对偶问题无可行解，则原问题也一定无可行解； ( 3)在互为对偶的一对原问题与对偶问题中，不管原问题是求极大或极小，原问题可行解的目标函数值一定不超过其对偶问题可行解的目标函数值；
(4)任何线性规划问题具有唯一的对偶问题。
3. 已知某求极大化线性规划问题用单纯形法求解时的初始单纯形表及最终单纯形表如下表所示，求表中各括弧内未知数的值。
CB 0 2 1 基 x4 x5 x6 B (b) 15 20 3 x1 1 (a) 2 0 2 x2 1 1 (c) 0 2 x3 1 2 1 2 0 x4 1 0 0 0 0 x5 0 1 0 0 0 x6 0 0 1 0 1
cj?zj
? 0 3 2 x4 x1 x2 5/4 25/4 5/2 0 1 0 -1 0 0 1 (k) (d) (e) (f) (g) ? (l) 0 0 0 -1/4 3/4 (h) -5/4 -1/4 (i) 1/2 (j) cj?zj 4. 给出线性规划问题 minz?2x1?3x2?5x3?6x4?x1?2x2?3x3?x4?2 ???2x1?x2?x3?x4??3?x?0(j?1,?,4)?j
(1)写出其对偶问题；(2)用图解法求解对偶问题；(3)利用(2)的结果及根据对偶问题性质写出原问题最优解。
5. 给出线性规划问题
maxz?x1?2x2?x3?x1?2x2?x3?2? ?x1?x2?x3?1 ??2x1?x2?x3?2??x1?0,x2?0,x3无约束(1)写出其对偶问题；(2)利用对偶问题性质证明原问题目标函数值z≤1。
6. 已知线性规划问题
maxz?x1?x2??x1?x2?x3?2 ?
?2x?x?x?1?123?x,x,x?0?123试根据对偶问题性质证明上述线性规划问题目标函数值无界。 7. 给出线性规划问题
2
maxz?2x1?4x2?x3?x4?x1?3x2?x4?8??2x1?x2?6??x2?x3?x4?6?x?x?x?923?1??xj?0(j?1,?,4)
要求：（1）写出其对偶问题；（2）已知原问题最优解为X=(2,2,4,0)，试根据对
偶理论，直接求出对偶问题的最优解。
8. 已知线性规划问题A和B如下：
问题A 问题B
maxz??cjxjj?1n*
对偶变量maxz??cjxjj?1n对偶变量?ny1??a1jxj?b1j?1??ny2??a2jxj?b2?j?1?n??a3jxj?b3y3?j?1??xj?0?j?1,?,n??n?1y??5a1jxj?5b1 ?j?1?n11?2ax?b2y??2jj55j?1??n??(a3j?3a1j)xj?b3?3b1y?3?j?1??xj?0?j?1,?,n?
?i同yi(i?1,2,3)间的关系式。 试分别写出y9. 用对偶单纯形法求解下列线性规划问题。
minz?4x1?12x2?18x3（1）?minz?5x1?2x2?4x3 （2）??x1?3x2?3?2x2?2x3?5?x?0(j?1,2,3)?j?3x1?x2?2x4?4?6x1?3x2?5x3?10?x?0(j?1,2,3)?j
10. 考虑如下线性规划问题：
minz?60x1?40x2?80x3?3x1?2x2?x3?2?4x?x?3x?4?123??2x1?2x2?2x3?3?xj?0(j?1,2,3)?
要求：(1)写出其对偶问题；(2)用对偶单纯形法求解原问题；(3)用单纯形法求解其对偶问题；(4)对比(2)与(3)中每步计算得到的结果。
3
11. 已知线性规划问题：
maxz?2x1?x2?x3?x1?x2?x3?6 ???x2?2x2?4?x?0(j?1,2,3)?j先用单纯形法求出最优解，再分析在下列条件单独变化的情况下最优解的变化。
(1)目标函数变为max z＝2x1+3x2+x3；
?6??3?(2)约束右端项由??4??变为??4??。
????(3)增添一个新的约束条件-x1+2x3≥2。
12. 给出线性规划问题
maxz?2x1?3x2?x311?1x?x??31323x3?1? 47?1?x1?x2?x2?333?3?xj?0(j?1,2,3)??用单纯形法求解得最终单纯形表见下表。
CB 2 3 基 x1 x2 B 1 2 2 x1 1 0 0 3 x2 0 1 0 1 x3 -1 2 -3 0 x4 4 -1 -5 0 x5 -1 1 -1 cj?zj 试分析下列各种条件下最优解(基)的变化： (1)目标函数中变量x3的系数变为6；
(2)分别确定目标函数中变量xl和x2的系数c1、c2在什么范围内变动时最优解不 变；
（3）约束条件右端项由????变为????；
?1??3??2??3??1?（4）增加一个新的变量x6,P6???1??,c6?7 ；
??
4