算法导论29 Problems 答案

29-1

a

假设现在存在一个标准型线性规划的算法LP-SOLVER-A(A, b, c)（其中\(\mathbf{A,b}\)表示约束，\(\mathbf{c}\)表示目标函数对应的向量，最大化\(\mathbf{c}^T\mathbf{x}\)的值），那么按照定理29.5，这个算法无非就返回\(3\)种结果：

1. 一个达到最优目标值的向量\(\mathbf{x}\)。
2. "unbounded"，即无界。
3. "infeasible"，即这个约束不可行。

那么线性不等式可行性问题检测算法LINEAR-INEQUALITY-FEASIBILITY用于检测标准型线性不等式可行性，只需要调用LP-SOLVER-A作为子程序即可。更具体的过程如下给出：

LINEAR-INEQUALITY-FEASIBILITY(A, b, m, n):
  let c[1 : n] be a new array
  sol = LP-SOLVE-A(A, b, c)
  if sol != "infeasible"
    return sol
  return NIL

这个过程用到的变量和约束的个数分是\(n,m\)，即它们本身。

b

如果一个标准型线性规划\(L\)存在一个有限最优解（最大值），那么其对偶问题也存在一个有限最优解（最小值）。如果我们令这个最大值和最小值相等，再交由LINEAR-INEQUALITY-FEASIBILITY-A求出一个可行解即可。

更具体地说，线性规划\(L\)可行当且仅当下面关于\(\mathbf{x,y}\)的线性不等式是否可行：

\(\begin{aligned} \mathbf{A}\mathbf{x}&\le\mathbf{b}\\ \mathbf{A}^T\mathbf{y}&\ge\mathbf{c}\\ \mathbf{c}^T\mathbf{x}&=\mathbf{b}^T\mathbf{y}\\ \mathbf{x}&\ge 0\\ \mathbf{y}&\ge 0\\ \end{aligned}\)

如果\(L\)是无界的，那么上面的线性不等式同样是不可行的。因此，我们下一步只需要判断\(L\)是否为可行，从而区分出无界和不可行这两种情况。只需要进行两次判断以区分这\(3\)种情况即可。更具体的情况由LP-SOLVE给出，假定LINEAR-INEQUALITY-FEASIBILITY-A是用于求解标准型线性不等式可行性的算法。最终求解线性规划算法由LP-SOLVE给出。

将上面的线性

LP-SOLVE(A, b, c, m, n)
  sol1 = LINEAR-INEQUALITY-FEASIBILITY-A(A, b, m, n)
  if sol1 == NIL
    return "infeasible"
  let A'[2 * n + 2 * m + 2, n + m] be a new table by 0
  let b'[2 * n + 2 * m + 2] be a new array by 0
  for i = 1 to m
    for j = 1 to n
      A'[i, j] = A[i, j]
      A'[m + j][n + i] = A[i, j]
  for i = 1 to m
    A[m + n + 1][n + i] = -b[i]
    A[m + n + 2][n + i] = b[i]
  for j = 1 to n
    A[m + n + 1][j] = c[j]
    A[m + n + 2][j] = -c[j]
  for k = 1 to m + n
    A[m + n + 2 + k][k] = -1
  for i = 1 to m
    b'[i] = b[i]
  for j = 1 to n
    b'[m + i] = c[j]
  sol2 = LINEAR-INEQUALITY-FEASIBILITY-A(A, b, 2 * n + 2 * m + 2, n + m)
  if sol2 == NIL
    return "unbounded"
  else
    return sol2

对上面的线性不等式标准化后，将会有\(2n+2m+2\)条不等式，\(n+m\)个变量，它们仍然是\(n\)和\(m\)的多项式。

29-2

a

该线性规划\(L\)给出的最优可行解为\(\mathbf{x}^{\ast}=(x_1,x_2,x_3)=(8,4,0)\)，对于其对偶线性规划，其最优可行解为\(\mathbf{y}^{\ast}=(y_1,y_2,y_3)=(0,1/6,2/3)\)。令\(\mathbf{A}\)表示原约束的系数矩阵，可以知道，\(\mathbf{Ax}^{\ast}=(12,24,36)^T,\mathbf{A}^T\mathbf{y}=(3,1,13/6)^T\)。将\(\mathbf{A}^T\mathbf{y^{\ast}}\)和\(\mathbf{x}^{\ast}\)以及\(\mathbf{Ax}\)和\(\mathbf{y}^{\ast}\)相对比即可完成验证。

