第二章 对偶问题.ppt

《第二章 对偶问题.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、2021/9/1--第2章对偶问题----1--第二章线性规划的对偶理论Duality对偶DualProblem对偶问题DualLinearProgramming对偶线性规划DualTheory对偶理论2021/9/12例甲方生产计划问题：ⅠⅡ能力设备A2212设备B4016设备C0515利润23Ⅰ，Ⅱ各生产多少,可获最大利润?乙方租借设备：甲方以何种价格将设备A、B、C租借给乙方比较合理？请为其定价。2.1问题的提出--第2章对偶问题--2021/9/13而就乙方而言，希望甲方的租金收入在满足约束的条件下越小越好，这样双方才可能达成协议。于是得到下述的线

2、性规划模型：解：假设A、B、C的单位租金分别为，所以生产产品Ⅰ的资源用于出租时，租金收入应满足：类似的，生产产品Ⅱ的资源用于出租时，租金收入应满足：总的租金收入：--第2章对偶问题--思路：就甲方而言，租金收入应不低于将设备用于自己生产时的利润。原问题的对偶问题2021/9/1--第2章对偶问题----4--例：某企业计划生产甲、乙两种产品，该两种产品均需经A、B、C、D四种不同设备加工，按工艺资料规定，在各种不同设备上的加工时间及设备加工能力、单位产品利润如表中所示。问：如何安排产品的生产计划，才能使企业获利最大?2021/9/1--第2章对偶问题---

3、-5--1.最大生产利润模型设企业生产甲产品为X1件，乙产品为X2件，则maxz=2X1+3X2s.t2X1+2X212X1+2X284X1164X212X10,X202.资源最低售价模型(原问题)<========>(对偶问题)设第i种资源价格为yi,（i=1,2,3,4,）则有minw=12y1+8y2+16y3+12y4s.t2y1+y2+4y3+0y422y1+2y2+0y3+4y43yi0,(i=1,2,3,4)y1y2y3y42021/9/1--第2章对偶问题----6--2.2原问题与对偶问题的关系一般表示式：原问题：max

4、z=c1X1+c2X2+┈+cnXns.ta11X1+a12X2+┈+a1nXnb1a21X1+a22X2+┈+a2nXnb2·······················am1X1+am2X2+┈+amnXnbmxj0，j=1,2,┈,n对偶问题：minw=b1y1+b2y2+┈+bmyms.ta11y1+a21y2+┈+am1ymc1a12y1+a22y2+┈+am2ymc2·························a1ny1+a2ny2+┈+amnymcnyi0，(i=1,2,···,m)2021/9/1--第2章对偶问题--

5、--7--典式模型对应对偶结构矩阵表示（1）maxz=CXs.tAXbX0minw=Ybs.tYACY0对偶问题原问题这是规范形式的原问题，由此写出其对偶问题如右方所示，那么，当原问题不是规范形式时，应如何写出其对偶问题？可以先将原问题化成规范的原问题，再写出对偶问题。2021/9/1--第2章对偶问题----8--对偶模型其他结构关系（2）若模型为maxz=CXs.tAXbX0maxz=CXs.t-AX-bX0变形minw=Ybs.tYACY0Minw=Y´(-b)st.Y´(-A)CY´0令Y=-Y´对偶问题对偶变量Y2021

6、/9/1--第2章对偶问题----9--（3）maxz=CXs.tAXbX0变形设X=-X´max=-CX´st.-AX´bX´0minw=Ybs.tYACY0则有minw=Ybs.t-YA-CY02021/9/1--第2章对偶问题----10--对偶问题典式：用矩阵形式表示：（1）maxz=CXminw=Ybs.tAXb<========>s.tYACX0Y0（2）maxz=CXminw=Ybs.tAXb<========>s.tYACX0Y0（3）maxz=CXminw=Ybs.tAXb<========>s.tYA

7、CX0Y011等式、无约束情况的对偶：原问题对偶问题12推导:原问题化为：即：13根据对称形式的对偶模型,可直接写出上述问题的对偶问题:14令，得对偶问题为：2021/9/1--第2章对偶问题----15--原问题与对偶问题关系表原问题(对偶问题)对偶问题(原问题)目标函数系数约束右端项约束右端项目标函数系数约束条件系数列向量A约束条件系数行向量AT变量个数约束条件个数maxmin变量xj:约束方程i:xj0xj无约束=xj0约束方程:变量yi:yi0=yi无约束yi02021/9/1--第2章对偶问题----16--2.3对偶问题的基

8、本性质Maxz=CXMinw=Ybst.AXbst.YACX