W≥0,y7≥0 min(-b, 0) 仿上可类似证明(L)有最优解。 从证明中易见。以上结论对(L)和(D)亦成立。 综上,互为对偶规划的解之间的联系,不外乎以下三种情况 两个规划都有最优解 20两个规划都没有可行解 3°一个规划有可行解,但目标函数在可行解集上无界,而另一个规划无可行解 此外由定理2的证明知,若B是(L)的最优基,则单纯形乘子x=CBB便是(D)的 最优解,于是从原问题(L)的最终单纯形表中可以直接得到对偶问题(D)的解。实际上 假如在原始阵A中有一个mxm阶的单位阵1,则在最后的表中,矩阵B出现在开始时为单 位阵I的地方,同时B-下面m个检验数为CBB--C1,这样从最后一行中对应的这些元 素与C,的对应分量相加,就获得了对偶问题的最优解W=CB-1。 定理3松紧定理 (i)、考虑非对称的对偶规划(L′)和(D’),设X和W0分别是它们的可行解, 则它们分别是(L′)和(D′)的最优解的充要条件是 (CWA)ⅹ0=0 证明由定理1和2知,可行解X0和W0为最优解的充要条件是 (Cw0A)x0=0 因Ⅹ≥0,C-WA≥0,故(1)式等价于
96 − = T T T T T T T T T Y W b W Y C Y W A I min( ,0) 0, 0 ( , ) 仿上可类似证明(L)有最优解。 从证明中易见。以上结论对（L ' ）和（D ' ）亦成立。 综上，互为对偶规划的解之间的联系，不外乎以下三种情况： 1 0 两个规划都有最优解。 2 0 两个规划都没有可行解。 3 0 一个规划有可行解，但目标函数在可行解集上无界，而另一个规划无可行解。 此外由定理 2 的证明知，若 B 是（L）的最优基，则单纯形乘子 −1 = CB B 便是（D）的 最优解，于是从原问题（L）的最终单纯形表中可以直接得到对偶问题（D）的解。实际上， 假如在原始阵 A 中有一个 m m 阶的单位阵 I,则在最后的表中，矩阵 B −1 出现在开始时为单 位阵 I 的地方，同时 B −1 下面 m 个检验数为 C B B − CI −1 ,这样从最后一行中对应的这些元 素与 C I 的对应分量相加，就获得了对偶问题的最优解 W=C −1 B B 。 定理 3 松紧定理 （ⅰ）、考虑非对称的对偶规划（L′）和（D′）,设 X 0 和 W 0 分别是它们的可行解， 则它们分别是（L′）和（D′）的最优解的充要条件是 （C-W 0 A）X 0 =0 (1) 证明 由定理 1 和 2 知，可行解 X 0 和 W 0 为最优解的充要条件是 CX 0 = W 0 b= W 0 A X 0 即 （C-W 0 A）X 0 =0 因 X 0 0，C- W 0 A 0,故（1）式等价于
(C,-W°p,)X0=0 P 由此可得结论: 1°、若(L′)有最优解X,使得对指标满足x>0(称为j对(L)是松的) 则对(D′)的一切最优解w,必有WP,=C,(称为j对(D′)是紧的) 2、若(D)有最优解W°,使对指标j,满足W°P,<C,(称j对(D′)是松的 则对(L′)的一切最优解X,必有x=0(称j对(L′)是紧的)。 (ⅱ)、考虑对称对偶规划(D)和(L),设X和W°分别是(D)和(L)的可行解 则它们同时也是最优解的充要条件为 (C-WA)X0=0 证明将对称形式(L)、(D)转化为非对称形式(L)和(D′) (A0 (L′)X≥0,y≥0 ∫W(4-D)≤(C0) max wb nin( c 由以上(i)的结论知, F0/和W0分别为(L)和(D)的最优解的充要条件 是 IC,0)-w(A- (C-WA,w D 由此得 (C-W AX=0 0=Wo(AX0-b)=0 故定理得证
97 （C j W p j 0 − ）X 0 j =0,j=1、……、n 由此可得结论： 1 0 、若（L′）有最优解 X 0 ,使得对指标 j,满足 X 0 j >0 （称为 j 对（L′）是松的）, 则对（D′）的一切最优解 w，必有 WP j =C j (称为 j 对（D′）是紧的)。 2 0 、若（D′）有最优解 W 0 ，使对指标 j，满足 W 0 P j C j (称 j 对（D′）是松的)， 则对（L′）的一切最优解 X，必有 X j =0（称 j 对（L′）是紧的）。 （ⅱ）、考虑对称对偶规划（D）和（L）,设 X 0 和 W 0 分别是（D）和（L）的可行解， 则它们同时也是最优解的充要条件为 − = − = ( ) 0 ( ) 0 0 0 0 0 W AX b C W A X (2) 证明 将对称形式（L）、（D）转化为非对称形式（L′）和（D′） （L′） = − Y X C X Y b Y X A I min( ,0) 0, 0 ( ) 0 （D′） − Wb W A I C max ( , ) ( ,0) 由以上（ⅰ）的结论知， 0 0 Y X 和 0 W 分别为（L′）和（D′）的最优解的充要条件 是 [( ,0) ( , )] 0 0 0 0 = − − Y X C W A I 即 ( , ) 0 0 0 0 0 = − Y X C W A W I 由此得 ( ) 0 0 0 C −W A X = ( ) 0 0 0 0 0 W Y = W AX − b = 故定理得证