收藏
0有用+1
0

最优性

运筹学术语
最优性,运筹学中的术语,对偶问题的基本性质之一。如果X是原问题的可行解,Y是对偶问题的可行解,并且CX=Yb,那么X和Y分别为原问题和对偶问题的最优解。这个定理说明了如果找到原问题和对偶问题的可行解,且它们目标函数值如果相等,那么这两个可行解都是各自问题的最优解。 [1]
中文名
最优性
外文名
optimizationcondition
分    类
数学 运筹学
形    式
标准 矩阵
功    能
找最优解

定义

播报
编辑

标准形式

假定原问题是最大化问题即线性规划问和几霉题(LP)的付嚷遥迁标兆体热准霸定形式:
其对偶问题(DLP)如下式所示:
如果xj(j=1,···,n)是原问题的可行解,yi(i=1,···,m)是其对偶问题的可行解,且有
则x肯兆虹j(j=1,···,n)是原问题的最优解,yi(i=1,···,m)是其对偶问题的最优解。 [2]

矩阵形式

矩阵形式的线几体凝性规划问题的原问题凶桨验为:
店提其对偶问题为:
若原问题及其对偶问题均有可行解,且CX=Yb,则原问题和对偶问题的可行解分别均是两者的最优解。

数学证明

播报
编辑

一般形式

最优解使某线性规划的目标函数达到最优值(最大值或最小值)的任一可行解。设x*是原问题的可行解,y*是对偶问题的可行解。
原问题如果是最大化问题,必有
对偶问题则是最小化问题,必有
弱对偶性,原问题任一可行解(最优解属于可行解)的目标函数值是其对偶问题的下界:
所以,
由条件知
,即上式的两头需要取等式,那么中间的等式也成立:
此等式表明如果原问题和对偶问题目标函数值相等,那必定是在最优解的情形下取得的。

矩阵形式

设X是原问题的可行解,Y是对偶问题的可行解。由弱对偶性可知对偶问题的所有可行解Yo都存在Yob≥CX,由条件知CX=Yb,所以Yob≥Yb,可见Y是使目标函数取值最小的可行解,因此是最优解。
同理可证明,对于原问题的所有可行解Xo,存在CX=Yb≥CXo,所以X是最优解。 [3]

适用范围

播报
编辑
无论原问题是极大化问题和极小化问题均适用。