运筹学07-对偶理论与灵敏度分析II-113.ppt

《运筹学07-对偶理论与灵敏度分析II-113.ppt》由会员分享，可在线阅读，更多相关《运筹学07-对偶理论与灵敏度分析II-113.ppt（38页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第7讲 对偶理论与灵敏度分析II7.1 对偶问题的基本性质7.2 对偶解的经济含义影子价格7.3 对偶单纯形法7.1 对偶问题的基本性质o对称性对称性o弱对偶性弱对偶性o最优性最优性o对偶性（强对偶性）对偶性（强对偶性）o互补松弛性互补松弛性(1)对称性 对偶问题对偶问题对称性定理对称性定理：对偶问题的对偶是原问题。：对偶问题的对偶是原问题。对偶问题对偶问题max z=CXs.t.AX b X 0max w =bTYs.t.ATY CTY 0min w=bTYs.t.ATY CT Y 0min z =CXs.t.AX b X 02.弱对偶性原问题(LP)对偶问题(DP)弱对偶定理弱对偶定理 若

2、若 和和 分别是原问题分别是原问题(LP)(LP)和对偶问题和对偶问题(DP)(DP)的的可行解，则有可行解，则有 原问题的目标函数值对偶问题的目标函数值证明：o极大化问题(原问题)任一可行解对应的目标函数值不可能超过其对偶问题任一可行解对应的目标函数值。根据弱对偶定理：根据弱对偶定理：s.t.LPs.t.DP生产安排问题资源定价问题一对对偶问题可行解X=(1,2)T,z=11可行解Y=(1,2,1)T,w=253.最优性最优性定理最优性定理 若若 和和 分别是原问题和对偶问题的可行解，且有分别是原问题和对偶问题的可行解，且有 则则 和和 分别是原问题和对偶问题的最优解。分别是原问题和对偶问题

3、的最优解。证明：设证明：设X为为LP的任一可行解，由弱对偶定理的任一可行解，由弱对偶定理因为因为 ，所以，对于，所以，对于LP的任一可行解的任一可行解X，有，有所以，所以，为为LP的最优解。类似地，可证的最优解。类似地，可证 为为DP的最优解。的最优解。o根据弱对偶定理和最优性定理，如果X为原问题的一个可行解，Y为对偶问题的一个可行解，只要有其中一个不是最优解，则必然有CXbTY成立，而只有当X和Y均为最优解的时候，才有CX=bTYs.t.LPs.t.DP生产安排问题资源定价问题对偶可行解X=(4,2)T,z=20可行解Y=(2,1,0)T,w=20最优解最优解4.强对偶性对偶定理对偶定理 若

4、若原原问问题题有有最最优优解解，则则其其对对偶偶问问题题也也具具有有最最优优解解，且且两者的最优解对应的目标函数值相等。两者的最优解对应的目标函数值相等。设X*为原问题的最优解，对应的最优基为B，由于X*为原问题的最优解，必定所有的检验数小于等于零，即令说明Y是对偶问题的一个可行解，对应的目标函数值：由最优性定理，Y是对偶问题的最优解。推论：对偶解定理推论：对偶解定理若用单纯形法解原问题若用单纯形法解原问题LP，得有最优解，得有最优解X*，相应的最，相应的最优基为优基为B，则，则 Y*=(CBB-1)T为其对偶问题为其对偶问题DP的最优解的最优解 原问题的检验数与对偶问题的解之间的对应关系原问

5、题(LP)对偶问题(DP)兼容性定理：原问题的检验数对应于对偶问题的一个基本解兼容性定理：原问题的检验数对应于对偶问题的一个基本解o在用单纯形法求解原问题的过程中，每一步中间迭代过程的检验数行对应于其对偶问题的一个基本解(但不可行)；只有当原问题达到最优解时，其检验数行对应于其对偶问题的一个基本可行解，并且该基本可行解即为其对偶问题的最优解。利用原问题的最优单纯形表求对偶问题最优解利用原问题的最优单纯形表求对偶问题最优解cBsxBsc0 xs检验数cBcN0 xBxNxsBNIcBcN0bb0cBcBxBxBIB-1NB-1b0cN-cBB-1N-cBB-1-cBB-1bB-1Y*=(CBB-

6、1)T例例7.1 求如下求如下 LP 问题的对偶问题的最优解问题的对偶问题的最优解max z=4x1+3x2+7x3 s.t.x1+2x2+2x3 100 3x1+x2+3x3 100 x1,x2,x3 0 解：解：对偶问题为对偶问题为min w=100y1+100y2 s.t.y1+3y2 4 2y1+y2 3 2y1+3y2 7 y1,y2 0 ccBxB37x2x3检验数43700 x1x2x3x4x5-3/4103/45/401-1/4-5/200-1/2b2525-250-1/21/2-2原问题的最优解和最优值为：原问题的最优解和最优值为：x*=(0,25,25)T z*=250由对

