第3章 对偶理论

§3.1 线性规划的对偶理论

3.1.1 对偶问题的表述

对称形式的对偶：

（L） mincx (D) maxwb s.t. Ax?b s.t. wA?c x?0 w?0

其中c为n维行向量，A为m?n矩阵，b为m维列向量，x表示n维列向量，w表示m维行向量。

称(D)为线性规划(L)的对偶规划问题。

定理1 (L)与(D)互为对偶规划问题。――（对合性）

例 设原问题 对偶问题

minx1?x2s.t. x1? x2?5 x1?2x2?1 x1,x2?0非对称形式的对偶：

max 5w1?w2s.t. w1? w2?1 w1?2w2??1 w1,w2?0

（LP） mincx (DP) maxwb s.t. Ax?b s.t. wA?c x?0

例 设原问题 对偶问题

min5x1?4x2?3x3s.t. x1? x2?x3?4 3x1?2x2?x3?5 x1,x2,x3?0一般线性规划问题：

max 4w1?5w2s.t. w1? 3w2?5 w1?2w2?4 w1? w2?3

可化为上述二者之一讨论其对偶问题，也可直接写出对偶问题，详细的对应法则见教材（陈宝林）124页。

37

直接写出对偶的弊端之一是对偶最优解不易确定，而对称形式和非对称形式对偶的最优解都可由原问题的单纯形乘子确定出来。

3.1.2 对偶定理(强对偶定理和弱对偶定理)

定理2 (弱对偶定理)：设x和w分别是

（L） mincx 和 (D) maxwb s.t. Ax?b s.t. wA?c x?0 w?0 的可行解，则有下列不等式成立：

cx?wb

证明：由于Ax?b和w?0，则有wAx?wb。

由于c?wA和x?0，则有cx?wAx。 因此有cx?wb

推论1 设x和w分别是(L)和(D)的可行解，且有cx?wb，则x和w分别是(L)和(D)的最优解。

推论2 如果(L)的目标函数在可行集上无下界，则对偶规划(D)无可行解。 推论3 如果(D)的目标函数在可行集上无上界，则原始规划(L)无可行解。

定理3 (强对偶定理)：如果互为对偶规划的两个问题之一有最优解，则另一个问题也有最优解，并且二者的目标值相等。

证明：设原问题（L）存在最优解，引进松弛变量，写成等价形式：

min cxs.t. Ax?v?b （1）

x?0 v?0由于（1）存在最优解，因此可以用单纯形方法求出它的一个最优基本可行解，不妨设

?x?该最优解是y???，相应的最优基是B。此时所有判别数均非正，即

?v?wpj?cj?0, ?j （2）

w?cBB?1为单纯形乘子。

38

考虑所有原来变量（不包括松弛变量）在基B下的判别数，把它们所满足的条件（2）用矩阵形式写出：

wA?c?0 或 wA?c （3）

把所有松弛变量在基B下的判别数所满足的条件（2）用矩阵形式写出：

w(?I)?0 或 w?0 （4）

由（3）和（4）可知，w是对偶问题（D）的可行解。

由于非基变量的取值为0，以及目标函数中松弛变量的系数为0，因此有

wb?cBB?1b?cByB?cx

根据定理2的推论1，w是对偶问题（D）的最优解，且原问题和对偶问题目标函数最优值相等。

类似地可以证明，如果对偶问题存在最优解，则原问题也存在最优解，并且二者的目标值相等。

注：也可用凸集分离定理证明该结论。但运用单纯形法证明该定理属于构造性证明，也适用于求解对偶问题。

3.1.3 互补松弛定理

利用对偶定理可以证明原问题和对偶问题的最优解满足重要的互补松弛性质。 对于互为对偶的一对线性规划问题，已知一个问题的最优解时，可以利用互补松弛定理求出另一个问题的最优解。

定理4 (对称形式的互补松弛定理)：设x和w分别是(L)和(D)的可行解，则二者分别为最优解的充分必要条件是：

w(Ax?b)?0, (wA?c)x?0

用Ai表示矩阵A的第i行，用pj表示矩阵A的第j列。

推论1 设x和w分别是(L)和(D)的可行解，则二者分别为最优解的充分必要条件是： (i) 对j?1,?,n，若xj?0，就有wpj?cj；若wpj?cj，就有xj?0。 (ii) 对i?1,?,m，若wi?0，就有Aix?bi；若Aix?bi，就有wi?0。 推论2 设x是(L)的最优解，则w是(D)的最优解的充要条件是： (i) 对j?1,?,n，若xj?0，就有wpj?cj；

39