经济应用数学教案3.2.3

3.2.3 运输问题数学模型教学目的：熟练掌握运输问题的表上作业法，掌握图上作业法。

内 容：1. 表上作业法2. 图上作业法教学重点：表上作业法、图上作业法 教学难点：表上作业法 教 具：多媒体课件教学方法：启发式教学，精讲多练 教学过程： 1.引入新课：由研究配送、运输管理及物资调运等问题引出运输问题数学模型，并给出解决运输问题数学模型的方法：表上作业法与图上作业法。

2.教学内容：一、表上作业法【例1】设某种物资有A 1、A 2、A 3三个产地和B 1、B 2、B 3、 B 4四个销地，各产地的产量分别为25吨、25吨和80吨，各销地的销量分别为45吨、20吨、30吨和35吨。

由各产地到各销地的单位运价见表1。

问如何安排供应才能使得总运费最省（最优调运方案）？解 设ij x 表示由产地i A 运往销地j B 物质数量（1,2,3;1,2,3,4i j ==），即供应数量，S 为总运费。

由题意可得运输问题的数学模型为：111234111213142122232431323334112131122232132333142434min 85925258045..2030350(1,2,3;1,2,3,4)ijS x x x x x x x x x x x x x x x x x x s t x x x x x x x x x x i j =++++++=⎧⎪+++=⎪⎪+++=⎪++=⎪⎨++=⎪⎪++=⎪++=⎪⎪≥==⎩ 约束条件实际上只有6个独立的方程。

此问题有3416+-=个基变量，其它是非基变量。

一般地，如果一个运输问题有 m 个产地，n 个销地，则该运输问题的数学模型可表示为：1111min (1,2,,)..(1,2,,)0(1,2,,;1,2,,)mnij iji j nij i j m ij j i ij S c x x a i m s t x b j n x i m j n =====⎧==⎪⎪⎪==⎨⎪⎪≥==⎪⎩∑∑∑∑其中，ij x 表示第i 个产地运往第j 个销地的运输量；ij c 表示第i 个产地运往第j 个销地的单位运价；S 表示总运费；i a 是第i 个产地的产量；j b 是第j 个销地的销量。

表上作业法具体过程如下： （1）确定初始调运方案最小元素法：在运价表中，选在产销地之间运价最小者优先安排，使需要得到最大限度的满足的方法。

最小元素的具体步骤：首先在表1中找出一个最小的运价222c =，考虑2A 与2B 之间的调运，由于222225,20,A B A B ==>，所以可以让2A 满足2B 的需要，令2220x =，将○20填入表3-29内，2A 剩下的5吨另作安排，因为2B 已供应完，在2B 列12x 32,x 格内划⨯，表示1A 、3A 产地不再供应2B 销地。

其次在剩下的运价表（除去划⨯及划圈标数字元素）中找最小运价334c =，考虑3A 与3B 之间的调运，3A 保证供应3B ，令3330x =，在表中填入○30，在3B 列13x 23,x 格内划⨯，见表2。

再在剩下的运价表中找最小运价24，因为A 2还剩5吨，而B 4需要35吨，所以把A 2所剩5吨全部调运给B 4，令245x =，在表中填入○5，这时A 2的产量已经全部运出，再不能向别处调运，在A 2行的21x 格内划×。

同样，再在剩下的运价表中找最小运价147c =，将A 1的25吨全部调运给4B ，令1425x =，在表中填入○25，在A 1行的11x 格内划×。

由于4B 的销量是35吨，现在有由A 1供应的25吨，由A 2供应的5吨，剩下的5吨应由A 3供应，令345x =，将⑤填入表内，1B 的销量为45吨，完全由A 3供应，令3145x =，将○45填入表中，这时，在运价表上就得到一个调运的初始方案，见表3。

总运费（2）最优方案的判定用最小元素法确定的初始方案，不一定是最优方案，必须加以检验。

在这里我们采用闭回路法来判定一个方案是否最优。

闭回路法依赖于运价表和初始调运方案，画出所有空格的闭回路，然后根据闭回路求出每个空格的检验数。

其步骤如下：①画出空格闭回路。

空格是指没有调运数量的格。

空格闭回路的画法是：在初始调运方案中，从空格出发用垂直和水平的线段作出闭回路。

它的转角点（指闭回路顶点）除空格出发点外，必须是填有调运数量的格（以下称数字格）。

在画闭回路时，线段可以交叉，也可以穿过数字格。

可以证明，只要数字格数等于m +n -1，每一个空格所对应的闭回路就是存在的而且是唯一的。

在表3-30中，空格11x 的闭回路是：1114343111x x x x x →→→→空格12x 的闭回路是：1214242212x x x x x →→→→ 空格13x 的闭回路是：1314343313x x x x x →→→→ 空格21x 的闭回路是：2124343321x x x x x →→→→ 空格23x 的闭回路是：2324343323x x x x x →→→→ 空格32x 的闭回路是：3234242232x x x x x →→→→②求空格的检验数。

检验数的求法是：由空格出发沿闭回路前进，给空格和各转角顶点依次标记序号为0，1，2…，将奇顶点的运价都加上负号，偶顶点的运价都加上正号，这些正负数的代数和称为空格检验数。

通常把空格ij x 检验数记作ij λ。

如果所有空格的检验数ij λ都非负，则对应的调运方案就是最优方案，这一法则叫最优方案的判定法则。

