圓排列包裝問題最優(yōu)解解析

楊金勇，宋海洲

（華僑大學(xué) 數(shù)學(xué)科學(xué)學(xué)院，福建 泉州362021）

近年來，組合優(yōu)化問題引起越來越多的關(guān)注，如文獻(xiàn)［1］用混合遺傳算法求解0-1背包問題，文獻(xiàn)［2］用蟻群算法解決TSP問題，文獻(xiàn)［3-6］用回溯法、蟻群算法求解圓排列問題.目前，圓排列研究得最多的問題是如何求解最小長度，然而，在生產(chǎn)生活中也會遇到下面這種情況，生產(chǎn)統(tǒng)一大小的盒子，要求這種盒子能夠裝下以任何一種排列順序排進(jìn)該盒子的n個大小不全相等的圓，且盒子長度盡可能的小.本文把這種問題稱為圓排列包裝問題，并對此進(jìn)行研究.

1 圓排列包裝問題的數(shù)學(xué)模型

圓排列包裝問題描述為找一個矩形框，將n個大小不全相等的圓以任何一種排列順序排進(jìn)該矩形框后，都能保證這n個圓與矩形的底邊相切，且要求這種矩形框長度最小.

下面給出一些集合和相關(guān)長度的定義.

定義1 給定n個圓C1，…，Cn，其圓心的橫坐標(biāo)分別為x1，x2，…，xn，半徑分別為R1，R2，…，Rn，R1≤R2≤…≤Rn，且R1＜Rn.定義下面4個的集合S，T，Q，P.

1）S＝｛w｜（w＝i1，i2，…，in）為1，…，n的n級排列｝.

2 圓排列包裝問題的最優(yōu)解的性質(zhì)

定理1 模型（2）中的所有最優(yōu)解中必存在一個最優(yōu)解l，使得該最優(yōu)解對應(yīng)的圓排列的圓心的橫坐標(biāo)構(gòu)成的向量屬于L.

圖1 圓排列Fig.1 Circle permutation

綜上所述，假設(shè)不成立，故定理得證.

3 模型的轉(zhuǎn)化及求解

由定理1可知：集合T必存在模型（2）的一個最優(yōu)解l，使得對應(yīng)圓心的橫坐標(biāo)向量（xk1，xk2，…，xkn）∈T.因此，對模型（2）可進(jìn)一步轉(zhuǎn)化為

對于模型（3），得到了如下主要結(jié)果.

定理2l＝（n，n-1，n-2，…，3，2，1）為模型（3）的一個最優(yōu)解.

為了證明定理2，先求解下面的模型，即

其中：a1≤a2≤…≤an，a1＜an.

對于模型（4），有如下定理.

定理3l＝（n，n-1，n-2，…，3，2，1）為模型（4）的一個最優(yōu)解.

為了證明定理3，先給出一些引理及定義.

易證如下3個引理成立：

由命題2及命題3易知定理2成立.

4 應(yīng)用舉例

［1］ 宋海洲，魏旭真.求解0-1背包問題的混合遺傳算法［J］.華僑大學(xué)學(xué)報：自然科學(xué)版，2006，27（1）：17-19.

［2］ 徐強，宋海洲，田朝薇.解TSP問題的蟻群算法及其收斂性分析［J］.華僑大學(xué)學(xué)報：自然科學(xué)版，2011，32（5）：589-591.

［3］ 王曉東.計算機(jī)算法設(shè)計與分析［M］.北京：電子工業(yè)出版社，2001：179-181.

［4］ 高尚，楊靖宇，吳曉俊，等.圓排列問題的蟻群模擬退火算法［J］.系統(tǒng)工程理論與實踐，2004（8）：102-106.

［5］ 章義剛，賈瑞玉，張燕平，等.快速蟻群算法求解圓排列問題［J］.計算機(jī)技術(shù)與發(fā)展，2007，17（8）：48-50.

［6］ 章義剛，王會穎.改進(jìn)蟻群算法求解圓排列問題［J］.機(jī)電工程，2008，25（5）：92-95.