中国地质大学(北京)《运筹学》课件-第五章

中国地质大学(北京)运筹学第五章2第五章单纯形法

我们在第三章所介绍的线性规划问题的计算机解法就是基于单纯形法编程来解决可以含有上千个决策变量的及上千个约束条件的复杂的线性规划问题。3§1单纯形法的基本思路和原理

从可行域中某一个顶点开始，判断此顶点是否是最优解，如不是则再找另一个使得其目标函数值更优的顶点，称之为迭代，再判断此点是否是最优解。直到找到一个顶点为其最优解，就是使得其目标函数值最优的解，或者能判断出线性规划问题无最优解为止。4在这里，可行域的顶点已不再像图解法中那样直接可见了。在单纯形法中的可行域的顶点叫做基本可行解，第一个找到的可行域的顶点叫做初始基本可行解。

一、找出一个初始基本可行解在第二章的例1中我们得到以下数学模型：5目标函数：约束条件：在加上松弛变量之后我们可得到标准型如下：目标函数：函数条件：6以上约束条件中有三个约束方程如下：这是由三个五元线性方程组成的方程组，它的系数矩阵其中pj为系数矩阵A中第j列的向量。由于在A中存在一个不为零的三阶子式，可知A的秩为3。7因为A的秩m小于此方程组的变量的个数n，从线形代数的知识可知其有无数多组解。为了找到一个初始基本可行解，先介绍以下几个线性规划的基本概念。基：已知A是约束条件的m×n系数矩阵，其秩为m。若B是A中m×m

阶非奇异子矩阵（即可逆矩阵，|B|0），则称B是线性规划问题中的一个基。B是由A中m个线性无关的系数列向量组成的。在此例题中与都是该线性规划的一个基。

8它们都是由3个线性无关的系数列向量组成的。基向量：基B中的一列即称为一个基向量。基B中共有m个基向量，在此例题中对基B＝来说

，，都是B的基向量，B中只有这三个基向量。基变量：与基向量pj相应的变量xj叫基变量，基变量有m个，在此例题中，而x1，x2，s1是B的基变量。s2，s3是B的非基变量。9

由线性代数的知识知道，如果我们在约束方程组系数矩阵中找到了一个基，令这个基的非基变量为零，再求解这个m元线性方程组就可得到唯一的解了，这个解我们称之为线性规划的基本解，在此例中我们不妨找到了B＝为A的一个基，令这个基的非基变量x1，s2为零。这时约束方程就变为基变量的约束方程：10求解得到唯一基变量的一组解：x2＝400，s1＝－100，s3＝－150，再加上非基变量：x1＝0，s2＝0，就得到了此线性规划的一个基本解：

x1＝0，

x2＝400，s1＝－100，s2＝0，s3＝－150。

由于在这个基本解中s1＝－100，s3＝－150，不满足该线性规划最后一个变量非负的约束条件，显然不是此线性规划的可行解，一个基本解可以是可行解，也可以是非可行解，它们之间的主要区别在于其所有变量的解是否满足非负的条件。11我们把满足非负条件的一个基本解叫做基本可行解，并把这样的基叫做可行基。例如在本例题中我们选基为B＝，令其非基变量x2，s2为零，这样约束方程就变为基变量的约束方程：求解得到基变量的唯一解s3＝250，

x1＝200，s1＝100，加上非基变量：x2＝0，s2＝0，得到一个基本解：x1＝200，

x2＝0，s1＝100，s2＝0，s3＝250。12由于所有变量的解都大于等于零，可知此基本解也是基本可行解；B＝是可行基。一般说来判断一个基是否是可行基，只有在求出其基本解后，当其基本解所有变量的值都是大于等于零，才能判定这个解是基本可行解，这个基是可行基。那么我们能否在求解之前，就找到一个可行解呢？由于在线性规划的标准型中要求bj都大于等于零，如果我们能找到一个基是单位矩阵，或者说一个基是由单位矩阵的各列向量所组成（至于各列向量的前后顺序无关紧要的）13例如：那么显然所求得的基本解一定是基本可行解，这个单位矩阵或由单位矩阵各列向量组成的基一定是可行基。实际上这个基本可行解中的各个变量或等于某个bj或等于零。在本例题中我们就找到了一个基是单位矩阵B＝，令B的非基变量x1，x2都为零，约束方程组就变为14加上非基变量x1＝0，x2＝0，我们就得到了该线性规划的一个基本可行解：

