第十六届华东杯大学生数学建模邀请赛—污水厂选址问题.doc

污水排放问题 摘要：本文对沿河工厂如何最省建立污水处理站以及当有联合建污水处理站时各厂如何合理分摊费用进行了研究,建立了0-1整数规划[1]最省建站模型和基于shapley法合理分摊费用模型，并对具体问题进行了求解，说明了求解方案的合理性。 对于第一问如何最省建立污水处理站，引入可能建站组合所需费用、组合所需处理的总流量以及0-1决策变量，建立0-1整数规划模型；对于联合建污水处理站各厂如何合理分摊费用，基于合作博弈shapley法[2]合理分配总节省投资，建立合理分摊费用模型。 对于第二问具体建站问题，运用第一问中的模型解得最省建站方案为：第一、二家厂联合建立一个污水处理站，第三家厂单独建立一个污水处理站，总的最少费用为万元，合理费用分摊方案为：第一家厂承担万元，第二家厂承担万元，第三家厂承担万元。 对于第三问分析方案合理性，在实际情况下，列出所有可能建站方案说明问题二求得的方案是最省的，然后从不同厂家的角度说明分摊费用方案是合理可行的。 关键字：污水处理站选址；0-1整数规划；shapley法 1 问题的重述 随着国民经济的快速发展和结构转型，企业在追求经济效益的同时，越来越重视环境保护问题。如何减少污染物的排放以保护环境，使经济得以稳健及可持续发展，是许多企业亟待解决的重要问题。 假设沿河有若干工厂，每天都会排放一定量的污水，这些污水必须经过处理才能排入河中。通常的解决办法是建造污水处理站，将污水进行处理，使之达到排放标准后再予以排放。 污水处理站可以由每个工厂单独建造，也可以几个工厂联合建造。联合建造时，处理站必须建在下游位置，上游工厂将污水通过管道送往下游的处理站集中处理。处理站的建造费用与污水处理量及铺设的管道总长度有关，表1给出了不同污水处理量和不同管道铺设总长度的建造费用及管道铺设费用。 (1)?请建立适当的数学模型，给出合理的污水处理站建造方案。如果是联合建造，应给出建造费用的分担方法。 (2)?若沿河从上游到下游有A，B，C三家工厂，各厂的排污量分别为4.5 t/s，2.5 t/s和6 t/s。已知AB之间的距离为20 km，BC之间的距离为40 km。请用你建立的模型给出具体的污水处理站建造方案和费用分担方法。 (3)?分析说明你所给方案的合理性。 表1 不同污水处理量和不同管道铺设长度的建造费用及管道铺设费用 排污量(t/s) 管道总长(km) 建站费(万元) 管道费(万元) 总费用(万元) 2 8 125.18 7.08 132.26 4 15 195.8 19.91 215.71 6.5 21 265.21 36.41 301.62 8 26 332.56 49.58 382.14 9 30 322.93 62.06 384.99 9.5 38 372.63 79.55 452.18 10 45 363.29 97.06 460.35 11 51 374.56 116.66 491.22 12.5 56 430.18 141.12 571.3 15 65 459.29 181.18 640.47 2 问题的分析 2.1问题一的分析 处理站的建站费用由建站费和管道费构成，而建站费只与处理的排污量有关，管道费只与管道的长度有关。通过表一所给的数据可以拟合出它们各自的函数关系。如果联合建站，污水处理站必须在下游，所以处理站建在最下游的厂的位置才能使总的管道费最省，从而总的建站费最省。 综上所述问题转化为如何将厂组合(同一组厂必须连续且相邻)，则污水处理站建立在最下游的厂位置。考虑到组合优化问题计算量随着约束的增加而急剧增长，称为组合爆炸。所以将所有的厂组合情况构造建站组合所需总费用矩阵、建站组合所需处理污水总量矩阵、联合厂家的总数矩阵，引入0-1决策变量，建立0-1整数规划模型。 对于联合建厂时的费用分摊，引入节省投资的定义，将由联合建造污水处理站比单独建造节省的费用看做是该厂获得的收益,这样费用分摊问题便可以看作是合作博弈收益分配问题。在合作博弈收益分配问题中，公平、公正是其最重要的特点，值算法是解决合作博弈收益分配问题的一种较好算法并能考虑到合作团队成员所作贡献及能做到公平公正，故采用法来合理分配总节省投资，使各个厂的费用承担相对合理 2.2问题二的分析 沿河从上游到下游有A，B，C三家工厂，各厂的排污量分别为4.5 t/s，2.5 t/s和6 t/s。已知AB之间的距离为20 km，BC之间的距离为40 km。 根据已知数值和实际情况，可以判断第一问中的模型适用于该具体案例，因而将其数据代入模型一当中，可以求出三家工厂建造污水处理站的合理方案；根据所求方案，在有联合建造污水处理站的情况下，可以根据合作博弈shapley法对总节省投资进行合理的分配，使得参与联合建站的工厂承担的费用相对合理。