互补松弛定理：原理与应用

互补松弛定理:如果X和Y分别为原问题和对偶问题的可行解,它们分别为原问题和对偶问题最优解的充要条件是(C－YA)X＝0与Y(b－AX)＝0。

证明:

①必要性。若X和Y分别为原问题和对偶问题的最优解,则(C－YA)X＝0与Y(b－AX)＝0同时成立。

X和Y分别为原问题和对偶问题的可行解,则AX≤b,YA≥C。分别引入松弛变量和剩余变量,将其标准化,有AX＋XS＝b,YA－YS＝C,移项后,XS＝b－AX,YS＝YA－C,分别左乘Y和右乘X后,YXS＝Y(b－AX),YSX＝(YA－C)X。因X和Y为最优解,根据强对偶定理,CX＝Yb,则(YA－YS)X＝Y(AX＋XS);YXS＋YSX＝0;YXS＝0,YSX＝0;Y(b－AX)＝0;(C－YA)X＝0。

②充分性。如果X和Y分别为原问题和对偶问题的可行解,它们分别为原问题和对偶问题最优解的充要条件是(C－YA)X＝0与Y(b－AX)＝0。

证明:设X和Y分别为原问题和对偶问题的可行解,且满足(C－YA)X＝0与Y(b－AX)＝0,即CX＝YAX,Yb＝YAX,因此,CX＝Yb,由强对偶定理可知,X和Y必为原问题和对偶问题的最优解。证毕。

互补松弛定理经常表示为Y∗XS＝0,YSX∗＝0。这表明,在线性规划问题的最优解中,如果对应某一约束条件的对偶变量取值为非零,则该约束条件为严格等式;反之,如果原问题约束条件为严格不等式,则其对应的对偶变量一定为零。

【例2-9】已知下面线性规划问题的最优解X∗＝(1/4,0,19/4)T,求其对偶问题的最优解。

解:

①求原问题松弛变量。

首先,在原问题模型的约束条件中加入松弛变量x4(xs1),x5(xs2)和x6(xs3),变成等式

然后,将已知条件x∗1＝1/4,x∗2＝0,x∗3＝19/4代入原问题约束条件,求得x4(xs1)＝0,x5(xs2)＝0,x6(xs3)＝3/2＞0。(www.xing528.com)

②利用互补松弛定理求解对偶问题。

设对偶问题变量为y1,y2和y3,则对偶模型为:

将约束条件变成等式后模型变为:

由互补松弛定理YXS＝0,y3×xs3＝0,y3×3/2＝0,y3＝0;

由互补松弛定理YSX＝0,ys1×x∗1＝0,ys1×1/4＝0,ys1(y4)＝0。这样,对偶模型中第一、三个约束等式变为:

得y1＝5/2,y2＝5/2;再代入第二个约束条件,得y5＝15/2,即Y∗＝(5/2,5/2,0,0,15/2),W∗＝55/2。

对于互补松弛定理,当线性规划问题达到最优时,有下列结论:

若原问题的某一约束为紧约束(松弛变量为0),则该约束对应的对偶变量应大于0或等于0(若xsi＝0,则yi＞0或yi＝0)。

若原问题的某一约束为松约束(松弛变量大于0),则该约束对应的对偶变量一定等于0(若xsi＞0,则yi＝0)。

若原问题的某一变量大于0,则该变量对应的对偶问题的约束为紧约束(若xj＞0,则ysj＝0)。

若原问题的某一变量等于0,则该变量对应的对偶问题的约束可能为紧约束,也可能为松约束(若xj＝0,则ysj＞0或ysj＝0)。