数学模型 水厂选址的最优化问题——图论第四题.doc

承 诺 书我们仔细阅读了南昌大学数学建模竞赛的竞赛规则。我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。报名序号是(没有或不清楚可不填):_.参赛队员(打印并签名) ： 所属院系（请填写完整的全名）： 1._王瑞_签名:_院系: 理学院光信息科学与技术0912._孙圆圆_签名:_院系:理学院光信息科学与技术0913._胡梦宁_签名:_院系: 理学院光信息科学与技术091 日期：2010年4月1日星期四目录一、问题重述（优化选址问题）3二、模型假设3三、符号表示3四、问题分析4五、模型的建立与求解4问题一：4一、模型的建立（线性最优化）4二、模型的求解（lingo）7三、结果分析（三种方案）8问题二：9一、模型的建立（重心法）9二、模型的求解（Excle表格）11三、模型的分析（结果比较）：12四、模型的重建（二元函数最小值）：14五、模型的二次求解（matlab求解）：14六、结果分析：14六、模型的评价与推广15七、附件一16附件二17水厂供水的优化问题摘要：选址是生活中经常遇到的问题，如向居民输送自来水等都是实际需要考虑的问题，在解决此类问题时，可以将实际问题具体化，首先将总区域建立成一个平面坐标，接着将居民区简化成坐标，如此，便可将复杂的生活问题化成数学建模问题。本文正是研究了一个向六个居民区输水的A、B水厂的选址问题，对于问题一，本论文采用线性最优化的思想，对成本在约束函数的条件下，求解其最小值，求解过程使用lingo软件。对于问题二，本论文把其定义为双选址问题，首先对六个居民点，分成两个区域，然后分别求解。为了简单易求，我们首先选择重心法，对其求解，但通过对其结果的分析，我们发现，重心法存在着缺点。所以本论文对模型进行重建，列出了一个二元方程，然后对其最小值进行求解。关键词：最优化，选址， 线性最优化，重心法，二元函数 一、问题重述（优化选址问题）某城市拟建A、B两个水厂。水厂分小、中、大三种规模，日均贮水量分别为30万吨、40万吨及50万吨，A、B两个水厂日进水量总和不超过80万吨。A、B两个水厂共同担负供应六个居民区（由表一给出坐标）用水任务，每户日均用水量为1.0吨，水厂供应居民点用水的成本为1.05元/吨公里。表1：各居民区的位置和拥有的家庭户数居民点123456位置012345454412家庭户数（万户）1011815822表一问题一：若已知A、B两个水厂的位置分别为A=A(1，4)和B=B(4，2)，试确定供水方案使总成本最低；问题二：若A、B两个水厂的位置尚未确定，请你确定它们的位置及供水方案使总成本最低；二、模型假设1.假设水厂与居民点的距离为直线距离，即忽略掉输水管道的路线问题。2.假设水厂与居民点之间的供水费用仅与供水长度有关，和输水量无关。3.假设水厂的建设资金是确定的，不会因规模的大小而改变。成本仅为供水成本。4.假设水厂和居民区都是理性化的质点。5.假设居民的用水量就为人均用水量乘上人口数。而且，长期不变。三、符号表示符号含义维护管道所花费的费用（，）（i=1，2，3，4，5，6）六个居民区的坐标（，） 两个水厂向六个居民区的输水量（，） （，）A、B水厂的坐标各居民区所需的水量各居民区距离水厂的位置四、问题分析通过简单的分析可以的知，总的用水量为74吨，而A、B两厂的总进水量为80吨，所以B两厂的规模只能为（30，50）、（40，40）、（50，30）三种方式。对于问题一，是典型的线性最优化问题，我们分三种方式对其求解。而对于问题二，我们则是采用将完全不同的模型：首先，利用聚类算法思想，把六个居民点化分成为两个区域，然后利用重心选址法初步判断和偏微分法求解地方法，分别对A、B两个水厂的位置进行确定。五、模型的建立与求解问题一：一、模型的建立（线性最优化）将从A、B（i=1，2）两个水厂，向居民区1、2、3、4、5、6（j=1，2，3，4，5，6）送水量分别定义为。即水厂i，向用户区j的供水量为。由乘法原则可得，这里有十二个决策变量分别为、。居民点123456位置012345454412距离A厂11124.424.47距离B厂33.163232.05表二由问题所给出的居民点、水厂的坐标，以及对模型的假设，可以计算出各水厂与各居民点的供水距离。由上面的问题分析，以及模型的假设，可知，要求总的成本（）最低，于是有：Min =1.05*（+ +2+4.42+4.47+3+3.16+3+3+2+2.05） 1、对于第一种情况（水厂的规模为30，50），其约束条件为：居民需求量约束：x11+x21=10；x12+x22=11；x13+x23=8；x14+x24=15；x15+x25=8；x16+x26=22；水厂供水量约束：x11+x12+x13+x14+x15+x16=30；x21+x22+x23+x24+x25+x26=50；2、对于第二种情况（水厂的规模为40，40），其约束条件为：居民需求量约束：x11+x21=10；x12+x22=11；x13+x23=8；x14+x24=15；x15+x25=8；x16+x26=22；水厂供水量约束：x11+x12+x13+x14+x15+x16=30；x21+x22+x23+x24+x25+x26=50；3、对于第三种情况（水厂的规模为50，30），其约束条件为：居民需求量约束：x11+x21=10；x12+x22=11；x13+x23=8；x14+x24=15；x15+x25=8；x16+x26=22；水厂供水量约束：x11+x12+x13+x14+x15+x16=30；x21+x22+x23+x24+x25+x26=50；二、模型的求解（lingo）把所有的约束条件作出线性规划的模型，对 取最优化解，输入lingo求解，求出结果如下：第一种：Global optimal solution found. Objective value: 134.6898 Total solver iterations: 1 Variable Value Reduced Cost X11 10.00000 0.000000 X12 11.00000 0.000000 X13 8.000000 0.000000 X14 0.000000 0.000000 X15 0.000000 1.420000 X16 0.000000 2.412000 X21 0.000000 2.000000 X22 0.000000 2.160000 X23 0.000000 2.000000 X24 15.00000 0.000000 X25 8.000000 0.000000 X26 22.00000 0.000000第二种：Global optimal solution found. Objective value: 134.6898 Total solver iterations: 1 Variable Value Reduced Cost X11 10.00000 0.000000 X12 11.00000 0.000000 X13 8.000000 0.000000 X14 5.000000 0.000000 X15 0.000000 1.420000 X16 0.000000 2.412000 X21 0.000000 2.000000 X22 0.000000 2.160000 X23 0.000000 2.000000 X24 10.00000 0.000000 X25 8.000000 0.000000 X26 22.00000 0.000000第三种：Global optimal solution found. Objective value: 134.6898 Total solver iterations: 0 Variable Value Reduced Cost X11 10.00000 0.000000 X12 11.00000 0.000000 X13 8.000000 0.000000 X14 15.00000 0.000000 X15 0.000000 1.491000 X16 0.000000 2.532600 X21 0.000000 2.100000 X22 0.000000 2.268000 X23 0.000000 2.100000 X24 0.000000 0.000000 X25 8.000000 0.000000 X26 22.00000 0.000000三、结果分析（三种方案）可知三种方案的最低成本是一样的，不同点在于对于第四居民点的供水分配：当水厂的规模为30，50时，全部由B水厂供给；当水厂的规模为40，40时，A厂供给5万吨，B厂供给10万吨；当水厂规模为50，30时，全部由A厂供给。又由于，假设水厂的成本与规模无关，所以以上三种方案都是可行的。方案一：A水厂的规模为30万吨，B水厂的规模为50万吨；居民区1、2、3均由水厂A来供水，居民区4、5、6由B水厂来供水。方案二：A水厂的规模为40万吨，B水厂的规模为40万吨；居民区1、2、3均由水厂A来供水，居民区4，由A（5万吨）、B（10万吨）一起来供水，居民区5、6由水厂B来供水。方案三：A水厂的规模为50万吨，B水厂的规模为30万吨；居民区1、2、3、4均由水厂A来供水，居民区5、6则由B来供水。三种方案的，供水成本均为134.6898万元。问题二：一、模型的建立（重心法）这是一个典型的选址问题，由于要选择两个水厂，根据聚类算法的思想，即同一类对象的相似度较高，而不同类的对象相似度较小的原理，需要将需求点划分成两个区域。1.划分区域：首先，在坐标纸上描绘出说有的需求区（这里指居民区），并把所有需求区，用直线连接起来，以距离为边做出一个完全图，如图所示：图一居民区110221.41403321.4104432.231055553.6053.160665.3853.6052.8282.2360表三然后，根据它们彼此的距离（如表三所示），先删除距离最大的边，然后再删除余下边中距离最大的，依次进行下去，直到图被分为两个彼此分离的图像，如下图所示：图二分为两个区域，根据用水量和供水量可知，A厂与B厂的供水量只能为50万吨，三十万吨。然后分别对A、B厂进行求解。2.公式（重心法选址）的推导：假设有n个居民点，居民点的坐标为（，），水厂的位置为（,）,则供水成本为：其中，A为单位距离的供水成本，为两点间的距离，为供水量。按重心法，将各居民区视为有重量的质点，为各质点的等效重量，重心是到各质点距离最短距离的点，这样，寻求水厂的地址问题，就转化为求重心坐标的问题，所以接下来就是解决求解重心的问题。假设各个质点的等效质量为G，根据重心的特征，可知，等效重量在重心对远点的力矩等于各质点在面上的力矩之和，即：由于X轴与Y轴互相垂直，为不相关变量，所以可以把力矩延着X轴、Y轴分解，即重心对X轴、Y轴的力矩，等于各质点对X轴、Y轴的力矩之和。那么可以得到： 又因为G为等效质量，所以。总上可得： （1）（，）就为所要求解的重心，也就是水厂的最优位置。二、模型的求解（Excle表格）对比重心法，中心坐标的求解，比较简单，所以本论文选择Excle 表格对其求解，A、B两厂的求解数据与过程分别见表四和表五。对于第一块区域（数据如表四所示）：居民区一居民区二居民区三居民区四（求和）x坐标0123y坐标4544分配量（质量）101181544X*质量011164572Y*质量40553260187表四数据带入公式（1），可以求出=1.6363， =4.25 。对于第二个区域（数据如表五所示）：居民区五居民区六（求和）x坐标45y坐标12分配量（质量）82230X*质量32110142Y*质量84452数据带入公式（1），可以求出=4.73，=1.733 。三、模型的分析（结果比较）：经过分析可以得知，虽然重心法处理问题，比较简单处理的数据比较少，把二元变量转化为易求的一元变量。但是，结果是否就是最优解呢 ？为了验证这一方法的可行性，我们新建了一个二元方程模型，并对它进行作图、求解。我们依然根据聚类算法的思想，把区域化作两个区域（详细见上面重心法模型），然后，再分开进行求解，对于假设A水厂的坐标为（，），则对于A厂的成本为： 同理，对于B厂成本为： 对于这两个二元函数，我们就是要求解其最小指。本论文，用matlab 软件，做出了，的分别关于（，），（，）三维网状图，分别如图三、图四（见附表）所示：图三图四通过，对图标的分析，本论文发现重心法的结果与实际结果有误差。所以，本论文对重心法重新分析：在重心法中，使用了力矩的概念，在物理学中，力矩是一个矢量，所以，应用矢量方程表示重心和各质点的力矩关系，应该是一个矢量表达式：因为，Z 是费用，并非是一个向量表达式，所以：所以，“重心法”因为有矢量运算(不做详细说明)，并不是选址的最优选法。四、模型的重建（二元函数最小值）：本论文重建模型，以最低费用为标准，建立一个关于坐标的二元函数： （2）当 Z 取到最小值时，谁对应的（X，Y）就是要选的水厂位置。所以，问题变成了求解复杂二元函数的最值，以及所对应的（X，Y）求解。五、模型的二次求解（matlab求解）：本论文使用 matlab 对其求解。由于这是一个比较复杂的二元函数，直接求解要求解 Z 的高次偏微分，而且使用 matlab 的“fmin函数”求最值时，软件显示“无法求解”。所以，最后本论文采用“迭代法”进行求解，即遍举所有的（，），选出他们求出的 Z 最小值，同时，输出他们所对应的（，）。（程序如附表二所示）程序输出的 z1 为第一个点的最小费用，（a1，b1）为 A 厂的坐标；z2 为第二个点的最小费用，（a2，b2）为 B 厂的坐标。六、结果分析：通过，软件的求解我们得出的最后结果是A厂（2，4），B厂（5，1）。（其具体结果见附表三）花费的费用一共为58.5561.其相对第一个模型的结果，在图上的拟合度更高。六、模型的评价与推广对于第一个问题，线性最优化方法（模型）已经成为解决这一类问题的最佳方法，也是一般的通用的方法。对于第二个问题的第一个模型（重心法选址），由于矢量的关系，其运算结果会有所出入，但是，由于其运算的简单，适用于处理数据数据特别大，而且选址精确不是很高，再配合其他检测、验证模型，也可以得到比较精确的地址。第二个模型（二元函数取极值），是解决选址问题的最根本、最准确的方法，但是鉴于其运算中会出现多元微分求偏微分的问题，所以对于数据较多、较大的选址问题，则是太过复杂，不适宜使用。所以，对于数据大、精确高的选址问题，要寻求更好的方法。还有，对于三个、四个更多的水厂选址问题，也要分成多个区域，依次求解。参考文献：鲁小雪等 双配中心选址方法 物流科技 2010年第二期 p29-33；路晓春等 关于配送中心的重心选址方法的研究 北方交通大学学习报 2000年12月第24卷 第6期 p108-110；姜启源等 数学建模 高等教育出版社 2006年；王强等 高等数学 高等教育出版社 2001年；七、附件一问题一的求解问题（三个文件）：model:min=1.05*(x11+x12+x13+2*x14+4.42*x15+4.47*x16+3*x21+3.16*x22+3*x23+2*x24+3*x25+2.058*x26);x11+x21=10;x12+x22=11;x13+x23=8;x14+x24=15;x15+x25=8;x16+x26=22;x11+x12+x13+x14+x15+x16=30;x21+x22+x23+x24+x25+x26=50;endmodel:min=1.05*(x11+x12+x13+2*x14+4.42*x15+4.47*x16+3*x21+3.16*x22+3*x23+2*x24+3*x25+2.058*x26);x11+x21=10;x12+x22=11;x13+x23=8;x14+x24=15;x15+x25=8;x16+x26=22;x11+x12+x13+x14+x15+x16=40;