防洪物资调运问题

《防洪物资调运问题》由会员分享，可在线阅读，更多相关《防洪物资调运问题（10页珍藏版）》请在装配图网上搜索。

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

2、据附件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各存储库的物

3、资储备量只有达到其预测值才有一定的防灾能力。二、问题分析3.1问题一的分析对于本问题，要根据附件二提供的信息建立该地区的公路交通网的数学模型，首先对附件二中 的交通网络进行分析，交通图中只有普通和高级公路两种且各个公路的交点标号均已给出，且公路 运费为高等级公路2元/公里?百件，普通公路1.2元/公里?百件。公路网是一种典型的网络模型, 因此我们可以采用图论的知识将交通图化为数学中的网络图。以公路之间的交点为网络的顶点，以 公路为网络中的边即可从原交通网中提取出数学网络模型。考虑到题目中既给定了每段公路的长度 又给定了公路的运费，因此我们可以以各段公路的长度为网络中对应边的权值建立表示相邻两点

4、之 间距离的路径图，也可以以各段公路上每百件物资的运费为权值建立表示相邻两点之间每百件物资 运费的运费图。对于没有直接相连的节点可以将他们之间的权值设为无穷大。精心整理3.2 问题二的分析本 设计合 资调运 而且应 满足国 备库的 对题目 件一进 在开始 个企业 储库均 的库存 企业生 固定不 个存储由i地运往j地的物资运输量每百件物资由i地运往j地的运输费i地的预测库存量i地的现有库存里企业每天的生产量（i=1,2,3）j地的最大库存里题要求理的物该首先 家级储 需求。 所给附 行分析 阶段每 以及存 有一定 量，且 产能力 变，各 库的现有量均超过其规定的最低库存，而且仓库3和5的现有库存

5、已大于其预测库存量。题目要求首先满 足国家级储备库的需求，根据假设我们可以在保证仓库3和5的库存量不小于其预测库存的情况下 第一时间从企业1、2、3和仓库3、5向两个国家级储备库运送物资，使它们达到预测值，然后再 考虑其它仓库的需求即可。由于对一个固定地区每年洪涝灾害的发生有一定的季节性,，即在时间段上可以分为非汛期和 汛期。因此我们分非汛期和汛期分别建立模型，求解出最优运输方案。在非汛期时因为没有灾害发 生只是进行物资的储备，因此进行物资运输时应以总的运费最小为目标；在汛期时由于紧急需要救 灾物资，所以模型建立时应以时间最短为目标。3. 3问题三的分析由于第二问建立了两个运输方案模型,所以根

6、据第二问的模型我们可以求解出应用两个模型进 行物资运输时20天后各库的库存量情况。3. 4问题四的分析汛期有四条路段中断，如果根据问题二的汛期模型结果进行货物运输时没有经过这几条中断路 径，则可以运用模型二解决紧急调运问题，但是若其结果经过这几条中断路径，则只需要把问题二 建立的模型中的这几条路之间的路程和费用改成无穷大再对模型进行求解即可。四、符号说明精心整理给三家企业、八个仓库和两个国家级储备库编号1至13 （ i二1,2,13j 二 1,2,13）五、模型建立及求解5.1 建立问题一交通图的数学模型据问题分析将交通图化为数学中的网络图，以各个地点作为网络节点，对附件 2 中的公路交点进行

7、假设处理，我们可以得出42个节点，原图中有两个9号交点，我们令右边的交点9为节点42, 我们用顶点及边线图来描述这个交通网，把两点之间路径用折线简化替代分别以路程和运费为权值 画出题目所给公路交通网的路径图和费用图分别如图1和图2所示：58仓80751172452268505001838804827270652304832402；28385030406252506270854062115454025601023835企业2企业11436仓库7仓库- 30储备库 231仓库450-6 -2838仓库858461928465仓 图错误！未指定顺序。图2 注：图中红色字体标注的为仓库所在位置为各个仓

