城市货物运输数学建模.doc

1、.B题 物资运送问题摘 要本文主要是以物资供应为背景,针对建立49个城市的供应网络以及对可能被破坏的道路问题进行研究,我们运用了Floyd算法,借助MATLAB软件,综合分析了49个城市的供应链网络的相关数据,建立了板块内供应点的固定费用与运输费用之和的二元一次的模型,利用穷举法对所有可能成为供应点的城市计算其作为供应点的总费用,比较确定出了八个供应点,并建立了相关的供应关系网络见文中表13.在预测恐怖分子破坏道路的问题上，首先对数据分析，排除可以肯定不能成功的方案，再运用穷举法比较得出最终被破坏的道路.针对问题一,就如何对城市供应点进行优化,使物资运送费用最小进行研究.利用MATLAB软件画

2、出各城市间道路的分布情况,根据道路分布、建立供应点的个数以及最终的优化目标,将整个城市网络分为八个部分,每一个部分分别对应一个供应城市.由于28号城市距离每个可建为供应点的城市路程都较远,因此,将28号城市单独划分为一类,具体图像见图1.运用Floyd算法,计算出每个城市之间的最短路径,再根据建立供应点的要求,剔除距离过远的城市,依据求出的最短路径对整个城市网络进行初步划分,得出可能作为供应点的城市.由题中给出的运输价格,建立总费用与运输距离、需求量之间的二元一次函数关系式,用穷举法对所有可能的作为供应点的城市计算它们对应的总费用,最后比较得到的总费用,选择每个板块内供应费用最小的城市为供应点

3、,得出这八个供应点分别为:4、10、14、20、24、26、28、40.针对问题二,由表4中可能被破坏的道路结合城市路径分布图1,在供应点都不改变的情况下,首先排除不能被破坏的道路,再运用Floyd算法,求出被破坏后受到影响的被供应点到供应城市的最短路径.假设可能被破坏的道路都被破坏,由问题一的得出的总费用与运输路程、需求量之间的二元一次函数关系式,计算出被破坏后相对于破坏前增加的费用.采用穷举法与排列组合对所有的情况进行组合,分别得出它们的组合后增加的总费用,得出费用最接近破坏前总额的25%的破坏方案,判断出恐怖组织可能破坏的道路为:1、2、4、5、6、9.为何要用英文的句号？后面也是？关键

4、字: 道路破坏 最短路径 Floyd算法 穷举法一、问题重述某公司要在全国各城市之间建立物资供应网络,需要选定部分城市作为供应点,向各个城市供应物资.该公司共考虑49个城市的网络, 城市的坐标见附录一中的表1,城市之间的道路连接关系见附录一中的表2,在每个城市建立配送中心的固定费用和需求量见附录一中的表3.现需要在这些城市中建立8个物资供应点,为各城市提供货物供应, 供应点城市不产生费用.货物运输利用汽车进行公路运输,运输价格每公里运输费用为:送货距离在300公里以下,500吨以下部分,每吨0.7元;501吨至1000吨部分,每吨0.6元;1001吨至1500吨部分,每吨0.5元;1500吨以

5、上部分,每吨0.45元;距离在301公里至500公里,每吨每公里运费增加0.1元（超出300公里的部分）;距离超出500公里的部分,每吨每公里运费增加0.15元.汽车回到出发点的空驶费用为0.3元/公里.建立供应点后,有恐怖组织对该供应网络的道路进行破坏,但并非所有的道路都可以被破坏,可破坏的道路见附录一中的表4.当某条道路被破坏后,该条道路就不能再被使用,以前运输经过该道路的只有改道,但总是沿费用最小路径运输.恐怖组织的目标是使所有运送物资的汽车消耗的总费用增加25%,而每破坏一条道路都需要成本和代价,因此需要破坏最少的道路.问题:1、求出当总费用最小时选出的供应点的城市,并给出每个供应点供

