收藏 分销(赏)

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

上传人:仙人****88 文档编号:14772113 上传时间:2026-11-19 格式:PPT 页数:21 大小:765.50KB 下载积分:10 金币
下载 相关
运筹学经典课件第6次(1).ppt_第1页
第1页 / 共21页
运筹学经典课件第6次(1).ppt_第2页
第2页 / 共21页


点击查看更多>>
资源描述
单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,上堂课主要内容,:,线性规划的对偶问题,:,对称型线性规划:,形如:,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,)的最优解,则,练习:,
展开阅读全文

开通  VIP、SVIP  下载更划算
下载10份以上建议开通 VIP 会员
下载20份以上建议开通SVIP会员


开通VIP      成为共赢上传

当前位置:首页 > 教育专区 > 其他

移动网页_全站_页脚广告1

关于我们      便捷服务       自信AI       AI导航        关注我们

©2010-2026 宁波自信网络信息技术有限公司  版权所有

客服电话:0574-28810668  投诉电话:18658249818

gongan.png浙公网安备33021202000488号   

icp.png浙ICP备2021020529号-1  |  浙B2-20240490  

关注我们 :微信公众号    抖音    微博    LOFTER 

客服