用单纯形法解决线性规划问题

子任务2.4　用单纯形法解决线性规划问题

2.4.1　任务引入

【任务2-10】　求解线性规划问题，其模型如下：

maxz=3x₁+2x₂

【任务2-11】　求解线性规划问题，其模型如下：

2.4.2　任务分析

解线性规划问题著名的单纯形方法（Simplex Method）是G.B.Dantzig在1947年提出来的，两个变量的线性规划问题可以用图解法进行求解，而当变量是3个或3个以上且约束条件又多时，可行域所在的凸集表现为一个凸多边形，在空间上必将是一个凸几何体，因此我们几乎或实在无法通过作图来找可行域，更无法找到最优解，此时图解法就显得无能为力，但这些问题可以利用下面讲解的单纯形法进行求解。

2.4.3　知识构建

1）单纯形法的改进

单纯形法的实质是从一个基本可行解走向另一个基本可行解，一步步地达到最优解的迭代过程。上面所介绍的表格形式的单纯形算法，其过程就是一种特殊的消去法，我们可能已经注意到了，在每个迭代表格中，我们主要关心的数据，就是检验数所在的一行和最大正检验数所在的一列，而这些数据都可以通过矩阵的运算而直接地从问题的初始数据中计算出来，这种借助于矩阵运算的单纯形法，就是单纯形法创始者丹茨格（G.B.Dantzig）后来提出的改进的单纯形法（revised simplex method）。

从2.3节中的图解法得出的结论可知，线性规划的最优解一定可以在线性规划可行域的某个顶点上达到。实际对于任意一个有n个变量的线性规划问题，如果它有有界的线性规划可行域，则它的最优解必然在所有约束条件的交点处取得。而一个有界的线性规划可行域，其顶点个数必然是有限的；因此，求线性规划的最优解时，只要在线性规划可行域的有限个顶点上去寻找即可。

线性规划的基本可行解的个数是有限的，理论上我们可以通过比较所有的基本可行解来求最优解。但是，当约束方程个数和决策变量的数目很大时，其基本可行解的数目也十分巨大。虽然单纯形法理论上可以解决一切线性规划问题，但人力往往无法承受相应的计算能力。幸运的是，计算机技术的发展已经使我们拥有了足够的计算能力。

改进的单纯形法与表格形式的单纯形法，其实质完全一样，只是计算形式不同。表格形式的单纯形法，方法简单，容易掌握，非常适用于手算，且在计算机上用于求解小型线性规划问题时，也是比较方便的，但由于在计算机上使用表格式的单纯形法需要把整个表格储存在计算机中，因此这种方法不适合求解较大规模的线性规划问题。而改进的单纯形法，一般说来，不适合用于手工计算，但较大规模的线性规划问题，其约束方程组的系数矩阵往往是稀疏的（即矩阵中的大多数元素为零），于是利用计算机上数据处理的某些技巧，就可以在电子计算机上使用改进的单纯形法处理较大规模的线性规划问题了。

这就是改进的单纯形法的最主要的优点，无论使用哪一种形式，经验表明，要解一个含有m个约束条件的线性规划问题，只要经过m～1.5m次迭代就可以了，因此，单纯形方法是一种非常有效的计算方法。

2）利用单纯形法求解线性规划问题的流程

下面简要介绍使用计算机编程来求解线性规划问题的原理。

首先考察单纯形算法的基本思路，用单纯形法解题分为两个阶段：

第一阶段是寻求一个可行解，经检验若不是最优解，则转入第二阶段。

第二阶段从所求出的可行解出发，通过变量的调整求出新的可行解。调整的方法是从一个基本可行解出发，设法得到另一个更好的基本可行解，直到目标函数达到最优时，基本可行解即为最优解；如果仍然不是最优解，则重复进行调整，每调整一次，目标函数就改进一次（在线性规划问题的标准型中，目标函数值总是大于或等于前面得到的解的目标函数值），直到求得最优解。这一过程实际上就是如图2-5所示的迭代过程。

2.4.4　任务实施

步骤一　将线性规划问题化为标准型

对任务2-10引入松弛变量x₃，x₄，x₅后将已知模型转化为如下标准型。即

maxz=3x₁+2x₂+0x₃+0x₄+0x₅

图2-5　利用单纯形法求解线性规划问题的流程

该标准型存在三阶单位矩阵E，如x₃只在第一个方程中系数为1，而在其他方程中系数为0，说明x₃为基变量；同样，x₄，x₅也为基变量，而x₁，x₂为非基变量。

令非基变量x₁=x₂=0可得一组基本可行解，即

x₁=0，x₂=0，x₃=4，x₄=14，x₅=3

这组解是否为最优需要进行检验，为着重说明其检验方法，下面将直接在单纯形表上进行迭代运算。

