第二章线性规划与单纯形第二章线性规划与单纯形法.docVIP

2. 线性规划与单纯形法 在第一章中,我们讨论了如何利用几何方法求具有两个决策变量解线性规划问题的最优解。几何解法虽然较为直观,但当决策变量数目大于三个以上时,其应用就受到限制。在本章中,我们将介绍具有两个以上决策变量线性规划问题的算法,一般称为单纯形法,为了方便大家阅读,如果没有特别声明,本章所涉及到的线性规划问题都是标准最大化线性规划问题(1.5)。 单纯形的几何意义是在维空间中,由个点连接起来的几何体。在一维空间中, 单纯形是连接两个点的一条直线;在二维空间中,单纯形是由三个点形成的三角形;在三维空间中,单纯形是由四个顶点构成的四个平面的金字塔。在介绍线性规划问题的几何解法时,我们提到线性规划问题的最优解一定是出现在可行域(二维空间的多边形)的某个顶点,这个结论同样适用于维空间中的可行域(维空间的单纯形)。 对于维空间,我们无法通过几何方法直接观察到维空间的单纯形顶点,但是利用线性代数的知识,我们能够设法计算出单纯形顶点的坐标及对应目标函数值。所以,我们将通过某种方式(我们将看到它就是基可行解)来记录,描述和分析目标函数和约束函数在单纯形顶点的情况。我们还将讨论如何获得单纯形的初始顶点,如何建立从一个顶点到另一个顶点的基本迭代规则,以及建立判别最优顶点的准则。由于寻找线性规划问题最优解的过程是在由约束函数构成的单纯形上进行的,我们称其为单纯形法。 2.1基本概念 举例 在讨论单纯形法的迭代规则和具体计算步骤之前,我们先通过一个例子来观察单纯形法是如何运用的。 例 考虑下面标准最大化线性规划问题 我们首先对问题的约束条件引进松弛变量,对于问题的每一个小于等于不等式约束,我们引进松弛变量使不等式的左右两端相等,比如说,对第一个不等式约束, 我们引进松弛变量,使下面等式成立: 或 那么完全等价于 。如果继续对问题的第二个和第三个不等式约束分别引入松弛变量和,我们就获得与问题完全等价的线性规划问题如下: 其中,表示目标函数的值。我们称问题中的为独立变量,称,,为非独立变量或依赖变量。我们通常也称依赖变量为基变量,称独立变量为非基变量。 由于问题的等式约束构成了一个单纯形,单纯形法的基本思路是在该单纯形上不断搜寻使目标函数值增加的可行解,直到找到最优解。为了对问题进行迭代,我们必须确定迭代的初始可行解,,计算出对应的目标函数值。那么,迭代能够继续的前提是下一个新的可行解对应的目标函数值必须满足,即: 我们继续重复这种迭代过程直到不能够再找到使目标函数值继续增加的可行解,那么当前的可行解就是例线性规划问题的最优解。 那么,我们如何选择问题的初始可行解?,如何寻找使成立的新可行解?首先,我们观察到如果令问题的约束函数右端的三个非基变量等于,即,,,则问题的基变量就分别等于,, ,我们将这个解记为: 由于满足的所有约束条件,它正好构成问题的初始可行解,与此同时,初始目标函数值。 然后,我们能否在可行解集合中找到另外一个可行解,比如,,并且使的目标函数值大于初始目标函数值?我们注意到在目标函数中变量的系数是绝对值最大的正数,如果我们将从增加到任何一个正数,目标函数值也就会增大。但是,我们看到当的取值增大时,变量的取值也会受到影响。我们暂时保持和的取值不变,即,那么式的第一个约束条件就变成: 而的取值又必须大于等于,即有: 我们得出的取值范围是在之间,或的解集为:。 同样原理,根据式的第二个约束条件和的非负限制,有: 这就要求的取值范围是在之间,或。 最后,根据的第三个约束条件和的非负限制,有: 它要求的取值范围在之间,或。 因为取值范围必须同时满足上述三个解集,所以只有当时,才能满足三个解集,这样我们得出。令,,,并将其分别代入到问题的第一,二和三个约束条件中,则有:,,,我们得到新可行解如下: 对应这个可行解,目标函数值等于。 那么从初始可行解到第二个可行解,目标函数值从增加到了。对初始可行解来说,是非基变量,是基变量;但是,对于第二个可行解而言,成为基变量,成为非基变量,与的角色发生了互换。对第二个可行解,当时,达到其取值上限,被调出非基变量;同时,等于,被调入基变量。那么,我们能否将新的基变量,,和目标函数表示为非基变量,,的线性函数,为此,我们首先利用中的第一个等式约束来求解,得到: 同样,我们也可以将,和也表示为,,的线性函数(分别将代入到其他三个方程中),所以我们可以将问题改写为: 如果我们令式右端所有非基变量都等于,即:,,,那么,式的基变量就分别为:,,,这时,目标函数为:。 我们称从式到式为一次单纯形迭代(从顶点到顶点),迭代完成前后