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

污水排放问题摘要：本文对沿河工厂如何最省建立污水处理站以及当有联合建污水处理站时各厂如何合理分摊费用进行了研究,建立了0-1整数规划[1]最省建站模型和基于shapley法合理分摊费用模型，并对具体问题进行了求解，说明了求解方案的合理性。对于第一问如何最省建立污水处理站，引入可能建站组合所需费用、组合所需处理的总流量以及0-1决策变量，建立0-1整数规划模型；对于联合建污水处理站各厂如何合理分摊费用，基于合作博弈shapley法[2]合理分配总节省投资，建立合理分摊费用模型。对于第二问具体建站问题，运用第一问中的模型解得最省建站方案为：第一、二家厂联合建立一个污水处理站，第三家厂单独建立一个污水处理站，总的最少费用为581.1万元，合理费用分摊方案为：第一家厂承担195.5万元，第二家厂承担2.126万元，第三家厂承担263.1万元。对于第三问分析方案合理性，在实际情况下，列出所有可能建站方案说明问题二求得的方案是最省的，然后从不同厂家的角度说明分摊费用方案是合理可行的。关键字：污水处理站选址；0-1整数规划；shapley法1问题的重述随着国民经济的快速发展和结构转型，企业在追求经济效益的同时，越来越重视环境保护问题。如何减少污染物的排放以保护环境，使经济得以稳健及可持续发展，是许多企业亟待解决的重要问题。假设沿河有若干工厂，每天都会排放一定量的污水，这些污水必须经过处理才能排入河中。通常的解决办法是建造污水处理站，将污水进行处理，使之达到排放标准后再予以排放。污水处理站可以由每个工厂单独建造，也可以几个工厂联合建造。联合建造时，处理站必须建在下游位置，上游工厂将污水通过管道送往下游的处理站集中处理。处理站的建造费用与污水处理量及铺设的管道总长度有关，表1给出了不同污水处理量和不同管道铺设总长度的建造费用及管道铺设费用。(1)请建立适当的数学模型，给出合理的污水处理站建造方案。如果是联合建造，应给出建造费用的分担方法。(2)若沿河从上游到下游有A，B，C三家工厂，各厂的排污量分别为4.5t/s，2.5t/s和6t/s。已知AB之间的距离为20km，BC之间的距离为40km。请用你建立的模型给出具体的污水处理站建造方案和费用分担方法。(3)分析说明你所给方案的合理性。表1不同污水处理量和不同管道铺设长度的建造费用及管道铺设费用排污量(t/s)管道总长(km)建站费(万元)管道费(万元)总费用(万元)28125.187.08132.26415195.819.91215.716.521265.2136.41301.62826332.5649.58382.14930322.9362.06384.999.538372.6379.55452.181045363.2997.06460.351151374.56116.66491.2212.556430.18141.12571.31565459.29181.18640.472问题的分析2.1问题一的分析处理站的建站费用y由建站费1y和管道费2y构成，而建站费1y只与处理的排污量x有关，管道费2y只与管道的长度z有关。通过表一所给的数据可以拟合出它们各自的函数关系。如果联合建站，污水处理站必须在下游，所以处理站建在最下游的厂的位置才能使总的管道费2y最省，从而总的建站费y最省。综上所述问题转化为如何将厂组合(同一组厂必须连续且相邻)，则污水处理站建立在最下游的厂位置。考虑到组合优化问题计算量随着约束的增加而急剧增长，称为组合爆炸。所以将所有的厂组合情况构造建站组合所需总费用矩阵0A、建站组合所需处理污水总量矩阵0Q、联合厂家的总数矩阵0P，引入0-1决策变量，建立0-1整数规划模型。对于联合建厂时的费用分摊，引入节省投资的定义，将由联合建造污水处理站比单独建造节省的费用看做是该厂获得的收益,这样费用分摊问题便可以看作是合作博弈收益分配问题。在合作博弈收益分配问题中，公平、公正是其最重要的特点，shapley值算法是解决合作博弈收益分配问题的一种较好算法并能考虑到合作团队成员所作贡献及能做到公平公正，故采用shapley法来合理分配总节省投资，使各个厂的费用承担相对合理2.2问题二的分析沿河从上游到下游有A，B，C三家工厂，各厂的排污量分别为4.5t/s，2.5t/s和6t/s。已知AB之间的距离为20km，BC之间的距离为40km。根据已知数值和实际情况，可以判断第一问中的模型适用于该具体案例，因而将其数据代入模型一当中，可以求出三家工厂建造污水处理站的合理方案；根据所求方案，在有联合建造污水处理站的情况下，可以根据合作博弈shapley法对总节省投资进行合理的分配，使得参与联合建站的工厂承担的费用相对合理。2.3问题三的分析对于问题二中给出的具体的建站方案和费用分摊方案，从所有可能的方案考虑所得建站方案是否最省，从不同厂家的角度分析承担的费用是否合理。3模型的假设(1)管道规格相同，且能承受足够大的压力；(2)管道费只与长度有关，可以通过增加处理站的压力提高污水流速达到大排量的要求；(3)在第i家工厂建立污水处理站不考虑第i家工厂的管道费(相对于厂与厂之间的管道长度可以忽略不计)；(4)各厂家的排污量不会出现特别小以至于不需要建立污水处理站的情况；(5)题中所给数据真实有效。4符号说明i：沿河上游到下游的工厂编号，其中1,2,,1,inn；j：联合建立一个污水处理站的厂数，其中1,2,,1,jnn，如4j表示4家工厂联合建立一个污水处理站；iq：第i家工厂的排污量；il：第i家工厂到第1i家工厂所需的管道长度；0A:联合建站时建站组合所需总费用矩阵，且0,()ijnnAa，其中,ija表示从第i家工厂开始沿下游有j个工厂联合建一个污水处理站的总费用；0Q：联合建站时建站组合所需处理污水总量矩阵，且0,()ijnnQQ，其中,ijQ表示从第i家工厂开始沿下游有j个工厂联合建一个污水处理站所处理的污水总量；0P：联合建站时联合厂家的总个数矩阵，且0,()ijnnPp，其中,ijp表示从第i家工厂开始沿下游有j个工厂联合建污水处理站；,ijx：建污水处理站的位置，其中,01ijx或，其中,1ijx表示从第i家工厂开始沿下游有j个工厂联合建一个污水处理站，否则,0ijx；s:所有厂的组合情况集合为1,2,,1,Inn,则sI为I的子集，；)(sv:联合(集合s)建造污水处理站比单独建造节约的投资；)/(isv：s集合中除去第i厂，其他厂联合建造污水处理站比单独建造节约的投资；iw：第i个厂从节省投资中得到的分配；it：联合建站时第i家工厂应该承担的费用；s：子集s中的厂的个数；iS：包含所有i的子集(所有联合建厂方案中包含第i厂的方案)；)(sh：s决定的权重。5模型的建立与求解5.1处理站建站费用的确立处理站的建造费用即总费用y与污水处理量及铺设的管道总长度有关，且为处理站的建站费1y和管道费2y之和，即12yyy下面确立建站费1y和管道费2y与排污量x和管道长度z之间的关系。5.1.1建站费的确立建站费1y只与处理排污量x的能力有关，即1()yfx由表一所给数据，在最小二乘准则[3]下拟合函数，拟合结果如图1051015050100150200250300350400450500排污量建站费原始数据拟合曲线图1建站费1y拟合曲线同时得到拟合优度20.9834R，拟合效果较好，于是得到拟合函数0.65182.1yx分析拟合的建站费曲线可以得出：(1)建站费随着处理污水量的增加呈现大致的线性增长；(2)建站费在排污量小于1t/s时的增长速度明显大于排污量大于1t/s时的增长速度。5.1.2管道费的确立由于采用的管道相同，管道费只与管道的总长度有关。实际上对于单位排量大的管道，由于QVA其中Q为管道单位排量，V污水流速，A为管道面积，即使采用相同的管道，也可以提高处理站的处理能力从而提高管道排污的流速达到大排量的要求。所以管道费可以近似为2()ygz其中z为管道的总长度。由表一所给数据，在最小二乘准则下拟合函数，拟合结果如图2010203040506070020406080100120140160180200管长管道费原始数据拟合曲线图2管道费2y拟合曲线同时得到拟合优度20.9944R，拟合效果较好，于是得到拟合函数1.4620.39yz分析拟合的管道费曲线可以得出：(1)管道费随着管道长度的增加而增加；(2)管道费的增长率随着管道长度的增大而增大。5.2问题一模型的建立与求解5.2.1建造污水处理站问题设从沿河上游到下游有n家工厂，1,2,,1,inn为工厂的编号，如5i表示第5家工厂；iq表示第i家工厂的排污量；il表示从i家工厂到第1i家工厂的距离即管道长度,且0nl。引入⑴建站组合所需总费用矩阵0A1,11,21,11,2,12,22,101,11,2,1nnnnnnaaaaaaaAaaa其中0A为左上三角矩阵，,ija表示不存在这种组合情况，否则,ija表示从第i家工厂开始沿下游有j个工厂联合建一个污水处理站(由问题分析知污水站一定建在联合建厂的最下游厂的位置)的总费用，则121212,()+()ijijijkkkikiafqgl其中1,2,,1,inn，1,2,,1,jnn。⑵建站组合所需处理污水总量矩阵0Q1,11,21,11,2,12,22,101,11,2,1000000nnnnnnQQQQQQQQQQQ其中0Q为左上三角矩阵，,ijQ表示从第i家工厂开始沿下游有j个工厂联合建一个污水处理站(由问题分析知污水站一定建在联合建厂的最下游厂的位置)所处理的污水总量，则111,ijijkkiQq其中1,2,,1,inn，1,2,,1,jnn。⑶联合建站时联合厂家的总个数矩阵0P0121121012001000nnnP其中0P为左上三角矩阵，,ijpj表示从第i家工厂开始沿下游有j个工厂联合建污水处理站，当,ijp在左上三角。⑷引入决策变量,10ijijx表示从第家工厂开始沿下游有个工厂联合建一个污水处理站否则于是得到决策矩阵,()nnijnnXx。所以沿河n家工厂建立污水处理站的总费用为,,11nnijijijcxa约束条件有：Ⅰ.每个厂有且只需要一个污水处理站，则,11,1,2,,1,nijjxinnⅡ.建立的污水处理站能覆盖所有的厂家,则,,11nnijijijxpnⅢ.建立所有污水处理站的处理污水量之和等于所有厂家的污水排量之和，则,,11nnijijijxQQ总其中1=niiQq总为所有厂家的污水排量之和。综上所述，建立0-1整数规划模型如下：,,11minnnijijijcxa,1,,11,,11,11,2,,1,s.t.011,2,,1,1,2,,1,nijjnnijijijnnijijijijxinnxpnxQQxinnjnn总或5.2.2联合建污水处理站分摊费用问题假设有m个厂联合建立一个污水处理站，采用合作博弈shapley值法来给出合理的费用分摊方案。记m个联合建造工厂的集合1,2,,1,Imm，子集Is，存在实函数)(sv满足121212()0()()(),vvssvsvsss其中)(sv为联合(集合s)建厂比单独建厂节约的投资。vI,为m个厂的节约投资分配方案，)/(isv为s集合中除去第i厂其他厂联合建厂比单独建厂节约的投资。记m个工厂单独建造污水处理厂所需要的总费用为1miic,ic表示第i个工厂单独建造污水站的费用，m个工厂联合建造费用为c联，则11()()1,2,...,mmiiiiiiwccvIwviin