CS170 Efficient Algorithms and Intractable Problems HW8

课程主页：

https://cs170.org/

https://inst.eecs.berkeley.edu/~cs170/fa18/

课程视频：

https://www.bilibili.com/video/BV1wK411g7ck

参考资料：

https://people.eecs.berkeley.edu/~daw/teaching/cs170-s03/Notes/lecture15.pdf

https://piazza.com/class_profile/get_resource/honxzoabz711ew/hvep5i3vb292gs

这次回顾HW8。

2. Jeweler

(a)

假设生成$x$个项链，$y$个戒指，那么线性规划问题为

$$\begin{aligned} \max\quad &60 x + 30y \\ & 4x +y\le 80\\ & 2x + 3y \le 90\\ & x \ge 0\\ &y \ge 0 \end{aligned}$$

顶点以及对应的利润为（这里假设项链的利润为$C$）

$x$	$y$	利润
0	80	2400
0	30	900
0	0	0
20	0	20C
45	0	45C
15	20	15C+600

(b)

需要考虑的顶点只有

$x$	$y$	利润
0	80	2400
45	0	45C
15	20	15C+600

$(0,80)$为最优顶点当且仅当

$$\begin{aligned} 2400&\ge 45C\\ 2400&\ge 15C+600\\ C&\le \frac{160}{3} \end{aligned}$$

$(45,0)$为最优顶点当且仅当

$$\begin{aligned} 2400&\le 45C\\ 15C+600&\le 45C\\ C&\ge \frac{160}{3} \end{aligned}$$

$(15,20)$为最优顶点当且仅当

$$\begin{aligned} 15C+600&\ge 2400\\ 15C+600&\ge 45C\\ \frac{160}{3}\le C&\le 20,无解 \end{aligned}$$

3. Modeling: Tricks of the Trade

(a)

设

$$\begin{aligned} z_i &= y_i -(a+bx_i)\\ z_i &= z_i^{+}- z_i^{-}\\ |z_i|&= z_i^{+} + z_i^- \end{aligned}$$

那么问题可以描述为

$$\begin{aligned} \max \quad &\sum_{i=1}^n (z_i^++ z_i^-)\\ & z_i^{+}- z_i^{-} =y_i-(a+bx_i)\\ & z_i^{+}\ge 0\\ &z_i^{-}\ge 0\\ &i=1,\ldots, n \end{aligned}$$

(b)

令

$$z=\max _{i=1 \ldots n}\left|y_{i}-\left(a+b x_{i}\right)\right|$$

那么

$$z\ge \left|y_{i}-\left(a+b x_{i}\right)\right|, i=1,\ldots,n$$

结合(a)可得

$$\begin{aligned} \min \quad &z\\ & z_i^{+}- z_i^{-} =y_i-(a+bx_i)\\ & z_i^{+}\ge 0\\ &z_i^{-}\ge 0\\ &z \ge z_i^{+}+ z_i^{-}\\ &i=1,\ldots, n \end{aligned}$$

4. Repairing a Flow

参考了官方解答。

假设修改的边为$e=(u,v)$，根据最大流构造剩余网络$G^f=(V,E^{f})$，那么$(v, u)\in G^f$并且$(u,v)\not\in G^f$，现在利用DFS找到$u\to s$的路径以及$t\to v$的路径，合并到一起找到一条$t\to s$的路径，对于路径上除了$(v,u)$的每条边$(i,j)$，更新

$$\begin{aligned} f_{ij}&=f_{ij}-1\\ f_{ji}&=f_{ji}+1 \end{aligned}$$

然后查找是否存在$s\to t$的路径，如果存在，最大流则不变，否则最大流减少1。

5. Generalized Max Flow

问题描述：

$$\begin{aligned} \max\quad& \sum_{i=1}^k \sum_{(s_i, u) \in E} f_{s_i u}\\ &\sum_{(w, u) \in E} f_{w u}^{(i)}=\sum_{(u, z) \in E} f_{u z}^{(i)},u\neq s_i, t_i \\ &\sum_{i=1}^k f^{(i)}_e \le c_e \\ &\sum_{(s_i, u) \in E} f_{s_i u} \ge d_i\\ \end{aligned}$$

6. Reductions Among Flows

(a)

构造新图$G’$，其中包含$G$中任意节点$v$；另一方面，对$G$中任意一个节点$v$，构造$v’$，使得对于任意$(v,u)\in G$，都有$(v’,u)\in G’$，并且满足

$$w(v',u)=w(v,u)$$

另一方面，新增一条边$(v,v’)$，满足

$$w(v,v') = c_v$$

由于$v$流入的流量总和必然等于流出的流量，而$G’$中和$v$相连的唯一顶点为$v’$，该边上的流量必然小于等于容量，即

$$\sum_{u:(u, v) \in E} f_{u v} \leq c_{v}$$

(b)

增加节点$s$，其中

$$w(s,s_i)=\sum_{(s_i,s_j)\in E} w(s_i, s_j)$$

这样可以转换为单源的问题。

7. Provably Optimal

对偶问题为

$$\begin{aligned} \min\quad & y_1 + y_2\\ & y_1 \ge 1\\ & -y_1 +2y_2 \ge 0\\ & -y_2 \ge -2\\ & y_1 ,y_2\ge 0 \end{aligned}$$

注意约束条件为

$$\begin{aligned} y_1 &\ge 1\\ y_1 &\le 2y_2 \\ y_2 &\le 2\\ y_2&\ge 0 \end{aligned}$$

所以可以推出

$$y_1\ge 1, y_2 \ge \frac 1 2$$

所以最优解为

$$1+\frac 1 2 =\frac 3 2$$

8. Bimetallism

1

设生成第$i$种alloy的数量为$x_i$，那么可以将问题建模为

$$\begin{aligned} \max\quad & \sum_{i=1}^n p_ix_i\\ & \sum_{i=1}^n g_i x_i\le G \\ & \sum_{i=1}^n s_i x_i\le S \end{aligned}$$

2

对偶问题

$$\begin{aligned} \min\quad & Gy_1 + S y_2\\ & g_i y_1 + s_i y_2 \ge p_i, i=1,\ldots,n \end{aligned}$$

问题解释：

$y_1,y_2$解释为金银的价格，我们的目标是在第$i$种alloy的成本大于等于$p_i$时，最小化总成本$Gy_1 +Sy_2$。