Chapter2对偶理论及灵敏度分析

1、2022-5-612022-5-622022-5-63返回本章目录2022-5-64在实际问题中，一个问题的优化往往可以从不同的两个角度提出问题。譬如，要求在有限资源条件下生产利润最大；或在一定生产能力条件下使资源消耗最少。所以，在线性规划中，对任一给定的求最大值问题，相应也存在一个求最小值的问题。且两者包括有相同的数据。若称前者为原问题，则后者便称为对偶问题；或称前者为对偶问题，而称后者为原问题。两者互为对偶，具有密切的关系。只要得到其中一个问题的解，也就能够得到另一个问题的解。因而，从中选一个问题求解就可以了。2022-5-65例1 美佳公司利用该公司资源生产两种家电产品的线性规划模型为：

2、0,524261552max) 1(212121221xxxxxxxxxzLP设y1，y2，y3分别表示设备A、B和调试工序单位时间的价格。则0,1252652415min)2(32132132321yyyyyyyyyyywLP0y1+6y2+y325y1+2y2+y31对生产产品的全部资源的定价。假如另一公司想收购美佳公司的资源，美佳公司出让自己资源的条件是什么？出让代价不低于用同等资源组织生产两种产品所能获得的利润。对生产产品的全部资源的定价。产品的利润产品的利润2022-5-66 原问题对偶问题x1x2原关系min wy10515y26224y3115对偶关系max z = min wm

3、ax z210,524261552max) 1(212121221xxxxxxxxxzLP0,1252652415min)2(32132132321yyyyyyyyyyywLP2022-5-67满足下列条件的线性规划问题称为具有对称形式：满足下列条件的线性规划问题称为具有对称形式：其变量均具有非负约束，其约束条件当目标函数求极大时取其变量均具有非负约束，其约束条件当目标函数求极大时取“”号，当目标函数求极小时均取号，当目标函数求极小时均取“”号。号。) 3 . 2(), 2 , 1(0max221122222121112121112211njxbxaxaxabxaxaxabxaxaxaxcxc

4、xczjmnmnmmnnnnnn则其对偶问题的则其对偶问题的一般形式为：一般形式为：)4 . 2(), 2 , 1(0min221122222112112211112211miycyayayacyayayacyayayaybybybwinmmnnnmmmmmm若原问题的一若原问题的一般形式为：般形式为：yi(i=1,2,，m)代表第代表第i种资源种资源的估价。的估价。2022-5-68原问题：)5 . 2(0maxXbAXCXz对偶问题：) 6 . 2(0minYCYAbYw0maxYCYAbYw0minXbAXCXz令ww对偶问题令zz2022-5-69考虑标准形式的线性规划：max z =

5、 CX AX = b X0max z = CX AX b AX b X0min w = bT (YY) AT (Y Y ) CT Y0， Y 0令令Y= YY min w = bT Y AT Y CT Y 为自由变量这就是非对称形式的对偶关系。在这种形式中，Y 不要求非负。max z = CX AX b AX b X0YYmin w = Yb AY C Y 为自由变量2022-5-610原问题（对偶问题） 对偶问题（原问题） （1）目标函数极大化 （1）目标函数极小化 （2）目标函数中的系数 （2）约束条件的右边常数 （3）约束条件的右边常数 （3）目标函数中的系数 （4）变量非负 （4）约束

6、条件为不等式 （5）自由变量 （5）约束条件为等式“=” （6）约束条件为不等式 （6）变量非负 （7）约束条件为等式“=” （7）自由变量 （ 在写对偶问题时，要特别注意上表中原问题与其对偶问在写对偶问题时，要特别注意上表中原问题与其对偶问题的对应关系。题的对应关系。2022-5-611：根据原问题数学模型的形式统一符号。若原问题目标函数，则将其约束条件统一成的形式；若原问题目标函数为，则将其约束条件统一成的形式。：假设对偶变量。对偶变量与原问题的约束条件一一对应，每一个约束条件都有一个对偶变量与它相对应。所以，对偶变量数等于原问题的约束方程数。：根据原问题与对偶问题的关系写出对偶规划模型。

7、2022-5-612原问题：原问题：max z = 4x1+x2-5x3-4x4-2x5 2x2+x3+3x4+4x5 = - 6 3x1+x2-x3-x4 2 - 4x1+2x3-2x4 - 5 - 6 x1 18 x2 25 x3,x4 0; x5 不受限制统一符号（因求max,故约束统一成“ ”的形式：max z = 4x1+x2-5x3-4x4-2x5 2x2+x3+3x4+4x5 = - 6 - 3x1- x2 +x3 +x4 - 2 - 4x1 +2x3 -2x4 - 5 x1 18 - x1 6 x2 25 x3,x4 0;x1,x2, x5 不受限制y1y2y3y4y6y5mi

8、n w = - 6y1-2y2-5y3+18y4+6y5+25y6-3y2-4y3+y4- y5 = 42y1-y2+y6=1y1+y2+2y3 -53y1+y2-2y3 - 44y1= - 2yi 0 ( i=2,3,4,5,6) ; y1为自由变量对对偶偶问问题题2022-5-613无约束321321321321321, 0, 04163253234maxxxxxxxxxxxxxxxxz无约束341431431431431, 0,4163235243maxxxxxxxxxxxxxxxxz令令x2x4，x40统一约束统一约束符号：符号：y1y2y3无约束321321321321321, 0,

9、4336513242minyyyyyyyyyyyyyyyw无约束341341341341341, 0, 03654313242minyyyyyyyyyyyyyyyw2022-5-614无约束321321321321321, 0, 04163253234maxxxxxxxxxxxxxxxxz令x2x2；x3x3x3 0,4)(1)(632)(532)(34max33213321332133213321xxxxxxxxxxxxxxxxxxxxz用两个不等式约束表示等式约束： 0,441)66325532334max332133213321332133213321xxxxxxxxxxxxxxxxxx

