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

《数学建模竞赛课件钻井布局.ppt》由会员分享，可在线阅读，更多相关《数学建模竞赛课件钻井布局.ppt（38页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 一一.问题提出问题提出 勘探部门在某地区找矿。初步勘探时期已 零散地在若干位置上钻井，取得了地质资料。进入系统勘探时期后，要在一个区域内按纵横等距的网格点来布置井位，进行“撒网式”全面钻探。由于钻一口井的费用很高，如果新设计的井位与原有井位重合（或相当接近），便 可利用旧井的地质资料，不必打这口新井。(1999)钻井布局钻井布局 因此，应该尽量利用旧井，少打新井，以 节约钻探费用。比如:钻一口新井的费用为500万元 设平面上有n个点Pi，其坐标为（ai,bi）i=1，2，,n,表示已有的个井位。新布置的井位是一个正方形网格N的所有 结点（所谓“正方形网格”是指每个格子都是正 方形的网格；结点

2、是指纵线和横线的交点）。,利用旧井资料的费用为10万元，则利用一口旧井 就节约费用490万元。假定每个格子的边长（井位的纵横间距）都是1单位（比如100米）。整个网格是可以 在平面上任意移动的。若一个已知点Pi点与某个网格结点Xi的距离 不超过给定误差（=0.05单位），则认为Pi处 的旧井资料可以利用，不必在结点Xi处打新井。为进行辅助决策，勘探部门要求我们研究 如下问题：1.假定网格的横向和纵向是固定的（比如东 西向和南北向），并假定距离误差是沿横向和纵向计算的;即要求可利用Pi点与相应结点Xi的横坐标之 差(取绝对值)及纵坐标之差(取绝对值)均不超 过.在平面上平行移动网格N，使可利用的

3、 旧井数尽可能大。试提供一种数值计算方法，并对下面的数 值例子用计算机进行计算。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、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 单位为边长作一 个正方

5、形(或半径为 的圆).若网格在平移过程中,网格中的 某个结点 落在以 为中心的正方 形(或圆)的闭区域上,则可以认为 可以利用旧井 的相应资料.)以 为中心,2 单位为边长作一 个正方形(或半径为 的圆).若网格 在平移过程中,落在以 为中心的 正方形(或圆)的闭区域上,则可以认 为 可以利用旧井 的相应资料.注:这两种方法分别对应于网格移动 和坐标平移,显然它们是等价的.对问题1.由于精度要求为 0.01(=0.05)且网格可上下、左右平行移 动.因此:可按纵横坐标方向分别平移 100次.对区域中的所有12个旧井点 进行搜索,记录可利用的旧井数.最后比较这100100次平移中 哪一次可利用的

6、旧井数最大,则该网 格位置为最优.对问题2.以某一角度为步长转动 网格,在每一角度下,固定网格方向,按问题1.的方法检验最多有多少旧 井可以利用.再比较所有搜索过的角度下可 利用的旧井数,即可得允许转动时可 利用最多的旧井数.注:)由于两点间的纵横距离会因转 动而改变,故问题2采用欧氏距离.)由于方格的对称性,只需从 转 到 即可.)为保证旋转小角度后,点的变动 不超过精度 =0.01,取步长 .R为距离最远点到旋转中心的距离.本题中求出 .需要 将0,分为2,000份,因此,本题要 进行2000次问题一的计算.题目要求就网格的方向固定或不 固定两种情况,计算可利用的最大 旧井数,并给出相应的

7、算法.四四.假设假设.地形对误差无影响,无须考虑地形 这一因素.网格充分大,给出的旧井均在所定 勘探区域内,旧井位点的坐标可记为 .网格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的求解.

8、我们要弄清楚,对给定的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份,然后在 1001

9、00个点中求出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)否则 是可利用的.注:用这种方法计算出所

10、有的 ().(此例:n=12)由 f(s,t)=得到 s,t 给定 时的函数值 f(s,t).由此可得以上问题的数学模型:目标函数 =max s.t.结点:考虑用欧氏距离表示误差而网格 N 可以旋转的情形.欲求的网格N的横向和纵向可 用新坐标系0 xy的横轴和纵轴表 示,其中ox轴与ox轴的夹角为 ,根据坐标变换公式,点pi在新坐标系下的坐标为 (3)注:坐标原点o不一定是网格N的结点.我们设计在坐标系oxy中,网格N中离原点最近的结点为(s,t),其中:|s|,|t|这样一来,网格N的设计参数为,s,t.由于方格的对称性，只需从即可，为保证旋转小角度后，点的变动不超过精度 0.01,取步长 R为距离最远点到旋转中心的距离.本题中求出需要将 分为2000等份.步骤:将的取值范围离散化,将 分为2000等份.对每一个值,运用坐标变换公式:计算出各点在新坐标系 0 xy 中的坐标.运用上述的算法进行搜索,本问 题要进行2000100100=次数 值计算.对 次计算结果进行比较,求 出最大值.当=/4时,S=-0.27,t=0.03,最大可利用井数为6,可利用的井号为1,6,7,8,9,11,也可以取第一象限中离原点最近的 结点为(s,t),(os1,0t1)计算过程类似.对给定的数值例子,计算结果是:注:s.t.=作业：求解以下规划问题：