灵敏度分析与对偶理论

第二章 对偶理论与灵敏度分析练习题答案

1．判断下列说法是否正确：

(1) 任何线性规划问题存在并具有惟一的对偶问题；()

(2) 根据对偶问题的性质，当原问题为无界解时，其对偶问题无可行解，反之，当对偶问题无可行解时，其原问题具有无界解；()

(3) 设jˆx，iˆy分别为标准形式的原问题与对偶问题的可行解，*jx，*iy分别为其最优解，则恒有nnmm**jjjjiiiij1j1i1i1ˆˆcxcxbyby；()

(4) 若线性规划的原问题有无穷多最优解，则其对偶问题也一定具有无穷多最优解；()

(5) 已知*iy为线性规划的对偶问题的最优解，若*iy0，说明在最优生产计划中第i种资源已完全耗尽；()

(6) 已知*iy为线性规划的对偶问题的最优解，若*iy0，说明在最优生产计划中第i种资源一定有剩余；()

(7) 若某种资源的影子价格等于k，在其他条件不变的情况下，当该种资源增加5个单位时，相应的目标函数值将增大5k；()

(8) 应用对偶单纯形法计算时，若单纯形表中某一基变量ix0，又xi所在行的元素全部大于或等于零，则可以判断其对偶问题具有无界解；()

(9) 若线性规划问题中的bi，cj值同时发生变化，反映到最终单纯形表中，不会出现原问题与对偶问题均为非可行解的情况；()

(10) 在线性规划问题的最优解中，如某一变量xj为非基变量，则在原来问题中，无论改变它在目标函数中的系数cj或在各约束中的相应系数aij，反映到最终单纯形表中，除该列数字有变化外，将不会引起其他列数字的变化。()

2．下表是某一约束条件用“≤”连接的线性规划问题最优单纯形表格，其中x4、x5为松弛变量。

XB ｂ x1 x2 x3 x4 x5

x3 5/2 0 1/2 1 1/2 0

x1 5/2 1 -1/2 0 -1/6 1/3

σj 0 -4 0 -4 -2

要求：(1)写出原线性规划问题及其对偶问题的数学模型；(2)直接由表写出对偶问题的最优解；

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

一、学习目的与要求

1、掌握对偶理论及其性质

2、掌握对偶单纯形法

3、熟悉灵敏度分析的概念和内容

4、掌握限制常数与价值系数、约束条件系数的变化对原最优解的影响

5、掌握增加新变量和增加新的约束条件对原最优解的影响，并求出相应因素的灵敏度范围

6、了解参数线性规划的解法

二、课时 6学时

第一节 线性规划的对偶问题

一、对偶问题的提出

定义：一个线性规划问题常伴随着与之配对的、两者有密切联系的另一个线性规划问题，我们将其中一个称为原问题，另一个就称为对偶问题，在求出一个问题的解时，也同时给出了另一问题的解。

应用：在某些情况下，解对偶问题比解原问题更加容易；对偶变量有重要的经济解释(影子价格)；作为灵敏度分析的工具；对偶单纯形法(从一个非可行基出发，得到线性规划问题的最优解)；避免使用人工变量(人工变量带来很多麻烦，两阶段法则增加一倍的计算量)。

例：某家具厂木器车间生产木门与木窗；两种产品。加工木门收入为56元/扇，加工木窗收入为30元/扇。生产一扇木门需要木工4小时，油漆工2小时；生产一扇木窗需要木工3小时，油漆工1小时；该车间每日可用木工总共时为120小时，油漆工总工时为50小时。

问：(1)该车间应如何安排生产才能使每日收入最大？

(2)假若有一个个体经营者，手中有一批木器家具生产订单。他想利用该木器车间的木工与油漆工来加工完成他的订单。他就要考虑付给该车间每个工时的价格。他可以构造一个数学模型来研究如何定价才能既使木器车间觉得有利可图而愿意为他加工这批订单、又使自己所付的工时费用最少。

