防洪物资调运问题.doc

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

1、防洪物资调运问题摘要本题所研究的是防洪物质调运问题。在问题一中，要建立该地区公路交通网的数学模型。我们考虑到高等级公路与普通公路的运输成本的差异，通过加权，求任意两个点之间运费每一百件最少的路线。我们采用图论和网络优化的方法，借助Dijkstra算法，得到各库、企业之间的最短的加权路线，即公路交通网（见图一）。然后是问题二，以及问题三的求解。首先问题三是问题二的承接，我们只需要得出题二的模型，便可以解决。再者考虑物资的合理调运方案，重点保证国家储备库的情况下，运用动态规划，使得在一个较短的时间内完成对各库预测库存的需要，生产过剩的将分别运往储备库1、2，具体

2、的调运方案见（表一）。于是，20天的调运方案，得到如下的结果：仓库名仓库1仓库2仓库3仓库4仓库5仓库6仓库7仓库8储备库1储备库220天后库存量50060030035045030050060038402740最后是问题四的紧急调运方案的修改。考虑被洪水冲断的路线，我们进行重新的图论分析，使用Dijkstra算法，得到新的公路交通网（见图二），再根据第二问的解题思路，我们可以实现模型的修改，得到了紧急调运方案（见表三）。同时，模型的运用还可以扩展到许多的方面，如产品的分配，人员指派，最短路径、设备的合理安排以及生产与库存管理等等问题。1、问题的重述我国地域辽

3、阔，气候多变，各种自然灾害频频发生，特别是每年在长江、淮河、嫩江等流域经常爆发不同程度的洪涝灾害，给国家和人民财产带来重大损失，防洪抗涝成为各级政府的一项重要工作。现有某地区为做好今年的防洪抗涝工作，根据气象预报及历史经验，决定提前做好某种防洪抗涝物资的储备。已知该地区有生产该物资的企业三家，大小物资仓库八个，国家级储备库两个，各库库存及需求情况见附件1，其分布情况见附件2。经核算该物资的运输成本为高等级公路2元/公里•百件，普通公路1.2元/公里•百件，假设各企业、物资仓库及国家级储备库之间的物资可以通过公路运输互相调运。需要求解如下的问题：（1）请根据附

4、件2提供的信息建立该地区公路交通网的数学模型，尽量满足点与点的运输路线最短。（2）设计该物资合理的调运方案，包括调运量及调运线路，在重点保证国家级储备库的情况下，为给该地区有关部门做出科学决策提供依据。（3）根据你的调运方案，20天后各库的库存量是多少。（4）如果汛期下列路段因洪水交通中断，能否用问题二的模型解决紧急调运的问题，如果不能，请修改模型。中断路段：14——23，11——25，26——27，9——312、基本的假设1、各企业、物资仓库及国家级储备库之间的物资可以通过公路运输互相调运；2、每一条公路满足最大时的车流量，即选择的运输路线顺利通车，不出现

5、较长时间的路障以及断路；3、所有路线均可双向行使，即车辆往返使用同一线路；4、不考虑货物在运输过程中的损坏和遗失，货物全部安全到达目的地；5、物资调运的运输时间不计，即运输能力足够大；3、符号的说明表示i路段为j等级的距离,i=1,2,...n;j取1(高等级公路）或者j取2（普通公路）；表示该地区所有交点路段数目；表示物资的运输成本为高等级公路2元/公里•百件，表示普通公路1.2元/公里•百件（r=1,2)；4、问题一建立公路交通网4.1问题的分析根据附件2提供的信息，要求建立该地区的公路交通网模型，也就是通过所给的公路长度数据，加权，采取一定的方法求解出

6、各个点与点（企业、仓库、储备库三者）之间的加权最短路径。4.2问题的假设1、以百件为基本问题出发点，即运输物资一百件；4.3问题模型的建立与求解4.3.1模型的建立以仓库，企业，储备库任一为出发点，余下的其中一点为终点，得到加权路线的函数表达式为其中表示加权路线函数，m表示虚拟的0-1变量0不通过此路径m=1通过此路径于是可得目标函数表示为在所有的中取最短路径，即k=1时，取中所有路线最短的一条。4.3.2模型的求解图论是针对最短路径的一种有效的解决方法，其中比较常用的算法有Dijkstra。4.3.2.1Dijkstra基本思想Dijkstra算法建模的基

7、本思想如下：如果，，...，...，...是某图G从到的最短路径，这它的子路，...一定是从到的最短路径.4.3.2.2Difkstra算法的步骤该算法可求得网络中从某顶点到其他所有顶点的最短路径,算法步骤如下:(1)假设网络G有n个顶点,用带权的邻接矩阵W来表示，W(i，j）表示从顶点到的弧或边的权值，不存在弧或边的权值用∞（在MATLAB中为inf)表示。S为已求出的从已知始点出发的最短路径的终点的集合，它的初始状态为空集。则从出发到图上其余各顶点可能达到的最短路径长度的初值为：D(k)=min{W(i,k)

8、∈V-{i}};(2)选择，使得：D(k)=

9、min{W(i,k)

10、∈V-S};就是当前求得的一条