钻井布局摘要本文将网格移动和旋转问题转换为旧井点坐标的平移和旋转，对每一问题，先将旧井点坐标变换到单位格子中，这样分别将问题一、问题二转化为在单位格子中移动边长为2ε的正方形和半径为ε的圆，使落入正方形或圆中（包括边界）的点数最多。

对于问题三，依然采用一、二问的坐标变换思想，将n 个井点坐标旋转、平移到单位格子中，则n 个井点均可利用的条件就是寻找半径最小的圆（在欧式距离下），使之包含全部的井点。

问题一：按上述思想进行坐标平移后，假设正方形中心坐标(,)x y ，建立了非线性规划模型。

为了方便数值计算，在分析题目所给数据后，以0.01为步长，将x,y 在区间[0,1]上量化，运用穷举法，用matlab 编程，对每一组(,)x y ，计算每个井点到中心(,)x y 的距离，判断其是否落入正方形内或边上，计算出落入正方形内和边上的井点数121i i f =∑。

然后比较，求出最大的121ii f =∑及相应的(,)x y 。

计算的结果是，最大可利用旧井点数为4个，此时(),x y 有多组，其中一组为（0.36,0.46），且可利用的4个旧井都是2,4,5,10号井。

问题二：先按照坐标旋转公式对坐标进行旋转，然后平移到单位格子中。

用类似问题一的解法，设圆心坐标为(,)x y ，也建立了非线性规划模型。

在分析数据的基础上，将旋转角度θ以0.001为步长在区间0,2π⎡⎤⎢⎥⎣⎦上量化，x,y 的量化方法和第一问相同，对每一组(,,)x y θ，计算每个井点到圆心(,)x y 的距离，判断是否落入圆内或圆上，求出落入的井点数。

然后比较，求出落入圆内或圆上的最大井点数及相应的(,,)x y θ。

计算结果是，在可旋转条件下，距离采用欧式距离时，最大可利用旧井点数为6个，此时对应的(,,)x y θ有多组，其中一组为（0.775,0.770,0.120），并且可利用的旧井均为1、6、7、8、9、11号这六口井。

问题三：对n 口旧井，求让其全部能被利用得条件，由问题一、二的求解，我们发现对一个固定的ε，其可利用的最大旧井数是一定的。

所以必定存在一个最小的ε，使n 口旧井恰能都被利用。

我们选用欧式距离，在网格可旋转的情况下，讨论了最小ε的求法，这样在给定误差ε时，只要比较它和最小误差的大小，若大于，则可全部利用。

本文重点论述了，已知n 个井点坐标，在将其旋转、平移至单位格子中后，求包含所有点的最小圆的方法。

即依据三点确定一个圆，计算其包含的点数，这样遍历3n c 次，比较找出包含n 个点的最小圆。

本文还考虑了单位格子边界上的点有等价点的情况，对这些等价点也要进行遍历判断问题重述勘探部门在某地区找矿。

初步勘探时期已零散地在若干位置上钻井，取得了地质资料。

进入系统勘探时期后，要在一个区域内按纵横等距的网格点来布置井位，进行“撒网式”全面钻探。

由于钻一口井的费用很高，如果新设计的井位与原有井位重合（或相当接近），便可利用旧井的地质资料，不必打这口新井。

因此，应该尽量利用旧井，少打新井，以节约钻探费用。

比如钻一口新井的费用为 500 万元，利用旧井资料的费用为 10 万元，则利用一口旧井就节约费用 490 万元。

设平面上有n 个点i P ，其坐标为,()i i a b ,i=1,2,3···,n,表示已有的n 个井位。

新布置的井位是一个正方形网格N 的所有结点（所谓“正方形网格”是指每个格子都是正方形的网格；结 点是指纵线和横线的交叉点）。

假定每个格子的边长（井位的纵横间距）都是1单位（比如100米）。

整个网格是可以在平面上任意移动的。

若一个已知点i P 与某个网格结点i X 的距 离不超过给定误差ε（=0.05单位），则认为i P 处的旧井资料可以利用，不必在结点i X 处打新井。

为进行辅助决策，勘探部门要求我们研究如下问题： 1)假定网格的横向和纵向是固定的（比如东西向和南北向），并规定两点间的距离为其横向距离（横坐标之差绝对值）及纵向距离（纵坐标之差绝对值）的最大值。

在平面上平行移动网格N ，使可利用的旧井数尽可能大。

试提供数值计算方法，并对下面的数值例子用计算机进行计算。

2)在欧氏距离的误差意义下，考虑网格的横向和纵向不固定（可以旋转）的情形，给出算法及计算结果。

3)如果有n 口旧井，给出判定这些井均可利用的条件和算法（你可以任意选定一种距离）。

基本模型假设1. 忽略地理因素，假设旧井和新井在同一平面内。

2. 假设正方形网N 格充分地大，使矿区为N 的一部分，方便问题的讨论，不影响问题的实质。

3. 假定一个网格点附近不可能出现两口旧井，即两口旧井之间的距离至少为（情形1中的距离）或2ε（欧式距离）。

4. 假定网格的横向和纵向不固定（可以旋转）的情况视为网格N 的整体旋转。

符号说明ε：旧井点可利用条件时与网格点距离的最大值，也叫误差。

i P ：第i 个旧井点。

(,)i i a b ：第i 个旧井点的原始坐标。

''(,)i i a b ：对第i 个旧井点原始坐标仅进行平移变换后的坐标。

