用覆蓋問題解決變電站選址的探究

程安祺

【摘要】隨著我國城市配電網改造的快速發展，變電站的重要性同樣不可忽略，尋求變電站布置最佳方案有重要的意義。變電站的位置對電力系統的網絡結構有決定性作用，起到承上啟下的作用，關系到電網的經濟性與穩定性。不合理的站點選址不僅可能會造成某些地方出現覆蓋盲區或容量不足的情況，還會增加網絡建設的成本。變電站選址時需要考慮的因素非常復雜，需要綜合地理環境、物質資源、經濟協助、人力資源、信號覆蓋等多方面問題，本文將變電站選址問題抽象為數學模型，經過綜合考慮后，將地理環境（如：樓房阻礙、海拔落差、溫度、濕度等）忽略，將物質資源、經濟協助與人力資源統一為經濟成本，信號覆蓋方面考慮是否全部覆蓋及浪費的面積，忽略信號的衰弱及額定功率，構建成本函數，對成本進行最優化設計。

【關鍵詞】變電站選址 最小覆蓋圓 點集覆蓋 圓內四邊形 覆蓋 凸包

【中圖分類號】TM63 【文獻標識碼】A 【文章編號】2095-3089（2017）01-0243-03

本文主要工作如下：

1.將變電站選址問題抽象為平面區域的圓覆蓋問題；

2.對比平面區域圓覆蓋與平面點集圓覆蓋，通過點集覆蓋尋求較優解；

3.對一些簡單情況，比如點集個數n=3，4，5，覆蓋圓個數m=1，2等，利用成本函數判斷不同類型下變電站位置及覆蓋半徑；

4.分析并使用一些數學結論，比如：若一個圓能夠覆蓋一個區域內的所有點，則一定能夠覆蓋這些點構成的凸包；用幾何方法求出單位圓內最大四邊形為圓內接四邊形。尋求平面點集最小圓覆蓋方法。

在城市電網規劃中，變電站選址直接影響到未來電力系統的網絡結構、供電質量和運行經重要。針對信號是否能夠全面覆蓋以及浪費面積的計算，構建成本函數，從而得到最佳的選址方案。

1.構建鋪設成本和功率模型

變電站鋪設時，需要考慮鋪設成本與功率兩個方面。若忽略鋪設成本而只考慮最小化功率，則只需在每個負荷點附近鋪設一個變電站即可，顯然，這種方案是不現實的。因此，不難看出變電站的鋪設成本與功率相制約。

設C為總成本，c為每個變電站的成本，m為變電站的個數，s為浪費的面積（變電站總覆蓋面積減去需要覆蓋的面積，包括重復覆蓋面積及無用覆蓋面積），s0為待覆蓋區域的面積，r為每個變電站覆蓋區域的半徑，為每個變電站的材料成本（與r2成正比），c2為每個變電站的人員工資、運輸費用等（與r成正比），k1為浪費面積與成本之間的比例系數，k2為變電站半徑與材料成本的之間的比例系數，k3為變電站半徑與人員工資、運輸費用等之間的比例系數。

計算時不妨令k1=k2=k3=1，最后成本函數為：

2.將區域覆蓋問題轉化為平面點集覆蓋問題

由于平面區域的最小圓覆蓋問題是NP問題。因此，我們不可能給出令人滿意的結果?？紤]到在實際應用中，變電站覆蓋也不需要區域某個地區全部的點，只需要覆蓋某些小區、寫字樓等集中用電區。所以我們將區域覆蓋問題轉化為平面點集的覆蓋，將集中用電區抽象為平面上的點。

本文考慮某個地區范圍內需要供電的n個負荷點U={u1，u2，…un}，用最小圓區覆蓋這n個點。本文從簡單情況做起，考慮m=1，2，即用一個或兩個圓覆蓋區域上的n個點。

2.1 假定m=1

此時s0等于0，易知，r越小，總成本C越小

a）n=1，只需將變電站放在這個點A處即可；

b）n=2，變電站應放在A、B兩點中點處，覆蓋區域半徑為AB/2；

c）n=3，文獻3中已經給出詳細證明，這里本文使用幾何畫板軟件給出圖像，證明過程不再重復。當△ABC為銳角三角形時，通過幾何畫板可得 最小覆蓋圓是它的外接圓；變電站應放在△ABC的外心O處，覆蓋區域半徑為OA，如圖1-1。

圖1-1

當△ABC為鈍角三角形時，通過幾何畫板可得其最小覆蓋圓為鈍角所對邊為直徑的圓。不妨設AB邊。為最長邊，變電站應放在A、B兩點中點處，覆蓋區域半徑為AB/2，如圖1-2

圖1-2

d）n=4，類似地，文獻3中已經給出詳細證明，這里本文使用幾何畫板軟件給出圖像，證明過程不再重復。當四邊形ABCD為凹四邊形時，不妨設∠ABC>180°，此時△ACD的最小覆蓋圓即為四邊形ABCD的最小覆蓋圓，變電站應放在△ABC的外心O處，覆蓋區域半徑為OA，通過幾何畫板比較容易得到，如圖1-3，1-4

當四邊形ABCD為凸四邊形時不妨設∠D+∠B≥∠A+ ∠C且∠B≥∠D，此時△ACD的最小覆蓋圓為四邊形ABCD的最小覆蓋圓。

