对偶理论和灵敏度分析精.ppt

《对偶理论和灵敏度分析精.ppt》由会员分享，可在线阅读，更多相关《对偶理论和灵敏度分析精.ppt（49页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、对偶理论和灵敏度分析第1页，本讲稿共49页1.单纯形的矩阵描述用矩阵语言描述单纯形法的关键是写出两个基本的表达式,设线性规划的标准型为 maxz=CX AX=b X0C=(CB,CN)，X=(XB,XN)，A=(B,N)由约束条件AX=(B,N)(XB,XN)=BXB+NXN=b，可以得到用非基变量表示基变量的表达式:XB=B-1b-B-1NXN (1)第2页，本讲稿共49页将将(1)式代入目标函数的表达式式代入目标函数的表达式,可以得到用非基变可以得到用非基变量表示目标函数的表达式量表示目标函数的表达式.Z=CX=(CB,CN)(XB,XN)=CBXB+CNXN=CB(B-1-B-1NXN)

2、+CNXN=CBB-1b+(CN-CBB-1N)XN=CBB-1b+N NXN另非基变量等于零，则另非基变量等于零，则Z=CBB-1b注意注意XB检验数为零检验数为零,实质上是实质上是CB-CBB-1B=0Y=CBB-1为单纯为单纯形乘子形乘子第3页，本讲稿共49页 c x bCB CN XB XNXBB-1bB-1B B-1N-z-CBB-1b 0 CN-CBB-1 N第4页，本讲稿共49页注意:在初始单位矩阵的位置,在各运算表中就是B-1的所在位置 BIIB-1第5页，本讲稿共49页2.改进单纯形法改进单纯形法又称为逆矩阵法或修正单纯改进单纯形法又称为逆矩阵法或修正单纯形法形法,是在原来单

3、纯形法基础上加以改进，关键是在原来单纯形法基础上加以改进，关键在于求在于求B-1,有了有了B-1,单纯单纯形算法的各个表中的数字都形算法的各个表中的数字都可以利用可以利用线线性性规规划中的原始数据划中的原始数据计计算出来。算出来。第6页，本讲稿共49页第7页，本讲稿共49页 3对偶理论某厂生产甲乙两种产品，各自的零部件分别在A、B车间生产，最后都需在C车间装配，相关数据如表所示：问如何安排甲、乙两产品的产量，使利润为最大。产品产品车间车间工时单耗工时单耗甲甲 乙乙生产能力生产能力ABC 1 0 0 2 3 48 1236单位产品获利单位产品获利 3 5maxZ=3x1+5 x2 x1 8 2x

4、2 12 3x1+4 x2 36 x1 0,x2 0S.t.第8页，本讲稿共49页若若上上例例中中该该厂厂的的产产品品平平销销，现现有有另另一一企企业业想想租租赁赁其其设设备备。厂厂方方为为了了在在谈谈判判时时心心中中有有数数，需需掌掌握握设设备备台台时时费费用用的的最最低低价价码码，以以便便衡衡量量对对方方出出价价，对对出出租租与与否否做做出出抉择。抉择。在在这这个个问问题题上上厂厂长长面面临临着着两两种种选选择择：自自行行生生产产或或出出租设备。首先要弄清两个问题：租设备。首先要弄清两个问题：合理安排生产能取得多大利润合理安排生产能取得多大利润?为保持利润水平不降低，资源转让的最低价格是多

5、少？为保持利润水平不降低，资源转让的最低价格是多少？问题问题 的最优解：的最优解：x1=4，x2=6，Z*=42。第9页，本讲稿共49页假设出让假设出让A、B、C设备所得利润分别为设备所得利润分别为y1、y2、y3原本用于生产甲产品的设备台时，如若出让，不应低原本用于生产甲产品的设备台时，如若出让，不应低于自行生产带来的利润，否则宁愿自己生产。于是有于自行生产带来的利润，否则宁愿自己生产。于是有 y1+0y2+3y3 3同理，对乙产品而言，则有同理，对乙产品而言，则有 0y1+2y2+4y3 5设备台时出让的收益（希望出让的收益最少值）设备台时出让的收益（希望出让的收益最少值）min=8y1+

