2019區域覆蓋問題設計報告

2021-04-23 01:50:11 字數 4750 閱讀 8762

目錄一、 問題重述

二、 問題分析

三、 模型假設

四、 定義與符號說明

五、 模型的建立與求解

模型i(正方形模型)

模型ii(正六邊形模型)

推廣 :以圓求解模型

六、 對模型的評價

七、 參考文獻

八、 附錄

﹑問題重述

給定乙個m*n的矩形區域,如果半徑為r的圓對其進行完全覆蓋,要求相鄰兩個圓相交的公共面積不小於乙個圓面積的k%,使得完全覆蓋整個圖形時所用圓的個數最少,求解覆蓋模型。

二﹑問題分析

對於問題的分析,要求我們要完全相同的最少的圓完全覆蓋矩形區域,這樣減少圓的個數,讓其求解該題的思路更加清晰。該問題屬於數學中的幾何問題,通常採用幾何作圖的方法再結合幾何定理嘗試解決該問題的模型,再通過具體資料對模型進行驗證優化,篩選出最優模型。

對於問題所要求的結果進行分析:題目要求使用盡可能少的完全相同的圓完全覆蓋矩形區域,要使其完全覆蓋則圓與圓之間必有重疊部分。基於上述要求,本題就從減少重疊部分著手。

又因為此題給出了一組資料,利用資料可使得問題簡化。從實際結合理論要求,我們採用**、推理、證明的方法。首先,正方形是乙個特殊的四邊形,用圓進行覆蓋,把兩個特殊的圖形聯絡起來。

很自然的想到利用正方形進行覆蓋,而用正方形的外接圓再覆蓋矩形區域。再從具體的資料入手計算,考慮完全覆蓋的最優個數問題。那麼其他的正多邊形是否可以同樣利用外接圓的思想對矩形區域進行完全覆蓋計算?

通過證明可以知道正三角形、正方形、正六邊形可以滿足要求(見附錄1.2)。利用幾何定理自然地可以推廣到正六邊形。

這就是本文的基本思路。

綜合以上原因,首先,我們建立了乙個以正方形為單位對矩形區域進行覆蓋的模型,然後,建立了乙個以正六邊形為單位的對矩形區域進行覆蓋的模型。先對兩個模型進行**,再利用所給的實際資料進行計算,對結果進行了分析。最後,得出較優模型。

三、模型假設

.覆蓋區域為乙個矩形;

.每乙個圓都是半徑相同的等圓;

.相鄰兩個圓相交的公共面積不小於乙個圓面積的k%;

.如果乙個圓只有部分在圖形中,也按乙個計算;

.用相同的正多邊形完全覆蓋矩形,相鄰正多邊形間無縫隙。

四、定義與符號說明

模型的建立與求解

一以正方形為單位的對矩形區域進行覆蓋的模型i

在解決本問題的過程中,我們需要考慮的問題主要有以下幾點:

一、怎樣用圓覆蓋矩形區域,且使得所用圓的個數最少?

二、相鄰兩個圓重合面積的怎樣計算?由於題中最後給出了一邊長為1000的正方形,半徑為100的圓去填充正方形,故我們可以通過該特殊例子的求解方案建立模型,從而推廣到一般的矩形區域覆蓋問題。

針對m=n=1000.r=100,的覆蓋問題的求解

解題思路如下:

建立以正方形為基礎,通過以正方形外接圓為單位去覆蓋例題中所給的正方形,然後根據例題作進一步的推廣到矩形。如下圖所示

小正方形的對角線ab為200,則可以通過計算得到小正方形的邊長為100 (注1.4142)小正方形的外接圓半徑r=100,用小正方形外接圓去覆蓋小正方形。當正方形邊長為1000時,可以將此正方形分解為對角線長為200的若干小正方形,沒有被分為小正方形部分為小矩形,然後用小正方形的外接圓去覆蓋小正方形,剩餘的小矩形補為對角線長為200的小正方形,然後用小正方形外接圓去覆蓋小正方形。

通過程式設計得到(附錄3)如下圖

