运输问题的表上作业法.pptx

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