管理学管理运筹学单纯形法课件

此法是求解线性规划问题的一种有效方法本章的学习内容：§1、单纯形法的基本思路和原理§2、单纯形法的表格形式§3、求目标函数值最小的问题的单纯形表解法4、几种特殊情况

第五章单纯形法此法是求解线性规划问题的一种有效方法第五章单纯形法

图解法只能解决仅含有两个决策变量的线性规划的问题，对多于两个决策变量的线性规划问题，图解法就显得无能为力了。在这一章里将介绍由美国数学家丹捷格(G·B·Dantgig)1947提出的，得到最广泛应用的线性规划的代数算法——单纯形法，这恐怕是在运筹学发展史上最辉煌的一笔，此算法是对运筹学算法的一次革命。在第三章所介绍的线性规划问题的计算机解法就是基于单纯形法原理来编程的。它可解决多个变量线性规划问题。在后来研究上还发明其它求解线性规划的方法,如前苏联科学家发明的内点法、印度科学家发明的K算法等。图解法只能解决仅含有两个决策变量的线性规划的

单纯形法的基本思路：从可行域中某一个顶点开始，判断此顶点是否是最优解，如不是则再找另一个使得其目标函数值更优的顶点，称之为迭代，再判断此点是否是最优解。直到找到一个顶点为其最优解，就是使得其目标函数值最优的解，或者能判断出线性规划问题无最优解为止。在这里，可行域的顶点已不再像图解法中那样直接可见了。在单纯形法中的可行域的顶点叫做基本可行解，第一个找到的可行域的顶点叫做初始基本可行解。下面通过第二章例1来介绍单纯形法。§5.1单纯形法的基本思路和原理单纯形法的基本思路：从可行域中某一个顶点开始，在第二章的例1中我们得到以下数学模型：目标函数：maxZ=50X1+100X2约束条件：X1+X2≤300，2X1+X2≤400，X2≤250,X1≥0,X2≥0.加上松弛变量后得到如下标准型：目标函数：maxZ=50X1+100X2约束条件：X1+X2+S1=300,2X1+X2+S2=400,X2+S3=250,X1,X2,S1,S2,S3≥0一、找出一个初始基本可行解（可行域边界上一个点）在第二章的例1中我们得到以下数学模型：一、找出一个初始基本其中pj为系数矩阵A中第j列的向量。由于在A中存在一个不为零的三阶子式，可知A的秩为3。因为A的秩m小于此方程组的变量的个数n，从线性代数的知识可知其有无数多组解。为了找到一个初始基本可行解，先介绍一些线性规划的基本概念。则约束条件组成的线性方程组的系数矩阵为：其中pj为系数矩阵A中第j列的向量。由于在A中存在一个不为零基：已知A是约束条件的m×n系数矩阵，其秩为m。若B是A中m×m阶非奇异子矩阵(即可逆矩阵，｜B｜≠0)，则称B是线性规划问题中的一个基。也即任一m阶的可逆矩阵都可作为基。基：已知A是约束条件的m×n系数矩阵，其秩为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个，在可行解：满足：最优解：满足目标函数：maxZ=50X1+100X2

的可行解称为最优解。的解称为可行解（注意包括了非负）。X1+X2+S1=3002X1+X2+S2=400X2+S3=250X1,X2,S1,S2,S3≥0可行解：最优解：的解称为可行解（注意包括了非负）。X1+X2由于在这个基本解中S1=-100，S3=-150，不满足该线性规划S1≥0，S3≥0的约束条件，显然不是问题的可行解。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都小于等于零时，则∑σjXj≤0，要使目标函数（1）式的值最大，显然只有当∑σjXj为零才最大。即把这些Xj取为非基变量(即令这些Xj的值为零)，所求得的基本可行解就使目标函数值最大为z0。2.最优解判别定理在求最大值目标函数的问题中，对于某个基本可行解，如果所有检验数σj≤0，则这个基本可行解是最优解。下面来解释最优解判别定理。设用非基变量表示的目标函数为如下形式其中，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,也不是最优解。对于求目标函数最小值的情况，只需把上述的定理中的σj≤0，改为σj≥0即可。至于如何来判断无最优解的方法将在后面用具体实例予以阐述。在本例题中当取基变量为由于σ1=50，σ2=100都大于零，显然这个基

