运筹学对偶问题.ppt

《运筹学对偶问题.ppt》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、第四章对偶问题对偶问题的一般形式对偶问题的经济意义对偶性质对偶单纯形法对偶单纯形法的解题原理一、对偶问题的一般形式若设一线性规划问题如下：（A）则以下线性规划问题：（B）称为原问题（A）的对偶线性规划问题，或称A、B互为对偶问题。如果采用向量、矩阵来表示（A）（B）其中：可以将以上关系列成以下对偶表：maxminx1x2…xnby1a11a12…a1n≤b1y2a21a22…≤b2…………………ymam1am2…amn≤bm≥≥…≥cc1c2…cn例写出下列线性规划问题的对偶问题解：可以将原问题的有关参数列成下表maxminx1x2x3by1142≤48y2124≤60≥≥≥c6141

2、3∴对偶规划问题为比较以上我们介绍的对偶问题是严格定义的对偶问题，也成为对称对偶问题。它满足两个条件：两个条件：1、所有变量非负：即X>0，Y>02、约束条件均为同向不等式。若原问题约束条件均为“≤”，则它的对偶问题的约束条件都是“≥”。当原问题的约束条件的符号不完全相同时，也存在对偶问题，这种对偶问题称为非对称对偶问题。例分析：为求对偶问题，可先做过渡，将问题对称化：对称化则，原问题变为（A）（A‘）则（A’）的对偶问题如下：（B‘）（A‘）对比结果以上对偶问题（B‘）并非原问题（A）的对偶问题，它是线性规划问题（A’）的对偶问题。（A）（B‘）调整对照问题B‘目标函数系数的符号与原

3、问题A中约束条件右端常数项的符号，可做以下调整：令y1=y1’，y2=-y2’，y3=y4’-y3’令y1=y1’，y2=-y2’，y3=y4’-y3’则得到以下对偶问题（B‘）（B）合并（B）比较对于任何一个线性规划问题，我们都可以求出它的对偶问题。（A）（B）原问题与对偶问题的相应关系原问题A（对偶问题B）对偶问题B（原问题A）最大化max最小化minA系数矩阵ATB右端常数（列向量）目标函数系数(行向量)C目标函数系数右端常数（列向量）第i个约束条件为等式“=”yi为自由变量第i个约束条件为不等式“≤”yi≥0第i个约束条件为不等式“≥”yi≤0xj为自由变量第j个约束条件为等式

4、“=”xj≥0第j个约束条件为不等式“≥”xj≤0第j个约束条件为不等式“≤”例：写出下列问题的对偶形式：解：例：写出下列问题的对偶问题解：二、对偶问题的经济意义：若原规划问题是“在一定条件下，使工作或成果（产品产量、利润等）尽可能的大”，那么它的对偶问题就是“在另外一些条件下，使工作的消耗（浪费、成本等）尽可能的小”。实际上是一个问题的两个方面。例：某产品计划问题的线性规划数学模型为假设生产部门根据市场变化，决定停止生产甲、乙产品，而将原有的原料、设备专用于接受外来订货以生产市场急需的紧俏商品，则需要考虑决策的问题就是“在什么样的价格条件下，才能接受外来订货？”。问题的实质就是如何

5、确定原料、设备的收费标准？分析若设y1为单位原材料的价格，y2为设备单位台时价格，由于用了3个单位原料和5个单位设备台时就可以生产一个单位甲产品而获利2个单位，现在不生产甲产品，转而接受外来订货加工，则收取的费用不能低于2个单位，否则自己生产甲产品更有利。因此，可以得到下面的条件：分析同理，将生产乙产品的原料和设备工时用于接受外来加工订货，收取的费用不能低于乙产品的单位利润1个单位：分析另外，为了争取外来加工订货，在满足上述要求的基础上，收费标准应尽可能低从而具有竞争力，因此总的收费w=15y1+10y2应极小化。这样，就得到一个目标函数：这样，就得到另一个线性规划模型：比较生产问题（

6、要利用资源）资源利用问题（会影响生产）第二节对偶理论定理1（对称性定理）对偶问题（B）的对偶规划为线性规划（A）对称性定理是很重要的。它表明原规划问题（A）和对偶规划问题（B）是互为对偶的。也就是说，如果（B）是（A）的对偶，那么（A）也是（B）的对偶。这就为以后的讨论带来方便。不难理解，如果当A具有某种性质时可以推出B的某些性质，于是可以无需另加证明地得到：当B具有某种性质时，问题A也具有那些性质。定理2（弱对偶定理）当原问题A是求最大值max，而对偶问题是求最小值时，如果X0是原问题的任意可行解，Y0是对偶问题的任意可行解，则有以下关系式成立：定理3（最优性定理）设和分别是问题A和

7、B的可行解，若相应于和，A和B的目标函数值相等，即，则和分别是A和B的最优解。定理4（无界性定理）如果原问题A的目标函数值无界，则对偶问题B无可行解；如果对偶问题B的目标函数值无界，则原问题A无可行解。以上三个定理可以这样记忆原问题A和对偶问题B如果有可行解，则它们的可行解区域只可能相接，不可能相交。两个区域的交界线即是它们的最优解，如果原问题A的目标函数无界，意味着可行解区域无界，向外扩张，挤占了对偶问题B的可行解区域，则对偶问题无可行解，反