任务三　线性规划的单纯形法

前面介绍的图解法虽然简单、直观，容易理解，但是，它只能解决2个决策变量的线性规划问题，对更为复杂的问题则无能为力。所以，我们需要寻找这种问题的一般解法，20世纪40年代末，单茨格（Dantzig）提出的单纯形法，完美地解决了线性规划问题。

3.1　单纯形法的一些基本概念

在线性规划中，设A为约束条件的m×n阶系数矩阵（设n＞m），其秩为m，B是矩阵A的一个m×m的满秩子矩阵，那么我们称B是线性规划问题的一个基。

基变量：B中每一列所对应的变量叫基变量，其余的叫非基变量。

基本可行解：一般地，如果包括松弛变量在内的变量个数为n，方程个数为m，那么在标准形式中，有n-m个变量等于0的可行解叫做基本可行解。

最优解：满足目标函数要求的基本可行解为最优解。最优解对应的基为最优基。

矩阵的初等变换：将矩阵的一行同乘以一个数；将矩阵的一行同乘以一个数，再加到另外一行上去。

3.2　单纯形法的理论依据

单纯形法解决线性规划问题的理论依据：线性规划问题的可行域是n维向量空间Rn中的多面凸集，其最优值如果存在必在该凸集的某顶点处达到。顶点所对应的可行解称为基本可行解。

单纯形法的基本思想：先找出一个基本可行解，对它进行鉴别，看是否是最优解；若不是，则按照一定法则转换到另一改进的基本可行解，再鉴别；若仍不是，则再转换；按照这个方法重复进行。因基本可行解的个数有限，故经有限次转换后必能得出问题的最优解。如果问题无最优解也可用此法判别。单纯形法是从某一基本可行解出发，连续地寻找相邻的基本可行解，直到达到最优的迭代过程，其实质是解线性方程组。

3.3　线性规划的标准形式

线性规划问题是求一个线性目标函数在一组线性约束条件下的最大值或最小值问题。在线性规划模型中，目标函数根据实际问题的要求可以求最大值，也可以求最小值；每一个约束条件可能是相等约束，也就是约束函数等于资源常量项，也可能是不等约束，也就是约束函数大于资源常量项或约束函数小于资源常量项。资源常量项可能非负也可能非正，决策变量取值范围可能非负，可能非正，甚至可能无限制。因此，线性规划模型的形式是多种多样的，这给求解线性规划问题带来了诸多不便。为了求解的方便，我们可以先把线性规划模型转化成标准形式，然后再进行求解。所有的线性规划模型都可以转化为标准形式。下面我们介绍线性规划的标准形式。

线性规划的标准形式为

它也常写成向量形式

线性规划的标准形式必须满足以下四个条件：

（1）目标函数极大化；

（2）约束条件的右端常数项非负；

（3）所有的约束条件必须为等式；

（4）决策变量非负。

那么，如何将线性规划转化为标准形式呢？

（1）如果目标函数为求极小值，即minz＝CX，因为minz＝-max（-z），所以我们可以令z′＝-z＝-CX，这时，目标函数就变成maxz′＝-CX，转化后的问题与原问题有相同的最优解。

（2）如果约束条件为不等式，那么将它转化为等式时，可以引入一个松弛变量xn＋1（非负），这时原不等式就变为

如果约束条件是不等式，这时可以引入剩余变量xn＋1（非负），这时原不等式就变为

也就是说，如果原不等式左边小于等于右边，就让左边加上一个非负数，使得两边相等；如果原不等式左边大于等于右边，就让左边减去一个非负数，使得两边相等。

（3）如果右端常数项小于0，只需两边同乘以-1即可。

（4）如果决策变量无非负约束，这时可以分为以下两种情况讨论：

①决策变量xj≤0，可以令，这里非负。

②若xj为自由变量，即xj可为任意实数，可令，且，将变换后的变量代入原模型，则转化后的问题和转化前的问题具有相同的最优解。

例2-3-1　将下列线性规划问题转化为标准形式。

解：第一步，目标函数乘以-1，转化为最大化。即

maxz＝-x1＋2x2-3x3

第二步，在第一个约束条件中引入松弛变量x4，在第二个约束条件中引入剩余变量x5，即

x1＋x2＋x3＋x4＝7

x1-x2＋x3-x5＝2

第三步，在第三个约束条件等式两边同乘以-1，使等式右边为非负。即

-3x1＋x2＋2x3＝5

第四步，将无约束的x3转化为x3＝x6-x7，把它代入原问题中，因此，可以得到原问题的标准形式