b

必要性：假设互补松驰性成立，那么有\(\displaystyle{\sum_{j=1}^n c_j\overline{x}_j=\sum_{j=1}^n\sum_{i=1}^m a_{ij}\overline{y}_i\overline{x}_j}\)。原因在于，考虑每个\(j\in[1,n]\)，如果\(\overline{x}_j=0\)，那么\(\displaystyle{c_j\overline{x}_j=0,\overline{x}_j\cdot\sum_{i=1}^ma_{ij}\overline{y}_i=0}\)，等式\(\displaystyle{c_j\overline{x}_j=\sum_{i=1}^ma_{ij}\overline{y}_i\overline{x}_j}\)成立；如果\(\overline{x}_j=0\)不成立，那么按照互补松弛性，此时有\(\displaystyle{\sum_{i=1}^ma_{ij}\overline{y}_i=c_j}\)，等式\(\displaystyle{c_j\overline{x}_j=\sum_{i=1}^ma_{ij}\overline{y}_i\overline{x}_j}\)依旧成立。因此有\(\displaystyle{\sum_{j=1}^n c_j\overline{x}_j=\sum_{j=1}^n\sum_{i=1}^m a_{ij}\overline{y}_i\overline{x}_j}\)。

可以用类似的方法证明\(\displaystyle{\sum_{i=1}^m b_i\overline{y}_i=\sum_{i=1}^m\sum_{j=1}^n a_{ij}\overline{x}_j\overline{y}_i}\)。考虑每个\(i\in[1,m]\)，如果\(\overline{y}_i=0\)，那么\(\displaystyle{b_i\overline{y}_i=0,y_i\cdot\sum_{j=1}^n}a_{ij}\overline{x}_j=0\)，等式\(\displaystyle{b_i\overline{y}_i=\sum_{j=1}^n a_{ij}\overline{x}_j\overline{y}_i}\)成立。如果\(\overline{y}_i=0\)不成立，那么按照互补松弛性，此时有\(\displaystyle{\sum_{j=1}^n a_{ij}\overline{x}_j=b_i}\)，等式\(\displaystyle{b_i\overline{y}_i=\sum_{j=1}^n a_{ij}\overline{x}_j\overline{y}_i}\)依旧成立。因此有\(\displaystyle{\sum_{i=1}^m b_i\overline{y}_i=\sum_{i=1}^m\sum_{j=1}^n a_{ij}\overline{x}_j\overline{y}_i}\)。

由于\(\displaystyle{\sum_{j=1}^n\sum_{i=1}^m a_{ij}\overline{y}_i\overline{x}_j=\sum_{i=1}^m\sum_{j=1}^n a_{ij}\overline{x}_j\overline{y}}\)，因此有\(\displaystyle{\sum_{j=1}^n c_j\overline{x}_j=\sum_{i=1}^m b_i\overline{y}_i}\)，即\(\mathbf{c}^T\overline{\mathbf{x}}=\mathbf{b}^T\overline{\mathbf{y}}\)。

按照定理29.4，\(\overline{\mathbf{x}},\overline{\mathbf{y}}\)分别是原线性规划和对偶线性规划的最优解，原结论成立。

充分性：我们将使用反证法完成证明。假设现在\(\mathbf{x}^{\ast},\mathbf{y}^{\ast}\)分别是原线性规划和对偶线性规划的最优解。假设\(\exists i\in[1,m]\)满足\(y_i^{\ast}\neq 0\)，并且有\(\displaystyle{\sum_{j=1}^n a_{ij}x_j^{\ast}<b_i}\)，使用必要性种类似的计算过程，可以得到：

