概念和定义
基本解、基变量、非基变量
在m*n（m个方程、n变量）方程组中，令n-m个变量为0，剩下m*m方程组，如果有唯一解，解——>基本解、n-m个0变量——>非基变量、m个变量——>基变量。
单纯形方法
解决$\leq$方程组问题，增加非负松弛变量$s_i$，然后使用单纯形表解决。
解惑
可行性条件：为什么是最小非负比？
正如“可行性条件”之名，如果移动最小非负比，不会使得原约束被违背，但是具体是为什么呢？
？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？
大M方法
解惑
对于存在$\geq , =$的问题，即变为等式时，存在有的式子没有“松弛变量”（如果是=，没有增加变量，如果是$\geq$，增加的$-s_i$，是盈余变量），这些式子里要增加人工变量（这一步其实是破坏了原约束，因此最终求出来最优解人工变量必须是0），并在目标函数增加惩罚（max时，$-MR_1$，min时$+MR_1$，其中M必须数量级大于其他变量，使得最后取最优的时候人工变量一定为0）。
为什么有松弛变量的式子不需要增加人工约束？
首先要明白，增加人工变量实际上是为了找到一组初始解，为此不惜破坏原约束，退而求其次用惩罚来“挽救”。而找初始解这一过程又和单纯形方法的本质有关，本质就是松弛变量作为初始的一组基变量，一定能找到一组初始解：
通过增加松弛变量，等价地转换为等式。可以通过让松弛变量直接等于等号右边的值找到初始的一组解（其实就是让非基变量为0，对应就是式子里的松弛变量直接=右边），并且这样做一定能找到一个初始解：$x_1 + 2x_2 \leq 2$ 转换成 $x_1 + 2x_2 +s_1 = 2,~ s_1 \geq 0$，只需要让$s_1=2$，剩下两个变量一定满足约束。
但是如果是盈余变量就不一定了：$x_1 + 2x_2 \geq 2$，先要转换等式：$x_1+2x_2-s_1 = 2,~s_1\geq 0$， 这时候显然不能通过取 $\pmb{-s_1 = 2}$ 得到初始解！ 所以要有人工变量（系数为正！），为了使得对约束的破坏不发生（本质是希望尽量保证等价），所以有了$M$的惩罚项。
在接下来使用近似的单纯形表方法时，需要注意：
为什么要让目标变量中基变量系数为0？
上图中的说法确实是对的，z行的右侧值有问题，但本质是希望基变量的系数保持为0，这样才能使得每次进基、出基操作，让原来系数能使得效果更加的“非基变量”从0变成可以取值（使得我们得到更优答案），同时原来的基变量因为系数为0，他出去（本质上是变成0）不会使答案变差！（因为在z中就没他事，变不变无所谓）。
大M方法的过程
- 化不等式为等式（松弛、盈余）
- 在无松弛变量的等式增加人工变量，同时对目标函数增加相应大M惩罚
- 每行的松弛变量、人工变量作为基变量，画单纯形表
- 让单纯形表z行的人工变量系数归0（消元）
- 求解，如果没有可行解：人工变量取不到0——结果为有1个及以上人工变量非0；否则就是最优解。
两阶段方法
如果您喜欢此博客或发现它对您有用，则欢迎对此发表评论。 也欢迎您共享此博客，以便更多人可以参与。 如果博客中使用的图像侵犯了您的版权，请与作者联系以将其删除。 谢谢 ！