钻井布局优化问题原创Word文档格式.docx
《钻井布局优化问题原创Word文档格式.docx》由会员分享，可在线阅读，更多相关《钻井布局优化问题原创Word文档格式.docx（24页珍藏版）》请在冰点文库上搜索。
4：
表示点
按向量（[x]，[y]）移动后的点即（x-[x]，y-[y]），[x]，[y]表示取整；
表示坐标上横纵坐标；
6Z表示0.1单位为边长的正方形；
7ε是已知点Pi与某个网格结点的距离不超过给定误差，且不大于0.05单位；
8：
0-1单位的w网格的结点坐标（
）:
（0，0）（0，1）（1,1）（1,0）;
9:
设点（
）是原旧井的坐标，点（
）是去整后的坐标；
10:
点（
）是点（
）经过坐标旋转后的新坐标；
11：
n是表示可以利用的最多旧井数,（x1,y1）坐标,h是表示可以利用的旧井的编号，
12：
旋转角度为
关键词：
新旧井，打井费用，结点，误差ε，圆，网格，欧氏距离，横纵坐标；
问题重述：
勘探部门在某地区找矿。
初步勘探时期已零散地在若干位置上钻井，取得了地质资料。
进入系统勘探时期后，要在一个区域内按纵横等距的网格点来布置井位，进行“撒网式”全面钻探。
由于钻一口井的费用很高，如果新设计的井位与原有井位重合（或相当接近），便可利用旧井的地质资料，不必打这口新井。
因此，应该尽量利用旧井，少打新井，以节约钻探费用。
比如钻一口新井的费用为500万元，利用旧井资料的费用为10万元，则利用一口旧井就节约费用490万元。
设平面上有n个点
，其坐标为（
i=1,2,…,n，表示已有的n个井位。
新布置的井位是一个正方形网格N的所有结点（所谓“正方形网格”是指每个格子都是正方形的网格；
结点是指纵线和横线的交叉点）。
假定每个格子的边长（井位的纵横间距）都是1单位（比如100米）。
整个网格是可以在平面上任意移动的。
若一个已知点
与某个网格结点
的距离不超过给定误差ε（=0.05单位），则认为
处的旧井资料可以利用，不必在结点
处打新井。
为进行辅助决策，勘探部门要求我们研究如下问题：
1）假定网格的横向和纵向是固定的（比如东西向和南北向），并规定两点间的距离为其横向距离（横坐标之差绝对值）及纵向距离（纵坐标之差绝对值）的最大值。
在平面上平行移动网格N，使可利用的旧井数尽可能大。
试提供数值计算方法，并对下面的数值例子用计算机进行计算。
2）在欧氏距离的误差意义下，考虑网格的横向和纵向不固定（可以旋转）的情形，给出算法及计算结果。
3）如果有n口旧井，给出判定这些井均可利用的条件和算法（你可以任意选定一种距离）。
数值例子n=12个点的坐标如下表所示（i=1,2,…,n，）：
=[0.50，1.41，3.00，3.37，3.40，4.72，4.72，5.43，7.57，8.36，8.98，9.50]
=[2.00，3.50，1.50，3.51，5.50，2.00，6.24，4.10，2.01，4.05，3.41，0.80]
问题一的分析：
由于钻探一个新井呀比利用一个旧井多花490万，所以在钻探新井时要尽可能多的利用原来的旧井。
根据题意，把所有井视为坐标上的点，于是问题可以简化为：
网格的方向是固定的,对于任意一点
，当网格纵横平移整数个单位时，
相对于最近的网格结点的距离是不变的,即当
在网格上纵横平移整数个单位至
时，
相对同一网格的距离不变,于是，我们把所有的旧井点都纵横平移整数个单元,使他们都落在同一网格单元W中,此时，各点相对于最近网格结点的距离保持不变。
所讨论的问题就可以简化为用一个边长为0.1的正方形去覆盖移动的点，也就让正方形去尽可能的多覆盖点。
定一个变量，按移动向量进行移动。
移动后的去整点：
=x-[x]；
=y-[y]。
如图1所示：
问题一的模型建立与解答：
如图2所示,我们把12个旧井点都移到0-1的W网格坐标内。
假设网格固定。
由于新井分布在网格的结点上。
根据题目的定义,两点间的距离取横向距离（横坐标之差绝对值）及纵向距离（纵坐标之差绝对值）的最大值，误差范围不大于0.05个单位长度。
只要旧井点被这个正方形覆盖，我们就认为这个旧井点可以利用，即让尽可能多的旧井点落在以结点为中心，２ε为边长的正方形内。
这样，原问题就转化为用小正方形Q去盖住尽可能多的点。
如图所示：
所有的旧井点进行坐标变换使它们平移到网格W里.
由假设可知：
原来旧井点坐标（x，y），移动后的点去整坐标（
）
=x-[x]；
即：
将原来的旧井点坐标减去取整的旧井点坐标得到新的点坐标
问题可以简化为：
当找到旧井与新井在误差允许的范围重合的最大数，再构造一个正方形来盖住这些点，则此正方形的中心即为达到盖住最多旧井点的结点（为避免考虑边界条件，我们同时考虑正方形四个顶点与旧井点的距离差达到最小，即每移动一次正方形就计算一次各个顶点与旧井点的位置关系），把网格原点移到这个结点，此时的网格N即为所求。
利用matlab，建立数组对所有点的坐标进行编号。
最后我们再将点平移回去找出原来旧井点的坐标位置。
原12个旧井点中可利用的旧井点坐标位置如图所示：
问题一的结论
按上述的方法可以知道最大多四口旧井可同时利用，它们的编号分别为2,4,5,10；
在问题的打井要求下合理规划钻井方案示意图如图所示
这里我们也可以采用直接考虑边界条件做：
将移动后的旧井点的横纵坐标分别与x=0，x=1，y=0，y=1作比较，看他们之间的距离，如图2所示可以明显看到有四个点是可以利用的旧井点，只要横纵坐标中有大于0.9个单位的减去1，若不大于0.9就保持不变，且还有可能有个别横纵坐标大于0.9的点仍然可用，将所有的点再进行移动，再用一个边长为0.1的正方形去覆盖移动的点，覆盖移动的点最多时，也就是利用旧井数最多，现在我们要的就是把点的编号找出来，建立数组对所有点的坐标进行编号，最后我们再将点平移回去找出原来旧井点的坐标位置。
问题二的分析：
在欧氏距离的误差意义下，考虑网格的横向和纵向不固定（可以旋转）的情形，由于在坐标变换的过程中,点和点的距离是不变的。
所以我们可以从两点间的距离不变入手；
找到一个网格坐标系，使旧井点中能同时与结点（欧氏距离）≤ε的点尽可能多。
问题二的模型建立与解答：
由于要考虑旋转问题，问题一中的模型对问题二不再适用了，也无法用手工算出方案结果。
根据提给条件，在欧氏距离的意义下，网格上结点的有效范围是以此结点为圆心，0.05个单位为半径的圆。
我们可以固定网格坐标，采用旋转旧井点后再去整平移，再用上述我们所说的圆去覆盖旧井点的方法，直接搜索能够同时落在有效范围内的点数，找出圆覆盖旧井点数最多时的圆心位置及旧井点的坐标。
设旋转角度为
；
考虑到网格是正方形，即
在0-pi/2取值，在这个角度范围不断旋转，最终得到一个旋转角度使得同时使利用旧井数达到最多；
将问题一中的坐标旋转一定角度后得到一个新的坐标后,利用坐标变换公式，可得原来的点在新的坐标系中的坐标。
除距离的定义变换外,类同于题一的做法，对每一个α都能得到相应可利用的最大点数．至于网格相对于原坐标的位移量,对点的纵横坐标取最大值即可；
如图3所示,我们把12个旧井点都移到0-1的W网格坐标内。
方法一：
直接考虑边界条件，12旧井点旋转以后再去整后，我们可以图中明显看到有六个点是可以利用的旧井点，只要横纵坐标中有大于0.9个单位的减去1，若不大于0.9就保持不变，且还有可能有个别横纵坐标大于0.9的点仍然可用。
坐标变换的过程中,点和点的距离是不变的，将所有的点再进行移动，用两点间的距离不大于2ε（即0.1个单位）。
方法二：
不直接考虑边界条件，同时考虑12个旧井点与四个结点（类似于有四个中心）的位置关系，任意移动一个中心（结点）坐标一次，就分别计算出这个以及其他三个中心（结点）坐标与12个旧井点的位置关系，找出达到盖住最多旧井点的结点位置。
问题最终可以简化为用一个以0.05个单位的圆去尽可能覆盖多去整以后的点，也就是寻找能够覆盖最多点的中心位置的坐标；
同时把此时圆中点的编号找出来，事先建立数组对所有点的坐标进行编号；
最后我们再将点平移旋转回去找出原来旧井点的坐标位置。
问题二的结论：
按上述的方法一可以得出最多有6口旧井可同时利用，它们的编号分别为1、6、7、8、9、11；
0.05为半径的圆中心（网格的网格结点）坐标为：
（-0.1000、0.7400）（类似于坐标（0.900、0.7400））；
为45.0000时利用旧井数达到最多
按上述的方法二可以得出最多有6口旧井可同时利用，它们的编号分别为1、6、7、8、9、11；
0.05为半径的圆中心（网格的四个网格结点）坐标为：
（0.9100，0.7800），（0.9100，1.7800），（1.9100，0.7800），（1.9100，1.7800）；
为45.0345时利用旧井数达到最多
两种方法结果一致,在问题二的打井要求下合理规划钻井方案示意图如图所示
问题三模型的建立与求解：
假设
为
旋转角度，[X]表示取整。
为第i口旧井（
，
）所在的点坐标；
为第i口旧井旋转角度
后点所在的坐标（
）。
问题三其实是问题二的推广，同样需要采用坐标旋转。
我们可以采用类似于问题二的方法对问题三建立相对合理的模型进行求解。
坐标旋转一定角度后得到一个新的坐标后,利用坐标变换公式，可得原来的旧井点在新的坐标系中的坐标：
映射到单位正方形上所在点的坐标（
），有如下关系式：
边界处理：
若
则
若
：
利用旧井时，新井与旧井的最大误差。
1、棋盘距离：
所有旧井均可利用的充分条件是：
当
经过旋转及映射后到
中所有的像点必须落在一个边长为为
的正方形内（此正方形制作平移不旋转）
判据：
对于
中所有的点，如果存在两点的横坐标或纵坐标距离大于
时，则n口旧井不能同时被利用，此两点不可能同时在边长为
的正方形中。
反之，则可以同时存在于边长为
正方形的中心的搜索：
对于点
（
）：
令
（不妨设
则中心坐标的横坐标为
纵坐标
边长为d的正方形是包含n个井点的最小正方形。
所以：
若
时，所有的像点能被全部利用；
若
时，所有的像点不能被全部利用。
结论：
有上述的推理我们可以得到一定理：
2、欧氏距离：
当所有源点旋转角度（0/2）形成一映射区（称为-映射区）后，所有像点必须落在一个半径R的圆内，即=n.并且Dij2。
我们称其为误差圆.对于完全利用问题，可用如下判据作优先判断：
判据一：
在-映射区内，若存在两点的距离Dij>
2，则n口旧井不能同时利用，因为相距Dij>
2的两点不可能同时在一个误差圆内
判据二：
若-映射区内任意两点距离Dij满足Dij
，则有=n，即这个n像点能被全部包含在误差圆内，这时n口旧井能全部利用
判据三：
任意连接三个像点成三角形，若成锐角或直角三角形，则其外接圆是能将三个顶点完全包围的最小圆；
若成钝角三角形，则以钝角的对变为直径作的圆为能将三个顶点完全包围的所有圆中的最小圆.当最小圆半径R>
时，则n。
这就是说如果存在三个点不能同时在一个误差圆中，这时n口旧井就一定不能同时被利用。
为了在映射区中找到能覆盖全部像点的最小圆域，做包含个n像点的凸m（mn）边形，作其直径PQ的中垂线交多边形于S,T，从PQ与ST的交点O出发，在中垂线上搜索所求圆的圆心，步骤如下：
1.取点O为圆心，R=|OP|=|OQ|为半径作圆；
2.找出其余m-2个像点到O点的最长距离D。
若D>
R，则使圆心Oi朝Ri 增大而Di减小的方向（向外）移至SO的中点，继续步骤3；
若DR，则R即为所求最小圆的半径，结束；
（下标i代表迭代运算的次数,i=1,2,…）
3.找出其余m-2个像点到Oi的最长距离Di，若Di>
Ri（Ri=POi），则使圆Oi+1心向Ri增大的方向移动，移至Di与其向外方向邻接点的中点处；
若DiRi，则使圆心Oi+1向Ri减小的方向（向内）移动，移至Oi与其向内方向邻接点的中点处；
若Di=Ri，则Ri即为所求最小圆的半径，结束；
4.重复步骤3的工作，直到|Di-Ri|（为任意给定的充分小的正实数）为止，此时Ri即为所求最小圆的半径,若Ri，则能覆盖全部像点，所有像点能全部利用，否则若Ri>
，不能完全利用
若n口井能被全部利用，则圆Q内一定有n个点，且一个源点在圆Q内只对应一个象点；
证明：
因n口井可以被全部利用，则有０≤Dij≤２ε，处于边界区的每个源点对应圆Q内一个象点，而任一个源点所对应的两个或三个象点只能有一个在圆Q内．得证；
这样,边界问题的考虑不会影响问题的实质,即井点个数及可利用井点的编号不变。
定理：
平面上n个点可以被一个半径为的圆域所覆盖，当且仅当如下二条件成立：
（i）任意两点距离2；
（ii）任意形成锐角三角形的三点的外接圆半径。
证明：
必要性显然.充分性实质上是证明这样一个对偶命题：
包含n个点的圆域半径的最小值等于任意“三点确定的圆域”的半径的最大值，这里，所谓三点确定的圆域是指包含它们的最小圆域，即当三点构成锐角三角形时，它就是外接圆，否则就是一斜边为直径的圆，我们把其中以两点连线为直径的圆给第一类圆，锐角三角形的外接圆成为第二类圆，这些圆的半径最大值r．现在作覆盖n个给定点的最小圆域，设其圆周为C，半径为R。
由覆盖性知Rr。
由最小性知，C上至少有两个给定点。
若恰有两个点，则C为第一类圆，从而Rr，下设C上的给定点为P1,P2,…,Pt（t3）.在C上取出包含这t个点的最小圆弧A。
分如下情形：
（a） 若A小于半圆，则可以过A的两端点作出半径小于R的圆域包含n个给定点，与C的最小性矛盾。
（b） 若A恰为半圆，则C是以A的两个端点连线为直径的圆，即第一类圆，故Rr。
（c） 若A大于半圆，则在P1,P2,…,Pt中可找到三点构成锐角三角形，从而C是第二类圆，故Rr。
综上得到R=r。
证毕
模型推广与评价：
问题三就是问题一、二的推广，该问题也可以应用到各种搜救活动时人员的调配（就近原则，减少在路程上花费的时间），最大程度（及时）的援救更多需要援救的人和物。
本模型的优点重要是在解决实际问题可以减少相应的（钻井）成本，缺点是在实际情况下无法达到那种精确的程度。
参考文献：
[1]未知作者中国数据在线
http:
//www.chinadataonline.org/member/yearbook/default.asp?
StartYear=1984&
EndYear=2005>
2007.9.21.
[2]王宏健全国大学生数学建模竞赛优秀论文汇编 2007
[3]谢剑，赵彤<
<
Excel在建筑工程中的应用：
快速计算工具实例<
天津大学出版社2004
[4]作者：
姜启源数学模型[M]北京：
高等教育出版社2005
[5]作者：
王沫然，书名：
MATLAB与科学计算，出版地：
电子工业出版社，出版年：
2003年9月第二版；
[6]、作者：
南昌大学数学建模研究室编，书名：
教学软件简介与应用，起止页码：
1-95，出版年：
2005年3月；
[7]作者：
萧树铁、姜启源、张立平、何青、高立，书名：
大学数学，出版地：
高等教育出版社，出版年：
2006年5月第二版；
[8]作者：
甘筱青,《数学建模教育及竞赛》,江西:
江西高教出版社，2004年6月第1版
[编号]作者，论文名，杂志名，卷期号：
起止页码，出版年。
附录：
问题一程序：
ai=[0.501.413.003.373.404.724.725.437.578.388.989.50];
bi=[2.003.501.503.515.502.006.244.102.014.503.410.80];
a=ai-floor（ai）;
b=bi-floor（bi）;
x1=[0,0,1,1];
y1=[0,1,0,1];
c=y1;
n=0;
fori=0:
0.001:
0.5
x1=x1+i;
y1=c;
forj=0:
y1=y1+j;
n1=0;
p1=[];
fork=1:
12
form=1:
4
ifabs（a（k）-x1（m））<
=0.05&
abs（b（k）-y1（m））<
=0.05
n1=n1+1;
p1=[p1,k];
end
ifn1>
n
n=n1;
p=p1;
x=x1;
y=y1;
end
n,p,x,y
%原旧井坐标与可利用旧井坐标示意图程序：
p=[24510];
x=[0.37800.37801.37801.3780];
y=[0.46501.46500.46501.4650];
pj=[ai;
bi];
i=1;
pi=[];
whilei<
=length（p）
pi=[pi,pj（:
p（i））];
i=i+1;
ci=pi（1,:
）;
di=pi（2,:
plot（ai,bi,'
b*'
holdon
plot（ci,di,'
rp'
gridon
title（'
原旧井坐标与可利用旧井坐标示意图'
gtext（'
p2'
p4'
p5'
p10'
%问题一合理规划钻井方案示意图程序：
kp'
X2=0:
ceil（max（ai））;
Y2=0:
ceil（max（bi））;
[x2,y2]=meshgrid（X2,Y2）;
x2=x2+x
（1）;
y2=y2+y
（1）;
plot（x2,y2,'
r.'
xlabel（'
x'
ylabel（'
y'
问题一：
合理规划钻井方案示意图'
问题二程序：
%考虑边界问题程序：
ai=[0.51.413.003.373.404.724.725.437.578.388.989.50];
h=0;
forafa1=0:
0.01*pi:
pi/2
n2=0;
a=ai*cos（afa1）-bi*sin（afa1）;
b=ai*sin（afa1）+bi*cos（afa1）;
fori=1:
ifa（i）-floor（a（i））>
0.9
a（i）=a（i）-floor（a（i））-1;
elsea（i）=a（i）-floor（a（i））;
ifb（i）-floor（b（i））>
b（i）=b（i）-floor（b（i））-1;
elseb（i）=b（i）-floor（b（i））;
fore=-0.1:
0.01:
1
forf=-0.1:
n1=0;
if（a（k）-e）^2+（b（k）-f）^2<
=0.0025
升级会员 