数学建模例题：锁具装箱

1、问题：树上有十只鸟，开枪打死问题：树上有十只鸟，开枪打死一只，还剩几只？一只，还剩几只？9 9只？还是只？还是0 0只？只？分析：这是一道儿童时期的数学分析：这是一道儿童时期的数学应用题。但他一样是数学建模问应用题。但他一样是数学建模问题，不过答案就不重要了，重要题，不过答案就不重要了，重要的是过程。的是过程。是无声手枪或别的无声的枪吗？是无声手枪或别的无声的枪吗？不是。不是。枪声有多大？枪声有多大？8010080100分贝。分贝。那就是说会震得耳朵疼？那就是说会震得耳朵疼？是。是。在这个城市里打鸟犯不犯法？在这个城市里打鸟犯不犯法？不犯。不犯。您确定鸟里真的没有聋子？您确定鸟里真的没有聋子？

2、没有。没有。吃饱了撑着的问答吃饱了撑着的问答有没有关在笼子里的？有没有关在笼子里的？没有。没有。边上还有没有其他的树，树上还有没有其他的鸟？边上还有没有其他的树，树上还有没有其他的鸟？没有没有有没有残疾的鸟或饿得飞不动的鸟？有没有残疾的鸟或饿得飞不动的鸟？没有。没有。打鸟的人眼有没有花？保证是十只？打鸟的人眼有没有花？保证是十只？没有花，就十只。没有花，就十只。有没有傻得不怕死的鸟？有没有傻得不怕死的鸟？都怕死。都怕死。会不会一枪打死两只？会不会一枪打死两只？不会。不会。所有的鸟都可以自由活动吗？所有的鸟都所有的鸟都可以自由活动吗？所有的鸟都可以自由活动吗？可以自由活动吗？完全可以。完全可以。

3、如果您的回答没有骗人，打死的鸟要是挂如果您的回答没有骗人，打死的鸟要是挂在是挂在树上没掉下来，那么就剩一只，在是挂在树上没掉下来，那么就剩一只，若果掉下来，就一只不剩。若果掉下来，就一只不剩。不是开玩笑，这就是数学建模。这就是数学建模。从不同度思考一个问题，想尽所有的从不同度思考一个问题，想尽所有的可能，正所谓智者千虑，绝无一失，可能，正所谓智者千虑，绝无一失，这才是数学建模的高手。这才是数学建模的高手。常用数学建模方法有：常用数学建模方法有：几何理论、图论、排队论、几何理论、图论、排队论、优化方法、网络优化、优化方法、网络优化、插值与拟合、插值与拟合、差分方法、微分方程、差分方法、微分方程、

4、随机决策、多目标决策、层次分析、随机决策、多目标决策、层次分析、模糊数学、灰色系统理论、神经网络、模糊数学、灰色系统理论、神经网络、随机模拟、组合概率、统计分析、时间随机模拟、组合概率、统计分析、时间序列、序列、综合评价方法、机理分析等方法。综合评价方法、机理分析等方法。 锁具装箱锁具装箱 1 问题 2 背景知识 3 锁具的数量 4 锁具的装箱方案 5 顾客抱怨程度问题 某厂生产一种弹子锁具,每个锁具的钥匙有5个槽,每个槽的高度从1,2,3,4,5,66个数(单 位略)中任取一数.由于工艺及其它原因,制造锁具时对5个槽的高度还有两个限制:至少有3 个不同的数;相邻两槽的高度之差不能为5.满足以

5、上条件制造出来的所有互不相同的锁具称 为一批. 从顾客的利益出发,自然希望在每批锁具中“一把钥匙开一把锁”.但是在当前工艺条件下, 对于同一批中两个锁具是否能够互开,有以下试验结果:若二者相对应的5个槽的高度中有4个 相同,另一个槽的高度差为1,则能互开;在其它情形下,不可能互开. 原来,销售部门在一批锁具中随意地取每60个装一箱出售.团体顾客往往购买几箱到几十箱, 他们抱怨购得的锁具会出现互开的情形.现聘你为顾问,回答并解决以下的问题:(1)每一批锁具有多少个,装多少箱.(2)为销售部门提出一种方案,包括如何装箱(仍是60个锁具一箱),如何给箱子以标志,出售 时如何利用这些标志,使团体顾客不

6、再或减少抱怨.(3)采取你提出的方案,团体顾客的购买量不超过多少箱,就可以保证一定不会出现互开的情 形.(4)按照原来的装箱办法,如何定量地衡量团体顾客抱怨互开的程度(试对购买一、二箱者给 出具体结果).背景1背景2背景3: 锁的历史 中华古锁起源于5000年前的仰韶文化时期，后经历代能工巧匠的不断努力，生产制作出了无数把质地不同、造形各异、机关巧布的古锁。质地有：金、银、铜、铁、铝、木等，古锁生产材料的变化反映了人类社会不断进步、不断发展的轨迹；造形上有：与帝王到百姓生活有关的各种吉祥图案。用途不一样的古锁，体现出了各历史时期丰富的社会文化内涵，展示中华古锁工艺的精湛。木锁木制大钥匙 宝瓶双

