数学建模例题：锁具装箱.pptVIP

二分图的匹配的算法举例 一些技巧：提高速度 初始匹配的寻找 可扩路的寻找 一个简单的算法： 最困难的先解决，可以减小难度，提高效率。 进一步探讨的问题：在奇偶分类的基础上再分类 问题（3）：进一步分类后的互开分析 问题（4）：顾客抱怨程度的定量化 对特挑剔的顾客 对一般顾客 利用计算机模拟的方法 随机装箱的方案 奇偶分类装箱的方案 在奇偶分类基础上再分类 练习 利用匈牙利算法给出下面二分图的一个最大匹配 背景4 国家标准：GB-9303-88（ 轻工业）门锁， 1988年颁布 互开率： 优等品和一等品：0.204%; 合格品： 0.286%。 互开率检验： 抽取50把，分5组检验， 9分钟换一次，共45分钟； 互开率： R为互开出现次数，T为抽样数。 背景5 为什么要求至少3个不同的槽高？ 为什么相邻高差不为5？ 为什么“若二者相对应的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-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 end end s 问题（1） B：排列组合法 问题（1） C: 递推法 问题（1） D: 图论法 总数的计算 无16相邻的锁具 减去 仅有一个和两个槽个的锁具 6306-6-420=5880 类似的问题：锁具的个数 某厂生产一种弹子锁具，每个锁具有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） 装箱方案 奇偶装箱：将槽高之和为奇数和偶数的锁分别装箱 装箱方案 奇偶装箱的最优性 按槽高之和的奇偶分类是不是最优方案,即能否找到更好的分类装 箱方案,使不可互开的锁具个数大于2940？ 最优性的证明可以通过图论知识和计算机计算实现. 图与二分图 二分图的匹配 交错路的概念 设M是二分图G＝(V,E)的一个匹配, P是G中的一条路径。 如果P的边交错在M和E＼M中出现, 则称P是G中的一条M－交错路. 起点和终点都是G关于M的非饱和点的交错路称为一条M－可扩路. 最大匹配的充分必要条件 设 是二分图Ｇ＝(Ｖ,Ｅ)的一个子集, N(A)是 中与A相连的节点的集合, 则存在从