《数学建模之水厂供水的优化问题》由会员分享,可在线阅读,更多相关《数学建模之水厂供水的优化问题(8页珍藏版)》请在金锄头文库上搜索。
1、数学建模在实际中的应用水厂供水的优化问题学号 姓名 专业 选址是生活中经常遇到的问题,如向居民输送自来水等都是实际需要考虑的问题, 在解决此类问题时,可以将实际问题具体化,首先将总区域建立成一个平面坐标,接 着将居民区简化成坐标,如此,便可将复杂的生活问题化成数学建模问题。本模型正 是研究了一个向六个居民区输水的 A、B 水厂的选址问题,本模型把其定义为双选址问 题,首先对六个居民点,分成两个区域,然后分别求解。为了简单易求,也可以首先 选择重心法,对其求解,但通过对其结果的分析,发现重心法存在着缺点。所以采取 对模型进行重建的方法,列出了一个二元方程,然后对其最小值进行求解。一、问题描述(优
2、化选址问题)某城市拟建 A、B 两个水厂。水厂分小、中、大三种规模,日均贮水量分别为 30 万吨、40 万吨及 50 万吨,A、B 两个水厂日进水量总和不超过 80 万吨。A、B 两个水厂 共同担负供应六个居民区(由表一给出坐标)用水任务,每户日均用水量为 1.0 吨, 水厂供应居民点用水的成本为 1.05 元/吨公里。表表 1 1:各居民区的位置和拥有的家庭户数:各居民区的位置和拥有的家庭户数居民点123456iX012345 位置iY454412家庭户数(万户)1011815822表一问题:若 A、B 两个水厂的位置尚未确定,请确定它们的位置及供水方案使总成本 最低。二、模型假设1.假设水
3、厂与居民点的距离为直线距离,即忽略掉输水管道的路线问题。2.假设水厂与居民点之间的供水费用仅与供水长度有关,和输水量无关。3.假设水厂的建设资金是确定的,不会因规模的大小而改变。成本仅为供水成本。4.假设水厂和居民区都是理性化的质点。15.假设居民的用水量就为人均用水量乘上人口数。而且,长期不变。三、符号表示符号含义Z维护管道所花费的费用(,) (i=1,2,3,4,5,6)iXiY六个居民区的坐标(,) ijXijY654321j21i, 两个水厂向六个居民区的输水量(,) (,)AXBYAXBYA、B 水厂的坐标it各居民区所需的水量id各居民区距离水厂的位置四、问题分析通过简单的分析可以
4、的知,总的用水量为 74 吨,而 A、B 两厂的总进水量为 80 吨, 所以B 两厂的规模只能为(30,50) 、 (40,40) 、 (50,30)三种方式。对于问题一,是典型的线性最优化问题,我们分三种方式对其求解。而对于问题 二,我们则是采用将完全不同的模型:首先,利用聚类算法思想,把六个居民点化分 成为两个区域,然后利用重心选址法初步判断和偏微分法求解地方法,分别对 A、B 两 个水厂的位置进行确定。五、模型的建立与求解1、模型的建立(重心法)这是一个典型的选址问题,由于要选择两个水厂,根据聚类算法的思想,即同一 类对象的相似度较高,而不同类的对象相似度较小的原理,需要将需求点划分成两
5、个 区域。(1)划分区域首先,在坐标纸上描绘出说有的需求区(这里指居民区) ,并把所有需求区,用直 线连接起来,以距离为边做出一个完全图,如图所示:2图一表三然后,根据它们彼此的距离(如表三所示) ,先删除距离最大的边,然后再删除余 下边中距离最大的,依次进行下去,直到图被分为两个彼此分离的图像,如下图所示:图二居民区1 10 02 21.4141.4140 03 32 21.411.410 04 43 32.232.231 10 05 55 55 53.6053.6053.163.160 06 65.385.385 53.6053.6052.8282.8282.2362.2360 03分为两
6、个区域,根据用水量和供水量可知,A 厂与 B 厂的供水量只能为 50 万吨, 三十万吨。然后分别对 A、B 厂进行求解。(2)公式(重心法选址)的推导:假设有 n 个居民点,居民点的坐标为(,) ,水厂的位置为(,),则供iXiY0X0Y水成本为:iniitdAZ 1其中,A 为单位距离的供水成本,为两点间的距离,为供水量。idit按重心法,将各居民区视为有重量的质点,为各质点的等效重量,重心是到各it质点距离最短距离的点,这样,寻求水厂的地址问题,就转化为求重心坐标的问题, 所以接下来就是解决求解重心的问题。假设各个质点的等效质量为 G,根据重心的特征,可知,等效重量在重心对远点的 力矩等于
7、各质点在面上的力矩之和,即:XOY niiiodtGd1由于 X 轴与 Y 轴互相垂直,为不相关变量,所以可以把力矩延着 X 轴、Y 轴分解, 即重心对 X 轴、Y 轴的力矩,等于各质点对 X 轴、Y 轴的力矩之和。那么可以得到: niiioxtGx 1 niiioytGy1又因为 G 为等效质量,所以。 niitG 1总上可得: niiiniitxtx110 niiiniityty110(1)(,)就为所要求解的重心,也就是水厂的最优位置。0X0Y2、模型的求解(Excle 表格)对比重心法,中心坐标的求解,比较简单,所以本论文选择 Excle 表格对其求解,4A、B 两厂的求解数据与过程分
8、别见表四和表五。对于第一块区域(数据如表四所示)居民区一居民区二居民区三居民区四(求和)x 坐标0123 y 坐标4544 分配量(质量)101181544 X*质量011164572 Y*质量40553260187 表四数据带入公式(1) ,可以求出=1.6363, =4.25 。0x0y对于第二个区域(数据如表五所示):居民区五居民区六(求和) x 坐标45 y 坐标12 分配量(质量)82230 X*质量32110142 Y*质量84452数据带入公式(1) ,可以求出=4.73,=1.733 。0x0y3、模型的分析(结果比较)经过分析可以得知,虽然重心法处理问题,比较简单处理的数据比
9、较少,把二元 变量转化为易求的一元变量。但是,结果是否就是最优解呢 ?为了验证这一方法的可行性,我们新建了一个二元方程模型,并对它进行作图、 求解。我们依然根据聚类算法的思想,把区域化作两个区域(详细见上面重心法模型) ,然后,再分开进行求解,对于假设 A 水厂的坐标为(,) ,则对于 A 厂的成本为:AXAY)(Z40Ai iidt 22)()(iAiAiyyxxd同理,对于 B 厂成本为:)(Z21Bi iidt 22)()(iBiBiyyxxd5对于这两个二元函数,我们就是要求解其最小指。本论文,用 matlab 软件,做出了,的分别关于(,) , (,)三维网状图,分别如图三、图四(见
10、AZBZAXAYBXBY附表)所示:图三图四通过,对图标的分析,本论文发现重心法的结果与实际结果有误差。所以,本论 文对重心法重新分析:在重心法中,使用了力矩的概念,在物理学中,力矩是一个矢量,所以,应用矢量方程表示重心和各质点的力矩关系,应该是一个矢 niiiodtGd1量表达式:6iniidtrr 00dG因为,Z 是费用,并非是一个向量表达式,所以:iniidtrr 00dGZ所以, “重心法”因为有矢量运算(不做详细说明),并不是选址的最优选法。4、模型的重建(二元函数最小值)此设计模型,以最低费用为标准,建立一个关于坐标的二元函数:(2))()( Z 2 02 0n0yyxxtii
11、ii即:当 Z 取到最小值时,谁对应的(X,Y)就是要选的水厂位置。所以,问题变成了 求解复杂二元函数的最值,以及所对应的(X,Y)求解。5、模型的二次求解(matlab 求解)此设计使用 matlab 对其求解。由于这是一个比较复杂的二元函数,直接求解要 求解 Z 的高次偏微分,而且使用 matlab 的“fmin 函数”求最值时,软件显示“无法 求解” 。所以,最后本论文采用“迭代法”进行求解,即遍举所有的(,) ,选出他xy 们求出的 Z 最小值,同时,输出他们所对应的(,) 。 (程序如附表二所示)xy程序输出的 z1 为第一个点的最小费用, (a1,b1)为 A 厂的坐标;z2 为第
12、二个 点的最小费用, (a2,b2)为 B 厂的坐标。6、结果分析通过,软件的求解我们得出的最后结果是 A 厂(2,4) ,B 厂(5,1) 。花费的费用 一共为 58.5561。7重心法首先要在坐标系中标出各个地点的位置,目的在于确定各点的相对距离。坐标系可以随便建 立。在国际选址中,经常采用经度和纬度建立坐标。然后,根据各点在坐标系中的横纵坐标值求出 成本运输最低的位置坐标 X 和 Y,重心法使用的公式是: 公式中 Cx- 重心的 x 坐标; Cy- 重心的 y 坐标; Dix-第 i 个地点的 x 坐标; Diy-第 i 个地点的 y 坐标; Vi-运到第 i 个地点或从第 i 个地点运出的货物量。 最后,选择求出的重心点坐标值对应的地点作为要布置设施的地点