1 第二章线性规划的对偶理论与灵敏度分析习题 1. 写出下列线性规划问题的对偶问题。 (1)无约束321321321321321,0,534332243422minxxxxxxxxxxxxxxxz (2) 0,0,837435522365max321321321321321xxxxxxxxxxxxxxxz无约束(3), 1;, 1(0), 1(), 1(min1111njmixnjbxmiaxxczijmijijnjiijmiijnjij (4), 1(0),2, 1(),1(min1211111nnjxmmmibxammibxaxczjnjijijnjijijnjjj无约束2. 判断下列说法是否正确，为什么? (1) 如果线性规划的原问题存在可行解，则其对偶问题也一定存在可行解；(2) 如果线性规划的对偶问题无可行解，则原问题也一定无可行解；( 3) 在互为对偶的一对原问题与对偶问题中，不管原问题是求极大或极小，原问题可行解的目标函数值一定不超过其对偶问题可行解的目标函数值；(4) 任何线性规划问题具有唯一的对偶问题。3. 已知某求极大化线性规划问题用单纯形法求解时的初始单纯形表及最终单纯形表如下表所示，求表中各括弧内未知数的值。3 2 2 0 0 0 CB基B x1x2x3x4x5x60 x4(b) 1 1 1 1 0 0 2 x515 (a) 1 2 0 1 0 1 x620 2 (c) 1 0 0 1 jjzc0 0 2 0 0 0 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 1 页，共 6 页2 0 x45/4 0 0 (d) (l) -1/4 -1/4 3 x125/4 1 0 (e) 0 3/4 (i) 2 x25/2 0 1 (f) 0 (h) 1/2 jjzc-1 (k) (g) 0 -5/4 (j) 4. 给出线性规划问题) 4, 1(0322326532min432143214321jxxxxxxxxxxxxxzj (1) 写出其对偶问题；(2) 用图解法求解对偶问题；(3) 利用 (2) 的结果及根据对偶问题性质写出原问题最优解。5. 给出线性规划问题无约束321321321321321, 0,0221222maxxxxxxxxxxxxxxxxz(1) 写出其对偶问题；(2) 利用对偶问题性质证明原问题目标函数值z 1。 6. 已知线性规划问题0,122max32132132121xxxxxxxxxxxz试根据对偶问题性质证明上述线性规划问题目标函数值无界。 7. 给出线性规划问题精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 2 页，共 6 页3 )4,1(096628342max321432214214321jxxxxxxxxxxxxxxxxzj要求： （1）写出其对偶问题； （2）已知原问题最优解为X*=(2,2,4,0)，试根据对偶理论，直接求出对偶问题的最优解。8. 已知线性规划问题A和 B如下：问题 A问题 B njxybxaybxaybxaxczjnjjjnjjjnjjjnjjj, 10max3133212211111对偶变量njxybbxaaybxaybxaxczjnjjjjnjjjnjjjnjjj, 10?3)3(?5151?55max311313212211111对偶变量试分别写出iy ?同)3 ,2, 1(iyi间的关系式。9. 用对偶单纯形法求解下列线性规划问题。（1）)3, 2, 1(05223318124min3221321jxxxxxxxxzj（2）)3 ,2, 1(010536423425min321421321jxxxxxxxxxxzj10. 考虑如下线性规划问题：)3,2, 1(03222434223804060min321321321321jxxxxxxxxxxxxxzj要求： (1) 写出其对偶问题；(2) 用对偶单纯形法求解原问题；(3) 用单纯形法求解其对偶问题；(4) 对比 (2) 与(3) 中每步计算得到的结果。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 3 页，共 6 页4 11. 已知线性规划问题：)3, 2 , 1(04262max22321321jxxxxxxxxxzj先用单纯形法求出最优解，再分析在下列条件单独变化的情况下最优解的变化。(1) 目标函数变为max z2x1+3x2+x3；(2) 约束右端项由46变为43。(3) 增添一个新的约束条件-x1+2x3 2。12. 给出线性规划问题)3, 2, 1(03373431131313132max221321321jxxxxxxxxxxzj用单纯形法求解得最终单纯形表见下表。2 3 1 0 0 CB基B x1x2x3x4x52 x11 1 0 -1 4 -1 3 x22 0 1 2 -1 1 jjzc0 0 -3 -5 -1 试分析下列各种条件下最优解( 基) 的变化： (1)目标函数中变量x3的系数变为6； (2)分别确定目标函数中变量xl和 x2的系数 c1、c2在什么范围内变动时最优解不变；（3）约束条件右端项由31变为32；（4）增加一个新的变量7,11,666cPx；精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 4 页，共 6 页5 (5) 增添一个新的约束x1+2x2+x3 4。13. 分析下列线性规划问题中，当且变化时最优解的变化，并画出z( ) 对 的变化关系图。2, 10112610524, 105322223max22min1212121421431214321jxxxxxxxjxxxxxxxxxzxxxxzjj3 , 2, 107304260234024, 10122523max42min321313214324313214321jxxxxxxxxjxxxxxxxxxxzxxxxzjj14. 某厂生产A， B ，C 三种产品，其所需劳动力、材料等有关数据见下表。要求： (1) 确定获利最大的产品生产计划；(2) 产品 A的利润在什么范围内变动时，上述最优计划不变； (3) 如果设计一种新产品D ，单件劳动力消耗为8 单位，材料消耗为2单位，每件可获利3 元，问该种产品是否值得生产?(4) 如果劳动力数量不增，材料不足时可从市场购买，每单位0.4 元。问该厂要不要购进原材料扩大生产，以购多少为宜。A B C 可用量劳动力6 3 5 45 材料3 4 5 30 产品利润（元 / 件）3 1 4 15.已知线性规划问题)5,.,1(0300)(max225323222121214313212111543322111jxtbxxaxaxatbxxaxaxaxxxcxcxtczj当021tt时求得解最终单纯形表进见下表。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 5 页，共 6 页6 项目1x2x3x4x5x3x 5/2 0 0.5 1 0.5 0 1x 5/2 1 -0.5 0 -1/6 1/3 jjzc0 -4 0 -4 -2 （1）确定232221131211321,aaaaaaccc和21,bb的值；（2） 当02t时，1t在什么范围内变化上述最优解不变；（3）当01t时，2t在什么范围内变化上述最优基不变； 16某文教用品厂利用原材料白坯纸生产原稿纸、日记本和练习本三种产品。该厂有工人 100 人，每天白坯纸的供应量为30000kg。如单独生产各种产品时，每个工人每天可生产原稿纸30 捆，或日记纸30 打，或练习本30 箱。已知原材料消耗为：每捆原稿纸用白坯纸313kg, 每打日记本用白坯纸3113kg, 每箱练习本用白坯纸3226kg。 已知生产各种产品的赢利为：每捆原稿纸1 元，每打日记本2 元，每箱练习本 3 元。试决定：（1）在现有生产条件下使该厂赢利最大的方案；（2）如白坯纸供应量不变， 而工人数量不足时可从市场上招收临时工，临时工费用为每人每天15 元。问该厂应否招临时工及招收多少人为宜。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 6 页，共 6 页