- 一、原问题与对偶问题标准形式
- 二、互补松弛定理
- 三、已知原问题最优解求对偶问题最优解
- 四、互补松弛定理求最优解思路
原问题 P \rm P P : m a x Z = C X s . t { A X ≤ b X ≥ 0 \begin{array}{lcl} \rm maxZ = C X \\\\ \rm s.t\begin{cases} \rm AX \leq b \\\\ \rm X \geq 0 \end{cases}\end{array} maxZ=CXs.t⎩⎪⎨⎪⎧AX≤bX≥0 ; \ \ \ \ \ \ \ \ \ \ \, 对偶问题 D \rm D D : m i n W = b T Y s . t { A T Y ≥ C T Y ≥ 0 \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} minW=bTYs.t⎩⎪⎨⎪⎧ATY≥CTY≥0
等价方法 :
- 生产 : 目标函数追求 利润最大化 , 约束方程设备的使用时长受约束 , 小于等于 某个时间值 ;
- 出租设备 : 目标函数追求 租金最小化 , 约束方程设备产生的利润要 大于等于 生产的利润 , 不能亏钱 ;
X 0 \rm X^0 X0 和 Y 0 \rm Y^0 Y0 分别是 原问题 P \rm P P 问题 和 对偶问题 D \rm D D 的 可行解 ,
这两个解各自都是对应 线性规划问题 的 最优解
的 充要条件是 : { Y 0 X s = 0 Y s X 0 = 0 \begin{cases} \rm Y^0 X_s = 0 \\\\ \rm Y_sX^0 = 0 \end{cases} ⎩⎪⎨⎪⎧Y0Xs=0YsX0=0
其中 X s , Y s \rm X_s , Y_s Xs,Ys 是 松弛变量 或 剩余变量 ;
三、已知原问题最优解求对偶问题最优解已知线性规划 :
m i n W = 2 x 1 − x 2 + 2 x 3 { − x 1 + x 2 + x 3 = 4 − x 1 + x 2 − x 3 ≤ 6 x 1 ≤ 0 , x 2 ≥ 0 , x 3 无 约 束 \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} minW=2x1−x2+2x3⎩⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎧−x1+x2+x3=4−x1+x2−x3≤6x1≤0,x2≥0,x3无约束
上述线性规划的对偶问题的最优解是 Y 0 = ( 0 − 2 ) \rm Y^0 = \begin{pmatrix} \quad \rm 0 \quad \rm -2 \quad \end{pmatrix} Y0=(0−2) , 求其原问题最优解 ;
互补松弛定理 :
" X 0 \rm X^0 X0 和 Y 0 \rm Y^0 Y0 分别是 原问题 P \rm P P 问题 和 对偶问题 D \rm D D 的 最优解 " ⇔ \Leftrightarrow ⇔ { Y 0 X s = 0 Y s X 0 = 0 \begin{cases} \rm Y^0 X_s = 0 \\\\ \rm Y_sX^0 = 0 \end{cases} ⎩⎪⎨⎪⎧Y0Xs=0YsX0=0
其中 X s , Y s \rm X_s , Y_s Xs,Ys 是 松弛变量 或 剩余变量 ;
分析 :
给出了对偶问题最优解 Y 0 = ( 0 − 2 ) \rm Y^0 = \begin{pmatrix} \quad \rm 0 \quad \rm -2 \quad \end{pmatrix} Y0=(0−2) , 其互补松弛定理中对应原问题的松弛变量 X s = ( x 4 x 5 ) \rm X_s =\begin{pmatrix} \quad \rm x_4 \quad \\\\ \quad \rm x_5 \quad \end{pmatrix} Xs=⎝⎛x4x5⎠⎞ ;
根据公式有 ( 0 − 2 ) × ( x 4 x 5 ) = 0 \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 (0−2)×⎝⎛x4x5⎠⎞=0 0 x 4 − 2 x 5 = 0 \rm 0 x_4 - 2x_5= 0 0x4−2x5=0
− 2 x 5 = 0 \rm - 2x_5= 0 −2x5=0
原问题添加松弛变量 ,
− x 1 + x 2 + x 3 = 4 \rm -x_1 + x_2 + x_3 = 4 −x1+x2+x3=4 已经是等式了 , 添加一个 x 4 \rm x_4 x4 松弛变量 , x 4 = 0 \rm x_4 = 0 x4=0 ,
− x 1 + x 2 − x 3 ≤ 6 \rm -x_1 + x_2 - x_3 \leq 6 −x1+x2−x3≤6 添加松弛变量 x 5 \rm x_5 x5 , 由于对应的最优解不为 0 0 0 , 是 − 2 -2 −2 , 其对应的松弛变量还是 0 0 0 , 即 x 5 = 0 x_5 = 0 x5=0 ;
原问题的最优解满足 { − x 1 + x 2 + x 3 = 4 − x 1 + x 2 − x 3 = 6 \begin{cases} \rm -x_1 + x_2 + x_3 = 4 \\\\ \rm -x_1 + x_2 - x_3 = 6 \end{cases} ⎩⎪⎨⎪⎧−x1+x2+x3=4−x1+x2−x3=6 方程 , 该方程组 2 2 2 个等式 , 3 3 3 个变量 , 如果再得到一个方程 , 就可以得到三个方程 ;
根据 对偶理论中的 强对偶性 , 如果 原问题 与 对偶问题 都有可行解 , 只要有一个问题有最优解 , 则 两个问题都有最优解 , 二者的最优解的目标函数值相等 ;
这里求一下对偶问题的目标函数值 , 对偶问题的目标函数与原问题的目标函数值相等 ;
对偶问题的目标函数是 m a x Z = 4 y 1 + 6 y 2 = 4 × 0 − 2 × 6 = − 12 \rm max Z = 4y_1 + 6y_2 = 4 \times 0 - 2 \times 6 = -12 maxZ=4y1+6y2=4×0−2×6=−12 ;
因此原问题的目标函数值也是 12 12 12 , 得到式子 m i n W = 2 x 1 − x 2 + 2 x 3 = − 12 \rm minW= 2x_1 - x_2 + 2x_3 = -12 minW=2x1−x2+2x3=−12 ;
这里就得到了 3 3 3 个方程组 , 3 3 3 个变量 , 求解下面的方程组 , 最终结果就是最优解 ;
{ − x 1 + x 2 + x 3 = 4 ① − x 1 + x 2 − x 3 = 6 ② 2 x 1 − x 2 + 2 x 3 = − 12 ③ \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} ⎩⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎧−x1+x2+x3=4 ①−x1+x2−x3=6 ②2x1−x2+2x3=−12 ③
最终方程组的解是 :
{ x 1 = − 5 x 2 = 0 x 3 = − 1 \begin{cases} \rm x_1 = -5 \\\\ \rm x_2 = 0 \\\\ x_3 = -1 \end{cases} ⎩⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎧x1=−5x2=0x3=−1
最终的原方程的最优解是 ( − 5 0 − 1 ) \begin{pmatrix} \quad \rm -5 \quad 0 \quad \rm -1 \quad \end{pmatrix} (−50−1)
目标函数值是 − 12 -12 −12
四、互补松弛定理求最优解思路给定线性规划 , 给定一个问题的最优解 , 求另一个问题的最优解 ;
互补松弛定理 :
" X 0 \rm X^0 X0 和 Y 0 \rm Y^0 Y0 分别是 原问题 P \rm P P 问题 和 对偶问题 D \rm D D 的 最优解 " ⇔ \Leftrightarrow ⇔ { Y 0 X s = 0 Y s X 0 = 0 \begin{cases} \rm Y^0 X_s = 0 \\\\ \rm Y_sX^0 = 0 \end{cases} ⎩⎪⎨⎪⎧Y0Xs=0YsX0=0
其中 X s , Y s \rm X_s , Y_s Xs,Ys 是 松弛变量 或 剩余变量 ;
使用上述互补松弛定理 , 求出 给定的最优解 对应的对偶问题线性规划 松弛变量的值 ;
将 松弛变量 代入到 约束方程等式 中 , 求解出的值就是线性规划问题的最优解 ;
还有一种方式 , 就是根据给定的最优解 , 求出 本问题线性规划的 松弛变量值 ,
根据 本问题的松弛变量值 求对应 对偶问题的 最优解 ;