6、应的城市.2、问恐怖组织能否实现该目标？如果能实现,可能会选取哪几条线路进行破坏. 二、问题分析对于问题一,根据题目可知供应点城市应该满足两个基本条件:一是与被供应城市有道路连接,二是供应城市到被供应城市的运输费用加上建设供应点的固定费用之和最小.根据各城市的坐标以及各公路段的连接情况,运用MATLAB软件画出各城市路径图1,假设供应点到被供应城市之间最多只有一个中转城市,将49个供应城市划分在八个板块内,通过总费用与运送的最短路程及所需运送物质吨数之间的二元一次非线性函数关系式,计算出各个板块内可用来作为供应点的城市对应的总费用,选择各个板块内总费用最小的供应城市作为该板块的唯一供应点,最后

7、将各版块所求最小费用相加即得到总费用.对于问题二,首先依据问题一得出的结论,计算出破坏前总费用的25%,再分别求出各板块内每条可能被破坏的道路被破坏并且选择新的最短运输路线后所在板块内增加的费用.运用排列组合可知恐怖分子可能试行的方案有256种,由于要使破坏后增加的费用达到破坏前总额的25%,因此可以排除一些费用特别低的组合。对比剩下的每种方案的结果,选出破坏后增加费用接近破坏前总费用25%的方案,即为最终结果.三、模型假设1、假设每个城市的物资需求量固定不变;2、假设道路被破坏后,短时间内不能被修复;3、假设道路被破坏,城市所需物资的供应点不改变;4、假设汽车在运输过程中无突发状况,运输路途

8、畅通;5、假设各个城市间只有题中给出的运输线路且无其他的运输方式;6、假设每个供应点的物资是充足的,可以充分满足相应城市的需求.四、模型的建立与求解4.1模型一首先根据附录一中的表1与表2,运用MATLAB软件编程得到该公司考虑的49个城市之间的路径分布图1,程序见附录二中的程序1.图1 各城市之间的路径分布图从图1中可以看出各城市之间的道路连接情况以及各城市的地理坐标,利用最短路径问题及Floyd算法构建最短路径模型:1) 将带权邻接矩阵作为距离矩阵的初值,即.2) ,其中.3) ,其中.4) 重复上述操作,得到距离矩阵.再利用MATLAB软件编程，程序见附录二中的程序2,顺序构建各城市之间

9、的最短路程表,在这里我们截取部分表格内容如下表5:表5 部分城市最短路程表12345678101202704805407991129135921200370580660919124914793270370021074010691399147944805802100530127916091689554066074053001339166918996799919106912791339033056071129124913991609166933002308135914791479168918995602300再以城市编号分别为X轴和Y轴,以各城市之间的最短路程为Z轴,画出各城市之间最短路径图2:图

10、2 各城市之间的最短路程图由图像2的结果可知城市32、37与其他城市之间的距离最大,所以这两点不宜作为供应点. 假设第个城市为供应点,第个城市表示被供应城市,城市到城市的最短路径为,供应点的固定费用为,城市需求量为,若供应点城市与被供应城市之间的路径最短,则其值为1,反之则为0,供应点与被供应点之间的判断矩阵为.由于运费受路径长短与需求量的双重影响,因此根据题中给出的每公里及需求量的单价,可将运输情况划分为以下12类.最短路径并且时,运输单价元;最短路径并且时,运输单价元;最短路径并且时,运输单价元;最短路径并且时,运输单价元;最短路径并且时,超出300公里部分的运输单价元;最短路径并且时,超

11、出300公里的部分运输单价元;最短路径并且时,超出300公里的部分运输单价元;最短路径并且时,超出300公里的部分运输单价元;最短路径并且时,超出500公里的部分运输单价元;最短路径并且时,超出500公里的部分运输单价元;最短路径并且时,超出500公里的部分运输单价元;最短路径并且时,超出500公里的部分运输单价元;汽车回到供应点的空载运费为0.3元每公里.依据上述的运输单价以及表3,计算城市到与它邻近的城市（即两城市之间无中转城市）的供需费用关系,建立出每个板块内总费用模型（1）. （1） 由程序3（见附录二中的程序3 ）,画出各个城市对应的总费用图3.图3 各城市作为供应点时与其最邻近城市

12、对应的总费用命名不行从图3中,可以看出32、37的费用过高,因此剔除这两个城市的结果,对剔除后的城市再次画图得到图4.图4 剔除后的城市作为供应点时与其最邻近城市对应的总费用为使总费用最小,根据附录一中的表3,可知以下的城市由于固定费用过高不能作为供应城市:2、6、8、9、21、29、31、32、33、34、35、36、37、38、39、41、42、46、47、48、49 ,再根据图4 可以判断出城市14、15、16、19、25、27、31、43由于总费用过高,也是不适合作为供应点的,得出可作为供应点的有:3、4、5、7、10、11、12、13、17、18、20、22、23、24、26、40、

