全国大学生《数学建模》竞赛：1999B

钻井布局模型 陈罡郭成良吴廷彬 (大连理工大学,大连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的条件,坐

钻井布局 推论2-4如果n个旧井点的相互连线PP(i=1,2,…,n;=1,2,…,n)的近似 N分解m,na满足命题2-4中(4)式,那么这n个旧井点可以通过坐标变换分别靠近 某网格的n个结点(不一定小于) 根据命题2-3和推论2-2容易得到结论 命题2-5n口井P(a1,b)都可利用充分必要条件是以下两式有公共解 (x1-x1)2+(y-y1)2=m12+n12 (x1-x2)2+(y-y2)2=ma2+n2(i=2,3,…,n) (6) y-y3)2 b1)2≤ 1,2,…,n) (其中:m;,n为PP的一种近似M-N分解且满足命题2-4,当i=j时,记m=0,n 0,且所有的不全等时,总是设"12≠m1). 证明【充分性】设(6)式有解,表示存在一系列点X(x1,y)(i=1,2,…,n),使得1 xX|=√m2+n2,所以X式存在一种M-N分解为(m,n).又因为m,n满足命 题2-4中的(4)式,根据命题2-4的充分条件(m全等时表明x共线,由于mn满足 (4)式显然也满足(3)式,由命题2-3的充分条件)可知X(=1,2,…,n)都在某网格坐标 系的结点上,而(7)式说明PX≤ε,(i=1,2,…,n),即P1(i=1,2,…,n)都可以利 用 【必要性】n口井都利用即表示在某网格坐标系(不妨设为G)下1PX1≤(x1( )为该网格上的结点),则X(x;,y)满足(7)式,又因为X是G上的结点,设X区在坐 标G下的分量为m,n,显然ma,n满足(6)式 必要条件成立 证毕 4.5问题二的解答步骤 步骤1建立一张12口井之间的距离互相关系表.如下表所示,当两口旧井之间的距 离满足近似的M-N分解时,记录下能进行所有可能的近似M-N分解,如果旧井点P, P可以进行近似M-N分解就在第i行列记下PP的近似M-N分解的可能数目,如果 P4,P不能进行近似MN分解则记为0.通过对绝对值小于两点之间的距离的所有整数 进行穷举,求出所有可能的m,n,把它们存入数组,以供以后使用.(下面是根据原题所附 数据得出的结果) 2#0 3#0 4#1 5#1 6# 7#1 8#?121 9#3

448 全国大学生数学建模竞赛优秀论文汇编 示10#131131210 11#21114111110 122.0小1)0个0 1#2#3#4#5#6#7#8#9#10#11# 步骤2根据推论2-1,找出系列集合,使得集合中间任意两点之间的距离都可以进行 近似M-N分解(通过步骤1给出的表判定),算法程序为子程序 Conduct,为了加快运算, 用子程序band去掉重复的集合 步骤3根据命题2-2,在上述集合中,进一步判断,找出任意三个点都可构成近似整 数分解三角形的集合 步骤4对步骤3判断的结果进一步判断.对其中的任何一个集合,判断这k个点的近 似M-N分解是否可能满足命题2-4条件,如果不可能,则该集合不满足条件,如果可能 则输出该集合和相应的M-N分解值.这样可以得到可能的结果为:(只打出4个元素以上 的集合) ,许(别世 444446 9 的一 11的 7(8 真解就是在这些集合中 以上4步由程序 PREDUCT.CPP, SECOND.CPP完成 步骤5对输出集合进行顺序调整,当k个点都在同一直线上(即 )任取三点X,X2,x3否则,不妨设有不共线的三点x1,X2,X3,然后把(6)式转化为 f(x1,x2…,x,y,y2…,y)=√(a1÷x1)2+(b1=y1)2处 g(x1,x2,…,xk,y1,y2,…,yk),h(x1,x2,…,x,y1,y2,,y)为向量函数,其分量为 g:1(x1,x2,…,x1,y1,y2…,y)=√(a1-x1)2+(b1-y)2e )2+(y1-y)2-(m12+m12) h43=(x1-x2)2+( y2)2-(m2+n2)润 (x1-x3)2+(y1-y3)2-(m132+n32) 考虑如下规划模型 g1(x1,…,x,y……,y)≤0 h;( 显然该规划模型与命题2-5中(6)(7)式是等价的,又因为命题2-5是一个充分必要 条件,所以:当minf(x1,…,x,y1,,y)≤0时表示存在X(x,y)满足(6)式,即n口井

钻井布局模型 449 都可以利用.当minf(x1,…,xk,y1,…,)>0时,n口井不可能被同时利用 采用 MATLAB作为优化工具,用 constr函数进行优化,逐步判断所有集合中所含元素 最多的子集和集合本身,通过运算得出满足条件的集合为:1,6,7,8,9,111.根据返回的 X(x,y)的M-N分解值建立网格坐标系将12个旧井点的坐标进行转换,得到如附图 所示的结果,在这个网格中,6个点到它们各自附近整点的距离最大值为:S9=0.049<c 四4.6问题三的分析和解法 长半个一示中 显然,问题二的解法是一个通用算法,对于问题三同样适用.综合问题二的命题和推 论得出以下算法:(本题在欧氏距离意义下讨论) 1.根据推论2-1:n个点能同时利用必需满足对任意两点P,P,存在(m,m)使得 P 2根据推论2-3:n个点能同时利用必须满足任意三点P,P,P的任意一边满足近 似M-N分解,而且分出的(m;,n1)满足命题2-2中式(2) 3.根据推论2-4:如果n个旧井点的相互连线PP(i-1,2,…,n;=1,2,…,n)的 近似M-N分解ma,n满足命题2-4中(4),那么这n个旧井点可以通过坐标变换靠近n 个网格结点(不一定小于E) 在通过这三步的判断后我们提出两种方法来作最后的判断 带不 方法一根据命题2-5:n口井能同时利用的充分必要条件是在满足上述三个条件的 前提下,满足命题2-5中的不等式(7).依次判断给定的n个点是否满足上面分析中的4个 条件,如果其中一步不满足,则表明不能同时利用,如果全部满足,则表示这n个点可以同 时利用、具体步骤参考问题二 方法二根据前面的计算得出的可能网格坐标系结点,算出这些结点在该网格坐标系 下的坐标为X(c,d1),则把这些结点作坐标变换 8 sino\ci Ar 即 sing cos0/{d+△ 可得 =f(6,△x,△y)=cos0(c;+△x)+sin0(d1+△y) =f(0,4x,4y)=-sin(c;+△x)+cos0(d1+△y) 又根据命题3-3(见后面所附命题),要使得n个点能同时被利用,至少要保证任何 个点P附近存在n层重叠区域S,,根据S1的构造方法易知判断S的存在性等价于判断下 面的不等式组是否有解: x)2+(b. √(a;-x;)2+(b1-y)2≤Sn+ (9) )2+(b-y)2≥S (其中j=1.2…1,+1…,n;Sn=)2+(x-y2)把(8)式代入不等式 组(9)并整理即可得一组关于(0,△x,△y)的不等式组 f(0,4x,4)2+((0,△x,4y)2≤c ,(a4-1(0,△,4)+(+k(O,△,4yD/e(10

450 全国大学生数学建模竞赛优秀论文汇编 对所有的x解这样的不等式组就可得出结论.由于时间的关系,我们没有给出方法二 的具体程序,但是因为方法二是一个比较初等的方法,因此可以很容易的构造出它的具体解 法和程序 出场,本合原动的 4.7问题三的附加命题 一 命题3-1设有任意两点P1,P2和某网格两结点x1,x2,=1x1x2,以P1点为圆 环中心,作一个半径为R=5+E,r=5-e的圆环,再以P2点为圆心作一个半径为e的圆 设圆环和圆的重叠区域为S2,同理对称地在P1点附近求得一个重叠区域S1那么满足 1X1P1|≤e,|X2P2l≤c的充要条件是:存在X1∈S1,X2∈S2 证明【充分性】如果X1∈S1,X2∈S2,命题显然成立 【必要性】(先不妨设s≤1P1P21,则圆环与圆的重叠区域必然如图3-1所示)假设, 不妨设X2∈S2(S2为P2圆内除去S2的部分)连接X1P1,X1X2,X2P1三条线段,根据 三角形的性质有:1X1P1+1x1X21≥1x2P1 的出且长不 的(又显然X2在圆环外侧,所以1X2P1>R5+E个 X2121X2P1X1P1>s+7=5 即1X1X21>1X1X21,产生矛盾 假设不成立 来式再出自三发近 x2∈S2,同理X1∈S1 当5>P1P2时,证法与此类似,应用三角形三边的关系即可得证,因此略去 命题3-2在命题3-1的基础上考虑三个点P1,P2,P3的情形,如图3-2.取其重复 三层覆盖的区域为S1,S2,S3,这样要使1X1P1≤e,|X2P2≤,lX3P3≤c的充要 条件是:存在X1∈S1,X2∈S2,X3∈S3·周 St X- 图3 证明【充分性】易知 论,【必要性】例如对点P1,根据命题3-1,如果x1∈S1,则X1,X3不能同时满足条件, 果X1∈S1,则X1,X2不能同时满足条件 01)命题3-3类似地可以对n个点的情形进行证明,取其n层重叠区域为S1,S2,…,S 要使得1XP1≤e,(i=1,2,…,n).如果某一个点P附近不存在n层重叠区域,即S

钻井布局模型 451 ∈O,则x∈O,这样的x不存在,即这n个点不可能同时有某网格的n个结点使得 XP1|≤c·如果存在,且能找到某网格的n个结点X1,X2,…,Kn使得X∈S,则这m 个点能满足同时利用的条件 5算法分析 (1)在第二题的解法中,我们给出了一个通用的解法,不仅能判断n个旧井点是否可以 同时利用,而且在不能同时利用时给出了能同时利用旧井点的最大数 (2)算法采用逐层筛选,不存在误差.最后的多变量求极值时,根据命题四的分析,我 们知道n个点都靠近网格结点,因此误差很小 (3)通过必要条件的层层筛选,不仅优化步骤提供了M-N分解值,是必不可少的 步.而且使后来的优化处理的数据范围小,大大减少了优化的次数 (4)在第三题的解法中,我们给出了两种不同的解法,这两种解法的区别在于第二种解 法需要的仅仅是求关于三个变量的n2个不等式是否有解,可以用穷举的办法来解决,不需 要用优化方法来解题 参考文献 [1周承高,廖园.《优化方法及应用程序设计).中国铁道出版社,1989 MATLAB语言》.中国科技大学出版社,1995.11 昌,曾文艺.《数学模型与数学建模》北京师范大学出版社,1997,8 数学的发展关系到整个科学技术的发展而科学技术是第一生产力;所以数学的发 展是一件国家大事。 钱学森,发展我国的数学科学一在中国数学会召开的数学教育与科研座谈会上的讲话 《数学进展》,1990,19(2):129-135 干大不离照总的的振离国,:3因0比