数学建模之水厂供水的优化问题

数学建模在实际中的应用水厂供水的优化问题学号姓名专业选址是生活中经常遇到的问题，如向居民输送自来水等都是实际需要考虑的问题，在解决此类问题时，可以将实际问题具体化，首先将总区域建立成一个平面坐标，接着将居民区简化成坐标，如此，便可将复杂的生活问题化成数学建模问题。本模型正是研究了一个向六个居民区输水的A、B水厂的选址问题，本模型把其定义为双选址问题，首先对六个居民点，分成两个区域，然后分别求解。为了简单易求，也可以首先选择重心法，对其求解，但通过对其结果的分析，发现重心法存在着缺点。所以采取对模型进行重建的方法，列出了一个二元方程，然后对其最小值进行求解。一、问题描述（优化选址问题）某城市拟建A、B两个水厂。水厂分小、中、大三种规模，日均贮水量分别为30万吨、40万吨及50万吨，A、B两个水厂日进水量总和不超过80万吨。A、B两个水厂共同担负供应六个居民区（由表一给出坐标）用水任务，每户日均用水量为1.0吨，水厂供应居民点用水的成本为1.05元/吨公里。表1：各居民区的位置和拥有的家庭户数居民点123456位置iX012345iY454412家庭户数（万户）1011815822表一问题：若A、B两个水厂的位置尚未确定，请确定它们的位置及供水方案使总成本最低。二、模型假设1.假设水厂与居民点的距离为直线距离，即忽略掉输水管道的路线问题。2.假设水厂与居民点之间的供水费用仅与供水长度有关，和输水量无关。3.假设水厂的建设资金是确定的，不会因规模的大小而改变。成本仅为供水成本。4.假设水厂和居民区都是理性化的质点。5.假设居民的用水量就为人均用水量乘上人口数。而且，长期不变。1三、符号表示符号含义Z维护管道所花费的费用（iX，iY）（i=1，2，3，4，5，6）六个居民区的坐标（ijX，ijY）654321j21i，，，，，，两个水厂向六个居民区的输水量（‘AX，BY）（AX，BY）A、B水厂的坐标it各居民区所需的水量id各居民区距离水厂的位置四、问题分析通过简单的分析可以的知，总的用水量为74吨，而A、B两厂的总进水量为80吨，所以B两厂的规模只能为（30，50）、（40，40）、（50，30）三种方式。对于问题一，是典型的线性最优化问题，我们分三种方式对其求解。而对于问题二，我们则是采用将完全不同的模型：首先，利用聚类算法思想，把六个居民点化分成为两个区域，然后利用重心选址法初步判断和偏微分法求解地方法，分别对A、B两个水厂的位置进行确定。五、模型的建立与求解1、模型的建立（重心法）这是一个典型的选址问题，由于要选择两个水厂，根据聚类算法的思想，即同一类对象的相似度较高，而不同类的对象相似度较小的原理，需要将需求点划分成两个区域。(1)划分区域首先，在坐标纸上描绘出说有的需求区（这里指居民区），并把所有需求区，用直线连接起来，以距离为边做出一个完全图，如图所示：2图一表三然后，根据它们彼此的距离（如表三所示），先删除距离最大的边，然后再删除余下边中距离最大的，依次进行下去，直到图被分为两个彼此分离的图像，如下图所示：图二分为两个区域，根据用水量和供水量可知，A厂与B厂的供水量只能为50万吨，三居民区110221.41403321.4104432.231055553.6053.160665.3853.6052.8282.23603十万吨。然后分别对A、B厂进行求解。(2)公式（重心法选址）的推导：假设有n个居民点，居民点的坐标为（iX，iY），水厂的位置为（0X,0Y）,则供水成本为：iniitdAZ1其中，A为单位距离的供水成本，id为两点间的距离，it为供水量。按重心法，将各居民区视为有重量的质点，it为各质点的等效重量，重心是到各质点距离最短距离的点，这样，寻求水厂的地址问题，就转化为求重心坐标的问题，所以接下来就是解决求解重心的问题。假设各个质点的等效质量为G，根据重心的特征，可知，等效重量在重心对远点的力矩等于各质点在XOY面上的力矩之和，即：niiiodtGd1由于X轴与Y轴互相垂直，为不相关变量，所以可以把力矩延着X轴、Y轴分解，即重心对X轴、Y轴的力矩，等于各质点对X轴、Y轴的力矩之和。那么可以得到：niiioxtGx1niiioytGy1又因为G为等效质量，所以niitG1。总上可得：niiiniitxtx110niiiniityty110（1）（0X，0Y）就为所要求解的重心，也就是水厂的最优位置。2、模型的求解（Excle表格）对比重心法，中心坐标的求解，比较简单，所以本论文选择Excle表格对其求解，A、B两厂的求解数据与过程分别见表四和表五。4对于第一块区域（数据如表四所示）居民区一居民区二居民区三居民区四∑（求和）x坐标0123y坐标4544分配量（质量）101181544X*质量011164572Y*质量40553260187表四数据带入公式（1），可以求出0x=1.6363，0y=4.25。对于第二个区域（数据如表五所示）：居民区五居民区六∑（求和）x坐标45y坐标12分配量（质量）82230X*质量32110142Y*质量84452数据带入公式（1），可以求出0x=4.73，0y=1.733。3、模型的分析（结果比较）经过分析可以得知，虽然重心法处理问题，比较简单处理的数据比较少，把二元变量转化为易求的一元变量。但是，结果是否就是最优解呢？为了验证这一方法的可行性，我们新建了一个二元方程模型，并对它进行作图、求解。我们依然根据聚类算法的思想，把区域化作两个区域（详细见上面重心法模型），然后，再分开进行求解，对于假设A水厂的坐标为（AX，AY），则对于A厂的成本为：)(Z40Aiiidt22)()(iAiAiyyxxd同理，对于B厂成本为：)(Z21Biiidt22)()(iBiBiyyxxd对于这两个二元函数，我们就是要求解其最小指。本论文，用matlab软件，做出了AZ，BZ的分别关于（AX，AY），（BX，BY）三维网状图，分别如图三、图四（见附5表）所示：图三图四通过，对图标的分析，本论文发现重心法的结果与实际结果有误差。所以，本论文对重心法重新分析：在重心法中，使用了力矩的概念，在物理学中，力矩是一个矢量，所以，应用矢量方程表示重心和各质点的力矩关系，niiiodtGd1应该是一个矢量表达式：iniidt00dG6因为，Z是费用，并非是一个向量表达式，所以：iniidt00dGZ所以，“重心法”因为有矢量运算(不做详细说明)，并不是选址的最优选法。4、模型的重建（二元函数最小值）此设计模型，以最低费用为标准，建立一个关于坐标的二元函数：))()((Z2020n0yyxxtiiii即：（2）当Z取到最小值时，谁对应的（X，Y）就是要选的水厂位置。所以，问题变成了求解复杂二元函数的最值，以及所对应的（X，Y）求解。5、模型的二次求解（matlab求解）此设计使用matlab对其求解。由于这是一个比较复杂的二元函数，直接求解要求解Z的高次偏微分，而且使用matlab的“fmin函数”求最值时，软件显示“无法求解”。所以，最后本论文采用“迭代法”进行求解，即遍举所有的（x，y），选出他们求出的Z最小值，同时，输出他们所对应的（x，y）。（程序如附表二所示）程序输出的z1为第一个点的最小费用，（a1，b1）为A厂的坐标；z2为第二个点的最小费用，（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个地点运出的货物量。最后，选择求出的重心点坐标值对应的地点作为要布置设施的地点