下面介绍如何进行基变换找到一个新的可行基，具体的做法是从可行基中换一个列向量，得到一个新的可行基，使得求解得到的新的基本可行解，使得其目标函数值更优。为了换基就要确定换入变量与换出变量。

三、基变换x1x2基变换的实质就是从一个顶点换到另一个顶点。下面介绍如何进行基变换找到一个新的可行基，具体的

从最优解判别定理知道，当某个σj>0时，非基变量xj变为基变量（即不取零值）可以使目标函数值增大，故我们要选基检验数大于0的非基变量换到基变量中去(称之为入基变量)。若有两个以上的σj>0，则为了使目标函数增加得更大些，一般选其中的σj最大者的非基变量为入基变量，在本例题中σ2=

100是检验数中最大的正数，故选X2为入基变量。1．入基变量的确定从最优解判别定理知道，当某个σj>0时，非

求得基本解：X1=0,X2=300,S1=0,S2=100,S3=-50.显然这不是基本可行解，因为S3<0,所以S1不能作为出基变量。2．出基变量的确定在确定了X2为入基变量之后，要在原来的3个基变量S1,S2,S3中确定一个出基变量，也就是确定哪一个基变量变成非基变量呢?如果确定S1为出基变量，则新的基变量为X2,S2,S3，因为非基变量X1=S1=0，则：X1+X2+S1=3002X1+X2+S2=400X2+S3=250X2=300X2+S2=400X2+S3=250求得基本解：X1=0,X2=300,S1=0,S2=1如果把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=3002X1+X2+S2=400X2+S3=250X2=300X2+S1=400X2+S2=250如果把s3作为出基变量呢？求得基本解：X1=0

以下就来看在找出了初始基本可行解和确定了入基变量之后，怎么样的基变量可以确定为出基变量呢?确定出基变量的方法：把已确定的入基变量在各约束方程中的正的系数除其所在约束方程中的常数项的值，把其中最小比值所在的约束方程中的原基变量确定为出基变量。这样在下一步迭代的矩阵变换中可以确保新得到的bj值都大于等于零。

能否在求出基本解以前来确定出基变量呢?证明过程略。详情见P77-P80啊！重要以下就来看在找出了初始基本可行解和确定了入基变

在本例题中约束方程为X1+X2+S1=

300，2X1+X2+S2=400，X2+S3=250在第二步中已经知道X2为入基变量，把各约束方程中X2的为正的系数除对应的常量，得：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=50×0+100×250=25000，显然比初始基本可行解X1=0，X2=0，S1=300，S2=400，S3=250时的目标函数值50×0+100×0=0要好得多。下面我们再进行检验其最优性，不是最优解还要继续进行基变换，直至找到最优解，或者能够判断出线性规划无最优解为止。为了使单纯形法更加简洁明了下面用表格来做。此表称为单纯形法表。这时目标函数值为50X1+l00X2=50×

在讲单纯形法的表格形式之前，先从一般数学模型里推导出检验数σj的表达式。可行基为m阶单位矩阵的线性规划模型如下(假设其系数矩阵的前m列是单位矩阵)：maxz=c1x1+c2x2+…+cnxn

x1+a1,m+1xm+1+…+a1,nxn=b1,x2+a2,m+1xm+1+…+a2,nxn=b2,………………xm+am,m+1xm+1+…+am,nxn=bm,xj≥0,(j=1,2,…,n)以下用Xi(i=1，2，…，m)表示基变量，用Xj(j=m+1,m+2,…,n)表示非基变量。§5.2单纯形法的表格形式在讲单纯形法的表格形式之前，先从一般数学模型把第i个约束方程移项，就可用非基变量表示基变量:把第i个约束方程移项，就可用非基变量表示基变量:[管理学]管理运筹学单纯形法课件