13、44、45、28、30.根据最短路径以及城市的分布情况，将这个网络大致做出如下表6的划分.上下间距问题，以及表格中的居中表6 供应城市与需求城市对应关系供求区可做供应点的城市需求点17、406、7、8、39、40、41、42212、10、119、10、11、12、15、37、38、4333、4、5、441、2、3、4、5、16、27、44、46、47428、3031、29、30、2852626622、23、2422、23、24、25720、19、20、21、33、34、35、48、49817、18、4513、14、17、18、32、36、45得到如图5的区域划分图.图5 供求区域划分图 图形做

14、的不好根据各供应点的总费用模型，计算各板块内可作为供应点的城市如果作为供应点可能产生的总费用，选择费用最低的点即为最优供应点.在板块一中,做出供应点与需求点的最短路程表7.以下表格均不行！不能没有每一栏的名称表7 板块一供应点与需求点的最短路程678394041427330023071773342934740103173396314180304929当以7为供应点时,总费用,当以40为供应点时,总费用,比较7与40的总费用可知应以40为板块一的最优供应城市.在板块二中,做出供应点与需求点的最短路程表8.表8 板块二供应点与需求点的最短路程9101112153738431028002791606

15、74100000598325111902780439953100000877604124401604390784100000758435当以3为供应点时,总费用;当以11为供应点时,总费用;当以12为供应点时,总费用,比较各供应的总费用可知应以10为板块二的最优供应城市.在板块三中,做出供应点与需求点的最短路程表9.表9 板块三供应点与需求点的最短路程123451627444647327037002107404408407251144936448058021005304306307159347165540660740530096010311245727186449951075725715124

16、528563709411431当以3为供应点时,总费用;当以4为供应点时,总费用;当以5为供应点时,总费用;当以44为供应点时,总费用,比较各供应的总费用可知以4为板块三的最优供应城市.在板块四中,做出供应点与需求点的最短路程表10.表10 板块四供应点与需求点的最短路程2930312828230500198003073002480500当以3为供应点时,总费用;当以30为供应点时,总费用,比较各供应的总费用可知应以30为板块三的最优供应城市.由于板块五只有一个城市,因此以它为最优供应城市.在板块六中,做出供应点与需求点的最短路程表11.表11 板块六供应点与需求点的最短路程222324252

17、203404901090233400830990244908300650当以22为供应点时,总费用;当以23为供应点时,总费用;当以24为供应点时,总费用,比较各供应的总费用可知以24为板块七的最优供应城市.由于板块七只有一个城市,因此以它为最优供应城市.在板块八中,做出供应点与需求点的最短路程表12.表12 板块八供应点与需求点的最短路程1314171832364517950270038010000018183621813206403800100000146850845128563236250810000019760当以17为供应点时,总费用;当以18为供应点时,总费用;当以45为供应点时,

18、总费用,比较各供应的总费用可知以45为板块八的最优供应城市.得到最终优化后的供应点与被供应城市的关系表格13.表13 供应关系网络供求区可做供应点的城市需求点1406,7, 8, 39,40, 41, 422109,10,11,12,15,37,38,43341,2,3,4,5,16,27,44,46,4742831,29,30,285262662422,23,24,2572019,20,21,33,34,35,48,4981413,14,17,18,32,36,45根据上述表格可以确定出最终的供应城市为:4、10、14、20、24、26、28、40.4.2模型二由城市路径分布图1可知,可能被

19、破坏的道路大部分都在不同的板块内,因此对可能破坏的道路结合图1（城市路径分布图）进行分析可知8号道路不能被破坏,否则会造成49号城市的物资供应被切断.当道路被破坏后,设经过此道路的费用为无穷大.假设破坏后城市（供应点）与被供应城之间的最短路程为,固定费用依旧为,需求量为,得出破坏后总费用的计算公式（2）. （2）其中的数值根据与共同确定.同问题一,运用Floyd算法,对程序2中的部分参数进行修改,再依据破坏后总费用的计算公式得到破坏后的道路总费用以及相对增长费用如表14所示.表14 破坏后的道路总费用及相对增长费用破坏的道路总费用相对增长费用18873900068990002889600007

