双重问题的基本性质.ppt

返回;对 偶 问 题;（ ）;原问题的变量;（ ）;两个问题作一比较: 1.两者的最优值相同 2.变量的解在两个单纯形表中互相包含 原问题最优解（决策变量） 对偶问题最优解（决策变量）;从引例中可见： 原问题与对偶问题在某种意义上来说，实质上是一样的，因为第二个问题仅仅在第一个问题的另一种表达而已。;对偶问题的基本性质;二、弱对偶性定理： ——若 和 分别是原问题（1）及对偶问题（2）的可行解，则有 ;从弱对偶性可得到以下重要结论：;（4）若对偶问题可行，但其目标函数值无界，则原问题无可行解。 （5）若原问题有可行解而其对偶问题无可行解，则原问题目标函数值无界。 （6）对偶问题有可行解而其原问题无可行解，则对偶问题的目标函数值无界。;三、最优性定理： ——若 和 分别是（1）和（2）的可行解，且有 则 分别是（1）和（2）的最优解 。 ;证明： 原问题与对偶问题的解一般有三种情况： 一个有有限最优解 另一个有有限最优解。 一个有无界解 另一个无可行解。 两个均无可行解。;五、互补松弛性： ——若 分别是原问题（1）与对偶问题（2）的可行解， 分别为（1）、（2）的松弛变量，则： 即： ; 说明：在线性规划问题的最优解中，如果对应某一约束条件的对偶变量值为非零，则该约束条件为严格等式；反之如果约束条件为严格不等式，则其对应的对偶变量一定为零。;互补松弛定理应用： （1）从已知的最优对偶解，求原问题最优解，反之亦然。 （2）证实原问题可行解是否为最优解。 （3）从不同假设来进行试算，从而研究原始、对偶问题最优解的一般性质。 （4）非线性的方面的应用。;返回