这一节课讲解了求解线性规划问题的方法：单纯形法（simplexmethod）。
记辅助向量$v=\begin{bmatrix}\lambda_1&\lambda_2&\dots&\lambda_k&0&0&\dots&0\end{bmatrix}^T$，我们仍然构造$x'=x+\epsilonv$和$x''=x-\epsilonv$（熟悉的套路...）。显然有$x=\frac{x'+x''}{2}$，由于$x$是最优解，当然$x'$和$x''$也是最优解。如果存在$\lambda_i<0$，那么我们取$\epsilon=\min\limits_{\lambda_i<0}-\frac{x_i}{\lambda_i}$，就能把$x'$中$x_1$到$x_k$的某一个变成0；如果不存在$\lambda_i<0$，那么我们取$\epsilon=\min\frac{x_i}{\lambda_i}$，就能把$x''$中$x_1$到$x_k$的某一个变成0。也就是说，非0元素少了一个。这样一直构造下去，我们就能不断减少非0元素，直到$x_1$到$x_k$在$A$中对应的$k$列线性无关，$x$就变成了一个基可行解。而且在构造过程中，最优性没有改变，$x$还是最优解。
接下来介绍用单纯形法（simplexmethod）求解线性规划问题的方式。单纯形法的每一步都在引入一个非基变量取代某一基变量，找出目标函数值更优的另一基本可行解，这样一步一步调整到最优解。
来看一个例题：$$\begin{matrix}&\max\limits_{x}\quad3x_1+2x_2\\\text{s.t.}&2x_1+x_2\le12\\&x_1+2x_2\le9\\&x_1,x_2\ge0\end{matrix}$$引入松弛变量，将原问题变为$$\begin{matrix}&\max\limits_{x}\quadz=3x_1+2x_2\\\text{s.t.}&2x_1+x_2+x_3=12\\&x_1+2x_2+x_4=9\\&x_1,x_2,x_3,x_4\ge0\end{matrix}$$首先，我们有一个可行解：$x=\begin{bmatrix}0&0&12&9\end{bmatrix}^T$，当前目标函数值为$z=0$。我们把各个变量用非基变量进行表示，有$$x_3=12-2x_1-x_2\\x_4=9-x_1-2x_2\\z=3x_1+2x_2$$看起来$x_1$对$z$的贡献比$x_2$来的大（$x_1$的系数比较大，这个系数称为“检验数”），我们考虑把$x_1$变成基变量。要注意，$x_3\ge0$和$x_4\ge0$的条件仍然需要成立。根据$x_1$与$x_3$和$x_4$之间的表达式不难看出，当$x_1=6$时，$x_3$最先变成0，我们把它从基变量中去除。
现在，可行解变为$x=\begin{bmatrix}6&0&0&3\end{bmatrix}^T$，当前目标函数值为$z=18$。继续把各个变量用非基变量进行表示，有$$x_1=6-x_2/2-x_3/2\\x_4=3-3x_2/2+x_3/2\\z=18+x_2/2-3x_3/2$$从系数可以看出，只有增加$x_2$才能对目标函数值的增大有所贡献，考虑把$x_2$变成基变量。从$x_2$与$x_1$和$x_4$的关系式中也不难发现，当$x_2=2$时，$x_4$最先变成0，我们把它从基变量中去除。
当然，完全有可能出现某一个变量可以无限增大，求不出最优解的情况。考虑以下线性规划问题：$$\begin{matrix}&\max\limits_{x}\quad2x_1+x_2\\\text{s.t.}&-3x_1+x_2\le3\\&-4x_1+x_2\le5\\&x_1,x_2\ge0\end{matrix}$$加入松弛变量后有$$\begin{matrix}&\max\limits_{x}\quad2x_1+x_2\\\text{s.t.}&-3x_1+x_2+x_3=3\\&-4x_1+x_2+x_4=5\\&x_1,x_2,x_3,x_4\ge0\end{matrix}$$有初始可行解$x=\begin{bmatrix}0&0&3&5\end{bmatrix}^T$，仍然用非基变量表示其它变量，有$$x_3=3+3x_1-x_2\\x_4=5+4x_1-x_2\\z=2x_1+x_2$$从$x_1$和$x_3$与$x_4$的关系式中可以看出，不管$x_1$如何增大，两个基变量都不会小于0，而且$x_1$的检验数也是正数，那么这个优化问题没有最优解。
归纳起来，单纯形法的基本步骤如下（来自wiki）：
可以用矩阵的形式，把各个变量用非基变量进行表示。
设要优化的线性规划问题（标准形式）为$$\begin{matrix}&\max\limits_{x}\quadz=c^Tx\\\text{s.t.}&Ax\leb\\&x\ge0\end{matrix}$$我们可以把各个矩阵或向量根据基变量和非基变量分为两部分：令$c^T=\begin{bmatrix}c_B^T&c_N^T\end{bmatrix}$，令$A=\begin{bmatrix}A_B&A_N\end{bmatrix}$，令$x=\begin{bmatrix}x_B^T&x_N^T\end{bmatrix}^T$，显然我们有$$A_Bx_B+A_Nx_N=b\\z=c_B^Tx_B+c_N^Tx_N$$通过移项就能用$x_N$表示其它变量：$$x_B=A_B^{-1}b-A_B^{-1}A_Nx_N\\z=c_B^TA_B^{-1}b+(c_N^T-c_B^TA_B^{-1}A_N)x_N$$当然啦，由于基可行解中$x_N=0$，我们有$$x_B=A_B^{-1}b\\z=c_B^TA_B^{-1}b$$单纯形表可以帮助我们利用矩阵形式，通过列表的方式求解线性规划问题，也利于编程实现。
首先画一张这样的表：$$\begin{array}{c|cc|c}&c_B^T&c_N^T&0\\\hlinex_B&A_B&A_N&b\end{array}$$利用行变换将$A_B$变为$I$，根据线性代数的知识，这相当于左乘了一个$A_B^{-1}$，那么表会变成这样：$$\begin{array}{c|cc|c}&c_B^T&c_N^T&0\\\hlinex_B&I&A_B^{-1}A_N&A_B^{-1}b\end{array}$$然后再把下面一行乘上$c_B^T$，用上面一行减一减，得到$$\begin{array}{c|cc|c}&0&c_N^T-c_B^TA_B^{-1}A_N&-c_B^TA_B^{-1}b\\\hlinex_B&I&A_B^{-1}A_N&A_B^{-1}b\end{array}$$这是一张非常神奇的表：第一行第二列（$x_B$那一列我们不看）就是检验数，第一行第三列就是$-z$，而基变量和非基变量之间的系数也可以通过第二行的第二、三两列求出，计算起来非常方便。表格每这样计算一次，就是单纯形法里的一次迭代。
虽然这个表格看起来有点麻烦（比如，看起来每次迭代好像都要重新写上$A_B$和$A_N$什么的，从头开始变化？），但实际操作起来是非常简便的，每次迭代的变化不会很多。看一个例子就知道了：
$$\begin{matrix}&\max\limits_{x}\quad3x_1+2x_2\\\text{s.t.}&2x_1+x_2\le12\\&x_1+2x_2\le9\\&x_1,x_2\ge0\end{matrix}$$这个例子和上一节的例子是一样的。仍然加入松弛变量变化为标准形式：$$\begin{matrix}&\max\limits_{x}\quadz=3x_1+2x_2\\\text{s.t.}&2x_1+x_2+x_3=12\\&x_1+2x_2+x_4=9\\&x_1,x_2,x_3,x_4\ge0\end{matrix}$$初始的基可行解是$x=\begin{bmatrix}0&0&12&9\end{bmatrix}^T$，绘制初始的单纯形表：$$\begin{array}{c|cccc|c}&3&2&0&0&0\\\hlinex_3&2&1&1&0&12\\x_4&1&2&0&1&9\end{array}$$由于$x_B=\begin{bmatrix}x_3&x_4\end{bmatrix}^T$，所以此时的$A_B$由第二行和第三行的三、四两列组成，而且恰好是$I$；$c_B^T$由第一行的第三、四两列组成，而且恰好是0，我们直接来到了最后一步。
退化是指一个基可行解中，存在至少一个基变量为0的情况。也就是说，这个基变量可以和另一个非基变量任意互换，而不影响结果（反正两个变量在这个解里取值都是0）。
不过，我们可以使用如下法则让单纯形法一定不会陷入循环（也就是一定能找到最优解）：在有多个可以入基的变量时，选择下标最小的一个；在有多个可以出基的变量时，也选择下标最小的一个。不过我不会证明...
接下来证明单纯形法在非退化的情况下为什么可以取到最优解，以及为什么可以停止。
首先证明：若检验数向量$\hat{c}=c_N-c_B^TA_B^{-1}A_N$的每一维都小等于0，那么此时基可行解$x$是最优解。
反证：假设有一个更优的$y$才是最优解。令$d=x-y$，我们有$$Ax-Ay=b-b=0\\=Ad=A_Bd_B+A_Nd_N$$那么$$d_B=-A_B^{-1}A_Nd_N$$则$$c^Td=c_B^Td_B+c_N^Td_N\\=(c_N^T-c_B^TA_B^{-1}A_N)d_N=\hat{c}d_N$$要注意，这里的B（基变量）和N（非基变量）都是对于$x$而言的。
显然根据基可行解的定义$x_N=0$，又$y\ge0$，所以$d_N\ge0$；又$\hat{c}\le0$，所以$c^Td=\hat{c}d_N\le0$，那么$c^Ty=c^Tx+c^Td\lec^Tx$，说明$y$并没有比$x$更优，矛盾。这就说明了为什么在检验数均小等于0时停止算法，就能得到最优解。
类似地，我们可以说明若基可行解$x$是非退化的最优解，那么检验数向量的每一维都小等于0。否则由于$x$是非退化的最优解，如果有一个检验数大于0，它对应的非基变量一定有增加的空间（而不会像退化的解一样，增加的空间为0），那么就能构造一个更优的解。这就说明了，在非退化的情况下，肯定有解满足算法停止的情况。