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

1、本节主要内容:一、图上作业法一、图上作业法 在经济建立中，经常碰到物资调拨中的运输问题。例如 煤、钢材、粮食、木材等物资，在全国都有假设干消费基地，分别将这些物资调到各消费基地去，应如何制定调运方案，使总的运输费用最少？问题的提出: 运输问题的普通提法是：设某种物资有m个产地和n个销地。产地Ai的产量为 ；销地Bj的销量 。从第i个产地向第j个销地运输每单位物资的运价为Cij。 这就是由多个产地供应多个销地的单种类物资运输问题。问如何调运这些物资才干使总运费到达最小。), 2 , 1( miai ), 2 , 1( njbj 1、运输问题的普通提法单位运价表 1 。即运输问题的总产量等于其总销

2、量，这样的运输问题称为产销平衡的运输问题。 2 。即运输问题的总产量不等于总销量，这样的运输问题称为产销不平衡的运输问题。 njjmiiba11 njjmiiba11分两种情况来讨论： 假设用xij表示从Ai到Bj的运量，那么在产销平衡的条件下，要求得总运费最小的调运方案，数学模型为： 0, 2 , 1)13(, 2 , 1.min1111ijnjiijmijijminjijijxmiaxnjbxtsxcz2、运输问题的数学模型其中，ai和bj满足： 称为产销平衡条件。 njjmiiba11将约束方程式展开可得11112122111211112222 nnmmnmmmxxaxxaxxaxxxb

3、xxx212 nnmnnbxxxb约束方程式中共mn个变量，m+n个约束。行行行行nmAxxxxxxxxxmnmmnn 111111111111111111212222111211 上述模型是一个线性规划问题。但是其构造很特殊，上述模型是一个线性规划问题。但是其构造很特殊，特点如下：特点如下：1.变量多mn个，但构造简单。 技术系数矩阵 该系数矩阵中每列只需两个元素为1，其他的都为零。ijab2.m+n个约束中有一个是多余的由于其间含有一个平衡关系式 所以R(A)=m+n-1，即解的mn个变量中基变量为m+n-1个。二、图上作业法二、图上作业法 在运输中，假设运用同一种运输工具，那么运费的计算

4、往往仅与运送物资的多少及里程有关。因此，在求最正确的运输方案时，用吨公里作为度量的规范比用运费作为度量规范更加方便、适用。 在求解最正确运输方案时，用吨公里作为度量单位，还可以在曾经画出的交通图上进展，操作起来较为简单、方便、直观、快捷。 在铁路、公路等交通部门经常运用这种方法决策最优运输问题，这种方法被称为图上作业法。一编制交通图和流向图 交通图 反映发点产地与收地销地及交通线路及其间隔组成的图形。 发点用“表示，发出货物的数量记在“之内单位：吨 收地销地用“表示，收取货物的数量记在“之内单位：吨 两点之间的线路长度记在交通线路的旁边。1、交通图1、交通图2、流向图 流向图: 在交通图上表示

5、物资流向的图被称为流向图。在图中每个发点吨数全部运完，每个收点所需吨数均已满足。2、流向图发点发点A到收点到收点B的的运输量，用括号运输量，用括号括起。括起。2、流向图 关于流向图的一些规定 箭头必需表示物资运输的方向 流量写在箭头的旁边，加小括号。 流向不能直接跨越道路上的收点、发点、交叉点 任何一段弧上最多只能显示一条流向！即同一段弧上的多条流向必需合并。 除端点外，任何点都可以流进和流出 含有圈的流向图的补充规定 顺时针方向的流向必需画在圈的内侧，称为内圈流向 逆时针方向的流向必需画在圈的外侧，称为外圈流向内圈流向、外圈流向举例44426图：图：5-144426图：图：5-2二对流向图的

6、检验 在物资运输中，把某种物资从各发点调到各收点的调运方案是很多的，但我们的目的是找出吨公里数是最小的调运方案。这就要留意在调运中不要发生对物流运输和迂回运输，因此，我们在制定流向图时，就要防止它的出现。1不合理的景象1：对流 1对流：所谓对流就是在一段线路上有同一种物资出现相对运输景象往返运输同一段线路上，两各方向都有流向，如图4-4。 甲乙两地是一种对流景象。假设把流向图改成图4-5，就可以防止对流景象，从而可以节约运输量2010=200(吨公里)。201010(10)(20)乙甲图 5-3图 5-4201010(10)(10)乙甲(20)2不合理的景象2：迂回 2迂回：当收点与发点之间的

7、运输线路有两条或两条以上时即交通图成圈，假设运送的货物不是走最短线路，那么称这种运输为迂回运输。 注：当交通图成圈时，假设流向图中内圈流向的总长简称内圈长或外圈流向的总长简称外圈长超越整个圈长的一半就称为迂回运输。例如某物资流向图如图4-6、4-7所示。迂回运输的判别44426图：图：5-544426图：图：5-6显然：图显然：图5-5为迂回运输为迂回运输3、正规最优流向图 正规最优流向图：一个最优的调运方案，它的流向图必是无对流、无迂回的流向图，称这种流向图为正规流向图。 物资调运的图上作业法就是寻觅一个无对流、无迂回的正规流向图。 步骤如下： 作出一个无对流的初始可行方案； 检验有无迂回

8、假设无，终了；否那么，调整，直到最优。三、图上作业法的求解过程 1、无圈的交通图 2、有圈的交通图 方法：供需归邻站 【例1】求最优调运方案324786451A1A2B1B3B2A5A3A4B4 口诀：抓各端，各端供需归邻站 即：先满足端点的要求，逐渐向中间逼近，直至收点与发点得到全部满足为止。324786451A1A2B1B3B2A5A3A4B4342347310图图 4-8练一练答案 【例2】求最优调运方案454786454A1A2B1B3B2B5A38B42273463图图 4-9 第一步：变有圈为无圈。 方法：“丢边破圈。即丢掉一条边，破去一个圈。 留意：丢边时，往往是丢掉圈中长度最大

9、的边。如下图第一步： “丢边破圈454786454A1A2B1B3B2B5A38B42273463 第二步：在无圈的交通图上作流向图。 原那么：先外后内，先端点后中间点，要求每个边都有流向。当某条边无流向时，必需填上运输量为零的虚流向。454786454A1A2B1B3B2B5A38B4227346348 15328图图 4-10 第三步：补上丢掉的边，检查有无迂回。 圈B5B4B3A2的圈长=4+4+5+8=21,内圈长= 4+4+5=1321/2，有迂回，所以流向图不是最优流向图。需求调整。 第四步：对方案进展调整。 方法：找出有迂回圈的流量最小的边去掉的边除外，改此边为丢掉的边边B5B4

10、，并补上原来丢掉的边边B5A2，得到新的交通图。在此交通图上做新的流向图。454786454A1A2B1B3B2B5A38B4227346348 15126图图 4-11 第五步：对新方案进展检验。 圈B5B4B3A2的圈长=4+4+5+8=21,内圈长= 4+5=921/2，外圈长= 825/2，有迂回，所以流向图不是最优流向图。需求调整。 第六步：对方案进展调整。 方法：找出有迂回圈的流量最小的边去掉的边除外，改此边为丢掉的边边A1B3，并补上原来丢掉的边边B1A3，得到新的交通图。在此交通图上做新的流向图。454786454A1A2B1B3B2B5A38B422734633714226图

11、图 4-12 可验证：此方案中无迂回景象。即为最优方案。发收B1B2B3B4B5发货量A1347A24228A3145收货量44462练一练答案 运输问题依然是线性规划问题，可以用线性规划法中的单纯形法来处理。但是： 1.运输问题所涉及的变量多，呵斥单纯形表太大； 2.假设把技术系数矩阵A中的0迭代成非0，会使问题更加复杂。 以上两个缘由使得我们不得不利用运输问题的特点设计出它的特殊解法表上作业法。表上作业法，本质上还是单纯形法。其步骤如下：1.确定一个初始可行调运方案。可以经过最小元素法、西北角法、Vogel 法来完成；2.检验当前可行方案能否最优，常用的方法有闭回路法和位势法，用这两种方法

12、计算出检验数，从而判别方案能否最优；3.方案调整，从当前方案出发寻觅更好方案，常采用闭回路法。 例3 某公司从三个产地A1、A2、A3 将物品运往四个销地B1、B2、B3、B4，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表3-4所示 问应如何调运，可使得总运输费最小? 即初始根本可行解确实定，与普通线性规划即初始根本可行解确实定，与普通线性规划问题不同，产销平衡运输问题总是存在可行解。问题不同，产销平衡运输问题总是存在可行解。1、确定初始方案 确定初始根本可行解的方法很多，普通希望方法是既简便，又尽能够接近最优解。下面引见两种方法：最小元素法，西北角法、 Vogel 法1最

13、小元素法 最小元素法的根本思想是优先满足单位运价最小的供销业务。 首先找出运价最小的，并以最大限制满足其供销量为原那么确定供销业务。同样的方法反复进展直到确定了一切的供销业务，得到一个完好的调运方案即初始根本可行解为止。 销产A17311310A241928A3974105需求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个。空格是非基变量，共

14、划去m+n=7条线；假设填上一个变量之后能同时划去两条线一行与一列，就须在所划去的该行或该列填一个0，此0格当有数格对待。初始方案运费 Z0=31+64+43+12+310+35=86(元)2西北角法 西北角法与最小元素法不同，它不是优先思索具有最小单位运价的供销业务，而是优先满足运输表中西北角左上角上空格的供销需求。 销销产产A17311310A241928A3974105需求需求365620342236方案表运价表 例例4 某公司下属有消费一种化工产品的三个产地某公司下属有消费一种化工产品的三个产地A1、A2、A3 ，有四个销售点，有四个销售点B1、B2、B3、B4 销售这种化工产品。销售

15、这种化工产品。各产地的产量、各销地的销量和各产地运往各销地每吨产品各产地的产量、各销地的销量和各产地运往各销地每吨产品的运费百元如下表所示。的运费百元如下表所示。 销产A1753859A2402948A3806375需求35405565195 问应如何调运，可使得总运输费最小问应如何调运，可使得总运输费最小? 解：用西北角法求初始根本可行解解：用西北角法求初始根本可行解 销产A1753859A2402948A3806375需求35405565195方案表运价表35400401565(3)伏格尔法次小运价与最小运价之差大者先安排 销销产产A17311310A241928A3974105需求需求3

16、65620方案表运价表 2 5 1 3 01160123 2 1 2 3765122、判别当前方案能否为最优 用单纯形法解线性规划问题时，在迭代过程中每次求得一个根本可行解以后，都要检验它是不是最优解，假设不是最优解，就要继续进展迭代，直到求得最优解或者断定无最优解。 表上作业法是用以下两种方法来处置这个问题的：闭回路法和位势法。1闭回路法 在单纯形法中，为了检验一个根本可行解是不是最优解，需求求出一切非基变量的检验数。在运输问题中，每个空格对应一个非基变量。因此，我们需求求出每个空格的检验数。 由于目的要求极小，因此，当一切的检验数都大于或等于零时该调运方案就是最优方案。 B1B2B3B4A

17、143A231A363 对方案表中每一空格，确定一条由空格出发的闭回路。 闭回路是由程度或垂直线组成的闭合图形。闭回路上的顶点除了这个空格外，其他均为有数格。B1B2B3B4A143A231A363 可以证明，对每一个空格都存在而且独一存在这样一条封锁回路。B1B2B3B4A143A231A363B1B2B3B4A143A231A363B1B2B3B4A143A231A363B1B2B3B4A143A231A363计算出空格的检验数等于闭回路上由此空格起奇数顶点运价与偶数顶点运价负值的代数和。B1B2B3B4A143A231A363 11=3 - 3+2 - 1=1 11=3 - 3+2 -

18、1=1 22= 9-2+30+54 =1 22= 9-2+30+54 =1 31= 7-5+103+21=1031= 7-5+103+21=10 12=11 - 10+5 - 4=212=11 - 10+5 - 4=2 24= 810 +3 2 =-124= 810 +3 2 =-1 33=10 - 5+10 -3=1233=10 - 5+10 -3=12那么当前方案是最优的，假设尚有空格检验数小于零，阐明当前方案尚有待调整。 假设一切的空格检验数都大于等于零，阐明任何一个空格处调运1单位都会引起总本钱的上升，这阐明当前方案不能再改良，即定为最优方案。 ij 具有确切的经济意义，它表示由具有确

19、切的经济意义，它表示由Ai往往Bj增运增运1单单位时，引起的总运输本钱的变化数。位时，引起的总运输本钱的变化数。B1B2B3B4A143A231A363 闭回路法的主要缺陷是：当变量个数较多闭回路法的主要缺陷是：当变量个数较多时，寻觅闭回路以及计算都会产生困难。时，寻觅闭回路以及计算都会产生困难。2位势法对偶变量法 对于一个调运方案的每列赋予一个值，称为列位势，记 ，对于每行赋予一个值，称为行位势，记为 nvvv,21muuu,21ijjicvu 那么检验数为： ij = cij - ui - vj i = 1, , m ; j = 1, , n它们的值由以下方程组决议：其中， cij 是一切

20、基变量数字格xij 的运价系数 。 销销产产A17311310A241928A3974105需求需求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 =

21、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在有数格上填上相应的运价 销销产产A143A231A363方案表运价表 销销产产A1310A212A345u1u2u3

22、v1v3v2v4位势法在表上进展： (2) 设u1=0，然后根据cij=ui+vj 有数格，依次求得ui和vj的值，并填在相应的位置 销销产产A1310A212A345u1u2u3v1v3v2v4239100-1-5计算(ui+vj )表，把(ui+vj )位势和值填在表中相应位置上，并将有数格位置上的值ui+vj 加上括号以示区别。 2989-3-2(ui+vj )表 销销产产A1311310A21928A374105运价表 销销产产A129(3)(10)A2(1)8(2)9A3-3(4)-2(5)u1u2u3v1v3v2v4239100-1-5检验数表 销销产产A1A2A33计算检验数表ij = cij ( ui + vj)(ui+vj )表121-110123、调整方案 假设在检验数上有某空格的检验数为负，那么可改良方案，降低本钱。调整的方法是从具有负检验数的空格出发(有多个负检验数时，选择绝对值大的一个)，沿它的闭回路进展调整，即在坚持方案可行的条件下，尽量添加空格