单纯形法的表格形式是把用单纯形法求出基本可行解、检验其最优性、迭代某步骤都用表格的方式来计算求出，其表格的形式有些像增广矩阵，而其计算的方法也大体上使用矩阵的行的初等变换。以下用单纯形表格来求解第二章的例1。1、max50X1+100X2+0S1+0S2+0S3，X1+X2+S1=300,2X1+X2+S2=400,X2+S3=250,X1,X2,S1,S2,S3≥0单纯形法的表格形式是把用单纯形法求出基本可行把上面的数据填入如下的单纯形表格迭代次数基变量CBX1X2S1S2S3b比值bi/ai2501000000S1S2

S3000111002101001001300400250Zjσj=Cj-Zj

max50X1+100X2+0S1+0S2+0S3，X1+X2+S1=300,2X1+X2+S2=400,X2+S3=250,把上面的数据填入如下的单纯形表格迭代次数基变量X1基变量S1、S2、S3的顺序不能填错，在S1,S2,S3的右边CB列中填入这些变量在目标函数中的系数。在Zj行中填入各列的∑Ciaij的值，也就是把系数矩阵的第j列与CB列中对应元素相乘相加所得的值，如Z2=0×1+0×1+0×1=0，所在Zj行中的第2位数填入0。迭代次数基变量CBX1X2S1S2S3b比值bi/ai2501000000S1S2

S3000111002101001001300400250Zjσj=Cj-Zj00000Z=050100000基变量S1、S2、S3的顺序不能填错，在S1,S2,在σj=Cj–Zj，则σ1=50-0=50,σ2=100,σ3=0,σ4=0,σ5=0，Z值表示把初始基本可行解代入目标函数所得的函数值。Z的值就等于约束方程的常数项bi乘以此约束方程的基变量在目标函数中的系数之和，Z=300×0+400×0+250×0=0，故Z=0。迭代次数基变量CBX1X2S1S2S3b比值bi/ai2501000000S1S2

S3000111002101001001300400250Zjσj=Cj-Zj00000Z=050100000在σj=Cj–Zj，则σ1=50-0=50,填完了此表，得初始基本可行解，S1=300，S2=400，S3=250，X1=0，X2=0，(因X1，X2是非基变量，非基变量取零值)，其目标函数值Z=0，同时在σj=Cj–Zj一栏中可知σ1=50，σ2=100，σ3=σ4=σ5=0。可知这个基本可行解不是最优解（因为检验数>0)，迭代次数基变量CBX1X2S1S2S3b比值bi/ai2501000000S1S2

S3000111002101001001300400250Zjσj=Cj-Zj00000Z=050100000填完了此表，得初始基本可行解，S1=300，S2=400，迭代次数基变量CBX1X2S1S2S3b比值bi/ai2501000000S1S2

S3000111002101001001300400250Zjσj=Cj-Zj00000Z=050100000想想，如何进行迭代？为什么选取X2作为入基变量？迭代次数基变量X1X2迭代次数基变量CBX1X2S1S2S3b比值bi/ai2501000000S1S2

S3000111002101001001300400250300/1400/1250/1Zjσj=Cj-Zj00000Z=050100000你怎么知道S3为出基变量啊？σ32=1叫主元？郁闷！迭代次数基变量X1X2迭代次数基变量CBX1X2S1S2S3b501000001S1S2

X200100

01001

250Zjσj=Cj-Zj

迭代迭代迭代迭代迭代3行×(-1)+2行3行×(-1)+1行150-15000201-110111100300210104000100125050/1150/2比值bi/ai201000010050000-100Z=25000迭代次数基变量X1X2又从σ1=50>0可知这个基本可行解也不是最优解。从σj我们知道σ1为最大的正数，可知X1为入基变量，从此值可知b1/a11=50为bi/ai1中最小的正数，可知S1为出基变量，a11为主元，这样我们可以进行第2次迭代后得下表：迭代次数基变量CBX1X2S1S2S3b比值bi/ai2501000002X1S2

X25001001010-100-21101001505025050/1150/2Zjσj=Cj-Zj501005005000-500-50Z=27500又从σ1=50>0可知这个基本可行解也不是最优解。从σj

