设决策变量为，求解以下优化问题

线性规划标准形式为

设是秩为的约束矩阵中的一个阶满秩子方阵，称的一个基。中个线性无关的列向量称为基向量。变量中与之对应的个分量称为基变量，其余的分量称为非基变量。

令所有非基变量取值为零，得到解称为基本解。当基本解非负时，称为基本可行解，此时对应的基称为可行基。

1. 给出初始基本可行解
2. 计算非基变量的检验数
3. 若存在检验数大于0，则选检验数最大的基，用最小比值法确定传出的基变量
4. 所有非基变量检验数都为负，则已经达到最优解。若存在检验数为正，但是对应列系数都为负，则无有限最优解。

添加人工变量，通过在迭代过程中把人工变量换出可行基获得原问题的可行基。

1. 大M法。把目标函数换成
2. 两阶段法。先把目标函数设为，迭代到该目标函数等于零时再用原目标函数。