线性规划问题及单纯形法概述(ppt 66页).ppt

运筹学,OperationsResearch,第一章线性规划及单纯形法,第一章线性规划及单纯形法,线性规划（LinearProgramming，简称LP）运筹学的一个重要分支，是运筹学中研究较早、发展较快、理论上较成熟和应用上极为广泛的一个分支。,1947年G.B.Dantying提出了一般线性规划问题求解的方法单纯形法之后，线性规划的理论与应用都得到了极大的发展。,60年来，随着计算机的发展，线性规划已广泛应用于工业、农业、商业、交通运输、经济管理和国防等各个领域，成为现代化管理的有力工具之一。,1线性规划问题及其数学模型,e.g.1资源的合理利用问题,问：如何安排生产计划，使得既能充分利用现有资源又使总利润最大？,表1产品资源甲乙库存量A1360B1140单件利润1525,某工厂在下一个生产周期内生产甲、乙两种产品，要消耗A、B两种资源，已知每件产品对这两种资源的消耗，这两种资源的现有数量和每件产品可获得的利润如表1。,第一章线性规划及单纯形法,maxz=15x1+25x2s.t.x1+3x260 x1+x240 x1，x20,解：,设x1，x2为下一个生产周期产品甲和乙的产量；,约束条件：,Subjectto,x1+3x260,x1+x240,x1，x20,目标函数：,z=15x1+25x2,表1产品资源甲乙库存量A1360B1140单件利润1525,决策变量,1线性规划问题及其数学模型,e.g.2营养问题,假定在市场上可买到B1,B2,Bnn种食品，第i种食品的单价是ci,另外有m种营养A1,A2,Am。设Bj内含有Ai种营养数量为aij(i=1m,j=1n)，又知人们每天对Ai营养的最少需要量为bi。见表2：,表2食品最少营养B1B2Bn需要量A1a11a12a1nb1A2a21a22a2nb2Amam1am2amnbm单价c1c2cn,试在满足营养要求的前提下，确定食品的购买量，使食品的总价格最低。,第一章线性规划及单纯形法,表2食品最少营养B1B2Bn需要量A1a11a12a1nb1A2a21a22a2nb2Amam1am2amnbm单价c1c2cn,解：,设xj为购买食品Bj的数量(j=1,2,n),（i=1,2,m）,xj0（j=1,2,n）,0xjlj,1线性规划问题及其数学模型,三个基本要素：,Note：,1、善于抓住关键因素，忽略对系统影响不大的因素；,2、可以把一个大系统合理地分解成n个子系统处理。,1、决策变量xj0,2、约束条件一组决策变量的线性等式或不等式,3、目标函数决策变量的线性函数,第一章线性规划及单纯形法,max（min）z=c1x1+c2x2+cnxns.t.a11x1+a12x2+a1nxn（或=，）b1a21x1+a22x2+a2nxn（或=，）b2am1x1+am2x2+amnxn（或=，）bmxj0（j=1,2,n）,其中aij、bi、cj（i=1,2,m；j=1,2,n）为已知常数,1线性规划问题及其数学模型,线性规划问题的标准形式：,maxz=c1x1+c2x2+cnxns.t.a11x1+a12x2+a1nxn=b1a21x1+a22x2+a2nxn=b2am1x1+am2x2+amnxn=bmxj0（j=1,2,n）bi0（i=1,2,m）,特点：,1、目标函数为极大化；,2、除决策变量的非负约束外，所有的约束条件都是等式，且右端常数均为非负；,3、所有决策变量均非负。,第一章线性规划及单纯形法,如何转化为标准形式？,1、目标函数为求极小值，即为：。,因为求minz等价于求max(-z)，令z=-z，即化为：,2、约束条件为不等式，,xn+10松弛变量,如何处理？,1线性规划问题及其数学模型,、右端项bi0,xk0，,分两种情况讨论：,如果p1,p2,pk线性无关，即x的非零分量对应的列向量线性无关，则由定理1知，它是LP的一个基本可行解，定理成立。,(2)如果p1,p2,pk线性相关，则必存在一组不全为零的数1,2,k使得,第一章线性规划及单纯形法,假定有i0，,取,作,其中,由（6）式知，必有,即,又因为由（5）式知,故有，,，即,也是LP的两个可行解。,3线性规划问题解的基本性质,再由的取法知，在式(7)的诸式中，至少有一个等于零，于是所作的可行解中，它的非零分量的个数至少比x的减少1，如果这些非零分量所对应的列向量线性无关，则为基可行解，定理成立。,否则，可以从出发，重复上述步骤，再构造一个新的可行解，使它的非零分量的个数继续减少。这样经过有限次重复之后，必可找到一个可行解使它的非零分量对应的列向量线性无关，故可行解必为基可行解。证毕。,返回,3线性规划问题解的基本性质,定理3证明,设,是LP的一个最优解。,如果x*是基本解，则定理成立；,如果x*不是基本解，则由定理2的证明过程可构造两个可行解,它的非零分量的个数比x*的减少，且有,，,又因为x*是最优解，故有,由式（8）和（9）知，必有,即x(1),x(2)仍为最优解。,如果x(1)或x(2)是基可行解，则定理成立。,否则，按定理2证明过程，可得基可行解x(s)或x(s+1),使得,即得基可行解x(s)或x(s+1)为最优解。,返回,第一章线性规划及单纯形法,LP问题解的几何意义,定义5设集合是n维欧氏空间中的一个点集，如果及实数,则称S是一个凸集。,几何意义：如果集合中任意两点连线上的一切点都在该集合中，则称该集合为凸集。,Note:空集和单点集也是凸集。,3线性规划问题解的基本性质,定义6设则称,为点的一个凸组合。,第一章线性规划及单纯形法,定理5设D为LP问题的可行解集，则x是D的极点的充分必要条件是x为LP问题的基可行解。,prove,（此时，该LP问题有无穷多最优解）,3线性规划问题解的基本性质,Note:,1、如何判断LP问题有最优解；,2、计算复杂性问题。,设有一个50个变量、20个约束等式的LP问题，则最多可能有个基。,即约150万年,4单纯形法的基本原理,单纯形法（SimplexMethod）是1947年由G.B.Dantzig提出，是解LP问题最有效的算法之一，且已成为整数规划和非线性规划某些算法的基础。,基本思路：基于LP问题的标准形式，先设法找到一个基可行解，判断它是否是最优解，如果是则停止计算；否则，则转换到相邻的目标函数值不减的一个基可行解.（两个基可行解相邻是指它们之间仅有一个基变量不相同）。,第一章线性规划及单纯形法,单纯形法引例,首先，化原问题为标准形式：,x3,x4是基变量.,基变量用非基变量表示：,x3=60-x1-3x2x4=40-x1-x2,代入目标函数：,z=15x1+25x2,令非基变量x1=x2=0,z=0基可行解x(0)=(0,0,60,40)T,是最优解吗？,maxz=15x1+25x2s.t.x1+3x260 x1+x240 x1，x20,maxz=15x1+25x2+0 x3+0 x4s.t.x1+3x2+x3=60 x1+x2+x4=40 x1，x2,x3,x40,4单纯形法的基本原理,z=15x1+25x2x3=60-x1-3x2x4=40-x1-x2,因为x2的系数大，所以x2换入基变量。,x3=60-3x20 x4=40-x20,谁换出？,如果x4换出，则x2=40，x3=-60，不可行。,如果是“+”会怎样？,如果x3换出，则x2=20，x4=20。,最小比值法则,所以x3换出。,基变量用非基变量表示：,代入目标函数：,z=500+20/3x1-25/3x3,令非基变量x1=x3=0,z=500基可行解x(1)=(0,20,0,20)T,大于零！,第一章线性规划及单纯形法,因为x1的系数大，所以x1换入基变量。,所以x4换出。,基变量用非基变量表示：,代入目标函数：,z=7005x310 x4,令非基变量x3=x4=0,z=700基可行解x(2)=(30,10,0,0)T,因为非基变量的系数都小于零，所以x(2)=(30,10,0,0)T是最优解zmax=700,4单纯形法的基本原理,目标函数用非基变量表示时，非基变量的系数称为检验数,(40,0),(0,0),(0,20),A,B,C,(30,10),O,L1,L2,Z=250,x2,x1,x(0)=(0,0,60,40)Tz=0,x(1)=(0,20,0,20)Tz=500,x(2)=(30,10,0,0)Tz=700,第一章线性规划及单纯形法,单纯形法的基本原理,称(1a)(2a)(3a)为LP问题对应于基B的典则形式（典式）.,Ax=b,基变量用非基变量表示：,代入目标函数：,4单纯形法的基本原理,如果记,则典式(1a)(2a)(3a)可写成,第一章线性规划及单纯形法,定理7在LP问题的典式(1b)(3b)中，如果有,则对应于基B的基可行解,是LP问题的最优解，记为,相应的目标函数最优值z*=z(0),此时，基B称为最优基,4单纯形法的基本原理,定理8在LP问题的典式(1b)(3b)中，,是对应于基B的一个基可行解，如果满足下列条件：,(1)有某个非基变量xk的检验数k0(m+1kn);,(2)aik(i=1,2,m)不全小于或等于零，即至少有一个aik0(i=1,2,m);,(3)0(i=1,2,m),即x(0)为非退化的基可行解。,则从x(0)出发，一定能找到一个新的基可行解,第一章线性规划及单纯形法,定理9在LP问题的典式(1b)(3b)中，如果检验数满足最优准则j0(j=m+1,n)，且其中有一个k=0(m+1kn)，则该LP问题有无穷多个最优解。,这在应用中很有价值,则该LP问题解无界（无最优解）。,5单纯形法的计算步骤,单纯形表,第一章线性规划及单纯形法,如何得到单纯形表？,B-1b,-cBB-1b,检验数,BN,cBcN,IB-1N,0cN-cBB-1N,5单纯形法的计算步骤,e.g.4列出如下LP问题的初始单纯形表。,maxz=4x1+3x2+2x3+5x4s.t.x1+3x2+x3+2x4=54x1+2x2+3x3+7x4=17x1，x2，x3，x40,不妨已知x3、x4为可行基变量,1,-7,0,1,2,6,-31,0,5,-2,-1,17,1,0,1,1,4,0,-12,x(0)=(0,0,1,2)T,z0=12,第一章线性规划及单纯形法,单纯形法求解LP问题的计算步骤：,Step1找出初始可行基，列初始单纯形表,确定初始基可行解；,Step2检验各非基变量xj的检验数j,如果所有的j0（j=1,2,n），则已求得最优解，停止计算。否则转入下一步；,Step3在所有的j0中，如果有某个k0，所对应的xk的系数列向量pk0（即aik0，i=1,2,m），则此问题解无界，停止计算。否则转入下一步;,5单纯形法的计算步骤,Step4根据,确定xk为换入基变量，又根据最小比值法则计算:确定xr为换出基变量。转入下一步;,Step5以为主元进行换基变换，用初等行变换将xk所对应的列向量变换成单位列向量，即,同时将检验数行中的第k个元素也变换为零，得到新的单纯形表。返回Step2。,第一章线性规划及单纯形法,maxz=15x1+25x2s.t.x1+3x260 x1+x240 x1，x20,maxz=15x1+25x2+0 x3+0 x4s.t.x1+3x2+x3=60 x1+x2+x4=40 x1，x2，x3，x40,0,0,x2,1/3,-500,x1,0,-700,1/2,检验数都小于等于零,x(2)为最优解zmax=700,60/3,40/1,25,3,1/3,1,20,0,0,-1/3,1,20,20/3,-25/3,0,20/1/3,20/2/3,15,2/3,2/3,1,0,-1/2,3/2,30,0,-1/2,10,0,-5,-10,5单纯形法的计算步骤,思考：,在单纯形法中根据,确定xk为进基变量，是否在这次变换中，使目标函数值提高最大？,如果不是，应选择哪个变量进基，保证这次变换使得目标函数值提高最大？,目标函数值能提高多少？,6单纯形法的进一步讨论,一、初始可行基的求法,maxz=c1x1+c2x2+cnxn(1c)s.t.a11x1+a12x2+a1nxn=b1a21x1+a22x2+a2nxn=b2.(2c)am1x1+am2x2+amnxn=bmxj0（j=1,2,n）(3c),a11x1+a12x2+a1nxn+xn+1=b1a21x1+a22x2+a2nxn+xn+2=b2am1x1+am2x2+amnxn+xn+m=bmxj0（j=1,2,n,n+1,n+m）,人工变量,1、试算法,人造基本解：x0=(0,0,0,b1,bm)T,2、人工变量法,6单纯形法的进一步讨论,(1)大M法,惩罚法,maxw=c1x1+c2x2+cnxnM(xn+1+xn+m)s.t.a11x1+a12x2+a1nxn+xn+1=b1a21x1+a22x2+a2nxn+xn+2=b2am1x1+am2x2+amnxn+xn+m=bmxj0（j=1,2,n,n+1,n+m）,M是一个充分大的正数,结论：,设,为上述问题的最优解,则,为原问题的最优解，这时的目标函数值为最优值；,则原问题无可行解。,不全为零，,第一章线性规划及单纯形法,e.g.5,用大M法求解,maxz=3x1-x2x3s.t.x1-2x2+x311-4x1+x2+2x33-2x1+x3=1x1，x2，x30,maxz=3x1-x2x3+0 x4+0 x5-Mx6-Mx7s.t.x1-2x2+x3+x4=11-4x1+x2+2x3-x5+x6=3-2x1+x3+x7=1xj0(j=1,2,7),解：,引入松弛变量x4，x5和人工变量x6，x7得,3-4M,M-1,2M-1,0,-M,0,-M,3M,3-6M,M-1,3M-1,0,-M,0,0,4M,11/1,3/2,1/1,x3,-1,1,3,-2,0,1,1,0,0,-1,10,0,1,0,0,-1,1,-2,1,1,M-1,0,0,-M,1-3M,M+1,1/1,1,x2,-1,3,0,0,1,-2,2,-5,12,1,0,0,0,-1,-1-M,2,1,12/3,x1,3,0,0,1/3,-2/3,2/3,-5/3,4,0,0,1,2/3,-4/3,4/3,-7/3,9,0,0,0,-1/3,-1/3,2/3-M,-2,3,1,0,1-M,1/3-M,200-0.2M0?,由于人工变量x6=x7=0,所以,得原问题的最优解x*=(4,1,9,0,0)T目标函数最优值zmax=2,Note:在计算过程中,某个人工变量一旦变为非基变量,则该列可被删去,6单纯形法的进一步讨论,(2)两阶段法,第一阶段：,maxz=c1x1+c2x2+cnxn(1c)s.t.a11x1+a12x2+a1nxn=b1a21x1+a22x2+a2nxn=b2.(2c)am1x1+am2x2+amnxn=bmxj0（j=1,2,n）(3c),maxw=xn+1xn+2xn+m(1d)s.t.a11x1+a12x2+a1nxn+xn+1=b1a21x1+a22x2+a2nxn+xn+2=b2(2d)am1x1+am2x2+amnxn+xn+m=bmxj0（j=1,2,n,n+1,n+m）(3d),判断原LP问题,（1c）（3c）是否存在可行解，如果存在就找出一个初始基可行解；,解之可得：,（a）如果wmax0,则原问题无可行解，停止计算；,（b）如果wmax=0,且人工变量都不是基变量，则转入第二阶段；,第一章线性规划及单纯形法,（c）如果wmax=0,但仍有取零的人工变量为基变量；,x1x2xnxn+1xn+kxn+mbal1al2alnaln+11an+m0,如xn+k=0是基变量，在最终单纯形表中：,al1al2aln不可能全为零，必有某个alj0，这时xj不是基变量，与xn+k交换即可。,第二阶段：,从第一阶段所求得的初始可行基出发，求解原问题,6单纯形法的进一步讨论,二、关于退化和循环,1955年Beale给出如下例子：,最优解：,第一章线性规划及单纯形法,Bland法则：,（对极大值问题而言）,则选择xk作为进基变量。,7线性规划应用举例,e.g.6生产计划问题,某工厂明年根据合同，每个季度末向销售公司提供产品，有关信息如表，若当季生产的产品过多，季末有积余，则一个季度每积压一吨产品需支付存贮费0.2万元.现该厂考虑明年的最佳生产方案，使该厂在完成合同的情况下，全年的生产费用最低.试建立线性规划模型.,第一章线性规划及单纯形法,解：,方法一,设工厂第j季度生产产品xj吨,需求约束：,第一季度末需交货20吨，x120,第二季度末需交货20吨，x1-20+x220,这是上季末交货后积余,第三季度末需交货30吨，x1+x2-40+x330,第四季度末需交货10吨，x1+x2+x3-70+x4=10,生产能力约束：,0xjajj=1,2,3,4,生产、存储费用：,第一季度：15x1第二季度:14x2+0.2(x1-20)第三季度:15.3x3+0.2(x1+x2-40)第四季度:14.8x4+0.2(x1+x2+x3-70),minz=15.6x1+14.4x2+15.5x3+14.8x4-26s.t.x1+x240,x1+x2+x370 x1+x2+x3+x4=80,20x130,0x240,0x320,0x410.,7线性规划应用举例,方法二,设第i季度生产而用于第j季度末交货的产品数量为xij吨.,需求约束：,x11=20 x12+x22=20,x13+x23+x33=30 x14+x24+x34+x44=10,生产能力约束：,x11+x12+x13+x1430,x22+x23+x2440,x33+x3420,x4410,xij的费用cij=di+0.2(j-i),minz=15x11+15.2x12+15.4x13+15.6x14+14x22+14.2x23+14.4x24+15.3x33+15.5x34+1