共要8*8=64個小方形

此時相鄰兩正方形外接圓重合面積為s1 如下圖所示

s1=() s=

k%==18.15%

以上是對邊長為1000的正方形的計算,通過該計算思想可以推廣到矩形區域覆蓋問題上

已知矩形的長為m,寬為 n ,用半徑為 r的圓去覆蓋矩形,可把矩形分成若干個對角線長為2r 的小正方形,沒有被分為小正方形部分為小矩形,然後用小正方形的外接圓去覆蓋小正方形,剩餘剩餘的小矩形補為對角線長為200的小正方形,然後用小正方形外接圓去覆蓋小正方形。建立如下公式

a2=b2=

s=a2*b2=

根據以上公式我們可以通過程式設計計算出要用多少個圓去覆蓋矩形,該求解該模型的思路和求解上一特例的思路一樣,即相鄰兩正方形外接圓重合面積與上例相同 k%=18.15%

下用正六邊形求解矩形區域覆蓋問題

二以正六邊形形為單位的對矩形區域進行覆蓋的模型ii

(1) 模型的知識準備

在滿足完全覆蓋矩形區域的條件下,使得所用圓個數最少,就要充分利用每個圓覆蓋的區域範圍,盡可能減小重疊部分。為便於討論,考慮三個圓相交的情況,如圖1(a)中以o1,o2,o3為圓心的圓,我們的目標是要使得他們之間相互重合部分面積達到最小,又從圖1(b)可以看出三圓重疊的面積比1(a)中更小。

