防洪物资调运问题分析1.doc

2012 集美大学数学建模竞赛承 诺 书我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。所属学院（请填写完整的全名）： 集美大学理学院 参赛队员 (打印并签名) ：1. 朱伟 2. 卢进铭 3. 杨志强 日期： 2012 年 8 月 22 日2012集美大学数学建模竞赛编 号 专 用 页评阅编号：评阅记录：评阅人评分备注C题 防洪物资调运问题分析摘 要我国地域辽阔，气候多变，近几年各种自然灾害的频发使得如何建立科学的防洪物资调运方案更是刻不容缓。本文主要研究防洪物资调运的问题，在以图论、统筹规划知识为基础并综合word、lingo软件建立了公路交通网数学模型、最少天数调运模型和最小费用调运模型，并对问题进行了分析。问题一：利用word的绘图工具结合附件1的信息建立公路交通网数学模型。问题二：重点保护储备库的调运数学模型即储备库库存达到最大库存，各仓库库存达到预测库存的模型。首先根据分布图将最优路线找出，运用lingo软件建立最少天数调运模型和最小费用调运模型，并根据现实情况选择。问题三：将数据20天代入最少天数调运模型和最小费用调运模型即可得出。问题四：从问题二的数学模型可以找出调运路线，运用word软件找出是否包含中断路线，若包含则只需重新找出最优路线，并在问题二的数学模型上重修修改数学模型即可。关键词：调运路线；库存量；调运量；1、 问题重述1、问题背景长期以来自然灾害的频发给国家和人民财产带来的损失已不容小觑，尤其是近几年的洪涝问题更是迫在眉睫。如何做好防洪物资调运，最大程度的保障国家和人民生命财产并减小洪涝灾害带来的损失已成为各级政府的一项重要任务。2、 提出问题（1）请根据信息建立该地区公路交通网的数学模型。（2）设计该物资合理的调运方案，包括调运量及调运线路，在重点保证国家级储备库 的情况下，为给该地区有关部门做出科学决策提供依据。（3）根据你的调运方案，20天后各库的库存量是多少？311423927262511（4）如果汛期下列路段因洪水交通中断，能否用问题二的模型解决紧急调运的问题， 如果不能，请修改你的模型。中断路段： ， ， ， 二、问题分析问题1：本体的关键是运用公路交通网数学模型分析最优调运路线，我们利用word的绘图工具并结合附件1的信息建立公路交通网数学模型。 问题2：从现实生活中可知，科学决策的调运方案应该是使得调运费用最少，于是我们必须先找出个点之间的最优路线即运输费用最少路线。假设所有调运都能在当天完成，为了重点保证国家级储备库，则必须保证储备库的库存量达到最大库存量，其余仓库只需达到预测库存量即可。从数据可得出仓库3和仓库5的现有库存量大于预测库存量，于是便考虑仓库3和5是否调运给仓库货储备库。1）最短天数模型（附件1）：由于天数最短，即仓库3和仓库5的多余库存便往外调运，于是在用lingo建立模型时必须增加仓库3和5的多余库存量全部调运的约束条件。另外根据数据可以算出最短天数为24.天，于是便可假设天数为25天，大概知道企业1、2、3的物资总量（现有库存+生产量）。在最短天数已知前提建立模型寻找费用最低的调运方案。2）最小费用模型（附件2）：经过比较可知仓库3和仓库5调运到仓库或储备库的费用均大于企业调运到仓库或储备库的费用，于是为了得出最小费用仓库3和仓库5可不进行调运。在比较3个企业调运到各仓库和储备库的费用，各仓库和储备库的调运均由3个企业中调运费用最小的企业负责。由于不考虑天数，于是我们便给3个企业的总库存量（现有库存+总生产量）赋很大的值（保证库存量能满足完成调运任务）。 问题3：1） 最短天数模型：由于20天时还未完成任务，于是我们只需将20天时3个企业的总库存量算出，并代入数据，运行模型即可得出答案。2） 最小费用模型：由问题二的最小费用模型可得出20天时各企业的总库存量，代入数据，运行模型即可得出答案。问题4：从问题2的两个数学模型可以找出调运路线，运用word分别找出两个模型的调运路线中是否包含中断路线，若包含则只需重新找出最优路线，并在问题二的数学模型上修改数据即可。若不包含中端路线则模型仍然适用。三、模型假设（1）所有运输在一天内都可抵达。（2）运输过程中没有突发状况的发生。（3）当天生产时间可忽略不计。（3）运输过程中不会产生额外的费用。（4）企业生产产生的费用可忽略不计。（5）企业每天的产量可不达到最大值。4、 符号说明 天数 费用 企业的总调运量 企业 的现有库存 仓库 的现有库存 储备库 的现有库存 仓库 的预测库存 储备库 的最大库存 企业 每天的产量 企业 的总量五、模型建立与求解问题一： 交通网数学模型问题二：最优路线即运输费用最少路线。根据分布图计算得表1、表2、表3。表1 调运到储备库的线路与费用储备库1储备库2企业1路线：24+20+13+27费用：241.6路线：24+26+19+18+15+42+28+29+30费用：312企业2路线：24+26+19+18+15+42+28+29+30费用：157.6 路线：41+6+4+30费用：177.6企业3路线：34+1+2+9+27费用：224.4路线：34+32+39+30费用：122.4仓库1路线：28+42+41+6+40+27费用：227路线：28+29+30费用：146.4仓库2路线：23+18+19+15+11+27 费用：331.6路线：23+18+19+15+11+27 费用：342仓库3路线：35+32+34+1+2+9+27费用：372路线：35+32+39+30费用：210仓库4路线：31+32+34+1+2+9+27 费用：254.4路线：31+32+39+30费用：152.4仓库5路线：22+20+13+27费用：277.6路线：22+19+18+15+42+28+29+30费用：400.8仓库6路线：6+3+2+9+27费用：224.4路线：36+33+1+34+32+39+30费用：296.4仓库7路线：29+4+6+40+27费用：216路线：29+30费用：74.4仓库8路线：38+32+34+1+2+9+27费用：336路线：38+32+39+30费用：174表2 企业调运到各仓库路线和费用企业1仓库1路线：24+26+25+15+42+28费用：156仓库2路线：24+26+19+18+23 费用：150仓库3路线：24+26+25+15+42+28+29+30+39+32+35费用：224.4仓库4路线：24+26+25+15+42+41+28+29+30+39+32+31费用：483.6仓库5路线：224+26+19+22 费用：156仓库6路线：24+20+13+12+10+3+36费用：410.4仓库7路线：24+26+25+15+42+28+29 费用：256.8仓库8路线：24+26+25+15+42+28+29+30+32+38费用：505.2企业2仓库1路线：41+4+28费用：69.6仓库2路线：41+42+15+18+23费用：188.4仓库3路线：41+6+4+30+39+32+35费用：394.8仓库4路线：41+6+4+30+39+32+31费用：348仓库5路线：41+42+15+18+19 费用：160.8仓库6路线：41+6+40+9+2+3+36费用：303.6仓库7路线：41+42+28+29 费用：141.6仓库8路线：41+6+4+30+39+32+38费用：382.8企业3仓库1路线：34+32+39+30+29+28费用：268.8仓库2路线：34+32+39+30+4+6+41+41+42+15+18+23费用：488.4仓库3路线：34+32+35费用：147.6仓库4路线：24+32+31费用：90仓库5路线：34+32+39+30+4+6+41+42+15+18+19+22费用：463.2仓库6路线：34+1+33+36费用：174仓库7路线：34+1+2+7 费用：196.8仓库8路线：34+32+38 费用：111.6表3 仓库3、5到各仓库路线和费用仓库3仓库5仓库1路线：35+32+39+30+29+28费用：356.4路线：22+19+!8+15+42+28费用：254.4仓库2路线：35+32+39+30+4+6+41+42+15+18+23 费用：558 路线：22+19+18+23 费用：166.8仓库4路线：35+32+31费用：174路线：22+20+13+12+10+3+2+1+34+32+31费用：620.4仓库6路线：35+32+34+1+33+36 费用：321.6 路线：22+20+13+12+10+3+36 费用：446.4仓库7路线：35+32+39+30+29 费用：156路线：22+19+26+25+15+42+28+29 费用：340.8仓库8路线：35+32+38 费用：199.2路线：22+20+13+12+10+3+36+33+37+38 费用：582假设所有调运都能在当天完成，为了重点保证国家级储备库，则必须要求保证储备库的库存量达到最大库存量，其余仓库只需达到预测库存量即可。从数据可得出仓库3和仓库5的现有库存量大于预测库存量，于是便考虑仓库3和5是否调运给仓库和储备库。1） 最短天数模型：求，得=3，5。即仓库3和仓库5多余的库存需要向外调运， ， 得仓库3向外调运150，仓库5向外调运400。根据公式： 最短天数= 代入数据求得最短天数为24.天，于是便可假设天数=25。企业1、2、3的总量： （现有库存+生产总量） 解得 = 1600， =1100， =1000运用lingo软件建立最短天数数学模型（附件1），求得调运量（表4）仓库1仓库2仓库4仓库6仓库7仓库8储备1储备2企业100000016000企业23000001100330290企业3000200700910仓库300120003000仓库503300000700需求3003301202011010020001200表4 最短天数调运量调运路线请结合表1、2、3、4查看。 结合表1、表2、表3、表4的数据可以求得最短天数的最小费用550824。2） 最小费用模型从表2和表3的数据比较得仓库3和仓库5调运到仓库或储备库的费用均大于企业调运到仓库或储备库的费用，为了得到最小费用仓库3和仓库5可不进行调运。给3个企业的总库存量赋值。运用lingo软件建立最小最小费用数学模型（附件2），求得调运量（表5） 仓库1仓库2仓库4仓库6仓库7仓库8储备1储备2生产量企业103300000200002330企业2300000110000410企业300120200100012001440仓库3000000000仓库5000000000需求量30033012020110100200012004180表5 最小费用调运量调运路线请结合表1、2、3、4查看。 结合表1、表2、表3、表6的数据可以求得最小费用=498276。问题三：1) 最短天数模型：20天时3个企业的总库存量: ()解得，。将数据代入模型求得调运量（表6）仓库1仓库2仓库4仓库6仓库7仓库8储备1储备2生产量企业1000000140001400企业2300000110053020960企业300000700830900仓库300120003000150仓库503300000700400需求300330120011010020008502910表6 最短天数模型20天调运量因此可得各库的库存量（表7）仓库1仓库2仓库3仓库4仓库5仓库6仓库7仓库8储备库1储备库2库存500600300350400280500600400026502）最小费用模型：从问题二的最小费用模型可得出企业 的总调运量 企业 生产天数： 解得， ， 因为，所以20天时3个企业的总库存量: 由 （）， 得，。 将数据代入模型得求得调运量（表8），仓库1仓库2仓库4仓库6仓库7仓库8储备1储备2生产量企业1000000140001400企业2300000110000410企业300120001000680900仓库3000000000仓库5000000000需求量3000120011010014006802710表8 最小费用模型20天调运量因此可得各库的库存量（表9）仓库1仓库2仓库3仓库4仓库5仓库6仓库7仓库8储备库1储备库2库存50027045035080028050060034002480问题四：将4个中断路线结合问题2的2个模型路线查看。1） 最短天数模型： 可得以下路线受到影响： 企业1储备库1 24+26+27 (30+70)*1.2=120企业3储备库1 34+32+31+9+27 (25+50+52+40)*1.2=200.4仓库3储备库1 35+32+31+9+27 (98+50+52+40)*1.2=288仓库5储备库1 22+19+26+27 (72+28+70)*1.2=204企业1储备库2 24+26+27+40+6+4+30 (30+70+30+30+70)*1.2+32*2=340企业1仓库4 24+26+27+9+31 （30+70+40+52）*1.2=230.4企业1仓库6 24+26+27+9+2+3+36 （30+70+40+62+35+50）*1.2=344.4企业1仓库8 24+26+27+9+31+32+38 （30+70+40+52+50+68）*1.2=372企业2仓库4 41+6+40+9+31 （48+30+28+52）*1.2=189.6企业2仓库8 41+6+40+9+31+32+38 （48+30+28+52+50+68）*1.2=331.2企业3仓库2 34+32+31+9+27+26+19+18+23 （25+50+52+40+70+28+22+45）*1.2=398.4仓库3仓库2：35+32+31+9+27+26+19+18+23 486把以上路线修改得： 企业1储备库1 24+20+13+27 (50+68)*1.2+50*2=241.6 企业3储备库1 34+1+2+9+27 (45+40+62+40)*1.2=224.4企业3储备库1 34+1+2+9+27 (45+40+62+40)*1.2=224.4仓库3储备库1 35+32+34+1+2+9+27 (98+25+45+40+62+40)*1.2=372仓库5储备库1 22+20+13+27 (80+68)*1.2+50*2=277.6企业1储备库2 24+26+27+40+6+4+30 (30+70+30+30+70)*1.2+32*2=340企业1仓库4 24+26+25+15+9+41+6+40+9+31 （30+18+46+28+26+48+30+28+52）*1.2=367.2企业1仓库6 24+20+13+12+10+3+36 （50+68+80+52+42+50）*1.2=410.4企业1仓库8 24+20+13+12+10+3+36+33+37+38 （50+68+80+52+42+50+40+38+35）*1.2=546企业2仓库4 41+6+4+30+39+32+31 (48+30+70+62+50 )*1.2=348企业2仓库8 41+6+4+30+39+32+38 （48+30+70+15+62+68）*1.2=382.8企业3仓库2 34+32+39+30+4+6+41+41+42+15+18+23仓库3仓库2：35+32+39+30+29+28+42+15+18+23 552由于紧急调用，因此需要用到最短天数模型。将问题2的模型最短天数模型的数据如以上数据修改，可得新模型。运行模型后结果如下表10仓库1仓库2仓库4仓库6仓库7仓库8储备1储备2生产量企业1000000152001520企业230000011004102901110企业30002007009101000仓库300120003000150仓库503300000700400需求30033012020110100200012004180表10 紧急调用模型六、模型结果分析与检验1、 由于我们建立的是最少天数和最小费用的模型，若是要求最短时间则最少天数模型可供选择，若时间比较充足考虑费用，则最少费用可供选择。 七、模型的评价与推广1、 模型的评价优点：1）模型运用图论以及统筹规划知识对最小问题模型符合实际情况。2）从模型的建立可以得出即使库存、产量、路线发生变化也符合模型建立的基本思想，因此模型具有通用性。3）最短天数与最小费用模型能够结合现实综合考虑，并依照实施情况选择模型。缺点：1）该模型在处理问题时有假设与理想化的思想，与实际问题的求解还有一定距离2）该模型在设计时没有考虑人力成本、道路的现实路况、不同地区需求程度等问题，具有局限性。3）由于题目没有给出各企业的生产成本，因此费用最少模型有缺陷。2、 模型的推广模型的运用的图论和统筹规划还可以普及到各个领域，如最大流最小费用问题。该模型对我国防洪物资调运的科学性具有重要意义尤其是在我国日趋严重的洪涝等自然灾害。八、参考文献1 萧树铁，数学实验（第二版），北京：高等教育出版社，2006九、附录附件1：最短天数数学模型model:sets:cangku1/1,2,4,6,7,8/:a;qiye/1.3/:b;chubei/1,2/:c;cangku2/3,5/:d;links1(qiye,cangku1):x1,cost1;links2(qiye,chubei):x2,cost2; links3(cangku2,cangku1):x3,cost3; links4(cangku2,chubei):x4,cost4;endsetsmin=sum(links1:x1*cost1)+sum(links2:x2*cost2)+sum(links3:x3*cost3)+sum(links4:x4*cost4);!目标函数即费用最小;for(cangku1(i):sum(links1(j,i):x1(j,i)+sum(links3(j,i):x3(j,i)=a(i);!仓库（1,2,4,6,7,8）达到预测库存;for(chubei(i):sum(links2(j,i):x2(j,i)+sum(links4(j,i):x4(j,i)=c(i);!储备库达到最大库存;for(qiye(i):sum(links1(i,j):x1(i,j)+sum(links2(i,j):x2(i,j)=b(i);!企业的总运输量小于或等于其最大生产量; for(cangku2(i):sum(links3(i,j):x3(i,j)+sum(links4(i,j):x4(i,j)=d(i);!仓库（3,5）的总运输量等于其多出来的库存量;data:a=300 330 120 20 110 100;c=2000 1200;b=1600 1110 1000; d=150 400;cost1=184.8 150 230.4 344.4 256.8 372 69.6 188.4 189.6 303.6 141.6 331.2 268.8 398.4 90 174 196.8 111.6;cost2=120 340 157.6 177.6 200.4 122.4; cost3=356.4 486 174 321.6 284.4 199.2 254.4 166.8 314.4 446.4 340.8 456; cost4=288 222204 400.8;enddata附件2：最小费用数学模型model:!最小费用（通过结果得企业1生产43.25天，企业2生产1.67天，企业3生产47天，仓库3、仓库5没有运出）;sets:cangku1/1,2,4,6,7,8/:a;qiye/1.3/:b;chubei/1,2/:c;cangku2/3,5/:d;links1(qiye,cangku1):x1,cost1;links2(qiye,chubei):x2,cost2; links3(cangku2,cangku1):x3,cost3; links4(cangku2,chubei):x4,cost4;endsetsmin=sum(links1:x1*cost1)+sum(links2:x2*cost2)+sum(links3:x3*cost3)+sum(links4:x4*cost4);!目标函数即费用最小;for(cangku1(i):sum(links1(j,i):x1(j,i)+sum(links3(j,i):x3(j,i)=a(i);!仓库（1,2,4,6,7,8）等于预测库存;for(chubei(i):sum(links2(j,i):x2(j,i)+sum(links4(j,i):x4(j,i)=c(i);!储备库达到最大库存;for(qiye(i):sum(links1(i,j):x1(i,j)+sum(links2(i,j):x2(i,j)=b(i);!企业的总运输量小于或等于其最大生产量; for(cangku2(i):sum(links3(i,j):x3(i,j)+sum(links4(i,j):x4(i,j)=d(i);!仓库（3,5）的总输出量小于或等于其多余库存量;data:a=300 330 120 20 110 100;c=2000 1200;b=4000 4000 4000; d=150 400;cost1=184.8 150 230.4 344.4 256.8 372 69.6 188.4 189.6 303.6 141.6 331.2 268.8 398.4 90 174 196.8 111.6;cost2=120 340 157.6 177.6 200.4 122.4; cost3=356.4 486 174 321.6 284.4 199.2 254.4 166.8 314.4 446.4 340.8 456; cost4=288 222204 400.8;enddata附件3：最小费用20天模型model:!最小费用（通过结果得企业1生产43.25天，企业2生产1.67天，企业3生产47天，仓库3、仓库5没有运出）;sets:cangku1/1,2,4,6,7,8/:a;qiye/1.3/:b;chubei/1,2/:c;cangku2/3,5/:d;links1(qiye,cangku1):x1,cost1;links2(qiye,chubei):x2,cost2; links3(cangku2,cangku1):x3,cost3; links4(cangku2,chubei):x4,cost4;endsetsmin=sum(links1:x1*cost1)+sum(links2:x2*cost2)+sum(links3:x3*cost3)+sum(links4:x4*cost4);!目标函数即费用最小;for(cangku1(i):sum(links1(j,i):x1(j,i)+sum(links3(j,i):x3(j,i)=a(i);!仓库（1,2,4,6,7,8）小于或等于预测库存;for(chubei(i):sum(links2(j,i):x2(j,i)+sum(links4(j,i):x4(j,i)=c(i);!储备库小于或等于最大库存;for(qiye(i):sum(links1(i,j):x1(i,j)+sum(links2(i,j):x2(i,j)=b(i);!企业的总运输量等于其最大生产量; for(cangku2(i):sum(links3(i,j):x3(i,j)+sum(links4(i,j):x4(i,j)=d(i);data:a=300 330 120 20 110 100;c=2000 1200;b=1400 410 900; d=150 400;cost1=184.8 150 230.4 344.4 256.8 372 69.6 188.4 189.6 303.6 141.6 331.2 268.8 398.4 90 174 196.8 111.6;cost2=120 340 157.6 177.6 200.4 122.4; cost3=356.4 486 174 321.6 284.4 199.2 254.4 166.8 314.4 446.4 340.8 456; cost4=288 222204 400.8;enddata附件4：最短天数20天模型model:sets:cangku1/1,2,4,6,7,8/:a;qiye/1.3/:b;chubei/1,2/:c;cangku2/3,5/:d;links1(qiye,cangku1):x1,cost1;links2(qiye,chubei):x2,cost2; links3(cangku2,cangku1):x3,cost3; links4(cangku2,chubei):x4,cost4;endsetsmin=sum(links1:x1*cost1)+sum(links2:x2*cost2)+sum(links3:x3*cost3)+sum(links4:x4*cost4);!目标函数即费用最小;for(cangku1(i):sum(links1(j,i):x1(j,i)+sum(links3(j,i):x3(j,i)=a(i);!仓库（1,2,4,6,7,8）小于或等于预测库存;for(chubei(i):sum(links2(j,i):x2(j,i)+sum(links4(j,i):x4(j,i)=c(i);!储备库小于或等于最大库存;for(qiye(i):sum(links1(i,j):x1(i,j)+sum(links2(i,j):x2(i,j)=b(i);!企业的总运输量等于其生产量; for(cangku2(i):sum(links3(i,j):x3(i,j)+sum(links4(i,j):x4(i,j)=d(i);!仓库（3,5）的总输出量等于其多出来的库存量;data:a=300 330 120 20 110 100;c=2000 1200;b=1400 960 900; d=150 40