maxw?24y1?15y2?30y3??4y1?3y2??7??2y1?6y2?5y3?4???6y1?4y2?3y3??3?y?0、y?0、y无约束?123
对于非对称型对偶问题，关键在于处理等式约束和无约束变量，从
上面例子可以看出，等式约束和无约束变量之间的关系：
? 原问题的等式约束条件，对应于对偶问题的无约束变量； ?? 对偶问题的等式约束条件，对应于原问题的无约束变量； 所以，原问题与对偶问题的对偶规则可以归纳如下，根据这些规则直接写出一般线性规划问题的对偶问题：
原问题(对偶问题) 目标函数maxz 变量??????????????n个?0?0无约束m个???对偶问题(原问题) 目标函数minw n个???m个???????约束条件 约束条件 ???0???0?无约束??变量 约束条件右端项 目标函数变量的系数 目标函数变量的系数 约束条件右端项 例4． 写出下列线性规划问题的对偶问题
minz?2x1?3x2?5x3?x4x1?x2?3x3?x4?52x1?2x3?x4?4x2?x3?x4?6x1?0;x2,x3?0;x4无约束
60
解：根据原问题与对偶问题的对偶规则，对偶问题为，
maxw?5y1?4y2?6y3y1?2y2?2y1?y2?y3?3?3y1?2y2?y3??5y1?y2?y3?1y1?0,y2?0,y3无约束
第五节 对偶问题的基本性质
这些基本性质将揭示原问题的解与对偶问题解之间的一些重要性质。 以下约定原问题是指
maxz?CX ?AX?b??X?0
其对偶问题为
minw?Yb?YA?C??Y?0
对于其它的互为对偶的线性规划问题，也有相应的以下这些性质。 1. 对称性
证：将对偶问题的两边同乘(-1),得，
?minw??Yb,?YA??C,Y?0
由于minw??max(?w) ，有，
max(?w)??Yb,?YA??C,Y?0 (1)
根据对偶变换关系，上式问题的对偶问题为，
min(?w?)??CX,?AX??b,X?0 又由于，min(?w?)??maxw? ， 所以，
61
maxw??maxz?CX,AX?b,X?0 即为原问题。
2. 弱对偶性
如果X、Y分别是原问题和对偶问题的可行解，则必有CX?Yb。 证：因为X、Y分别是原问题和对偶问题的可行解，所以，有
AX?b,X?0; ?YAX?Yb;
和YA?C,Y?0 ?YAX?CX;
所以，必有，CX?Yb
3. 最优性
如果X?、Y?分别是原问题和对偶问题的可行解，且CX??Y?b，那么，X?、Y?分别是原问题和对偶问题的最优解。 证：根据性质2，对于原问题任一个可行解X，有CX?Y?b，而CX??Y?b
? CX?Yb?CX，所以，X是原问题目标函数值最大的可行解，X?是
???原问题的最优解。 同理，根据性质2，对于对偶问题任一个可行解Y，有CX??Yb，又已知，
????所以，Y?是对偶问题目标函数值最小的CX?Yb ? Yb?CX?Yb，
可行解，Y?是对偶问题的最优解。 4. 无界性
如果原问题(对偶问题)为无界解，则其对偶问题(原问题)无可行解。 证：用反证法证明，假设其对偶问题有可行解Y，则必有Yb，根据弱对偶性，有CX?Yb，显然，这与原问题有无界解矛盾，所以，其对偶问题无可行解。
但要注意，这个性质的逆命题不一定成立，即原问题(对偶问题)为无可行解，其对偶问题(原问题) 可能有无界解，也可能有无可行解。 例5． 已知原问题及其对偶问题：
maxz?x1?2x22minw?2y1?y2??y1?2y2?1?x?x?x?2?13? 和 ??y1?y2?2???2x1?x2?x3?1?y1?y2?0?x?0,j?1,2,3?j??y1,y2?0
62
试用对偶理论证明原问题无界。
证：显然，在原问题中，X?(0,0,0)T是原问题的一个可行解，说明原问题有可行解；而对偶问题的第一个约束条件?y1?2y2?1明显不能成立，对偶问题不可行，所以，原问题无界。 5. 强对偶性
如果原问题有最优解，那么，对偶问题也有最优解，且目标函数值相等。(或者说，如果原问题和对偶问题都有可行解，则它们都是最优解，且目标函数值相等。)
证：设原问题的最优解为X?，根据最优性条件，对应于基矩阵B必然有，
C?CBB?1A?0,?CBB,?1?0
令Y?CBB?1 ，则有， C?YA?0Y?0 ? YA?C,Y?0，
可见，Y是对偶问题的一个可行解，对应的目标函数值w为，
w?Yb?CBBb
?1已知，X?是原问题的最优解，目标函数值z为，
z?CX??CBBb
?1所以，可得，CX??Yb ，根据性质3，Y也是最优解，且目标值相等。 6. 互补松弛性
如果X?、Y?分别是原问题和对偶问题的可行解，则它们为最优解的充分必要条件是YsX??0,Y?Xs?0。
证：必要性，在原问题和对偶问题中分别引入松弛变量Xs和Ys，则有，
AX?Xs?b,YA?Ys?C
?若X?、Y?为原问题和对偶问题的最优解，根据对偶性质，CX
?Yb，
63
?
