返回题库

线性规划基

Linear Programming Basis and Reformulation

专题
Algorithmic Programming / 算法编程
难度
L4

题目详情

考虑线性规划

max⁡  x4+x5+x6+x7s.t.Ax=b,  x≥0,\max\; x_4 + x_5 + x_6 + x_7 \quad \text{s.t.} \quad Ax = b,\; x \ge 0,

其中

A=(1−10−1−100001100000021100200101),b=(−2243),A = \begin{pmatrix} 1 & -1 & 0 & -1 & -1 & 0 & 0 \\ 0 & 0 & 1 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 2 & 1 & 1 & 0 \\ 0 & 2 & 0 & 0 & 1 & 0 & 1 \end{pmatrix}, \quad b = \begin{pmatrix} -2 \\ 2 \\ 4 \\ 3 \end{pmatrix},

以及点 v=(0,0,0,2,0,0,3)Tv = (0, 0, 0, 2, 0, 0, 3)^T。

(a) vv 是否是该线性规划的一个基本可行解（basic feasible solution）？

(b) B={4,5,6,7}B = \{4,5,6,7\} 是否是一个可行基（feasible basis）？

(c) 将该 LP 重写为一个（非等式形式的）只涉及 x1,x2,x3x_1,x_2,x_3 的 LP。（提示：用 x1,x2,x3x_1,x_2,x_3 参数化集合 {x∈R7:Ax=b}\{x\in\mathbb{R}^7: Ax=b\}。）

(d) 用 (c) 的表述证明 vv 是该 LP 的最优解。

英文原题

Consider the objective

max⁡x4+x5+x6+x7s.t.Ax=b and x≥0\max x_4 + x_5 + x_6 + x_7 \quad \text{s.t.} \quad Ax = b \text{ and } x \geq 0

where

A=(1−10−1−100001100000021100200101),b=(−2243)A = \begin{pmatrix} 1 & -1 & 0 & -1 & -1 & 0 & 0 \\ 0 & 0 & 1 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 2 & 1 & 1 & 0 \\ 0 & 2 & 0 & 0 & 1 & 0 & 1 \end{pmatrix}, \quad b = \begin{pmatrix} -2 \\ 2 \\ 4 \\ 3 \end{pmatrix}

and the point v=(0,0,0,2,0,0,3)Tv = (0, 0, 0, 2, 0, 0, 3)^T.

(a) Is vv a basic feasible solution to this linear program?

(b) Is B={4,5,6,7}B = \{4, 5, 6, 7\} a feasible basis?

(c) Reformulate this LP as an LP (not in equational form) involving only x1,x2,x3x_1, x_2, x_3. (Hint: parametrize {x∈R7:Ax=b}\{x \in \mathbb{R}^7 : Ax = b\} using the variables x1,x2,x3x_1, x_2, x_3 as parameters.)

(d) Use your formulation in (c) to show that vv is an optimal solution to this LP.

解析

(a) 先验算可行性：代入 vv 有

  • 第 1 行：−x4−x5=−2-x_4-x_5=-2 成立；
  • 第 2 行：x3+x4=2x_3+x_4=2 成立；
  • 第 3 行：2x4+x5+x6=42x_4+x_5+x_6=4 成立；
  • 第 4 行：2x2+x5+x7=32x_2+x_5+x_7=3 成立；

且 v≥0v\ge 0，所以 vv 可行。

再看是否为 BFS：只需存在一个 4 列组成的可逆子矩阵作为基，使得非基变量为 0 时得到 vv。下题 (b) 给出的 B={4,5,6,7}B=\{4,5,6,7\} 正好做到，因此 vv 是一个基本可行解（并且是退化的，因为 x5=x6=0x_5=x_6=0 但可作为基变量）。

(b) 取基变量 (x4,x5,x6,x7)(x_4,x_5,x_6,x_7)，令非基变量 x1=x2=x3=0x_1=x_2=x_3=0，由 Ax=bAx=b 解得

  • 第 2 行：x4=2x_4=2；
  • 第 1 行：−x4−x5=−2⇒x5=0-x_4-x_5=-2\Rightarrow x_5=0；
  • 第 3 行：2x4+x5+x6=4⇒x6=02x_4+x_5+x_6=4\Rightarrow x_6=0；
  • 第 4 行：x5+x7=3⇒x7=3x_5+x_7=3\Rightarrow x_7=3。

得到 xB=(2,0,0,3)≥0x_B=(2,0,0,3)\ge 0，故 BB 是可行基。

(c) 用 x1,x2,x3x_1,x_2,x_3 参数化。由等式组：

  • 从 x3+x4=2x_3+x_4=2 得 x4=2−x3x_4=2-x_3；
  • 从第 1 行 x1−x2−x4−x5=−2x_1-x_2-x_4-x_5=-2 得 x5=x1−x2+x3x_5=x_1-x_2+x_3；
  • 从第 3 行 2x4+x5+x6=42x_4+x_5+x_6=4 得 x6=x3−x1+x2x_6=x_3-x_1+x_2；
  • 从第 4 行 2x2+x5+x7=32x_2+x_5+x_7=3 得 x7=3−x1−x2−x3x_7=3-x_1-x_2-x_3。

于是原目标函数

