防洪物资调运问题3第四届苏北数学建模联赛

防洪物资调运问题

王欣邵定夫姜丽丽

（中国矿业大学，徐州221008）

摘要

每年，洪涝灾害都会使我国人民的生命财产遭受严重损失。因此，提前做好抗灾物资的调运工作，对于防洪抗涝具有重要意义。

问题一是图论当中的最短路问题。我们首先从该地区的交通状况图中提炼出两个矩阵，用来表征图中连通的两点之间的距离和运输成本。利用这两个矩阵，我们根据Dijkstra算法的原理建立了规划模型Ⅰ：最优路径模型。利用这个模型，我们求出了任意两个调运节点之间运费最小的路径。

在处理问题二时，我们充分考虑了各个调运节点的库存情况，利用已经求出的调运节点之间的最优路径及其运费，建立了模型Ⅱ：最优调运模型。这个模型以总运费最小为目标函数，只要给定了调运期限T和可容相对误差ε，就可以求解出最优调运方案。在将T定为8天，ε定为5％时，我们得到了相应的最优调运方案。

问题三实际上是模型Ⅱ的应用。将给定的条件代入模型Ⅱ中，我们得到了在这个具体情况下的最优调运方案。

当汛期到来，需要对物资进行紧急调运的情况下，我们将路程最短作为最优目标，利用模型Ⅰ，求出了各个调运节点之间的最短路径。以此为基础，我们引入“量程积”的概念，将模型Ⅱ进行了调整，建立了以量程积最小为目标函数的优化模型，得出了问题四所要求的调运方案。

通过前面得出的结果，我们发现当T取值不同时，总运费也不同。利用模型Ⅲ：最佳时间模型，我们求出了一系列不同T值所对应的总运费。通过对比我们发现，总运费随着T的增大而减小。当T在22天以上时，总运费达到最小值，并保持稳定不变。由此我们得出结论：在调运期限为22天时，总运费最小。

另外，我们还研究了ε的取值对总运费的影响。我们发现，随着ε的增大，总运费减少。比较T和ε的影响效果，发现ε的影响更显著。

最后，我们对如何预测汛期、合理安排调运期限提出了合理的建议。

一、背景分析（略）

二、问题的提出与重述（略）

三、基本假设

1、高等级公路与普通级公路的调运速度是恒定且相等的，因此运输时间只与路程远近有关。

2、由于该地区任意两点之间的距离不大，认为运输能力没有限制，即无论运输路程多远、运输件数多少，运输都能在一天内完成。

3、各企业、物资仓库及国家级仓储库之间的物资可以通过公路运输互相调运。

4、企业可以生产也可以不生产。

5、预测值指的是各库存最终需要尽量满足的目标值。

四、变量符号说明

为了便于描述问题，我们在此列出文中主要使用一些符号和基本变量，其他一些变量将在文中陆续说明。

五、问题分析

题目的第一问要求我们根据该地区交通情况示意图所提供的信息建立该地区公路交通网的数学模型。从图中我们可以看出，各个运输节点在该地区的分布

较为均匀。要建立公路交通网的数学模型，就需要将构成公路交通运输系统的各个运输节点间的最短路径找出来，从这幅比较庞杂的大图中提炼出一幅包含这些运输节点的小图。

第二问要求我们设计物资合理的调运方案。我们认为，合理的调运方案要在尽可能地满足各个运输节点的需求的前提下，尽量使运输费用最小。利用第一问的结果，我们应该可以很方便的建立一个优化模型，作为物资调度的指导依据。

问题三实际上是问题二的应用。将具体的时间代入到第二问的模型中，可以很容易得出计算结果。

问题四和问题二略有不同。在紧急情况下，要首先考虑的不再是费用问题，而是怎样最快地将救灾物资送到指定地点。所以我们的优化模型的目标函数应该与问题二有所不同。而且，由于道路受到洪水的影响发生了改变，各个运输节点之间的最短路径都应该进行重新计算，利用新的路径，给出合理的调度方案。

六、 问题1模型的建立与求解

该地区交通的示意图上，分布着42个不同的点。任意两个相连的点之间的距离在图上标出。因此，我们可以从中提炼出一个42×42的矩阵，用ij s 表示从图上点i 到图上点j 之间的路程，用ij p 表示从图上点i 到图上点j 之间的运输成本。根据这个矩阵，我们建立了模型Ⅰ，用来找出任意两个调运节点之间的最优路径。

