运筹学第5章 单纯形法课件

《运筹学第5章 单纯形法课件》由会员分享，可在线阅读，更多相关《运筹学第5章 单纯形法课件（48页珍藏版）》请在金锄头文库上搜索。

1、1,第五章 单 纯 形 法,1单纯形法的基本思路和原理 2单纯形法的表格形式 3求目标函数值最小的线性规划的问题的 单纯形表解法 4几种特殊情况,2,1单纯形法的基本思路和原理,一、找出一个初始基本可行解 通过第二章例1的求解来介绍单纯形法: 在加上松弛变量之后我们可得到标准型如下： 目标函数： max Z = 50 x1+100 x2 约束条件：x1+x2+s1= 300， 2x1+x2+s2= 400， x2+s3 = 250. xj0 （j=1，2）,sj0 （j=1，2,3）,单纯形法的基本思路：从可行域中某一个顶点开始，判断此顶点是否是最优解，如不是,则再找另一个使得其目标函数值更优

2、的顶点，称之为迭代，再判断此点是否是最优解。直到找到一个顶点为其最优解，就是使得其目标函数值最优的解，或者能判断出线性规划问题无最优解为止。,3,1单纯形法的基本思路和原理,基：已知A是约束条件的mn系数矩阵，其秩为m。若B是A中mm阶非奇异子矩阵（即可逆矩阵），则称B是线性规划问题中的一个基。 基向量：基B中的一列即称为一个基向量。基B中共有m个基向量。 非基向量：在A中除了基B之外的一列则称之为基B的非基向量。 基变量：与基向量pi相应的变量xi叫基变量，基变量有m个。 非基变量：与非基向量pj相应的变量xj叫非基变量，非基变量有nm个。,它的系数矩阵,其中pj为系数矩阵A第j列的向量。A

3、的秩为3,A的秩m小于此方程组的变量的个数n，为了找到一个初始基本可行解，先介绍以下几个线性规划的基本概念。,4,1单纯形法的基本思路和原理,在此例中我们不妨找到了 为A的一个基，令 这个基的非基变量x，s2为零。这时约束方程就变为基变量的约束方程：,由线性代数的知识知道，如果我们在约束方程组系数矩阵中找到一个基，令这个基的非基变量为零，再求解这个m元线性方程组就可得到唯一的解了，这个解我们称之为线性规划的基本解。,5,1单纯形法的基本思路和原理,x2+s1= 300， x2=400， x2+s3=250. 求解得到此线性规划的一个基本解： x1=0，x2=400，s1=100，s2=0，s3

4、=150,由于在这个基本解中s1=100，s3=150，不满足该线性规划s10，s30的约束条件，显然不是此线性规划的可行解，一个基本解可以是可行解，也可以是非可行解，它们之间的主要区别在于其所有变量的解是否满足非负的条件。我们把满足非负条件的一个基本解叫做基本可行解，并把这样的基叫做可行基。,6,1单纯形法的基本思路和原理,一般来说判断一个基是否是可行基，只有在求出其基本解以后，当其基本解所有变量的解都是大于等于零，才能断定这个解是基本可行解，这个基是可行基。那么我们能否在求解之前，就找到一个可行基呢？也就是说我们找到的一个基能保证在求解之后得到的解一定是基本可行解呢？由于在线性规划的标准型

5、中要求bj都大于等于零，如果我们能找到一个基是单位矩阵，或者说一个基是由单位矩阵的各列向量所组成（至于各列向量的前后顺序是无关紧要的事）例如， 那么显然所求得的基本解一定是基本可行解，这个单位矩阵或由单位矩阵各列向量组成的基一定是可行基。实际上这个基本可行解中的各个变量或等于某个bj或等于零。,7,1单纯形法的基本思路和原理,在本例题中我们就找到了一个基是单位矩阵。 在第一次找可行基时，所找到的基或为单位矩阵或为由单位矩阵的各列向量所组成，称之为初始可行基，其相应的基本可行解叫初始基本可行解。如果找不到单位矩阵或由单位矩阵的各列向量组成的基作为初始可行基，我们将构造初始可行基，具体做法在以后详

