线性规划的算法分析

作者: PrivateEye_zzy | 来源:发表于2018-06-11 18:03 被阅读0次

本章涉及知识点

1、线性规划的定义

2、可行区域、目标函数、可行解和最优解

3、转线性规划为标准型

4、转线性规划为松弛型

5、单纯形算法的思想和例子

6、避免退化—Bland规则

7、广义单纯形算法的步骤

8、约束条件为负数情况下存在的问题

9、构造辅助线性规划函数

10、从辅助线性规划函数还原目标函数

11、辅助线性函数的求解步骤

12、完整的单纯形算法步骤

13、python编程实现单纯形算法

14、实验验证单纯形算法处理不同线性规划问题

一、线性规划的定义

我们来看一个实际问题：

假设你是一个单位的采购经理，你有2000元经费，需要采购单价为50元的若干桌子和单价为20元的若干椅子，你希望桌椅的总数尽可能的多，但要求椅子数量不少于桌子数量，且不多于桌子数量的1.5倍，那你需要怎样的一个采购方案呢？

于是我们可以假设桌子数量和椅子数量为x1和x2，为此我们的目标函数为

目标函数

而约束条件可以写为

约束条件

上述既包含目标函数，又含有约束条件，就可以抽象为一个线性规划问题，即在有限的资源和若干竞争约束下，求某个目标函数的最大化或最小化的最优策略

二、可行区域、目标函数、可行解和最优解

我们由上述案例来看，因为是只有两个变量属于二维空间，我们在笛卡尔坐标系中画出约束条件和目标函数

案例线性规划空间

从二维空间中我们可以看出，紫色区域就是满足所有约束条件的安全区域，包括最优解也必须在其中，我们把这个区域叫做可行域。红色函数即是目标函数，而要求目标函数达到最大值或最小值，就是平行的移动目标函数，让目标函数在可行域上达到截距最大(最小)。图中的A、B、C三个点都属于目标函数与可行域的交点，我们称之为可行解，而使得目标函数达到最大(最小)的可行解被我们定义为最优解，其对应于图中的A点

至此我们可以总结出线性规划的几个特征

（1）线性规划的可行域总是一个凸集

（2）目标函数的可行解(包括最优解)一定出现在可行域的一个顶点上

（3）目标函数可以是直线(二维空间)或者超平面(高维空间)的线性变化，所以它的局部最优解实际上就是全局最优解

三、转线性规划为标准型

为了统一用一种数学模型来描述任意线性规划问题，我们定义了两种规范形式：标准和松弛

线性规划的标准形式为

标准形式

其中A，x和b都是向量形式，我们可以将任意一个线性规划转化为标准形式

（1）如果目标函数是求max，那么乘以-1使目标函数转化为求min

（2）如果约束条件有>=约束，同理乘以-1将约束变为<=

我们将开头的案例转化为标准形式如下：

开头案例的标准形式

可以看到，线性规划的标准型，是满足不等式约束的一个目标线性函数最小化(最大化)过程

四、转线性规划为松弛型

在求解线性规划算法中，我们更喜欢用等式约束来等价描述不等式约束，为此我们引入松弛形式

松弛形式

为了将约束条件都变为等式，我们需要引入松弛变量进入x向量，下面我们将开头案例转化为松弛形式如下：

开头案例的松弛形式

可以看到松弛变量的意义，就是度量了等式约束与原不等式约束之间的松弛或差别，我们的单纯形算法都是建立在线性规划的松弛形式上

五、单纯形算法的思想和例子

我们以开头案例，来一步步介绍单纯形算法的思想

我们将松弛变量单独提到等式左边，将松弛形式等价的变为

开头案例松弛形式

在上述的等式中，我们将等式左边的部分称之为基本变量，而右边部分称之为非基本变量

现在我们考虑这个状态下的基本解，其计算方式为：将等式右边的所有非基本变量设为0，然后单独计算左边的基本变量值，为此我们得到第一个基本解为

第一个基本解

而这组基本解没有违反任意约束条件，即该基本解就是一个可行解，也就是可行区域的一个顶点。这里需要说明一点，基本解完全存在不是可行解的情况，这种情况需要引入辅助线性函数做等效变化，我们放在第八点来说明。

下面我们选出当前目标函数中第一个系数为负数的非基本变量，需要将其变化为基本变量，为此我们选出x1，我们也将这个非基本变量称为替入变量

紧接着我们需要在约束条件里找到一个对当前替入变量x1最严格的一个约束，我们计算出第一个约束里x1可以增大到0，第二个约束里x1可以增大到无穷，第三个约束里x1可以增大到400，因此第一个约束条件对x1更为严格，我们选择第一个约束，而这个约束里的基本变量我们称为替出变量，得到x1 = x2 - x3，将其带入当前的约束集合变化得到

第一次旋转

