设计用料最省的铁皮罐头-福州大学软件学院

1、设计用料最省的铁皮罐头- PAGE 19 -题目：设计用料最省的铁皮罐头软件学院 软件工程 林维勇 林朝裕 董琦摘要：本文针对工厂生产铁罐的实际情况，引入了程序设计、经济学、微积分、工程切割的有关知识，将其与实用数值计算有机地结合起来，切合实际的考虑了如何生产来节省原料，在此基础上建立模型，应用于最优圆料冲压和最优方料切割以及工厂大规模生产。关键字：条件极值 最优圆料冲压 最优方料切割 回溯算法 递归算法 帕累托最优 逐层枚举分析 1、问题重述1.1相关信息某厂生产容积为1升（1立方分米）的圆柱形铁皮罐。请根据以下情景分别设计下料方案。1.2 需要解决的问题(1) 做一个铁罐，圆形上盖和下底由

2、外切正方形板材冲压得到，怎样做用料最省？ (2) 现有2米长1米(3) 如果工厂大规模生产铁罐，铁罐的上盖、下底以及侧面都从规格为2米12、问题分析在实际的生产生活中，都存在着节省材料的问题，这里我们讨论的就是如何才能最优的使用材料而不必造成不必要的浪费。所以提出“设计用料最省的铁皮罐头”问题。针对问题一，用铁皮做成一个容积一定的圆柱形的容器，问圆形上盖和下底由外切正方形板材冲压得到，怎样做用料最省？ 用几何语言来表述就是: 体积给定的圆柱体, 其表面积最小的尺寸(半径和高)为多少?表面积S是关于r的函数，因此我们用条件极值模型求解该问题。针对问题二，我们需要两张2米长1米针对问题三，如果工厂

3、大规模生产铁罐，铁罐的上盖、下底以及侧面都从规格为2米13、模型假设3.1 总体假设假设工厂大规模生产时，生产10000个同等规格的铁罐，冲压与切割工艺不会出现失误，冲压与切割后的铁罐已经经过 1.印刷生产线. 2.马口铁生产线. 3.罐装生产线. 4.密封消毒生产线. 5.包装生产线.即冲压与切割结束后即可出厂，无需考虑后面工艺，铁皮提供无限制。3.2 具体假设与约定(1) 所处的环境为常温常压下，外界影响忽略(2) 生产铁罐所用的铁皮质量较好，即生产过程种没有造成铁皮的损坏(3) 铁罐不受温度变化影响，不会因为装入的物质而变形或是腐蚀(4) 生产出的铁罐为同一种型号（均为圆柱体）(5) 侧

4、面与底面采用的铁皮一致(6) 忽略铁皮的厚度（实际情况改进时将考虑）(7) 忽略冲压或切割时对铁皮边缘造成的卷曲破损等影响(8) 约定圆料和方料不在同一张铁皮上混合下料4、变量说明4.1 变量说明见表1表1对象类型符号单位铁罐底面半径参数Rm铁罐高参数Hm铁罐表面积输出变量S铁罐上(下)表面积输出变量铁罐体积常量V铁皮长度输入参数Lm铁皮宽度输入参数Bm圆形上(下)盖数量输出变量N整数铁罐侧面数量输出变量M整数4切圆数量输出变量整数6切圆数量输出变量整数切割矩形数量输出变量整数利用率输出变量W%5、模型建立和求解5.1 问题（1）的模型建立问题一讨论的是最优化设计问题（用料最省），因此我们建立

5、条件极值模型来求解该问题。5.1.1铁罐图示化图1图22rhrh图1为铁罐侧面展开图,图2为铁罐立体图。图1图22rhrh5.1.2模型一的分析过程用铁皮做成一个容积一定的圆柱形的容器，问圆形上盖和下底由外切正方形板材冲压得到，怎样做用料最省？ 用几何语言来表述就是: 体积给定的圆柱体, 其表面积最小的尺寸(半径和高)为多少?表面积S是关于r的函数，因此我们用条件极值模型求解该问题。5.1.3 模型一的铁罐是一个正圆柱体，则：5.2 问题（2）5.2.1 问题的分析根据题意，我们需要两张2米长1米宽的铁皮，一张用来冲压上盖和下底，一张用来切割铁罐侧面长方形来生产尽可能多的铁罐。所以，我们需要从

