防洪物资调运问题.docx

防洪物资调运问题一、 问题重述我国地域辽阔，气候多变，各种自然灾害频频发生，特别是每年在长江、淮河、 嫩江等流域经常爆发不同程度的洪涝灾害， 给国家和人民财产带来重大损失， 防洪抗 涝成为各级政府的一项重要工作。 某地区为做好今年的防洪抗涝工作， 根据气象预报 及历史经验，决定提前做好某种防洪抗涝物资的储备。已知该地区有生产该物资的企业三家，大小物资仓库八个，国家级储备库两个， 各库库存及需求情况见附件 1，其分布情况见附件 2。经核算该物资的运输成本为高 等级公路 2元/公里? 百件，普通公路元 /公里? 百件，假设各企业、物资仓库及国家 级储备库之间的物资可以通过公路运输互相调运。需解决的问题：（1）根据附件 2 中给出的生产企业、物资仓库及国家级储备库分布图，建立该地 区交通网数学模型。（2）在优先保证国家级储备库的情况下， 建立一种调运量及调运路线的方案模型。（3）根据自己所建立的调运方案，求出 20 天后各库存量。（4）汛期时，路段（ 14- 23、11-25、26-27、9-31 ） 被冲断，还能否用问题（ 2） 的模型解决此问题。若不能，再建立一种新模型。二、模型假设1. 假设每个储存库需求物资的预测值是科学的可靠的。2. 假设车辆在高等级公路和普通公路的调运速度相同3. 假设在一天内可运输货物量无上限。4. 假设公路交汇点 27 为储备库 1，交汇点 30 为储备库 2，将交汇点 15与 28 之 间的交汇点 9改为 42。5. 各存储库的物资储备量只有达到其预测值才有一定的防灾能力。问题分析问题一的分析对于本问题，要根据附件二提供的信息建立该地区的公路交通网的数学模型，首先 对附件二中的交通网络进行分析， 交通图中只有普通和高级公路两种且各个公路的交点 标号均已给出，且公路运费为高等级公路 2 元/ 公里? 百件，普通公路元 / 公里? 百件。 公路网是一种典型的网络模型， 因此我们可以采用图论的知识将交通图化为数学中的网 络图。以公路之间的交点为网络的顶点，以公路为网络中的边即可从原交通网中提取出 数学网络模型。考虑到题目中既给定了每段公路的长度又给定了公路的运费，因此我们 可以以各段公路的长度为网络中对应边的权值建立表示相邻两点之间距离的路径图， 也 可以以各段公路上每百件物资的运费为权值建立表示相邻两点之间每百件物资运费的 运费图。对于没有直接相连的节点可以将他们之间的权值设为无穷大。问题二的分析本题要求设计合理的物资调运方案，而且应该首先满足国家级储备库的需求。对题 目所给附件一进行分析在开始阶段每个企业以及存储库均有一定的库存量， 且企业生产 能力固定不变，各个存储库的现有量均超过其规定的最低库存，而且仓库 3 和 5 的现有 库存已大于其预测库存量。题目要求首先满足国家级储备库的需求，根据假设我们可以 在保证仓库 3 和 5 的库存量不小于其预测库存的情况下第一时间从企业 1 、2 、3 和仓 库3 、5向两个国家级储备库运送物资，使它们达到预测值，然后再考虑其它仓库的需 求即可。由于对一个固定地区每年洪涝灾害的发生有一定的季节性， ，即在时间段上可以分 为非汛期和汛期。因此我们分非汛期和汛期分别建立模型，求解出最优运输方案。在非 汛期时因为没有灾害发生只是进行物资的储备， 因此进行物资运输时应以总的运费最小 为目标；在汛期时由于紧急需要救灾物资，所以模型建立时应以时间最短为目标。问题三的分析由于第二问建立了两个运输方案模型， 所以根据第二问的模型我们可以求解出应用 两个模型进行物资运输时 20 天后各库的库存量情况。问题四的分析汛期有四条路段中断， 如果根据问题二的汛期模型结果进行货物运输时没有经过这 几条中断路径，则可以运用模型二解决紧急调运问题，但是若其结果经过这几条中断路 径，则只需要把问题二建立的模型中的这几条路之间的路程和费用改成无穷大再对模型 进行求解即可。四、符号说明五、模型建立及求解Aj由i地运往j地的物资运输量Bj每百件物资由i地运往j地的运输费Yi地的预测库存量Ri地的现有库存量Di企业每天的生产量（i=1,2,3）MAXjj地的取大库存量给三家企业、八个仓库和两个国家级储备库编号1至13(i 1,2, L ,13 j1,2, L ,13)建立问题一交通图的数学模型据问题分析将交通图化为数学中的网络图，以各个地点作为网络节点，对附件2中的公路交点进行假设处理，我们可以得出 42个节点，原图中有两个9号交点，我们令 右边的交点9为节点42,我们用顶点及边线图来描述这个交通网， 把两点之间路径用折 线简化替代分别以路程和运费为权值画出题目所给公路交通网的路径图和费用图分别 如图1和图2所示：5845仓库8017655222仓库72564522681850231950142858:业1363025461838708508040485627'备库11128125032仓32709265273048322(4140企.286038503042402936210355262854070仓库431仓企业36库362391545402560331026838仓983835仓库83537图116177862.415020仓库86.41125426.481.6186019606033.669.6:业17236132655.221.67684810096809611211133.61006464140931.262.43674057.638.428414896610企:33.656727650.4603680574.4仓库72042264.4608417048仓库431企业3636074.439185430487220481.645.6117.6835仓仓仓仓仓27储备库502850仓库 769.6/（亠 储备库 2一f仓54仓 229674.442储备库2图2注：图中红色字体标注的为仓库所在位置为各个仓库所在位置，绿色字体标注的为企业 所在位置，蓝色字体标注的为储备库所在位置 （标注右上方的储备库为 1, 右下方的为 2）， 图中圆圈表示公路交点（编号依次为 1-42 ）。问题二模型的建立与求解非汛期模型的建立与求解由于是在非汛期，时间相对充裕，应建立以运输费用最少的目标函数、仓库最大和 最小储备量为约束条件的线性规划模型。题目中要求要重点保护国家级储备库， 即当各个仓库还未达到预测库存量时两个国 家储备库要达到预测值，最终随时间推移，使得各个仓库和储备库的存储量至少达到预 测值。所以物资调运可以分两阶段进行，第一阶段先要使两个国家级储备库的存储量达 到预测库存，第二阶段使 8 个仓库的库存量达到预测库存。第一阶段 :使储备库达到预测库存：对题目中所给数据进行分析可知，两个储备库达到预测库存的需求量为 1700，三个 企业的现有库存为 1460，仓库3及仓库 5的现有库存都超过了它们的预测库存。 初步计算， 企业现存量和仓库超过预测的量能够满足储备库的需求。 储备库达到预测库存的需求量 由企业和超过预测库存的仓库 3、5向储备库提供。由假设可知每天的运输量没有上限， 所以在一天之内物资可以到达储备库。建立以三个企业、仓库 3、5 向储备库运输费用最小为目标的线性规划模型目标函数：运输费用minAij Bij （i=1,2,3,6,8 ；j=12,13 ）（1）约束条件：1调运到1储备库的总物资量等于其预测量与现有量的差值：A12 ¥2 R12 1000Q 123,6,8）i（2）2、调运到2储备库的总物资量等于其预测量与现有量的差值：A13 兀尺3700（i1,2,3,6,8）i（ 3）3、仓库3的调出量小于等于其现有量与预测库存量之差：13A6j Y6 Rs 150（ 4）j 124、仓库5的调出量小于等于其现有量与预测库存量之差：13A8j 丫8 R8 400（ 5）j 125、企业i的调出量小于等于其库存量13Aj R（i 1,2,3）j 12（ 6）利用lingo求解得到第一阶段的最小费用为 240796元，具体的调用路线、调运量以及第一阶段后每个地点的存储量如下表所示：表一：运往储备库1、2的运输路线及运输量储备库1路线储备库2路线企业160024-26-270/企业231041-6-40-275041-6-4-30企业30/50034-32-39-30仓库30/15035-32-39-30仓库59022-19-26-270/表二：第一阶段后每个地点的存储量仓库仓库仓库仓库仓库仓库仓库仓库储备储备12345678库1库220027030023071028039050030002500第二阶段考虑八个仓库:把三家企业每天的生产总量按需分配给 于等于预测库存量。1、2、4、6 7、8仓库，使它们的储存量大三家企业每天调运出的物资为Aj (j=4,5,11 )目标函数：总费用min n*(i3Ai4 Bi 413Ai5Bi5i 13A7B7i 1Ai9Bi93Ai10Bi10i 13Ai11Bi11)(7)约束条件:1、企业i , n天的总调出量不大于其生产量与现有库存量之和:(8)n*( A4 A5 Ai7 Ai9 A10 A11) Di * n R (i 1,2,3)2、n天内调运到仓库j物资量大于等于预测库存量减去现有库存量，小于等于最大库存量减去现有库存量3Y Rj n*Aj MAXj Rj(j 4,5,7,9,10,11)i 1(9)3、n为整数：n N利用lingo求解得到n=20天，第二阶段的最小费用为114312元，每个企业每天向各个仓库的运输量、运输路线以及第二阶段后的每个地点的库存量如下：表三：企业每天向各个仓库的运输量仓库仓库仓库仓库四仓库五仓库六仓库七仓库八企业一017000000企业二150000060企业三00060105表四：企业向每个仓库的运输路线企业一企业二企业三仓库一/41-9-28/仓库二24-26-19-18-23/仓库四/34-32-31仓库六/34-1-33-36仓库七/41-9-28-29/仓库八/34-32-38表五：第二阶段后每个地点的存储量仓库1仓库2仓库3仓库4仓库5仓库6仓库7仓库8储备库1储备库250061030035071030051060030002500汛期模型的建立与求解由于在汛期，应尽快将抗洪物资运往受灾地区，此时对抗洪物资的调运不能再以调 运费用作为讨论对象，而应以调运时间最少为目标。由于题目中提出要首先保证国家级储备库的储存量， 且假设中提出一天的运输量上 限不定。所以在一天内，国家级储备库的存量可达预测库存量。第一阶段使国家级储备库达到预测库存量分配方案与非汛期相同第二阶段：使各个仓库的库存量达到预测库存。目标函数：时间最短min n(10)约束条件：1、企业i , n天的总调出量不大于其生产量与现有库存量之和：n*( A4 A5 A7 A9 A10 A11) D i * n R(i 1,2,3)(伯)2、n天内调运到仓库j物资量大于等于预测库存量减去现有库存量，小于等于 最大库存量减去现有库存量3Yj Rj n* A MAXj Rj(j 4,5,7,9,10,11)i 1 (12)3、n为整数n N利用lingo求解得到第二阶段为n=10天，费用为127360元，贝U总时间为11天，每个 企业每天向各个仓库的运输量、运输路线以及第二阶段后的每个地点的库存量如下：表六：企业每天往仓库的运输量仓库仓库仓库仓库四仓库五仓库六仓库七仓库八企业一634000022企业二240000090企业三000120208表七：企业向每个仓库的运输方案企业一企业二企业三仓库一24-26-25-15-9-2841-9-2834-32-39-30-29-28仓库二24-26-25-18-23/仓库四/34-32-31仓库六/34-1-33-36仓库七24-26-25-11-6-4-2941-6-4-29/仓库八24-26-27-42-31-32-38/34-32-38表八：阶段二后每个地点的存储量仓库1仓库2仓库3仓库4仓库5仓库6仓库7仓库8储备库1储备库250061030035071030050060030002500第三阶段：使各个存储库达到最大存储量经过阶段二每个仓库以及两个储备库的库存量都至少达到了他们的预测值，此时各个仓库均已具备救灾能力，但是考虑到汛期对物资的需求比较紧迫因此在各个存储库均 达到预测库存的情况下，我们考虑第三阶段即三个企业继续生产物资，并且将物资不断 地运往存储库直到存储库达到其存储量的最大限度即可。由于经过阶段一和阶段二的调运各个储备库均已具备抗灾能力，所以在第三阶段进行货物调运时我们没有必要再以时 间最短为目标而应以如何安排物资调运使得装满各个存储库时总的运输费用最小。各个仓库以及储备库要想达到最大库存还需要补充的物资量如下表所示：表九：仓库剩余空间仓库仓库仓库仓库仓库仓库仓库仓库储备储备12345678库1库2剩余300290300502902001002001000500空间首先我们根据问题1所建立的费用图，将原交通网络图划分为三个部分。因为储备 库1、仓库2、仓库5与企业1之间运输单位量的物资费用最小，所以将他们划分为一个区 域，企业1以后时间段生产的物资按照运输费用由小到大的顺序依次向储备库1、仓库2、仓库5运送物资使他们的存储量分别达到最大既可停止生产，而不再向其他存储库调用 物资。同理将企业2和仓库1、7划分为一个区域，仓库2只需负责向仓库1和7调运物资使 他们分别达到最大库存既可，企业3只需依次向仓库4、仓库8、储备库2、仓库3和仓库6 运送物资使他们的库存量依次达到上限既可停止生产。表十：企业向其负责存储库运送物资的先后顺序企业企业按费用最小依次需要填满的储存库顺序1储备库1仓库2仓库52仓库1 仓库73仓库4仓库8储备库2仓库3仓库6因为企业1现在库存量为零，且其产量为 40/天，要将储备库一、仓库二和仓库五 全部存满总共需要1580,所以企业一至少还需生产天。同理企业二还需生产天，企业三 还需生产天。问题三的求解对于问题二的非汛期模型非汛期是以最小费用为目标的规划模型，第一阶段与第二阶段合起来总共的调运天 数为21天，所以只需在第二问得出的8个仓库2个储备库21天后的现有库存量减去一 天的物资调运量既可得出非汛期 20天后2个储备库以及8个仓库的储存量如下表所示表一 ：非汛期 20天后各个地点的存储量仓库仓库仓库仓库仓库仓库仓库仓库储备储备12345678库1库250061030035071030050060030002500汛期汛期是以最短时间为目标的规划模型，第一阶段、第二阶段都与问题二中的汛期相 同。第11天当每个仓库的库存量已经达到预测库存量，该地区已经有一定的防备洪水的 能力，在此基础上按第二问建立的汛期物资调晕模型的第三阶段物资调运方案，可得到 知在接下来的9天时间里，企业1还能生产360百件物资，企业2还能生产270百件物资， 企业3还能生产180百件物资。由于储备库1的剩余库容量为1000,所以企业1在9天时间 里生产的360百件物资可以全部运往储备库1，这样储备库1的库存量变为3360.由于仓库 1的剩余库容量为300,所以企业2生产的270百件物资可以全部运往仓库1。，这样仓库1 的库存量变为770.由于仓库4剩余库容量为40,所以在这9天的前两天企业3生产的物资 全部调往仓库4使其存储量达到最大，接着7天生产的140百件物资全部调往仓库8既可。 最后得出20天后2个储备库，以及8个仓库的物资存储量如下表所示：表十二：汛期20天后各个地点的存储量仓库1仓库2仓库3仓库4仓库5仓库6仓库7仓库8储备库1储备库277061030040071030050074033602500问题四模型的建立与求解由于洪水造成部分公路交通中断，中断道路为14-23、11-25、26- 27、9-31，只需把这四段道路的权值设置为无穷大重新利用弗洛伊德算法计算任意两点间的最短路径，依然采用第二问建立的汛期的模型分三个阶段计算，阶段一的运费为320380元，其运输方案见下表。表十三：运往储备库 1、2的运输路线及运输量储备库1路线储备库2路线企业160024-20-13-270/企业231041-6-40-275041-6-4-30企业30/50034-32-39-30仓库30/15035-32-39-30仓库59022-20-13-270/阶段二中以最短时间为目标函数的模型，该阶段耗时10天，运费为133320元，两阶段运费共计453700元，其调运方案见下表：表十四：企业每天往仓库的运输量仓库仓库仓库仓库四仓库五仓库六仓库七仓库八企业一633000023企业二240000090企业三000130207表十五：企业向每个仓库的运输路线企业一企业二企业三仓库一24-26-25-15-9-2841-9-28/仓库二24-26-25-18-23/仓库四/34-32-31仓库六/34-1-33-36仓库七24-26-25-15-9-28-2941-6-4-29/仓库八24-26-25-15-9/34-32-3828-29-30-39-32-38表十六：阶段二后每个地点的存储量仓库仓库仓库仓库仓库仓库仓库仓库储备储备12345678库1库250060030036071030050060030002500阶段三：在阶段二使得各个存储库达到其预测值之后，我们就可以按照费用最小原 则来进行物资的进一步储备，使得各存储库的物资量达到最大值。各个仓库以及储备库要想达到最大库存还需要补充的物资量如下表所示:表十七：仓库剩余空间仓库1仓库2仓库3仓库4仓库5仓库6仓库7仓库8储备库1储备库2剩余空间300300300402902001002001000500仍然把最小费用图新的最小费用图划分成三部分。因为储备库 1、仓库2、仓库5与 企业1之间运输单位量的物资费用最小，所以将他们划分为一个区域；将企业 2和仓库1、 7划分为一个区域；将企业3和仓库4、仓库8、储备库2、仓库3和仓库6划分为一个区域。表十八：企业向其负责存储库运送物资的先后顺序企业企业按费用最小依次需要填满的储存库顺序1储备库1仓库2仓库52仓库1 仓库73仓库4仓库8储备库2仓库3仓库6因为企业1现在库存量为零，且其产量为40百件/天，要将储备库一、仓库二和仓 库五全部存满总共需要1590百件，所以企业一至少还需生产天。同理企业二还需生产 天，企业三还需生产62天。六、模型评价及推广模型的优点：在本篇论文里，我们首先能合理将实际中的网络转换成数学中的网络图模型，使得对实际问题的解决更加容易。在求解具体问题时我们采用线性规划，对现实中可能发生的不同情况，针对性的建立了不同侧重点的数学模型，而且每个模型中都根据实际需要进行了分阶段考虑。模型的实用性比较强，利用计算机编程，对于模型结果的求解也非 常快。模型的缺点：本文在建立模型的过程中假设高级公路和普通公路的物资调用没有差别， 而且对车 速也没有任何限制。但实际中高级公路的运输速度肯定比普通公路大，所以模型还需要 进一步的改进，需要进一步考虑两种公路运输速度问题，对不同公路上的车速赋予不同 权值，这样建立的模型就会更符合实际。模型的推广对于本文中我们建立的救灾物资的运输问题，可以应用到其他许多领域：比如，某 个地区需要引进自来水，自来水公司就需要考虑怎样进行各个用户之间水管的布置，以 便使其既能满足用户需求又能最大程度的节省费用问题可以应用本题中建立的网络图 模型，求解出相应节点的最短路既可，但此时还得考虑水管铺设并不一定严格按照最短 路去铺设，还有可能在地下走捷径进行水管铺设，网络公司对用户家庭进行网线的布置 也与此类似。还有厂家生产商品再调运到各个分店去销售的问题，也可用此模型进行解 决，只需改变约束，就可以应用此模型。七、参考文献123运筹学教材编写组，运筹学（修订版） ，清华大学出版社， 傅英定，成孝予，唐应辉，最优化理论与方法，北京：国防工业出版社， 殷剑宏，吴开亚，图论及其算法，合肥：中国科学技术大学出版社，4韩中庚，数学建模方法及其应用，高等教育出版社，