【运筹学】对偶理论 : 最优性定理、强对偶性

一、最优性定理

最优性定理 :

如果 X 0 \rm X^0 X0 是 原问题的可行解 , Y 0 \rm Y^0 Y0 是 对偶问题的可行解 ,

并且 两个可行解对应的目标函数值相等 , 即 C X 0 = B Y 0 \rm CX^0 = BY^0 CX0=BY0 , 即 z = w \rm z = w z=w ,

则 X 0 \rm X^0 X0 是原问题的最优解 , Y 0 \rm Y^0 Y0 是对偶问题的最优解 ;

两个互为对偶的线性规划问题 , 只要有一个有最优解 , 另一个也有最优解 ;

最优解 首先是可行解 , 其次该可行解使目标函数达到最优 ( 最小值 / 最大值 ) ;

互为对偶的两个问题 :

原问题的目标函数求最大值 , 该值不断增大 , 处于一个界限值下方 ; 其最大值就是界限值 ;

对偶问题的目标函数求最小值 , 该值不断减小 , 处于一个界限值上方 ; 其最小值就是界限值 ;

当上述 X 0 \rm X^0 X0 是 原问题的可行解 , Y 0 \rm Y^0 Y0 是 对偶问题的可行解 ,

如果 C X 0 = B Y 0 \rm CX^0 = BY^0 CX0=BY0 , 则说明 C X 0 = B Y 0 = 界 限 值 \rm CX^0 = BY^0 = 界限值 CX0=BY0=界限值 , 当前的目标函数值就是界限值 ;

该界限值就是 原问题 目标函数的最大值 , 同时也是 对偶问题目标函数的最小值 ;

二、强对偶性

强对偶性 : 如果 原问题 与 对偶问题 都有可行解 , 只要有一个问题有最优解 , 则 两个问题都有最优解 , 二者的最优解的目标函数值相等 ;