运筹学定理（优秀）_运筹学原理

运筹学定理（优秀）由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“运筹学原理”。

性质2 弱对偶原理(弱对偶性)：设 X0 和 Y0 分别是问题(P)和(D)的可行解，则必有

n

m

00 CXYb即：cjxjyibij1i1

推论1:

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

推论2:

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

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

性质3 最优性定理：如果 X0 是原问题的可行解，Y0 是其对偶问题的可行解，并且: CX0BY0即:z＝w则

X0 是原问题的最优解，Y0 是其对偶问题的最优解。

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

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

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

0解的充要条件是： YXs0 0YsX0

其中：Xs、Ys为松弛变量 性质5的应用：

该性质给出了已知一个问题最优解求另一个问题最优解的方法，即已知Y＊求X＊或已知X＊求Y＊ YXs0 互补松弛条件 YX0 s由于变量都非负，要使求和式等于零，则必定每一分量为零，因而有下列关系：

若Y＊≠0，则Xs必为0；若X＊≠0，则Ys必为0 利用上述关系，建立对偶问题（或原问题）的约束线性方程组，方程组的解即为最优解。

判断下列结论是否正确，如果不正确，应该怎样改正？ 1）任何线性规划都存在一个对应的对偶线性规划.2）原问题第i个约束是“≤”约束，则对偶变量yi≥0.3）互为对偶问题，或者同时都有最优解，或者同时都无最优解.4）对偶问题有可行解，则原问题也有可行解.5）原问题有多重解，对偶问题也有多重解.6）对偶问题有可行解，原问题无可行解，则对偶问题具有无界解.7）原问题无最优解，则对偶问题无可行解.8）对偶问题不可行，原问题可能无界解.9）原问题与对偶问题都可行，则都有最优解.10）原问题具有无界解，则对偶问题不可行.11）对偶问题具有无界解，则原问题无最优解.12）若X*、Y*是原问题与对偶问题的最优解，则X*=Y*.