全国大学生《数学建模》竞赛：1999B

钻井布局 推论2-4如果n个旧井点的相互连线PP(i=1,2,…,n;=1,2,…,n)的近似 N分解m,na满足命题2-4中(4)式,那么这n个旧井点可以通过坐标变换分别靠近 某网格的n个结点(不一定小于) 根据命题2-3和推论2-2容易得到结论 命题2-5n口井P(a1,b)都可利用充分必要条件是以下两式有公共解 (x1-x1)2+(y-y1)2=m12+n12 (x1-x2)2+(y-y2)2=ma2+n2(i=2,3,…,n) (6) y-y3)2 b1)2≤ 1,2,…,n) (其中:m;,n为PP的一种近似M-N分解且满足命题2-4,当i=j时,记m=0,n 0,且所有的不全等时,总是设"12≠m1). 证明【充分性】设(6)式有解,表示存在一系列点X(x1,y)(i=1,2,…,n),使得1 xX|=√m2+n2,所以X式存在一种M-N分解为(m,n).又因为m,n满足命 题2-4中的(4)式,根据命题2-4的充分条件(m全等时表明x共线,由于mn满足 (4)式显然也满足(3)式,由命题2-3的充分条件)可知X(=1,2,…,n)都在某网格坐标 系的结点上,而(7)式说明PX≤ε,(i=1,2,…,n),即P1(i=1,2,…,n)都可以利 用 【必要性】n口井都利用即表示在某网格坐标系(不妨设为G)下1PX1≤(x1( )为该网格上的结点),则X(x;,y)满足(7)式,又因为X是G上的结点,设X区在坐 标G下的分量为m,n,显然ma,n满足(6)式 必要条件成立 证毕 4.5问题二的解答步骤 步骤1建立一张12口井之间的距离互相关系表.如下表所示,当两口旧井之间的距 离满足近似的M-N分解时,记录下能进行所有可能的近似M-N分解,如果旧井点P, P可以进行近似M-N分解就在第i行列记下PP的近似M-N分解的可能数目,如果 P4,P不能进行近似MN分解则记为0.通过对绝对值小于两点之间的距离的所有整数 进行穷举,求出所有可能的m,n,把它们存入数组,以供以后使用.(下面是根据原题所附 数据得出的结果) 2#0 3#0 4#1 5#1 6# 7#1 8#?121 9#3

448 全国大学生数学建模竞赛优秀论文汇编 示10#131131210 11#21114111110 122.0小1)0个0 1#2#3#4#5#6#7#8#9#10#11# 步骤2根据推论2-1,找出系列集合,使得集合中间任意两点之间的距离都可以进行 近似M-N分解(通过步骤1给出的表判定),算法程序为子程序 Conduct,为了加快运算, 用子程序band去掉重复的集合 步骤3根据命题2-2,在上述集合中,进一步判断,找出任意三个点都可构成近似整 数分解三角形的集合 步骤4对步骤3判断的结果进一步判断.对其中的任何一个集合,判断这k个点的近 似M-N分解是否可能满足命题2-4条件,如果不可能,则该集合不满足条件,如果可能 则输出该集合和相应的M-N分解值.这样可以得到可能的结果为:(只打出4个元素以上 的集合) ,许(别世 444446 9 的一 11的 7(8 真解就是在这些集合中 以上4步由程序 PREDUCT.CPP, SECOND.CPP完成 步骤5对输出集合进行顺序调整,当k个点都在同一直线上(即 )任取三点X,X2,x3否则,不妨设有不共线的三点x1,X2,X3,然后把(6)式转化为 f(x1,x2…,x,y,y2…,y)=√(a1÷x1)2+(b1=y1)2处 g(x1,x2,…,xk,y1,y2,…,yk),h(x1,x2,…,x,y1,y2,,y)为向量函数,其分量为 g:1(x1,x2,…,x1,y1,y2…,y)=√(a1-x1)2+(b1-y)2e )2+(y1-y)2-(m12+m12) h43=(x1-x2)2+( y2)2-(m2+n2)润 (x1-x3)2+(y1-y3)2-(m132+n32) 考虑如下规划模型 g1(x1,…,x,y……,y)≤0 h;( 显然该规划模型与命题2-5中(6)(7)式是等价的,又因为命题2-5是一个充分必要 条件,所以:当minf(x1,…,x,y1,,y)≤0时表示存在X(x,y)满足(6)式,即n口井

钻井布局模型 449 都可以利用.当minf(x1,…,xk,y1,…,)>0时,n口井不可能被同时利用 采用 MATLAB作为优化工具,用 constr函数进行优化,逐步判断所有集合中所含元素 最多的子集和集合本身,通过运算得出满足条件的集合为:1,6,7,8,9,111.根据返回的 X(x,y)的M-N分解值建立网格坐标系将12个旧井点的坐标进行转换,得到如附图 所示的结果,在这个网格中,6个点到它们各自附近整点的距离最大值为:S9=0.049<c 四4.6问题三的分析和解法 长半个一示中 显然,问题二的解法是一个通用算法,对于问题三同样适用.综合问题二的命题和推 论得出以下算法:(本题在欧氏距离意义下讨论) 1.根据推论2-1:n个点能同时利用必需满足对任意两点P,P,存在(m,m)使得 P 2根据推论2-3:n个点能同时利用必须满足任意三点P,P,P的任意一边满足近 似M-N分解,而且分出的(m;,n1)满足命题2-2中式(2) 3.根据推论2-4:如果n个旧井点的相互连线PP(i-1,2,…,n;=1,2,…,n)的 近似M-N分解ma,n满足命题2-4中(4),那么这n个旧井点可以通过坐标变换靠近n 个网格结点(不一定小于E) 在通过这三步的判断后我们提出两种方法来作最后的判断 带不 方法一根据命题2-5:n口井能同时利用的充分必要条件是在满足上述三个条件的 前提下,满足命题2-5中的不等式(7).依次判断给定的n个点是否满足上面分析中的4个 条件,如果其中一步不满足,则表明不能同时利用,如果全部满足,则表示这n个点可以同 时利用、具体步骤参考问题二 方法二根据前面的计算得出的可能网格坐标系结点,算出这些结点在该网格坐标系 下的坐标为X(c,d1),则把这些结点作坐标变换 8 sino\ci Ar 即 sing cos0/{d+△ 可得 =f(6,△x,△y)=cos0(c;+△x)+sin0(d1+△y) =f(0,4x,4y)=-sin(c;+△x)+cos0(d1+△y) 又根据命题3-3(见后面所附命题),要使得n个点能同时被利用,至少要保证任何 个点P附近存在n层重叠区域S,,根据S1的构造方法易知判断S的存在性等价于判断下 面的不等式组是否有解: x)2+(b. √(a;-x;)2+(b1-y)2≤Sn+ (9) )2+(b-y)2≥S (其中j=1.2…1,+1…,n;Sn=)2+(x-y2)把(8)式代入不等式 组(9)并整理即可得一组关于(0,△x,△y)的不等式组 f(0,4x,4)2+((0,△x,4y)2≤c ,(a4-1(0,△,4)+(+k(O,△,4yD/e(10

450 全国大学生数学建模竞赛优秀论文汇编 对所有的x解这样的不等式组就可得出结论.由于时间的关系,我们没有给出方法二 的具体程序,但是因为方法二是一个比较初等的方法,因此可以很容易的构造出它的具体解 法和程序 出场,本合原动的 4.7问题三的附加命题 一 命题3-1设有任意两点P1,P2和某网格两结点x1,x2,=1x1x2,以P1点为圆 环中心,作一个半径为R=5+E,r=5-e的圆环,再以P2点为圆心作一个半径为e的圆 设圆环和圆的重叠区域为S2,同理对称地在P1点附近求得一个重叠区域S1那么满足 1X1P1|≤e,|X2P2l≤c的充要条件是:存在X1∈S1,X2∈S2 证明【充分性】如果X1∈S1,X2∈S2,命题显然成立 【必要性】(先不妨设s≤1P1P21,则圆环与圆的重叠区域必然如图3-1所示)假设, 不妨设X2∈S2(S2为P2圆内除去S2的部分)连接X1P1,X1X2,X2P1三条线段,根据 三角形的性质有:1X1P1+1x1X21≥1x2P1 的出且长不 的(又显然X2在圆环外侧,所以1X2P1>R5+E个 X2121X2P1X1P1>s+7=5 即1X1X21>1X1X21,产生矛盾 假设不成立 来式再出自三发近 x2∈S2,同理X1∈S1 当5>P1P2时,证法与此类似,应用三角形三边的关系即可得证,因此略去 命题3-2在命题3-1的基础上考虑三个点P1,P2,P3的情形,如图3-2.取其重复 三层覆盖的区域为S1,S2,S3,这样要使1X1P1≤e,|X2P2≤,lX3P3≤c的充要 条件是:存在X1∈S1,X2∈S2,X3∈S3·周 St X- 图3 证明【充分性】易知 论,【必要性】例如对点P1,根据命题3-1,如果x1∈S1,则X1,X3不能同时满足条件, 果X1∈S1,则X1,X2不能同时满足条件 01)命题3-3类似地可以对n个点的情形进行证明,取其n层重叠区域为S1,S2,…,S 要使得1XP1≤e,(i=1,2,…,n).如果某一个点P附近不存在n层重叠区域,即S

钻井布局模型 451 ∈O,则x∈O,这样的x不存在,即这n个点不可能同时有某网格的n个结点使得 XP1|≤c·如果存在,且能找到某网格的n个结点X1,X2,…,Kn使得X∈S,则这m 个点能满足同时利用的条件 5算法分析 (1)在第二题的解法中,我们给出了一个通用的解法,不仅能判断n个旧井点是否可以 同时利用,而且在不能同时利用时给出了能同时利用旧井点的最大数 (2)算法采用逐层筛选,不存在误差.最后的多变量求极值时,根据命题四的分析,我 们知道n个点都靠近网格结点,因此误差很小 (3)通过必要条件的层层筛选,不仅优化步骤提供了M-N分解值,是必不可少的 步.而且使后来的优化处理的数据范围小,大大减少了优化的次数 (4)在第三题的解法中,我们给出了两种不同的解法,这两种解法的区别在于第二种解 法需要的仅仅是求关于三个变量的n2个不等式是否有解,可以用穷举的办法来解决,不需 要用优化方法来解题 参考文献 [1周承高,廖园.《优化方法及应用程序设计).中国铁道出版社,1989 MATLAB语言》.中国科技大学出版社,1995.11 昌,曾文艺.《数学模型与数学建模》北京师范大学出版社,1997,8 数学的发展关系到整个科学技术的发展而科学技术是第一生产力;所以数学的发 展是一件国家大事。 钱学森,发展我国的数学科学一在中国数学会召开的数学教育与科研座谈会上的讲话 《数学进展》,1990,19(2):129-135 干大不离照总的的振离国,:3因0比