max⁡(x4+x5+x6+x7)=max⁡(5−x1−x2),\max (x_4+x_5+x_6+x_7)=\max (5-x_1-x_2),

并且约束 x≥0x\ge 0 等价于以下关于 x1,x2,x3x_1,x_2,x_3 的不等式：

x1≥0,  x2≥0,  x3≥0,  x3≤2,x1−x2+x3≥0,x3−x1+x2≥0,x1+x2+x3≤3.\begin{aligned} &x_1\ge 0,\;x_2\ge 0,\;x_3\ge 0,\;x_3\le 2,\\ &x_1-x_2+x_3\ge 0,\\ &x_3-x_1+x_2\ge 0,\\ &x_1+x_2+x_3\le 3. \end{aligned}

这就是只含 x1,x2,x3x_1,x_2,x_3 的 LP。

(d) 在 (c) 中，目标是最大化 5−x1−x25-x_1-x_2。由于 x1,x2≥0x_1,x_2\ge 0，故

5−x1−x2≤5.5-x_1-x_2\le 5.

取 x1=x2=0x_1=x_2=0 且例如 x3=0x_3=0（满足所有约束）即可达到目标值 5。

当 (x1,x2,x3)=(0,0,0)(x_1,x_2,x_3)=(0,0,0) 时，对应

(x4,x5,x6,x7)=(2,0,0,3),(x_4,x_5,x_6,x_7)=(2,0,0,3),

即点 vv，其目标值为 2+0+0+3=52+0+0+3=5，达到上界，因此 vv 最优。

英文解析

    • (a) * * Prior calculation feasibility: Replace with vv Yes
  • Line 1: −x4−x5=−2-x_4-x_5=-2 established;
  • Line 2: x3+x4=2x_3+x_4=2 established;
  • Line 3: 2x4+x5+x6=42x_4+x_5+x_6=4 is established;
  • Line 4: 2x2+x5+x7=32x_2+x_5+x_7=3 established;

And v≥0v\ge 0, so vvworks.

Look again at whether it is BFS: it is only necessary to have a reversible submatrix consisting of 4 columns as the base, so that when the non-basic variable is 0, vv is obtained. The B={4,5,6,7}B=\{4,5,6,7\} given in question (b) below does just that, so vv is a basically feasible solution (and is degenerate, because x5=x6=0x_5=x_6=0 can be used as a base variable).

    • (b) * * Take the base variable (x4,x5,x6,x7)(x_4,x_5,x_6,x_7), so that the non-base variable x1=x2=x3=0x_1=x_2=x_3=0is solved by Ax=bAx=b
  • Line 2: x4=2x_4=2;
  • Line 1: −x4−x5=−2⇒x5=0-x_4-x_5=-2\Rightarrow x_5=0;
  • Line 3: 2x4+x5+x6=4⇒x6=02x_4+x_5+x_6=4\Rightarrow x_6=0;
  • Line 4: x5+x7=3⇒x7=3x_5+x_7=3\Rightarrow x_7=3.

You get xB=(2,0,0,3)≥0x_B=(2,0,0,3)\ge 0, so BBis a viable basis.

    • (c) * * Parameterized with x1,x2,x3x_1,x_2,x_3. By Equation Group:

-x4=2−x3x_4=2-x_3 fromx3+x4=2x_3+x_4=2;
-x5=x1−x2+x3x_5=x_1-x_2+x_3 from line 1x1−x2−x4−x5=−2x_1-x_2-x_4-x_5=-2;

  • Get x6=x3−x1+x2x_6=x_3-x_1+x_2 from line 3 2x4+x5+x6=42x_4+x_5+x_6=4;
  • Get x7=3−x1−x2−x3x_7=3-x_1-x_2-x_3 from line 4 2x2+x5+x7=32x_2+x_5+x_7=3.

So the original objective function

max⁡(x4+x5+x6+x7)=max⁡(5−x1−x2),\max (x_4+x_5+x_6+x_7)=\max (5-x_1-x_2),

and constrain x≥0x\ge 0 to be equivalent to the following inequality for x1,x2,x3x_1,x_2,x_3:

x1≥0,  x2≥0,  x3≥0,  x3≤2,x1−x2+x3≥0,x3−x1+x2≥0,x1+x2+x3≤3.\begin{aligned} &x_1\ge 0,\;x_2\ge 0,\;x_3\ge 0,\;x_3\le 2,\\ &x_1-x_2+x_3\ge 0,\\ &x_3-x_1+x_2\ge 0,\\ &x_1+x_2+x_3\le 3. \end{aligned}

This is the LP with only x1,x2,x3x_1,x_2,x_3.

    • (d) * * In (c), the goal is to maximize 5−x1−x25-x_1-x_2. As a result of x1,x2≥0x_1,x_2\ge 0,
5−x1−x2≤5.5-x_1-x_2\le 5.

Take x1=x2=0x_1=x_2=0 and for example x3=0x_3=0 (meets all constraints) to reach the target value of 5.

When (x1,x2,x3)=(0,0,0)(x_1,x_2,x_3)=(0,0,0), corresponds to

(x4,x5,x6,x7)=(2,0,0,3),(x_4,x_5,x_6,x_7)=(2,0,0,3),

That is, vv, the target value is 2+0+0+3=52+0+0+3=5, which reaches the upper limit, so vvis the best.