线性规划算法简述

为便于讨论一般解法，常将线性规划问题的约束条件归结为一组线性方程和一组非负性限制条件，并且将目标函数统一成求最大值，即是说，将线性规划问题的数学模型化为如下形式：

其中，b_i≥0。式（3-49）称为线性规划问题的标准形式。将式（3-49）写为如下简洁的形式：

其中

并且B可逆。称B为基矩阵；x_B为基变量；x_N为非基变量。

1.基本思想

线性规划问题的可行域是多面体凸集，其最优值如果存在，必在该凸集的某顶点处达到。顶点所对应的可行解称为基本可行解。单纯形法的基本思想是：先找出一个基本可行解，对它进行鉴别，看是否是最优解；若不是，则按照一定法则转换到另一改进的基本可行解，再鉴别；若仍不是，则再转换，按此重复进行。因基本可行解的个数有限，故经有限次转换必能得出问题的最优解。如果问题无最优解也可用此法判别。单纯形法的一般解题步骤可归纳如下：

（1）把线性规划问题的约束方程组化成标准形式，找出基本可行解作为初始基本可行解；

（2）若基本可行解不存在，即约束条件有矛盾，则问题无解；

（3）若基本可行解存在，把初始基本可行解作为起点，根据最优性条件和可行性条件，引入非基变量取代某一基变量，找出目标函数值更优的另一基本可行解；

（4）按步骤（3）进行迭代，直到对应检验数满足最优性条件（这时目标函数值不能再改善），即得到问题的最优解。若迭代过程中发现问题的目标函数值无界，则终止迭代。

2.预处理

若不具有式（3-49）的形式，则做如下处理。

（1）含约束x_j≤0的情况

令x_j=-x′_j。最终要根据最优解x′_j^*确定x_j^*=-x′_j^*。

（2）对x_i，既无约束x_i≤0，也无约束x_i≥0的情况

引入两个新变量{x′_i，x″_i}，可令

x_i=x′_i-x″_i，x′_i≥0，x″_i≥0 （3-52）最终要根据最优解{x_i′^*，x″_i^*}确定x_i^*=x′_i^*-x″_i^*。

（3）上下界的处理

如果只有下界，要求，则令。如果只有上界，要求，则令，则令，并在优化中加入如下不等式约束：

以上做了变量替换。也可以不做变量替换，直接用不等式约束代替上、下界。

（4）不等式约束的处理

不等式约束

等价于约束条件

而不等式约束

等价于约束条件

这里增添的变量称为辅助变量。

（5）b_i＜0的情况

用替换。

3.优化求解算法

（1）基本公式

由于Ax=b可以写为

故得到

记N为非基变量的下标集合。将得到(www.xing528.com)

称C_N-C_BB^-1N=[σ₁，σ₂，…，σ_n-m]为非基变量x_N的检验向量，它的各个分量称为检验数。

显然，若c_j-C_BB^-1a_j＞0，则增加非基变量x_j的值会使目标函数J增加。如果x^*_B=B^-1b，x^*_N=0是式（3-50）的可行解，而且C_N-C_BB^-1N≤0，则{x^*_B，x^*_N}是最优解。

定理3.1 （无穷多最优解判别定理）若是一个基本可行解，所对应的检验向量C_N-C_BB^-1N≤0，其中存在一个检验数σ_k=0，则线性规划问题有无穷多最优解。

如果现行的基本可行解不是最优解，即在检验向量中存在正的检验数，则需要寻找一个新的基本可行解，具体做法是：

1）先从检验数为正的非基变量中确定一个进基变量，使它从非基变量变成基变量；

2）再从原来的基变量中确定一个退基变量，使它从基变量变成非基变量。

假设检验向量中有两个以上的检验数为正，那么为了使目标函数增加得快些，通常要用“最大增加原则”，即选取最大检验数所对应的非基变量为进基变量，即若

则取对应的x_k为进基变量。根据式（3-60），退基变量要按照最小比值原则来确定，即若

则选取对应的基变量x_n-m+_l为退基变量。

定理3.2 （无有限最优解判别定理）若是一个基本可行解，有一个检验数σ_j＞0（即存在进基变量），但是B-¹a_j≤0（即不存在对应的退基变量），则线性规划问题无有限最优解。

（2）大M单纯形法

运用单纯形算法原理进行求解存在着以下问题：

1）要确定一个初始基矩阵B，要求可逆，并非易事；

2）即使找到一个基矩阵B，也不能保证可行；

3）必须求基矩阵B的逆矩阵B^-1。

大M单纯形法解决上述问题的思路是在线性规划求解过程中，设法得到一个m阶单位矩阵I作为初始可行基B。大M法首先将线性规划问题化为标准型，然后在约束方程组的左边加上若干个非负的人工变量x_av，使某m个变量对应的系数列向量构成一个单位矩阵。以单位矩阵为初始基矩阵，则初始基本可行解为。

为了求得原问题的解，必须尽快通过迭代过程把人工变量x_av从基变量中替换出来。为此可以在目标函数中赋予人工变量x_av一个绝对值很大的负权重系数-M。这样只要基变量中还存在人工变量，目标函数就不可能实现最大化。为简单起见，可直接加m个人工变量，这样式（3-50）～式（3-51）变为如下形式：

其中

在下面的算法的每个迭代步骤，均采用如下的标准记法：

但注意其中的各个参数都是随着迭代的进行所变化的，且在迭代开始时式（3-65）等于式（3-64）。

4.算法步骤

取M=10⁵。采用优化问题式（3-63）～式（3-64），初始基本可行解为x=。然后按照如下步骤进行迭代计算。

（1）B=I总是成立。x_B=B^-1b=b。令x_N=0，计算目标函数值J=C_Bb。

（2）对于非基变量，计算判别数σ_j=c_j-z_j=c_j-C_Ba_j（j=1，2，…，n）。若所有判别数σ_j≤0，则得到最优解，运算结束。

（3）找到所有使得检验数σ_j＞0的j。若有其中一个a_j≤0，则停止计算，问题不存在有限最优解。

（4）找到σ_k=max_1≤j≤n{c_j-z_j}，则x_k为进基变量。记。确定退基变量下标l，使，得到退基变量x_n+_l。

（5）显然，此时

对矩阵[N|B|b]的每一行i，做如下变换：

1）先考虑第l行，该行除a_lk；

2）再考虑i≠l，则第i行减“第l行×a_ik”。

（6）对变换后的[N|B|b]，交换第k列和第n+l列，得到新的[N|B|b]；对应地，交换第k个和第n+l个元，交换第k个和第n+l个元；返回步骤（1）。