从表中可知基本可行解为X1=50，X2=250，S1=0,S2=50,S3=0，这时Z=27500。由于检验σj都小于等于零，此基本可行解为最优解，Z=27500为最优目标函数值。迭代次数基变量CBX1X2S1S2S3b比值bi/ai2501000002X1S2

X25001001010-100-21101001505025050/1150/2Zjσj=Cj-Zj501005005000-500-50Z=27500从表中可知基本可行解为X1=50，X2=250第二章例2的数学模型如下：目标函数:minf=2X1+3X2.约束条件：X1+X2≥350，X1≥125，2X1+X2≤600，X1，X2≥0．

其约束条件的标准型如下：X1+X2-S1=350，X1-S2=125，2X1+X2+S3=600，X1，X2,,S1,S2，S3≥0．§5.3求目标函数值最小的线性规划问题的单纯形表解法第二章例2的数学模型如下：§5.3求目标函数值最小的线性规至于目标函数，在标准型中并不一定要求求最大值或最小值，但是为了使单纯形表解法有一个统一的解法，我们把所有求目标函数最小值的问题化成求目标函数最大值的问题。具体做法只要把目标函数乘以(-1)，就把原来求目标函数最小值的问题化成了求目标函数最大值的问题。本例题的目标函数就化为了：目标函数：max(-f)=-2X1-X2．为了统一符号，不妨设Z=-f，这样目标函数就写成:maxZ=-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,a2≥0．这样在约束方程的系数矩阵中就可找到单位向量e3，e1，e2了,这时可知基变量为s3,a1,a2，初始基本可行解为X1=0,X2=0,S1=0,S2=0,S3=600,a1=350,a2=125.[管理学]管理运筹学单纯形法课件人工变量的含义

人工变量是与松弛、剩余变量不同的。松弛变量、剩余变量它们可以取零值，也可以取正值，而人工变量只能取零值。一旦人工变量取正值，则有人工变量的约束方程和原始的约束方程就不等价了，这样所求得的解就不是原线性规划的解了。为了保证人工变量为零，规定人工变量在目标函数中的系数为-M，这里M为任意大的数。这样只要人工变量>0，所求的目标函数最大值就是一个任意小的数。这样为了使目标函数实现最大就必须把人工变量从基变量中换出。如果一直到最后，人工变量仍不能从基变量中换出，即人工变量仍不为零，则该问题无可行解。这样此例的目标函数就写为：maxZ=-2X1-3X2-Ma1-Ma2人工变量的含义人工变量是与松弛、剩余变量不此例的数学模型如下所示：maxz=-2X1-3X2-Ma1-Ma2s.tX1+X2-S1+a1=350，X1-S2+a2=125，2X1+X2+S3=600，X1，X2,,S1,S2,a1,a2≥0．像这样，为了构造初始可行基得到初始可行解，把人工变量“强行”地加到原来的约束方程中去，又为了尽力地把人工变量从基变量中替换出来，就令人工变量在求最大值的目标函数里的系数为-M，这个方法叫做大M法，M叫做罚因子。下面我们就用大M法来求解此题。此例的数学模型如下所示：像这样，为了构造初始可行基迭代次数基变量CBx1x2s1s2s3a1a2b比值-2-3000-M-M0a1-M11-10010350350/1a2-M100-1001125125/1s302100100600600/2Zjσj=cj-zj-2M-MMM0-M-M-475M-2+2M-3+M-M-M0001a1-M01-1101-1225225x1-2100-1001125s30010210-2350350/2Zjσj=cj-zj-2-MM-M+20-MM-2-225M-2500-3+M-MM-2002-2M迭代次数基变量x1x2s1s2s3a1a2-2-3000-M迭代次数基变量CBx1x2s1s2s3a1a2b比值-2-3000-M-M2a1-M01/2-10-1/2105050/(1/2)x1-211/2001/200300300/(1/2)s2001/2011/20-1175175/(1/2)Zjσj=cj-zj-2-M/2-1M0-M/2-1-M0-50M-6000M/2-2-M0M/2+10-M3x2-301-20-120100x1-210101-10250s2000111-1-1125Zjσj=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-如果没有单位矩阵，约束条件的等式也可设计人工变量例如MaxZ=3X1-X2-X3stX1-2X2+X3≤11-4X1+X2+2X3≥3-2X1+X3=1X1,X2,X3≥0约束条件加上松驰和剩余变量后为：X1-2X2+X3+S1=11-4X1+X2+2X3-S2=3-2X1+X3=1X1,X2,X3≥0仍未有单位矩阵，在第二、三约束上分别加上人工变量a1,a2得：如果没有单位矩阵，约束条件的等式也可设计人工变量例如MMaxZ=3X1-X2-X3-Ma1-Ma2stX1-2X2+X3+S1=11-4X1+X2+2X3-S2+a1=3-2X1+X3+a2=1X1,X2,X3≥0则基变量为S1，a1,a2。这样就可进行求解了。除了大M法外，还有两阶段法（略）MaxZ=3X1-X2-X3-Ma1-Ma2一、无可行解.例1．求解下列线性规划问题目标函数：maxZ=20X1+30X2约束条件：3X1+10X2≤150，X1≤30，X1+X2≥40，X1,X2≥0．解：在上述问题的约束条件中加入松弛变量，剩余变量，人工变量得到：目标函数：maxZ=20X1+30X2-Ma1约束条件：3X1+10X2+S1=150，X1+S2=30,X1+X2-S3+a1=40X1,X2,S1,S2,S3,a1≥0

