建立组合数数学建模例子.doc

对五个球的排序问题对五个球的排序问题摘要：摘要： 现有 ABCDE5 个球构成的排列组合,可重复抽取.最多取到 16 个,共有多少种组合方式？问题重塑问题重塑：：现有 ABCDE5 个球构成的排列组合,可重复抽取.最多取到 16 个,共有多少种组合方式？为 分析题目对其进行一些假设分析五个球的组合，运用数学排序的函数对它进行分析， 计算模型假设：模型假设： 假设 1：假设球完全一样，摸到的几率相等 假设 2：重复抽取时，先捣乱再抽取 假设 3：抽取的个数大于等于一符号设定：符号设定：*为乘号； C(N,M)为排序符号； A,B,C,D,E 为五种球的种类 \ 为除法的符号模型的建立与求解：模型的建立与求解： 取 1 个球可以构成的组合有 A B C D E 共 5 种 取 2 个球可以构成的组合有 5+4+3+2+1=15 种 （BA 和 AB 这种重复的 排列 算成一种） AA AB AC AD AE BB BC BD BE CC CD CE DD DE EE 取 3 个球可以构成的组合是 （5+4+3+2+1）+（4+3+2+1）+（3+2+1） +（2+1）+1= 35 种 AAA AAB AAC AAD AAE ABB ABC ABD ABE ACC ACD ACE ADD ADE AEEBBB BBC BBD BBE BCC BCD BCE BDD BDE BEECCC CCD CCE CDD CDE CEEDDD DDE DEEEEE 取四个球的方法： AAAA AAAB AAAC AAAD AAAE AABA AACA AADA AAEAAABB AABC AABD AABE AACB AADB AAEB AACC AACD AACE AADC AAEC AADD AADE AAED AAEE BBBB BBBC BBBD BBBE BBCB BBEB BBCC BBCD BBCE BBDC BBEC BBDD BBDE BBED BBEECCCC CCCD CCCE CCDC CCEC CCDD CCDE CCED CCEEDDDD DDDE DDED DDEEEEEE以上都可以采用树枝法来计算。

从上述的排列可以看出此次题目可以运用数学排序问题来解决 如取一次球时可得到：5！/1！*4！=5 种方法； 再有取两次球可得到：两次的取法都有 5！/1！*4！=5 种；从两次中分别去取 一个球得到 C(5,2)=15; 可以推出一下的结论： 从 ABCDE 这 5 个球里,重复抽取 N 个, 有 C(n,n+5-1)=C(n,n+4)=C(4,n+4)个组合. 取 1 个球的组合有 C(1,5)=5 种 取 2 个球的组合有 C(2,6)=15 种 取 3 个球的组合有 C(3,7)=35 种 取 4 个球的组合有 C(4,8)=70 种 取 5 个球的组合有 C(5,9)=15 种取 6 个球的组合有 C(4,n+4)=C(4,10)种 最多能取 16 个=C(4,20)种 取 1-16 个的过程中 总计有: C(4,5)+C(4,6)+...+C(4,20) 不难发现把所有的情况列出之后，再通过公式计算，得到的结果是一样的，这 样充分的说明了这个模型的正确性，同时运用这种方法避免了大量的草稿，画 图等等的计算节省了很多时间尤其是推广到后面，随着推后计算量也大大的 加大了，采用直接的方法明显不合适了，说明这个模型在简洁方面有很大的优 势。

评价方案：评价方案：本方案还有很多没有考虑到的问题，例如抽取球的环境，是否在黑袋子里抽取还有抽取的方式，还有其他的诸多因素并且有数学知识可知道排序函数的使用是有要求的在组合的定义中,C 二表示从个不同元素中取出 R 个元素的组合数这里 n、R 满足条件, (1):R, (2)n、R 都是自然数 在解一些含有组合符号的题目时,常常要考虑这两个条件组合数的应用还有很多如组合数学中的著名问题地图着色问题：对世界地图着色，每一种国家使用一种颜色如果要求相邻国家的颜色相异，是否总共只需四种颜色？这是图论的问题 四色定理指出每个可以画出来的地图都可以至多用 4 种颜色来上色，而且没有两个相接的区域会是相同的颜色被称为相接的两个区域是指他们共有一段边界，而不是一个点这一定理最初是由 Francis Guthrie 在 1853 年提出的猜想很明显，3 种颜色不会满足条件，而且也不难证明 5 种颜色满足条件且绰绰有余但是，直到 1977 年四色猜想才最终由 Kenneth Appel 和 Wolfgang Haken 证明他们得到了 J. Koch 在算法工作上的支持证明方法将地图上的无限种可能情况减少为 1,936 种状态（稍后减少为 1,476 种），这些状态由计算机一个挨一个的进行检查。

这一工作由不同的程序和计算机独立的进行了复检在 1996 年，Neil Robertson、Daniel Sanders、Paul Seymour 和 Robin Thomas 使用了一种类似的证明方法，检查了 633 种特殊的情况这一新证明也使用了计算机，如果由人工来检查的话是不切实际的四色定理是第一个主要由计算机证明的理论，这一证明并不被所有的数学家接受，因为它不能由人工直接验证最终，人们必须对计算机编译的正确性以及运行这一程序的硬件设备充分信任参见实验数学缺乏数学应有的规范成为了另一个方面；以至于有人这样评论“一个好的数学证明应当像一首诗——而这纯粹是一本簿！”船夫过河问题：船夫要把一匹狼、一只羊和一棵白菜运过河只要船夫不在场，羊就会吃白菜、狼就会吃羊船夫的船每次只能运送一种东西怎样把所有东西都运过河？这是线性规划的问题 中国邮差问题：由中国组合数学家管梅谷教授提出邮递员要穿过城市的每一条路至少一次，怎样行走走过的路程最短？这不是一个 NP 完全问题，存在多项式复杂度算法：先求出度为奇数的点，用匹配算法算出这些点间的连接方式，然后再用欧拉路径算法求解这也是图论的问题 任务分配问题（也称婚配问题）：有一些员工要完成一些任务。

各个员工完成不同任务所花费的时间都不同每个员工只分配一项任务每项任务只被分配给一个员工怎样分配员工与任务以使所花费的时间最少？这是线性规划的问题因此这方案的应用范围非常广泛参考文献：参考文献：【1】网络搜寻；【2】数学建模与数学实验 高等教育出版 2008.1；【3】 中国大学生数学建模竞赛，李大潜主编，高等教育出版社(1998)． 【4】 大学生数学建模竞赛教材， (一)(二)(三)，叶其孝主编，湖南教育 出版社(1993，1997，1998)． 【5】 数学建模教育与国际数学建模竞赛 《工科数学》专辑，叶其孝主编，《工科数学》杂志社，1994)．。