(最新)[数学].对偶问题

《(最新)[数学].对偶问题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、对偶问题1对偶规划2对偶问题的基本性质3对偶问题的解4影子价格5对偶单纯形法11对偶规划2对偶问题的提出例1、生产组织与计划问题A,B各生产多少,可获最大利润?可用资源煤劳动力仓库AB123202单位利润40503060243MaxZ=40x1+50x2x1+2x2303x1+2x2602x224x1，x20s.t目标函数约束条件如果因为某种原因，不愿意自己生产，而希望通过将现有资源承接对外加工来获得收益，那么应如何确定各资源的使用价格？4MaxZ=40x1+50x2x1+2x2303x1+2x

2、2602x224x1，x20s.t目标函数约束条件两个原则所得不得低于生产的获利要使对方能够接受设三种资源的使用单价分别为y1,y2,y3y1y2y3生产单位产品A的资源消耗所得不少于单位产品A的获利生产单位产品B的资源消耗所得不少于单位产品B的获利y1+3y2402y1+2y2+2y3505通过使用所有资源对外加工所获得的收益W=30y1+60y2+24y3根据原则2，对方能够接受的价格显然是越低越好，因此此问题可归结为以下数学模型：MinW=30y1+60y2+24y3y1+3y2402y

3、1+2y2+2y350y1,y2,y30s.t目标函数约束条件原线性规划问题称为原问题，此问题为对偶问题，y1,y2,y3称为影子价格6例2原问题（P）实际意义资源分配问题：3种有限的资源生产2种产品，决策变量为2种产品的产量，目标函数决策变量系数为2种产品获得的单位利润，目标为利润最大化。7对偶问题（D）8假定管理决策者从另一个角度来讨论这个问题，不考虑自己生产甲、乙两种产品去盈利，而是将现有资源标价出售，试问：决策者应该怎样给资源定一个合理的价格？对偶问题实际意义9设分别表示三种资源的单位售价决策

4、者应该考虑卖掉资源的收入不能低于用资源安排生产的获利10表示将用于生产单位第一种产品的资源卖出去后，所获利不能少于其用于生产的获利（第一种产品的单位利润）。表示将用于生产单位第二种产品的资源卖出去后，所获利不能少于其用于生产的获利（第二种产品的单位利润）。11一般化表示用于生产单位第j种产品的资源卖出去后，所获利不能少于其用于生产的获利（第j种产品的单位利润）。12矩阵形式原问题LP对偶问题DP13原问题对偶问题决策变量个数为原问题方程个数目标函数maxmin约束方程组右端常数为原问题目标函数中决策变量的

5、系数：CbT约束方程组系数为原问题约束方程系数矩阵的转置：AAT约束方程组符号目标函数中决策变量的系数为原问题约束方程组右端常数：bCT14练习1:写出对偶问题15练习1答案16定义设原线性规划问题为则称下列线性规划问题为其对偶问题，其中yi(i=1,2,…,m)称为对偶变量。上述对偶问题称为对称型对偶问题。原问题简记为(P)，对偶问题简记为(D)17例3：求线性规划问题的对偶规划解：由原问题的结构可知为对称型对偶问题18例4：求线性规划问题的对偶规划解：由原问题的结构可知不是对称型对偶问题，可先化为对称

6、型，再求其对偶规划。19例5：求线性规划问题的对偶规划解：由原问题的结构可知不是对称型对偶问题，可先化为对称型，再求其对偶规划。20上式已为对称型对偶问题，故可写出它的对偶规划令则上式化为21对偶关系对应表LPDP目标maxmin变量n个约束n个≥0≥≤≤无约束=约束m个变量m个≥≤0≤≥0=无约束22例223LP约束DP变量例2答案24LP变量DP约束25目标函数2627练习228练习2答案292对偶理论30定理1对偶问题的对偶问题是原问题。MaxW’=-Ybs.t.-YA≤-CY≥0MinZ’=-CX

7、s.t.-AX≥-bX≥0MaxZ=CXs.t.AX≤bX≥0MinW=Ybs.t.YA≥CY≥0对偶的定义对偶的定义31定理2（弱对偶性）设X，Y分别是（P）、（D）的任一可行解，则引申：若（P）有可行解，但无最优解，则对偶问题（D）无可行解。证明：由AXb,y0有yAXby由AyC,X0有yAXCX所以CXyAXyb32推论2、(P)有可行解,但无有限最优解，则(D)无可行解。定理3、yX,分别为(P),(D)的可行解，且XyC=b,则它们是(P),(D)的最优解。证明：对任X，有CX

8、by=CXX最优推论1、(P),(D)都有可行解，则必都有最优解。33定理4(主对偶定理)若一对对偶问题(P)和(D)都有可行解，则它们都有最优解，且目标函数的最优值必相等。证明：(1)当X*和Y*为原问题和对偶问题的一个可行解有原问题目标函数值对偶问题目标函数值所以原问题的目标函数值有上界，即可找到有限最优解；对偶问题有下界，也存在有限最优解。34(2)当X*为原问题的一个最优解，B为相应的最优基,通过引入松弛变量Xs,