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

文章目录

• 一、最优性定理
• 二、强对偶性

一、最优性定理

最优性定理 :

如果

是 原问题的可行解 ,

是 对偶问题的可行解 ,

并且 两个可行解对应的目标函数值相等 , 即

, 即

,

则

是原问题的最优解 ,

是对偶问题的最优解 ;

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

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

互为对偶的两个问题 :

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

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

当上述

是 原问题的可行解 ,

是 对偶问题的可行解 ,

如果

, 则说明

, 当前的目标函数值就是界限值 ;

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

二、强对偶性

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