欢迎来到麦多课文档分享! | 帮助中心 海量文档,免费浏览,给你所需,享你所想!
麦多课文档分享
全部分类
  • 标准规范>
  • 教学课件>
  • 考试资料>
  • 办公文档>
  • 学术论文>
  • 行业资料>
  • 易语言源码>
  • ImageVerifierCode 换一换
    首页 麦多课文档分享 > 资源分类 > PPT文档下载
    分享到微信 分享到微博 分享到QQ空间

    第四章 对偶原理.ppt

    • 资源ID:380210       资源大小:1.46MB        全文页数:80页
    • 资源格式: PPT        下载积分:2000积分
    快捷下载 游客一键下载
    账号登录下载
    微信登录下载
    二维码
    微信扫一扫登录
    下载资源需要2000积分(如需开发票,请勿充值!)
    邮箱/手机:
    温馨提示:
    如需开发票,请勿充值!快捷下载时,用户名和密码都是您填写的邮箱或者手机号,方便查询和重复下载(系统自动生成)。
    如需开发票,请勿充值!如填写123,账号就是123,密码也是123。
    支付方式: 支付宝扫码支付    微信扫码支付   
    验证码:   换一换

    加入VIP,交流精品资源
     
    账号:
    密码:
    验证码:   换一换
      忘记密码?
        
    友情提示
    2、PDF文件下载后,可能会被浏览器默认打开,此种情况可以点击浏览器菜单,保存网页到桌面,就可以正常下载了。
    3、本站不支持迅雷下载,请使用电脑自带的IE浏览器,或者360浏览器、谷歌浏览器下载即可。
    4、本站资源下载后的文档和图纸-无水印,预览文档经过压缩,下载后原文更清晰。
    5、试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓。

    第四章 对偶原理.ppt

    1、第四章 对偶原理,窗含西岭千秋雪,门泊东吴万里船对偶是一种普遍现象,2,x1x2x3,y1 y2 y3 y4,假设工厂考虑不进行生产而把全部可利用的资源都让给其他企业,工厂希望给这些资源定出一个合理的价格,即使别的单位愿意购买,又使本工厂能得到生产这些产品所能获得的最大收益。,3,二、对偶问题的表达,(1)对称LP问题的定义,(2)对称LP问题的对偶问题,第一类对称形式,第二类对称形式,(L),(D),4,例1:写出下列LP问题的对偶问题,对偶,5,(3)对偶问题的对偶,推导过程,变形,(D),6,对偶,变形,结论:对偶问题的对偶为原问题。,(DD),7,写出下列LP问题的对偶问题:,例2:,

    2、8,写出对称形式的对偶规划的要点: (1) min变成max (2) 价值系数与右端向量互换 (3) 系数矩阵转置 (4) 变 原问题中约束条件的个数=对偶问题中变量的个数 原问题中变量的个数=对偶问题中约束条件的个数,9,非对称形式的对偶,写成对称形式,对偶问题为:,10,例 min 5x1+4x2+3x3s.t. x1+x2+x3=43x1+2x2+x3 =5x1 0, x2 0, x3 0 对偶问题为max 4w1+5w2s.t. w1+3w25w1+2w2 4w1+w2 3,11,一般情形LP问题的对偶问题,min cx s.t. A1x b1 A1 为m1n , b1为m11A2x

    3、=b2 A2 为m2n , b2为m21A3x b3 A3 为m3n , b3为m31x 0 引入松弛变量min cxs.t. A1x xs =b1 xs为m11A2x =b2 A3x +xt = b3 xt为m31x, xs , xt 0,12,min cx s.t. A1x xs =b1 xs为m11A2x =b2 A3x +xt = b3 xt为m31x, xs , xt 0 对偶问题为 max w1b1+ w2b2 + w3b3 s.t. w1A1+ w2A2 + w3A3 c w1Is 0w3It 0max w1b1+ w2b2 + w3b3s.t. w1A1+ w2A2 + w3A

    4、3 cw1 0, w3 0,13,min max 变 0 约 量 0 束无限制 = 方程 约 0 束 0 变 方 = 无限制 量 程,14,15,直接写出LP问题的对偶问题,例3,16,17,第二节 对偶问题的基本性质,原问题(L) 对偶问题(D) min cx max wbs.t. Ax b s.t. wA cx 0 w 0,18,定理1:弱对偶定理,19,例:,1)原问题任一可行解 x=(1, 1)T,(LP),目标值 =40,40是DLP问题最优目标值的上界.,2)对偶问题任一可行解 w=(1 1 1 1)目标值 =1010是LP问题最优目标值的下界.,20,推论1:,若LP(或DLP)

    5、问题有无界解,则其对偶问题(或原问题)无可行解; 若LP (或DLP)问题无可行解,则对偶问题(或原问题)或者无可行解,或者目标函数值趋于无穷。,推论2:,极大化问题的任何一个可行解所对应的目标 函数值都是其对偶问题的目标函数值的下界。,极小化问题的任何一个可行解所对应的目标 函数值都是其对偶问题的目标函数值的上界。,推论3:,21,定理2:最优性准则,证明:,22,例5,23,定理3:强对偶定理,若(L),(D)均有可行解,则(L),(D)均有最 优解,且(L),(D)的最优目标函数值相等.,证明:,24,(L),引入剩余变量,把(L)化为标准形,25,26,推论:,在用单纯形法求解LP问题

    6、(L)的最优单纯 形表中松弛变量的检验数的相反数(单纯形 乘子w=cBB-1)就是其对偶问题(D)的最优解,27,方法,由于(L) 化成标准形式时,松弛变量xn+j对应的列为-ej,它在目标函数中的价格系数,所以, 判别数cBB-1(-ej)-0=-wj 则松弛变量对应的判别数均乘以(-1),变得到单纯形乘子w=(w1,wm). 当原问题达最优时,单纯形乘子即为对偶问题的最优解.,28,解:化为标准型,例5 求下列问题对偶问题的最优解,29,4,1,30,2,此时达到最优解。x*=(4,2), MaxZ=14。,31,(L),(DL),32,小结,原问题(min) 对应关系 对偶问题(max)

    7、,有最优解,有最优解,无界解,不可行,不可行,无界解,33,(无可行解),(无可行解),34,(无界解),(无可行解),35,定理4:互补松驰定理,36,证明:(必要性),37,证明:(充分性),38,定理4:互补松驰定理(非对称形式),39,例6 考虑下面问题,40,解:,则,,41,1、定义,对偶问题的经济学解释:影子价格,2、含义,考虑在最优解处,右端项bi的微小变动对目标函数值的影响.,42,若把原问题的约束条件看成是广义的资源约束,则右端项的值表示每种资源的可用量. 对偶解的经济含义:资源的单位改变量引起目标函数值的增加量. 通常称对偶解为影子价格. 影子价格的大小客观地反映了资源在

    8、系统内的稀缺程度.资源的影子价格越高,说明资源在系统内越稀缺,而增加该资源的供应量对系统目标函数值贡献越大.,43,木门 木窗 木工 4小时 3小时 120小时/日 油漆工 2小时 1小时 50小时/日 收入 56 30 解:设该车间每日安排 x1 x2 x3 x4 生产木门x1扇,木窗x2。 x3 4 3 1 0 120 max z=56 x1 +30 x2 x4 2 1 0 1 50s.t. 4 x1 +3 x2120 -56 -30 0 0 02 x1 + x2 50 x3 0 1 1 -2 20x1 x2 0 x1 1 1/2 0 1/2 250 -2 0 28 1400x2 0 1

    9、1 -2 20x1 0 0 -1/2 -1/2 150 0 2 24 1440,对偶问题的解为: w*=(2, 24),44,(2)告诉管理者花多大代价购买进资源或卖出资源是合适的,3、影子价格的作用,(1)告诉管理者增加何种资源对企业更有利,(3)为新产品定价提供依据,45,对偶单纯形法,定义:设x(0)是(L)的一个基本解(不一定是可行解),它对应的矩阵为B,记w=cBB-1,若w是(L)的对偶问题的可行解,即对任意的j, wPj-cj 0,则称x(0)为原问题的对偶可行的基本解。 结论:当对偶可行的基本解是原问题的可行解时,由于判别数0,因此,它就是原问题的最优解。,46,基本思想: 从

    10、原问题的一个对偶可行的基本解出发; 求改进的对偶可行的基本解:每个对偶可行的基本解x=(xBT,0)T对应一个对偶问题的可行解w=cBB-1,相应的对偶问题的目标函数值为wb=cBB-1b,所谓改进的对偶可行的基本解,是指对于原问题的这个基本解,相应的对偶问题的目标函数值wb有改进(选择离基变量和进基变量,进行主元消去); 当得到的对偶可行的基本解是原问题的可行解时,就达到最优解。,47,与原单纯形法的区别: 原单纯形法保持原问题的可行性,对偶单纯形法保持所有检验数wPj-cj 0,即保持对偶问题的可行性。 特点:先选择出基变量,再选择进基变 量。,48,3、换基迭代,1. 化标准型,建立初始

    11、单纯形表,4、回到第2步,(若所有yrj0,则该LP无可行解),步骤:,49,50,51,-4,-13/4,52,用对偶单纯形法求解下列LP问题,解:原问题变形为,53,-1,-1,54,关于初始对偶可行的基本解,min cx s.t. Ax=bx 0 若初始对偶可行的基本解不易直接得到,则解一个扩充问题,通过这个问题的求解,给出原问题的解答。,55,方法,附加人工约束,56,57,58,显然, (2,3,-2,0,0) 不是对偶可行解, 所以加一个约束,59,60,方法一,x1 x2 x3 x4 x5 x6,1,-1,最优解为 (0,9,0,2,0) 最优值=-4,61,x1 x2 x3 x

    12、4 x5 x6,x1 x2 x3 x6,1 0 0 1 -2 0,0 1 0 -3 1 0,0 0 1 -1 -1 0,0 0 0 1 1 1,0 0 0 2 -4 0,1 0 0 0 -3 -1,0 1 0 0 4 3,0 0 1 0 0 1,0 0 0 1 1 1,0 0 0 0 -6 -2,-1/3 0 0 0 1 1/3,-4/3 1 0 0 0 5/3,0 0 1 0 0 1,1/3 0 0 1 6 2/3,-2 0 0 0 0 0,x1 x2 x3 x4,x5 x2 x3 x4,2 3 -2 M,2-M 3+3M M-2 M,(M-2)/3 17/3+5M/3 M-2 2/3+2M

    13、/3,0,-2M,-4,1,-3,方法二,62,扩充问题有最优解,最优值=-4,原问题最优值=-4,原问题最优解为,最优值=-4,63,用对偶单纯形法解下列问题,64,最优表为:,扩充问题的最优解是:,65,原始-对偶算法,基本思想: 从对偶问题的一个可行解开始,同时计算原问题和对偶问题,试图求出原问题的满足互补松弛条件的可行解。,66,原问题:,对偶问题:,67,限定原始问题 Restricted primal problem,人工变量,68,限定原始问题的对偶问题,69,70,71,由于对偶问题无上界,所以原问题无可行解。,72,计算步骤,73,74,限定原始问题目标函数值,对偶问题可行解为w时所有的wpj-cj,对偶问题函数值f=wb,75,用原始-对偶算法解下列问题,解:对偶问题为,76,限定原始问题为:,77,78,1,79,80,


    注意事项

    本文(第四章 对偶原理.ppt)为本站会员(registerpick115)主动上传,麦多课文档分享仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知麦多课文档分享(点击联系客服),我们立即给予删除!




    关于我们 - 网站声明 - 网站地图 - 资源地图 - 友情链接 - 网站客服 - 联系我们

    copyright@ 2008-2019 麦多课文库(www.mydoc123.com)网站版权所有
    备案/许可证编号:苏ICP备17064731号-1 

    收起
    展开