2023-03-28 20:35:11
浏览数 (1)
文章目录
- 一、原问题与对偶问题标准形式
- 二、互补松弛定理
- 三、互补松弛定理示例说明
一、原问题与对偶问题标准形式
原问题
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 X^0 和
rm Y^0 分别是 原问题
rm P 问题 和 对偶问题
rm D 的 可行解 ,
这两个解各自都是对应 线性规划问题 的 最优解
的 充要条件是 :
begin{cases} rm Y^0 X_s = 0 \\ rm Y_sX^0 = 0 end{cases}其中
rm X_s , Y_s 是 松弛变量 或 剩余变量 ;
三、互补松弛定理示例说明
原问题与对偶问题的对应关系 :
生产问题 ( 原问题 ) :
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}将上面两个线性规划的最优解代入目标函数 , 得到的值都是
14 ;
互补松弛定理 :
"
rm X^0 和
rm Y^0 分别是 原问题
rm P 问题 和 对偶问题
rm D 的 最优解 "
Leftrightarrowbegin{cases} rm Y^0 X_s = 0 \\ rm Y_sX^0 = 0 end{cases}其中
rm X_s , Y_s 是 松弛变量 或 剩余变量 ;
begin{pmatrix} quad rm 4 quad 2 quad \ end{pmatrix} 是原问题
rm P 的最优解 , 是
rm X^0 ,
rm Y_s 是对偶问题
rm D 的剩余变量 ,
begin{cases} rm 2 y_1 y_2 4y_3 0y_4 - y_5 = 2 \\ rm 2 y_1 2y_2 0y_3 4y_4 - y_6 = 3 end{cases} , 两个剩余变量是
begin{pmatrix} quad rm y_5 quad \ quad rm y_6 quad \ end{pmatrix} , 是
rm Y_s ,
根据互补松弛定理 ,
rm Y_sX^0 = 0 , 将真实值代入 :
rm Y_sX^0 = begin{pmatrix} quad rm 4 quad 2 quad \ end{pmatrix} times begin{pmatrix} quad rm y_5 quad \ quad rm y_6 quad \ end{pmatrix} =4 y_5 2y_6 = 0rm y_5 , y_6 都是大于等于
0 的 , 如果要满足
rm 4 y_5 2y_6 = 0 , 则得到
rm y_5 = 0, y_6 = 0 结论 ;
