数模论文final (1).doc

南京航空航天大学第八届校数学建模竞赛 题目： 灾区救援物资的运输问题 队员姓名 2010年5月25日灾区救援物资的运输问题摘 要本文建立了灾区救援物资运输方案的优化模型，对于问题1，分别以运输总费用最少和总时间最短为原则建立最优整数规划模型（模型I），算出了各地独立运输和全国统一调度下的最佳车辆安排方案以及相应的运输费用，在此基础上，又以获得最佳货物安排为目标进一步建立了补充优化模型（模型II），用以求解最佳车辆安排下的最优货物安排。对于问题2考虑紧迫性的情况建立了图论模型（模型III），并通过Dijkstra算法求解两点间最短通路获得了最佳运输路线。对于问题3，以募捐物资价值为目标函数建立了线性规划模型（模型IV）用以求解目标函数最大化时的资金使用方案。模型I：对于问题1，当各地独立运输物资时，通过使用Lingo编程求解获得了各城市最优的运输车辆安排，此时所需的最少总费用为163435.222元；全国统一调度时，求得了中转城市的最优的运输车辆安排，以及运输所需最少总费用155007.577元。对于问题2，求解结果与问题1中独立运输时相同，并给出了分析。模型II：对于问题1、2在使用模型1求出了最优的运输车辆安排的前提下，将相应运输车辆数据代入模型II的Lingo程序中求解，获得了各运输方案最佳的货物装车安排。模型III：对于问题2考虑紧迫性的情况，对实际公路网建立了图论模型，并用C+实现了Dijkstra算法，求解获得了各地到灾区的最佳运输路径，以使运输时间最短。模型IV：对于问题3，因为采取了各地物资兑换成资金后在离玉树相对最近的重庆进行采购的方案，故通过建立线性规划模型IV并使用Lingo求解，获得了募捐物资价值最大时各物资采购数量方案：类别棉被（条）帐篷（顶）饮用水（箱）米（袋）数量8021330280001860相应最大募捐物资价值为1989820元。关键词：运输问题 救援物资 整数规划 图论模型 线性规划 一、问题的提出1.1 基本情况2010年4月14日，青海省玉树县发生7.1级地震，灾情牵动着社会各界的心，我们有义务帮助灾区人们重建家园。全国各地都积极进行募捐活动，救援物资的运输成为一个急需解决的问题。目前各地车辆都有以下3种型号的卡车可供租用,车挂为5.23，高2米,载重8吨; 车挂为7.23，高2米,载重10吨; 车挂为9.23，高2米,载重12吨; 租用费用分别为每天100元,150元,200元.司机的劳务费为每小时30元(可考虑有备用司机,即车在运输工程中不休息)。运输距离按照城市间距离计算。各地募捐物资数量描述如下： 地点棉被（条）帐篷（顶）饮用水（箱）米（吨）北京30020090020上海10030010008南京5001005005重庆3003008004太原8002007006西安5004006005南昌6002004006深圳100050010008杭州70020070010哈尔滨120020050010广州9004008008昆明6003001003假设棉被体积为70cm70cm20cm,重3斤，帐篷体积为150cm20cm20cm，重30斤，每箱水体积为35cm35cm20cm，重50斤，每袋大米重50千克，体积为50cm30cm10cm。1.2 需解决的问题问题1： 如果不考虑物资的紧迫性，1）如果各地自己运送物资,该如何安排运输车辆，使得将物资运输至灾区所需要的总时间，总路程最短，总费用最少(油费也需考虑)2）如果全国统一调度，该如何安排运输车辆，使得将各地物资运输至灾区所需要的总时间，总路程最短，总费用最少(油费也需考虑)问题2：如果考虑物资的紧迫性，请重新考虑上述问题。问题3：如果募捐物资可以兑换成同等价值的现金，该如何使用这些现金，使得效益达到最大(物品不得少于原募捐物资)? 2、 问题分析2.1 条件分析（1） 最大化卡车的利用率。现已知有三种类型的卡车可供租用，由已知可计算其可载体积和最大载重如下：卡车型号可载体积（ ）最大载重（Kg）租用费用（元/天）a31.28000100b43.210000150c55.212000200为了减少运输车次，降低运输花费，应尽量增大每辆卡车的利用率，使托运货量尽可能接近或达到卡车运载最大值，即： 每车货运量最大载重 且 货运体积可载体积（2） 考虑货物的外形尺寸和卡车车挂尺寸对运输量的影响。由于不同货物拥有固定的外形尺寸，运输时不能任意变形以适应车挂尺寸，所以实际运输时卡车体积利用率不可能达到100%,而要受到各物品外形和摆放方式的制约。基于实际情况考虑，不可能对装货时每件货物的具体摆放方式作出要求，故需通过计算确定外形对体积利用率的影响。为确保考虑外形时货物亦能装入，引入影响因子k，并将（1）中相应体积利用率的条件改写为： 货运体积k*可载体积通过编写程序模拟考虑三维外形时的货物摆放（Fortran程序代码见附录），对比计算出的实际最大装货量与不考虑外形时的理论最大装货量如下：（只考虑了棉被，因为帐篷和水的限制因素是载重）卡车型号棉花实际理论ka3023180.95b4284400.97c5465630.97故取k=0.9足以保证货物在考虑外形时亦能装入。2.2 问题1分析 问题1要求在不考虑紧迫性的情况下求解：1）各自调度时总时间，总路程最短，总费用最少(油费也需考虑)的调度方案；2）统一调度时，总时间，总路程最短，总费用最少(油费也需考虑)的调度方案。因为不考虑紧迫性，故首要考虑因素是使得总费用最少，而总时间最短作为次要考虑因素。对于1）中的各自运输，是一个线性规划问题，可以先建立最优整数规划模型，以车辆安排为决策量，根据对各货物的数量及货物重量的要求，加入约束条件，使用数学软件对模型进行求解，即可得出总费用最少的车辆安排方案。然后在第一层线性规划的基础上，以每辆车各类物资数量为决策量，再次建立整数规划模型，以每辆车的可载体积和最大载重为约束，求解各卡车运输物资的最优方案。对于2）中的统一调度，可选择合适的城市设置物资中转站，通过货物的集中大量运输减少总运输车次，再建立1）中使用的两层线性规划模型求解出总花费最小且总时间最少的车辆安排方案与货物运输方案。2.3 问题2分析问题2要求考虑运输的紧迫性，故首要考虑因素是使得时间最少，而总花费最少作为次要考虑因素。要使得救灾物资尽快到达灾区，各地运输车辆须选择通往灾区的最短路径，同时尽可能减少装卸次数，一次性将所有物资运往灾区。因为设置中转站会有物资中转时间的额外开销，所以可考虑取消中转站，各地独立将所有物资运一次性往灾区。故可先建立图论模型，求解出到达灾区的最小路径，然后使用与问题1中相同的最优整数规划模型进行求解。2.4 问题3分析问题3中募捐物资可以兑换成同等价值的现金，要求求解使得效益达到最大的资金使用方案。可将所有物资看作可用资金的一部分，结合问题2的结果可估算出总的可用资金数目，可以将效益看作是募捐物资价值与总可用资金比值，并以募捐物资价值为目标函数，以资金限制、运输能力限制以及物资数量要求为约束，建立线性规划模型，求解效益最优情况下的资金使用方案。3、 基本假设(1) 每辆卡车能在最大限度内正常使用；(2) 各种型号的卡车行驶速度相同；(3) 各地都有足够多的卡车可供租用；(4) 卡车回程不计各类运费；(5) 运输过程中不考虑租用费、司机劳务费以及燃油费之外的其他费用；(6) 每辆卡车都有备用司机，车在运输工程中不休息；(7) 各城市间交通路线畅通无阻，行驶速度不受路况影响且运输过程不受天气影响；(8) 各种货物能够实现任意混装；(9) 各类卡车耗油量恒定，分别为：16L/100km、20L/100km、24L/100km，柴油价格：6000元/吨；(10) 募捐物资价值固定，分别为：棉被120元/条、帐篷150元/顶、饮用水20元/箱、米200元/袋；4、 符号约定：租用第i型车的数量。：第i型车的日租费。：第i型车的油耗（L/100km）。：第j种物品的数量。：单位数量j种物品的体积（）。：单位数量j种物品的质量（）。：第i型车的可载体积（）。：第i型车的最大载重（）。：第i辆车装j种物品的数量。：第j种物品的采购数量。：第j种物品的价格。5、 模型的建立与求解5.1 问题1的分析与求解1.问题（1）分析不考虑紧迫性情况下，各地若自己运送物资，首要考虑因素是使得总费用最少，而总时间最短作为次要考虑因素。根据假设有：总费用=总租用费+总劳务费+总燃油费若安排租用第i型车辆，则： （其中d为租用天数） （其中h为运输时间） （其中s为运输路程，为柴油密度，为油价）故有：安排运输车辆时，为降低运输车次，要尽量充分利用每辆卡车。同时，为保证安全，卡车不能超载，且考虑物品外形影响下卡车有足够的体积装下货物，由此得出卡车最大运输能力的两个约束条件：（1） 考虑货物外形影响的最大体积约束：（2） 最大载重约束：2.模型I建立（第一层整数规划模型）根据以上分析可建立模型I最优整数规划模型如下：目标函数：约束条件： 最大体积约束： 最大载重约束： 整数约束：决策变量为整数（i=1，2，3）3.算法流程图模型I的算法流程图如图1所示：图144.模型求解使用Lingo软件对模型I进行求解（具体程序见附录），代入各个城市的数据后求解结果如下：独立调度车辆安排地点运输车次最少运费(元)a型卡车b型卡车c型卡车北京01318090.72上海21118744.02南京1018916重庆1118219.232太原1209682.544西安2018508.522南昌0209126.672深圳03122292.77杭州10215114.08哈尔滨01219618.88广州00318093.72昆明0205917.632总运费163435.222注：运输车次为n表示同时租用该型卡车n辆一次运完或租用1辆该型卡车运输n次，在假设条件下两者花费相同，故在不考虑紧迫性时两种方式皆可。5.基于模型I的进一步分析模型I以各型卡车租用量为决策变量，总运费为目标函数，求解得到了各城市独立运输时最小总运费下的运输车次安排。但实际运输时很可能会出现因货物安排不合理而导致无法在规定运输车次内运完货物，故有必要根据模型I的求解结果建立第二层最优整数规划模型，以给出达到最小运费时货物在各车的分布情况。要使货物分布均匀，则每辆车的剩余空间所占比例应大致相同，故目标函数可取各车货物总体积与该货车可载体积比值之积，同时约束为各辆车的可载体积、最大载重与货物数量的限制，从而可求解出目标函数值最大时（此时各车货物总体积与该货车可载体积比值近似相等）的货物分布矩阵。6. 模型II的建立（第二层整数规划模型）根据以上分析可建立模型II最优整数规划模型如下：目标函数： （其中n为求解出的总运输车次）约束条件： 各卡车最大体积约束： ， 各卡车最大载重约束： ， 货物数量约束：, 整数约束：决策变量为整数,7.算法流程图模型II的算法流程图如所示：图28.模型求解使用Lingo软件对模型II进行求解（具体程序见附录），代入模型I的结果后求解出最优货物分布如下：城市车号车型棉被（条）帐篷（顶）饮用水（箱）米（袋）北京1b8251216742c71512331063c73492271094c7449224111上海1a1310923972a11127183303b2463280404c52129883南京13141134454重庆1a93149178222b93114258313c1143736427太原1a20181186352b30158254443b2986126041西安1a174148128382a130231105313c1962136731南昌1b258181171472c3421922973深圳1b265113222382b262115228393c28059290434c19321326040杭州1a174154179142c279331381493c2471338337哈尔滨1b34175160622c42282143853c4374319753广州1c300134268492c301133266533c29913326658昆明1b30015050302b30015050309. 问题（2）分析全国统一调度时，若不考虑紧迫性，首要考虑因素仍是使得总费用最少，而总时间最短作为次要考虑因素。考虑选择合适的城市设置物资中转站，一方面方便救灾物资的统一周转中和配送，同时通过货物的集中大量运输可以减少总运输车次。中转站的设置应以减少花费为原则，故中转城市的选择要基于以下要求：（1） 为了不使总运输路程增加，显然应该避免运输车辆向远离灾区的方向运输物资，即中转站应该在相对靠近玉树的城市中选取。（2） 所有物资在运到中转城市后需要卸货后重新安排运输方案，如图所示,O，B向A运送物资时，设置O为中转站，考虑最坏情况下，中转站O未能使B，O各自运输时的车辆总数减少，即相当于B向A独立运输物资的路程从变为，要使运输路程不增加，应满足：当且仅当AOB共线时才能满足条件，即中转站应该在运输直达路线上所经城市中选取。OAB图3路线3路线4路线2路线1图4 各城市到玉树的直达路线（来自google 地图）基于以上两点考虑，结合各城市到玉树的实际直达路线图（图4），可设置太原、西安、重庆分别为线路1、2、3的中转城市，线路4昆明独立运输。10. 问题（2）模型建立与求解该问题可直接使用问题（1）中建立的两层整数规划模型I、II进行求解。先使用模型I的求解程序解得统一调度时各路线最优车辆安排如下：线路1地点运输车次运费(元)a型卡车b型卡车c型卡车 北京-太原0133695.117哈尔滨-太原0038793.859 太原-玉树11733690.7最少总费用46179.676线路2地点运输车次运费(元)a型卡车b型卡车c型卡车上海-西安2117801.024南京-西安1013247.056杭州-西安1026215.773南昌-西安0113745.501西安-玉树201039372.82最少总费用60382.174线路3地点运输车次运费(元)a型卡车b型卡车c型卡车深圳-重庆03110925.85广州-重庆0038650.637重庆-玉树00928869.24最少总费用48445.727注：运输车次为n表示同时租用该型卡车n辆一次运完或租用1辆该型卡车运输n次，在假设条件下两者花费相同，故在不考虑紧迫性时两种方式皆可。显然非中转城市车辆安排与独立调度时相同，相应每辆车的货物安排也应相同，故只需用模型II求解中转站在统一调度时每辆车的货物安排。各中转城市所需运输物资为所在线路所有物资数量之和，如下表所示：地点棉被（条）帐篷（顶）饮用水（箱）米（袋）太原-玉树23006002100720西安-玉树240012003200680重庆-玉树220012002600400将数据代入模型II的求解程序中可解得最优货物分布如下：城市车号车型棉被（条）帐篷（顶）饮用水（箱）米（袋）太原1307341141203c300151671434243643334752561438136294211881307270412704182181899012392761432663西安1a19214011553221297140543c1971002945741971012915851971002915761971002945771971012915881971002945791971002925710197100291581119710429157122235731657重庆1c2441362884422441332884432441332884442441332884452441332884462441332884472441332884882481332884492441332964411. 结果分析问题1）与问题2）花费比较如下：线路1线路2线路3总花费独立调度47392.14461091.96148605.722157089.827统一调度46179.67660382.17448445.727155007.577变化率2.56%1.16%0.33%1.33%以上结果表明，全国统一调度时相较于独立调度不仅提高了物资收发效率，同时节省了花费。观察车辆安排的变化可知运费的减少是由于集中运输时主要租用运输能力最强的c型卡车，与独立运输相比减少了运输车次。5.2 问题2的分析与求解 在实际的灾区救援物资的运输问题中，显然需要考虑紧迫性问题，即在尽可能短的时间里将救援物资运送到灾区。故在问题2中，首要考虑因素是使得运输时间最少，而总花费最少则作为次要考虑因素。运输时间最少体现在两个方面：一、救援物资在最短时间里送达灾区；二、运输过程所花费的时间最少。前者要求物资的运输具有较少的延迟，后者要求运输车辆平均速度要最大，运输路程最短。出于减少运输延迟的考虑，不应设置中转城市，因为中转城市需要花费一定的等待时间来集中物资，同时增加了装卸货物的时间开销；根据假设，各型卡车运输速度相等，所以在最小运输时间下各地应该独立将所有物资运一次性往灾区（区别于问题1中可采取的多次往返运输），同时保证运输路径为最短。为了确定各货源城市到达灾区的最短路径，可对实际公路网建立图论模型，通过求解两点间最小通路问题得到最短运输路程。1. 模型III建立（图论模型）把提供救灾物资的每个城市看作是一个节点v，两个城市直接相连的直达公路看作边e，城市vi与城市vj之间卡车最短行驶时间（根据假设，路径长度与行驶时间成正比）看作是边vivj的权w(vivj)=tij，这样现有的公路网络就是一个赋权图G。在这个网络的两个指定城市之间确定一条最短路线，即最短通路问题，就可转化为：在赋权图G中，寻找任意两点间的最短通路。根据实际的地理位置（见图4），建立赋权图G如下(权值tij省略标注）：节点号0 1 2 3 4 5 6 7 8 9 10 11 12 城市9731245681011120玉树太原北京哈尔滨西安南昌杭州南京上海重庆广州深圳昆明权值tij如下表：节点号01234567891011120 0 34 32 30 34 1 34 0 7 8 16 14 2 7 0 15 19 13 3 15 0 4 32 8 0 14 16 13 14 22 5 16 19 14 0 8 20 11 11 23 6 16 8 0 4 2 18 7 14 13 13 8 4 0 3 25 19 19 8 2 3 0 29 20 19 9 30 14 20 25 29 0 23 24 12 10 22 11 19 20 23 0 2 21 11 11 18 19 19 24 2 0 22 12 34 23 12 21 22 0 注：若第i城市与第j个城市存在直接相连的公路，tij为它们之间的行驶时间；若第i城市与第j个城市不存在直接相连的公路，tij=。2. 模型III求解对于最短通路问题，可采用Dijkstra算法求解。求解流程如下：1、 任取一点u0，置l(u0)=0，对vu0, l(v)=, S0=u0且i=0;2、对每个vVSi，用minl(v), l(ui)+w(uiv)代替l(v)，计算minl(v)，并把达到这个最小值的一个点记为ui+1, 置Si+1=Siui+1;3、若i=n-1, 则停止，若i0)thenca=saif(wh0)thenca=sa;if(wb=sb)thenp=sbendifendifendifelseif(wb0)thenif(p=r)thenca=qelseca=aendifcb=r;ch=h;wa=i;wb=j;wh=kif(wh0)thencb=sb;if(wa=sb)thent=wb;wb=wa;wa=tmh=ch/wh;sh=mod(ch,wh)ma=ca/wa;sa=mod(ca,wa)mb=cb/wb;sb=mod(cb,wb)m=m+ma*mb*mhendifendifelseif(wa=(na*0.098+nb*0.06+nc*0.0245+nd*0.015);sum(a(i):x(i)*m(i)=na*1.5+nb*15+nc*25+nd*50;for(a(i):gin(x(i);End3. 货物按排求解程序（Lingo）model:sets:row/1.9/:vc,mc;arrange/1.4/:vs,ms,n;link(row,arrang