防洪物资调运问题

《防洪物资调运问题》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、防洪物资调运问题摘要我国地域辽阔，气候多变，各种自然灾害频频发生，国家和人民每年因此损失惨重，因此防洪抗涝工作至关重要，而防洪抗涝物资的调运与储备与物流管理息息相关。所以，物资调运作为物流不可或缺的环节其重要性也日益呈现出来，其合理化也显得十分重要。对于问题一，我们通过对交通网络的分析，构造了最短路权的二维矩阵，从而建立了这个地区公路交通网的数学模型，对于该模型的求解我们采用Dijkstra算法并按照一定的迭代规则进行n次迭代，得到了一个最短路权对称矩阵。相比于其它算法，这种算法更易于实现和理解，且效率高，运行速度快。在

2、问题二中我们先从简单入手，将问题尽量的简化建立了一个简单的数学模型并得出了一个较为合理的结果，但是题中并没有对时间以及理想库存等影响决策变量的因素进行量化，这就需要我们对其模糊条件进行量化，从而建立了调运系统中模糊条件的量化模型，并选取了适当的“虚拟”运价和“虚拟”销地，他超越了以往经典问题的求法。对于其解法我们又将规划转化为规划并建立了相比于单纯形法，放宽了条件限制，也避免了由于贮存空间大选用分枝界定法和割平面法带来的求解运算量大，计算效率低等问题，从而使得我们的模型更具有可靠性。在计算过程中路径和运费作为基本出发点，

3、在满足提设条件下以运费最小为参考。最后，我们对这个调运问题提出了合理的调运方案并为该地提供了调运的科学依据。一、问题重述（略）二、问题分析问题一：要建立该地区的交通网的数学模型，考虑其现实意义我们应当从任意两点间的最短路权来考虑，因此我们引出了交通网的最短路权矩阵，从而建立了交通网的最短路权举证模型。问题二：要求合理的调运方案，我们应该在满足提设要求的情况下主要从时间、运费、路经等加以分析。但是由于题中并没有对时间以及理想库存等量化，这就需要我们对其模糊条件进行量化，从而建立了调运系统中模糊条件的量化模型。问题三：在问题

4、二的基础上我们很容易得出结果。问题四：要看模型二能否解决问题，关键是看我们在解问题二时是否用到了中断路线，如果有用到那么我们的模型就要做相应的改进，反之则不。三、基本假设1、忽略调运时间，即开始调运就能立即到达。2、货物在运输过程中没有损耗。3、相同费用情况下可把高等级公路换算成普通公路。4、等量的货物在各个仓库的库存费用相等。四、符号说明、：运量函数：企业的现有库存：仓库的现有库存：企业的最低库存：仓库的最低库存、：储备库1、2的现有库存、：调运后储备库的库存、：储备库的最大库存量：仓库的预测库存：各企业分别向仓库进行

5、调运的运量（=1、2、3；=1、2、3、4、5、6、7、8）注：其它符号在文中相应处说明五、模型的建立与求解问题一：模型的建立与求解：要建立该地区交通的数学模型，我们引入交通网络最短路权矩阵。我们知道，在交通网络中，从节点A到节点B的最短路径是指在节点A到节点B的所有路径中，某路段的路权和为最小的那条路径。此最短路径的路权和称为从节点A到节点B的最短路权，所有交通节点两两间的路权所组成的二维矩阵称为这个交通网络的最短路权矩阵。路权可以表示路段长度，平均行程时间，费用等交通特征。因此，我们对于该模型所用到的概念作如下约定：

6、1)对于某个交通网络，可抽象为带权有向图G=(V，E)。式中：V为节点集合,V={}；E为边集合，E={}，=()，=(∈V且到有边相连，i,j∈{1，2，⋯，n})，权是非负的。2)路权矩阵D=[]，定义如下。=(i,j=1，2，⋯,n)3)记从到的某条路径。式中：为V中某r个互异元素(不包括)的一个有向序列，的权定义为路径上各边的权之和。4)记第m次迭代后的路权矩阵。由相应迭代规则计算得到，记=D。5)将本文给出的最短路径的概念进行扩充，允许对最短路径的求解额外增加某种限制条件(比如路径上至多有k条边)，那么在不同的

7、限制条件下得到不同意义的最短路径。此后提到的最短路径如无特别说明，均指不加额外限制的最短路径。同样，对最短路权、最短路权矩阵的概念也作相似扩充和约定。对于该模型的最短路权矩阵为：对于两点间最短路权计算，国际上采用比较多的是Dijkstra算法。此算法可以找出网络中从一点到其余各点间的最短路径。它的时间复杂度为，n为网络的大小（即节点数目），而在交通分配过程中，需要知道的是所有节点两两之间的最短路径，可以通过调用n次的Dijkstra算法来实现，因此可以用的时间复杂度来求出网络的最短路权矩阵。其具体的算法如下：迭代公式为：

8、（1.1）式中：为运算号，其运算规则为（1.2）利用式(1)反复迭代，直至，那么矩阵就是最短路权矩阵。将到满足中间节点编号不大于k这一条件时的最短路径记为，它同样是节点组成的一个有向序列。相当于最短路径分别被限制为中间节点编号不大于0，k，n情况下的最短路权矩阵；特别地，由于整个网络中最大节点编号为n，对于，中间节点