1、暑 期 培 訓,數(shù) 學 建 模 競 賽,一.問題提出 勘探部門在某地區(qū)找礦。初步勘探時期已 零散地在若干位置上鉆井，取得了地質資料。 進入系統(tǒng)勘探時期后，要在一個區(qū)域內按 縱橫等距的網(wǎng)格點來布置井位，進行“撒網(wǎng)式” 全面鉆探。 由于鉆一口井的費用很高，如果新設計 的井位與原有井位重合（或相當接近），便 可利用舊井的地質資料，不必打這口新井。,(1999)鉆井布局,因此，應該盡量利用舊井，少打新井，以 節(jié)約鉆探費用。 比如:鉆一口新井的費用為500萬元 設平面上有n個點Pi，其坐標為（ai ,bi） i= 1，2，,n,表示已有的個井位。 新布置的井位是一個正方形網(wǎng)格N的所有 結點（所謂“正方形

2、網(wǎng)格”是指每個格子都是正 方形的網(wǎng)格；結點是指縱線和橫線的交點）。, 利用 舊井資料的費用為10萬元，則利用一口舊井 就節(jié)約費用490萬元。,假定每個格子的邊長（井位的縱橫間距） 都是1單位（比如100米）。整個網(wǎng)格是可以 在平面上任意移動的。 若一個已知點Pi點與某個網(wǎng)格結點Xi的距離 不超過給定誤差（=0.05單位），則認為Pi處 的舊井資料可以利用，不必在結點Xi處打新井。 為進行輔助決策，勘探部門要求我們研究 如下問題： 1.假定網(wǎng)格的橫向和縱向是固定的（比如東 西向和南北向），,并假定距離誤差是沿橫向和縱向計算的; 即要求可利用Pi點與相應結點Xi的橫坐標之 差(取絕對值)及縱坐標之

3、差(取絕對值)均不超 過.在平面上平行移動網(wǎng)格N，使可利用的 舊井數(shù)盡可能大。 試提供一種數(shù)值計算方法，并對下面的數(shù) 值例子用計算機進行計算。 2. 在問題1.)的基礎上，考慮 網(wǎng)格的橫向 和縱向不固定（可以旋轉）的情形，給出算 法及計算結果。,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=不大

4、于x的最大整數(shù). x=INT(X) r(x)=x+ . (x按4舍5入規(guī)則取整),數(shù)值例子: n=12個點的坐標如下表所示,按4舍5入取整的小數(shù) 部分 2.) 距離概念. 縱橫距離: 給定兩點P(a,b)及X(x,y) d(P,X)=max 歐氏距離: 3.)記號:,x的小數(shù)部分., 代表題設誤差,即 0.05 單位 第i口舊井所在的點.其坐標 . 為 代表 附近的網(wǎng)格結點,其 坐標為 . (s , t) 網(wǎng)格離原點最近的結點坐 標. 網(wǎng)格旋轉的角度.,三. 問題分析與要求 如果一個已知點 與某個網(wǎng)格 結點 距離不超過給定誤差 (0.05)單位,則認為 處的舊井資 料可以利用. 因此,在縱橫(

5、或歐氏)距離定義 下, 可采用以下兩種處理方法: )以 為中心,2 單位為邊長作一,個正方形(或半徑為 的圓). 若網(wǎng)格在平移過程中,網(wǎng)格中的 某個結點 落在以 為中心的正方 形(或圓)的閉區(qū)域上,則可以認為 可以利用舊井 的相應資料. )以 為中心,2 單位為邊長作一 個正方形(或半徑為 的圓).若網(wǎng)格 在平移過程中, 落在以 為中心的,正方形(或圓)的閉區(qū)域上,則可以認 為 可以利用舊井 的相應資料. 注: 這兩種方法分別對應于網(wǎng)格移動 和坐標平移,顯然它們是等價的. 對問題1.由于精度要求為 0.01 ( = 0.05)且網(wǎng)格可上下、左右平行移 動. 因此:可按縱橫坐標方向分別平移,10

6、0次.對區(qū)域中的所有12個舊井點 進行搜索,記錄可利用的舊井數(shù). 最后比較這100100次平移中 哪一次可利用的舊井數(shù)最大,則該網(wǎng) 格位置為最優(yōu). 對問題2. 以某一角度為步長轉動 網(wǎng)格,在每一角度下,固定網(wǎng)格方向, 按問題1.的方法檢驗最多有多少舊,井可以利用. 再比較所有搜索過的角度下可 利用的舊井數(shù),即可得允許轉動時可 利用最多的舊井數(shù). 注:)由于兩點間的縱橫距離會因轉 動而改變,故問題2采用歐氏距離. )由于方格的對稱性,只需從 轉 到 即可.,) 為保證旋轉小角度后,點的變動 不超過精度 =0.01,取步長 . R為距離最遠點到旋轉中心的距離. 本題中求出 .需要 將0, 分為2,

