什么是最优性介绍

最优性，运筹学中的术语，对偶问题的基本性质之一。如果X是原问题的可行解，Y是对偶问题的可行解，并且CX=Yb，那么X和Y分别为原问题和对偶问题的最优解。这个定理说明了如果找到原问题和对偶问题的可行解，且它们目标函数值如果相等，那么这两个可行解都是各自问题的最优解。

最优性定义

最优性标准形式

假定原问题是最大化问题即线性规划问题（LP）的标准形式：

其对偶问题（DLP）如下式所示：

如果x_j(j=1,···,n)是原问题的可行解，y_i(i=1,···,m)是其对偶问题的可行解，且有

则x_j(j=1,···,n)是原问题的最优解，y_i(i=1,···,m)是其对偶问题的最优解。

最优性矩阵形式

矩阵形式的线性规划问题的原问题为：

其对偶问题为：

若原问题及其对偶问题均有可行解，且CX=Yb，则原问题和对偶问题的可行解分别均是两者的最优解。

最优性数学证明

最优性一般形式

最优解使某线性规划的目标函数达到最优值（最大值或最小值）的任一可行解。设x*是原问题的可行解，y*是对偶问题的可行解。

原问题如果是最大化问题，必有

对偶问题则是最小化问题，必有

弱对偶性，原问题任一可行解(最优解属于可行解)的目标函数值是其对偶问题的下界：

所以，

由条件知

，即上式的两头需要取等式，那么中间的等式也成立：

此等式表明如果原问题和对偶问题目标函数值相等，那必定是在最优解的情形下取得的。

最优性矩阵形式

设X是原问题的可行解，Y是对偶问题的可行解。由弱对偶性可知对偶问题的所有可行解Y_o都存在Y_ob≥CX，由条件知CX=Yb，所以Y_ob≥Yb，可见Y是使目标函数取值最小的可行解，因此是最优解。

同理可证明，对于原问题的所有可行解X_o，存在CX=Yb≥CX_o，所以X是最优解。

最优性适用范围

无论原问题是极大化问题和极小化问题均适用。