关于炼油厂的选址问题

第五届太原地区数学建模联赛

承 诺 书

我们仔细阅读了太原地区数学建模联赛的竞赛规则.

我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。

我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。

我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。

我们参赛选择的题号是（从A/B中选择一项填写）： 我们的参赛报名号为： 参赛队员 (打印并签名) ：1. 2. 3.

日期： 2011 年 5 月 15 日

1

-

第五届太原地区数学建模联赛

评阅记录

评阅记录（可供评阅时使用）： 评 阅 人 评 分 备 注 2

-

炼油厂选址问题

摘要

本文对炼油厂选址问题进行了深入研究。

问题一，首先考虑在位置可以随意选择的情况下，并且其距离可为直线，计算出最佳位置，有结果可知，此位置不在任何一油井处，其次，选择距离此最优点距离最近的油井口作为炼油厂选址地点，可知，其余八个油井到炼油厂距离=各油井到最佳位置的距离+最佳距离到最近油井（炼油厂选址）的距离，则问题一可解决。

问题二，考虑两点间距离为直线计算，首先排除产量的干扰，只计算出选择哪个点的情况下此点到各个点的距离之和最小，其次，加入产量的影响，进行加权处理，从而得出最优点，即为炼油厂选择地点。

问题三，应用重心法，首先，计算任意两个油井之间的距离，然后根据相距远近分为两个区域，分别计算两个区域的最优解，炼油厂则选择在这两个最优解处，问题三可解。

本文综合考虑多种方案的因素，所建立的模型结构严谨、逻辑性强。最后并对模型进行了推广。

关键词

最优化，选址， 线性最优化，重心法，二元函数，加权，转化思想，LINGO软件，几何画板

3

-

一、问题的重述（优化选址问题）

基本问题

某一油田在一平坦地区拥有九口油井，各油井的年产量均不同，所有的原油都需要运输到炼油厂进行提炼。不考虑炼油厂的建设费用，总费用仅和炼油厂的位置有关，在不同的情况下讨论炼油厂如何选址得出最优解问题。 需要解决的问题

第一，折线情况下，如何选择折线方案才能达到最优解问题 第二，在炼油厂不被限制的情况下，如何选择炼油厂位置才能到各个点距离最短 第三，建立两个炼油厂的情况下，如何分配两个炼油厂的位置以达到最优解

二、模型假设

1. 假设炼油厂和井口都是理性化的质点。 2. 假设油井输油量单位时间内不变。

3. 假设炼油厂的建设资金是确定的，不会因规模的大小而改变。成本仅为运输费用。

三、符号表示

符号 含义 运输费用 Z （Xi，Yi）（i=1，2，3，4，5，6，7，8，9） 九个油井的坐标 i1，2YX2，3，4，5，6,7,8,9 （ij，ij） j1，‘，YB） （XA，YB） （XA两个炼油厂接受九个油井的输油量 A、B炼油厂的坐标 各油井口所供应的油量 各油井距离炼油厂的距离 单位距离运费 第一个炼油厂 tidi C A 4

-

B 第二个炼油厂 四、问题分析

问题一采用递进方法，先计算直线最优解，然后计算折线最优解，问题二先计算距离最优解，再加权计算最优解，问题三先划分为两个区域，再分别计算两个区域的最优解，得出两个炼油厂的选址地点

五、模型的建立与求解

问题一： 模型的建立

假设炼油厂不一定要选择在某个井口位置，且各井口到最优点之间为直线连接，得出最优点后，再找出距离此点最近的油井口，则炼油厂选择在距离最优点最近的油井口处，其他任意八个油井口到达此油井口折线方案为，先到达最优点处，再由最优点到达炼油厂（距离最优点最近的油井口），即为答案。 模型的解答

首先找出九个点的最优点，使九个点到达最优点的直线距离之和最短 使用LINGO软件： 计算公式为

ZAditii1n

编程程序为： model: sets:

r/1..9/:q; c/1..2/:; link(r,c):d; endsets data: d=22 38 8 13 4 81 51 32 38 11 17 12 81 63 19 45 62 12;

q=17 40 60 20 25 15 50 8 30; enddata