\(\begin{aligned} \sum_{j=1}^n c_jx_j^{\ast}&=\sum_{j=1}^n\sum_{i=1}^ma_{ij}y_i^{\ast}x_j^{\ast}\\ &=\sum_{i=1}^m\sum_{j=1}^n a_{ij}x_j^{\ast}y_i^{\ast}\\ &<\sum_{i=1}^m\sum_{j=1}^n b_iy_i^{\ast}\\ \end{aligned}\)

按照定理29.4，\(\overline{\mathbf{x}},\overline{\mathbf{y}}\)必定不是原线性规划和对偶线性规划的最优解，因此原结论成立。

对于另外一种情况的证明过程类似，假设\(\exists j\in[1,n]\)满足\(x_j^{\ast}\neq 0\)，并且有\(\displaystyle{\sum_{i=1}^m a_{ij}y_i^{\ast}>c_j}\)，使用必要性种类似的计算过程，可以得到：

\(\begin{aligned} \sum_{j=1}^n c_jx_j^{\ast}&<\sum_{j=1}^n\sum_{i=1}^ma_{ij}y_i^{\ast}x_j^{\ast}\\ &=\sum_{i=1}^m\sum_{j=1}^n a_{ij}x_j^{\ast}y_i^{\ast}\\ &=\sum_{i=1}^m\sum_{j=1}^n b_iy_i^{\ast}\\ \end{aligned}\)

同样的，\(\overline{\mathbf{x}},\overline{\mathbf{y}}\)必定不是原线性规划和对偶线性规划的最优解，因此原结论成立。

因此原结论成立。

c

本题使用29-2-b的结论即可直接证明。 充分性：由于\(\mathbf{x}^{\ast}\)是原线性规划的最优解，令\(\mathbf{y}^{\ast}\)是对偶线性规划的最优解，那么其必定满足条件1。按照题目29-2-b的结论，条件2和3都成立。由此充分性成立。

必要性：条件1说明了\(\overline{\mathbf{y}}\)是对偶线性规划的一个可行解，根据题目29-2-b的结论，条件2和条件3说明了构造出来的可行解\(\overline{\mathbf{x,y}}\)都是各自线性规划的最优解。由此必要性成立。

因此原结论成立。

29-3

a

证明过程和在线性规划时期，对引理29.1的证明过程完全相同。不失一般性，假设现在需要证明的整数规划是标准型。

令\(\mathbf{x}\)是原整数规划的一个可行解，\(\mathbf{y}\)是对偶整数规划的一个可行解，那么有

\(\begin{aligned} \mathbf{c}^T\overline{\mathbf{x}}&\le (\mathbf{A}^T\overline{\mathbf{y}})^T\overline{\mathbf{x}}\\ &=\overline{\mathbf{y}}^T\mathbf{A}\overline{\mathbf{x}}\\ &\le\overline{\mathbf{y}}^T\mathbf{b} \end{aligned}\)

因此原结论成立。

b

考虑如下单个变量\(x\)的标准型整数规划：

\(\begin{aligned} \text{maximize}&& x\\ \text{subject to}& \\ &&x&\le\dfrac{1}{2}\\ &&x&\ge 0 \end{aligned}\)

可以发现其最优可行解只有\(x=0\)，目标函数值为\(0\)。

那么其对偶整数规划为：

\(\begin{aligned} \text{mimimize}&& \dfrac{1}{2}y\\ \text{subject to}& \\ &&y&\ge 1\\ &&y&\ge 0 \end{aligned}\)

可以发现其最优可行解为\(y=1\)，目标函数值为\(\dfrac{1}{2}\)。

由于它们的最优解不相同，因此整数规划不满足对偶性。

c

不失一般性，假设现在需要证明的整数规划是标准型。

令\(L_I\)是一个标准型整数规划，\(L\)是\(L_I\)除去整数约束后所得到的线性规划，\(L_I^D\)是\(L_I\)的对偶整数规划，\(L^D\)是\(L\)的对偶线性规划。那么\(P,D\)分别是\(L,L^D\)的目标函数值。按照定理29.4，有\(P=D\)。

由于\(L_I\)是\(L\)添加上了整数约束而来，因此\(L_I\)的可行域必定是\(L\)的可行域的子集。这意味着在\(L\)中的最优解必定不劣于\(L_I\)中的最优解，因此有\(IP\le P\)；类似的，在\(L^D\)中的最优解必定不劣于\(L^D_I\)中的最优解，因此有\(ID\ge D\)。

