《运筹学》第三章运输问题.ppt

1,第3章 运输问题,2,3.1 运输问题的典例和数学模型,3.2 运输问题的求解方法：表上作业法,3.3 几类特殊的运输问题,3.4 运输问题的应用,3,运输问题：根据已有的交通网，如何制定运输方案，使得这些物资被运送到各个销售地，并保证某个指标最优(例如总运费最小)。,4,3.1 运输问题的典例和数学模型,一、典例 某食品公司经营糖果业务，公司下设三个工厂A1、A2、A3，四个销售门市部B1、B2、B3、B4。已知每天各自的生产量、销售量及调运时的单位运输费用情况。问：如何调运可使总费用最小？,生产量：A17吨，A2 4吨，A3 9吨销售量：B1 3吨，B2 6吨，B3 5吨，B4 6吨,产地,单位运价,销地,B1 B2 B3 B4,A1,A2,A3,3 11 3 10,1 9 2 8,7 4 105,5,调运示意图,A1,A2,A3,B1,B2,B3,B4,7吨,4吨,9吨,3吨,6吨,5吨,6吨,x11,x12,x13,x14,x21,x22,x23,x24,x31,x32,x33,x34,产地,销地,6,二、建立模型,设 xij第i产地到第j销地之间的调运量，则有,Min z=cij xij,3,4,i=1,j=1,x11+x12+x13+x14=7,x11+x21+x31=3,xij0,(i=1,2,3；j=1,2,4),产量限制,销量限制,x21+x22+x23+x24=4,x31+x32+x33+x34=9,x12+x22+x32=6,x13+x23+x33=5,x14+x24+x34=6,7,单位运价表,产销平衡表,8,一般模型表示(ai=bj),9,三、模型的特点,1.变量数：mn个2.约束方程数：m+n个 最大独立方程数：m+n-13.系数列向量结构：,Pij=,第i个分量第m+j个分量,0110,10,x11 x12 x1n x21 x22 x2n,xm1 xm2 xmn,1 1 1 0 0 0 0 0 00 0 0 1 1 1 0 0 00 0 0 0 0 0 1 1 11 0 0 1 0 0 1 0 00 1 0 0 1 0 0 1 00 0 1 0 0 1 0 0 1,i=1i=2i=mj=1j=2j=n,11,关于运输模型的几个结论：(1)设有m个产地，n个销地且产销平衡的运输问题，则基变量数是m+n-1；(2)若变量组B包含有闭回路，则B中变量对应的列向量线性相关；(3)m+n-1个变量组构成基变量的充要条件是它不包含任何闭回路。,12,初始基可行解,新的基可行解,最优否？,STOP,Y,N,3.2 运输问题的求解方法：表上作业法,单纯形法求解思路,13,表上作业法步骤:初始运输方案最优性检验改进运输方案一、初始方案的确定1.最小元素法2.Vogel法二、最优性检验1.闭回路法2.位势法三、方案改进方法在闭回路内改进。,14,3,产地,销地,A1 A2 A3,B1 B2 B3 B4,产地,销地,A1 A2 A3,B1 B2 B3 B4,产量,销量,3 11 3 10 1 9 2 8 7 4 10 5,6,3,4,1,3,3 6 5 6,7 4 9,单位运价表,产销平衡表,最小元素法,15,例,产地,销地,A1 A2,B1 B2,15 15,10 20,产量,销量,2,8,5,1,最小元素法：z=810+25+115=105,Vogel法：z=105+152+51=85,Vogel法,16,产地,销地,A1 A2 A3,B1 B2 B3 B4,7 4 9,产量,销量,3 6 5 6,6,3,5,2,1,3,产地,销地,A1 A2 A3,B1 B2 B3 B4,行两最小元素之差,列两最小元素之差,3 11 3 10 1 9 2 8 7 4 10 5,0 1 1,2 5 1 3,0 1 2,2-1 3,0 1-,2-1 2,7 6-,-1 2,Vogel法,产销平衡表,17,针对最小元素法和vogel法，需要说明的几点：,(1)任何运输问题都有基可行解，且有最优解；,(2)如果供应量和需求量都是整数，那么一定可以得到整数形式的最优解;,(4)若在中途同时有行列要求得到满足，将同时划掉一行一列，最后数字格个数将少于m+n-1个。为使数字格的个数恰好等于m+n-1，在同时划去的行列中，任选（或选其价格系数最小元素对应的）空格，填上数字0作为特殊的数字格（即基变量）。,(3)用最小元素法和vogel法得到的是运输问题的一个基可行解，数字格对应基变量；,18,例,产地,销地,A1 A2 A3,B1 B2 B3 B4,产地,销地,A1 A2 A3,B1 B2 B3 B4,产量,销量,2 7 3 11 8 4 6 9 4 3 10 5,20,30 25 10 15,20 10 50,单位运价表,产销平衡表,10,25,15,10,0,19,产地,销地,A1 A2 A3,B1 B2 B3 B4,产地,销地,A1 A2 A3,B1 B2 B3 B4,产地,销地,A1 A2 A3,B1 B2 B3 B4,产量,销量,3 11 3 10 1 9 2 8 7 4 10 5,6,3,4,3,1,3,3 6 5 6,7 4 9,3 6 5 6,7 4 9,产量,销量,3,6,3,5,2,1,(1),(2),(1),(-1),(10),(12),z=c11-c13+c23-c21=1=11,z=c12-c14+c34-c32=2=12,(0),(2),(2),(9),(1),(12),单位运价表,产销平衡表,闭回路法,20,注:只要求的基变量是正确的，并且数目为m+n-1个，那么每个非基变量的闭回路存在且唯一，因此，检验数唯一。,21,产地,销地,A1 A2 A3,B1 B1 B3 B4,位势法,4,1,3,2.计算行位势和列位势；令v1=1，则依cij=ui+vj 计算各ui和vj,3.计算空格处位势；ij=ui+vj,行位势ui,列位势vj,1,1,0,-4,2,8,9,4.计算空格处检验数：ij=cij-ij,1.数字格处上添上对应的运价；,销地,A1 A2 A3,B1 B1 B3 B4,3 11 3 10 1 9 2 8 7 4 10 5,产地,单位运价表,位势表:,2,10,5,(2),(9),(8),(9),(-3),(-2),22,产地,销地,A1 A2 A3,B1 B1 B3 B4,7 4 9,产量,销量,3 6 5 6,6,3,4,3,(-1),3,(1),(2),(1),(10),1,(12),检验数表,注：位势法求检验数的依据是对偶理论。,23,注:对于同一组基变量，所求的检验数是唯一的；(2)在最优解表中，有非基变量（即空格)的检验数为0，根据线性规划单纯形法原理知，应有无穷多最优解，即有多解。运输问题表上作业法求多解的方法：任选一检验系数为0的空格入基，进行方案改进，可得新的最优解；(3)在进行调运方案改进时，若沿闭合回路出现多个可作为调出变量的数字格（即闭回路上的数字格最小值有多个），此时，任选一个为调出变量，其余的填0，保证调整后的调运方案中仍有m+n-1个数字格。,24,5,例：,产地,销地,A1 A2 A3,B1 B1 B3 B4,7 4 9,产量,销量,3 6 5 6,6,3,5,2,1,3,(0),(2),(2),(9),(1),(12),产地,销地,A1 A2 A3,B1 B1 B3 B4,7 4 9,产量,销量,3 6 5 6,6,3,3,1,2,25,4,(1),产地,销地,A1 A2 A3,B1 B2 B3 B4,产量,销量,6,3,2,2,3,3 6 6 5,6 5 9,(2),(1),(-1),(10),(12),例：,6,产地,销地,A1 A2 A3,B1 B2 B3 B4,产量,销量,6,3,0,3,3 6 6 5,6 5 9,2,26,练习,产地,销地,A1 A2 A3,B1 B2 B3 B4,产地,销地,A1 A2 A3,B1 B2 B3 B4,产量,销量,10 1 20 11 12 7 9 20 2 14 16 18,5 15 15 10,15 25 5,单位运价表,产销平衡表,27,最小元素法,产地,销地,A1 A2 A3,B1 B2 B3 B4,产地,销地,A1 A2 A3,B1 B2 B3 B4,产量,销量,10 1 20 11 12 7 9 20 2 14 16 18,5 15 15 10,15 25 5,单位运价表,产销平衡表,15,5,15,10,0,0,28,Vogel法,产地,销地,A1 A2 A3,B1 B2 B3 B4,产地,销地,A1 A2 A3,B1 B2 B3 B4,产量,销量,10 1 20 11 12 7 9 20 2 14 16 18,5 15 15 10,15 25 5,单位运价表,产销平衡表,8 6 7 7,9 2 12,5,-6 11 9,10 2-,15,-6-9,10 13-,10,5,10,0,29,注:表上作业法适用于下列情形：cij0；min z；产销平衡。,表上作业法步骤,30,3.3 几类特殊的运输问题,一、产销不平衡问题,1产销,2销产,二、需求量不确定,三、中转问题,31,Min z=cij xij,n,i=1,j=1,m,一、产销不平衡问题,1产销(aibj),Min z=cijxij+0 xi,n+1,n,i=1,j=1,m,i=1,m,32,产地,销地,A1 A2 Am,B1B2Bn,C11C12C1n C21C22C2n Cm1Cm2Cmn,Bn+1,产销问题单位运价表,销量,产量,b1b2bn,a1 a2 am,aibj,33,Min z=cij xij,n,i=1,j=1,m,2销产(bjai),Min z=cijxij+0 xm+1,j,n,i=1,j=1,m,j=1,n,34,产地,销地,A1 A2 Am,B1B2Bn,C11C12C1n C21C22C2n Cm1Cm2Cmn,Am+1,销产问题单位运价表,0 0 0,销量,产量,b1b2bn,a1 a2 am,bjai,35,例：有A、B、C三个化肥厂供应四个地区、的农用化肥，三个工厂每年各自的产量为A-50万吨，B-60万吨，C-50万吨。四个地区的需求量分别是地区最高50万吨，最低30万吨，地区为70万吨，地区为30万吨以下，地区不低于10万吨。问：如何调运，可使总的调运费用最小？单位调运费用如下表所示。,产地,销地,A,产量,最低需求,16 13 22 17 14 13 19 15 19 20 23,单位运价表,50 60 50,30 70 0 10,单位：万元/万吨,设 xij-第i工厂调至第j需求地区的化肥数量,二、需求量不确定,B,C,最高需求,50 70 30 不限,36,A B C,161613221717,141413191515,19192023 M M,M0M0M0,供应,需求,产量,销 量,50 60 50,302070301050,产销平衡表,D,50,注：M表示无穷大正数，最低需求不能由D生产地提供。,37,最优方案：,38,练习,产地,销地,A,最高发量,4 6 7-7 8,单位运价表,60 40 400,B,C,销量,70 80 50,D,最低发量,80 40 不限50,5 4 6 4 5-,39,三、中转问题,在前面的例题中，若既可以从Ai运到Bj，也可以经过中间站T1、T2、T3、T4或者Ai、Bj转运，称为扩大的运输问题。,几点说明：1.所有的产地、销地、中间站均视作产地、销地；2.不能出现循环倒运现象，允许自身往自身最多调运一次，运价为cii=0；3.转运量可定位总的产量之和；4.实际产地产量为转运量与该产地实际产量之和，实际销地销量为转运量与实际销量之和。,40,A1 A2 A3,T1 T2 T3 T4,B1 B2 B3 B4,A1 A2 A3,T1 T2 T3 T4,B1 B2 B3 B4,0 1 3 1 0-3-0,2 1 4 3 3 5-2 1-2 3,3 11 3 10 1 9 2 8 7 4 10 5,2 3 1 1 5-4-2 3 2 3,3 1 7 11 9 4 3 2 10 10 8 5,0 1 3 2 1 0 1 1 3 1 0 2 2 1 2 0,2 8 4 6 4 5 2 7 1 8 2 4 1-2 6,2 4 1 1 8 5 8-4 2 2 2 6 7 4 6,0 1 4 2 1 0 2 1 4 2 0 3 2 1 3 0,产,销,产量,销量,27 24 29,20 20 20 20,20 20 20 20,20 20 20,20 20 20 20,23 26 25 26,产销平衡表,41,3.4 运输问题的应用,42,例：某工厂按合同规定必须于当年的每个季度末分别提供10、15、25、20台同一规格的柴油机。已知该厂的生产能力及生产每台柴油机的成本如表示。又如果生产出来的柴油机当季不交货，每台每积压一个季度需要存储维护费用0.15万元。要求在完成合同的情况下，做出使全年生产费用最小的决策。,季度,生产能力,(台),单位成本,(万元/台),25353010,43,模型：设xij第i季度生产，用于第j季度交货的数量。,obj.min z=cij xij,i=1j=1,4 4,x11+x12+x13+x1425,x22+x23+x2435,x33+x3430,x4410,x11=10,x12+x22=15,x13+x23+x33=25,x14+x24+x34+x44=20,xij 0,(i=1,4;j=1,4),供应：,需求：,44,单位费用表：,10.8 10.9511.10 11.25,M 11.10 11.25 11.40,M M 11.00 11.15,M MM 11.30,单位：万元,供应,需求,45,例:某餐馆承办宴会，每晚连续举行，共举行五次。宴会上需用特殊的餐巾，根据参加的人数，预计每晚的需要量为：第一天1000条，第二天700条，第三天800条，第四天1200条，第五天1500条，五天之后，所有的餐巾作废。宴会中用过的餐巾经过洗涤处理后可以重复使用，这样可以降低使用成本。已知每条新餐巾需要1元的费用，送洗时可选择两种方式：快洗仅需要一天时间，每条洗涤费用为0.2元，慢洗需要两天时间，每条洗涤费用0.1元。问：如何安排，可使总费用最低？,46,建立模型：,设 xj第j天使用新毛巾的数量；yij第i天送第j天使用快洗 餐巾的数量；zij第i天送第j天使用慢洗餐巾的数量；,第一天：x1=1000,第二天：x2+y12=700,第三天：x3+z13+y23=800,第四天：x4+z14+z24+y34=1200,第五天：x5+z15+z25+z35+y45=1500,需求约束,供应约束,新购餐巾：x1+x2+x3+x4+x55200,第一天送洗：y12+z13+z14+z151000,第二天送洗：y23+z24+z25700,第三天送洗：y34+z35800,第四天送洗：y451200,xj0，yij0，zij0，（i=1,4；j=1,5）,Min z=xj+0.2yij+0.1zij,47,新 购 第一天第二天第三天第四天,111110,M0.20.10.10.10,MM0.20.10.10,MMM0.20.10,供应,需求,产量,销 量,5200 1000 700 800 1200,MMM0.20.10,1000700800120015003700,产销平衡表,48,第3章学习要求,掌握产销不平衡运输问题转化为产销平衡问题的处理办法；掌握运输问题在实践中的典型应用；,(1)了解产销平衡运输问题的数学模型及其特点；,(2)掌握运输问题的表上作业法，包括初始调运方案的确定、检验数的计算、运输方案的调整方法；,(3)掌握产销不平衡运输问题转化为产销平衡问题的处理办法；了解运输问题在实践中的典型应用。,