运筹学--对偶线性规划与灵敏分析.pptx
《运筹学--对偶线性规划与灵敏分析.pptx》由会员分享,可在线阅读,更多相关《运筹学--对偶线性规划与灵敏分析.pptx(81页珍藏版)》请在咨信网上搜索。
1、运筹学运筹学 第二章第二章 对偶偶线性性规划与灵敏度分析划与灵敏度分析本章重点本章重点n对偶问题的求解n对偶定理n对偶单纯形法 n灵敏度分析对偶线性规划问题的导出对偶线性规划问题的导出(1)n(前面(前面讲过的生的生产计划划问题)某工厂用三种原料生产三种产品,已知的条件如下表所示,试制订总利润最大的日生产计划单位产品所需原料单位产品所需原料数量(公斤)数量(公斤)产品产品Q1产品产品Q2产品产品Q3原料可用量原料可用量(公斤(公斤/日)日)原料原料P12301500原料原料P2024800原料原料P33252000单位产品的利润单位产品的利润(千元)(千元)354对偶线性规划问题的导出对偶线性
2、规划问题的导出(2)(2)n设每天生产三种产品的数量分别为x1、x2、x3现在三种产品销路不畅,可以将所有的原料外卖,现在要谈判,我们的价格底线是什么?对偶线性规划问题的导出对偶线性规划问题的导出(3)(3)n解决这一问题应考虑u外卖原料获利应不少于生产产品的获利,即出卖能够制造一件产品的原料的获利应该不少于生产一件该产品的获利u价格应该尽可能低,这样才有竞争力u价格应该是非负的n设出租或外卖三种原料的价格分别为y1、y2、y3对偶线性规划问题的导出对偶线性规划问题的导出(4)(4)n上述两个线性规划模型是在同一工厂的资源状况和生产状况条件下产生的,是同一问题从不同角度来观察所产生的,因此两者
3、密切相关,我们称这两个线性规划问题互为对偶问题,其中一个问题是另一问题的对偶问题。对偶问题的定义对偶问题的定义(1)n对于线性规划问题(1)对偶问题的定义对偶问题的定义(2)和(2)对偶问题的定义对偶问题的定义(2)n称(1)是(2)的对偶问题;也称(2)是(1)的对偶问题n这种对偶关系称为对称形式的称形式的对偶偶,用矩阵表示为对偶问题的定义对偶问题的定义(3)n还有一种非非对称形式的称形式的对偶偶,用矩阵表示为求对偶问题求对偶问题原问题(或对偶问题)原问题(或对偶问题)对偶问题(或原问题)对偶问题(或原问题)目标函数 MaxZ目标函数 MinW约束条件数:m个第i个约束条件类型为“”第i个约
4、束条件类型为“”第i个约束条件类型为“=”变量数:m个第i个变量0第i个变量0第i个变量是自由变量 变量数:n个第j个变量0第j个变量0第j个变量是自由变量 约束条件数:n个第 j个 约 束 条 件 类 型 为“”第 j个 约 束 条 件 类 型 为“”第j个约束条件类型为“=”示例示例(2.1-1)n写出下面线性规划的对偶规划示例示例(2.1-2)n结果为作业作业(6)n书上99页的2-1对偶定理对偶定理(1)n对偶定理偶定理是揭示原始问题的解与对偶问题的解之间重要关系的一系列定理n定理1 对称性定理u对偶问题的对偶问题是原问题n定理2 弱对偶定理u极大化原问题的任一可行解的目标函数值,不大
5、于其对偶问题的任一可行解的目标函数值对偶定理对偶定理(2)均有可行解,分别为均有可行解,分别为 和和 ,则,则证明:证明:由由(L),左乘左乘 ,得,得 由由(D),右乘右乘 ,得,得 设设(L)和和 (D)对偶定理对偶定理(3)n推论1u极大化问题的任意一个可行解所对应的目标函数值是其对偶问题最优目标函数值的一个下界n推论2u极小化问题的任意一个可行解所对应的目标函数值是其对偶问题最优目标函数值的一个上界n推论3u若原问题可行,则其目标函数无界的充要条件是对偶问题没有可行解对偶定理对偶定理(4)n推论4u若对偶问题可行,则其目标函数无界的充要条件是原问题没有可行解n定理3 最最优性准性准则定
6、理定理u若 、分别为互为对偶问题的线性规划的可行解,且 ,则 和 分别是相应线性规划问题的最优解对偶定理对偶定理(5)CXbTYT弱对偶弱对偶定定 理理已已 知知结论结论最优解定义最优解定义X=Y=特别取特别取证证 明明CXCXC对偶定理对偶定理(6)n定理4 主主对偶定理偶定理u若原始问题和对偶问题两者均可行,则两者均有最优解,且此时目标函数值相同n证明:u第一部分证明两者均有最优解由于原始问题和对偶问题均可行,根据弱对偶定理知两者均有界,于是均有最优解。u第二部分证明在达到最优时,两个问题的目标函数值相等利用单纯形法的特征,就非对称形式的对偶问题给出对偶定理对偶定理(7)第一步:给出原问题
7、和对偶问题第一步:给出原问题和对偶问题(L)设原问题有对应于最优基B的最优基本可行解X=(XB,0)T,则有XB=B-1b(D)对偶定理对偶定理(8)第第二二步步:利利用用单单纯纯形形法法的的矩矩阵阵描描述述,由由单单纯纯形形法法最最优优性性判判别别定定理理得得出出重重要要结结论论 ,并并引出引出“单纯形乘子单纯形乘子”的定义的定义 ;定义 (最优单纯形乘子)令 A=(B,N),所以对应于最优基B的检验数满足 对偶定理对偶定理(9)第三步:证明最优单纯形乘子就是对偶问题的第三步:证明最优单纯形乘子就是对偶问题的可行解可行解所以,是对偶问题的可行解对偶定理对偶定理(10)第四步:进一步证明第四步
8、:进一步证明 是对偶问题的最优解,是对偶问题的最优解,并验证两个问题的目标函数值相等。并验证两个问题的目标函数值相等。又又根根据据最最优优性性准准则则定定理理,这这时时的的 正正是是对对偶偶问问题题的最优解。的最优解。对偶最优解的经济含义对偶最优解的经济含义影子价格影子价格(1)n前面已经讲过,生产计划问题的对偶问题是资源定价问题。n该对偶问题的最优解代表的是工厂在当前的资源状况b,技术状况A和市场状况C已知的情况下,单位资源对企业的价值。n若X*=(x1*,x2*,xn*)T 和 Y*=(y1*,y2*,ym*)分别是生产计划问题和资源定价问题的最优解,根据主对偶定理,其最优值相等。即对偶最
9、优解的经济含义对偶最优解的经济含义影子价格影子价格(2)n由此可知n若把Z*看作b1,b2,bm的函数,则由 可知,yi*是资源bi 价值的一种度量,称为bi 的影子价格影子价格,其含义是在其他条件不变的情况下,最优目标值随资源数量变化的变化率。对偶最优解的经济含义对偶最优解的经济含义影子价格影子价格(3)n影子价格所包含的信息u资源紧缺状况(越紧缺的资源价格越高)u确定资源转让基价u取得紧缺资源的代价由原问题最优单纯形表由原问题最优单纯形表求对偶问题最优解求对偶问题最优解n由检验数的计算方法可知n设B是原线性规划问题的最优基,则 是其对偶问题的最优解n若A中有单位子矩阵,该子矩阵对应的列为第
10、i1,i2,im(i1i2 0 时,以xj为入基变量,用单纯形法继续迭代求出新的最优解B-1bIB-1N-CBB-1b0CN-CBB-1Nj=cj-CBB-1PjCB中的某个中的某个cj发生变化发生变化n从最优表中可以看出,CB中的某个cj发生变化时,影响最优值和所有的检验数N(N=CN-CBB-1N)u当N 0 时,最优基不变,最优解不变,最优值改变u若有某个j 0,以xj为入基变量,用单纯形法继续迭代求出新的最优解B-1bIB-1N-CBB-1b0CN-CBB-1NC中的某个中的某个cj发生变化发生变化ncj变化相当于生产问题中该产品的价格变动n当某个cj变化时,如能保持N 0,则当前解仍
- 配套讲稿:
如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。