7、000份,因此,本題要 進行2000次問題一的計算. 題目要求就網(wǎng)格的方向固定或不 固定兩種情況,計算可利用的最大,舊井數(shù),并給出相應的算法. 四. 假設. .地形對誤差無影響,無須考慮地形 這一因素. .網(wǎng)格充分大,給出的舊井均在所定 勘探區(qū)域內,舊井位點的坐標可記為 . 網(wǎng)格N的鉛垂網(wǎng)線,水平網(wǎng)線分別 與兩坐標軸平行.,即:網(wǎng)格N可由該網(wǎng)格中的任何一個 結點所唯一確定. 五.模型的建立與求解.,設對給定的直角坐標系oxy, 已知 點pi的坐標為(ai,bi), (1in),在網(wǎng)格N中離原點o最近的結點為(s,t),則 |S|1/2, |t|1/2, 且網(wǎng)格N的任一結點可表示為(s+m,t+

8、n),其m,n 均為整數(shù).,結點 (s,t) 可看作網(wǎng)格N上的一個參 照點,它可以在單位正方形 內移動.,于是網(wǎng)格N的設計參數(shù)為s,t.,1. 問題1的求解. 我們要弄清楚,對給定的s及t,如何 計算可利用的舊井數(shù)目f(s,t). 由于只有兩個變量,我們可以用數(shù) 值計算方法,并借助計算機,用列表法 把二元函數(shù)f(s,t)的值計算出來,然后 求其最大值.下面是一種計算方案.,已知點pi與結點xi的距離誤差是 沿坐標軸方向的，即要求pi與xi的橫（縱）坐標之差的絕對值.,網(wǎng)格移動,坐標平移,即: 當且僅當正方形鄰域 中存在結點 (s+m,t+n) 時, 是可 利用的.,當 (1) 時布爾變量 否則

9、 可利用的舊井數(shù):,問題1可歸結為如下的最優(yōu)化問題: 目標函數(shù): = s.t.,以上模型可用計算機求其數(shù)值解. 比如取0.01為步長,將s及t的取 值 范圍各自等分為100份,然后在 100100個點中求出f(s,t)的值,并 從 中直接比較求出最優(yōu)解來. 在計算f(s,t)時只要對滿足不等 式 的i進行計數(shù).,對給出的數(shù)值例子,其計算結果為: max f(s,t)=4, 其中: s=0.4 , t=0.5, 可利用的井號為 2, 4, 5, 10. 2.問題2的求解. 首先考慮用歐氏距離表示誤差而 網(wǎng)格N不旋轉的情形. 顯然,當且僅當園形鄰域,內存在結點 (s+m,t+n) 時,已知點 是可

10、利用的. 此時,記布爾變量 由于網(wǎng)格N不旋轉,且正方形鄰 域 包含了園形鄰域 即:,否則,.,.,我們可以進一步檢驗該結點是 否落入園形鄰域中. 因此,當且僅當 時,布爾變量 即:當且僅當 (2),否則,是可利用的. 注: 用這種方法計算出所有的 ( ). (此例:n=12) 由 f(s,t)= 得到 s , t 給定 時的函數(shù)值 f(s,t). 由此可得以上問題的數(shù)學模型: 目標函數(shù) =max,s.t.,結點:,考慮用歐氏距離表示誤差而網(wǎng)格 N 可以旋轉的情形. 欲求的網(wǎng)格N的橫向和縱向可 用新坐標系0 xy的橫軸和縱軸表 示,其中ox軸與ox軸的夾角為 ,根據(jù)坐標變換公式,點pi在新坐標系下的坐標為,(3),注: 坐標原點o不一定是網(wǎng)格N的結點.,我們設計在坐標系oxy中,網(wǎng)格N 中離原點最近的結點為(s,t),其中: |s|,|t|,這樣一來,網(wǎng)格N的設計參數(shù)為, s , t.,由于方格的對稱性， 只需從,即可，為保證旋轉小角度,后，點的變動不超過精度 0.01,取 步長 R為距離最遠點到旋轉中 心的距離.本題中求出,需要將 分為2000等份.,步驟:將的取值范圍離散化,將 分為2000等份.,對每一個值,運用坐標變換 公式: 計算出各點,在新坐標系 0 xy 中的坐標,.,運用上述的算法進行搜索,本問 題要進行2000100100次