离散数学模型与实验(精品).ppt

《离散数学模型与实验(精品).ppt》由会员分享，可在线阅读，更多相关《离散数学模型与实验(精品).ppt（72页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、离散模型与实验 第七章：离散模型与实验第七章：离散模型与实验7.1截断切割截断切割7.2锁具装箱锁具装箱7.3钻井布局钻井布局7.4讨论题讨论题下一页上一页下一页上一页下一页上一页7.1 7.1 截断切割截断切割 7.1.1 7.1.1 问题的提出问题的提出 这是这是19971997年全国大学生数学建模竞赛的年全国大学生数学建模竞赛的B B题，问题如下：题，问题如下：某些工业加工部门，经常需要从一个长方体中加工出一个某些工业加工部门，经常需要从一个长方体中加工出一个尺寸已知，位置预定的长方体（设长方体的对应表面是平面），尺寸已知，位置预定的长方体（设长方体的对应表面是平面），通常采用截断切割的

2、加工方式，这里通常采用截断切割的加工方式，这里“截断切割截断切割”是指将物体沿是指将物体沿某个切割平面分成两部分，因此，一般情况下，须经过某个切割平面分成两部分，因此，一般情况下，须经过6 6次截次截断切割，分别截去原长方体的前后、左右、上下断切割，分别截去原长方体的前后、左右、上下6 6个方向多余个方向多余的部分。的部分。下一页上一页下一页上一页下一页上一页 设水平切割单位面积的费用是垂直切割单位面积费用的设水平切割单位面积的费用是垂直切割单位面积费用的r r倍，且当先后两次垂直切割的平面不平行时，因调整刀具需额倍，且当先后两次垂直切割的平面不平行时，因调整刀具需额外费用外费用e e，显然，

3、若截去各个多余小块的先后顺序不同，则加显然，若截去各个多余小块的先后顺序不同，则加工费用不同，试设计一种确定最优加工次序的方法，使加工费工费用不同，试设计一种确定最优加工次序的方法，使加工费用最少。用最少。用以下实例验证你的方法：待加工长方体与成品长方体的用以下实例验证你的方法：待加工长方体与成品长方体的长、宽、高分别为长、宽、高分别为1010；14.514.5；1919和和3 3；2 2；4 4二者左面，前面，二者左面，前面，底面之间的距离分别为底面之间的距离分别为6 6；7 7；9 9（单位（单位cmcm），），垂直切割费用为垂直切割费用为1 1元元/cmcm2 2，r r和和e e的数据

4、有以下的数据有以下4 4组：组：a a）r r=1=1；e e=0=0；b b）r r=1.5=1.5；e e=0=0；c c）r r=8=8；e e=0=0；d d）r r=1.5=1.5；22e e1515下一页上一页下一页上一页下一页上一页7.1.2 7.1.2 模型假设及符号说明模型假设及符号说明（1 1）假设水平工作台接触的长方体底面是事先指定的。）假设水平工作台接触的长方体底面是事先指定的。（2 2）假设第一次切割前调整刀具的费用不计。）假设第一次切割前调整刀具的费用不计。（3 3）假设加工前后，两长方体对应的表面平行。）假设加工前后，两长方体对应的表面平行。（4 4）假设垂直切割

5、费用为）假设垂直切割费用为1 1元元/cmcm2 2，水平切割费用为水平切割费用为r r元元/cmcm2 2。（5 5）假设调整一次刀具的费用为）假设调整一次刀具的费用为e e。（6 6）假设总的加工费用为假设总的加工费用为C C。（7 7）假设待加工长方体的长、宽、高分别为假设待加工长方体的长、宽、高分别为a a、b b、c c，为为 常数，成品长方体的长、宽、高分别为常数，成品长方体的长、宽、高分别为A A、B B、C C，也是也是 常数。常数。（8 8）假设待加工长方体与成品长方体的左面、前面、后面、）假设待加工长方体与成品长方体的左面、前面、后面、下面、上面之间的距离为下面、上面之间的

6、距离为 且为常数。且为常数。下一页上一页下一页上一页下一页上一页 7.1.3 7.1.3 问题分析及数学模型问题分析及数学模型 根根据据所所给给的的实实际际问问题题，从从一一个个长长方方体体加加工工出出一一个个尺尺寸寸位位置置预预定定的的长长方方体体，通通常常情情况况下下，需需要要经经过过6 6次次截截断断切切割割，如如果果我我们们假假定定这这6 6个个切切割割面面分分别别位位于于左左、右右、前前、后后、下下、下下面面，那那么么可可将将它它们们相相应应地地编编号号为为1 1、2 2、3 3、4 4、5 5、6 6。这这样样这这6 6个个数数字字的的一一个个全全排排列列代代表表着着一一种种切切割

