运输问题的表上作业法

第3章运输问题（TP）2学习目标了解运输问题模型的特点。掌握产销平衡运输问题的表上作业法。学会产销不平衡运输问题的转化。学习表上作业法在物流管理中的典型应用。3运输问题（TP）3运输问题的模型3.1运输问题的表上作业法3.2产销不平衡的运输问题3.3运输问题的应用案例3.4运输问题的Excel处理3.53运输问题（TP）43.2运输问题的表上作业法3.2.1产销平衡运输问题的表上作业法利用表上作业法求解运输问题时，与单纯形法类似，首先要求出一个初始方案（即线性规划问题的初始基本可行解）。一般来讲这个方案不一定是最优的，因此需要给出一个判别准则，并对初始方案进行调整、改进。每进行一次调整，我们就得到一个新的方案（基本可行解），而这个新方案一般比前一个方案要合理些，也就是对应的目标函数z值比前一个方案要小些。经过若干次调整，我们就得到一个使目标函数达到最小值的方案—最优方案（最优解），而这些过程都可在产销矩阵表（运输表）上进行，故称为表上作业法。其实质是单纯形法5步骤描述方法第一步求初始基行可行解（初始调运方案）最小元素法、元素差额法、第二步求检验数并判断是否得到最优解当非基变量的检验数σij全都非负时得到最优解，若存在检验数σij0，说明还没有达到最优，转第三步。闭回路法和位势法第三步调整运量，即换基，选一个变量出基，对原运量进行调整得到新的基可行解，转入第二步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；j1,2,3,4），而将Ai到Bj的单位运价cij用小型字写在每格的右上角，以便直观地制定和修改调运方案。从表3.5的数据可知，例3.1是个满足产销平衡条件的产销平衡问题。（2）初始方案确定的方法—最小元素法。最小元素法：就近供应，运价数小的尽可能优先分配。3.2运输问题的表上作业法3.2.1产销平衡运输问题的表上作业法93.2运输问题的表上作业法3.2.1产销平衡运输问题的表上作业法10这样，我们便得到这样问题的一个初始基本可行x11=0x12=0x13=4x14=3x21=3x22=0x23=1x24=0x31=0x32=6x33=0x34=3它所对应的目标函数z值为z=3×0+11×0+3×4+10×3+1×3+9×0+2×1+8×0+7×0+4×6+10×0+5×3=86（万元）因此，在应用最小元素法确定初始方案时，必须注意以下两点。3.2运输问题的表上作业法3.2.1产销平衡运输问题的表上作业法111.当选定最小元素（不妨假定为cst）后，如果发现该元素所在行的产地的产量as恰好等于它所在列的销地的销量bt（即as=bt），可在产销矩阵表上xst处填上一个数as，并画上圈。为了保证调运方案中画圈的数字为m+n−1个，只能在s行的其他格子里都打上“×”（或在t列的其他格子里都打上“”），不可以同时把s行和t列的其他格子里都打上“×”。2.当最后只剩下一行（或一列）还存在没有填数和打“×”的格子时，规定只允许填数，不允许打“×”，其目的也是为了保证画圈数字的个数恰为m+n−1个。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产销平衡运输问题的表上作业法133.2运输问题的表上作业法3.2.1产销平衡运输问题的表上作业法第二步的最小元素为c32=2，可在x32处填上数字min(6,6)=6，并在x12、x22处打上“×”（或在x33、x34处打上“×”），由上面的注意（1）可知，不能同时在x12、x22、x33、x34处都打上“×”。继续运用前面所述的方法，再经过两步计算，可得到表3.8。143.2运输问题的表上作业法3.2.4确定初始方案的其他方法1.西北角法153.2运输问题的表上作业法3.2.4确定初始方案的其他方法2．沃格尔法16单位销地运价产地产量311310719284741059销量36564321BBBB321AAA3.2运输问题的表上作业法17方法1：最小元素法基本思想是就近供应，即从运价最小的地方开始供应（调运），然后次小，直到最后供完为止。B1B2B3B4产量A17A24A39销量3656311310192741058341633总的运输费＝(3×1)+(6×4)+(4×3)+(1×2)+(3×10)+(3×5)=86元3.2运输问题的表上作业法18元素差额法对最小元素法进行了改进，考虑到产地到销地的最小运价和次小运价之间的差额，如果差额很大，就选最小运价先调运，否则会增加总运费。例如下面两种运输方案。85102120151515510总运费是z=10×8+5×2+15×1=105最小元素法：3.2运输问题的表上作业法85102120151551510后一种方案考虑到C11与C21之间的差额是8－2=6，如果不先调运x21，到后来就有可能x11≠0，这样会使总运费增加较大，从而先调运x21，再是x22，其次是x12总运费z=10×5+15×2+5×1=85用元素差额法求得的基本可行解更接近最优解，所以也称为近似方案。19最小元素法基本步骤：1.在单位运价表中找出最小的运价cij,其对应的变量xij优先赋值xij=min(ai,bj),2.使该行或列对应的供或求得到满足，在产销平衡表中填对应的供求数值，3.在单位运价表中划去该行或列，以示不需再予供应，4.在剩余的单位运价表中做同样的操作，直到单位运价表中所有的元素都被划去为止。表上作业法要求：调运方案的数字格必须为m+n-1个，且有数字格不构成闭回路。一般用最小元素法给出的方案符合这要求。3.2运输问题的表上作业法20方法2：Vogel法1）从运价表中分别计算出各行和各列的最小运费和次最小运费的差额，并填入该表的最右列和最下行。B1B2B3B4产量行差额A177A241A391销量3656列差额25133113101927410583.2运输问题的表上作业法21B1B2B3B4产量行差额A177A241A391销量3656列差额251331131019274105852）再从差值最大的行或列中找出最小运价确定供需关系和供需数量。当产地或销地中有一方数量供应完毕或得到满足时，划去运价表中对应的行或列。重复1)和2)，直到找出初始解为至。3.2运输问题的表上作业法22单位销地运价产地产量行差额311310719284741059销量3656列差额4321BBBB321AAA71135215××3.2运输问题的表上作业法23单位销地运价产地产量行差额311310719284741059销量3656列差额4321BBBB321AAA7135275×××3×3.2运输问题的表上作业法24单位销地运价产地产量行差额311310719284741059销量3656列差额4321BBBB321AAA113515×××3×631××2该方案的总运费:(1×3)＋(4×6)＋(3×5)＋(2×10)＋(1×8)＋(3×5)＝85元3.2运输问题的表上作业法25Vogel基本步骤：1.对单位运价表中求出各行和各列的最小运费和次小运费的差额－－罚数2.从行罚数和列罚数中选取最大者，再在它所在的行或列中选取最小元素3.在产销平衡表中对应位置，仍按最小元素法的方法，填入可使该行或该列之一得到满足的数值4.在单位运价表中划去该行或列，以示不需再予供应5.在剩余的单位运价表中找出各行和各列的最小运费和次小运费的差额，直到单位运价表中所有的元素都被划去为止注意的问题：当同时有两个差额最大时，选取运费较小的一个.3.2运输问题的表上作业法26（3）调运方案的检验—闭回路法。（计算打“×”处的检验数）从某一打“×”处出发，沿水平方向或垂直方向前进,遇到合适“○”的数字格可以旋转90度，继续前进,若最后能回到出发点,则所构成的回路为闭回路。约定作为起始顶点的（打“×”）为偶数次顶点，其它顶点（打“○”）从1开始顺次排列，那麽，该“×”检验数：=（闭回路上偶数次顶点运距或运价之和）-（闭回路上奇数次顶点运距或运价之和）结论:在任何可行方案中,以空格(i,j)为一个顶点,其余顶点全是数字格的闭回路存在且唯一。3.2运输问题的表上作业法3.2.1产销平衡运输问题的表上作业法sijmin的非基变量检验数σij的经济意义:在保持产销平衡的条件下,非基变量每增加一个单位运量而成为进基变量时引起目标函数值(总运费）的增量.检验原理：利用检验数的经济意义σij0表示总运费还可以减少，σij0表示总运费增加。3.2运输问题的表上作业法作法:先从任意空格(i,j)处出发，作一闭回路给空格(i,j)一个单位的运量,调整闭回路上其余数字格的运量,使达到产销平衡.则闭回路上总运费的变化值等于空格(i,j)的检验数.当所有的检验数都为正时，则为最优解.3.2运输问题的表上作业法(+1)(-1)(-1)(+1)3312奇点偶点经调运后，运费的变化值为：3-3+2-1=1，即空格(AI,B1)的检验数为1依次求出所有空格（非基变量）的检验数，当检验数还存在负数时，说明原方案还不是最优解。303.2运输问题的表上作业法3.2.1产销平衡运输问题的表上作业法313.2运输问题的表上作业法3.2.1产销平衡运输问题的表上作业法323.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利用位势法求检验数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=10→v4=9u3+v4=5→u3=−4u3+v2=4→v2=8•把这些数分别填入表3.24的ui列和vj行，得到表3.25。383.2运输问题的表上作业法3.2.3利用位势法求检验数第三步是求出位势，可以根据下面的原理求“”处格子的检验数（即非基变量的检验数）。例3.3对于表3.19所示的调运方案Ⅱ，利用位势法求检验数。解：（1）在表3.19中添