数学建模之垃圾处理
城市生活垃圾管理问题研究
摘要
近年来，随着垃圾产量的日益增加，人们已经逐渐意识到它对生态环境及人类生存带来的极大威胁。本文针对垃圾处理问题，先采用一元线性回归和最小二乘曲线拟合的方法，求出垃圾产量的预测模型，再采用图论法，得到垃圾最短收运路径以及最佳车辆分配方案。
对于第一问，我们根据题意找到影响垃圾产量的六个因素，查得相关数据后，
式，如下：
12345638.262618.38748.0855 5.7036 2.9462 4.5376Y y y y y y y =-+++++ 这样，在已知年份的条件下，可以通过各个影响因素的值，预测出垃圾的产量。由于预测量考虑了实际中的各个影响因素，故具有准确性和较高的实用性。
对于第二问，我们经过数据预处理，画出以车库为原点的垃圾收集点、中转站分布图。接着，根据题中垃圾车的最大装载量与垃圾站的分布特点将数据分成十二区域，用图论法在每个区域中找到最小生成树，为了避免垃圾收运车走重复路线，我们通过观察，将最小生成树的树叶融入树中，形成一条链，即为垃圾收运车的最短收运路线。在得到12个区域的最短路径图后，我们将行驶时间、装
为3辆垃圾收运车每辆每天前往4个区域收运垃圾。
运用以上方法得到的收运路线，不但满足题设条件（不超过垃圾车的最大装载量、日负载总量以及最多日收集点数），而且还能使垃圾的收运时间最短，另外该模型可以提出合理的车辆分配方案，提高了资源利用率。因此，本模型具有较好的实用性和可靠性。
关键词 垃圾预产量 线性回归 最小二乘曲线拟合 图论法 收运路线
1.问题的重述
由于人类生产和生活的不断发展而产生的垃圾对生态环境及人类生存带来极大的威胁已逐步成为重要的社会问题。城市生活垃圾是居民生活、消费过程中产生的废弃物，其年增长速度达8-10%，因此导致城市垃圾的数量日益庞大，并且其组分复杂还处于不断变化中, 使处理费用慢慢升高。另一方面城市垃圾占用大量土地、污染水体、污染大气、破坏植被, 严重影响城市的市容景观和居民的生活环境[1]。城市垃圾已成为各国政府急需妥善解决的首要问题之一。
城市垃圾管理包括计划、组织、行政、金融、法律和工程等多方面，并涉及到城市生活垃圾收集、运输和处置。而中国目前处置水平低，管理办法不多，更是急待解决的问题。在这方面，世界许多国家在谋求解决城市生活垃圾过程中，产生出许多好的办法，并在此过程中总结了经验和教训。
一般认为城市生活垃圾的影响因素包括地理位置、人口、经济发展水平（生产总值）、居民收入以及消费水平、居民家庭能源结构等等。城市生活垃圾产量是垃圾管理系统的关键参数，城市在建造垃圾填埋场之前,必须对该地区的未来垃圾产量进行合理预测。若对城市垃圾产生量的估计过高,相应的填埋场库容设计必然增大,各种投资亦相应增加,将导致物力财力的巨大浪费;若对垃圾产量估计过低,在未达到填埋场设计使用年限时就将被迫关闭,不得不投资另行建造其他填埋场或对填埋场进行扩容,同样会导致物力财力的浪费[2]。因此对未来某段时间内垃圾产量的准确预测是相关垃圾管理的部门做出管理规划的前提。
另外，城市垃圾自其产生到最终被送到处置场处理，需要环卫部门对其进行收集与运输，这一过程称为城市垃圾的收运。收运过程可简述如下：某城市有多个行政区，每个区内均有一个车库，假设某一车库拥有最大装载量为w的垃圾收集车k 辆，并且该区的垃圾收集点（待收集垃圾的点）有n 个，该城市共有垃圾中转站p 座。每天k 辆垃圾车从车库出发，经过收集点收集垃圾，当垃圾负载达到最大装载量时，垃圾车运往中转站，在中转站卸下所有收运的垃圾，然后再出站收集垃圾，如此反复，直到所有收集点的垃圾都被收集完，垃圾车返回车库。以上收运过程均在各点的工作区间之内完成。（注：必须在收集点的工作区间之内，垃圾车才能在该点收集垃圾。）
请利用数学方法建立以下问题的数学模型并求解，对模型的结果做出合理分析和解释。
1. 在查阅相关文献，搜集垃圾产量数据的基础上建立城市生活垃圾产量中短期预测模型，并且分析模型的准确性和实用性。
2. 在收运过程已知下述（1）（2）（3）（4）等条件下，如何安排垃圾收运车的收运路线，使垃圾收运车的行车里程尽可能的少，或者垃圾收运时间尽可能短？
（1）车库和收集点、收集点与中转站、中转站与车库的距离；
（2）各收集点每天的垃圾产量；
（3）每辆垃圾收运车的最大载荷；
（4）垃圾收集点、车库、中转站的工作区间[a,b]。
请给出规划以上垃圾收运路线的数学模型，并设计出有效的算法，针对题中给出的数据，求解模型。并且对模型的适用性、算法的稳定性和鲁棒性做出分析。
2.问题的分析
2.1. 分析影响城市生活垃圾的因素
城市生活垃圾的影响因素决定了城市生活垃圾的总量，而这些影响因素包括城市规模、城市经济的发展程度、城市人口的多少及居民的收入、消费水平等诸多方面，故此处首先查阅相关资料[3]，了解以往在解决此类问题时的标准，再根据近几年我国居民消费水平，生活方式能源结构等方面的变化规律进行分析，最终得到对城市生活垃圾总量影响显著的几个因素如下：
（1）人口数量：随着人口的不断增加以及城市人口流动的不断加剧，在人均垃圾产量稳定变化的基础上人口的变化必定造成城市生活垃圾产量的变化；（2）生产总值：生产总值的变化意味着居民生活水平的改变, 居民生活水平的好坏直接关系到其生活方式的调整，不同的生活方式会对城市生活垃圾产量的大小造成影响；
（3）城市居民人均收入、人均消费水平：是居民生活水平的指标，人均收入关系到消费水平，而消费增水平的改变导致购买力发生变化；
（4）人均住房面积、城市燃气普及率：人均住房面积的波动关联到供暖面积，而供暖需要消耗能源，故影响到垃圾的产生量；城市燃气普及率的高低意味着煤炭等产生固体垃圾的能源消耗量的多少。
2.2. 搜集城市生活垃圾产量数据
随机选定重庆市作为研究对象，在中国国家统计局网站上查到其2001~2006年人口数量、国内生产总值等各影响因素及垃圾产量的统计数据如表格 2.2-1：
表格 2.2-1
年份
生产总
值/亿元
城市居民人
均收入/元
人均消
费水平/
元
人口数
量/万人
人均住
房面积/
平方米
城市燃
气普及
率/%
垃圾产
量/万
吨
2001 1765.68 6572.3 1078.06 3097.91 22.5 32.2 164.6 2002 1990.01 7238.07 1228.89 3113.83 23.9 46.6 211.7 2003 2272.82 8093.67 1415.31 3130.1 25.72 59.5 215.3 2004 2692.81 9220.96 3596 3144.23 28.25 63.52 237.2 2005 3070.49 10243.99 4782 3169.16 30.68 68.84 237.6 2006 3452.14 11569.74 5417 3198.87 31.36 75.84 243.9
2.3. 整体分析得城市生活垃圾产量中短期预测模
首先画出各个影响因素与年份之间的散点图，确定为线性关系，建立一元线
性回归模型，求解方程参数；再确定垃圾产量与各影响因素的近似拟合曲线，利用最小二乘原理得出精确的拟合方程；综上，将两次求得关系通过方程联立，即得最终预测模型。
2.4. 构建垃圾收运路线的模型
对题目所给的数据进行预处理，画出车库、中转站、垃圾收集点分布图，以不超过每辆车的最大装载量为依据将垃圾收集点分组，接着，利用图论法画出每组的最小生成树，将树叶融入树中，形成最优路线。根据最优路线算出从车库出发到收集完垃圾回车库所用的总时间，进一步确定合理安排车辆收运垃圾的方案。
3.模型的假设
1.假设影响垃圾产量的只有内在因素（如人口数量、居民生活水平等），不包
括社会因素（如社会行为准则、社会道德规范）和个体因素（人类本身个体的行为习惯、受教育程度）[4]；
2.假设垃圾产量只包括被清运的垃圾，散落的垃圾不予统计。查询垃圾产量统
计数据时即默认为生活垃圾清运量；
4.符号说明
5.模型的建立
5.1. 模型一：城市生活垃圾产量中短期预测模型
5.1.1.建立城市生活垃圾产量的各影响因素与年份的关系
（1）初步判断年份与城市生活垃圾产量的影响因素
先根据年份x与影响因素y的试验值画出散点图，根据散点图确定须配曲线的类型。此处以生产总值为例，画出散点图，如图 5.1-1：
图 5.1-1
由图中散点知，数据点大致落在一条直线附近，故确定为一次函数曲线（其他几个因素均如此），建立一元线性回归模型：
???==++=2
10,0σεεε
ββD E x y 其中固定的未知参数0β、1β称为回归系数，自变量x 也称为回归变量。 将x Y 10ββ+=，称为y 对x 的回归直线方程
（2）用n 对试验值n i y x i i ,...,2,1),,(=对0β、1β和σ作最小二乘估计
设 012
12,1,2,...,0, ,...,i i i i n y x i n
E D ββεεεσεεε=++=???==??且相互独立
记 ()∑∑==--===n
i i i n i i
x y Q Q 1
2
101
2
10),(ββεββ
解得 011
22???y x xy x y x x βββ?=-??-=?-?
或 ()()
()
∑∑==---=n
i i
n
i i i
x x
y y x x
1
2
1
1?β
其中 2
21111
1111,,,n n n n i i i i i i i i i x x y y x x xy x y n n n n ========∑∑∑∑
得回归方程 )(????110x x y x y -+=+=βββ （3）检验回归方程x Y 10ββ+=的显著性
归结为对假设0:;0:1110≠=ββH H 进行检验。假设01:0H β=被拒绝，则回归显著，认为y 与x 存在线性关系，所求的线性回归方程有意义；否则回归不显著，y 与x 的关系不能用一元线性回归模型来描述，所得的回归方程也无意义。 F 检验法：当0H 成立时，)
2/(-=
n Q U
F e ~()1,2F n -
其中 ()∑=-=n
i i y y U 1
2?（回归平方和），当F >)2,1(1--n F α时，拒绝0H ，否则就
接受0H 。
（4）判断回归系数01,ββ的置信区间
0β和1β置信水平为1-α的置信区间分别为：
???
?????+-++----xx e xx e L x n n t L x n n t 221022101?)2(?,1?)2(?σβσβα
α 和 ??
????-+---
-xx e xx e L n t L n t /?)2(?,/?)2(?211211σβσβαα 5.1.2. 确定垃圾产量与其各影响因素的关系
（1）确定拟合函数
观测影响因素与垃圾产量的一系列数据集，考虑借助曲线拟合用一个相对简单的解析曲线去逼近所得到的数据集，但拟合的曲线往往不能完全符合给出的数据，因此需要对拟合的性能给出一个量度，这里使用最小二乘原理（极小化偏差的平方和）作为衡量曲线拟合优劣的准则，它不要求得到的曲线过所有的点（可消除误差的影响），只要求在给定点上的误差的平方和最小；并且能够尽可能表现数据的趋势，靠近原来的数据点。
这里选择形如()()()()()001122n n Y s x a y x a y x a y x a y x ==++++…的式子作为拟合的曲线
式中()()()[]01,,,,n y x y x y x C a b ∈…是线性无关的函数族 （2）根据最小二乘原理先求法方程系数
假定在[],a b 上给出一组数
据
(){},,10,1,i
i
x Y =…,m ，
i a x b ?≤≤以及对应的一组权{}0m
i ρ，这里0i ρ>为权系数，要求
(){}01,,s x span y y =n …,y 使()01,,n I a a a …，最小，其中
2010
(,,...,)[()]m
n i i i i I a a a s x Y ρ==-∑
()01,,n I a a a …，实际上是关于12,,n a a a …，的多元函数，求I 的最小值就是求多元函数I 的极值，由极值必要条件，可得
00110
2[()()...()]()0,1,...,m
i i i n n i i k i i k I
a y x a y x a y x Y y x n a ρ=?=+++-=?∑ 根据内积定义引入相应带权内积记号
0(,)()()(,)()
m
j k i j i k i i m
k i i k i
i y y y x y x Y y Y y x ρρ==?
=????=??
∑∑ 则可改写为
()()()()n k Y y a y y a y y a y y k n k n k k ,,1,0,,,,,1100??==+??++
这是关于参数
的线性方程组，用矩阵表示为
0001
00101111101(,)(,)(,)(,)(,)(,)(,)(,)(,)(,)(,)(,)n n n n n n n n y y y y y y a Y y y y y y y y a Y y y y y y y y a Y y ????????????????????=??????:::::?????????????
上式称为法方程。当
(){}
,0,1,j
y x j n =…，线性无关，且在点集
{}()01,,,m X x x x m n =≥…上至多只有n 个不同零点，则称、01,,,n y y y ……在X 上满足Haar 条件，此时法方程的解存在唯一，其解为
*
,0,1,k k a a k n ==…，
从而得到最小二乘拟合曲线
****0011()()()...()n n Y s x a y x a y x a y x ==+++
5.2. 模型二：垃圾收运路线规划模型
根据垃圾车最大装载量和数据分布将所给数据分成若干个区域，每个区域均
有若干个点，通过图论生成最小生成树，找到连接所有垃圾收集点的最小路径。 通过Prim 算法[5]求所分区域的最小生成树，方法如下：
（1）建立以两点间距离为权值的权邻接矩阵[(,)]n n a i j ?，其中一两点间的Manhattan 距离为权值，计算公式如下：
11221212(,) ((,),(,))distance x y x y x y x x x y y y =-+-==
（2）建立初始候选边表,B T φ←;
（3）从候选边中选出最短边(,),(,)i j T T i j ←?；
（4）调整候选边集B ; （5）重复（2）、（3）直到T 中含有1n -条边。
通过上述算法得到的线路即为连接各点的最小生成树，其特点是边权和最小。但是，垃圾的收运不是简单的连接问题，而最小生成树形成的路线需要在树杈路线上回返，这样就会增加行程，故在最小生成树的基础上比较树杈与其相邻的权边，以边权增加最小为原则进行边替换，将树叶融入主干，这样便可以得到能将所分区域的所有垃圾收集点串联起来的一条“链”，且其权和最小，该“链”即为最佳的行车路线。
6. 模型的求解
6.1. 确定年份与城市生活垃圾产量各影响因素的关系式 6.1.1. 求解影响因素与年份的一元回归模型
以生产总值因素为例，假设变量x 与y 满足如下关系： b y ax =+，运用MATLAB 中一元线性回归程序处理数据分析得： 345.5a =， 1331.3b =，方程为1345.5 1331.3y x =+
由拟合结果知：a 的置信区间为[297.7，393.4]，b 的置信区间为[1144.9，1517.7]。相关系数r 2为0.9901，F 的值为401.6431，与F 对应的概率p 为0.0000。
由于相关系数r 2越接近1，说明回归方程越显著；F 越大，说明回归方程越显著；与F 对应的概率p 小于显著性水平(缺省时为0.05）时，回归模型成立。故回归方程及参数拟合准确。
根据上述步骤对其他指因素回归方程、相关系数r 2、F 的值以及F 对应的概率p ，如表格 6.1-1：
表格 6.1-1
由表格中数据可以看出：每组数据模拟出方程的r 2数值都接近于1，p 的值也远小于0.05，故可认为模型假设正确
6.1.2. 求解垃圾产量与影响因素的多元回归模型
对于各个指标与垃圾清运量的关系我们借助调用MATLAB 优化工具箱中最小二乘曲线拟合函数lsqlin （源程序见附录1）求解得：
12345638.262618.38748.0855 5.7036 2.9462 4.5376Y y y y y y y =-+++++
综合上述两个模型，在已知年份的条件下，可以通过求解各个影响因素的值，预测出垃圾的产量。此模型即为垃圾产量预测模型。 6.2. 求解垃圾收运路线的规划模型 6.2.1. 数据预处理
分析题中已知数据发现有垃圾站点重复现象，我们将重复点的垃圾量相加，得到该点垃圾总量，并以车库为原点进行数据平移，画出中转站、垃圾收集点的相对位置，如图 6.2-1：
图 6.2-1
6.2.2.确定垃圾收集分组区域
根据车库、中转站、垃圾收集点的相对位置图，从最左边的收集点开始，以不超过每辆垃圾车的最大装载量为依据，对收集点进行分组，得到12个垃圾收集分组区域。
6.2.3.画最小生成树图
针对区域一的数据，利用图论法编程（源程序见附录2），得到最小生成树如图 6.2-2：
图 6.2-2
6.2.4.画最短路径图，得最优路线
由上图可看出，如果按照上述路线进行收运垃圾，存在同一路线的往返问题，无疑增加了垃圾车的行程，使垃圾收运时间变长，故在此图的基础之上，根据权值比较对树杈进行修改，将其融入树干连成一条链，即得到此区域内经过所有点的最短路径（源程序见附录3），路线图如图 6.2-3：
图 6.2-3
在垃圾收运时，垃圾车从车库出发到达相对于中转站而言的最远点，沿上图路线收运垃圾，将垃圾送到中转站后再回到车库，此即为最优路线。
按照以上方法画出其他十一个区域的垃圾收运最优路线。（最小生成树图与最短路径图见附录4）
6.2.5.提出车辆最佳分配方案
在得到12个区域的最短路径图后，依次对各个垃圾收集点之间的距离求和，将该值与车库到最远收集点的距离，以及中转站到最近收集点的距离相加，得行车里程。此时，行车里程与垃圾车的行车速度的比值，即为行驶时间。接着，我们将行驶时间、装车时间、卸车时间相加，得到在每个区域收集垃圾的总时间(h)，如表格 6.2-1：
表格 6.2-1
行车里程行驶时间(h) 装车时间(h) 卸车时间(h) 总时间(h)
289196 1.3693 0.23611 0.5 2.1054
275794 1.3058 0.22917 0.5 2.035
269512 1.2761 0.17361 0.5 1.9497
268638 1.272 0.19444 0.5 1.9664
209118 0.99014 0.27778 0.5 1.7679
199050 0.94247 0.20833 0.5 1.6508
197228 0.93384 0.26389 0.5 1.6977
204222 0.96696 0.20139 0.5 1.6683
213524 1.011 0.22917 0.5 1.7402
232556 1.1011 0.25 0.5 1.8511
219346 1.0386 0.28472 0.5 1.8233
219300 1.0384 0.16667 0.5 1.705
由上表总时间可以看出，只有区域一、二的时间略微超过两小时，可近似按两小时计算，其余十个区域均小于两小时。根据国家规定，每个工作日的工作时间为八小时，故每辆车每天可以收集四个区域的垃圾，所以车库每天至少需要3辆垃圾收运车，最佳的车辆分配方案为3辆车每天前往4个区域收运垃圾。
7.模型的检验
以生产总值为例，检验城市生活垃圾产量影响因素与年份的一元回归模型。做残差图，如下：
从残差图可以看出，除第1个数据外，其余数据的残差离零点均较近，且残
差的置信区间均包含零点，这说明回归模型345.5 1331.3
=+能较好的符合原
y x
始数据，而第1个数据可视为异常点。
同上对其他影响因素作残差分析，结果如下：
其中正常数据点的残差均离零点较近，置信区间包含零点，故回归模型能较好的反应原始数据，准确性较高。
8.模型的评价
通过建立模型一，我们便可以在已知年份的条件下，借助各个影响因素的值，预测出垃圾的产量，便于相关垃圾管理的部门做出管理规划综合整治、处理垃圾，利于城市市容景观和居民生活环境的改善。此种预测方法考虑了实际中的各个影响因素，故具有准确性和较高的实用性。
通过模型二求得的最优收运路线，不但考虑到垃圾车的最大装载量、日负载总量和最多日收集点数，而且还能使垃圾的收运时间最短，另外该模型可以提出合理的车辆分配方案，提高了资源利用率。因此，本模型具有较好的实用性和可靠性。
9.参考文献
[1]刘守芳,刘沙等.城市垃圾产量预测研究.云南环境科学.2006,25(1):28-30
[2] 廖智强等.基于指数趋势模型在城市垃圾产量预测中的应用.环境保护科学.2006,32(4),27-29
[3]王欢,王伟.城市生活垃圾产生量及组分的预测方法研究.环境卫生工程.2006,14(4):6-8
[4] 向盛斌.城市居民生活垃圾影响因素分析及产量预测.环境卫生工程.1998,6(1):7-12
[5]傅鹂、何中市等.数学实验.北京:科学出版社.2000.215-218
10.附录
附录1
clear
clc
b=load('shuju.txt');
A=zscore(b);
Y=[A(:,8)];
x1=[A(:,2)];
x2=[A(:,3)];
x3=[A(:,4)];
x4=[A(:,5)];
x5=[A(:,6)];
x6=[A(:,7)];
X=[x1 x2 x3 x4 x5 x6];
[x,resnorm,residual,exitflag,output,lambda]=lsqlin(X,Y)
附录2
clear
clc
B=[-39337,-38419,-38154,-38112,-37730,-37730,-37475,-37308,-37167,-36280,-355 94,-35587,-35567,-35067,-34803,-34519,-34388,-34383,-34326,-34049,-33872,-3369 7;
19154,18370,19940,15957,23121,23121,23760,17139,23875,12596,16592,10230,199 10,23446,19963,22756,14327,23362,20343,18801,19928,23018]'
a=mandist(B,B');
T=[];c=0;v=1;n=length(B(:,1));sb=2:n;
for j=2:n
b(1,j-1)=1;
b(2,j-1)=j;
b(3,j-1)=a(1,j);
end
while size(T,2) [min,i]=m(b(3,:)); T(:,size(T,2)+1)=b(:,i); c=c+b(3,i); v=b(2,i); temp=find(sb==b(2,i)); sb(temp)=[];b(:,i)=[]; for j=1:length(sb) d=a(v,b(2,j)); if d b(1,j)=v;b(3,j)=d; end end end A=B'; x=A(1,:); y=A(2,:); plot(x,y,'.') for i=1:length(x),text(A(1,i),A(2,i)+800,sprintf('%g',i)),end for j=1:size(T,2) k1=T(1:2,j); k=k1'; hold on plot(x(k),y(k)) end 附录3 clear clc A=[-39337,-38419,-38154,-38112,-37730,-37730,-37475,-37308,-37167,-36280,-355 94,-35587,-35567,-35067,-34803,-34519,-34388,-34383,-34326,-34049,-33872,-3369 7;19154,18370,19940,15957,23121,23121,23760,17139,23875,12596,16592,10230,1 9910,23446,19963,22756,14327,23362,20343,18801,19928,23018]; x=A(1,:); y=A(2,:); plot(x,y,'.') for i=1:length(x),text(A(1,i),A(2,i)+200,sprintf('%g',i)),end k=[6 7 9 14 16 18 22 21 20 19 13 3 1 2 4 8 11 17 10 12]; hold on plot(x(k),y(k)) 附录4 区域二区域三 区域四区域五 区域六区域七 区域八区域九 区域十区域十一 区域十二 多变量有约束最优化问题 摘要 本文以一家运输航空公司的一架飞机运载能力100吨和运载货物的容量50000立方英尺有限的情况下，有三种货物（即x1、x2、x3）需要运输，公司规定每吨货物收取一定的费用，而要运输的每种货物的吨数都有规定的上限（最多不超过30吨、40吨、50吨），并且公司规定由于飞机需要保养与维护，飞机须停飞115天，因此每年只有250天的工作时间。在此情况下每天怎样安排运输三种货物使公司每年获得最大利润w。对于此问题只用线性规划的一般方法建立相应的数学模型，在用数学软件求出在给定限行区域内的最优解（w、x1、x2、x3），在对这些最优解进行分析与讨论，确定其为有效最优解。并以此作为公司对三种货物运输安排方式。 对于问题一，求使得运输航空公司获得最大利润w的x1、x2、x3三种货物的吨数，建立相应的数学模型。再根据运输能力最多100吨和运载货物容积的最大50000立方英尺，还有每天公司规定的每种货物的运输上限即x1种货物最多运输30吨，x2种货物最多运输40吨，x3种货物最多50吨，建立约束条件。并用数学软件mathematica进行求解，即为所求的最优解（也就是w=21875，x1=30，x2=7.5，x3=50）。 对于问题二中，要求计算每个约束的影子价格。我们将利用问题一中建立的目标函数和约束条件，将其编写成源程序输入到Lindo软件中进行求解。再将得到的界进行讨论与和模型的稳健性分析并且通过其在题意的理解，解释其含义。 问题三中，对于公司将耗资改装飞机以扩大运货区来增加运输能力，且旧飞机使用寿命为5年，每架飞机的改造要花费200000美元，可以增加2000立方英尺的容积。重量限制仍保持不变。假设飞机每年飞行250天，这些旧飞机剩余的使用寿命约为5年。根据此问题我们将建立数学规划模型，利用Lindo软件计算其影子价格和利润并且与前面进行比较，进行分析。 关键词：线性规划、mathematica软件的应用、Lindo的软件应用。 数学建模大赛货物运输 问题 SANY标准化小组 #QS8QHH-HHGX8Q8-GNHHJ8-HHMHGN# 货物配送问题 【摘要】 本文是针对解决某港口对某地区8个公司所需原材料A、B、C的运输调度问题 提出的方案。我们首先考虑在满足各个公司的需求的情况下，所需要的运输的 最小运输次数，然后根据卸载顺序的约束以及载重费用尽量小的原则，提出了 较为合理的优化模型，求出较为优化的调配方案。 针对问题一，我们在两个大的方面进行分析与优化。第一方面是对车次安排的优化分析，得出①~④公司顺时针送货，⑤~⑧公司逆时针送货为最佳方案。第二方面我们根据车载重相对最大化思想使方案分为两个步骤，第一步先是使每个车次满载并运往同一个公司，第二步采用分批次运输的方案，即在第一批次运输中，我们使A材料有优先运输权；在第二批次运输中，我们使B材料有优先运输权；在第三批次中运输剩下所需的货物。最后得出耗时最少、费用最少的方案。 耗时为小时，费用为元。 针对问题二，加上两个定理及其推论数学模型与问题一几乎相同，只是空载路径不同。我们采取与问题一相同的算法，得出耗时最少，费用最少的方 案。耗时为小时，费用为元。 针对问题三的第一小问，我们知道货车有4吨、6吨和8吨三种型号。我们经过简单的论证，排除了4吨货车的使用。题目没有规定车子不能变向，所 以认为车辆可以掉头。然后我们仍旧采取①~④公司顺时针送货，⑤~⑧公司逆 时针送货的方案。最后在满足公司需求量的条件下，采用不同吨位满载运输方案，此方案分为三个步骤：第一，使8吨车次满载并运往同一公司；第二，6 吨位车次满载并运往同一公司；第三，剩下的货物若在1~6吨内，则用6吨货 车运输，若在7~8吨内用8吨货车运输。最后得出耗时最少、费用最省的方 案。耗时为小时，费用为。 一、问题重述 某地区有8个公司(如图一编号①至⑧)，某天某货运公司要派车将各公司 所需的三种原材料A,B,C从某港口(编号⑨)分别运往各个公司。路线是唯一的 双向道路(如图１)。货运公司现有一种载重 6吨的运输车，派车有固定成本20元/辆，从港口出车有固定成本为10元/车次(车辆每出动一次为一车次)。每辆车平均需要用15分钟的时间装车，到每个公司卸车时间平均为10分钟，运输 车平均速度为60公里／小时(不考虑塞车现象)，每日工作不超过8小时。运输车载重运费元/吨公里，运输车空载费用元/公里。一个单位的原材料A,B,C分 别毛重4吨、3吨、1吨，原材料不能拆分，为了安全，大小件同车时必须小件在上，大件在下。卸货时必须先卸小件，而且不允许卸下来的材料再装上车， 另外必须要满足各公司当天的需求量(见表１)。问题： 1、货运公司派出运输车6辆，每辆车从港口出发(不定方向)后运输途中不允许掉头，应如何调度(每辆车的运载方案，运输成本)使得运费最小。 2、每辆车在运输途中可随时掉头，若要使得成本最小，货运公司怎么安排车辆数应如何调度 污水处理模型 摘要 随着经济的快速发展，环保问题已经成为一个不容忽视的问题，而水资源更是关系着每个居民的日常生活，因此对于污水处理这一特殊的问题我们在解决时就应该本着高效的原则去实施，在这个污水处理问题中，我们先建立了一般情况下的模型，然后将该模型应用到实际问题中从而解决了实际问题。在模型的建立中我们要考虑工厂的净化能力，江水的自净能力，在保证江水经这一系列的处理后在到达下一个居民点后要达到国家标准，还要花费最少，对该问题进行全面的分析后可知这是一个运筹学方面关于线性规划的最优解问题，在该模型的建立中我们针对江水污水浓度在每个居民点之前小于国家标准这一条件对其建立线性约束条件，然后综合考虑费用最小，在结合三个处理厂各自的情况后，关于费用抽象数模型的目标函数，运用LINGO9.0规划软件求解，最后求得使江面上所有地段的水污染浓度达到国家标准时的最小费用为5万元。 关键词：污水处理自净系数污水流量处理系数污水浓度 一、 问题重述 如下图，由若干工厂的污水经排污口流入某江，各口有污水处理站，处理站对面是居民点。工厂1上游江水流量和污水浓度，国家标准规定的水的污染浓度，以及各个工厂的污水流量和污水浓度都已知道。设污水处理费用与污水处理前后的浓度差和污水流量成正比，使每单位流量的污水下降一个浓度单位需要的处理费用（称处理系数）为已知，处理后的污水与江水混合，流到下一个排污口之前，自然状态下江水也会使污水浓度降低一个比例系数（称自净系数）该系数可以估计。试确定各污水处理站出口的污水浓度，使在符合国家标 先建立一般情况下的数学模型，再求解以下的具体问题： 设上游江水流量为min /10100012l ?，污水浓度为l mg /8.0,三个工厂的污水流量均为min /10512l ?，污水浓度（从上游到下游排列）分别为100，60，50（l mg /），处理系数均为1万元/)/(m in)/10(12l mg l ?，3个工厂之间的两段江面的自净系数（从上游到下游）分别为0.9，0.6。国家规定的污水浓度不能超过1l mg /。 （1）为了使江面上所有地段的水污染达到国家标准，最少需要花费多少费用？ （2）如果只要求三个居民点上游的水污染达到国家标准，最少需要花费 江水 货物配送问题 【摘要】 本文是针对解决某港口对某地区8个公司所需原材料A、B、C的运输调度问题提出的方案。我们首先考虑在满足各个公司的需求的情况下，所需要的运输的最小运输次数，然后根据卸载顺序的约束以及载重费用尽量小的原则，提出了较为合理的优化模型，求出较为优化的调配方案。 针对问题一，我们在两个大的方面进行分析与优化。第一方面是对车次安排的优化分析，得出①~④公司顺时针送货，⑤~⑧公司逆时针送货为最佳方案。第二方面我们根据车载重相对最大化思想使方案分为两个步骤，第一步先是使每个车次满载并运往同一个公司，第二步采用分批次运输的方案，即在第一批次运输中，我们使A材料有优先运输权；在第二批次运输中，我们使B材料有优先运输权；在第三批次中运输剩下所需的货物。最后得出耗时最少、费用最少的方案。耗时为小时，费用为元。 针对问题二，加上两个定理及其推论数学模型与问题一几乎相同，只是空载路径不同。我们采取与问题一相同的算法，得出耗时最少，费用最少的方案。耗时为小时，费用为元。 针对问题三的第一小问，我们知道货车有4吨、6吨和8吨三种型号。我们经过简单的论证，排除了4吨货车的使用。题目没有规定车子不能变向，所以认为车辆可以掉头。然后我们仍旧采取①~④公司顺时针送货，⑤~⑧公司逆时针送货的方案。最后在满足公司需求量的条件下，采用不同吨位满载运输方案，此方案分为三个步骤：第一，使8吨车次满载并运往同一公司；第二，6吨位车次满载并运往同一公司；第三，剩下的货物若在1~6吨内，则用6吨货车运输，若在7~8吨内用8吨货车运输。最后得出耗时最少、费用最省的方案。耗时为小时，费用为。 一、问题重述 某地区有8个公司(如图一编号①至⑧)，某天某货运公司要派车将各公司所需的三种原材料A,B,C从某港口(编号⑨)分别运往各个公司。路线是唯一的双向道路(如图１)。货运公司现有一种载重 6吨的运输车，派车有固定成本20元/辆，从港口出车有固定成本为10元/车次(车辆每出动一次为一车次)。每辆车平均需要用15分钟的时间装车，到每个公司卸车时间平均为10分钟，运输车平均速度为60公里／小时(不考虑塞车现象)，每日工作不超过8小时。运输车载重运费元/吨公里，运输车空载费用元/公里。一个单位的原材料A,B,C分别毛重4吨、3吨、1吨，原材料不能拆分，为了安全，大小件同车时必须小件在上，大件在下。卸货时必须先卸小件，而且不允许卸下来的材料再装上车，另外必须要满足各公司当天的需求量(见表１)。问题： 蔬菜运输问题 2012年8月22日 摘要 本文运用floyd算法求出各蔬菜采购点到每个菜市场的最短运输距离，然后用lingo软件计算蔬菜调运费用及预期短缺损失最小的调运方案，紧接着根据题目要求对算法加以修改得出每个市场短缺率都小于20%的最优调运方案，并求出了最佳的供应改进方案。 关键词 最短路问题 floyd算法运输问题 一、问题重述 光明市是一个人口不到15万人的小城市。根据该市的蔬菜种植情况，分别在花市（A），城乡路口（B）和下塘街（C）设三个收购点，再由各收购点分送到全市的8个菜市场，该市道路情况，各路段距离（单位：100m）及各收购点，菜市场①L⑧的具体位置见图1，按常年情况，A,B,C三个收购点每天收购量分别为200，170和160（单位：100 kg）,各菜市场的每天需求量及发生供应短缺时带来的损失（元/100kg）见表 1.设从收购点至各菜市场蔬菜调运费为1元/(100kg.100m). ①7 ② 5 4 8 3 7 A 7 ⑼ 6 B ⑥ 6 8 5 5 4 7 11 7 ⑾ 4 ③ 7 5 6 6 ⑤ 3 ⑿ 5 ④ ⑽ 8 6 6 10 C 10 ⑧ 5 11 ⑦图1 表1 菜市场每天需求（100 kg）短缺损失（元/100kg） ①75 10 ②60 8 ③80 5 ④70 10 ⑤100 10 ⑥55 8 ⑦90 5 ⑧80 8 (a)为该市设计一个从收购点至个菜市场的定点供应方案，使用于蔬菜调运及预 期的短缺损失为最小； (b)若规定各菜市场短缺量一律不超过需求量的20%，重新设计定点供应方案 (c)为满足城市居民的蔬菜供应，光明市的领导规划增加蔬菜种植面积，试问增 产的蔬菜每天应分别向A,B,C三个采购点供应多少最经济合理。 二、问题分析 求总的运费最低，可以先求出各采购点到菜市场的最小运费，由于单位重量运费和距离成正比，题目所给的图1里包含了部分菜市场、中转点以及收购点之间的距离，（a）题可以用求最短路的方法求出各采购点到菜市场的最短路径，乘上单位重量单位距离费用就是单位重量各运输线路的费用，然后用线性方法即可解得相应的最小调运费用及预期短缺损失。 第二问规定各菜市场短缺量一律不超过需求量的20%，只需要在上题基础上加上新的限制条件，即可得出新的调运方案。 第三问可以在第二问的基础上用灵敏度分析进行求解，也可以建立新的线性问题进行求解。 三、模型假设 1、各个菜市场、中转点以及收购点都可以作为中转点； 2、各个菜市场、中转点以及收购点都可以的最大容纳量为610吨； 3、假设只考虑运输费用和短缺费用，不考虑装卸等其它费用； 4、假设运输的蔬菜路途中没有损耗； 5、忽略从种菜场地到收购点的运输费用。 四、符号说明 A收购点分送到全市的8个菜市场的供应量分别为a1,b1,c1,d1,e1,f1,g1,h1, B收购点分送到全市的8个菜市场的供应量分别为a2,b2,c2,d2,e2,f2,g2,h2, C收购点分送到全市的8个菜市场的供应量分别为a3,b3,c3,d3,e3,f3,g3,h3, 8个菜市场的短缺损失量分别为a,b,c,d,e,f,g,h(单位均为100kg)。 五、模型的建立和求解 按照问题的分析，首先就要求解各采购点到菜市场的最短距离，在图论里面关于最短路问题比较常用的是Dijkstra算法，Dijkstra算法提供了从网络图中某一点到其他点的最短距离。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。但由于它遍历计算的节点很多，所以效率较低，实际问题中往往要求网络中任意两点之间的最短路距离。如果仍然采用Dijkstra算法对各点分别计算，就显得很麻烦。所以就可以使用网络各点之间的矩阵计算法，即Floyd 算法。 Floyd算法的基本是：从任意节点i到任意节点j的最短路径不外乎2种可能，1是直接从i到j，2是从i经过若干个节点k到j。i到j的最短距离不外乎存在经过i和j之间的k和不经过k两种可能，所以可以令k=1，2，3，...，n(n是城市的数目)，在检查d(i,j)和d(i,k)+d(k,j)的值；在此d(i,k)和d(k,j)分别是目前为止所知道的i到k和k到j的最短距离。因此d(i,k)+d(k,j)就是i到j经过k的最短距离。所以，若有d(i,j)>d(i,k)+d(k,j)，就表示从i出发经过k再到j的距离要比原来的i到j距离短，自然把i到j的d(i,j)重写为 货运公司运输问题 数信学院14级信计班魏琮 【摘要】 本文是针对解决某港口对某地区8个公司所需原材料A、B、C的运输调度问题提出的方案。首先考虑在满足各个公司的需求的情况下，所需要的运输的最小运输次数，然后根据卸载顺序的约束以及载重费用尽量小的原则，提出了较为合理的优化模型，求出较为优化的调配方案。 针对问题一，在两个大的方面进行分析与优化。第一方面是对车次安排的优化分析，得出①~④公司顺时针送货，⑤~⑧公司逆时针送货为最佳方案。第二方面根据车载重相对最大化思 想使方案分为两个步骤，第一步先是使每个车次满载并运往同一个公司，第二步采用分批次运输的方案，即在第一批次运输中，我们使A材料有优先运输权；在第二批次运输中，我们使B材料有优先运输权；在第三批次中运输剩下所需的货物。最后得出耗时最少、费用最少的方案。耗时为40.3333小时，费用为4864.0元。 针对问题二，加上两个定理及其推论数学模型与问题一几乎相同，只是空载路径不同。采取与问题一相同的算法，得出耗时最少，费用最少的方案。耗时为26.3小时，费用为4487.2元。 针对问题三的第一小问，知道货车有4吨、6吨和8吨三种型号。经过简单的论证，排除了4吨货车的使用。题目没有规定车 子不能变向，所以认为车辆可以掉头。然后仍旧采取①~④公司 顺时针送货，⑤~⑧公司逆时针送货的方案。最后在满足公司需 求量的条件下，采用不同吨位满载运输方案，此方案分为三个步骤：第一，使8吨车次满载并运往同一公司；第二，6吨位车次 满载并运往同一公司；第三，剩下的货物若在1~6吨内，则用6 吨货车运输，若在7~8吨内用8吨货车运输。最后得出耗时最少、费用最省的方案。耗时为19.6833小时，费用为4403.2元。 一、问题重述 某地区有8个公司(如图一编号①至⑧)，某天某货运公司要派车将各公司所需的三种原材料A,B,C从某港口(编号⑨)分别运往各个公司。路线是唯一的双向道路(如图１)。货运公司现有一种载重6吨的运输车，派车有固定成本20元/辆，从港口出车有固定成本为10元/车次(车辆每出动一次为一车次)。每辆车平均需要用15分钟的时间装车，到每个公司卸车时间平均为10分钟，运输车平均速度为60公里／小时(不考虑塞车现象)，每日工作不超过8小时。运输车载重运费1.8元/吨公里，运输车空载费用0.4元/公里。一个单位的原材料A,B,C分别毛重4吨、3吨、1吨，原材料不能拆分，为了安全，大小件同车时必须小件在上，大件在下。卸货时必须先卸小件，而且不允许卸下来的材料再装上车，另外必须要满足各公司当天的需求量(见表１)。问题： 1、货运公司派出运输车6辆，每辆车从港口出发(不定方向)后运输途中不允许掉头，应如何调度(每辆车的运载方案，运输成本)使得运费最小。 污水处理系统数学模型 摘要 随着水资源的日益紧缩和水环境污染的愈加严重，污水处理的问题越来越受到人们的关注。由于污水处理过程具有时变性、非线性和复杂性等鲜明特征，这使得污水处理系统的运行和控制极为复杂。而采用数学模型，不仅能优化设计、提高设计水平和效率，还可优化已建成污水厂的运行管理，开发新的工艺，这是污水处理设计的本质飞跃，它摆脱了经验设计法，严格遵循理论的推导，使设计的精确性和可靠性显著提高。数学模型是研究污水处理过程中生化反应动力学的有效方法和手段。计算机技术的发展使数学模型的快速求解成为可能，使这些数学模型日益显示出他们在工程应用与试验研究中的巨大作用。 对于污水处理，有活性污泥法、生物膜法以及厌氧生物处理法等污水处理工艺，其中以活性污泥法应用最为广泛。活性污泥法是利用自然界微生物的生命活动来清除污水中有机物和脱氮除磷的一种有效方法。活性污泥法污水处理过程是一个动态的多变量、强耦合过程，具有时变、高度非线性、不确定性和滞后等特点，过程建模相当困难。为保证处理过程运行良好和提高出水质量，开发精确、实用的动态模型已成为国内外专家学者普遍关心的问题。此外，由于污水处理过程是一个复杂的生化反应过程，现场试验不仅时间长且成本很高，因此，研究对污水处理过程的建模和仿真技术具有十分重要的现实意义。本文在充分了解活性污泥法污水处理过程的现状及工艺流程的基础上，深入分析了现有的几种建模的方法，其中重点分析了ASM1。ASM1主要适用于污水生物处理的设计和运行模拟，着重于生物处理的基本过程、原理及其动态模拟，包括了碳氧化、硝化和反硝化作用等8种反应过程；包含了异养型和自养型微生物、硝态氮和氨氮等12种物质及5个化学计量系数和14个动力学参数。ASMI的特点和内容体现在模型的表述方式、污水水质特性参数划分、有机生物固体的组成、化学计量学和动力学参数等四个方面。 关键词：污水处理系统，活性污泥，数学模型，ASM1 数学建模--运输问题 运输问题 摘要 本文主要研究的是货物运输的最短路径问题，利用图论中的Floyd算法、Kruskal算法，以及整数规划的方法建立相关问题的模型，通过matlab，lingo 编程求解出最终结果。 关于问题一，是一个两客户间最短路程的问题，因此本文利用Floyd算法对其进行分析。考虑到计算的方便性，首先，我们将两客户之间的距离输入到网络权矩阵中；然后，逐步分析出两客户间的最短距离；最后，利用Matlab软件对其进行编程求解，运行得到结果：2-3-8-9-10总路程为85公里。 关于问题二，运输公司分别要对10个客户供货，必须访问每个客户，实际上是一个旅行商问题。首先，不考虑送货员返回提货点的情形，本文利用最小生成树问题中的Kruskal算法，结合题中所给的邻接矩阵，很快可以得到回路的最短路线：1-5-7-6-3-4-8-9-10-2；然后利用问题一的Floyd算法编程，能求得从客户2到客户1（提货点）的最短路线是：2-1，路程为50公里。即最短路线为：1-5-7-6-3-4-8-9-10-2-1。但考虑到最小生成树法局限于顶点数较少的情形，不宜进一步推广，因此本文建立以路程最短为目标函数的整数规划模型；最后，利用LINGO软件对其进行编程求解，求解出的回路与Kruskal算法求出的回路一致。 关于问题三，是在每个客户所需固定货物量的情况下，使得行程之和最短。这样只要找出两条尽可能短的回路，并保证每条线路客户总需求量在50个单位以内即可。因此我们在问题二模型的基础上进行改进，以货车容量为限定条件，建立相应的规划模型并设计一个简单的寻路算法，对于模型求解出来的结果，本文利用Kruskal算法结合题中所给的邻接矩阵进行优化。得到优化结果为：第 一辆车：1-5-2-3-4-8-9-1，第二辆车：1-7-6-9-10-1，总路程为280公里。 关于问题四，在问题一的基础上我们首先用Matlab软件编程确定提货点到每个客户点间的最短路线，然后结合一些限定条件建立一个目标模型，设计一个较好的解决方案进行求解可得到一种很理想的运输方案。根据matlab运行结果分析得出4条最优路线分别为：1-5-2，1-4-3-8，1-7-6，1-9-10。最短总路线为245公里，最小总费用为645。 关键词： Floyd算法 Kruskal算法整数规划旅行商问题 数学建模运输问题公司内部档案编码：[OPPTR-OPPT28-OPPTL98-OPPNN08] 运输问题 摘要 本文主要研究的是货物运输的最短路径问题，利用图论中的Floyd 算法、Kruskal算法，以及整数规划的方法建立相关问题的模型，通过matlab，lingo编程求解出最终结果。 关于问题一，是一个两客户间最短路程的问题，因此本文利用Floyd 算法对其进行分析。考虑到计算的方便性，首先，我们将两客户之间的距离输入到网络权矩阵中；然后，逐步分析出两客户间的最短距离；最后，利用Matlab软件对其进行编程求解，运行得到结果：2-3-8-9-10总路程为85公里。 关于问题二，运输公司分别要对10个客户供货，必须访问每个客户，实际上是一个旅行商问题。首先，不考虑送货员返回提货点的情形，本文利用最小生成树问题中的Kruskal算法，结合题中所给的邻接矩阵，很快可以得到回路的最短路线：-9-10-2；然后利用问题一的Floyd算法编程，能求得从客户2到客户1（提货点）的最短路线是：2-1，路程为50公里。即最短路线为：-9-10-2-1。但考虑到最小生成树法局限于顶点数较少的情形，不宜进一步推广，因此本文建立以路程最短为目标函数的整数规划模型；最后，利用LINGO软件对其进行编程求解，求解出的回路与Kruskal算法求出的回路一致。 关于问题三，是在每个客户所需固定货物量的情况下，使得行程之和最短。这样只要找出两条尽可能短的回路，并保证每条线路客户总需 求量在50个单位以内即可。因此我们在问题二模型的基础上进行改进，以货车容量为限定条件，建立相应的规划模型并设计一个简单的寻路算法，对于模型求解出来的结果，本文利用Kruskal算法结合题中所给的邻接矩阵进行优化。得到优化结果为：第一辆车：-1，第二辆车：，总路程为280公里。 关于问题四，在问题一的基础上我们首先用Matlab软件编程确定提货点到每个客户点间的最短路线，然后结合一些限定条件建立一个目标模型，设计一个较好的解决方案进行求解可得到一种很理想的运输方案。根据matlab运行结果分析得出4条最优路线分别为：1-5-2，1-4-3-8，1-7-6，1-9-10。最短总路线为245公里，最小总费用为645。 关键词： Floyd算法 Kruskal算法整数规划旅行商问题 一、问题重述 某运输公司为10个客户配送货物，假定提货点就在客户1所在的位置，从第i个客户到第j个客户的路线距离（单位公里）用下面矩阵中的(,) i j=位置上的数表示（其中∞表示两个客户之间无直接的 i j(,1,,10) 路线到达）。 1、运送员在给第二个客户卸货完成的时候，临时接到新的调度通知，让 他先给客户10送货，已知送给客户10的货已在运送员的车上，请帮运送员设计一个到客户10的尽可能短的行使路线（假定上述矩阵中给出了所有可能的路线选择）。 2、现运输公司派了一辆大的货车为这10个客户配送货物，假定这辆货车 一次能装满10个客户所需要的全部货物，请问货车从提货点出发给 实验名称：第十一章最短路问题 一、实验内容与要求 掌握Dijkstra算法和Floyd算法，并运用这两种算法求一些最短路径的问题。 二、实验软件 MATLAB7.0 三、实验内容 1、在一个城市交通系统中取出一段如图所示，其入口为顶点v1，出口为顶点v8，每条弧段旁的数字表示通过该路段所需时间，每次转弯需要附加时间为3，求v1到v8的最短时间路径。 V1 1 V2 3 V3 1 V5 6 V6 V4 2 V7 4 V8 程序： function y=bijiaodaxiao(f1,f2,f3,f4) v12=1;v23=3;v24=2;v35=1;v47=2;v57=2;v56=6;v68=3;v78=4; turn=3; f1=v12+v23+v35+v56+turn+v68; f2=v12+v23+v35+turn+v57+turn+v78; f3=v12+turn+v24+turn+v47+v78; f4=v12+turn+v24+v47+turn+v57+turn+v56+turn+v68; min=f1; if f2 f4 实验结果： v1到v8的最短时间路径为15，路径为1-2-4-7-8. 2、求如图所示中每一结点到其他结点的最短路。V110 V3V59 V6 floy.m中的程序： function[D,R]=floyd(a) n=size(a,1); D=a for i=1:n for j=1:n R(i,j)=j; end end R for k=1:n for i=1:n for j=1:n if D(i,k)+D(k,j) 姓名：王文斌 学号：3110008343 学院班级:应用数学学院信息与计算科学2班 摘要：现实生活中，污水如何进行处理，节约工厂的支出，是很多工厂都会面临的问题，根据题目假设了若干理想条件，在理想条件下进行模型的设计。对国家的污水处理标准、理想的环境系数、理想的处理工作环境。进行分析。具有一定的可参考价值。 关键字：LINGO,污水处理，最小化费用，数模。 问题重述 如下图，有若干工厂的污水经排污口流入某江，各口有污水处理站，处理站对面是居民点。工厂1上游江水流量和污水浓度，国家标准规定的水的污染浓度，以及各个工厂的污水流量和污水浓度均已知道。设污水处理费用与污水处理前后的浓度差与污水流量成正比，使每单位流量的污水下降一个浓度单位需要的处理费用（称处理系数）为已知。处理后的污水与江水混合，流到下一个排污口之前，自然状态下的江水也会使污水浓度降低一个比例系数（称自净系数），该系数可以估计。试确定各污水处理站出口的污水浓度，使在符合国家标准规定的条件下总的处理费用最小。 工厂1 工厂2 工厂3 处理站1 处理站3 江水 居民点1 居民点2 居民点3 问题的提出： 先建立一般情况下的数学模型，再求解以下的具体问题： 设上游江水流量为12 ?l/min，污水浓度为0.8mg/l，3个工厂的污水流量均为 100010 12 ?l/min，污水浓度（从上游到下游排列）分别为100，60，50（mg/l），处理系数均为510 1万元/((12 10l/min) (mg/l))，3个工厂之间的两段江面的自净系数（从上游到下游）分别为0.9，0.6。国家标准规定水的污染浓度不能超过1mg/l。 （1）为了使江面上所有地段的水污染达到国家标准，最少需要花费多少费用？ （2）如果只要求三个居民点上游的水污染达到国家标准,最少需要花费多少费用？ 模型的假设如下： 1：假设污水源只有江本身和工厂。 2：假设污水能和江水充分混合->浓度一致。 3：假设1+1必须等于2.即只有数学变化没有其他的生化反应。 4：混合过程瞬间完成。 5：只计算处理厂1至处理3之间的江面污染浓度。 6: 假设自净过程在江面段末尾完成即处理站1与处理站2之间的江面段的尾部完成。处理站2与处理站3之间也是一样。 7：假设居民点在污水处理口的上游。 问题分析： 由提出的假设可知。 符号说明： X1:工厂1排出污水的浓度。 X2:工厂2排出污水的浓度。 X3:工厂3排出污水的浓度。 Y1:工厂1排出的污水经过处理厂处理后的浓度。 Y2:工厂2排出的污水经过处理厂处理后的浓度。 Y3:工厂3排出的污水经过处理厂处理后的浓度。 Z1:处理厂1排出的污水浓度与江水混合后的浓度(问题2中加入自净)。 Z2:处理厂2排出的污水浓度与江水混合后的浓度(问题2中加入自净)。 Z3:处理厂3排出的污水浓度与江水混合后的浓度(问题2中加入自净)。 F1:处理厂1处理所用的处理费用。 F2:处理厂2处理所用的处理费用。 F3:处理厂3处理所用的处理费用。 运输问题 摘要 本文主要研究的是货物运输的最短路径问题，利用图论中的Floyd算法、Kruskal算法，以及整数规划的方法建立相关问题的模型，通过matlab，lingo 编程求解出最终结果。 关于问题一，是一个两客户间最短路程的问题，因此本文利用Floyd算法对其进行分析。考虑到计算的方便性，首先，我们将两客户之间的距离输入到网络权矩阵中；然后，逐步分析出两客户间的最短距离；最后，利用Matlab软件对其进行编程求解，运行得到结果：2-3-8-9-10总路程为85公里。 关于问题二，运输公司分别要对10个客户供货，必须访问每个客户，实际上是一个旅行商问题。首先，不考虑送货员返回提货点的情形，本文利用最小生成树问题中的Kruskal算法，结合题中所给的邻接矩阵，很快可以得到回路的最短路线：1-5-7-6-3-4-8-9-10-2；然后利用问题一的Floyd算法编程，能求得从客户2到客户1（提货点）的最短路线是：2-1，路程为50公里。即最短路线为：1-5-7-6-3-4-8-9-10-2-1。但考虑到最小生成树法局限于顶点数较少的情形，不宜进一步推广，因此本文建立以路程最短为目标函数的整数规划模型；最后，利用LINGO软件对其进行编程求解，求解出的回路与Kruskal算法求出的回路一致。 关于问题三，是在每个客户所需固定货物量的情况下，使得行程之和最短。这样只要找出两条尽可能短的回路，并保证每条线路客户总需求量在50个单位以内即可。因此我们在问题二模型的基础上进行改进，以货车容量为限定条件，建立相应的规划模型并设计一个简单的寻路算法，对于模型求解出来的结果，本文利用Kruskal算法结合题中所给的邻接矩阵进行优化。得到优化结果为：第一辆车：1-5-2-3-4-8-9-1，第二辆车：1-7-6-9-10-1，总路程为280公里。 关于问题四，在问题一的基础上我们首先用Matlab软件编程确定提货点到每个客户点间的最短路线，然后结合一些限定条件建立一个目标模型，设计一个较好的解决方案进行求解可得到一种很理想的运输方案。根据matlab运行结果分析得出4条最优路线分别为：1-5-2，1-4-3-8，1-7-6，1-9-10。最短总路线为245公里，最小总费用为645。 关键词： Floyd算法 Kruskal算法整数规划旅行商问题 一、问题重述 某运输公司为10个客户配送货物，假定提货点就在客户1所在的位置，从第i个客户到第j个客户的路线距离（单位公里）用下面矩阵中的 i j=L位置上的数表示（其中∞表示两个客户之间无直接的路线到i j(,1,,10) (,) 达）。 1、运送员在给第二个客户卸货完成的时候，临时接到新的调度通知，让他先给 客户10送货，已知送给客户10的货已在运送员的车上，请帮运送员设计一个到客户10的尽可能短的行使路线（假定上述矩阵中给出了所有可能的路线选择）。 2、现运输公司派了一辆大的货车为这10个客户配送货物，假定这辆货车一次能 装满10个客户所需要的全部货物，请问货车从提货点出发给10个客户配送 数学模型在污水处理厂中的应用 发帖人: bluesnail 点击率: 487 郝二成，常江，周军，甘一萍 （北京城市排水集团有限责任公司，北京 100063） 摘要：综述了数学模型的发展历史，以及它在国内外污水处理厂中的应用情况，并对模型应用的问题和前景进行了分析。 关键词：数学模型；模拟；污水处理厂 模拟是污水处理设计和运行控制的本质部分，数学模型的核心是从反应机理出发，在一定条件下，在时间和空间范围内模拟、预测污水处理的实际过程。数学模型的应用可以大大减少我们的实验工作量，不仅提高了工作效率，而且节省了大量人 力、物力和财力。 在发达国家，应用数学模型从事污水处理工艺开发、设计及实现污水处理厂运行管理的精确控制，已相当普遍，而我国 在这一方面尚处于起步阶段，扩展的空间很大。 1 数学模型的发展 活性污泥法是废水生物处理中应用最广泛的方法之一。起初对活性污泥过程的设计和运行管理主要依靠经验数据，自20世纪50年代后期，Eckenfelder等人基于反应器理论和生物化学理论提出活性污泥法静态模型以来，动态模型研究不断发展，已 成为国际废水生物处理领域的研究热点。 传统静态模型以20世纪50 ~ 70年代推出的Eckenfelder、Mckinney、Lawrence-McCarty模型为代表，这些模型所采用的是生长－衰减机理。传统静态模型因为具有形式简单、变量可直接测定、动力学参数测定和方程求解较方便，得出的稳态结果基本满足工艺设计要求等优点，曾得到广泛应用。然而，长期实际应用也表明，这种基于平衡态的模型丢失了大量不同平衡生长状态间的瞬变过程信息，忽视了一些重要的动态现象，应用到具有典型时变特性的活性污泥工艺系统时，存在许多问题：无法解释有机物的“快速去除”现象；不能很好的预测基质浓度增大时微生物增长速度变化的滞后，要突破这些局限，必须建 立动态模型。 污水生物处理的动态模型主要包括Andrews模型、WRC模型、BioWin模型、UCT（University of Cape Town）模型、活性污泥数学模型、生物膜模型和厌氧消化模型等，其中以活性污泥数学模型研究进展最快，应用也最广。1983年，IAWQ（国际水质协会）成立了一个任务小组，以加快污水生物处理系统的设计和管理实用模型的发展和应用。首要任务是测评现有的模型， 华东交通大学数学建模2012年第一次模拟训练题 所属学校：华东交通大学（ECJTU ） 参赛队员：胡志远、周少华、蔡汉林、段亚光、 李斌、邱小秧、周邓副、孙燕青 指导老师：朱旭生（博士） 摘要： 本文的运输问题是一个比较复杂的问题，大多数问题都集中在最短路径的求 解问题上，问题特点是随机性比较强。 根据不同建模类型 针对问题一 ，我们直接采用Dijkstra 算法（包括lingo 程序和手算验证），将问题转化为线性规划模型求解得出当运送员在给第二个客户卸货完成的时，若要他先给客户10送货，此时尽可能短的行使路线为：109832V V V V V →→→→，总行程85公里。 针对问题二，我们首先利用prim 算法求解得到一棵最小生成树： 121098436751V V V V V V V V V V V →→→→→→→→→→ 再采用Dijkstra 算法求得客户2返回提货点的最短线路为12V V →故可得到一条理想的回路是：121098436751V V V V V V V V V V V →→→→→→→→→→ 后来考虑到模型的推广性，将问题看作是哈密顿回路的问题，建立相应的线性规划模型求解，最终找到一条满足条件的较理想的的货车送货的行车路线： 121098436751V V V V V V V V V V V →→→→→→→→→→。 针对问题三，我们首先直接利用问题二得一辆车的最优回路，以货车容量为限定条件，建立相应的规划模型并设计一个简单的寻路算法，最终可为公司确定合理的一号运输方案:两辆车全程总和为295公里（见正文）；然后建立线性规划模型得出二号运输方案：两辆车全程总和为290公里（见正文）； 针对问题四， 污水处理和渔业持续收获的数学建模 关于污水处理的数学建模 摘要 因为全球经济的日益增长中国经济也随之快速发展，经济发展的越快，就不可避免的破坏更多的自然环境，所以环保问题已经成为一个不容忽视的问题，而与每个居民的日常生活密切相关的就是水资源问题，因此对于污水处理这一特殊的问题我们在解决时就应该本着高效的原则去实施，在这个污水处理问题中，我们先建立了一般情况下的模型，然后将该模型应用到实际问题中从而解决了实际问题。在模型的建立中我们要考虑工厂的净化能力，江水的自净能力，在保证江水经这一系列的处理后在到达下一个居民点后要达到国家标准，还要花费最少，对该问题进行全面的分析后可知这是一个运筹学方面关于线性规划的最优解问题，在该模型的建立中我们针对江水污水浓度在每个居民点之前小于国家标准这一条件对其建立线性约束条件，然后综合考虑费用最小，在结合三个处理厂各自的情况后关于费用抽象数模型的目标函数，，然后应用LINDO软件求解该问题得到当三个处理厂排出的污水浓度分别为40 mg/l，20 mg/l，50 mg/l时，此时我们得到使江面上所有地段的水污染达到国家标准,最少需要花费费用为500万元。当从三个处理厂出来的污水浓度分别为 62.222225mg/l，60mg/l，50mg/l,时，此时如果只要求三个居民点上游的水污染达到国家标准最少需要花费费用为188.8889万元。 问题的提出 设上游江水流量为1000（12 10L/min），污水浓度为0.8（mg/L），3个工 厂的污水流量均为5（12 10L/min），污水浓度（从上游到下游排列）分别为 100，60，50（mg/L），处理系数均为1（万元/（（12 10L/min）×（mg/L））），3个工厂之间的两段江面的自净系数（从上游到下游）分别为0.9和0.6。国家标准规定水的污染浓度不超过1（mg/L）。 （1）为了使江面上所有地段的水污染达到国家标准，最少需要花费多少费用？ (2) 如果只要求3个居民点上游的水污染达到国家标准，最少需要花费多 少费用？ 问题的分析 通过对该污水处理所花费用最少问题的分析，我们可知在此问题中有多个污水浓度，江水的原始污水浓度，工厂排出的污水浓度，处理厂排出的污水浓度，以及当处理厂排出污水与江水混合后再经江水自净后的浓度，在这几个浓度中只有经处理厂排出的污水的浓度是未知的，其关系着整个问题，要使总费用最少，江中每段的污水浓度都达到国家标准，江水中污水浓度在到达下一居民点之前须达到国家标准1（mg/l），那么问题的重点就在于对污水浓度的认识。在问题中有三个工厂以及对应的三个污水处理厂，那么这三个污水处理厂各向江中投放的污水浓度就要有一个界值，又因当处理厂将污水排到江中之后污水会随着江水不断向下游移动，因此下游污水的浓度与上游污水的浓度是紧密相关的，即江面中每段污水的浓度都是有联系的，在模型的建立过程中我们就要考虑应用递推的方法进行相邻两端之间污水浓度的联系，在问题的求解中因所花费用都是用来对污水的处理，因此对个处理厂排出的污水浓度的确定就显得至关重要，只有确 基于最短路问题的研究及应用令狐采学 姓名：Fanmeng 学号： 指导老师： 摘要 最短路问题是图论中的一大问题，对最短路的研究在数学建模和实际生活中具有很重要的实际意义，介绍最短路问题的定义及这类问题的解决办法Dijkstra算法，并且能够在水渠修建实例运用到此数学建模的方法，为我们解决这类图论问题提供了基本思路与方法。 关键字数学建模最短路问题Dijkstra算法水渠修建。 目录 第一章．研究背景1 第二章．理论基础2 2.1 定义2 2.2 单源最短路问题Dijkstra求解:2 2.2.1 局限性2 2.2.2 Dijkstra算法求解步骤2 2.2.3 时间复杂度2 2.3 简单样例3 第三章．应用实例4 3.1 题目描述4 3.2 问题分析4 3.3符号说明4 3.4 模型假设5 3.5模型建立与求解5 3.5.1模型选用5 3.5.2模型应用及求解5 3.6模型评价5 第四章. 参考文献5 第五章．附录6 第一章．研究背景 在现实生活中中，我们经常会遇到图类问题，图是一种有顶点和边组成，顶点代表对象，在示意图中我们经常使用点或者原来表示，边表示的是两个对象之间的连接关系，在示意图中，我们使用连接两点G点直接按的下端来表示。顶点的集合是V，边的集合是E的图记为G[V,E] ,连接两点u和v的边用e(u,v)表示[1]。最短问题是图论中的基础问题，也是解决图类问题的有效办法之一，在数学建模中会经常遇到，通常会把一个实际问题抽象成一个图，然后来进行求的接任意两点之间的最短距离。因此掌握最短路问题具有很重要的意义。 第二章．理论基础 2.1 定义 最短路问题（short-path problem ）：若网络中的每条边都有一个数值（长度、成本、时间等），则找出两节点，（通常是源节点和目标节点）之间总权和最小的路径就是最短路问题。最短路问题是网络理论解决的典型问题之一，可用来解决管道铺设，线路安装，厂区布局和设备更新等实际问题[2]。 2.2 单源最短路问题Dijkstra 求解: 2.2.1局限性 Dijkstra 算法不能够处理带有负边的图，即图中任意两点之间的权值必须非负。 2.2.2Dijkstra 算法求解步骤 (1).先给图中的点进行编号，确定起点的编号。 (2).得到图的构成，写出写出图的矩阵 0000(,)(,) (,) (,) n n n n u u u u G u u u u = (3).根据要求求出发点S 到终点E 的最短距离，那么需要从当前没被访问过的结点集合 unvist={u | u {1,2,3...}}n ∈中找到一个距离已经标记的点的集合中vist={u | u {1,2,3...}}n ∈的最短距离，得到这个顶点； (4).利用这个顶点来松弛其它和它相连的顶点距离S 的值 (5).重复步骤(2)和(3)，直到再也没有点可以用来松弛其它点，这样我们就得到了由起点S 到其它任意点的最短距离。 2.2.3时间复杂度 时间复杂度达到 2 ()O N 数学建模一周论文论文题目：基于运输问题的数学模型 1：学号： 2：学号： 3：学号： 专业： 班级： 指导教师： 2011年12 月29 日 （十五）、已知某运输问题的产销平衡表与单位运价表如下表所示 （1）求最优调拨方案； （2）如产地的产量变为130，又B地区需要的115单位必须满足，试重新确定最优调拨方案。 一论文摘要 一般的运输问题就是要解决把某种产品从若干个产地调运到若干个销地，在每个产地的供应量与每个销地的需求量已知，并知道各地之间的运输单价的前提下，如何确定一个使得总的运输费用最小的方案的问题。本论文运用线性规划的数学模型来解决此运输问题中总费用最小的问题。引入x变量作为决策变量，建立目标函数，列出约束条件，借助MATLAB软件进行模型求解运算，得出其中的最优解，使得把某种产品从3个产地调运到5个销地的总费用最小。 针对模型我们探讨将某产品从3个产地调运到5个销地的最优调拨方案，通过运输问题模，得到模型 Z=1011x+1512x+2013x+2014x+4015x+2021x+4022x+1523x+3024x min x+3031x+3532x+4033x+5534x+2535x +30 25 Z= 并用管理运筹学软件软件得出最优解为： min 关键词：运输模型最优化线性规划 二．问题的重述和分析 A（i=1,2,3）和五个销地j B（j=1,2,3,4,5），已知产地i A的产量有三个产地 i s和销地j B的销量j d，和将物品从产地i运到销地j的单位运价ij c，请问：i 将物品从产地运往销地的最优调拨方案。 A，2A，3A三个产地的总产量为50+100+150=300单位；1B，我们知道， 1 B，3B，4B，5B五个销地的总销量为25+115+60+30+70=300单位，总2 A,2A,3A的产量全产量等于总销量，这是一个产销平衡的运输问题。把产地 1 B,2B,3B,4B,5B，正好满足这三个销地的需要。先将安排的部分配给销地 1 运输量列如下表中：数学建模飞机运输问题
数学建模大赛货物运输问题
污水处理模型(最终版)
数学建模大赛货物运输问题
#蔬菜运输问题--数学建模
数学建模城市垃圾运输问题概论
污水处理数学模型
数学建模--运输问题
数学建模运输问题
数学建模实验报告第十一章最短路问答
数模 污水处理论文
数学建模运输问题
数学模型在污水处理厂中的应用
数学建模运输问题
污水处理和渔业持续收获的数学建模
数学建模模最短路
基于运输问题的数学建模