2对偶理论与灵敏度分析.ppt

《2对偶理论与灵敏度分析.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、线性规划与单纯形法回顾线性规划问题建模图解法最优解必在顶点模型标准型式基本可行解单纯形法单纯形表第二章对偶理论与灵敏度分析DualTheoryandSensitivityAnalysis运筹学OperationsResearch2.1线性规划的对偶理论2.2灵敏度分析2.1线性规划的对偶理论一、对偶问题的提出与模型1、对偶问题的提出[例1]第一章中的例1。[例2]这时有另厂提出要购买A、B、C全部资源，在原厂可接受的条件下，单价多少可使另厂付费最低？例1称为例2的原问题，记为(P)例2称为例1的对偶问题，记为(D)2、对偶模型的一般形式以例2为例，原问题为：(P)：记Y＝(y1,y2,y3)

2、，则对偶问题为：(D)：这是最常见的对偶模型形式，称为对称式对偶模型。二者间具有十分对称的对应关系。对偶模型的特点：（1）P为max型，D为min型（2）P的变量个数＝D的约束个数（3）P的约束个数＝D的变量个数（4）P的目标函数系数＝D的资源限制向量（5）P的资源限制向量＝D的目标函数系数（6）P的技术系数矩阵＝D的技术系数矩阵转置(P)：(D)：（7）若P的某个约束为“=”型，则D的相应变量为自由；若P的某个变量为自由，则D的相应约束为“=”型。令y3'＝y3-y4,，则有：3、如何写出LP模型的对偶模型（1）若LP为max型，则尽量化成(P)形式。（等式、自由变量不用转换）(P)(D)（

3、2）若LP为min型，则尽量化成(D)形式。（等式、自由变量不用转换）[例3]写出下面线性规划的对偶规划模型。解：设对偶变量为y1,y2,y3，对偶目标为w，则其对偶规划模型为：[练习]写出下面LP的对偶模型。对偶模型为：二、对偶性质与定理1、对称性：（P）与（D）互为对偶。2、弱对偶性设X、Y分别为（P）、（D）的任一可行解，则由此可推出：3、无界性若（P）为无界解，则（D）无可行解；若（D）为无界解，则（P）无可行解。4、解的最优性5、对偶定理若（P）有最优解，则（D）也有最优解，且二者最优值相等。则设分别为（P）、（D）的可行解，且问题：（1）由性质5可知，对偶问题最优解的表达式Y*=？

4、Y*=CBB-1；其中B为原问题的最优基。（2）求Y*是否有必要重新求解（D）？CX0XSCBB-1bB-1AB-1C-CBB-1A-CBB-1Y*即为（P）终表的XS的检验数的负值；若无XS，则用Y*=CB*(B*)-1计算。[例4]已知求解下列LP模型的单纯形终表如下，求其对偶模型的最优解。cj→2.5100CBXBB-1bx1x2x3x40x39019/51-3/52.5x1212/501/5000-0.5X*=（2，0，9，0）T;z*=5Y*=（0，0.5）;w*=56、松紧定理（互补松弛性）说明：在线性规划问题的最优解中，若对应某一约束条件的对偶变量值为非零，则该约束条件取严格

5、等式；另一方面，如果约束条件取严格不等式，则其对应的变量一定为零。设分别为（P）、（D）的可行解，则有：原问题的变量X在一对变量中，其中一个大于0，另一个一定等于0。松弛变量Xs松弛变量Ys对偶问题的变量Y[例5]已知线性规划问题已知其对偶问题的最优解为：y1*=4/5，y2*=3/5，z*=5试用对偶理论找出原问题的最优解。[练习]已知线性规划问题已知原问题的最优解为：x1*=2，x2*=2，x3*=4，x4*=0试用对偶理论找出对偶问题的最优解。三、对偶问题的经济解释1、对偶最优解的经济解释——资源的影子价格（ShadowPrice）Y*=(y1*,y2*,……，ym*）为DP的最优解，则

6、yi*表示LP某资源bi变化1个单位对目标产生的影响，称yi*为bi的影子价格。CBB-1——对偶问题的最优解——买主的最低出价——原问题资源的影子价格——当该资源增加1单位时引起的总收入的增量——卖主的内控价格。[例6]例1的单纯形终表如下：请指出资源A、B、C的影子价格，并解释其经济意义。cj→23000CBXBB-1bx1x2x3x4x52x141001/400x5400–21/213x22011/2–1/8000–3/2–1/80影子价格在管理决策中的作用：（1）影子价格≠市场价格若影子价格＞市场价格，则应影子价格＜市场价格，则应买进该资源卖出该资源（2）影子价格反映了资源的稀缺性

7、，影子价格越高，则越稀缺。例如：资源C的影子价格为0，则表明有剩余。2、对偶约束的经济解释——产品的机会成本（OpportunityCost）机会成本：是指为了得到某种东西而所要放弃另一些东西的最大价值。机会成本小的具有比较优势，即把一定资源投入某一用途后所放弃的在其他用途中所能获得的最大利益。例如：某块土地如果选择养某种家禽就不能选择养其他家禽。假设养猪可以获得9万元，养鸡可以获得7万元，养鸭可