钻井布局 徐胜阳陈思多金豪 (武汉汽车工业大学,武汉430070) 指导教师数学建模教练组 编者按本文对前两问的解答采用了正确的穷举算法,得到了正确的结果.对间题三的 解答有特点:第一,给出了一个好用的充分条件;Vi,,D≤e;第二,通过算法给出了求n个 像点的最小外接圆的方法,该圆的半径即可作为判别n个源点是否可用的条件此处反应出 作者们较强的创造性 摘要本文将旧井的利用问题归结为0-1规划问题,由此建立了目标函数提出映射 原理,将旧井的位置映射到一个单位网格中,从而大大地简化了模型的求解,应用映射原理和 穷举方法,求解出有方向约束条件下的可利用点为4个,经过转化,推广到无方向约束条件下 的可利用问题,解得6个点可利用研究了目标成立的充分条件,给出了三种特殊情形下的判 定方法提出了中垂线上的二分通近法 1问题重述(略 文 2符号约定 xoy为绝对坐标系,记为S x1o1y1为题设给定的点所在平面的坐标系,记为S1; x202y2为网格所在平面的坐标系,满足坐标轴与网格上的边平行,坐标原点与网格上 某一结点重合,记为S2 D为P1与P,之间的距离(i≠j;i,j=1,2,…,n) 3模型的建立 旧井要么被利用,要么被舍弃,这便形成了一种0-1规划问题.由此得到目标函数 第i个旧井被利用 =∑2,2=0,第;个旧井被舍弃=1,2,…,n 我们要寻求目标函数的最大值,即=zmx 每个Z,都由同一个激活函数1f确定在给定某种距离D下,D≤c时有激活函数 f(P)=1,否则为0.即有阙值ε.当源点P1与距离最近的结点的距离不大于给定误差e 时,点P被激活可用 由题设,采用向量的p一范数定义距离问题一为‖·‖∞,平面上的c-邻域为边长2e 的正方形域;问题二为‖·‖2,平面上的ε一邻域为半径c的圆域 4模型求解 4.1问题一:有方向约束下的求解问题 引理设有非负实数a,非负整数m,n,则有:(a+m)modl=(a+n)modl(证略)
钻井布局六 453 映射原理给定边长为1单位的正方形网格,以其上某结点为原点建立直角坐标系 S1,令坐标轴与网格纵横边平行,并满足所有点均处于第一象限,根据上述引理,对应坐标 上任意一点P1(x,y1),在矩形区域C=0≤x<1 0≤y3、有唯一的点P(x∵,y”) ri=r mod 1 与之对应把所有旧井的坐标P(以下称为源点)映射到这个矩形区域C yi :- yi mod 1 内,它包含了所有经过映射后的点P:(以下称为像点),我们称区域C为映射区 P映射到P后,相对于包含它的单个网格的相对位置不变,故源点与像点的激活状 态完全相同,即有f(P:)=f(P)问题转化成在映射区中寻找像点P分布最为密集的边 长为2e的正方形区域,该区域内所有像点P所对应的源点P均在c一邻域内可供利用 这种映射算法按一个常数倍数减小了时间复杂度 根据问题一所设,用‖‖定义距离下P的c一邻域,对包含所有像点P的映射区 C作穷举,激活g一邻域内的所有像点,以确定目标函数 在映射区内,按照平移方式穷举,移动步长为s.步长s的选取要权衡复杂度与精度的 问题,以保证在不漏掉可能的最优解的情况下使运算时间最短 边界问题图2中,由粗线围成的区域为映射区,与其内部的细线围成环状区域,其宽 度为e,由旧井方位P1与P2映射而成的两点P1与P2分别分布在映射区两条对边的附 近,与对应边的距离均不超过给定误差,它们可能同时成为可利用点,如果直接用c一邻 域在映射区穷举,则不可能同时容纳这两点.为了不漏掉可能的最优解,下面给出边界问题 解决方法 图1旧井及其映射点的方位 图2边界问题示意图 如图2,网格的右、上两条边附近有区域A,B,C,将这些区域及其上的所有点分别复制 到对应区域A,A,C.为了易于编制程序,将左上角与右下角区域也补齐,形成一个边 长为1+c的扩大的正方形搜索区域,那么原有的点与点之间的关系将全部反映到映射后的 网格上,从而解决了边界问题,得到了完善的算法在计算机上求解得出,在第一象限内,距 原点最近的网格结点,相对于原点的横向偏移为0.4,纵向偏移为0.5,可利用点为第2,4, 5,10点 P