对偶问题性质与线性实例.pdfVIP

本节主要绍的对偶问题的性质及应用

一．对偶问题的性质。

1.对称性。

对偶问题的对偶是原问题（请参看52页或文献（1）

2.弱对偶性。

X

若原问题是max型，则对偶问题为min型，且是原问

解，Q是对偶问题的可行解，在此情况下，原问题的目标函

不超过对偶问题的目标函数值Qb即：

CXQb

请大家记住由此而得的几个推论。

3．可行解是最优解时的性质

CXQbXQ

沿用2中的设定。若则、分别是原问题和

对偶问题的最优解。

4．对偶定理。

若原问题有最优解，那么对偶问题也一定有最优解，且原问题

与对偶问题的最优目标函数值相等。其实这一结论由3中就可以看

出，详细证明请参考54页的内容。

通过一个实例探讨原问题的最优解与对偶问题最优解之间的联

系，考虑下面的线性规划问题：

maxZ5x+4xminω8y+4y+6y

12123

2x+2x≤82y+4y≥5

1213

2y+3y+y≥4

LP13x2≤4LP2123

y，y，y≥0

4x+x≤6123

12

x，x，≥0

12

在LP中引入松弛变量x,x,x；在LP引入多余变量y，

134524

y及人工变量y，y，分别用单纯形法求解得出的最优单纯

567

形表如下：

LP1(max)松弛变量

C→54000

j

x

CBXBbx1x2x34x5

0x33001