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

原问题 $\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 i n W = 2 x 1 − x 2 + 2 x 3 { − x 1 + x 2 + x 3 = 4 − x 1 + x 2 − x 3 ≤ 6 x 1 ≤ 0 , x 2 ≥ 0 , x 3 无 约 束

上述线性规划的对偶问题的最优解是 Y 0 = ( 0 − 2 ) \rm Y^0 =

互补松弛定理 :

" ${\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}}$ 是 松弛变量 或 剩余变量 ;

分析 :

给出了对偶问题最优解 Y 0 = ( 0 − 2 ) \rm Y^0 =

根据公式有 ( 0 − 2 ) × ( x 4 x 5 ) = 0 \rm

$-2{\mathrm{x}}_5=0$

原问题添加松弛变量 ,

$-{\mathrm{x}}_1+{\mathrm{x}}_2+{\mathrm{x}}_3=4$ 已经是等式了 , 添加一个 ${\mathrm{x}}_4$ 松弛变量 , ${\mathrm{x}}_4=0$ ,

$-{\mathrm{x}}_1+{\mathrm{x}}_2-{\mathrm{x}}_3\le 6$ 添加松弛变量 ${\mathrm{x}}_5$ , 由于对应的最优解不为 $0$ , 是 $-2$ , 其对应的松弛变量还是 $0$ , 即 $x_5=0$ ;

原问题的最优解满足 { − x 1 + x 2 + x 3 = 4 − x 1 + x 2 − x 3 = 6

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

这里求一下对偶问题的目标函数值 , 对偶问题的目标函数与原问题的目标函数值相等 ;

对偶问题的目标函数是 $\mathrm{m}\mathrm{a}\mathrm{x}\mathrm{Z}=4{\mathrm{y}}_1+6{\mathrm{y}}_2=4\times 0-2\times 6=-12$ ;

因此原问题的目标函数值也是 $12$ , 得到式子 $\mathrm{m}\mathrm{i}\mathrm{n}\mathrm{W}=2{\mathrm{x}}_1-{\mathrm{x}}_2+2{\mathrm{x}}_3=-12$ ;

这里就得到了 $3$ 个方程组 , $3$ 个变量 , 求解下面的方程组 , 最终结果就是最优解 ;

{ − x 1 + x 2 + x 3 = 4    ① − x 1 + x 2 − x 3 = 6    ② 2 x 1 − x 2 + 2 x 3 = − 12    ③

最终方程组的解是 :

{ x 1 = − 5 x 2 = 0 x 3 = − 1

最终的原方程的最优解是 ( − 5 0 − 1 )

目标函数值是 $-12$

四、互补松弛定理求最优解思路

给定线性规划 , 给定一个问题的最优解 , 求另一个问题的最优解 ;

互补松弛定理 :

" ${\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}}$ 是 松弛变量 或 剩余变量 ;

使用上述互补松弛定理 , 求出 给定的最优解 对应的对偶问题线性规划 松弛变量的值 ;

将 松弛变量 代入到 约束方程等式 中 , 求解出的值就是线性规划问题的最优解 ;

还有一种方式 , 就是根据给定的最优解 , 求出 本问题线性规划的 松弛变量值 ,

根据 本问题的松弛变量值 求对应 对偶问题的 最优解 ;

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

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