运输问题的表上作业法ppt课件.ppt

第3章运输问题（TP）,2,学习目标,了解运输问题模型的特点。 掌握产销平衡运输问题的表上作业法。 学会产销不平衡运输问题的转化。 学习表上作业法在物流管理中的典型应用。,3 运输问题（TP）,3,3 运输问题（TP）,4,3.2 运输问题的表上作业法,3.2.1 产销平衡运输问题的表上作业法,利用表上作业法求解运输问题时，与单纯形法类似，首先要求出一个初始方案（即线性规划问题的初始基本可行解）。一般来讲这个方案不一定是最优的，因此需要给出一个判别准则，并对初始方案进行调整、改进。每进行一次调整，我们就得到一个新的方案（基本可行解），而这个新方案一般比前一个方案要合理些，也就是对应的目标函数z值比前一个方案要小些。经过若干次调整，我们就得到一个使目标函数达到最小值的方案最优方案（最优解），而这些过程都可在产销矩阵表（运输表）上进行，故称为表上作业法。 其实质是单纯形法,5,3.2 运输问题的表上作业法,3.2.1 产销平衡运输问题的表上作业法,6,例3.1 设有3个产煤基地A1、A2、A3，4个销煤基地B1、B2、B3、B4，产地的产量、销地的销量以及从各产地至各销地煤炭的单位运价列于表3.4中，试求出使总运费最低的煤炭调拨方案。,3.2 运输问题的表上作业法,3.2.1 产销平衡运输问题的表上作业法,7,（1）列出运输问题的产销矩阵表。,3.2 运输问题的表上作业法,3.2.1 产销平衡运输问题的表上作业法,8,其中：xij为产地Ai到销地Bj的运量（i=1,2,3；j1,2,3,4），而将Ai到Bj的单位运价cij用小型字写在每格的右上角，以便直观地制定和修改调运方案。 从表3.5的数据可知，例3.1是个满足产销平衡条件的产销平衡问题。（2）初始方案确定的方法最小元素法。最小元素法：就近供应，运价数小的尽可能优先分配。,3.2 运输问题的表上作业法,3.2.1 产销平衡运输问题的表上作业法,9,3.2 运输问题的表上作业法,3.2.1 产销平衡运输问题的表上作业法,10,这样，我们便得到这样问题的一个初始基本可行x11=0 x12=0 x13=4 x14=3 x21=3 x22=0 x23=1 x24=0 x31=0 x32=6 x33=0 x34=3它所对应的目标函数z值为z=30+110+34+103+13+90+21+80+70+46+100+53=86（万元）因此，在应用最小元素法确定初始方案时，必须注意以下两点。,3.2 运输问题的表上作业法,3.2.1 产销平衡运输问题的表上作业法,11,1.当选定最小元素（不妨假定为cst）后，如果发现该元素所在行的产地的产量as恰好等于它所在列的销地的销量bt（即as=bt），可在产销矩阵表上xst处填上一个数as，并画上圈。为了保证调运方案中画圈的数字为m+n1个，只能在s行的其他格子里都打上“”（或在t列的其他格子里都打上“”），不可以同时把s行和t列的其他格子里都打上“”。2.当最后只剩下一行（或一列）还存在没有填数和打“”的格子时，规定只允许填数，不允许打“”，其目的也是为了保证画圈数字的个数恰为m+n1个。3.在特殊情况下可填“0”并画上圈，这个“0”应与其他画圈的数字同样看待。（不限于最后一行或最后一列）。,3.2 运输问题的表上作业法,3.2.1 产销平衡运输问题的表上作业法,12,例在表3.7中，第一步最小元素为c31=1，在x31处填上数字min(13,19)=13，并在x11、x21处打上“”。,3.2 运输问题的表上作业法,3.2.1 产销平衡运输问题的表上作业法,13,3.2 运输问题的表上作业法,3.2.1 产销平衡运输问题的表上作业法,第二步的最小元素为c32=2，可在x32处填上数字min(6,6)=6，并在x12、x22处打上“”（或在x33、x34处打上“”），由上面的注意（1）可知，不能同时在x12、x22、x33、x34处都打上“”。 继续运用前面所述的方法，再经过两步计算，可得到表3.8。,14,3.2 运输问题的表上作业法,3.2.4 确定初始方案的其他方法,1. 西北角法,15,3.2 运输问题的表上作业法,3.2.4 确定初始方案的其他方法,2沃格尔法,16,3.2 运输问题的表上作业法,17,方法1：最小元素法 基本思想是就近供应，即从运价最小的地方开始供应（调运），然后次小，直到最后供完为止。,3,11,3,10,1,9,2,7,4,10,5,8,3,4,1,6,3,3,总的运输费(31)+(64) +(43) +(12)+(310)+(35)=86元,3.2 运输问题的表上作业法,18,元素差额法对最小元素法进行了改进，考虑到产地到销地的最小运价和次小运价之间的差额，如果差额很大，就选最小运价先调运，否则会增加总运费。例如下面两种运输方案。,15,5,10,总运费是z=108+52+151=105,最小元素法：,3.2 运输问题的表上作业法,5,15,10,后一种方案考虑到C11与C21之间的差额是82=6，如果不先调运x21，到后来就有可能x110，这样会使总运费增加较大，从而先调运x21，再是x22，其次是x12,总运费z=105+152+51=85,用元素差额法求得的基本可行解更接近最优解，所以也称为近似方案。,19,最小元素法基本步骤：在单位运价表中找出最小的运价cij,其对应的变量xij 优先赋值xij =min(ai ,bj ),使该行或列对应的供或求得到满足，在产销平衡表中填对应的供求数值，在单位运价表中划去该行或列，以示不需再予供应，在剩余的单位运价表中做同样的操作，直到单位运价表中所有的元素都被划去为止。,表上作业法要求：调运方案的数字格必须为m+n-1个，且有数字格不构成闭回路。一般用最小元素法给出的方案符合这要求。,3.2 运输问题的表上作业法,20,方法2：Vogel法1）从运价表中分别计算出各行和各列的最小运费和次最小运费的差额，并填入该表的最右列和最下行。,3,11,3,10,1,9,2,7,4,10,5,8,3.2 运输问题的表上作业法,21,3,11,3,10,1,9,2,7,4,10,5,8,5,2）再从差值最大的行或列中找出最小运价确定供需关系和供需数量。当产地或销地中有一方数量供应完毕或得到满足时，划去运价表中对应的行或列。重复1)和2)，直到找出初始解为至。,3.2 运输问题的表上作业法,22,7,1,1,3,5,2,1,5,3.2 运输问题的表上作业法,23,7,1,3,5,2,7,5,3,3.2 运输问题的表上作业法,24,1,1,3,5,1,5,3,6,3,1,2,该方案的总运费:(13)(46)(35)(210)(18)(35)85元,3.2 运输问题的表上作业法,25,Vogel基本步骤：对单位运价表中求出各行和各列的最小运费和次小运费的差额罚数从行罚数和列罚数中选取最大者，再在它所在的行或列中选取最小元素在产销平衡表中对应位置，仍按最小元素法的方法，填入可使该行或该列之一得到满足的数值在单位运价表中划去该行或列，以示不需再予供应在剩余的单位运价表中找出各行和各列的最小运费和次小运费的差额，直到单位运价表中所有的元素都被划去为止,注意的问题：当同时有两个差额最大时，选取运费较小的一个.,3.2 运输问题的表上作业法,26,（3）调运方案的检验闭回路法。（计算打“”处的检验数）从某一打“”处出发，沿水平方向或垂直方向前进,遇到合适“”的数字格可以旋转90度，继续前进,若最后能回到出发点,则所构成的回路为闭回路。 约定作为起始顶点的（打“”）为偶数次顶点，其它顶点（打“”）从1开始顺次排列，那麽，该“”检验数： =（闭回路上偶数次顶点运距或运价之和）-（闭回路上奇数次顶点运距或运价之和） 结论:在任何可行方案中,以空格(i,j)为一个顶点,其余顶点全是数字格的闭回路存在且唯一。,3.2 运输问题的表上作业法,3.2.1 产销平衡运输问题的表上作业法,min的非基变量检验数ij的经济意义: 在保持产销平衡的条件下,非基变量每增加一个单位运量而成为进基变量时引起目标函数值(总运费）的增量.,检验原理：利用检验数的经济意义,ij 0 表示总运费增加。,3.2 运输问题的表上作业法,作法:先从任意空格(i,j)处出发，作一闭回路给空格(i,j)一个单位的运量,调整闭回路上其余数字格的运量,使达到产销平衡.则闭回路上总运费的变化值等于空格(i,j)的检验数.当所有的检验数都为正时，则为最优解.,3.2 运输问题的表上作业法,(+1),(-1),(-1),(+1),3,3,1,2,经调运后，运费的变化值为：3-3+2-1=1，即空格( AI,B1)的检验数为1,依次求出所有空格（非基变量）的检验数，当检验数还存在负数时，说明原方案还不是最优解。,30,3.2 运输问题的表上作业法,3.2.1 产销平衡运输问题的表上作业法,31,3.2 运输问题的表上作业法,3.2.1 产销平衡运输问题的表上作业法,32,3.2.1 产销平衡运输问题的表上作业法,3.2 运输问题的表上作业法,33,利用闭回路法检验某调运方案是否最优，可按下列步骤进行。 求检验数。 （计算打“”处的检验数） 根据检验数进行判别（若全部大于等于零，则该方案就是最优调运方案，否则就应进行调整。）将所有打“”处的检验数填入表中，得到检验数表，如表3.12所示。,3.2 运输问题的表上作业法,3.2.1 产销平衡运输问题的表上作业法,34,当一个运输问题的产地和销地个数很多时，用这个方法计算检验数的工作十分繁重。 下面介绍一种简便的求检验数的方法位势法。 表3.23（同表3.6）给出了例3.1利用最小元素法确定的初始调运方案。 第一步是在表3.23中添加新的一列ui列（i的个数等于产地的个数）和新的一行vj行（j的个数等于销地的个数），如表3.24所示。,3.2 运输问题的表上作业法,3.2.3 利用位势法求检验数,35,3.2 运输问题的表上作业法,3.2.3 利用位势法求检验数,36,3.2 运输问题的表上作业法,3.2.3 利用位势法求检验数,表3.24中的ui和vj分别称为第i行和第j列的位势（i=1, 2,m；j=1,2,n），并规定它们与表中画圈数字所在的格对应的单位运价有如下关系：第二步是确定ui和vj的数值。由于ui与vj的数值相互之间是有关联的，所以只要任意给定其中的一个，则可根据关系式（3-3）很容易地将其他所有位势的数值求出。,37,3.2 运输问题的表上作业法,3.2.3 利用位势法求检验数,例如，在表3.24中，先令v1 = 1，则有u2 + v1 = 1 u2 = 0u2 + v3 = 2 v3 = 2u1 + v3 = 3 u1 = 1u1 + v4 = 10v4 = 9u3 + v4 = 5 u3 = 4 u3 + v2 = 4 v2 = 8 把这些数分别填入表3.24的ui列和vj行，得到表3.25。,38,3.2 运输问题的表上作业法,3.2.3 利用位势法求检验数,第三步是求出位势，可以根据下面的原理求“”处格子的检验数（即非基变量的检验数）。例3.3 对于表3.19所示的调运方案，利用位势法求检验数。解：（1）在表3.19中添加新的ui列和vj行得表3.26。（2）令u1=5，对于各个有圈数字所在格的单位运价，按照关系式cij=(ui+vj)，依次求出各位势值填入表3.26。,39,3.2 运输问题的表上作业法,3.2.3 利用位势法求检验数,（3）利用打“”处的单位运价，根据式（3-4），即可间接求得相应的检验数表，如表3.27所示。,40,第一步，求初始调运方案，采用最小元素法，保证有调运量的格子个数（基变量个数）等于m+n1。第二步，求检验数。第三步，调整。,3.2 运输问题的表上作业法,3.2.2 产销平衡运输问题的表上作业法步骤,41,当存在非基变量的检验数kl0且kl=minij时，做出过xkl处的闭回路。在最小负检验数所在的闭回路上，取奇次点（打“”）中运量最小的记为d。将d填在xkl处，并打“”，同时奇次点减调整量d，偶点加调整量d，得到新的方案。即闭回路上，奇数次顶点的调运量减去d，偶数次顶点（包括起始顶点）的调运量加上d；闭回路之外的变量调运量不变。,3.2 运输问题的表上作业法,3.2.2 产销平衡运输问题的表上作业法步骤,42,表上作业法,3,11,3,10,1,9,2,7,4,10,5,8,4,3,6,3,1,3,(),(),(),(),调整步骤为：在进基变量的闭回路中标有正号的变量加上调整量d，标有负号的变量减去调整量d，其余变量不变，得到一组新的基可行解。然后求所有非基变量的检验数重新检验。,1,2,5,3.2 运输问题的表上作业法,43,例3.2 某工地有3个高地A1、A2、A3和4个洼地B1、B2、B3、B4，希望用高地的土有计划地填平洼地。 设各个高地的出土量和各个洼地的填土量如表3.14所示，各个高地与各个洼地之间的距离如表3.15所示，试用表上作业法制定最合理的调运方案。,3.2 运输问题的表上作业法,3.2.2 产销平衡运输问题的表上作业法步骤,44,解：（1）将运量表与距离表合并为产销矩阵表，如表3.16所示。（2）用最小元素法求出初始调运方案，如表3.17所示。（3）利用闭回路法求得检验数表，如表3.18所示。,3.2 运输问题的表上作业法,3.2.2 产销平衡运输问题的表上作业法步骤,45,（4）在检验数表中，|21|较大，所以过调运方案（表3.17）的x21处作出它的闭回路，进行调整得到调运方案，如表3.19所示。,3.2 运输问题的表上作业法,3.2.2 产销平衡运输问题的表上作业法步骤,46,（5）求调运方案的检验数表，如表3.20所示。因为调运方案检验数表中的检验数有负数，必须进行调整。,3.2 运输问题的表上作业法,3.2.2 产销平衡运输问题的表上作业法步骤,47,（6）因为13=50，所以过调运方案（表3.19）的x13处作出它的闭回路，进行调整得到调运方案，如表3.21所示。,3.2 运输问题的表上作业法,3.2.2 产销平衡运输问题的表上作业法步骤,48,（7）再求出方案的检验数表，如表3.22所示。由于检验数全部为正数，所以调运方案为最优方案。,3.2 运输问题的表上作业法,3.2.2 产销平衡运输问题的表上作业法步骤,49,（8）目标函数值为: min z=2010+255+102+153+204+105=520（土方千米）,3.2 运输问题的表上作业法,3.2.2 产销平衡运输问题的表上作业法步骤,