单纯形法

---

求解任何有限个决策变量的线性规划问题的一般方法。

它是从线性规划问题的一个初始基本可行解开始，经过反复迭代，逐步改善基本可行解，直到求得最优解(或判断无解)的迭代计算方法。其理论依据是，对一个线性规划问题，目标函数如果有最大(或最小)值的话，最优解必定在约束条件所确定的凸集上某个顶点实现。用单纯形法求解线性规划问题时，首先应线性规划问题数学模型标准化，列出初始单纯形表，并根据约束条件求得一个初始基本可行解；然后，经过检验，初始基本可行解若不是最优解，则进行第一次换基迭代，在初始基本可行解基础上，对基变量作适当变换，再求出一个新的基本可行解，再进行检验，如此反复迭代下去。如果某一步求出基本可行解之后，再也找不到比其更好的基本可行解，它便是最优解。由于单纯形法的整个迭代计算工作量较大，一般用计算机完成。