文章目录
- 一、原问题与对偶问题标准形式
- 二、互补松弛定理
- 三、已知原问题最优解求对偶问题最优解
- 四、使用单纯形法求解
- 五、使用互补松弛定理公式一求解
- 六、使用互补松弛定理公式二求解 ( 无效方法 )
- 七、总结
一、原问题与对偶问题标准形式
原问题
\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 = 3x_1 + 4x_2 + x_3 \\\\ \rm \begin{cases} \rm x_1 + 2x_2 + x_3 \leq 10 \\\\ \rm 2x_1 + 2x_2 + x_3 \leq 16 \\\\ \rm x_1,x_2, x_3 \geq 0 \end{cases}\end{array}上述线性规划的最优解是
\rm X^0 = \begin{pmatrix} \quad \rm 6 \quad \rm 2 \quad 0 \quad \end{pmatrix} , 求其对偶问题最优解 ;
四、使用单纯形法求解
方法一 : 写出上述线性规划的对偶问题 , 然后使用单纯形法求最优解 ,
首先写出 对偶问题 , 然后转为 标准形式 , 找 单位阵 作为基矩阵 , 然后得到基变量 , 假设非基变量为
0 求出 基解 ,
在单纯形表中计算 检验数 , 如果 检验数都小于
0 就是最优解 , 如果检验数都大于
0 , 则不是最优解 ;
根据检验数确定 出基变量 , 然后计算出 入基变量 , 进行下一次迭代 ;
方程组 同解变换, 构造单位阵 , 然后计算检验数 , 继续按照上述方法进行迭代 ;
该方法比较麻烦 ;
五、使用互补松弛定理公式一求解
方法二 : 利用 互补松弛定理 计算 ;
写出原问题的对偶问题 :
\begin{array}{lcl} \rm minW = 10y_1 + 16y_2 \\\\ \rm \begin{cases} \rm y_1 + 2y_2 \geq 3 \\\\ \rm 2y_1 + 2y_2 \geq 4 \\\\ \rm y_1 + y_2 \geq 1 \\\\ \rm y_1,y_2 \geq 0 \end{cases}\end{array}给对偶问题的约束方程添加剩余变量 :
\begin{cases} \rm y_1 + 2y_2 - y_3 = 3 \\\\ \rm 2y_1 + 2y_2 - y_4 = 4 \\\\ \rm y_1 + y_2 - y_5 = 1 \\\\ \rm y_1,y_2, y_3 , y _4, y_5 \geq 0 \end{cases}互补松弛定理 :
"
\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 P 线性规划最优解是
\rm X^0 = \begin{pmatrix} \quad \rm 6 \quad \rm 2 \quad 0 \quad \end{pmatrix} ,
对偶问题的剩余变量是
\rm Y_s= \begin{pmatrix} \quad \rm y_3 \quad \\\\ \quad \rm y_4 \quad \\\\ \quad \rm y_5 \quad \\ \end{pmatrix}互补松弛定理中
\rm Y_sX^0 = 0 , 将上述
\rm X^0 和
\rm Y_s 代入上述式子得到 :
\rm Y_sX^0 = \begin{pmatrix} \quad \rm 6 \quad \rm 2 \quad 0 \quad \end{pmatrix} \times \begin{pmatrix} \quad \rm y_3 \quad \\\\ \quad \rm y_4 \quad \\\\ \quad \rm y_5 \quad \\ \end{pmatrix} = 6y_3 + 2y_4 + 0y_5 = 6y_3 + 2y_4 =0已知
\rm y_3, y_4 \geq 0 , 上述
\rm 6y_3 + 2y_4 = 0 , 因此
\rm y_3 = 0 , y_4 = 0 ;
将
\rm y_3 = 0 , y_4 = 0 代入到约束方程
\begin{cases} \rm y_1 + 2y_2 - y_3 = 3 \\\\ \rm 2y_1 + 2y_2 - y_4 = 4 \\\\ \rm y_1 + y_2 - y_5 = 1 \\\\ \rm y_1,y_2, y_3 , y _4, y_5 \geq 0 \end{cases} 中 ;
得到
\begin{cases} \rm y_1 + 2y_2 = 3 \\\\ \rm 2y_1 + 2y_2 = 4 \end{cases} , 解上述方程 ,
① 变换 :
\begin{cases} \rm 2y_1 + 4y_2 = 6 \\\\ \rm 2y_1 + 2y_2 = 4 \end{cases}② 求解 :
\begin{cases} \rm y_1 = 1 \\\\ \rm y_2 = 1 \end{cases}上述求出的值就是最优解 , 即
\rm Y^0 = \begin{pmatrix} \quad \rm 1 \quad 1 \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_sX^0 = 0 公式进行求解 , 在本小节中使用
\rm Y^0 X_s = 0 公式进行求解 ;
原问题
\rm P 线性规划最优解是
\rm X^0 = \begin{pmatrix} \quad \rm 6 \quad \rm 2 \quad 0 \quad \end{pmatrix} , 将该最优解代入原问题的约束条件中 , 求出原问题的约束变量
\rm X_s ;
原问题 :
\begin{array}{lcl} \rm maxZ = 3x_1 + 4x_2 + x_3 \\\\ \rm \begin{cases} \rm x_1 + 2x_2 + x_3 \leq 10 \\\\ \rm 2x_1 + 2x_2 + x_3 \leq 16 \\\\ \rm x_1,x_2, x_3 \geq 0 \end{cases}\end{array}原问题添加松弛变量后 :
\begin{array}{lcl} \rm maxZ = 3x_1 + 4x_2 + x_3 \\\\ \rm \begin{cases} \rm x_1 + 2x_2 + x_3 + x_4 = 10 \\\\ \rm 2x_1 + 2x_2 + x_3 + x_5 =16 \\\\ \rm x_1,x_2, x_3, x_4 , x_5 \geq 0 \end{cases}\end{array}将最优解
\rm X^0 = \begin{pmatrix} \quad \rm 6 \quad \rm 2 \quad 0 \quad \end{pmatrix} 代入原问题 :
\begin{cases} \rm 6 + 2\times 2 + 0 + x_4 = 10 \\\\ \rm 2 \times 6 + 2 \times 2 + 0 + x_5 = 16 \end{cases}得到 :
\begin{cases} \rm x_4 = 0 \\\\ \rm x_5 = 10 \end{cases}\rm X_s = \begin{pmatrix} \quad \rm 0 \quad \\\\ \quad \rm 0 \quad \end{pmatrix}这个信息是无用的 , 根据这个
\rm X_s 乘以任意的
\rm Y^0 值都是
0 , 求不出对偶问题的最优解 ;
七、总结
互补松弛定理 :
"
\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 P 线性规划最优解是
\rm X^0 = \begin{pmatrix} \quad \rm 6 \quad \rm 2 \quad 0 \quad \end{pmatrix} ,
对偶问题的剩余变量是
\rm Y_s= \begin{pmatrix} \quad \rm y_3 \quad \\\\ \quad \rm y_4 \quad \\\\ \quad \rm y_5 \quad \\ \end{pmatrix}最优解中不等于
0 的 , 对应的剩余变量中对应的一定为
0 ,
如果最优解中等于
0 , 那么剩余变量中的对应的值就不确定了 ;