-
最優性
鎖定
最優性，運籌學中的術語，對偶問題的基本性質之一。如果X是原問題的可行解，Y是對偶問題的可行解，並且CX=Yb，那麼X和Y分別為原問題和對偶問題的最優解。這個定理説明了如果找到原問題和對偶問題的可行解，且它們目標函數值如果相等，那麼這兩個可行解都是各自問題的最優解。
[1]
- 中文名
- 最優性
- 外文名
- optimizationcondition
- 分 類
- 數學 運籌學
- 形 式
- 標準 矩陣
- 功 能
- 找最優解
最優性定義
最優性標準形式
假定原問題是最大化問題即線性規劃問題（LP）的標準形式：
其對偶問題（DLP）如下式所示：
如果xj(j=1,···,n)是原問題的可行解，yi(i=1,···,m)是其對偶問題的可行解，且有
最優性矩陣形式
矩陣形式的線性規劃問題的原問題為：
其對偶問題為：
若原問題及其對偶問題均有可行解，且CX=Yb，則原問題和對偶問題的可行解分別均是兩者的最優解。
最優性數學證明
最優性一般形式
原問題如果是最大化問題，必有
對偶問題則是最小化問題，必有
弱對偶性，原問題任一可行解(最優解屬於可行解)的目標函數值是其對偶問題的下界：
所以，
由條件知
，即上式的兩頭需要取等式，那麼中間的等式也成立：
此等式表明如果原問題和對偶問題目標函數值相等，那必定是在最優解的情形下取得的。
最優性矩陣形式
設X是原問題的可行解，Y是對偶問題的可行解。由弱對偶性可知對偶問題的所有可行解Yo都存在Yob≥CX，由條件知CX=Yb，所以Yob≥Yb，可見Y是使目標函數取值最小的可行解，因此是最優解。
最優性適用範圍
無論原問題是極大化問題和極小化問題均適用。
