数学建模竞赛课件钻井布局.ppt

暑 期 培 训,数 学 建 模 竞 赛,(1999)钻井布局,因此，应该尽量利用旧井，少打新井，以 节约钻探费用。 比如:钻一口新井的费用为500万元 设平面上有n个点Pi，其坐标为（ai ,bi） i= 1，2，,n,表示已有的个井位。 新布置的井位是一个正方形网格N的所有 结点（所谓“正方形网格”是指每个格子都是正 方形的网格；结点是指纵线和横线的交点）。, 利用 旧井资料的费用为10万元，则利用一口旧井 就节约费用490万元。,假定每个格子的边长（井位的纵横间距） 都是1单位（比如100米）。整个网格是可以 在平面上任意移动的。 若一个已知点Pi点与某个网格结点Xi的距离 不超过给定误差（=0.05单位），则认为Pi处 的旧井资料可以利用，不必在结点Xi处打新井。 为进行辅助决策，勘探部门要求我们研究 如下问题： 1.假定网格的横向和纵向是固定的（比如东 西向和南北向），,并假定距离误差是沿横向和纵向计算的; 即要求可利用Pi点与相应结点Xi的横坐标之 差(取绝对值)及纵坐标之差(取绝对值)均不超 过.在平面上平行移动网格N，使可利用的 旧井数尽可能大。 试提供一种数值计算方法，并对下面的数 值例子用计算机进行计算。 2. 在问题1.)的基础上，考虑 网格的横向 和纵向不固定（可以旋转）的情形，给出算 法及计算结果。,I 1 2 3 4 5 6 7 8 9 10 11 12 aI 0.50 1.41 3.00 3.37 3.40 4.72 4.72 5.43 7.57 8.38 8.98 9.50 bI 2.00 3.50 1.50 3.51 5.50 2.00 6.24 4.10 2.01 4.50 3.41 0.80 二.名词和符号说明 1.取整运算. x=不大于x的最大整数. x=INT(X) r(x)=x+ . (x按4舍5入规则取整),数值例子: n=12个点的坐标如下表所示,按4舍5入取整的小数 部分 2.) 距离概念. 纵横距离: 给定两点P(a,b)及X(x,y) d(P,X)=max 欧氏距离: 3.)记号:,x的小数部分., 代表题设误差,即 0.05 单位 第i口旧井所在的点.其坐标 . 为 代表 附近的网格结点,其 坐标为 . (s , t) 网格离原点最近的结点坐 标. 网格旋转的角度.,三. 问题分析与要求 如果一个已知点 与某个网格 结点 距离不超过给定误差 (0.05)单位,则认为 处的旧井资 料可以利用. 因此,在纵横(或欧氏)距离定义 下, 可采用以下两种处理方法: )以 为中心,2 单位为边长作一,个正方形(或半径为 的圆). 若网格在平移过程中,网格中的 某个结点 落在以 为中心的正方 形(或圆)的闭区域上,则可以认为 可以利用旧井 的相应资料. )以 为中心,2 单位为边长作一 个正方形(或半径为 的圆).若网格 在平移过程中, 落在以 为中心的,正方形(或圆)的闭区域上,则可以认 为 可以利用旧井 的相应资料. 注: 这两种方法分别对应于网格移动 和坐标平移,显然它们是等价的. 对问题1.由于精度要求为 0.01 ( = 0.05)且网格可上下、左右平行移 动. 因此:可按纵横坐标方向分别平移,100次.对区域中的所有12个旧井点 进行搜索,记录可利用的旧井数. 最后比较这100100次平移中 哪一次可利用的旧井数最大,则该网 格位置为最优. 对问题2. 以某一角度为步长转动 网格,在每一角度下,固定网格方向, 按问题1.的方法检验最多有多少旧,井可以利用. 再比较所有搜索过的角度下可 利用的旧井数,即可得允许转动时可 利用最多的旧井数. 注:)由于两点间的纵横距离会因转 动而改变,故问题2采用欧氏距离. )由于方格的对称性,只需从 转 到 即可.,) 为保证旋转小角度后,点的变动 不超过精度 =0.01,取步长 . R为距离最远点到旋转中心的距离. 本题中求出 .需要 将0, 分为2,000份,因此,本题要 进行2000次问题一的计算. 题目要求就网格的方向固定或不 固定两种情况,计算可利用的最大,旧井数,并给出相应的算法. 四. 假设. .地形对误差无影响,无须考虑地形 这一因素. .网格充分大,给出的旧井均在所定 勘探区域内,旧井位点的坐标可记为 . 网格N的铅垂网线,水平网线分别 与两坐标轴平行.,即:网格N可由该网格中的任何一个 结点所唯一确定. 五.模型的建立与求解.,设对给定的直角坐标系oxy, 已知 点pi的坐标为(ai,bi), (1in),在网格N中离原点o最近的结点为(s,t),则 |S|1/2, |t|1/2, 且网格N的任一结点可表示为(s+m,t+n),其m,n 均为整数.,结点 (s,t) 可看作网格N上的一个参 照点,它可以在单位正方形 内移动.,于是网格N的设计参数为s,t.,1. 问题1的求解. 我们要弄清楚,对给定的s及t,如何 计算可利用的旧井数目f(s,t). 由于只有两个变量,我们可以用数 值计算方法,并借助计算机,用列表法 把二元函数f(s,t)的值计算出来,然后 求其最大值.下面是一种计算方案.,已知点pi与结点xi的距离误差是 沿坐标轴方向的，即要求pi与xi的横（纵）坐标之差的绝对值.,网格移动,坐标平移,即: 当且仅当正方形邻域 中存在结点 (s+m,t+n) 时, 是可 利用的.,当 (1) 时布尔变量 否则 可利用的旧井数:,问题1可归结为如下的最优化问题: 目标函数: = s.t.,以上模型可用计算机求其数值解. 比如取0.01为步长,将s及t的取 值 范围各自等分为100份,然后在 100100个点中求出f(s,t)的值,并 从 中直接比较求出最优解来. 在计算f(s,t)时只要对满足不等 式 的i进行计数.,对给出的数值例子,其计算结果为: max f(s,t)=4, 其中: s=0.4 , t=0.5, 可利用的井号为 2, 4, 5, 10. 2.问题2的求解. 首先考虑用欧氏距离表示误差而 网格N不旋转的情形. 显然,当且仅当园形邻域,内存在结点 (s+m,t+n) 时,已知点 是可利用的. 此时,记布尔变量 由于网格N不旋转,且正方形邻 域 包含了园形邻域 即:,否则,.,.,我们可以进一步检验该结点是 否落入园形邻域中. 因此,当且仅当 时,布尔变量 即:当且仅当 (2),否则,是可利用的. 注: 用这种方法计算出所有的 ( ). (此例:n=12) 由 f(s,t)= 得到 s , t 给定 时的函数值 f(s,t). 由此可得以上问题的数学模型: 目标函数 =max,s.t.,结点:,考虑用欧氏距离表示误差而网格 N 可以旋转的情形. 欲求的网格N的横向和纵向可 用新坐标系0xy的横轴和纵轴表 示,其中ox轴与ox轴的夹角为 ,根据坐标变换公式,点pi在新坐标系下的坐标为,(3),注: 坐标原点o不一定是网格N的结点.,我们设计在坐标系oxy中,网格N 中离原点最近的结点为(s,t),其中: |s|,|t|,这样一来,网格N的设计参数为, s , t.,由于方格的对称性， 只需从,即可，为保证旋转小角度,后，点的变动不超过精度 0.01,取 步长 R为距离最远点到旋转中 心的距离.本题中求出,需要将 分为2000等份.,步骤:将的取值范围离散化,将 分为2000等份.,对每一个值,运用坐标变换 公式: 计算出各点,在新坐标系 0xy 中的坐标,.,运用上述的算法进行搜索,本问 题要进行2000100100= 次数 值计算. 对