圖1(a圖1(b)

定理1:如果三個半徑相同的圓兩兩相交且覆蓋面積最大,則三圓必交於一點。

定理2:如果三圓兩兩相交於一點並且三個圓心圍成等邊三角形,則其覆蓋面積最大。

圖2證明:由定理1如圖2設o為三個圓的交點,每個圓圓心到交點的距離均為r。三圓心必然在以o為圓心r為半徑的圓周上。要使得三圓覆蓋面積最大,即求陰影部分最小。又在同一圓中,必有;

扇形=;

設以上三個扇形總面積為s,則s=;

=s-六邊形;

要使陰影部分面積最小,就要讓六邊形面積最大,也就是三角形面積最大。要使得三角形面積最大,又因為共圓,所以三角形為等邊三角形時面積最大。

又從定理2可知當覆蓋的面積最大時三圓心構成了等邊三角形, 圖3如圖3所示=,由乙個圓與六個相同半徑的圓相交構成了乙個正六邊形。如此相互覆蓋就形成了以正六邊形為單位的覆蓋模型。

由程式(見附錄4)可得如下圖形:

從圖可知用正六邊形覆蓋正方形區域共需45個。

此時相鄰兩正六邊形外接圓重合面積為s1 如下圖所示

=5.8%

通過該思路可以推廣到一般情況,如下:

(2) 模型的建立

c=六、對模型的評價與推廣

一、模型的優缺點

1優點:

(1):本模型從正多邊形引入,然後以正多邊為基礎,通過用正多邊形的外接圓去覆蓋矩形,這樣更清晰明了的點出該問題的求解方案。

(2):本模型採用正三角形、正方形、正六邊形的外接圓,最後經過計算、篩選建立出以正方形、正六邊形為基礎的模型i、ii,並用matlab軟體程式設計,計算出最優結果,使得該問題求解簡單、明了。

(3):模型中採用大量的圖形,更加直觀、清晰展現出求解該問題的過程,更具有說服性。

缺點(1):建立的模型太過理想化,模型i、ii都只是用單一的正多邊形外接圓去覆蓋矩形,沒有採用多種正多邊形的組合去覆蓋矩形,假如用正三角形和正方形,或者正六邊形與正三角形去覆蓋矩形,然後用兩個圖形的外接圓去覆蓋矩形區域,會不會減少圓使用的個數呢?這是乙個新的想法,程式設計可能更複雜,這裡就沒有考慮。

二、模型的推廣

該本模型針提出了如何用最少的圓去覆蓋矩形區域,並且兩個圓的相交部分的面積不小於k%,針對這一問題我們建立了最優化模型,這樣減少了圓的使用個數,更加節省了資源。在以後的地磚鋪設、牆面粉飾等裝修領域均可以使用。可以高效節省資源。

八參考文獻

(1) 赫孝良戴永紅周義倉 .數學建模競賽賽題簡析與**點評.西安.西安交通大學出版社.2002

(2) 趙靜但琦,數學建模與數學實驗,高等教育額出版社.2008

(3) 馬俊華.數學通報.中學數學月刊.2006

附錄附錄1

證明只有正三角形、正方形、正六邊形可以覆蓋矩形

正多邊形的定義各邊相等,各角也相等的多邊形叫做正多邊形

若要用同一種多正多形鑲嵌平面圖形,則應該密鋪(圖形與圖形之間沒有空隙)正多邊形的乙個內角能被360整除就可以

k= (k表示正多邊形內角度數,n表示正多邊形邊數)

n 通過計算得n為3、4、6。所以只有正三角形、正方形、正六邊形可以進行平面鑲嵌。即選擇以上三種圖形覆蓋矩形.

附錄2function count=t(m,n,r)

%m*n的矩陣用半徑為r的圓覆蓋,相鄰相交圓相交得的面積不小於圓面積的k%求圓的個數

m=input('輸入矩陣的長度m=');

n=input('輸入矩陣的寬度n=');

r=input('輸入圓的半徑r=');

k=input('輸入相鄰相交圓的相交面積與圓面積的百分比 k=');

k=k/100;

disp(['m=',num2str(m),' n=',num2str(n),' r=',num2str(r),' k=',num2str(k)])

disp('');

format long;

%當用正三角形覆蓋時求k的值

k1=(1/2*r^2*2*pi/3-1/2*r^2*1/2*sqrt(3))*2/(pi*r^2);

%當用正方形覆蓋時求k的值

k2=(1/2*r^2*pi/2-1/2*r^2)*2/(pi*r^2);

%當用正六邊形覆蓋時求k的值

k3=(1/2*r^2*pi/3-1/2*r*sqrt(3)*r/2)*2/(pi*r^2);

disp(['三角形覆蓋k1=',num2str(k1),' 正方形覆蓋k2=',num2str(k2),' 正六邊形覆蓋k3=',num2str(k3)]);

z=sqrt(m^2+n^2)/2;

if r>=z

count=1;

disp(count);break;

else

if abs(k-k2)>abs(k-k3)

disp('此時用正六邊形覆蓋矩形。');

v1=m/3/r-floor(m/3/r);

if v1==0

a1=2*m/3/r; %a1為矩形長所包含的正六邊形個數

endif v1<1/3|v1==1/3

a1=floor(2*m/3/r)+1;

1 50000區域地質調查專案設計編寫要求

2 有關1 50000區域地質調查的標準及技術要求 1 dz t0001 區域地質調查總則 1 50000 2 zb t d10004 城市地區區域地質調查工作技術要求 1 50000 3 gb t14158 區域水文地質工程地質環境地質綜合勘查規範 1 50000 4 dz t0158 淺覆蓋區區...

2019區域分析與規劃實驗

區域分析與規劃課程實驗 華北水利水電大學資源與環境學院 2015年11月 實驗一 一 題目 河南省區域發展水平綜合評價和分割槽規劃 二 目的 運用教材所學的區域發展的指數評價的方法 參照教材37 40頁,156 158頁 對河南省2006和2011年區域發展綜合水平進行評價,學習並掌握綜合指標體系方...

2019屆高三二輪複習專題9區域空間定位

根據所學知識並結合下圖,回答1 3題 1 圖 地區可重點發展的經濟作物是 a 棉花 b 黃麻 c 甘蔗 d 天然橡膠 2 與圖 地區相比,圖 地區農業生產的優勢條件是 a 水源充足 b 熱量充足 c 土壤肥沃 d 地勢平坦 3 圖 中兩地區在國土整治方面應重點做好的工作是 a 治理水土流失 b 防治...