7、割顺顺序序。例例如如，排排列列1 1 2 2 3 3 4 4 5 5 6 6代代表表的的的的切切割割顺顺序序为为“左左前前后后右右下下上上”。我我们们将将这这6 6个个数数字字的的所有全排列记为集合所有全排列记为集合S S，即：即：因此问题转化为求总的切割费用因此问题转化为求总的切割费用C C在在S S上的最小值问题。上的最小值问题。下一页上一页下一页上一页下一页上一页 总总的的切切割割费费用用应应包包含含二二部部分分，一一部部分分为为加加权权的的切切割割面面积积之和，另一部分是刀具调整费用之和之和，另一部分是刀具调整费用之和,因此，数学模型为：因此，数学模型为：其中其中 ：表表示示 进进行行

8、切切割割后后，加工面加工面 的切割面积；的切割面积；：为相应切割面的权，由题意有：为相应切割面的权，由题意有：为调整刀具的次数。：为调整刀具的次数。下一页上一页下一页上一页下一页上一页 7.1.4 7.1.4 模型的分析及计算模型的分析及计算 当当e e=0=0时（时（1 1）式成为：）式成为：由由于于集集合合S S为为有有限限集集，只只有有 个个元元素素，代代表表着着720720种种切切割割方方式式，r r给给定定，切切割割顺顺序序固固定定则则很很容容易易计计算算出出加加工工费费用用。比比较较出出所所有有不不同同切切割割方方式式下下的的费费用用，便便可可得得到到最最小小费费用用下下的的切切割

9、方式。下面给出割方式。下面给出MATLABMATLAB计算程序。计算程序。1 1）建立可行的加工顺序表。）建立可行的加工顺序表。2 2）用穷举法求出）用穷举法求出720720种切割方式下的费用。种切割方式下的费用。3 3）求最小费用及其对应的切割方式。）求最小费用及其对应的切割方式。下一页上一页下一页上一页下一页上一页在在MATLAB编辑器中建立如下文件。编辑器中建立如下文件。%截断切割截断切割ch711%文件名：文件名：ch711.ma0=10 14.5 19;a1=3 2 4;d1=6 7 9;r=1;d2=a0-a1-d1;d=d1,d2;d=d(1,4,2,5,3,6);p=0;for

10、 i=1:6 for j=1:6,if(j-i)=0,for k=1:6,if(k-i)*(k-j)=0,for l=1:6,if(l-i)*(l-j)*(l-k)=0,for m=1:6,if(m-i)*(m-j)*(m-k)*(m-l)=0,for n=1:6,if(n-i)*(n-j)*(n-k)*(n-l)*(n-m)=0,p=p+1;x(p,:)=i j k l m n;end end end end end end 下一页上一页下一页上一页下一页上一页 end end end end end end end end end endf=1 1 2 2 3 3;f=1 1 2 2 3