6、铁皮上切割出尽可能多的圆形和矩形，并且圆形和矩形的比例关系尽可能接近2：1。为考虑实际问题与计算方便，我们把铁罐底面半径限定在一定的范围0.04-0.08内，采用枚举算法，逐步缩小范围，最后得出最优结果。因此我们需要建立两个模型（模型二，模型三）。5.2.2 模型二的建立（1）假设：假设铁皮可以高精度地光滑切割，可使圆与圆彼此相切；每个圆之间接触的形式（除临近铁皮边缘的圆）为：与4个圆相切与6个圆相切（2）建立模型与数学求解：对与4个圆相切的方式：考虑参数变化的影响。若b2nr 能得到n列圆，若b增大到（2n+2）r,还可以增多一列。说明列数n是b/2r的整数部分b/2r.同理可推得行数为l/

7、2r,故圆板总数为N=b/2r l/2r,损耗 W=(lb-b/2r l/2r)/lb. LLbb=2nrb=(2n+2)rLb(2n+1)r(2n+2)r (2n+3)rrr4切圆6切圆现对l,b和r的一般取值，讨论六点相切的情形。当铁皮宽度b是r 的奇数倍(2n+1)r,那么直到b增大到（2n+2）r足以再容纳一个圆板前，每行包括n个圆板。b增大到（2n+2）r时各行交替为n+1个和n个，b再增大到（2n+3）r时每行就能包含n+1个圆板。若共有x行，则x必须满足2r+ (x-1)rl,而x又是整数，所以x=1+(1/ )(l/r-2).在每行有n个圆板的情况下，总数N=nx,由条件（2n

8、+1）r=b(2n+2)r得n=1/2(b/r-1).因此， N=1/2(b/r-1)1+(1/ )(l/r-2).在各行交替有n+1个和n个圆板的情况下，当x为偶数时，长行（有n+1个圆板）的个数为x/2,当x为奇数时是（x+1）/2,n也必须满足（2n+2）r=b(2n+3)r.于是n=1/2(b/r-2).故当x为偶数，总数N=x(n+1/2),x为奇数，则N=x(n+1/2)+1/2.（3）结论总结如下：当（2n+1）r= b (2n+2)r时每行都含n个圆板，且 N=x/2(b/r-1).当（2n+2）r= b (2n+3)r时每行交替含n+1个和n个圆板，且N=x/2(b/r-1)

9、, x是偶数； N=x/2(b/r-1)+1/2,x是奇数。在各种情况下 x=1+1/ (l/r-2).（4）模型说明：不能断言6点相切与4点相切两种方法哪种更有效，随着参数值的变化，两种方法都可能更有效，应注意的是对同一组参数，两种方法可以切割出相同的圆板个数N，但损耗W却会改变。5.2.3 模型三的建立模型的分析：（下面分两种算法进行分析）算法一的分析：这是寻求最优解的问题，我们可以使用穷举搜索的方法，也称回溯技术。回溯算法可用伪码描述如下： Proc Search(当前状态)； Begin If 当前状态等于目标状态 then exit; For 对所有可能的状态 Search(新状态)

10、； End;之所以用递归程序设计思想，是因为大多借助回溯技术解决的问题具备两个特点：一是问题本身可以转为几个简单问题；二是最简单的问题可以直接解决。虽然递归算法的效率很低、费时，并且花费内存空间，但鉴于递归算法能使一个蕴含递归关系且结构复杂的程序简洁精炼，增加可读性，采用递归算法编程比较合适。(方式3)对大矩形纵向切割,对小矩形纵向放置(方式4)对大矩形纵向切割,对小矩形横向放置切割方向不外乎两种：横向或纵向。而对每种切割方向，小矩形的放置方式又可以有两种：纵向放置或横向放置，所以共有四种切割方式，如下图所示。(方式3)对大矩形纵向切割,对小矩形纵向放置(方式4)对大矩形纵向切割,对小矩形横向