6、12y2+36y3显然还有显然还有 y1，y2，y30第10页，本讲稿共49页min =8y1+12y2+36y3 y1+0y2+3y3 3 0y1+2y2+4y3 5 y1，y2，y30 S.t.maxZ=3x1+5 x2 x1 8 2x2 12 3x1+4 x2 36 x1,x2 0S.t.第11页，本讲稿共49页例例 线性规划线性规划问题 maxz=3x1+5x2st x1+3x2 10 7x1+4x2 20 xj 0;j=1,2.对偶偶问题为：ming=10y1+20y2st y1+7y2 3 3y1+4y2 5 yi 0;i=1,2。第12页，本讲稿共49页 3.1对偶变换的规则对偶

7、变换的规则第13页，本讲稿共49页 3.2对偶问题的基本性质对偶问题的基本性质为了便于讨论，下面不妨总是假设(1)对称性：对称性：对偶问题的对偶是原问题。(2)弱弱对偶性：对偶性：对偶问题(min)的任何可行解Y0，其目标函数值总是不小于原问题(max)任何可行解X0的目标函数值，即CX0Yb0。弱弱对偶定理推论：对偶定理推论：原问题原问题的任何可行解目标函数值是是其对偶问题对偶问题目标函数值的下限下限；对偶问题对偶问题的任何可行解目标函数值是原问题是原问题目标函数值的上限上限。第14页，本讲稿共49页(3)(3)无界性无界性 若原若原(对偶对偶)问题为无界解，则其对偶问题为无界解，则其对偶(

8、原原)问题无可问题无可行解行解v当原问题当原问题(对偶问题对偶问题)为无可行解为无可行解,其对偶问题其对偶问题(原问题原问题)或具有无界解或具有无界解或无可行解。或无可行解。v如果原如果原(对偶对偶)问题有可行解，其对偶问题有可行解，其对偶 (原原)问题无可行解，则原问问题无可行解，则原问题为无界解。题为无界解。(4)强对偶性强对偶性可行解是最优解的性质可行解是最优解的性质(最优性准则定理最优性准则定理)若原问题的某个可行解若原问题的某个可行解X0的目标函数值与对偶问题某个可行解的目标函数值与对偶问题某个可行解Y0的目标函数值相等，则的目标函数值相等，则X0,Y0分别是相应问题的最优解分别是相

9、应问题的最优解（5）主对偶）主对偶定理定理 若原问题和对偶问题两者皆可行若原问题和对偶问题两者皆可行,则两者均有最优解则两者均有最优解,且此时且此时目标函数值相等。目标函数值相等。第15页，本讲稿共49页 综上所述，一对对偶问题的解必然是下列三种情况之一综上所述，一对对偶问题的解必然是下列三种情况之一:原问题和对偶问题都有最优解。原问题和对偶问题都有最优解。一个问题具有无界解，另一个问题无可行解。一个问题具有无界解，另一个问题无可行解。原问题和对偶问题都无可行解。原问题和对偶问题都无可行解。(6)互补松弛互补松弛性性设设X0,Y0分别是原问题和对偶问题的可行解，分别是原问题和对偶问题的可行解，

10、Xs为原问题的松弛变为原问题的松弛变量的值、量的值、Ys为对偶问题剩余变量的值。为对偶问题剩余变量的值。X0,Y0分别是原问题和对偶问分别是原问题和对偶问题最优解的充分必要条件是题最优解的充分必要条件是：Y0 Xs=Ys X0=0第16页，本讲稿共49页(7)原问题单纯形表检验数行与对偶问题解的关系原问题单纯形表检验数行与对偶问题解的关系原问题单纯形表检验数的相反数对应对偶问题的一个基解原问题单纯形表检验数的相反数对应对偶问题的一个基解.显然显然,原问题最终单纯形表检验数的相反数对应对偶问题原问题最终单纯形表检验数的相反数对应对偶问题的一个基可行解的一个基可行解XBXNXS0CN-CBB-1N

