美国数学家G.B. Dantzig (丹捷格)发明了一种“单纯形法”的代数算法，尤其是方便于计算机运算。这是运筹学史上最辉煌的阶段。

与单纯形法有关的三条定理：

　　

翻译一下就是：

• 若某个基本可行解对应的检验向量<0，那么这个基本可行解就是最优的。

• 若某个基本可行解对应的检验向量=0，则有无穷多个最优解。

• 若某个基本可行解对应的检验向量>0，并且系数(约束条件)小于0，无解。

CN$C_N$——非基变量系数

CB$C_B$——基变量系数

B——基，即线性无关向量组R(A)=R(B)

N——非基向量组

 

单纯形法计算步骤： 

1. 将线性规划问题化成标准型 (引入松弛变量)

2. 找出或构造一个m阶单位矩阵作为初始可行基，建立初始单纯形表。

3. 计算各非基变量的检验数σj=cj−zj${\sigma }_j=c_j-z_j$ 若所有检验数≤0，则问题已得到最优解，停止计算。否则，转入下一步。(检验数)

4. 在大于0的检验数中，若某个检验数对应的系数列向量≤ 0，则此问题是无界解，停止计算，否则转入下步。

5. 根据max$max$（检验数j$j$ | 检验数j$j$>0）=检验数k的原则，确定为换入变量(进基变量) 再按最小比值法则(biaik$\frac{b_i}{a_{ik}}$，&aik$a_{ik}$>0)确定换出变量，建立新的单纯形表，此时的基变量中xk$x_k$代替的换出变量的位置。

6. 以aik$a_{ik}$为主元素进行迭代，把xk$x_k$所对应的列向量变为单位列向量，即aik$a_{ik}$变为1 同列中其他元素变为0，继续计算各非基变量的检验数，进行第三步。