对偶性质
? 原问题与其对偶问题的变量与解的对应关系：
? 在单纯形表中，原问题的松弛变量对应对偶问题的变量，对偶问题的剩余变量对应原问题
的变量。
性质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
相关推荐：
loading