MBA数模考试复习资料

对偶性质

? 原问题与其对偶问题的变量与解的对应关系：

? 在单纯形表中，原问题的松弛变量对应对偶问题的变量，对偶问题的剩余变量对应原问题

的变量。

性质1 对称性定理：对偶问题的对偶是原问题

Page 37 of 48

推论1: 原问题任一可行解的目标函数值是其对偶问题目标函数值的下届；反之，对偶问题任意可行解的目标函数值是其原问题目标函数值的上界。

推论2: 在一对对偶问题（P）和（D）中，若其中一个问题可行但目标函数无界，则另一个问题无可行解；反之不成立。这也是对偶问题的无界性。

推论3：在一对对偶问题（P）和（D）中，若一个可行（如P），而另一个不可行（如D），则该可行的问题目标函数值无界。

性质4 强对偶性：若原问题及其对偶问题均具有可行解，则两者均具有最优解，且它们最优解的目标函数值相等。

还可推出另一结论：若（LP）与（DP）都有可行解，则两者都有最优解，若一个问题无最优解，则另一问题也无最优解。

性质5 互补松弛性：设X0和Y0分别是P问题 和 D问题 的可行解，则它们分别是最优解的充要条件是：

其中：Xs、Ys为松弛变量

性质5的应用：

该性质给出了已知一个问题最优解求另一个问题最优解的方法，即已知Y＊求X＊或已知X＊求Y＊

由于变量都非负，要使求和式等于零，则必定每一分量为零，因而有下列关系：

若Y＊≠0，则Xs必为0；若X＊≠0，则Ys必为0

利用上述关系，建立对偶问题（或原问题）的约束线性方程组，方程组的解即为最优解。

Page 38 of 48

例2.4 已知线性规划

的最优解是X＊=(6,2,0)T,求其对偶问题的最优解Y＊。

解：写出原问题的对偶问题，即

设对偶问题最优解为X＊＝(x1，x2 ，x3)T ,由互补松弛性定理可知，X＊和 Y＊满足：

将Y＊带入由方程可知，y3＝y5＝0，y4＝1。 ∵y2=-2≠0 ∴x5＝0 又∵y4=1≠0 ∴x2＝0

将x2，x5分别带入原问题约束方程中，得：

解方程组得：x1=-5,x3=-1, 所以原问题的最优解为 X＊=(-5,0,-1)，最优值z=-12

设对偶问题最优解为Y＊＝(y1，y2),由互补松弛性定理可知，X*和 Y*满足：

即：

解此线性方程组得y1=1,y2=1,从而对偶问题的最优解为： Y＊=(1,1)，最优值w=26。

Page 39 of 48

原问题与对偶问题解的对应关系小结

判断下列结论是否正确，如果不正确，应该怎样改正？ 1）任何线性规划都存在一个对应的对偶线性规划.

2）原问题第i个约束是“≤”约束，则对偶变量yi≥0. 3）互为对偶问题，或者同时都有最优解，或者同时都无最优解. 4）对偶问题有可行解，则原问题也有可行解.

5）原问题有多重解，对偶问题也有多重解.

6）对偶问题有可行解，原问题无可行解，则对偶问题具有无界解. 7）原问题无最优解，则对偶问题无可行解. 8）对偶问题不可行，原问题可能无界解.

9）原问题与对偶问题都可行，则都有最优解.

10）原问题具有无界解，则对偶问题不可行. 11）对偶问题具有无界解，则原问题无最优解.

12）若X*、Y*是原问题与对偶问题的最优解，则X*=Y*.

敏感性分析

假设得到了一个额外的1000磅的钢铁。钢铁约束的RHS值将由27变为28=27+1。

Page 40 of 48