7、偶解定理可知：由对偶解定理可知：对偶问题的最优解和最优值为对偶问题的最优解和最优值为 y*=(1/2,2)T w*=2505.互补松弛性互补松弛定理互补松弛定理LP的可行解的可行解 与与DP的可行解的可行解 是最优解的充分必要条件是：是最优解的充分必要条件是：orLP问题和DP问题最优解之间的互补松弛关系图解maxz=CXs.t.AX+XS=bX,XS0minw=bTYs.t.ATY-YS=CTY,YS0maxz=CXs.t.AXbX0minw=bTYs.t.ATYCTY0对偶引进松弛变量引进剩余变量(X)TYS=0(Y)TXS=0互补松弛关系X，XsY，Ys由于所有的变量均为非负，要使求和式

8、等于零，则每一个分量必定为零，从而有下列关系成立：原问题、对偶问题的原问题、对偶问题的最优解最优解与与松弛变量松弛变量之间的关系之间的关系原问题原问题(对偶问题对偶问题)最优解中某一个分量最优解中某一个分量=0对偶问题对偶问题(原问题原问题)中该分量对应的约束以等式成立中该分量对应的约束以等式成立以最优解代入原问题以最优解代入原问题(对偶问题对偶问题)的约束条件，为严的约束条件，为严格不等式格不等式(松弛变量松弛变量=0)对偶问题对偶问题(原问题原问题)的最优解中该约束条件的对应分的最优解中该约束条件的对应分量量=0o例7.2：利用互补松弛定理求最优解maxs.t.已知原问题的最优解是已知原问

9、题的最优解是求对偶问题的最优解。求对偶问题的最优解。解：解：设对偶变量为设对偶变量为mins.t.则对偶问题为则对偶问题为设对偶问题的最优解为设对偶问题的最优解为因因由互补松弛性知由互补松弛性知解方程组得解方程组得故对偶问题的最优解为故对偶问题的最优解为o例7.3：利用互补松弛定理求最优解已知原问题的最优解是已知原问题的最优解是maxs.t.求对偶问题的最优解。求对偶问题的最优解。mins.t.将将 代入原问题约束条件得代入原问题约束条件得由互补松弛性知由互补松弛性知又又故对偶问题的最优解为故对偶问题的最优解为得得例例7.4 7.4 利用互补松弛定理求最优解利用互补松弛定理求最优解已知其对偶问

10、题的最优解是已知其对偶问题的最优解是mins.t.求原问题的最优解。求原问题的最优解。对偶问题为对偶问题为设原问题的最优解为设原问题的最优解为maxs.t.将将 代入对偶问题约束条件得：代入对偶问题约束条件得：(2)、(3)、(4)为严格不等式为严格不等式由互补松弛性知由互补松弛性知又因又因由互补松弛性知由互补松弛性知得得故原问题最优解为故原问题最优解为7.2 对偶解的经济含义原问题原问题(LP)对偶问题对偶问题(DP)对偶解定理对偶解定理：若用单纯形法解原问题：若用单纯形法解原问题LP，得有最优解，得有最优解X*，相应，相应的最优基为的最优基为B，则对偶解为，则对偶解为在最优解处，原问题和对

11、偶问题的目标函数值相等在最优解处，原问题和对偶问题的目标函数值相等是原问题中m个约束条件的右端常数，反映了m种资源的限制，而z*则是在这m种资源的限制条件下所达到的目标函数的最优值。现在的问题是，如果某些资源的限制条件发生了变化，那么目标函数的最优值如何变化呢？例如，如果第i个约束条件的右端常数增加了1个单位，那么目标函数的最优值的改变量是多少呢？我们假设右端常数增加1个单位非常微小，不会对原问题的最优基产生影响，即最优基仍为B，从而对偶问题的最优解不会发生改变，仍为CBB-1可以看到，在其他条件不发生变化的情况下，第i个约束的右端常数增加1个单位，所引起的目标函数最优值的改变量为yi*，即该

12、资源约束对应的对偶问题的最优解分量反映了目标目标函数的最优值关于该资源的变化率函数的最优值关于该资源的变化率，也即yi*是第i种资源的拥有量变化所引起的目标函数最优值的改变量，反映了该种资源对目标函数的贡献程度，或者说该种资源的价值，这一价值被形象地称为“影子价格”。影子价格影子价格在对偶问题的互补松弛性中若若 ，则，则若若 ，则，则说说明明若若某某资资源源 未未被被充充分分利利用用，则该种资源的影子价格为则该种资源的影子价格为0 0；若若某某资资源源的的影影子子价价格格不不为为0 0，则则说说明已有资源在已消耗完毕。明已有资源在已消耗完毕。影子价格的大小客观地反映了资源在系统内的稀缺程度。如

13、果第影子价格的大小客观地反映了资源在系统内的稀缺程度。如果第 i i 种资源在系统内供大于求，即在达到最优解时，该资源并没有用完，种资源在系统内供大于求，即在达到最优解时，该资源并没有用完，该资源的影子价格为该资源的影子价格为0 0。它表明了，增加该资源的供应不会引起系统。它表明了，增加该资源的供应不会引起系统目标值的增加。目标值的增加。资源的影子价格越高，说明资源在系统内越稀缺，而增加该资源的资源的影子价格越高，说明资源在系统内越稀缺，而增加该资源的供应量对系统目标函数值的贡献也越大。供应量对系统目标函数值的贡献也越大。7.3 对偶单纯形法o在前面讲过，在用单纯形表求解原问题的过程中，检验数