10、xxxxxxz 0,44166325532334max332133213321332133213321xxxxxxxxxxxxxxxxxxxxxxxxz2022-5-615 0,44166325532334max332133213321332133213321xxxxxxxxxxxxxxxxxxxxxxxxz 0,44166325532334max3321333213332123321133213321xxxxyxxxxyxxxxyxxxxyxxxxxxxxz 0,36536543132442min332133213321332133213321yyyyyyyyyyyyyyyyyyyyyyyy

11、w令y2y2；y3y3y3无约束321321321321321321, 0, 03653654313242minyyyyyyyyyyyyyyyyyyw2022-5-616无约束321321321321321321, 0, 03653654313242minyyyyyyyyyyyyyyyyyyw无约束321321321321321321, 0, 03653654313242minyyyyyyyyyyyyyyyyyyw无约束321321321321321, 0, 03654313242minyyyyyyyyyyyyyyyw2022-5-617一、单纯形法计算的矩阵描述), 2 , 1(0), 2

12、, 1(max11njxmibxaxczjinjjijnjjj), 2 , 1(0), 2 , 1(min11miynjcyaybwijmiiijmiii0, 00maxsssXXbIXAXXCXz返回本章目录2022-5-6180, 00maxsssXXbIXAXXCXz0,0,maxSNBSNBSNBNBXXXbIXXXNBXXXCCz0,0maxSNBSNBSNNBBXXXbIXNXBXXXCXCz2022-5-6192022-5-620基变量XB的检验数为：CBCBI 0所以，在最终单纯形表中，原变量的检验数可写为CCBB-1A0（2.17）CBB-10（2.18）CBB-1称为单纯形

13、乘子。令Y CBB-1，则2.17、2.18式可以改写为CCBB-1A0 YACI AYC Y0可以看出，原问题得到最优解时，其检验数的相反数是对偶问题的一个可行解。代入对偶问题的目标函数得w Yb CBB-1bz即 原问题得到最优解时，对偶问题为可行解，两者具有相同的目标函数值。2022-5-621)5 , 2 , 1(0524261550002max5214213254321jxxxxxxxxxxxxxxzj)5 , 2 , 1(0125260052415min532143254321iyyyyyyyyyyyyywi原问题：对偶问题：2022-5-622X(x1,x2,x3,x4,x5)T

14、(7/2,3/2,15/2,0,0)T与最优解对应的目标函数值为：21700002150232720002max54321xxxxxzY(y1,y2,y3,y4,y5)T(0,1/4,1/2,0,0)T与最优解对应的目标函数值为：217000021541240150052415min54321yyyyywwzmin217max2022-5-623 在最优单纯形表的检验数行，原问题变量对应的数的相反数，是对偶问题剩余变量的值；原问题松弛变量对应的数的相反数，是对偶问题变量的值。反之亦然。2022-5-6241.弱对偶性：miiinjjjijybxcmiynjx11), 2 , 1(), 2 ,

