讨论课 9

(a) 可行域如下图所示（由约束半平面的交集构成）。

(b) 可行域的顶点为 \((0, 4), (0, 5), (6, 3), (4, 0)\)。依赖于起始顶点，单纯形法会以贪心方式访问顶点以最大化目标 \(5x + 4y\)。例如，假设我们从 \((0, 4)\) 出发，步骤如下：

• 在 \((0, 4)\) 处目标值为 \(5(0) + 4(4) = 16\)。其邻居为 \((0, 5)\) 与 \((4, 0)\)，目标值分别为 \(5(0) + 4(5) = 20\) 与 \(5(4) + 4(0) = 20\)。由于我们试图最大化目标函数，应移向其中一个邻居（此处两者目标值相同，不妨移向 \((0, 5)\)）。

• 在 \((0, 5)\) 处目标值为 20。其邻居：\((0, 4)\) 为 16，\((6, 3)\) 为 \(5(6) + 4(3) = 42\)。由于 \(42 > 20\)，移向 \((6, 3)\)。

• 在 \((6, 3)\) 处目标值为 42，高于其任意邻居（\((0, 5)\) 与 \((4, 0)\) 均为 20）。因此已找到 LP 的最优点。

本次单纯形运行依次访问了 \((0, 4), (0, 5), (6, 3)\)。

(a) 一个分配 \(x\) 是对数值 \(x_{ij}\) 的选择，其中 \(x_{ij}\) 表示第 \(i\) 个人在工作 \(j\) 上花费的时间比例。

(b) 约束如下：

• 任何第 \(i\) 个人工作的总时间不能超过 1 天： \[ \sum_{j=1}^{J} x_{ij} \le 1, \quad i = 1, \dots, I. \]

• 任何工作 \(j\) 不能被投入超过完成所需的时间： \[ \sum_{i=1}^{I} x_{ij} \le 1, \quad j = 1, \dots, J. \]

• 非负性： \[ x_{ij} \ge 0, \quad i = 1, \dots, I,\; j = 1, \dots, J. \]

(c) 第 \(i\) 个人在工作 \(j\) 上工作 \(x_{ij}\) 时间所贡献的价值为 \(a_{ij}x_{ij}\)。因此净价值为 \[ \sum_{i=1}^{I}\sum_{j=1}^{J} a_{ij}x_{ij} = A \bullet x. \]

(a) 假。考虑以下图：S->A 容量 7，S->B 容量 5，A->C 容量 4，B->C 容量 9，A->T 容量 2，B->T 容量 3，C->T 容量 3（所有容量互异）。存在多个达到同一最大流值的流分配，故最大流不唯一。

(b) 假。考虑以下图：S->A 容量 7，S->B 容量 1，A->C 容量 4，B->C 容量 8，A->T 容量 2，B->T 容量 3，C->T 容量 3。割 \(\{S,A\}\) 与割 \(\{S,A,B\}\) 的值均为 7，故最小割不唯一。

(c) 假。将 (b) 中图中所有边的容量加 1。割 \(\{S,A\}\) 与 \(\{S,A,B\}\) 的值现在不同，最小割发生改变。

(d) 真。设一个割的值为 \(\sum_{e} c_e\)，最小割的值为 \(\sum_{e'} c_{e'}\)。乘以正整数 \(a\) 后，由分配律： \[ a\sum_{e'} c_{e'} - a\sum_{e} c_e = a\left(\sum_{e'} c_{e'} - \sum_{e} c_e\right), \] 故割之间的优劣关系不变，最小割仍为原最小割。

(e) 假。考虑存在有向环 A->B->C->A 且环上每条边流量均为正的最大流实例。

(f) 真。取 (e) 中图去掉边 S->A 后的图，或任意不含正流量有向环的最大流即可。

(a) 沿 S->A->C->T 推送 4 单位流后的残差图：

• S->A 剩余容量 3，反向边 A->S 容量 4；

• A->C 剩余容量 0（边消失），反向边 C->A 容量 4；

• C->T 剩余容量 3，反向边 T->C 容量 4；

• 其余边保持不变：S->B 容量 5，B->C 容量 6，A->T 容量 4，B->T 容量 7。

(b) 一个数值为 11 的最大流由以下推送得到：

• 沿 S -> A -> C -> T 推送 4 单位流；

• 沿 S -> B -> T 推送 5 单位流；