8、库所在位置，绿色字体标注的为企业所在位置， 蓝色字体标注的为储备库所在位置（标注右上方的储备库为 1,右下方的为2），图中圆圈表示公路 交点（编号依次为 1-42）。5.2 问题二模型的建立与求解5.2.1 非汛期模型的建立与求解由于是在非汛期，时间相对充裕，应建立以运输费用最少的目标函数、仓库最大和最小储备量 为约束条件的线性规划模型。精心整理 题目中要求要重点保护国家级储备库，即当各个仓库还未达到预测库存量时两个国家储备库要 达到预测值，最终随时间推移，使得各个仓库和储备库的存储量至少达到预测值。所以物资调运可 以分两阶段进行，第一阶段先要使两个国家级储备库的存储量达到预测库存，第二阶段使

9、 8 个仓库 的库存量达到预测库存。第一阶段:使储备库达到预测库存：对题目中所给数据进行分析可知，两个储备库达到预测库存的需求量为1700，三个企业的现有 库存为1460，仓库3及仓库5的现有库存都超过了它们的预测库存。初步计算，企业现存量和仓库超 过预测的量能够满足储备库的需求。储备库达到预测库存的需求量由企业和超过预测库存的仓库3、 5向储备库提供。由假设可知每天的运输量没有上限，所以在一天之内物资可以到达储备库。建立以三个企业、仓库3、5向储备库运输费用最小为目标的线性规划模型目标函数：运输费用min = W人代(i=l,2,3,6,8; j=12,13)(1)ij j约束条件：1、调运

10、到1储备库的总物资量等于其预测量与现有量的差值:工A 二 Y - R 二 1000(i 二 1,2,3,6,8)i121212i(2 )2、调运到2储备库的总物资量等于其预测量与现有量的差值:LA 二 Y - R 二 700(i 二 1,2,3,6,8)i(3 )3、仓库3的调出量小于等于其现有量与预测库存量之差：L A Y -R = 150(4)6 j66j=124、仓库5的调出量小于等于其现有量与预测库存量之差：LA Y R = 400(5)8 j88j=125、企业i的调出量小于等于其库存量L A R (i = 1,2,3)ij i,、j=12(6)利用lingo求解得到第一阶段的最小费

11、用为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/表二：第一阶段后每个地点的存储量精心整理仓库1仓库2仓库3仓库4仓库5仓库6仓库7仓库8储备库1储备 库220027030023071028039050030002500第二阶段考虑八个仓库：把三家企业每天的生产总量按需分配给1、2、4、6、7、8仓库

12、，使它们的储存量大于等于预测 库存量。三家企业每天调运出的物资为工A、工A、工A (j=4,5,，ll)1j2j3 j目标函数：总费用(7)约束条件：1、企业i, n天的总调出量不大于其生产量与现有库存量之和：n *(A + A + A + A + A + A ) D *n + R (i = 1,2,3)i 4i5i 7i9i10illii(8)2、n天内调运到仓库j物资量大于等于预测库存量减去现有库存量，小于等于最大库 存量减去现有库存量Y - R n * A MAX - R (j = 4,5,7,9,10,11) j j ij j ji=13、n为整数:利用lingo求解得到n=20天，第

13、二阶段的最小费用为114312元，每个企业每天向各个仓库的运 输量、运输路线以及第二阶段后的每个地点的库存量如下：表三：企业每天向各个仓库的运输量仓库仓库仓库仓库四仓库五仓库 六仓库 七仓库八企业一017000000企业二150000060企业三00060105表四：企业向每个仓库的运输路线企业一企业二企业三仓库一/41-9-28/仓库二24-26T9-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储备库2500610300350710

