防洪物资调运问题
王 欣 邵定夫 姜丽丽 （中国矿业大学，徐州 221008）
摘 要
每年，洪涝灾害都会使我国人民的生命财产遭受严重损失。因此，提前做好抗灾物资的调运工作，对于防洪抗涝具有重要意义。
问题一是图论当中的最短路问题。我们首先从该地区的交通状况图中提炼出两个矩阵，用来表征图中连通的两点之间的距离和运输成本。利用这两个矩阵，我们根据Dijkstra算法的原理建立了规划模型Ⅰ：最优路径模型。利用这个模型，我们求出了任意两个调运节点之间运费最小的路径。
在处理问题二时，我们充分考虑了各个调运节点的库存情况，利用已经求出的调运节点之间的最优路径及其运费，建立了模型Ⅱ：最优调运模型。这个模型以总运费最小为目标函数，只要给定了调运期限T和可容相对误差?，就可以求解出最优调运方案。在将T定为8天，?定为5％时，我们得到了相应的最优调运方案。
问题三实际上是模型Ⅱ的应用。将给定的条件代入模型Ⅱ中，我们得到了在这个具体情况下的最优调运方案。
当汛期到来，需要对物资进行紧急调运的情况下，我们将路程最短作为最优目标，利用模型Ⅰ，求出了各个调运节点之间的最短路径。以此为基础，我们引入“量程积”的概念，将模型Ⅱ进行了调整，建立了以量程积最小为目标函数的优化模型，得出了问题四所要求的调运方案。
通过前面得出的结果，我们发现当T取值不同时，总运费也不同。利用模型Ⅲ：最佳时间模型，我们求出了一系列不同T值所对应的总运费。通过对比我们发现，总运费随着T的增大而减小。当T在22天以上时，总运费达到最小值，并保持稳定不变。由此我们得出结论：在调运期限为22天时，总运费最小。
另外，我们还研究了?的取值对总运费的影响。我们发现，随着?的增大，总运费减少。比较T和?的影响效果，发现?的影响更显著。
最后，我们对如何预测汛期、合理安排调运期限提出了合理的建议。
一、 背景分析（略） 二、 问题的提出与重述（略）
三、 基本假设
1、高等级公路与普通级公路的调运速度是恒定且相等的，因此运输时间只与路程远近有关。
2、由于该地区任意两点之间的距离不大，认为运输能力没有限制，即无论运输路程多远、运输件数多少，运输都能在一天内完成。
3、各企业、物资仓库及国家级仓储库之间的物资可以通过公路运输互相调运。
4、企业可以生产也可以不生产。
5、预测值指的是各库存最终需要尽量满足的目标值。
四、 变量符号说明
为了便于描述问题，我们在此列出文中主要使用一些符号和基本变量，其他一些变量将在文中陆续说明。
表1 符号 意义 单位 sij pij wij 从图上点i到图上点j之间的路程 从图上点i到图上点j之间的运输成本 从图上点i到图上点j之间路线的权重 将要进行运输调度的地点依次命名为调运节点(depot)Di，其公里 元/公里?百件 Di 中(i?1,2,?,13)，这13个点构成了一个完全图K13（见附件1） Sij 从调运节点i到调运节点j之间的最短路程 从调运节点i到调运节点j之间最优路线的权重 从调运节点i到调运节点j之间的物资运输量 调运节点i的最小库存量 调运节点i的最大库存量 调运节点i的现有库存量 调运节点i调运后的库存量 调运节点i的预测库存量 调运节点（企业）i生产速度，i?1,2,3 调运节点（企业）i在调运计划中的生产天数 可容相对误差，即与调运节点i预测库存的偏离程度 总调运费用 公里 元/百件 百件 百件 百件 百件 百件 百件 百件/天 天 元 Wij xij mi Mi ci ri fi vi ti ? y 五、 问题分析
题目的第一问要求我们根据该地区交通情况示意图所提供的信息建立该地区公路交通网的数学模型。从图中我们可以看出，各个运输节点在该地区的分布
较为均匀。要建立公路交通网的数学模型，就需要将构成公路交通运输系统的各个运输节点间的最短路径找出来，从这幅比较庞杂的大图中提炼出一幅包含这些运输节点的小图。
第二问要求我们设计物资合理的调运方案。我们认为，合理的调运方案要在尽可能地满足各个运输节点的需求的前提下，尽量使运输费用最小。利用第一问的结果，我们应该可以很方便的建立一个优化模型，作为物资调度的指导依据。
问题三实际上是问题二的应用。将具体的时间代入到第二问的模型中，可以很容易得出计算结果。
问题四和问题二略有不同。在紧急情况下，要首先考虑的不再是费用问题，而是怎样最快地将救灾物资送到指定地点。所以我们的优化模型的目标函数应该与问题二有所不同。而且，由于道路受到洪水的影响发生了改变，各个运输节点之间的最短路径都应该进行重新计算，利用新的路径，给出合理的调度方案。
六、 问题1模型的建立与求解
该地区交通的示意图上，分布着42个不同的点。任意两个相连的点之间的距离在图上标出。因此，我们可以从中提炼出一个42×42的矩阵，用sij表示从图上点i到图上点j之间的路程，用pij表示从图上点i到图上点j之间的运输成本。根据这个矩阵，我们建立了模型Ⅰ，用来找出任意两个调运节点之间的最优路径。
1、模型准备
显然，这是图论中的“最短路问题”。我们首先对这幅图做出一些定义和说明： 定义 1
图G(V,E)中V?{v1,v2,?,vn}是有限集合，E?{(vi,vj)|vi,vj?V}。称V中的
元素vi(i?1,2,?,n)为图的顶点(vertex)，E中的元素e?(vi,vj)为图的边(edge)或弧(arc)。 定义 2
如果G?(V?,E?)是一个图，并且V??V，E??E，则称G?是G(V,E)的子图
(subgraph)。对于图G(V,E)，如果对(vi,vj)?E，赋予一个实数w(vi,vj)，则称
，G连同边上的权重称为赋权图w(vi,vj)为边(vi,vj)的权(weigh(weightedgraph)。
定义 3
如果(vi,vj)?E，则称vj和vi邻接，具有n个顶点的图的邻接矩阵是一个(adjacenmcatrix)n?n阶矩阵A?(aij)n?n，其分量为
?1,aij???0,(vi,vj)?E,Others.
n个顶点赋权图的赋权矩阵是一个n?n阶矩阵W?(wij)n?n，其分量为
?w(vi,vj),wij????,(vi,vj)?E,Others.
2、模型Ⅰ的建立
Dijkstra算法是解决最短路问题的一种很有效的方法，它的原理如下： 假设S是V的真子集且u0?S，并以S记V\\S。若P?u0??uv是从u0到S的最短路，则显然u?S且P的(u0,u)节必然是最短(u0,u)路。所以，
d(u0,v)?d(u0,u)?w(uv)
并且从u0到S的距离由公式
d(u0,S)?min{d(u0,u)?w(uv)}
u?Sv?S给出。这个公式便是Dijkstra算法的基础。
在整个算法中，每个顶点v给以标号l(v)，它是d(u0,v)的一个上界。开始时
l(u0)?0，而对v?u0，则有l(v)??。在算法进行时，这些标号不断被修改：在第i步结束时
l(u)?d(u0,u) 对u?Si成立
并且 l(v)?min{d(u0,u)?w(uv)} 对v?Si成立
u?Si下面是具体的Dijkstra算法操作流程图：
当算法结束时，从u0到v的距离由标号l(v)的终值给出。
假设图有n个顶点，现需要求从顶点1到顶点n的最短路。设决策变量为xij，当xij?1，说明弧(i,j)位于顶点1到顶点n的路上；否则xij?0。由此，我们可以写出求解此问题的模型Ⅰ——最优路径模型：
minW?(i,j)?E?wijxij
i?1,i?1,n,
i?n;
?n?1,n????xij??xji??0,s..t?j?1j?1??1,(i,j)?E(j,i)?E???xij?0,(i,j)?E?
3、模型Ⅰ的求解。
在利用这个模型求解任意两点之间的最优路径时，需要注意目标函数中的每段路线上的权重wij。wij的含义不同，最终的结果也不同。当情况紧急，需要寻找一条最短最快捷的路径时，可以将wij定义为两点之间路线的长度sij，目标函数变为这样的形式：
minW?
(i,j)?E?sijxij