钻井布局模型 陈罡郭成良吴廷彬 (大连理工大学,大连116024) 指导教师教师组 编者按本文根据钻井布局的实际情况,重点研究了在欧氏距离下最大限度地利用初探 时所钻井的问题提出了仅依据旧井的坐标检验旧井是否能全部利用的条件,并提出了两种 检验方法.虽然将所得条件用于寻找最大数量的旧井(问题2)时仍较麻烦,是否还能找到更简 便的办法有待进一步研究,但作者在三天时间内能对该问题作出较深入的分析,得出了关键性 的结果,并给出了较严格的证明,是十分可嘉的 摘要本文的关键思想是找出在变化中的不变量,对于第一小题,作者发现可以把所 有的点“移到”一个方格中,而它们相对网格结点的距离不变,这样问题就得到了大大的简化 对于第二题,本文发现坐标变换时各点之间的欧氏距离不变,利用各点的距离关系,给出一系 列的判定条件,最后用优化算法(充要条件)判定,第二题的算法对于第三题也是通用的,因 此第三题应用第二题的方法来解决 关键词M-N分解;网格坐标系;结点 1问题重叙(略 2问题的条件和假设 (1)在本题中,地形对误差无影响,无需考虑地形这一因素 (2)不需要考虑总井数,利用旧井不会导致总井数的增加,只要考虑尽可能多利用旧 井 (3)给出的旧井均在所定勘探区域内 (4)网格充分大 3符号约定和名词解释 x]取整,等于X的整数部分 在没有说明的情况下代表题设误差,即0.05单位 P 第i口旧井(a;,b1)所在的点 P 第i口旧井平移(m,n)个单位后的点(a;+m,b2+n)(m,n∈z) X代表P附近的网格结点 个边长为2e的只可平移不可转动的正方形 结点(0,0),(0,1),(1,0),(1,1)所围成的一个网格 网格坐标系以某点为坐标原点,以网格纵横方向为x,y轴方向建立的坐标系,并以 题设网格边长为单位长度 矢量的M-N分解若矢量A1A2可表示成A1A2=mi+ni,m,n∈z,i,为互相 垂直的单位向量,则称m,n为A1A2的一组M-N分解
是井布局模型 距离的近似M一N分解两个点PP的距离d满足1d-√m2+n21≤2em,n∈ Z,称m,n为距离d的近似M-N分解,简称近似M-N分解 网格原点设起始时网格坐标系与题设坐标系重合,称这时的坐标原点为网格原点 4问题分析和解答 4.1问题一的分析 根据题意,网格的方向是固定的,对于任意一点P,当网格纵横平移整数个单位时,P 相对于最近的网格结点的距离是不变的,即当P在网格上纵横平移整数个单位时,P相对 于网格结点的距离不变.于是,我们把所有的旧井点都纵横平移整数个单元,使它们都落在 同一网格单元中,此时,各点相对于最近网格结点4y果要 的距离保持不变 如图1-1所示,我们把n个旧井点都移到网0 L1)H个 格W里.在题一的距离意义下,要使尽可能多的 网格结点与旧井点的距离不大于,等价于让尽 可能多的旧井点落在以结点为中心,2e为边长的 正方形内.此时,如果正方形的中心为某种网格的 网格结点,则正方形里面的点都可以利用.这样原 来的问题就转化为用小正方形Q去盖住尽可能多 的点,( 5p0 (1.o)(+,0 4.2问题一解题步骤 基本步骤如下 1.对所有的旧井点进行坐标变换使它们平移到网格W里设原旧井点的坐标为(x y),则新的坐标为(x,y),其中 2.考虑到图1-1中点P2,它位于离网格边界≤e的地方,它的映像点P2可能与Pa, P1同时被正方形Q盖住,如果不作处理,则这种情况可能遗漏因此在实际解题的过程中, 我们把这样的点映射到[1,1+]再进行处理 3.对于网格W中的旧井点,我们先对它们按X,Y坐标进行分组,设 A.=1(x,y)x∈a,a;+2cl,(x,y)∈(a1,b1),(a2,b2),…,(anb,) (i=1,2,…,n) B1={(x,y)y∈[b1,b1+2e],(x,y)∈1(a1,b1),(a2,b2),…,(an,b)H (i=1,2,…,n) 令C=A1∩B(=1,2,…,n=1,2,…,n) 易知任何一个C中所有的点都可以被左下角坐标为(a1,b)的正方形Q同时盖住,同 时这个正方形不能再盖住别的点 4.找出元素数目最多的C,以此再构造一个正方形来盖住这些点.则这个正方形的 中心就是达到盖住最多旧井点的结点.把网格原点移到这个结点,此时的网格N即为所
444 全国大学生数学建模竞赛优秀论文汇编 4.3问题一的结论 按上述步骤编写的程序为 FIRST.CPP.对于所附的数据经过计算机计算后得出结论 为:最大可同时利用四口旧井(编号为4,10,5,2),此时网格原点移到:(0.40,0.55 4.4问题二的分析 由于纵横坐标方向不定,且坐标原点不定,因此直接考虑坐标是不切实际的,但是在坐 标变换的过程中,点和点的距离是不变的 命题2-1两口旧井能同时利用的充要条件是: 存在m,7∈使得Sm+”22(其中SP为旧井P,P之间的距 离,) 证明【必要性】如果P,P能同时利用如图2-1,则存 在两个网格结点X,X满足SPx≤E,SPx≤E 显然存在两个整数m,n使得Sxx PP 整理得59-8x1585x+8x(<2x1 图2-1 五,点 即 √m2+n21≤2e(1) 【充分性】在线段P1P2所在直线上取两点X1,X2(其中X1在P1一侧,X2在P2一侧), 使得1X1X21=√m2+n2且P1,P2的中点与X,X2的中点重合,则 1P1P2|-1X1X2|1P1P2 1P1X1|=1P2X21 又:IX1X21=√m2+n2 n∈z 示坐 显然X1,X2都可在某网格的结点上 点中 中两个旧井能同时利用 证毕 推论2-1n口旧井能同时利用的必要条件是任意两口旧井的距离满足近似M-N 分解 命题2-2三个点x1,x2,X3在某网格坐标系下都是结点的充要条件是向量X1X2 X2X3,X3X1存在M一N分解(m1,n1),(m2,n2),(m3,n3)使得: n;=0 证明【必要性】根据向量的性质知xx+X2x+x3对=0,相应的分量相加即为 (2)式 充分性】设x1x,x2x3,x3对可表示为
钻井布局模型大 445 XIX =m121+n1J1 x2X3=m12+21个边, 设有一网格坐标系(如图2-2),记其x轴,y轴的单位向 量为i,j,在该网格任取一结点Y1,由于m1,m2,n1,n2∈Z, 可找到结点Y2,Y3使Y1Y2=m1+n,y2Y3=m2+n2 图 又YY=Y1Y=-(Y+Y2Y)=-(m1+m2)(n+n2) 及m1+m2+m3=0,n1+n2+n3=0 可知Y3Y1=m313+n3J3 以下证明△Y1Y2Y3与△X1X2X3全等 事实上,根据构造△Y1Y2Y3过程易知△Y1Y2Y3与△X1X2X3对应边长相等,所以 两三角形全等.由于Y1,Y2,Y3在一网格的结点上,所以X1,X2,X3也可以在某网格的结 点上 三点共线时,易证结论成立 证毕 如果三个点的任意一边满足距离的近似M-N分解,而且分出的(m1,n)满足命题2 2的条件,称这三个点构成的三角形为可近似整数分解三角形, 推论2-2若△P1P2P3是可近似整数分解三角形,则存在某网格的三个结点,使得该 三角形的三个顶点分别靠近这些网格结点 证明如图2-3,设P1P2,P1P3,P2P3的近似M-N 分解分别为(m1,n1),(m2,n2),(m3,n3),作一条与P1P2 中点重合,且在P1P2所在直线上,长度为√m12+n2的线 段AB.则易知P1A1<c有P2B1<g.设点C是使得 △ABC为三边分解为(m1,n1),(m2,n2),(m3,n3)的可 整数分解三角形的点.这样可以根据A,B,C建立网格坐 标系,使得A,B,C都是网格结点.又因为△ABC与 △P1P2P3各边的差很小(根据△P1P2P3为近似可整数分 解三角形且其分解和△ABC的分解相同),所以C点和P3点的距离也很小(当然这个距离 可能大于e,但是现在不需要也无法给出一个充分的结论). 回证毕 推论2-3n口井都可同时利用的必要条件是:任意三个点构成的三角形都是近似整 数化三角形, 命题2-3mn个共线的点X1,X2,…,X。都是某网格坐标系的结点的充分必要条件是 它们的一组M-N分解满足 大节个(1 m1+2+m1=0:3,…,n) (3) (其中m,n为XX的一组MN分解,且不妨设当i=方时,m=0,n=0) 证明【充分性】以X1点为原点建立一网格坐标系,旋转该坐标系使X2处在结点
446 全国大学生数学建模竞赛优秀论文汇编 (m12,n12)上(根据M-N分解的定义,易知这是可以实现的).取结点(m1;,n1;),显然这 个点与X1,X2构成的矢量的M-N分解满足(3)式且在X1X2所在的直线上.又因为满足 (3)式的点到X1X2两点的距离确定,所以这个结点就是x 【必要性】如果有n个共线的点X1,X2,…,Xn在网格结点上,显然有(3)式成立 引理若一个点X1到三个不共线三点X2,X3,X4的距离确定,则X1的相对位置唯 证明如果存在不同于X1的点X1使得1X1X(=1X1X1,则点X2,X3,X在线段 X1X1的中垂线上与X2,X3,X4不共线的假设相矛盾 命题2-4设有n个点X(i=1,2,…,n)不共线,且X1,X2,X3为不共线的点,则这 n个点都在某网格坐标系的结点上的充分必要条件是满足 0 Jn12+ n2:+n4=0 (4) 0 n2+n3;+nn2=0的回一 (其中ma,n的意义同命题2-3中m,n) 证明【充分性 1.n=3时即为命题2-2,显然成立 2.设n=k-1时成立,三 3.当n=k时,考虑: m12+m2k+m1=0 0 m23+m3k+mk2=0 n23+n3k+n2=0 根据上一步假设k-1个点时成立,即在某网格坐标G下k-1个点都在某格节点上, 在该网格坐标系G中,作X1X=m1k·i+m1·j(m1=-m1,n1k=-n1,,意义 同前)连接线段x2X,X3X,根据(5)式和矢量的性质可知X2x=m2·i+n2 m3k·i+n3k·J XIXI=l X,X I,I XXI=I X2XE 1, I X2X l=l X2Xr I 又X1,X2,X3不共线 平根据引理可知X4与X4重合,X在网格节点上 1篇∵,n=k时成立个三 【必要性】设X(i=1,2,…,n)在网格坐标系G下都是结点,对X(i≥3)进行分析 当i=3时,设x1x2,X2X3,X3x1在G下的分量分别为(m12,n12),(m2,n23),(m3 n31)根据命题2-2,(4)式前两个等式成立 当i>3时,由于X1,X2,X3,X4都在网格结点上,根据命题2-2可知(4)式前两个等 式和后两个等式分别成立 证毕 易知:命题2-3的条件包含在命题2-4的条件中,所以满足命题2-4的条件自然满 足命题2-3的条件,坐