线性规划与单纯形法.ppt

第二章线性规划建模及单纯形法,本章内容重点,线性规划模型与解的主要概念线性规划的单纯形法，线性规划多解分析线性规划应用建模,1.线性规划的概念,例2.1:某工厂拥有A、B、C三种类型的设备，生产甲、乙两种产品。每件产品在生产中需要占用的设备台时、每件产品可以获得的利润以及三种设备可利用的时数如下表所示：,3,1.线性规划的概念,问题是：工厂应生产多少单位产品甲和产品乙才能使获利最多？,目标函数Maxz=1500 x1+2500 x2约束条件s.t.3x1+2x2652x1+x2403x275x1,x20,1.线性规划的概念,目标为变量的线性函数,变量的线性等式或不等式,线性规划模型,这是一个典型的利润最大化的生产计划问题。其中，“Max”是英文单词“Maximize”的缩写，含义为“最大化”；“s.t.”是“subjectto”的缩写，表示“满足于”。因此，上述模型的含义是：在给定条件限制下，求使目标函数z达到最大的x1,x2的取值。,1.线性规划的概念,一般形式-p11目标函数：Max(Min)z=c1x1+c2x2+cnxn,约束条件：a11x1+a12x2+a1nxn(=,)b1a21x1+a22x2+a2nxn(=,)b2.am1x1+am2x2+amnxn(=,)bmx1，x2，xn0,1.线性规划的概念,标准形式-p14目标函数：Maxz=c1x1+c2x2+cnxn,约束条件：a11x1+a12x2+a1nxn=b1a21x1+a22x2+a2nxn=b2.am1x1+am2x2+amnxn=bmx1，x2，xn,bi0,1.线性规划的概念,可以看出，线性规划的标准形式有如下四个特点：目标最大化、约束为等式、决策变量均非负、右端项非负。对于各种非标准形式的线性规划问题，我们总可以通过以下变换，将其转化为标准形式:,1.线性规划的概念,1.极小化目标函数的问题：设目标函数为Minf=c1x1+c2x2+cnxn则可以令z-f，该极小化问题与下面的极大化问题有相同的最优解，即Maxz=-c1x1-c2x2-cnxn但必须注意，尽管以上两个问题的最优解相同，但他们最优解的目标函数值却相差一个符号，即Minf-Maxz,1.线性规划的概念,2、约束条件不是等式的问题：设约束条件为ai1x1+ai2x2+ainxnbi可以引进一个新的变量s-松弛变量，使它等于约束右边与左边之差s=bi(ai1x1+ai2x2+ainxn)显然，s也具有非负约束，即s0，这时新的约束条件成为ai1x1+ai2x2+ainxn+s=bi,1.线性规划的概念,当约束条件为ai1x1+ai2x2+ainxnbi时，类似地令s=(ai1x1+ai2x2+ainxn)-bi显然，s也具有非负约束，即s0剩余变量，这时新的约束条件成为ai1x1+ai2x2+ainxn-s=bi,1.线性规划的概念,数学意义：为了使约束由不等式成为等式而引进的变量，对于小于等于型：s称为“松弛变量”；对于大于等于型：s称为“剩余变量”。如果原问题中有若干个非等式约束，则将其转化为标准形式时，必须对各个约束引进不同的松弛变量和剩余变量。,1.线性规划的概念,13,现实含义,s-slack松弛变量：约束条件中没使用的资源或能力称之为松弛变量。-p14s-surplus剩余变量:代表最低限约束的超过量。p17,例2.2：将以下线性规划问题转化为标准形式Minf=3.6x1-5.2x2+1.8x3s.t.2.3x1+5.2x2-6.1x315.74.1x1+3.3x38.9x1+x2+x3=38x1,x2,x30,1.线性规划的概念,解：首先,将目标函数转换成极大化：令z=-f=-3.6x1+5.2x2-1.8x3,其次考虑约束，有2个不等式约束，引进松弛变量x4，x50。于是，我们可以得到以下标准形式的线性规划问题：Maxz=-3.6x1+5.2x2-1.8x3s.t.2.3x1+5.2x2-6.1x3+x4=15.74.1x1+3.3x3-x5=8.9x1+x2+x3=38x1,x2,x3,x4,x50,1.线性规划的概念,3.变量无符号限制的问题：在标准形式中，必须每一个变量均有非负约束。当某一个变量xj没有非负约束时，可以令xj=xj-xj”其中xj0，xj”0即用两个非负变量之差来表示一个无符号限制的变量，当然xj的符号取决于xj和xj”的大小。（也可以消去自由变量）,1.线性规划的概念,4.右端项有负值的问题：在标准形式中，要求右端项必须每一个分量非负。当某一个右端项系数为负时，如bim，秩(A)=m，bRmb=(b1，b2，bm)T在约束等式中，令n维空间的解向量：x=(x1，x2，xn)T,2.线性规划解的概念,若其中n-m个变量为零，如果剩下的m个变量在线性方程组中有唯一解，则这n个变量的值组成的向量x就对应于n维空间Rn中若干个超平面的一个交点。当这n个变量的值都是非负时，这个交点就是线性规划可行域的一个极点。根据以上分析，我们建立以下概念：（1）线性规划的基：对于线性规划的约束条件Ax=b，x0,2.线性规划解的概念,设B是矩阵A中的一个非奇异（可逆）的mm子矩阵，则称B为线性规划的一个基。记：A=(p1，p2，pn)，其中pj=(a1j，a2j，amj)TRm，任取A中的m个线性无关列向量pjRm构成矩阵B=(p1，p2，pm)。那么B为线性规划的一个基。称对应于基B中的各基向量的变量x1，x2，xm为基变量，共为m个；而其他变量称为非基变量，共n-m个。,2.线性规划解的概念,可以用矩阵来描述这些概念。设B是线性规划的一个基，则A可以表示为A=B,Nx也可相应地分成xBx=xN其中xB为m维列向量，它的各分量称为基变量，与基B的列向量对应；xN为n-m列向量，它的各分量称为非基变量，与非基矩阵N的列向量对应。这时约束等式Ax=b可表示为,2.线性规划解的概念,xBB,N=bxN或BxB+NxN=b如果对非基变量xN取确定的值，则xB有唯一的值与之对应xB=B-1b-B-1NxN基变量用非基变量线性表示特别，当取xN=0，这时有xB=B-1b。关于这类特别的解，有以下概念。,2.线性规划解的概念,（2）线性规划问题的基本解、基本可行解和可行基：对于线性规划问题，设矩阵B=(p1，p2，pm)为一个基，令所有非基变量为零，可以得到m个关于基变量x1，x2，xm的线性方程，解这个线性方程组得到基变量的值。我们称这个解为一个基本解；若得到的基变量的值均非负，则称为基本可行解，同时称这个基B为可行基。,2.线性规划解的概念,矩阵描述为，对于线性规划的解xBB-1bx=xN0称为线性规划与基B对应的基本解。若其中B-1b0，则称以上的基本解为一基本可行解，相应的基B称为可行基。,2.线性规划解的概念,我们有以下结论：线性规划的基本可行解就是可行域的极点。这个结论被称为线性规划的基本定理，它的重要性在于把可行域的极点这一几何概念与基本可行解这一代数概念联系起来，因而可以通过求基本可行解的线性代数的方法来得到可行域的一切极点，从而有可能进一步获得最优极点。,2.线性规划解的概念,67,例2.9:考虑例2.8的线性规划模型Maxz=1500 x1+2500 x2s.t.3x1+2x2+x3=652x1+x2+x4=403x2+x5=75x1,x2,x3,x4,x50再次提醒:线性规划的基本解、基本可行解（极点）和可行基只与线性规划问题标准形式有关。,2.线性规划解的概念,32100A=P1,P2,P3,P4,P5=2101003001A矩阵包含以下10个33的子矩阵：B1=p1，p2，p3B2=p1，p2，p4B3=p1，p2，p5B4=p1，p3，p4B5=p1，p3，p5B6=p1，p4，p5B7=p2，p3，p4B8=p2，p3，p5B9=p2，p4，p5B10=p3，p4，p5,2.线性规划解的概念,其中B4=0，因而B4不是该线性规划问题的基。其余均为非奇异方阵，因此该问题共有9个基。对于基B3=p1，p2，p5，令非基变量x3=0，x4=0，在等式约束中令x3=0，x4=0，解线性方程组：3x1+2x2+0 x5=652x1+x2+0 x5=400 x1+3x2+x5=75得到x1=15，x2=10，x5=45，对应的基本可行解：x=(x1，x2，x3，x4，x5)T=(15，10，0，0，45)T。于是对应的基B3是一个可行基。,2.线性规划解的概念,综上可得到x(1)=(15，10，0，0，45)T（对应B3）x(2)=(5,25,0,5,0)T（对应B2）x(7)=(20,0,5,0,75)T（对应B5）x(8)=(0,25,15,15,0)T（对应B7）x(9)=(0,0,65,40,75)T（对应B10）是基本可行解；而x(3)=(0,32.5,0,7.5,-22.5)T（对应B9）x(4)=(65/3,0,0,-10/3,75)T（对应B6）x(5)=(7.5,25,-7.5,0,0)T（对应B1）x(6)=(0,40,-15,0,-45)T（对应B8）是基本解。,2.线性规划解的概念,因此，对应基本可行解（极点）的B2B3B5B7B10都是可行基。这里指出了一种求解线性规划问题的可能途径，就是先确定线性规划问题的基，如果是可行基，则计算相应的基本可行解以及相应解的目标函数值。由于基的个数是有限的（最多个），因此必定可以从有限个基本可行解中找到最优解。,2.线性规划解的概念,73,2.线性规划解的概念,讨论总结：对线性规划模型的标准型而言1）等价性定理：X是D=X|AX=b,X=0的极点的充要条件是X是线性规划标准型的基本可行解。推论1：若凸集D=X|AX=b,X=0非空，则它至少有一个极点。推论2：如果一个线性规划问题有有限的最优解，则必有一个最优解是D的极点。2）极点的个数等于基本可行解的个数。3）目标函数CX一定可以在非空有界集D=X|AX=b,X=0的某一极点处达到最大。,74,2.线性规划解的概念,结论：因此，求解线性规划标准型最优解，我们只需找到可行基（极点），然后在极点范围内求解最优解就可以了，无需考虑其它！单纯形法就是基于这种思路求解的！切记之！,利用求解线性规划问题基本可行解（极点）的方法来求解较大规模的问题是不可行的。单纯形法（1947年美国数学家G.B.Dantzig提出）的基本思路是有选择地取基本可行解，即是从可行域的一个极点出发，沿着可行域的边界移到另一个相邻的极点，要求新极点的目标函数值不比原目标函数值差。,3.单纯形法,由上节的讨论可知，对于线性规划的一个基，当非基变量确定以后，基变量和目标函数的值也随之确定。因此，一个基本可行解向另一个基本可行解的移动，以及移动时基变量和目标函数值的变化，可以分别由基变量和目标函数用非基变量的表达式来表示（求检验数过程）。同时，当可行解从可行域的一个极点沿着可行域的边界移动到一个相邻的极点的过程中，所有非基变量中只有一个变量的值从0开始增加（基变换过程），而其他非基变量的值都保持0不变。,3.单纯形法,77,相邻极点：12，17，28，89，79x(1）=(15,10,0,0,45)T（对应B3）x(2)=(5,25,0,5,0)T（对应B2）x(1）=(15,10,0,0,45)T（对应B3）x(7)=(20,0,5,0,75)T（对应B5）x(2)=(5,25,0,5,0)T（对应B2）x(8)=(0,25,15,15,0)T（对应B7）x(8)=(0,25,15,15,0)T（对应B7）x(9)=(0,0,65,40,75)T（对应B10）x(7)=(20,0,5,0,75)T（对应B5）x(9)=(0,0,65,40,75)T（对应B10）,3.单纯形法,单纯形法的基本过程核心是：变量迭代,找一个初始可行基,单位矩阵或由单位矩阵各列向量组成,考虑标准形式的线性规划问题：Maxz=c1x1+c2x2+cnxns.t.a11x1+a12x2+a1nxn=b1a21x1+a22x2+a2nxn=b2.am1x1+am2x2+amnxn=bmx1,x2,xn0 x1c1b1a11a12.a1nx2c2b2a21a22.a2nx=.CT=.b=.A=.xncnbmam1am2.amn,3.单纯形法,这里，矩阵A表示为：A=(p1，p2，pn)，其中pj=(a1j，a2j，amj)TRm。若找到一个可行基，无妨设B=(p1，p2，pm)，则m个基变量为x1,x2,xm，n-m个非基变量为xm+1，xm+2，xn。通过运算，所有的基变量都可以用非基变量来表示：,3.单纯形法,3.单纯形法,x1=b1-（a1m+1xm+1+a1m+2xm+2+a1nxn）x2=b2-（a2m+1xm+1+a2m+2xm+2+a2nxn）(2-11).xm=bm-（amm+1xm+1+amm+2xm+2+amnxn）把它们代入目标函数，得z=z+m+1xm+1+m+2xm+2+nxn(2-12)其中j=cj-（c1a1j+c2a2j+cmamj）我们把基变量由非基变量线性表示的（LP）称为与基B相应的典式。通常把目标函数中非基变量前面的系数j叫“检验数”。,单纯形法的基本步骤可描述如下：（1）寻找一个初始的可行基和相应基本可行解（极点），确定基变量、非基变量以及基变量、非基变量（全部等于0）和目标函数的值，并将目标函数和基变量分别用非基变量表示；,3.单纯形法,（2）在用非基变量表示的目标函数表达式（2-12）z=z+m+1xm+1+m+2xm+2+nxn中，我们称非基变量xj的系数为检验数记为j。若j0，那么相应的非基变量xj的值从当前值0开始增加时，目标函数值随之增加。这个选定的非基变量xj称为“进基变量”，转（3）。如果任何一个非基变量的值增加都不能使目标函数值增加，即所有j非正（小于等于0），则当前的基本可行解就是最优解，计算结束；这是最优性判别定理！,3.单纯形法,84,注意：为尽快找到最优解，在换入变量时有一定的要求。如将目标系数大的（即检验数最大的）先换入等。,（3）在用非基变量表示的基变量的表达式x1=b1-（a1m+1xm+1+a1m+2xm+2+a1nxn）x2=b2-（a2m+1xm+1+a2m+2xm+2+a2nxn）(2-11)xm=bm-（amm+1xm+1+amm+2xm+2+amnxn）中，观察进基变量增加时各基变量变化情况，确定基变量的值在进基变量增加过程中首先减少到0的变量xr，满足，=minbi/aijaij0=br/arj这个基变量xr称为“出基变量”。（最小比值原则，看p73）当进基变量的值增加到时，出基变量xr的值降为0时，可行解就移动到了相邻的基本可行解（极点），转（4）。,3.单纯形法,如果进基变量的值增加时，所有基变量的值都不减少，即所有aij非正，则表示可行域是不封闭的，且目标函数值随进基变量的增加可以无限增加，此时，不存在有限最优解，计算结束；（4）将进基变量作为新的基变量，出基变量作为新的非基变量，确定新的基、新的基本可行解和新的目标函数值。在新的基变量、非基变量的基础上重复（1）。,3.单纯形法,例2.10：用单纯形法的基本思路解例2.8的线性规划问题（用代数方法求解LP）Maxz=1500 x1+2500 x2s.t.3x1+2x2+x3=652x1+x2+x4=403x2+x5=75x1,x2,x3,x4,x50,3.单纯形法,第一次迭代：（1）取初始可行基B10=(p3,p4,p5)，那么x3，x4，x5为基变量，x1，x2为非基变量。将基变量和目标函数用非基变量线性的表示：z=1500 x1+2500 x2x3=65-3x1-2x2x4=40-2x1-x2x5=75-3x2当非基变量x1，x2=0时，相应的基变量和目标函数值为x3=65，x4=40，x5=75，z=0，得到当前的基本可行解：x=(0,0,65,40,75)T，z=0。这个解对应于平面图2-7的D、E交点。（投影）,3.单纯形法,89,（2）选择进基变量。在目标函数z=1500 x1+2500 x2中，非基变量x1，x2的系数都是正数，因此x1，x2进基都可以使目标函数z增大，但x2的系数为2500，绝对值比x1的系数1500大，因此把x2作为进基变量可以使目标函数z增加更快。选择x2为进基变量，使x2的值从0开始增加，另一个非基变量x1保持零值不变。,3.单纯形法,（3）确定出基变量。在约束条件x3=65(3x1+2x2)x4=40(2x1+x2)x5=75(0 x1+3x2)中，由于进基变量x2在3个约束条件中的系数都是正数，当x2的值从0开始增加时，基变量x3、x4、x5的值分别从当前的值65、40和75开始减少，当x2增加到25时，x5首先下降为0成为非基变量（应用最小比值原则确定）。这时，新的基变量为x3、x4、x2，新的非基变量为x1、x5，当前的基本可行解和目标函数值为：x=(0，25，15，15，0)T，z=62500。这个解对应于图中的C、D交点。,3.单纯形法,92,第二次迭代：（1）当前的可行基为B7=(p2,p3,p4)，那么x2，x3，x4为基变量，x1，x5为非基变量。在原标准型中将基变量和目标函数用非基变量表示：z=62500+1500 x1(2500/3)x5x2=25(1/3)x5x3=15-3x1+(2/3)x5x4=15-2x1+(1/3)x5,3.单纯形法,（2）选择进基变量。在目标函数z=62500+1500 x1(2500/3)x5中，非基变量x1的系数是正数，因此x1进基可以使目标函数z增大，于是选择x1进基，使x1的值从0开始增加,另一个非基变量x5保持零值不变。(3)确定出基变量。在约束条件x2=250 x1+(1/3)x5x3=153x1-(2/3)x5x4=152x1-(1/3)x5,3.单纯形法,中，由于进基变量x1在两个约束条件中的系数都是正数，当x1的值从0开始增加时，基变量x3、x4的值分别从当前的值15、15开始减少，当x1增加到5时，x3首先下降为0成为非基变量（应用最小比值原则确定）。这时，新的基变量为x1、x2、x4，新的非基变量为x3、x5，当前的基本可行解和目标函数值为：x=(5，25，0，5，0)T，z=70000。这个解对应于图中的A、C交点。,3.单纯形法,96,第三次迭代：（1）当前的可行基为B2=(p1,p2,p4)，那么x1，x2，x4为基变量，x3，x5为非基变量。在原标准型中将将基变量和目标函数用非基变量表示：z=70000500 x3-500 x5x1=5(1/3)x3-(2/9)x5x2=250 x3+(1/3)x5x4=5-(2/3)x3+(1/9)x5,3.单纯形法,（2）选择进基变量。在目标函数z=70000500 x3500 x5中，非基变量x3、x5的系数均不是正数，因此进基都不可能使目标函数z增大，于是得到最优解，x*=(5，25，0，5，0)T，最优目标值为z*=70000。这个解对应于图2-7的A、C交点。我们也称相应的基B2=(p1,p2,p4)为最优基。计算结束。,3.单纯形法,99,100,例2-11（用代数单纯形方法求解LP）,101,第一步：引入非负的松弛变量x4,x5,将该LP化为标准型,102,第二步：寻求初始可行基，确定基变量,对应的基变量是x4，x5；,第三步：写出初始基本可行解和相应的目标函数值,103,两个关键的基本表达式：用非基变量表示基变量的表达式,104,用非基变量表示目标函数的11111表达式,105,第四步：分析两个基本表达式，看看目标函数是否可以改善？,分析用非基变量表示目标函数的表达式非基变量前面的系数均为正数，所以任何一个非基变量进基都能使Z值增加注意：非基变量前面的系数叫“检验数”；,106,选哪一个非基变量进基？选x1为进基变量（换入变量）问题：能否选其他的非基变量进基？,任意一个任意一个正检验数对应的非基变量最大正检验数对应的非基变量排在最前面的正检验数对应的非基变量,107,确定出基变量：问题讨论,x1进基意味着其取值从0变成一个正数，能否无限增大？当x1增加时，x4，x5如何变化？现在的非基变量是哪些？具体如何确定换出变量？,108,由用非基变量表示基变量的表达式,当x1增加时，x4，x5会减小，但有限度必须大于等于0，以保持解的可行性！于是,109,当x1的值从0增加到3时，x4首先变为0，此时x5=60因此选x4为出基变量（换出变量）。这种用来确定出基变量的规则称为“最小比值原则”（或原则）。如果P10，会出现什麽问题？最小比值原则会失效！,110,基变换新的基变量x1,x5；新的非基变量x2,x3,x4；写出用非基变量表示基变量的表达式：,可得新的基本可行解X（1）=（3，0，0，0，6）T,由,111,写出用非基变量表示目标函数的表达式:,可得相应的目标函数值为Z（1）=6检验数仍有正的返回进行讨论。,112,第五步：上述过程何时停止？当用非基变量表示目标函数的表达式中，非基变量的系数（检验数）全部非正时，当前的基本可行解就是最优解!为什麽？,分析用非基变量表示目标函数的表达式，如果让负检验数所对应的变量进基，目标函数值将下降！,3、单纯形法,表格单纯形法考虑：bi0i=1,mMaxz=c1x1+c2x2+cnxns.t.a11x1+a12x2+a1nxnb1a21x1+a22x2+a2nxnb2am1x1+am2x2+amnxnbmx1，x2，xn0,3、单纯形法,加入松弛变量化为标准型（就是典式的另外一种表达方式）：,典式的矩阵表达式（复习）：,115,代数单纯形法求解时典式的表达式（复习）：,对于典式表达式（1），为了方便求解大规模(LP)问题，我们构建如下表格形式的单纯形表,116,显然，xj=0j=1,n;xn+i=bii=1,m是基本可行解对应的基是单位矩阵。以下是初始单纯形表：mm其中：f=-cn+ibij=cj-cn+iaij为检验数cn+i=0i=1,mi=1i=1ai,n+i=1,aj,n+i=0(ji)i,j=1,mi=bi/aij,3、单纯形法,3、单纯形法,例2.12求标准形式：Maxz=1500 x1+2500 x2s.t.3x1+2x2+x3=652x1+x2+x4=403x2+x5=75x1,x2,x3,x4,x50最优解x1=5x2=25x4=5（松弛标量，表示B设备有5个机时的剩余）最优值z*=70000,118,例2-13用表格单纯形法求解,119,引入非负的松弛变量x4,x5,将该LP化为标准型,120,例2-13的表格单纯形法计算过程：,121,从最优表可知:该LP的最优解是X*=(1,2,0,0,0)T相应的目标函数最优值是Zmax=8,注意：单纯形法中，(1)每一步运算只能用矩阵初等行变换；(2)表中第3列的数总应保持非负（0）（最小比值原则可保证）；(3)当所有检验数均非正（0）时，得到最优单纯形表。（4）当最优单纯形表存在非基变量对应的检验数为零时，存在无穷多最优解；（5）如果某大于0的检验数所对应的所有aij非正，则表示可行域是不封闭的，且目标函数值随进基变量的增加可以无限增加，此时，不存在有限最优解，计算结束。,3、单纯形法,管理运筹学,123,管理运筹学,124,3、单纯形法大M法两阶段法,如果线性规划限制条件都是“”或“=”类型的约束，且初始基本可行解不明显如何处理？,管理运筹学,125,3、单纯形法大M法两阶段法,将约束条件标准化，再引入非负的人工变量，以人工变量作为初始基变量，其对应的系数列向量构成单位阵，称为“人造基”；然后用大M法或两阶段法求解。,126,等式约束左端引入人工变量的目的,使约束方程的系数矩阵中出现一个单位阵，用单位阵的每一个列向量对应的决策变量作为“基变量”，这样，出现在单纯形表格中的b(i)列（即约束方程的右边常数）值正好就是基变量的取值。,管理运筹学,127,1）大M法,考虑标准型（LP）问题,（1-1）,管理运筹学,128,1）大M法,引入人工变量xn+i0（i=1,，m）及充分大正数M。,把（LP）的标准型（1-1）变换为,基本思路,管理运筹学,129,1）大M法,（1-2）,基本思路,管理运筹学,130,（1-2）的初始可行基：,（1-2）的初始基本可行解：,1）大M法,基本思路,管理运筹学,131,若得到(1-2)最优解满足xn+i=0,i=1,m.则是原问题(1-1)最优解；否则，原问题无可行解。,重要判别依据,1）大M法,然后用单纯形法求解。,问题是在什么情况下得到最优解？,管理运筹学,132,Maxz=5x1+2x2+3x3-x4s.t.x1+2x2+3x3=152x1+x2+5x3=20 x1+2x2+4x3+x4=26x1,x2,x3,x40,1）大M法,例2.14（LP）,管理运筹学,133,Maxz=5x1+2x2+3x3-x4-Mx5-Mx6s.t.x1+2x2+3x3+x5=152x1+x2+5x3+x6=20 x1+2x2+4x3+x4=26x1,x2,x3,x4,x5,x60,解:在上述问题中引入人工变量及充分大的正数M得:,取基变量为x5,x6,x4,于是得到：,注意：这里并不是典式,管理运筹学,134,初始可行基：,初始基本可行解：,利用单纯形算法计算如下：,管理运筹学,135,得到最优解：(25/3，10/3，0，11)T最优目标值：112/3,单纯形法迭代过程,管理运筹学,136,大M法的有关注意事项,（1）在约束条件中人为地加入非负的人工变量，目的是：使它们对应的系数列向量构成单位阵人造基。,管理运筹学,137,大M法的有关注意事项,（2）在目标函数中，给人工变量前面添上一个绝对值很大的负系数-M（M0），目的是：迭代过程中，只要基变量中还存在人工变量，目标函数就不可能实现极大化惩罚！,管理运筹学,138,（3）最优表中，如果基变量不包含人工变量(xn+i=0)，则所得最优解就是原线性规划的最优解；,大M法的有关注意事项,管理运筹学,139,（4）最优表中，基变量中仍含有人工变量，线性规划没有可行解，也就没有最优解！,大M法的有关注意事项,管理运筹学,140,2）两阶段法,考虑标准型（LP）问题,（2-1）,管理运筹学,141,2）两阶段法,第一阶段:引入人工变量xn+i0，i=1,m；构造一辅助线性规划问题来求原问题的一个初始基本可行解。,基本思路,管理运筹学,142,对于（2-1）所构造的辅助线性规划问题为：,（2-2）,管理运筹学,143,辅助线性规划问题（2-2）初始可行基：,辅助线性规划问题（2-2）初始基本可行解：,2）两阶段法,管理运筹学,144,2）两阶段法,然后用单纯形法求辅助线性规划问题（2-2）最优解。目的是：得到原问题（2-1）的初始基本可行解。,问题是在什么情况下得到（2-1）初始基本可行解？,管理运筹学,145,若得到的辅助线性规划问题（2-2）的最优解满足xn+i=0,i=1,m，则最优解就是原问题的基本可行解;否则，原问题无可行解。,重要结论,2）两阶段法,管理运筹学,146,第二阶段：如果第一阶段求出了（2-1）的一个可行基，则在辅助问题（2-2）的最优单纯形表上删除全部人工列及检验数行，补上（2-1）的检验数即得到原（LP）的初始单纯形表，再使用单纯形法求（2-1）最优解。,2)两阶段法,管理运筹学,147,例2.12：（LP）Maxz=5x1+2x2+3x3-x4s.t.x1+2x2+3x3=152x1+x2+5x3=20 x1+2x2+4x3+x4=26x1,x2,x3,x40,2）两阶段法,管理运筹学,148,Maxz=-x5-x6s.t.x1+2x2+3x3+x5=152x1+x2+5x3+x6=20 x1+2x2+4x3+x4=26x1,x2,x3,x4,x5,x60,第一阶段问题（LP-1）构造辅助（LP）,管理运筹学,149,得到原问题的基本可行解:(0，15/7，25/7，52/7)T,第一阶段（LP-1）求解辅助（LP）,管理运筹学,150,第二阶段（LP-2）计算原（LP）检验数及-z,管理运筹学,151,第二阶段（LP-2）把基本可行解填入表中,得到原问题的最优解:(25/3，10/3，0，11)T最优目标值：112/3,管理运筹学,152,（1）辅助线性规划的结构：目标函数Z为所有人工变量之和的相反数，目标要求是使目标函数极大化，约束条件除人工变量外其余与原线性规划相同。,两阶段法的有关注意事项,管理运筹学,153,（2）Z最优值=0即所有人工变量取值全为0（为什麽？），均为非基变量，最优解是原线性规划的一个基本可行解，转入第二阶段；（3）Z最优值=0但人工变量中有等于0的基变量，构成退化的基本可行解，可以转化为情况（2）；如何转化？选一个不是人工变量的非基变量进基，把在基中的人工变量替换出来,管理运筹学,154,（4）Z最优值0至少有一个人工变量取值0,说明基变量中至少有1个人工变量,表明原问题没有可行解,停止计算。,管理运筹学,155,解的退化如果在一个基本可行解的基变量中至少有一个分量xBi=0(i=1,2,m)，则称此基本可行解是退化的基本可行解。退化的结构对单纯形迭代会造成什么不利的影响？,4、迭代过程中可能出现的问题及处理方法,管理运筹学,156,会增加迭代次数，使单纯形法收敛的速度减慢。在特殊情况下，退化会出现基的循环。,4、迭代过程中可能出现的问题及处理方法,不利的影响,管理运筹学,157,4、迭代过程中可能出现的问题及处理方法,Beale1955年提出如下例子说明退化会出现基的循环：最大检验数所在列作为主列，主行按最小比值相同的几行中其基变量下标最小者选取，经过6次迭代，单纯形表又恢复为初始单纯形表！,循环不止永远得不到最优解,管理运筹学,158,在选择进基变量时，在所有j0的非基变量中选取列数最小的进基；当有多个变量同时可作为出基变量（最小比值相等）时，选择行数最小的那个变量出基。,4、迭代过程中可能出现的问题及处理方法,避免出现循环的方法Bland原则,管理运筹学,159,单纯形法小结,求解思想顶点的逐步转移，条件是使目标函数值不断得到改善。,管理运筹学,160,表格单纯形法求解步骤,第一步：将LP化为标准型，并加以整理。引入适当的松驰变量、剩余变量和人工变量，使约束条件化为等式，并且约束方程组的系数阵中有一个单位阵。确定初始可行基，写出初始基本可行解,管理运筹学,161,第二步：最优性检验,计算检验数，检查：所有检验数是否0？是结束，写出最优解和目标函数最优值；还有正检验数检查相应系数列0？是结束，该LP无“有限最优解”！不属于上述两种情况，转入下一步基变换。确定是停止迭代还是转入基变换？,管理运筹学,162,选择（最大）正检验数对应的系数列为主元列，主元列对应的非基变量为换入变量；最小比值对应的行为主元行，主元行对应的基变量为换出变量。,第三步：基变换,确定进基变量和出基变量。,管理运筹学,163,利用矩阵的初等行变换把主元列变成单位向量，主元素变为1，进基变量对应的检验数变成0，从而得到一张新的单纯形表，返回第二步。,第四步换基迭代,完成一次迭代，得到新的基本可行解和相应的目标函数值,管理运筹学,164,该迭代过程直至下列情况之一发生时停止检验数行全部变为非正值；（得到最优解）或主元列0（最优解无界）,停止迭代的标志（停机准则）,依据：最优性检验的两个定理最优性判别定理；无“有限最优解”判断定理,管理运筹学,165,若为一基本可行解，有一非基变量xk,其检验数,而对于i=1,2,，m，均有，则该线性规划问题没有“有限最优解”。,无“有限最优解”的判别定理,若是对应于基B的基本可行解，是非基变量的检验数，若对于一切非基变量的角指标j，均有0，则X(0)为最优解。,最优性判别定理,管理运筹学,166,用表格单纯形法直接计算极小化线性规划时要修改哪些原则？最优性判别：所有检验数非负换入变量的选择原则：（最小）负检验数所对应的变量进基，以保证目标函数值（较快）减小；用大M法求解时，在目标函数中人工变量的前面添上一个很大的正系数M；,管理运筹学,167,各种类型线性规划的处理1、分类及处理原则：（1）类型一：目标要求是“Max”，约束条件是“”类型左边加上非负松弛变量变成等式约束（约束条件标准化），将引入的松弛变量作为初始基变量，则初始可行基是一个单位阵，用原始单纯形法求解。,管理运筹学,168,（2）类型二：目标要求是“Max”，约束条件是“=”类型左边引入非负的人工变量，并将引入的人工变量作为初始基变量，则初始可行基是一个单位阵，然后用大M法或两阶段法求解。（3）类型三：目标要求是“Max”，约束条件是“”类型约束条件标准化，左边减去非负的剩余变量，变成等式约束，化为类型二。,管理运筹学,169,（4）类型四：目标要求是“Min”方法1化为极大化问题方法2按照极小化问题直接在单纯形表格上计算处理，但相应的原则要作改动。,管理运筹学,170,处理人工变量的方法：（1）大M法在约束条件中人为地加入非负的人工变量，以便使它们对应的系数列向量构成单位阵。问题：加入的人工变量是否合理？如何处理？在目标函数中，给人工变量前面添上一个绝对值很大的负系数-M（M0），迭代过程中，只要基变量中还存在人工变量，目标函数就不可能实现极大化惩罚！,管理运筹学,171,最优表中，基变量不包含人工变量，则最优解就是原线性规划的最优解，不影响目标函数的取值；最优表中，基变量中仍含有人工变量，线性规划没有可行解，也就没有最优解！,结果,管理运筹学,172,（2）两阶段法第一阶段：建立辅助线性规划并求解，以判断原线性规划是否存在基本可行解。辅助线性规划的结构：目标函数Z为所有人工变量之和的相反数，目标要求是使目标函数极大化，约束条件与原线性规划相同。,管理运筹学,173,求解结果Z最优值=0即所有人工变量取值全为0（为什麽？），均为非基变量，最优解是原线性规划的一个基本可行解，转入第二阶段；Z最优值=0但人工变量中有等于0的基变量，构成退化的基本可行解，可以转化为情况；如何转化？选一个不是人工变量的非基变量进基，把在基中的人工变量替换出来,管理运筹学,174,Z最优值0至少有一个人工变量取值0,说明基变量中至少有1个人工变量,表明原问题没有可行解,讨论结束。,管理运筹学,175,第二阶段：将第一阶段的最优解作为初始可行解，目标函数换成原问题的目标函数，进行单纯形迭代，求出最优解。问题讨论：如何实施？需要重新建立初始单纯形表吗？,管理运筹学,176,实施中，在第一阶段最优表格中划去人工变量列，将表头部分和CB列的价值系数换成原问题的价值系数(把目标函数换成原线性规划的目标函数)，继续迭代，直至求出最优解。,在大M法中，当人工变量出基后能否立即划去该人工变量所在的系数列？,合理利用线材问题：如何下料使用材最少。配料问题：在原料供应量的限制下如何获取最大利润。投资问题：从投资项目中选取方案，使投资回报最大。,4.线性规划在工商管理中的应用,产品生产计划：合理利用人力、物力、财力等，使获利最大。劳动力安排：用最少的劳动力来满足工作的需要。运输问题：如何制定调运方案，使总运费最小。,4.线性规划在工商管理中的应用,数学规划的建模有许多共同点，要遵循下列原则：(1)容易理解。建立的模型不但要求建模者理解，还应当让有关人员理解。(2)容易查找模型中的错误。这个原则的目的显然与(1)相关。,(3)容易求解。对线性规划来说，容易求解问题主要是控制问题的规模，包括决策变量的个数和约束条件的个数。这条原则的实现往往会与(1)发生矛盾，在实现时需要对两条原则进行统筹考虑。,4.线性规划在工商管理中的应用,建立线性规划模型的过程可以分为四个步骤：(1)设立决策变量；(2)明确约束条件并用决策变量的线性等式或不等式表示；(3)用决策变量的线性函数表示目标，并确定是求极大（Max）还是极小（Min）；(4)根据决策变量的物理性质研究变量是否有非负性。,4.线性规划在工商管理中的应用,例2.12：某昼夜服务的公交线路每天各时间段内所需司机和乘务人员数如下：p39,人力资源分配的问题,设司机和乘务人员分别在各时间段一开始时上班，并连续工作8h，问该公交线路怎样安排司机和乘务人员，既能满足工作需要，又配备最少司机和乘务人员?,解：设xi表示第i班次时开始上班的司机和乘务人员数,这样我们建立如下的数学模型。目标函数：MinZ=x1+x2+x3+x4+x5+x6约束条件：s.t.x1+x660 x1+x270 x2+x360 x3+x450 x4+x520 x5+x630 x1,x2,x3,x4,x5,x60且为整数,人力资源分配的问题,例2.13:某工厂要做100套钢架，每套用长为2.9m,2.1m,1.5m的圆钢各一根。已知原料每根长7.4m，问：应如何下料，可使所用原料最省？p46,套裁下料问题,解:考虑下列各种下料方案（按一种逻辑顺序给出）,把各种下料方案按剩余料头从小到大顺序列出,假设x1,x2,x3,x4,x5分别为上面前5种方案下料的原材料根数。我们建立如下的数学模型。目标函数：Minx1+x2+x3+x4+x5约束条件：s.t.x1+2x2+x41002x3+2x4+x51003x1+x2+2x3+3x5100 x1,x2,x3,x4,x50且为整数,套裁下料问题,例2.14:明兴公司生产甲、乙、丙三种产品，都需要经过铸造、机加工和装配三个车间。甲、乙两种产品的铸件可以外包协作，亦可以自行生产，但产品丙必须本厂铸造才能保证质量。数据如下表。问：公司为了获得最大利润，甲、乙、丙三种产品各生产多少件？甲、乙两种产品的铸造中，由本公司铸造和由外包协作各应多少件？p41,生产计划的问题,解：设x1,x2,x3分别为三道工序都由本公司加工的甲、乙、丙三种产品的件数，x4,x5分别为由外协铸造再由本公司机加工和装配的甲、乙两种产品的件数。,生产计划的问题,求xi的利润:利润=售价-各成本之和可得到xi（i=1,2,3,4,5）的利润分别为15、10、7、13、9元。这样我们建立如下数学模型：目标函数:Max15x1+10 x2+7x3+13x4+9x5约束条件：s.t.5x1+10 x2+7x380006x1+4x2+8x3+6x4+4x5120003x1+2x2+2x3+3x4+2x510000 x4x1,x2,x3,x4,x50且为整数,生产计划的问题,例2.15:永久机械厂生产、三种产品，均要经过A、B两道工序加工。假设有两种规格的设备A1、A2能完成A工序；有三种规格的设备B1、B2、B3能完成B工序。可在A、B的任何规格的设备上加工；可在任意规格的A设备上加工，但对B工序,只能在B1设备上加工；只能在A2与B2设备上加工；数据如下表。问：为使该厂获得最大利润，应如何制定产品加工方案？p44,生产计划的问题,解：设xijk表示第i(1、2、3)种产品，在第j(A=1、B=2)种工序上的第k种设备上加工的数量.如x212？利润=（销售单价-原料单价）产品件数之和-（每台时的设备费用设备实际使用的总台时数）之和。,生产计划的问题,这样我们建立如下的数学模型:见教材p45Max0.75x111+0.7753x112+1.15x211+1.3611x212+1.9148x312-0.375x121-0.5x221-0.4475x122-1.2304x322-0.35x123s.t5x111+10 x2116000（设备A1）7x112+9x212+12x31210000（设备A2）6x121+8x2214000(设备B1）4x122+11x322700(设备B2）7x1234000（设备B3）,生产计划的问题,x111+x112-x121-x122-x123=0(产品在A、B工序加工的数量相等）x211+x212-x221=0(产品在A、B工序加工的数量相等）x312-x322=0(产品在A、B工序加工的数量相等）xijk0,i=1,2,3;j=1