Problem

给定目标函数 $y=\sum c_ix_i$ 和若干限制形如 $\sum {a_{ij}}x_j\le b_i$ 要求

Solution

根据数学必修五的解题经验，可以发现最优解一定出现在可行域的边界或者顶点。单纯形的做法，就是不停地变换整个线性规划让取值从一个顶点走到令一个顶点，直到可以判定当前解最优为止。

标准型与松弛型

所谓标准型，即把约束条件写成形如 $\sum a_{ij}x_j\le b_i$ 所谓松弛型，即加入一个松弛变量 $x'$ ，把约束调节写成 $x'_i=b_i-\sum a_{ij}x_j,x'_i\ge 0$ 标准型转化到松弛型是很显然的，非标准型也容易通过同乘 $-1$ 什么的转化到标准型。可以发现，对于一个松弛型，当 $b_i$ 均 $\ge 0$ 的时候，令 $x'_i=b_i$ ，其它变量都为 $0$ ，就是一组可行解(而对于存在 $b_i< 0$ ，可以通过一些构造方法生成一组可行解)。所以接下来就在这个可行解的基础上逼近最优解。

Simplex

$y=\sum c_ix_i$ ，可以发现，如果变换之后，仍然有某个 $c_i> 0$ ，那就有可能通过修改 $x_i$ 的值让 $y$ 增大。当所有 $c_i< 0$ ，即可以证明线性规划已经达到了最优解。。 $Pivot$ 就是修改某个值之后相应变换整个线性规划的过程。

Pivot

对于选定出的 $e$ 使得 $c_e> 0$ ，需要在满足条件的情况下。那就遍历每个式子 $x'_i=b_i-\sum a_{ij}x_j,x'_i\ge 0$ ，如果 $a_{ie}\ge 0$ ，说明这个式子对 $x_e$ 产生了约束，在这个式子中， $x_e$ 取最大值的情况就是其它变量为 $0$ ，使得 $a_{ie}x_e=b_i$ 。因此用 $\dfrac {b_i}{a_{ie}}$ 衡量限制的松紧。找出对这个变量限制最紧的式子，把所有 $b_i$ 都分给它，式子变形为，即。此时在 $x_e$ 位置上的那个变量就已经不是 $x_e$ ，而是 $x'_i$ ，所以需要将这个式子带到所有其它的式子里面，相当于把 $x_e$ 用它对应的新式子等效地替代掉。举个栗子(用 $'$ 表示变换之后的量) 带入另一个式子 $k$ 化简以下就出来了。相应地， $c[]$ 数组也要修改。因为也要把 $x_i''$ 向 $y$ 里面带，带完之后所有项的系数都变了。这样，单纯形就解完了。

对偶原理

是这样说的：线性规划 $\sum {a_{ij}}x_j\le b_i$ 的对偶问题是 $\sum {a_{ji}}x'_i\ge c_j$ 两者具有相同的最优解

比如算法导论上给出了一个栗子满足 $x_1+x_2+3x_3\le 30$ $2x_1+2x_2+5x_3\le 24$ $4x_1+x_2+2x_3\le 36$ $x_1,x_2,x_3\ge 0$ 的对偶问题是满足 $y_1+2y_2+4y_3\ge 3$ $y_1+2y_2+y_3\ge 1$ $3y_1+5y_2+2y_3\ge 2$ $y_1,y_2,y_3 \ge 0$

有了这个工具，一些情况下就可以避免乘 $-1$ 使 $b_i$ 出现负值了。