运输问题(运筹学)ppt课件

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,运 筹 学,王 莉 莉,四川农业大学数学系,2012,年,10,月,运输问题(运筹学)ppt课件,1,学习目标,理解运输问题的特点；,掌握表上作业法；,掌握确定初始调运方案的方法；,掌握最优解的检验法,掌握调运方案的改进法,.,第四章,运输问题,学习目标第四章运输问题,2,引 言,在生产经营活动中，经常碰到大宗物质的调运问题,.,如煤炭、钢铁、木材、粮食等等物质，在全国有若干个生产基地，根据已有的交通网，应如何制定调运方案，将这些物质运到消费地点，而总运费要最小,.,引 言 在生产经营活动中，经常碰到大宗物质的调,3,运输问题的提法,m,个产地,A,i,输出某种货物，其量为,a,i,(,i,=1,，,2,，,，,m,).,n,个销地,B,j,，收到某种货物，其量为,b,j,(,j,=1,，,2,，,，,n,),.,从,A,i,到,B,j,单位货物运价为,C,ij,，问题是在尽量满足销地的需求时总运价最小,.,运输问题的提法,4,2,3,1,2,3,4,1,供求平衡的运输问题,B,1,=22,B,2,=13,B,3,=12,B,4,=13,A,2,=27,A,3,=19,A,1,=14,供应地,运价,需求地,6,7,5,3,4,8,2,7,5,9,10,6,供应量,需求量,总供应量,60,吨,总需求量,60,吨,供求平衡的运输问题,2312341供求平衡的运输问题B1=22B2=13B3=1,5,13,12,13,22,销量,19,6 /x,34,10 /x,33,9 /x,32,5 /x,31,A3,27,7 /x,24,2 /x,23,4 /x,22,8 /x,21,A2,14,3 /x,14,5 /x,13,7 /x,12,6,/x,11,A1,运量,B4,B3,B2,B1,销地,产地,单位 利润,供应地约束,需求地约束,13121322销量196 /x3410 /x339 /x3,6,运输问题约束条件系数矩阵特点,系数矩阵元素松散，只有,1,和,0,；,系数矩阵每列仅有两个,1,，其余均为,0,运输问题约束条件系数矩阵特点 系数矩阵元素松散，只有1和0；,7,运输问题,1,、平衡运输问题：总产量,=,总销量,2,、产大于销运输问题：总产量,总销量,3,、产小于销运输问题：总产量,总销量,运输问题1、平衡运输问题：总产量=总销量,8,平衡运输问题的数学模型,设,x,ij,表示从,A,i,到,B,j,的运量,平衡运输问题的数学模型设xij 表示从Ai 到Bj 的运量,9,产大于销运输问题的数学模型,设,x,ij,表示从,A,i,到,B,j,的运量,产大于销运输问题的数学模型设xij 表示从Ai 到Bj 的,10,产小于销运输问题的数学模型,设,x,ij,表示从,A,i,到,B,j,的运量,产小于销运输问题的数学模型设xij 表示从Ai 到Bj 的,11,产销,平衡问题,总产量等于总销量的运输问题,a,、建立运输表，,确定初始调运方案,b,、对该方案进行,最优性检验,，若是最优解，停止计算；否则转入下一步,c,、对非最优解进行调整,改进,(,也就是确定换入变量和换出变量,),，找到新的可行方案,d,、重复,b,、,c,步，直到找到最优解为止,.,解法,表上作业法,产销平衡问题总产量等于总销量的运输问题解法表上作业法,12,开始,画出运输表，确定初始调运方案,(,西北角法、最小元素法、沃格尔法,),最优解检验,(,闭回路法、位势法,),得到最优解,解的调整,(,闭回路法,),是,否,表上作业法的流程图,结束,开始画出运输表，确定初始调运方案最优解检验得到最优解解的调整,13,2,3,1,2,3,4,1,供求平衡的运输问题,B,1,=22,B,2,=13,B,3,=12,B,4,=13,A,2,=27,A,3,=19,A,1,=14,供应地,运价,需求地,6,7,5,3,4,8,2,7,5,9,10,6,供应量,需求量,总供应量,60,吨,总需求量,60,吨,供求平衡的运输问题,2312341供求平衡的运输问题B1=22B2=13B3=1,14,B,1,B,2,B,3,B,4,产,A,1,6,7,5,3,14,A,2,8,4,2,7,27,A,3,5,9,10,6,19,销,22,13,12,13,一、确定初始调运方案,根据已知条件，写出运输表,运价,调运量，当无调,运量时，填,B1B2B3B4产A1675314A2842727A3591,15,B,1,B,2,B,3,B,4,产,A,1,6,7,5,3,14,A,2,8,4,2,7,27,A,3,5,9,10,6,19,销,22,13,12,13,1,、西北角法,思路,：优先满足运输表上,西北角,(,左上角,),所在空格的供销需求,.,14,8,13,6,6,13,目标函数,z=614 +88 +413 +26 +106 +613=350 .,B1B2B3B4产A1675314A2842727A3591,16,B,1,B,2,B,3,B,4,产,A,1,6,7,5,3,14,A,2,8,4,2,7,27,A,3,5,9,10,6,19,销,22,13,12,13,2,、最小元素法,思路,：优先满足,最小单位运价,所在空格的供销需求,.,1,13,2,19,13,12,目标函数,z=61 +82 +519 +413 +212 +313=232 .,B1B2B3B4产A1675314A2842727A3591,17,3,、沃格尔法,思路,：首先计算每行和每列最小运价与次小运价之差，该数值称为,行罚数,和,列罚数,，其含义为若不能按照最小运价确定供求关系，就必须考虑次小运价，这样它们之间便产生运费的差额,.,差额越大说明如果不按照最小运价确定供求关系运输，而是按照次小运价由此所增加的运费越多，因而对差额最大处，应该采用最小运价调运,.,3、沃格尔法思路：首先计算每行和每列最小运价与次小运价之差，,18,B,1,B,2,B,3,B,4,产,行罚数,A,1,6,7,5,3,14,A,2,8,4,2,7,27,A,3,5,9,10,6,19,销,22,13,12,13,列罚数,3,、沃格尔法,2,1,13,2,1,3,3,3,B1B2B3B4产行罚数A1675314A2842727A3,19,B,1,B,2,B,3,B,4,产,行罚数,A,1,6,7,5,3,14,A,2,8,4,2,7,27,A,3,5,9,10,6,19,销,22,13,12,13,列罚数,3,、沃格尔法,5,1,13,2,1,3,3,3,12,B1B2B3B4产行罚数A1675314A2842727A3,20,B,1,B,2,B,3,B,4,产,行罚数,A,1,6,7,5,3,14,A,2,8,4,2,7,27,A,3,5,9,10,6,19,销,22,13,12,13,列罚数,3,、沃格尔法,1,1,13,3,1,3,3,3,12,13,19,1,2,目标函数,z=61 +82 +519,+413 +212 +313=232 .,B1B2B3B4产行罚数A1675314A2842727A3,21,通常来说，沃格尔法所得到的初始调运方案要比最小元素法所得到的优，最小元素法得到的初始调运方案又要比西北角法得到的优,.,通常来说，沃格尔法所得到的初始调运方案要比最小元素法所得到的,22,B,1,B,2,B,3,B,4,产,A,1,6,7,5,3,14,A,2,8,4,2,7,27,A,3,5,9,10,6,19,销,22,13,12,13,二、最优解检验,在运输表中,运价,调运量，当调运,量为零时，填,检验数,B1B2B3B4产A1675314A2842727A3591,23,二、最优解检验,最优解要求：所有格的检验数必须全部为非负,.,常用方法：,闭回路法,位势法,二、最优解检验最优解要求：所有格的检验数必须全部为非负.常,24,B,1,B,2,B,3,B,4,产,A,1,6,7,5,3,14,A,2,8,4,2,7,27,A,3,5,9,10,6,19,销,22,13,12,13,1,、闭回路法,思路,：以,格为起点和终点，由横线和竖线组成封闭多边形，除起点外，其余转折点必须为数字格,.,通过该回路来计算,格的检验数,.,14,8,6,13,6,13,B1B2B3B4产A1675314A2842727A3591,25,B,1,B,2,B,3,B,4,产,A,1,6,7,5,3,14,A,2,8,4,2,7,27,A,3,5,9,10,6,19,销,22,13,12,13,1,、闭回路法,14,8,6,13,6,13,运量：,x,12,每增加一个单位，,x,22,就减少一个单位,从而,x,21,增加一个单位，最后,x,11,减少一个单位,.,检验数,s,=7-4+8-6=50,，说明运量,x,12,不能增加，为最优,.,B1B2B3B4产A1675314A2842727A3591,26,B,1,B,2,B,3,B,4,产,A,1,6,7,5,3,14,A,2,8,4,2,7,27,A,3,5,9,10,6,19,销,22,13,12,13,1,、闭回路法,14,8,6,13,6,13,5,检验数,s,=5-2+8-6=50,，说明运量,x,13,不能增加，为最优,.,运量：,x,13,每增加一个单位，,x,23,就减少一个单位,从而,x,21,增加一个单位，最后,x,11,减少一个单位,.,B1B2B3B4产A1675314A2842727A3591,27,B,1,B,2,B,3,B,4,产,A,1,6,7,5,3,14,A,2,8,4,2,7,27,A,3,5,9,10,6,19,销,22,13,12,13,1,、闭回路法,14,8,6,13,6,13,5,检验数,s,=3-6+10-2+8-6=70,，说明运量,x,14,不能增加，为最优,.,5,B1B2B3B4产A1675314A2842727A3591,28,B,1,B,2,B,3,B,4,产,A,1,6,7,5,3,14,A,2,8,4,2,7,27,A,3,5,9,10,6,19,销,22,13,12,13,1,、闭回路法,14,8,6,13,6,13,5,检验数,s,=7-6+10-2=90,，说明运量,x,24,不能增加，为最优,.,5,7,B1B2B3B4产A1675314A2842727A3591,29,B,1,B,2,B,3,B,4,产,A,1,6,7,5,3,14,A,2,8,4,2,7,27,A,3,5,9,10,6,19,销,22,13,12,13,1,、闭回路法,14,8,6,13,6,13,5,检验数,s,=9-4+2-10=-30,，说明运量,x,32,可以增加，从而非最优,.,5,7,9,B1B2B3B4产A1675314A2842727A3591,30,B,1,B,2,B,3,B,4,产,A,1,6,7,5,3,14,A,2,8,4,2,7,27,A,3,5,9,10,6,19,销,22,13,12,13,1,、闭回路法,14,8,6,13,6,13,5,检验数,s,=5-8+2-10=-110,，说明运量,x,31,可以增加，从而非最优,.,5,7,9,-3,B1B2B3B4产A1675314A2842727A3591,31,B,1,B,2,B,3,B,4,产,A,1,6,7,5,3,14,A,2,8,4,2,7,27,A,3,5,9,10,6,19,销,22,13,12,13,1,、闭回路法,14,8,6,13,6,13,5,由于存在检验数小于零，说明此运输方案非最优，需改进,.,5,7,9,-3,-11,B1B2B3B4产A1675314A2842727A3591,32,B,1,B,2,B,3,B,4,产,u,i,A,1,6,7,5,3,14,A,2,8,4,2,7,27,A,3,5,9,10,6,19,销,22,13,12,13,v,j,2,、位势法,s,ij,= c,ij,- u,i,- v,j,14,8,6,13,6,13,数字格的检验数,s,为,0,B1B2B3B4产uiA1675314A2842727A35,33,B,1,B,2,B,3,B,4,产,u,i,A,1,6,7,5,3,14,A,2,8,4,2,7,27,A,3,5,9,10,6,19,销,22,13,12,13,v,j,2,、位势法,14,8,6,13,6,13,0,2,s,ij,= c,ij,- u,i,- v,j,0,- 4,2,10,6,令,u,1,=,0,B1B2B3B4产uiA1675314A2842727A35,34,B,1,B,2,B,3,B,4,产,u,i,A,1,6,7,5,3,14,A,2,8,4,2,7,27,A,3,5,9,10,6,19,销,22,13,12,13,v,j,2,、位势法,14,8,6,13,6,13,0,2,0,- 4,2,10,6,5,5,7,9,-3,-11,B1B2B3B4产uiA1675314A2842727A35,35,B,1,B,2,B,3,B,4,产,u,i,A,1,6,7,5,3,14,A,2,8,4,2,7,27,A,3,5,9,10,6,19,销,22,13,12,13,v,j,2,、位势法,14,8,6,13,6,13,0,2,0,- 4,2,10,6,5,5,7,9,-3,-11,由于存在检验数小于零，说明此运输方案非最优，需改进,.,B1B2B3B4产uiA1675314A2842727A35,36,三、解的改进,若格的检验数存在负数，说明当前调运方案不是最优解，需要进行改进,.,若格的检验数存在一个以上的检验数为负，一般应选取其中,检验数最小,的所在空格进行调整,.,调整方法：,闭回路法,三、解的改进 若格的检验数存在负数，说明当前调,37,B,1,B,2,B,3,B,4,产,A,1,6,7,5,3,14,A,2,8,4,2,7,27,A,3,5,9,10,6,19,销,22,13,12,13,步骤,14,8,6,13,6,13,5,(1),以该,格为出发点，做一闭回路,.,5,7,9,-3,-11,B1B2B3B4产A1675314A2842727A3591,38,B,1,B,2,B,3,B,4,产,A,1,6,7,5,3,14,A,2,8,4,2,7,27,A,3,5,9,10,6,19,销,22,13,12,13,步骤,14,8,6,13,6,13,5,(2),以,格不在的对角线上最小运量作为调整量，,格的运量增加调整量，其余各顶点的运量对应改变,.,5,7,9,-3,-11,6,2,12,0,B1B2B3B4产A1675314A2842727A3591,39,B,1,B,2,B,3,B,4,产,A,1,6,7,5,3,14,A,2,8,4,2,7,27,A,3,5,9,10,6,19,销,22,13,12,13,步骤,14,13,13,6,2,12,0,(2),以,格不在的对角线上最小运量作为调整量，,格的运量增加调整量，其余各顶点的运量对应改变,.,B1B2B3B4产A1675314A2842727A3591,40,B,1,B,2,B,3,B,4,产,u,i,A,1,6,7,5,3,14,A,2,8,4,2,7,27,A,3,5,9,10,6,19,销,22,13,12,13,v,j,14,2,13,12,6,13,0,2,s,ij,= c,ij,- u,i,- v,j,0,7,2,-1,6,令,u,1,=,0,步骤,(3),继续计算调整后所有空格的检验数，若均非负，则已经得到最优解，否则返回步骤,(1).,B1B2B3B4产uiA1675314A2842727A35,41,B,1,B,2,B,3,B,4,产,u,i,A,1,6,7,5,3,14,A,2,8,4,2,7,27,A,3,5,9,10,6,19,销,22,13,12,13,v,j,14,2,13,12,6,13,0,2,s,ij,= c,ij,- u,i,- v,j,0,7,2,-1,6,令,u,1,=,0,步骤,5,5,-4,-2,8,11,由于存在小于零的检验数，故此方案也非最优方案，还需进一步调整,.,再次进入步骤,(1),检验,.,B1B2B3B4产uiA1675314A2842727A35,42,B,1,B,2,B,3,B,4,产,A,1,6,7,5,3,14,A,2,8,4,2,7,27,A,3,5,9,10,6,19,销,22,13,12,13,14,13,13,6,2,12,13,0,19,1,步骤,B1B2B3B4产A1675314A2842727A3591,43,B,1,B,2,B,3,B,4,产,A,1,6,7,5,3,14,A,2,8,4,2,7,27,A,3,5,9,10,6,19,销,22,13,12,13,又得到新的调整方案，重新检验,.,1,13,2,19,13,12,B1B2B3B4产A1675314A2842727A3591,44,B,1,B,2,B,3,B,4,产,u,i,A,1,6,7,5,3,14,A,2,8,4,2,7,27,A,3,5,9,10,6,19,销,22,13,12,13,v,j,1,13,2,13,12,19,0,2,s,ij,= c,ij,- u,i,- v,j,0,3,2,-1,6,令,u,1,=,0,B1B2B3B4产uiA1675314A2842727A35,45,B,1,B,2,B,3,B,4,产,u,i,A,1,6,7,5,3,14,A,2,8,4,2,7,27,A,3,5,9,10,6,19,销,22,13,12,13,v,j,1,2,13,12,19,13,0,2,s,ij,= c,ij,- u,i,- v,j,0,3,2,-1,6,步骤,5,5,2,8,11,4,由于此时所有的检验数都大于,0,，则此时目标函数值最小,Min z=61 +82 +519 +413 +212 +313=232 .,B1B2B3B4产uiA1675314A2842727A35,46,表上作业法计算中的问题,无穷多最优解,在进行检验时，若某格检验数为零，说明该运输问题有无穷多最优解,.,退化问题,1,、在确定初始调运方案时，当在某空格填入一运量后，出现对应产地的产量和销地的销量同时得到满足；,2,、在用闭回路法进行解的改进时，,格不在的对角线上有多于一个数字格变为空格,.,表上作业法计算中的问题无穷多最优解,47,产销不平衡运输问题,产大于销,考虑增加一个假想的销地，使得产销平衡,.,同时由于该销地实际不存在，故运价为零,.,然后采用表上作业法计算,.,产销不平衡运输问题产大于销 考虑增加一个假想,48,产销不平衡运输问题,产小于销,考虑增加一个假想的产地，使得产销平衡,.,同时由于该产地实际不存在，故运价为零,.,然后采用表上作业法计算,.,产销不平衡运输问题产小于销 考虑增加一个假想,49,有转运的运输问题,在上面所讨论的问题中，我们都假定物品是由产地直接运送到销地的，没有经过任何中间转运,.,然而，在实际当中常常会遇到一种情形：需要先将物品由产地运到某个中间转运站（可能是另外的产地、销地或中间转运仓库），然后再转运到目的地,.,有时，可能经过转运比直接运到目的地更加经济,.,因此，在决定运输方案时有必要把转运也考虑进去,.,这样，将使运输问题更加复杂,.,有转运的运输问题 在上面所讨论的问题中，我们都假,50,