算法导论29.2 Exercises 答案
29.2-1
这个最短路问题的对应线性规划问题如下：
\(\begin{aligned} \text{maximize}&& d_x\\ \text{subject to}& \\ &&d_t&\le d_s+3\\ &&d_y&\le d_s+5\\ &&d_x&\le d_t+6\\ &&d_y&\le d_t+2\\ &&d_z&\le d_x+2\\ &&d_t&\le d_y+1\\ &&d_x&\le d_y+4\\ &&d_z&\le d_y+6\\ &&d_s&\le d_z+3\\ &&d_x&\le d_z+7\\ &&d_s&=0 \end{aligned}\)
29.2-2
这和第29.2章介绍的线性规划系统类似，如下给出：
\(\begin{aligned} \text{maximize}&& \sum_{v\in V} d_v\\ \text{subject to}& \\ &&d_v&\le d_u+w(u,v) &&\forall (u,v)\in E \\ &&d_s&=0 \end{aligned}\)
两条约束和29.2所给出的约束相同，区别在于目标函数。由于目前是希望最大化所有变量\(d_v\)，但是最短路径的松弛性质仍然保持，因此这时的最优解对应了\(s\)到所有节点的最短路径长度。
29.2-3
这个最大流问题的对应线性规划问题如下：
\(\begin{aligned} \text{maximize}&& f_{sv_1}+f_{sv_2}\\ \text{subject to}& \\ &&f_{uv}&\ge 0 &&\forall (u,v)\in E \\ &&f_{sv_1}&\le 16\\ &&f_{sv_2}&\le 14\\ &&f_{v_1v_3}&\le 12\\ &&f_{v_2v_1}&\le 4\\ &&f_{v_2v_4}&\le 14\\ &&f_{v_3v_2}&\le 9\\ &&f_{v_3v_t}&\le 20\\ &&f_{v_4v_3}&\le 7\\ &&f_{v_4t}&\le 4\\ &&f_{sv_1}+f_{v_2v_1}&= f_{v_1v_3}\\ &&f_{sv_2}+f_{v_3v_2}&= f_{v_2v_1}+f_{v_2v_4}\\ &&f_{v_1v_3}+f_{v_4v_3}&= f_{v_3v_2}+f_{v_3t}\\ &&f_{v_2v_4}&= f_{v_4v_3}+f_{v_4t}\\ \end{aligned}\)
29.2-4
这里使用题目24.1-4的结果：
\(\begin{aligned} \text{maximize}&& \sum_{(s,v)\in E} f_{sv}-\sum_{(v,s)\in E} f_{vs}\\ \text{subject to}& \\ &&f_{uv}&\ge 0 &&\forall (u,v)\in E \\ &&f_{uv}&\le c(u,v) &&\forall (u,v)\in E \\ &&\sum_{(u,v)\in E} f_{uv}&=\sum_{(v,u)\in E} f_{vu} &&\forall u\in V-\{s,t\} \end{aligned}\)
可见，这里一共有\(2|E|+|V|-2=O(V+E)\)条约束。
29.2-5
令二分图\(G=(V,E),V=L\cup R\)。使用第24.3章的结论，我们可以将这个问题转化成最大流问题进行解答：令\(V'=V\cup\{s,t\},E'=\{(s,l):l\in L\}\cup\{(r,t):r\in R\}\cup E\)，对于\(\forall (u,v)\in E'\)，都有\(c(u,v)=1\)。那么图\(G\)的二分图最大匹配数量相当于是图\(G'=(V',E')\)中从\(s\)到\(t\)的最大流。这个线性规划将使用题目29.2-4的结论，如下：
\(\begin{aligned} \text{maximize}&& \sum_{l\in L}f_{sl} \\ \text{subject to}& \\ &&f_{uv}&\ge 0 &&\forall (u,v)\in E' \\ &&f_{uv}&\le c(u,v) &&\forall (u,v)\in E' \\ &&\sum_{(u,v)\in E'} f_{uv}&=\sum_{(v,u)\in E'} f_{vu} &&\forall u\in V \end{aligned}\)
29.2-6
这意味着对于任意一条路径\(p_i\)，如果其经过边\((u,v)\)，那么这条路径就需要受到这条边容量的限制。因此，对于路径\(P\)，我们可以写出如下线性规划：
\(\begin{aligned} \text{maximize}&& \sum_{i=1}^px_i \\ \text{subject to}& \\ &&x_{i}&\ge 0 &&\forall i\in[1,p] \\ &&\sum_{1\le i\le p,(u,v)\in P_i}x_i&\le c(u,v) &&\forall (u,v)\in E \\ \end{aligned}\)
如果\(G\)是一个有\(\dfrac{|V|(|V|-1)}{2}\)条边的有向无环图，那么\(p\)的值可以达到\(2^{|V|-2}\)。因此使用这个线性规划求解最大流问题是不明智的，因为约束的大小和数量都太多（呈指数级数量）。
29.2-7
只需要对多商品流问题的目标函数进行修改即可。修改后的线性规划问题如下：
\(\begin{aligned} \text{minimize}&& \sum_{(u,v)\in E}a(u,v)\cdot\left(\sum_{i=1}^k f_{i,u,v}\right) \\ \text{subject to}& \\ &&\sum_{i=1}^kf_{i,u,v}&\le c(u,v) &&\forall (u,v)\in E\\ &&\sum_{(u,v)\in E}f_{i,u,v}-\sum_{(v,u)\in E}f_{i,v,u}&= 0 &&\forall i\in[1,k],\forall u\in V-\{s_i,t_i\} \\ &&\sum_{(s_i,v)\in E}f_{i,s_i,v}-\sum_{(v,s_i)\in E}f_{i,v,s_i}&= d_i &&\forall i\in[1,k]\\ &&f_{i,u,v}&\ge 0 &&\forall i\in[1,k],\forall (u,v)\in E\\ \end{aligned}\)