短学期数学建模论文-污水治理方案的优化设计

1、 嘉兴学院20142015学年第2学期短学期数学建模课程设计报告题 目： 污水治理方案的优化设计 学 院： 数理与信息工程学院 专 业： 数学与应用数学 班 级： 数学131班 组 员 1：张道飞，2，模型构造/写程序 组 员 2：裘琦丹，2，模型构造/写论文 组 员 3：吴霞玉，2，模型构造/写论文 完成日期：2015年7月9号 摘要对于所给题目我们主要分两大问题来进行分析与求解：模型一：管道铺设的问题。为了确保污水处理效果能达到环保要求，即污水管道铺设后可以覆盖所有污水源。同时，满足污水处理的总耗资到达最低值。经过对原始数据分析，做无限次微分处理后，我们发现其铺设管道的总体形态近似最小支撑

2、树结构。于是，我们运用Prim算法，来构造覆盖所有污水源的最小支撑树模型，并用最小支撑树中最长的支链作为管道铺设的主干道。模型二：污水处理厂位置以及数量的确定。结合实际生活，同时为了简化计算，我们假设该市只建设一种规模的污水处理厂，再结合问题一中求出的最小支撑树图形采用递推法，从主干道的左端递推到最右端来确定污水处理厂建造的可能区域。然后，结合实际，我们考虑到淤泥膨胀因素，将污水处理厂具体位置确定在污水源较集中地区。最后，我们运用Matlab软件，在已求出的最短主干道上用红点标出污水处理厂的具体位置。根据所给条件，结合主干道上建设污水处理厂所耗费用，同时去掉主干道上不必要的连接管道，我们得出全

3、市的污水处理管道系统。求得该系统所耗费的最小费用为：总费用=1256*管道单价+19*厂的单价+日处理量（148-30）*处理污水单价。 关键词： Prim算法、最小支撑树、图形结合、Matlab软件、递推法·问题的提出某市有72个污水发源点，其地理分布位置坐标和每个污水源日产污水量已经给出。有一条河流横穿该市，且河流不经过任何一个污水发源点，河流每日河流流量为30000万，根据环保要求，河水中污水的含量应不大于0.1%。现在计划建造污水净化厂，通过管道将全市的污水集中处理后再放入河流。已知铺设管道的费用为每千米1.5万元，处理污水的成本费平均1200元/万，每个污水净化厂造价按每万

4、2千万元。对此我们需要设计该市建造污水净化厂，首先确定经过每个污水源的最短管道铺设方案。其次确定每个污水净化厂的建设位置和每个污水净化厂日处理污水量，使河流污水的含量达到环保要求，同时达到建设污水净化厂和处理污水的总耗资最低。·条件的假设与符号的约定2.1条件的假设·假设所铺设主干道的管道粗细相同；·假设污水处理厂建设位置受淤泥膨胀等因素的影响；·假设所有污水处理厂规定以处理10万吨污水为最高限额的规模；·假设不考虑污水处理厂到河流间的管道费用。2.2 符号的约定·Xi - 污水点的横坐标·Yi - 污水点的纵坐标·

5、;Zi，j，k - 污水点的距离矩阵·Resulti，j，k - 污水点的最小支撑树矩阵·Weight- 最小支撑树距离·Si - 污水点的日产污水量·Cbzi，j，k - 厂的位置和处理量矩阵·问题的分析3.1问题一：最短管道铺设的问题关于问题一，为了使包含所有污水源的管道铺设费用达到最小值，我们运用现实生活中管道铺设的主干路线方法。下面是我们构造模型的过程：1、首先考虑用一条直线模拟求出主干线，此时误差显然较大；2、考虑用两条直线模拟，结果相比前者较精确；3、考虑用三条直线模拟，结果再一步精确；4、同上方法进行无限次微分，我们发现连接72点

6、的最小支撑树中最长的路径即为所求的主干线，其余支链为支干线。进行近一步的检验：假设有别的最短线路方案S2与最小支撑树S1有别。则对于不同路线的每个点有，由最小支撑树的性质可知S1中（A1,A2*An）的最小支撑树除去与S2中不同的点，其余点的路线（Ai，Aj*Am）仍为一最小支撑树，此时如果再有一点Ki与（Ai，Aj*Am）构成最短路线则（Ki，Ai，Aj*Am）构成的最小支撑树即为所求，如此循环叠加最后（Ki，Kj*Km，Ai，Aj*Am）=（A1,A2*An）的最小支撑树即为最短路线，其与假设相矛盾。故最短方案为最小支撑树S1。3.2问题二：污水处理厂位置以及数量的确定为了确定每个污水净化

