第二章-对偶问题.ppt
《第二章-对偶问题.ppt》由会员分享,可在线阅读,更多相关《第二章-对偶问题.ppt(47页珍藏版)》请在咨信网上搜索。
1、某工厂用三台设备生产两种产品,已知的条某工厂用三台设备生产两种产品,已知的条件如表所示,试制订总利润最大的生产计划件如表所示,试制订总利润最大的生产计划设备设备I产品产品II产品产品总有效台时总有效台时A2212B128C039单位产品的利单位产品的利润(千元)润(千元)23求求max引例引例1 1 生产计划问题生产计划问题换一角度:将设备卖出,售价定为多少适宜?换一角度:将设备卖出,售价定为多少适宜?原问题原问题对偶问题对偶问题两个互为对偶规划问题之间的关系两个互为对偶规划问题之间的关系(对称形对称形式)式)1)目标函数的目标互为相反。)目标函数的目标互为相反。(max,min)2)目目标标
2、函函数数的的系系数数是是另另一一个个约约束束条条件件右右端端的向量的向量 3)约约束束系系数数矩矩阵阵是是另另一一个个的的约约束束系系数数矩矩阵阵的转置的转置 4)约约束束方方程程的的个个数数与与另另一一个个的的变变量量的的个个数数相等相等max限定向量限定向量b价值向量价值向量Cm个约束,个约束,n个变量个变量约束条件约束条件“”变量变量“”原问题原问题对偶问题对偶问题min价值向量价值向量限定向量限定向量n个约束,个约束,m个变量个变量变量变量“”约束条件约束条件“”对称式对偶max限定向量限定向量b价值向量价值向量Cm个约束,个约束,n个变量个变量约束条件约束条件“=”原问题原问题对偶问
3、题对偶问题min价值向量价值向量限定向量限定向量n个约束,个约束,m个变量个变量变量自由变量变量自由变量非对称式对偶目标函数目标函数max原问题(对偶问题)原问题(对偶问题)对偶问题(原问题)对偶问题(原问题)目标函数目标函数min目标函数中变量的系数目标函数中变量的系数约束条件右端项约束条件右端项约束条件右端项约束条件右端项目标函数中变量的系数目标函数中变量的系数例例2:给出下列线性规划的对偶问题:给出下列线性规划的对偶问题:minZ=2X1+8X2-4X3X1+3X23X3=30-X1+5X2+4X3=80st.4X1+2X2-4X3=50X1=0,X3无约束无约束其对偶问题为:其对偶问题
4、为:MAXw=30y1+80y2+50y3y1-y2+4y3=2st.3y1+5y2+2y3=0,y2无约束,无约束,y30,Y20和松弛互补定理知和松弛互补定理知:X5,X6,=0从而从而,原问题的约束变为原问题的约束变为:2X3+3X4=203X3+2X4=20解此方程得解此方程得:X3=X4=4于是原问题的最优解为于是原问题的最优解为:(0,0,4,4)七、单纯形表的双重含义七、单纯形表的双重含义例例6:用单纯形法,解线性规划,:用单纯形法,解线性规划,(LP1)maxZ=2X1+X25X2=156X1+2X2=24st.X1+X2=0,X2=0对偶问题对偶问题为:(LP2)minW=1
5、5Y1+24Y2+5Y36Y2+Y3=2ST.5Y1+2Y2+Y3=1Y1=0,Y2=0基变量基变量X1X2X3X4X5解解X30015/4-15/2 15/2X11001/4-1/27/2X2010-1/4 3/23/2-Z(目标目标)000-1/4-1/2-17/2检验数全部检验数全部0,于是得到最优解为于是得到最优解为X=(7/2,3/2,15/2,0,0),最优值为最优值为:Z=17/2,把松弛变量的检验数的相反数把松弛变量的检验数的相反数(0,1/4,1/2)带带入对偶问题中入对偶问题中,看有什么规律看有什么规律?1、松松弛弛变变量量与与对对偶偶变变量量的的乘乘积积有有什什么么关关系
6、系?松弛变量与对偶变量的乘积松弛变量与对偶变量的乘积=0=02 2、对偶问题的最优解与什么对偶问题的最优解与什么对应对应?对对偶偶问问题题的的最最优优解解是是原原问问题题松松弛弛变变量量检检验数的相反数验数的相反数.结结论论:将将原原始始单单纯纯形形表表中中松松弛弛变变量量的的检检验数反号恰好得对应对偶问题的一个解。验数反号恰好得对应对偶问题的一个解。事实上,我们把原始问题写成事实上,我们把原始问题写成 (1)其对偶问题写成其对偶问题写成 (2)其中其中其中其中决策变量决策变量 和松弛变量和松弛变量 ,所对应的检验数分别为:所对应的检验数分别为:和和(不一定满足(不一定满足“0”条件)。条件)
7、。设设 为原始问题(为原始问题(1)的一个基本可行解)的一个基本可行解(不一定为最优解),它所对应的基矩阵为(不一定为最优解),它所对应的基矩阵为,令令这时两组检验数分别为:这时两组检验数分别为:和和再根据问题(再根据问题(2),这两组检验数可分别记为),这两组检验数可分别记为 上述对应关系如表上述对应关系如表2.在获得最优解之前,在获得最优解之前,及,及 的各分的各分量中至少有一大于零,即量中至少有一大于零,即 中至少有一个小于零。中至少有一个小于零。这时对应的对偶问题的解为非可行解。这时对应的对偶问题的解为非可行解。和和 即即 ,重要结论:重要结论:1.原始问题的单纯形表中,原始问题的松弛
8、变量原始问题的单纯形表中,原始问题的松弛变量的检验数对应于对偶问题的决策变量,而原始问题的检验数对应于对偶问题的决策变量,而原始问题的决策变量的检验数对应于对偶问题的松弛变量,的决策变量的检验数对应于对偶问题的松弛变量,只是符号相反;只是符号相反;此时对偶问题也同时获得最优解。此时对偶问题也同时获得最优解。和和 当原始问题获得最优解时,表明当原始问题获得最优解时,表明2.4 影子价格一、影子价格的含义一、影子价格的含义根据资源在生产中作出的贡献而作的估根据资源在生产中作出的贡献而作的估价。价。是对第是对第i 种资源实现最大利润的一种估计,种资源实现最大利润的一种估计,是对偶问题的最优解。是对偶
9、问题的最优解。二、影子价格的特点二、影子价格的特点 1.区别于市场价格,市场价格相对稳定;区别于市场价格,市场价格相对稳定;而影子价格不稳定,依赖于资源的利用。而影子价格不稳定,依赖于资源的利用。2.影子价格是一种边际价格。影子价格是一种边际价格。3.影子价格是一种机会成本。影子价格是一种机会成本。4.互补松弛定理指出:互补松弛定理指出:当某种资源未被充分利用,则该种资当某种资源未被充分利用,则该种资源的影子价格为源的影子价格为0;而当资源的影子价格不;而当资源的影子价格不为为0时,表明该种资源已耗尽。时,表明该种资源已耗尽。5.检验数的经济学含义。检验数的经济学含义。第第j种产品的种产品的单
10、位产值单位产值是生产该产品所是生产该产品所耗用的各种资源耗用的各种资源的影子价格,即的影子价格,即隐含成本。隐含成本。2.5 对偶单纯形法对偶单纯形法小结:在单纯形表格中小结:在单纯形表格中1.得到原问题的基本可得到原问题的基本可行解的同时,其检验行解的同时,其检验数的相反数就构成了数的相反数就构成了对偶问题的一个基本对偶问题的一个基本解。解。2.原原对对松弛变量松弛变量决策变量决策变量决策变量决策变量剩余变量剩余变量基变量基变量非基变量非基变量非基变量非基变量基变量基变量化标准型化标准型求一个对偶可求一个对偶可行基本解行基本解 检验最检验最优性优性是是结束结束否否换基换基 再确定入基变量:再
11、确定入基变量:先确定出基变量:先确定出基变量:bl=minbibi0,则对应,则对应xl出基;出基;则对应则对应xk入基。入基。对偶单纯形法步骤:对偶单纯形法步骤:00-15 -24 -5 0 0基基-15 -24 -5 0 00-5-6-2-1-11001 -2 -1-24 0-15 0 -1 -4 00-5101/6-2/3-1/6-1/3011/3-1/3-24-5-15/2 0 0 -7/2 -3/2-5/415/21001-1/4 1/21/4-3/21/41/2Min问题问题基基2 1 0 0 0061521100010 0 0 1 15 24 50002 1 0 0 000101
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第二 对偶 问题
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【精****】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【精****】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。