深圳南山区橱余垃圾处理方案设计

2014年河南科技大学模拟训练一承诺书我们仔细阅读了数学建模选拔赛的规则.我们完全明白，在做题期间不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人研究、讨论与选拔题有关的问题。,如果引用别人的成果或其他文引用处和参考文献中明确列出。我们郑重承诺，严格遵守选拔规则，以保证选拔的公正、公平性。如有违反选拔规则的行为，我们将受到严肃处理。我们选择的题号是（从A/B/C2011年夏令营A题：垃圾处理和清运方案队员签名：1.2.3.日期：2014年8月16日2014年河南科技大学数学建模竞赛选拔编号专用页评阅编号（评阅前进行编号）：评阅记录（评阅时使用）：备注摘要38个垃圾转运站归结为11个分布点，并在地图上选取主要干道的13交叉点与11个分布点一起作为橱余处理厂的建设候选点。由此将问题转化为图论问题。Floyd24个候选点两两之间的最短路程。[2]再次，根据中已证结论：当粮仓可以建在村庄里或道路上时，则粮仓建3个大型处理厂成本最小，然后利用lingo软件求解，得出处理厂的分布方案。具体如下：建设3个大型处理厂，分别在vv（前海公园公厕垃圾26v（大冲公厕垃圾站附近）进而规划清运路线。7再者，利用图论中的Dijkstra算法，求出最短的清运路线。具体如下：vv、vvv、vvv、vvvv、1241325166917166vvvv、vv、vvv、vvvvvv101918637821711242082172方案与橱余垃圾清运方案。的运输去向，同时模型的应用性强，可以用来解决本题中的1、2小题，并对模型进行了适当修改使之能够适用于其他地区的相关设施建设问题，适用性强。关键词：图论、最短路、Floyd算法、整数线性规划、Dijkstra算法问题重述有利于资源回收与再利用的城市绿色工程。在深圳，垃圾分为四类：橱余垃圾、可回收垃圾、有害垃圾和其他不可回收垃圾。它们的平均比例为，橱余垃圾：可回收垃圾：有害垃圾：其他不可回收垃圾比例约为4：2：13。在垃圾分类收集与处理中，不同类的垃圾有不同的处理方式，简述如下：（1做原料。不同处理规模的设备成本和运行成本（分大型和小型）如下：大型厨余垃圾处理设备，处理能力为200吨日，投资额约为4500万元，运行成本为150元/吨；小型餐厨垃圾处理机，处理能力为200-300/日，投资额约为28万元，运行成本为200元/吨。橱余垃圾处理后产物价格在1000-1500元/吨。成本指标处理后产物价格处理设备200/日200-300公斤/日4500万元28万元150元/吨200/吨1000-1500元/吨小型餐厨垃圾（）可回收垃圾将收集后分类再利用。（）有害垃圾将运送到固废处理中心集中处理。（）其他不可回收垃圾将运送到填埋场或焚烧场处理。所有垃圾将从小区运送到附近的转运站，再运送到少数几个垃圾处理中心。显然，1）和2）两项中，经过处理，回收和利用，产生经济效益，而3）和4）只有消耗处理费用，不产生经济效益。本项研究课题旨在为深圳市的垃圾分类化进程作出贡献。为此请你们运用数学建模方法对深圳市南山区的分类化垃圾的实现做一些研究，具体的研究目标是：最佳经济效益和环保效果。假设转运站允许重新设计，请为问题1）的目标重新设计。一个大型“厢”，平均吨公里耗油25L30L柴油/百公里。60辆2.5油20L35L汽油/百公里。司机月薪平均3500元。问题分析我们认为最符合经济效益应该为：总成本最小，其中总成本=处理厂建设成本+垃圾处理费用+分总量为804圾=42来算出橱余垃圾量为536问题。本题的运输路线是南山区的实际道路，已经建成，出于成本考虑，我们不题。本题是研究怎么建橱余处理厂使得总成本最小，是个整数规划问题。模型假设假设1：把实际地图简化成图论中的图。38个转站归结为中11一张图论中的图。假设2：假设建设三个大型处理设备处理所有橱余垃圾。虽然题目中有两种橱余处理设备，但是都建大型处理机需要三个，成本13500万，建两个大型的，其他建小型的处理机，处理完536吨橱余垃圾需要建设45421712距离为15公里，最大运输成本为15/100*536*7.34*30=17704.08元，远小于上面建设成本差8212万元。假设3：建设橱余处理厂不考虑当地建设成本差异，所有的候选点都能够建处理厂。假设4：假设所选的路线交通畅通，无事故发生，不考虑运输车辆（拖车）空车的运行成本。假设5：对于第二个问题，为简化问题，我们类似地把众多的居民区归为数量合理的点，并和上面的主要道路一起构成另一张图。假设6：问题二中所建设的中转站最大转运量为Z。符号说明：po:第i1113个为0。iW：第i个点是否建设处理厂，取值为0或1，取1代表建设处理厂，取i0代表不建设处理厂。U0或11代表从第i点运橱余垃圾到第j0则不运。ijDK：从第i点到第j点的最短路程。ij模型建立问题1：第一步：求处理厂位置与中转点垃圾运向问题。目标函数：运费最小。2424minKDproUWijiijjj1i1约束条件：1、处理厂的处理量不超过200。j=1,2UWiji12、保证每个点的垃圾只运到一个处理厂24U1i=1,2,3ijj13、保证只建三个大型处理厂i=1,2,3W3jj1第二步：清运路线在第一步求得的处理站与垃圾运向的基础上，运用Dijkstra算法求出最短线作为清运路线。问题2：符号说明：pro:第i个点需要转运的垃圾量。前m个为具体数值，后n-m个为0。iW：第i个点是否建设中转站，取值为0或1，取1代表建设中转站，取0代i表不建设中转站。U：取值为0或1，取1代表从第i点运垃圾到第j点，取0则不运。ijD：从i点到j点的最短路程。ijK第一步：中转站的个数与位置及小区垃圾去向目标函数：运费与建设成本和最小nnnminKDproUWCWijiijjjj1i1j1约束条件：1、中转站的中转量不超过Zj=1,2nUZWiji12、保证每个点的垃圾只运到一个中转站n1i=1,2,3nUijj1化为问题一。接下求解同问题一。模型求解问题一：第一步：画简化图，求邻接矩阵。简化深圳市南山区垃圾转运站分布图得到加权图：G（V,L其中,vi为简化后的第i个点,i=1,2,3„24,前11个为中转站点,用标出。由图边权可求得邻接矩阵：0(ij),边权(ij,v,v邻接),(ij,v,v不邻接)取1000，由于数据lijijij量大，这里不具体写出）下面是G(V,L)：V1V21222V34.5V.562.5.518V193V1024V11每1.5单位代表1km垃圾中转清运路站第二步：求Dij由邻接矩阵l，通过Floyd算法求出任意点的最短路程，使用VisualC++编ij第三步：求解线性规划模型：使用Lingo软件编程求解。第四步：求中转站到已定的处理厂的最短路线。根据第三步求解得到的处理厂位置和垃圾转运去向，使用Dijkstra算法，求出最短路线，从而得到垃圾的清运路线方案。们不具体求解第二题。结果表示D的值如下：ijLingo求出的规划模型结果为：vvv、、处建立大型垃圾处理厂。267vvv1v、、三处的中转站的橱余垃圾运向处理。242vvvv、、、vv四处的中转站的橱余垃圾运向处理。处理。56967vvvv、、、四处的中转站的橱余垃圾运向378由Dijkstra算法得到的清运路线如下：vv、vvv124132vvv、vvvv、vvvv51669171661019186vv、vvv、vvvvvv3782171124208217结果分析山区垃圾转运站分布图，并对中转站点作出了合理的简化。在此基础上，根据DFloyd算法运用VC++编程求出的两点间最短距离比较精准，再根据规划模ij型利用lingo编程求出结果，软件运行300多万次，显示结果为局部最优，基本可信。最后利用Dijkstra算法求出的清运路线方案基本可信。建设3就是最优解。模型评价了建设3性不强。模型修正必定与最优解有一定的误差，而且难推广，我们经过对原有模型的理解和思考，得到下面的修正模型：符号解释：X：取值0或1，只使用大型设备则取1，否则0；jY：取值0或1，只使用小型设备则取1，否则0；jZ：取值0或1，同时使用大型和小型设备则取1，否则0；jA：大型处理设备的处理能力；a：大型处理设备的建设费用；a：大型处理设备的运行成本；B：小型处理设备的处理能力；b：小型处理设备的建设费用；b：小型处理设备的运行成本。其他符号同原模型。目标函数：运费最小2424DUWijiijj11M/A1aMaXM/B1bMbYjjjjjj24MM/A/B1M/AaM/AjjjjZj1MM/AAbjj约束条件：1、保证中转站不会运垃圾到没有选中为处理厂的点：UWi=1,2,3j=1,2,3j2、保证每个点的垃圾只运到一个处理厂24U1i=1,2,3ijj13、保证作为处理厂的点只选一种处理设备的方案XYZ1j=1,2,3jjj参考文献[1]wen[2]27卷第1期，wen2011年03月。[3]26卷第11wen2006年11月。附录参考文献证明：Floyd算法程序：1、#include<iostream>2、usingnamespacestd;3、floatmin(floata,floatb)4、{5、6、if(a<=b)returna;elsereturnb;7、}8、voidmain()9、{10、11、12、13、14、15、16、17、18、19、20、21、22、23、24、25、26、27、28、29、30、31、32、33、34、35、}float*d[24];for(inti=1;i<=24;i++){d[i]=newfloat[i];for(intj=1;j<=i;j++)cin>>d[i][j];}for(intk=1;k<=24;k++){for(inti=1;i<=24;i++){for(intj=1;j<=i;j++){if(k>=i)d[i][j]=min(d[k][i]+d[k][j],d[i][j]);elseif(k<i&&k>=j)d[i][j]=min(d[i][k]+d[k][j],d[i][j]);elsed[i][j]=min(d[i][k]+d[j][k],d[i][j]);}}}for(i=1;i<=24;i++){for(intj=1;j<=i;j++)cout<<d[i][j]<<"";cout<<endl;}lingo求解程序与结果：程序：model:SETS:/:,W;!定义待定点，期中前9个为垃圾站点，用proW为是否建处理厂。;,U,!UD两个特征，其中Uik点，D为ki的距离;:0000000000000;5520.524.5595068459783774065369760