11、-CBB-1YS1-YS2-Y第17页，本讲稿共49页例已知线性规划问题：例已知线性规划问题：试用对偶理论证明此线性规划问题无最优解。试用对偶理论证明此线性规划问题无最优解。解：对偶问题为：解：对偶问题为：解：对偶问题为：解：对偶问题为：由第一约束条件显见，对偶问题无可行解因为（由第一约束条件显见，对偶问题无可行解因为（由第一约束条件显见，对偶问题无可行解因为（由第一约束条件显见，对偶问题无可行解因为（0 0，0 0，0 0）为线性规划问）为线性规划问）为线性规划问）为线性规划问题的可行解。而对偶问题无可行解，则原问题为无界解或无可行解，故原问题题的可行解。而对偶问题无可行解，则原问题为无界解

12、或无可行解，故原问题题的可行解。而对偶问题无可行解，则原问题为无界解或无可行解，故原问题题的可行解。而对偶问题无可行解，则原问题为无界解或无可行解，故原问题无最优解。无最优解。无最优解。无最优解。第18页，本讲稿共49页例例5：线性规划问题最优解为：线性规划问题最优解为：线性规划问题最优解为：线性规划问题最优解为用对偶问题求原问题的最优解。用对偶问题求原问题的最优解。用对偶问题求原问题的最优解。用对偶问题求原问题的最优解。第19页，本讲稿共49页对偶问题为：对偶问题为：将对偶问题的解代入上述约束条件，可知2、3、4式为严格不等式；由松弛互补性，可得x2=x3=x4=0,因y1,y2大于零，所以

13、原问题的两个约束条件应该取等式，故有：第20页，本讲稿共49页 4.影子价格（对偶价格）影子价格（对偶价格）对偶变量yi(i=1,2,m)表示原问题的第i个约束条件的影子价格，它表示：在其它条件不变的情况下，单位资源变化所引起的目标函数的最优值的变化。(1)影子价格能指示企业内部挖潜的方向。影子价格能指示企业内部挖潜的方向。影子价格越高的资源，它对目标增益的影响越大，同时也表明这种资源越稀缺和贵重。企业的管理者要重视这种资源的管理，挖掘潜力，及时组织资源，由此可以给企业带来较大的收益。(2)影子价格指导企业间的分工与协作。影子价格指导企业间的分工与协作。影子价格可以作为企业在接受外协加工任务时

14、，对外协单位使用资源的收费标准，按照影子价格收费，保证了企业与外协单位双方平等互利的格局，可以促进双方合作。第21页，本讲稿共49页(3)影子价格在新产品开发决策中的应用。影子价格在新产品开发决策中的应用。两种新产品A,B的机会成本机会成本（万元）：A单位产品的机会成本=13/4+20+31/4=3/2B单位产品的机会成本=23/4+10+41/4=5/2产品产品资源资源A B影子价格影子价格(万元万元)钢材煤机时1 22 13 43/4 01/4单位利润(万元)1 3第22页，本讲稿共49页 由于投产A产品所能提供的单位利润（1万元）不大于投产的机会成本（1.5万元），因此A产品不宜投产；而

15、B产品的机会成本（2.5万元）小于该产品投产后所能提供的利润（3万元），因此投产B产品可以给工厂带来较大的收益。如果新产品B确实为社会所欢迎,而在资源利用上与老产品发生冲突，工厂可以考虑用B产品去更换老产品，以获得更大的经济效益。(4)影子价格在资源采购决策中的应用。影子价格在资源采购决策中的应用。当资源的市场价格低于影子价格，企业买进该资源，扩大生产，当资源的市场价格高于影子价格，企业应设法转让该资源。第23页，本讲稿共49页(5)(5)利用影子价格分析工艺改变后对资源节约的收益。利用影子价格分析工艺改变后对资源节约的收益。例如设工厂现有钢材100吨，其影子价格为3/4，采用新工艺后，钢材可

