下载文档原格式
防洪物资调运问题黄权 解三健 曹兴进 （中国矿业大学，徐州 221008）摘 要我们的模型主要用于解决如何在最少运费的情况下将必需物资调运到各个仓库以达到防洪的目的。
对于问题一：我们采用赋权连通图的图论法，把两地的运费作为它们之间线路的权值，然后利用“画圈去大”原则进行最小总权值的求解。
然后，我们又引入了动态规划中的顺序递推法进行两地之间运费最短路的选择。
对于问题二：我们首先利用顺序递推法求解出任两地之间的运费最短路径。
同时，由于要重点保证国家储备库，我们引进加权系数1α、2α进行调运量的限制。
由于仓库3与仓库5的现有库存量大于预测库存量，我们考虑是否应将两库超过预测库存量的那部分空闲物资进行调运，进而建立了两个模型。
然后，我们分别运用线性规划的方法，给出目标函数，归纳如下：∑∑∑===++=310099318112)(i i i i i i j ij ij b C b C b C MinZ αα结合各自的约束条件，我们利用LINDO 软件进行解模，求出两者的最优调运量及总运费。
之后，进行两者总运费的比较，得出最终的最优调运方案。
对于问题三：我们利用问题二的结果求出每个企业必要的最低生产天数i t ，若企业的i t ＜20天，则它所供给的仓库以及储备库就已达到预测库存量。
若企业的i t ＞20天，则可以用比例求解出20天后该企业向每个仓库以及储备库的调运量，进而可以求出20天后各库的库存量。
对于问题四：当某路段遭破坏而不能保证某仓库的储存量时，我们考虑了三种方案。
一为寻找次短路线进行物资的重新调运；二为从其他企业向供应源中断的仓库进行物资调配；三为进行整体线路的重新调配。
最后进行三者总运费的比较，确定了最经济合理的调配方案。
一、问题重述（略）二、模型假设1、各企业的生产日期为无限。
即在洪水之前各个企业均已将全部物资调运到相应的仓 库。
2、在整个的生产过程中，生产费用不予考虑。
3、仓库的物资的储存费、转运费不予考虑。
物资紧急调运问题的优化模型摘要本文就物资的紧急调运问题，运用图论和线性规划的理论和方法建立数学模型，针对防洪救灾物资的调运问题设计了合理的调运方案。
在问题（1）中，将工作量（运输路程 调运量）作为衡量调运方案的标准。
利用Floyd算法（Matlab程序代码见附录二）得到各重要节点（企业、仓库、国家级储备库）之间的最短路线（详见表1）。
由于要求重点保证国家级储备库的库存量，我们将调运过程分为两个阶段：（1）企业和现有库存量超过预测需求量的仓库向国家级储备库调运；（2）企业向现有库存量小于预测需求量的仓库调运。
据此建立线性规划模型，用LINGO进行求解，得到最佳的紧急调运方案。
（详见表3、表4）。
在问题（2）中，在问题（1）所确定的调运方案的基础上，建立以时间最省为目标的线性规划模型。
利用LINGO软件求解得到18辆车的最佳调度方案（见表7），所用的时间为68.2天。
在问题（3）中，因为时间充裕，我们认为各仓库及国家级储备库均要达到其最大库存量才能应对灾害，为降低运输成本，在建立Floyd算法的邻接矩阵时，应以运费为权重，找到费用最省的路线后，调运救灾物资时必定沿费用最省的路径调运，据此建立线性规划模型求出使运输费用最省的调运方案（见表10）。
确定调运量后即可确定使车辆数最小的车辆调度方案（见表11），共需要32辆车。
最终得到最低运输成本为724253元。
在问题（4）中，由于16号地区灾情紧急，急需10万件救灾物资。
此时应在保证在5天内完成调运任务的前提下，使所需车辆尽量少。
首先在路段○16—○21,○16—○23,○11—○25 ,○25—○26和○32—○34中断的情况下求出各企业、仓库、国家级储备库向16号地区调运救灾物资的时间最省路径；其次建立以所需车辆最少为目标，5天内完成调运任务等为约束条件的线性规划模型。
通过LINGO求解得到最少需要60辆车（详见表13）。
关键词：救灾物资调运；Floyd算法；线性规划； LINGO1.问题的重述我国地域辽阔，气候多变，洪水、泥石流等各种自然灾害频频发生，给国家和人民财产带来重大损失，防洪救灾成为各级政府的一项重要工作。
物资配送问题是一种常见的物流配送问题，它涉及到如何安排车辆或路线，将物资从一个地方运送到另一个地方。
这个问题可以抽象为一个优化问题，目标是最小化运输成本或最大化运输效率。
下面是一种简单的数学建模方法：
1.确定问题和目标：明确需要配送的物资种类、数量、目的地以及运输工具等信
息，然后确定目标函数，例如最小化运输成本或最大化运输效率。
2.建立模型：将物资配送问题转化为一个线性规划问题，使用变量表示物资的数
量、车辆的数量、车辆的容量以及运输路径等信息。
3.确定约束条件：考虑车辆容量、物资数量、目的地等因素对配送的影响，确定
相应的约束条件。
4.确定目标函数：根据问题和目标，确定目标函数，例如最小化运输成本或最大
化运输效率。
5.求解模型：使用线性规划求解器或者其他优化工具，求解模型并得到最优解。
防洪物资调运问题姓名：夏茂江学号：3320 姓名：吴帆学号：3320姓名：丁宇学号：3320摘要防洪物资调运问题实质是个运筹学网络规划中的最短路问题。
由于灾害发生时间和地点等各种因素的影响，具有较大随机性，我们结合实际情况，对其建立了相应的模型。
我们建的模型主要是考虑以最短时间或者最经济的调运方案将防洪物资进行分配，并且满足一定的要求。
使用图论的思想将交通网络图转化为数学图形，比用图论的方法求出各企业到各储备库和仓库的最经济的路线和最短的路线。
在进行物资调运的过程中，还是按照先满足储备库达到预测库存为目标一，使所有的仓库达到预测库存为目标二，让所有仓库和储备库达到最大库存为目标三分为三个阶段。
第一阶段可以假设有足够的能力一次性运达，第二阶段和第三阶段还要考虑企业的生产能力。
以上面的方法建立了模型，求得20天后的各库存量就比较容易了。
根据前面的建立的模型我们根据路程最短为原则选取路线算出20天后的各仓库包括储备库的库存量。
根据第问题二的调运方案中的调运路线看是否经过中断路段，如果不经过则调运方案时可行的，如果经过那么要考虑其它的线路，使路程最短，因为在汛期时间是第一目标。
我们可以再图论中把中断路段所对应的边去掉，这样直观、明了，便于我们查看、计算。
一、问题重述我国地域辽阔，气候多变，各种自然灾害频频发生，特别是每年在长江、淮河、嫩江等流域经常爆发不同程度的洪涝灾害，给国家和人民财产带来重大损失，防洪抗涝成为各级政府的一项重要工作。
某地区为做好今年的防洪抗涝工作，根据气象预报及历史经验，决定提前做好某种防洪抗涝物资的储备。
已知该地区有生产该物资的企业三家，大小物资仓库八个，国家级储备库两个，各库库存及需求情况见附件1，其分布情况见附件2。
经核算该物资的运输成本为高等级公路2元/公里百件，普通公路元/公里百件，假设各企业、物资仓库及国家级储备库之间的物资可以通过公路运输互相调运。
（1）请根据附件2提供的信息建立该地区公路交通网的数学模型。
（2）设计该物资合理的调运方案，包括调运量及调运线路，在重点保证国家级储备库的情况下，为给该地区有关部门做出科学决策提供依据。
（3）根据你的调运方案，20天后各库的库存量是多少（4）如果汛期下列路段因洪水交通中断，能否用问题二的模型解决紧急调运的问题，如果不能，请修改你的模型。
中断路段： ， ， ，附件1：各库库存及需求情况（单位：百件）1423 1125 26 27931附件2：生产企业，物资仓库及国家级储备库分布图高等级公路普通公路河流1231213等表示公路交汇点；30，50，28等表示公路区间距离，单位：公里，如与之间距离为80公里二、模型假设及符号说明1、模型假设1、假定该预测值是科学的可靠的；2、假设公路交汇点27为储备库1，交汇点30为储备库2；将交汇点15与28之间的交汇点9改为42；3、假设在整个生产过程中企业的生产不受限制，仓库的储存费、装卸费不考虑；4、假设在高级公路和普通公路的行驶速度相等且不变；5、为了表述方便假设将两储备库分别处理为仓库9、10；6、假设运输能力足够，能一次性把物资运达目的地。
2、符号说明x：表示企业i的现有库存；iz：表示仓库j的预测库存；jy：表示企业i向仓库j的调运量；ijl：表示处理后企业i到仓库j的最短路程；ij三、问题分析可以根据题目的数据信息得以分析出，把实际的图形问题转换为理想的纯数学图形，再根据图论的知识，想办法把理想的纯数学图形放在图论中加以假设从而得到可以求解的数学模型。
1、对于问题（1），其实就是把实际图形理论化，转化为我们数学上的图论问题。
把企业、仓库、储备库转化为相应的定点，点与点之间的公路用线条表述，路程得以标出。
2、对于问题（2），合理的调运方案包括最优的调运线路以及合适调运量。
根据提议可知还要首先保证国家储备库的条件下进行最优选配。
在建立方案时要考虑各企业库存和产量，各仓库的库存要求，特别是预测库存的重要性。
在以上条件下使总运费最少，从而就转化为一个线性规划的问题。
路线可以根据模型图统计出来。
3、对于问题（3），根据2的方案，再考虑每个企业的总的生产量，得出20天后的各点的库存量。
4、对于问题（4），根据2的调运方案，查看方案中的调运路线是否经过中断的路段，如果不经过，2的调运方案时可行的。
如果经过中断的路段，那就需要重新考虑其他的路线，就在模型中去掉中断的路段，再重复2的步骤求解。
四、模型的建立和求解1、关于问题（1）的模型建立和求解：根据题中给出的生产企业、物资仓库及国家级储备库分布图，建立该地区交通网数学模型，即用数学语言来描述各段公路的距离。
从题中的图形中我们可以得到42个公路交汇点，其中包括三个企业、八个仓库和两个储备库等。
两个顶点和他们之间直接连接的一条边线可以描述网络图中的一个基本组成单位。
例如：从1点出发可以分别只经过一次直接到2、33、34点，且各段的路程分别为40、60、45。
一次类推可以得到所有点的一次交通网，从而组成完整的交通网，当需要查询多次运输时，直接在这些一次的交通线上寻找连接一起即可。
公路交通网如下图形所表述：表1：2、关于问题（2）的模型建立和求解：由于洪水是难以预期的，有一定的随机性。
所以为了有效的防御，应该当在最短的时间保证各储备库和仓库达到预测库存，也就是说在储备库和仓库未达到预测库存之前以时间为第一目标函数建立模型。
而当他们都达到预测库存之后，各地区都有充足的防洪能力了，所以我们可以以经济为第一目标函数建立模型。
首先要对数据进行处理，把高级公路长度按运费折算成普通公路的等效长度。
例如：企业1（点24）到储备库2（点30）之间的一条线路：24-26-25-11-6-4-30中分别从左至右的路程分别为30、18、40、32、30、70，总路程为220。
但其中40和32是高级公路上的路程，由题可知高级公路单价为2元，普通公路为。
可以把这两个路程转化为普通公路路程（40+32）*2/=120 故这条线路上的总路程268。
以此类推用这种方法就可以让路程等效。
我们可以利用动态规划的顺序解法求解个两点间的路程最短的问题，以及最优路线。
我们以求解企业1—仓库2的最短路程为例： 局部简化线路图如图所示：（注：粗线表示高级公路）（1）、当k =1时， )(11s f =)24(1f =0, （2）、当k =2时， )26(2f =30， （3）、当k =3时，852830(26,19)(26)= )19(323=+=+d f f 481830(26,25)(26)= )25(323=+=+d f f（4）、当k =4时，80982.1/2*3048802258min )18,25()25()18,19()19(min )18(43434=⎭⎬⎫⎩⎨⎧=+=+=⎭⎬⎫⎩⎨⎧++=d f d f f（5）、当k =5时，1254580)23,18()18()23(545=+=+d f f ＝即最短路是24-26-19-18-23 路程是125以此类推可以求得各个企业到各仓库的等效路程最短的路线。
因为首先满足储备库，故首先考虑三个企业向储备库的调运，其次由于仓库3和仓库5现有库存超过预测库存，所以也要考虑仓库3和仓库5向储备库的调运。
表2：4530281830第一阶段：我们使储备库达到预测库存，由企业和超过预测库存的仓库3、5向储备库提供。
此阶段以总调运时间最小为目标，但我们前面已经假设了把高级公路和普通公路路程等效，速度都是相等的恒定值。
故要求总运调时间也就是总路程最短，且满足再最短路上调运量最大。
模型1的建立： 目标函数：总的调运时间最小，5211min ij iji j l y ===∑∑约束条件：各企业(包括仓库3、5)向外运输量不大于现有的库存量，()2ij j=1y i=12345i x ≤∑、、、、使储备库要达到预测库存，()5iji=1y12j z j ==∑、用LINGO 求解,得到第一阶段各企业向各储备库的具体分配量如下:表-3：第二阶段：使其他各个仓库达到预测库存。
通过分析第一阶段的结果，发现三个企业现存量已全部运完，仓库3刚好达到预测库存，而仓库5超过预测库存310。
通过公式（-=预测库存总量现有库存总量时间三个企业的日产量和）得到各库存都达到预测值时间为天，即至少需要8天。
然后我们把8天后各企业总产量处理为其在8天可调运的总量，建立以时间最少为目标的模型，得到每个企业向各仓库8天的总分配量。
模型2的建立： 目标函数:4811min ij ij i j l y ===∑∑约束条件：各企业(包括仓库5)向外运输量不大于现有的库存量，()8ij j=1y i=1234i x ≤∑、、、被运输的各仓库要达到预备库存，()4iji=1yj=12345678j z =∑、、、、、、、用LINGO 求解,得到第二阶段各企业向各仓库的具体分配量如下:表-4：第三阶段：在达到预测库存之后，该地区已经具备了防御一般洪水的能力，为了防御更大的洪水，应该使库存物资尽可能多。
通过公式（-=最大库存总量预测库存总量时间三个企业的日产量和）得到各库存都达到预测值时间为天，即至少需要39天。
然后我们把39天后各企业总产量处理为其在39天可调运的总量，建立以运费最少为目标的模型，由于高级公路长度按运费折算成普通公路的等效长度，故求单位物资的调运费最小即为路程为最短。
得到每个企业向各仓库39天的总分配量。
建立模型3如下： 目标函数：ij i j ij y l ∑∑===31101min约束条件：企业1、2、3在达到预测库存后39天向外运输的总量分别不应超过4039⨯、3039⨯、2039⨯，()1011,4039j y j =≤⨯∑()1012,3039j y j =≤⨯∑()1013,2039j y j =≤⨯∑各库存不超过其最大储存量，31ijj i ym =≤∑模型3求解的企业后期调运分配方案如下： 表-5：3、关于问题（3）的模型建立和求解：在问题（2）中我们已经求得了各企业在三个阶段向仓库的调运量，我们现在需要先求出每个企业20天后的生产量，根据（2）中的方案求得第20天后各个库的存储量。
我们认为有能力将现有库存及第一天的参量都运送出去，即第一天就能够使储备库达到预测库存值。
对于调运的先后顺序问题，在优先考虑储备库到达预测库存之后，我们考虑线路的路程，越短越先满足，以达到经济的目的。
前20天的分配方案如下表： 表-6：进而得到20天后各库存量分别为：表-7：4、关于问题（4）的模型建立和求解：在汛期时,相当于紧急调运。
与问题（2）的模型有所不同，此时，无论在什么情况下，都要以时间为第一目标，即要满足调运时所走路线的实际距离最短（不再把高级公路和普通公路等效）,不仅不用考虑调用的经济问题,而且不用考虑储备库优先的情况。
