最優性

最優性，運籌學中的術語，對偶問題的基本性質之一。如果X是原問題的可行解，Y是對偶問題的可行解，並且CX=Yb，那么X和Y分別為原問題和對偶問題的最優解。這個定理說明了如果找到原問題和對偶問題的可行解，且它們目標函式值如果相等，那么這兩個可行解都是各自問題的最優解。

基本介紹

• 中文名：最優性
• 外文名：optimization condition
• 分類：數學 運籌學
• 形式：標準 矩陣
• 功能：找最優解
• 屬於：對偶問題

定義

標準形式

假定原問題是最大化問題即線性規劃問題（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是最優解。

適用範圍

無論原問題是極大化問題和極小化問題均適用。