对于包含1个优化目标，n个变量，m个线性约束条件的线性规划问题来说，首先这是一个凸优化问题，一定存在最优值，其次最优值的取值一定是在m个约束条件构建几何体的顶点上。那么怎么找到所有的顶点，并且找到其中对应最优值的那个顶点呢？单纯形法的思路为：

  1. 找到一个顶点，也就是一个基可行解；
  2. 在这个基可行解的基础上，跳到目标函数更好的相邻的另一个顶点上；
  3. 直到没有更好的顶点为止。

具体实施中需要解决：

  1. 什么是基可行解？
  2. 怎么根据该基可行解找到另一个目标函数更好的相邻的另一个可行解上？

下面我们以具体问题来说明：

求解问题：
$$maxZ=10x_1+15x_2+x_3+3x_4+2x_5$$
$$ s.t.=\left \{ \begin{array}{c} -x_1+2x_2+x_3= 18 \\ x_1+x_2+x_4=24 \\ x_1+x_5= 15 \\ x_1,x_2,x_3,x_4,x_5\ge 0 \end{array} \right. $$

将其写成矩阵形式：
$$(\textbf {A}|\textbf {b})=\left ( \begin{array}{c|c} \begin{matrix} -1&2&1&0&0\\ 1&1&0&1&0\\1&0&0&0&1 \end{matrix}& \begin{matrix} 18\\ 24\\15 \end{matrix} \end{array} \right ) $$

其中，初始基为：
$$B_0=(p_3,p_4,p_5)=\left ( \begin{matrix}1&0&0\\0&1&0\\0&0&1\end{matrix}\right )$$

\(x_3、x_4、x_5\)为基变量， \(x_1、x_2\)为非基变量，约束条件改写为：
$$ s.t.=\left \{ \begin{array}{c} x_3= 18+x_1-2x_2 \\ x_4=24-x_1-x_2\\ x_5= 15-x_1 \\ x_1,x_2,x_3,x_4,x_5\ge 0 \end{array} \right. $$

代入目标函数得\(Z=10x_1+15x_2+x_3+3x_4+2x_5=120+6x_1+10x_2\)，取非基变量\(x_1=0,x_2=0\)，可得到基可行解\(X^{(0)}=(0,0,18,24,15)\)，目标值\(Z=120\)

显然这不是最优解，因为在\(Z=120+6x_1+10x_2\) 中，若\(x_1、x_2\)增大，那么\(Z\)的值也会增大，说明直接让 \(x_1=0、x_2=0\) 是不妥的。

在\(Z=120+6x_1+10x_2\) 中，\(x_2\)对\(Z\)的增长贡献最大(因为\(x_2\)前面的系数更大一点)，因此我们不妨让\(x_2\)增长到一个正数，但是让\(x_2\)增大到多少才是最好的呢？

考虑让\(x_2\)成为基变量：
$$ s.t.=\left \{ \begin{array}{c} 2x_2+x_3= 18 \\ x_2+x_4=24\\ x_5= 15 \\ x_1,x_2,x_3,x_4,x_5\ge 0 \end{array} \right. $$
为了保证各决策变量非负，所以\(x_2=min\{\frac{18}{2},24\}=9\)，这就是\(x_2\)的最大取值，此时\(x_3=0\)，\(x_3\)就成了非基变量（也叫出基变量），\(x_2\)成为了基变量（进基变量），即新基是\(x_2,x_4,x_5\)，非基变量是\(x_1,x_3\)。

为了让新的基变量对应的系数为1，所以做初等变换：
$$\begin{align}(\textbf {A}|\textbf {b})&=\left ( \begin{array}{c|c} \begin{matrix} -1&2&1&0&0\\ 1&1&0&1&0\\1&0&0&0&1 \end{matrix}& \begin{matrix} 18\\ 24\\15 \end{matrix} \end{array} \right ) \\ &= \left ( \begin{array}{c|c} \begin{matrix} -\frac{1}{2}&1&\frac{1}{2}&0&0\\ 1&1&0&1&0\\1&0&0&0&1 \end{matrix}& \begin{matrix} 9\\ 24\\15 \end{matrix} \end{array} \right ) \\ &= \left ( \begin{array}{c|c} \begin{matrix} -\frac{1}{2}&1&\frac{1}{2}&0&0\\ \frac{3}{2}&0&-\frac{1}{2}&1&0\\1&0&0&0&1 \end{matrix}& \begin{matrix} 9\\ 15\\15 \end{matrix} \end{array} \right )\end{align} $$
新的基\(B_1=(p_2,p_4,p_5) =\left( \begin{matrix}1&0&0\\0&1&0\\0&0&1\end{matrix}\right )\)

\(x_2、x_4、x_5\)是基变量，\(x_1、x_3\)是非基变量，约束条件改写为：
$$ s.t.=\left \{ \begin{array}{c} -\frac{1}{2}x_1+x_2+\frac{1}{2}x_3= 9 \\ \frac{3}{2}x_1-\frac{1}{2}x_3+x_4=15\\ x_1+x_5= 15 \\ x_1,x_2,x_3,x_4,x_5\ge 0 \end{array} \right. \Rightarrow \left \{ \begin{array}{c} x_2= 9+\frac{1}{2}x_1-\frac{1}{2}x_3 \\ x_4=15 – \frac{3}{2}x_1+\frac{1}{2}x_3 \\ x_5= 15-x_1 \\ x_1,x_2,x_3,x_4,x_5\ge 0 \end{array} \right. $$

代入目标函数，得\(Z=10x_1+15x_2+x_3+3x_4+2x_5=210+11x_1-5x_3\)，令非基变量\(x_1=0,x_3=0\)，得\(X^{(1)}=(0,9,0,15,15)\)，目标值\(Z=210\)

新的目标值比上次得到的更优(210>200)，但这个是不是最优解呢？

也不是。理由是如果\(x_1\)增大，那么\(Z\)也会增大，沿着上面的思路，同理，考虑让\(x_1\)成为基变量：
$$ s.t.=\left \{ \begin{array}{c} -\frac{1}{2}x_1+x_2+\frac{1}{2}x_3= 9 \\ \frac{3}{2}x_1-\frac{1}{2}x_3+x_4=15\\ x_1+x_5= 15 \\ x_1,x_2,x_3,x_4,x_5\ge 0 \end{array} \right. $$
为了保证决策变量非负，所以，\(x_1=min\{\frac{15\times 2}{3},15\}=10\)，此时\(x_4=0\)，所以\(x_4\)就成了非基变量。新的基\(x_1,x_2,x_5\)成了基变量，而\(x_3,x_4\)是非基变量。

为了让新的基变量对应的系数为1，所以做初等变换：
$$\begin{align}(\textbf {A}|\textbf {b})&=\left ( \begin{array}{c|c} \begin{matrix} -1&2&1&0&0\\ 1&1&0&1&0\\1&0&0&0&1 \end{matrix}& \begin{matrix} 18\\ 24\\15 \end{matrix} \end{array} \right ) \\ &= \left ( \begin{array}{c|c} \begin{matrix} -\frac{1}{2}&1&\frac{1}{2}&0&0\\ 1&1&0&1&0\\1&0&0&0&1 \end{matrix}& \begin{matrix} 9\\ 24\\15 \end{matrix} \end{array} \right ) \\ &= \left ( \begin{array}{c|c} \begin{matrix} -\frac{1}{2}&1&\frac{1}{2}&0&0\\ \frac{3}{2}&0&-\frac{1}{2}&1&0\\1&0&0&0&1 \end{matrix}& \begin{matrix} 9\\ 15\\15 \end{matrix} \end{array} \right ) \\ &= \left ( \begin{array}{c|c} \begin{matrix} -\frac{1}{2}&1&\frac{1}{2}&0&0\\ 1&0&-\frac{1}{3}&\frac{2}{3}&0\\1&0&0&0&1 \end{matrix}& \begin{matrix} 9\\ 10\\15 \end{matrix} \end{array} \right ) \\ &= \left ( \begin{array}{c|c} \begin{matrix} 0&1&\frac{1}{3}&\frac{1}{3}&0\\ 1&0&-\frac{1}{3}&\frac{2}{3}&0\\0&0&\frac{1}{3}&-\frac{2}{3}&1 \end{matrix}& \begin{matrix} 14\\ 10\\5 \end{matrix} \end{array} \right ) \end{align} $$
新的基\(B_1=(p_1,p_2,p_5)=\left( \begin{matrix}0&1&0\\1&0&0\\0&0&1\end{matrix}\right )\)

\(x_1,x_2,x_5\)是基变量，\(x_3,x_4\)是非基变量，所以约束条件改写为：
$$ s.t.=\left \{ \begin{array}{c}x_2+\frac{1}{3}x_3+\frac{1}{3}x_4= 14 \\ x_1-\frac{1}{3}x_3+\frac{2}{3}x_4=10\\ \frac{1}{3}x_3-\frac{2}{3}x_4+x_5= 5 \\ x_1,x_2,x_3,x_4,x_5\ge 0 \end{array} \right. \Rightarrow \left \{ \begin{array}{c} x_2= 14-\frac{1}{3}x_3-\frac{1}{3}x_4 \\ x_1=10 + \frac{1}{3}x_3-\frac{2}{3}x_4 \\ x_5= 5-\frac{1}{3}x_3+\frac{2}{3}x_4 \\ x_1,x_2,x_3,x_4,x_5\ge 0 \end{array} \right. $$

代入目标函数，得\(Z=10x_1+15x_2+x_3+3x_4+2x_5=320-\frac{4}{3}x_3-\frac{22}{3}x_4\)，令非基变量\(x_3=0,x_4=0\)，得\(X^{(2)}=(10,14,0,0,5)\)，目标值\(Z=320\)

由于这个 \(Z=320-\frac{4}{3}x_3-\frac{22}{3}x_4\) 中\(x_3,x_4\)前面的系数是负数，所以无法通过增大\(x_3,x_4\)来使\(Z\)增大，而\(x_3,x_4\ge 0\)，所以这已经是最优情况，最优解\(X^*=(10,14,0,0,5)\)，最优值\(Z=320\)