Matlab在锁具装箱问题中的应用.ppt

Matlab在锁具装箱问题中的应用,某厂生产一种弹子锁具，每个锁具的钥匙有5个槽，每个槽的高度从1，2，3，4，5，66个数（单位略）中任取一个，由于工艺及其他原因，制造锁具时对5个槽的高度有两个限定：至少有3个不同的数；相邻两槽的高度之差不能为5。满足以上条件制造出来的所有互不相同的锁具称为一批。从顾客的利益出发，自然希望在每批锁具中“一把钥匙开一把锁”。但是在当前工艺条件下，对于同一批中两个锁是否能够互开，有一下实验结果：若二者相对应的5个槽的高度中有4个相同，另一个槽的高度差为1，则可能互开；在其他情形下，不可能互开。原来，销售部门在一批锁具中随意地取60个装成一箱出售。团体顾客往往购买几箱到几十箱，他们抱怨购买的锁具会出现互开的情形。现聘你为顾问，回答并解决以下问题：每一批锁具有多少个？装多少箱？为销售部门提出一种方案，包括如何装箱（仍是60个锁具一箱），如何给箱子以标志，出售时如何利用这些标志，使团体顾客不再或减少抱怨。采取你提出的方案，团体顾客的购买量不超过多少箱，就可以保证一定不会出现互开的情形。按照原来的装箱方，需找可能的开对总数。,一、每批锁的把数第一问完全是一个数学问题，首先可以求出有5个槽、每个槽有6个高度的所有可能的个数为n1=65=7776，为了满足题目中提出的至少有三个不同的高度，且相邻高度差不应为5的要求，我们应该减去不满足要求的锁具。在具体求每批锁的个数以及可以装多少箱时，既可以用排列组合法也可以编程用计算机求解。这里我们用Matlab编程求解。我们对5个钥匙槽的高度进行五重循环，并将判断条件设置为5个槽的高度中至少有3个不同的数且相邻两槽的高度之差不能为5，进行判断。将满足判断条件的累加起来，最后输出即可得到一批锁具总数的大小。可以装的箱数用锁具总数除于60即可得到。程序如下：,s=0;n=5;forj1=1:n+1forj2=1:n+1forj3=1:n+1forj4=1:n+1forj5=1:n+1a1=j1;a2=j2;a3=j3;a4=j4;a5=j5;amax=max(a1,a2,a3,a4,a5);amin=min(a1,a2,a3,a4,a5);numbers=(amax-a1)*(a1-amin)+(amax-a2)*(a2-amin)+(amax-a3)*(a3-amin)+(amax-a4)*(a4-amin)+(amax-a5)*(a5-amin);neighbours=max(abs(a1-a2),abs(a2-a3),abs(a3-a4),abs(a4-a5);ifnumbers0.5ifneighbours=2endendendendendendcountnbox=count/60,二、装箱方案我们采用理论分析和计算机编程相结合的方法来解决这一问题。（1）对锁具进行分类：当两个锁相对应的5个槽的高度中有4个相同,另一个槽的高度差为1时,它们可以互开。我们发现了下面的规律：在一批锁具中,设能够互开的两锁具的槽高排列分别为h1h2h3h4h5和h1h2h3h4h5,则其各槽高度之和H=,必然具有不同的奇偶性.证明：因为互开的两个锁具有四个槽高度相同,仅有一个槽高度差1,那么高度之和H=和H=,和H=,必为两个相邻的自然数,而两个相邻的自然数中,必有一个为奇数,另一个为偶数.根据以上规律,我们把锁具按钥匙槽高度之和H的奇偶分为两类,H为奇数的属于奇类（Q）,H为偶数的属于偶类（P）.这样,能够互开的锁具一定分属于奇类和偶类，奇类或偶类中的锁具均不能互开。（2）求解奇类和偶类中锁具的个数：这里用Matlab编程求解。我们只须在求解每批锁的把数的程序的基础上稍做修改，完成对每个锁具槽高之和的统计，并确定其奇偶性，槽和为奇数的累加到Q中，和为偶数的累加到P中，最后将Q和P分别输出即可得到奇类和偶类中锁具的个数。程序如下：,Q=0;P=0;forh1=1:6a(1)=h1;forh2=1:6a(2)=h2;forh3=1:6a(3)=h3;forh4=1:6a(4)=h4;forh5=1:6a(5)=h5;s=0;flag=1;b=sort(a);c=diff(a);d=diff(b);fori=1:4ifd(i)=0s=s+1;endifabs(c(i)=5flag=0;endendifs=2endendendendendendendQP,装箱的标记：生产锁具过程中记录每个钥匙槽的高度，从而确定H的奇偶性,将生产出来的锁具分奇类和偶类。将奇类和偶类分别装箱，并做“奇”和“偶”的标志。由于每箱60个，故奇类和偶类均可装49箱。这样,销售部门可以根据所做标记尽量只选同类的箱子售给团体顾客，就可以使他们不再或减少抱怨。而且只要他们一次购买的箱数不超过49箱(即2940个锁具)，我们就可以保证他们的锁具一定不会有互开现象。但按槽高之和的奇偶分类是不是最优方案，即能否找到更好的分类装箱方案，使不可互开的锁具个数大于2940。,三、寻找互开对总数的程序如下：,Q=0;P=0;hukaiduishu=0;forh1=1:6a(1)=h1;forh2=1:6a(2)=h2;forh3=1:6a(3)=h3;forh4=1:6a(4)=h4;forh5=1:6a(5)=h5;s=0;flag=1;b=sort(a);c=diff(a);d=diff(b);fori=1:4ifd(i)=0s=s+1;endifabs(c(i)=5flag=0;endendifs=2endendendendendendend,fori=1:Qfort=1:Py=j