课程主页:

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$个戒指,那么线性规划问题为

顶点以及对应的利润为(这里假设项链的利润为$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)$为最优顶点当且仅当

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

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

3. Modeling: Tricks of the Trade

(a)

那么问题可以描述为

(b)

那么

结合(a)可得

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)$,更新

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

5. Generalized Max Flow

问题描述:

6. Reductions Among Flows

(a)

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

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

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

(b)

增加节点$s$,其中

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

7. Provably Optimal

对偶问题为

注意约束条件为

所以可以推出

所以最优解为

8. Bimetallism

1

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

2

对偶问题

问题解释:

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