一、互补松弛定理作用

互补松弛定理作用 :

① 简化求对偶问题最优解过程 : 已知一个线性规划问题的最优解 , 可以 简化求另外一个问题最优解的过程 , 避免使用两次单纯形法求解 ;

② 影子价格问题 : 使用互补松弛定理可以进行一些 经济解释 , 如影子价格问题 ;

二、影子价格

影子价格 是 对偶问题的 经济解释 ;

影子价格定义 :

在一对 $\mathrm{P}$ 和 $\mathrm{D}$ 中 ,

如果 $\mathrm{P}$ 的某个 约束条件 的 右端常数项 ${\mathrm{b}}_{\mathrm{i}}$ ( 第 $\mathrm{i}$ 种资源的拥有量 ) 增加一个单位时 ,

所引起 $\mathrm{P}$ 目标函数 最优值 ${\mathrm{z}}^{\ast }$ 的该变量称为 第 $\mathrm{i}$ 种资源的 影子价格 ,

其值等于 $\mathrm{D}$ 问题 中的 对偶变量 ${\mathrm{y}}_{\mathrm{i}}^{\ast }$ ;

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

由对偶问题的基本性质得到如下结论 :

$${\mathrm{z}}^{\ast }=\sum _{\mathrm{j}=1}^{\mathrm{n}}{\mathrm{c}}_{\mathrm{j}}{\mathrm{x}}_{\mathrm{j}}=\sum _{\mathrm{i}=1}^{\mathrm{m}}{\mathrm{b}}_{\mathrm{i}}{\mathrm{y}}_{\mathrm{i}}$$

${\mathrm{c}}_{\mathrm{j}}$ 表示每个产品带来的利润 ,

${\mathrm{x}}_{\mathrm{j}}$ 表示产品的个数 ;

影子价格 是 对偶问题 的变量值 ;

三、影子价格示例

生产问题 ( 原问题 ) :

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 )

上述原问题线性规划中的影子价格 :

${\mathrm{z}}^{\ast }=2{\mathrm{x}}_1+3{\mathrm{x}}_2=12{\mathrm{y}}_1+8{\mathrm{y}}_2+16{\mathrm{y}}_3+12{\mathrm{y}}_4$

原问题分析 :

约束方程的 $4$ 个不等式 , 就是 $\mathrm{A}\mathrm{B}\mathrm{C}\mathrm{D}$ 四个设备的台时数 ,

甲产品带来利润 $2$ , 乙产品带来利润 $3$ ;

假设 $\mathrm{P}$ 问题的目标函数是 $\mathrm{m}\mathrm{a}\mathrm{x}\mathrm{Z}=2{\mathrm{x}}_1+3{\mathrm{x}}_2$ ,

$\mathrm{m}\mathrm{a}\mathrm{x}\mathrm{Z}$ 是利润 ,

${\mathrm{x}}_1$ 代表甲产品的数量 , ${\mathrm{x}}_1$ 的系数 $2$ 代表甲产品多生产一个单位能够带来的利润增加 $2$ ,

${\mathrm{x}}_2$ 代表乙产品的数量 , ${\mathrm{x}}_2$ 的系数 $3$ 代表乙产品多生产一个单位能够带来的利润增加 $3$ ;

对偶问题分析 :

$12{\mathrm{y}}_1$ 中的系数 $12$ 增大一个单位 , 能够对目标函数值贡献多少 , 该贡献值与 ${\mathrm{y}}_1$ 值相关 ;

将对偶问题最优解 ( 1 2 1 0 0 )

得到 $12\times \frac{1}{2}+8\times 1+16\times 0+12\times 0$

$12\times \frac{1}{2}$ 含义 : 当第一个系数 $12$ ( 设备 $\mathrm{A}$ 的台时数 ) 增大时 , 整个目标函数增大 , 每增大一个单位 , 目标函数增加 $\frac{1}{2}$ ;

$8\times 1$ 含义 : 当第二个系数 $8$ ( 设备 $\mathrm{B}$ 的台时数 ) 增大时 , 整个目标函数增大 , 每增大一个单位 , 目标函数增加 $1$ ;

$16\times 0$ 含义 : 当第三个系数 $16$ ( 设备 $\mathrm{C}$ 的台时数 ) 增大时 , 整个目标函数不变 , 每增大一个单位 , 目标函数增加 $0$ ;

$12\times 0$ 含义 : 当第四个系数 $21$ ( 设备 $\mathrm{D}$ 的台时数 ) 增大时 , 整个目标函数不变 , 每增大一个单位 , 目标函数增加 $0$ ;

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

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