x1＝0，

x2＝0，s1＝300，s2＝400，s3＝250。

像这样在第一次找可行基时，所找到的基或为单位矩阵或为由单位矩阵的各列向量所组成，称之为初始可行基，其相应的基本可行解叫初始基本可行解。如果找不到单位矩阵或由单位矩阵的各列向量组成的基作为初始可行基，具体做法在以后详细讲述。15二、最优性检验所谓最优性检验就是判断已求得的基本可行解是否是最优解。1、最优性检验的依据－－检验数

j

一般来说目标函数中既包括基变量，又包括非基变量。现在我们要求只用非基变量来表示目标函数，这只要在约束等式中通过移项等处理就可以用非基变量来表示基变量，然后用非基变量的表示式代替目标函数中基变量，这样目标函数中只含有非基变量了，16或者说目标函数中基变量的系数都为零了。此时目标函数中所有变量的系数即为各变量的检验数，把变量xi的检验数记为

i。显然所有基变量的检验数必为零。在本例题中目标函数为50x1+100x2。由于初始可行解中x1，x2为非基变量，所以此目标函数已经用非基变量表示了，不需要再代换出基变量了。这样我们可知

1＝50，

2＝100，

3＝0，

4＝0，

5＝0。2、最优解判别定理对于求最大目标函数的问题中，对于某个基本17所求得的基本可行解就使目标函数值最大为z0。在本例题中由于

1＝50，

2＝100，都大于零，显然这个基本可行解不是最优解，实际上让x1，x2为非基变量（即令其值为0）是最失策的，x1，x2在大于等于零的范围内，x1，x2不管取什么值也比其取零值要好，就能使得目标函数z的值比零更大。所以我们要找更好的基本可行解。对于求目标函数最小值的情况，只需把上述的定理中的

j

0，改为

j

0即可。至于如何来判断无最优解的方法我们将在后面用具体实例予以阐述。18三、基变换通过检验，我们知道这个初始基本可行解不是最优解。下面介绍如何进行基变换找到另一个新的可行解，具体的做法是从可行基中换一个列向量，得到一个新的可行基，使得求解得到的新的基本可行解，使得其目标函数值更优。为了换基就要确定换入变量与换出变量。1、入基变量的确定从最优判别定理知道，当某个

j

>0时，非基变量xj变为基变量不取零值可以使目标函数值增大,故我们19要选基检验数大于0的非基变量换到基变量中去（称之为入基变量）。若有两个以上的

j

>0，则为了使目标函数增加得更大些，一般选其中的

j

最大者的非基变量为入基变量，在本例题中

2＝100是检验数中最大的正数，故选x2为入基变量。2、出基变量的确定在确定了x2为入基变量之后，我们要在原来的3个基变量s1，s2，s3中确定一个出基变量，也就是确定哪一个基变量变成非基变量呢？如果我们确定s1为20出基变量，则新的基变量为x2，s2，s3，因为非基变量x1＝s1＝0，则从下式求得基本解：x1＝0，

x2＝300，s1＝0，s2＝100，s3＝－50。显然这不是基本可行解，所以s1不能作为出基变量。21如果把s3作为出基变量，则新的基变量为x2，s1，s2，因为非基变量x1＝s3＝0，我们也可以从下式：求出基本解：x1＝0，

x2＝250，s1＝50，s2＝150，s3＝0。

