钻井布局问题的数学模型摘要勘探部门在某地区找矿时，首先进行初步勘探，取几个位置钻井，取得地质资料；然后进行系统勘探，进行纵横等距的撒网式钻井。
显然假如能尽可能多的在系统勘探时利用初步勘探的钻井资料，就能有效的节约费用。
在不考虑网格方向的情况下，本文首先给出了两个结论，即网格的位置由节点唯一确定，与原始矿井节点以及单位方格内的矿井映射点有相同的性质。
如此就将问题等效为在单位方格内确定网格的一个节点。
要解决那个问题，首先我们提出运用一般的搜索法对网格节点在单位方格内进行遍历（模型一）。
通过对遍历算法进行有效的优化，大量减少了搜索的次数，进而初步计算得到了原井位最多有4个可被利用，并给出了方格节点的坐标为：Z ∈++i i i i Y X Y X , )50.0,40.0(考虑到搜索算法的复杂度，我们给出了模型二，即在单位方格内通过确定每个矿井映射节点被利用时节点的区域，来找出方格内被这些区域覆盖次数最高的部分，显然假如将节点放在这部分内，将会有最多的点被利用，从而也就确定了节点的位置范围。
运用MATLAB 进行计算与判不，得到最多有4个可被利用，并求出了网格节点坐标具体的范围：Z ∈∈∈++i i Y ,X )51.0,41.0(),47.0,37.0( 其中 ),s (t s Y t X i i当网格方向能够改变时，我们建立了模型三。
考虑到判不条件是欧氏距离，能够将原题简化为一个圆形进行覆盖，圆的半径为ε，再用类比利用模型二进行推断，那么就能相应的找到最优规划。
模型三首先进行了误差分析，依照假设的误差使用夹逼法则，然后，为了减小搜索范围，我们证明了时，最多有6个矿井可被利用。
关于第三问的判定算法，我们仍然依照模型三，建立假设模型四。
构造出两个极端情况，现在所有矿井均可被利用。
具体算法的见问题三分析步骤。
最后我们对模型四的一个假设进行了检验。
尽管那个假设严格的讲并不成立，但通过我们用蒙特卡罗方法进行多次模拟，发觉假设成立的概率极高。
综上，我们能够先用模型四进行计算，再对结果进行检验，对极少数不成立的，能够综合专门情况进行考虑。
关键词勘探矿井遍历算法蒙特卡罗数值分析误差分析假设检验一．问题重述勘探部门在某地区找矿。
初步勘探时期已零散地在若干位置上钻井，取得了地质资料。
进入系统勘探时期后，要在一个区域内按纵横等距的网格点来布置井位，进行“撒网式”全面钻探。
由于钻一口井的费用专门高，假如新设计的井位与原有井位重合（或相当接近），便可利用旧井的地质资料，不必打这口新井。
因此，应该尽量利用旧井，少打新井，以节约钻探费用。
比如，钻一口新井的费用为500万元，利用旧井资料的费用为10万元，则利用一口旧井就节约费用490万元。
设平面上有n个点P i，其坐标为(a i,b i),i=1,2,…,n，表示已有的n个井位。
新布置的井位是一个正方形网格N的所有结点（所谓“正方形网格”是指每个格子差不多上正方形的网格；结点是指纵线和横线的交叉点）。
假定每个格子的边长（井位的纵横间距）差不多上1单位（比如100米）。
整个网格是能够在平面上任意移动的。
若一个已知点P i与某个网格结点X i的距离不超过给定误差 （＝0.05单位），则认为P i处的旧井资料能够利用，不必在结点X i 处打新井。
为进行辅助决策，勘探部门要求我们研究如下问题：1)假定网格的横向和纵向是固定的（比如东西向和南北向），并规定两点间的距离为其横向距离（横坐标之差绝对值）及纵向距离（纵坐标之差绝对值）的最大值。
在平面上平行移动网格N，使可利用的旧井数尽可能大。
试提供数值计算方法，并对下面的数值例子用计算机进行计算。
2)在欧氏距离的误差意义下，考虑网格的横向和纵向不固定（能够旋转）的情形，给出算法及计算结果。
3)假如有n口旧井，给出判定这些井均可利用的条件和算法（你能够任意选定一种距离）。
n=12个点的坐标如下表所示：二．符号讲明(原始勘测中任意一点将旧井移至单位正方形里面时候的新井f 可利用的最大钻井数n 正方形的候选位置的数目旧井离新表格节点的距离Q（s,t）网格的一个节点推断旧井节点是否在表格范围内的标志位a,b等原始节点需要转化至单位正方形内部时候需要移动的整数大小。
三．模型假设1. 初步勘探时，所取的点比较分散，不存在两个点的资料被系统勘探时同一个点利用的情况。
2. 系统勘探所取的点数比初步勘探时取的点多。
3. 初步勘探所取的点在系统勘探的勘探范围之内。
4. 假定每个格子的边长（井位的纵横间距）差不多上1单位（比如100米）。
整个网格是能够在平面上任意移动的。
5. 若一个已知点P i与某个网格结点X i的距离不超过给定误差ε（=0.05单位），则认为P i处的旧井资料能够利用，不必在结点X i处打新井。
四．问题的分析及讲明考虑到勘探部门在某地区找矿时是分为两步进行的，即：第一步，初步勘探，取得地质资料。
第二步，系统勘探，进行“撒网式”全面钻探。
那么，为了节约钻探费用，我们自然希望充分利用第一步的数据，来减少勘探次数。
对实际问题进行分析，能够认为初步勘探时钻井的位置可对应与二维坐标系中的点，成为初始点。
系统勘探时的全面钻探可认为是二维坐标系中横坐标与纵坐标间距相等的点为节点所构成的网格。
如此，问题的实质就转化为如何定位网格，使尽可能多的初始点位于网格节点的误差范围内。
为了更好的表述问题，下面给出两条结论：结论一：假定网格的横向和纵向是固定的，那么只要确定其中一个节点，就可确定整个网格。
证明：专门显然，当网格节点中的一个点的坐标)s,(t 确定时，其他点的坐标可由如下公式确定：Z ∈++i i i y y t x s ,x ),(i结论二：关于坐标系里的每一个点),(i i b a ，能够定义其映射点⎣⎦⎣⎦),(i i i i b b a a --，映射点与原来的点对网格有相同的位置关系。
证明：⎣⎦i a 意为对i a 向下取整。
由于网格横向和纵向的单位差不多上1，因此当点),(i i b a 位于网格中一个节点),s (t 的误差范围内时，则其映射点必定位于⎣⎦⎣⎦),(i i i i b b a a --的误差范围内。
反之假如点),a (i i b 不在任何一个节点的误差范围内，那么映射点也不在任何一个节点的误差范围内。
五． 模型的建立模型一遍历法考虑差不多给定点（矿井）以及网格的横向与纵向固定，那么问题就变为如何确定出网格的最优平移位置。
由结论一，定出网格的位置只要确定出一个节点，同时，由于网格以1为单位，那么在单位方格内，必定有且只有一个节点，如此我们在0,0(四个点所构成的方块（单位方格）内对节点进行搜索，)0,1(),1,1(),1,0(),就能将网格的全部可能的平移情况进行遍历。
考虑到题目中所给数据精确到0.01，那么可取0.01为两个坐标的步长进行搜索。
关于搜索到的每一个坐标，作为网格的节点，来确定整个网格，再计算到底有多少初始点能进入网格节点的误差范围，最后进行比较，选出容纳初始点最多的网格作为解决方案。
搜索法从理论上是可行的，然而这种方法的计算量往往比较大。
如上例，要搜索的节点个数为（即循环次数）：100×100＝10000（次）而每一次循环都要对12个点依次进行推断，这必定十分复杂，当实际的数据量比较大，数据精度要求比较高时，这种直接搜索的方法计算起来就十分耗时，甚至是不可行的。
为了减少循环次数，必须想方法对算法进行优化。
那个地点我们考虑关于每一个初始点，由结论二，首先在单位方格内找到该点的映射点，如此就将所有点都映射到了单位方格内。
然后进行搜索，在映射点附近搜索网格节点，使映射点位于网格节点的误差范围内，再对节点构成的网格进行分析、比较，选出其中的最优。
通过如此的过程，循环的次数为：11×11×12＝1452（次）如此就大大减少了循环次数，优化了搜索算法，使之耗时短，使方案变得可行。
运用优化后的搜索算法，对所给数据进行计算，得到最多能够有4口井不必打而能够利用初步勘探的资料。
能够利用的初始点为： (1.41,3.50) (3.37,3.51) (3.40,5.50) (8.38,4.50)网格坐标为：Z ∈++i i i i y x y , )47.0,x 37.0(模型二 框图分析法考虑到遍历节点法怎么讲是一种复杂度极高的算法，当数据量大的时候就会有严峻缺陷，因此那个地点给出一种简单易行而又十分精确的算法：方框图分析法。
首先，依照定理二，确定出初始点在单位方格内的坐标（即映射点），变换前后点的坐标如下：表1：坐标映射表 n1 2 3 4 5 6 7 8 9 10 11点2.003.50 1.50 3.51 5.50 2.00 6.244.10 2.01 4.50 3.41变换点0.50 0.41 0.00 0.37 0.40 0.72 0.72 0.43 0.57 0.38 0.980.00 0.50 0.50 0.51 0.50 0.00 0.24 0.10 0.01 0.50 0.41 使用matlab软件将变换前的点画在一坐标系下，如图1：点图：1同时将映射之后的点画于一个坐标系下面得到如图2：映射点图：2将所有的旧井节点平移至单位正方形能够得到Q=｛（x,y）|0<=x<=1,0<=y<=1｝即（）--->在上述变换后，问题1大致等价于用一个变长为2 的正方形去覆盖尽可能多的,正方形的中心确实是网格的一个节点所在位置。
如图-3所示：观看可得，正方形有个候选位置。
若正方形左边通过，右边通过，则ԑ【, 】,ԑ【】代入数据得：ԑ【,】,ԑ【】（1）依照上表1可知：=。