最终有等式\(IP\le P=D\le ID\)。

29-4

这里的证明参考了这篇文章。

首先列出原始Farkas引理：

Farkas引理

给定\(M\in\mathbb{R}^{(m+1)\times n},g\in\mathbb{R}^{m+1}\)，如下两种陈述只有一种成立：

1. \(\exists \mathbf{v}\in \mathbb{R}^{n},\mathbf{Mv=g},\mathbf{v}\ge \mathbf{0}\)
2. \(\exists \mathbf{w}\in \mathbb{R}^{m+1},\mathbf{M}^T\mathbf{w}\ge \mathbf{0},\mathbf{g}^T\mathbf{w}<0\)

---

接下来证明题目中给定的变种Farkas引理。第一步则是使用反证法证明至多只有一个陈述成立。假设这两个陈述都成立，那么我们针对\(\mathbf{v,w}\)的存在性，可以列出：

\(\begin{aligned} \mathbf{Mv}&\le \mathbf{g}\\ \mathbf{w}^T\mathbf{M}&=\mathbf{0}\\ \mathbf{w}^T\mathbf{g}&<\mathbf{0} \end{aligned}\)

对第一条不等式左乘上一个恒非负的向量\(\mathbf{w^T}\)，得到\(\mathbf{w}^T\mathbf{Mv}\le \mathbf{w}^T\mathbf{g}\)，即得到\(\mathbf{w}^T\mathbf{g}=\mathbf{0}\)，和第三条不等式矛盾，因此这两个陈述至多只有一个成立。

接下来证明第2个陈述和如下第3个陈述是等价的：

3. \(\exists \mathbf{w}\in \mathbb{R}^{m+1}\)，使得\(\mathbf{w}\ge \mathbf{0},\mathbf{M}^T\mathbf{w}=0,\mathbf{w}^T\mathbf{g}=-1\)。

