管理运筹学单纯形法课件

王中昭制作王中昭制作此法是求解线性规划问题的一种有效方法此法是求解线性规划问题的一种有效方法 本章的学习内容：本章的学习内容：1、单纯形法的基本思路和原理、单纯形法的基本思路和原理2、单纯形法的表格形式、单纯形法的表格形式3、求目标函数值最小的问题的单纯形表解、求目标函数值最小的问题的单纯形表解法法4、几种特殊情况、几种特殊情况 第五章单纯形法第五章单纯形法此法是求解线性规划问题的一种有效方法 第五章单纯形法王中昭制作王中昭制作 图解法只能解决仅含有两个决策变量的线图解法只能解决仅含有两个决策变量的线性规划的问题，对多于两个决策变量的线性规性规划的问题，对多于两个决策变量的线性规划问题，图划问题，图 解法就显得无能为力了。在这一章解法就显得无能为力了。在这一章里将介绍由美国数学家丹捷格里将介绍由美国数学家丹捷格(GB Dantgig)1947提出的，得到最广泛应用的线性规划的代提出的，得到最广泛应用的线性规划的代数算法数算法单纯形法，这恐怕是在运筹学发展单纯形法，这恐怕是在运筹学发展史上最辉煌的一笔，此算法是对运筹学算法的史上最辉煌的一笔，此算法是对运筹学算法的一次革命。在第三章所介绍的线性规划问题的一次革命。在第三章所介绍的线性规划问题的计算机解法就是基于单纯形法原理来编程的。计算机解法就是基于单纯形法原理来编程的。它可解决多个变量线性规划问题。在后来研究它可解决多个变量线性规划问题。在后来研究上还发明其它求解线性规划的方法上还发明其它求解线性规划的方法,如前苏联科如前苏联科学家发明的内点法、印度科学家发明的学家发明的内点法、印度科学家发明的K算法算法等。等。图解法只能解决仅含有两个决策变量的线性规划的王中昭制作王中昭制作 单单纯纯形形法法的的基基本本思思路路：从从可可行行域域中中某某一一个个顶顶点点开开始始，判判断断此此顶顶点点是是否否是是最最优优解解，如如不不是是则则再再找找另另一一个个使使得得其其目目标标函函数数值值更更优优的的顶顶点点，称称之之为为迭迭代代，再再判判断断此此点点是是否否是是最最优优解解。直直到到找找到到一一个个顶顶点点为为其其最最优优解解，就就是是使使得得其其目目标标函函数数值值最最优优的的解解，或或者者能能判判断断出出线线性性规规划划问问题题无无最最优优解解为为止止。在在这这里里，可可行行域域的的顶顶点点已已不不再再像像图图解解法法中中那那样样直直接接可可见见了了。在在单单纯纯形形法法中中的的可可行行域域的的顶顶点点叫叫做做基基本本可可行行解解，第第一一个个找找到到的的可可行行域域的的顶顶点点叫叫做做初初始始基基本本可可行行解解。下下面面通通过过第第二二章章例例1来来介介绍绍单单纯形法。纯形法。5.1 单纯形法的基本思路和原理单纯形法的基本思路和原理 单纯形法的基本思路：从可行域中某一个顶点开始，王中昭制作王中昭制作在第二章的例在第二章的例1中我们得到以下数学模型：中我们得到以下数学模型：目标函数：目标函数：max Z=50X1+100X2约束条件：约束条件：X1+X2300，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一、找出一个初始基本可行解（可行域边一、找出一个初始基本可行解（可行域边界上一个点）界上一个点）在第二章的例1中我们得到以下数学模型：一、找出一个初始基本王中昭制作王中昭制作其其中中pj为为系系数数矩矩阵阵A中中第第j列列的的向向量量。由由于于在在A中中存存在在一一个个不不为为零零的的三三阶阶子子式式，可可知知A的的秩秩为为3。因因为为A的的秩秩m小小于于此此方方程程组组的的变变量量的的个个数数n，从从线线性性代代数数的的知知识识可可知知其其有有无无数数多多组组解解。为为了了找找到到一一个个初初始始基基本本可可行行解解，先先介介绍绍一一些些线线性性规规划划的基本概念。的基本概念。则约束条件组成的线性方程组的系数矩阵为：则约束条件组成的线性方程组的系数矩阵为：其中pj为系数矩阵A中第j列的向量。由于在A中存在一个不为零王中昭制作王中昭制作基基：已已知知A是是约约束束条条件件的的mn系系数数矩矩阵阵，其其秩秩为为m。若若B是是A中中mm阶阶非非奇奇异异子子矩矩阵阵(即即可可逆逆矩矩阵阵，B0)，则则称称B是是线线性性规规划划问问题题中中的的一一个个基基。也也即即任任一一m阶阶的的可逆矩阵都可作为基。可逆矩阵都可作为基。基：已知A是约束条件的mn系数矩阵，其秩为m。若B是A中m王中昭制作王中昭制作 基向量：基向量：基基B中的每一列即称为一个基向量。中的每一列即称为一个基向量。基基B中中共共有有m个个基基向向量量，在在此此例例中中对对于于基基B来来说说，三三个个列列向向量量都都是是基基向向量量，而而且且B只只有有这三个基向量。这三个基向量。非非基基向向量量：在在A中中除除了了基基B之之外外的的每每一一列列称称之之为基为基B的非基向量。的非基向量。基向量：基B中的每一列即称为一个基向量。王中昭制作王中昭制作基变量：基变量：基变量：基变量：与基向量与基向量pi相应的变量相应的变量Xi叫叫基变量基变量，基变，基变量有量有m个，在此例题中个，在此例题中X1，X2，S1都是都是B1的基变的基变量，而量，而S1，S2，S3是是B2的基变量。的基变量。非基变量：非基变量：非基变量：非基变量：与非基向量与非基向量pj相应的变量相应的变量Xj叫叫非基变非基变量量，非基变量有，非基变量有n-m个，在此例题中，个，在此例题中，S2，S3是是B1的非基变量。而的非基变量。而X1，X2是是B2的非基变量。的非基变量。基本解：基本解：由线性代数知识得：如果在约束方程组由线性代数知识得：如果在约束方程组系数矩阵中找到一个基，令这个基的非基变量为系数矩阵中找到一个基，令这个基的非基变量为零。再求解这个方程组就可得到唯一解了，这个零。再求解这个方程组就可得到唯一解了，这个解称为线性规划的解称为线性规划的基本解基本解。基变量：与基向量pi相应的变量Xi叫基变量，基变量有m个，在王中昭制作王中昭制作可行解：可行解：满足：满足：最优解最优解：满足目标函数：满足目标函数：max Z=50X1+100X2 的可行的可行解称为最优解。解称为最优解。的解称为可行解（注意包括了非负）。的解称为可行解（注意包括了非负）。X1+X2+S1=3002X1+X2+S2=400X2+S3=250X1,X2,S1,S2,S30可行解：最优解：的解称为可行解（注意包括了非负）。X1+X2王中昭制作王中昭制作 由于在这个基本解中S1=-100，S3=-150，不满足该线性规划S10，S30的约束条件，显然不是问题的可行解。X1+X2+S1=3002X1+X2+S2=400X2+S3=250X2+S1=300X2=400X2+S3=250 由于在这个基本解中S1=-100，S3=-150，不满王中昭制作王中昭制作一个基本解可以是可行解，也可以不是可行解。一个基本解可以是可行解，也可以不是可行解。它们之间主要区别在于其所有变量的解是否满它们之间主要区别在于其所有变量的解是否满足非负条件。足非负条件。把满足非负条件的一个基本解叫把满足非负条件的一个基本解叫做基本可行解，并把这样的基叫做可行基。做基本可行解，并把这样的基叫做可行基。可行解、基本解、基本可行解和最优解的关系：可行解、基本解、基本可行解和最优解的关系：可可可可行行行行解解解解基基基基本本本本解解解解基基基基本本本本可可可可行行行行解解解解非可行解非可行解非可行解非可行解最最最最优优优优解解解解一个基本解可以是可行解，也可以不是可行解。它们之间主要区别在王中昭制作王中昭制作关于基本解，可行解和基本可行关于基本解，可行解和基本可行解的概念：解的概念：注意首先要把模型变成标准型再判断。注意首先要把模型变成标准型再判断。可行解：可行解：满足约束条件（包括非负性）的解称为可行解，满足约束条件（包括非负性）的解称为可行解，但不一定含有基。但不一定含有基。基本解：基本解：找出一个基，令非基变量为找出一个基，令非基变量为0，再求出解，此，再求出解，此解不一定满足非负性。解不一定满足非负性。基本可行解：基本可行解：既满足非负性又满足基本解的解称为基本可行既满足非负性又满足基本解的解称为基本可行解。解。关于基本解，可行解和基本可行解的概念：注意首先要把模型变成标王中昭制作王中昭制作 由于所有变量的解都大于等于零，可知此基本解是基本可行解。所以 是可行基。由于所有变量的解都大于等于零，可知此基本解是基本可行解。所王中昭制作王中昭制作 判断一个基是否是可行基，判断一个基是否是可行基，只有在求出其基本解以后，当其只有在求出其基本解以后，当其基本解所有变量的解都大于等于基本解所有变量的解都大于等于零，才能断定这个解是基本可行零，才能断定这个解是基本可行解，这个基是可行基。那么能否解，这个基是可行基。那么能否在求解之前就找到一个可行基呢在求解之前就找到一个可行基呢?判断一个基是否是可行基，只有在求出其基本解以后王中昭制作王中昭制作也就是说你找到也就是说你找到的一个可行基能的一个可行基能否保证在求解之否保证在求解之后得到的解一定后得到的解一定是基本可行解吗是基本可行解吗？当然可以啊，如果找到一个基当然可以啊，如果找到一个基当然可以啊，如果找到一个基当然可以啊，如果找到一个基是单位矩阵，或者说一个基是是单位矩阵，或者说一个基是是单位矩阵，或者说一个基是是单位矩阵，或者说一个基是由单位矩阵的各列向量所组成，由单位矩阵的各列向量所组成，由单位矩阵的各列向量所组成，由单位矩阵的各列向量所组成，则所求得的基本解一定是基本则所求得的基本解一定是基本则所求得的基本解一定是基本则所求得的基本解一定是基本可行解！可行解！可行解！可行解！也就是说你找到的一个可行基能否保证在求解之后得到的解一定是基王中昭制作王中昭制作 由于在线性规划的标准型中要求由于在线性规划的标准型中要求bj都都大于等于零，如果找到一个基是单位矩大于等于零，如果找到一个基是单位矩阵，或者说一个基是由单位矩阵的各列阵，或者说一个基是由单位矩阵的各列向量所组成向量所组成(至于各列向量的前后顺序是至于各列向量的前后顺序是无关紧要的事无关紧要的事),例如例如:那么所求得的基本解一那么所求得的基本解一定是基本可行解，这个单位定是基本可行解，这个单位矩阵或由单位矩阵各列向量矩阵或由单位矩阵各列向量组成的基一定是可行基，为组成的基一定是可行基，为什么呢？什么呢？由于在线性规划的标准型中要求bj都大于等于零王中昭制作王中昭制作 加上非基变量加上非基变量X1=0，X2=0，就得到了该线性规划的一个，就得到了该线性规划的一个基本可行解：基本可行解：X1=0,X2=0,S1=300,S2=400,S3=250.实际上这个基本可行解中的各个变量或等于某实际上这个基本可行解中的各个变量或等于某个个bj或等于零。在本例题中就找到了一个基是单位或等于零。在本例题中就找到了一个基是单位矩阵矩阵:令令B2的非基变量的非基变量x1，x2 为零，为零，则：则：X1+X2+S1=3002X1+X2+S2=400X2+S3=250S1=300S2=400S3=250 加上非基变量X1=0，X2=0，就得到了该王中昭制作王中昭制作 像这样在第一次找可行基时，所找到的像这样在第一次找可行基时，所找到的基或为单位矩阵或为由单位矩阵的各列向基或为单位矩阵或为由单位矩阵的各列向量所组成，称之为初始可行基，其相应的量所组成，称之为初始可行基，其相应的基本可行解叫初始基本可行解。如果找不基本可行解叫初始基本可行解。如果找不到单位矩阵或由单位矩阵的各列向量组成到单位矩阵或由单位矩阵的各列向量组成的基作为初始可行基，我们将构造初始可的基作为初始可行基，我们将构造初始可行基，具体做法在以后详细讲述。行基，具体做法在以后详细讲述。这就是单纯形法的第一步。这就是单纯形法的第一步。注解注解 像这样在第一次找可行基时，所找到的基或为单位矩阵王中昭制作王中昭制作 所谓最优性检验就是判断已求得的基本可行解是否所谓最优性检验就是判断已求得的基本可行解是否所谓最优性检验就是判断已求得的基本可行解是否所谓最优性检验就是判断已求得的基本可行解是否是最优解。是最优解。是最优解。是最优解。1最优性检验的依据最优性检验的依据检验数检验数j 一般来说目标函数中既包括基变量，又包括非基变一般来说目标函数中既包括基变量，又包括非基变量。现在要求只用非基变量来表示目标函数，这只要在量。现在要求只用非基变量来表示目标函数，这只要在约束等式中通过移项等处理就可以用非基变量来表示基约束等式中通过移项等处理就可以用非基变量来表示基变量，然后将非基变量的表示式代入目标函数中，这样变量，然后将非基变量的表示式代入目标函数中，这样目标函数中只含有非基变量了，或者说目标函数中基变目标函数中只含有非基变量了，或者说目标函数中基变量的系数都为零了。量的系数都为零了。此时目标函数中所有变量的系数称此时目标函数中所有变量的系数称为各变量的检验数，把变量为各变量的检验数，把变量Xj的检验数记为的检验数记为j；显然显然所有基变量的检验数必为零（因为基变量已被非基变量所有基变量的检验数必为零（因为基变量已被非基变量代替了）。代替了）。二、最优性检验二、最优性检验 所谓最优性检验就是判断已求得的基本可行解是否王中昭制作王中昭制作 则非基变量为则非基变量为X1，X2。由于初始可行解中。由于初始可行解中X1，X2 为非基变量，所以此目标函数已经用非为非基变量，所以此目标函数已经用非基变量表示了，不需要用约束条件代换出基变基变量表示了，不需要用约束条件代换出基变量了。这样可知量了。这样可知1=50,2=100,3=0,4=0,5=0。在本例题中目标函数为在本例题中目标函数为50X1+100X2。如。如果取基变量为：果取基变量为：则非基变量为X1，X2。由于初始可行解中X1王中昭制作王中昭制作如果取基变量为如果取基变量为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。如果取基变量为B1：为求得检验数，通过移王中昭制作王中昭制作 其中，其中，z0为常数项，为常数项，J是所有非基变量的下标集。由是所有非基变量的下标集。由于所有的于所有的xj 的取值范围为大于等于零，当所有的的取值范围为大于等于零，当所有的j都小都小于等于零时，则于等于零时，则j Xj0，要使目标函数（，要使目标函数（1）式的值最）式的值最大，显然只有当大，显然只有当j Xj 为零才最大。即把这些为零才最大。即把这些Xj取为非取为非基变量基变量(即令这些即令这些Xj的值为零的值为零)，所求得的基本可行解就，所求得的基本可行解就使目标函数值最大为使目标函数值最大为z0。2.最优解判别定理最优解判别定理 在求最大值目标函数的问题中，对于某个基本可行在求最大值目标函数的问题中，对于某个基本可行在求最大值目标函数的问题中，对于某个基本可行在求最大值目标函数的问题中，对于某个基本可行解，如果所有检验数解，如果所有检验数解，如果所有检验数解，如果所有检验数 j j00，则这个基本可行解是最优解。，则这个基本可行解是最优解。，则这个基本可行解是最优解。，则这个基本可行解是最优解。下面来解释最优解判别定理。设用非基变量表示的目标下面来解释最优解判别定理。设用非基变量表示的目标函数为如下形式函数为如下形式 其中，z0为常数项，J是所有非基变量的下标集王中昭制作王中昭制作 由于由于1=50，2=100都大于零，显然这个基本可行解都大于零，显然这个基本可行解不是最优解，实际上让不是最优解，实际上让X1，X2为非基变量为非基变量(即令其值为即令其值为0)是最失策的，是最失策的，X1,X2在大于等于零的范围内，在大于等于零的范围内，X1，X2不不管取什么值也比其取零值要好，就能使得目标函数管取什么值也比其取零值要好，就能使得目标函数Z的值的值比零更大。所以要找更好的基本可行解。比零更大。所以要找更好的基本可行解。而对于第二种情况取基变量为而对于第二种情况取基变量为X1、S1、S3，检验数为，检验数为1=0,2=75,3=0,4=-25,5=0。也不是都小于等于。也不是都小于等于0,也也不是最优解。不是最优解。对于求目标函数最小值的情况，只需把上述的定理中对于求目标函数最小值的情况，只需把上述的定理中的的j0，改为，改为j0即可。至于如何来判断无最优解的方法即可。至于如何来判断无最优解的方法将在后面用具体实例予以阐述。将在后面用具体实例予以阐述。在本例题中当取基变量为在本例题中当取基变量为 由于1=50，2=100都大于零，显然这个基王中昭制作王中昭制作 下面介绍如何进行基变换找到一个新的可行下面介绍如何进行基变换找到一个新的可行基，具体的做法是从可行基中换一个列向量，得基，具体的做法是从可行基中换一个列向量，得到一个新的可行基，使得求解得到的新的基本可到一个新的可行基，使得求解得到的新的基本可行解，使得其目标函数值更优。为了换基就要确行解，使得其目标函数值更优。为了换基就要确定换入变量与换出变量。定换入变量与换出变量。三、基变换三、基变换x1x2基变换的实质就基变换的实质就是从一个顶点换是从一个顶点换到另一个顶点。到另一个顶点。下面介绍如何进行基变换找到一个新的可行基，具体的王中昭制作王中昭制作 从最优解判别定理知道，当某个从最优解判别定理知道，当某个从最优解判别定理知道，当某个从最优解判别定理知道，当某个 j j00时，非时，非时，非时，非基变量基变量基变量基变量x xj j变为基变量（即不取零值）可以使目变为基变量（即不取零值）可以使目变为基变量（即不取零值）可以使目变为基变量（即不取零值）可以使目标函数值增大，标函数值增大，标函数值增大，标函数值增大，故我们要选基检验数大于故我们要选基检验数大于0的的非基变量换到基变量中去非基变量换到基变量中去(称之为入基变量称之为入基变量)。若有两个以上的若有两个以上的j0，则为了使目标函数增加，则为了使目标函数增加得更大些，一般选其中的得更大些，一般选其中的j 最大者的非基变量最大者的非基变量为入基变量，在本例题中为入基变量，在本例题中2=100是检验数中最是检验数中最大的正数，故选大的正数，故选X2 为入基变量。为入基变量。1入基变量的确定入基变量的确定 从最优解判别定理知道，当某个j0时，非王中昭制作王中昭制作 求得基本解：求得基本解：X1=0,X2=300,S1=0,S2=100,S3=-50.显然这不是基本可行解，因为显然这不是基本可行解，因为S30)，迭代迭代次数次数基基变变量量CB X1 X2 S1 S2 S3 b比值比值 bi/ai2 50 100 0 0 0 0 S1 S2 S3 0 0 0 1 1 1 0 0 2 1 0 1 0 0 1 0 0 1 300 400 250 Zj j=Cj-Zj 0 0 0 0 0Z=0 50 100 0 0 0填完了此表，得初始基本可行解，S1=300，S2=400，王中昭制作王中昭制作迭代迭代次数次数基变基变量量CB X1 X2 S1 S2 S3 b比值比值 bi/ai2 50 100 0 0 0 0 S1 S2 S3 0 0 0 1 1 1 0 0 2 1 0 1 0 0 1 0 0 1 300 400 250 Zj j=Cj-Zj 0 0 0 0 0Z=0 50 100 0 0 0想想，如何进行迭代？为什么选取X2作为入基变量？迭代次数基变量 X1 X2 王中昭制作王中昭制作迭代迭代次数次数基变基变量量CB X1 X2 S1 S2 S3 b比值比值 bi/ai2 50 100 0 0 0 0 S1 S2 S3 0 0 0 1 1 1 0 0 2 1 0 1 0 0 1 0 0 1 300 400 250300/1400/1250/1 Zj j=Cj-Zj 0 0 0 0 0Z=0 50 100 0 0 0你怎么知道你怎么知道S3 为出为出基变量啊？基变量啊？32=1叫主元？郁闷！叫主元？郁闷！迭代次数基变量 X1 X2 王中昭制作王中昭制作迭代迭代次数次数基基变变量量CB X1 X2 S1 S2 S3 b 50 100 0 0 0 1 S1 S2 X2 0 0 100 0 1 0 0 1 250 Zj j=Cj-Zj 迭代迭代迭代迭代迭代迭代迭代迭代迭代迭代3行(-1)+2行3行(-1)+1行150-15000201-11011 1 1 0 0 3002 1 0 1 0 4000 1 0 0 1 25050/1150/2比值比值 bi/ai201000010050000-100Z=25000迭代次数基变量 X1 X2 王中昭制作王中昭制作又从又从1=500可知这个基本可行解也不是最优解。可知这个基本可行解也不是最优解。从从j 我们知道我们知道1为最大的正数，可知为最大的正数，可知X1为入基变为入基变量，从此值可知量，从此值可知b1/a11=50为为bi/ai1中最小的正数，中最小的正数，可知可知S1为出基变量，为出基变量，a11为主元，这样我们可以进为主元，这样我们可以进行第行第2次迭代后得下表：次迭代后得下表：迭代迭代次数次数基变基变量量CB X1 X2 S1 S2 S3 b比值比值 bi/ai2 50 100 0 0 0 2 X1 S2 X2 50 0 100 1 0 1 0 -1 0 0 -2 1 1 0 1 0 0 1 50 5025050/1150/2 Zj j=Cj-Zj 50 100 50 0 50 0 0 -50 0 -50Z=27500又从1=500可知这个基本可行解也不是最优解。从j 王中昭制作王中昭制作 从从表表中中可可知知基基本本可可行行解解为为X1=50，X2=250，S1=0,S2=50,S3=0，这这时时Z=27500。由由于于检检验验j 都都小小于于等等于于零零，此此基基本本可可行行解解为为最最优优解解，Z=27500为最优目标函数值。为最优目标函数值。迭代迭代次数次数基变基变量量CB X1 X2 S1 S2 S3 b比值比值 bi/ai2 50 100 0 0 0 2 X1 S2 X2 50 0 100 1 0 1 0 -1 0 0 -2 1 1 0 1 0 0 1 50 5025050/1150/2 Zj j=Cj-Zj 50 100 50 0 50 0 0 -50 0 -50Z=27500 从表中可知基本可行解为X1=50，X2=250王中昭制作王中昭制作第二章例第二章例2的数学模型如下：的数学模型如下：目标函数目标函数:min f=2X1+3X2.约束条件：约束条件：X1+X2350，X1125，2X1+X2600，X1，X20 其约束条件的标准型如下：其约束条件的标准型如下：X1+X2-S1=350，X1-S2=125，2X1+X2+S3=600，X1，X2,S1,S2，S305.3 求目标函数值最小的线性规划问求目标函数值最小的线性规划问题的单纯形表解法题的单纯形表解法第二章例2的数学模型如下：5.3 求目标函数值最小的线性规王中昭制作王中昭制作 至于目标函数，在标准型中并不一定要至于目标函数，在标准型中并不一定要求求最大值或最小值，但是为了使单纯形表求求最大值或最小值，但是为了使单纯形表解法有一个统一的解法，我们把所有求目标解法有一个统一的解法，我们把所有求目标函数最小值的问题化成求目标函数最大值的函数最小值的问题化成求目标函数最大值的问题。具体做法只要把目标函数乘以问题。具体做法只要把目标函数乘以(-1)，就把原来求目标函数最小值的问题化成了求就把原来求目标函数最小值的问题化成了求目标函数最大值的问题。本例题的目标函数目标函数最大值的问题。本例题的目标函数就化为了：就化为了：目标函数：目标函数：max (-f)=-2X1-X2为了统一符号，不妨设为了统一符号，不妨设Z=-f，这样目标，这样目标函数就写成函数就写成:max Z=-2X1-3X2 至于目标函数，在标准型中并不一定要求求最大值或最王中昭制作王中昭制作在标准型的约束方程的系数矩阵里，找不到在标准型的约束方程的系数矩阵里，找不到3阶单位阵阶单位阵或单位向量或单位向量。注意负的单位向量与单位向量是不同的，。注意负的单位向量与单位向量是不同的，用负的单位向量作基向量求得的基本解一般不满足非用负的单位向量作基向量求得的基本解一般不满足非负条件，不是可行解。这样我们就分别在第负条件，不是可行解。这样我们就分别在第1、第、第2个个约束方程中加上人工变量约束方程中加上人工变量a1,a2(aartificial的第一个的第一个字母字母)，这样的约束条件就变成了如下的形式：，这样的约束条件就变成了如下的形式：X1+X2-S1+a1=350，X1-S2+a2=125，2X1+X2+S3=600，X1，X2,S1,S2,a1,a20这这样样在在约约束束方方程程的的系系数数矩矩阵阵中中就就可可找找到到单单位位向向量量e3，e1，e2了了,这这时时可可知知基基变变量量为为s3,a1,a2，初初始始基基本本可可行行解解为为 X1=0,X2=0,S1=0,S2=0,S3=600,a1=350,a2=125.管理运筹学单纯形法课件王中昭制作王中昭制作M 人工变量的含义 人工变量是与松弛、剩余变量不同的。松弛变量、人工变量是与松弛、剩余变量不同的。松弛变量、剩余变量它们可以取零值，也可以取正值，而人工变剩余变量它们可以取零值，也可以取正值，而人工变量只能取零值。一旦人工变量取正值，则有人工变量量只能取零值。一旦人工变量取正值，则有人工变量的约束方程和原始的约束方程就不等价了，这样所求的约束方程和原始的约束方程就不等价了，这样所求得的解就不是原线性规划的解了。得的解就不是原线性规划的解了。为了保证人工变量为了保证人工变量为零，规定人工变量在目标函数中的系数为为零，规定人工变量在目标函数中的系数为-M，这，这里里M为任意大的数。这样只要人工变量为任意大的数。这样只要人工变量0，所求的目，所求的目标函数最大值就是一个任意小的数。这样为了使目标标函数最大值就是一个任意小的数。这样为了使目标函数实现最大就必须把人工变量从基变量中换出。如函数实现最大就必须把人工变量从基变量中换出。如果一直到最后，人工变量仍不能从基变量中换出，即果一直到最后，人工变量仍不能从基变量中换出，即人工变量仍不为零，则该问题无可行解。人工变量仍不为零，则该问题无可行解。这样此例的这样此例的目标函数就写为：目标函数就写为：max Z=-2X1-3X2-M a1-M a2 人工变量的含义 人工变量是与松弛、剩余变量不王中昭制作王中昭制作此例的数学模型如下所示：此例的数学模型如下所示：max z=-2X1-3X2-Ma1-Ma2 s.t X1+X2-S1+a1=350，X1-S2+a2=125，2X1+X2+S3=600，X1，X2,S1,S2,a1,a20 像这样，为了构造初始可行基得到初始可行解，把像这样，为了构造初始可行基得到初始可行解，把人工变量人工变量“强行强行”地加到原来的约束方程中去，又为地加到原来的约束方程中去，又为了尽力地把人工变量从基变量中替换出来，就令人工了尽力地把人工变量从基变量中替换出来，就令人工变量在求最大值的目标函数里的系数为变量在求最大值的目标函数里的系数为-M，这个方法，这个方法叫做大叫做大M法，法，M叫做罚因子。下面我们就用大叫做罚因子。下面我们就用大M法来法来求解此题。求解此题。此例的数学模型如下所示：像这样，为了构造初始可行基王中昭制作王中昭制作迭代迭代次数次数基变基变量量CBx1x2s1s2s3a1a2 b比值比值-2-3000-M-M0 a1-M11-10010350350/1 a2-M100-1001125125/1 s3 02100100600600/2 Zj j=cj-zj-2M-MMM0-M-M-475M-2+2M-3+M-M-M0001 a1-M01-1101-1225225 x1-2100-1001125 s30010210-2350350/2 Zjj=cj-zj-2-MM-M+20-MM-2-225M-2500-3+M-MM-2002-2M迭代次数基变量x1x2s1s2s3a1a2-2-3000-M王中昭制作王中昭制作迭代迭代次数次数基变基变量量CBx1x2s1s2s3a1a2 b比值比值-2-3000-M-M2 a1-M01/2-10-1/2105050/(1/2)x1-211/2001/200300300/(1/2)s2 001/2011/20-1175175/(1/2)Zj j=cj-zj-2-M/2-1M0-M/2-1-M0-50M-6000M/2-2-M0M/2+10-M3 x2-301-20-120100 x1-210101-10250 s2000111-1-1125 Zjj=cj-zj-2-3401-40-80000-40-1-M+4-M迭代次数基变量x1x2s1s2s3a1a2-2-3000-M王中昭制作王中昭制作 在在第第2次次迭迭代代的的检检验验数数中中X2 的的检检验验数数为为M/2-2，S3 的的检检验验数数为为M/2+1，由由于于M为为任任意意大大的的数数，我我们们可可以以认认为为这这两两个个数数一一样样大大，这这时时最最好好选选决决策策变变量量而而不不是是选选松松弛弛、剩剩余余或或人人工工变变量量为为入入基基变变量量。这这样样就就可能用较少次的迭代就能找到最优解，可能用较少次的迭代就能找到最优解，注意啊！注意啊！从上表中可知其基本可行解：从上表中可知其基本可行解：X1=250,X2=100,S1=0,S2=125,S3=0,a1=0,a2=0是本例题的最优解，是本例题的最优解，其最优值为其最优值为 f=-z=-(-800)=800。因为第。因为第3次迭代的所次迭代的所有的检验数都小于等于零。有的检验数都小于等于零。在第2次迭代的检验数中X2 的检验数为M/2-王中昭制作王中昭制作如果没有单位矩阵，约束条件的等式如果没有单位矩阵，约束条件的等式也可设计人工变量也可设计人工变量例如例如 Max Z=3X1-X2-X3 st X1-2X2+X311 -4X1+X2+2X33 -2X1+X3=1 X1,X2,X30约束条件加上松驰和剩余变量后为：约束条件加上松驰和剩余变量后为：X1-2X2+X3+S1=11 -4X1+X2+2X3-S2=3 -2X1+X3=1 X1,X2,X30 仍未有单位矩阵，在第二、三约束上分别加上人工变仍未有单位矩阵，在第二、三约束上分别加上人工变量量a1,a2得：得：如果没有单位矩阵，约束条件的等式也可设计人工变量例如 M王中昭制作王中昭制作Max Z=3X1-X2-X3-Ma1-Ma2 st X1-2X2+X3+S1=11 -4X1+X2+2X3-S2+a1=3 -2X1+X3+a2=1 X1,X2,X30则基变量为则基变量为S1，a1,a2。这样就可进。这样就可进行求解了。行求解了。除了大除了大M法外，还有两阶段法（略）法外，还有两阶段法（略）Max Z=3X1-X2-X3-Ma1-Ma2王中昭制作王中昭制作一、无可行解一、无可行解.例例1求解下列线性规划问题求解下列线性规划问题 目标函数：目标函数：max Z=20X1+30X2 约束条件：约束条件：3X1+10X2150，X130，X1+X240，X1,X20 解解：在在上上述述问问题题的的约约束束条条件件中中加加入入松松弛弛变变量量，剩剩余余变量，人工变量得到：变量，人工变量得到：目标函数：目标函数：max Z=20X1+30X2-Ma1 约束条件：约束条件：3X1+10X2+S1=150，X1+S2=30,X1+X2-S3+a1=40 X1,X2,S1,S2,S3,a105.4几种特殊情况几种特殊情况一、无可行解.例1求解下列线性规划问题5.4几种王中昭制作王中昭制作迭代迭代次数次数基基变变量量CBx1x2s1s2s3a1 b比值比值2030000-M0 s103101000150150/10 s2010010030 a1-M1100-114040/1 Zj j=cj-zj-M-M00M-M-40M20+M30+M00-M01 x2303/1011/100001515/(3/10)s201001003030/1 a1-M7/100-1/100-112525/(7/10)Zjj=cj-zj9-7M/10303+M/100M-M450-25M11+7M/100-3-M/100-M0迭代次数基变量x1x2s1s2s3a12030000-M s王中昭制作王中昭制作 所有的检验数所有的检验数j 都小于等于零，可知最优解为：都小于等于零，可知最优解为：X1=30,X2=6,S1=0,S2=0,S3=0,a1=40，其目标函数值，其目标函数值为为780-4M。把最优解。把最优解S3=0,a1=4 代入第代入第3个约束方程得个约束方程得X1+X2-S3+a1=40，即有：，即有：X1+X2=3640并不满足原来并不满足原来的约束条件的约束条件3:X1+X240,可知原线性规划问题无可行解，可知原线性规划问题无可行解，或者说其可行域为空集。或者说其可行域为空集。故这样只要线性规划的最优解故这样只要线性规划的最优解里有人工变量大于零，则此问题无可行解。里有人工变量大于零，则此问题无可行解。迭代迭代次数次数基变基变量量CBX1X2S1S2S3a1 b比值2030000-M2 X230011/10-3/10006X12010010030 a1-M00-1/10-7/10-114 Zj j=cj-zj20303+M/1011+7M/10M-M780-4M00-3-M/10-11-7M/10-M0 所有的检验数j 都小于等于零，可知最优解为：X王中昭制作王中昭制作 如果在最后的迭代时，所如果在最后的迭代时，所如果在最后的迭代时，所如果在最后的迭代时，所有检验数都小于或等于零，有检验数都小于或等于零，有检验数都小于或等于零，有检验数都小于或等于零，而人工变量仍然是基变量，而人工变量仍然是基变量，而人工变量仍然是基变量，而人工变量仍然是基变量，但人工变量取值为零，这时但人工变量取值为零，这时但人工变量取值为零，这时但人工变量取值为零，这时问题有解吗？问题有解吗？问题有解吗？问题有解吗？如果在最后的迭代时，所有检验数都小于或等于零，而王中昭制作王中昭制作 在在求求目目标标函函数数最最大大值值的的问问题题中中，所所谓谓无无界界解解是是指指在在约约束束条条件件下下目目标标函函数数值值可可以以取取得得任任意意的的大大。下下面面用单纯形表来求解第二章中的例子（用单纯形表来求解第二章中的例子（P15）。）。例例2、用单纯形表求：、用单纯形表求：目标函数：目标函数：max Z=X1+X2，约束条件：约束条件：X1-X21,-3X1+2X26，X10，X20解解：在在上上述述的的约约束束条条件件中中加加入入松松弛弛变变量量，得得标标准准型型如下：如下：max Z=X1+X2，S.t.X1-X2+S1=1,-3X1+2X2+S2=6，X10，X20二、无界解二、无界解 在求目标函数最大值的问题中，所谓无界解是指在约束王中昭制作王中昭制作 从从第第1次次迭迭代代的的2=2，得得基基本本可可行行解解X1=1,X2=0,S1=0，S2=9不不是是最最优优解解。如如果果进进行行第第2次次迭迭代代，那那么么选选X2为为入入基基变变量量，因因为为a12=-1，a22=-1,找找不不到到大大于于零零的的aij来来确确定定出出基基变变量量。碰碰到到这这种种情情况况可可以以断断定定此此问问题题是是无无界界的的，即此目标函数值可以取到无限大。即此目标函数值可以取到无限大。迭代迭代次数次数基变基变量量CB X1 X2 S1 S2 b比值比值 1 1 0 00 S1 S200 1 -1 1 0161-3 2 0 1 Zj j=cj-zj 0 0 0 0Z=0 1 1 0 01 X1 S210 1 -1 1 019 0 -1 3 1 Zjj=cj-zj 1 -1 1 0 1 0 2 -1 0 从第1次迭代的2=2，得基本可行解X1=1,X王中昭制作王中昭制作从从1次迭代的单纯形表中，得到约束方程次迭代的单纯形表中，得到约束方程:X1-X2+S1=1 -X2+3S1+S2=9移项得：移项得：X1=1+X2-S1 S2=X2-3S1+9 ，不妨设，不妨设X2=M,S1=0,得一组解：得一组解：X1=M+1,X2=M,S1=0,S2=M+9,显然这是此线性规划的可行解，此时目标函数显然这是此线性规划的可行解，此时目标函数:Z=X1+X2=M+1+M=2M+1 由于由于M可以是任意大的正数，可知此目标函数值无界。可以是任意大的正数，可知此目标函数值无界。警告各位！在某次迭代的单纯形表中（不要求是警告各位！在某次迭代的单纯形表中（不要求是警告各位！在某次迭代的单纯形表中（不要求是警告各位！在某次迭代的单纯形表中（不要求是最终单纯形表），如果存在着一个大于零的检验最终单纯形表），如果存在着一个大于零的检验最终单纯形表），如果存在着一个大于零的检验最终单纯形表），如果存在着一个大于零的检验数数数数 j j ，并且该列的系数向量的每个元素，并且该列的系数向量的每个元素，并且该列的系数向量的每个元素，并且该列的系数向量的每个元素a a ij ij(i=1(i=1，2,m)2,m)都小于或等于零，则此线性规划问题是无都小于或等于零，则此线性规划问题是无都小于或等于零，则此线性规划问题是无都小于或等于零，则此线性规划问题是无界的，一般地说此类问题的出现是由于建模的错界的，一般地说此类问题的出现是由于建模的错界的，一般地说此类问题的出现是由于建模的错界的，一般地说此类问题的出现是由于建模的错误所引起的。误所引起的。误所引起的。误所引起的。从1次迭代的单纯形表中，得到约束方程:王中昭制作王中昭制作 例例3用单纯形表求解下面的线性规划问题。用单纯形表求解下面的线性规划问题。目标函数：目标函数：max Z=50X1+50X2，约束条件：约束条件：X1+X2300，2 X1+X2400，X2250,X10,X20.解：用单纯形表来解，引入松弛变量解：用单纯形表来解，引入松弛变量S1,S2,S3,得得标准型：标准型：max Z=50X1+50X2，X1+X2+S1=300,2X1+X2+S2=400,X2+S3=250,X1,X2,S1,S2,S30，填入单纯形表得：填入单纯形表得：三、无穷多最优解三、无穷多最优解 例3用单纯形表求解下面的线性规划问题。三、无穷多最优解王中昭制作王中昭制作迭代次迭代次数数基变基变量量CB X1 X2 S1 S2 S3 b比值比值 50 50 0 0 00 S1 S2S3000 1 1 1 0 0300400250300/1400/1250/1 2 1 0 1 0 0 1 0 0 1 Zj j=cj-zj 0 0 0 0 00 50 50 0 0 01 S1 S2X20050 1 0 1 0 -15015025050/1150/2 2 0 0 1 -1 0 1 0 0 1 Zjj=cj-zj 0 50 0 0 50 12500 50 0 0 0 0迭代次数基变量 X1 X2 王中昭制作王中昭制作得最优解为得最优解为X1=50,X2=250,S1=0,S2=50,S3=0,最优值最优值为为15000。这个最优解是否是唯一的呢。这个最优解是否是唯一的呢?由于在第由于在第2次迭次迭代中除了基变量的检验数代中除了基变量的检验数1,2,4 等于零外，等于零外，非基变非基变量量s3 的检验数也等于零，这样可以断定此问题有无穷的检验数也等于零，这样可以断定此问题有无穷多最优解。多最优解。不妨把检验数也为零的非基变量选为入基不妨把检验数也为零的非基变量选为入基变量进行第变量进行第3次迭代。可求得另一个基本可行解：次迭代。可求得另一个基本可行解：迭代迭代次数次数基基变变量量CB X1 X2 S1 S2 S3 b比值比值 50 50 0 0 02 X1 S2X250050 1 0 1 0 -1505025050/1250/1 0 0 -2 1 1 0 1 0 0 1 Zj j=cj-zj 50 50 50 0 015000 0 0 -50 0 0得最优解为X1=50,X2=250,S1=0,S2=王中昭制作王中昭制作从检验数可知此基本可行解从检验数可知此基本可行解X1=100,X2=200,S1=0,S2=0,S3=50，也是最优解。，也是最优解。迭代迭代次数次数基基变变量量CB X1 x2 s1 s2 s3 b比值比值 50 50 0 0 03 x1 s3x250050 1 0 -1 1 010050200 0 0 -2 1 1 0 1 2 -1 0 Zj j=cj-zj 50 50 50 0 015000 0 0 -50 0 0从检验数可知此基本可行解X1=100,X2=200,S王中昭制作王中昭制作从图解法可知连接这两点的线段上的任一点都是此从图解法可知连接这两点的线段上的任一点都是此线性规划的最优解，不妨用向量线性规划的最优解，不妨用向量Z1，Z2表示上述两表示上述两个最优解即个最优解即Z1=(50，250，0，50，0)，Z2=(100，200，0，0，50)，则线段上的任一点，即，则线段上的任一点，即可表示为可表示为Z1+（1-）Z2，其中，其中0l。如下图所示：。如下图所示：x2100400100300 x1Z2250200Z1X1+X2=3002X1+X2=400目标函数目标函数Z=50 x1+50 x25000=50 x1+50 x2从图解法可知连接这两点的线段上的任一点都是此线性规划的最优解王中昭制作王中昭制作问题：在一个已得到问题：在一个已得到问题：在一个已得到问题：在一个已得到最优解的单纯形表中，最优解的单纯形表中，最优解的单纯形表中，最优解的单纯形表中，如果存在一个非基变如果存在一个非基变如果存在一个非基变如果存在一个非基变量的检验数量的检验数量的检验数量的检验数 s s 为零，为零，为零，为零，为什么当把这个非基为什么当把这个非基为什么当把这个非基为什么当把这个非基变量变量变量变量x xs s 作为入基变量作为入基变量作为入基变量作为入基变量进行迭代时得到的新进行迭代时得到的新进行迭代时得到的新进行迭代时得到的新的基本解仍为最优解的基本解仍为最优解的基本解仍为最优解的基本解仍为最优解呢呢呢呢?问题：在一个已得到最优解的单纯形表中，如果存在一个非基变量的王中昭制作王中昭制作 判断线性规划有无穷多最优解的方法：判断线性规划有无穷多最优解的方法：对于某个最优的基本可行解，如对于某个最优的基本可行解，如果存在某个（或果存在某个（或1个以上）非基变量的个以上）非基变量的检验数为零，则此线性规划问题有无检验数为零，则此线性规划问题有无穷多最优解。穷多最优解。证明过程略，详见证明过程略，详见P92-P93（即证明了（即证明了其他非基变量的检验数不变，仍然是其他非基变量的检验数不变，仍然是小于等于零，估新的基本可行解仍然小于等于零，估新的基本可行解仍然是最优解）是最优解）判断线性规划有无穷多最优解的方法：王中昭制作王中昭制作在单纯形法计算过程中，确定出基变量时有时存在在单纯形法计算过程中，确定出基变量时有时存在两个以上相同的最小比值，这样在下一次迭代中就两个以上相同的最小比值，这样在下一次迭代中就有了一个或几个基变量等于零，这称之为退化。有了一个或几个基变量等于零，这称之为退化。例例4、用单纯形表求解下列线性规划问题。、用单纯形表求解下列线性规划问题。目标函数：目标函数：max Z=2X1+3X3/2 约束条件：约束条件：X1-X22,2X1+X34,X1+X2+X33,X1,X2,X30加上松弛变量加上松弛变量S1，S2,S3 化为标准型并填入单纯形表化为标准型并填入单纯形表得：得：四、退化问题四、退化问题在单纯形法计算过程中，确定出基变量时有时存在两个以上相同的最王中昭制作王中昭制作迭代迭代次数次数基变基变量量CB X1 X2 X3 S1 S2 S3 b比比值值 2 0 3/2 0 0 00 S1 S2S3000 1 -1 0 1 0 02432/14/23/1 2 0 1 0 1 0 1 1 1 0 0 1 Zj j=cj-zj 0 0 0 0 0 00 2 0 3/2 0 0 01 X1 S2S3200 1 -1 0 1 0 02010/21/2 0 2 1 -2 1 0 0 2 1 -1 0 1 Zjj=cj-zj 2 -2 0 0 0 0 4 0 2 3/2 -2 0 0比值相同比值相同迭代次数基变量 X1 X2 王中昭制作王中昭制作迭代迭代次数次数基基变变量量CB X1 X2 X3 S1 S2 S3 b比值比值 2 0 3/2 0 0 02 X1 X2S3200 1 0 1/2 0 1/2 02012/(1/2)0/(1/2)0 1 1/2 -1 1/2 0 0 0 0 1 -1 1 Zj j=cj-zj 2 0 1 0 1 04 0 0 1/2 0 -1 0 可以看到在可以看到在0次迭代栏中，由于比值次迭代栏中，由于比值b1/a11=b2/a21=2为最小为最小比值，导致在第比值，导致在第1次迭代中出现了退化，基变量次迭代中出现了退化，基变量S2=0。又由于。又由于在第在第1次迭代次迭代 出现了退化，基变量出现了退化，基变量S2=0，又导致第，又导致第2次迭代所次迭代所取得的目标函数值并没有得到改善，仍然与第取得的目标函数值并没有得到改善，仍然与第1次迭代的一样次迭代的一样都等于都等于4。像这样继续迭代而得不到目标函。像这样继续迭代而得不到目标函 数的改善，当然减数的改善，当然减低了单纯形算法的效率，但一般来说还是可以得到最优解的。低了单纯形算法的效率，但一般来说还是可以得到最优解的。像本题继续计算如下：像本题继续计算如下：迭代次数基变量 X1 X2 王中昭制作王中昭制作迭代迭代次数次数基变基变量量CB X1 X2 X3 S1 S2 S3 b比比值值 2 0 3/2 0 0 03 X1 X3S323/20 1 -1 0 1 0 02012/11/1 0 2 1 -2 1 0 0 0 0 1 -1 1 Zj j=cj-zj 2 1 3/2 -1 3/2 04 0 -1 0 1 -3/2 0 X1 X3S123/20 1 -1 0 0 1 -1121 0 2 1 0 -1 2 0 0 0 1 -1 1 Zjj=cj-zj 2 1 3/2 0 1/2 1 5 0 -1 0 0 -1/2 -1迭代次数基变量 X1 X2 王中昭制作王中昭制作 这样得到了最优解这样得到了最优解X1=2,X2=0,X3=2,S1=1,S2=0,S3=0，其最优值为，其最优值为5。但有时候当出现退化时，即使存在最优但有时候当出现退化时，即使存在最优解，而迭代过程总是重复解的某一部分解，而迭代过程总是重复解的某一部分迭代过程，出现了计算过程的循环，目迭代过程，出现了计算过程的循环，目标函数值总是不变，永远达不到最优解。标函数值总是不变，永远达不到最优解。下面一个是由下面一个是由EBeale给出的循环的给出的循环的例