§5.4．几种特殊情况一、无可行解.例1．求解下列线性规划问题§5.4．几种迭代次数基变量CBx1x2s1s2s3a1b比值2030000-M0s103101000150150/10s2010010030a1-M1100-114040/1Zjσj=cj-zj-M-M00M-M-40M20+M30+M00-M01x2303/1011/100001515/(3/10)s201001003030/1a1-M7/100-1/100-112525/(7/10)Zjσj=cj-zj9-7M/10303+M/100M-M450-25M11+7M/100-3-M/100-M0迭代次数基变量x1x2s1s2s3a12030000-Ms所有的检验数σj都小于等于零，可知最优解为：X1=30,X2=6,S1=0,S2=0,S3=0,a1=4≠0，其目标函数值为780-4M。把最优解S3=0,a1=4代入第3个约束方程得X1+X2-S3+a1=40，即有：X1+X2=36<40．并不满足原来的约束条件3:X1+X2≥40,可知原线性规划问题无可行解，或者说其可行域为空集。故这样只要线性规划的最优解里有人工变量大于零，则此问题无可行解。迭代次数基变量CBX1X2S1S2S3a1b比值2030000-M2X230011/10-3/10006X12010010030a1-M00-1/10-7/10-114Zjσj=cj-zj20303+M/1011+7M/10M-M780-4M00-3-M/10-11-7M/10-M0所有的检验数σj都小于等于零，可知最优解为：X

如果在最后的迭代时，所有检验数都小于或等于零，而人工变量仍然是基变量，但人工变量取值为零，这时问题有解吗？如果在最后的迭代时，所有检验数都小于或等于零，而在求目标函数最大值的问题中，所谓无界解是指在约束条件下目标函数值可以取得任意的大。下面用单纯形表来求解第二章中的例子（P15）。例2、用单纯形表求：目标函数：maxZ=X1+X2，约束条件：X1-X2≤1,-3X1+2X2≤6，X1≥0，X2≥0．解：在上述的约束条件中加入松弛变量，得标准型如下：maxZ=X1+X2，S.t.X1-X2+S1=1,-3X1+2X2+S2=6，X1≥0，X2≥0．二、无界解在求目标函数最大值的问题中，所谓无界解是指在约束从第1次迭代的σ2=2，得基本可行解X1=1,X2=0,S1=0，S2=9不是最优解。如果进行第2次迭代，那么选X2为入基变量，因为a12=-1，a22=-1,找不到大于零的aij来确定出基变量。碰到这种情况可以断定此问题是无界的，即此目标函数值可以取到无限大。迭代次数基变量CBX1X2S1S2b比值11000S1S2001-110161-3201Zjσj=cj-zj0000Z=011001X1S2101-110190-131Zjσj=cj-zj1-110102-10从第1次迭代的σ2=2，得基本可行解X1=1,X从1次迭代的单纯形表中，得到约束方程:

