第章 对偶理论.docVIP

第3章 对偶理论 §3.1 线性规划的对偶理论 3.1.1 对偶问题的表述 对称形式的对偶： （L） (D) s.t. s.t. 其中为维行向量，为矩阵，为维列向量，表示维列向量，表示维行向量。 称(D)为线性规划(L)的对偶规划问题。 定理1 (L)与(D)互为对偶规划问题。――（对合性） 例 设原问题 对偶问题 非对称形式的对偶： （LP） (DP) s.t. s.t. 例 设原问题 对偶问题 一般线性规划问题： 可化为上述二者之一讨论其对偶问题，也可直接写出对偶问题，详细的对应法则见教材（陈宝林）124页。 直接写出对偶的弊端之一是对偶最优解不易确定，而对称形式和非对称形式对偶的最优解都可由原问题的单纯形乘子确定出来。 3.1.2 对偶定理(强对偶定理和弱对偶定理) 定理2 (弱对偶定理)：设和分别是 （L） 和 (D) s.t. s.t. 的可行解，则有下列不等式成立： 证明：由于和，则有。 由于和，则有。 因此有 推论1 设和分别是(L)和(D)的可行解，且有，则和分别是(L)和(D)的最优解。 推论2 如果(L)的目标函数在可行集上无下界，则对偶规划(D)无可行解。 推论3 如果(D)的目标函数在可行集上无上界，则原始规划(L)无可行解。 定理3 (强对偶定理)：如果互为对偶规划的两个问题之一有最优解，则另一个问题也有最优解，并且二者的目标值相等。 证明：设原问题（L）存在最优解，引进松弛变量，写成等价形式： （1） 由于（1）存在最优解，因此可以用单纯形方法求出它的一个最优基本可行解，不妨设该最优解是，相应的最优基是B。此时所有判别数均非正，即 （2） 为单纯形乘子。 考虑所有原来变量（不包括松弛变量）在基B下的判别数，把它们所满足的条件（2）用矩阵形式写出： 或 （3） 把所有松弛变量在基B下的判别数所满足的条件（2）用矩阵形式写出： 或 （4） 由（3）和（4）可知，是对偶问题（D）的可行解。 由于非基变量的取值为0，以及目标函数中松弛变量的系数为0，因此有 根据定理2的推论1，是对偶问题（D）的最优解，且原问题和对偶问题目标函数最优值相等。 类似地可以证明，如果对偶问题存在最优解，则原问题也存在最优解，并且二者的目标值相等。 注：也可用凸集分离定理证明该结论。但运用单纯形法证明该定理属于构造性证明，也适用于求解对偶问题。 3.1.3 互补松弛定理 利用对偶定理可以证明原问题和对偶问题的最优解满足重要的互补松弛性质。 对于互为对偶的一对线性规划问题，已知一个问题的最优解时，可以利用互补松弛定理求出另一个问题的最优解。 定理4 (对称形式的互补松弛定理)：设和分别是(L)和(D)的可行解，则二者分别为最优解的充分必要条件是： 用表示矩阵的第行，用表示矩阵的第列。 推论1 设和分别是(L)和(D)的可行解，则二者分别为最优解的充分必要条件是： (i) 对，若，就有；若，就有。 (ii) 对，若，就有；若，就有。 推论2 设是(L)的最优解，则是(D)的最优解的充要条件是： (i) 对，若，就有； (ii) 对，若，就有。 推论3 设是(D)的最优解，则是(L)的最优解的充要条件是： (i) 对，若，就有; (ii) 对，若，就有。 例： 设原问题 对偶问题 设用图解法求得对偶问题的最优解为 则可用互补松弛定理求原问题的最优解。 由于在最优解处，对偶问题的第3个约束成立严格不等式，因此原问题第3个变量。 又由于的两个分量均大于0，因此在原问题中前两个约束在最优解处成立等式，即 把代入上述方程组，可解得，。 原问题的最优解为。 §3.2