文章目录
一、互补松弛定理作用
互补松弛定理作用 :
① 简化求对偶问题最优解过程 : 已知一个线性规划问题的最优解 , 可以 简化求另外一个问题最优解的过程 , 避免使用两次单纯形法求解 ;
② 影子价格问题 : 使用互补松弛定理可以进行一些 经济解释 , 如影子价格问题 ;
二、影子价格
影子价格 是 对偶问题的 经济解释 ;
影子价格定义 :
在一对
rm P 和
rm D 中 ,
如果
rm P 的某个 约束条件 的 右端常数项
rm b_i ( 第
rm i 种资源的拥有量 ) 增加一个单位时 ,
所引起
rm P 目标函数 最优值
rm z^* 的该变量称为 第
rm i 种资源的 影子价格 ,
其值等于
rm D 问题 中的 对偶变量
rm y_i^* ;
原问题
rm P :
begin{array}{lcl} rm maxZ = C X \\ rm s.tbegin{cases} rm AX leq b \\ rm X geq 0 end{cases}end{array} ;
, 对偶问题
rm D :
begin{array}{lcl} rm minW = b^T Y \\ rm s.tbegin{cases} rm A^TY geq C^T \\ rm Y geq 0 end{cases}end{array}由对偶问题的基本性质得到如下结论 :
rm z^* = sum_{j = 1}^n c_jx_j = sum_{i = 1}^m b_iy_irm c_j 表示每个产品带来的利润 ,
rm x_j 表示产品的个数 ;
影子价格 是 对偶问题 的变量值 ;
三、影子价格示例
生产问题 ( 原问题 ) :
begin{array}{lcl} rm maxZ = 2x_1 3x_2 \\ rm s.tbegin{cases} rm 2 x_1 2x_2 leq 12 \\ rm x_1 2x_2 leq 8 \\ rm 4 x_1 leq 16 \\ rm 4x_2 leq 12 \\ rm x_1, x_2 geq 0 end{cases}end{array}上述线性规划的最优解是 :
begin{pmatrix} quad rm 4 quad 2 quad \ end{pmatrix} ;
甲产品生产
4 个单位 , 乙产品生产
2 个单位 ;
设备出租问题 ( 对偶问题 ) :
begin{array}{lcl} rm minW = 12y_1 8y_2 16y_3 12y_4 \\ rm s.tbegin{cases} rm 2 y_1 y_2 4y_3 0y_4 geq 2 \\ rm 2 y_1 2y_2 0y_3 4y_4 geq 3 \\ rm y_1, y_2 , y_3 , y _4 geq 0 end{cases}end{array}上述线性规划最优解是 :
begin{pmatrix} quad rm cfrac{1}{2} quad 1 quad 0 quad 0 quad \ end{pmatrix} , 或
begin{pmatrix} quad rm 0 quad cfrac{2}{3} quad cfrac{1}{8} quad 0 quad \ end{pmatrix}上述原问题线性规划中的影子价格 :
rm z^* = 2 x_1 3x_2 = 12y_1 8y_2 16y_3 12y_4原问题分析 :
约束方程的
4 个不等式 , 就是
rm ABCD 四个设备的台时数 ,
甲产品带来利润
2 , 乙产品带来利润
3 ;
假设
rm P 问题的目标函数是
rm max Z = 2 x_1 3x_2 ,
rm maxZ 是利润 ,
rm x_1 代表甲产品的数量 ,
rm x_1 的系数
2 代表甲产品多生产一个单位能够带来的利润增加
2 ,
rm x_2 代表乙产品的数量 ,
rm x_2 的系数
3 代表乙产品多生产一个单位能够带来的利润增加
3 ;
对偶问题分析 :
rm 12 y_1 中的系数
12 增大一个单位 , 能够对目标函数值贡献多少 , 该贡献值与
rm y_1 值相关 ;
将对偶问题最优解
begin{pmatrix} quad rm cfrac{1}{2} quad 1 quad 0 quad 0 quad \ end{pmatrix} 代入到
rm 12y_1 8y_2 16y_3 12y_4 中 ,
得到
rm 12 times cfrac{1}{2} 8 times 1 16 times 0 12 times 012 times cfrac{1}{2} 含义 : 当第一个系数
12 ( 设备
rm A 的台时数 ) 增大时 , 整个目标函数增大 , 每增大一个单位 , 目标函数增加
cfrac{1}{2} ;
8 times 1 含义 : 当第二个系数
8 ( 设备
rm B 的台时数 ) 增大时 , 整个目标函数增大 , 每增大一个单位 , 目标函数增加
1 ;
16 times 0 含义 : 当第三个系数
16 ( 设备
rm C 的台时数 ) 增大时 , 整个目标函数不变 , 每增大一个单位 , 目标函数增加
0 ;
12 times 0 含义 : 当第四个系数
21 ( 设备
rm D 的台时数 ) 增大时 , 整个目标函数不变 , 每增大一个单位 , 目标函数增加
0 ;
