算法导论29.3 Exercises 答案

发表于 分类于 阅读次数： 本文字数： 4.5k 阅读时长 ≈ 4 分钟

29.3-1

该线性规划的对偶线性规划为：

\(\begin{aligned} \text{maximize}&& 50y_1+100y_2+25y_3\\ \text{subject to}& \\ &&-2y_1+5y_2+3y_3&\le 1\\ &&8y_1+2y_2-5y_3&\le 1\\ &&0y_1+0y_2+10y_3&\le 1\\ &&10y_1+0y_2-2y_3&\le 1\\ &&y_1,y_2,y_3&\ge 0 \end{aligned}\)

29.3-2

整个过程分成两个步骤进行：

  1. 是将所有约束的比较符号的方向统一化。不失一般性，如果现在需要将除去非负约束以外的\(\ge\)的约束转化成\(\le\)的约束，那么只需要对原约束两侧乘上\(-1\)，并将比较符号反向即可。

  2. 假设经第1个步骤处理后，原线性规划的目标函数为\(\mathbf{c}^T\mathbf{x}\)，并且朝某一个方向优化（最大/最小），约束是\(\mathbf{A}^T\mathbf{x}\circ \mathbf{b}\)，其中\(\circ\in\{\le,\ge\}\)。那么原线性规划的对偶线性规划的目标函数是\(\mathbf{b}^T\mathbf{y}\)，并且朝另一个方向优化（最小/最大），约束是\(\mathbf{A}^T\mathbf{y}\overline{\circ} \mathbf{c}\)，即将统一前的比较符号均取反即可。

29.3-3

我们可以给出最大流问题线性规划的标准型为：

\(\begin{aligned} \text{maximize}&& \sum_{(s,v)\in E} f_{sv}-\sum_{(v,s)\in E} f_{vs}\\ \text{subject to}& \\ &&f_{uv}&\le c(u,v) &&\forall (u,v)\in E \\ &&f_{uv}&\ge 0 &&\forall (u,v)\in E \\ &&\sum_{(u,v)\in E} f_{uv}-\sum_{(v,u)\in E} f_{vu}&\le 0 &&\forall u\in V-\{s,t\}\\ &&\sum_{(v,u)\in E} f_{vu}-\sum_{(u,v)\in E} f_{uv}&\le 0 &&\forall u\in V-\{s,t\} \end{aligned}\)

可见，令左边的系数矩阵为\(\mathbf{A}\)，其大小为\((2|V|+2|E|-4)\times |E|\)，右边的\(\mathbf{b}\)是一个\(2|V|+2|E|-4\)维的向量，其目标函数\(\mathbf{c}^T\mathbf{x}\)中的向量\(\mathbf{c}^T\)长度为\(|E|\)。因此最大流问题的对偶线性规划为

\(\begin{aligned} \text{minimize}&& \mathbf{b}^T\mathbf{y}\\ \text{subject to}& \\ &&\mathbf{A}^T\mathbf{y}&\ge\mathbf{c} \end{aligned}\)

29.3-4

我们可以给出最小费用流问题线性规划的统一符号方向后的结果为：

\(\begin{aligned} \text{minimize}&& \sum_{(u,v)\in E} a(u,v)\cdot f_{uv}\\ \text{subject to}& \\ &&f_{uv}&\le c(u,v) &&\forall (u,v)\in E \\ &&f_{uv}&\ge 0 &&\forall (u,v)\in E \\ &&\sum_{(u,v)\in E} f_{uv}-\sum_{(v,u)\in E} f_{vu}&\le 0 &&\forall u\in V-\{s,t\}\\ &&\sum_{(v,u)\in E} f_{vu}-\sum_{(u,v)\in E} f_{uv}&\le 0 &&\forall u\in V-\{s,t\}\\ &&\sum_{(s,v)\in E} f_{sv}-\sum_{(v,s)\in E} f_{vs}&\le d\\ &&\sum_{(v,s)\in E} f_{vs}-\sum_{(s,v)\in E} f_{sv}&\le -d \end{aligned}\)

可见，令左边的系数矩阵为\(\mathbf{A}\)，其大小为\((2|V|+2|E|-2)\times |E|\)，右边的\(\mathbf{b}\)是一个\(2|V|+2|E|-2\)维的向量，其目标函数\(\mathbf{c}^T\mathbf{x}\)中的向量\(\mathbf{c}^T\)长度为\(|E|\)。因此最小费用流问题的对偶线性规划为

