运筹学对偶理论和灵敏度分析幻灯片.ppt
《运筹学对偶理论和灵敏度分析幻灯片.ppt》由会员分享,可在线阅读,更多相关《运筹学对偶理论和灵敏度分析幻灯片.ppt(61页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、运筹学运筹学对偶理偶理论和灵敏度分析和灵敏度分析1第1页,共61页,编辑于2022年,星期三第一节第一节 对偶问题的提出对偶问题的提出 材料材料产品产品甲甲乙乙丙丙丁丁单件单件收益收益A32112000B41324000C22343000限额限额600400300200假设工厂考虑不进行生产而把假设工厂考虑不进行生产而把全部资源都转让,问如何定价全部资源都转让,问如何定价这些资源,既能使其获利不低这些资源,既能使其获利不低于安排生产所获得的收益,又于安排生产所获得的收益,又能使资源租让具有竞争力。能使资源租让具有竞争力。一、引例一、引例MaxZ=2000 x1+4000 x2+3000 x3s
2、.t.3x1+4x2+2x36002x1+x2+2x3400 x1+3x2+3x3300 x1+2x2+4x3200 x1,x2,x30MinW=600y1+400y2+300y3+200y4s.t.3y1+2y2+y3+y420004y1+y2+3y3+2y440002y1+2y2+3y3+4y43000y1,y2,y3,y40 x1x2x3y1y2y3y42第2页,共61页,编辑于2022年,星期三二、对偶问题二、对偶问题(1 1)对称)对称LPLP问题的定义问题的定义(2 2)对称)对称LPLP问题的对偶问题问题的对偶问题第一类对称形式第一类对称形式第二类对称形式第二类对称形式3第3页,
3、共61页,编辑于2022年,星期三例例1 1 写出下列写出下列LPLP问题的对偶问题问题的对偶问题对偶对偶MaxZ=2x1+3x2s.t.x1+2x284x1164x212x1,x2 0MinW=8y1+16y2+12y3s.t.y1+4y222y1+4y33y1,y2,y3 04第4页,共61页,编辑于2022年,星期三(3 3)对偶问题的对偶是原问题)对偶问题的对偶是原问题推导过程推导过程变形对偶变变形形对偶对偶对偶对偶变变形形MaxZ=CTXs.t.AXbX0MinW=bTYs.t.ATYCY0MaxW=-bTYs.t.-ATY-CY0MinZ=-CTXs.t.-(AT)TX-bX05第
4、5页,共61页,编辑于2022年,星期三例例2 2 写出下列写出下列LPLP问题的对偶问题问题的对偶问题解解:上述上述LPLP问题的问题的 对偶问题为:对偶问题为:6第6页,共61页,编辑于2022年,星期三三、非对称三、非对称LPLP问题的对偶问题问题的对偶问题例例3 3 写出下列写出下列LPLP问题的对偶问题问题的对偶问题解:用解:用x2=-x2,x3=x3-x3代代入上述入上述LP问题,并将其问题,并将其化为化为第一类对称形式第一类对称形式MaxZ=x1+2x2+x3 x1+x2-x32s.t.x1-x2+x3=1 2x1+x2+x32x10,x20,x3无约束无约束MaxZ=x1-2x
5、2+x3-x3x1-x2-x3+x3 2 x1+x2+x3-x3 1s.t.-x1-x2-x3+x3-1 -2x1+x2-x3+x3-2 x1,x2,x3,x3 07第7页,共61页,编辑于2022年,星期三上述第一类对称形式上述第一类对称形式LP问题的对偶问题为:问题的对偶问题为:则上述问则上述问题变为:题变为:MinW=2y1+y2-y3-2y4y1+y2-y3-2y41 -y1+y2-y3+y4-2s.t.-y1+y2-y3-y41y1-y2+y3+y4-1 y1,y2,y3,y40MinW=2u1+u2+2u3 u1+u2+2u31s.t.u1-u2+u32 -u1+u2+u3=1u1
6、0,u30,u2无约束无约束令令 u1=y1u2=y2-y3 u3=-y48第8页,共61页,编辑于2022年,星期三(D)MinW=2u1+u2+2u3 u1+u2+2u31s.t.u1-u2+u32 -u1+u2+u3=1u10,u30,u2无约束无约束(L)MaxZ=x1+2x2+x3 x1+x2-x32s.t.x1-x2+x3=1 2x1+x2+x32x10,x20,x3无约束无约束对偶关系:对偶关系:一个问题第一个问题第i个变量的约束情况决定另一问题第个变量的约束情况决定另一问题第i个约个约束不等式的方向,反之亦然。束不等式的方向,反之亦然。正常的对正常的,不正常的对不正常的正常的对
7、正常的,不正常的对不正常的9第9页,共61页,编辑于2022年,星期三例例3 3 直接写出直接写出LPLP问题的对偶问题问题的对偶问题10第10页,共61页,编辑于2022年,星期三11第11页,共61页,编辑于2022年,星期三第二节第二节 LPLP问题的对偶理论问题的对偶理论若若X(0),Y(0)分别为分别为(L),(D)的可行解,则有的可行解,则有CTX(0)bTY(0)定理定理1(1(弱对偶定理弱对偶定理):):极大化原问题目标函数值总是不大于其极大化原问题目标函数值总是不大于其对偶问题的目标函数值。对偶问题的目标函数值。证明:证明:由于由于X(0)是是(L)的可行解,有的可行解,有A
8、X(0)b,X(0)0.由于由于Y(0)是是(D)的可行解,有的可行解,有Y(0)0.Y(0)T左乘不等式组左乘不等式组AX(0)b的两边得:的两边得:Y(0)TAX(0)Y(0)Tb.两边同时转置得两边同时转置得X(0)TATY(0)bTY(0)(1)12第12页,共61页,编辑于2022年,星期三又又ATY(0)C,X(0)T0.所以所以 X(0)TATY(0)X(0)TC=CTX(0)(2)由(由(1),(),(2)得:得:CTX(0)bTY(0)13第13页,共61页,编辑于2022年,星期三推论推论1 1 若若LPLP问题有无界解,则其对偶问题无可行解;问题有无界解,则其对偶问题无可
9、行解;若若LPLP问题无可行解,则对偶问题或有无界解或无可行解。问题无可行解,则对偶问题或有无界解或无可行解。推论推论2 2极大化问题的任何一个可行解所对应的目标极大化问题的任何一个可行解所对应的目标函数值都是其对偶问题目标函数值的下界。函数值都是其对偶问题目标函数值的下界。极小化问题的任何一个可行解所对应的目标极小化问题的任何一个可行解所对应的目标函数值都是其对偶问题目标函数值的上界。函数值都是其对偶问题目标函数值的上界。推论推论3 314第14页,共61页,编辑于2022年,星期三例例4 4 考虑下面一对考虑下面一对LPLP问题问题其对偶问题为:其对偶问题为:由于由于X(0)=(1,1,1
10、,1)T,Y(0)=(1,1)T分别为分别为(L),(D)的可行解,故的可行解,故Z40,W10.MaxZ=x1+2x2+3x3+4x4 x1+2x2+2x3+3x420s.t.2x1+x2+3x3+2x420 x1,x2,x3,x4 0MinW=20y1+20y2y1+2y21 2y1+y22 s.t.2y1+3y233y1+2y24 y1,y2015第15页,共61页,编辑于2022年,星期三定理定理2 2(最优性准则)(最优性准则)当当LPLP问题目标函数值与其对偶问题目标函问题目标函数值与其对偶问题目标函数值相等时,各自的可行解即为最优解。数值相等时,各自的可行解即为最优解。若若X(0
11、),Y(0)分别为分别为(L),(D)的可行解的可行解,且且CTX(0)bTY(0),则则X(0),Y(0)分别为分别为(L),(D)的最优解。的最优解。证明:证明:由定理由定理1 1可知,对于可知,对于(L)的任意可行解的任意可行解X,有,有CTXbTY(0)由于由于CTX(0)=bTY(0),故,故X(0)为为(L)的最优解。的最优解。同理同理Y(0)为为(D)的最优解。的最优解。16第16页,共61页,编辑于2022年,星期三例例5 5MaxZ=x1+2x2+3x3+4x4 x1+2x2+2x3+3x420s.t.2x1+x2+3x3+2x420 x1,x2,x3,x4 0MinW=20
12、y1+20y2y1+2y21 2y1+y22 s.t.2y1+3y233y1+2y24 y1,y20由于由于X(0)=(0,0,4,4)T,Y(0)=(6/5,1/5)T是是(L),(D)的的可行解且可行解且 CX(0)=bTY(0)=28,所以,所以X(0),Y(0)分别为分别为(L),(D)的最优解。的最优解。17第17页,共61页,编辑于2022年,星期三定理定理3 3(强对偶定理)(强对偶定理)若若(L),(D)均有可行解,则均有可行解,则(L),(D)均有最均有最优解,且目标函数最优值相等。优解,且目标函数最优值相等。证明:证明:设设X(0),Y(0)分别为分别为(L),(D)的可行
13、解的可行解,由弱对偶定理,对于由弱对偶定理,对于(L)的任意可行解的任意可行解X,有,有CTXbTY(0),所以,所以CTX在可行域内有上界,在可行域内有上界,故故(L)有最优解。有最优解。同理,对于同理,对于(D)的任意可行解的任意可行解Y,有有bTYCTX(0),所以,所以bTY在在可行域内有下界,故可行域内有下界,故(D)有最优解。有最优解。设设(L)的最优解为的最优解为X(0),且,且X(0)所对应的最优基为所对应的最优基为B,X(0)可以表示为可以表示为X(0)=XB(0)=B-1b XN(0)018第18页,共61页,编辑于2022年,星期三则则(AT,ST)=(CT,0T)CBT
14、B-1(A,I)0由于由于CTCBTB-1A0,所以所以CBTB-1A CT即即AT(CBTB-1)TC (1)又又0TCBTB-1I 0,故故(CBTB-1)T0.(2).(2)令令Y(0)=(CBTB-1)T,由由(1)(2)(2)知知Y(0)是是(D)的可行解的可行解.因为因为CTX(0)=(CBT,CNT)XB(0)=CBTXB(0)+CNTXN(0)=CBTB-1b XN(0)而而bTY(0)=bT(CBTB-1)T=CBTB-1b则则CTX(0)=bTY(0),由最优性准则知,由最优性准则知,X(0),Y(0)分别为分别为(L),(D)的最优解的最优解,且目标函数最优值相等。且目标
15、函数最优值相等。19第19页,共61页,编辑于2022年,星期三推论:推论:在用单纯形法求解在用单纯形法求解LPLP问题问题(L)的最优单纯形表中,松弛变的最优单纯形表中,松弛变量的检验数的相反数就是其对偶问题量的检验数的相反数就是其对偶问题(D)的最优解。的最优解。证明:因为证明:因为sT=0T-CBTB-1I=-CBTB-1y*T=CBTB-1所以所以y*=-s例例5 5 求下列问题对偶问题的最优解求下列问题对偶问题的最优解MaxZ=2x1+3x2s.t.x1+2x284x1164x212x1,x2 0解:化为标准型解:化为标准型MaxZ=2x1+3x2+0 x3+0 x4+0 x5s.t
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 运筹学 对偶 理论 灵敏度 分析 幻灯片
限制150内