线性规划的对偶问题
给出线性规划
\[\max z = c^T x \\
s.t. \begin{cases}
Ax \le b\\
x \ge 0
\end{cases}
\]
则其对偶问题为
\[\min z' = b^Ty\\
s.t. \begin{cases}
A^Ty \ge c\\
y \ge 0
\end{cases}
\]
可以由弱对偶定理记忆：
\[z = c^Tx \le y^T A x \le y^T b = z'
\]
现实意义
已知由材料 a,b 可以制作成商品 A,B,C。已知材料总量和商品获利，求最大总利润。
| A | B | C | 总量 | |
|---|---|---|---|---|
| a | 2 | 1 | 4 | 10 |
| b | 5 | 8 | 6 | 20 |
| 获利 | 20 | 40 | 80 |
不难得出线性规划模型：
\[\max z = 20x_1+40x_2+80x_3\\
s.t. \begin{cases}
2x_1 + x_2 + 4x_3 \le 10\\
5x_1 + 8x_2 + 6x_3 \le 20 \\
x_i \ge 0 (i = 1,2,3)
\end{cases}
\]
现对材料进行收购，价格待定，求最小收购价，则线性规划模型为：
\[\min z' = 10y_1 + 20y_2 \\
s.t. \begin{cases}
2y_1 + 5y_2 \ge 20\\
y_1 + 8y_2 \ge 40\\
4y_1 + 6y_2 \ge 80\\
y_1 \ge 0, y_2 \ge 0
\end{cases}
\]
我们惊喜地发现这此二者互为对偶问题。这两个问题的本质差别在于是从行还是从列的角度看待限制。
应用
P7246 手势密码
设对路径 \(S\) 操作了 \(x_S\) 次，则有线性规划模型：
\[\min z = \sum_S x_S\\
s.t. \begin{cases}
\sum_{S \ni u} x_S = a_u\\
x_S \ge 0
\end{cases}
\]
转对偶问题得
\[\max z' = \sum_{u=1}^n a_u y_u \\
s.t. \sum_{u \in S} y_u \le 1
\]
注意 \(y\) 可取全体实数。但分析条件实际上只用取 \(\{-1,0,1\}\)。此时不难得到简单树形 DP。
[ZJOI2020 D1T3] 序列
这题简直是上一题的弱化版。设操作的点集构成的集合为 \(\mathcal{I}\)，那么线性规划模型为：
\[\min z = \sum_{S \in \mathcal I} x_S\\
s.t. \begin{cases}
\sum_{S \ni i} x_S = a_i \\
x_S \ge 0
\end{cases}
\]
转对偶
\[\max z' = \sum_{u=1}^n a_u y_u \\
s.t. \sum_{u \in S} y_u \le 1
\]
和上一题完全一样。DP 比上一题更简单，一下子就做完了。
小结
以上两个例子中，线性规划转对偶问题的优越性体现在原问题是难以处理的操作 + 容易描述的限制，而转化为对偶问题后，变成了容易处理的操作 + 更容易描述的限制。结合上面提到的对偶问题的现实意义，我们对这一方法有了更加深层次的体会......
然而，其实上面两题解法中存在不完备之处，因为转对偶线性规划后不一定有整数最优解，这处漏洞我还没搞懂，在此挖坑，希望以后能填上。