单纯形法

作为一名数学系的学生，都没有写过关于数学的总结，正上运筹课，学到单纯形法，所以就把他的求解过程写一下。

我们都知道，一个线性规划问题，求解的办法有很多种，我们应用类似枚举法可以求解基本可行解的个数≤Cm,n个时的题目，但是如果可行解个数增大，我们就面临必须快速解决下面三个问题：

1.如何快速判别当前的基本可行解是否已经达到最优解。

2.若当前解不是最优解，如果去找一个改善了的基本可行解

3.如何得到一个初始的基本可行解。

解决方法：

1.我们首先将线性规划的约束方程变为标准形。即将小于等于的式子添加松弛变量将其变为等式，将大于等于的式子添加剩余变量将其变为等式。

2.将目标函数变为添加松弛变量，剩余变量的目标函数。（在有剩余变量的线性规划问题中，因为系数为负，我们还需要添加人工变量，即添加－M（M为一个很大的整数））。

3.建立初始的单纯形表   

  1.表格第一行，分别为目标函数变量的所有系数

  2.表格第二行，left部分，有三项Cb,Xb,b 。right部分，是所有变量（包括基本变量，剩余变量，松弛变量，人工变量）。

3.表格最后一行，为目标函数-Z。Z的计算：变量的目标函数系数－Cb*约束函数变量的系数，然后求和。

4.中间几行，right部分分别为各约束函数的系数。left部分的Xb的确定，是根据right部分的出现单位矩阵的系数开始记录其变量。Cb是Xb的目标函数中的系数。b为当所有变量（除Xb 变量）为0，算出的结果。

4.我们选取Z中最大的那个变量为进基，然用b列的值与进基系数做比值，选取最小的一个作为出基变量。

5.将进基变量的系数变为1，然后将其余变量，通过行向量的转换为0，其余变量系数也发生改变。

6.循环上述4.5过程，直到所有的z值全部变为负数，这样我们可以确定，得到最优解。此时的Xb中变量全部转换为基本变量，b中的数为最优解系数，Z为最优解。

人工变量：要使我们的目标函数实现最大化，所以人工变量必须从基变量中迅速换出去，否则目标函数不能实现最大化。

求解有两种方法：最小化求解和最大化求解

它们有一定的区别，上述方法用于最大化求解。

最小化问题求解：进基选择判别数为负最小的那一个，在所有判别数大于等于0时达到最优解

最大化问题求解：进基变量选取判别数为正的最大的那一个数，在所有判别数小于等于0达到最优解

共同点：离基变量均取比值最小的