14、300510600300025005.2.2汛期模型的建立与求解精心整理 由于在汛期，应尽快将抗洪物资运往受灾地区，此时对抗洪物资的调运不能再以调运费用作为 讨论对象，而应以调运时间最少为目标。由于题目中提出要首先保证国家级储备库的储存量，且假设中提出一天的运输量上限不定。所 以在一天内，国家级储备库的存量可达预测库存量。第一阶段使国家级储备库达到预测库存量分配 方案与非汛期相同。第二阶段:使各个仓库的库存量达到预测库存。目标函数：时间最短min 二 n（0）约束条件:1、企业i, n天的总调出量不大于其生产量与现有库存量之和：n *（A + A + A + A + A + A ） D *n

15、+ R （i = 1,2,3）i 4i5i 7i9i10illii（ 11）2、n天内调运到仓库j物资量大于等于预测库存量减去现有库存量，小于等于最大库存 量减去现有库存量（Y - R n * A MAX - R (j = 4,5,7,9,10,11) j jjj ji=13、n为整数利用lingo求解得到第二阶段为n=10天，费用为127360元，则总时间为11天，每个企业每天向 各个仓库的运输量、运输路线以及第二阶段后的每个地点的库存量如下：表六：企业每天往仓库的运输量仓库仓库仓库仓库四仓库五仓库 六仓库 七仓库八企业一634000022企业二240000090企业三000120208表七

16、：企业向每个仓库的运输方案企业一企业二企业三仓库一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精心整理第三阶段:使各个存储库达到最大存储量经过阶段二每个仓库以及两个储备库的库存量都至少达到了

17、他们的预测值，此时各个仓库均已 具备救灾能力，但是考虑到汛期对物资的需求比较紧迫因此在各个存储库均达到预测库存的情况下 我们考虑第三阶段即三个企业继续生产物资，并且将物资不断地运往存储库直到存储库达到其存储 量的最大限度即可。由于经过阶段一和阶段二的调运各个储备库均已具备抗灾能力，所以在第三阶 段进行货物调运时我们没有必要再以时间最短为目标而应以如何安排物资调运使得装满各个存储 库时总的运输费用最小。各个仓库以及储备库要想达到最大库存还需要补充的物资量如下表所示：表九：仓库剩余空间仓库1仓库2仓库3仓库4仓库5仓库6仓库7仓库8储备库1储备 库2剩余 空间3002903005029020010

18、02001000500首先我们根据问题1所建立的费用图，将原交通网络图划分为三个部分。因为储备库1、仓库2、 仓库5与企业1之间运输单位量的物资费用最小，所以将他们划分为一个区域，企业1以后时间段生 产的物资按照运输费用由小到大的顺序依次向储备库1、仓库2、仓库5运送物资使他们的存储量分 别达到最大既可停止生产，而不再向其他存储库调用物资。同理将企业2和仓库1、7划分为一个区 域，仓库2只需负责向仓库1和7调运物资使他们分别达到最大库存既可，企业3只需依次向仓库4、 仓库8、储备库2、仓库3和仓库6运送物资使他们的库存量依次达到上限既可停止生产。表十：企业向其负责存储库运送物资的先后顺序企业企

19、业按费用最小依次需要填满的储存库顺序1储备库1&仓库2&仓库52仓库1&仓库73仓库4&仓库8$储备库2&仓库3&仓库6因为企业1现在库存量为零，且其产量为40/天，要将储备库一、仓库二和仓库五全部存满总 共需要1580，所以企业一至少还需生产39.5天。同理企业二还需生产13.3天，企业三还需生产 62.5 天。5.3问题三的求解5. 31对于问题二的非汛期模型非汛期是以最小费用为目标的规划模型，第一阶段与第二阶段合起来总共的调运天数为 21 天， 所以只需在第二问得出的8 个仓库2 个储备库21 天后的现有库存量减去一天的物资调运量既可得 出非汛期20天后2 个储备库以及8 个仓库的储存量

