单纯形法

---

求解线性规划的一个行之有效的通用的算法。

这种方法最初是在1947年由丹西格(G．B．Dantzig)提出，其大概过程是：

第一步，将标准形式的线性方程组化成一个可行正规等价线性方程组，即可得到一个基础可行解，称为初始基础可行解；

第二步，判别初始基础可行解是否为最优解，若是，则停止运算。否则，进行第三步。

第三步，从初始基础可行解出发，找一个与它“相邻”的基础可行解，但要使目标函数值下降(设问题是求目标函数的极小值)，或者至少不增大。然后又回到第二步，如此循环直至求得一个最优解为止。