2.2 假定m=2

a）引理：若一個圓O能夠覆蓋區域S內的所有點，則圓O一定能覆蓋S的凸包。

證明：

取S凸包上的定點為A1，A2，……，An，……，不妨設OA1為OAn中最大的一項，OA2為次大的一項，取A1A2所在直線為l，過O作l的垂線交l于BOB≤max{OA1，OA2}，因此B在圓O內，因此凸包內的所有點均在圓O內，如圖2-1，2-2

通過這個結論我們可以看到，限定條件為只使用一個圓覆蓋時，平面區域覆蓋與平面點集覆蓋有某種統一性。這也說明本文考慮點集覆蓋問題的合理性。

b）m=2，n=5（這五個點A，B，C，D，E構成凸五邊形，且順時針排列）當∠A，∠B，∠C，∠D，∠E均為鈍角時，取一點，使得該點與兩個不相鄰兩點的距離之和最小，不妨設該點為A，則變電站1應放在AC中點O1處，覆蓋區域半徑為O1A，變電站2應放在AD中點O2處，覆蓋區域半徑為O2A，如圖2-3-1，2-3-2，2-3-3

證明：因為∠ABC為鈍角，所以B在以AC為直徑的圓O1內，所以△ABC在圓O1內，同理，E在以AD為直徑的圓O2內，所以△ADE在圓O2內。若∠ACD為鈍角，則C在圓O2內，則△ACD在圓O2內，同理；若∠ADC為鈍角，則D在圓O1內，則△ACD在圓O1內；若∠ACD與∠ADC均為銳角，則過A作CD的垂線交于F，△ACF在圓O1中，△ADF在圓O2中，此時△ACD包含在圓O1與圓O2中。因此圓O1和圓O2能夠覆蓋五邊形ABCDE。

當有且僅有∠A為銳角時，取一點（C或D），使得該點與兩個不相鄰定點的距離之和最小，分別連接該點與不相鄰兩點，取中點分別為O1，O2，其余同上，如圖2-4-1，2-4-2

證明：

因為∠CBA為鈍角，所以點B在圓O1內，因此△ABC在圓O1內，同理，△CDE在圓O2內。若∠CEA為鈍角，則點E在圓O1內，因此△CAE在圓O1內；若∠CAE，∠CEA均為銳角，則過C作線段AE的垂線，設垂足為F，易知△CAF在圓O1內，△CEF在圓O2內。

當有且僅有∠A，∠C為銳角時，連接AC，然后選取AD與CE中較短的線段，不妨設AD

證明：

因為∠ABD為鈍角，所以點B圓O1內，因此△ABC在圓O1內，同理，△ADE在圓O2內。若∠ADC為鈍角時，點D在圓O1內，因此△ADC在圓O1內；若∠ADC為銳角時，過A作線段CD的垂線，設垂足為F，易知，△ACF在圓O1內，△ADF在圓O2內。

2.3 回到區域覆蓋問題

既然一般的區域覆蓋問題是NP問題，本文逆向思考這個問題。將至轉化為給定一系列圓的位置，求它可以覆蓋的區域的面積的最大值。這里為方便起見，區域去成凸多邊形。

（1）當m=1時，如何在半徑為1的圓O內放置一個四邊形ABCD，使其面積最大？

解：

1.若A，B，C，D四個點不都在圓O上，則可將該點與半徑的連線平移到圓O上，必會使四邊形ABCD面積變大，如圖3-1，此后A，D均指代在圓上的對應點

2.連接AC，將四邊形ABCD劃分為△ABC和△ACD，它們均以AC為底邊，要想使面積更大，應增大兩個三角形的高。過O作AC垂線交圓于B`，D`，連接AB`，CB`，AD`，CD`，如圖3-2

3.經測量，此時A`B`C`D`為正方形，其面積應為2。

（2）當m=1時，如何在半徑為1的圓O內放置一個n邊形，使其面積最大？

本文提出假設：圓內n邊形面積最大時為圓內接正n邊形。

3.待解決的問題

1）如何證明：半徑為1的圓O內最大面積的n邊形是正n邊行

2）點集覆蓋問題中，若考慮更復雜的問題，比如n>5，m>2情況下，較優的解答

參考文獻：

[1]楊麗徙，陳慶文，王玲.基于最小覆蓋圓的配電網變電站優化選址[J].電力系統及其自動化學報，2008，20（2）：73-77.

[2]楊中華.平面點列最小覆蓋圓的計算方法[J].北京工業大學學報，2006，26（2）：96-97.

[3]魏寧初.最小覆蓋圓問題及應用[J].寧波教育學院學報，2010，12（2）：123-124.

[4]陳琦，陳計.凸圖形和覆蓋問題[J].中學數學（湖北），1994，3：33-36.

[5]蔡歷亮.多邊形最小覆蓋圓的確定方法[J].中小學數學（初中版），2011，6：33-36.

[6]陳慶文.基于最小覆蓋圓及頂點加權V圖的變電站優化選址研究[D]，河南：鄭州大，2007.

[7]周學光.世界奧林匹克解題大辭典（組合卷）[M].河北：河北少年兒童出版社.2012：848-854，915.

[8]田廷彥.組合幾何（數學奧林匹克命題人講座）.上海：上海科技教育出版社.2010：73，76.