徐文洋，劉光宇，余善恩

(1.杭州電子科技大學(xué)理學(xué)院，浙江 杭州 310018；

2.杭州電子科技大學(xué)自動(dòng)化學(xué)院，浙江 杭州 310018)

?

圓形區(qū)域中分散布局問題的研究

徐文洋1，劉光宇2，余善恩2

(1.杭州電子科技大學(xué)理學(xué)院，浙江 杭州 310018；

2.杭州電子科技大學(xué)自動(dòng)化學(xué)院，浙江 杭州 310018)

摘要：圓形區(qū)域分散布局問題是一類常見的數(shù)學(xué)問題，在區(qū)域分散布局的科學(xué)研究中占據(jù)了重要的位置。針對(duì)該類問題，文中建立了兩個(gè)布局模型，分別為基于目標(biāo)函數(shù)最小距離最大化的布局模型、基于對(duì)數(shù)函數(shù)懲罰性特點(diǎn)的分散布局模型。結(jié)合圓形布局區(qū)域的對(duì)稱性與布局模型，得到了兩個(gè)布局相關(guān)的基本結(jié)論，并給出了證明。實(shí)例求解表明，采用了序列二次型規(guī)劃方法得出的數(shù)值結(jié)果與理論吻合。

關(guān)鍵詞：分散布局；規(guī)劃模型；圓形區(qū)域

0引言

在日常生活中，為了美化環(huán)境、改善空氣質(zhì)量、提高人民的生活品質(zhì)，人們將大小不一的圓形花壇布置在十字路口、草坪和廣場(chǎng)等公共設(shè)施中?；▔胁粌H布置了五顏六色的花卉，還種植了小型灌木。特別是小型灌木的布置對(duì)花壇的美觀性、空氣質(zhì)量及花壇采光性的改善度起到了十分重要的作用。本文將小型灌木在花壇中的合理布局問題歸結(jié)為一類非線性規(guī)劃模型的求解問題。查閱文獻(xiàn)資料發(fā)現(xiàn)圓形區(qū)域分散布局問題和選址問題[1-3]有相似之處，尤其是選址問題中的最大覆蓋問題[4-6]，它和圓形區(qū)域分散布局問題尤為相似。然而，二者也存在一些有區(qū)別：最大覆蓋問題通常會(huì)給出一些備選的布局點(diǎn)，從備選的布局點(diǎn)中選出一部分作為實(shí)際布局點(diǎn)，而圓形區(qū)域分散布局問題[7]的布局點(diǎn)可以在布局區(qū)域內(nèi)任意選擇。由于布局點(diǎn)在布局區(qū)域中的位置不確定，故難以計(jì)算任意兩布局點(diǎn)間的實(shí)際距離，這很大程度地增加了問題的求解難度。為此，本文建立了兩個(gè)數(shù)學(xué)規(guī)劃模型，并提出了兩個(gè)相關(guān)布局定理，用于解決該類分散布局的數(shù)學(xué)問題。

1模型建立

在給出布局模型之前，首先闡述一下“分散”在文中所指的意義。所謂“分散”就是指任意兩個(gè)布局點(diǎn)間的距離盡可能地大，而“均勻分散”則是在分散的基礎(chǔ)上，要求任意相鄰布局點(diǎn)間的距離盡可能地相等，“均勻分散”在布局區(qū)域中的布局結(jié)果會(huì)比較勻稱和美觀。

1.1　建模基礎(chǔ)

為了建立圓形區(qū)域分散布局模型，下面給出文中數(shù)學(xué)符號(hào)的意義說明及定義。

pi(xi,yi)：布局點(diǎn)pi的坐標(biāo),其中xi為橫坐標(biāo),yi為縱坐標(biāo)。

r：圓形布局區(qū)域的半徑。

n：布局區(qū)域中布局點(diǎn)的總數(shù)。

E：標(biāo)集，E={1,2,…,n}。

為了研究圓形區(qū)域最大分散化布局問題，給出如下定義：

引理1[8]在圓的所有內(nèi)接多邊形中，正多邊形的周長(zhǎng)最長(zhǎng)，面積最大；且隨著邊數(shù)n的增多而增大，當(dāng)n趨于無窮時(shí)，它們分別趨向圓的周長(zhǎng)與面積。

1.2　布局模型

以圓形布局區(qū)域中心為坐標(biāo)原點(diǎn)，建立平面直角坐標(biāo)系，分析布局點(diǎn)在布局區(qū)域中的布局約束條件，得出如下優(yōu)化布局模型。

