最优性,运筹学中的术语,对偶问题的基本性质之一。如果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是对偶问题的可行解。由弱对偶性可知对偶问题的所有可行解Yo都存在Yob≥CX,由条件知CX=Yb,所以Yob≥Yb,可见Y是使目标函数取值最小的可行解,因此是最优解。
同理可证明,对于原问题的所有可行解Xo,存在CX=Yb≥CXo,所以X是最优解。 [3]
适用范围
播报编辑