运筹学经典课件第6次(1).ppt
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 运筹学 经典 课件
- 资源描述:
-
单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,上堂课主要内容,:,线性规划的对偶问题,:,对称型线性规划:,形如:,b,i,无正负限制,或:,1,、对称型对偶问题:,2,、,标准型的对偶问题,:,则,对偶问题(,D,),为:,原问题,对偶问题,目标函数,max,目标函数,min,目标函数系数,约束方程常数列,约束方程常数列,目标函数系数,变量个数,n,约束方程个数,n,约束方程个数,m,变量个数,m,约束方程,变量,0,0,=,无符号约束,变量,0,约束方程,0,无符号约束,=,系数矩阵,A,3,、混合型对偶问题,2.2 对偶线性规划 解的理论,定理,2.1,对偶问题的对偶就是原问题。,(即互为对偶规划),一、对称定理:,二、弱对偶性定理:,推论,1,:,若(,P,),有可行解,但无上界,则(,D,)无,可行解。若(,D,),有可行解,但无下界,则,(,P,)无可行解,推论,2,、若原问题(,P,)和其,对偶问题,(,D,),都存在,可行解,则(,P,),和(,D,),都存在最优解,定理,2.3,原线性规划(,P,),与其对偶规划(,D,)存,在以下对应关系:,(,1,)(,P,),有最优解的,充要条件,是(,D,),有最优解,(,2,)若,X,*,和,Y,*,分别是(,P,),和(,D,),的可行解,,则,X,*,和,Y,*,分别是(,P,),和(,D,),的最优解的充,要条件是:,CX,*,=,Y,*,b,三、对偶性定理:,2,、若(,P,),存在最优解,X,*,,,B,是对应的最优基,,则(,D,),一定存在最优解,Y*,,且,1,、原问题(,P,)与其对偶问题(,D,)最优值相同,说明,:,只需求出(,P,)或,(D),中一个的最优解和最优值,,即可得另一个的最优解和最优值,推论,3*,:,若(,P,)(,D,)为对称型对偶问题,且(,P,),存在最优解,X,*,,,则(,D,),一定存在最优解,Y*,,,且(,-1,),Y*,是(,P,)的标准型的最优单纯形表,检验行中松弛变量的系数,四、互补松弛定理:,定理,2.4,设,X*,和,Y*,分别是(,P,)和(,D,)的可行解,,则,X*,和,Y*,分别是(,P,)和(,D,)的最优解的,充要条件是方程组,证明,:,充分性,已知,X*,和,Y*,分别是(,P,)和(,D,)的,可行解,且,所以,X*,和,Y*,分别是(,P,)和(,D,)的最优解,一个数,0,0,0,0,0,0,0,0,0,0,0,0,互补松弛定理,:,设,X*,和,Y*,分别是(,P,)和(,D,)的可行解,则,X*,和,Y*,分别是(,P,)和(,D,)的最优解,的充要条件是方程组 成立,把,X*,代入(,P,)的第,i,个方程时为等式,松约束,紧约束,定理,2.4,设,X*,和,Y*,分别是(,P,)和(,D,)的可行解,则,X*,和,Y*,分别是(,P,)和(,D,)的最优解的充,要条件,是方程组 成立,对任一种形式的对偶问题成立,互补松弛定理,:,0,求对偶问题最优解的方法归纳:,1,、对任一种形式的对偶问题:,设,B,是原问题(,P,)的最优基,则,是对偶问题(,D,)的最优解,2,、对对称形的对偶问题:,(,-1,)原问题(,P,)的最优单纯形表上松弛变量的检验数,对偶问题(,D,)的最优解,=,3,、对任一种形式的对偶问题,,利用互补松弛定理,设已求得原问题(,P,)的最优解,则,练习:,展开阅读全文

咨信网声明:本文档由用户上传并分享,仅供学习交流、研究之用,未经授权,严禁复制、发行、汇编、翻译或网络传播等,侵权必究。
咨信网小贴示:
1、浏览或下载可查看了解,请点击【咨信网告知】。
2、下载文件中如有侵权或不适当内容,将立即纠正。
3、如果因为网速或其他原因下载失败请重新下载,重复下载[60天内]不扣币。
4、开具发票登录电脑端申请,请点击【索取发票】。
咨信网客服组:【微信客服】
1、浏览或下载可查看了解,请点击【咨信网告知】。
2、下载文件中如有侵权或不适当内容,将立即纠正。
3、如果因为网速或其他原因下载失败请重新下载,重复下载[60天内]不扣币。
4、开具发票登录电脑端申请,请点击【索取发票】。
咨信网客服组:【微信客服】


运筹学经典课件第6次(1).ppt
















自信AI助手














微信客服
客服QQ
发送邮件
意见反馈



链接地址:https://www.zixin.com.cn/doc/14772113.html