《防洪物资调运问题毕业论文》由会员分享，可在线阅读，更多相关《防洪物资调运问题毕业论文（24页珍藏版）》请在金锄头文库上搜索。
1、防洪物资调运问题摘要我国地域辽阔，气候多变，各种自然灾害频频发生，国家和人民每年因此损 失惨重，因此防洪抗涝工作至关重要，而防洪抗涝物资的调运与储备与物流管理 息息相关。所以，物资调运作为物流不可或缺的环节其重要性也日益呈现出来， 其合理化也显得十分重要。对于问题一，我们通过对交通网络的分析，构造了最短路权的二维矩阵 D ，从而建立了这个地区公路交通网的数学模型，对于该模型的求解我们采用 Dijkstra 算法并按照一定的迭代规则进行 n 次迭代，得到了一个最短路权对称 矩阵。相比于其它算法，这种算法更易于实现和理解，且效率高，运行速度快。 在问题二中我们先从简单入手，将问题尽量的简化建立了一
2、个简单的数学模 型并得出了一个较为合理的结果，但是题中并没有对时间以及理想库存等影响决 策变量的因素进行量化，这就需要我们对其模糊条件进行量化，从而建立了调运 系统中模糊条件的量化模型，并选取了适当的“虚拟”运价和“虚拟”销地，他 超越了以往经典问题的求法。 对于其解法我们又将规划 L1 转化为规划并建立了 L2 相比于单纯形法，放宽了条件限制，也避免了由于贮存空间大选用分枝界定法和割平面法带来的求解运算量大，计算效率低等问 题，从而使得我们的模型更具有可靠性。 在计算过程中路径和运费作为基本出发点，在满足提设条件下以运费最小为 参考。 最后，我们对这个调运问题提出了合理的调运方案并为该地提供
3、了调运的科 学依据。一、问题重述（略）二、问题分析问题一：要建立该地区的交通网的数学模型，考虑其现实意义我们应当从任意两 点间的最短路权来考虑，因此我们引出了交通网的最短路权矩阵，从而建立了交 通网的最短路权举证模型。 问题二：要求合理的调运方案，我们应该在满足提设要求的情况下主要从时间、 运费、路经等加以分析。但是由于题中并没有对时间以及理想库存等量化，这就 需要我们对其模糊条件进行量化，从而建立了调运系统中模糊条件的量化模型。 问题三：在问题二的基础上我们很容易得出结果。 问题四：要看模型二能否解决问题，关键是看我们在解问题二时是否用到了中断 路线，如果有用到那么我们的模型就要做相应的改进
4、，反之则不。三、基本假设1、忽略调运时间，即开始调运就能立即到达。 2、货物在运输过程中没有损耗。3、相同费用情况下可把高等级公路换算成普通公路。 4、等量的货物在各个仓库的库存费用相等。四、符号说明y 、 y：运量函数 i ：企业的现有库存 j ：仓库的现有库存 i：企业的最低库存j ：仓库的最低库存1、2 ：储备库 1、2 的现有库存1 、2 ：调运后储备库的库存1max 、2max ：储备库的最大库存量 j ：仓库的预测库存 j ：各企业分别向仓库进行调运的运量（ i =1、2、3； j =1、2、3、4、5、6、7、8）注：其它符号在文中相应处说明五、模型的建立与求解问题一：模型的建立
5、与求解： 要建立该地区交通的数学模型，我们引入交通网络最短路权矩阵。我们知道， 在交通网络中，从节点 A 到节点 B 的最短路径是指在节点 A 到节点 B 的所有路 径中，某路段的路权和为最小的那条路径。此最短路径的路权和称为从节点 A 到节点 B 的最短路权，所有交通节点两两间的路权所组成的二维矩阵称为这个交 通网络的最短路权矩阵。路权可以表示路段长度，平均行程时间，费用等交通特 征。 因此，我们对于该模型所用到的概念作如下约定： 1)对于某个交通网络，可抽象为带权有向图G=(V，E)。式中：V为节点集合,V= v1, v2 , v3, vn1, vn ；E为边集合，E= eij ， eij
6、 =( vi , v j )， vi , v j = ( vi , v j V且 vi 到 v j 有边相连，i,j 1，2， ，n)，权是非负的。0 eij Edij dD .d可以找出网络中从一点到其余各点间的最短路径。它的时间复杂度为 O(n ) ，n两之间的最短路径，可以通过调用 n 次的 Dijkstra 算法来实现，因此可以用 O(n )2)路权矩阵D= dij ，定义如下。dij给定的权 当存在从v 到v 的边时，e E当不存在从i到j的边时(i,j= 1，2， ,n )3)记从 vi 到 v j 的某条路径 pij vi , u1, u2 , ur1, ur , v j。式中：
7、u1, u2 , ur1, ur , v j 为V中某r个互异元素(不包括 vi , v j )的一个有向序列，pij 的权定义为路径上各边的权之和。4)记第m 次迭代后的路权矩阵 Dmmd ij m 由相应迭代规则计算得到，记 D0 =D 。5)将本文给出的最短路径的概念进行扩充，允许对最短路径的求解额外增 加某种限制条件(比如路径上至多有k条边)，那么在不同的限制条件下得到不同 意义的最短路径。此后提到的最短路径如无特别说明，均指不加额外限制的最短 路径。同样，对最短路权、最短路权矩阵的概念也作相似扩充和约定。 对于该模型的最短路权矩阵为： d11 12 d13 . . 1,n1 d1nd
8、21 d 22d 23 . . .d2,n1d2nd31 d32d33 . . .d3,n1d3n. d n1,1 . dn1,2. d n1,3 . . . . d n1,n1. d n1,ndn1 dn 2d n3 . . .d n,n1d n,n 对于两点间最短路权计算，国际上采用比较多的是 Dijkstra 算法。此算法2为网络的大小（即节点数目），而在交通分配过程中，需要知道的是所有节点两3的时间复杂度来求出网络的最短路权矩阵。其具体的算法如下： 迭代公式为：D Dd同样是节点组成的一个有向序列。D , D , D 相当于最短路径分别被限制为中算法的第k次迭代，已知 pathijpa
9、thij ij k1 dij ij k1 ；如果后者小，表示 pathij 经过节点k，其最短路 path k k k径为 pathik kjk1 两者的连接 k1k k1 k iji, j 1, 2, n1, n式中： 为运算号，其运算规则为dijk mindijk1 , dikk1 dkjk1利用式(1)反复迭代，直至 D k D k1 ，那么矩阵 D k 就是最短路权矩阵。将 vi 到 v j 满足中间节点编号不大于k这一条件时的最短路径记为 pathij k ，它0 k n间节点编号不大于0，k，n 情况下的最短路权矩阵；特别地，由于整个网络中最 大节点编号为 n，对于 D n ，中间
10、节点编号的限制条件是自然满足的(即限制条件被彻底取消), D n 就是最后所求的最短路权矩阵。k1i, w1, w2, wm, jm k1w1, w2 , wm为V的子集v1,v2,vk1 中的 m个互异元素的一个有向序列，即 w1, w2, wm, 节点编号均不大于k一1，而相应的最短路权为 d ij k1 。在这个基础上放宽条件，允许从vi 到 v j 的最短路径可以包括节点 vk ，即所有中间节点编号不大于k。考察 d ij k1 和 dikk1 +d kj k1 ， 如果前者小，表示 pathij k 不经过节点k,=d, path设：pathikk1i, u1,u2,ur ,k ,
11、pathkjk1 k , t1,t2,ts , j其中r, s k 1, u1,u2,ur , t1,t2,ts , v1,v2,vk1 r+S个互异元素的一个排列可以证明 u1,u2,ur , t1,t2,ts , 是互异的，且r+sk一1，事实上，若某个 um tc ，则路径（i， u1,u2,um, tc1,tc2,ts ,)比 pathik k1 pathkj k1 两者的连接要短，比pathij k 更要短，这与 pathij k1 的定义相矛盾，则 pathiji, u1, 2,ur , k , t1, 2,ts , ju tdij ik kj k1=d k1 d0 10D 10
12、0 38 38 090 168 2940 1048 78 104D 0 38 86 920 78 1040k k这一步保证 pathij k 的中间节点的编号不大于k，而且是这一限制下所求得的路径中最短的。由 D0 的定义及第k步的分析，根据归纳法，迭代终止时的矩阵一定是网络的最短路权矩阵。根据 D k 的定义，在最坏情况下，当k=n 时，迭代一定能终止。算法最多进行n 次矩阵迭代，而每次矩阵迭代需要进行 n 2 次式(1)运算，又式(1)的时间复杂度为常数，所以整个算法的平均时间复杂度为O( n3 )。首先我们写出该邻接矩阵 D，如下所示： 0 4040 0 35 35 0 0 26 26 0运用程序（见附录二）。其中 n42，可得该交通网络的最终最短路权。矩阵如下 D 所示：0 40 75 178 168 130 208 134 0 35 138 128 0 173 163 125 203 229 0 26 D与DD与D）122问题二：模型一的建立与求解：我们先从简单考虑用一般的解法加
