数学建模例题：锁具装箱ppt课件

问题：树上有十只鸟，开枪打死一只，还剩几只？,9只？还是0只？,分析：这是一道儿童时期的数学应用题。但他一样是数学建模问题，不过答案就不重要了，重要的是过程。,1,是无声手枪或别的无声的枪吗？不是。枪声有多大？80100分贝。那就是说会震得耳朵疼？是。在这个城市里打鸟犯不犯法？不犯。您确定鸟里真的没有聋子？没有。,吃饱了撑着的问答,2,有没有关在笼子里的？没有。边上还有没有其他的树，树上还有没有其他的鸟？没有有没有残疾的鸟或饿得飞不动的鸟？没有。打鸟的人眼有没有花？保证是十只？没有花，就十只。有没有傻得不怕死的鸟？都怕死。会不会一枪打死两只？不会。,3,所有的鸟都可以自由活动吗？所有的鸟都可以自由活动吗？完全可以。如果您的回答没有骗人，打死的鸟要是挂在是挂在树上没掉下来，那么就剩一只，若果掉下来，就一只不剩。,不是开玩笑，这就是数学建模。从不同度思考一个问题，想尽所有的可能，正所谓智者千虑，绝无一失，这才是数学建模的高手。,4,常用数学建模方法有：,几何理论、图论、排队论、优化方法、网络优化、插值与拟合、差分方法、微分方程、随机决策、多目标决策、层次分析、模糊数学、灰色系统理论、神经网络、随机模拟、组合概率、统计分析、时间序列、综合评价方法、机理分析等方法。,5,锁具装箱1问题2背景知识3锁具的数量4锁具的装箱方案5顾客抱怨程度,6,问题某厂生产一种弹子锁具,每个锁具的钥匙有5个槽,每个槽的高度从1,2,3,4,5,66个数(单位略)中任取一数.由于工艺及其它原因,制造锁具时对5个槽的高度还有两个限制:至少有3个不同的数;相邻两槽的高度之差不能为5.满足以上条件制造出来的所有互不相同的锁具称为一批.从顾客的利益出发,自然希望在每批锁具中“一把钥匙开一把锁”.但是在当前工艺条件下,对于同一批中两个锁具是否能够互开,有以下试验结果:若二者相对应的5个槽的高度中有4个相同,另一个槽的高度差为1,则能互开;在其它情形下,不可能互开.原来,销售部门在一批锁具中随意地取每60个装一箱出售.团体顾客往往购买几箱到几十箱,他们抱怨购得的锁具会出现互开的情形.现聘你为顾问,回答并解决以下的问题:每一批锁具有多少个,装多少箱.为销售部门提出一种方案,包括如何装箱(仍是60个锁具一箱),如何给箱子以标志,出售时如何利用这些标志,使团体顾客不再或减少抱怨.采取你提出的方案,团体顾客的购买量不超过多少箱,就可以保证一定不会出现互开的情形.按照原来的装箱办法,如何定量地衡量团体顾客抱怨互开的程度(试对购买一、二箱者给出具体结果).,7,背景1,8,背景2,9,背景3:锁的历史,中华古锁起源于5000年前的仰韶文化时期，后经历代能工巧匠的不断努力，生产制作出了无数把质地不同、造形各异、机关巧布的古锁。质地有：金、银、铜、铁、铝、木等，古锁生产材料的变化反映了人类社会不断进步、不断发展的轨迹；造形上有：与帝王到百姓生活有关的各种吉祥图案。用途不一样的古锁，体现出了各历史时期丰富的社会文化内涵，展示中华古锁工艺的精湛。,10,木锁,11,木制大钥匙,12,宝瓶双式木锁,13,琵琶锁,14,首饰锁-麒麟,15,文字组合锁具,16,动物锁,17,广锁,18,清代锁,19,工艺锁,20,抗战锁,21,连心锁,22,挂锁,23,门锁,24,指纹门锁,25,指纹识别技术,crossover：交叉core：核bifurcation：分ridgeending：脊断点island：岛型delta：三角形区域pore：孔,26,27,背景4,国家标准：GB-9303-88（轻工业）门锁，1988年颁布互开率：优等品和一等品：0.204%;合格品：0.286%。互开率检验：抽取50把，分5组检验，9分钟换一次，共45分钟；互开率：R为互开出现次数，T为抽样数。,28,背景5,为什么要求至少3个不同的槽高？为什么相邻高差不为5？为什么“若二者相对应的5个槽的高度中有4个相同,另一个槽的高度差为1,则能互开;在其它情形下,不可能互开”？锁厂调研的情况：生产，装箱。,29,问题（1）A：计算机求解,循环判断，排除不合格的，累加统计一批锁的数量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);neighbors=max(abs(a1-a2),abs(a2-a3),abs(a3-a4),abs(a4-a5);ifnumbers0.5ifneighbors4.5s=s+1;endendendendendendends,30,问题（1）B：排列组合法,31,32,33,问题（1）C:递推法,34,35,问题（1）D:图论法,36,37,38,39,40,41,42,总数的计算,无16相邻的锁具减去仅有一个和两个槽个的锁具6306-6-420=5880,43,类似的问题：锁具的个数,某厂生产一种弹子锁具，每个锁具有n个槽(2n9,n为自然数)，每个槽的高度从1，2，3，4这4个数(单位略)中任取一个，限制至少有一个相邻的槽高之差等于3，且至少有3个不同的槽高。每个槽的高度取遍这4个数且满足上面这两个限制时生产出一批锁（例如，当n等于3时，3个槽高为1，4，2的锁符合要求，而3个槽高为1，4，4的锁不满足要求）。求一批锁的把数。,44,解答（锁的个数记为L),n=3:L=8n=4:L=64n=5:L=360n=6:L=1776n=7:L=8216n=8:L=36640,45,问题（2）装箱方案,46,奇偶装箱：将槽高之和为奇数和偶数的锁分别装箱,47,装箱方案,48,奇偶装箱的最优性,按槽高之和的奇偶分类是不是最优方案,即能否找到更好的分类装箱方案,使不可互开的锁具个数大于2940？最优性的证明可以通过图论知识和计算机计算实现.,49,图与二分图,50,二分图的匹配,51,交错路的概念,设M是二分图G(V,E)的一个匹配,P是G中的一条路径。如果P的边交错在M和EM中出现,则称P是G中的一条M交错路.起点和终点都是G关于M的非饱和点的交错路称为一条M可扩路.,52,最大匹配的充分必要条件,53,54,设是二分图(,)的一个子集,N(A)是中与A相连的节点的集合,则存在从到的完全匹配的条件由下面的定理给出。,55,完全匹配的充要条件,56,57,匈牙利算法,用增广路求最大匹配(称作匈牙利算法，匈牙利数学家Edmonds于1965年提出)算法轮廓：(1)置M为空(2)找出一条增广路径P，通过取反操作获得更大的匹配M代替M(3)重复(2)操作直到找不出增广路径为止对任意基数有限的二分图G,Edmonds算法总会给出完全匹配的存在性或者不存在性,而存在性是通过给出一个完全匹配得到的。,58,Edmonds算法,Step1任意给出G的一个初始匹配M;Step2如果M已经饱和了中的所有节点,则M是G的一个完全匹配,计算结束。否则转下一步;Step3找出中的一个非饱和点,令Step4考察的邻接点,如果,则图G不存在完全匹配,计算结束,否则转下一步;Step5在中找出一点；Step6如果是M的饱和点,则在中找出的配对点,令,转第4步,否则进行下一步;Step7存在一条从到的可扩路P,由定理1知,M不是G的最大匹配,将M与P中的边进行选择,令则新的M的基数比原来的基数多1,转向第2步。,59,60,二分图的匹配的算法举例,61,一些技巧：提高速度,初始匹配的寻找可扩路的寻找一个简单