给定标准型线性规划（LP）：

在没有特别说明的情况下，（LP）满足下列条件：

m个等式约束相互独立.

我们已经知悉，求（LP）的最优解（若存在），只要在基本可行解中搜索就可，而基本解的个数至多个.但是，用枚举法从基本解中找出全部基本可行解，再从中寻求最优解，这个方法是不实用的.例如，n＝60，m＝30，，即使电子计算机能以10－6秒处理每个IB取法的速度进行工作，那么，要将全部取法处理完也要3 000年.何况其中有些指标集IB对应的矩阵B未必是基，或者相应的基本解不是可行解而使计算徒劳.同时，在这种枚举法中，目标函数是被动的，只有在所有的基本可行解都被确定后才能比较出那一个基本可行解的目标函数值最优.

G·B·丹捷格（G.B.Dantzig）在1947年提出了求解线性规划问题的方法——单纯形法.单纯形法的产生，使线性规划在理论上渐趋成熟，在实际中的应用日益广泛与深入，特别是电子计算机使用单纯形法能处理大规模的线性规划，从而使线性规划在现代管理决策中适用的领域更为广泛.

单纯形法的原理是：如果（LP）的可行域K不是空集，我们从K的某一顶点X0出发，判别它是否为最优解？若不是，沿着边界找它邻近的另一个顶点，它应比原来的顶点优，看它是否为最优解？若不是，再沿着边界找它邻近的顶点.通过逐次迭代，直至找出最优解（参看图1－6）.

按此原理，单纯形法的基本步骤是：(www.daowen.com)

（1）求（LP）的初始基本可行解X0，并将（LP）的有关信息制成表格（称为单纯形表）.

（2）判别X0是否为最优解？为此，需要给出一个基本可行解是否为最优解的判别准则.

图1－6

（3）若X0不是最优解，则应另求基本可行解X′，且使CTX′＜CTX0（至少CTX′≤CTX0）.同时，我们由X0相应的单纯形表给出X′相应的单纯形表.

（4）若X′不是最优解时，则视X′为X0，重复上述步骤，直至（LP）求得最优解或判定f在K内无下界.

下面我们逐一来解决各个问题，在此基础上建立单纯形法.