20、1200003886910006851000488576709673670958932800074880006887020006862000791840000100000009892020007362000增加的总费用59318709对上述的道路进行排列组合,排除掉其中费用明显低于原总费用25%的组合情况,当组合的道路数目小于等于5时,无论怎样组合,都不可能达到原总费用的25%.因此只对组合为6的情况进行分析.依据破坏后的总费用模型二,计算得出这些道路被破坏的运输情况以及超出与其对应的原总费用的运输费用如下表15:表15 道路破坏后的运输情况及增加费用受影响的供应点破坏前货物的运输道路破坏后货

21、物的运输道路增长的运输费用44-545474315430472460004-343143245341631416324670001010-11101137109111091137837091414174514184502020-1920211983500020-212021492019-21201921497090002424-252422252090004040-740-78406740678198000根据条件要使得破坏后增加的费用达到原来总费用的25%,并且选择最少的道路进行破坏,则恐怖组织可能选择破坏的道路为1、2、4、5、6、9.五、模型的评价及推广在本模型中运用了Floyd算法求出

22、了两个城市的最短路径,建立与完善了城市网络的分布,并对这49个城市作出了分块,较好地解决了费用最优问题,使公司的效益达到最大化;预测了可能会遭受到破坏的道路,给公司再面临突发的状况时能及时的选择最优方式将物资送达到被供应城市.但该模型存在一定的局限性，由于采用了穷举法，当数量过多的时候，此模型便不再适用.该模型贴近生活,能够很好地为实际生活中的最优问题提供实例,就自然灾害频发的年代我们可以将此模型运用在大自然灾害后道路被破坏,运输物资的问题上,也可以对恐怖组织破坏道路进行预测,从而提早进行预防使损失降到最小.也可以给其它方式运输的公司选择费用最小的路线.六、参考文献1司守奎 孙玺菁 张德存 周

23、刚 韩庆龙,数学建模算法与应用习题解答M,北京:国防工业出版社,2013.12陈国华 韦程东 蒋建初 付军,数学模型与数学建模方法M,天津:南开大学出版社,2012.63供应链网络的建立与道路破环问题,高等教育专业基础教材, 2014.8.6七、附录附录一:表1 各城市坐标编号城市坐标X(公里)坐标Y(公里)1北京363926852天津371226013石家庄348824654太原332624445呼市323827716沈阳419629567长春431232108哈尔滨438634309上海4177175610南京3918182111杭州4061163012合肥3780178813福州4029

24、116214南昌3676142215济南3715232216郑州3429209217武汉3507162418长沙3394135719广州343979920南宁293576021海口314045022重庆2769150823成都2545164324贵阳2778117425昆明2370102526拉萨1304168827西安3007203028兰州2562224429西宁2381232430银川2788250931乌市1332330532台北4263106933香港353870234澳门347069635深圳352673736厦门392897137宁波4201160338青岛4016228539大

25、连4089261340通辽4296292041白城4095337442海拉尔4512271043徐州3751205544南阳3334189345宜昌3229163346延安3054229047包头3089274948柳州304491949三亚3053261表2 各公路段及里程表序号城市1城市2距离（公里）112120213270315540416799511542061408447233708215360934210103153111131644012455301341643014427630154307601653072017540152118547186196733020639387216

26、407272278230237404292474134725842819269102802791119028915840291011279301012160311014660321015680331038598341043325351113880361114640371137153381214610391216650401217540411243435421314680431319102044133249045133626646133759247141727048141864049141986050151643051153836152154334953161754054162755055164

27、347356164428557171838058174440659174536260181978061182410106218455086318486646419207106519215806619341306719351276819366886920215607020246507120258207220483057321492707422233407522244907622251090772227910782245795792325990802326217081232792082242565083244856084252623208526291940862631267287272870088

28、2730640892744637902746304912829230922830500932831198094304755495333536963536591973843368984041304994042929100414266910144454661024647541表3 各城市建立供应中心的费用以及各城市对物资的需求量城市费用(元)需求量(吨)1112358412322100000000097437334009654272080358516948022361000000000715745782475381000000000989910000000001391106639366241141