上述的过程我们定义为一个转动(pivot)，而一次转动的目的，就是在当前的目标函数里选择一个替入变量，然后在约束集合里选择一个约束（替换变量），最后替换这组替入变量和替出变量的角色位置，其本质就是用替出变量来表示替入变量的代数式，至于选择替入变量和替处变量的规则，我们遵循Bland规则（单独在第六点讲解）

经过第一次旋转，此时的基本解变为

第一次旋转后的基本解

经过第一次旋转，此时的目标函数的值变为0

接下来我们需要不断的执行转动过程，直到目标函数无法改进，即目标函数的系数全部为非负数

由于目标函数里任然存在系数为负数的项，我们继续执行第二次转动，选择替入/替出的算法和第一次转动一样，我们从当前的目标函数里选择x2为替入变量，在约束集合里因为第一个和第二个约束都可以让x2增大到无穷，而第三个约束可以让x2增大到2000/70，为此我们选择第三个约束条件的x5为替出变量，得到x2 = 2000/70 + 5/7*x3 - 1/70 * x5，将其带入当前的约束集合变化得到

第二次旋转

经过第二次旋转，此时的基本解变为

第二次旋转后的基本解

经过第二次旋转，此时的目标函数的值变为-4000/70

由于目标函数里任然存在系数为负数的项，我们继续执行第三次转动，同理，我们选择x3为替入变量，选择第二个约束里的x4作为替出变量，得到x3 = 1000/80*x4-14/16*x4-1/160*x5，将其带入当前的约束集合变化得到

第三次旋转

经过第三次旋转，此时的基本解变为

第三次旋转后的基本解

经过第三次旋转，此时的目标函数的值变为-35000/560=-62.5

而此时此刻，我们的目标函数里已经没有系数为负数的项了，说明我们无法在继续增大(减小)目标函数，算法达到了收敛，停止转动，此时求出的基本解就是线性规划的最优解！这个解也解释了在案例里，最优的方案是购买25张桌子，37张椅子（椅子数量为整数），总的购买了25 + 37 = 62张桌椅，总花费了25*50+37*20=1990元

六、避免退化—Bland规则

我们从案例出发一步步介绍了单纯形算法的思想，经过一系列的旋转，最终得到了最优解和目标值，其中在旋转的操作里，我们涉及到替入变量和替出变量的选择，这一步至关重要，因为它将决定目标函数的变化和是否需要继续旋转，如果选择不当，我们的算法非常有可能进入循环旋转，并且不会停止，我们把这个现象称之为退化

可以说退化是导致单纯形算法不会收敛的唯一原因，那么如何避免退化呢？在这里我们使用Bland规则来选择替入和替出变量

Bland规则定义：在执行换基操作（即选择替入和替出变量并交换二者角色）的时候，我们总是选择下标最小的非基本变量去满足左侧的基本变量

替入变量选择：在目标函数中，选择系数为负数的第一个非基本变量

替出变量选择：在约束集合中，选择对当前替入变量约束最紧的第一个基本变量

七、广义单纯形算法的步骤

下面我们总结一下广义上单纯形算法的主要步骤

（1）从原线性规划问题中找到第一个基本解（必须是可行解）

（2）根据Bland规则，执行旋转操作

（3）重复第2步直到算法收敛

其中第二步和第三步都是围绕着旋转操作执行的，而我们需要重视的是第一步，因为从几何的角度上看，我们知道线性规划的可行解都是出现在可行域的顶点上，而单纯形算法的每一次旋转，都可以得到一个可行解，说明每一次的旋转其实是从可行域的一个顶点游走到另一个顶点，所以算法的第一步，我们必须让单纯形算法落在可行域的一个顶点上！也就是说需要初始化的基本解，必须是可行解！

案例里第一次我们的基本解就是可行解（因为没有违反任何约束），但是有一些线性规划问题中我们的基本解，不一定就是可行解

八、基本解不是可行解的情况

下面我们来看另外一个案例2

案例2

要解这个线性规划，我们按照单纯形算法的思想，先转化为松弛型

案例2松弛型

接下来我们进行单纯形算法的第一步，找到一个基本可行解，而此时的基本解为

第一个基本解

注意观察，此时的基本解不满足原线性规划的第二个约束条件，因为0+0=0>=1是不成立的！所以现在的基本解根本不在可行域的顶点上，不是线性规划的可行解！

因此此时不能进入单纯形算法来求解，我们需要思考为什么会产生基本解不是可行解的情况

注意看到上述案例的第二个约束条件存在负数约束，这也是导致我们的第一个基本解不满足该约束的问题所在，因此我们可以总结出单纯形算法的第一步需要分类讨论

（1）如果约束集合里不存在负数约束，说明初始化的基本解就是可行解，可以顺利执行单纯形算法

（2）如果约束集合里存在负数约束，说明初始化的基本解并不是可行解，需要进行原线性规划问题的等效变化来找到一个可行解，再执行单纯形算法