min=@sum(r(i):q(i)*((x-d(i,1))^2+(y-d(i,2))^2)^; end

5

-

其结果为

Local optimal solution found at iteration: 88 Objective value:

Variable Value Reduced Cost X Y Q( 1) Q( 2) Q( 3) Q( 4) Q( 5) Q( 6) Q( 7) Q( 8) Q( 9) D( 1, 1) D( 1, 2) D( 2, 1) D( 2, 2) D( 3, 1) D( 3, 2) D( 4, 1) D( 4, 2) D( 5, 1) D( 5, 2) D( 6, 1) D( 6, 2) D( 7, 1) D( 7, 2) D( 8, 1) D( 8, 2) D( 9, 1) D( 9, 2)

Row Slack or

Surplus

Dual Price 1

6

-

可得出，最优点坐标为X（，），最优点所需费用为

然后计算哪一个油井口与此最优点距离最近，本文使用的几何画板软件使用： 结果如下

（比例尺：1:100000）

可得出一号井距离最优点X距离为，则炼油厂选择在一号井位置为最佳解，即炼

7

-

油厂应选择在一号井处

一号井到最佳点所需运费为：

则其他八个油井从最佳点到一号油井所需运费为：8*=

由此可得出，其余二号到九号油井至炼油厂所需总运费为：Z=+所以，问题一的解答为：

炼油厂选择在一号油井处 所需总运费为

问题二

模型的建立

0x81{炼油厂可选择区域为：0y81所围成的区域内，选择最优点，使各油井

到炼油厂的运费最少 模型的解答

首先算出最短距离的最优解 使用LINGO软件：

S计算公式为

di1niti

编程程序为： model: sets:

r/1..9/:; c/1..2/:; link(r,c):d; endsets data: d=22 38 8 13 4 81 51 32 38 11 17 12 81 63 19 45 62 12; enddata

@bnd(0,x,81); @bnd(0,y,81);

min=@sum(r(i):((x-d(i,1))^2+(y-d(i,2))^2)^; end

8

-

其结果为：

Local optimal solution found at iteration: 60 Objective value:

Variable Value Reduced Cost X Y D( 1, 1) D( 1, 2) D( 2, 1) D( 2, 2) D( 3, 1) D( 3, 2) D( 4, 1) D( 4, 2) D( 5, 1) D( 5, 2) D( 6, 1) D( 6, 2) D( 7, 1) D( 7, 2) D( 8, 1) D( 8, 2) D( 9, 1) D( 9, 2)

Row Slack or Surplus Dual Price 1

9

-

可得出，最优点坐标为X（，），最优点到各油井距离之和为

其次，进行加权处理： 使用LINGO软件： 编程程序为： model: sets:

r/1..9/:q; c/1..2/:; link(r,c):d; endsets data: d=22 38 8 13 4 81 51 32 38 11 17 12 81 63 19 45 62 12;

q=17 40 60 20 25 15 50 8 30; enddata

@bnd(0,x,81); @bnd(0,y,81);

10

-

min=@sum(r(i):q(i)*((x-d(i,1))^2+(y-d(i,2))^2)^; end

其结果为：

Local optimal solution found at iteration: 65 Objective value:

Variable Value Reduced Cost X Y Q( 1) Q( 2) Q( 3) Q( 4) Q( 5) Q( 6) Q( 7) Q( 8) Q( 9) D( 1, 1) D( 1, 2) D( 2, 1) D( 2, 2) D( 3, 1) D( 3, 2) D( 4, 1) D( 4, 2) D( 5, 1) D( 5, 2) D( 6, 1) D( 6, 2) D( 7, 1) D( 7, 2) D( 8, 1) D( 8, 2) D( 9, 1) D( 9, 2)

Row Slack or Surplus Dual Price 1

11

-

可得出，最优点坐标为X（，），最优点所需费用为 所以，炼油厂应选择在（，）处，所需总运费为 问题二解决

问题三

模型的建立（重心法）

这是一个典型的选址问题，由于要选择两个炼油厂，根据聚类算法的思想，即同一类对象的相似度较高，而不同类的对象相似度较小的原理，需要将需求点划分成两个区域。

1.划分区域：

首先，在坐标纸上描绘出所有的油井口，并把所有油井口用直线连接起来，以距离为边做出一个完全图，如图所示：

12

-

图一

井口 1 2 3 4 5 6 7 8 9 1 0 2 0 3 0 4 0 表一

然后，根据它们彼此的距离（如表一所示），先删除距离最大的边，然后再删除余下边中距离最大的，依次进行下去，直到图被分为两个彼此分离的图像，如下图所示：

13

5 0 6 0 7 0 8 0 9 0 -

分为两个区域，然后分别对A、B两炼油厂进行求解。 2.公式（重心法选址）的推导： 假设有n个油井口，油井口的坐标为（则运输成本为：

nXiX0Y0，），炼油厂的位置为（,）,

YiZCditii1

其中，C为单位距离的运输成本，

di为两点间的距离，为产油量。

ti按重心法，将各油井口视为有重量的质点，为各质点的等效重量，重心是

到各质点距离最短距离的点，这样，寻求炼油厂的地址问题，就转化为求重心坐标的问题，所以接下来就是解决求解重心的问题。

假设各个质点的等效质量为G，根据重心的特征，可知，等效重量在重心对

ti14

-

远点的力矩等于各质点在XOY面上的力矩之和，即：

nGdotdii1i

由于X轴与Y轴互相垂直，为不相关变量，所以可以把力矩延着X轴、Y轴分解，即重心对X轴、Y轴的力矩，等于各质点对X轴、Y轴的力矩之和。那么可以得到：

Gxoti1nixi

Gyoti1niyi

G又因为G为等效质量，所以总上可得：

x0tixii1nti1ni。

ti1ni

y0tiyii1nti1ni （1）

（

X0，

Y0）就为所要求解的重心，也就是炼油厂的最优位置。

模型的求解（Excle表格）

对比重心法，中心坐标的求解，本论文选择Excle 表格对其求解，A、B两炼油厂的求解数据与过程分别见表二和表三。

对于第一块区域（数据如表二所示）： 井口 x坐标 y坐标 产量 X*产量 Y*产量 3 4 81 60 240 4860 7 求和 81 63 50 110 4050 4290 3150 8010 x0数据带入公式（1），可以求出=，

y0 =。

对于第二个区域（数据如表三所示）：

井口 x坐标 15

1 22 2 8 4 51 5 38 6 17 8 19 9 求和 62 -

y坐标 38 13 32 11 12 产量 17 40 20 25 15 X*产量 374 320 1020 950 255 Y*产量 646 520 640 275 180 数据带入公式（1），可以求出x0=，

y0 =。

则两个炼油厂选址为：A炼油厂选址坐标为（，） B炼油厂选址坐标为（，）

第一个区域所需费用为： 使用LINGO软件： 编程程序为：

model:

sets:

r/1..2/:q; c/1..2/:; link(r,c):d; endsets data: d=4 81 81 63; q=60 50; enddata

min=@sum(r(i):q(i)*((x-d(i,1))^2+(y-d(i,2))^2)^; end 结果为：

Local optimal solution found at iteration: 233 Objective value:

Variable Value Reduced Cost X Y Q( 1) Q( 2) D( 1, 1) D( 1, 2) D( 2, 1)

16

45 12 8 30 155 152 1860 4931 360 360 2981 -

D( 2, 2)

Row Slack or Surplus Dual Price 1

则第一部分费用为：

第二个区域所需费用为： 使用LINGO软件： 编程程序为： model: sets:

r/1..7/:q; c/1..2/:; link(r,c):d; endsets data: d=22 38 8 13 51 32 38 11

17

-

17 12 19 45 62 12;

q=17 40 20 25 15 8 30; enddata

min=@sum(r(i):q(i)*((x-d(i,1))^2+(y-d(i,2))^2)^; end 结果为：

Local optimal solution found at iteration: 90 Objective value:

Variable Value Reduced Cost X Y Q( 1) Q( 2) Q( 3) Q( 4) Q( 5) Q( 6) Q( 7) D( 1, 1) D( 1, 2) D( 2, 1) D( 2, 2) D( 3, 1) D( 3, 2) D( 4, 1) D( 4, 2) D( 5, 1) D( 5, 2) D( 6, 1) D( 6, 2) D( 7, 1) D( 7, 2)

Row Slack or Surplus Dual Price 1

18

-

则第二部分费用为：

所以，总运费=第一部分运费+第二部分运费=+=

则问题三解答为：A炼油厂选址坐标为（，） B炼油厂选址坐标为（，） 总运费为

六、模型的评价与推广

模型的评价

1）模型的优点

1.采用了较为新颖的解决思路 2.考虑较为全面 3.实用性强 2）模型的不足 1.未考虑地形变化

19

-

2.没有模型对比 模型的推广

对于第一个问题，将折线化为直线求解是这一类题的新思路，题目中使用了两段直线表示了折线，在现实生活中，可是使用折线转化为多段直线的思想解决一些例如铺设管道，修路，铺设线路等相关问题。 对于第二个问题，线性最优化方法（模型）已经成为解决这一类问题的最佳方法，也是一般的通用的方法。

对于第三个问题的重心法选址，由于矢量的关系，其运算结果会有所出入，但是，由于其运算的简单，适用于处理数据数据特别大，而且选址精确不是很高，再配合其他检测、验证模型，也可以得到比较精确的地址。

七、参考文献

【1】何坚勇 运筹学基础 137～173 2008年3月第2版 【2】水厂选址数学建模

作者：

网址：访问时间：2011-5-15

20