《对偶理论》PPT课件

《《对偶理论》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

第四章　对偶原理窗含西岭千秋雪，门泊东吴万里船对偶是一种普遍现象 x1x2x3y1y2y3y4甲　乙　丙　丁材料产品３　２　１　１４　１　３　２２　２　３　４ABC每台收益200040003000限额600400200300假设工厂考虑不进行生产而把全部可利用的资源都让给其他企业，工厂希望给这些资源定出一个合理的价格，即使别的单位愿意购买，又使本工厂能得到生产这些产品所能获得的最大收益。2 二、对偶问题的表达（1）对称LP问题的定义（2）对称LP问题的对偶问题第一类对称形式第二类对称形式(L)(D)3 例1：写出下列LP问题的对偶问题对偶4 （3）对偶问题的对偶推导过程变形(D)5 对偶变形结论：对偶问题的对偶为原问题。(DD)6 写出下列LP问题的对偶问题：例2：7 写出对称形式的对偶规划的要点：(1)min变成max(2)价值系数与右端向量互换(3)系数矩阵转置(4)≥变≤原问题中约束条件的个数=对偶问题中变量的个数原问题中变量的个数=对偶问题中约束条件的个数8 非对称形式的对偶写成对称形式对偶问题为：9 例min5x1+4x2+3x3s.t.x1+x2+x3=43x1+2x2+x3=5x1≥0,x2≥0,x3≥0对偶问题为max4w1+5w2s.t.w1+3w2≤5w1+2w2≤4w1+w2≤310 一般情形LP问题的对偶问题mincxs.t.A1x≥b1A1为m1×n,b1为m1×1A2x=b2A2为m2×n,b2为m2×1A3x≤b3A3为m3×n,b3为m3×1x≥0引入松弛变量mincxs.t.A1x–xs=b1xs为m1×1A2x=b2A3x+xt=b3xt为m3×1x,xs,xt≥011 mincxs.t.A1x–xs=b1xs为m1×1A2x=b2A3x+xt=b3xt为m3×1x,xs,xt≥0对偶问题为maxw1b1+w2b2+w3b3s.t.w1A1+w2A2+w3A3≤c–w1Is≤0w3It≤0maxw1b1+w2b2+w3b3s.t.w1A1+w2A2+w3A3≤cw1≥0,w3≤012 minmax变≥0≤约量≤0≥束无限制=方程约≥≥0束≤≤0变方=无限制量程13 14 直接写出LP问题的对偶问题例315 16 第二节对偶问题的基本性质原问题(L)对偶问题(D)mincxmaxwbs.t.Ax≥bs.t.wA≤cx≥0w≥017 定理1：弱对偶定理18 例：1）原问题任一可行解x=(1,1)T（LP）目标值=4040是DLP问题最优目标值的上界.2）对偶问题任一可行解w=（1111）目标值=1010是LP问题最优目标值的下界.19 推论1：若LP(或DLP)问题有无界解，则其对偶问题(或原问题)无可行解；若LP(或DLP)问题无可行解，则对偶问题(或原问题)或者无可行解,或者目标函数值趋于无穷。推论2：极大化问题的任何一个可行解所对应的目标函数值都是其对偶问题的目标函数值的下界。极小化问题的任何一个可行解所对应的目标函数值都是其对偶问题的目标函数值的上界。推论3：20 定理2：最优性准则证明：21 例522 定理3：强对偶定理若(L),(D)均有可行解,则(L),(D)均有最优解,且(L),(D)的最优目标函数值相等.证明：23 (L)引入剩余变量，把(L)化为标准形．24 25 推论：在用单纯形法求解LP问题（L）的最优单纯形表中松弛变量的检验数的相反数(单纯形乘子w=cBB-1)就是其对偶问题（D）的最优解26 方法由于(L)化成标准形式时,松弛变量xn+j对应的列为-ej，它在目标函数中的价格系数＝０，所以，判别数＝cBB-1(-ej)-0=-wj则松弛变量对应的判别数均乘以(-1)，得到单纯形乘子w=(w1,…,wm).当原问题达最优时,单纯形乘子即为对偶问题的最优解.27 解：化为标准型例5求下列问题对偶问题的最优解28 x1x2x3x4x5121004001004001-2-3000x3x4x58161201010-1/24001001001/4-20003/4x3x4x2216394129 x1x2x3x4x51010-1/200-41201001/40020-1/4x1x4x22831321001/4000-21/21011/2-1/80003/21/80x1x5x244214此时达到最优解。x*=(4,2),MaxZ=14。30 (L)(DL)31 小结原问题(min)对应关系对偶问题(max)有最优解有最优解无界解不可行不可行无界解32 （无可行解）（无可行解）w1w2l2l1x1x2l1l233 （无界解）（无可行解）l2x1x2l1zy1y2l1l234 定理4：互补松驰定理35 证明：（必要性）36 证明：（充分性）37 定理4’：互补松驰定理(非对称形式）38 例6考虑下面问题39 解:则，40 1、定义对偶问题的经济学解释：影子价格2、含义考虑在最优解处,右端项bi的微小变动对目标函数值的影响.41 若把原问题的约束条件看成是广义的资源约束,则右端项的值表示每种资源的可用量.对偶解的经济含义:资源的单位改变量引起目标函数值的增加量.通常称对偶解为影子价格.影子价格的大小客观地反映了资源在系统内的稀缺程度.资源的影子价格越高,说明资源在系统内越稀缺,而增加该资源的供应量对系统目标函数值贡献越大.42 木门木窗木工4小时3小时120小时/日油漆工2小时1小时50小时/日收入5630解：设该车间每日安排x1x2x3x4生产木门x1扇，木窗x2。x34310120maxz=56x1+30x2x4210150s.t.4x1+3x2≤120-56-300002x1+x2≤50x3011-220x1x2≥0x111/201/2250-20281400x2011-220x100-1/2-1/215002241440对偶问题的解为:w*=(2,24)43 （2）告诉管理者花多大代价购买进资源或卖出资源是合适的3、影子价格的作用（1）告诉管理者增加何种资源对企业更有利（3）为新产品定价提供依据44 对偶单纯形法定义：设x(0)是(L)的一个基本解（不一定是可行解），它对应的矩阵为B，记w=cBB-1，若w是(L)的对偶问题的可行解，即对任意的j,wPj-cj≤0，则称x(0)为原问题的对偶可行的基本解。结论：当对偶可行的基本解是原问题的可行解时，由于判别数≤0，因此，它就是原问题的最优解。45 所以，x(0)为对偶可行的基本解。46 基本思想：从原问题的一个对偶可行的基本解出发；求改进的对偶可行的基本解：每个对偶可行的基本解x=(xBT,0)T对应一个对偶问题的可行解w=cBB-1，相应的对偶问题的目标函数值为wb=cBB-1b，所谓改进的对偶可行的基本解，是指对于原问题的这个基本解，相应的对偶问题的目标函数值wb有改进（选择离基变量和进基变量，进行主元消去）；当得到的对偶可行的基本解是原问题的可行解时，就达到最优解。47 与原单纯形法的区别：原单纯形法保持原问题的可行性，对偶单纯形法保持所有检验数wPj-cj≤0，即保持对偶问题的可行性。特点：先选择出基变量，再选择进基变量。48 3、换基迭代1.化标准型,建立初始单纯形表4、回到第2步(若所有yrj≥0,则该LP无可行解）步骤：49 50 51 x1x2x3x4x5-3-1-1101-4-101-1-1-100x4x5-1-20-4-13/40-3/41-1/4-1/411/40-1/4-5/40-3/40-1/4x4x2-1/21/21/2-13/4103/13-4/131/13014/13-1/13-3/1300-6/13-5/13-2/13x1x22/137/139/1352 用对偶单纯形法求解下列LP问题解：原问题变形为53 x1x2x3x4x5x6-11-11001120100-11001x4x5x6-1-2-3000-48-201-11-1000211100-11001x1x5x60-3-2-10044-24-1-1100-10-100311201-100-1x1x5x200-5-10-36021054 关于初始对偶可行的基本解mincxs.t.Ax=bx≥0若初始对偶可行的基本解不易直接得到，则解一个扩充问题，通过这个问题的求解，给出原问题的解答。55 方法附加人工约束56 57 58 59 x1x2x3x4x5x1x2x31001-2010-31001-1-10002-423-2-2显然，（2，3，-2，0，0）不是对偶可行解，所以加一个约束60 61 方法一x1x2x3x4x5x6-200000-4-1000313100-501010-301001-20x6x2x3x4M-2902x1x2x3x61001-20010-310001-1-100001110002-4023-2M01000-3-10100430010010001110000-6-2x1x2x3x42-M3+3MM-2M-2M1-1最优解为(0,9,0,2,0)最优值=-462 x1x2x3x4x5x6x1x2x3x61001-20010-310001-1-100001110002-401000-3-10100430010010001110000-6-2-1/300011/3-4/310005/30010011/300162/3-200000x1x2x3x4x5x2x3x423-2M2-M3+3MM-2M(M-2)/317/3+5M/3M-22/3+2M/30-2M-41-3方法二63 扩充问题有最优解最优值=-4原问题最优值=-4原问题最优解为最优值=-464 用对偶单纯形法解下列问题65 最优表为:扩充问题的最优解是:所以原问题无界。66 原始-对偶算法基本思想：从对偶问题的一个可行解开始，同时计算原问题和对偶问题，试图求出原问题的满足互补松弛条件的可行解。67 原问题：对偶问题：68 限定原始问题Restrictedprimalproblem人工变量69 限定原始问题的对偶问题70 71 72 由于对偶问题无上界，所以原问题无可行解。73 计算步骤74 75 限定原始问题目标函数值对偶问题可行解为w时所有的wpj-cj对偶问题函数值f=wb限定原始问题的判别数76 用原始-对偶算法解下列问题解：对偶问题为77 限定原始问题为：78 △△79 4230218005235103123012112121321--yyyyxxx△△△180 42302120-210121-11023012112221321--yxyyxxx△△△81 △△△△△△△△１82 解：它的对偶规划是83 限定原始问题为84 △△△85 △△△△△△86 87 △△△△△88 89