29、161667712370120487135800326361452668049515733248603168767367211776060883418585504642199557767862052668069321100000000015622247532032572368460811262427664036425403560531263100851279411847742819638432329100000000019430114760151311000000000234321000000000246331000000000701341000000000553510000000002333

30、6100000000017437100000000056838100000000076139100000000058340289104317411000000000204421000000000272437204809484469920011504524380840146100000000022447100000000021748100000000036649100000000055(注:1000000000表示该点不用,费用太高) 表4破坏道路及概率道路序号城市1城市2 概率1450.62340.737400.45410110.5519200.55624250.4717450.5821490

31、.6920210.6附录二:程序1（各城市之间的路径分布图）:A=3639 3712 3488 3326 3238 4196 4312 4386 4177 3918 4061 3780 4029 3676 3715 3429 3507 3394 3439 2935 3140 2769 2545 2778 2370 1304 3007 2562 2381 2788 1332 4263 3538 3470 3526 3928 4201 4016 4089 4296 4095 4512 3751 3334 3229 3054 3089 3044 3053; 2685 2601 2465 2444 2

32、771 2956 3210 3430 1756 1821 1630 1788 1162 1422 2322 2092 1624 1357 799 760 450 1508 1643 1174 1025 1688 2030 2244 2324 2509 3305 1069 702 696 737 971 1603 2285 2613 2920 3374 2710 2055 1893 1633 2290 2749 919 261;x=A(1,:);y=A(2,:);plot(x,y,.)text(3639 ,2685,1)text(3712,2601,2)text(3488, 2465,3)tex

33、t(3326, 2444,4)text(3238, 2771,5)text(4196,2956,6)text(4312, 3210,7)text(4386,3430,8)text(4177,1756,9)text(3918,1821,10)text(4061,1630,11)text(3780,1788,12)text(4029,1162,13)text(3676,1422,14)text(3715,2322,15)text(3429,2092,16)text(3507,1624,17)text(3394,1357,18)text(3439,799,19)text(2935,760,20)te

34、xt(3140,450,21)text(2769,1508,22)text(2545,1643,23)text(2778,1174,24)text(2370,1025,25)text(1304,1688,26)text(3007,2030,27)text(2562,2244,28)text(2381,2324,29)text(2788,2509,30)text(1332,3305,31)text(4263,1069,32)text(3538,702,33)text(3470,696,34)text(3526,737,35)text(3928,971,36)text(4201,1603,37)t

35、ext(4016,2285,38)text(4089,2613,39)text(4296,2920,40)text(4095,3374,41)text(4512,2710,42)text(3751,2055,43)text(3334,1893,44)text(3229,1633,45)text(3054,2290,46)text(3089,2749,47)text(3044,919,48)text(3053,261,49)B=1 1 1 1 1 1 2 2 3 3 3 4 4 4 4 5 5 5 6 6 6 7 7 7 8 9 9 9 10 10 10 10 10 10 11 11 11 12

36、 12 12 12 13 13 13 13 13 14 14 14 15 15 15 16 16 16 16 17 17 17 18 18 18 18 19 19 19 19 19 20 20 20 20 21 22 22 22 22 22 23 23 23 24 24 25 26 26 27 27 27 27 28 28 28 30 33 35 38 40 40 41 44 46; 2 3 5 6 15 40 3 15 4 15 16 5 16 27 30 30 40 47 7 39 40 8 40 41 42 10 11 15 11 12 14 15 38 43 13 14 37 14 1

37、6 17 43 14 19 32 36 37 17 18 19 16 38 43 17 27 43 44 18 44 45 19 24 45 48 20 21 34 35 36 21 24 25 48 49 23 24 25 27 45 25 26 27 25 48 26 29 31 28 30 44 46 29 30 31 47 35 36 43 41 42 42 45 47;p q=size(B);for m=1:q line(A(1,B(1,m),A(1,B(2,m),A(2,B(1,m),A(2,B(2,m),Marker,.,LineStyle,-)end程序2(求最短路径):clearclcM=100000; a(1,:)=0,120,270,M,540,799,M,M,M,M,M,M,M,M,420,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,M,844, M,M,M,M,M,M,M,M,M; a(2,:)=ze