1)基于最小距離最大化的布局模型1

(1)

模型1是以最近兩個(gè)布局點(diǎn)間距最大化為目標(biāo)函數(shù)的非線性規(guī)劃模型，所有布局點(diǎn)中任意兩個(gè)布局點(diǎn)間的距離一定不小于最近的兩個(gè)布局點(diǎn)間的距離。因此，模型1取得最優(yōu)解時(shí)，布局點(diǎn)在圓形布局區(qū)域中必然是分散布局的。此外，模型1必有可行解。事實(shí)上，將圓形布局區(qū)域邊界n等分，則布局區(qū)域邊界的n個(gè)等分點(diǎn)就構(gòu)成了模型1的一個(gè)可行解。當(dāng)布局區(qū)域僅為區(qū)域邊界時(shí)，由引理1可知布局點(diǎn)在邊界上均勻分布時(shí)，布局方案具有最大的分散度，這時(shí)布局方案也是最優(yōu)布局方案。

2)基于自然對(duì)數(shù)函數(shù)懲罰性的布局模型2

(2)

模型2是以自然對(duì)數(shù)的和函數(shù)為目標(biāo)函數(shù)的規(guī)劃模型，由自然對(duì)數(shù)函數(shù)的單調(diào)性可知，模型2取得最優(yōu)解時(shí)，任意兩個(gè)布局點(diǎn)都會(huì)盡可能的分散。另一方面，對(duì)數(shù)函數(shù)還具有懲罰性,要求布局區(qū)域中相鄰的布局點(diǎn)間的距離dij,djk(i,j,k∈E)等。

模型1和模型2的目標(biāo)函數(shù)不同，模型1僅考慮使布局點(diǎn)在布局區(qū)域中最大程度的分散，而未考慮布局后的對(duì)稱性和美觀性。模型2利用了自然對(duì)數(shù)的單調(diào)性和懲罰性，兼顧了布局的分散性和均勻性。因此，模型2理論上布局效果會(huì)比較均勻。進(jìn)一步，由于兩個(gè)布局模型均存在可行解，并且布局區(qū)域和目標(biāo)函數(shù)均有上界(2r)，故兩個(gè)布局模型均存在最優(yōu)解。此外，參考文獻(xiàn)[9]對(duì)該類模型最優(yōu)解的存在性給出了詳細(xì)的證明。

定理1布局點(diǎn)數(shù)n大于1時(shí).圓形區(qū)域分散布局問題至少存在一個(gè)最優(yōu)解，該最優(yōu)解中至少有一個(gè)布局點(diǎn)分布在布局區(qū)域邊界上。

定理2布局點(diǎn)數(shù)n大于6時(shí)，圓形區(qū)域分散布局問題至少存在一個(gè)最優(yōu)解，該最優(yōu)解中至少有一個(gè)布局點(diǎn)分布在布局區(qū)域內(nèi)部。

2實(shí)例分析

在R2空間中，以布局區(qū)域中心為坐標(biāo)原點(diǎn)，地理正東與正北方向分別為x，y軸正方向，建立直角坐標(biāo)系。取布局區(qū)域半徑r=5m，使用序列二次規(guī)劃(SQP)方法，在Matlab軟件中通過編程求解模型結(jié)果如圖1所示。

圖1　模型求解結(jié)果

圖1中，當(dāng)布局點(diǎn)數(shù)n超過6時(shí)，兩個(gè)布局模型的求解結(jié)果中都至少有一個(gè)布局點(diǎn)落在區(qū)域的內(nèi)部。模型1的求解結(jié)果在n=8時(shí)，有兩個(gè)布局點(diǎn)落在區(qū)域內(nèi)部，而模型2只有一個(gè)布局點(diǎn)落在區(qū)域內(nèi)部。此時(shí)，模型1與模型2求解布局方案的分散度分別為0.712和0.868。由于SQP方法對(duì)布局模型初始解的選取有很強(qiáng)的依賴性，初始解微小變化可能會(huì)對(duì)算法的迭代次數(shù)產(chǎn)生很大的影響，從而影響計(jì)算時(shí)間。此外，通過試驗(yàn)發(fā)現(xiàn)，當(dāng)布局點(diǎn)數(shù)不超過15時(shí)，使用SQP方法求解模型1的計(jì)算時(shí)間多于模型2的計(jì)算時(shí)間；當(dāng)布局點(diǎn)數(shù)較多時(shí)，使用SQP方法求解模型1的計(jì)算時(shí)間少于模型2的計(jì)算時(shí)間，具體比較如表1所示。

