• / 34
  • 下载费用:10 金币  

对偶问题(运筹学).ppt

关 键 词:
对偶问题(运筹学).ppt
资源描述:
第四节 对偶问题,大连海事大学交通运输管理学院,2.4.1 对偶问题的提出 2.4.2 原问题与对偶问题 2.4.3 对偶问题的性质 2.4.4 对偶变量的经济含义 2.4.5 对偶单纯形法,第四节 对偶问题,一、对偶问题的提出,某工厂在计划期内要安排生产Ⅰ、Ⅱ两种产品,已知生产单位产品所需的设备台时及A、B两种原材料的消耗,如表1-1所示。每生产一件产品Ⅰ可获利2元,每生产一件产品Ⅱ可获利3元,问应如何安排计划使该工厂获利最多?,--第2章 对偶问题--,--4--,1.最大生产利润模型,设 企业生产甲产品为X1件, 乙产品为X2件,则,2.资源最低售价模型,(原问题) ( 对偶问题),设第i种资源价格为yi,( i=1, 2, 3) 则有,y1,y2,y3,y4,二、 原问题与对偶问题的关系,一般表示式: 原问题: max z = c1 X1 + c2 X2 + ┈ + cn Xns.t a11 X1 + a12 X2 + ┈ + a1n Xn  b1 a21 X1 + a22 X2 + ┈ + a2n Xn  b2 ·······················am1 X1 + am2 X2 + ┈ + amn Xn  bmxj  0,j=1,2,┈,n 对偶问题: min w = b1 y1 + b2 y2 + ┈ + bm yms.t a11 y1 + a21 y2 + ┈ + am1 ym  c1 a12 y1 + a22 y2 + ┈ + am2 ym  c2 ·························a1n y1 + a2n y2 + ┈ + amn ym  cn yi  0,(i=1,2,···,m ),,,典式模型对应对偶结构矩阵表示,(1) max z = C X s.t AX  b X  0,,min w = Y bs.t YA  CY  0,,对偶问题,原问题,,对偶模型其他结构关系,(2)若模型为 max z = C X s.t AX  b X  0,,,,max z = C Xs.t - AX  -b X  0,变形,,min w = Y bs.t YA  CY  0,,Min w=Y ´(-b)st. Y ´(-A)  C Y ´ 0,令 Y=- Y ´,,,对偶问题,对偶变量Y,(3)max z = C X s.t AX  b X  0,,变形,,设X= -X´,max = -CX ´st. -AX´  b X´ 0,,,min w = Y bs.t YA  CY  0,,则有,min w = Y bs.t -YA - CY 0,,,,对偶问题典式:,用矩阵形式表示:(1) max z = C X min w = Y bs.t AX  b s.t YA  CX  0 Y  0 (2) max z = C X min w = Y bs.t AX  b s.t YA  CX  0 Y  0 (3)max z = C X min w = Y bs.t AX  b s.t YA  CX  0 Y  0,原问题与对偶问题关系表,原问题(对偶问题) 对偶问题(原问题)目标函数系数 约束右端项 约束右端项 目标函数系数约束条件系数列向量 A 约束条件系数行向量 AT变量个数 约束条件个数max min变量 x j : 约束方程 i :x j  0  x j 无约束 =x j  0 约束方程: 变量 y i : y i  0 = y i 无约束  y i  0,,,,例2-10 写出下述线性规划问题的对偶问题。,例子,则由表中原问题和对偶问题的对应关系,可以直接写出上述问题的对偶问题,对偶问题解法,练习,max z = 2y1+5y2+1y32 y1+3 y2 +1y3 31 y1 -5 y2 +1y3 23 y1 +1y3 -1,≥,=,≤,
展开阅读全文
  微传网所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
0条评论

还可以输入200字符

暂无评论,赶快抢占沙发吧。

关于本文
本文标题:对偶问题(运筹学).ppt
链接地址:https://www.weizhuannet.com/p-9696047.html
微传网是一个办公文档、学习资料下载的在线文档分享平台!

微传网博客

网站资源均来自网络,如有侵权,请联系客服删除!

 网站客服QQ:80879498  会员QQ群:727456886

copyright@ 2018-2028 微传网络工作室版权所有

     经营许可证编号:冀ICP备18006529号-1 ,公安局备案号:13028102000124

收起
展开