6、细讲述。,8,1单纯形法的基本思路和原理,二、 最优性检验 所谓最优性检验就是判断已求得的基本可行解是否是最优解。 1. 最优性检验的依据检验数j,一般来说目标函数中既包括基变量，又包括非基变量。现在我们要求只用非基变量来表示目标函数，这只要在约束等式中通过移项等处理就可以用非基变量来表示基变量，然后用非基变量的表示式代替目标函数中基变量，这样目标函数中只含有非基变量了，或者说目标函数中基变量的系数都为零了。此时目标函数中所有变量的系数即为各变量的检验数，把变量xi的检验数记为i。显然所有基变量的检验数必为零。在本例题中目标函数为50 x1+100 x2。由于初始可行解中x1，x2为非基变量，

7、所以此目标函数已经用非基变量表示了，不需要再代换出基变量了。这样我们可知1=50，2=100，3=0，4=0，5=0。,9,1单纯形法的基本思路和原理,对于求最大目标函数的问题中，对于某个基本可行解，如果所有检验数 0，则这个基本可行解是最优解。下面我们用通俗的说法来解释最优解判别定理。设用非基变量表示的目标函数为如下形式 由于所有的xj的取值范围为大于等于零，当所有的 都小于等于零时，可知 是一个小于等于零的数，要使z的值最大，显然 只有为零。我们把这些xj取为非基变量(即令这些xj的值为零)，所求得的基本可行解就使目标函数值最大为z0。 *对于求目标函数最小值的情况，只需把 0改为 0,9

8、,2.最优解判别定理,10,1单纯形法的基本思路和原理,从最优解判别定理知道，当某个j0时，非基变量xj变为基变量不取零值可以使目标函数值增大，故我们要选基检验数大于0的非基变量换到基变量中去（称之为入基变量）。若有两个以上的j0，则为了使目标函数增加得更大些，一般选其中的j最大者的非基变量为入基变量，在本例题中2=100是检验数中最大的正数，故选x2为入基变量。,三、 基变换 通过检验，我们知道这个初始基本可行解不是最优解。下面介绍如何进行基变换找到一个新的可行基，具体的做法是从可行基中换一个列向量，得到一个新的可行基，使得求解得到的新的基本可行解，其目标函数值更优。为了换基就要确定换入变量

9、与换出变量。,1. 入基变量的确定（最大正检验数j对应的非基变量）,11,1单纯形法的基本思路和原理,在确定了x2为入基变量之后，我们要在原来的3个基变量s1，s2，s3中确定一个出基变量，也就是确定哪一个基变量变成非基变量呢？ 如果把s3作为出基变量，则新的基变量为x2，s1，s2，因为非基变量x1=s3=0， 我们也可以从下式： x2 +s1=300， x2+s2=400， x2=250， 求出基本解：x1=0，x2=250，s1=50，s2=150，s3=0。因为此解满足非负条件，是基本可行解，故s3可以确定为出基变量。 能否在求出基本解以前来确定出基变量呢？,2. 出基变量的确定（mi

10、n=bj/akj对应的基变量),12,1单纯形法的基本思路和原理,这样在下一步迭代的矩阵变换中可以确保新得到的bj值都大于等于零。在本例题中约束方程为 在第二步中已经知道x2为入基变量，我们把各约束方程中x2的为正的系数除对应的常量，得,以下就来看在找出了初始基本可行解和确定了入基变量之后，怎么样的基变量可以确定为出基变量呢？或者说出基变量要具有什么条件呢？,12,我们把确定出基变量的方法概括如下：把已确定的入基变量在各约束方程中的正的系数除其所在约束方程中的常数项的值，把其中最小比值所在的约束方程中的原基变量确定为出基变量。,13,1单纯形法的基本思路和原理,其中 的值最小，所以可以知道在原

