圆排列包装问题最优解解析.pdf

《圆排列包装问题最优解解析.pdf》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、第34卷第2期华侨大学学报(自然科学版)V0L34No．22013年3月JournalofHuaqiaoUniversity(NaturalScience)Mar．2013文章编号：1000-5013(2013)02-0220—05圆排列包装问题最优解解析杨金勇，宋海洲(华侨大学数学科学学院，福建泉州362021)摘要：研究圆排列包装问题，给出该问题的数学模型及其简化形式．通过研究圆排列包装问题的最优解的性质，将该问题的数学模型进一步转化为一个较易求解的数学模型，并给出一个关于其最优解的定理和证明．该定理表明：按半径大小降序排列且两两相切的圆排列为圆排列包装问题的一个最优圆排列．关键词：圆排列

2、；包装问题；两两相切；顺序排列；反向操作中图分类号：O157文献标志码：A近年来，组合优化问题引起越来越多的关注，如文献[1]用混合遗传算法求解O一1背包问题，文献[2]用蚁群算法解决TSP问题，文献[3—6]用回溯法、蚁群算法求解圆排列问题．目前，圆排列研究得最多的问题是如何求解最小长度，然而，在生产生活中也会遇到下面这种情况，生产统一大小的盒子，要求这种盒子能够装下以任何一种排列顺序排进该盒子的个大小不全相等的圆，且盒子长度尽可能的小．本文把这种问题称为圆排列包装问题，并对此进行研究．1圆排列包装问题的数学模型圆排列包装问题描述为找一个矩形框，将个大小不全相等的圆以任何一种排列顺序排进该矩

3、形框后，都能保证这个圆与矩形的底边相切，且要求这种矩形框长度最小．设任给一个c，C2，⋯，的圆排列Ci，Ci，⋯，(il，i2，⋯，i是1，2，⋯，的级排列)，圆对应的圆心坐标~(xlk，Rik)，其中k=l，⋯，，则圆排列包装问题模型的非线性二层规划为fmin(max(xik+R)一n(一R))，maxts．t．~／(z一z)+(R一R)≥R+R，’⋯“IP一1，⋯，；q一1，⋯，；P≠q，(1)【zt≤2≤⋯≤Xin，下面给出一些集合和相关长度的定义．定义1给定个圆C“，G，其圆心的横坐标分别为X，z。，⋯，，半径分别为R。，Rz，⋯，R，R≤⋯≤R，且R<．定义下面4个的集合S，T，Q，

4、P．1)S一{Wl(叫一1，i2，⋯，i)为1，⋯，的咒级排列}．2)T一((z¨⋯，．。)J(。，。，⋯，)ES，圆排列G．，⋯，不在左右两端的圆与相邻的两个圆两两相切(左端的圆是指取圆心的横坐标为所有圆的横坐标的最小值的圆，右端的圆是指取圆心的横坐标为所有圆的横坐标最大值的圆)，圆Ci，的坐标为(zR‘)，其中，J一1，⋯，，且min(z一R‘)一O)．3)Q一{(⋯，．27)l(，i，⋯，)ES，圆排列G，⋯，C0不在左右两端的圆与相邻的两个圆两两收稿日期：2012—01—16通信作者：宋海洲(1971一)，男，副教授，主要从事数学模型的研究．E-mail．hzsong@hquedu．o

5、n．基金项目：华侨大学科研基金资助项目(10Hz6)第2期杨金勇，等：圆排列包装问题最优解解析221相切，圆的坐标为(z0，R‘)，其中一1，⋯，J~．min(xi，．一R0)一0；圆排列Ci1，．”，Ci．左端的圆的平行于y轴的左切线的横坐标等于min(x~k—)，其中，k-1，⋯，；同时，该圆排列中右端的圆的平行于Y轴的右切线的横坐标等于x(+)，其中k=l，⋯，)．4)P—T／Q显然，QT，PT，QUP=T，Q~P=O．设叫一(”，i)∈S，记L(硼)为模型1≤2≤⋯‘‘量x‘以+忌一^一R]ls．t．√(一z)+(Rip—Riq)≥RipAVRiq，fP一1，⋯，；q一1，⋯，；P≠q

6、J的最优值．为了表述方便，记D一{(zz⋯，Xin)Iz≤≤⋯≤z，~／(z-Xiq)。-~-(Rip—Riq)≥R+R，一1，⋯，；q一1，⋯，；p=／=q．)，将模型(1)简化表示为maxL()，s．t．叫一(il，iz，⋯，)∈S，1(z。，z。，⋯，z)∈arg霉)∈。{x(z+R)一min(x—Rk))·J(，2圆排列包装问题的最优解的性质定理1模型(2)中的所有最优解中必存在一个最优解z，使得该最优解对应的圆排列的圆心的横坐标构成的向量属于L-证明(反证法)假设叫=(i，⋯，)∈S，硼对应的圆排列为Ce”，，其对应的圆的圆心的横坐标分别为f1’南，⋯，，满足≤≤⋯≤，(⋯，X)∈，

7、W为模型(2)的任意一个最优解，但(¨zb，⋯，f_)T．由于(，⋯，)T，则必有如下两种情形之一．情形1圆排列G，，，⋯，中圆C‘与前面的所有圆都不相切，如图1(a)所示．将圆G。和其后面的圆向左平移相同的位移，使得圆与其前面的某个圆C‘(1≤≤忌一1)相切，得到新的圆排列C，C，，⋯，C，‘，其对应的圆的横坐标zf1，Xf，，⋯，‘，满足X≤z≤⋯≤，且新圆排列长度比原来的圆排列，，，⋯，长度