\(\begin{aligned} \text{maximize}&& \mathbf{b}^T\mathbf{y}\\ \text{subject to}& \\ &&\mathbf{A}^T\mathbf{y}&\ge\mathbf{c} \end{aligned}\)

29.3-5

不失一般性，这里仅考虑标准型的线性规划：

\(\begin{aligned} \text{maximize}&& \mathbf{c}^T\mathbf{x}\\ \text{subject to}& \\ &&\mathbf{A}\mathbf{x}&\le\mathbf{b}\\ &&\mathbf{x}&\ge\mathbf{0} \end{aligned}\)

按照定义，其对偶线性规划为：

\(\begin{aligned} \text{minimize}&& \mathbf{b}^T\mathbf{y}\\ \text{subject to}& \\ &&\mathbf{A}^T\mathbf{y}&\ge\mathbf{c}\\ &&\mathbf{y}&\ge\mathbf{0} \end{aligned}\)

该对偶线性规划的对偶线性规划为：

\(\begin{aligned} \text{maximize}&& \mathbf{c}^T\mathbf{x'}\\ \text{subject to}& \\ &&\mathbf{A}\mathbf{x'}&\le\mathbf{b}\\ &&\mathbf{x'}&\ge\mathbf{0} \end{aligned}\)

可见，第一个线性规划和第三个线性规划的形式是完全一致的，因此一个线性规划对偶的对偶是它本身。

29.3-6

最大流问题中，推论24.5最大流的值的上界被最小割值限制着，这可以被解释成最大流问题的弱对偶。

29.3-7

本题以分类讨论为主。

对于原线性规划：

  • 当\(r>0,s<0\)时，原线性规划的可行域是\(\varnothing\)，因此它不可行。
  • 当\(r>0,s\ge 0\)时，原线性规划的可行域是\(0\le x\le s/r\)。此时目标值必定是有限的。
  • 当\(r=0,s<0\)时，原线性规划的可行域是\(\varnothing\)，因此它不可行。
  • 当\(r=0,s\ge 0\)时，原线性规划的可行域是\(x\ge 0\)。如果\(t\le0\)，那么其目标值有限，否则是无界的。
  • 当\(r<0,s<0\)时，原线性规划的可行域是\(x\ge s/r\)。如果\(t\le0\)，那么其目标值有限，否则是无界的。
  • 当\(r<0,s\ge 0\)时，原线性规划的可行域是\(x\ge 0\)。如果\(t\le0\)，那么其目标值有限，否则是无界的。

可见这个线性规划的对偶线性规划是：

\(\begin{aligned} \text{minimize}&& sy\\ \text{subject to}& \\ &&ry&\ge t\\ &&y&\ge0 \end{aligned}\)

  • 当\(r>0,t\le 0\)时，对偶线性规划的可行域是\(y\ge 0\)。如果\(s\ge 0\)，那么其目标值有限，否则是无界的。
  • 当\(r>0,t>0\)时，对偶线性规划的可行域是\(y\ge t/r\)。如果\(s\ge 0\)，那么其目标值有限，否则是无界的。
  • 当\(r=0,t\le 0\)时，对偶线性规划的可行域是\(y\ge 0\)。如果\(s\ge 0\)，那么其目标值有限，否则是无界的。
  • 当\(r=0,t> 0\)时，对偶线性规划的可行域是\(\varnothing\)，因此它不可行。
  • 当\(r<0,t\le 0\)时，对偶线性规划的可行域是\(0\le x\le t/r\)。此时目标值必定是有限的。
  • 当\(r<0,t> 0\)时，对偶线性规划的可行域是\(\varnothing\)，因此它不可行。

综上所述：

  1. 当\((r=0\land s\ge 0\land t\le 0)\lor(r>0\land r>0\land s\ge 0)\lor(r<0\land t\le 0)\)为真时，满足第一个断言。
  2. 当\((r=0\land s\ge 0\land t> 0)\lor(r<0\land t> 0)\)为真时，满足第二个断言。
  3. 当\((r=0\land s< 0\land t\le 0)\lor(r>0\land s< 0)\)为真时，满足第三个断言。
  4. 当\(r=0\land s< 0\land t> 0\)为真时，满足第四个断言。

29.3-8

如果一个线性规划无解，即不存在一个向量\(\mathbf{x}\)满足各个约束，那么说明这个标准线性规划是不可行的。

否则，必定存在一系列可行解，使得多个向量\(\mathbf{x}\)满足这些约束。如果这个线性规划没有有限的最优目标值，那么说明这个可行域必定是无界的。否则按照最优性（即要么最大，要么最小），有一个有限目标值的最优解。