20、如下表所示表十一：非汛期20天后各个地点的存储量仓库1仓库2仓库3仓库4仓库5仓库6仓库7仓库8储备库1储备 库250061030035071030050060030002500精心整理5.3.2汛期汛期是以最短时间为目标的规划模型，第一阶段、第二阶段都与问题二中的汛期相同。第11 天当每个仓库的库存量已经达到预测库存量，该地区已经有一定的防备洪水的能力，在此基础上按 第二问建立的汛期物资调晕模型的第三阶段物资调运方案，可得到知在接下来的9天时间里，企业1 还能生产360百件物资，企业2还能生产270百件物资，企业3还能生产180百件物资。由于储备库1 的剩余库容量为1000，所以企业1在9天

21、时间里生产的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储备 库2770610300400710300500740336025005.4问题四模型的建

22、立与求解由于洪水造成部分公路交通中断，中断道路为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天，运

23、费为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-25T5-928-29-30-39-32-38/34-32-38-六：阶段二后每个地点的存F储量仓库

24、1仓库2仓库3仓库4仓库5仓库6仓库7仓库8储备库1储备库250060030036071030050060030002500阶段三：在阶段二使得各个存储库达到其预测值之后，我们就可以按照费用最小原则来进行物 资的进一步储备，使得各存储库的物资量达到最大值。各个仓库以及储备库要想达到最大库存还需要补充的物资量如下表所示：表十七：仓库剩余空间仓库1仓库2仓库3仓库4仓库5仓库6仓库7仓库8储备库1储备 库2剩余空间300300300402902001002001000500仍然把最小费用图新的最小费用图划分成三部分。因为储备库1、仓库2、仓库5与企业1之间运 输单位量的物资费用最小，所以将他们划分

25、为一个区域；将企业2和仓库1、7划分为一个区域；将 企业3和仓库4、仓库8、储备库2、仓库3和仓库6划分为一个区域。表十八：企业向其负责存储库运送物资的先后顺序企业企业按费用最小依次需要填满的储存库顺序1储备库1&仓库2&仓库52仓库1&仓库73仓库4&仓库8$储备库2&仓库3&仓库6因为企业1现在库存量为零，且其产量为40百件/天，要将储备库一、仓库二和仓库五全部存 满总共需要1590百件，所以企业一至少还需生产39.75天。同理企业二还需生产13.3天，企业三 还需生产62天。六、模型评价及推广6.1 模型的优点：在本篇论文里，我们首先能合理将实际中的网络转换成数学中的网络图模型，使得对实

26、际问题 的解决更加容易。在求解具体问题时我们采用线性规划，对现实中可能发生的不同情况，针对性的 建立了不同侧重点的数学模型，而且每个模型中都根据实际需要进行了分阶段考虑。模型的实用性 比较强，利用计算机编程，对于模型结果的求解也非常快。6.2 模型的缺点：本文在建立模型的过程中假设高级公路和普通公路的物资调用没有差别，而且对车速也没有任 何限制。但实际中高级公路的运输速度肯定比普通公路大，所以模型还需要进一步的改进，需要进 精心整理 一步考虑两种公路运输速度问题，对不同公路上的车速赋予不同权值，这样建立的模型就会更符合 实际。6.3 模型的推广对于本文中我们建立的救灾物资的运输问题，可以应用到

27、其他许多领域：比如，某个地区需要 引进自来水，自来水公司就需要考虑怎样进行各个用户之间水管的布置，以便使其既能满足用户需 求又能最大程度的节省费用问题可以应用本题中建立的网络图模型，求解出相应节点的最短路既可 但此时还得考虑水管铺设并不一定严格按照最短路去铺设，还有可能在地下走捷径进行水管铺设， 网络公司对用户家庭进行网线的布置也与此类似。还有厂家生产商品再调运到各个分店去销售的问 题，也可用此模型进行解决，只需改变约束，就可以应用此模型。七、参考文献1 运筹学教材编写组，运筹学（修订版），清华大学出版社，2004.92 傅英定，成孝予，唐应辉，最优化理论与方法，北京：国防工业出版社，2008.63 殷剑宏，吴开亚，图论及其算法，合肥：中国科学技术大学出版社，2003.74 韩中庚，数学建模方法及其应用，高等教育出版社，2005.6