表1　不同布局點(diǎn)下兩類模型計(jì)算時(shí)間比較　s

表1中，當(dāng)布局點(diǎn)數(shù)分別為12和18時(shí)，模型1與模型2的計(jì)算時(shí)間最大，是由于這時(shí)算法迭代次數(shù)最多，分別為40次和96次。此外，一般情況下SQP方法求解模型得到的只是局部最優(yōu)解，且其對(duì)初始解有很強(qiáng)的依賴性。因此，要徹底解決圓形區(qū)域分散布局問題需要改進(jìn)原有的一些方法或提出新的解法。

3結(jié)束語

本文建立了圓形區(qū)域分散布局?jǐn)?shù)學(xué)模型，給出了詳細(xì)的問題描述及相關(guān)布局結(jié)論，并結(jié)合實(shí)例驗(yàn)證了利用模型布局的合理性，為圓形區(qū)域分散布局提供了理論依據(jù)，但未能給出模型的求解方法，故圓形區(qū)域分散布局問題有待進(jìn)一步完善。

參考文獻(xiàn)

[1] 蔡麗艷.不確定性物流中心選址問題研究[J].物流科技,2013，36(6)：64-68.

[2]從峰，耿娜，顧一韜，等.確定需求下的家庭護(hù)理中心網(wǎng)絡(luò)選址問題研究[J].工業(yè)工程與管理,2013,18(1)：41-45.

[3]陳明.基于空間連續(xù)需求的最大覆蓋選址模型及應(yīng)用[J].物流技術(shù),2014,33 (3),169-175.

[4]王維，蘇經(jīng)宇，馬東輝，等.城市避震疏散場(chǎng)所選址的時(shí)間滿意覆蓋模型[J].上海交通大學(xué)學(xué)報(bào),2014,48(1):154-158.

[5]Sturdy I,Kincaid R.The Robust Maximum-Coverage Problem[C]//Systems and InFormation Engineering Design Symposium (SIEDS),2014.Charlottesville：IEEE,2014:38-41.

[6]Fan X,Li V O K.The probabilistic maximum coverage problem in social networks[C]//Global Telecommunications ConFerence (GLOBECOM 2011),2011 IEEE.Houston：IEEE,2011:1-5.

[7]Wang Y,Shi Y,Teng H.Scatter Search For Constrained Layout Optimization Problem[C]//Natural Computation,2007.ICNC 2007.Third International ConFerence on.Haikou：IEEE,2007:100-104.

[8]李潔.“割圓術(shù)”蘊(yùn)涵的兩個(gè)結(jié)論[J].中學(xué)數(shù)學(xué)研究,2007,(10)：18-19.

[9]宋永明.無窮維規(guī)劃最優(yōu)解的存在性[J].成都大學(xué)學(xué)報(bào)(自然科學(xué)版),2008,27(1)：28-29.

Research oF the Scattered Layout Problem in Circular Zone

Xu Wenyang1， Liu Guangyu2， Yu Shanen2

(1.SchooloFScience，HangzhouDianziUniversity，HangzhouZhejiang310018，China;

2.SchooloFAutomation，HangzhouDianziUniversity，HangzhouZhejiang310018，China)

Abstract:Scattered layout problem is a class oF common mathematical problem in the Field oF decentralized layout scientiFic research occupied an important position. To solve such problems， we established two decentralized layout programming models. The one is based on the principle oF Max Min， the other is on the basis oF the penalty property oF logarithmic Function. There are two relevant conclusions be proposed through the analysis oF the layout models and proved in detail. With concreted examples， the results using SQP method derived are consistent with the theoretical. ThereFore， the programming models and theories presented in this paper possessed important guiding signiFicance oF actual dispersed layout problems．

Key words:scattered layout; programming model; circular area

中圖分類號(hào)：O221

文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1001-9146(2015)03-0093-04

通信作者:

作者簡(jiǎn)介：徐文洋(1989-)，男，安徽亳州人，在讀研究生，優(yōu)化理論與應(yīng)用.劉光宇教授,E-mail: g.liu@hdu.edu.cn.

收稿日期：2014-09-18

DOI:10.13954/j.cnki.hdu.2015.03.020