《广西大学MBA 管理运筹学 第五章 单纯形法课件》由会员分享，可在线阅读，更多相关《广西大学MBA 管理运筹学 第五章 单纯形法课件（75页珍藏版）》请在金锄头文库上搜索。
1、此法是求解线性规划问题的一种有效方法 本章的学习内容： 1、单纯形法的基本思路和原理 2、单纯形法的表格形式 3、求目标函数值最小的问题的单纯形表解法 4、几种特殊情况,图解法只能解决仅含有两个决策变量的线性规划的问题，对多于两个决策变量的线性规划问题，图 解法就显得无能为力了。在这一章里将介绍由美国数学家丹捷格(GB Dantgig) 1947提出的，得到最广泛应用的线性规划的代数算法单纯形法，这恐怕是在运筹学发展史上最辉煌的一笔，此算法是对运筹学算法的一次革命。在第三章所介绍的线性规划问题的计算机解法就是基于单纯形法原理来编程的。它可解决多个变量线性规划问题。在后来研究上还发明其它求解线性
2、规划的方法,如前苏联科学家发明的内点法、印度科学家发明的K算法等。,单纯形法的基本思路：从可行域中某一个顶点开始，判断此顶点是否是最优解，如不是则再找另一个使得其目标函数值更优的顶点，称之为迭代，再判断此点是否是最优解。直到找到一个顶点为其最优解，就是使得其目标函数值最优的解，或者能判断出线性规划问题无最优解为止 。 在这里，可行域的顶点已不再像图解法中那样直接可见了。在单纯形法中的可行域的顶点叫做基本可行解，第一个找到的可行域的顶点叫做初始基本可行解。下面通过第二章例1来介绍单纯形法。,在第二章的例1中我们得到以下数学模型： 目标函数： max Z=50X1+100X2 约束条件： X1+X
3、2300， 2 X1+X2400， X2250, X10, X20. 加上松弛变量后得到如下标准型： 目标函数：max Z=50X1+100X2 约束条件： X1+X2+S1=300, 2X1+X2+S2=400, X2+S3=250, X1,X2,S1,S2,S30,其中pj为系数矩阵A中第j列的向量。由于在A中存在一个不为零的三阶子式，可知A的秩为3。因为A的秩m小于此方程组的变量的个数n，从线性代数的知识可知其有无数多组解。为了找到一个初始基本可行解，先介绍一些线性规划的基本概念。,基：已知A是约束条件的mn系数矩阵，其秩为m。若B是A中mm阶非奇异子矩阵( 即可逆矩阵，B0)，则称B是
4、线性规划问题中的一个基。也即任一m阶的可逆矩阵都可作为基。,基向量：基B中的每一列即称为一个基向量。 基B中共有m个基向量，在此例中对于基B来说，三个列向量都是基向量，而且B只有这三个基向量。 非基向量：在A中除了基B之外的每一列称之为基B的非基向量。,基变量：与基向量pi相应的变量Xi叫基变量，基变量有m个，在此例题中X1，X2，S1都是B1的基变量，而S1，S2，S3是B2的基变量。 非基变量：与非基向量pj相应的变量Xj叫非基变量，非基变量有n-m个，在此例题中，S2，S3是B1的非基变量。而X1，X2是B2的非基变量。 基本解：由线性代数知识得：如果在约束方程组系数矩阵中找到一个基，令
5、这个基的非基变量为零。再求解这个方程组就可得到唯一解了，这个解称为线性规划的基本解。,可行解： 满足：,最优解： 满足目标函数：max Z=50X1+100X2 的可行解称为最优解。,的解称为可行解（注意包括了非负）。,X1+X2+S1=300,2X1+X2+S2=400,X2+S3=250,X1,X2,S1,S2,S30,由于在这个基本解中S1= -100，S3=- 150，不满足该线性规划S10，S30的约束条件，显然不是问题的可行解。,X1+X2+S1=300,2X1+X2+S2=400,X2+S3=250,X2+S1=300,X2=400,X2+S3=250,一个基本解可以是可行解，也
6、可以不是可行解。它们之间主要区别在于其所有变量的解是否满足非负条件。把满足非负条件的一个基本解叫做基本可行解，并把这样的基叫做可行基。 可行解、基本解、基本可行解和最优解的关系：,可行解,基本解,基本可行解,非可行解,最优解,关于基本解，可行解和基本可行解的概念：,注意首先要把模型变成标准型再判断。 可行解： 满足约束条件（包括非负性）的解称为可行解，但不一定含有基。 基本解： 找出一个基，令非基变量为0，再求出解，此解不一定满足非负性。 基本可行解： 既满足非负性又满足基本解的解称为基本可行解。,由于所有变量的解都大于等于零，可知此基本解是基本可行解。所以,是可行基。,判断一个基是否是可行基
7、，只有在求出其基本解以后，当其基本解所有变量的解都大于等于零，才能断定这个解是基本可行解，这个基是可行基。那么能否在求解之前就找到一个可行基呢?,当然可以啊，如果找到一个基是单位矩阵，或者说一个基是由单位矩阵的各列向量所组成，则所求得的基本解一定是基本可行解！,由于在线性规划的标准型中要求bj都大于等于零，如果找到一个基是单位矩阵，或者说一个基是由单位矩阵的各列向量所组成(至于各列向量的前后顺序是无关紧要的事), 例如 :,那么所求得的基本解一定是基本可行解，这个单位矩阵或由单位矩阵各列向量组成的基一定是可行基，为什么呢？,加上非基变量X1=0，X2=0，就得到了该线性规划的一个基本可行解：X
8、1=0,X2=0,S1=300, S2=400,S3=250.,实际上这个基本可行解中的各个变量或等于某个bj或等于零。在本例题中就找到了一个基是单位矩阵:,令B2的非基变量x1，x2 为零，则：,X1+X2+S1=300,2X1+X2+S2=400,X2+S3=250,S1=300,S2=400,S3=250,像这样在第一次找可行基时，所找到的基或为单位矩阵或为由单位矩阵的各列向量所组成，称之为初始可行基，其相应的基本可行解叫初始基本可行解。如果找不到单位矩阵或由单位矩阵的各列向量组成的基作为初始可行基，我们将构造初始可行基，具体做法在以后详细讲述。 这就是单纯形法的第一步。,所谓最优性检验
9、就是判断已求得的基本可行解是否是最优解。 1最优性检验的依据检验数j 一般来说目标函数中既包括基变量，又包括非基变量。现在要求只用非基变量来表示目标函数，这只要在约束等式中通过移项等处理就可以用非基变量来表示基变量，然后将非基变量的表示式代入目标函数中，这样目标函数中只含有非基变量了，或者说目标函数中基变量的系数都为零了。此时目标函数中所有变量的系数称为各变量的检验数，把变量Xj的检验数记为j ； 显然所有基变量的检验数必为零（因为基变量已被非基变量代替了）。,则非基变量为X1，X2。由于初始可行解中X1，X2 为非基变量，所以此目标函数已经用非基变量表示了，不需要用约束条件代换出基变量了。这
10、样可知1=50, 2=100, 3=0, 4=0, 5=0。,在本例题中目标函数为50X1+100X2。如果取基变量为：,如果取基变量为B1：,为求得检验数，通过移项等处理就可以用非基变量来表示基变量，基变量为X1、S1、S3，则非基变量为X2、S2。故在目标函数为Z=50X1+100X2中，只需将X1换为X2及S2的表达式即可。在约束条件X1+X2+S1=300，2X1+X2+S2=400，X2+S3=250只将二式变为 X1=200-X2/2-S2/2代入目标函数得：Z=1000+75X2-25S2， 可知1=0, 2=75, 3=0, 4=-25, 5=0。,其中，z0为常数项，J是所有
11、非基变量的下标集。由于所有的xj 的取值范围为大于等于零，当所有的j都小于等于零时，则j Xj0，要使目标函数（1）式的值最大，显然只有当j Xj 为零才最大。即把这些Xj取为非基变量(即令这些Xj的值为零)，所求得的基本可行解就使目标函数值最大为z0 。,在求最大值目标函数的问题中，对于某个基本可行解，如果所有检验数j0，则这个基本可行解是最优解。下面来解释最优解判别定理。设用非基变量表示的目标函数为如下形式,由于1=50，2=100都大于零，显然这个基本可行解不是最优解，实际上让X1，X2为非基变量(即令其值为0)是最失策的，X1, X2在大于等于零的范围内，X1，X2不管取什么值也比其取
12、零值要好，就能使得目标函数Z的值比零更大。所以要找更好的基本可行解。 而对于第二种情况取基变量为X1、S1、S3，检验数为1=0, 2=75, 3=0, 4=-25, 5=0。也不是都小于等于0,也不是最优解。 对于求目标函数最小值的情况，只需把上述的定理中的j0，改为j0即可。至于如何来判断无最优解的方法将在后面用具体实例予以阐述。,在本例题中当取基变量为,下面介绍如何进行基变换找到一个新的可行基，具体的做法是从可行基中换一个列向量，得到一个新的可行基，使得求解得到的新的基本可行解，使得其目标函数值更优。为了换基就要确定换入变量与换出变量。,x1,x2,从最优解判别定理知道，当某个j0时，非
13、基变量xj变为基变量（即不取零值）可以使目标函数值增大，故我们要选基检验数大于0的非基变量换到基变量中去(称之为入基变量)。若有两个以上的j0，则为了使目标函数增加得更大些，一般选其中的j 最大者的非基变量为入基变量，在本例题中2= 100是检验数中最大的正数，故选X2 为入基变量。,求得基本解：X1=0,X2=300,S1=0,S2=100,S3=-50. 显然这不是基本可行解，因为S30, 所以S1不能作为出基变量。,在确定了X2为入基变量之后，要在原来的3个基变量S1,S2,S3 中确定一个出基变量，也就是确定哪一个基变量变成非基变量呢?如果确定S1为出基变量，则新的基变量为X2,S2,
14、S3，因为非基变量X1=S1=0，则：,X1+X2+S1=300,2X1+X2+S2=400,X2+S3=250,X2=300,X2+S2=400,X2+S3=250,如果把s3作为出基变量呢？,求得基本解：X1=0,X2=250,S1=50,S2=150,S3=0. 因为此解满足非负条件，是基本可行解，故s3可以确定为出基变量。 同学们可试试能否把S2作为出基变量？ （不能因为此时解为X1=S2=0, S1=-100,S3=-150, X2=400）,则新的基变量为X2,S1,S2，因为非基变量X1=S3=0，则从下式：,X1+X2+S1=300,2X1+X2+S2=400,X2+S3=25
15、0,X2=300,X2+S1=400,X2+S2=250,以下就来看在找出了初始基本可行解和确定了入基变量之后，怎么样的基变量可以确定为出基变量呢? 确定出基变量的方法： 把已确定的入基变量在各约束方程中的正的系数除其所在约束方程中的常数项的值，把其中最小比值所在的约束方程中的原基变量确定为出基变量。这样在下一步迭代的矩阵变换中可以确保新得到的bj 值都大于等于零。,证明过程略。详情见P77-P80,啊！,重,要,在本例题中约束方程为 X1+X2+S1= 300， 2X1+X2+S2 =400， X2+S3=250 在第二步中已经知道X2为入基变量，把各约束方程中X2 的为正的系数除对应的常量
16、，得： b1/a12=300/1=300, b2/a22=400/1=400, b3/a32=250/1=250 其中 a12, a22, a32分别为X2所在约束方程的正系数， b1,b2b3分别对应约束方程常数项的值。 其中b3/a32的值最小，所以可以知道在原基变量中系数向量为e3=(0，0，1) 的基变量S3为出基变量，这样可知X2, S1，S2为基变量，X1，S3为非基变量。令非基变量为零，得： X2+S1= 300， X2+S2 =400， X2=250 求得新的可行解：X1=0, X2=250, S1=50, S2=150.,这时目标函数值为50X1+l00X2=500+100250=25000，显然比初始基本可行解X1=0，X2=0，S1=300，S2=400，S3=250时的目标函数值500+1000=0要好得多。下面我们再进