''''(,)i i a b ：对第i 个旧井点原始坐标先进行旋转变换，然后进行平移变换后的坐标。

(,)x y ： 表示正方形中心坐标（第一中距离下）或圆心坐标（欧式距离下）。

θ： 旋转角度。

[]x : 取整，即取不大于x 的最大整数。

： 取绝对值。

i f ： 标志变量，为1表示第i 个井点在正方形内、边上或圆内、边上。

max(): 取最大值。

： 逻辑表达式，若内部表达式为真返回1，否则返回0。

mod()：取余函数。

sgn(): 符号函数。

问题分析1. 由于网格移动或旋转同固定坐标系而对每个坐标进行移动或旋转是等价的，因此，我们采用对井点坐标进行变换。

2. 对给定的ε，要使井点平移后可利用的旧井点数尽可能多，就是要使移动后的旧井点落在以格子点为中心的ε闭邻域（正方形或圆形）中的数目达到最大，由此可以抛弃井点的实际坐标值，而只考虑井点和格子点的相对位置，因此，首先将所有井点坐标变换到[][]0,10,1⨯的单位格子中去，对每个井点i P ,()i i a b 做如下变换：（1）{''sgn()[]sgn()[]i i i i i i i i a a a a b b b b =-=-1,2,3,,i n =•••其中sgn()x 表示符号函数，[]x 表示不超过x 的最大整数。

3. 对井点坐标变换之后，问题（1）转化为在单位格子中移动以2ε为边长的正方形，使得旧井点()'',i i a b 落在该正方形中的数目达到最大，即求此时正方形的中心坐标。

4. 问题（2）考虑网格可旋转的情况，等价为先对坐标进行旋转，然后归一化到单位格子中。

这样问题（2）转化为在单位格子中移动以ε为半径的圆，使得旧井点()'''',i i a b 落在该圆中的数目达到最大，即求此时圆的圆心坐标。

5. 问题（3）针对更为一般情况，要求让n 口旧井均可利用的条件，我们依然用处理问题1、2的坐标转化思想和方法，该问题转化为求ε至少为多少才能让所有点都落入对应正方形或圆形。

模型建立与求解一、 对问题1的求解 1.1问题分析由于网格移动同固定坐标系而对每个坐标进行移动是等价的，为了便于问题的分析，对井点坐标进行变换。

按照第一种两点间距离的定义，对给定的ε，要使井点平移后可利用的旧井点数尽可能多，就是要使移动后的旧井点落在以格子点为中心的边长为2ε的正方形中的数目达到最大，由此可以抛弃井点的实际坐标值，而只考虑井点和格子点的相对位置，因此，首先将所有井点坐标,()i i a b 变换到 [][]0,10,1⨯的单位格子中去，得转化后坐标()'',i i a b 。

这样，问题转化为在单位格子中移动以2ε为边长的正方形，使得旧井点()'',i i a b 落在该正方形中或边上的数目达到最大，即求此时正方形的中心坐标。

1.2 模型建立由于题目中的坐标值均为正值，所以将井点坐标等价转换到[][]0,10,1⨯单位格子中的坐标转换公式为：（2）[][]{''i i i i i i a a a b b b =-=-设边长为2ε的正方形中心坐标为(),x y ，01x ≤≤，01y ≤≤，则对任一井点，它与正方形中心的距离为''max(,)i i a x b y --，则任一井点在正方形内部或边上的充要条件是：''max(,)i i a x b y --<=ε （*）对任一井点i P ，设一变量i f ,当满足上述条件，i f =1，否则i f =0。

因此建立非线性规划模型： 121ii MAXf=∑}{''0101.0,1max(,)i ii i x y s t f f a x b y ε≤≤⎧⎪≤≤⎪⎨∈⎪⎪=--≤⎩其中表示条件成立，结果为1，否则为0.在该非线性规划中，由于题中12个井点坐标值精确到为小数点后两位，故以0.01为间距将,x y 离散化，这样在单位格子中取10000个(),x y ，运用穷举法，对每一个(),x y 计算满足条件（*）的井点个数121ii f=∑，找出使121ii f=∑最大的(),x y 。

1.3 模型求解运用上述坐标转换公式，求得转换后的坐标()'',i i a b 如下表：表 ,()i i a b →()'',i i a bMAX(121ii f=∑)=4,即可利用的旧井数最大为4个，此时(),x y 有多组，满足：0.360.42,0.460.55x y ≤≤≤≤，其中一组为（0.36,0.46），且可利用的4个旧井都是2,4,5,10号井。

二、 对问题二的求解 2.1问题分析在网格可旋转情形下，等价为坐标的旋转，然后按照问题一的方法平移到单位格子中去。

这样，在欧式距离下，把问题转换为在单位格子中移动半径为ε的圆，使得落入圆内或圆上的井点数最多。

2.2模型建立●坐标旋转如右图，对任一点(),a b ，设其与X 轴的夹角为ϕ，到原点的距离为r ，则cos ,sin a r b r ϕϕ==。

设坐标系旋转一个角度θ，设新坐标系下该点坐标为()'',a b ，则()()''cos cos cos sin sin sin sin cos cos sin a r r r b r r ϕθϕθϕθϕθϕθϕθ=-=+=-=-得到新坐标与旧坐标的关系：''cos sin cos sin a a b b b a θθθθ=+=-●坐标平移由于进行坐标旋转后，有些坐标值会变为负值，所以要用原始坐标变换公式（1）将所有坐标平移到单位格子中。