最优化2:线性规划及单纯形法
本文旨在介绍线性规划的基本概念、单纯形算法和分析单纯形法背后的原理，参考资料包括Convex Optimization(by Stephen Boyd)，《最优化理论与算法(第2版)》(陈宝林 编著)，维基百科以及其他在线资料等(详情见参考)。1 线性规划
1.1 线性规划基本概念
线性规划(LP, Linear Programming)是指具有线性约束(包括等式约束和非等式约束)、线性目标函数的最优化问题。它是数学规划中极为特殊的一种形式。
其数学表达为
https://www.zhihu.com/equation?tex=%5Cbegin%7Bequation%7D+%5Cbegin%7Barray%7D%7Bll%7D++%5Ctext+%7B+min+%7D+%26+c%5E%7BT%7D+x+%5C%5C+%5Ctext+%7B+s.t.+%7D+%26+A+x+%3D+b%5C%5C+%5Ctext+%7B+%7D+%26+Gx%5Cpreceq+h+%5Cend%7Barray%7D+%5Cend%7Bequation%7D
特点：
[*]可行域是一个凸集(包括空集)。因为其可行域有限多个半空间和超平面的交集，因此是一个多面体（前文已经说明多面体是一个凸集）。
[*]目标函数既是凸函数，又是凹函数(因为是线性函数或仿射函数)
定理：
解的存在性定理。因为凸函数的最大值必在边界处取得，凹函数的最小值必在边界处取得。因此线性规划的目标函数的最小值和最大值都在边界处取得。因此线性规划的最优解(如果有的话)一定能在极点(vertices)处取得(当有多个最优解时，最优解的集合一定包含某个极点)。在两种情况下，LP无最优解：
[*]LP不可行。即LP的约束自相矛盾，也即LP的可行域为空集。因为无可行解，自然也就没有最优解。
[*]LP的可行域在目标函数梯度负方向无界(如果是最大化目标函数，则LP可行域在目标函数梯度方向无界)。在这种情况下，我们总能沿着负梯度方向找到更优的解，使得目标函数更小，因此无最优解。
多面体的极点和极方向。
定义(极点):
设为非空凸集， https://www.zhihu.com/equation?tex=x%5Cin+S ，若不能表示为中两个不同点的严格凸组合，即 https://www.zhihu.com/equation?tex=x+%3D+%5Clambda+x%5E%7B%281%29%7D%2B%281-%5Clambda%29x%5E%7B%282%29%7D%28%5Clambda%5Cin%280%2C1%29%29%5CLongrightarrow+x%3Dx%5E%7B%281%29%7D%3Dx%5E%7B%282%29%7D ,则称为凸集中的极点。
从几何上看，极点是凸集的边界的一点，包含该点且不以该点为端点的任意线段都不在这个凸集中。多面体的极点就是构成该多面体的超平面的交点。而圆上的每一点都是极点。
可以看出，有界集中任意一点都可以表示为极点的凸组合。但是对无界集却不成立，这时需要引入极方向的概念。
定义(极方向)：
设为闭凸集，为非零向量，如果对中的每一个，都有射线
https://www.zhihu.com/equation?tex=%5C%7Bx%2B%5Clambda+d%5Cmid+%5Clambda+%5Cgeq+0%5C%7D%5Csubset+S
则称为的方向。若不能表示为的两个不同方向的整的线性组合，则称为的极方向。
几何上，只有无界集才有方向。而极方向则是无界集的某个边界的方向向量。
加上极方向后，内的任意点可以用极点和极方向表示出来：
https://www.zhihu.com/equation?tex=x%3D%5Csum_%7Bj%3D1%7D%5E%7Bk%7D%5Clambda_jx%5E%7B%28j%29%7D%2B%5Csum_%7Bj%3D1%7D%5E%7Bl%7D%5Cmu_jd%5E%7B%28j%29%7D%5C%5C+%5Csum_%7Bj%3D1%7D%5Ek%5Clambda_j%3D1%5C%5C+%5Clambda_j%5Cgeq0%2C%5C+%5C+j%3D1%2C%5Cdots%2Ck%2C%5C%5C+%5Cmu_j%5Cgeq0%2C%5C+%5C+j%3D1%2C%5Cdots%2Cl
即凸可行域中的任意一点都可以表示为极点的凸组合+极方向的锥组合。
1.2 标准形式
一般的线性规划总是可以写成如下标准形式(通过添加松弛变量，将不等式约束变为等式约束，同时提升可行域的维度等方法)：
https://www.zhihu.com/equation?tex=%5Cbegin%7Bequation%7D+%5Cbegin%7Barray%7D%7Bll%7D++%5Ctext+%7B+min+%7D+%26+c%5E%7BT%7D+x+%5C%5C+%5Ctext+%7B+s.t.+%7D+%26+A+x+%3D+b%5C%5C+%5Ctext+%7B+%7D+%26+x%5Cgeq0+%5Cend%7Barray%7D+%5Cend%7Bequation%7D
其中 https://www.zhihu.com/equation?tex=A%5Cin+%5Cmathbb%7BR%7D%5E%7Bm%5Ctimes+n%7D_m , https://www.zhihu.com/equation?tex=x%2Cc%5Cin%5Cmathbb%7BR%7D%5En , https://www.zhihu.com/equation?tex=b%5Cin+%5Cmathbb%7BR%7D%5Em%2Cb%5Csucceq0
化成标准形式的目的是便于引出基本可行解的概念和性质，进而为单纯形方法做铺垫。
1.3 基本可行解
我们引入基本可行解的目的是为了便于缩小最优解的范围。通过前面的分析，我们已经知道线性规划的最优解一定在极点处取得，因此只需找出极点的集合，则最优解一定在这个集合中。但是极点是个很强的几何概念，虽有直观的优势，但是它对于数值计算来说不太方便。因此，我们从数值上引入基本可行解的概念，并证明它与极点等价。基本可行解的代数含义很明确，便于演算。于是，我们将求解线性规划问题转变为求解可行域的极点问题，进而转换为求解基本可行解的问题。
接下来先给出基本可行解的定义，然后给出定理说明基本可行解与极点等价。
1.3.1基本可行解的概念
设 https://www.zhihu.com/equation?tex=A%3D%28p_1%2Cp_2%2C%5Cdots%2Cp_n%29 ,已经假设矩阵的秩为，则必存在 https://www.zhihu.com/equation?tex=m+ 个线性无关的列向量。设这个列向量的下标组成的集合为；又设 是中以的元素为下标的列向量构成的 https://www.zhihu.com/equation?tex=m%5Ctimes+m 方阵。设有点 ,它的以中元素作为下标的分量构成的列向量为。称为基矩阵，称为一组基，各分量为基变量，中其他分量为非基变量。令非基变量全为，则显然有。此时，称为基本解(注意：基变量和非基变量在中的对应位置不变)。又若还满足不等式约束,称为基本可行解。(这段话比较绕，多读几遍)
至于基本解为什么要叫这个名字。个人认为“基”和线性空间里的“基”是类似的。还记得前面说的，紧的凸集中任何一个点都可以由极点线性表出吗？那么这里极点就相当于一个空间里的基(不严谨，但可以这样理解)，于是极点对应的解就称为基本解。
下面举一个例子来帮助理解基本可行解的概念：
<hr/>例：设一个标准线性规划的等式约束为 https://www.zhihu.com/equation?tex=Ax%3Db ，其中 https://www.zhihu.com/equation?tex=%5Cbegin%7Bequation%7D+A%3D%5Cleft%28%5Cbegin%7Barray%7D%7Blll%7D+1+%26+0+%26+1++%5C%5C+0+%26+1+%26+1++%5Cend%7Barray%7D%5Cright%29+%5Cend%7Bequation%7D , https://www.zhihu.com/equation?tex=%5Cbegin%7Bequation%7D+b%3D%5Cleft%28%5Cbegin%7Barray%7D%7Bl%7D+1++%5C%5C+0++%5Cend%7Barray%7D%5Cright%29+%5Cend%7Bequation%7D ,求解该线性规划的基本可行解。
解 令 https://www.zhihu.com/equation?tex=A%3D%28p_1%2Cp_2%2Cp_3%29 。
[*]令 https://www.zhihu.com/equation?tex=%5Cbegin%7Bequation%7D+B%3D%28p_1%2Cp_2%29%3D%5Cleft%28%5Cbegin%7Barray%7D%7Bll%7D+1+%26+0%5C%5C+0+%26+1+%5Cend%7Barray%7D%5Cright%29+%5Cend%7Bequation%7D , 解出 ，则
[*]令 https://www.zhihu.com/equation?tex=%5Cbegin%7Bequation%7D+B%3D%28p_1%2Cp_3%29%3D%5Cleft%28%5Cbegin%7Barray%7D%7Bll%7D+1+%26+1%5C%5C+0+%26+1+%5Cend%7Barray%7D%5Cright%29+%5Cend%7Bequation%7D, 解出 ，则
[*]令 https://www.zhihu.com/equation?tex=%5Cbegin%7Bequation%7D+B%3D%28p_2%2Cp_3%29%3D%5Cleft%28%5Cbegin%7Barray%7D%7Bll%7D+0+%26+1%5C%5C+1+%26+1+%5Cend%7Barray%7D%5Cright%29+%5Cend%7Bequation%7D, 解出https://www.zhihu.com/equation?tex=x_B%3DB%5E%7B-1%7Db%3D%5Cbegin%7Bequation%7D+%5Cleft%28%5Cbegin%7Barray%7D%7Bl%7D+-1+%5C%5C+1+%5Cend%7Barray%7D%5Cright%29+%5Cend%7Bequation%7D ，则 https://www.zhihu.com/equation?tex=%5Cbegin%7Bequation%7D+x%3D%5Cleft%28%5Cbegin%7Barray%7D%7Br%7D+0%5C%5C+-1%5C%5C+1+%5Cend%7Barray%7D%5Cright%29+%5Cend%7Bequation%7D,不满足不等式约束，因此不是基本可行解。
所以本题中线性规划的基本可行解为。
<hr/>几点发现：
[*]根据基本可行解的概念，我们可以知道基本可行解最多可以有个，因为从 https://www.zhihu.com/equation?tex=n 个列向量中选取个作为基的可能的选法有个。
[*]线性规划的基本可行解只与系数矩阵和偏置有关。
[*]基本可行解中正分量的个数不超过系数矩阵的秩。
1.3.2 极点集与基本可行解集的等价性
定理：令 https://www.zhihu.com/equation?tex=K%3D%5C%7Bx%7CAx%3Db%2Cx%5Csucceq+0%5C%7D ,是矩阵，秩为。则 https://www.zhihu.com/equation?tex=K 的极点集与 https://www.zhihu.com/equation?tex=Ax%3Db%2Cx%5Csucceq+0 的基本可行解等价。
这里不给出严格证明，只描述证明思路：分别证明充分性和必要性。
[*]已知是极点，证明是基本可行解。设有个正分量，先证明的正分量对应的中的列向量线性无关，由此说明的正分量个数小于等于。然后其他个列向量与这个列向量组成基矩阵，相应的拆分为和其他非基变量(都是0)。由此可得，因此是基本可行解。
[*]已知是基本可行解，证明是极点。设分别为可行解，且是它们的凸组合。因为有个分量为，则对应的分量也必须为0(因为正数的凸组合必大于0)。再根据https://www.zhihu.com/equation?tex=Ax%5E%7B%281%29%7D%3Db%2CAx%5E%7B%282%29%7D%3Db%2C得到https://www.zhihu.com/equation?tex=x_B%5E%7B%281%29%7D%3Dx_B%5E%7B%282%29%7D%3DB%5E%7B-1%7Db%3Dx_B,从而 https://www.zhihu.com/equation?tex=x%3Dx%5E%7B%281%29%7D%3Dx%5E%7B%282%29%7D 。因此是极点。
有了这个定理，我们可以将求解极点问题转换为求解基本可行解问题。然后再基本可行解集中寻找最优解。即，线性规划问题的求解，可归结为求最优基本可行解。这也正是单纯形方法的基本出发点。
1.3.3 基本可行解的存在问题
直接给出定理而不加证明。
定理：如果 https://www.zhihu.com/equation?tex=Ax%3Db%2Cx%5Csucceq0 有可行解，则一定存在基本可行解。
2 单纯形方法
2.1 单纯形方法的概念和原理
上文已经探讨了线性规划最优解与基本可行集的关系，即如果线性规划具有最优解，它一定能在基本可行解中找到。我们可以先找到所有的基本可行解，然后代入目标函数，寻找最大值。然而，一个的系数矩阵可能有多达个基本可行解，如果 https://www.zhihu.com/equation?tex=n%3E%3Em ，那么时间复杂度会很高。所以应该改良这种暴力算法，采用一种更高效的方法。这就是成熟的单纯形法(Simplex Algorithm or Simplex Method)。
这部分内容不打算按照课本那样用定理和公式来解释单纯形法(但是重要的推导还是有必要的)，而是着重于剖析其原理。由于“基本可行解”和“极点”的定价性，下文可能将二者混用，以便更好地理解。
首先介绍单纯形法的思想：相对于暴力算法，单纯形法从一个基本可行解切换到另一个基本可行解时，不是盲目的切换。首先，它只会沿着边(edge)切换到与它相邻的极点。其次，它只会切换到能改良优化目标的极点。重复这样的做法，直到再也找不到能改良优化目标的相邻极点时，此刻所在的极点就是本次线性规划的最优解。这种做法的合理性基于以下事实：若一个极点不是线性规划的最优解，则它的一个相邻极点比它更优。
那什么样的相邻极点是更好的呢？不妨设此时所在的极点是，它的一个相邻极点是。则如果 https://www.zhihu.com/equation?tex=x%5E%7B%281%29%7D-x%5E%7B%280%29%7D 的方向与目标函数的负梯度方向成锐角，那么一定比更优(这是显然的)。用数学公式描述为 https://www.zhihu.com/equation?tex=%5Cnabla+f%5ET%28x%5E%7B%281%29%7D-x%5E%7B%280%29%7D%29%3C0 。
我们就以该不等式为出发点探究应满足什么条件。
首先，规定一些符号。从 https://www.zhihu.com/equation?tex=x%5E%7B%280%29%7D%5Cin+%5Cmathbb%7BR%5En%7D 中抽取其所有基变量组成维向量https://www.zhihu.com/equation?tex=x%5E%7B%280%29%7D_B+%5Cin+%5Cmathbb%7BR%5Em%7D ,剩余的非基变量组成 https://www.zhihu.com/equation?tex=n-m 维向量 https://www.zhihu.com/equation?tex=x%5E%7B%280%29%7D_N%3D0_%7Bn-m%7D%5Cin+%5Cmathbb%7BR%7D%5E%7Bn-m%7D （基本可行解的非基变量都是零）。类似地，分别从 https://www.zhihu.com/equation?tex=c%5ET%5Cin+%5Cmathbb%7BR%5En%7D%2CA%5Cin%5Cmathbb%7BR%7D%5E%7Bm%5Ctimes+n%7D 中抽取出 https://www.zhihu.com/equation?tex=c%5ET_B%5Cin+%5Cmathbb%7BR%5Em%7D%2Cc%5ET_N%5Cin+%5Cmathbb%7BR%5E%7Bm-n%7D%7D%2CB%5Cin+%5Cmathbb%7BR%7D%5E%7Bm%5Ctimes+m%7D%2CN%5Cin+%5Cmathbb%7BR%7D%5E%7Bm%5Ctimes+%28n-m%29%7D 。然后从中抽取与相同位置的变量https://www.zhihu.com/equation?tex=x%5E%7B%281%29%7D_B+%5Cin+%5Cmathbb%7BR%5Em%7D,https://www.zhihu.com/equation?tex=x%5E%7B%281%29%7D_N%5Cin+%5Cmathbb%7BR%7D%5E%7Bn-m%7D 。
强调一下， https://www.zhihu.com/equation?tex=x%5E%7B%281%29%7D_B 不是代表的基变量组成的向量，它只是代表和 https://www.zhihu.com/equation?tex=x%5E%7B%280%29%7D_B 位置而已，同样也不是零向量(后面会说它的含义)。
下面正式开始推导。
https://www.zhihu.com/equation?tex=%5Cbegin%7Bequation%7D+%5Cbegin%7Bsplit%7D+%26%5Cnabla++f%5ET%28x%5E%7B%281%29%7D-x%5E%7B%280%29%7D%29+%5C%5C+%26+%3Dc%5ETx%5E%7B%281%29%7D-c%5ETx%5E%7B%280%29%7D%5C%5C+%26+%3Dc%5ET_Bx%5E%7B%281%29%7D_B%2Bc%5ET_Nx%5E%7B%281%29%7D_N-%28c%5ET_Bx%5E%7B%280%29%7D_B%2Bc%5ET_Nx%5E%7B%280%29%7D_N%29%5C%5C+%26+%3D%28+c%5ET_BB%5E%7B-1%7Db-c%5ET_BB%5E%7B-1%7DNx_N%5E%7B%281%29%7D%2Bc%5ET_Nx%5E%7B%281%29%7D_N%29-%28c%5ET_BB%5E%7B-1%7Db%29%5C%5C+%26%3D%28-c%5ET_BB%5E%7B-1%7DN%2Bc%5ET_N%29x%5E%7B%281%29%7D_N%3C0%5C%5C+%5Ciff%26+%28c%5ET_BB%5E%7B-1%7DN-c%5ET_N%29x%5E%7B%281%29%7D_N%3E0+%5Cend%7Bsplit%7D+%5Cend%7Bequation%7D
注意是任取的。也就是说，只要满足就说明还有优化空间,即从切换到；否则，意味着就是该问题的最优解。
问题转变为我们从当前极点，挑选满足不等式的相邻极点，然后切换到该极点就完成了一次优化的迭代。那如果多个极点满足该条件呢？理论上我们应该取 https://www.zhihu.com/equation?tex=%28c%5ET_BB%5E%7B-1%7DN-c%5ET_N%29x%5E%7B%281%29%7D_N 最大的那个。可是，这要求要找出当前极点的所有相邻极点，也需要很大的计算量(虽然比暴力解法确实进步了)。所以，可以退而求其次，取使https://www.zhihu.com/equation?tex=%28c%5ET_BB%5E%7B-1%7DN-c%5ET_N%29 最大的就行，因为这个是不需要其他极点就能计算的。
在继续讨论之前，我们给出的含义。我们知道当从一个极点移动到另一个极点时，非基变量中有且仅有一个会从0增加到一个正值。由于 https://www.zhihu.com/equation?tex=x%5E%7B%280%29%7D%2Cx%5E%7B%281%29%7D 是相邻极点，https://www.zhihu.com/equation?tex=x%5E%7B%280%29%7D_N是0向量，所以中有一个元素为正值，其余全是0。
现在来探究一下意味着什么。
将不等式写成分量形式： https://www.zhihu.com/equation?tex=%5Csum_%7Bj%5Cin+R%7D%28c%5ET_BB%5E%7B-1%7Dp_j-c_j%29x_j%3E0 ，其中 https://www.zhihu.com/equation?tex=R 是非基变量的下标集合。再设中不为0的元素下标为，则不等式可进一步化简为 https://www.zhihu.com/equation?tex=%28c%5ET_BB%5E%7B-1%7Dp_k-c_k%29%3E0%2Ck%5Cin+R 。令 https://www.zhihu.com/equation?tex=%5Csigma_k%3Dc%5ETB%5E%7B-1%7Dp_k-c_k ,称为判别数。
所以这个不等式的意思其实是：如果当前所在极点存在某个属于非基变量下标集合的下标,它对应的各参数满足这个不等式，那么我们可以让成为新的基矩阵的元素，这个基矩阵对应的基本可行解优于当前可行解。
那如果有多个下标满足该不等式呢？当然是选取https://www.zhihu.com/equation?tex=%5Cmax%5C%7B%5Csigma_k%3E0%2Ck%5Cin+R%5C%7D 。注意，我们没有计算所有的相邻极点，而是根据的特殊结构，计算出所有的相邻极点对应的判别数 https://www.zhihu.com/equation?tex=%5Csigma_k ，再取它们中最大的对应的下标，作为新入基列的下标。有列入基，就有列出基，因为基矩阵只容纳个列。那应该怎么选择出基的那一列呢？
为了便于说明，先将问题作一个化简：我们令 https://www.zhihu.com/equation?tex=B%3DI 。这总是可以通过行初等变换做到，相应的 https://www.zhihu.com/equation?tex=N%2Cb 也同时做一样的行初等变换以保持解不变。这样变换后的的值就是基变量的取值（如果经过行初等变换后有负的元素，那就说明这个基矩阵对应的基本解不可行，应该重新寻找基矩阵）。当有新列入基时，我们将该列变换为中的某一列，即只有一个元素为1，其余元素都为0；然后，与新列重复的那一列出基。那么我们应该将新列的哪个元素(主元)变换为1呢？设新列的第个元素为，取对应的那个下标。因为只有这样才能保证在行初等变换时，不会把中的元素消为负数。还有一个问题是，如果新入基列中所有元素都小于等于0呢？这样的话，是不存在的(因为 https://www.zhihu.com/equation?tex=b_r 必定非负)。实际上，出现了这样情况说明该线性规划问题无最优解(目标函数可以任意小)。
2.2 单纯形方法的步骤
介绍完单纯形方法的原理，步骤也就呼之欲出了。这里简要做一个总结。
[*]将线性规划问题转换为标准形式
[*]在系数矩阵中寻找一个基矩阵，并通过行初等变换将它转换为单位矩阵。如果此时 https://www.zhihu.com/equation?tex=b%5Cnsucceq0 ，则重新寻找基矩阵并转换为单位阵，直到 https://www.zhihu.com/equation?tex=b%5Csucceq0 。
[*]计算 https://www.zhihu.com/equation?tex=N 中每一列对应的判别数 https://www.zhihu.com/equation?tex=%5Csigma_j%3Dc%5ETB%5E%7B-1%7Dp_j-c_j%3Dc%5ETp_j-c_j ，然后取 https://www.zhihu.com/equation?tex=%5Csigma_k%3D%5Cmax_j%5C%7B%5Csigma_j%5C%7D 。如果 https://www.zhihu.com/equation?tex=%5Csigma_k%5Cleq0 ，则当前基本可行解就是最优解，算法停止。否则，若 https://www.zhihu.com/equation?tex=p_k%5Cpreceq0 ，则说明线性规划无最优解，算法停止。否则，选择作为入基列。
[*]计算 https://www.zhihu.com/equation?tex=%5Cmin_r%5C%7B%5Cfrac%7Bb_r%7D%7Bp_%7Bkr%7D%7D%3E0%5C%7D 对应的，将作为主元，通过行初等变换将主元化为1，其余元素化为0，实际完成了入基。返回步骤3。
PS: 操作过程中，一定要注意各参数的对应。比如如果基矩阵 https://www.zhihu.com/equation?tex=I%3D%28p_2%2Cp_5%2Cp_1%29 ，那么相应的 https://www.zhihu.com/equation?tex=x_B%5ET%3D%28x_2%2Cx_5%2Cx_1%29%2Cc%5ET_B%3D%28c_2%2Cc_5%2Cc_1%29 ，而不是简单得按照顺序取 https://www.zhihu.com/equation?tex=x%5ET_B%3D%28x_1%2Cx_2%2Cx_5%29 等等。
2.3 两阶段法
上面给出了单纯形方法的原理和步骤，对线性规划问题给出了一个成熟优雅的方案。但是，还是有一点小瑕疵，那就是单纯形方法的第一步：寻找初始的基本可行解。如果系数矩阵中存在能组成单位矩阵的列向量，那就很完美，我们已经找到了一个基本可行解。但若不存在单位矩阵呢？一般情况下，很难直接看出哪些列是线性无关的。因此 ，我们需要人为地构造出一个单位矩阵来提供初始的基本可行解。两阶段法和大M法提供了这样的功能。本小节简要介绍两阶段法；下一节简要介绍大M法。
2.3.1 两阶段法的思想
在一个标准线性规划问题中，一般不存在现成的单位矩阵，两阶段法通过引入人工变量 https://www.zhihu.com/equation?tex=0%5Cpreceq+x_a%5Cin%5Cmathbb%7BR%7D%5Em ，将的每个元素添加到每个方程中，等价于在右端增加了一个单位向量。但是这个做法已经破坏了方程组的结构，没关系，后续的处理(即第一阶段)会讲人工变量逼出基变量，从而消除这个不好影响。
2.3.2 第一阶段
求解一下线性优化问题，以消除人工变量的影响：
https://www.zhihu.com/equation?tex=%5Cbegin%7Bequation%7D+%5Cbegin%7Barray%7D%7Bll%7D++%5Ctext+%7B+min+%7D+%26+e%5E%7BT%7D+x_a+%5C%5C+%5Ctext+%7B+s.t.+%7D+%26+A+x%2Bx_a+%3D+b%5C%5C+%5Ctext+%7B+%7D+%26+x%5Csucceq0%5C%5C%26x_a%5Csucceq0+%5Cend%7Barray%7D+%5Cend%7Bequation%7D
其中 https://www.zhihu.com/equation?tex=e%5ET%3D%281%2C1%2C%5Cdots%2C1%29 。
因为有初始基本可行解，且目标函数有下届，所以必存在最优基本可行解，设为 https://www.zhihu.com/equation?tex=%5Cbegin%7Bequation%7D+%5Cbegin%7Bsplit%7D+%5Cleft%5B+%5Cbegin%7Barray%7D%7Bc%7D+x%5C%5C+x_a+%5Cend%7Barray%7D+%5Cright%5D+%5Cend%7Bsplit%7D+%5Cend%7Bequation%7D 。此时，有三种情况：
[*] ，则原线性规划无可行解。因为若原线性规划有可行解，则 https://www.zhihu.com/equation?tex=%5Cbegin%7Bequation%7D+%5Cbegin%7Bsplit%7D+%5Cleft%5B+%5Cbegin%7Barray%7D%7Bc%7D+x%5C%5C+x_a+%5Cend%7Barray%7D+%5Cright%5D%3D%5Cleft%5B+%5Cbegin%7Barray%7D%7Bc%7D+%5Chat%7Bx%7D%5C%5C+0+%5Cend%7Barray%7D+%5Cright%5D+%5Cend%7Bsplit%7D+%5Cend%7Bequation%7D 是这个线性规划的可行解，则目标函数可以取0，矛盾。
[*] 且的分量都是非基变量。则个基变量都是原线性规划的基变量。
[*] 且的某些分量是基变量。这时可以使用主元消去法，将这些元素离基，得到不含人工变量的基变量。
2.3.3 第二阶段
用第一阶段得到的基，求解原线性规划问题。
2.4 大M法
2.4.1 大M法简要介绍
大M法和两阶段法类似，都是通过引入人工变量构造单位矩阵，然后迫使人工变量离基。但大M法只需要一个阶段，它的思想是在目标函数上加上很大的倍数M的人工变量的惩罚项，在优化过程中使人工变量必须为0。大M法其实是两阶段法中两个阶段的结合。
大M法求解以下线性规划问题。
https://www.zhihu.com/equation?tex=%5Cbegin%7Bequation%7D+%5Cbegin%7Barray%7D%7Bll%7D++%5Ctext+%7B+min+%7D+%26+c%5ETx%2BMe%5E%7BT%7D+x_a+%5C%5C+%5Ctext+%7B+s.t.+%7D+%26+A+x%2Bx_a+%3D+b%5C%5C+%5Ctext+%7B+%7D+%26+x%5Csucceq0%5C%5C%26x_a%5Csucceq0+%5Cend%7Barray%7D+%5Cend%7Bequation%7D
其结果必是下面三种情况之一：
[*]达到线性规划最优解，且,则此时就是原线性规划最优解。
[*]达到线性规划最优解，且，则原线性规划问题无可行解。
[*]不存在有限最优值，则原线性规划问题无界或无可行解。
参考
[*]^https://en.wikipedia.org/w/index.php?title=Linear_programming&oldid=1054533005
页:
[1]