必要性显然成立，因为\(\mathbf{w}^T\mathbf{g}=-1<0\)，从而第2个陈述也是成立的。接下来证明充分性，令\(\mathbf{w'}=-\dfrac{1}{\mathbf{w}^T\mathbf{g}}\cdot w\)，那么由于\(-\dfrac{1}{\mathbf{w}^T\mathbf{g}}<0\)，因此\(\mathbf{w'}\ge 0\)仍然成立；\(\mathbf{w'}^T\mathbf{g}=\dfrac{1}{\mathbf{w}^T\mathbf{g}}\cdot(\mathbf{w}^T\mathbf{g})=-1\)；此外，\(\mathbf{w'}^T\mathbf{M}=-\dfrac{1}{\mathbf{w}^T\mathbf{g}}\cdot (\mathbf{w}^T\mathbf{M})=0\)，最终\(\mathbf{w'}\)的存在说明充分性成立。由此，第2个陈述和第3个陈述等价。

假设现在第2个陈述不成立，那么第3个陈述也不成立。那么可以将\(\mathbf{M}^T\mathbf{w}=\mathbf{0},\mathbf{g}^T\mathbf{w}=-1\)重写成\(\mathbf{A}=(\mathbf{M},\mathbf{g})^T,\mathbf{b}=(0,0,\dots,0,-1)^T\)。

由于第3个陈述不成立，这意味着\(\nexists \mathbf{x}\in\mathbb{R}^{m+1},\mathbf{x}\ge 0\)使得\(\mathbf{Ax=b}\)。也就是说，这时不满足原始Farkas引理的第1个陈述，那么这意味着原始Farkas引理第2个陈述必须成立，因此通过这条陈述，给出了\(\exists \mathbf{y}\in\mathbb{R}^{n+1},\mathbf{A}^T\mathbf{y}\ge 0,\mathbf{b}^T\mathbf{y}<0\)。

令\(\mathbf{y}=\begin{pmatrix}\mathbf{z}\\\lambda\end{pmatrix}\)，其中\(\mathbf{z}\in \mathbb{R}^n,\lambda\in \mathbb{R}\)。由于\(\mathbf{b}^T\)前\(n\)个分量都是\(0\)，因此\(\mathbf{b}^T\mathbf{y}=-\lambda<0\)，因此得到\(\lambda>0\)。\(\mathbf{A}^T\mathbf{y}\ge 0\)意味着\(\begin{pmatrix}\mathbf{M}&\mathbf{g}\end{pmatrix}\begin{pmatrix}\mathbf{z}\\\lambda\end{pmatrix}\ge 0\)，这给出了\(\mathbf{Mz}+\lambda \mathbf{g}\ge 0\)，即\(\mathbf{M}(-\mathbf{z}/\lambda)\le g\)。向量\((-\mathbf{z}/\lambda)\)的存在证明了变种Farkas引理的第1条陈述是正确的，因此原结论成立。

29-5

a

由于删除了一些约束，因此这个问题的线性规划可以从最小费用流问题转化而来：

\(\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} &&\forall u\in V \end{aligned}\)

b

由于花费函数\(a(u,v)>0\)，并且线性规划的目标函数是最小化费用。因此线性规划的最优方案将是：不使用任何边进行流动，那么这样将不会产生任何花费。因此，这个流是的大小为\(0\)。

c

不失一般性，我们可以删除\(E\)中\((t,s)\)的边，这不会减少最大流的值。

我们构造图\(G'=(V',E')\)，其中\(V'=V,E'=E\cup\{(t,s)\}\)。令\(a(t,s)=-1,c(t,s)=+\infty\)，对于\(\forall(u,v)\in E\)，都有\(a(u,v)=0,c(u,v)\)为原最大流问题中，有向边\((u,v)\)的容量。考虑新构造后的图\(G'\)，以及对应的容量函数\(c\)和费用函数\(a\)，那么最大流问题就相当于解决如此一个最小费用流通问题。

在\(G'\)中，如果一个“流”从\(t\)流动到\(s\)，那么将会有一个真正的流从\(s\)流动到\(t\)。并且由于\(a(t,s)=-1\)，因此线性规划算法将会“激励”尽量多的流产生，并且产生一个真正的流并不会添加任何代价。由于\(c(t,s)=+\infty\)，因此这将不会限制从\(s\)到\(t\)的流产生。

最终，舍去变量\(f_{ts}\)的值（或者是让其值为\(0\)），那么计算出的一组解\(f\)为原图\(G\)上的最大流。

d

令\(\displaystyle{A=1+\sum_{(u,v)\in E}a(u,v)}\)，其中\(a(u,v)\)是从\(u\)到\(v\)的距离。也就是说，\(M\)是一个足够大的数，但并非是无穷大。

同样的，不失一般性，我们可以删除\(E\)中\(s\)的所有入边，这不会增加从\(s\)到任意节点的最短路径。

可以构造图\(G'=(V',E')\)，其中\(V'=V,E'=E\cup\{(v,s):v\in V-\{s\}\}\)。\(\forall (v,s)\in E'\)，令\(c(v,s)=1,a(v,s)=-A\)。\(\forall (u,v)\in E,c(u,v)=+\infty,a(u,v)\)为原最短路问题中，从\(u\)到\(v\)的距离边权。考虑新构造后的图\(G'\)，以及对应的容量函数\(c\)和费用函数\(a\)，那么最短路问题就相当于解决如此一个最小费用流通问题。

在\(G'\)中，任意一条简单路径的长度都小于\(A\)。因此在一个最小费用流通问题中，使用边\((v,s)\in E'\)一定是更优的。对于任意\(v\in V-\{s\}\)，这意味着必定有一个流从\(s\)到达\(v\)，并且这个流的费用是最小的，这时从\(s\)到\(v\)的这个流恰好就对应了原问题的最短路径。

最终，舍去所有变量\(f_{vs}(s\in V-\{s\})\)（或者是让其值为\(0\)）。对于任意节点\(v\in V-\{s\}\)，求出从\(s\)到\(v\)的最短路径，需要从\(v\)开始，逐渐向前移动，找到这个流的起点即可。最终处理出来的流就是对应最短路径。