步骤二　列出初始单纯形表，并在表中计算出检验数λ_j

表2-4的计算说明如下。

表2-4　初始单纯形表

①z_j行的计算：用C_j列（C_j列指目标函数中基变量的系数C_B）中各数乘决策变量列的相对应数后再相加，即，具体计算结果如下：

z₁=0×（-1）+0×3+0×1=0

z₂=0×2+0×2+0×（-1）=0

z₃=0×1+0×0+0×0=0　　

z₄=0×0+0×1+0×0=0　　

z₅=0×0+0×0+0×1=0　　

z=0×4+0×14+0×3=0　　

②λ_j行的计算：λ_j=C_j-z_j，即用C_j行各数减去z_j行相对应数，称为检验数。一般地，λ_j≤0表示基本可行解达到最优；否则λ_j中有一正数就要继续进行迭代运算，向最优解逼近，这λ₁=3-0=3，λ₂=2-0=2，λ₃=λ₄=λ₅=0-0=0，所以要继续迭代运算。

步骤三　确定主元列、主元行、主元

①确定主元列，选择进基变量。当检验数λ_j有正数时，称检验数中最大正数所在列为λ_j，主元列所对应的非基变量为进基变量。由于表2-4的检验数中最大正数为3，所以第一列为主元列，所对应的非基变量x₁为进基变量，如表中箭头所示。需要注意：在每一步迭代过程中，在选择进基变量与离基变量的同时，在表上都需将基变量列中的基变量与目标系数列中的系数作相应改变，不可疏忽。

②确定主元行，选择离基变量。按最小比值原则，即用常数列各数除以主元列相对应的正商数，取其最小比值，该比值所在行为主元行，主元行与主元列交叉的元素称为主元，主元所对应的基础变量为离基变量。

③由表2-4可知：min｛3/1，14/3｝=3（主元列中的零或负数不作比值比较），于是第三行为主元，主元为［1］，它对应的基础变量为x₅，离基变量就是x₅，如表中箭头所示。注意：基变量列（x₃，x₄，x₅）^T变为（x₃，x₄，x₁）^T，且C_j列（0，0，0）^T变为（0，0，3）^T并置于表2-5中。

表2-5　改进单纯形表（一）

④对增广矩阵用初等行变换将主元化为1，主元所在列其余元素化为零。

由表2-4可知，主元已为1，只要将第一列其余元素化为零即可。根据上述步骤并计算z_j与λ_j之后列入表2-5单纯形表中。

步骤四　继续迭代寻找最优解

由于表2-4检验数仍有正数5，因此继续以下运算。

重新对表2-5确定主元列与主元行及主元，选择进基变量与离基变量。

由表2-5可知，主元列是第二列，进基变量为对应的非基变量x₂，按最小比值原则min｛5/5，7/1｝=1，于是主元行为第二行，主元为［5］，离基变量为对应的基变量x₄。

对增广矩阵用初等行变换将主元［5］化为1，将主元［5］所在第二列其余元素化为零，得表2-6。注意：基变量列应由（x₃，x₄，x₁）^T变为（x₃，x₂，x₁）^T；C_j列应由（0，0，3）^T变为（0，2，3）^T并置于表2-6中。

表2-6　改进单纯形表（二）

步骤五　迭代运算终止

由于表2-6中检验数都满足λ_j≤0，因此最优解已经找到，迭代运算终止，最优解为x₁=4，x₂=1，x₃=6，x₄=0，x₅=0，最优目标函数为z=14。

当运算得非常熟练以后，可以在同一表上进行迭代运算。下面以任务2-11说明。

先将任务2-11模型化为标准型，再用单纯形法。

将求解的一系列单纯形表汇总于表2-7中。

表2-7　单纯形计算表

由表2-7可知，最优解为x₁=20，x₂=20，x₃=0，x₄=0，x₅=0，最优目标函数值为z=1700。

下面根据以上例题，给出单纯形法主要求解步骤：

第一步：将线性规划问题转化为标准型。由前面的例题可以知道一定存在单位矩阵，并且单位矩阵对应的决策变量必为基础变量。

第三步：用最小比值原则确定主元行，主元行所对应的基础变量为离基变量。最小比值计算方法为min｛b_j/a_ij｝。

第四步：主元行与主元列交叉的元素为主元。对增广矩阵用初等行变换将主元化为1，主元所在列其余元素化为零（主元以下［　］号表示）。

第五步：每一次迭代都要计算z_j与检验数λ_j，当λ_j≤0时可终止计算，表示得到最优解，否则就要继续迭代寻找最优解。

从第二步到第五步就是所谓单纯形法的迭代过程，每次迭代都得到一个新的单纯形表和改进的基本可行解。单纯形法的运算效率取决于基本可行解的检验次数，因此在单纯形法计算中应尽量减少迭代次数。