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

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