算法导论随笔(十五)：线性规划与单纯形算法（上篇：基本概念）

线性规划（Linear Programming）问题指的是在给定有限资源的前提下，最大化或最小化某个目标的问题。这里我将分上下两篇来谈谈线性规划和单纯形算法。

前言

线性规划问题有很多例子，比如在算法导论随笔(六)：贪心算法Greedy algorithm与分数背包问题中，我曾经提到过一个分数背包问题。当时是使用贪心策略来解决。其实，这个问题也可以使用线性规划来解决。

先来回顾一下分数背包问题：如下图，图中有5瓶液体，分别标号为1，2，3，4，5。编号为1的液体有4毫升，每毫升价值3美元。所以该液体的总价值为12美元。类似地，编号2，3，4和5的液体，分别有8毫升，2毫升，6毫升和1毫升，而每毫升的价值分别为4，20，5，50美元，它们的总价值分别为32，40，30，50美元。

现在我们有一个10毫升的杯子，想从5个瓶子里取出共10毫升的液体，使得该10毫升液体的总价值最高。回顾本篇文章最开始时候对线性规划问题的描述：在给定有限资源的前提下，最大化或最小化某个目标的问题。
这里我们可以看出来，对于分数背包问题，“给定有限资源的前提”就是：我们只能从每瓶液体中取出大于0而且小于该液体容积的液体，并且最后的总容积为10毫升。“最大化某个目标”也就是指我们要使得该10毫升的液体总价值最高。假定我们把这5个瓶子中所拿出的液体体积分别设置为x₁，x₂，x₃，x₄和x₅，那么如果我们把这些前提和目标用数学的方式写下来，就是下面的这种形式。
最大化
x 1 × 3 + x 2 × 4 + x 3 × 20 + x 4 × 5 + x 5 × 50 x_1 \times 3 + x_2 \times 4 + x_3 \times 20 + x_4 \times 5 + x_5 \times 50 x1​×3+x2​×4+x3​×20+x4​×5+x5​×50
，其中x₁，x₂，x₃，x₄和x₅满足下列条件：
x 1 ≥ 0 x 1 ≤ 4 x 2 ≥ 0 x 2 ≤ 8 x 3 ≥ 0 x 3 ≤ 2 x 4 ≥ 0 x 4 ≤ 6 x 5 ≥ 0 x 5 ≤ 1 x 1 + x 2 + x 3 + x 4 + x 5 = 10 x_1 \ge 0 \newline x_1 \le 4 \newline x_2 \ge 0 \newline x_2 \le 8 \newline x_3 \ge 0 \newline x_3 \le 2 \newline x_4 \ge 0 \newline x_4 \le 6 \newline x_5 \ge 0 \newline x_5 \le 1 \newline x_1 + x_2 + x_3 + x_4 + x_5 = 10 x1​≥0x1​≤4x2​≥0x2​≤8x3​<