一、原问题与对偶问题标准形式

原问题 $\mathrm{P}$ : m a x Z = C X s . t { A X ≤ b X ≥ 0

等价方法 :

• 生产 : 目标函数追求 利润最大化 , 约束方程设备的使用时长受约束 , 小于等于 某个时间值 ;
• 出租设备 : 目标函数追求 租金最小化 , 约束方程设备产生的利润要 大于等于 生产的利润 , 不能亏钱 ;

二、互补松弛定理

${\mathrm{X}}^0$ 和 ${\mathrm{Y}}^0$ 分别是 原问题 $\mathrm{P}$ 问题 和 对偶问题 $\mathrm{D}$ 的 可行解 ,

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

的 充要条件是 : { Y 0 X s = 0 Y s X 0 = 0

其中 ${\mathrm{X}}_{\mathrm{s}},{\mathrm{Y}}_{\mathrm{s}}$ 是 松弛变量 或 剩余变量 ;

三、互补松弛定理示例说明

原问题与对偶问题的对应关系 :

生产问题 ( 原问题 ) :

m a x Z = 2 x 1 + 3 x 2 s . t { 2 x 1 + 2 x 2 ≤ 12 x 1 + 2 x 2 ≤ 8 4 x 1 ≤ 16 4 x 2 ≤ 12 x 1 , x 2 ≥ 0

上述线性规划的最优解是 : ( 4 2 )

甲产品生产 $4$ 个单位 , 乙产品生产 $2$ 个单位 ;

设备出租问题 ( 对偶问题 ) :

m i n W = 12 y 1 + 8 y 2 + 16 y 3 + 12 y 4 s . t { 2 y 1 + y 2 + 4 y 3 + 0 y 4 ≥ 2 2 y 1 + 2 y 2 + 0 y 3 + 4 y 4 ≥ 3 y 1 , y 2 , y 3 , y 4 ≥ 0

上述线性规划最优解是 : ( 1 2 1 0 0 )

将上面两个线性规划的最优解代入目标函数 , 得到的值都是 $14$ ;

互补松弛定理 :

" ${\mathrm{X}}^0$ 和 ${\mathrm{Y}}^0$ 分别是 原问题 $\mathrm{P}$ 问题 和 对偶问题 $\mathrm{D}$ 的 最优解 " $\iff$ { Y 0 X s = 0 Y s X 0 = 0

其中 ${\mathrm{X}}_{\mathrm{s}},{\mathrm{Y}}_{\mathrm{s}}$ 是 松弛变量 或 剩余变量 ;

( 4 2 )

${\mathrm{Y}}_{\mathrm{s}}$ 是对偶问题 $\mathrm{D}$ 的剩余变量 , { 2 y 1 + y 2 + 4 y 3 + 0 y 4 − y 5 = 2 2 y 1 + 2 y 2 + 0 y 3 + 4 y 4 − y 6 = 3

根据互补松弛定理 , ${\mathrm{Y}}_{\mathrm{s}}{\mathrm{X}}^0=0$ , 将真实值代入 :

Y s X 0 = ( 4 2 ) × ( y 5 y 6 ) = 4 y 5 + 2 y 6 = 0 \rm Y_sX^0 =

${\mathrm{y}}_5,{\mathrm{y}}_6$ 都是大于等于 $0$ 的 , 如果要满足 $4{\mathrm{y}}_5+2{\mathrm{y}}_6=0$ , 则得到 ${\mathrm{y}}_5=0,{\mathrm{y}}_6=0$ 结论 ;

文章来源: hanshuliang.blog.csdn.net，作者：韩曙亮，版权归原作者所有，如需转载，请联系作者。

原文链接：hanshuliang.blog.csdn.net/article/details/112078796