《运筹学》对偶理论ppt.ppt
《《运筹学》对偶理论ppt.ppt》由会员分享,可在线阅读,更多相关《《运筹学》对偶理论ppt.ppt(73页珍藏版)》请在咨信网上搜索。
1、第第3章章 线性规划对偶理论及其应用线性规划对偶理论及其应用 线性规划的对偶模型对偶性质对偶问题的经济解释影子价格对偶单纯形法 本章主要内容:线性规划的对偶模型线性规划的对偶模型设某工厂生产两种产品甲和乙,生产中需设某工厂生产两种产品甲和乙,生产中需4种设备按种设备按A,B,C,D顺序加工,每件产品加工所需的机时数、每件产品的利润值顺序加工,每件产品加工所需的机时数、每件产品的利润值及每种设备的可利用机时数列于下表及每种设备的可利用机时数列于下表:产品数据表 设备设备产品产品ABCD产品利润产品利润(元件)(元件)甲甲 21402乙乙 22043设备可利用设备可利用机时数(时)机时数(时)12
2、81612问:充分利用设备机时,工厂应生产甲和乙型产品各多少件才能获得最大利润?1.对偶问题的现实来源对偶问题的现实来源线性规划的对偶模型线性规划的对偶模型解:设甲、乙型产品各生产解:设甲、乙型产品各生产x1及及x2件,则数学模型为:件,则数学模型为:反过来问:若厂长决定不生产甲和乙型产品,决定出租机器用于接受外加工,只收加工费,那么种机器的机时如何定价才是最佳决策?线性规划的对偶模型线性规划的对偶模型在市场竞争的时代,厂长的最佳决策显然应符合两条:在市场竞争的时代,厂长的最佳决策显然应符合两条:(1)不吃亏原则。即机时定价所赚利润不能低于加工甲、乙型)不吃亏原则。即机时定价所赚利润不能低于加
3、工甲、乙型产品所获利润。由此原则,便构成了新规划的不等式约束条件。产品所获利润。由此原则,便构成了新规划的不等式约束条件。(2)竞争性原则。即在上述不吃亏原则下,尽量降低机时总收)竞争性原则。即在上述不吃亏原则下,尽量降低机时总收费,以便争取更多用户。费,以便争取更多用户。设A、B、C、D设备的机时价分别为y1、y2、y3、y4,则新的线性规划数学模型为:线性规划的对偶模型线性规划的对偶模型把同种问题的两种提法所获得的数学模型用表把同种问题的两种提法所获得的数学模型用表2表示,将会发表示,将会发现一个有趣的现象。现一个有趣的现象。原问题与对偶问题对比表A(y1)B(y2)C(y3)D(y4)甲
4、(甲(x1)21402乙(乙(x2)220431281612 min max z 线性规划的对偶模型线性规划的对偶模型2.原问题与对偶问题的对应关系原问题与对偶问题的对应关系原问题(对偶问题)对偶问题(原问题)线性规划的对偶模型线性规划的对偶模型(1)对称形式)对称形式特点:目标函数求极大值时,所有约束条件为号,变量非负;目标函数求极小值时,所有约束条件为号,变量非负.已知P,写出D线性规划的对偶模型线性规划的对偶模型例例.写出线性规划问题的对偶问题写出线性规划问题的对偶问题解:首先将原问题变形为对称形式线性规划的对偶模型线性规划的对偶模型线性规划的对偶模型线性规划的对偶模型(2)非对称型对偶
5、问题若给出的线性规划不是对称形式,可以先化成对称形式再写对偶问题。也可直接写出非对称形式的对偶问题。线性规划的对偶模型线性规划的对偶模型原问题(或对偶问题)原问题(或对偶问题)对偶问题(或原问题)对偶问题(或原问题)约束条件右端项约束条件右端项目标函数变量的系数目标函数变量的系数目标函数变量的系数目标函数变量的系数约束条件右端项约束条件右端项目标函数目标函数 max目标函数目标函数 min约约束束条条件件m个个m个个变变量量00=无约束无约束变变量量n个个n个个约约束束条条件件00无约束无约束=线性规划的对偶模型线性规划的对偶模型例例2 写出下列线性规划问题的对偶问题写出下列线性规划问题的对偶
6、问题.解:原问题的对偶问题为资源定价问题(LP2)比较原问题(生产计划)对偶问题(资源定价)规范形式的线性规划问题规范形式的线性规划问题原问题(LP)对偶问题(DLP)规范形式最大化问题:约束条件全为型决策变量全部非负最小化问题:约束条件全为型决策变量全部非负规范形式的对偶关系原问题对偶问题目标函数:max CX目标函数:minbYm个约束条件:AX bm个决策变量:Y 0n个决策变量:X 0n个约束条件:AY C原问题对偶问题非规范形式的对偶关系对非规范形式的对偶关系,只需对上述表进行相应修改即可:例如对于一个最小化问题,若某个决策变量yi 0,则期对偶的约束条件为型的;若其某个约束条件是型
7、,则其对应的对偶变量是非正的.非规范形式线性规划的对偶问题非规范形式线性规划的对偶问题非规范形式线性规划的对偶问题非规范形式线性规划的对偶问题1 变量取值范围不符合非负要求的情况非规范形式线性规划的对偶问题非规范形式线性规划的对偶问题非规范形式线性规划的对偶问题非规范形式线性规划的对偶问题2 约束方程不是“”的情况 总结总结总结总结约束条件对变量,变量对约束条件;正常对正常,不正常对不正常;变量正常是非负,约束条件正常看目标(max ,min)。课堂作业:求解下面线性规划的对偶规划课堂作业:求解下面线性规划的对偶规划LPDLP对偶性质对偶性质例3 分别求解下列2个互为对偶关系的线性规划问题分别
8、用单纯形法求解上述2个规划问题,得到最终单纯形表如下表:对偶性质对偶性质XBb原问题的变量原问题的变量原问题的松弛变量原问题的松弛变量x1x2x3x4x5x315/20015/4-15/2x17/21001/4-1/2x23/2010-1/43/20001/41/2XBb对偶问题的变量对偶问题的变量对偶问题的剩余变量对偶问题的剩余变量y1y2y3y4y5y21/4-4/510-1/41/4y31/215/2011/2-3/215/2007/23/2原问题最优表对偶问题最优表对偶性质对偶性质原问题与其对偶问题的变量与解的对应关系:原问题与其对偶问题的变量与解的对应关系:原问题与其对偶问题的变量与
9、解的对应关系:原问题与其对偶问题的变量与解的对应关系:在单纯形表中,原问题的松弛变量对应对在单纯形表中,原问题的松弛变量对应对偶问题的变量,对偶问题的剩余变量对应原问偶问题的变量,对偶问题的剩余变量对应原问题的变量。题的变量。对偶性质对偶性质性质1 对称性定理:对偶问题的对偶是原问题 min W=Y bs.t.YA C Y 0max Z=C Xs.t.AXb X 0对偶性质对偶性质性质2 弱对偶原理(弱对偶性):设 和 分别是问题(P)和(D)的可行解,则必有推论1:原问题任一可行解的目标函数值是其对偶问题目标函数值的下届;反之,对偶问题任意可行解的目标函数值是其原问题目标函数值的上界。推论推
10、论2:在一对对偶问题(在一对对偶问题(P)和()和(D)中,若其中一个问题可)中,若其中一个问题可行但目标函数无界,则另一个问题无可行解;反之不成立。这行但目标函数无界,则另一个问题无可行解;反之不成立。这也是对偶问题的无界性。也是对偶问题的无界性。无界如:(原)无可行解(对)对偶性质对偶性质推论推论3 3:在一对对偶问题(在一对对偶问题(P)和()和(D)中,若一个可行(如)中,若一个可行(如P),而另一个不可行(如),而另一个不可行(如D),则该可行的问题目标函数),则该可行的问题目标函数值无界。值无界。性质3 最优性定理:如果 是原问题的可行解,是其对偶问题的可行解,并且:则 是原问题的
11、最优解,是其对偶问题的最优解。对偶性质对偶性质性质性质4 强对偶性:若原问题及其对偶问题均具有可行解,则强对偶性:若原问题及其对偶问题均具有可行解,则两者均具有最优解,且它们最优解的目标函数值相等。两者均具有最优解,且它们最优解的目标函数值相等。还可推出另一结论:若(LP)与(DP)都有可行解,则两者都有最优解,若一个问题无最优解,则另一问题也无最优解。性质5 互补松弛性:设X0和Y0分别是P问题 和 D问题 的可行解,则它们分别是最优解的充要条件是:其中:Xs、Ys为松弛变量约束 条件 也分为两种情况:,约束条件比较松;,约束条件比较紧;yi 0,分为两种情况:yi0,约束条件比较松;yi=
12、0,约束条件比较紧;互补松弛定理的解释互补松弛定理的解释互补松弛定理的解释互补松弛定理的解释变量同其对偶问题的约束方程之间至多只能够有一个取松弛的情况,当其中一个取松弛的情况时,另外一个比较紧,即取严格等号。已知下面的已知下面的LP1和和LP2为一组对偶规划,且已知为一组对偶规划,且已知LP1的最优解的最优解为为X=(1.5,1)。试运用互补松弛定理求出对偶问题的最。试运用互补松弛定理求出对偶问题的最优解优解Y。原问题(LP1)对偶问题(LP2)解:由X=(1.5,1)得联立求解得:对偶性质对偶性质性质性质5的应用:的应用:该性质给出了已知一个问题最优解求另一个问题最优解该性质给出了已知一个问
13、题最优解求另一个问题最优解的方法,即已知的方法,即已知Y求求X或已知或已知X求求Y互补松弛条件由于变量都非负,要使求和式等于零,则必定每一分量为零,因而有下列关系:若Y0,则Xs必为0;若X0,则Ys必为0利用上述关系,建立对偶问题(或原问题)的约束线性方程组,方程组的解即为最优解。对偶性质对偶性质例例4 已知线性规划已知线性规划的最优解是X=(6,2,0)T,求其对偶问题的最优解Y。解:写出原问题的对偶问题,即标准化对偶性质对偶性质设对偶问题最优解为设对偶问题最优解为Y(y1,y2),由互补松弛性定理可知,由互补松弛性定理可知,X和和 Y满足:满足:即:因为X10,X20,所以对偶问题的第一
14、、二个约束的松弛变量等于零,即y30,y40,带入方程中:解此线性方程组得y1=1,y2=1,从而对偶问题的最优解为:Y=(1,1),最优值w=26。对偶性质对偶性质例例5 已知线性规划已知线性规划 的对偶问题的最优解为Y=(0,-2),求原问题的最优解。解:对偶问题是标准化对偶性质对偶性质设对偶问题最优解为设对偶问题最优解为X(x1,x2,x3)T,由互补松弛性定理由互补松弛性定理可知,可知,X和和 Y满足:满足:将Y带入由方程可知,y3y50,y41。y2=-20 x50又y4=10 x20将x2,x5分别带入原问题约束方程中,得:解方程组得:x1=-5,x3=-1,所以原问题的最优解为X
15、=(-5,0,-1),最优值z=-12对偶问题的经济解释影子价格对偶问题的经济解释影子价格1.影子价格的数学分析:影子价格的数学分析:定义:在一对 P 和 D 中,若 P 的某个约束条件的右端项常数bi(第i种资源的拥有量)增加一个单位时,所引起目标函数最优值z*的改变量称为第 i 种资源的影子价格,其值等于D问题中对偶变量yi*。由对偶问题得基本性质可得:对偶问题的经济解释影子价格对偶问题的经济解释影子价格2.影子价格的经济意义影子价格的经济意义1)影子价格是一种边际价格)影子价格是一种边际价格在其它条件不变的情况下,单位资源数量的变化所引起在其它条件不变的情况下,单位资源数量的变化所引起的
16、目标函数最优值的变化。即对偶变量的目标函数最优值的变化。即对偶变量yi 就是第就是第 i 种资源的种资源的影子价格。即:影子价格。即:对偶问题的经济解释影子价格对偶问题的经济解释影子价格2)影子价格是一种机会成本)影子价格是一种机会成本影子价格是在资源最优利用条件下对单位资源的估价,影子价格是在资源最优利用条件下对单位资源的估价,这种估价不是资源实际的市场价格。因此,从另一个角度说,这种估价不是资源实际的市场价格。因此,从另一个角度说,它是一种机会成本。它是一种机会成本。若第i 种资源的单位市场价格为mi,则有当yi*mi 时,企业愿意购进这种资源,单位纯利为yi*mi,则有利可图;如果yi*
17、mi 则购进资源i,可获单位纯利yi*mi 若yi*mi则转让资源i,可获单位纯利miyi影子价格影子价格010 20 30 40 50 6010 2 0 3 0 4 0 50 x2 x1123(50/7,200/7)多了 32/7010 20 30 40 50 6010 2 0 3 0 4 0 50 x2 x1123(50/7.200/7)x1010 20 30 40 50 6010 2 0 3 0 4 0 50 x2 123(55/7.199/7)影子价格影子价格010 20 30 40 50 6010 2 0 3 0 4 0 50 x2 x1123(47/7.202/7)多了 6/7影子
18、价格影子价格对偶问题的经济解释影子价格对偶问题的经济解释影子价格3)影子价格在资源利用中的应用)影子价格在资源利用中的应用根据对偶理论的互补松弛性定理根据对偶理论的互补松弛性定理:Y*Xs=0 ,YsX*=0表明生产过程中如果某种资源表明生产过程中如果某种资源bi未得到充分利用时,该种资未得到充分利用时,该种资源的影子价格为源的影子价格为0;若当资源资源的影子价格不为;若当资源资源的影子价格不为0时,表明时,表明该种资源在生产中已耗费完。该种资源在生产中已耗费完。对偶问题的经济解释影子价格对偶问题的经济解释影子价格4)影子价格对单纯形表计算的解释)影子价格对单纯形表计算的解释单纯形表中的检验数
19、其中cj表示第j种产品的价格;表示生产该种产品所消耗的各项资源的影子价格的总和,即产品的隐含成本。当产值大于隐含成本时,即 ,表明生产该项产品有利,可在计划中安排;否则 ,用这些资源生产别的产品更有利,不在生产中安排该产品。定义:在一对 P 和 D 中,若 P 的某个约束条件的右端项常数bi 增加一个单位时,所引起的目标函数最优值Z*的改变量y*i称为第i个约束条件的影子价格,又称为边际价格。影子价格影子价格CCBCN0CBXBbXBXNXSCBXBB-1bIB-1NB-1ZCB B-1b0CNCB B-1NCB B-1本章小结本章小结学习要点:1.线性规划解的概念以及3个基本定理2.熟练掌握
20、单纯形法的解题思路及求解步骤三、灵敏度分析 讨论模型的系数或变量发生小的变化时对解的影响(如它们在何范围内变化时可使原最优解或最优基不变?)我们主要讨论C、b和变量结构变化时对解的影响。对解怎样影响?影响解的 -最优性 -可行性3.增加新变量时的分析 主要讨论增加新变量xn+1是否有利。经济意义是第n+1种新产品是否应当投产,数学意义是xn+1是否应进基。经济意义:市场价影子价1.1.C C变化时的分析变化时的分析变化时的分析变化时的分析1、目标函数系数cj变化例 3.7 C由(3.2)变为(3,1),请问最优生产计划如何变化?解:由原最优单纯形表得:基变量31000bCBxBx1x2x3x4
21、x50 x30 0 1 5/2-3/23/23x11 0 0 3/2-1/23/21x20 1 0 -2 1 1 0 0 0 -5/21/211/2单纯形迭代得:单纯形迭代得:基变量31000bCBxBx1x2x3x4x50 x30 3/21 -1/2033x11 1/20 1/2020 x50 10 -21 1 0 -1/20-3/2-3/26所以得到新的最优生产计划为产品所以得到新的最优生产计划为产品I生产生产2件,产品件,产品II不生产,此时总利润上升为不生产,此时总利润上升为6万元。万元。2、约束条件右端向量、约束条件右端向量b的变化的变化2、约束条件右端向量、约束条件右端向量b的变化
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 运筹学 对偶 理论 ppt
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【a199****6536】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【a199****6536】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。