解(1)：设该车间每日安排生产木门x1扇，木窗x2扇，则数学模型为

0502120343056max21212121xxxxxxxz 2 X*=(15,20)’ Z*=1440元

解(2)：设y1为付给木工每个工时的价格，y2为付给油工每个工时的价格

第二章.对偶理论与灵敏度分析

1. 已知线性规划问题：

332211maxxcxcxcz























































)5,,1(010

01

.

21

543

2313

2

2212

1

2111

jxbb

xxx

aa

x

aa

x

aa

st

j

用单纯形法求解得最终单纯形表如下表所示：

（a） 求232221131211,,,,,aaaaaa和21,bb （b） 求321,,ccc

1x 2x 3x 4x 5x

3x 3/2

2x 2 1

1/2 0

1 1

0 1/2

－1 -1/2

2

jjzc -3 0 0 0 -4

答：

8,4,7,5,8,2,4,1,1,2/5,2/9

32121231322122111cccbbaaaaaa

2. 已知矩阵A及其逆矩阵1A如下：











104020012

A













11202/1004/12/1

1A

试根据改进单纯形法中求逆矩阵的方法原理求下述矩阵B的逆矩阵1B，已知











144210152

B

答：先设









144010052

C

 



















72/14/11

415

1A

 



















16201002/52/1

114002002/111

11AC











144210152

B

有 



















1322/11

121

1C

 





















26/226/1226/426/426/226/826/1126/126/9

13/10013/21026/1101

11CB

3. 已知线性规划的原问题与对偶问题分别为：

（P）原问题：CXzmax (D)对偶问题：Ybwmin

第二章 对偶理论与灵敏度分析练习题答案

1．判断下列说法是否正确：

(1) 任何线性规划问题存在并具有惟一的对偶问题；(?)

(2) 根据对偶问题的性质，当原问题为无界解时，其对偶问题无可行解，反之，当对偶问题无可行解时，其原问题具有无界解；(?)

(3) 设jˆx，iˆy分别为标准形式的原问题与对偶问题的可行解，*jx，*iy分别为其最优解，则恒有nnmm**jjjjiiiij1j1i1i1ˆˆcxcxbyby；(?)

(4) 若线性规划的原问题有无穷多最优解，则其对偶问题也一定具有无穷多最优解；(?)

(5) 已知*iy为线性规划的对偶问题的最优解，若*iy0，说明在最优生产计划中第i种资源已完全耗尽；(?)

(6) 已知*iy为线性规划的对偶问题的最优解，若*iy0，说明在最优生产计划中第i种资源一定有剩余；(?)

(7) 若某种资源的影子价格等于k，在其他条件不变的情况下，当该种资源增加5个单位时，相应的目标函数值将增大5k；(?)

(8) 应用对偶单纯形法计算时，若单纯形表中某一基变量ix0，又xi所在行的元素全部大于或等于零，则可以判断其对偶问题具有无界解；(?)

(9) 若线性规划问题中的bi，cj值同时发生变化，反映到最终单纯形表中，不会出现原问题与对偶问题均为非可行解的情况；(?)

(10) 在线性规划问题的最优解中，如某一变量xj为非基变量，则在原来问题中，无论改变它在目标函数中的系数cj或在各约束中的相应系数aij，反映到最终单纯形表中，除该列数字有变化外，将不会引起其他列数字的变化。(?)

2．下表是某一约束条件用“≤”连接的线性规划问题最优单纯形表格，其中x4、x5为松弛变量。

XB ｂ x1 x2 x3 x4 x5

x3 5/2 0 1/2 1 1/2 0

x1 5/2 1 -1/2 0 -1/6 1/3

σj 0 -4 0 -4 -2

要求：(1)写出原线性规划问题及其对偶问题的数学模型；(2)直接由表写出对偶问题的最优解； (3)其它条件不变时，约束条件右端项b1在何范围内变化，上述最优基不变。(4)若以单价购入第一种资源是否值得，为什么若有人愿意购买第二种资源应要价多少，为什么 答案：