11、3;for p=1:720for p=1:720 o=x(p,:);cost=0;a=a0;o=x(p,:);cost=0;a=a0;for i=1:6 for i=1:6 j=j=o(i);aao(i);aa=a;aa(f(ja;aa(f(j)=;)=;if f(j)=3 if f(j)=3 cost=cost+r*aa(1)*aa(2);cost=cost+r*aa(1)*aa(2);else else cost=cost+aa(1)*aa(2);cost=cost+aa(1)*aa(2);end end a(f(j)=a(f(j)-d(j);a(f(j)=a(f(j)-d(j);end

12、end c(p)=cost;c(p)=cost;endendmincminc=min(c),find(c=min(c),find(c=mincminc););minx=minx=x(ansx(ans,:),:)下一页上一页下一页上一页下一页上一页执行后输出执行后输出最小切割费用最小切割费用mincminc=374 374最优切割顺序最优切割顺序minx=minx=5 3 1 6 4 2 5 3 1 6 4 2 5 3 6 1 4 2 5 3 6 1 4 2即当即当r=1,e=0r=1,e=0时最优切割顺序有两条，它们分别是时最优切割顺序有两条，它们分别是“下前左上后右下前左上后右”和和“下前上

13、左后右下前上左后右”，最小切割费用为，最小切割费用为374374元。元。当当e e00时，模型为（时，模型为（1 1）式，即）式，即下一页上一页下一页上一页下一页上一页 由由于于垂垂直直切切割割的的方方向向有有两两个个，因因此此至至少少调调整整一一次次刀刀具具，而而垂垂直直切切割割共共进进行行四四次次，故故调调整整刀刀具具的的次次数数至至多多，于于是是额额外外费费用用有有e e，2 2e e，3 3e e，三三种种可可能能。所所以以我我们们把把全全体体切切割割顺顺序序按按刀刀具具的的调调整整费费用用分分类类，共共分分三三类类，同同类类的的刀刀具具调调整整费费用用是是相相等等的的，故故可可先先分

14、分别别求求出出在在e e=0=0时时每每一一类类的的最最小小费费用用及及加加工工顺顺序序，再再将将每每一一类类的的最最小小切切割割费费用用加加上上相相应应的的刀刀具具调调整整费费用用，便便得得到到总总的的加加工工费费用用，从从而而比比较较各各类类加加工工顺顺序序求求出出整整体体最最优优的加工顺序。下面给出的加工顺序。下面给出MATLABMATLAB计算程序。计算程序。1 1）计算出三类可行的加工顺序及相应的切割费用表；）计算出三类可行的加工顺序及相应的切割费用表；2 2）对对每每一一个个最最小小费费用用的的切切割割顺顺序序，与与刀刀具具调调整整费费用用结结合考虑；合考虑；3 3）求出总的费用最

15、小时的切割顺序及调整刀具次数。）求出总的费用最小时的切割顺序及调整刀具次数。下一页上一页下一页上一页下一页上一页%截断切割截断切割ch712ch712%文件名：文件名：ch712.mch712.mfunction minc,minx1,minx2,minx3=cutorde(a0,a1,d1,r)function minc,minx1,minx2,minx3=cutorde(a0,a1,d1,r)mincminc=inf,inf,inf;minx1=;minx2=;minx3=;=inf,inf,inf;minx1=;minx2=;minx3=;k1=0;k2=0;k3=0;k1=0;k2=0

16、;k3=0;v1=1 2 3 4 5 6;v1=1 2 3 4 5 6;%建立可行的加工顺序表建立可行的加工顺序表 x x1,1,x x2,2,x x3 3及相应的切割费用表及相应的切割费用表for i1=1:6,o1=v1(i1);v2=v1;v2(i1)=;for i1=1:6,o1=v1(i1);v2=v1;v2(i1)=;for i2=1:5,o2=v2(i2);v3=v2;v3(i2)=;for i2=1:5,o2=v2(i2);v3=v2;v3(i2)=;for i3=1:4,o3=v3(i3);v4=v3;v4(i3)=;for i3=1:4,o3=v3(i3);v4=v3;v4

17、(i3)=;for i4=1:3,o4=v4(i4);v5=v4;v5(i4)=;for i4=1:3,o4=v4(i4);v5=v4;v5(i4)=;for i5=1:2,o5=v5(i5);o6=v5(3-i5);for i5=1:2,o5=v5(i5);o6=v5(3-i5);x=o1,o2 o3 o4 o5 o6;x=o1,o2 o3 o4 o5 o6;c=cost(x,a0,a1,d1,r);c=cost(x,a0,a1,d1,r);z=z=adjustnum(xadjustnum(x););switch z switch z case 1,k1=k1+1;x1(k1,:)=x;c1

18、(k1)=c;case 1,k1=k1+1;x1(k1,:)=x;c1(k1)=c;case 2,k2=k2+1;x2(k2,:)=x;c2(k2)=c;case 2,k2=k2+1;x2(k2,:)=x;c2(k2)=c;case 3,k3=k3+1;x3(k3,:)=x;c3(k3)=c;case 3,k3=k3+1;x3(k3,:)=x;c3(k3)=c;下一页上一页下一页上一页下一页上一页 end end end end end end end end end endendendmincminc=min(c1)min(c2)min(c3);find(c1=minc(1);=min(c1

19、)min(c2)min(c3);find(c1=minc(1);minx1=x1(ans,:);find(c2=minc(2);minx1=x1(ans,:);find(c2=minc(2);minx2=x2(ans,:);find(c3=minc(3);minx2=x2(ans,:);find(c3=minc(3);minx3=x3(ans,:);minx3=x3(ans,:);下一页上一页下一页上一页下一页上一页%求切割费用的子函求切割费用的子函ch713.mch713.mfunction c=cost(x,a0,a1,d1,r)function c=cost(x,a0,a1,d1,r)c

20、=0;c=0;d2=a0-a1-d1;a=a0;d2=a0-a1-d1;a=a0;for p=1:6for p=1:6 switch x(p)switch x(p)case 1,c=c+a(2)*a(3);a(1)=a(1)-d1(1);case 1,c=c+a(2)*a(3);a(1)=a(1)-d1(1);case 2,c=c+a(2)*a(3);a(1)=a(1)-d2(1);case 2,c=c+a(2)*a(3);a(1)=a(1)-d2(1);case 3,c=c+a(1)*a(3);a(2)=a(2)-d1(2);case 3,c=c+a(1)*a(3);a(2)=a(2)-d1

21、(2);case 4,c=c+a(1)*a(3);a(2)=a(2)-d2(2);case 4,c=c+a(1)*a(3);a(2)=a(2)-d2(2);case 5,c=c+r*a(1)*a(2);a(3)=a(3)-d1(3);case 5,c=c+r*a(1)*a(2);a(3)=a(3)-d1(3);case 6,c=c+r*a(1)*a(2);a(3)=a(3)-d2(3);case 6,c=c+r*a(1)*a(2);a(3)=a(3)-d2(3);end endendend下一页上一页下一页上一页下一页上一页%求调整刀具次数的子函数求调整刀具次数的子函数ch714.mch714

22、.mfunction z=function z=adjustnum(xadjustnum(x)z=-1;v0=0;z=-1;v0=0;for p=1:6for p=1:6 if x(p)5 if x(p)5 if x(p)3 if x(p)3 v=1;v=1;else else v=2;v=2;end end if(v0-v)=0 if(v0-v)=0 z=z+1;v0=v;z=z+1;v0=v;end end end endend end 下一页上一页下一页上一页下一页上一页在窗口中输入主程序在窗口中输入主程序ch715.mch715.ma0=10,14.5,19;a1=3,2,4;d1=6

23、,7,9;r=1.5;a0=10,14.5,19;a1=3,2,4;d1=6,7,9;r=1.5;mincminc,minx1,minx2,minx3=cutorde(a0,a1,d1,r),minx1,minx2,minx3=cutorde(a0,a1,d1,r)执行后输出执行后输出mincminc=442.5000 456.5000 437.5000 442.5000 456.5000 437.5000minx1=minx1=3 5 4 1 6 2 3 5 4 1 6 2minx2=minx2=1 3 5 4 6 2 1 3 5 4 6 2minx3=minx3=3 1 5 4 6 2 3

24、 1 5 4 6 2 3 5 1 4 6 2 3 5 1 4 6 2下一页上一页下一页上一页下一页上一页 每一类的最小费用为：每一类的最小费用为：调整一次刀具：调整一次刀具：切割顺序为切割顺序为:3 5 4 1 6 2:3 5 4 1 6 2 调整二次刀具：调整二次刀具：切割顺序为切割顺序为:1 3 5 4 6 2:1 3 5 4 6 2 调整三次刀具：调整三次刀具：切割顺序为切割顺序为:3 1 5 4 6 2:3 1 5 4 6 2 3 5 1 4 6 2 3 5 1 4 6 2 在坐标系中，画出三条曲线在坐标系中，画出三条曲线l l1 1，l l2 2，l l3 3，求出它们的求出它们的交

25、点，如图交点，如图7-17-1。由图可得全体加工顺序中最小费用为：。由图可得全体加工顺序中最小费用为：下一页上一页下一页上一页下一页上一页 当当 时，最小费用为时，最小费用为437.5+3437.5+3e e。对应的加工顺对应的加工顺序为序为3 3、1 1、5 5、4 4、6 6、2 2和和3 3、5 5、1 1、4 4、6 6、2 2。当当 时，最小费用为时，最小费用为442.5+442.5+e e。对应的加工顺序对应的加工顺序为为3 3、5 5、4 4、1 1、6 6、2 2。图图71图图71下一页上一页下一页上一页下一页上一页 7.1.5 7.1.5 问题的进一步讨论问题的进一步讨论 在

26、在(1)(1)式中，式中，为不同的切割方式的总数，由为不同的切割方式的总数，由于相邻二个平行面的次序交换并不影响总费用于相邻二个平行面的次序交换并不影响总费用C C，因此，由因此，由容斥原理可计算出容斥原理可计算出 可减少至可减少至426426，同时考虑到切割面，同时考虑到切割面k k到到相应的边界面的距离，称为切割厚度。不失一般性，假定相应的边界面的距离，称为切割厚度。不失一般性，假定 a1a2 a1a2，b1b2b1b2，c1c2 c1c2 （2 2）当（当（2 2）式不成立时，假定）式不成立时，假定 即可，其它的作类即可，其它的作类似处理，在（似处理，在（2 2）式成立时，只考虑）式成立

27、时，只考虑S S的一个子集，即只考的一个子集，即只考虑虑1 1在在2 2前、前、3 3在在4 4前、前、5 5在在6 6前的那些排列，这个子集中含有前的那些排列，这个子集中含有元素元素720/2720/23 3=90=90。下一页上一页下一页上一页下一页上一页 （1 1）e e=0=0时的优化方法时的优化方法 这时的优化准则为：将这时的优化准则为：将排列成不增序列，相应的指标序列即为切割面的最优序排列成不增序列，相应的指标序列即为切割面的最优序列。在证明中，若假设列。在证明中，若假设r r=1=1，否则在垂直方向作一个因否则在垂直方向作一个因子为子为1/1/r r 的变换，其切割面积和的最小化

28、相当于原来的的变换，其切割面积和的最小化相当于原来的加权面积和最小化，因此在证明中便不妨假设加权面积和最小化，因此在证明中便不妨假设 同时考虑到同时考虑到e e=0=0的情形，于是（的情形，于是（1 1）式成立。式成立。（3 3）其中其中 下一页上一页下一页上一页下一页上一页 下下面面性性质质被被称称为为相相邻邻交交换换原原则则：设设 ，此此时时假假定定第第j j个个切切割割厚厚度度大大于于或或等等于于第第k k个个切切割割厚厚度度，将将相相邻邻加加工工面面k k与与j j交交换换后后得得 ，则则对对（3 3）式式给给出出的的函数，必有函数，必有 （4 4）这这个个原原则则也也就就说说明明了了

29、上上述述的的优优化化准准则则了了。这这主主要要是是因因为为，从从任任何何一一个个最最优优解解出出发发，如如果果第第j j个个厚厚度度最最大大，第第j j个个切切割割面面通通过过交交换换总总可可度度调调到到第第一一个个位位置置，由由于于（4 4）式式保保持持为最优解；对于切割厚度次大者，也可以这样做。为最优解；对于切割厚度次大者，也可以这样做。下一页上一页下一页上一页下一页上一页 相邻交换原则的简单证明：相邻交换原则的简单证明：设相应于切割方式设相应于切割方式 中加工面中加工面j j，k k的切割的切割面积为面积为 ；设相应于切割方式；设相应于切割方式 中中加工面加工面k k，j j的切割面积为

30、的切割面积为 ，由几何知识可得，由几何知识可得 （5 5）其中其中 为切割厚度。为切割厚度。事实上，上式二者均等于在加工方式事实上，上式二者均等于在加工方式x x（或或 ）下加）下加工面工面k k与与j j被切割之前与切割之后的体积差，由（被切割之前与切割之后的体积差，由（5 5）式移项）式移项得：得：下一页上一页下一页上一页下一页上一页 由于由于 ，因此有，因此有 ，即：，即：而而 与与 所含有的各项所含有的各项相同，从而便证明了结论（相同，从而便证明了结论（4 4）。）。（2 2）e e00时的优化方法时的优化方法 用表达式（用表达式（1 1）建立截断切割的数学模型之后，通常可）建立截断切

31、割的数学模型之后，通常可采用分支定界法来求解。每一个分支相当于前面采用分支定界法来求解。每一个分支相当于前面n n个面的切个面的切割方式已经确定的情形，这时，后面割方式已经确定的情形，这时，后面n n个面的切割面还可以个面的切割面还可以用多种方式排列，相应费用的下界可以由二部分和组成，用多种方式排列，相应费用的下界可以由二部分和组成，一部分为加权切割面的面积之和，它可以由一部分为加权切割面的面积之和，它可以由e e=0=0时的优化准时的优化准则得到，另一部分为刀具的调整费用的下界，它为则得到，另一部分为刀具的调整费用的下界，它为0 0或或e e。下一页上一页下一页上一页下一页上一页 借助于借助

32、于e e=0=0时的解来求时的解来求e e00时的解，是一种较为简单的时的解，是一种较为简单的方法。当方法。当e e=0=0时的最优解时的最优解 的调整刀具次数的调整刀具次数 q q（x x）为为1 1时，时，x x使（使（1 1）式中的）式中的C C取最小值，当取最小值，当x x的刀具调整的刀具调整次数次数q q（x x）为为2 2时，则只能断言，时，则只能断言，x x使（使（1 1）式在所有刀具调）式在所有刀具调整次数大于整次数大于1 1的切割方式中达到最小，为求（的切割方式中达到最小，为求（1 1）式的整体最）式的整体最小，还应考虑刀具调整次数小，还应考虑刀具调整次数q q（x x）为为

33、1 1的切割方式，由前面的切割方式，由前面所述，不妨设（所述，不妨设（2 2）式成立，这时，可只考虑）式成立，这时，可只考虑1 1在在2 2前、前、3 3在在4 4前、前、5 5在在6 6前的那些切割方式，在刀具调整次数为前的那些切割方式，在刀具调整次数为1 1时，在那时，在那些切割方式中，加工面些切割方式中，加工面1 1、2 2、3 3、4 4的排列方式只可能是的排列方式只可能是1 1、2 2、3 3、4 4与与3 3、4 4、1 1、2 2，然后将加工面，然后将加工面5 5与与6 6按照相邻交换原则插按照相邻交换原则插入到适当的位置，可以得到几个候选的切割方式，它们相当入到适当的位置，可以

34、得到几个候选的切割方式，它们相当于一定意义下的局部解。这些局部解与上述于一定意义下的局部解。这些局部解与上述x x组成候选解，组成候选解，比较所有的候选解，便得到比较所有的候选解，便得到e e00时的最优切割方式。时的最优切割方式。下一页上一页下一页上一页下一页上一页 由由于于按按排排列列1 1、2 2、3 3、4 4的的次次序序至至多多有有2 2个个单单调调下下降降段段，可可知知加加工工面面5 5与与6 6按按相相邻邻单单调调下下降降方方式式插插入入时时，至至多多可可得得到到3 3个个局局部部解解，对对排排列列3 3、4 4、1 1、2 2就就是是这这样样。所所以以q q（x x）=2=2时

35、时，候候选选解解总总数数至至多多为为3+3+1=73+3+1=7，当当x x的的刀刀具具调调整整次次数数q q（x x）为为3 3时时，除除了了补补充充考考虑虑刀刀具具调调整整次次数数为为1 1的的切切割割方方式式外外，还还必必须须补补充充考考虑虑刀刀具具调调整整次次数数为为2 2的的切切割割方方式式，它它们们可可由由加加工工面面5 5与与6 6按照相邻交换原则插入到按照相邻交换原则插入到1 1、3 3、4 4、2 2与与3 3、1 1、2 2、4 4。它们各具有它们各具有2 2个单调下降段（二者的插入方式各不超过个单调下降段（二者的插入方式各不超过3 3），或者，二者之一具有），或者，二者之

36、一具有3 3个单调下降段，而另一个则必个单调下降段，而另一个则必定只有一个单调下降段（前者的插入方式不超过定只有一个单调下降段（前者的插入方式不超过6 6，后者的，后者的插入方式为插入方式为1 1，总数不超过，总数不超过7 7），所以候选解的总数不超过），所以候选解的总数不超过7+6+1=147+6+1=14，这样就很容易求出，这样就很容易求出00时的最优切割顺序。时的最优切割顺序。下一页上一页下一页上一页下一页上一页 7.2 7.2 锁具装箱锁具装箱 7.2.1 7.2.1 问题的提出问题的提出 这是这是19941994年全国大学生数学建模竞赛的年全国大学生数学建模竞赛的B B题，问题如下：

37、题，问题如下：某厂生产一种弹子锁具，每个锁具的钥匙有某厂生产一种弹子锁具，每个锁具的钥匙有5 5个槽，每个槽，每个槽的高度从个槽的高度从11，2 2，3 3，4 4，5 5，6666个数（单位略）中任取个数（单位略）中任取一个数。由于工艺及其它原因，制造锁具时对一个数。由于工艺及其它原因，制造锁具时对5 5个槽的高度个槽的高度还有两个限制：至少有还有两个限制：至少有3 3个不同的数；相邻两槽的高度之差个不同的数；相邻两槽的高度之差不能为不能为5 5。满足以上条件制造出来的所有互不相同的锁具称。满足以上条件制造出来的所有互不相同的锁具称为一批。为一批。从顾客的利益出发，自然希望在每批锁具中从顾客

38、的利益出发，自然希望在每批锁具中“一把钥匙一把钥匙开一把锁开一把锁”。但是在当前工艺条件下，对同一批中两个锁具。但是在当前工艺条件下，对同一批中两个锁具是否能够互开，有以下试验结果：若二者相对应的是否能够互开，有以下试验结果：若二者相对应的5 5个槽的个槽的高度中有高度中有4 4个相同，另一个槽的高度差为个相同，另一个槽的高度差为1 1，则能互开；在其，则能互开；在其它情况下，不可能互开。它情况下，不可能互开。下一页上一页下一页上一页下一页上一页 先先前前，销销售售部部门门随随意意地地在在一一批批锁锁具具中中取取每每6060个个装装一一箱箱出出售售，团团体体顾顾客客往往往往购购买买几几箱箱到到

39、几几十十箱箱，他他们们抱抱怨怨购购得得的的锁锁具具会出现互开的情形。现聘你为顾问，回答并解决以下的问题：会出现互开的情形。现聘你为顾问，回答并解决以下的问题：（1 1）每一批锁具有多少个，装多少箱。）每一批锁具有多少个，装多少箱。（2 2）为为销销售售部部门门提提出出一一种种方方案案，包包括括如如何何装装箱箱（仍仍是是6060个个锁锁具具一一箱箱），如如何何给给箱箱子子以以标标志志，出出售售时时如如何何利利用用这这些些标标志，使团体顾客不再或减少抱怨。志，使团体顾客不再或减少抱怨。（3 3）采采取取你你提提出出的的方方案案，团团体体顾顾客客的的购购买买量量不不超超过过多多少少箱，就可以保证一定

40、不会出现互开的情形。箱，就可以保证一定不会出现互开的情形。（4 4）按照原来的装箱办法，如何定量地衡量团体顾客抱）按照原来的装箱办法，如何定量地衡量团体顾客抱怨互开的程度（试对购买一、二箱者给出具体结果）。怨互开的程度（试对购买一、二箱者给出具体结果）。下一页上一页下一页上一页下一页上一页 7.2.2 7.2.2 模型假设及符号说明模型假设及符号说明 （1 1）假假设设按按工工艺艺要要求求生生产产出出的的每每个个锁锁具具都都为为合合格格品品，没有因质量问题造成可以互开的情形。没有因质量问题造成可以互开的情形。（2 2）假假设设题题中中的的试试验验互互开开的的情情况况是是唯唯一一的的，即即只只有

41、有当当二二个个锁锁具具相相对对应应的的5 5个个槽槽的的高高度度中中的的4 4个个相相同同，另另一一个个槽槽的的高度差为高度差为1 1则能互开，否则不管什么情况，都不能互开。则能互开，否则不管什么情况，都不能互开。（3 3）假假设设相相邻邻槽槽高高之之差差为为5 5的的锁锁具具集集合合记记为为A A；n n（A A）表示集合表示集合A A中的元素个数。中的元素个数。（4 4）假设）假设 表示锁具第表示锁具第n n个槽的高度。个槽的高度。下一页上一页下一页上一页下一页上一页 7.2.3 7.2.3 问题分析及数学模型问题分析及数学模型 根根据据所所给给的的实实际际问问题题，要要对对所所生生产产的

42、的锁锁具具进进行行分分类类、装装箱箱，使使同同一一箱箱中中的的锁锁具具不不能能互互开开，在在批批量量销销售售时时尽尽可可能能地地减减少少互互开开现现象象，从从而而减少团体顾客的抱怨。减少团体顾客的抱怨。因为弹子锁具的钥匙有因为弹子锁具的钥匙有5 5个槽，每个槽的高度从个槽，每个槽的高度从11，2 2，3 3，4 4，5 5，66这这6 6个数中任取一数，且对个数中任取一数，且对5 5个槽的高度必须满足两个槽的高度必须满足两 个条件：个条件：1 1）至少有三个不同的数；至少有三个不同的数；2 2）相邻两槽的高度之差不能为）相邻两槽的高度之差不能为5 5，所以我们在，所以我们在求一批锁具的总数时，

43、可以把问题化为三种情况，即求一批锁具的总数时，可以把问题化为三种情况，即5 5个槽的高度由个槽的高度由5 5个不同数字组成；由个不同数字组成；由4 4个不同数字组成；由个不同数字组成；由3 3个不同数字组成。分别计个不同数字组成。分别计算出各种情况的锁具个数，然后相加便得到一批锁具的总数，在分别算出各种情况的锁具个数，然后相加便得到一批锁具的总数，在分别求这三种情况的锁具个数时，先求出满足条件求这三种情况的锁具个数时，先求出满足条件1 1）的锁具个数，再减）的锁具个数，再减去不满足条件去不满足条件2 2）的锁具个数。它等价于求出有）的锁具个数。它等价于求出有5 5个槽，每个槽有个槽，每个槽有6

44、 6个个高度的所有可能的个数，再减去不满足要求的锁具个数。对于只有高度的所有可能的个数，再减去不满足要求的锁具个数。对于只有5 5个槽，每个槽有个槽，每个槽有6 6个高度的所有可能的个数为个高度的所有可能的个数为n n1 1=6=7776=6=7776，为求出一批为求出一批锁具的个数，应从锁具的个数，应从n n1 1中减去不满足中减去不满足1 1）、）、2 2）的锁具。）的锁具。下一页上一页下一页上一页下一页上一页 只有一个槽高的锁具数目为只有一个槽高的锁具数目为 只有二个槽高的锁具数目为只有二个槽高的锁具数目为 对于相邻槽高之差为对于相邻槽高之差为5 5的锁具，若记为集合的锁具，若记为集合A

45、 A，则则A A可以可以分解为以下分解为以下4 4种集合：种集合：或或 ：或或 ：或或 ：或或下一页上一页下一页上一页下一页上一页其中其中，为，为1 1，2 2，3 3，4 4，5 5，6 6这这6 6个数中任意个数中任意一个，显然一个，显然,则由集合论知识可知则由集合论知识可知A A中的锁具个中的锁具个数为数为:5个槽中只有两个槽高，且相邻高差为个槽中只有两个槽高，且相邻高差为5的锁具个数为的锁具个数为所以，我们得到一批锁具的个数为所以，我们得到一批锁具的个数为下一页上一页下一页上一页下一页上一页 7.2.4 7.2.4 模型的分析与计算模型的分析与计算 由上面的分析，显然，匀们只需计算出由

46、上面的分析，显然，匀们只需计算出n n（A A）即可。即可。A A1 1A A2 2的的槽槽高高为为（1 1，6 6，1 1，x x1 1，x x2 2）或或（6 6，1 1，6 6，x x1 1，x x2 2），因此因此n n（A A1 1A A2 2）=26=262 2=72=72，同理，同理，n n（A A2 2A A3 3）=n n（A A3 3A A4 4）=72=72。A A1 1A A3 3的的槽槽高高为为（1 1，6 6，1 1，6 6，x x1 1）或或（1 1，6 6，6 6，1 1，x x1 1），或或（6 6，1 1，1 1，6 6，x x1 1）或或（6 6，1 1，

47、6 6，1 1，x x1 1），因因此此，n n（A A1 1A A3 3）=46=24=46=24，同理，同理，n n（A A1 1A A4 4）=n n（A A2 2A A4 4）=24=24。A A1 1A A2 2A A3 3的的槽槽高高为为（1 1，6 6，1 1，6 6，x x1 1）或或（6 6，1 1，6 6，1 1，x x1 1），），因此，因此，n n（A A1 1 A A2 2A A3 3）=26=12=26=12，同理，同理，n n（A A2 2A A3 3A A4 4）=12=12。下一页上一页下一页上一页下一页上一页 A A1 1A A2 2A A4 4的的槽槽高高

48、为为（1 1，6 6，1 1，1 1，6 6）或或（1 1，6 6，1 1，6 6，1 1）或或（6 6，1 1，6 6，1 1，6 6）或或（6 6，1 1，6 6，6 6，1 1），因因此，此，n n（A A1 1 A A2 2A A4 4）=4=4，同理，同理，n n（A A1 1A A3 3A A4 4）=4=4。A A1 1A A2 2A A3 3A A4 4的的槽槽高高为为（1 1，6 6，1 1，6 6，1 1）或或（6 6，1 1，6 6，1 1，6 6），因此，），因此，n n（A A1 1 A A2 2 A A3 3A A4 4）=2=2。故而得到一批锁具的个数为：故而得到

49、一批锁具的个数为：58805880 所以每批锁具有所以每批锁具有58805880把，可以装把，可以装9898箱。箱。下一页上一页下一页上一页下一页上一页 下面给出下面给出MATLABMATLAB计算程序。计算程序。算法：算法：1 1）设）设5 5个槽高为个槽高为 ，对它们从，对它们从1 1到到6 6进行循环。进行循环。2 2）为除掉仅有一个槽高的情况，可以用）为除掉仅有一个槽高的情况，可以用 进行判断。进行判断。3 3）为除掉相邻高差为）为除掉相邻高差为5 5的情况，可以用的情况，可以用 进行判断。进行判断。下一页上一页下一页上一页下一页上一页 4 4）为除掉只有二个槽高的情况，可以令）为除掉

50、只有二个槽高的情况，可以令 ，当当 时时,令令 ，否则当，否则当 时时,令令 ，利用，利用 进行判断。进行判断。下一页上一页下一页上一页下一页上一页%锁具装箱锁具装箱ch72ch72%文件名：文件名：ch72.mch72.mb2=0;o=0;g1=1;b2=0;o=0;g1=1;for a1=1:6for a1=1:6 for a2=1:6 for a2=1:6 for a3=1:6 for a3=1:6 for a4=1:6 for a4=1:6 for a5=1:6 for a5=1:6 g1=1;g1=1;if abs(a1-a2)+abs(a2-a3)+abs(a3-a4)+abs(a