《最新第十六届华东杯大学生数学建模邀请赛—污水厂选址问题 [汇编整理]》由会员分享，可在线阅读，更多相关《最新第十六届华东杯大学生数学建模邀请赛—污水厂选址问题 [汇编整理]（14页珍藏版）》请在金锄头文库上搜索。
1、污水排放问题 摘要 本文对沿河工厂如何最省建立污水处理站以及当有联合建污水处理站时各 厂如何合理分摊费用进行了研究 建立了 0 1 整数规划 1 最省建站模型和基于 shapley法合理分摊费用模型 并对具体问题进行了求解 说明了求解方案的合理 性 对于第一问如何最省建立污水处理站 引入可能建站组合所需费用 组合所 需处理的总流量以及0 1 决策变量 建立 0 1 整数规划模型 对于联合建污水处 理站各厂如何合理分摊费用 基于合作博弈shapley法 2 合理分配总节省投资 建立合理分摊费用模型 对于第二问具体建站问题 运用第一问中的模型解得最省建站方案为 第一 二家厂联合建立一个污水处理站
2、第三家厂单独建立一个污水处理站 总的最少 费用为 581 1万元 合理费用分摊方案为 第一家厂承担195 5万元 第二家厂承 担2 126万元 第三家厂承担263 1万元 对于第三问分析方案合理性 在实际情况下 列出所有可能建站方案说明问 题二求得的方案是最省的 然后从不同厂家的角度说明分摊费用方案是合理可行 的 关键字 污水处理站选址 0 1 整数规划 shapley法 1 问题的重述 随着国民经济的快速发展和结构转型 企业在追求经济效益的同时 越来越 重视环境保护问题 如何减少污染物的排放以保护环境 使经济得以稳健及可持 续发展 是许多企业亟待解决的重要问题 假设沿河有若干工厂 每天都会排
3、放一定量的污水 这些污水必须经过处理 才能排入河中 通常的解决办法是建造污水处理站 将污水进行处理 使之达到 排放标准后再予以排放 污水处理站可以由每个工厂单独建造 也可以几个工厂联合建造 联合建造 时 处理站必须建在下游位置 上游工厂将污水通过管道送往下游的处理站集中 处理 处理站的建造费用与污水处理量及铺设的管道总长度有关 表 1 给出了不 同污水处理量和不同管道铺设总长度的建造费用及管道铺设费用 1 请建立适当的数学模型 给出合理的污水处理站建造方案 如果是联合 建造 应给出建造费用的分担方法 2 若沿河从上游到下游有A B C三家工厂 各厂的排污量分别为t s t s 和 6 t s
4、已知 AB之间的距离为 20 km BC之间的距离为 40 km 请用你建立的 模型给出具体的污水处理站建造方案和费用分担方法 3 分析说明你所给方案的合理性 表 1 不同污水处理量和不同管道铺设长度的建造费用及管道铺设费用 排污量 t s 管道总长 km 建站费 万 元 管道费 万 元 总费用 万 元 28 415 21 826 930 38 1045 1151 56 1565 2 问题的分析 问题一的分析 处理站的建站费用y 由建站费 1 y和管道费 2 y构成 而建站费 1 y只与处理的 排污量x有关 管道费 2 y只与管道的长度z有关 通过表一所给的数据可以拟合 出它们各自的函数关系
5、如果联合建站 污水处理站必须在下游 所以处理站建 在最下游的厂的位置才能使总的管道费 2 y最省 从而总的建站费y最省 综上所述问题转化为如何将厂组合 同一组厂必须连续且相邻 则污水处理 站建立在最下游的厂位置 考虑到组合优化问题计算量随着约束的增加而急剧增 长 称为组合爆炸 所以将所有的厂组合情况构造建站组合所需总费用矩阵 0 A 建站组合所需处理污水总量矩阵 0 Q 联合厂家的总数矩阵 0 P 引入 0 1 决策变 量 建立 0 1 整数规划模型 对于联合建厂时的费用分摊 引入节省投资的定义 将由联合建造污水处理 站比单独建造节省的费用看做是该厂获得的收益 这样费用分摊问题便可以看作 是合
6、作博弈收益分配问题 在合作博弈收益分配问题中 公平 公正是其最重要 的特点 shapley值算法是解决合作博弈收益分配问题的一种较好算法并能考虑 到合作团队成员所作贡献及能做到公平公正 故采用shapley法来合理分配总节 省投资 使各个厂的费用承担相对合理 问题二的分析 沿河从上游到下游有A B C 三家工厂 各厂的排污量分别为t s t s 和 6 t s 已知 AB之间的距离为 20 km BC之间的距离为 40 km 根据已知数值和实际情况 可以判断第一问中的模型适用于该具体案例 因而将其数据代入模型一当中 可以求出三家工厂建造污水处理站的合理方案 根据所求方案 在有联合建造污水处理站
7、的情况下 可以根据合作博弈shapley 法对总节省投资进行合理的分配 使得参与联合建站的工厂承担的费用相对合 理 问题三的分析 对于问题二中给出的具体的建站方案和费用分摊方案 从所有可能的方案 考虑所得建站方案是否最省 从不同厂家的角度分析承担的费用是否合理 3 模型的假设 1 管道规格相同 且能承受足够大的压力 2 管道费只与长度有关 可以通过增加处理站的压力提高污水流速达到大 排量的要求 3 在第 i 家工厂建立污水处理站不考虑第i 家工厂的管道费 相对于厂与厂之 间的管道长度可以忽略不计 4 各厂家的排污量不会出现特别小以至于不需要建立污水处理站的情况 5 题中所给数据真实有效 4 符
8、号说明 i 沿河上游到下游的工厂编号 其中1 2 1 innL j 联合建立一个污水处理站的厂数 其中1 2 1 jnnL 如4j表示 4 家工厂联合建立一个污水处理站 i q 第 i 家工厂的排污量 i l 第 i 家工厂到第1i家工厂所需的管道长度 0 A 联合建站时建站组合所需总费用矩阵 且 0 i jn n Aa 其中 i j a表示从第 i 家工厂开始沿下游有j 个工厂联合建一个污水处理站的总费用 0 Q 联合建站时建站组合所需处理污水总量矩阵 且 0 i jn n QQ 其中 i j Q 表示从第 i 家工厂开始沿下游有j 个工厂联合建一个污水处理站所处理的污水总 量 0 P 联合
9、建站时联合厂家的总个数矩阵 且 0 i jn n Pp 其中 i j p表示从第 i 家工厂开始沿下游有j 个工厂联合建污水处理站 i j x 建污水处理站的位置 其中 01 i j x或 其中 1 i j x表示从第 i 家工厂开 始沿下游有 j 个工厂联合建一个污水处理站 否则 0 i j x s 所有厂的组合情况集合为1 2 1 InnL 则 sI 为 I 的子集 sv 联合 集合s 建造污水处理站比单独建造节约的投资 isv s集合中除去第 i 厂 其他厂联合建造污水处理站比单独建造节约的 投资 i w 第 i 个厂从节省投资中得到的分配 i t 联合建站时第 i 家工厂应该承担的费用
10、 s 子集s中的厂的个数 i S 包含所有 i 的子集 所有联合建厂方案中包含第i 厂的方案 sh s 决定的权重 5 模型的建立与求解 处理站建站费用的确立 处理站的建造费用即总费用y与污水处理量及铺设的管道总长度有关 且 为处理站的建站费 1 y和管道费 2 y之和 即 12 yyy 下面确立建站费 1 y和管道费 2 y与排污量x和管道长度z之间的关系 5 1 1 建站费的确立 建站费 1 y只与处理排污量x的能力有关 即 1 yfx 由表一所给数据 在最小二乘准则 3 下拟合函数 拟合结果如图1 051015 0 50 100 150 200 250 300 350 400 450 5
11、00 排 污 量 建 站 费 原 始 数 据 拟 合 曲 线 图 1 建站费 1 y拟合曲线 同时得到拟合优度 2 0 9834R 拟合效果较好 于是得到拟合函数 0 65 182 1yx 分析拟合的建站费曲线可以得出 1 建站费随着处理污水量的增加呈现大致的线性增长 2 建站费在排污量小于 1 t s时的增长速度明显大于排污量大于1 t s时的增 长速度 5 1 2 管道费的确立 由于采用的管道相同 管道费只与管道的总长度有关 实际上对于单位排量 大的管道 由于 QVA 其中Q为管道单位排量 V 污水流速 A为管道面积 即使采用相同的管道 也 可以提高处理站的处理能力从而提高管道排污的流速达
12、到大排量的要求 所以管 道费可以近似为 2 yg z 其中z为管道的总长度 由表一所给数据 在最小二乘准则下拟合函数 拟合结果如图2 010203040506070 0 20 40 60 80 100 120 140 160 180 200 管 长 管 道 费 原 始 数 据 拟 合 曲 线 图 2 管道费 2 y拟合曲线 同时得到拟合优度 2 0 9944R 拟合效果较好 于是得到拟合函数 1 46 2 0 39yz 分析拟合的管道费曲线可以得出 1 管道费随着管道长度的增加而增加 2 管道费的增长率随着管道长度的增大而增大 问题一模型的建立与求解 5 2 1 建造污水处理站问题 设从沿河上
13、游到下游有n家工厂 1 2 1 innL为工厂的编号 如5i表 示第 5家工厂 i q表示第 i 家工厂的排污量 i l表示从 i 家工厂到第1i家工厂的 距离即管道长度 且0 n l 引入 建站组合所需总费用矩阵 0 A 1 11 21 11 2 12 22 1 0 1 11 2 1 nn n nn n aaaa aaa A aa a L L MMNMM L L 其中 0 A为左上三角矩阵 i j a表示不存在这种组合情况 否则 i j a表示从第 i 家工厂开始沿下游有j 个工厂联合建一个污水处理站 由问题分析知污水站一定 建在联合建厂的最下游厂的位置 的总费用 则 12 12 12 ij
14、ij i jkk kiki afqgl 其中1 2 1 innL 1 2 1 jnnL 建站组合所需处理污水总量矩阵 0 Q 1 11 21 11 2 12 22 1 0 1 11 2 1 0 00 000 nn n nn n QQQQ QQQ Q QQ Q L L MMNMM K L 其中 0 Q为左上三角矩阵 i j Q表示从第 i 家工厂开始沿下游有j 个工厂联合建一 个污水处理站 由问题分析知污水站一定建在联合建厂的最下游厂的位置 所处理 的污水总量 则 1 1 1 ij i jk ki Qq 其中1 2 1 innL 1 2 1 jnnL 联合建站时联合厂家的总个数矩阵 0 P 0
15、121 1210 1200 1000 nn n P L L M M NLM L L 其中 0 P为左上三角矩阵 i j pj表示从第 i 家工厂开始沿下游有j 个工厂联合建 污水处理站 当 i j p 在左上三角 引入决策变量 1 0 i j ij x 表示从第 家工厂开始沿下游有个工厂联合建一个污水处理站 否则 于是得到决策矩阵 n ni jn n Xx 所以沿河 n 家工厂建立污水处理站的总费用为 11 nn i ji j ij cx a 约束条件有 每个厂有且只需要一个污水处理站 则 1 1 1 2 1 n i j j xinnL 建立的污水处理站能覆盖所有的厂家 则 11 nn i j
16、i j ij xpn 建立所有污水处理站的处理污水量之和等于所有厂家的污水排量之和 则 11 nn i ji j ij x QQ总 其中 1 n i i Qq 总 为所有厂家的污水排量之和 综上所述 建立 0 1 整数规划模型如下 11 min nn i ji j ij cxa 1 11 11 1 1 2 1 s t 01 1 2 1 1 2 1 n i j j nn i ji j ij nn i ji j ij i j xinn xpn x QQ xinnjnn L LL 总 或 5 2 2 联合建污水处理站分摊费用问题 假设有m个厂联合建立一个污水处理站 采用合作博弈shapley值法来给出 合理的费用分摊方案 记m个联合建造工厂的集合1 2 1 ImmL 子集Is 存在实函 数 sv满足 121212 0 v v ssv sv sssUI 其中 sv为联合 集合s 建厂比单独建厂节约的投资 vI 为m个厂的节约投资 分配方案 isv为s集合中除去第 i 厂其他厂联合建厂比单独建厂节约的投资 记m个工厂单独建造污水处理厂所需要的总费用为 1 m i i c i c表示第i个工厂 单
