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

程安祺

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

【關(guān)鍵詞】變電站選址 最小覆蓋圓 點(diǎn)集覆蓋 圓內(nèi)四邊形 覆蓋 凸包

【中圖分類號】TM63 【文獻(xiàn)標(biāo)識碼】A 【文章編號】2095-3089（2017）01-0243-03

本文主要工作如下：

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

2.對比平面區(qū)域圓覆蓋與平面點(diǎn)集圓覆蓋，通過點(diǎn)集覆蓋尋求較優(yōu)解；

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

4.分析并使用一些數(shù)學(xué)結(jié)論，比如：若一個圓能夠覆蓋一個區(qū)域內(nèi)的所有點(diǎn)，則一定能夠覆蓋這些點(diǎn)構(gòu)成的凸包；用幾何方法求出單位圓內(nèi)最大四邊形為圓內(nèi)接四邊形。尋求平面點(diǎn)集最小圓覆蓋方法。

在城市電網(wǎng)規(guī)劃中，變電站選址直接影響到未來電力系統(tǒng)的網(wǎng)絡(luò)結(jié)構(gòu)、供電質(zhì)量和運(yùn)行經(jīng)重要。針對信號是否能夠全面覆蓋以及浪費(fèi)面積的計(jì)算，構(gòu)建成本函數(shù)，從而得到最佳的選址方案。

1.構(gòu)建鋪設(shè)成本和功率模型

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

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

計(jì)算時(shí)不妨令k1=k2=k3=1，最后成本函數(shù)為：

2.將區(qū)域覆蓋問題轉(zhuǎn)化為平面點(diǎn)集覆蓋問題

由于平面區(qū)域的最小圓覆蓋問題是NP問題。因此，我們不可能給出令人滿意的結(jié)果。考慮到在實(shí)際應(yīng)用中，變電站覆蓋也不需要區(qū)域某個地區(qū)全部的點(diǎn)，只需要覆蓋某些小區(qū)、寫字樓等集中用電區(qū)。所以我們將區(qū)域覆蓋問題轉(zhuǎn)化為平面點(diǎn)集的覆蓋，將集中用電區(qū)抽象為平面上的點(diǎn)。

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

2.1 假定m=1

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

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

b）n=2，變電站應(yīng)放在A、B兩點(diǎn)中點(diǎn)處，覆蓋區(qū)域半徑為AB/2；

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

圖1-1

當(dāng)△ABC為鈍角三角形時(shí)，通過幾何畫板可得其最小覆蓋圓為鈍角所對邊為直徑的圓。不妨設(shè)AB邊。為最長邊，變電站應(yīng)放在A、B兩點(diǎn)中點(diǎn)處，覆蓋區(qū)域半徑為AB/2，如圖1-2

圖1-2

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

當(dāng)四邊形ABCD為凸四邊形時(shí)不妨設(shè)∠D+∠B≥∠A+ ∠C且∠B≥∠D，此時(shí)△ACD的最小覆蓋圓為四邊形ABCD的最小覆蓋圓。

2.2 假定m=2

a）引理：若一個圓O能夠覆蓋區(qū)域S內(nèi)的所有點(diǎn)，則圓O一定能覆蓋S的凸包。

證明：

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

通過這個結(jié)論我們可以看到，限定條件為只使用一個圓覆蓋時(shí)，平面區(qū)域覆蓋與平面點(diǎn)集覆蓋有某種統(tǒng)一性。這也說明本文考慮點(diǎn)集覆蓋問題的合理性。

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

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

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

證明：

因?yàn)椤螩BA為鈍角，所以點(diǎn)B在圓O1內(nèi)，因此△ABC在圓O1內(nèi)，同理，△CDE在圓O2內(nèi)。若∠CEA為鈍角，則點(diǎn)E在圓O1內(nèi)，因此△CAE在圓O1內(nèi)；若∠CAE，∠CEA均為銳角，則過C作線段AE的垂線，設(shè)垂足為F，易知△CAF在圓O1內(nèi)，△CEF在圓O2內(nèi)。

當(dāng)有且僅有∠A，∠C為銳角時(shí)，連接AC，然后選取AD與CE中較短的線段，不妨設(shè)AD

證明：

因?yàn)椤螦BD為鈍角，所以點(diǎn)B圓O1內(nèi)，因此△ABC在圓O1內(nèi)，同理，△ADE在圓O2內(nèi)。若∠ADC為鈍角時(shí)，點(diǎn)D在圓O1內(nèi)，因此△ADC在圓O1內(nèi)；若∠ADC為銳角時(shí)，過A作線段CD的垂線，設(shè)垂足為F，易知，△ACF在圓O1內(nèi)，△ADF在圓O2內(nèi)。

2.3 回到區(qū)域覆蓋問題

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

（1）當(dāng)m=1時(shí)，如何在半徑為1的圓O內(nèi)放置一個四邊形ABCD，使其面積最大？

解：

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

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

3.經(jīng)測量，此時(shí)A`B`C`D`為正方形，其面積應(yīng)為2。

（2）當(dāng)m=1時(shí)，如何在半徑為1的圓O內(nèi)放置一個n邊形，使其面積最大？

本文提出假設(shè)：圓內(nèi)n邊形面積最大時(shí)為圓內(nèi)接正n邊形。

3.待解決的問題

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

2）點(diǎn)集覆蓋問題中，若考慮更復(fù)雜的問題，比如n>5，m>2情況下，較優(yōu)的解答

參考文獻(xiàn)：

[1]楊麗徙，陳慶文，王玲.基于最小覆蓋圓的配電網(wǎng)變電站優(yōu)化選址[J].電力系統(tǒng)及其自動化學(xué)報(bào)，2008，20（2）：73-77.

[2]楊中華.平面點(diǎn)列最小覆蓋圓的計(jì)算方法[J].北京工業(yè)大學(xué)學(xué)報(bào)，2006，26（2）：96-97.

[3]魏寧初.最小覆蓋圓問題及應(yīng)用[J].寧波教育學(xué)院學(xué)報(bào)，2010，12（2）：123-124.

[4]陳琦，陳計(jì).凸圖形和覆蓋問題[J].中學(xué)數(shù)學(xué)（湖北），1994，3：33-36.

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

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

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

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