因为此解满足非负条件，是基本可行解，故s3可以确定为出基变量。能否在求出基本解以前来确定出基变量呢？22以下就来看在找出了初始基本可行解和确定了入基变量之后，怎么样的基变量可以确定为出基变量呢？或者说出基变量要具有什么条件呢？我们把确定出基变量的方法概括如下：把已确定的入基变量在各约束方程中的正的系数除以其所在约束方程中的常数项的值，把其中最小比值所在的约束方程中的原基变量确定为出基变量。这样在下一步迭代的矩阵变换中可以确保新得到的bj值都大于等于零。23

在本例题中约束方程为在第二步中已经知道x2为入基变量，我们把约束方程中的x2为正的系数除对应的常量，得24其中b3/a32的值最小，所以可以知道在原基变量中系数向量为e3=(0,0,1)T的基变量s3为出基变量，这样可知x2，s1，s2为基变量，x1，s3为非基变量。令非基变量为零，得：求解得到新的基本可行解：x1＝0，

x2＝250，s1＝50，s2＝150，s3＝0。

这时目标函数值为50

x1+100

x2＝2500，显然比25初始基本可行解x1＝0，

x2＝0，s1＝300，s2＝400，s3＝250时的目标函数值50×0+100×0＝0要好得多。下面我们再进行检验其最优性，不是最优解还要继续进行基变换，直至找到最优解，或者能够判断出线性规划无最优解为止。为了使单纯形法更加简洁明了，我们常常借助于单纯形法的表格形式。26§2单纯形法的表格形式

在讲单纯形法的表格形式之前，先从一般数学模型里推导出检验数

j的表达式。可行基为m阶单位矩阵的线性规划模型如下（假设其系数矩阵的前m列是单位矩阵）：27以下用xi(i=1,2,…,m)表示基变量，用xj(j=m+1,m+2,…,n)表示非基变量。把第i

个约束方程移项，就可以用非基变量来表示基变量xi，把以上的表达式代入目标函数，就有2829上面假设x1,

x2,…,xm是基变量，即第i行约束方程的基变量正好是xi，而经过若干次迭代后，基发生了若干次变化，一般不会是上述假设情况了，因此目标规划问题及其数学模型问题的提出： 目标规划是在线性规划的基础上，为适应经济管理多目标决策的需要而由线性规划逐步发展起来的一个分支。 由于现代化企业内专业分工越来越细，组织机构日益复杂，为了统一协调企业各部门围绕一个整体的目标工作，产生了目标管理这种先进的管理技术。目标规划是实行目标管理的有效工具，它根据企业制定的经营目标以及这些目标的轻重缓急次序，考虑现有资源情况，分析如何达到规定目标或从总体上离规定目标的差距为最小。目标规划问题及其数学模型例5.1某企业计划生产甲，乙两种产品，这些产品分别要在A,B,C,D四种不同设备上加工。按工艺文件规定，如表所示。ABCD单件利润甲11402乙22043最大负荷1281612问该企业应如何安排计划，使得计划期内的总利润收入为最大？目标规划问题及其数学模型解：设甲、乙产品的产量分别为x1，x2，建立线性规划模型：其最优解为x1＝4，x2＝2，z＊＝14元33上述计算zj的式子也应改变。如果迭代后的第i行约束方程中的基变量为xBi（不一定是xi），与xBi相应的目标函数系数为cBi

，而迭代后的系数列向量为p’j(j=1,2,…,n)，则其中，(CB)是由第1列第m行各约束方程中的基变量相应的目标函数系数依次组成的有序行向量。单纯形法的表格形式是把用单纯形法求出基本可行解、检验其最优性、迭代某步骤都用表格的方式34计算求出，其表格的形式有些像增广矩阵，而其计算的方法也大体上使用矩阵的行的初等变换。以下用单纯形表格来求解第二章的例1。

把上面的数据填入如下的单纯形表格35

迭代次数基变量CBx1x2s1s2s3b比值bi/

ai2501000000s1011100300300/1s2021010400400/1s300[1]001250250/1zj00000z＝0

j=

cj-zj50100000以下进行第一次迭代，其变量为s1，s2，s3，通过矩阵行的初等变换，求出一个新的基本可行解，具体的做法用行的初等变换使得x2的系数向量p2变