X1-X2+S1=1-X2+3S1+S2=9移项得：X1=1+X2-S1S2=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，并且该列的系数向量的每个元素aij(i=1，2,…,m)都小于或等于零，则此线性规划问题是无界的，一般地说此类问题的出现是由于建模的错误所引起的。从1次迭代的单纯形表中，得到约束方程:

例3．用单纯形表求解下面的线性规划问题。目标函数：maxZ=50X1+50X2，约束条件：X1+X2≤300，2X1+X2≤400，X2≤250,X1≥0,X2≥0.解：用单纯形表来解，引入松弛变量S1,S2,S3,得标准型：maxZ=50X1+50X2，X1+X2+S1=300,2X1+X2+S2=400,X2+S3=250,X1,X2,S1,S2,S3≥0，填入单纯形表得：三、无穷多最优解例3．用单纯形表求解下面的线性规划问题。三、无穷多最优解迭代次数基变量CBX1X2S1S2S3b比值50500000S1S2S300011100300400250300/1400/1250/12101001001Zjσj=cj-zj00000050500001S1S2X2005010101150/22001-101001Zjσj=cj-zj050005012500500000迭代次数基变量X1X2得最优解为X1=50,X2=250,S1=0,S2=50,S3=0,最优值为15000。这个最优解是否是唯一的呢?由于在第2次迭代中除了基变量的检验数σ1,σ2,σ4等于零外，非基变量s3的检验数也等于零，这样可以断定此问题有无穷多最优解。不妨把检验数也为零的非基变量选为入基变量进行第3次迭代。可求得另一个基本可行解：迭代次数基变量CBX1X2S1S2S3b比值50500002X1S2X2500501010-1505025050/1250/100-21101001Zjσj=cj-zj505050001500000-5000得最优解为X1=50,X2=250,S1=0,S2=从检验数可知此基本可行解X1=100,X2=200,S1=0,S2=0,S3=50，也是最优解。迭代次数基变量CBX1x2s1s2s3b比值50500003x1s3x25005010-1101005020000-211012-10Zjσj=cj-zj505050001500000-5000从检验数可知此基本可行解X1=100,X2=200,S从图解法可知连接这两点的线段上的任一点都是此线性规划的最优解，不妨用向量Z1，Z2表示上述两个最优解即Z1=(50，250，0，50，0)，Z2=(100，200，0，0，50)，则线段上的任一点，即可表示为αZ1+（1-α）Z2，其中0≤α≤l。如下图所示：x2100400100300x1Z2250200Z1X1+X2=3002X1+X2=400目标函数Z=50x1+50x25000=50x1+50x2从图解法可知连接这两点的线段上的任一点都是此线性规划的最优解问题：在一个已得到最优解的单纯形表中，如果存在一个非基变量的检验数σs为零，为什么当把这个非基变量xs作为入基变量进行迭代时得到的新的基本解仍为最优解呢?问题：在一个已得到最优解的单纯形表中，如果存在一个非基变量的

判断线性规划有无穷多最优解的方法：对于某个最优的基本可行解，如果存在某个（或1个以上）非基变量的检验数为零，则此线性规划问题有无穷多最优解。证明过程略，详见P92-P93（即证明了其他非基变量的检验数不变，仍然是小于等于零，估新的基本可行解仍然是最优解）判断线性规划有无穷多最优解的方法：在单纯形法计算过程中，确定出基变量时有时存在两个以上相同的最小比值，这样在下一次迭代中就有了一个或几个基变量等于零，这称之为退化。例4、用单纯形表求解下列线性规划问题。目标函数：maxZ=2X1+3X3/2约束条件：X1-X2≤2,2X1+X3≤4,X1+X2+X3≤3,X1,

