清华大学运筹学3运输问题.pptx

第三章运输问题,第一节运输问题及其数学模型第二节表上作业法第三节进一步讨论,1/73,第一节运输问题及其数学模型,一、问题的提出,2/73,3/73,3,11,3,10,1,9,2,8,7,4,10,5,例2平整某场地，有三处高，需削平，有四处低，需填高。已算出高处总余方量恰好满足低处总需方量。12种运价也已算出，在右上角方格内。问：如何调度，才花费最少？,4/73,Minz=3x11+11x12+3x13+10 x14+x21+9x22+2x23+8x24+7x31+4x32+10 x33+5x34s.t.x11+x12+x13+x14=7x21+x22+x23+x24=4x31+x32+x33+x34=9x11+x21+x31=3x12+x22+x32=6x13+x23+x33=5x14+x24+x34=6xij0，1i3,1j4，i和j皆为正整数。供应点有m=3个，用户有n=4个。,5/73,运输问题数学模型Minz=CXs.t.AX=bX0X=(x11,x12,x13,x14,x21,x22,x23,x24,x31,x32,x33,x34)TC=(c11,c12,c13,c14,c21,c22,c23,c24,c31,c32,c33,c34)b=(s1,s2,s3,d1,d2,d3,d4)Ts1,s2和s3分别是三个供应点供应量,d1,d2,d3和d4分别是四个用户需求量。当s1+s2+s3=d1+d2+d3+d4时，是供求平衡运输问题，否则，是供求不平衡运输问题。先讨论前者。,6/73,x11x12x13x14x21x22x23x24x31x32x33x34111111111111A=111111111111A是(m+n)(mn)矩阵，又可写成：A=(P11,P12,P13,P14,P21,P22,P23,P24,P31,P32,P33,P34),7/73,Pij=ei+em+jei和em+j分别是第i和第m+j个元素为1的m+n维单位向量。,第二节表上作业法,8/73,一、确定初始可行解1.最小元素法2.西北角法（不讲）3.Vogel法（不讲）1.最小元素法举例说明。,9/73,10/73,3,11,3,10,1,9,2,8,7,4,10,5,从A2运往B1的费用最低，先将A2的土运往B1，B1需求量是3，满足后，A2还有剩余。B1的需求既然已经满足，以后不再考虑。划去第一列,11/73,3,11,3,10,1,9,2,8,7,4,10,5,剩下的，从A2运往B3的费用最低，B3需要5，A2只能满足1。A2以后不再考虑。划去第二行。,12/73,3,11,3,10,1,9,2,8,7,4,10,5,剩下的，从A1运往B3的费用最低，将A1的土运往B3，B3需求量是4，从A1运来4，就满足了，以后不再考虑。划去第三列。,13/73,3,11,3,10,1,9,2,8,7,4,10,5,剩下的，从A3运往B2的费用最低，B2需求量是6，可从A3处满足，以后不再考虑。划去第二列。,14/73,3,11,3,10,1,9,2,8,7,4,10,5,剩下的，从A3运往B4的费用最低，B4需求量是6，可从A3处得到3，以后不再考虑A3。划去第三行。,15/73,3,11,3,10,1,9,2,8,7,4,10,5,B4需3，A1剩3，可满足。划去第一行和第四列。非负数字格叫基格，对应基变量(m+n-1个)。其他格叫非基格，对应非基变量(mn-m-n+1个)，非基变量均取0。,16/73,z=3x13+10 x14+x21+2x23+4x32+5x34=34+103+3+21+46+53=12+30+3+2+24+15=86初始基可行解是否最优，即z是否达到了最小值？用非基变量检验数判断。检验数有几种算法。1.迴路法计算检验数ij=cij-CBB-1Pij，为此，考察非基变量同基变量的关系。B=(P13,P14,P21,P23,P32,P34,e7),17/73,先看非基变量x11，非基格11与基格13、基格23、基格21构成迴路。再看如下关系：P11-P13+P23-P21=e1+e4-e1-e6+e2+e6-e2-e4=0,18/73,因此有，P11=P13-P23+P2111=c11-CBB-1P11=c11-CBB-1(P13-P23+P21)=c11-CB(e1-e4+e3)=c11-(c13,c14,c21,c23,c32,c34,0)(e1-e4+e3)=c11-(c13-c23+c21)=3-(3-2+1)=1B=(P13,P14,P21,P23,P32,P34,e7),3,3,1,2,19/73,同样，P12=P14-P34+P3212=c12-CBB-1P12=c12-CBB-1(P14-P34+P32)=c12-CB(e2-e6+e5)=c12-(c13,c14,c21,c23,c32,c34,0)(e2-e6+e5)=c12-(c14-c34+c32)=11-(10-5+4)=2B=(P13,P14,P21,P23,P32,P34,e7),11,10,4,5,20/73,同样，P22=P23-P13+P14-P34+P3222=c22-CBB-1(P23-P13+P14-P34+P32)=c22-CB(e4-e1+e3-e6+e5)=c12-(c13,c14,c21,c23,c32,c34,0)(e4-e1+e3-e6+e5)=c12-(c23-c13+c14-c34+c32)=9-(2-3+10-5+4)=1B=(P13,P14,P21,P23,P32,P34,e7),10,4,5,3,9,2,21/73,24=c24-(c23-c13+c14)=8-(2-3+10)=-1,10,8,3,2,22/73,31=c31-(c21-c23+c13-c14+c34)=7-(1-2+3-10+5)=10,10,5,3,2,1,7,23/73,33=c33-(c13-c14+c34)=10-(3-10+5)=12,10,5,3,10,24/73,2.对偶变量法计算检验数运输问题数学模型Minz=CXs.t.AX=bX0对偶问题是Maxw=+=s.t.ui+vjcij,25/73,Minz=3x11+11x12+3x13+10 x14+x21+9x22+2x23+8x24+7x31+4x32+10 x33+5x34s.t.x11+x12+x13+x14=7u1x21+x22+x23+x24=4u2x31+x32+x33+x34=9u3x11+x21+x31=3v1x12+x22+x32=6v2x13+x23+x33=5v3x14+x24+x34=6v4其对偶问题是,26/73,Maxw=7u1+4u2+9u3+3v1+6v2+5v3+6v4s.t.u1+v13=c11u1+v211=c12u1+v33=c13u1+v410=c14u2+v11=c21u2+v29=c22u2+v32=c23u2+v48=c24u3+v17=c31u3+v24=c32u3+v310=c33u3+v45=c34,27/73,令YT=(u1,u2,um,v1,v2,vn)则ij=cij-CBB-1Pij=cij-YTPij=cij-(u1,u2,um,v1,v2,vn)(ei+em+j)=cij-(ui+vj)对于基变量xij，检验数ij=0，即ui+vj=cij若从中求得ui和vj，就能利用ij=cij-(ui+vj)求得非基变量的ij。,先看基变量u1+v3=3,令u1=0，v3=3u1+v4=10,v4=10，u2+v3=2,u2=-1，u2+v1=1,v1=2，u3+v4=5,u3=-5，u3+v2=4,v2=9，,28/73,3,11,3,10,1,9,2,8,7,4,10,5,再看非基变量11=c11-u1-v1=3-0-2=1,12=c12-u1-v2=11-0-9=2,22=c22-u2-v2=9+1-9=1,24=c24-u2-v4=8+1-10=-131=c31-u3-v1=7+5-2=10,33=c33-u3-v3=10+5-3=12u1=0，v3=3,v4=10，u2=-1，v1=2，u3=-5，v2=9，,29/73,3,11,3,10,1,9,2,8,7,4,10,5,30/73,三、解的改进1.以x24为换入变量2.以非基格24为第一个顶点，沿迴路找运输量最小的偶数顶点，将该格换出，并以其运输量为调整量=minxij|基格ij是偶数顶点。3.沿迴路调整各格中运输量，奇数格加，偶数格减。4.调整后，再计算检验数。若所有的ij0，已经得到最优解。否则，重复以上步骤，直到取得最优解。,31/73,=minx23，x14=min1，3=1,32/73,重新计算检验数11=c11-(c14-c24+c21)=3-10+8-1=012=c12-c14+c34-c32=11-10+5-4=222=c22-c24+c34-c32=9-8+5-4=223=c23-c24+c14-c13=2-8+10-3=131=c31-c21+c24-c34=7-1+8-5=933=c33-c13+c14-c34=10-3+10-5=12,3,11,3,10,1,9,2,8,7,4,10,5,33/73,所有的ij0，已经得到最优解。z=3x13+10 x14+x21+8x24+4x32+5x34=35+102+3+81+46+53=15+20+3+8+24+15=85,34/73,四、须注意之点1.若有多个非基变量检验数小于零，一般取最小者对应的非基变量换入。2.若有非基变量检验数等于零，说明有多重解，应当将其全部求出。3.当同时划掉一行和一列时，会出现退化解。这时，应在该行和该列相交的格中填数字0，确保有m+n-1个基格（基变量）。,第三节进一步讨论,35/73,36/73,一、供求不平衡运输问题如果=这时的数学模型是Minz=s.t.=si(i=1,2,m)=dj(j=1,2,n)xij0为了用表上作业法，可添加一个假想用户Bn+1，需求量就是运不出去的数量，运费是0，即ci,n+1=0。Bn+1的需求量dn+1=,37/73,于是，这时的数学模型是Minz=+s.t.=+=si(i=1,2,m)=dj(j=1,2,n+1)xij0供不应求问题，同样处理。,38/73,2,7,4,3,6,5,例1有两个砖厂，供三个城市使用。产量、需求量和单位运费列于下表。问：如何调度，才使运费最少？,39/73,2,7,4,0,3,6,5,0,假设滞销的砖由该地区建委收购，留在砖厂，以备将来使用。这样，建委就成了第四个用户。,以下用最小元素法确定初始基可行解,40/73,2,7,4,0,3,6,5,0,2,7,4,0,3,6,5,0,41/73,2,7,4,0,3,6,5,0,2,7,4,0,3,6,5,0,12=c12-c13+c23-c22=7-4+5-6=2均大于0，已经得21=c21-c11+c13-c23=3-2+4-5=0到最优解。14=c14-c24+c23-c13=0-0+5-4=1，Minz=210+415+625=230,42/73,2,7,4,0,3,6,5,0,43/73,8,7,4,3,5,9,例2政府计划将两个老区500户搬到三个新建小区。愿意搬的人家、住宅套数和每户拆迁费列于下表。问：如何调度，才使拆迁费最少（假定每户一套）？,44/73,8,7,4,3,5,9,假设剩下的100套由市住房办保管，用作临时安置新增人口。不需拆迁费。,0,0,0,45/73,8,7,4,3,5,9,0,0,0,用最小元素法确定初始基可行解1,46/73,8,7,4,3,5,9,0,0,0,用最小元素法确定初始基可行解2,47/73,8,7,4,3,5,9,0,0,0,用最小元素法确定初始基可行解3,48/73,8,7,4,3,5,9,0,0,0,用最小元素法确定初始基可行解4,49/73,8,7,4,3,5,9,0,0,0,用最小元素法确定初始基可行解5,50/73,8,7,4,3,5,9,0,0,0,判断是否最优：11=c11-c13+c23-c21=8-4+9-3=1012=c12-c13+c23-c22=7-4+9-5=732=c32-c31+c21-c22=0-0+3-5=-233=c33-c31+c21-c23=0-0+3-9=-6z=4150+3100+5100+950=1850,51/73,8,7,4,3,5,9,0,0,0,换基：非基变量x33换入，确定调整量=minx31,x23=min100,50=50，调整如下：,52/73,8,7,4,3,5,9,0,0,0,重新计算检验数11=c11-c13+c33-c31=8-4+0-0=412=c12-c13+c33-c31+c21-c22=7-4+0-0+3-5=123=c23-c33+c31-c21=9-0+0-3=632=c32-c31+c21-c22=0-0+3-5=-2z=4150+3150+5100=1550,53/73,8,7,4,3,5,9,0,0,0,再换基：非基变量x32换入，确定调整量=minx31,x22=min50,100=50，调整如下：,54/73,8,7,4,3,5,9,0,0,0,重新计算检验数11=c11-c13+c33-c32+c22-c21=8-4+0-0+5-3=612=c12-c13+c33-c32=7-4+0-0=323=c23-c33+c32-c22=9-0+0-5=431=c31-c21+c22-c32=0-3+5+0=2，所有的ij0，已得到最优解。Minz=4150+3200+550=1450,55/73,3,7,6,0,2,4,3,0,4,3,8,0,习题3.7第2题,4,2,5,56/73,3,7,6,0,2,4,3,0,4,3,8,0,习题3.7第2题,4,2,5,57/73,3,7,6,0,2,4,3,0,4,3,8,0,习题3.7第2题,4,2,5,58/73,3,7,6,0,2,4,3,0,4,3,8,0,习题3.7第2题,4,2,5,59/73,3,7,6,0,2,4,3,0,4,3,8,0,习题3.7第2题,4,2,5,60/73,3,7,6,0,2,4,3,0,4,3,8,0,习题3.7第2题,4,2,5,61/73,计算检验数12=c12-c14+c34-c32=7-4+5-3=513=c13-c14+c33-c33=6-4+5-8=-122=c22-c21+c11-c14+c35-c32=4-2+3-4+5-3=323=c23-c33+c34-c14+c11-c21=3-8+5-4+3-2=-324=c24-c21+c11-c14=2-2+3-4=-125=c25-c15+c11-c21=0-0+3-2=131=c31-c34+c14-c11=4-5+4-3=035=c35-c15+c14-c34=0-0+4-5=-1令x23换入。然后，沿计算23的回路调整运输量。,62/73,3,7,6,0,2,4,3,0,4,3,8,0,习题3.7第2题,4,2,5,63/73,3,7,6,0,2,4,3,0,4,3,8,0,习题3.7第2题,4,2,5,64/73,再计算检验数12=c12-c11+c21-c23+c33-c32=7-3+2-3+8-3=813=c13-c23+c32-c11=6-3+2-3=214=c14-c34+c33-c23+c21-c11=4-5+8-3+2-3=322=c22-c32+c33-c23=4-3+8-3=624=c24-c23+c33-c34=2-3+8-5=225=c25-c15+c11-c21=0-0+3-2=131=c31-c33+c23-c21=4-8+3-2=-335=c35-c15+c11-c21+c23-c33=0-0+3-2+3-8=-4令x35换入。然后，沿计算35的回路调整运输量。,65/73,3,7,6,0,2,4,3,0,4,3,8,0,习题3.7第2题,4,2,5,35=c35-c15+c11-c21+c23-c33=0-0+3-2+3-8=-4,66/73,3,7,6,0,2,4,3,0,4,3,8,0,习题3.7第2题,4,2,5,67/73,第三次计算检验数12=c12-c15+c35-c32=7-0+0-3=413=c13-c11+c21-c23=6-3+2-3=214=c14-c15+c35-c34=4-0+0-5=-122=c22-c21+c11-c15+c35-c32=4-2+3-0+0-3=224=c24-c34+c35-c15+c11-c21=2-5+0-0+3-2=-225=c25-c15+c11-c21=0-0+3-2=131=c31-c35+c15-c11=4-0+0-3=1令x24换入。然后，沿计算24的回路调整运输量。,68/73,3,7,6,0,2,4,3,0,4,3,8,0,习题3.7第2题