11、基变量中系数向量为 的基变量s3为出基变量，这样可知x2，s1，s2为基变量，x1，s3为非基变量。 令非基变量为零，得 x2+s1=300, x2+s2=400, x2=250. 求解得到新的基本可行解x1=0,x2=250,s1=50,s2=150. 这时目标函数值为 50 x1+100 x2=500+100250=25000。 显然比初始基本可行解x1=0,x2=0,s1=300,s3=250时的目标函数值为0要好 得多。 下面我们再进行检验其最优性，如果不是最优解还要继续进行基变 换，直至找到最优解，或者能够判断出线性规划无最优解为止。,13,14,2单纯形法的表格形式,在讲解单纯形法

12、的表格形式之前，先从一般数学模型里推导出检验数 的表达式。 可行基为m阶单位矩阵的线性规划模型如下（假设其系数矩阵的前m列是单位矩阵）： 以下用 表示基变量，用 表示非基变量。,14,15,2单纯形法的表格形式,把第i个约束方程移项，就可以用非基变量来表示基变量xi， 把以上的表达式带入目标函数，就有 其中：,15,16,2单纯形法的表格形式,单纯形法的表格形式是把用单纯形法求出基本可行解、检验其最优性、迭代某步骤都用表格的方式来计算求出，其表格的形式有些像增广矩阵，而其计算的方法也大体上使用矩阵的行的初等变换。以下用单纯形表格来求解第二章的例1。 max 50 x1+100 x2+0s1+0

13、s2+0s3. x1+x2+s1=300， 2x1+x2+s2=400， x2+s3=250，,16,上面假设x1,x2,xm是基变量，即第i行约束方程的基变量正好是xi，而经过迭代后，基将发生变化，计算zj的式子也会发生变化。如果迭代后的第i行约束方程中的基变量为xBi，与xBi相应的目标函数系数为cBi，系数列向量为 则 其中，(cB)是由第1列第m行各约束方程中的基变量相应的目标函数依次组成的有序行向量。,17,2单纯形法的表格形式,17,x1, x2, s1, s2, s30. 把上面的数据填入如下的单纯形表格,按照线性规划模型在表中填入相对应的值，如上表所示； 在上表中有一个m*m的

14、单位矩阵，对应的基变量为s1,s2,s3； 在zj行中填入第j列与cB列中对应的元素相乘相加所得的值，如z2=0*1+0*1+0*1=0，所在zi行中的第2位数填入0；,18,在 行中填入cj-zj所得的值，如 ； z表示把初始基本可行解代入目标函数求得的目标函数值，即b列*cB列； 初始基本可行解为s1=300,s2=400,s3=250,x1=0,x2=0; 由于250/1最小，因此确定s3为出基变量； 由于 ，因此确定x2为入基变量。出基变量所在行，入基变量所在列的交汇处为主元，这里是a32=1，在表中画圈以示区别。,19,2单纯形法的表格形式,在上表中第3个基变量s1已被x2代替，故基

15、变量列中的第3个基变量应变为x2。由于第0次迭代表中的主元a32已经为1，因此第3行不变。为了使第1行的a12为0，只需把第3行*(-1)加到第1行即可。同样可以求得第2行。,以下进行第一次迭代，其变量为x2,s1,s2,通过矩阵行的初等变换，求出一个新的基本可行解，具体的做法用行的初等变换使得x2的系数向量p2变换成单位向量，由于主元在p2的第3 分量上，所以这个单位向量是 也就是主元素变成1。这样我们又得到的第1次迭代的单纯表如下所示。,20,2单纯形法的表格形式,求得第1次迭代的基本可s1=50,s2=150,x2=250,x1=0,s3=0,z=25000. 从上表可以看出，第一次迭代的 ，因此不是最优解。设x1为入基变量，从此值可知b1/a11=50为最小正数，因此，s1为出基变量，a11为主元，继续迭代如下表所示。 从上表中可知第二次迭代得到的基本可行解x1=50,x2=250,s1=0,s2=50, s3=0,这时z=27500。 由于检验数都0，因此所求得的基本可行解为最优解， z=27500为最优目标函数值。 实际上，我们可以连续地使用一个单纯形表，不必一次迭代重画一个表头。,21,2单纯形法的表格形式,Ex: min f = 3x1 - 2x2 + 5x3 s.t x1 + 2x2 + x35 -3x1 + x2 -