,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,Click to edit Master title style,运输问题求解,表上作业法,运输问题求解之表上作业法,1.,运输问题模型及其求解思路,2.,确定初始基本可行解,3.,最优性检验,4.,方案调整,2,1.,运输问题模型及其求解思路,运输问题：,研究把某种商品从若干个产地运至若干个销售地而使总运费最小的一类问题。,目标：,1,总运费最小,3,1.,运输问题模型及其求解思路,已知有,m,个产地,A,i,（,i,=1,2,，,，,m,）可供应某种物资，其供应量（产量）分别为,a,i,，有,n,个销地,B,j,（,j,=1,2,，,，,n,）其销量（需求量）分别为,b,j,，从,A,到,B,的单位物资运价为,c,ij,。,4,若设 代表从第,A,i,个产地到第,B,j,个销售地的调运量，在,产销平衡,的条件下（），要确定总运输费用最小的调运方案，可表示为如下的数学模型,s.t,.,(,i,=1,，,2,，,，,m,；,j,=1,，,2,，,，,n,),矩阵形式：,s.t,.,1.,运输问题模型及其求解思路,5,1 1 1,1 1 1,1 1 1,1 1 1,1 1 1,1 1 1,A=,m,行,n,行,1.,运输问题模型及其求解思路,系数矩阵,6,2,1.,运输问题模型及其求解思路,对于产销平衡的运输问题，,若产地为,m,个，销地为,n,个，,则 变量个数为,mn,个，,约束条件个数为,m+n,，,其中包含：总产量总销售,故线性无关的约束条件个数为,m+n-1,，,基本解中的基变量个数为,m+n-1,。,7,运输问题求解思路,表上作业法,由于运输规划系数矩阵的特殊性，如果直接使用线性规划单纯形法求解计算，则无法利用这些有利条件。,人们在分析运输规划系数矩阵特征的基础上建立了针对运输问题的,表上作业法,。,1.,运输问题模型及其求解思路,8,表上作业法是单纯形法在求解产销平衡的运输问题时的一种简化方法，其实质仍是单纯形法，所不同的只是完成各步采用的具体形式。,具体操作步骤如下：,（,1,）确定一个初始基本可行解：即在,mn,阶产销平衡表上给出,m+n-1,个数字格（,基变量,）；,（,2,）求各非基变量（空格）的检验数，即在表上计算空格的,检验数,。判别式否达到最优解。如果是最优解，则停止计算，否则进入下一步。,（,3,）确定换入变量和换出变量，找出新的基可行解。,（,4,）重复,(2),、,(3),直至得到最优解为止,。,1.,运输问题模型及其求解思路,9,2.,确定初始基本可行解,1,）最小元素法,基本思想：,就近供应,，按运价最小的优先调运原则确定初始方案，即从单位运价表中选择运价最小的开始确定调运关系，然后次小。若某行（列）的产量（销量）已满足，则把该行（列）的其他格划去。如此进行下去，一直到给出初始基可行解为止。,10,例如，某公司经营某种产品，该公司下设,A,、,B,、,C,三个生产厂，有甲、乙、丙、丁四个销售点。公司每天把三个工厂生产的产品分别运往四个销售点，各工厂到各销售点的路程不同，单位产品的运费不同。各工厂每日的产量、各销售点每日的销量，以及从各工厂到各销售点单位产品的运价如下表。问该公司如何调运产品，在满足各销售点需要的前提下，使,总运费最小,。,2.,确定初始基本可行解,11,s.t,2.,确定初始基本可行解,若设 代表从第,i,个产地到第,j,个销售地的运输量（,i=1,2,3,；,j=1,2,3,4),12,3,4,3,1,6,3,2.,确定初始基本可行解,Z=43+310+31+12+64+35=86,13,为保证基变量的个数有,m+n-1,个，,1,、每次填完数，只能划去一行或一列，只有最后一个格子例外。,2,、用最小元素法时，可能会出现基变量个数还差两个以上但只剩下一行或一列的情况，此时不能将剩下行或列按空格划掉，应在剩下的空格中标上,0,。（退化的基本可行解）,2.,确定初始基本可行解,注意：,14,3,5,3,0,6,3,2.,确定初始基本可行解,15,）伏格尔法,伏格尔法的基本思想：如果某一地的产品不能按最小运费就近供应，就考虑次小运费，两者间就有一个差额。差额越大，说明,费用增量,越大。因而对差额最大处，优先采用最小运费调运。,步骤：,分别计算表中各行和各列中,最小运费和次小运费的差 额,，并填入表中的最右列和最下行。,从行和列的差额中选出最大者，选择其所在行或列中的最小元素，按类似于最小元素法优先供应，划去相应的行或列。,对表中未划去的元素，重复，直到所有的行和列都划完为止。,2.,确定初始基本可行解,16,2.,确定初始基本可行解,0,1,1,2,5,1,3,17,2.,确定初始基本可行解,18,2.,确定初始基本可行解,19,2.,确定初始基本可行解,20,2.,确定初始基本可行解,21,2.,确定初始基本可行解,22,2.,确定初始基本可行解,Z=53+210+31+18+64+35=85,23,3.,最优性检验,检验数的意义：非基变量增加一个单位，使目标函数值增加的数量。,运输问题中目标函数值要求最小化，因此，当所有的检验数都,大于或等于零,时该调运方案就是最优方案；否则不是。,下面介绍两种计算检验数的方法：,24,1,、闭回路法,闭回路：在已给出基本解的运输表上，从一个非基变量出发，沿水平或竖直方向前进，只有碰到基变量，才能向右或向左转,90,o,(,当然也可以不改变方向）继续前进。,这样继续下去，总能回到出发的那个非基变量，由此路线形成的封闭曲线，叫闭回路。,3.,最优性检验,25,3.,最优性检验,若让,x,11,1,，则总运费变化：,31+23,1,。,11,=1,若让,x,31,1,，则总运费变化：,75+103+2-1,10,。,31,=10,26,3.,最优性检验,6,3,24,=-1,3,B,4,9,33,=12,6,31,=10,A,3,5,6,3,销量,4,1,22,=1,3,A,2,7,4,12,=2,A,1,产量,B,3,B,2,B,1,11,=1,最优标准：所有检验数,ij,0,27,2,、位势法,闭回路法的缺点：当变量个数较多时，寻找闭回路以及计算两方面都容易出错。,位势法检验步骤：,1,）设产地,A,i,对应的位势量为,u,i,，销地,B,j,对应的位势量为,v,j,；,2,）由,ij,=C,ij,-,（,U,i,+V,j,）,利用对基变量而言有,ij,=0,，,计算位势,U,i,，,V,j,，,即,C,ij,-,（,U,i,+V,j,）,=0,，令,U,1,=0,；,3,）再由,ij,=C,ij,-,（,U,i,+V,j,）,计算非基变量的检验数,ij,3.,最优性检验,28,u,1,u,2,u,3,v,1,v,2,v,3,v,4,0,10,3,-1,-5,2,9,3.,最优性检验,29,ij,=C,ij,-,（,U,i,+V,j,）,11,=C,11,-,（,U,1,+V,1,）,=3-(0+2)=1,12,=C,12,-,（,U,1,+V,2,）,=11-(0+9)=2,(1),(2),3.,最优性检验,30,3.,最优性检验,33,=12,11,=1,22,=1,31,=10,24,=-1,12,=2,当存在非基变量的检验数,ij,0,，说明现行方案为最优方案，否则目标成本还可以进一步减小。,31,3.,最优性检验,1,、闭回路法计算式：,ij,=(,闭回路上的奇数顶点运价之和,)-(,闭回路上的偶数顶点运价之和,),2,、位势法计算式：,ij,=c,ij,-u,i,v,j,当存在非基变量的检验数,ij,0,，说明现行方案为最优方案，否则目标成本还可以进一步减小。,32,4.,方案调整,闭回路调整法步骤：,1,、入基变量的确定：选负检验数中最小者,rk,，那么,x,rk,作为进基变量；（使总运费尽快减少）,2,、出基变量的确定：在进基变量,x,rk,的闭回路上，选取偶数顶点上调运量最小的值，将其对应的运量作为出基变量。（刚好有一个基变量出基，其它基变量都为正）,33,4.,方案调整,即求,=,Min,x,ij,闭回路上的偶数顶点的,x,ij,=,x,pq,。,那么确定,x,pq,为出基变量，,为调整量；,3,、换基调整：对闭回路的奇数顶点运量调整为：,x,ij,+,，对各偶数顶点运量调整为：,x,ij,-,，特别,x,pq,-,=0,，,x,pq,变为非基变量。,重复以上步骤，直到所有检验数均非负，即得到最优解。,34,4.,方案调整,最小检验数原则，确定进基变量,最小偶点原则，确定出基变量和调整量,+1,-1,+1,-1,35,四、方案调整,得到新的基变量：,x,13,=5,x,14,=2,x,21,=3,x,24,=1,x,32,=6,x,34,=3,。重新计算检验数。,（,1,）,（,2,）,（,2,）,（,1,）,（,9,）,（,12,）,36,四、方案调整,经过一次基变换，所有,ij,0,，已得到最优解：,x,13,=5,x,14,=2,x,21,=3,x,24,=1,x,32,=6,x,34,=3,，其它为,0,。,最优值：,f*=35+102+13+81+46+53=85,37,表上作业法计算中的相关问题,1.,无穷多最优解,当最优方案中存在某空格（非基变量）检验数为,0,时，则该运输问题一定有多重最优解。,2.,退化解,当运输问题的最优表中有数格（基变量）的运量为,0,，则出现退化。,1,）确定基本可行解中，出现同时需要划去一行和一列的情况，则需要在填写数格的行或列上，写上一个,0,数格。,2,）在闭回路中进行调整时，如同时有,t(t1),个最小数格时，则只有一个运量为,0,的数格必须出基，其余的必须补上（,t-1),个,0,数格。,38,产销不平衡运输问题,当产大于销：,s.t,.,(,i,=1,，,2,，,，,m,；,j,=1,，,2,，,，,n,),s.t,.,(,i,=1,，,2,，,，,m,；,j,=1,，,2,，,，,n+1,),39,产销不平衡运输问题,40,产销不平衡运输问题,当产小于销：,s.t,.,(,i,=1,，,2,，,，,m,；,j,=1,，,2,，,，,n,),s.t,.,(,i,=1,，,2,，,，,m+1,；,j,=1,，,2,，,，,n,),41,产销不平衡运输问题,42,海量,PPT,模板免费下载,Thank You!,