单纯形法
不失一般性，只考虑最大化问题： \[\max \quad c^T x \] 满足\[Ax=b,\qquad x\ge 0\] 其中\[A\in\mathbb R^{m\times n},\quad x\in\mathbb R^n,\quad b\in\mathbb R^m,\quad c\in\mathbb R^n. \] 通常假设\(A\)的秩为\(m\)且\(m<n\)，矩阵\(A\)有\(n\)列，因此写成\(A=[a_1,a_2,\dots,a_n]\)。从中选取\(m\)个线性无关的列，组成一个可逆矩阵\(B\in\mathbb R^{m\times m}\)，称之为“基”。
这\(m\)列所对应的变量为基变量\(x_B\)，剩余\(n-m\)个变量成为非基变量\(x_N\)。于是约束可以写成\[Bx_B+Nx_N=b\] 单纯形法让所有非基变量为0，那么\(Bx_B=b\)，所以\(x_B=B^{-1}b\)，因此一个基对应于一个解： \[\boxed{ x_B=B^{-1}b,\qquad x_N=0 }\] 记\(\bar{b}=B^{-1}b\)，如果恰好\(\bar{b}\ge 0\)，那么这个解满足\(x\ge0\)，成为一个基本可行解（BFS）。
单纯形法讨论在已经有了一个基本可行解下的后续操作，因为：\[Bx_B+Nx_N=b\] 解出基变量为\[x_B=B^{-1}b-B^{-1}Nx_N=\bar{b}-\bar{A}x_N\]代入目标函数为\[z=c_B^Tx_B+c_N^Tx_N=c_B^TB^{-1}b + \left( c_N^T-c_B^TB^{-1}N \right)x_N=c_B^T \bar{b}+x_N^T\bar{c}\] 其中第一项是当前的目标函数值，第二项的系数\(\bar{c}^T=c_N^T-c_B^TB^{-1}N\)是一个约化成本（检验数）向量，其中的每个元素表示相应的非基变量增加1，会导致目标函数如何变化。
如果某次得到新的基后，计算出的检验数向量满足\(\bar{c}\le 0\)，则代表已经没有任何局部改善方向，对于LP而言，这代表达到全局最优，停止迭代。如果还存在某个非基变量满足\(\bar{c}_j>0\)，则可以选择这个变量入基，让他从0增加到\(\theta\)，那么这时等式约束仍需要满足，即： \[Bx_B+a_j\theta=b\]于是\(x_B=B^{-1}b-B^{-1}a_j\theta\)，定义\(y=B^{-1}a_j\)，那么就有\(x_B(\theta)=x_B-y\theta\)
由于\(x_B(\theta)\ge 0\)仍然需要成立，所以\(x_B -y\theta\ge0\)对该向量中的每个元素都成立。解得\[ \theta^*= \min_{i:y_i>0} \frac{x_{B_i}}{y_i} \] 当\(\theta\)达到\(\theta^*\)后，至少一个基变量刚好变成零，这个基变量就离开了基，称为出基变量。此时可以组成新的基：\[B\longrightarrow B'\] 如此循环直至检验数向量满足\(\bar{c}\le 0\)收敛。
最后一个问题是如何获得最初的基，由基本可行解的定义，目标就是找一个列指标集合\(B\)，使得对应的基矩阵\(A_B\)可逆，且\(A_B^{-1}b\ge 0\)。如果原问题中已经显然存在一个这样的基，直接取该基即可，否则进行以下处理：
首先把问题整理成\[Ax=b,\qquad x\ge 0\] 如果存在某个\(b_i<0\)，则把这一行整体乘以-1。
然后对每个约束，都查找有没有只在自身处系数不为0，而对其他所有约束都为0的基变量（形如\(e_i=(0,\cdots,1,\cdots,0)^T\)），如果有，则将该基变量加入基中。否则人为地增加辅助变量\(a_i\)，哪一行缺少用于构造初始基的列，就在哪一行加入辅助变量，于是扩充后的约束可以写成\[Ax+Ea=b\]其中有\(a\ge 0\)。于是可以构造出一个显然的初始基本可行解，然后求以下的辅助LP：\[\max \quad w=\sum_{i=1}^k a_i \] 满足\[x\ge0,a\ge0,Ax+Ea=b\] 这个问题称为Phase I问题，目标是把所有人工变量压回到0，如果最后解的\(w^*>0\)，则代表即使把人工变量压到最小，它们仍不能全部为零，因此原问题不可行。否则可以把所有\(a_i\)全部取0，即得到了原问题的一个基本可行解。这个时候可能部分\(a_i=0\)但仍然留在基变量内，可以通过一次pivot把新的变量换入基，人工变量换出基（因为取值为0所以实质没有改变解），即得到了初始基\(B\)，而后就可以开始用单纯形法求解。
对偶单纯形法
对偶单纯形法对于线性规划的reoptimization非常重要，他也是MILP的求解中最常使用的用于求解LP松弛的方法。单纯形法在保持可行性的基础上寻求最优性，对偶单纯形法在保持最优性的基础上寻求可行性。
按照前面定义的符号，现在有两个条件： \[\bar{b}\ge0, \bar{c}\le 0\] 分别代表可行性和最优性。
假设已经有一个解满足\(\bar{c}\le 0\)已经全部成立，但是\(\bar{b}_i\ge 0\)对于某些\(i\)不成立，因为\(x_B=\bar{b}\)，这代表这些\(i\)对应着负的分量。于是常常先选择一个\(\bar{b}_r<0\)，作为出基行，常见规则是选择最负的一个即\[r=\arg\min_i\bar b_i\] 对前面得到的：\[x_B=\bar{b}-\bar{A}x_N\]取第\(r\)行，即得到\[x_{B_r}=\bar{b}_r-\sum_{j\in N} \bar{a}_{rj} x_j\] 我们希望让某个非基变量入基，来把\(x_{B_r}\)从负数推到0，因此可以只考虑一个\(x_j\) \[x_{B_r}=\bar{b}_r-\bar{a}_{rj}x_j\] 因为\(\bar{b}_r<0\)，\(x_j>0\)，因此在选择\(x_j\)需要保证\(\bar{a}_{rj}<0\)，另外还要保证变换之后仍然有\(c\le 0\)，这次换基之后，有\[\bar{c}_k'=\bar{c_k}-\frac{\bar{c_j}}{\bar{a}_{rj}} \bar{a}_{rk}\le 0\] 整理后得到\[\frac{\bar{c}_k}{\bar{a}_{rk}}\ge \frac{\bar{c}_j}{\bar{a}_{rj}}\] 对所有的\(k\)都成立，因此在选择\(j\)时，需要选择： \[j^*=\min_{a_{rj}<0} \frac{\bar{c_{j}}}{\bar{a}_{rj}}\] 于是选择让\(x_{B_r}\)出基，让\(x_{j^*}\)出基。如此类似反复直到收敛即为对偶单纯形法的求解过程。
