1、第30卷第1期2000年1月数学的实践与认识MA THEMA T ICS I N PRACT ICE AND THEORYVol130No11Jan.2000钻 井 布 局 的 设 计朱振波,谢文冲,皮兴宇指导教师:数学建模组(空军雷达学院,武汉430010)编者按:本文建立了正确的数学模型来研究怎样尽可能利用旧井的问题,用多种方法来求解,得到正确的结果,还给出了利用n个旧井的充分必要条件.摘要:本文首先给出钻井布局的数学模型,进一步采用全面搜索法、局部搜索法、图论法、目测法、图上作业法等不同的优化方法,进行了模型求解.对于给定的数值例子,得到问题(1)的解为4,可利用的旧井为P2,P4,P5
2、和P10;问题(2)的解为6,可利用的旧井为P1,P6,P7,P8,P9和P11.最后对于问题(3),本文给出了n个旧井均可利用的充分必要条件.1 问题的提出(略)2问题的分析与假设1.取定坐标系,向东为横轴正向,向北为纵轴正向.旧井位点的坐标可记为Pi(ai,bi),i=1,n.21 由于问题是尽量利用旧井,故可以假设边长为1个单位的正方形网格N覆盖整个平面.31 为分析问题简便起见,总可以假设网格N的铅垂网线,水平网线分别与两坐标轴平行,故一个网格N可由该网格中的任何一个结点所唯一确定.3模型的建立与求解311问题(1)的求解由于网格N的横向与纵向是固定的,故一个网格N可由该网格中的一个结
3、点Xi所唯一确定,记为NXi.因此覆盖整个平面的各种不同网格必可由任一单位正方形内的所有点所确定.对于一个网格NXi,用f(NXi)表示所能利用的旧井点数.于是我们得到如下模型:maxf(NX)s.t.maxx-xi,y-yi0.5;其中X=(x,y),Xi=(xi,yi).由于此模型很难用分析法进行求解,故利用计算机进行数值计算.模式?全面搜索(地毯式搜索)由于所给例子中井位坐标的最小单位为0101,而误差 为0105单位,从而我们只需以步长(0101单位)来作平移搜索.定义1设Q1=(x1,y1),Q2=(x2,y2)Dx=m inx1-x2-x1-x2,1+x1-x2-(x1-x2)获取
4、更多数学建模相关资料关注【公众号：数模加油站】国赛交流分享群：544457657获取更多数学建模相关资料关注【公众号：数模加油站】国赛交流分享群：544457657Dy=m iny1-y2-y1-y2,1+y1-y2-(y1-y2)D(Q1,Q2)=maxDx,Dy 其中:x表示对x取整.则称D(Q1,Q2)为Q1与Q2的网格距离.特别用D(Q)表示Q点与原点的网格距离.由此定义立即可知:若构造网格NQ,则D(Pi,Q)表示旧井位Pi与网格NQ中某个结点的距离,故D(Pi,Q)也可称为Pi与网格NQ的距离.易知:网格距离有下述性质与定理:性质1D(Q1,Q2)=D(Q2,Q1).性质20D(Q
5、1,Q2)0.5.定理1设NQ为已知网格,Pi为旧井位的坐标,则Pi可以被利用D(Pi,Q).定理2设P1,P2为两个旧井位,则存在某个网格N,使得P1,P2可同时利用的充要条件是:D(P1,P2)2.由定理2可知,f(NX)即为P1,Pn中与X的网格距离的个数.上述两个定理的直观意义是明显的,为节省篇幅,证明过程从略.编程思想如下:(1)令Q为原点,构造网格NQ,若D(Pi,Q),i=1,n,则旧井位Pi可以利用.所有这些可利用的Pi的个数即为f(NQ).(2)将Q每次向右平移1个步长(每步长为0101单位),移一百次,再向上按同样的步长移动100次,即可得到(对于所给例子)1002=100
6、00个f(NQ),取其最大者即得.对于所给的例子,相应的程序清单见附录(略),程序运算结果如下:最大可利用的旧井数为4,旧井点分别为:P2,P4,P5,P10.网格平移范围:(1)向左平移:01580163;(2)向上平移:01450.54.模式 局部搜索模式?是全面搜索,需循环10000次.事实上只须小范围搜索即可.方法是:先取Q=Pi,(i=1,n),按模式?所给方法计算f(NQ),然后让Q在以Pi为中心,边长为2的小正方形内遍历(步长为0101)计算f(NQ),共有112个f(NQ).对于所给例子,最多需计算11212个f(NQ)(实际上,有很多Q是相同的,故不须重复计算),然后取一个最
7、大的即可.对于所给的例子,相应的程序清单见附录(略),程序运算结果如下:最大可利用旧井数为4,旧井点分别为:P2,P4,P5,P10.网格平移范围:(1)向左平移:0.580.63;(2)向上平移:0.450.54;模式 图论方法令aij=1,D(Pi,Pj)20,D(Pi,Pj)2,则A=(aij)为n阶布尔方阵,故只需寻找A所对应图的最大完全子图(即含顶点数最多的完全子图),其顶点数就是可利用的最大旧井位数(依据见后文定理5).求一个图的最大完全子图,程序见附录(略).程序运算结果为:最大可利用的旧井数为4,旧井点分别为:P2,P4,P5,P10.上述三个模型为精确的算法.此外还可用如下简
8、便实用的解法:86数学的实践与认识30卷获取更多数学建模相关资料关注【公众号：数模加油站】国赛交流分享群：544457657获取更多数学建模相关资料关注【公众号：数模加油站】国赛交流分享群：544457657模式?目测法先把所有点都移到以原点为左下角的一个单位正方形内,方法如下:令Pi=(ai,bi),Pi=(ai,bi)其中ai=ai-ai,bi=bi-bi(i=1,n)ai=ai-ai+1,bi=bi-bi+1(i=1,n)图1则Pi,(i=1,n)就位于上述单位正方形内.再把该正方形分别向上、向右扩充0.1个单位,扩大成一个边长为1.1个单位的正方形,并在图上标出Pi.如果Pi(i=1,
9、n)也在上述扩大的正方形内,则将其标在图上(见图1).通过观察图上各点分布的密集程度,即可得出最多有几个点在某个边长为0.1单位的正方形内,则此点数即为最多可利用的旧井数.对于所给的例子,用此法一眼就能看出最大可利用的旧井数为4,它们分别是:P2,P4,P5,P10.模式 图上作业法先按照模式?的方法构造上述图形,然后用单位为011的正方形透明网格状矩形尺(要求与上述图形单位一致)在图上进行平移,可以直观看出哪个正方形内包含的点最多,则相应的点数即为满足条件的最多点数.对于所给的例子,用此法能很快地得出最大可利用的旧井数为4,它们分别是:P2,P4,P5,P10.312问题(2)的求解设N是平
10、面中的一个正方形网格.X是N中的一个结点.那么,显然N中的网线与给定坐标系横轴正向的夹角有2个,设为 1与 2(以横轴正向转到网线为准).令=m in(1,2),称 为网格N与坐标系的夹角.显然,02,该网格N由结点X与 完全确定,记为NX().可见问题(1)中的NX是NX()当=0时的特例,即NX=NX(0).对于一个网格NXi(),用g(NXi()表示所能利用的旧井点数,则问题(2)的数学模型为:maxg(NX()s.t.maxx,y015 且 0,则ai-(ai0+)或bi-(bj0+)不妨设ai-(ai0+),那么ai-ai0 2,因此D(Pi,Pi0)=D(Pi,Pi0)2,与题设矛
11、盾.再证必要性,由定理2立即可得.算法容易实施,略去.情况二:选定两点距离为欧氏距离首先,任意两点之间的欧氏网格距离不能大于2,即若max1i,jn(Pi,Pj)2,则由定理2,11,Pn不可能全部被利用.显然,n个点P1,P2,Pn全部可被利用的充要条件是平面上存在一点P,满足max1in(P,Pi).为了缩小搜索范围,减小运算量,我们给出下面的局部搜索定理.定理6P1,Pn全部可被利用的充分必要条件是:Pnj=1P(P,Pj)使得max1in(P,Pi).证明充分性设条件成立,则j,P,满足(P,Pj),max1in(P,Pi).取定网格NP,由定理3,P1,P2,Pn可以被利用.必要性设
12、存在某网格NP,使得P1,P2,Pn都是可被利用,则由定理3(P,Pi),i=1,2,n.Pnj=1P(P,Pj)且max1in(P,Pi).编程思想如下:171期朱振波等:钻井布局的设计获取更多数学建模相关资料关注【公众号：数模加油站】国赛交流分享群：544457657获取更多数学建模相关资料关注【公众号：数模加油站】国赛交流分享群：544457657分别取j=1,2,n,让P在以Pj为圆心,为半径的圆内变动.选取合适的步长,编程计算(P,P1),(P,Pn).若能搜索到P点,使max1in(P,Pi)说明P1,P2,Pn都可以被利用,结束程序;否则继续搜索.21 网格的横向和纵向不固定(可
13、以旋转)首先,取网格的铅垂网线,水平网线与所给坐标系的纵横轴平行,按上文所提供的方法进行判别和编程.其次,将坐标系绕原点旋转 角度(为保证精度,的选取必须适当的小),计算井位Pi在 新坐标系下的坐标.记为Pi()=(ai(),bi(),对旋转后的新坐标系中井位新坐标Pi(),再继续按上文所提供的方法求解.如此继续下去,直到旋过角度2为止.如果在上述搜索过程中,已得知P1,Pn可被全部利用,即可终止程序,打印结果.4模型分析及推广应用对于直接搜索模型,作为一种最直接、最简单的模型,它能够保证在不遗漏一个点的情况下找到解.但是,此模型是建立在全面搜索的基础上,丝毫不考虑可简化的因素,因而具有计算量
14、大,搜索速度慢等缺点,不利于推广应用.而对于优化搜索模型,它在充分考虑有利条件的同时,可避免某些不利因素,从而能够在比较短的时间内寻找到目标点,完成任务.这对于其它类似问题也有很好的参考价值.比如说在考虑已有交通枢纽城镇的情况下,如何安排某地区交通建设,使投资比较少,但达到改善各地交通及城市建设规划的目的,以及在充分利用已有某些有利条件下,再如何人为增加有利因素,以达到最优化效果等,本优化模型都有一定的借鉴作用.当然,如何较快的找到优化模型,就成为其进一步推广应用的重要制约因素.参考文献:1姜启源 1 数学模型 1 北京:高等教育出版社,1987.2齐欢 1 数学模型方法 1 武汉:华中理工大
15、学出版社,1996,613施久玉等 1 数学建模 1 哈尔滨:哈尔滨工程大学出版社,1996,514张莹 1 运筹学基础 1 北京:清华大学出版社,1995,415王树禾 1 图论及其算法 1 北京:中国科学技术出版社,1990,101M ine Drilling D istributionZHU Zhen2bo,X IE W en2chong,P IXing2yu(A irforce Radar Institute,W uhan430010)Abstract:This paper offers a mathematicalmodel of m ine drillings distributi
16、on and its solu2tion by using different opti m ization methods,such as all2sided searching method,partial2search227数学的实践与认识30卷获取更多数学建模相关资料关注【公众号：数模加油站】国赛交流分享群：544457657获取更多数学建模相关资料关注【公众号：数模加油站】国赛交流分享群：544457657第30卷第1期2000年1月数学的实践与认识MA THEMA T ICS I N PRACT ICE AND THEORYVol130No11Jan.2000ing method,
17、graph theorymethod,sightmethod and operation2in2graph mehtod.For the given nu2merical examples,the obtained solution to problem(1)is 4 and the available old drillings areP2,P4,P5,P10;the solution to problem(2)is 6 and the available old drillings areP1,P6,P7,P8,P9,P11.Finally,for problem(3),this pape
18、r gives a sufficient and necessary condition for n olddrillings being available.“钻井布局”问题评述林诒勋(郑州大学数学系,郑州450052)摘要:本文评述1999年全国大学生数学建模竞赛赛题“钻井布局”,就背景、模型、解法途径及进一步研究等方面作出总结.1问题来源80年代一位地质工程师在从事一项研究中与笔者讨论过此题的原型,当时研究的情况比较复杂,如网格的纵横间隔可以选择,但不能太小,转角也有限制,尽可能利用全部旧井.本题就是从中提取出来的一个形式比较简明的问题.后来又经过组委会几位同志的精心设计,才得到专科组的
19、两小题和本科组的三小题(赛题参见前面的介绍).数值例子的数据不是真实的.由于此题原先是入选为D题(专科组)的,希望计算上容易些,故意使某些点的坐标的小数部分比较密集.这样就造成了一个缺陷:数据对计算方案的不敏感性.笔者在评阅工作过程中,受到一些优秀答卷的启发,并听取了评阅专家的讨论意见,对这道赛题的认识有很大的提高.现在谈一些看法,供大家参考.2基本概念解此题不需要专门的知识,方法是初等的,但一些基本概念要清楚.一些好的答卷都是由于把握住这些概念;而大部分答卷中的错误都是源于这些方面的疏忽.(1)取整运算研究网格点与其它点的关系必然要用取整运算.常用的有如下两种:x=不大于x的最大整数(x的整数部分),r(x)=x+12(x按四舍五入规则的取整).前者相当于计算机中的函数I N T,后者相当于函数ROUND(对非负数而言).此外,有时还会用到上取整(ceiling)和下取整(floor).这里x相当于下取整.我们可以分别表示按下取整及四舍五入取整的小数部分为x=x-x,f(x)=x-r(x).获取更多数学建模相关资料关注【公众号：数模加油站】国赛交流分享群：544457657获取更多数学建模相关资料关注【公众号：数模加油站】国赛交流分享群：544457657
