【运筹学】对偶理论 : 互补松弛性 ( 定理内容 | 定理证明 )

文章目录

• 一、互补松弛性
• 二、证明 互补松弛性

一、互补松弛性

和

分别是 原问题

问题 和 对偶问题

的 可行解 ,

这两个解各自都是对应 线性规划问题 的 最优解

的 充要条件是 :

其中

是 松弛变量 或 剩余变量 ;

二、证明 互补松弛性

原问题 :

对偶问题 :

松弛变量 与 剩余变量 :

将原问题的约束方程变为等式 ,

, 添加 松弛变量 ,

; 其中

;

将对偶问题的约束方程变为等式 ,

, 减去 剩余变量 ,

; 其中

;

代入可行解到约束方程中 :

是原问题的可行解 ,

是对偶问题的可行解 ;

将

代入到

等式中 , 可以得到

的一个可行解 ,

将

代入到

等式中 , 可以得到

的一个可行解 ;

根据 对偶理论中的 强对偶定理 , 只要 "

和

分别是 原问题

问题 和 对偶问题

的 最优解 "

那么其目标函数就是最大值与最小值的界限值 , 将这两个最优解代入到对应的目标函数中 , 求得的两个值是相等的 ;

将

代入到

目标函数中 , 得到

;

将

代入到

目标函数中 , 得到

;

上述两个值相等 :

将

和

代入到上述等式中 , 得到

其中

都是大于等于

的 , 但上述等式

中符号相反 , 说明 等号两边的值都是

;