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

第十六届华东杯大学生数学建模邀请赛—污水厂选址问污水排放问题摘要：本文对沿河工厂如何最省建立污水处理站以及当有联合建污水处理站时各厂如何合理分摊费用进行了研究,建立了0-1整数规划[1]最省建站模型和基于shapley法合理分摊费用模型，并对具体问题进行了求解，说明了求解的合理性。对于第一问如何最省建立污水处理站，引入可能建站组合所需费用、组合所需处理的总流量以及0-1决策变量，建立0-1整数规划模型；对于联合建污水处理站各厂如何合理分摊费用，基于合作博弈shapley法[2]合理分配总节省投资，建立合理分摊费用模型。对于第二问具体建站问题，运用第一问中的模型解得最省建站方案为：第一、二家厂联合建立一个污水处理站，第三家厂单独建立一个污水处理站，总的最少费用为万元，合理费用分摊方案为：第一家厂承担万元，第二家厂承担万元，第三家厂承担万元。对于第三问分析方案合理性，在实际情况下，列出所有可能建站方案说明问题二求得的方案是最省的，然后从不同厂家的角度说明分摊费用方案是合理可行的。关键字：污水处理站选址；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问题一的分析处理站的建站费用由建站费和管道费构成，而建站费只与处理的排污量有关，管道费只与管道的长度有关。通过表一所给的数据可以拟合出它们各自的函数关系。如果联合建站，污水处理站必须在下游，所以处理站建在最下游的厂的位置才能使总的管道费最省，从而总的建站费最省。综上所述问题转化为如何将厂组合(同一组厂必须连续且相邻)，则污水处理站建立在最下游的厂位置。考虑到组合优化问题计算量随着约束的增加而急剧增长，称为组合爆炸。所以将所有的厂组合情况构造建站组合所需总费用矩阵、建站组合所需处理污水总量矩阵、联合厂家的总数矩阵，引入0-1决策变量，建立0-1整数规划模型。对于联合建厂时的费用分摊，引入节省投资的定义，将由联合建造污水处理站比单独建造节省的费用看做是该厂获得的收益,这样费用分摊问题便可以看作是合作博弈收益分配问题。在合作博弈收益分配问题中，公平、公正是其最重要的特点，值算法是解决合作博弈收益分配问题的一种较好算法并能考虑到合作团队成员所作贡献及能做到公平公正，故采用法来合理分配总节省投资，使各个厂的费用承担相对合理2.2问题二的分析沿河从上游到下游有A，B，C三家工厂，各厂的排污量分别为4.5t/s，2.5t/s和6t/s。已知AB之间的距离为20km，BC之间的距离为40km。根据已知数值和实际情况，可以判断第一问中的模型适用于该具体案例，因而将其数据代入模型一当中，可以求出三家工厂建造污水处理站的合理方案；根据所求方案，在有联合建造污水处理站的情况下，可以根据合作博弈shapley法对总节省投资进行合理的分配，使得参与联合建站的工厂承担的费用相对合理。2.3问题三的分析对于问题二中给出的具体的建站方案和费用分摊方案，从所有可能的方案考虑所得建站方案是否最省，从不同厂家的角度分析承担的费用是否合理。3模型的假设(1)管道规格相同，且能承受足够大的压力；(2)管道费只与长度有关，可以通过增加处理站的压力提高污水流速达到大排量的；(3)在第家工厂建立污水处理站不考虑第家工厂的管道费(相对于厂与厂之间的管道长度可以忽略不计)；(4)各厂家的排污量不会出现特别小以至于不需要建立污水处理站的情况；(5)题中所给数据真实有效。4符号说明：沿河上游到下游的工厂编号，其中；：联合建立一个污水处理站的厂数，其中，如表示家工厂联合建立一个污水处理站；：第家工厂的排污量；：第家工厂到第家工厂所需的管道长度；:联合建站时建站组合所需总费用矩阵，且，其中表示从第家工厂开始沿下游有个工厂联合建一个污水处理站的总费用；：联合建站时建站组合所需处理污水总量矩阵，且，其中表示从第家工厂开始沿下游有个工厂联合建一个污水处理站所处理的污水总量；：联合建站时联合厂家的总个数矩阵，且，其中表示从第家工厂开始沿下游有个工厂联合建污水处理站；：建污水处理站的位置，其中，其中表示从第家工厂开始沿下游有个工厂联合建一个污水处理站，否则；:所有厂的组合情况集合为,则为的子集，；:联合(集合)建造污水处理站比单独建造节约的投资；：集合中除去第厂，其他厂联合建造污水处理站比单独建造节约的投资；：第个厂从节省投资中得到的分配；：联合建站时第家工厂应该承担的费用；：子集中的厂的个数；：包含所有的子集(所有联合建厂方案中包含第厂的方案)；：决定的权重。5模型的建立与求解5.1处理站建站费用的确立处理站的建造费用即总费用与污水处理量及铺设的管道总长度有关，且为处理站的建站费和管道费之和，即下面确立建站费和管道费与排污量和管道长度之间的关系。5.1.1建站费的确立建站费只与处理排污量的能力有关，即由表一所给数据，在最小二乘准则[3]下拟合函数，拟合结果如图1图1建站费拟合曲线同时得到拟合优度，拟合效果较好，于是得到拟合函数分析拟合的建站费曲线可以得出：(1)建站费随着处理污水量的增加呈现大致的线性增长；(2)建站费在排污量小于时的增长速度明显大于排污量大于时的增长速度。5.1.2管道费的确立由于采用的管道相同，管道费只与管道的总长度有关。实际上对于单位排量大的管道，由于其中为管道单位排量，污水流速，为管道面积，即使采用相同的管道，也可以提高处理站的处理能力从而提高管道排污的流速达到大排量的要求。所以管道费可以近似为其中为管道的总长度。由表一所给数据，在最小二乘准则下拟合函数，拟合结果如图2图2管道费拟合曲线同时得到拟合优度，拟合效果较好，于是得到拟合函数分析拟合的管道费曲线可以得出：(1)管道费随着管道长度的增加而增加；(2)管道费的增长率随着管道长度的增大而增大。5.2问题一模型的建立与求解5.2.1建造污水处理站问题设从沿河上游到下游有家工厂，为工厂的编号，如表示第家工厂；表示第家工厂的排污量；表示从家工厂到第家工厂的距离即管道长度,且。引入⑴建站组合所需总费用矩阵其中为左上三角矩阵，表示不存在这种组合情况，否则表示从第家工厂开始沿下游有个工厂联合建一个污水处理站(由问题分析知污水站一定建在联合建厂的最下游厂的位置)的总费用，则其中，。⑵建站组合所需处理污水总量矩阵其中为左上三角矩阵，表示从第家工厂开始沿下游有个工厂联合建一个污水处理站(由问题分析知污水站一定建在联合建厂的最下游厂的位置)所处理的污水总量，则其中，。⑶联合建站时联合厂家的总个数矩阵其中为左上三角矩阵，表示从第家工厂开始沿下游有个工厂联合建污水处理站，当在左上三角。⑷引入决策变量于是得到决策矩阵。所以沿河家工厂建立污水处理站的总费用为约束条件有：Ⅰ.每个厂有且只需要一个污水处理站，则Ⅱ.建立的污水处理站能覆盖所有的厂家,则Ⅲ.建立所有污水处理站的处理污水量之和等于所有厂家的污水排量之和，则其中为所有厂家的污水排量之和。综上所述，建立0-1整数规划模型如下：5.2.2联合建污水处理站分摊费用问题假设有个厂联合建立一个污水处理站，采用合作博弈shapley值法来给出合理的费用分摊方案。记个联合建造工厂的集合，子集，存在实函数满足其中为联合(集合)建厂比单独建厂节约的投资。为个厂的节约投资分配方案，为集合中除去第厂其他厂联合建厂比单独建厂节约的投资。记个工厂单独建造污水处理厂所需要的总费用为,表示第个工厂单独建造污水站的费用，个工厂联合建造费用为，则其中为第个厂从节约投资中得到的分配，且其中为子集中的厂的个数，为所有包含第家厂的子集（所有联合建厂方案中包含第厂的方案），为决定的权重。所以第个厂的所需承担的建立污水站的费用为单独建造污水站的费用与节约投资所得分配的差值，即5.3问题二的求解沿河从上游到下游有A，B，C三家工厂，各厂的排污量分别为4.5t/s、2.5t/s和6t/s；AB之间的距离为20km，BC之间的距离为40km，即有，；，，；，。利用第一问中的0-1整数规划模型给出具体的污水处理站的建站方案，若出现联合建站的情况则利用第一问中值法来给出合理的费用分摊方案。5.3.1建造污水处理站的方案建立联合建站时建站组合所需总费用矩阵，由其中，，得到联合建站时建站组合所需总费用矩阵为建立联合建站时建站组合所需处理污水总量矩阵，由其中，，得到联合建站时建站组合所需处理污水总量矩阵为。建立联合建站时联合厂家的总个数矩阵为引入决策矩阵其中，表示从第家工厂开始沿下游有个工厂联合建一个污水处理站，否则。由第一问得到0-1整数规划模型如下：其中为家厂的污水排量之和。解得决策矩阵为于是得到最省建站方案为：第一家和第二家厂在第二家厂的位置共建一个污水处理站，第三家厂则在自己厂的位置单独建一个污水处理站。同时得到最省费用为5.3.2联合建造污水处理站时分摊费用的方案因为一、二两厂联合建造，所以建造工厂的集合为。设一、二两厂联合建造的费用为，一厂单独建造的费用为，二厂单独建造的费用为，三个厂分别单独建造费用之和为，则有万元万元万元万元设联合建厂比单独建厂节约的投资为，且子集，存在，则万元。故有：(1)当时，根据值法解得的节省投资分配方案见表2表2当时的值法节省投资分配其中为子集中的厂的个数，为所有包含第1家厂的子集，即所有联合建厂方案中包含第厂的方案，为决定的权重,则有万元所以万元。(2)当时，根据值法解得的节省投资分配方案见表3表3当时的值法节省投资分配其中为子集中的厂的个数，为所有包含第2家厂的子集，即所有联合建厂方案中包含第厂的方案，为决定的权重,则有万元所以万元。综上所述，分配方案为一、二两厂联合建造，且一厂承担万元，二厂承担万元，三厂单独建造且承担费用为万元。5.3问题三的求解5.3.1建造污水处理站的方案的合理性为了检验问题二中模型解得建造污水处理站的方案是否合理，可以枚举出所有可能方案，检验方案是否费用最小。对于第二问三家厂建设污水处理站一共有4种情况：①三家工厂都各自单独建立污水处理站时，总费用为万元②三家工厂联合建造一个污水处理站时，总的费用为万元③第一家工厂和第二家工厂联合建造一个污水处理站，第三家工厂单独建造一个污水处理站时，总费用为万元④第二家工厂和第三家工厂联合建造一个污水处理站，第一家工厂单独建造一个污水处理站时，总费用为万元其中为第二问中联合建站时建站组合所需总费用矩阵中的元素。由以上枚举的结果可知第②中情况三家工厂的总费用最少，这和问题二中模型求解所得到的方案相同，所以问题二中模型解得建造污水处理站的方案是合理的。5.3.2联合建造污水处理站时分摊费用方案的合理性在问题二中解得的最优方案中，第一家工厂和第二家工厂合建一个污水处理站，所以存在一个费用分摊的问题。从第二家厂的角度出发，认为合建的污水处理站的建站费应该由两家厂按处理的污水量比例分摊，由于自己并没有使用排污管道，所以管道费应该由第一家厂承担。第一家厂按照第二家厂的费用分摊方案计算联合建污水处理站时自己应承担的费用为万元如果第一家厂自己单独建造一个污水处理站应承担的费用为万元其中为第二问中联合建站时建站组合所需总费用矩阵中的元素。相反第二家厂联合建造时承担的费用比单独建造时承担的费用减少为万元由以上可知第一家厂在联合建污水处理站分摊的费用比自己单独建造污水处理站承担的费用还高，而联合建造时节省的投资全部分配给了第二家厂，显然第一家厂不会同意这种方案。综上所述只有合理分配节省的投资才能使分摊费用方案更合理，而问题二使用中shapley值法给出合理的费用分摊方案的实质就是根据各个厂对节省投资“贡献”的权重来分配节省投资，且每一个厂承担的费用一定比单独建造承担得少，对于所有工厂来说是公平的，所以方案具有一定的合理性。6模型的评价与推广本文通过所给的参数以及结合一些合理假设，建立如何建造污水处理站的0-1线性模型有效地避免了组合优化带来的组合爆炸,确定了合理的费用分摊方案。根据第二问所给数据，通过模型求得具体的方案，从具体情况说明所建模型的合理性。模型的准确性高，对于实际情况下的污水处理站建造问题及费用分摊问题有一定的借鉴意义。但也存在着一些不足:没有站在单一工厂的角度考虑如何费用最省，在模型的假设上存在主观上的判断，下一步对模型的改进方面可以考虑进一步探讨相关问题；如果有的厂家的排污量出现很小的情况，即可以不连续厂家建站的情况没有考虑，下一步可以进行改进。参考文献：[1]赵静，但琦，数学建模与数学实验，北京,高等教育出版社，2007年5月[2]司守奎，孙玺菁，数学建模算法与应用，北京：国防工业出版社，2011年3月[3]汪天飞，邹进，张军，数学建模与数学实验，北京：科学出版社，2013,1月p1=tril(p1);q2=tril(q2);fori=1:3a1=rot90(a1);p1=rot90(p1);q2=rot90(q2);endfori=1:n;forj=1:n;ifa1(i,j)==0;a1(i,j)=10000;endendendxlswrite('apq.xls',a1,'sheet1','a1');xlswrite('apq.xls',p1,'sheet2','a1');xlswrite('apq.xls',q2,'sheet3','a1');建站的lingo程序：model:!输入厂家的个数n;data:n=10;enddatasets:cz/1..n/;gs/1..n/;wsz(cz,gs):x,a,p,q;endsets!调入费用矩阵a,个数矩阵p，流量矩阵q，注意定义数据模块名称;data:a,p,q=@ole('d:/matlab2013/work/apq.xls','a','p','q');enddatamin=@sum(wsz:x*a);@for(cz(i):@sum(gs(j):x(i,j))<1);@sum(wsz:x*p)=n;@sum(wsz:x*q)=q(1,n);@for(wsz:@bin(x));end