16、以节约2%，则由此带来的经济收益为：1003/42%=3/2(万元)第24页，本讲稿共49页5.对偶单纯形法对偶单纯形法对偶单纯形法是应用对偶原理求解原问题线性规划的对偶单纯形法是应用对偶原理求解原问题线性规划的一种方法一种方法,采用的技术是在原问题的单纯形表格上进行对采用的技术是在原问题的单纯形表格上进行对偶处理。注意偶处理。注意:对偶单纯形法不是求解对偶问题的单纯形对偶单纯形法不是求解对偶问题的单纯形法。法。第25页，本讲稿共49页单纯形法的求解过程是：在保持原始可行(b列保持）的前提下，通过逐步迭代实现对偶可行（检验数行）。换个角度考虑线性规划的求解过程：能否保持对偶可行（检验数行保持）

17、的前提下，通过逐步迭代实现原始可行(b列，从非可行解变成可行解）呢？答案是肯定的，这就是对偶单纯形法的基本思想。第26页，本讲稿共49页步骤：（1）根据线性规划问题，列出初始单纯形表。若b列数字还有负分量，检验数保持非正，则（2）确定换出变量选min(B-1b)i/(B-1b)i 0对应的变量xl为换出变量（3）确定换入变量=mincj-zj/aij(aij0)所对应的非基变量xk为换入变量。（4）以alk为主元素进行迭代运算，并重复以上步骤第27页，本讲稿共49页利用对偶单纯形法求解以下线性规划问题：第28页，本讲稿共49页cjCBXBbx1x2x3x4x5-1-3000-2-3-1-1-2

18、-2100010解法001-3-4-1x3x4x5000-1-3000cj-zj1/33/2x3x1x50101/32/3-4/3100-2/3-1/3-1/3001cj-zj-1/34/31/30-7/30-1/301/20-10 x4x1x53/21/2010-1/2-3/2-3/2-1/2-1/21000010-10cj-zj0-5/2-1/200-3/2此时所有的B-1b均0，且所有的cj-zj均0，此时已得到最优解为：X*=(3/2,0,0,1/2,1/2)TZ*=-3/2第29页，本讲稿共49页总结：对偶单纯形法与单纯形法的比较最优解时要求单纯形法对偶单纯形法保持B-1b0所有的c

19、j-zj0所有的cj-zj0B-1b0第30页，本讲稿共49页特点：可以避免加人工变量，简化计算灵敏度分析和整数规划常借助于对偶单纯形法分析局限性在于初始单纯形表的检验数行很难满足小于或等于零的要求，即满足检验数行对应的对偶问题的解是可行解第31页，本讲稿共49页6.灵敏度分析灵敏度分析灵敏度分析的意义灵敏度分析的意义 线性规划研究的是一定条件下的最优化问题，采用优化方案可以达到节约资源、提高效益的目的，但是对“优化方案”必须要有全面的认识，不可机械地对待。优化方案是建立在特定的资源环境和技术条件之上的，而环境和条件总是处在不断地变化之中，如产品价格、原材料成本、加工技术水平、资源消耗系数等时

20、有波动，所以优化方案是个相对稳定的概念。当基础数据发生变化时，最优方案也就变了。基础数据往往是测算估计的数值，虽然在运算过程中要求十分严格，但基础数据的误差是不可避免的。为了对优化结果有更全面的了解和恰当的运用，就需要进行灵敏度分析。第32页，本讲稿共49页灵敏度分析所要解决的问题：灵敏度分析所要解决的问题：系数在什么范围内变化，不会影响已获得的最优基系数在什么范围内变化，不会影响已获得的最优基(即即最优解或最优解结构不变最优解或最优解结构不变)。如果系数的变化超过以上范围，如何在用最简便的方法在如果系数的变化超过以上范围，如何在用最简便的方法在原来最优解的基础上求得新的最优解原来最优解的基础

21、上求得新的最优解当线性规划问题增加一个新的变量或新的约束，如何在当线性规划问题增加一个新的变量或新的约束，如何在原来最优解的基础上获得新的最优解。原来最优解的基础上获得新的最优解。第33页，本讲稿共49页6.1右端项bi变化的灵敏度分析bi变化到什么程度可以保持最优基不变？用xB=B-1b 0。第34页，本讲稿共49页例：求以下模型中第二个约束条件右端项b2的变化范围。maxZ=70X1+120X29X1+4X23604X1+5X2 200 3X1+10X2 300 X10 X20第35页，本讲稿共49页 Cj70 120 0 0 0CBXBbX1 X2 X3 X4 X5i 0 0 0X3X4

22、X5360200300 9 4 1 0 0 4 5 0 1 0 3 10 0 0 1 904030j0 70 120 0 0 0 0 0 120X3X4X224050 30 7.8 0 1 0 -0.4 2.5 0 0 1 -0.5 0.3 1 0 0 0.130.7620100j3600 34 0 0 0 -12070120X3X1X2842024 0 0 1 -3.12 1.16 1 0 0 0.4 -0.2 0 1 0 -0.12 0.16j4280 0 0 0 -13.6 -5.2第36页，本讲稿共49页解：从最优单纯形表得出：XB=(20,24,84)T最优基为：注意：应为初始数据。

23、还可以从单纯形表中找出B-1.第37页，本讲稿共49页设b2由200变为200 b2，则b由 由此得到迭代后的单纯形表：cj70120000CBXBbx1x2x3x4x5i010001100-3.120.4-0.121.16-0.20.1684-3.12 b220+0.4 b224-0,12 b2x3x1x2070120j4280+13.6 b2000-13.6-5.2第38页，本讲稿共49页上述解是最优解，必须是可行解：即：解得：50 b2 26.9。可知右端项系数b2的变化范围是:（20050）（20026.9)第39页，本讲稿共49页在此范围内j 0，B-1b 0，最优解仍有效，即最优解

24、的基变量不变，最优解为：最优值为：Z*=4280+13.6 b2 第40页，本讲稿共49页6.2目标函数中价值系数cj的灵敏度分析分cj是非基变量的系数还是基变量的系数两种情况来讨论。若cj是非基变量xj的系数，此时，当cj变化 cj后，要保证最终表中这个检验数仍小于或等于零即可。若cj是基变量xj的系数，则引起的变化较大。第41页，本讲稿共49页例：在模型例1中，求基变量x2的系数变化范围。解：本例的最优单纯形表如下：070120cjCBXBbx3x1x2842024x1x2x3x4x5i70120000010001100-3.120.4-0.121.16-0.20.16j4280000-1

25、3.6-5.2第42页，本讲稿共49页基变量系数c2由120变为120 c2后，可以得到迭代后的单纯形表。cjCBXBbx3x1x2842024x1x2x3x4x5i70120 c2000010001100-3.120.4-0.121.16-0.20.16j428024 c2000-13.6+0.12 c2-5.2-0.16 c2070120+c2第43页，本讲稿共49页要保持最优解，必须使j 0，即：13.6+0.12 c2 0 -5.2-0.16 c2 0解得32.5 c2 113.3由此可知，c2 的变化范围为：（12032.5)(120+113.3)，即87.5 c2 233.3。第4

26、4页，本讲稿共49页6.3技术系数aij的灵敏度分析某非基变量技术系数的改变会影响该非基变量的检验数，如果检验数仍然可以满足，则最优解保持不变否则继续迭代某基变量技术系数j的改变的灵敏度分析比较复杂，因为某基变量技术系数的改变对最终表解的可行性和检验数行的检验系数都可能产生影响第45页，本讲稿共49页例：讨论线性规划的系数列向量 的情况。第46页，本讲稿共49页解：首先利用单纯形法得出初始单纯形表及最优单纯形表如下。CBXBbx1x2x3x4x52-1-10000 x4x5641-112101001j 2-1-10020 x1x56101013111101j0-3-1-20第47页，本讲稿共49页由于 .所以CBXBbx1x2x3x4x52-1-10000 x4x5641-112101001j 2-1-10020 x1x56101013111101j0-3-1-2027-5由此可知，当前解仍为最优解。第48页，本讲稿共49页第49页，本讲稿共49页