单纯形法

解决的问题

单纯形法可以在较短的时间（似乎是非多项式时间，但我不会证，也找不到论文，不过就是非常快）内解决线性规划问题

形式的处理

对于一个线性规划问题，我们可以写作(以下的\(\,x\,\)是变量，其他都是常数，大写字母表示矩阵)：

\[max\ z=\sum_{i=1}^nc_ix_i=CX\\ s.t.\begin{cases} \sum_{i=1}^na_{1,i}x_i\leq b_1\\ \sum_{i=2}^na_{2,i}x_i\leq b_2\\ \quad\quad\quad\cdots\\ \sum_{i=1}^na_{m,i}x_i\leq b_m\\ \forall x_i\geq0 \end{cases} \]

其中 \(n\geq m\) ，否则没有意义

这样的形式是不利于我们计算的，我们考虑一个更好看的形式（标准形式）：

\[max\ z=\sum_{i=1}^nc_ix_i=CX\\ s.t.\begin{cases} \sum_{i=1}^na_{1,i}x_i=b_1\\ \sum_{i=2}^na_{2,i}x_i=b_2\\ \quad\quad\quad\cdots\\ \sum_{i=1}^na_{m,i}x_i=b_m\\ \forall x_i\geq0 \end{cases} \]

当然，为了处理时的一致有序，我们把\(\,z\,\)的表达式也插入到矩阵中，并令其值为\(\,0\)，这样这一行最后的\(\,z\,\)就是答案的相反数（也就是说后文中的\(\,C\,\)都是“答案行”消元后的系数）

下面给出一些简单情况的转化方法：

如果求的是min或约束条件中出现大于等于，全部取负即可

\[\sum_{j=1}^na_{i,j}x_j\leq b_i\Longrightarrow\sum_{j=1}^na_{i,j}x_j+x_{n+1}=b_i \\x\leq0\Longrightarrow x=y-z,y-z\leq0\,\and\,y,z\geq0 \]

如此，我们就得到了标准形式的线性约束条件

单纯形的处理

关于矩阵的联想

标准形式和线性方程组很像，我们不由得联想到高斯消元，但是线性规划是一个狭长的矩形(上文说了，总存在\(\,n\geq m\,\))

这时我们就不能完全消元，只能选择其中一个\(\,m\,\)阶矩阵将其变为单位矩阵，而单纯形法就是告诉我们应该选择那些来消元

更具体的步骤

选择基变量

要求\(\,z=CX\,\)的最大值，我们不难发现，对于任意\(\,c_i\leq0\)，我们可以直接令\(\,x_i=0\,\)（当然得保证有解）

联系几何意义，线性规划实际上就是在一个超平面上的凸包里选择一个点，使其坐标的一个线性组合最大，那么不难发现是凸包最外围的“界”上的点满足性质

而“界”的代数含义就是\(\,\exists x_i=0\)，于是我们可以让所有我们不准备进行消元的变量为\(\,0\)，之后我们称这样的变量为非基变量，反之叫做基变量

显然，我们希望基变量在\(\,C\,\)中对应的系数越大越好，因为这样答案收敛快

不过除了第一次，在选择基变量时也应注意解的可行性，记基变量全体为\(\,J\,\)，有定义有

\[\forall i\in J,i\geq0 \]

于是我们采用最为朴素的方法，枚举所有的\(\,x\in J\)，假设我们要将\(\,y\,\)加入\(\,J\,\)并将\(\,x\,\)删除，那么我们可以直接令\(\,x=0\,\)，并计算\(\,y\,\)值，代回去验证解的可行性（注意此时除了\(\,y\,\)的非基变量依然都是\(\,0\,\)而基变量经过消元后每行只有一个），然后选择最大的合法\(\,y\,\)值即可

在得到新的\(\,J\,\)之后，重新消元重复上述步骤

终止条件

结合上文，注意到当所有非基变量在\(\,C\,\)中对应的系数都不大于\(\,0\,\)时为最优解（值得一提的是，如果此时存在一个非基变量在\(\,C\,\)中的对应系数恰为\(\,0\)，有无穷种构造方案）

因为如果存在对应系数大于\(\,0\,\)的情况，那么可以将其作为新的基变量，并且一定会使得答案增大

又是没有实现的一天

如有错误，欢迎指正