3.4　单纯形法的求解

例2-3-2　用单纯形法求解线性规划。

解：先把线性规划问题化为标准型：

这时我们可以得到约束条件的增广矩阵：

取单位矩阵所在的列对应的变量为基变量，其余变量为非基变量，获得基本可行解X＝（0，0，15，24，5）T。列出一个初始单纯形表，见表2-3-1。

表2-3-1的最后一行，我们称为目标函数行。从目标函数行我们可以看出，现在z＝0，也就是说目标函数值为0。那么这个基本可行解是不是最优解呢？判定方法是：单纯形表中目标函数行对应于非基变量的元素，我们把它称为检验数。而当所有检验数都非正时，就得到了最优解，否则解仍然可以改善。

事实上，如果检验数有正数，那么以该检验数为系数的非基变量取值大于0时，目标函数值就仍然可以增大，所以这个解不是最优解；而当所有检验数非正时，非基变量取值为0，目标函数已取得极大值，所以这个解就是最优解。

在表2-3-1中的检验数，2和1均为正数，因此，解仍然可以改善。把原来的一个非基变量换为基变量，使得目标函数值增大。因为x1的价值系数更大，所以如果把x1变为基变量，目标函数值会增加更快。选择将x1换为基变量，称为进基变量。因为换入了一个基变量，因此，有一个原来的基变量会被换出，称之为离基变量。

选定进基变量后，可以用最小比值法，，确定6作为主元，即要化为1的元素。这个元素不能为负，不能为0。可以把主元用括号标志出来，如表2-3-2所示。

接下来，通过初等行变换，把主元化为1，把主元列其他元素全部都变为0，结果如表2-3-3所示。

检查检验数，仍有正数，证明目标函数值还能增大，所以让正的检验数所对应的变量x2作为进基变量，用最小比值法，所以主元定为。再次进行初等行变换，得到表2-3-4。

观察表2-3-4的目标函数行，所有检验数都非正，这时我们就得到了最优解，把它代入到目标函数，得到最优值。

由此，我们总结出单纯形法的基本步骤为：

（1）建立线性规划问题模型，并将其化为标准形式。

（2）在标准形式的基础上做出初始单纯形表，求出检验数。

（3）确定检验数中最大正数所在的列为主元列，选择主元列所对应的非基变量为进基变量。

（4）按最小比值原则，用常数列各数除以主元列相对应的正商数，取其最小比值，该比值所在的行为主元行；主元列与主元行交叉的元素为主元，主元所对应的基变量为出基变量。

（5）对含常数列的增广矩阵用初等变换把主元变为1，主元所在的列的其余元素化为0。

（6）计算检验数，直到全部检验数小于等于0，迭代终止，基变量对应的常数列为最优解，代入目标函数得最优目标函数值。

例2-3-3　用单纯形法求解线性规划。

解：（1）先将上述问题化为标准形式。

（2）在标准形式的基础上做出初始单纯形表（见表2-3-5），求出检验数。

（3）检验数4，5都是正数，还能找到更优的解。因此，我们要进行初等行变换。选择检验数比较大的5所对应变量x2作为进基变量。

（4）用最小比值法确定主元，，所以主元定为1。进行初等行变换，把主元变为1，主元列其他元素变为0，见表2-3-6。

（5）观察目标函数行的检验数，发现4仍然为正数，于是选择4所对应变量x1为进基变量。

（6）用最小比值法确定主元，，进行初等行变换，把主元变为1，主元列其他元素变为0，见表2-3-7。

（7）观察目标函数行的检验数，发现3仍然为正数，于是选择3所对应变量x4为进基变量。

（8）用最小比值法确定主元，，进行初等行变换，把主元变为1，主元列其他元素变为0，见表2-3-8。

观察表2-3-8中目标函数的检验数，全部非正，这时我们就找到了该线性规划问题的最优解。最优解为X＝（4，2，0，1，0）T，去掉松弛变量和剩余变量，最优解为X＝［4，2］T，代入目标函数得最优值z＝26。

有的时候，当得到最优解之后，检验数并不全部为负，而是有0存在。这时，把检验数为0的一列作为进基变量，再次进行迭代，会得到另外一组最优解，代表该线性规划有无穷多最优解。只要是已得到最优解的单纯形表中出现了检验数为0的情况，一般该问题都有着无穷多最优解。

同理，如果单纯形表中某非基变量的检验数为正，但此时该非基变量所对应列所有元素非正，那么该问题无最优解。