11、放置(方式(方式2)对大矩形横向切割,对小矩形横向放置(方式1)对大矩形横向切割,对小矩形纵向放置一个大矩形就按照上面四种方式分割,比如对大矩形作横向切割时,小矩形的放置可以纵向或横向,作了一次分割以后,又对剩下的部分作进一步分割,分割方式仍然是前面四种,直到将大矩形分割完毕或剩余的部分不足够一个小矩形为止,分割操作才结束. (代码实现见附录1.)算法二用C+程序实现.(详细内容见附录2)N=N= , 4点相切 , , x是偶数+ ,x是奇数6点相切铁罐底面半径r的范围为0.04m-0.08m (见5.2.16点相切在各种情况下 结合模型三算法二得出表2表2r(m)h(m)0.0400.199

12、300336380.0450.157242263420.0500.127200209460.0550.105162170500.0600.088128143580.0650.075105119610.0700.06598104660.0750.0577890740.0850.0445565750.0900.039556083以下图3，图4，图5，图6，图7是根据表2的r与h，之间的关系描绘出来的离散图示。图3可以得出在0.04-0.09范围内铁罐底面半径与铁罐高度的拟合函数为图4可以得出在0.04-0.09范围内铁罐底面半径与4切圆的拟合函数为图5可以得出在0.04-0.09范围内铁罐底面半径

13、与6切圆的拟合函数为图6可以得出在0.04-0.09范围内铁罐底面半径与可切割矩形数目的拟合函数为图70.0650.065图7为图5和图6的结合函数图像矩形数量与圆块数量()的比值等于1:2,所以所取数据应尽可能接近1:2,分析上表和图7可得出当r=0.065m时, =61, =119,铁罐数=59个,此时与的比值最接近1:2且做出的铁罐的数量也最多.为进一步得出更精确的结果,得下表:表3r(m)h(m)0.0610.085128135580.0620.083128135600.0630.080105126600.0640.07810511958为便于分析,我们由上表得出了下图:图8从表3和图

14、8分析可知,当r=0.064m时,=58, =119,铁罐数=58个,此时与的比值最接近1:2,但与r=0.063m及r=0.062m相比,前者做出的铁罐的数量较少。故我们取r=0.063m或r=0.062m。当r=0.063时，h=0.08m，=126，=60；当r=0.062时，h=0.083，=135，=60。5.2.5问题(2)的结论在2米长1米宽的铁皮两张，为方便加工，一张用来冲压上盖和下底，一张用来切割铁罐侧面长方形。当铁罐半径取0.062m或0.063时,可使生产的铁罐尽可能多,此时，铁罐的底面直径各是0.124m和0.126m，高各是0.083m和5.3 问题（3）5.3.1

15、问题的分析如果工厂大规模生产铁罐，铁罐的上盖、下底以及侧面都从规格为2米15.3.2 模型四的建立假设工厂大规模生产a个铁罐，分配做圆的铁皮数为X块（表示分配给4切圆的铁皮数，表示分配给6切圆的铁皮数），做矩形的铁皮数为Y块，则所用的总铁皮数为Z，Z=X+Y（X=，Y=）。根据题意，大规模生产a个产品，要使用料较省，则所求Z要较小。又考虑r在实际生产中的可行性，则r须限定在一定范围内（0.020m0.090m）。结合问题2中的模型2及模型3可得： N（r）为一张铁皮可做出的圆料数,可由模型二中的公式计算出来。M（r）为一张铁皮可做出的方料数，可由模型三中的程序得出。5.3.3 模型四的解答（下

16、面的计算中我们取a=10000）由5.3.2中的公式可以列出下表：表4rZhY0.0212501397176040.7957716155890.025741874215000.5092927234770.03528608274040.3536738333710.035392432343420.2598452472950.04300336383240.1989467602640.045242263423160.1571983772390.05200209463140.12732100962180.055162170503180.105221241182000.06128143583130.088

17、411571402730.065105119613330.075331911691640.0798104663450.064962051931520.0757890743590.056552572231360.087277704030.049732782601430.0855565754420.044053643081340.095560834550.03929364334121由上表建立出下面的函数图像；图9分析表4和图9，当r=0.05m-0.06m时，Z可以取到较小的值，但因为r的精度问题，Z还可能取更小的值，故我们又对0.05m表5rZhY0.051171198493070.12237

18、1171022050.052171198503020.117711171022000.053162179513090.113311241121970.054162179503120.109151241122000.055162170503180.105221241182000.056136160513220.10151481251970.057136160543110.097971481251860.058136152523250.094621481321930.059128143523330.09144157140193表5中，分析得如果工厂生产铁罐时切割精度只精确到毫米的话，我们就取铁罐底

19、面半径r=0.052m，此时高h=0.118m，所用料Z为302张铁皮。若切割可以更精确的话，r在0.051m-0.053m表6rZhY0.0511171198493070.12191171022050.0512171198493070.121421171022050.0513171198493070.120951171022050.0514171198493070.120481171022050.0515171198493070.120011171022050.0516171198503020.119551171022000.0517171198503020.119081171022000.

20、0518171198503020.118621171022000.0519171198503020.118171171022000.052171198503020.117711171022000.0521171198512990.117261171021970.0522171189513030.116811171121970.0523171189513030.116371171121970.0524171189513030.115921171121970.0525171189513030.115481171121970.0526171189513030.115041171121970.0527

21、162179513090.114611241121970.0528162179513090.114171241121970.0529162179513090.11374124112197分析表6，我们得出当r=0.0521m，h=0.1173m时，用料Z达到最少，Z=299。分配给做圆料的铁皮张数X=102，分配给方料的铁皮张数Y= 问题（3）的结论如果工厂大规模生产铁罐，为方便计算，假设只生产10000个，铁罐的上盖、下底以及侧面都从规格为2米1米的铁皮冲压或切割出来（为方便加工，圆料和方料不在同一张铁皮上混合下料），我们用模型二和模型三的最优切割方法，采用逐层枚举分析，得出用料最省的铁罐规

22、格及方料和圆料的分配。以毫米为切割精度时，r = 0.052m，h=0.118m取得最省原料解，只需用302张铁皮即可生产出10000个铁罐；当精度进一步提高时，r =0.0521m，h=6、模型的评价与改进6.1 模型的优点(1)本模型在建模过程中，对铁罐的生产过程做了合理的简化，建立了合理的模型，建模简单清晰，对生产有一定指导意义。(2)在计算中，合理使用确定范围逐步求精的方法,使计算简便、精确、计算结果经检验分析是正确的，由此得到结论合理可信。(3)提出的模型改进方案有一定的实际意义。(4)模型二与模型三的最优下料算法可以推广到实际生活中的各个方面。6.2模型的缺点(1)模型三是用计算机

23、编程实现，程序较为复杂。(2)由于缺乏某些必要的专业知识和数据，使得讨论无法更深入进行。6.3模型的改进(1)在模型中我们可以继续增大精度，得到更加准确的结果。(2)改进模型，增加对多种规格铁罐切割的考虑，使产品多样化。7、参考文献1徐全智，杨晋浩，数学建模，高等教育出版社，2003.72王晓东，数据结构与算法设计，电子工业出版社，2002.33电子科技大学应用数学系，实用数值计算方法，高等教育出版社，2001.14同济大学应用数学系,高等数学，高等数学出版社，1999.95 吴春尧 , 杨炳孺 , 张岩，矩形材料上切割数量最优问题的研究Quantity Optimization of Inc

24、ision on Rectangular Material，2005年04期6 HYPERLINK /download.htm /download.htm7 /mmb/附录1：Procedure TForml.count(total:integer;Blong,Bwide,Slong,Swide;real);Begin/切割方式一:大矩形横向切割,小矩形纵向放置 if(Blong=Swide)and(Bwide=Slong)then begin total:=total+trunc(Blong/Swide); mode1:=mode1+=1; count(total,Blong,Bwide-S

25、long,Slong,Swide); total:=total-trunc(Blong/Swide); mode1:=leftstr(mode1,length(mode1)-1); end else if max=Slong)and(Bwide=Swide)then begin total:=total+trunc(Blong/Slong); mode1:=mode1+2; count(total,Blong,Bwide-Swide,Slong,Swide); total:=total-trunc(Blong/Slong); mode1:=leftstr(mode1,length(mode1)

26、-1); end else if(max=Swide)and(Bwide=Slong)then begin total:=total+trunc(Bwide/Slong); mode1:=mode1+3; count(total,Blong-Swide,Bwide,Slong,Swide); total:=total-trunc(Bwide/Slong); mode1:=leftstr(mode1,length(mode1)-1); end else if max=Slong)and(Bwide=Swide)then begin total:=total+trunc(Bwide/Swide);

