文章目录
一、原问题与对偶问题标准形式
原问题
\rm P :
\begin{array}{lcl} \rm maxZ = C X \\\\ \rm s.t\begin{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.t\begin{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.t\begin{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.t\begin{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 的 最优解 "
\Leftrightarrow\begin{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 = 0\rm y_5 , y_6 都是大于等于
0 的 , 如果要满足
\rm 4 y_5 + 2y_6 = 0 , 则得到
\rm y_5 = 0, y_6 = 0 结论 ;
粤公网安备44030502008569号