东三省数学建模一等奖论文.docx
《东三省数学建模一等奖论文.docx》由会员分享，可在线阅读，更多相关《东三省数学建模一等奖论文.docx（30页珍藏版）》请在冰点文库上搜索。
东三省数学建模一等奖论文
摘要
本文以深圳南山区各个垃圾转运站为研究对象，根据转运垃圾量的不同和转运站间的距离不同，存在转运站之间路径最短、总收入最大、总消耗最低三个目标函数。
本文采用了连续模型，将求解目标函数最优值的问题转化为最短路径问题和选址问题。
首先只考虑距离的情况下建垃圾场，本文根据街道办将南山区划分为八个部分，此问题与扩展泰森多边形问题相类似，在建立基于最短路径的扩展泰森多边形模型时,可以舍弃道路网以外的区域而不予考虑,只需对整个道路网进行分析即可，该模型方法比较简单，准确性高，可操作性强。
其次，在计算总消耗时，本文结合最短路径问题，假设各个云转站之间均为直线运用MATLAB算法，算出最少消耗。
在各个街道办选择出垃圾转运中心后，又考虑到实际情况，未必每个垃圾中心都有必要设立，因此本文采用了选址问题求解方法，建立模型，选择出最优垃圾中心位置。
在第二题的求解过程中，取两个服务距离最大的垃圾转运站为边界点，后可直接采用Dijkstra算法，以最远处的两个转运站为端点，求出一条最短的清运路线，取中点建立垃圾中心。
求出任意两垃圾转运站之间最优线路，合并舍掉运输不方便的的转运站。
在该算法中，考虑一站点对其以后其他转运站的最短路径的影响。
Dijkstra算法复杂度较高，但运用该算法可以得到更优化的线路。
最后，本文对模型进行了评价和推广，使其能更好的应用于实际生产生活中。
关键词
连续模型，最短距离，选址问题，采用Dijkstra算法，MATLAB算法
1.问题重述
垃圾分类化收集与处理是有利于减少垃圾的产生，有益于环境保护，同时也有利于资源回收与再利用的城市绿色工程。
在发达国家普遍实现了垃圾分类化，随着国民经济发展与城市化进程加快，我国大城市的垃圾分类化已经提到日程上来。
本项研究课题旨在为深圳市的垃圾分类化进程作出贡献。
为此请你们运用数学建模方法对深圳市南山区的分类化垃圾的实现做一些研究，具体的研究目标是：
1）假定现有垃圾转运站规模与位置不变条件下，给出大、小型设备（橱余垃圾）的分布设计，同时在目前的运输装备条件下给出清运路线的具体方案。
以期达到最佳经济效益和环保效果。
2）假设转运站允许重新设计，请为问题1）的目标重新设计。
仅仅为了查询方便，在题目附录2所指出的网页中，给出了深圳市南山区所有小区的相关资料，同时给出了现有垃圾处理的数据和转运站的位置。
其他所需数据资料自行解决。
2.问题背景及分析
目前， 在城市化进程中，垃圾作为城市代谢的产物曾经是城市发展的负担，世界上许多城市均有过垃圾围城的局面。
而如今，垃圾被认为是最具开发潜力的、永不枯竭的“城市矿藏”，是“放错地方的资源”。
这既是对垃圾认识的深入和深化，是城市发展的必然要求。
2010年5月国家发改委、住房和城乡建设部、环境保护部、农业部联合印发了《关于组织开展城市餐厨废弃物资源化利用和无害化处理试点工作的通知》，并且在北京、上海、重庆和深圳都取得一定成果，但是许多问题仍然是垃圾分类化进程中需要深入研究的。
本文的核心是提出一个解决垃圾中心选择问题的方案。
根据对实际情况的考虑并结合深圳市南山区提供的地图，本文认为垃圾转运的要求主要为转运站之间路径最短、总收入最大、总消耗最低。
这三种需求对应的三个目标函数的最优解的求解与最短路径问题和选址问题相似。
现在如果把三个目标函数的最优解的求解转化为最短路径问题和选址问题，就会遇到以下两个问题：
（1）考虑公路时，线路比较复杂，如何用已知的线路信息建立有向赋权图。
（2）建立有向赋权图之后，如何利用选址问题设立垃圾中心同时使消耗最小。
基于这两个问题，到以下解决办法：
考虑简单的公交线路，即只考虑两转运站间的直线距离。
根据测量转运站间距离的信息建立有向赋权图，使该有向赋权图的最短路径问题可以直接求解，即而利用选址问题的解决方法求出垃圾中心的最佳设立点。
3、模型假设
1、居民区在垃圾站周围呈均匀分布。
2、垃圾运输时，遵循就近原则，直接运往距离其最近的垃圾站。
3、所用人口数据均为常住人口，并不只是在籍人口。
4、当算各个转运站之间距离时，只考虑两点间的直线距离。
5、垃圾转运中心就在某个垃圾转运站处
6、所有垃圾先运往转运站，再由拖车将垃圾分类运往垃圾中心，焚烧场及填埋场。
3、符号说明
P人均垃圾日产生量
Df总收入
A厨余垃圾
B可回收垃圾
C有害垃圾
D其他不可回收垃圾
Eo总消耗费用
Ds收集车消耗
Dc厨余垃圾消耗
Ef转运到焚烧场的耗油量
Et转运到填埋场的耗油量
4、建立目标函数
4．1各转运站间最短路径为目标函数
本文将转运站按街道办划分为八个区域，利用扩展泰森多边形的建立方法将每个街道办按多边形画分开来，最后求出每个街道办处到其他转运站路径最短的转运站，即所求垃圾转运中心，因此各转运站间最短路径为所求目标函数。
4．2总收入为目标函数
Df=max{Df1,Df2}
=max{1000×A+1×a+2.5×b+0.5×c+2.5×d，1500×A+1×a+2.5×b+0.5×c+2.5×d}
4.3总消耗费用为目标函数
Eo=Ds+Dc+Ef+Et
5、模型建立与求解
5．1建立小区的划分区域
只考虑距离的情况下建垃圾场，本文根据街道办将南山区划分为八个部分，此问题与泰森多边形问题相类似，在建立基于最短路径的扩展泰森多边形模型时,可以舍弃道路网以外的区域而不予考虑,只需对整个道路网进行分析即可。
但由于传统的泰森多边形是对空间不考虑路径距离的一种分割方式,使得其在很多领域的应用受到了限制,尤其是在城市规划和沿路径分析等方面表现更为突出。
针对这种情况,本文用一种基于最短路径的扩展泰森多边形的建立方法,并对这种泰森多边形的应用前景提出了自己的看法。
道路是连接整个城市的纽带。
在对城市进行路径分析时,不可能也没有必要深入到每个居民区的内部结构中去,居民区均可用其邻近的道路交通网上的某点代替。
因此,基于这种原因,本文提出了一种转运站分割算法,该算法的精髓是把每一个转运站逐一分配到相应的扩展泰森多边形中，因此本文将南山区按转运站分成三十八个凸多边形。
利用该算法建立基于最短路径的扩展泰森多边形的步骤如下:
1）在转运站覆盖区内任取一条路段。
2）在该路段上任取一点A,A不能为路段的两个端点。
3）算出A点到所有转运站质点的最短路径,并找出其中最短和次短的两条路径（不妨设这两条最短路径分别对应控制点Pi、Pj）,由这两条路径合成的通过A点的路径记为L,取L的路径中点P,P即为Pi、Pj的基于最短路程的泰森多边形的交点,而P分L所得的两段路径则分属Pi、Pj所控制的两个泰森多边形;
4）将L经过的所有路段做上标记,不需再取。
5）如果还有没有取完的路段,则转步骤1）,否则,转步骤6。
6）将每个控制点所控制的路径的端点按照一定顺序连成一个区域,得到基于最短路径的扩展泰森多边形。
5、2求各街道办垃圾转运中心位置
本文以街道办为限，在每个街道办都拟设立一个垃圾转运中心，由于转运垃圾要消耗能源，因此本文假设垃圾转运中心就在某个垃圾转运站处，现建立数学模型如下：
将每个街道办的垃圾转运站视为质点，各质点间距离如下表，利用最短路径问题的求解方法，求出到其他各转动站路径最短的转运站，即为该街道办的垃圾转运中心。
（注：
以下所述距离均为图上距离）
ai为第i行元素（i=1,2……10）
bj为第j列元素（j=1,2……10）
ci为第i行元素之和（i=1,2……10）
dj为第j列元素之和（j=1,2……10）
5．2．1求解西丽街道办垃圾转运中心位置：
1、麻勘公厕垃圾站2、阳光公厕垃圾站3、白芒公厕垃圾站4、牛成公厕垃圾站5、大石勘公厕垃圾站6、官龙村公厕垃圾站7、新围公厕垃圾站8、西丽路公厕垃圾站9、松坪山公厕垃圾站10、松坪山
（二）公厕垃圾站
1
2
3
4
5
6
7
8
9
10
ci
1
0
7.55
8
15.8
13
23
25
31
38.4
39
200.75
2
7.55
0
4
9.6
18.5
21.4
24
29.2
36
36
186.25
3
8
4
0
8
16
18
20
25
32.8
32.8
164.6
4
15.8
9.6
8
0
82.4
16.6
19.5
22.8
29.6
29
233.3
5
13
18.5
16
22.4
0
19
19
25.5
32
34.8
200.2
6
23
21.4
18
16.6
19
0
3
8
15
16
140
7
25
24
20
19.5
19
3
0
6.4
13.6
15.8
146.3
8
31
29.2
25
22.8
25.5
8
6.4
0
7.2
9.6
164.7
9
38.4
36
32.8
29.6
32
15
13.6
7.2
0
5
209.6
10
39
36
32.8
29
34.8
16
15.8
9.6
5
0
218
dj
200.75
186.25
164.6
173.3
260.2
140
146.3
164.7
209.6
218
表5-1
由表5-1可得，在西丽区内官龙村公厕垃圾站到其他垃圾站的距离最短，因此本文设西丽区的垃圾转运中心在官龙村公厕垃圾站。
5．2．2求解桃源街道办垃圾中心位置：
1、福光公厕垃圾站2、塘朗公厕垃圾站3、长源公厕垃圾站4、动物园公厕垃圾站5、光前公厕垃圾站6、龙井公厕垃圾站7、平山村公厕垃圾站
1
2
3
4
5
6
7
ci
1
0
1.4
7
15
21
18.6
16.2
79.2
2
1.4
0
6.6
15.8
20.4
17.8
16.6
78.6
3
7
6.6
0
2.2
26.6
23
23
88.4
4
15
15.8
2.2
0
14.4
17
4
68.4
5
21
20.4
26.6
14.4
0
5.6
11
99
6
18.6
17.8
23
17
5.6
0
13.8
95.8
7
16.2
16.6
23
4
11
13.8
0
84.6
dj
79.2
78.6
88.4
68.4
99
95.8
84.6
表5—2
由表5—2可得，在桃源区内官龙村公厕垃圾站到其他垃圾站的距离最短，因此本文设桃源区的垃圾转运中心在动物园公厕垃圾站。
5．2．3求解南头街道办垃圾转运中心位置：
1、前海公园2、月亮湾大道3、同乐村垃圾站4、九街公厕垃圾站5、玉泉公厕垃圾站6、大新小学垃圾站7、涌下村
1
2
3
4
5
6
7
ci
1
0
0.8
11.8
4.1
10.3
4.9
7.8
39.7
2
0.8
0
11.7
4.8
10.7
5.5
8.5
42
3
11.8
11.7
0
12.5
11
15
17.6
79.6
4
4.1
4.8
12.5
0
7
2.8
5.4
36.6
5
10.3
10.7
11
7
0
9.3
10.6
58.9
6
4.9
5.5
15
2.8
9.3
0
3
40.5
7
7.8
8.5
17.6
5.4
10.6
3
0
52.9
dj
39.7
42
79.6
36.6
58.9
40.5
52.9
表5—3
由表5—3可得，在南头区内九街公厕垃圾站到其他垃圾站的距离最短，因此本文设南头区的垃圾转运中心在九街公厕垃圾站。
5．2．4求解粤海街道办垃圾转运中心位置：
1、大冲公厕垃圾站2、深圳大学垃圾站3、科技园公厕垃圾站
1
2
3
ci
1
0
7.6
10.3
17.9
2
7.6
0
6.2
13.8
3
10.3
6.2
0
16.5
dj
17.9
13.8
16.5
表5—4
由表5—4可得，在粤海区内深圳大学垃圾站到其他垃圾站的距离最短，因此本文设粤海区的垃圾转运中心在深圳大学垃圾站。
5．2．5求解沙河街道办垃圾转运中心位置：
1、沙河市场垃圾站2、白石洲南公厕垃圾站3、华侨成公厕垃圾站
1
2
3
ci
1
0
7.8
12.5
20.3
2
7.8
0
14
21.8
3
12.5
14
0
26.5
dj
20.3
21.8
26.5
表5—5
由表5—5可得，在沙河区内沙河市场垃圾站到其他垃圾站的距离最短，因此本文设沙河区的垃圾转运中心在沙河市场垃圾站。
5．2．6求解南山街道办垃圾转运中心位置：
1、南山市场公厕垃圾站2、北头公厕垃圾站3、南园公厕垃圾站4、南光公厕垃圾站5、南山村公厕垃圾站
1
2
3
4
5
ci
1
0
3
3.2
4.2
8
18.4
2
3
0
1.8
5.1
5
14.9
3
3.2
1.8
0
3.5
5.3
13.8
4
4.2
5.1
3.5
0
8.5
21.3
5
8
5
5.3
8.5
0
26.8
dj
18.4
14.9
13.8
21.3
26.8
表5—6
由表5—6可得，在南山区内南园公厕垃圾站到其他垃圾站的距离最短，因此本文设南山区的垃圾转运中心在南园公厕垃圾站。
5．2．7求解蛇口街道办垃圾转运中心位置：
1、花果路公厕垃圾站2、望海路垃圾站
1
2
ci
1
0
2.2
2.2
2
2.2
0
2.2
dj
2.2
2.2
表5—7
由表5—7可得，在蛇口区内花果路公厕垃圾站到其他垃圾站的距离最短，因此本文设蛇口区的垃圾转运中心在花果路公厕垃圾站。
5．2．8求解招商街道办拟垃圾中心位置：
因为招商街道办处只有疏港小区一个垃圾转运站，因此将转运转运中心设于此。
5、3确定垃圾处理中心位置
由上述可得，各街道办的垃圾转运中心分别设在官龙村公厕垃圾站、动物园公厕垃圾站、九街公厕垃圾站、深圳大学垃圾站、沙河市场垃圾站、南园公厕垃圾站、花果路公厕垃圾站、疏港小区垃圾站。
考虑到实际情况，未必每个垃圾中心都有必要设立，因此本文用选址问题求解方法，建立数学模型：
测出任意两个垃圾中心vi和vj之间的最短路径长度d（vi,vj）=dij，求出最大服务距离越小的点，设置为垃圾处理中心。
5、3、1人均垃圾日产生量P为：
5、3、2根据所给地图求出图例面积（距离）与实际面积（距离）比：
本文按题中所给地图的26.3%印出地图，利用油膜法测出所印地图的面积为392平方厘米。
则所给地图实际面积为392/0.263=1490.49平方厘米。
又查得南山区实际面积为188.3平方千米，由此得出面积比为：
1490.49:
188.3=1:
1263000000,距离比为：
1:
35500。
5、3．3具体求解过程
用v1、v2……v8分别表示官龙村公厕垃圾站、动物园公厕垃圾站、九街公厕垃圾站、深圳大学垃圾站、沙河市场垃圾站、南园公厕垃圾站、花果路公厕垃圾站、疏港小区垃圾站。
建立无向赋权图如图5—1。
图5—1
本文测出任意两个垃圾中心vi和vj之间的最短路径长度d（vi,vj）=dij,得矩阵d=（dij）如下：
v1v2v3v4v5v6v7v8l（vi）
v10728272437.2505656
v2703331.224.44243.661.661.6
v328330112410.827.63033
d=v42731.211014.612.82331.831.8
v52424.42414.6027.232.845.245.2
v637.24210.812.827.2017.620.242
v75043.627.62332.817.6015.850
v85661.63031.845.220.715.8061.6
本文依次对定点vi求l（vi）（i=1,……，8）：
l（vi）=max{dij┃j=1,……，8}
称l（vi）为vi的最大服务距离，并将（l（v1），....l（v8））T置于矩阵d的最右列。
l（vi）的实际意义是：
如果本文把垃圾转运中心设在vi，，那么垃圾处理中心与最远的服务对象间的距离是l（vi）。
这样，最大服务距离越小的点，设置为垃圾处理中心就越好。
现在
min{l（v1）,….l（v8）}=min{56,61.6,33,31.8,45.2,42,50,61.6}
=31.8
=l（v4）.
需要处理的垃圾量=1280×0.4=512，由于一个大厨余处理垃圾能力为200吨，所以估计至少需要建立两个垃圾中心。
假设设置两个垃圾处理中心，则设在v3，v4处较好。
假若设在v3和v4，那么对点v1来说，垃圾可以运往v3也可以运往v4，由矩阵d知d13=28,及d14=27,这样，v1处的垃圾自然选到v4处运送，其服务距离为27。
本文依次找出v2，……，v8的服务距离，将相关信息列成表5—8。
Vj
V1
V2
V3
V4
V5
V6
V7
V8
d（vj,v3）
28
33
0
11
24
10.8
27.6
30
d（vj,v4）
27
31.2
11
0
14.6
12.8
23
31.8
距离
27
31.2
0
0
14.6
10.8
23
30
表5—8
从表中可看出，当垃圾中心设在V3和V4时，最大服务距离为
max{27,31.2,0,0,14.6,10.8,23,30}=31.2
记
l（V3,V4）=31.2
本文求任意一对Vi和Vj的最大服务距离l（V3,V4），并将它们列成矩阵L=（l（V3,V4））:
v1v2v3v4v5v6v7v8
v1―563031.845.22427.628
v256―3031.845.224.427.631.2
v33030―31.230333333
v431.831.831.2―31.831.231.231.2
v545.245.23031.8―24.424.424.4
v62424.43331.224.4―4242
v727.627.63331.224.442―50
v82831.23331.224.44250―
由矩阵L可知，
l（V1,V6）=24
在诸l（Vi,Vj）中卫最小，故垃圾中心拟设在V1及V6。
由地图可得，应将桃源街道办出的全部垃圾和沙河街道办的部分垃圾运往V1处处理，
沙河街道办：
沙河市场垃圾站的厨余垃圾量=53.853×0.4=21.54（t）
白石洲南公厕垃圾站的厨余垃圾量=53.853×0.4=21.54（t）
华侨城公厕垃圾站的厨余垃圾量=125.693×0.4=50.27（t）
因为一个大厨余可以处理200吨垃圾，为了最大限度节省能源，本文将西丽、桃源街道办的全部厨余垃圾，以及沙河市场垃圾站的全部厨余垃圾和华侨城公厕垃圾站其中的40.816吨厨余垃圾运往V1处的垃圾处理中心处理。
经计算，南头、南山、粤海街道办的总厨余垃圾量为200.8吨，故将南头、南山、粤海处的全部厨余垃圾运往V6处的垃圾处理中心处理。
再在各个垃圾转运站建立小厨余。
由于运输消耗的油费与垃圾处理设备投资相比很小，可忽略不计。
此时所需费用为：
4500×2+（512—400）÷0.3×28=19453.3（万元）
若设立三个大厨余垃圾设备此时所需费用为：
4500×3=13500（万元）
∵13500＜19453.3
∴应设立三个大厨余。
又因为沙河街道办处的垃圾量最多，所以第三处垃圾处理中心应设在沙河街道办处的沙河市场垃圾站。
三个垃圾处理中心分别建立在v1，v5，v6，每处都设立一个大厨余设备。
5.4总收入范围：
题中所给垃圾总量为1280t,且A:
B:
C:
D=4:
2:
1:
3，a:
b:
c:
d=55:
35:
6:
4，其中a,b,c,d分别为纸类，塑料，玻璃，金属，其价格为每公斤1元，2.5元，0.5元，2.5元，且厨余垃圾处理后的产物价格在1000—1500元/吨。
则
A=1280×0.4=512tB=1280×0.2=256t
C=1280×0.1=128tD=1280×0.3=384t
a=256×0.55=140.8tb=256×0.35=89.6t
c=256×0.06=15.36td=256×0.04=10.24t
则
Df1=1000×512+140800×1+89600×2.5+15360×0.5+10240×2.5
=761040（元）
Df2=1500×512+140800×1+89600×2.5+15360×0.5+10240×2.5
=1017040（元）
其总利益的范围：
761040≤Df≤1017040
5.5总消耗费用：
5．5．1收集车消耗：
假设以各个转运站为圆心，2km为半径作圆，其所覆盖的面积为小区分布处，运用积分求出各个转运站所覆盖的面积，再乘以垃圾总数除以每辆收集车运送吨数，再乘以每车每公里耗油量即为收集车的消耗。
下面以西丽街道办的麻堪公厕垃圾站为例：
S=πr2dr=0.5π（23—03）=12.56
收集车每公里耗油费=7.31×20÷100=1.462（元）
收集车消耗=12.56×12.749÷2.5×1.462=93.64（元）
因此所有收集车为Ds=38×93.64=3558.32（元）
其余垃圾转动站在收集车上所耗的费用算法同上。
5．5．2厨余设备消耗：
大厨余垃圾处理设备投资Dc=4500×3=13500（万）
转运站到焚烧场的运行成本：
经查得柴油的价钱为7.17元/升，由题意可
升级会员 