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

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

文章目录

一、最优性定理

二、强对偶性





一、最优性定理


最优性定理 :


如果 X 0 \rm X^0X

0

 是 原问题的可行解 , Y 0 \rm Y^0Y

0

 是 对偶问题的可行解 ,


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

0

=BY

0

 , 即 z = w \rm z = wz=w ,


则 X 0 \rm X^0X

0

 是原问题的最优解 , Y 0 \rm Y^0Y

0

 是对偶问题的最优解 ;



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


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



互为对偶的两个问题 :


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


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


当上述 X 0 \rm X^0X

0

 是 原问题的可行解 , Y 0 \rm Y^0Y

0

 是 对偶问题的可行解 ,


如果 C X 0 = B Y 0 \rm CX^0 = BY^0CX

0

=BY

0

 , 则说明 C X 0 = B Y 0 = 界 限 值 \rm CX^0 = BY^0 = 界限值CX

0

=BY

0

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


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






二、强对偶性


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


目录
打赏
0
0
0
0
39
分享
相关文章
上升到人生法则的贝叶斯理论
贝叶斯定理在数据分析、机器学习和人工智能等领域有广泛的应用。贝叶斯定理(Bayes' theorem)是一种用于计算条件概率的重要定理,它基于条件概率的定义,描述了在已知某一条件下,另一个条件发生的概率。
凸优化理论基础3——凸集和凸锥重要例子
凸优化理论基础3——凸集和凸锥重要例子
980 0
凸优化理论基础3——凸集和凸锥重要例子
算法基础系列第四章——数论之从欧拉卷到欧几里得(2)
算法基础系列第四章——数论之从欧拉卷到欧几里得(2)
109 0
算法基础系列第四章——数论之从欧拉卷到欧几里得(2)
凸优化理论基础2——凸集和锥
凸优化理论基础2——凸集和锥
413 0
凸优化理论基础2——凸集和锥
【运筹学】对偶理论 : 互补松弛性 ( 定理内容 | 定理证明 )
【运筹学】对偶理论 : 互补松弛性 ( 定理内容 | 定理证明 )
1167 0
【运筹学】对偶理论 : 弱对偶性质 ( 弱对偶原理 | 弱对偶性 | 推论 1 | 推论 2 对偶问题的无界性 | 推论 3 )
【运筹学】对偶理论 : 弱对偶性质 ( 弱对偶原理 | 弱对偶性 | 推论 1 | 推论 2 对偶问题的无界性 | 推论 3 )
453 0
【运筹学】对偶理论 : 互补松弛性 ( 原问题与对偶问题标准形式 | 互补松弛定理 | 互补松弛定理示例说明 )
【运筹学】对偶理论 : 互补松弛性 ( 原问题与对偶问题标准形式 | 互补松弛定理 | 互补松弛定理示例说明 )
1101 0
Newton冷却定理微分数学公式推导
Newton冷却定理微分数学公式推导
1600 0
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等