设Xs与Ys分别是（LP）与（DP）的松驰变量。
【性质1】 对称性 对偶问题的对偶是原问题。 【证】设原问题是
max Z CX , AX b, X 0
§2.2对偶性质 Dual Property
由表2－1知，它的对偶问题是
Ch2 Dual Problem
2020年6月20日星期六 Page 2 of 23
当C X°= Y°b时，由性质1，对任意可行解 X及Y有
C X Y 0b CX 0 Yb
即Y°b是（DP）中任一可行解的目标值的下界，C X°是 （LP）中任一可行解的目标值的上界，从而X°、Y°是最优 解。
§2.2对偶性质 Dual Property
Ch2 Dual Problem
2020年6月20日星期六 Page 7 of 23
【性质4】 还可推出另一结论：若（LP）与（DP）都有可行 解，则两者都有最优解，若一个问题无最优解，则另一问题也 无最优解。
【证】设（LP）有最优解X°，那么对于最优基B必有 C－ CBB-1A≤0与－CBB-1≤0，即有Y°A≥C与Y°≥0， 这里Y°= CBB-1 ，从而Y°是可行解，对目标函数有
得C X°≤Y°AX°
故
C X°≤Y°AX≤Y°b
这一性质说明了两个线性规划互为对偶时，求最大值的线性规 划的任意目标值都不会大于求最小值的线性规划的任一目标值， 不能理解为原问题的目标值不超过对偶问题的目标值。
§2.2对偶性质 Dual Property
由这个性质可得到下面几个结论：
Ch2 Dual Problem
CX 0 CB X B CB B1b Y 0b
由性质3知Y°是最优解。
由性质 4 还可推出另一结论：若（LP）与（DP）都有可行解， 则两者都有最优解，若一个问题无最优解，则另一问题也无最 优解。
§2.2对偶性质 Dual Property
Ch2 Dual Problem
2020年6月20日星期六 Page 8 of 23
§2.2对偶性质 Dual Property
Ch2 Dual Problem
2020年6月20日星期六 Page 1 of 23
设原问题是（记为LP）： 对偶问题是（记为DP）：
max Z CX
min w Yb
AX b X 0
YA C Y 0
这里A是m×n矩阵X是n×1列向量，Y是1×m行向量。假
【性质3】最优准则定理 设X°与Y°分别是（LP）与（DP） 的可行解，则当X°、Y°是（LP）与（DP）的最优解当且仅 当C X°= Y°b.
【 证 】 若 X° 、 Y° 为 最 优 解 ， B 为 （ LP ） 的 最 优 基 ， 则 有 Y°=CBB－1，并且
CX 0 CB B1b Y 0b
min w Yb, YA C,Y 0
它与下列线性规划问题是等价的：
max( w) Yb,YA C,Y 0
再写出它的对偶问题。
min w' CX ,AX b, X 0
它与下列线性规划问题是等价的
max Z CX , AX b, X 0
即是原问题。
§2.2对偶性质 Dual Property
注意上述结论（2）及（3）的条件不能少。一个问题有可 行解时，另一个问题可能有可行解（此时具有无界解）也 可能无可行解。
§2.2对偶性质 Dual Property
例如：
min z x1 2x2
x1
x1
1 2
x2
x2 2
2
x1
,
x
2
0
无可行解，而对偶问题
Ch2 Dual Problem
2020年6月20日星期六 Page 5 of 23
max w 2 y1 2 y2
y1 y2 1
1
y12, yy21
y 0
2
2
有可行解，由结论（3）知必有无界解。
§2.2对偶性质 Dual Property
Ch2 Dual Problem
2020年6月20日星期六 Page 6 of 23
2020年6月20日星期六 Page 4 of 23
（1）（LP）的任一可行解的目标值是（DP）的最优值下 界；（DP）的任一可行解的目标是（LP）的最优值的上 界；
（2）在互为对偶的两个问题中，若一个问题可行且具有 无界解，则另一个问题无可行解；
(3）若原问题可行且另一个问题不可行，则原问题具有 无界解。
Ch2 Dual Problem
2020年6月20日星期六 Page 3 of 23
【性质2】 弱对偶性 设X°、Y°分别为（LP）与（DP）的
可行解，则 CX 0 Y 0b
【证】因为X°、Y°是可行解，故有AX°≤b, X°≥0及 Y°A≥C，Y°≥0, 将不等式 AX°≤b 两边左乘Y°
得Y°AX°≤Y°b 再将不等式Y°A≥C两边右乘X°，
Y°A X°＝Y°b
Y°A X°=C X°
显然有Y°b=C X°,由性质3知Y°与X°是（LP）与（DP） 的最优解。证毕。
§2.2对偶性质 Dual Property
Ch2 Dual Problem
2020年6月20日星期六 Page 10 of 23
性质5告诉我们已知一个问题的最优解时求另一个问题的 最优解的方法，即已知Y°求X°或已知X°求Y°。
【性质5】互补松弛定理 设X°、Y°分别为（LP）与 （DP）的可行解，XS和YS是它的松弛变量的可行解，则 X°和Y°是最优解当且仅当
YSX°=0和Y°XS=0
【证】设X°和Y°是最优解，由性质3 ，C X°= Y°b，
由于XS和YS是松弛变量A X，°则＋有XS＝b
Y°A－YS=C 将第一式左乘Y°，第二式右乘X°得
Y°A X°＋Y°XS＝Y°b
Y°A X°－YS X°=C X°
§2.2对偶性质 Dual Property
Ch2 Dual Problem
2020年6月20日星期六 Page 9 of 23
显然有
Y°XS=－YY°XS=0和YS X°=0
反之， 当Y°XS=0和YS X°=0时，有
Y°XS=0和YS X°=0 两式称为互补松弛条件。将互补松弛条件写成下式
m
yi0 xSi 0
i 1
m
ySj xj0 0
j 1
由于变量都非负，要使求和式等于零，则必定每一分量 为零，因而有下列关系：