1、模型准备

显然，这是图论中的“最短路问题”。我们首先对这幅图做出一些定义和说明：

定义 1

图(,)G V E 中12{,,,}n V v v v = 是有限集合，{(,)|,}i j i j E v v v v V =∈。称V 中的元素(1,2,,)i v i n = 为图的顶点(vertex)，E 中的元素(,)i j e v v =为图的边(edge)或弧(arc)。

定义 2

如果(,)G V E '''是一个图，并且V V '?，E E '?，则称G '是(,)G V E 的子图(subgraph)。对于图(,)G V E ，如果对(,)i j v v E ∈，赋予一个实数(,)i j w v v ，则称

(,)i j w v v 为边(,)i j v v 的权(w e i g h

，G 连同边上的权重称为赋权图(weighted graph)。

定义 3

如果(,)i j v v E ∈，则称j v 和i v 邻接，具有n 个顶点的图的邻接矩阵

(a d j a c e n c m a t r i x )是一个n n ?阶矩阵()ij n n A a ?=，其分量为

1,(,),

0,i j ij v v E a ∈?=??Others.

n 个顶点赋权图的赋权矩阵是一个n n ?阶矩阵()ij n n W w ?=，其分量为

(,),(,),

,i j i j ij w v v v v E w ∈?=?∞?Others.

2、模型Ⅰ的建立

Dijkstra 算法是解决最短路问题的一种很有效的方法，它的原理如下： 假设S 是V 的真子集且0u S ∈，并以S 记\V S 。若0P u u v = 是从0u 到S 的最短路，则显然u S ∈且P 的0(,)u u 节必然是最短0(,)u u 路。所以，

00(,)(,)()d u v d u u w uv =+

并且从0u 到S 的距离由公式

00(,)min{(,)()}u S

v S

d u S d u u w uv ∈∈=+ 给出。这个公式便是Dijkstra 算法的基础。

在整个算法中，每个顶点v 给以标号()l v ，它是0(,)d u v 的一个上界。开始时0()0l u =，而对0v u ≠，则有()l v =∞。在算法进行时，这些标号不断被修改：在第i 步结束时

0()(,)l u d u u = 对i u S ∈成立

并且 0()min{(,)()}i

u S l v d u u w uv ∈=+ 对i v S ∈成立 下面是具体的Dijkstra 算法操作流程图：

当算法结束时，从0u 到v 的距离由标号()l v 的终值给出。

假设图有n 个顶点，现需要求从顶点1到顶点n 的最短路。设决策变量为ij x ，当1ij x =，说明弧(,)i j 位于顶点1到顶点n 的路上；否则0ij x =。由此，我们可以写出求解此问题的模型Ⅰ——最优路径模型：

(,)min ij ij i j E W w x ∈=

∑

11(,)(,)1,1,

0,1,,..1,;0,(,)n n ij ji j j i j E j i E ij i x x i n s t i n x i j E ==∈∈?=???-=≠????-=???≥∈?

∑∑

3、模型Ⅰ的求解。

在利用这个模型求解任意两点之间的最优路径时，需要注意目标函数中的每段路线上的权重ij w 。ij w 的含义不同，最终的结果也不同。当情况紧急，需要寻

找一条最短最快捷的路径时，可以将ij w 定义为两点之间路线的长度ij s ，目标函

数变为这样的形式：

(,)min ij ij i j E W s x ∈=

∑

所求出来的结果就是出发点与目的地之间的最短路径。

如果情况不是很紧急，则应该综合考虑运输费用，此时，我们可以定义权重为单位运输成本与路程的乘积：ij ij ij w p s =?，这样得到的目标函数是：

(,)min ij ij ij i j E W p s x ∈=

∑

这样求出来的路径就是运输费用最低的路径。

考虑一般情况，我们都选择运输费用最低的路径，即定义ij ij ij w p s =?，利用

lingo 8.0软件编程求解，我们得到：

企业1到企业2之间的最优路径是 24→26→25→15→42→41，在这条路径上运输物资的费用为177.6元/百件。

由于篇幅所限，全部13个运输节点之间的最优路径及在该路径上的运输费用将在附件2、3 中列出。

七、 问题2的模型建立与求解

要得到一个最合理的调运方案，就需要建立一个优化模型，用来求出最佳调运量以及调运路线。

1、约束条件的确定

我们令按照模型求出的从i 调运节点到j 调运节点的调运量为ij x ， 0ij x ≥。则调运结束后各个节点的库存i r 为：

131311131311,1,2,3

,4,5,,13i ij ji i i j j i i ij ji j j c x x v t i r c x x i ====?-++=??=??-+=??

∑∑∑∑ 题目列出了各库库存与需求情况，其中列出了预测库存一项。我们认为，按照运输方案进行调度之后，各个运输节点的库存，应该尽可能地接近或大于预测库存。 令ε为能够接受的实际库存与预测库存的偏离程度，i f 预测库存量，有：

,4,5,,11i i i

f r i f ε-≤= 另外，一个节点需要的库存能力有限制，必须不超过最大库存，有：

1,2,,13i i r M i ≤=

此外，要重点保证国家级储备库的库存。因此，我们要求的方案必须使国家级储备库的库存达到或者超过其预测值，即：

,12,13i i f r i ≤=

2、目标函数的建立

我们希望我们的调运方案在满足各项要求的基础上，所花费的运输费用最小。从第一问的结果中，我们已经得到了任意两个调运节点之间花费最小的最优路径，该路径的每百件物资的运输费用为ij W 元。显然，如果从调运节点i 运输ij x 百件物资到调运节点j ，一定会从已经求得的最优路径进行运输。这样，调运结束之后，花费的总费用为：

1313

11ij ij i j y W x ===∑∑

3、模型Ⅱ建立

根据上面的分析，我们建立了模型Ⅱ—最优调运模型：

1313

11min ,1,2,,13,4,5,,11..,12,13

0,,1,2,,130,ij ij

i j i i i i i i i ij

i y W x r M i f r i f s t f r i x i j t T t ε===≤=??-?≤=??≤=??≥=??≤≤??

∑∑ 为整数 其中：

131311131311,1,2,3

,4,5,,13i ij ji i i j j i i ij ji j j c x x v t i r c x x i ====?-++=??=??-+=??

∑∑∑∑ 通过这个模型，在给定了偏离程度ε以及调运天数T 的情况下，就可以求出相应的最优方案。

4、一种情况下的最优方案

我们用一种特殊情况来演示模型Ⅱ的效果。

由于不知道汛期何时到来，我们需要尽快做好准备，在最短的时间内使各个调运节点的预测库存得到尽量满足。我们可以先进行一个粗略的估算：各个调运节点的原有库存之和1318380i i c ==∑，而各个调运节点的预测库存之和13

49050i i f ==∑，

即相差670。因此，要基本满足要求，需要各企业至少生产8天。我们就以8天为调运期，求出最优方案。我们假定ε取0.05，于是模型Ⅱ变为：

11,1,2,,130.05,4,5,,11..,12,13

0,,1,2,,1308,i j i i i i i i i ij

i r M i f r i f s t f r i x i j t t ==≤=??-?≤=??≤=??≥=??≤≤??

为整数

利用lingo 8.0编程求解，得到最低总运输费用为321680元。调运方案及其线路如表2所示：

其中三个企业都生产8天。

八、 问题三的解答

利用模型Ⅱ，我们可以很容易地求出结果。仍令ε取0.05，此时，模型为：

11,1,2,,130.05,4,5,,11..,12,13

0,,1,2,,13020,i j i i i i i i i ij

i r M i f r i f s t f r i x i j t t ==≤=??-?≤=??≤=??≥=??≤≤??

为整数 编程求解可求得最优调运方案（见附件4）。此时的运输费用为299763元，20天后各个调运节点的库存情况如表3 所示：

九、 问题四的解答

问题四要求紧急情况下的调运方案。由于是紧急情况，所以应该考虑速度尽可能快，路程尽可能少，对运费的要求就不是那么重要了。因此，我们要重新计算各个调运节点之间的最短路径。另外，由于洪水使部分道路不能使用，新的最短路径必然与上面计算的最优路径有很大区别。

利用模型I ： (,)min ij ij i j E W s x ∈=

∑

我们重新计算出各个调运节点之间的最短路径，由此，我们得到了一组新的ij W ，由于此时ij W 的意义是两调运节点之间的最短路程，因此，我们用ij S 来表示这个量。

我们引入“量程积”的概念。量程积，即ij ij W x ，运输数量与运输路程之积，单位是百件·公里。由于是紧急情况，我们必须尽快完成调运，并且使总量程积

最小，我们仍规定在8天内完成调运任务。利用模型Ⅱ：

1313

11min ij ij i j y W x ===∑∑

我们解出了在这种情况下的最优调度方案（见附件4）。此时的总量程积为：314297.5百件·公里。

十、 模型的进一步讨论

1、调运期的长短与运费的关系

在求解问题2和问题3的时候，我们发现，在调运期为8天的时候，总运费为321680元，调运期为20天的时候，总运费为299763元。显然，调运时间的长短对最终运费有着显著影响。

我们希望能够找到一个最佳的时间，使得总运费能够达到最小，同时，各个调运点的能够达到或超过预测值。为了找出这个最佳时间，我们在模型Ⅱ的基础上作了一点改动，建立了模型Ⅲ——最佳时间模型：

Min 1313

1311{}i ij ij i i j z Max t w x ≤≤===?∑∑ ,1,2,,13..0,,1,2,,13,1,2,3

i i i ij i f r M i s t x i j t T i ?≤≤=?≥=??≤=?

由于模型Ⅱ中与预测库存的偏差ε的取值对最终费用的大小有影响，因此，在这个模型中，我们对于调运后的库存量进行了强制约束，要求在调度完毕之后，各库的库存都要达到或超过预测值。通过这个模型，代入不同的T 值，将求出的结果互相比较，就可以得到最佳的调运期限。

利用lingo 8.0，我们将T 从8开始，逐渐增加后代入求解。最终，我们得到每次的T 值与其对应的总运费，如图1 所示：

图1

从图1中我们能不难看出，随着调运期的增加，总的调运费用不断下降。当T 增加到22天的时候，调运费用趋于平衡，不再发生改变。

造成这种情况的原因是，随着调运期限的增加，企业可用来生产的天数也增加，因而企业能够运出的物资量也增加，相应的输出选择面和灵活度也增加，从而使总运费降低。

因此，我们能够得出如下结论：

（1） 调运期限越长，所要花费的总运费越少。

（2） 22天是最佳调运期限，此后的调运费用不发生改变，因此没有必要制定多于22天的调运计划。

（3） 如果能够对于汛期的到来进行比较准确的预测，则在汛期到来之前22天开始进行调运，到汛期到来前一天结束，能够得到最合适的结果。

2、调运期的长短、ε的取值对于费用的影响

ε的取值对于费用也有着重要的影响。因此，我们希望能够找到ε和T 对于总费用的影响效果。

模型Ⅱ：1313

11min ij ij i j y W x ===∑∑中同时含有ε和T 两个因素，因此，我们分别取

不同的ε和T 值，得到不同的费用（见附件5 ），作出了图2 ：

图2

从上述图表中我们可以很容易地看到：总调运费用y 是关于普通仓库预测库存相对误差ε和调运周期T 的二元函数；且总调运费用y 均随着可容相对误差ε和物资生产天数T 的增加而减少。

这是非常符合实际情况的，因为当可容相对误差ε的增大使得调运工作的约束条件减弱，自由度增加，因而总的调运费用降低；物资生产天数T 的增加使得各个企业的输出能力增大，故导致调运任务的灵活性增加，因而总的调运费用降低。

同时，从上图中我们也可以很明显地看出：可容相对误差ε的波动对总调运

费用y 的影响比物资生产天数T 的改变对总调运费用y 的影响要大。

3、汛期的预测

前面说过，如果能够对汛期开始的时间做出准确的预测，就可以合理地安排调运期限，从而使运费最小。但是自然灾害的发生时间带有一定随机性，并不容易预测；天气预报对于短期气候比较准确，对于长期的气候情况则很难得到准确的预报。

根据历史数据，可以得到时间t 开始汛期的概率()p t ，利用下面的关系式，我们可以得到汛期起始时刻的期望值t*：

21

12[,]*()t t t t t t t t p t dt ∈==?? 由于这仅仅是预测值，为了保险起见，并不直接以t*作为调运的最后期限，而是给定一个保险期，规定调运必须在t*之前5天结束。这样，利用前面得出的结论，可以在t*之前27天开始调运，在t*之前5天结束，从而使运输费用最小。 当调运开始与(*5)t -之后时，要按照紧急调运的情况进行处理，求出最优方案。

十一、 模型的优缺点分析（略）