线性规划单纯形法

出处：按学科分类—经济湖北人民出版社《企业管理公式辞典》第342页（2290字）

一种求解线性规划模型的通用算法，它是从满足线性规划所有结构约束条件的可行方案中，用替代法则逐步找到使目标函数最优的方案的计算方法和步骤。此法于1947年由美国捷格首先创立(单纯形是数学术语，在n维空间内有n+1个点组成的几何图形称单纯形)。求解线性规划问题，一般均可用单纯形法，单纯形法通常可用单纯形表进行运算。单纯形表的构造形式如下：

用单纯形表求解线性规划问题的步骤如下：

第一步：将待求解的线性规划模型转换成标准形式。用上述单纯形表进行运算，线性规划模型必须转变成满足下列条件的标准形式：

(1)目标函数取MAX化形式；

(2)全部约束条件改写成等式形式(通过引入附加变量)；

(3)全部约束条件右端项b₁≥0；

(4)约束条件系数矩阵中(A阵)，有一个阶数和约束条件个数相同的单位子矩阵；

(5)全部变量(包括附加变量)均应非负(即变量≥0)。

第二步：填充初始单纯形表，即按模型规模填写X行，C₁行，a_1j系数表，右边常数列b₁。

第三步：按初始基本解，分清基变量与非基变量，填好C₁列及X_B列(a_ij系数矩阵中单位子矩阵对应的变量即为基变量X_B)。

第四步：计算现行解的目标函数值及检验数。

检验数：

第五步：判断解的最优性。

(1)若检验数行中所有Z_j－C_j≥0，且没有人工变量在基中取正值，这时问题取得最优解，终止运算。基变量对应的b列值为基变量解的取值，非基变量为零(若全部Z_j－C_j≥0，人工变量在基中取正值，说明原问题无可行解，运算亦终止)。

(2)若检验数行中存在Z_j－C_j＜0，说明现行解应当改进，转入下一步(若对任一Z_j－C_j＜0的检验数，它所对应的a_1j系数中列向量没有正元素，那么原问题为无界解，运算应终止)。

第六步：选标准列(或称主列)，确定进基变量。在Z_j－C_j＜0的诸元素中，择其绝对值最大检验数所在列用*作记，称标准列，该列所对应非基。变量即为进基变量。

第七步：选标准行(或主行)，确定出基变量。将标准列中对应的正系数a_ij*除同行右端常数b₁，填入θ列：选择θ₁值最小行，

用*作记，称标准行，该行所对应的基变量即为出基变量。

第八步：作变量代换，进行迭代运算，得到新的单纯形表。

以标准行与标准列交叉处元素a_1*j*为枢轴元素(或称主元)，X_j*为进基变量，X_1*为出基变量，作变量更换(基变量及其在目标中的系数同时更换)。作变量代换后，用矩阵的初等变换方法，将枢轴元素变为1，而枢轴元素对应列中其他元素都变为0(初等变换运算包括Z_j－C_j行，b_i列同时进行，在这个运算过程中，表中其他元素也发生了相应变化)。得到新的单纯形表后，转入第五步。

迭代运算过程(用矩阵初等变换求解新表的运算过程)，可归结成如下计算：

(1)新表中主元列(j^*)各元素，除主元素a_1*j*是1以外，其余全部为

(2)新表中主元行(i^*)各元素，为旧表中元素乘主元素倒数得到：