圓排列包裝問題最優解解析

楊金勇，宋海洲

（華僑大學 數學科學學院，福建 泉州362021）

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

1 圓排列包裝問題的數學模型

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

下面給出一些集合和相關長度的定義.

定義1 給定n個圓C1，…，Cn，其圓心的橫坐標分別為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 圓排列包裝問題的最優解的性質

定理1 模型（2）中的所有最優解中必存在一個最優解l，使得該最優解對應的圓排列的圓心的橫坐標構成的向量屬于L.

圖1 圓排列Fig.1 Circle permutation

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

3 模型的轉化及求解

由定理1可知：集合T必存在模型（2）的一個最優解l，使得對應圓心的橫坐標向量（xk1，xk2，…，xkn）∈T.因此，對模型（2）可進一步轉化為

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

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

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

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

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

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

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

易證如下3個引理成立：

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

4 應用舉例

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

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

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

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

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

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