文章目录
一、原问题与对偶问题标准形式
原问题
\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 minW= 2x_1 - x_2 + 2x_3 \\\\ \rm \begin{cases} \rm -x_1 + x_2 + x_3 = 4 \\\\ \rm -x_1 + x_2 - x_3 \leq 6 \\\\ \rm x_1 \leq 0 ,x_2 \geq 0 , x_3 无约束 \end{cases}\end{array}上述线性规划的对偶问题的最优解是
\rm Y^0 = \begin{pmatrix} \quad \rm 0 \quad \rm -2 \quad \end{pmatrix} , 求其原问题最优解 ;
互补松弛定理 :
"
\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 是 松弛变量 或 剩余变量 ;
分析 :
给出了对偶问题最优解
\rm Y^0 = \begin{pmatrix} \quad \rm 0 \quad \rm -2 \quad \end{pmatrix} , 其互补松弛定理中对应原问题的松弛变量
\rm X_s =\begin{pmatrix} \quad \rm x_4 \quad \\\\ \quad \rm x_5 \quad \end{pmatrix} ;
根据公式有
\rm \begin{pmatrix} \quad \rm 0 \quad \rm -2 \quad \end{pmatrix} \times \begin{pmatrix} \quad \rm x_4 \quad \\\\ \quad \rm x_5 \quad \end{pmatrix} = 0\rm 0 x_4 - 2x_5= 0\rm - 2x_5= 0原问题添加松弛变量 ,
\rm -x_1 + x_2 + x_3 = 4 已经是等式了 , 添加一个
\rm x_4 松弛变量 ,
\rm x_4 = 0 ,
\rm -x_1 + x_2 - x_3 \leq 6 添加松弛变量
\rm x_5 , 由于对应的最优解不为
0 , 是
-2 , 其对应的松弛变量还是
0 , 即
x_5 = 0 ;
原问题的最优解满足
\begin{cases} \rm -x_1 + x_2 + x_3 = 4 \\\\ \rm -x_1 + x_2 - x_3 = 6 \end{cases} 方程 , 该方程组
2 个等式 ,
3 个变量 , 如果再得到一个方程 , 就可以得到三个方程 ;
根据 对偶理论中的 强对偶性 , 如果 原问题 与 对偶问题 都有可行解 , 只要有一个问题有最优解 , 则 两个问题都有最优解 , 二者的最优解的目标函数值相等 ;
这里求一下对偶问题的目标函数值 , 对偶问题的目标函数与原问题的目标函数值相等 ;
对偶问题的目标函数是
\rm max Z = 4y_1 + 6y_2 = 4 \times 0 - 2 \times 6 = -12 ;
因此原问题的目标函数值也是
12 , 得到式子
\rm minW= 2x_1 - x_2 + 2x_3 = -12 ;
这里就得到了
3 个方程组 ,
3 个变量 , 求解下面的方程组 , 最终结果就是最优解 ;
\begin{cases} \rm -x_1 + x_2 + x_3 = 4 \ \ ① \\\\ \rm -x_1 + x_2 - x_3 = 6 \ \ ② \\\\ 2x_1 - x_2 + 2x_3 = -12 \ \ ③ \end{cases}最终方程组的解是 :
\begin{cases} \rm x_1 = -5 \\\\ \rm x_2 = 0 \\\\ x_3 = -1 \end{cases}最终的原方程的最优解是
\begin{pmatrix} \quad \rm -5 \quad 0 \quad \rm -1 \quad \end{pmatrix}目标函数值是
-12四、互补松弛定理求最优解思路
给定线性规划 , 给定一个问题的最优解 , 求另一个问题的最优解 ;
互补松弛定理 :
"
\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 是 松弛变量 或 剩余变量 ;
使用上述互补松弛定理 , 求出 给定的最优解 对应的对偶问题线性规划 松弛变量的值 ;
将 松弛变量 代入到 约束方程等式 中 , 求解出的值就是线性规划问题的最优解 ;
还有一种方式 , 就是根据给定的最优解 , 求出 本问题线性规划的 松弛变量值 ,
根据 本问题的松弛变量值 求对应 对偶问题的 最优解 ;