27、 mode1:=mode1+4; count(total,Blong-Slong,Bwide,Slong,Swide); total:=total-trunc(Bwide/Swide); mode1:=leftstr(mode1,length(mode1)-1); end else if maxtotal then begin max:=total; mode2:=mode1;end;end;附录2：#include#includeint max,min;int maxblank,maxlayer,layer;int k=0;int xx,yy;int cut(int x,int y, int

28、 a,int b)/x,y初始表示有切割的材料大小，即长，宽，运行中表示剩余可切割的长宽区域；/a,b表示切割的最小单元长，宽; int z1,z2,x1,y1;if(xy)max=x;min=y;else max=y;min=x;if(maxa)|(minb)return 0;/确定是否继续分割，否则退出循环！else/继续分割下去 layer=layer+1;/计算当前的层数x1=x-a;/计算横切块数z1=cut(x1,y,a,b)+y/b;if(x10)z1=z1-y/b;y1=y-a;/计算竖切块数z2=cut(x,y1,a,b)+x/b;if(y1z2)layer=layer-1;

29、if(layermaxlayer) maxlayer=layer;return z1;elselayer=layer-1;if(layermaxlayer)maxlayer=layer;return z2;int forword(int x,int y, int a,int b) int z1,z2,x1,y1,qk,qh; if(x=xx&y=yy) qh=qk=0;if(xy)max=x;min=y;else max=y;min=x;if(maxa)|(minb)return 0;/确定是否继续分割，否则退出循环！else/继续分割下去 /layer=layer+1;/计算当前的切割的大块

