算法导论29.1 Exercises 答案

29.1-1

\((0,7),(1,6),(2,5)\)分别是这个线性规划的\(3\)个可行解，其目标函数值分别为\(21,16,11\)。

29.1-2

\((7,3,0),(7,4,0),(7,5,0)\)分别是这个线性规划的\(3\)个可行解，其目标函数值分别为\(35,42,49\)。

29.1-3

对第二条约束变形后，得到\(x_1+x_2\ge 5\)，这和第一条约束\(x_1+x_2\le 2\)是明显冲突的。因此，这个线性规划是不可行的。

29.1-4

考虑令\(x_1=2t,x_2=t\)，那么目标函数为\(t\)。当\(t\ge 0\)时，第一条约束化成\(-3t\le -1\)，第二条约束化成\(-4t\le -2\)，其余约束化成\(t\ge 0\)。哪怕\(t\)趋向于正无穷，这些约束仍然是成立的。由于需要最大化目标值，那么目标值可以到达正无穷，因此这个线性规划是无界的。

29.1-5

构造出的线性规划问题如下：

\(\begin{aligned} \text{maximize}&& x_1+x_2\\ \text{subject to}& \\ &&x_1+2x_2&\le 4\\ &&2x_1+x_2&\le 5 \end{aligned}\)

虽然可行解是无界的，但是最优解只有一个：\((2,1)\)，其目标值为\(3\)。

29.1-6

a

只需要将等式约束\(\displaystyle{\sum_{j=1}^n a_{ij}x_j=b_j}\)替换成如下两个约束即可：

\(\begin{aligned} \sum_{j=1}^n a_{ij}x_j &\le b_i\\ \sum_{j=1}^n a_{ij}x_j &\ge b_i \end{aligned}\)

b

将不等式约束\(\displaystyle{\sum_{j=1}^n a_{ij}x_j\le b_j}\)替换成如下两个约束即可：

\(\begin{aligned} \sum_{j=1}^n a_{ij}x_j &= b_i-s\\ s&\ge 0 \end{aligned}\)

29.1-7

如果当前是对某个目标函数\(f(x)\)最小化，那么其等价的最大化线性约束就是对目标函数\(g(x)=-f(x)\)最大化。

令\(S\)是第一个线性规划的可行域，\(x_0\in S\)是其一个最优解。这意味着\(\forall x\in S\)，都有\(f(x)\ge f(x_0)\)。代入\(g(x)=-f(x)\)，那么有\(f\forall x \in S\)，均有\(g(x)\le g(x_0)\)。因此，原线性规划和新线性规划是等价的。

29.1-8

还需要添加如下约束，以确保真实投票人数不会超过人口数：

\(\begin{aligned} -2x_1+8x_2+0x_3+10x_4&\le 100\\ 5x_1+2x_2+0x_3+0x_4&\le 200\\ 3x_1-5x_2+10x_3-2x_4&\le 50\\ \end{aligned}\)