运筹学课件(对偶理论)分析.ppt

《运筹学课件(对偶理论)分析.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、对偶理论(DualityTheory)对偶问题的提出线性规划的对偶理论对偶问题的经济解释----影子价格对偶单纯形法一、问题的提出对偶性是线性规划问题的最重要的内容之一。每一个线性规划（LP）必然有与之相伴而生的另一个线性规划问题，即任何一个求maxZ的LP都有一个求minZ的LP。其中的一个问题叫“原问题”，记为“P”，另一个称为“对偶问题”，记为“D”。例一、资源的合理利用问题已知资料如表所示，问应如何安排生产计划使得既能充分利用现有资源有使总利润最大？单件产消耗品资源甲乙资源限制A52170（钢材

2、）B23100（煤炭）C15150（设备）单件利润1018下面从另一个角度来讨论这个问题：假定：该厂的决策者不是考虑自己生产甲、乙两种产品，而是将厂里的现有资源用于接受外来加工任务，只收取加工费。试问该决策者应制定怎样的收费标准（合理的）？分析问题：1、每种资源收回的费用不能低于自己生产时的可获利润；2、定价又不能太高，要使对方能够接受。一般而言，W越大越好，但因需双方满意，故为最好。该问题的数学模型为：例二、合理配料问题，其数学模型为：假设工厂想把这m种营养成分分别制成一种营养丸销售，问如何定价（以保

3、证总收入为最多）？原问题对偶问题目标函数maxmin约束条件≤≥变量数量约束条件个数约束条件个数变量数量例三、23x1x2原问题12y122≤128y212≤816y340≤1612y404≤12对偶问题23二、线性规划的对偶理论（一）、对偶问题的形式1、对称型对偶问题：已知P，写出D。例一、写出线性规划问题的对偶问题解：首先将原式变形注意：以后不强调等式右段项b≥0，原因在对偶单纯型表中只保证而不保证，故b可以是负数。2、非对称型对偶问题例二、原问题2、混合型对偶问题例三、原问题对偶问题综上所述，其变

4、换形式归纳如下：原问题（或对偶问题）对偶问题（或原问题）目标函数max目标函数min约束条件m个m个变量≤≥0≥≤0=无约束变量n个n个约束条件≥0≥≤0≤无约束=约束条件右端项目标函数变量的系数目标函数变量的系数约束条件右端项例四、线性规划问题如下：minZ’=-CXs.t.-AX≤-bX≥0（二）、对偶问题的性质1、对称性定理：对偶问题的对偶是原问题。minW=Ybs.t.YA≥CY≤0maxZ=CXs.t.AX≥bX≥0对偶的定义对偶的定义maxW’=-Ybs.t.YA≥CY≤02、弱对偶原理（弱

5、对偶性）：设和分别是问题（P）和（D）的可行解，则必有推论⑴.若和分别使问题（P）和（D）的可行解，则是（D）的目标函数最小值的一个下界；是（P）的目标函数最大值的一个上界。推论⑵.在一对对偶问题（P）和（D）中，若其中一个问题可行但目标函数无界，则另一个问题不可行；反之不成立。这也是对偶问题的无界性。关于无界性有如下结论：原问题对偶问题问题无界无可行解无可行解问题无界无界无可行解如：（原）（对）推论⑶.在一对对偶问题（P）和（D）中，若一个可行（如P），而另一个不可行，（如D），则该可行的问题无界。例

6、一、试估计它们目标函数的界，并验证弱对偶性原理。（P）26解：（D）由观察可知：=（1.1.1.1），=（1.1），分别是（P）和（D）的可行解。Z=10，W=40，故有，弱对偶定理成立。由推论⑴可知，W的最小之不能小于10，Z的最大值不能超过40。＜例二、已知试用对偶理论证明原问题无界。解：=（0.0.0）是P的一个可行解，而对D的第一个约束条件不能成立（因为y1,y2≥0)。因此，对偶问题不可行，由推论⑶可知，原问题无界。例3、已知显然，这两个问题都无可行解。3、最优性判别定理：若X*和Y*分别是P

7、和D的可行解且CX*=Y*b，则X*.Y*分别是问题P和D的最优解。例如，在例1中，可找到X*=（0.0.4.4），Y*=（1.2.0.2）,则Z=28，W=28.故X*.Y*分别是P和D的最优解。224、对偶定理（强对偶性）：若一对对偶问题P和D都有可行解，则它们都有最优解，且目标函数的最优值必相等。推论⑷.若P和D的任意一个有最优解，则另一个也有最有解，且目标函数的最优值相等。综上所述，一对对偶问题的关系，只能有下面三种情况之一出现：①.都有最优解，分别设为X*和Y*，则必有CX*=Y*b；②.一个

8、问题无界，则另一个问题无可行解；③.两个都无可行解。5、互补松弛定理：设X*和Y*分别是问题P和D的可行解，则它们分别是最优解的充要条件是同时成立一般而言，我们把某一可行点（如X*和Y*）处的严格不等式约束（包括对变量的非负约束）称为松约束，而把严格等式约束称为紧约束。所以有如下推论：设一对对偶问题都有可行解，若原问题的某一约束是某个最优解的松约束，则它的对偶约束一定是其对偶问题最优解的紧约束。例4、已知试通过求对偶问题的最优解来求解原问题