运输问题的数学模型详细讲解,有案例多种方法.ppt

运输问题的数学模型,一、 运输问题及其数学模型 二、 图上作业法 三、 表上作业法,本节主要内容:,一、图上作业法,一、 运输问题及其数学模型,在经济建设中，经常碰到物资调拨中的运输问题。 例如 煤、钢材、粮食、木材等物资，在全国都有若干生产基地，分别将这些物资调到各消费基地去，应如何制定调运方案，使总的运输费用最少？,问题的提出:,运输问题的一般提法是：设某种物资有m个产地和n个销地。产地Ai的产量为 ；销地Bj的销量 。从第i个产地向第j个销地运输每单位物资的运价为Cij。 这就是由多个产地供应多个销地的单品种物资运输问题。问如何调运这些物资才能使总运费达到最小。,1、运输问题的一般提法,单位运价表,（1） 。即运输问题的总产量等于其总 销量，这样的运输问题称为产销平衡的运输问题。 （2） 。即运输问题的总产量不等于总 销量，这样的运输问题称为产销不平衡的运输问题。,分两种情况来讨论：,若用xij表示从Ai到Bj的运量，那么在产销平衡的条件下，要求得总运费最小的调运方案，数学模型为：,2、运输问题的数学模型,其中，ai和bj满足： 称为产销平衡条件。,将约束方程式展开可得,约束方程式中共mn个变量，m+n个约束。,上述模型是一个线性规划问题。但是其结构很特殊，特点如下：,1.变量多（mn个），但结构简单。,技术系数矩阵,该系数矩阵中每列只有两个元素为1，其余的都为零。,2.m+n个约束中有一个是多余的（因为其间含有一个平衡关系式 ） 所以R(A)=m+n-1，即解的mn个变量中基变量为m+n-1个。,二、图上作业法,在运输中，若使用同一种运输工具，则运费的计算往往仅与运送物资的多少及里程有关。因此，在求最佳的运输方案时，用吨公里作为度量的标准比用运费作为度量标准更加方便、实用。 在求解最佳运输方案时，用吨公里作为度量单位，还可以在已经画出的交通图上进行，操作起来较为简单、方便、直观、快捷。 在铁路、公路等交通部门经常使用这种方法决策最优运输问题，这种方法被称为图上作业法。,（一）编制交通图和流向图,交通图 反映发点（产地）与收地（销地）及交通线路及其距离组成的图形。 发点用“”表示，发出货物的数量记在“”之内（单位：吨） 收地（销地）用“”表示，收取货物的数量记在“”之内（单位：吨） 两点之间的线路长度记在交通线路的旁边。,1、交通图,1、交通图,2、流向图,流向图: 在交通图上表示物资流向的图被称为流向图。在图中每个发点吨数全部运完，每个收点所需吨数均已满足。,2、流向图,2、流向图,关于流向图的一些规定 箭头必须表示物资运输的方向 流量写在箭头的旁边，加小括号。 流向不能直接跨越路线上的收点、发点、交叉点 任何一段弧上最多只能显示一条流向！即同一段弧上的多条流向必须合并。 除端点外，任何点都可以流进和流出,2、流向图,2、流向图,含有圈的流向图的补充规定 顺时针方向的流向必须画在圈的内侧，称为内圈流向 逆时针方向的流向必须画在圈的外侧，称为外圈流向,内圈流向、外圈流向举例,（二）对流向图的检验,在物资运输中，把某种物资从各发点调到各收点的调运方案是很多的，但我们的目的是找出吨公里数是最小的调运方案。这就要注意在调运中不要发生对物流运输和迂回运输，因此，我们在制定流向图时，就要避免它的出现。,（1）不合理的现象1：对流,（1）对流：所谓对流就是在一段线路上有同一种物资出现相对运输现象（往返运输）（同一段线路上，两各方向都有流向），如图4-4。 甲乙两地是一种对流现象。如果把流向图改成图4-5，就可以避免对流现象，从而可以节约运输量2010=200(吨公里)。,（2）不合理的现象2：迂回,（2）迂回：当收点与发点之间的运输线路有两条或两条以上时（即交通图成圈），如果运送的货物不是走最短线路，则称这种运输为迂回运输。 注：当交通图成圈时，如果流向图中内圈流向的总长（简称内圈长）或外圈流向的总长（简称外圈长）超过整个圈长的一半就称为迂回运输。例如某物资流向图如图4-6、4-7所示。,迂回运输的判断,显然：图5-5为迂回运输,（3）、正规（最优）流向图,正规（最优）流向图：一个最优的调运方案，它的流向图必是无对流、无迂回的流向图，称这种流向图为正规流向图。 物资调运的图上作业法就是寻找一个无对流、无迂回的正规流向图。 步骤如下： 作出一个无对流的初始可行方案； 检验有无迂回 若无，结束； 否则，调整，直到最优。,三、图上作业法的求解过程,1、无圈的交通图 2、有圈的交通图 方法：供需归邻站,1、交通图无圈情形,【例1】求最优调运方案,案例分析,口诀：抓各端，各端供需归邻站 即：先满足端点的要求，逐步向中间逼近，直至收点与发点得到全部满足为止。,（3）,（4）,（2）,（3）,（4）,（7）,（3）,（10）,图 4-8,练一练,答案,2、交通图有圈情形,【例2】求最优调运方案,图 4-9,解题步骤：,第一步：变有圈为无圈。 方法：“丢边破圈”。即丢掉一条边，破去一个圈。 注意：丢边时，往往是丢掉圈中长度最大的边。如图所示,第一步： “丢边破圈”,第二步：在无圈的交通图上作流向图。 原则：先外后内，先端点后中间点，要求每个边都有流向。当某条边无流向时，必须填上运输量为零的虚流向。,第二步：作流向图,（4）,（8）,（1）,（5）,（3）,（2）,（8）,图 4-10,第三步：补上丢掉的边，检查有无迂回。 圈B5B4B3A2的圈长=4+4+5+8=21,内圈长= 4+4+5=1321/2，有迂回，所以流向图不是最优流向图。需要调整。,第四步：对方案进行调整。 方法：找出有迂回圈的流量最小的边（去掉的边除外），改此边为丢掉的边（边B5B4），并补上原来丢掉的边（边B5A2），得到新的交通图。在此交通图上做新的流向图。,第四步：调整方案,4,5,4,7,8,6,4,5,4,A1,A2,B1,B3,B2,B5,A3,8,B4,2,2,7,3,4,6,3,（4）,（8）,（1）,（5）,（1）,（2）,（6）,图 4-11,第五步：对新方案进行检验。 圈B5B4B3A2的圈长=4+4+5+8=21,内圈长= 4+5=925/2，有迂回，所以流向图不是最优流向图。需要调整。,第六步：对方案进行调整。 方法：找出有迂回圈的流量最小的边（去掉的边除外），改此边为丢掉的边（边A1B3），并补上原来丢掉的边（边B1A3），得到新的交通图。在此交通图上做新的流向图。,第六步：调整方案,4,5,4,7,8,6,4,5,4,A1,A2,B1,B3,B2,B5,A3,8,B4,2,2,7,3,4,6,3,（3）,（7）,（1）,（4）,（2）,（2）,（6）,图 4-12,可验证：此方案中无迂回现象。即为最优方案。,练一练,答案,二、 表上作业法,运输问题仍然是线性规划问题，可以用线性规划法中的单纯形法来解决。但是： 1.运输问题所涉及的变量多，造成单纯形表太大； 2.若把技术系数矩阵A中的0迭代成非0，会使问题更加复杂。 以上两个原因使得我们不得不利用运输问题的特点设计出它的特殊解法表上作业法。,表上作业法，实质上还是单纯形法。其步骤如下：,1.确定一个初始可行调运方案。可以通过最小元素法、西北角法、Vogel 法来完成； 2.检验当前可行方案是否最优，常用的方法有闭回路法和位势法，用这两种方法计算出检验数，从而判别方案是否最优； 3.方案调整，从当前方案出发寻找更好方案，常采用闭回路法。,二、表上作业法,例3 某公司从三个产地A1、A2、A3 将物品运往四个销地B1、B2、B3、B4，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表3-4所示,问应如何调运，可使得总运输费最小?,即初始基本可行解的确定，与一般线性规划问题不同，产销平衡运输问题总是存在可行解。,1、确定初始方案,确定初始基本可行解的方法很多，一般希望方法是既简便，又尽可能接近最优解。下面介绍两种方法：最小元素法，西北角法、 Vogel 法,（1）最小元素法,最小元素法的基本思想是优先满足单位运价最小的供销业务。 首先找出运价最小的，并以最大限度满足其供销量为原则确定供销业务。同样的方法反复进行直到确定了所有的供销业务，得到一个完整的调运方案即初始基本可行解为止。,1,3,2,1,3,4,4,6,5,3,10,3,方案表,运价表,以此，得到一初始方案： X13=4 , X14=3， X21=3，X23=1， X32=6， X34=3 （有数格） X11=X31=X12=X22=X33=X24=0（空格）,注： （）有数格是基变量，共m+n-1=3+4-1=6个。空格是非基变量，共划去m+n=7条线； （）如果填上一个变量之后能同时划去两条线（一行与一列），就须在所划去的该行或该列填一个0，此0格当有数格对待。,初始方案运费 Z0=31+64+43+12+310+35=86(元),（2）西北角法,西北角法与最小元素法不同，它不是优先考虑具有最小单位运价的供销业务，而是优先满足运输表中西北角（左上角）上空格的供销需求。,3,4,2,2,3,6,方案表,运价表,注：应用西北角法和最小元素法，每次填完数，都只划去一行或一列。 当填上一个数后行、列同时饱和时，也应任意划去一行(列)。在饱和的列（行）没被划去的格内标一个 0 , 然后划去该列（行）。,例4 某公司下属有生产一种化工产品的三个产地A1、A2、A3 ，有四个销售点B1、B2、B3、B4 销售这种化工产品。各产地的产量、各销地的销量和各产地运往各销地每吨产品的运费（百元）如下表所示。,问应如何调运，可使得总运输费最小?,解：用西北角法求初始基本可行解,方案表,运价表,35,40,0,40,15,65,(3)伏格尔法（次小运价与最小运价之差大者先安排）,方案表,运价表,2 5 1 3,0 1 1,6,0 1 2,3,2 1 2,3,7 6,5,1,2,2、判断当前方案是否为最优,用单纯形法解线性规划问题时，在迭代过程中每次求得一个基本可行解以后，都要检验它是不是最优解，如果不是最优解，就要继续进行迭代，直到求得最优解或者判定无最优解。 表上作业法是用以下两种方法来处理这个问题的：闭回路法和位势法。,（1）闭回路法,在单纯形法中，为了检验一个基本可行解是不是最优解，需要求出所有非基变量的检验数。在运输问题中，每个空格对应一个非基变量。因此，我们需要求出每个空格的检验数。 由于目标要求极小，因此，当所有的检验数都大于或等于零时该调运方案就是最优方案。,对方案表中每一空格，确定一条由空格出发的闭回路。 闭回路是由水平或垂直线组成的闭合图形。闭回路上的顶点除了这个空格外，其余均为有数格。,可以证明，对每一个空格都存在而且惟一存在这样一条封闭回路。,计算出空格的检验数等于闭回路上由此空格起奇数顶点运价与偶数顶点运价负值的代数和。,11=3 - 3+2 - 1=1 22= 9-2+30+54 =1 31= 7-5+103+21=10,12=11 - 10+5 - 4=2 24= 810 +3 2 =-1 33=10 - 5+10 -3=12,当所有空格检验数 ij 0,则当前方案是最优的，若尚有空格检验数小于零，表明当前方案尚有待调整。,若所有的空格检验数都大于等于零，表明任何一个空格处调运1单位都会引起总成本的上升，这表明当前方案不能再改进，即定为最优方案。, ij 具有确切的经济意义，它表示由Ai往Bj增运1单位时，引起的总运输成本的变化数。,闭回路法的主要缺点是：当变量个数较多时，寻找闭回路以及计算都会产生困难。,（2）位势法（对偶变量法）,对于一个调运方案的每列赋予一个值，称为列位势，记 ，对于每行赋予一个值，称为行位势，记为,则检验数为： ij = cij - ui - vj i = 1, , m ; j = 1, , n,它们的值由下列方程组决定： 其中， cij 是所有基变量（数字格）xij 的运价系数 。,1,3,2,1,3,4,4,6,5,3,10,3,方案表,运价表,u1 + v3 = c13 = 3 u2 + v1 = c21 = 1 u3 + v2 = c32 = 4,u1,u2,u3,v1,v3,v2,v4,u1 + v4 = c14 = 10 u2 + v3 = c23 = 2 u3 + v4 = c34 = 5,令u1 = 5 则有 v4 = 5,v3 = -2,u2 = 4,u3=0,v2=4,v1= -3,11 = c11 u1 - v1 = 3 5 (-3) = 1,12 = c12 u1 v2 = 11 5 4 = 2,22 = c22 u2 v2 = 9 4 4 = 1,24 = c24 u2 v4 = 8 4 5 = -1,31 = c31 u3 - v1 = 7 0 (-3) = 10,33 = c33 u3 v3 = 10 0 (-2) = 12,再求非基变量（空格）检验数：,u1 + v3 = c13 = 3 u2 + v1 = c21 = 1 u3 + v2 = c32 = 4,u1 + v4 = c14 = 10 u2 + v3 = c23 = 2 u3 + v4 = c34 = 5,（1）在有数格上填上相应的运价,方案表,运价表,u1,u2,u3,v1,v3,v2,v4,位势法在表上进行：,(2) 设u1=0，然后根据cij=ui+vj （有数格），依次求得ui和vj的值，并填在相应的位置,u1,u2,u3,v1,v3,v2,v4,2,3,9,10,0,-1,-5,计算(ui+vj )表，把(ui+vj )位势和值填在表中相应位置上，并将有数格位置上的值ui+vj 加上括号以示区别。,（ ）,（ ）,（ ）,（ ）,（ ）,（ ）,2,9,8,9,-3,-2,(ui+vj )表,运价表,u1,u2,u3,v1,v3,v2,v4,2,3,9,10,0,-1,-5,检验数表,（3）计算检验数表,ij = cij ( ui + vj),(ui+vj )表,1,2,1,-1,10,12,3、调整方案,若在检验数上有某空格的检验数为负，则可改进方案，降低成本。调整的方法是从具有负检验数的空格出发(有多个负检验数时，选择绝对值大的一个)，沿它的闭回路进行