7、厂的建设位置和日处理污水量，达到河流污水的含量不超过0.1%，建设污水净化厂和处理污水的总耗资最低的目标。结合问题一中求出的覆盖所有污水源的最小支撑树。通过资料查阅，我们考虑到污水淤泥膨胀的因素，发现在现实生活中由于淤泥膨胀而引发管道堵塞问题几率较大。因此，我们决定污水处理厂的建设位置须在污水源较集中地区，以便发生管道堵塞时可以较快的找出问题发生源。同时，假设所有污水处理厂规定以处理10万吨污水为最高限额的规模。综合以上得出如下两个约束条件，确定污水处理厂的建厂位置和数量：1、所有污水处理厂的位置受淤泥膨胀因素的影响。2、所有污水处理厂的位置受规定以处理10万吨污水为最高限额的规模的影响。故经

8、过分析以上约束条件和实际情况结合，由递推法确定每个污水处理厂应处理污水源的个数和污水总量。同时，污水处理厂应建设污水源较集中的地区。·模型的建立及求解4.1 问题一4.1.1 问题一的解答为了确定经过所有污水源的管道铺设最短方案，我们首先对原始数据进行初步处理，主要是运用Matlab中的数据处理与制图功能，借此来反映所有污水源的分布规律。以下是通过原始数据所绘制的污水源点分布表：对于主干道的选取，即求72个点的最小支撑树，我们首先求出两两之间的距离共有72*71个距离，将所得数据带入距离矩阵Zi，j，k 中，（i,j)列表示各污水源在坐标系中的坐标，(k)列表示各点之间的距离。再运用

9、Matlab软件，结合Prim算法，求出72点的最小支撑树（程序详见附件1）。得出覆盖所有污水源的最小支撑树图像为如下Resulti，j，k ： 4.2 问题二 4.2.1 问题二的解答为了确定污水处理厂的建造数量与位置，我们采用递推法，运用问题一求出的最小支撑树图形，从主干道的左端逐步递推至最右端，即从点1312。建厂主要遵循以下原则：1、污水处理厂的位置统一选在干道上；2、污水处理厂要位于所负责处理污水源的中心，即污水源最密集处；3、污水处理厂的日处理污水量不超过10万吨。结合上述原则，我们开始选取第一个污水处理厂建造位置。从点13出发，沿途有点14，15，8，16其总和流量=9，而此时再

10、向前即加17点的流量，则总和超过10吨，与假设相矛盾，故第一个处理厂应负责处理点13，14，15，8，16的污水。再根据原则一，其具体位置应在主干道上，同时结合图形可知到周边管道最短的点为8，故该厂的位置应选在点8，处理的污水日流量为9万吨。同理，运用Matlab软件编程可依次递推出其余的厂的位置，求得结果如下：Czb=25.0000 10.0000 9.0000 27.0000 40.0000 6.6000 50.5000 46.0000 7.7000 70.0000 40.0000 10.0000 100.0000 25.0000 8.7000 140.0000 50.0000 7.500

11、0 142.0000 82.0000 7.6000 117.0000 102.0000 9.9000 139.0000 116.0000 9.3000 151.0000 117.0000 9.0000 191.0000 115.0000 8.1000 198.0000 102.0000 3.6000 205.0000 100.0000 7.6000 171.0000 93.0000 9.0000 190.0000 49.0000 8.5000 194.0000 86.0000 6.2000 215.0000 91.0000 8.5000 240.5000 121.5000 8.1000 234

12、.0000 116.0000 4.0000图中红色的为厂的具体位置，故可知总共应建19个厂。接下来应去掉连接各个厂的无用管道，分别为：16-17;6-19;18-59;61-62;65-67;10-24;4-23;31-30;35-38;40-39;44-45;46-47;47-48;37-1;28-26;48-49;50-11;55-57;再用Matlab软件求出此时的管道分布及厂址选取图，如下：红色点即为污水处理厂的具体位置。最后，可求出总的最小费用=1256*管道单价+19*厂的单价+日处理量（148-30）*处理污水单价。·模型的评价和改进5.1模型的优点： 在问题一中，模型

13、采用了构造最小支撑树的方法来寻求最短管道铺设方案。运用Matlab软件比较方便、清晰易懂，并且准确地求出72个污水源点彼此之间的距离，使得最终的管道铺设总长度达到理论最小值。 在问题二中，我们考虑到了实际管道铺设中存在淤泥膨胀因素的影响，以此作为污水处理厂建造的约束条件之一，比较符合实际。5.2模型的缺点： 在问题一中，对相连的污水源之间，我们考虑用直线管道铺设，没有联系实际情况中，受居民点等建筑物的影响。对于所采用的管道粗细，为简化计算，我们统一选定相同规格的管道，因此没有很好的考虑污水流量的影响。 在问题二中，对于污水处理厂建造位置的选定，我们以10吨污水为处理最高限额，与实际生活有一定的

