第二章对偶理论与灵敏度分析
第一节线性规划的对偶问题
例：某公司计划生产甲、乙两种产品，已知各生产一件时
分别占用的设备A、B的台时、调试时间和调试工序每天可用于
这两种产品的能力、各销售一件时的获利情况，如下表所示。
问该公司应生产两种产品各多少件，使获取的利润为最大。
甲乙每天可用能力
设备A(h)
设备B(h)
调试工序(h)0
6
15
2
115
24
5
利润（元）21每一个线性规划问题都存在一个与其对偶的问题，在求出
一个问题的解的时候，同时也给出了另一问题的解。
设和分别表示该公司生产甲乙两种产品的数量
1x
2x
212maxxxz
0,52426155
2121212
xxxxxxx目标函数
约束条件(LP1)设y
1, y
2 和y
3 代表单位时间设备A、设备B和调试工序
的出让代价。
因为该公司用6小时设备B和1小时调试可以生产甲产品一
件，盈利2元；用5小时设备A，2小时设备B和1小时调试可生
产乙产品一件，盈利1元。由此y
1, y
2 和y
3 的取值应该满足
26
32yy
125
321yyy
32152415minyyyw
012526
3132132
yyyyyy(LP2)
注：通常称LP1 为原问题，LP2 为对偶问题。定义：满足下列条件的线性规划问题称为具有对称形式：
其变量均具有非负约束，其约束条件当目标函数求极大时均取
小于等于号，当目标函数求极小时均取大于等于号。
nnxcxcxcz
2211max
0,,
122112222212111212111
nmnmnmmnnnn
xxbxaxaxabxaxaxabxaxaxa
对称形式下线性规划原问题的一般形式为：
CXzmax
0XbAX矩阵表达形式：
用y
i ( i=1, ···, m ) 代表第i 种资源的估价，则其对偶问题
的一般形式为：
第2章 对偶问题
判断下列说法是否正确：
对偶问题的对偶问题一定是原问题；
根据对偶问题的性质，当原问题为无界解时，其对偶问题无可行解，反之，当对偶问题无可行解时，其原问题具有无界解；
已知*iy为线性规划的对偶问题的最优解，若*iy>0，说明在最优生产计划中的i种资源已完全耗尽；
已知*iy为线性规划的对偶问题的最优解，若*iy＝0，说明在最优生产计划中第i种资源一定有剩余；
若某种资源的影子价格等于k，在其它条件不变的情况下，当改种资源增加5个单位时，相应的目标函数值将增大5k；
在线性规划问题的最优解中，如某一变量jx为非基变量，则在原来问题中，无论改变它在目标函数中的系数jc或在各约束中的相应系数ija，反映到最终单纯形表中，除该列数字有变化外，将不会引起其它列数字的变化。
简答题
、试述对偶单纯形法的优点及其应用上的局限性。
、试述对偶单纯形法的步骤。
、试解释对偶解的经济含义和影子价格在市场决策中的作用。
、什么是资源的影子价格？同相应的市场价格之间有何区别？以及研究影子价格的意义是什么？
:判断下列说法是否正确，为什么？
（a）如果线性规划的原问题存在可行解，则其对偶问题也一定存在可行解；
（b）如果线性规划的对偶问题存在可行解，则其原问题也一定无可行解；
（c）在互为对偶的一对原问题和对偶问题中，不管原问题是求极大或极小，原问题可行解的目标函数都一定不超过其对偶问题可行解的目标函数。
若某种资源的影子价格等于k，在其他条件不变的情况下，当该种资源增加5个单位时，相应的目标函数最大值将增加5k吗？
已知*iy为某线性规划问题的对偶问题最优解中的第i分量，若*iy＝0，能否肯定在最优生产计划种第i种资源一定有剩余？
写出对偶问题
写出下列线性规划问题的对偶问题
123max102Zxxx 123123123210420,,0xxxxxxxxx
第2章 对偶问题
3.3 （1）12min1020Wyy （2）123min54Wyyy
12121212410122,0yyyyyyyy
12312123131322213310,0,yyyyyyyyyyyyy无约束
（3）123max352Wyyy （4）123max15205Wyyy
1212312312312323232337344440,0,yyyyyyyyyyyyyy无约束 1231231231235556631070,0,yyyyyyyyyyyy无约束
（5）123min235Wyyy （6）123min1264Wyyy
12312123123232315765,,0yyyyyyyyyyy 12312123123212157610,,y0yyyyyyyyyy无约束
（7）123maxW642yyy
1231212312324225730,,0yyyyyyyyyyy无约束
3.4 （1）最优解为*2110(,)1313TX，最优值为*31min13Z；
（2）最优解为*(1.5,0.125,0)TX，最优值为*min14Z；
3.5 原问题的最优解为*(0,20,0,0,10)TX，最优值为*max100Z；
（1）线性规划问题发生了变化，其最优解为*(0,0,9,3,0)TX，最优值为*max117Z；
对偶问题习题
● 证明题(选做)
1． 证明下面的线性规划问题要么无解，要么最优目标函数值为零，其中C为n维向量，b为m维向量，A为mn矩阵。
min..0,0ybcxAxbstyAcxy
证明 把问题拆成两个问题
(A) max..0zcxAxbstx 和 (B) min..0wybyAcsty
显然两个问题为原问题和对偶问题，分四种情形讨论：
情形1 如果两个问题都有可行解，那么两个问题都有最优解，且最优目标函数值相等。根据对偶理论，由于有cxyb，因此0ybcx。而**ybcx=0，因而该情形下有解，且最优解为0。
情形2 如果问题A有解但为无穷解，那么B问题一定无解，也就是yAc不成立，从而该情形下无解。
情形3 如果问题B有解但为无穷解，那么A问题一定无解，也就是Axb不成立，从而该情形下无解。
情形4 如果问题A和问题B均无解，那么Axb和yAc都不成立，从而该情形下也无解。
综合上述，根据对偶理论只可能有如上情形，从而命题成立。
2． 设线性规划问题1是
11max..0(1)njjjnijjijjzcxaxbstxjn
其中***12(,,,)myyy是其对偶问题的最优解。
又设线性规划问题2是 11max..0(1)njjjnijjiijjzcxaxbkstxjn
其中ik是给定的常数，求证
*211max()max()miiizzky
证明 问题1的对偶问题为
11221min...,1,2,...,..0mmmijijiiwbybybyaycjnsty
