运筹学之对偶函数_运筹学之对偶问题

运筹学之对偶函数由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“运筹学之对偶问题”。

4.1 对偶问题(1)对偶问题的提出对偶理论是线性规划中最重要的理论之一，是深入了解线性规划问题结构的重要理论基础。同时，由于问题提出本身所具有的经济意义，使得它成为对线性规划问题系统进行经济分析和敏感性分析的重要工具。那么，对偶问题是怎样提出的，为什么会产生这样一种问题呢？2 王老板的家具生产模型：x1、x2是桌、椅生产量。Z是家具销售总收入（总利润）。max Z = 50x1 + 30x2s.t.4x1+3x2≤120（木工）2x1+ x2≤50（油漆工）x1，x2 ≥0原始线性规划问题，记为（P）王老板的资源出租模型：y1、y2单位木、漆工出租价格。W是资源出租租金总收入。min W =120y1 + 50y2s.t.4y1+2y2≥503y1+ y2≥30y1，y2 ≥0对偶线性规划问题，记为（D）两个原则1.所得不得低于生产的获利2.要使对方能够接受2011-8-194 王老板按（D）的解y1、y2出租其拥有的木、漆工资源，既保证了自己不吃亏（出租资源的租金收入并不低于自己生产时的销售收入），又使得出租价格对李老板有极大的吸引力（李老板所付出的总租金W最少）。按时下最流行的一个词，叫什么来着————2011-8-195 例1目标函数MaxZ=40x1 +50x2x1 + 2x230 y1y2 y33x1 + 2x2602x224x1，x20约束条件s.t三种资源的使用单价分别为y1 , y2 , y3生产单位产品A的资源消耗所得不少于单位产品A的获利y1 +3 y2 40生产单位产品B的资源消耗所得不少于单位产品B的获利2y1 + 2 y2+ 2y3 502011-8-196 通过使用所有资源对外加工所获得的收益W = 30y1 + 60 y2+ 24y3根据原则2，对方能够接受的价格显然是越低越好，因此此问题可归结为以下数学模型：目标函数MinW = 30y1 + 60 y2+ 24y3y1 + 3y2 40约束条件s.t2y1 + 2 y2+ 2y3 50y1 , y2 , y3 0原问题，此问题为对偶问题，y1 , y2 , y3为对偶变量，也称为影子价格2011-8-197(2)对偶问题的形式定义设原线性规划问题为MaxZc1x1c2x2cnxna11x1a12x2a1nxnb1a21x1a22x2a2nxnb2axaxaxbm11m22mnnmxj0j1,2,,n则称下列线性规划问题MinWb1y1b2y2bmyma11y1a21y2am1ymc1a12y1a22y2am2ymc2ayayayc2n2mnmn1n1yi0i1,2,,ms.ts.t为其对偶问题，其中yi(i=1,2,…,m)称为对偶变量。上述对偶问题称为对称型对偶问题。原问题简记为(P)，对偶问题简记为(D)2011-8-198 原始问题Max Z=CXs.t.AX≤bX≥0MaxC对偶问题Min W=Ybs.t.YAT≥CY ≥0MinbTATm≥CTmAn≤bn2011-8-199 上式已为对称型对偶问题，故可写出它的对偶规划Mins.t7y19y2Z7y13y14y253y12y1y262y1,y1,y20y1则上式化为Maxs.tZ5x16x23x12x274x1x29x1,x20令y1y1y1Mins.tZ7y19y23y14y252y1y26y无限制,y0212011-8-1913 对偶关系对应表原问题目标函数类型目标函数系数与右边项的对应关系变量数与约束数的对应关系原问题变量类型与对偶问题约束类型的对应关系原问题约束类型与对偶问题变量类型的对应关系变量目标函数系数右边项系数对偶问题右边项系数目标函数系数Max Min变量数n 约束数n约束数m 变量数m0 0 约束无限制＝约束＝0 变量0 无限制2011-8-1914 4.2 对偶问题的基本性质Maxs.tZCXAXbX0对偶的定义Mins.tWYbYACY0Mins.tZCX-AX-bX0对偶的定义Maxs.tWYb-YACY02011-8-1915 定理4(主对偶定理)若一对对偶问题(P)和(D)都有可行解，则它们都有最优解，且目标函数的最优值必相等。证明：(1)当X*和Y*为原问题和对偶问题的一个可行解有AXbYAXYbYACYAXCX对偶问题目标函数值原问题目标函数值CXYAXYb所以原问题的目标函数值有上界，即可找到有限最优解；对偶问题有下界，也存在有限最优解。2011-8-1917(2)当X*为原问题的一个最优解，B为相应的最优基,通过引入松弛变量Xs,将问题(P)转化为标准型Maxs.tZCX0XsAXIXsbX,Xs01令X*ˆ*XXsC0CBBCBB10AICCBB1ACBB10CBB0令YCBB0CYA0YAC11CCBB1A0所以Y*是对偶问题的可行WYbCBB1b解，对偶问题的目标函数值为X*是原问题的最优解，原问题的目标函数值为2011-8-19ZWZCXCBB1b18 推论：若一对对偶问题中的任意一个有最优解，则另一个也有最优解，且目标函数最优值相等。一对对偶问题的关系，有且仅有下列三种：1.都有最优解，且目标函数最优值相等；2.两个都无可行解；3.一个问题无界，则另一问题无可行解。2011-8-1919 证:(必要性）原问题MaxZCXAXXsbs.tX,Xs0AXXsbXsbAXYAXYXsYb对偶问题WYbYAYscs.tY,Ys0YAYsCYsYACMinYAXYsXCXYXsYsX02011-8-1920 原始问题和对偶问题变量、松弛变量的维数Max Z=CXs.t.AX+XS=bX, XS≥0Min W=Ybs.t.ATY-YS=CW, WS≥0nXmYmXSAYSI=bXYS=0YTXS=02011-8-19TnATm-I=Cn21 原始问题的变量原始问题的松弛变量x1xjxnxn+1xn+ixn+my1yiymym+1ym+jyn+m对偶问题的变量对偶问题的松弛变量xjym+j=02011-8-19yixn+i=0(i=1,2,…,m;j=1,2,…,n)在一对变量中，其中一个大于0，另一个一定等于022 4.3 对偶问题的解Max设原问题为s.tZCX0XsX*为原问ˆ*题的一AXIXsb令XXs最优解X,Xs0MinWYb则YCBB1为对偶问题s.tYAC的一最优解Y0C基系数CB基变量XBCBXBI0CNXNB-1NCN-CBB-1N0XsB-1-CBB-1解B-1bCBB-1bσ2011-8-1923 例1Max Z=40X1+ 50X2 Min W = 30y1+ 60y2 + 24y3X1+2X2 30y1y1+3y2 + 0y3403X1+2X2 60y2s.t2y1+2y2 + 2y350s.t2X2 24y3y1 , y2 , y3 0X1 , X2 0Max W’=-30y1-60y2-24y3y1+3y2 + 0y3 –y4=402ys.t1+2y2 + 2y3–y5=50y1 , y2 , y3 , y4 , y5 02011-8-1924 Max W’=-30y1-60y2-24y3 +0(y4 +y5)-M(y6 +y7)y1+3y2 + 0y3 –y4 +y6=402y1+2y2 + 2y3–y5+y7=50s.ty1 , y2 , y3 , y4 , y5 0cjcB-M-Mσj-30yBy6y7y112-60y232-24y3022M-240y4-10-M0y50-1-M-My6100-My7010B-1b4050-90Mθ40/350/23M-305M-602011-8-1925 cjcB-60-Mσ-60-24σ-60-30σjjj-30yBy2y7y11/34/34M/3-10-60y2100-24y3022M-240y4-1/32/32M/3+200y50-1-M-My61/3-2/3-5M/3+20-My7010B-1b40/370/3800-70M/3θ35/3y2y3y2y11/32/36100010-1/31/3-120-1/2-121/3-1/3-M+1201/2-M+1240/335/3-10804035/2010100-1/23/2-9-1/21/2-151/4-3/4-15/21/2-1/2-M+30-1/43/4-M-15/215/235/2-9752011-8-1926 例

1、Max Z=40X1+ 50X2 X1+2X2 303X1+2X2 60s.ts.t2X2 24X1 , X2 0cjcB40050σjX1+2X2 +X3 = 303X1+2X2 +X4 =602X2 +X5 = 24X1 –X5 00x4-1/2-1/21/4-15/20 x50100B-1b15915/297540xBx1x5x2x1100050x200100x31/23/2-3/4-35/22011-8-1927 X*015x10152x2-3520x3-1520x409x5Y*y13520y21520y309y4015y50152282011-8-19 例2对于线性规划问题Minw2x13x25x32x43x5x1x22x3x43x54s.t2x1x23x3x4x53x0,j1,2,3,4,5j43已知其对偶问题的最优解为y*;z5。55试求原问题的最优解。解：可采用两种方法求解：122011-8-19单纯形法；应用对偶理论；现应用对偶理论求解。29 首先写出原问题的对偶问题如下：Maxz4y13y21y12y22yy32212y13y2534y1y223yy3512y1，y20x1x2x3x4x5s.t43234为严格将最优解y*代入约束条件，得5515为等式；根据互补松弛不等式，定理可知:****x*2x3x40,x10,x50;同理，原问题的两个约束条件为等式，故有：2011-8-1930 **x13x54**2x1x53*求解后得到：x*，x51。11所以原问题的最优解为：x*10001w*5T2011-8-1931 例3Maxs.tz2x13x25x3x1x2x372x15x2x310x1,x2,x30解：Maxs.tz2x13x25x3Mx4x6x1x2x3x472x15x2x3x5x610xj0,j1,,62011-8-1932 cjcB-M-Mσ-M2σ32σjjj2xBx4x6x4x1x2x1x1123M+23x21-5-4M+3-5x3112M-5-Mx41001002/75/70 x50-1M1/2-1/21/7-1/7-1/7-M x6010-1/21/2-1/71/7-M+1/7B-1b710-17M254/745/7102/7θ754/70100107/2-5/21001/21/21/76/77M/2+8M/2-6M/2+1-3M/2-110-2M-50/7-M-16/72011-8-1933 Max(P)s.tz2x13x25x3x1x2x372x15x2x310x1,x2,x30Mins.tw7y110y2y12y22y15y23y1y25y1无限制,y20Mins.tw7y110y2y12y2y32y15y2y43y1y2y55y1无限制,y20,y3,y4,y502011-8-1934 σx0457x1047x2507016M70x4171M70x60x5x3yy1167y217y30y40y5507YCss2011-8-1935 4.4 影子价格(1)原始问题是利润最大化的生产计划问题总利润(元)单位产品的利润(元/件)产品产量(件)资源限量(吨)Maxa11x1a21x1axm11x1,s.tzc1x1cnxnb1a1nxnxn100b2a2nxn0xn20amnxn00xnmbmxn,xn1,xn2,xnm0单位产品消耗的资源(吨/件))剩余的资源(吨)消耗的资源(吨)2011-8-1936(2)对偶问题原始和对偶问题都取得最优解时，最大利润Max z=Min w总利润(元)资源限量(吨)资源价格(元/吨)Mina11y1a12y1ay1n1y1,s.twb1ybmymc1am1ymym100c2am2ym0ym20amnym00-ymncnym,ym1,ym2,ymn0对偶问题是资源定价问题，对偶问题的最优解y1、y2、...、ym称为m种资源的影子价格（Shadow Price）2011-8-1937(3)资源影子价格的性质zwb1y1b2y2biyibmymzzb1y1b2y2(bibi)yibmymzbiyi■影子价格越大，说明这种资源越是相对紧缺■影子价格越小，说明这种资源相对不紧缺■如果最优生产计划下某种资源有剩余，这种资源的影子价格一定等于02011-8-1938 X2x12x230x12x231X=(14.5,8.25)Z=992.5X=(15,7.5)Z=9752x224X=(15.5,7.25)Z=982.503x12x2603x12x261X1392011-8-19(4)产品的机会成本maxzs.t.c1x1a11x1a21x1am1x1x1c2x2a12x2a22x2am2x2x2增加单位资源可以增加的利润cjxja1jxja2jxjcnxna1nxna2nxnxnb1y1b2y2bmym0xjamjxjamnxn减少一件产品可以节省的资源机会成本a1jy1a2jy2aijyiamjym表示减少一件产品所节省的资源可以增加的利润2011-8-1940(5)产品的差额成本（Reduced Cost）机会成本差额成本利润MinWb1y1b2y2bmyms.t.a11y1a21y2am1ymym1a12y1a22y2am2yma1ny1a2ny2amnymy1y2ymym1ym2ym2c1c2ymncnymn0差额成本=机会成本-利润2011-8-1941(6)互补松弛关系的经济解释y0xni0yixni0ixni0yi0xj0ymj0xjymj0ymj0xj0在利润最大化的生产计划中（1）边际利润大于0的资源没有剩余（2）有剩余的资源边际利润等于0（3）安排生产的产品机会成本等于利润（4）机会成本大于利润的产品不安排生产2011-8-1942 4.5 对偶单纯形法(1)对偶单纯形法的基本原理定义：设A=(B N)，其中B是一个非奇异的m×m阶方阵，对应地C=(CBCN)，则YB=CB的解Y*=CBB-1称为对偶问题(D)的一个基本解；若Y*还满足Y*N≧CN，则称Y*为(D)的一个基可行解；若有Y*N>CN，则称Y*为非退化的基可行解，否则称为退化的基可行解。定义：如果原问题(P)的一个基本解X与对偶问题(D)的基可行解Y对应的检验数向量满足条件则称X为原问题(P)的一个正则解。原问题(P)的基本解X与对偶问题(D)的基本解Y一一对应原问题(P)的正则解X与对偶问题(D)的基可行解Y一一对应原问题(P)的最优解X*与对偶问题(D)的最优解Y*一一对应2011-8-1943 原问题解空间对偶问题解空间可行解最优解基本解正则解基可行解基可行解正则解基本解可行解2011-8-1944 对偶单纯形法的基本思想从原规划的一个基本解出发，此基本解不一定可行(正则解)，但它对应着一个对偶基可行解（检验数非正），所以也可以说是从一个对偶基可行解出发；然后检验原规划的正则解是否可行，即是否有负的分量，如果有小于零的分量，则进行迭代，求另一个正则解，此正则解对应着另一个对偶基可行解（检验数非正）。如果得到的正则解的分量皆非负则该正则解为最优解。也就是说，对偶单纯形法在迭代过程中始终保持对偶解的可行性（即检验数非正），使原规划的正则解由不可行逐步变为可行，当同时得到对偶规划与原规划的可行解时，便得到原规划的最优解。2011-8-1945