14、行对应的是其对偶问题的基本解，当原问题达到最优解时，即可由检验数行同时得到其对偶问题的最优解。原问题对偶问题基可行解基解检验数是否最优解非可行解可行解换基迭代否是原始单纯形法从一个基本可行解迭代到下一个基本可行解时，总是保原始单纯形法从一个基本可行解迭代到下一个基本可行解时，总是保持解的可行性不变，变化的只是检验数持解的可行性不变，变化的只是检验数 例如对于极大化问题而言，检验向量从部分分量不满足例如对于极大化问题而言，检验向量从部分分量不满足 逐步过渡到逐步过渡到 ，一旦达到一旦达到 ，也就达到了最优解。，也就达到了最优解。由于由于 ，是对偶问题的可行解。是对偶问题的可行解。可以这样理解原始

15、单纯形法的迭代过程：可以这样理解原始单纯形法的迭代过程：从基本可行解向最优解的迭从基本可行解向最优解的迭代过程，是在始终保持原问题解的可行性条件下，其对偶解由不可行代过程，是在始终保持原问题解的可行性条件下，其对偶解由不可行向可行转化。一旦对偶解也成为可行解时，原问题的可行解即成为最向可行转化。一旦对偶解也成为可行解时，原问题的可行解即成为最优解。优解。也就是说，当原问题解保持可行性条件下，其最优性条件与对偶解可也就是说，当原问题解保持可行性条件下，其最优性条件与对偶解可行这个条件是一致的。行这个条件是一致的。o这为我们提供了另一条求解思路：在迭代过程中，始这为我们提供了另一条求解思路：在迭代

16、过程中，始终保持对偶问题解的可行性，而原问题的解由不可行终保持对偶问题解的可行性，而原问题的解由不可行向可行性转化，一旦原问题的解也满足可行性条件，向可行性转化，一旦原问题的解也满足可行性条件，也就达到了最优值。这就是对偶单纯形方法的思路。也就达到了最优值。这就是对偶单纯形方法的思路。o对偶单纯形法并不需要把原问题转化为对偶问题，而对偶单纯形法并不需要把原问题转化为对偶问题，而是利用原问题与对偶问题的数据相同，只是所处的位是利用原问题与对偶问题的数据相同，只是所处的位置不同这一特点，直接在反映原问题的单纯形表上进置不同这一特点，直接在反映原问题的单纯形表上进行运算。行运算。对偶单纯形法的基本思

17、路 原始单纯形法保持b列0行由不满足0 对偶单纯形法保持行0b列由不满足0b列0,行0问题达到最优解保持原问题解的可行性，对偶问题的解由不可行到可行保持对偶问题解的可行性，原问题的解由不可行到可行当原问题和对偶问题的解都达到可行时，两者也达到最优(2)确定换出变量确定换出变量 根根据据 ，确确定定基基变变量量 xl 作作为为换换出出变变量量。检验检验 xl 所在行各元素所在行各元素若所有若所有alj 0,则无可行解，停止计算。否则转入则无可行解，停止计算。否则转入()，(3)确定换入变量确定换入变量按最小比值原则，若按最小比值原则，若确定非基变量确定非基变量 xk 为换入变量。为换入变量。(4

18、)以以alk 为主元进行旋转变换，得新的单纯形表，重复为主元进行旋转变换，得新的单纯形表，重复 (2)-(4)直到求得最优解。直到求得最优解。对偶单纯形法的计算步骤如下（对于极大化目标函数问题）：对偶单纯形法的计算步骤如下（对于极大化目标函数问题）：(1)根根据据原原始始线线性性规规划划，列列出出初初始始单单纯纯形形表表，检检查查b列列数数字字和和检检验验行行元元素素，若若b列列数数字字全全部部非非负负，检检验验数数全全部部非非正正，则则已已经经求求得得最最优优解解，停停止止计计算算。若若b列列中中至至少少有有一一个个负负分分量量，检检验验数数全全部部非正非正，则转入（，则转入（2）,例例7.

19、5 7.5 用对偶单纯形法求解用对偶单纯形法求解对偶单纯形允许约束方程右端为负，对偶单纯形允许约束方程右端为负，因此可将方程因此可将方程2 2，3 3两端同乘两端同乘-1-1，可得含单位矩阵的标准型：可得含单位矩阵的标准型：解：先化为标准型解：先化为标准型据此列出初始单纯形表，并施行对偶单纯形法迭代步骤如下：据此列出初始单纯形表，并施行对偶单纯形法迭代步骤如下：-5/4-7/4 000-1/4 1/4 0102x2-2-1/4-3/4 0014x1-3 5/4 3/4 1004x3 0-2/3 000-7/3-1/3 0011/3 10/3 x2-21/3 100-4/3-16/3 x4 0101018 x3 0000-2-3100-3-1-10 x5 00101-1-2 x4 00013218 x3 0 x5 x4 x3 x2 x1 b XB CB 000-2-3 C可得最优解可得最优解