X2,X3≥0加上松弛变量S1，S2,S3化为标准型并填入单纯形表得：四、退化问题在单纯形法计算过程中，确定出基变量时有时存在两个以上相同的最迭代次数基变量CBX1X2X3

S1S2S3b比值203/20000S1S2S30001-101002432/14/23/1201010111001Zjσj=cj-zj0000000203/20001X1S2S32001-101002010/21/2021-210021-101Zjσj=cj-zj2-200004023/2-200比值相同迭代次数基变量X1X2迭代次数基变量CBX1X2X3

S1S2S3b比值203/20002X1X2S3200101/201/202012/(1/2)0/(1/2)011/2-11/200001-11Zjσj=cj-zj2010104001/20-10可以看到在0次迭代栏中，由于比值b1/a11=b2/a21=2为最小比值，导致在第1次迭代中出现了退化，基变量S2=0。又由于在第1次迭代出现了退化，基变量S2=0，又导致第2次迭代所取得的目标函数值并没有得到改善，仍然与第1次迭代的一样都等于4。像这样继续迭代而得不到目标函数的改善，当然减低了单纯形算法的效率，但一般来说还是可以得到最优解的。像本题继续计算如下：迭代次数基变量X1X2迭代次数基变量CBX1X2X3

S1S2S3b比值203/20003X1X3S323/201-101002012/11/1021-2100001-11Zjσj=cj-zj213/2-13/2040-101-3/20X1X3S123/201-1001-11210210-120001-11Zjσj=cj-zj213/201/2150-100-1/2-1迭代次数基变量X1X2

这样得到了最优解X1=2,X2=0,X3=2,S1=1,S2=0,S3=0，其最优值为5。但有时候当出现退化时，即使存在最优解，而迭代过程总是重复解的某一部分迭代过程，出现了计算过程的循环，目标函数值总是不变，永远达不到最优解。下面一个是由E．Beale给出的循环的例子。这样得到了最优解X1=2,X2=0,X这个例题的确存在最优解，但经过6次迭代后得到的单纯形表与第0次单纯形表一样，而目标函数仍是零，这样迭代下去，永远达不到最优解。为了避免这种现象，下面介绍一种做法这个例题的确存在最优解，但经过6次迭代后得到的单纯勃兰特法则的做法。首先把松弛变量(剩余变量)、人工变量都用Xj表示，一般松弛变量(剩余变量)的下标号列在决策变量之后，人工变量的下标号列在松弛变量(剩余变量)之后，在计算中遵守以下两个规则：

(1)在所有检验数大于零的非基变量中，选一个下标最小的作为入基变量。(2)在存在两个和两个以上最小比值时，选一个下标最小的基变量为出基变量。这样就一定能避免出现循环。注意了，此法是在出现循环时才用！勃兰特法则的做法。首先把松弛变量(剩余变量)、人工变量都用X本章结束，谢谢！作业：P97,1,5(1),7(1)本章结束，谢谢！作业：P97,1,5(1),7(1)此法是求解线性规划问题的一种有效方法本章的学习内容：§1、单纯形法的基本思路和原理§2、单纯形法的表格形式§3、求目标函数值最小的问题的单纯形表解法4、几种特殊情况

第五章单纯形法此法是求解线性规划问题的一种有效方法第五章单纯形法

图解法只能解决仅含有两个决策变量的线性规划的问题，对多于两个决策变量的线性规划问题，图解法就显得无能为力了。在这一章里将介绍由美国数学家丹捷格(G·B·Dantgig)1947提出的，得到最广泛应用的线性规划的代数算法——单纯形法，这恐怕是在运筹学发展史上最辉煌的一笔，此算法是对运筹学算法的一次革命。在第三章所介绍的线性规划问题的计算机解法就是基于单纯形法原理来编程的。它可解决多个变量线性规划问题。在后来研究上还发明其它求解线性规划的方法,如前苏联科学家发明的内点法、印度科学家发明的K算法等。图解法只能解决仅含有两个决策变量的线性规划的

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