场景描述

假设有个老板要租赁该车间，最少需要支付的费用
设w1为木工每小时工钱， w2为油漆工每小时工钱
min \ f = 120w_1 + 50w_2 \\ s.t. \left\{\begin{matrix} 4w_1 + 2w_2 \geq 56 \\ 3w_1 + w_2 \geq 30 \\ w_1\ w_2 \geq 0 \\ \end{matrix}\right. \\ f^* = 1440 w^* = (2, 24)
这是一个极小值问题，需要使用dual simplex method,为啥呢？
simplex method需要先确定一组基础可行解（可行不一定最优），一般选择松弛变量s1,s2构成一组可行解，从几何上看，从最小的点开始逐渐增加，直到可行域的最大值。
但是极小值问题，无法确定一个基础可行解，因为一般约束条件都是a^T\cdot x \geq b的格式，一般围成的是一个开放区域。这种场景我们能快速确定一个最优但是不可行的解，比如原点，然后对该解一步步迭代找出可行最优解，这就是dual simplex method的核心思想

算法步骤

1. 初始化。将问题转化为标准格式，选择松弛变量构成初始可行解
2. solution列中负值的绝对值最大元素对应的行为pivot row和离基变量，都非负算法结束
3. 根据min{目标行中负值/pivot} 最小值确定入基变量和pivot column,如果所有目标行系数都非负，问题无解
4. 进行初等行变换，更换basic列中的标签。然后进入步骤2

说明：
步骤2选择绝对值最大是贪心体现，为了尽快逼近可行最优解
步骤3选择min{目标行中负值/pivot} ，是因为要是贪心会直接跳过最优解，从几何上看只能小步前进

1、初始化表格

根据"solution绝对值最大"-56确定[离基变量s1]和pivot row, 根据"目标行系数/支点行系数最小值", min(-120/-4, -50/-2) 确定pivot column = 2,那么入基变量 = w2，将第1行前面basic的标签改为w2
根据初等行变换，第1行所有元素除以-2，第2行和第3行分别加上第1行的1倍和50倍，得到下面的表格

第一次迭代后表格

根据"solution绝对值最大"-2确定[离基变量s2]和 pivot row, 根据"目标行系数/支点行系数最小值", min(-20/-1, -25/-.5) 确定pivot column = 1,那么入基变量 = w1，将第2行前面basic的标签改为w1
根据初等行变换，第2行所有元素除以-1，第1行和第3行分别加上第-2行的1倍和20倍，得到下面的表格

再次次迭代后表格

solution列所有系数非负，结束，最优解为w2=24, x1=2, 目标值为1440， (15, 20)是对偶问题的解

对偶单纯法和单纯法比较

单纯法适合求解能快速确定基础可行解的极大值问题。
对偶单纯法适合求解极小值问题，如果右端为负也可以处理
如果一个问题的约束矩阵的行数大于列数，可以将其转换为对偶问题，对偶问题求解后等于原问题求解

Posted in: IT人生