当我们要求解的线性规划出现了上述第二种情况，就需要引入构造辅助线性规划函数来进行原线性规划的变形

九、构造辅助线性规划函数

我们以案例2，来一步步介绍辅助线性规划函数的意义

我们在案例2的标准形式上，继续构造一个新的线性规划函数

辅助线性规划函数

我们引入新的变量x0，且x0的系数是-1(用于第一次旋转的时候将所有的负数约束系数变为正数)，显然当x0=0的时候，说明原线性规划组有解。我们写出其松弛形式为

辅助线性函数的松弛形式

同理，我们将右侧非基本变量视为0，计算出左侧的基本变量，则第一个基本解为

第一个基本解

显然这个解违反了原线性规划的第二个不等式约束，为此我们对引入的新变量x0做第一个旋转操作：

将非基本变量x0作为替入变量，并且在约束集合里选一个约束系数最小的那一行的基本变量作为替出变量，进行旋转操作

显然当前约束集合里约束系数min(2,-1)=-1，为此我们选择x4作为替出变量，得到x0=1-x1-x2+x4，将其带入当前的约束集合变化得到

第一次旋转

经过第一次旋转，此时的基本解变为

第一次旋转后的基本解

经过第一次旋转，此时的目标函数的值变为1

从第一次旋转我们可以看到，由于x0的系数为-1，经过一次旋转，为此我们已经将原约束集合里所有的负数约束变为了正数约束，这也是开头我们引入x0的原因！

接下来我们需要求解这个辅助线性规划，我们使用单纯形算法求解即可，每次旋转选取的替入/替出变量规则一样，如果能解出辅助线性规划的目标函数最优值x0=0，那么就说明原线性规划有解。我们从目标函数里选择x1为替入变量(系数为负数的第一项)，选择第二个约束的x0作为替出变量，得到x1=1-x2+x4-x0，将其带入当前的约束集合变化得到

第二次旋转

经过第二次旋转，此时的基本解变为

第二次旋转后的基本解

可以看到此时的基本解已经同时满足了原线性规划的所有约束条件，即此时的基本解在可行域的顶点上，是一个基本可行解！

此时的目标函数的值变为0，说明了原线性规划是有解的，并且我们已经成功的找到了一个基本可行解(顶点)

十、从辅助线性规划函数还原目标函数

经过辅助线性规划的求解，我们已经成功的找到一个基本可行解，接下来，我们需要恢复原线性规划的目标函数，等效还原的方法为

等效还原目标函数：用此时的基本变量替换原目标函数中的基本变量

原目标函数为

案例2的原目标函数

可以看到x1和x2为原来的基本变量，而此时的基本变量为x1和x3，我们代替x1即可

现基本变量替换原基本变量

由于x0=0，我们将其去掉，最终我们得到了经过辅助线性函数等效变化后的一个新的线性规划

等效变化后的线性规划

可以看到这个线性规划的基本解就是可行解，我们顺利完成了单纯形算法的第一步：从原线性规划问题中找到第一个基本可行解，那么我们就可以继续用单纯形算法的第二三步来顺利求解之！

十一、辅助线性函数的求解步骤

下面我们总结一下辅助线性函数的求解步骤

（1）引入x0的列变量，且系数为-1，构造辅助线性规划函数

（2）辅助线性规划的目标函数为x0

（3）选择x0作为替入变量，同时选择当前约束集合中约束系数最小的那一行的基本变量作为替出变量，进行第一次旋转操作，将所有约束系数变为非负数

（4）使用单纯形算法求解当前辅助线性规划函数，如果解出辅助线性函数的目标函数的最优解为0，证明原线性规划函数有解，否则证明原线性规划函数无解

（5）如果求解后x0仍然是基本变量，则在x0作为基本变量的那一行约束条件里，将x0作为替出变量，同时在此时的目标函数里找到第一个系数不为0的变量作为替入变量，进行旋转操作，将x0变为非基本变量

（6）经过上述第一次旋转和求解辅助线性函数，得到了第一组基本可行解，则等效的还原原问题的目标函数（用当前的基本变量替换原目标函数中的基本变量），并且去掉x0的那一列

（7）执行单纯形算法的第二步和第三步

十二、完整的单纯形算法步骤

考虑到存在求解辅助线性函数，我们也总结出单纯形算法的完整步骤

（1）将线性规划的标准矩阵转化为松弛矩阵

（2）如果约束系数矩阵里不存在负数，找到基本可行解，转到步骤(5)

（3）如果约束系数矩阵里存在负数，没有找到基本可行解，则构造辅助线性规划函数，转到步骤(4)

（4）求解辅助线性规划函数，找到基本可行解，还原原目标函数，转到步骤(5)

（5）根据Bland规则，执行矩阵旋转操作

（6）重复步骤(5)直到算法收敛

十三、python编程实现单纯形算法

下面我们用python编程实现单纯形算法的各个求解步骤