15、1(的可行解，则恒有是对偶问题是原问题的可行解，如果 miiinjjjminjijijminjijijmiiiminjijijnjmijiijnjjjybxcyxayxaybyxaxyaxc111111111111)()(2022-5-625（1）原问题任一可行解的目标函数值是其对偶问题目标函数值的下界；反之，对偶问题任一可行解的目标函数值是其原问题目标函数值的上界。（2）如原问题有可行解且目标函数值无界（无界解），则其对偶问题无解；反之，对偶问题有可行解且目标函数值无界，则其原问题无可行解。（3）若原问题有可行解而其对偶问题无可行解，则原问题目标函数值无界；反之，对偶问题有可行解而其原问题无

16、可行解，则对偶问题目标函数值无界。2022-5-626若原问题及其对偶问题均具有可行解，则两者均具有最优解，且它们最优解的目标函数值相等。对偶问题的最优解。是其是原问题的最优解，则有对偶问题的可行解，且是其是原问题的可行解，如果), 2 , 1(), 2 , 1(), 2 , 1(), 2 , 1(11miynjxybxcmiynjxijmiiinjjjij2022-5-62700,0,0,000,0,0,01111jsjjsjimiiijsjjmiiijjisiisiinjjijsiinjjijixyxybyaycyaxyxyxbxaxbxay因此，一定有则有即若即则有若对偶问题时：将松弛互

17、补定理用于其因此，一定有则有即若即则有若2022-5-628当线性规划原问题求得最优解xj*( j =1,2,n )时，其对偶问题也得到最优解yi*( i =1,2,m )，且两者的目标函数值相等。即*1*1*wybxczmiiinjjjbi：线性规划原问题右端项，代表第 i 种资源的拥有量；yi*：对偶变量，代表在最优资源利用条件下对单位第 i 种资源的估价，称为影子价格。(Shadow Price)也称为机会成本(Opportunity Cost),它是根据具体的经济目标、技术水平和资源条件作出的对资源利用的评价。：是资源在市场上流通的实际价格，它由整个社会的经济技术状况决定。返回本章目录

18、2022-5-629这说明，。这样一来，在有限资源条件下使收益最大化这一类问题中，就可以把对偶变量的最优值，看成是相应资源每一单位对于目标函数的贡献，即这些资源被充分利用时所能带来的收益。从而， yi* 的值就相当于对单位 i 种资源在实现最大利润时的一种价格估计。这种估计是针对具体企业，具体产品而存在的一种特殊价格，称之为影子价格，它与市场价格不同。若仅从经济上考虑，。随着资源的买进卖出，它的影随着资源的买进卖出，它的影子价格也将随之变化，直到影子价格与市场价格保持同等水平子价格也将随之变化，直到影子价格与市场价格保持同等水平时，才处于平衡状态。时，才处于平衡状态。*1*1*wybxczmi

19、iinjjj*iiybz2022-5-63001234501234Q1Q3Q2Q4Ox1x22022-5-631（1）用影子价格判别资源的供求关系如果线性规划的原问题在得到最优解时，某个约束条件为严格的不等式，即最优解中该约束的松弛变量的值大于零，即0, 0,1isiinjjijyxbxa时表明。如果线性规划的原问题在得到最优解时，某个约束条件为严格的等式，即最优解中该约束的松弛变量的值等于零，即0, 0,1isiinjjijyxbxa时表明。由此可见，2022-5-632m)n,1,2,(j0 xybxxaxaxaybxxaxaxaybxxaxaxaxcxcxcmaxzjmminnmn2m2

20、1m1222nn2n222121111nn1n212111nn2211n)m,1,2,(i0yxcyyayayaxcyyayayaxcyyayayaybybybminwinnnmmmn22n11n222mmm2222112111mmm1221111mm22112022-5-633算出各种资源的影子价格后，可参考影子价格高低顺序合理分配资源，高者优先投资。同时，也可以参考资源的影子价格，合理地确定各种资源的价格。2022-5-634前面介绍的单纯形法，是从一个基本可行解开始进行迭代运算，在迭代过程中，始终保持解的可行性，当所有检验数都非正时，就得到了原问题的最优解。根据对偶定理，原问题单纯形表中

21、的检验数实际上是对偶问题的一组解，但不一定可行，检验数逐渐变为非正的过程，可以理解为对偶问题解的不可行性逐渐消失的过程，当对偶问题的解变为可行解时，原问题就得到了最优解。因此，我们可以选择在对偶问题的解之间进行迭代运算，在迭代过程中，始终保持最优判别条件得到满足，当求出对偶问题的可行解时，也就得到了原问题的最优解。返回本章目录2022-5-635将约束条件两边同时乘以“-1”得：0,1252652415min32132132321yyyyyyyyyyyw)5 , 2 , 1(0125260052415max532143254321iyyyyyyyyyyyyywi标准形式标准形式)5 , 2 ,