30、数目qh+=y/b;/计算横切的次数x1=x-a;/计算横切块数z1=cut(x1,y,a,b)+y/b;if(x10)z1=z1-y/b;qh-=y/b; qk+=x/b;/计算竖切的次数y1=y-a;/计算竖切块数z2=cut(x,y1,a,b)+x/b;if(y1z2)cout横切的次数：竖切的次数：qh=qh#qk=qkendl;return z1;else cout横切的次数：竖切的次数：qh=qh#qk=qkendl;return z2;float circle(float l, float b, float r, int flag)int x=floor(1+(l/r-2)/sq

31、rt(3);if(flag=4) float f=2*r;float t3=b/f;int t1=floor(t3);float t4=l/f;int t2=floor(t4);return t1*t2;elseif(int)(floor(b/r)%2=0)if(x%2=0) return x/2.0*(floor(b/r)-1);else return x/2.0*(floor(b/r)-1)+0.5;elsereturn x/2.0*(floor(b/r)-1);double Max(float r)int h=100.0/(3.1415926*r*r); int f=200000*3.1415926*r; int temp;cout高:hh)temp=f;f=h;h=temp;int n=cut(200000,100000,h,f);float m1=circle(2, 1, r, 4);float m2=circle(2, 1, r, 6);coutN=nendl;coutM1=m1 M2=m2endl;cout四切圆铁皮数:ceil(20000.0/m1) 六切圆铁皮数:ceil(20000.0/m2)endl;