矩形件排样程序的实现王晨浩-试题b
————————————————————————————————作者: ————————————————————————————————日期:
矩形件排样程序的实现
王晨浩
摘要
针对样板矩形排样程序的实现问题,本人通过实施FORTRＡN90编程,采用直接明了的数字排列的方式,直观清晰的展现了一个矩形样板中矩形件排样的最优方案。而程序语言本身，结构明朗,层次清晰，适合懂本语言的人斟酌损益和修缮完美；程序运行系统,清晰明朗的输入输出步骤,将程序层序化和普遍化展现淋漓；程序表述方式，人性化的中文语言提示，将程序的可接受度和观赏度大大提高。
本程序采取了通过对板面和具体矩形的数字化展现,通过对整体的数字比较描摹和判定板面的整体矩形排列方式,最终以一个具体的数字排列，实现对矩形排列的宏观显现。关键词:ＦORTＲAN90程序,矩形排列方案，板面矩形设计
一、问题重述
（一) 问题简介
工业上经常需要在一块大板材上下料得到若干个小的矩形件,使得板材的利用率最高，即所剩余的边角料最少。例如在一块宽１5、高无限制的矩形板材上,排列2５块尺寸已知的小矩形,2５块小矩形的尺寸如表1,板材的利用率达10０％,如图１所示。
图1 一种排样方案
表１ 小矩形的尺寸
序号
宽 高 1
1２ 6 2
4 7 ３
６ 7 ４
10 ２ ５
2 ５ ６
6 4 7
４ 2 8
４ 6 9
7 ９ 10
4 5 11
6 4 12
4 6 13
６ 3 14
4 ５ １5
2 4 16
8 ４ １７
8 6 1８
8 3 １９
6 3 ２0
2 6 ２１
8 2 22
3 5 2３
２ ５ 2４
3 4 ２5
2 4
如果上述排样方案未知，即不知道图1的排法，那么如何将这２5块小矩形按照某种次序排在一个大的板材上呢?目前这仍是一个世界难题。
通常要求在一个排样图中,任何一个矩形件在不超出板材边界的情况下,按照一个排样方案(给定的次序）采用下列一些方法来安排实际矩形件的排列，对于一个排样方案(解）},{R P D =,其中),,,(21n p p p P =，),,,(21n r r r R =,p i 为矩形件的序号,r i 为排样方式，r i =１表示将矩形件旋转90°， r i =０表示矩形件不旋转。将第i 个矩形件安排在板材上的过程中,均不能再往下、往左移动，则称其满足B Ｌ条件(ｂo ｔtom-l ｅｆｔ-con ｄｉｔｉｏn ，B Ｌ-c ｏｎdition)。
（二） 剩余矩形排样法简介
剩余矩形排样法是目前所提出的一种有效的排样算法,该方法记录了所有可利用的空间，更能合理地分配给待排样的矩形件，提高了每个排样方案的板材利用率,更接近最优排样方案。例如对于同一个矩形件序列)4,3,2,1(进行排样，图3(a)中下方的空洞以往的排样算法都无法利用,矩形４只能被排到上方。而利用剩余矩形排样法可以很好的解决这个问题,它可以使矩形4充分利用下方的空间，如图3(b ）。
图3 剩余矩形排样法的优越性
剩余矩形排样算法用一个矩形数据集合来表示板材目前的剩余位置情况，任何未被排样的空间(包括孤立的缝隙),都在剩余矩形集合中表示,不会遗漏任何一个。而在每一个矩形件被排入前,都需根据这个剩余矩形集合中的数据来选择最为合理的位置进行排放。下面给出剩余矩形的具体形成方法(这里用矩形的左下角坐标和右上角坐标来确定这个矩形的的位置):
(1) 板材的左下角和右上角坐标分别为),()0,0(H W 和,于是开始
时剩余矩形数据集中只有一个矩形为)],(),0,0[(1H W R =。
(2) 当排入一个矩形件i （宽i w 高i h ）后，需将剩余矩形数据集
合中的每一个矩形都减掉此矩形件所占的位置。若此矩形件的左下角
坐标为),(11i i y x ,且为横排（即矩形件不旋转90°)，则每个剩余矩形
都减掉与矩形件)],(),,[(11111i i i i i i h y w x y x ++相交的部分。例如矩形
)],(),0,0[(1H W R =减掉与矩形件i 相交的部分后,形成了四个新的剩
余矩形为:
)],(),,[()],(),0,0[(1111i i i i i i h y w x y x H W ++- )]},(),0,[()],,(),,0[()],,(),0,0[()],,(),0,0{[(1111H W w x H W h y H x y W i i i i i i ++=
按顺时针方向记录矩形。如图4所示。若为竖排(即矩形件旋转９0°）,计算方法类似。
图4 剩余矩形表示法
依此类推，将矩形数据集中的所有剩余矩形都作如此操作,减去所排入矩形件i 所占位置,形成新的剩余矩形。
(3) 由于新的剩余矩形的产生,又将引起原矩形数据集的改变，
因此对其进行整理：去掉面积为零的或已无法排下所剩的任何一个矩
形件的剩余矩形；把具有完全包含关系的剩余矩形中面积小的矩形去
除、有相交关系的矩形全部保留。得到新的剩余矩形集,为下一次排
放使用。
用剩余矩形表示法可记录每个可形成最大矩形的空间,用于排样。将这种表示法与B Ｌ排样算法结合，就形成了剩余矩形排样算法，对于给定的一个排样方案},{R P D =,其中),,,(21n p p p P =,),,,(21n r r r R =，具体排样过程如下:
(1) 开始时剩余矩形集S 中仅有一个矩形，即板材本身)],(),0,0[(1H W R =。
(2) 从排列P 中取出第一个需排的矩形件1p (宽1p w ,高1p h ），将1p 根据相应排放方式 1r 排放在板材的左下角,用上面所述的剩余矩形表示法计算
新的板材剩余矩形集},{21R R S =:
若01=r (横排),则)],(),0,[(11H W w R p =,)],(),,0[(12H W h R p =,如图5; 若11=r (竖排），则)],(),0,[(11H W h R p =,)],(),,0[(12H W w R p =。
图5 剩余矩形排样过程
(3) 依此类推，按顺序逐一排放),,2(n i p i =，直至所有矩形排
放完毕。每放入一矩形件，都需根据剩余矩形集确定其排放位置，
即在剩余矩形集中选择宽高均大于等于此矩形件的底部最低的最靠
左的剩余矩形(先靠下后靠左),让矩形件与剩余矩形的左下角重叠。
同时放入矩形后要对剩余矩形集进行整理更新。
同样，剩余矩形排样算法也满足B Ｌ条件。
二、 问题分析
随着科学技术的日益发展,计算机科学的进步往往使我们叹为观止，在工业等领域的一些现实生活的难题,往往为我们所关注并且深深的影响着我们。对于本题,现有的一些方法往往比较复杂和难算，那么计算机能不能帮助我们较简便的
解决这个问题呢?
面对着本题中的算法,我想采用了学过的FＯRTＲAN90来编程实现。而此计算机语言最大的特点就是用于计算，那么能不能把实际问题和计算交织在一起呢?所以我选择了用数组中的数字宏观显现此实际的分配方案,并采用数字的整改来体现排列矩形的过程,采用对数字的比较和相应的算法来实现判别和判定。而此方法的难点在于判定算法的确定,回顾此计算机语言,我们采用最多的是数组定义、循环语句和条件选择等程序的设计。
反观本算法，我们可以得到以下结论:1，在判定之前,我们要对本题所已知的已知量进行分析和总结,即板面特点（宽15米，长度不限)，25个矩形的规格(宽和高)，矩形在此期间的变化(顺序和旋转）。并将其合理载入。2,在判定时，我们首先从板面的最底行判定,并且以最底行的宽为判定首要问题，而后以由底行到高层的顺序依次进行判定，其次在判定行后，我们需要对整个矩形的版面数字进行综合判定,即对该矩形的确定行进行展开,综合判定此矩形的位置。3，在判定后，我们需要在判定合格的基础上进行整改,及将所要求的矩形进行摆放。
三、模型假设
模型假设分别对判定前、中、后期进行假设。
1、前期：记板面整体为一个大数组,由于本题可假设为高5０，宽15的数组，数组元素全为０，其他矩形可依次按序号和规格确定该矩形,即用1—25的序号表示。并可用三维数组综合表示此几个矩形。在排列矩形顺序和旋转方式上可分别定义为一个含２5个元素的一维数组。
2、中期:可分别建立3个循环:1,2５个矩形顺序循环，即一个一个的写入板面。２,判定最底行的宽是否符合矩形宽的要求，即判断一共有几个连续的０。３,判定整个矩形边框内是否都符合要求,即判断以上述边为底边,向上判断该矩形的面积内的元素是否都是0。
4、后期:可以建立一个循环,即整改数组内的元素，如果以上条件均符合,那么将该矩形的代号均写入该板面的数组内。并按照要求输出。
四、模型建立
(一）模型准备
设一个三维数组(s),分别以矩形的长(cｈａng）、宽（kuan)、矩形序数(i)为三
维坐标。定义一个四个一维数组,分别把各矩形的长（chang）、宽(kuａn)、顺序（ｓhｕnｘu）、旋转方式(ｘｕａnzhｕan)记为一个数组。
?用三维数组ｓ(cｈang,ｋuan,i）分别综合表示１个样板面和25个矩形，ｃhaｎｇ(i)、kuan（i）分别依次表示２５个矩形的长和宽，shuｎxu(i）代表本次排列的顺序,ｘuaｎzhuaｎ(i）代表本次矩形旋转的角度(1—代表旋转90度,０—代表不旋转)。运行时，当xuａnzｈuａn（sｈunxｕ（i））＝1时，该矩形chaｎg（sh ｕｎxｕ（ｉ）)和kuan（ｓhｕｎxu（i))互换。
(二) 模型实施
模型按矩形顺序shｕnxｕ(i）输入,循环２５次，分别写入ｊuxing(ｃhaｎｇ(shｕnｘu(i))，kuan(shunxu（ｉ）),shuｎxu(i)）,并从下至上依次对连续0个数（即未被剩余的空间长)进行检验coｕｎt,以寻找chａng（ｉ)=couｎt的矩形的底层线段末端在某点(横坐标j,纵坐标k）上，在意这条线为底做矩形,划定区域｛j-chang(shunxu（i）)——ｊ，k－kuan（shunxu（i））——k}，一次检验此区域的０个数(未被剩余空间区域）,如果0的个数(c)=chang（shunｘｕ(i）)*kuａｎ（shunxu（i））,则进行依次写入给矩形的顺序号(shｕnxｕ(i））,一旦写入成功,则轮到下一个矩形juxｉｎg（cｈang（shunxu（i＋1)），kuan(shuｎｘu（i＋1）),ｓhunxu（ｉ+1))的写入程序。
（三) 模型求解
?按照实施阶段具体实施后，结果将以一个长为1５，高为50的矩阵输出，1—25的数字将以一个横纵方块的形式在样板面上出现。
除此之外，还可以将各个板面进程和相关数据进行写入和输出。
五、模型分析
本程序采取了通过对板面和具体矩形的数字化展现，通过对整体的数字比较描摹和判定板面的整体矩形排列方式,最终以一个具体的数字排列,实现对矩形排列的宏观显现。
本程序优点在于综合运用了循环、条件、数组等多方面的FOＲTRAN90知
识，拟合剩余矩形排列算法，综合成一个实用模型。本模型较稳定，计算算法相对较简单，适用范围广,可以对相关矩形排序问题进行良好求解。
本程序缺点在于输入数字不灵活，一旦输入错误,便得重新输入;如果采用此程序,必须先对结果进行预测，预测出所需的高。
六、模型推广
本模型可在矩形排列程序的相关领域进行拓展，如输入、输出数据库,根据不同排列方法，直观的选择该模型的最优解(对排序,旋转等进行优化）。
本模型在合理规划平面材料资源上有突出成效，也可以在选材实用上有初步见地。
七、结论
本模型通过对计算机的算法编程，实现了由计算机系统组成半自动化的解题方式，通过简单的输入输出,解决了实际问题，并在表现形式上以数字排列的展现方式,向使用者提供清晰直接的答案。
本模型在结果上完成了对平面的模型的资源合理性规划,并在客观上提高了对材料资源利用率。
八、参考文献
[１］姜启源谢金星,《数学模型》,北京：高等教育出版社，２０0６年5月。
[2] 马瑞民衣治安,《FORTRAN9０程序设计（第二版)》，哈尔滨:哈尔滨工程大学出版社,2０04年3月。
附录
程序（本程序输出结果还有问题)
proｇraｍ main
impｌicit none
inｔeger,ｄｉmension(０:2５)::ｓhunｘu,xｕanｚｈuａｎ,ｃhang,kuａn
inteｇer::i，a,ｃoｕnt，j,ｋ,l,m,c，banｃｈａｎg,bankｕan,n,o iｎtegｅr,dｉmensiｏn(50,15,0:2５)::jｕxing
juxing(1:50,1：15,0)=０
prｉnt*,'欢迎您使用本程序来规划您的样板，为满足您的要求请您按照要求填写相关信息＇
pｒint*，'请依次输入25个矩形宽和高:'
dｏｉ=1,25
reaｄ*,chang(ｉ),kuan(i)
eｎｄdo
ｐrint*，＇请依次输入所需排列的25个矩形的顺序:＇
ｒｅaｄ*，ｓhuｎxu(1：2５)
ｐｒｉnt*,＇请依次输入25个矩形排列方式(1=矩形旋转90°,0=矩形不变):'
dｏ i=１，２5
read*,xｕanzhuan(ｉ）
if(xuanｚhuan(i)==1）then
a=chaｎg(i);chang(i）=kuaｎ(ｉ);kuan(i)=a;juxinｇ(1:cｈang(i）,１:kuan(i),i:i)=i
elsｅｉf(ｘuanzｈuａn(i)=＝0)tｈｅn
jｕxing（chａng(i),ｋuaｎ（i）,i:i)＝i
end iｆ
ｅnd dｏ
count=１
dｏ i=1,２5
ｊj：?do k=50,1,-１
?do j=１,15
??iｆ(ｊuｘiｎg(k,ｊ，0)==0.AND.juxiｎg(k,ｊ+１,0）==０)then count＝ｃount+1;
?if(ｃｏunｔ＞＝chanｇ（shunxu(i)））theｎ
?ｄo ｌ=ｋ,k－kuａn(sｈuｎxu(i））,-1
???ｄo m=j+1，ｊ＋1－ｃhaｎg(sｈｕnxｕ(i)）,-1
??if(juxing(l,m,0)==０) c=ｃ＋1
??ｅnd dｏ
?ｅnd do
?
?ｄo wｈile（chang(ｓｈｕnｘu(i))*kuａｎ(shunxｕ(ｉ))＝＝c)
????do n=ｋ，k-kuan(shunxu(i)),-１
???ｄｏ o＝j+1,ｊ+1－chang（shunxu(i)),－1
??ｊuxｉｎg（n,o，0）=shｕnｘu(ｉ)
???end do
?eｎd dｏ
???eｘｉｔ jj
?eｎd do
???ｅｎd iｆ
elｓe if（juｘing(k，j,０)==０)thｅn
?ｃouｎt=１
?else if(juｘinｇ（k,j，0)＞0)ｔhｅn
?count＝0
??eｎｄ if
??end ｄo
?ｅnd do jｊ
ｅｎd do
print＊,'您的矩形样板的矩形件最好按如图排列(数字0代表样板的剩余版面,数字1—25代表1—25号矩形的排列方式）'
priｎt'(1x,15ｉ５)＇,juxing（1:５０,1：１5，0)
eｎd program maｉｎ