线性规划

线性规划有两种形式：

1. 标准型：

   $$maxmize\ \sum_{j=1}^nc_jx_j\\\sum^n_{j=1}a_{ij}x_j\le b_i\ ,\ i=1,2,\dots,m\\\ \ \ \ \ \ \ \ \ \ \ x_j\ge0\ ,\ j=1,2,\dots,n$$

$$maxmize\ c^Tx\\Ax\le b\\\ \ \ x\ge0$$

   要化为标准型，要克服一下困难。

1. 目标函数不是最大化，而是最小化。

   将所有的都取负。

2. 变量不具有非负约束。

   将$x_j$转为$x_j'-x_j''$，这两个引入的变量有非负约束。

3. 有等式约束

   将其转为一个$\le和一个\ge。$

4. 松弛型

   $$maxmize\ z=v+\sum_{j\in N}c_jx_j\ \ \ \ \ \ \\\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ x_i=b_i-\sum_{j\in N}a_{ij}x_j,i\in B$$

松弛型就是对于每一个标准型中的约束引入一个有非负约束的松弛变量来将其改写为等式约束，并且依此改写目标函数。其中，等式左侧的松弛变量是基本变量，而右边的则为非基本变量，最终目标函数中只允许出现非基本变量。其中，B为基本变量的下标集合，而N为非基本变量的下标集合。

实际上所有的变量都是非负约束的。

后续中用（N, B, A, b, c, v)来表示一个松弛型。

一些问题用线性规划解决

1. 最小费用流

   是对于最大流的一个推广。不再是求最大流，而是在汇点要求一定流的情况下，要求成本最小，这是由于现在每条路径上都存在一个单位流成本。

2. 多商品流

   对于最小费用流的一个推广。现在有多种流，但每种流的源节点和汇点不一定相同，但流共享容量。不再需要最小化成本，只需给出一个方案即可。看起来这个并没有目标函数，但实际上，只不过它的目标函数是一个用0替代的常数罢了，所以仍然是一个线性规划。

单纯形算法

对于一个松弛型的线性规划来说，基本解是非基本变量都为0，而基本变量根据非基本变量求出。如果这个基本解是一个可行解，那么称之为可行基本解。

单纯形算法由一个可行基本解出发，不断将松弛型更改为一个等价的松弛型来缩小可行域的范围(我是这么理解的)。

而更改松弛型的方式就是转动。将一个基本变量替入其中(变为非基本变量，放到等式右侧)，将一个非基本变量换出（变为非基本变量，放到等式左侧)。

这个过程的实质就是缩小范围。对于目标函数中系数为正的变量，我们希望其越大越好。而系数为负的变量，我们希望其越小越好，实际上取0即可，因为非负约束。而对于一个系数为正的变量，我们将其增大，而唯一的限制就是所有基本变量的非负约束，我们取对该非基本变量限制最严格的基本变量替入，也就是让该非基本变量变为部分取决于限制最严格的基本变量，其范围也就自然而然被缩小了，缩小为当前限制体现出来不可能的部分。

当在目标函数中所有自变量的系数都为负数时，其就是最优解了，因为存在一个非负约束，导致最大值就是v。

无界的情况：当对于某一个系数为正的非基本变量寻找对于它最严格的基本变量的约束时，若发现没有约束或者负相关时，也就是这个非基本变量能够无限增大，也就是说，目标函数可以无限增大，此时无界。

按理来说，由于松弛型最多只有$C_{n+m}^m$种，n为非基本变量数量，m为基本变量数量，因此循环最多就进行松弛型的种类数。但是有时会出现循环的情况，此时我们可以通过每次都选择具有最小下标的非基本变量这一策略，这一策略能保证不会出现无限循环的情况，在此不做证明。

对偶性

对于一个规划问题，原问题是求最大值。则其对偶问题就是求其最小值，且其最优值就是原问题的最大值。对偶问题不唯一，因为实际上要求很少。但是我们针对一个规划问题，去找他的对偶问题实际上是为了简化，并且实际上对偶问题本身也很难找，在我们本身并不知道最优值是多少的情况下。

常用的有拉格朗日对偶。

在此处，算法导论使用的对偶比较特殊，是专门针对线性规划问题的。

$$minmize\ \sum_{i=1}^mb_iy_i\\\sum^m_{i=1}a_{ij}y_i\ge c_j\ ,\ j=1,2,\dots,m\\\ \ \ \ \ \ \ \ \ \ \ y_i\ge0\ ,\ i=1,2,\dots,n$$

这就是标准型的对偶问题。

首先很轻松可以证明，原问题的目标函数必然小于等于该对偶问题的目标函数。证明见附录图1。

此时，只要我们能够证明其最大值与最小值是相等的，我们就可以证明这个最大值和最小值是最优解。因为互相限制。

为了证明这一点，我们首先需要求出对偶问题的解。

假设$c_j'$是最后松弛型的系数，那么$\overline{y_i}=\begin{cases}-c_{n+i}'\ \ \ \ 若(n+i)\in N\\0\ \ \ \ \ \ \ \ \ \ \ \ 其他 \end{cases}$。

经过数学证明，可以证明两个最优值相等，且对偶问题的解是可行的。证明见附录图2。

可行初始解

到目前为止，还差最后一块拼图，那就是最初的可行初始解怎么确定，因为当非基本变量全取0的时候可能并不是一个可行初始解。

但实际上，这样的一个可行初始解相当难找，因此我们构造一个“没有目标”的线性规划来找到任意一组可行初始解。

$$maxmize\ \ \ \ -x_0\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \\\sum^n_{j=1}a_{ij}x_j-x_0\le b_i\ ,\ i=1,2,\dots,m\ \ \ \ \ \ \ \ \ \ \ \ \ \\\ \ \ \ \ \ \ \ \ \ \ x_j\ge0\ ,\ j=0,1,2,\dots,n$$

由于限制了$x_0\ge0$，因此若是达到最大化，$x_0$=0。而此时求出的其他x也是满足约束条件的，因此是一个可行解。若是最优值不能达到0，那么就是没有可行解的。

流程：

1. 是否所有b都$\ge$0，如果是，则非基本变量全0是一组可行解。
2. 否则构造上述线性规划问题。
3. 用$x_0$替入替换$x_l,l=n+k,k为最小的b的下标$，此时基本变量$x_l$将是最小的基本变量，初始解为全0。
4. 可以证明，在第三步结束所得的解将会变为一个对于该问题的可行解。证明见附录图3。
5. 求出辅助线性规划的最优值，判断是否是0
6. 若是0，则通过转动将$x_0$变为非基本变量。
7. 否则无解。

附录

---

图1

---

图2

---

图3

---