14、偏差。参考文献：1运筹学教材编写组，运筹学第4版，北京，清华大学出版社，2012.9；2 姜启源、谢金星、叶俊版，数学模型第4版，北京，高等教育出版社，2011.1；J/OL 最小支撑树Prim算法, ,2015.7.7附录1：72个污水源间距离矩阵算法：z=;for i=1:72 for k=1:72 if i=k a=sqrt(x(i)-x(k)2+(y(i)-y(k)2);z=z;i,k,a; end endend求覆盖所有污水源的最小支撑树程序：e=z;n=max(e(:,1);e(:,2); % 顶点数m=size(e,1); % 边数M=sum(e(:,3); % 代表无穷大a=z

15、eros(n,n);for k=1:m a(e(k,1),e(k,2)=e(k,3);enda=a+a'a(find(a=0)=M; % 形成图的邻接矩阵result=;p=1; % 设置生成树的起始顶点tb=2:length(a); % 设置生成树以外顶点while length(result)=length(a)-1 % 边数不足顶点数-1 temp=a(p,tb);temp=temp(:); % 取出与p关联的所有边 d=min(temp); % 取上述边中的最小边 jb,kb=find(a(p,tb)=d); % 寻找最小边的两个端点(可能不止一个) j=p(jb(1);k=t

16、b(kb(1); % 确定最小边的两个端点 result=result,j;k;d; % 记录最小生成树的新边 p=p,k; % 扩展生成树的顶点 tb(find(tb=k)=; % 缩减生成树以外顶点endresult % 显示生成树（点、点、边长）weight=sum(result(3,:)求最小支撑树图的程序：for i=1:71 m=x(result (1,i),x(result (2,i);n=y(result (1,i),y(result (2,i); plot(m,n,m,n,'*');hold on;endfor i=1:72 text(x(i),y(i),nu

17、m2str(i);hold on;end污水位置的横坐标：x=183.5 139 117 134.5 82 47 19 25 90 137 232 244 51 34 25 12 27 56 50.5 43 46 115 126 131 171 188.5 219 194 142 125 115 142 145 151 148 170 171 154 163 157 135 181 191 195 198 201 205 208 215 218.5 205.5 205 209 238.5 234 241 240.5 245 70 80 90 100 110 120 130 140 150 16

18、0 170 180 190 200;污水位置的纵坐标：y=91 116 102 93.5 65 41 56 10 75 68 111 134 17 11 5 30 40 41 46 68 77 91 95 75 73 70.5 84 86 82 112 114 112 122 117 109 103 93 114 122.5 127 135 121 115 101 102 99 100 90 91 96 104.5 108 110 113 116 125 121.5 120 40 35 30 25 40 20 10 50 30 55 78 37 49 31；72个点之间最小支撑树矩阵：附录2：

19、污水的日流量：s=2.2 2.1 2.4 2.4 1.6 2.6 2.4 2.2 2.1 2.6 1.9 1.9 1.4 1.4 2.4 1.6 1.61.2 1.8 2.3 2.4 2.6 2.5 2.8 2.4 2.7 2.4 2.1 2.4 2.6 2.4 2.2 2.1 1.62.4 1.9 2 1.6 1.8 2.1 1.6 2.2 2.4 1.7 1.8 1.8 1.9 1.9 2.1 2.1 1.8 2.11.8 2.1 1.9 2.4 1.9 1.9 1.9 2.8 1.6 2.6 1.8 2.1 2.2 1.3 2.1 1.5 2.71.1 2.7 2;除去连接无用的管道程序

20、：plot(czb(:,1),czb(:,2),'r*');hold on;plot(x(16),x(17),y(16),y(17),'w');hold on;plot(x(6),x(19),y(6),y(19),'w');hold on;plot(x(18),x(59),y(18),y(59),'w');hold on;plot(x(61),x(62),y(61),y(62),'w');hold on;plot(x(65),x(67),y(65),y(67),'w');hold on;plot(x

21、(10),x(24),y(10),y(24),'w');hold on;plot(x(4),x(23),y(4),y(23),'w');hold on;plot(x(31),x(30),y(31),y(30),'w');hold on;plot(x(35),x(38),y(35),y(38),'w');hold on;plot(x(40),x(39),y(40),y(39),'w');hold on;plot(x(44),x(45),y(44),y(45),'w');hold on;plot(x(4

22、6),x(47),y(46),y(47),'w');hold on;plot(x(47),x(48),y(47),y(48),'w');hold on;plot(x(37),x(1),y(37),y(1),'w');hold on;plot(x(28),x(26),y(28),y(26),'w');hold on;plot(x(48),x(49),y(48),y(49),'w');hold on;plot(x(50),x(11),y(50),y(11),'w');hold on;plot(x(55),x(57),y(55),y(57),'w');hold on;厂的位置和处理量