钻井布局优化问题【原创】

钻井问题摘要：在当今高速发达的经济社会中，无论是国家还是团体、个人都时时刻刻考虑经济问题，都希望做到少花钱多办事，以后为自己创造更多的利益。本题是钻井优化问题，题给打一个新井要500万、旧井10万，所以问题就是钻化如何更多的利用旧井以减少钻井的成本，这样的话我们就必须寻求一个中间变量，对我们所要讨论的问题进行简化，问题一要讨论是在一定的区域中，如何合理安排正方形网格式打井，使旧井设备得到充分利用。根据抽屉原理，得出平移旧井点后，在给定的误差范围内旧井与新井结点重合的条件，让尽可能多的旧井点落在以结点为中心，２ε为边长的正方形内。此时，如果正方形的中心为某种网格的网格结点，则正方形里面的点都可以利用。这样，原问题就转化为用小正方形Z去盖住尽可能多的点。可以知道最多四口旧井可同时利用，它们的编号分别为2,4,5,10；网格的网格结点坐标为：（0.3780，0.4650）；问题二在旧井点可以旋转的过程中，在欧氏距离的意义下，网格上结点的有效范围是以此结点为圆心，0.05个单位为半径的圆。固定网格坐标，可以直接考虑边界问题采用旋转旧井点后再去整平移，再用上述我们所说的圆去覆盖旧井点的方法，直接搜索能够同时落在有效范围内的点数，也可以不直接考虑边界问题，也就是同时考虑12个旧井点与四个结点（类似于有四个中心）的位置关系，任意移动一个中心（结点）坐标一次，就分别计算出这个以及其他三个中心（结点）坐标与12个旧井点的位置关系，找出圆覆盖旧井点数最多时的圆心位置及旧井点的坐标。两种方法可以得出基本相同的结果。可以知道最多有6口旧井可同时利用，它们的编号分别为1、6、7、8、9、11；当旋转角为45.0000°时利用旧井数达到最多。问题三n个旧井点同时利用的情况。平面n个井点都在一个边长为2的正方形内（及边界），当且仅当任意两点的横、纵坐标距离（最大值）小于等于2（最小值），则这平面n个井点可以同时被利用。假设与条件：1：网格充分大，勘测区域全部被网格覆盖；2：原来给出的旧井均在在现在的勘测区域内；3：无论旧井是否利用，都对总的钻探井数没有影响，即总井数不变；4：钻井的过程中只要考虑尽可能多的利用旧井；5：地面连续，不出现间断，可以视为一个起伏不大的曲面或是平面，地形对误差无影响，无需考虑地形因素；符号的解释与说明：1：用w表示0-1的网格；2：N表示正方形网格；3：ip表示点（x，y）4：'ip表示点ip按向量（[x]，[y]）移动后的点即（x-[x]，y-[y]），[x]，[y]表示取整；5：'',,,jijixyxy表示坐标上横纵坐标；6Z表示0.1单位为边长的正方形；7ε是已知点Pi与某个网格结点的距离不超过给定误差，且不大于0.05单位；8：0-1单位的w网格的结点坐标('',jixy):（0，0）（0，1）（1,1）(1,0);9:设点(,jiab)是原旧井的坐标，点（,ab）是去整后的坐标；10:点（,XY）是点（,xy）经过坐标旋转后的新坐标；11：n是表示可以利用的最多旧井数,（x1,y1）坐标,h是表示可以利用的旧井的编号，12：旋转角度为关键词：新旧井，打井费用，结点，误差ε，圆，网格，欧氏距离，横纵坐标；问题重述：勘探部门在某地区找矿。初步勘探时期已零散地在若干位置上钻井，取得了地质资料。进入系统勘探时期后，要在一个区域内按纵横等距的网格点来布置井位，进行“撒网式”全面钻探。由于钻一口井的费用很高，如果新设计的井位与原有井位重合（或相当接近），便可利用旧井的地质资料，不必打这口新井。因此，应该尽量利用旧井，少打新井，以节约钻探费用。比如钻一口新井的费用为500万元，利用旧井资料的费用为10万元，则利用一口旧井就节约费用490万元。设平面上有n个点ip，其坐标为(ia,ib,i=1,2,…,n，表示已有的n个井位。新布置的井位是一个正方形网格N的所有结点（所谓“正方形网格”是指每个格子都是正方形的网格；结点是指纵线和横线的交叉点）。假定每个格子的边长（井位的纵横间距）都是1单位（比如100米）。整个网格是可以在平面上任意移动的。若一个已知点ip与某个网格结点ix的距离不超过给定误差ε（=0.05单位），则认为ip处的旧井资料可以利用，不必在结点ix处打新井。为进行辅助决策，勘探部门要求我们研究如下问题：1)假定网格的横向和纵向是固定的（比如东西向和南北向），并规定两点间的距离为其横向距离（横坐标之差绝对值）及纵向距离（纵坐标之差绝对值）的最大值。在平面上平行移动网格N，使可利用的旧井数尽可能大。试提供数值计算方法，并对下面的数值例子用计算机进行计算。2)在欧氏距离的误差意义下，考虑网格的横向和纵向不固定（可以旋转）的情形，给出算法及计算结果。3)如果有n口旧井，给出判定这些井均可利用的条件和算法（你可以任意选定一种距离）。数值例子n=12个点的坐标如下表所示（i=1,2,…,n，）：ia=[0.50，1.41，3.00，3.37，3.40，4.72，4.72，5.43，7.57，8.36，8.98，9.50]ib=[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万，所以在钻探新井时要尽可能多的利用原来的旧井。根据题意，把所有井视为坐标上的点，于是问题可以简化为：网格的方向是固定的,对于任意一点ip，当网格纵横平移整数个单位时，ip相对于最近的网格结点的距离是不变的,即当ip在网格上纵横平移整数个单位至'ip时，ip相对同一网格的距离不变,于是，我们把所有的旧井点都纵横平移整数个单元,使他们都落在同一网格单元W中,此时，各点相对于最近网格结点的距离保持不变。所讨论的问题就可以简化为用一个边长为0.1的正方形去覆盖移动的点，也就让正方形去尽可能的多覆盖点。定一个变量，按移动向量进行移动。移动后的去整点：'x=x-[x]；'y=y-[y]。如图1所示：问题一的模型建立与解答：如图2所示,我们把12个旧井点都移到0-1的W网格坐标内。假设网格固定。由于新井分布在网格的结点上。根据题目的定义,两点间的距离取横向距离（横坐标之差绝对值）及纵向距离（纵坐标之差绝对值）的最大值，误差范围不大于0.05个单位长度。只要旧井点被这个正方形覆盖，我们就认为这个旧井点可以利用，即让尽可能多的旧井点落在以结点为中心，２ε为边长的正方形内。此时，如果正方形的中心为某种网格的网格结点，则正方形里面的点都可以利用。这样，原问题就转化为用小正方形Q去盖住尽可能多的点。如图所示：所有的旧井点进行坐标变换使它们平移到网格W里.由假设可知：原来旧井点坐标（x，y），移动后的点去整坐标(,jixy)'x=x-[x]；'y=y-[y]。即：将原来的旧井点坐标减去取整的旧井点坐标得到新的点坐标问题可以简化为：当找到旧井与新井在误差允许的范围重合的最大数，再构造一个正方形来盖住这些点，则此正方形的中心即为达到盖住最多旧井点的结点（为避免考虑边界条件，我们同时考虑正方形四个顶点与旧井点的距离差达到最小，即每移动一次正方形就计算一次各个顶点与旧井点的位置关系），把网格原点移到这个结点，此时的网格N即为所求。利用matlab，建立数组对所有点的坐标进行编号。最后我们再将点平移回去找出原来旧井点的坐标位置。原12个旧井点中可利用的旧井点坐标位置如图所示：问题一的结论按上述的方法可以知道最大多四口旧井可同时利用，它们的编号分别为2,4,5,10；网格的网格结点坐标为：（0.3780，0.4650）；在问题的打井要求下合理规划钻井方案示意图如图所示这里我们也可以采用直接考虑边界条件做：将移动后的旧井点的横纵坐标分别与x=0，x=1，y=0，y=1作比较，看他们之间的距离，如图2所示可以明显看到有四个点是可以利用的旧井点，只要横纵坐标中有大于0.9个单位的减去1，若不大于0.9就保持不变，且还有可能有个别横纵坐标大于0.9的点仍然可用，将所有的点再进行移动，再用一个边长为0.1的正方形去覆盖移动的点，覆盖移动的点最多时，也就是利用旧井数最多，现在我们要的就是把点的编号找出来，建立数组对所有点的坐标进行编号，最后我们再将点平移回去找出原来旧井点的坐标位置。问题二的分析：在欧氏距离的误差意义下，考虑网格的横向和纵向不固定（可以旋转）的情形，由于在坐标变换的过程中,点和点的距离是不变的。所以我们可以从两点间的距离不变入手；找到一个网格坐标系，使旧井点中能同时与结点(欧氏距离)≤ε的点尽可能多。问题二的模型建立与解答：由于要考虑旋转问题，问题一中的模型对问题二不再适用了，也无法用手工算出方案结果。根据提给条件，在欧氏距离的意义下，网格上结点的有效范围是以此结点为圆心，0.05个单位为半径的圆。我们可以固定网格坐标，采用旋转旧井点后再去整平移，再用上述我们所说的圆去覆盖旧井点的方法，直接搜索能够同时落在有效范围内的点数，找出圆覆盖旧井点数最多时的圆心位置及旧井点的坐标。设旋转角度为；考虑到网格是正方形，即在0-pi/2取值，在这个角度范围不断旋转，最终得到一个旋转角度使得同时使利用旧井数达到最多；将问题一中的坐标旋转一定角度后得到一个新的坐标后,利用坐标变换公式，可得原来的点在新的坐标系中的坐标。cossinsincosXxyYxy除距离的定义变换外,类同于题一的做法，对每一个α都能得到相应可利用的最大点数．至于网格相对于原坐标的位移量,对点的纵横坐标取最大值即可；如图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时利用旧井数达到最多两种方法结果一致,在问题二的打井要求下合理规划钻井方案示意图如图所示问题三模型的建立与求解：假设为ip旋转角度，[X]表示取整。ip为第i口旧井（ia，bi）所在的点坐标；'ip为第i口旧井旋转角度后点所在的坐标（'ia，'bi）。问题三其实是问题二的推广，同样需要采用坐标旋转。我们可以采用类似于问题二的方法对问题三建立相对合理的模型进行求解。坐标旋转一定角度后得到一个新的坐标后,利用坐标变换公式，可得原来的旧井点在新的坐标系中的坐标：''bbbcossinsincosiiiiiiaaaiQ映射到单位正方形上所在点的坐标（iA，Bi），有如下关系式：''''bb[][]iiiiiiaaAB边界处理：若0.8iA则1iiAA