www.100xuexi.com 圣才电子书 十万种考研考证电子书、题库视频学习平台
第2章 对偶理论与灵敏度分析
2.1 复习笔记
1．单纯形法的矩阵描述
设线性规划问题为max z?CX;AX?b;X?0。在该线性规划问题的约束条件中加入松弛变量XS后，得到标准型：max z?CX?0XS;AX?IXS?b;X,XS?0。该标准型的矩阵表示为：
目标函数：max z?CBXB?CNXN?CBXB?CN1XN1?CS2XS2 约束条件：BXB?NXN?BXB?N1XN1?S2XS2?b 非负条件：XB,XN?0
其中B，N，S分别表示对应基变量、非基变量、松弛变量的系数矩阵。 进一步分析可得到：
基可行解：XB?Bb?BN1XN1?BS2XS2
目标函数：z?CBB?1b?CN1?CBB?1N1XN1?CS2?CBB?1IXS
注意：重点要搞清楚哪些是行向量，哪些是列向量，XB,XN为列向量，CB,CN为行向量。
2．单纯形表与矩阵表示的关系
上述基可行解、目标函数的表达式可改写为：
1 / 48
?1?1?1???? www.100xuexi.com 圣才电子书 十万种考研考证电子书、题库视频学习平台 XB?B?1N1XN1?B?1XS2?B?1b?z??CN1?CBB?1N1?XN1?CBB?1XS2??CBB?1b
再将以上两式用矩阵关系式表示为：
该分块矩阵也可以列表表示为：
3．原问题与对偶问题之间的关系 原问题
max z?c1x1?c2x2?…?cnxn ?x1?a a a?1112?b1?1n???? ??x2?????????? ??bm???am1 am2 amn???x???n?x1,x2,…,xn?0
对偶问题
min ??y1b1?y2b2?…?ymbm
?y1,y2,?a11 a12 a1n???c,c,,ym?? ???12??am1 am2 amn??,cn?
y1,y2,…,ym?0
线性规划的原问题与对偶问题的关系，其变换形式可归纳如下：
表2-1
2 / 48
www.100xuexi.com 圣才电子书 十万种考研考证电子书、题库视频学习平台 记忆方法：
极大化转化为极小化，变不反约反；极小化转化为极大化，变反约不反。
注：变指变量，约指约束条件。反指大于变小于，小于变大于。不反指大于变大于，小于变小于。注意等号总是变无约束，无约束总是变等号。
4．对偶问题的基本性质
（1）对称性：对偶问题的对偶是原问题。
（2）弱对偶性：若X是原问题的可行解，Y是对偶问题的可行解。则存在CX?Yb。 注意，由弱对偶性可以推出：
①max问题任一可行解的目标值为对偶min问题目标值的一个下界； ②min问题任一可行解的目标值为对偶max问题目标值的一个上界。
（3）无界性：若原问题（对偶问题）为无界解，则其对偶问题（原问题）无可行解。 注：这个问题的性质不存在逆。当原问题（对偶问题）无可行解时，其对偶问题（原问题）或具有无界解或无可行解。
（4）可行解是最优解时的性质：设X是原问题的可行解，Y是对偶问题的可行解，当
CX?Yb，X,Y是最优解。
3 / 48
www.100xuexi.com 圣才电子书 十万种考研考证电子书、题库视频学习平台 （5）对偶定理：若原问题有最优解，那么对偶问题也有最优解；且目标函数值相等。 要记住一点：原问题、对偶问题均存在可行解，则存在最优解。
（6）互补松弛性：若X,Y分别是原问题和对偶问题的可行解。那么YXS?0和
YSX?0，当且仅当X,Y为最优解。
（7）设原问题是max z?CX;AX?XS?b;X,XS?0，它对应的对偶问题是
max ??Yb；YA?YS?C;Y,YS?0，则原问题单纯形表的检验数行对应其对偶问题的一
个基解。
记忆方法：
①原问题非最，优检验数的负值为对偶问题的一个基解。 ②原问题最优，检验数的负值为对偶问题的最优解。
③原问题检验数行，其松弛变量的检验数的绝对值对应其对偶问题的各个变量的解。
5．对偶问题的经济解释——影子价格 （1）影子价格的定义
设B是max z=CXAX?b,X?0的最优基，则z?CBBb?Yb 由此
??*?1*?z*?CBB?1?Y* ?b变量yi的经济意义是在其他条件不变的情况下，单位资源变化所引起的目标函数的最优值的变化。yi的值代表对第i种资源的估价。这种估价是针对具体工厂的具体产品而存在的一种特殊价格，称它为“影子价格”。
（2）影子价格的经济意义
** 4 / 48
www.100xuexi.com 圣才电子书 十万种考研考证电子书、题库视频学习平台 影子价格随具体情况而异，在完全市场经济的条件下，当某种资源的市场价低于影子价格时，企业应买进该资源用于扩大生产；而当某种资源的市场价高于该企业影子价格时，则企业的决策者应把已有资源卖掉。可见影子价格对市场有调节作用。
要记住：市场价格低于影子价格，可以买进（然后用灵敏度分析进行计算），若市场价格高于影子价格，不买进。
6．对偶单纯形法
对偶单纯形法的思想：在单纯形表中进行迭代时，在b列中得到的是原问题的基可行解，而在检验数行得到的是对偶问题的基解。通过逐步迭代，当在检验数行得到对偶问题的解也是基可行解时，此时已得到最优解。根据对偶问题的对称性，也可以这样考虑：若保持对偶问题的解是基可行解，即cj?CBBPj?0，而原问题在非可行解的基础上，通过逐步迭代达到基可行解，这样也得到了最优解。
对偶单纯形法的计算步骤如下：
（1）根据线性规划问题，列出初始单纯形表。检查b列的数字，若都为非负，检验数都为非正，则已得到最优解，停止计算。若检查b列的数字时，至少还有一个负分量，检验数保持非正，则转入下一步。
（2）确定换出变量 按min?1??B?1b??B?1b??0??B?1b?对应的基变量xl为换出变量。
iil?（3）确定换入变量
在单纯形表中检查xl所在行的各系数alj?j?1,2,…,n?。若所有alj?0，则无可行解，停止计算。若存在在alj?0?j?1,2,…,n?，计算
5 / 48
《运筹学》教材编写组《运筹学》笔记和课后习题(含考研真题)详解(对偶理论与灵敏度分析)
