第二章 线性规划的对偶理论 第四讲ppt课件.ppt

第二章 线性规划的对偶理论 第四讲ppt课件.ppt

ID:58688904

大小:1.23 MB

页数:51页

时间:2020-10-04

第二章 线性规划的对偶理论 第四讲ppt课件.ppt_第1页
第二章 线性规划的对偶理论 第四讲ppt课件.ppt_第2页
第二章 线性规划的对偶理论 第四讲ppt课件.ppt_第3页
第二章 线性规划的对偶理论 第四讲ppt课件.ppt_第4页
第二章 线性规划的对偶理论 第四讲ppt课件.ppt_第5页
资源描述:

《第二章 线性规划的对偶理论 第四讲ppt课件.ppt》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库

1、第二章线性规划的对偶理论最优化方法OptimizingMethods§1对偶问题的提出一、对偶问题的实例产品资源资源甲乙限制A3265B2140C0375单件利润15002500maxz=1500x1+2500x2s.t.3x1+2x2≤652x1+x2≤40(1)3x2≤75x1,x2≥0最优解为:x1*=5,x2*=25zmax=70000设y1,y2,y3分别为A,B,C三种资源出售的价格3y1+2y2≥15002y1+y2+3y3≥2500w=65y1+40y2+75y3minw=65y1+40y2+75y3s.t.3y1

2、+2y2≥1500(2)2y1+y2+3y3≥2500y1,y2,y3≥0最优解为:y1*=500y2*=0,y3*=500,wmin=70000如果称(1)为LP问题的原问题,则称(2)为(1)的对偶问题。第二章线性规划的对偶理论二、对偶问题的形式1、对称型对偶问题maxz=c1x1+c2x2+…+cnxns.t.a11x1+a12x2+…+a1nxn≤b1a21x1+a22x2+…+a2nxn≤b2(3)……am1x1+am2x2+…+amnxn≤bmxj≥0(j=1,2,…,n)minw=b1y1+b2y2+…+bmyms.

3、t.a11y1+a21y2+…+am1ym≥c1a12y1+a22y2+…+am2ym≥c2(4)……a1ny1+a2ny2+…+amnym≥cnyi≥0(i=1,2,…,m)定义1设原LP问题为则称下列LP问题为其对偶问题,其中yi≥0(i=1,2,…,m)称为对偶变量,并称(3)、(4)为一对对称型对偶问题maxz=cx(P)s.t.Ax≤bx≥0minw=yb(D)s.t.yA≥cy≥0§1对偶问题的提出2、非对称型对偶问题maxz=cx(P)s.t.Ax=bx≥0maxz=cxs.t.Ax≤b-Ax≤-bx≥0引入对偶变量

4、(u,v),其中u=(u1,u2,…,um)为对应于第一组不等式约束Ax≤b的对偶变量,v=(v1,v2,…,vm)为对应于第二组不等式约束-Ax≤-b的对偶变量,按对称型的结论:minw=(u-v)bs.t.(u-v)A≥cu,v≥0令y=u-vminw=yb(D)s.t.yA≥cy≥0minw=yb(D)s.t.yA≥cy无符号限制第二章线性规划的对偶理论3、混合型对偶问题maxz=c1x1+c2x2s.t.A11x1+A12x2≤b1A21x1+A22x2=b2A31x1+A32x2≥b3x1≥0,x2无符号限制其中Aij为

5、mi×nj矩阵;bi为mi维列向量;cj为nj维行向量;xj为nj维列向量,i=1,2,3;j=1,2,且m1+m2+m3=m,n1+n2=n令x2=x21-x22,x21,x22≥0.化原问题为标准型:maxz=c1x1+c2(x21-x22)s.t.A11x1+A12(x21-x22)+Isxs=b1A21x1+A22(x21-x22)=b2A31x1+A32(x21-x22)-Itxt=b3x1,x21,x22,xs,xt≥0minw=b1y1+b2y2+b3y3s.t.y1A11+y2A21+y3A31≥c1y1A12+y

6、2A22+y3A32≥c2-y1A12-y2A22-y3A32≥-c2y1Is≥0-y3It≥0y1,y2,y3无符号限制按非对称型minw=b1y1+b2y2+b3y3s.t.y1A11+y2A21+y3A31≥c1y1A12+y2A22+y3A32=c2y1≥0,y2无符号限制,y3≤0§1对偶问题的提出原问题与对偶问题的关系原问题目标函数max目标函数minm个≤≥=n个≥≤=n个≥0≤0无符号限制m个≥0≤0无符号限制目标函数的系数约束条件右端常数系数矩阵A约束条件右端常数目标函数的系数系数矩阵AT约束条件约束条件变量变量

7、对偶问题e.g.1写出(P)问题的(D)问题maxz=2x1+3x2-5x3+x4s.t.4x1+x2-3x3+2x4≥53x1-2x2+7x4≤4-2x1+3x2+4x3+x4=6x1≤0,x2,x3≥0,x4无符号限制minw=5y1+4y2+6y3s.t.4y1+3y2-2y3≤2y1-2y2+3y3≥3-3y1+4y3≥-52y1+7y2+y3=1y1≤0,y2≥0,y3无符号限制§2对偶问题的基本性质讨论对称形式:(P)问题maxz=cxs.t.Ax≤bx≥0(D)问题minw=ybs.t.yA≥cy≥0一、对偶规划的若

8、干定理Theorem1(对称性定理)对偶问题的对偶是原问题.互为对偶proofTheorem2(弱对偶定理)设x0和y0分别是(P)问题和(D)问题的可行解,则必有cx0≤y0b.Corollary1如果x*和y*分别是(P)问题和(D)问题的可行

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。