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

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

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

(5)增添一个新的约束x1+2x2+x3≤4。

13. 分析下列线性规划问题中，当且变化时最优解的变化，并画出z(λ)对λ的变化关系图。

?1?minz?x1?x2??x3?2?x4??x1?x3?2x4?2??2x1?x2?3x4?5?x?0?j?1,?4??j??2?maxz??????3???x1??2???x2?2x1?5x2?10?6x?x?12?12??x1?x2?1??xj?0?j?1,2?

?3?minz????x1?x2?2x3?x4??x1?2x3?x4?2????x2?x3?x4??1???x?0?j?1,?4??j??4?maxz????3x1?2x2?5x3?x1?2x2?x3?40???3x?2x?60?2??13??x1?4x2?30?7???xj?0?j?1,2,3?

14. 某厂生产A，B，C三种产品，其所需劳动力、材料等有关数据见下表。要

求：(1)确定获利最大的产品生产计划；(2)产品A的利润在什么范围内变动时，上述最优计划不变；(3)如果设计一种新产品D，单件劳动力消耗为8单位，材料消耗为2单位，每件可获利3元，问该种产品是否值得生产?(4)如果劳动力数量不增，材料不足时可从市场购买，每单位0.4元。问该厂要不要购进原材料扩大生产，以购多少为宜。 劳动力 材料 产品利润（元/件） A 6 3 3 B 3 4 1 C 5 5 4 可用量 45 30

15.已知线性规划问题

maxz?(c1?t1)x1?c2x2?c3x3?0x4?0x5?a11x1?a12x2?a13x3?x4?b1?3t2??a21x1?a22x2?a23x3?x5?b2?t2?x?0(j?1,...,5)?j

当t1?t2?0时求得解最终单纯形表进见下表。

5

项目 x1 0 1 0 x2 0.5 -0.5 -4 x3 1 0 0 x4 0.5 -1/6 -4 x5 0 1/3 -2 x3 5/2 x1 5/2 cj?zj （1）确定c1,c2,c3,a11,a12,a13,a21,a22,a23和b1,b2的值； （2） 当t2?0时，t1在什么范围内变化上述最优解不变； （3）当t1?0时，t2在什么范围内变化上述最优基不变；

16．某文教用品厂利用原材料白坯纸生产原稿纸、日记本和练习本三种产品。该厂有工人100人，每天白坯纸的供应量为30000kg。如单独生产各种产品时，每个工人每天可生产原稿纸30捆，或日记纸30打，或练习本30箱。已知原材料消耗为：每捆原稿纸用白坯纸311kg, 每打日记本用白坯纸13kg, 每箱练习本用白坯纸 33226kg。 已知生产各种产品的赢利为：每捆原稿纸1元，每打日记本2元，每箱练3习本3元。试决定：（1）在现有生产条件下使该厂赢利最大的方案；（2）如白坯纸供应量不变，而工人数量不足时可从市场上招收临时工，临时工费用为每人每天15元。问该厂应否招临时工及招收多少人为宜。

6

项目 x1 0 1 0 x2 0.5 -0.5 -4 x3 1 0 0 x4 0.5 -1/6 -4 x5 0 1/3 -2 x3 5/2 x1 5/2 cj?zj （1）确定c1,c2,c3,a11,a12,a13,a21,a22,a23和b1,b2的值； （2） 当t2?0时，t1在什么范围内变化上述最优解不变； （3）当t1?0时，t2在什么范围内变化上述最优基不变；

16．某文教用品厂利用原材料白坯纸生产原稿纸、日记本和练习本三种产品。该厂有工人100人，每天白坯纸的供应量为30000kg。如单独生产各种产品时，每个工人每天可生产原稿纸30捆，或日记纸30打，或练习本30箱。已知原材料消耗为：每捆原稿纸用白坯纸311kg, 每打日记本用白坯纸13kg, 每箱练习本用白坯纸 33226kg。 已知生产各种产品的赢利为：每捆原稿纸1元，每打日记本2元，每箱练3习本3元。试决定：（1）在现有生产条件下使该厂赢利最大的方案；（2）如白坯纸供应量不变，而工人数量不足时可从市场上招收临时工，临时工费用为每人每天15元。问该厂应否招临时工及招收多少人为宜。

6

本文来源：https://www.bwwdw.com/article/fesp.html