22、 1(0125260052415max532143254321iyyyyyyyyyyyyywi1001),(54PPB2022-5-63621, 2min0|minjiijrbbby4为换出变量rssjrjrjjjaaa4,15,624,min0|miny2为换入变量。2022-5-637对一线性规划问题来说，一旦其约束条件系数矩阵对一线性规划问题来说，一旦其约束条件系数矩阵A、约束条件右侧常数向量约束条件右侧常数向量b和价值系数向量和价值系数向量C给定之后，这个线给定之后，这个线性规划问题就确定了。反之，给定一个线性规划问题，就有性规划问题就确定了。反之，给定一个线性规划问题，就有确定的一组

23、确定的一组A、b和和C与之对应。与之对应。在此之前，我们一直假定在此之前，我们一直假定A、b和和C中的元素是常数，它中的元素是常数，它们不发生变化。但实际上这些系数往往是通过估计、预测或们不发生变化。但实际上这些系数往往是通过估计、预测或人为决策得来的，不可能十分准确和一成不变。人为决策得来的，不可能十分准确和一成不变。例如：市场条件一变，价值系数例如：市场条件一变，价值系数cj就会跟着变化；约束就会跟着变化；约束条件系数矩阵条件系数矩阵A中的元素中的元素aij往往随着工艺技术条件的变化而往往随着工艺技术条件的变化而改变；改变；bi通常取决于现有条件和决策人的决策。通常取决于现有条件和决策人的

24、决策。这就是说，随着时间的推移或情况的变化，我们往往需这就是说，随着时间的推移或情况的变化，我们往往需要修改原来线性规划问题中的若干系数，从而使原来的规划要修改原来线性规划问题中的若干系数，从而使原来的规划问题有所改变。问题有所改变。就实际需要来讲，求出最优解，还不能说问题已完全解就实际需要来讲，求出最优解，还不能说问题已完全解决。决策者还需要知道以下一些问题。决。决策者还需要知道以下一些问题。返回本章目录2022-5-638当这些系数中的一个或几个发生变化时，已求得的最优当这些系数中的一个或几个发生变化时，已求得的最优解有什么变化？解有什么变化？这些系数在什么范围内改变时，规划问题的最优解或

25、最这些系数在什么范围内改变时，规划问题的最优解或最优基不变？优基不变？若最优解变化，如何用最简便的方法找到新的最优解？若最优解变化，如何用最简便的方法找到新的最优解？。（1 1）将参数的变化反映到最终单纯形表上；）将参数的变化反映到最终单纯形表上；（2 2）检查原问题是否仍为最优解；）检查原问题是否仍为最优解；（3 3）检查对偶问题是否仍为最优解；）检查对偶问题是否仍为最优解；（4 4）按下表所列情况得出结论，决定继续计算的步骤。）按下表所列情况得出结论，决定继续计算的步骤。2022-5-639表2-9可行解可行解问题的最优解或最优基不变可行解非可行解用单纯形法继续迭代求最优解非可行解 可行解

26、用对偶单纯形法继续迭代求最优解非可行解 非可行解引进人工变量，重新编单纯形表计算ABCCyaczcPBPbBbBmiiijjjjjjj11*11)(或2022-5-6405 , 2 , 10524261550002max5214213254321jxxxxxxxxxxxxxxzj2022-5-6412022-5-642（1）美佳公司家电的利润降至1.5元/件，家电的利润增至2元/件。y1=0, y2=1/4, y3=1/21.521.5281)0452)41(5 .1410)(33422411444cacacac49)343(0)232)21(5.1)215(0051/8-9/4返回提要202

27、2-5-643家电的利润变化范围：2321131122cc13102321,04141若要保持最优解不变，必须1+ 1+ 414141141245001444miiiacc41412321231212215001555miiiacc23212022-5-644（1）美家公司设备A和调试工序的每天能力不变，设备B每天的能力增加到32小时，分析公司最优计划的变化。0805524321515b221008023410214102154511bBb35/211/2-1/2返回提要2022-5-645设调试工序每天可用能力为（5+）小时。23212150023410214102154511bBb2323

28、212721521523232127215215bbb1102323021270215215解得：215215212723232022-5-646增加一个变量在实际问题中表示增加一种新产品。分析步骤：。继续迭代，求出最优解若原最优解不变，若计算计算, 0, 0. 3. 2. 111*jjjjmiiijjjjjPBPyaczc例7 美佳佳公司计划推出新型产品家电，生产一件所需设备A、B及调试工序的时间分别为3小时、4小时、2小时，该产品的预期盈利为3元/件，试分析该产品是否值得投产；如投产，该公司生产计划有何变化。解：设该公司每天生产家电x6件，则有c6 = 3; P6 = ( 3,4,2 )T

29、124321,41, 03620724323410214102154516P返回提要2022-5-647x63-7021佳佳2022-5-648aij 的变化将引起约束条件系数矩阵的变化将引起约束条件系数矩阵 A 发生变化。发生变化。例例8 在美佳公司的例子中，若家电在美佳公司的例子中，若家电每件需设备每件需设备A、B和和调试工时变为调试工时变为8小时、小时、4小时、小时、1小时，该产品的利润变为小时，该产品的利润变为3元元/件，试重新确定该公司的最优生产计划。件，试重新确定该公司的最优生产计划。解：将生产工时变化后的新家电解：将生产工时变化后的新家电看作是一种新产品，看作是一种新产品，生产量

30、为生产量为x2，则，则2314821,41, 031*22miiijyac21212111482341021410215451212PBP返回提要2022-5-649从上表看出，原问题和对偶问题均为非可行解，故先设法使原问题变为可行解。x34x424x59x34x424x5x69人人工工变变量量2022-5-650佳佳2022-5-6512022-5-652增加一个约束条件在实际问题中相当于增加一道工序。分析增加一个约束条件在实际问题中相当于增加一道工序。分析方法是先将原问题最优解的变量值代入新增的约束条件，如满方法是先将原问题最优解的变量值代入新增的约束条件，如满足，说明新增的约束条件未起到

31、限制作用，原最优解不变。否足，说明新增的约束条件未起到限制作用，原最优解不变。否则，将新增的约束直接反映到最终单纯形表中再进一步分析。则，将新增的约束直接反映到最终单纯形表中再进一步分析。例例9 设美佳公司家电设美佳公司家电，家电，家电经调试后，还需经过一道环经调试后，还需经过一道环境试验工序，家电境试验工序，家电每件须环境试验每件须环境试验3小时，家电小时，家电每件每件2小时，小时，环境试验工序每天生产能力为环境试验工序每天生产能力为12小时。试分析增加该工序后，小时。试分析增加该工序后，美家公司的最优生产计划。美家公司的最优生产计划。 解：环境试验工序的约束条件为解：环境试验工序的约束条件

32、为3x1+2x212将原问题最优解代入得：将原问题最优解代入得：37/223/227/212由此可见，新增约束得不到满足，需加入松弛变量，将其化由此可见，新增约束得不到满足，需加入松弛变量，将其化为标准形式：为标准形式：3x1+2x2x612以以x6为基变量，将新增约束填入最终单纯形表中。为基变量，将新增约束填入最终单纯形表中。返回提要2022-5-65332用对偶单用对偶单纯形法迭纯形法迭代计算代计算增加环境试增加环境试验工序后，验工序后，美佳公司的美佳公司的最优生产计最优生产计划为每天生划为每天生产 家 电产 家 电 4 件。件。2022-5-654灵敏度分析中研究灵敏度分析中研究cj、b

33、i等参数改变到某一值时对问题最等参数改变到某一值时对问题最优解的影响，若令优解的影响，若令cj、bi沿某一方向连续变动，则目标函数沿某一方向连续变动，则目标函数 z将随将随 cj 或或 bi 的变动而呈线性变动，的变动而呈线性变动，z 是这个变动参数的线性是这个变动参数的线性函数，因而称为参数线性规划。函数，因而称为参数线性规划。参数线性规划的一般形式：参数线性规划的一般形式：0)()(max*XbAXXCCzcj 连续变化时：连续变化时：0)(max*XbbAXCXzbi 连续变化时：连续变化时：C*和和b*为变动向量，为变动向量， 为变动参数。为变动参数。返回本章目录2022-5-655解

34、：令0，求得：0,52426155)21 ()2()(max212121221xxxxxxxxxz2+1+22+1+241412521 213217;0 ,0 ,215,23,271510252104141*zXT最优解为解得2022-5-65651511,0205151解得2022-5-657414125212022-5-65835316131 4 4 8 8 z z; ;4 4, ,0 0, ,1 15 5, ,0 0, ,1 1最最优优解解为为：X X5 51 1 2 2解解得得0 0 6 61 13 31 1, ,0 0 3 35 53 31 1T T* *2022-5-659 0,5 ,24,15,