• 沿 S -> A -> B -> T 推送 2 单位流。

（还存在其它同一最大流值的流。）该最大流对应的残差图：

• S->A 容量 1（反向 A->S 容量 6）；

• S->B 容量 0（反向 B->S 容量 5）；

• A->C 容量 0（反向 C->A 容量 4）；

• B->C 容量 4（反向 C->B 容量 2）；

• A->T 容量 4；

• B->T 容量 0（反向 T->B 容量 7）；

• C->T 容量 3（反向 T->C 容量 4）。

一个数值为 11 的最小割为划分 \(\{S, A, B\}\) 与 \(\{C, T\}\)，跨割边为 A->C 与 B->T。

(a) 对偶为：

\[ \min \quad 7x_{SA} + 5x_{SB} + 4x_{AT} + 4x_{AB} + 7x_{BT} \]

满足

\[ \begin{cases} x_{SA} + x_{AT} \ge 1 & \text{（对应 } f_1 \text{ 的约束）} \\ x_{SA} + x_{AB} + x_{BT} \ge 1 & \text{（对应 } f_2 \text{ 的约束）} \\ x_{SB} + x_{BT} \ge 1 & \text{（对应 } f_3 \text{ 的约束）} \\ x_e \ge 0 \quad \forall e \in E \end{cases} \]

(b) 注意到每个约束包含了对应路径上所有边的变量 \(x_e\)。对于任意 s-t 割，每条 s-t 路径都包含至少一条跨割边。因此对于任意割，所建议的解会使每条路径上至少一个 \(x_e\) 被设为 1，从而每个约束都被满足。

(c) 该对偶 LP 是刻画最小割（min-cut）问题的 LP。由上一部分可知，约束描述的是对应于割的解；目标函数则要求找到值最小的割。由 LP 对偶性，对偶与原问题的最优值相等，即最大流与最小割的值相等。

(a) 算法：构造一个有 \(m+n+2\) 个节点的二部图。将其中两个节点标为“源点（source）”和“汇点（sink）”，将 \(m\) 个节点标为供应商，\(n\) 个节点标为采购方。创建如下边：

• 从源点到供应商 \(i\) 连一条容量为 \(s[i]\) 的边。

• 对 \(L\) 中的每个配对 \((i, j)\)，从供应商 \(i\) 到采购方 \(j\) 连一条容量为无穷大（infinite）的边。

• 从采购方 \(j\) 到汇点连一条容量为 \(b[j]\) 的边。

然后将该图输入网络流求解器，取最大流的值作为最多可售出的产品数。

正确性证明：我们断言最大流的值恰好是可进行的最大交易量。为此，证明一个产品售卖策略恰好对应于该图中的一个流，反之亦然。

对任意流，令 \(x_{i,j}\) 为从供应商 \(i\) 的节点流向采购方 \(j\) 的节点的流量。则一个产品售卖策略恰好从供应商 \(i\) 卖给采购方 \(j\) 共 \(x_{i,j}\) 件产品。这是一个可行策略，因为流出供应商 \(i\) 节点的流量已由源点到该节点的边容量限制在 \(s[i]\) 之内，采购方同理。反过来，任意可行售卖策略也导出一个同值的可行流。

(b) 定义变量 \(x_{i,j}\)，表示从供应商 \(i\) 取走并卖给采购方 \(j\) 的产品数量。则有如下线性规划：

\[ \max \quad \sum_{i=1}^{m}\sum_{j=1}^{n} x_{i,j} \]

满足

\[ \begin{cases} \sum_{i=1}^{m} x_{ij'} \le b[j'], & \forall j' \in [1, n] \\ \sum_{j=1}^{n} x_{i'j} \le s[i'], & \forall i' \in [1, m] \\ x_{ij} = 0, & \forall (i, j) \notin L \\ x_{ij} \ge 0, & \forall (i, j) \end{cases} \]

该 LP 有 \(mn\) 个变量和 \(O(mn)\) 个线性不等式，因此可在关于 \(m, n\) 的多项式时间内求解。

(c) 网络流更好。线性规划不保证找到整数解（即使整数解存在），因此 (b) 的方法可能给出涉及售卖非整数件产品的解。相反，由于 (a) 中图的边容量均为整数，Ford-Fulkerson 最大流算法将找到整数解。因此最大流是更好的选择，因为该建模方式下存在能找到整数解的算法。