7、式木锁琵琶锁 首饰锁 - 麒麟 文字组合锁具 动物锁广锁广锁清代锁 工艺锁 抗战锁 连心锁挂锁 门锁 指纹门锁指纹识别技术指纹识别技术crossover：交叉 core：核 bifurcation：分ridge ending：脊断点island：岛型delta：三角形区域pore：孔 背景4国家标准：GB-9303-88（ 轻工业）门锁， 1988年颁布互开率： 优等品和一等品：0.204%; 合格品： 0.286%。互开率检验： 抽取50把，分5组检验， 9分钟换一次，共45分钟；互开率： R为互开出现次数，T为抽样数。 背景5 为什么要求至少3个不同的槽高？ 为什么相邻高差不为5？ 为什么

8、“若二者相对应的5个槽的高度中有4个 相同,另一个槽的高度差为1,则能互开;在其它情形下,不可能互开”？ 锁厂调研的情况：生产，装箱。问题（1） A：计算机求解 循环判断，排除不合格的，累加统计一批锁的数量s=0;n=5;for j1=1:n+1 for j2=1:n+1 for j3=1:n+1 for j4=1:n+1 for j5=1:n+1 a1=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

9、-amin)+(amax-a3)*(a3-amin) +(amax-a4)*(a4-amin)+(amax-a5)*(a5-amin); neighbors=max(abs(a1-a2),abs(a2-a3),abs(a3-a4),abs(a4-a5); if numbers0.5 if neighbors4.5 s=s+1; end end end end end endends问题（1） B：排列组合法问题（1） C: 递推法问题（1） D: 图论法总数的计算 无16相邻的锁具 减去 仅有一个和两个槽个的锁具 6306-6-420=5880类似的问题：锁具的个数锁具的个数 某厂生产一种弹子

10、锁具，每个锁具有n个槽(2n9, n为自然数)，每个槽的高度从1，2，3，4这4个数(单位略)中任取一个，限制至少有一个相邻的槽高之差等于3，且至少有3个不同的槽高。每个槽的高度取遍这4个数且满足上面这两个限制时生产出一批锁（例如，当n等于3时，3个槽高为1，4，2的锁符合要求，而3个槽高为1，4，4的锁不满足要求）。求一批锁的把数。 解答（锁的个数记为L) n=3: L=8 n=4: L=64 n=5: L=360 n=6: L=1776 n=7: L=8216 n=8: L=36640问题（2） 装箱方案奇偶装箱：将槽高之和为奇数和偶数的锁分别装箱装箱方案奇偶装箱的最优性 按槽高之和的奇偶

11、分类是不是最优方案,即能否找到更好的分类装 箱方案,使不可互开的锁具个数大于2940？ 最优性的证明可以通过图论知识和计算机计算实现.图与二分图二分图的匹配交错路的概念 设M是二分图G(V,E)的一个匹配, P是G中的一条路径。 如果P的边交错在M和EM中出现, 则称P是G中的一条M交错路. 起点和终点都是G关于M的非饱和点的交错路称为一条M可扩路.最大匹配的充分必要条件 设 是二分图(,)的一个子集, N(A)是 中与A相连的节点的集合, 则存在从 到 的完全匹配的条件由下面的定理给出。 1VA 2V2V2V1V完全匹配的充要条件匈牙利算法匈牙利算法用增广路求最大匹配用增广路求最大匹配(称作

12、匈牙利算法，匈牙利称作匈牙利算法，匈牙利数学家数学家Edmonds于于1965年提出年提出)算法轮廓：算法轮廓：(1)置置M为空为空(2)找出一条增广路径找出一条增广路径P，通过取反操作获得更大，通过取反操作获得更大的匹配的匹配M代替代替M(3)重复重复(2)操作直到找不出增广路径为止操作直到找不出增广路径为止 对任意基数有限的二分图对任意基数有限的二分图G, Edmonds算算法总会给出完全匹配的存在性或者不存在性法总会给出完全匹配的存在性或者不存在性, 而存在性是通过给出一个完全匹配得到的。而存在性是通过给出一个完全匹配得到的。EDMONDS算法Step1 Step1 任意给出任意给出G

13、G的一个初始匹配的一个初始匹配 M;M;Step2 Step2 如果如果M M已经饱和了已经饱和了 中的所有节点中的所有节点, , 则则M M是是G G的一个完全匹配的一个完全匹配, , 计计算结束。否则转下一步算结束。否则转下一步; ;Step3 Step3 找出找出 中的一个非饱和点中的一个非饱和点 , , 令令Step4 Step4 考察考察 的邻接点的邻接点, , 如果如果 , , 则图则图G G不存在完全匹配不存在完全匹配, , 计计算结束算结束, , 否则转下一步否则转下一步; ;Step5 Step5 在在 中找出一点中找出一点 ；Step6 Step6 如果如果 是是M M的饱

14、和点的饱和点, , 则在则在 中找出中找出 的配对点的配对点 , , 令令 , , 转第转第4 4步步, , 否则进行下一步否则进行下一步; ;Step7 Step7 存在一条从存在一条从 到到 的可扩路的可扩路P, P, 由定理由定理1 1知知, M, M不是不是G G的最大匹配的最大匹配, , 将将M M与与P P中的边进行选择中的边进行选择, , 令令 则新的则新的M M的基数比原来的基数多的基数比原来的基数多1, 1, 转向第转向第2 2步。步。1V1Vx( )N AB ,AxB , AAxBBy( )MME Py1V( )yN ABx1Vzyy2VA二分图的匹配的算法举例1v2v3v4v5v6