对偶问题的基本性质

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,返回,上页,下页,对偶问题,返回,继续,第二节对偶问题的基本性质,引例,对称性,弱对偶性,最优性,对偶性（强对偶性）,互补松弛性,1,对,偶,问,题,原,问,题,收,购,厂,家,引例,2,（ ）,原问题,的变量,原问题松弛变量,对偶问题,剩余变量,对偶问题的变量,化为极小问题,原问题化为极小问题，最终单纯形表：,3,原问题的变量,原问题松弛变量,对偶问题剩余变量,对偶问题的变量,对偶问题用两阶段法求解的最终的单纯形表,4,（ ）,原问题,的变量,原问题松弛变量,对偶问题,剩余变量,对偶问题的变量,化为极小问题,原问题,最优解,对偶问题,最优解,原问题化为极小问题，最终单纯形表：,5,两个问题作一比较:,1.两者的最优值相同,2.变量的解在两个单纯形表中互相包含,原问题最优解,（决策变量）,对偶问题最优解,（决策变量）,对偶问题的松弛变量,原问题的松弛变量,6,从引例中可见：,原问题与对偶问题在某种意义上来说，实质上是一样的，因为第二个问题仅仅在第一个问题的另一种表达而已。,理论证明：,原问题与对偶问题解的关系,7,对偶问题的基本性质,一、对称定理：,定理对偶问题的对偶是原问题,。,设原问题（1） 对偶问题（2）,8,二、弱对偶性定理：,若 和 分别是原问题（1）及对偶问题（2）的可行解，则有,证明：,对偶问题的基本性质,9,从弱对偶性可得到以下重要结论：,（1）极大化问题（原问题）的任一可行解所对应的目标函数值是对偶问题最优目标函数值的下界。,（2）极小化问题（对偶问题）的任一可行解所对应的目标函数值是原问题最优目标函数值的上界。,（3）若原问题可行，但其目标函数值无界，则对偶问题无可行解。,10,（4）若对偶问题可行，但其目标函数值无界，则原问题无可行解。,（5）若原问题有可行解而其对偶问题无可行解，则原问题目标函数值无界。,（6）对偶问题有可行解而其原问题无可行解，则对偶问题的目标函数值无界。,原问题,对偶问题,11,三、最优性定理：,若 和 分别是（1）和（2）的可行解，且有 则 分别是（1）和（2）的最优解 。,则 为（1）的最优解，,反过来可知： 也是（2）的最优解。,证明：因为（1）的任一可行解 均满足,对偶问题的基本性质,12,证明：,原问题与对偶问题的解一般有三种情况,：,一个有有限最优解 另一个有有限最优解。,一个有无界解 另一个无可行解。,两个均无可行解。,四、对偶定理（强对偶性）：,若原问题及其对偶问题均具有可行解，则两者均具有最优解，且它们最优解的目标函数值相等,。,对偶问题的基本性质,13,五、互补松弛性：,若 分别是原问题（1）与对偶问题（2）的可行解， 分别为（1）、（2）的松弛变量，则：,即：,为最优解,原问题第,i,条约束,A,的第,i,行,14,说明：,在线性规划问题的最优解中，如果对应某一约束条件的对偶变量值为非零，则该约束条件为严格等式；反之如果约束条件为严格不等式，则其对应的对偶变量一定为零。,另一方面：,对偶问题的第,j,条约束,15,互补松弛定理应用：,（1）从已知的最优对偶解，求原问题最优解，反之亦然。,（2）证实原问题可行解是否为最优解。,（3）从不同假设来进行试算，从而研究原始、对偶问题最优解的一般性质。,（4）非线性的方面的应用。,以上性质同样适用于非对称形式。,16,返回,结束,对偶问题的基本性质,17,