在表3-30中，1187991λ=-+-= 1257622λ=-+-= 1367944λ=-+-= 21106994λ=-+-= 2376946λ=-+-= 3239622λ=-+-=-由于检验数3220λ=-<，所以该方案不是最优方案。

判断方案是否为最优方案，就是看检验数中是否有负数。

因此，我们只要在在调运表中逐格检查，遇到一个空格就求与它相对应的检验数，一旦发现有负的检验数，就立即进行调整，其余空格的检验数就不用再求了。

（3）方案的调整对于运输问题，最优解总是存在的。

如果初始调运方案不是最优的，我们可以在原方案的基础上进行调整。

首先在表3-31中找出对就于负检验数32λ的空格32x 及这个空格的闭回路，见表4。

在表4中，把空格32所对应的非基变量改为基变量，使这一非基变量的值由零增大到一适当的数值，为保持平衡，同时还必须使改变后的基变量不出现负数，因此非基变量增大的数值（称为调整数），必须是闭回路中第奇次拐角中最小的调运量。

然后把32x 的闭回路第奇次拐角点的调运量都减去这个调整数，偶拐角点的调运量都加上这个调整数。

在本例中，取min(5,20)5θ==为调整数，调整后的运量见表5。

上等于检验数-2与调整数5的乘积，即调整后运费降低量ij λθ=⨯。

这样每次调整后运费能降低多少，我们都能预先知道。

表5对应的是不是最优方案，还需进行判定，经检验1187623910λ=-+-+-=-<，该方案仍不是最优方案，应当继续调整。

找出11λ对应的空格及这个空格的闭回路，见表6。

这个方案的总运费为815710625930320430790S =⨯+⨯+⨯+⨯+⨯+⨯=(元)。

这个方案是否最优，仍需检验，其检验数为： 1258933λ=-+-=1368943λ=-+-= 21108763λ=-+-=222678931λ=-+-+-= 237678945λ=-+-+-= 3497891λ=-+-=由于检验数均大于零，所以该方案是最优方案，其最小运费790S =元。

表上作业法求解运输运输问题的步骤： Ⅰ. 用最小元素法编制出初始调运方案；Ⅱ. 用闭回路法逐一求出所有空格的检验数λ（只要判定正、负号即可）。

如果所有的检验数都非负，就得到最优方案，计算可以终止；Ⅲ. 一经发现负的检验数就进行调整，得到新的调运方案；Ⅳ. 对新的调运方案，重复Ⅱ、Ⅲ两步，直到所有检验数都非负，这时所得方案为最优方案。

注意：①在用最小元素法编制初始调运方案或用闭合回路法调整调运方案时，必须始终保持m+n -1个基变量。

②遇到不平衡运输问题时，通常总是把它转化为平衡运输问题来解决。

【例2】设某商品有三个产地和四个销地，它们的产量和销量及单位运价见表8。

问应如何安排供应，才能使总运费最省？现虚设一个销地（或增加一个库存，库存为4吨），同时在运价表上增加一列，因为库存不需要运费，所以这一列的运价都填上零，如表9。

这里要注意，在利用最小元素法编制初始调运方案时，不考虑库存一列，然后逐次取最小运价进行编制，得初始调运方案，见表10。

224333142335S =⨯+⨯+⨯+⨯+⨯=（元）。

由表3-38可以看出，多余的4吨物资应库存在A 1、A 2两地各2吨，然后进行平衡物质调运才能使总运费最少。

二、图上作业法求解运输问题，直接在交通图上作流向图，编制并确定最优方案，这种方法称为图上作业法。

1．基本概念定义1 在运输问题中，调出物资的地点称为发点。

用“○”表示，调出物资的数量称为发量（单位：吨），记在“○”内；调入物资的地点称为收点，用“□”表示，调入物资的数量称为收量（单位：吨），记在“□”内。

运输路线用“—”表示，称为交通线。

如果把收发点、收发量和连接它们之间的交通线画出来，并在交通线旁边标上距离（单位：公里）就得到交通图。

交通图有多种多样，但一般可分为交通图不成圈、交通图成圈两种情况，分别如图1、图2所示。

定义2 物资的调运方向称为流向，用“→”表示，模仿交通法规，画在前进方向交通线的右侧。

流向经过的距离称为流向长。

调运物资的数量称为流量，记在“→”的右侧，并加括号“（）”（与交通线旁的距离区别开），把标有流向和流量的交通图称为流向图。

如图3所示的流向图，表示A2B1上的流量为5吨，流向长为2+3=5公里；流向A1B2上的流量为10吨，流向长为3+5=8公里。

A1、A2是发点，发量为10+5=15吨；B1、B2是收点，收量为5+10=15吨。

在物资调运过程中，把某种物资从各个发点调运到各个收点，调运方案可以很多，问题是如何去找使运输量（吨·公理）最小的调运方案。

这就必须要避免物资调运中的对流和迂回两种不合理的运输现象。

定义3 同一种物资在同一条交通线上，如果存在往返运输，则称其为对流。

对流现象是物资调运中的不合理现象，是浪费运输力的现象。

在图3中，把A 2点的5吨物资运到B 1点，A 1点的10吨物资运到B 2点，那么就在A 1、A 2之间 这一段交通线上形成了对流。

在流向图上消灭对流是很容易做到的。

把A 1点的10吨物资运给B 1点5吨，余下的5吨运给A 2 点，以满足B 2点对10吨物资的需求，这样得到流向图4注意 定义4 在交通图成圈时，按照画流向图的规定，有的流向在图的圈内，称为内圈流向；有的流向在图的圈外，称为外圈流向。