《数学建模离散问题建模方法及案例分析》由会员分享，可在线阅读，更多相关《数学建模离散问题建模方法及案例分析（29页珍藏版）》请在金锄头文库上搜索。
1、离散问题建模方法 及案例分析 上海海事大学 丁颂康 一 . 离散数学的研究对象 离散数学是 “ 研究离散变量相互关系和结构的数学理论的总称。包括集合论、数论、有限群论、组合数学、图论、数理逻辑、可行计算理论等。 ” - 辞海 离散数学研究的对象是有限集合。该集合的大小又是与某些参数的组合数有关。因此，也常常被称为组合结构。 讨论的问题类型很多，主要有： 安排 (arrangement)、 分类 (grouping)、排序 (ordering)、 选择 (selection)等。 变量的 “ 离散性 ” 对象通常是以个体形式 出现 问题的 “ 离散性 ” 二分问题、七桥问题、八后问题、二十问问
2、题 方法的 “ 离散性 ” 由问题的离散性带来方法上的离散性。不存在统一的求解模式：常用的有整数规划、图论、数理逻辑等方法。更大量的则是枚举法以及所谓的启发式算法 关于算法复杂性 (complexity) 问题 算法 结果 An algorithm is considered “good” if the required number of elementary computational steps is bounded by a polynomial in the size of the problem. - J.Edmonds & R.M.Karp (1960) P - NP - NP-
3、C 二 . 离散问题建模方法 根据许多数学家的描述，离散问题通常以以下三种形式出现： “ Does the arrangement exist? ” “ How many arrangements are there? ” “ What is a best arrangement? ” 这就是存在性问题、计数问题和最优性问题。 1. 存在性问题案例 - 董事会会议安排 Mix Well For Fruitful Discussion (MCM1997-B) 一 . 问题的提出 An Tostal 公司董事会由 29名董事 (其中 9名在职 )组成。 公司要召开为期一天的董事会会议。 上午分 3
4、节 (sessions), 每节分成 6组 (groups) 下午 4 节 , 每节分成 4组。 为让董事们充分发表意见，应如何安排各节各组的 董事名单 ? 二 . 分析和建模 关于 组合设计 1. Euler36军官问题和正交拉丁方 设 是一个 n元集合。 A是一个 阶 矩阵 ,它的元素为 S中的元素。如果 S 中的每一个元素都 恰好在 A的每一行中出现一次 ,同时在 A的每一列中出现 一次 , 那么就称 A为 S上的一个 n阶拉丁方。 假设 A和 B都是 n阶拉丁方， 。如果 个有序对 各不相同。则称该两个拉丁方正 交。 , 21 naaaS nn)(),( ijij bBaA 2n ),
5、( ijij ba 正交拉丁方的存在性 1782年， Euler猜测，当 时， n阶 正交拉丁 方都不存在。 其中， 2阶的 不存在性是显然的。 6阶的 不存在性是 Tarry在 1900年证明的。也就是说， 36军官问题确实没 有解。 直到 1960年， Euler的猜想最终被推翻。 Shrikhande, Bose, Parker证明了：除了 2和 6两种特殊情况， n阶 正交 拉丁方都存在。 )4(m od2n 2. Steiner三元系 设 S是一个 n元集合， B是由 S的 一些 三元子 集组成的 集合。如果 S中的任意一对不同的元素，都恰好同时包 含在 B的唯一的一个三元子 集中
6、, 则称 ( S, B )组成一个 n 阶的 Steiner三元系 , 记作 STS(n)。 例如： (1,2,3), (1,4,5), (1,6,7), (2,4,6), (2,5,7), (3,4,7), (3,5,6) 组成一个 7阶的 Steiner三元系。 (1,2,3), (4,5,6), (7,8,9)； (1,4,7), (2,5,8), (3,6,9)； (1,5,9), (2,6,7), (3,4,8)； (1,6,8), (2,4,9), (3,5,7)。 组成一个 9阶的 Steiner三元系。 Steiner三元系的存在性： 容易见到： 1847年 ， Kirkman
7、证明了： STS(n)存在当且仅当 或者 。 Steiner三元系的图形表示： 23.1n )1(2.2 n16 kn 36 k3. Steiner三元系的推广 平衡不完全区组设计 Steiner三元系还可以向两个方向推广： 1) 将 “ 三元子集 ” 推广到 k元子集； 2) 将 “ 唯一的 ” 推广到大家重复 次。 于是就有了 平衡不完全区组设计 的概念： 设 S是一个 n元集合 ， B是由 S的 一些 k元子 集 (或称 k元 组 ) 组成的集合 。 如果 S中的任意一对不同的元素 ， 都 恰好同时包含在 B的 个 k 元 子 集中 ,则称 （ S, B） 组成 一个区组长度为 k, 相
8、遇数为 的 平衡不完全区组设计。记作 B(k,; n)。 平衡不完全区组设计的存在性： 容易见到， B(k,; n)存在的必要条件是： 1) ； 2) 。 有人证明了，除了少数情况，以上条件也是充分的。 回到原问题：由于董事会人数的关系，任意两位董事分在同组 的次数不可能做到完全平衡。只能力求平衡。以九名在职董事为 例 ，可以安排如下： )1()1( nnkk )1()1( nk 组别 1 2 3 4 5 6 上午第一节 15 29 48 36 7 - 上午第二节 39 68 1 - 24 57 上午第三节 4 - 27 18 35 69 组别 1 2 3 4 下午第一节 123 49 58
9、67 下午第二节 19 456 37 28 下午第三节 25 34 789 16 下午第四节 26 38 59 147 2.计数问题案例 - 截断切割 (CMCM1997-B) 一 .问题的提出 截断切割是指将物体沿某个切割平面切成两部分。 从一个长方体内加工出一个已知尺寸、位置预定的长方体 (两个长方体对应的平面相互平行 )，通常要经过 6次切割。 假定切割费用与切割时扫过的面积成正比，则需要考虑的不同切割方案的总数是多少？ （其它要求和其它问题略） 二 . 分析和结果 首先考虑到一共需要切割 6次。按照排列，不同方案应该有 种。 然而，因为如果两次相继的加工是切割一对相互平行的平面，那么交
10、换其顺序对整个切割费用将不产生任何影响。 这种相互平行的平面一共有 3对。其中的 1对在加工顺序中相邻的共 5!种，有某 2 对相邻的共 4!种， 3对都相邻的有 3!种。 根据组合学中的容斥原理便可得到结果： (种 ) 720!6 4 2 6!3!43!53!6 3.最优性问题案例一 - 通讯网络的最小 Steiner树 (MCM1991-B) 一 .问题的提出 9个通讯站位于以下坐标点处 : 要设计一个连接这 9个通讯站的局部网络 ,使总费用最省 . (假定连线费用与距离成正比 ). )3,10()0,25()7,35()11,23()25,33()20,20()24,16()20,5()
11、51,0(ihgfedcba 二 .问题的分析和建模 最小连接问题 : 树 连通无圈图 . 树的性质 : 1.任意两点间存在唯一的路 ; 2.边数等于点数减 1; 3.任意去掉一条边 ,树就变得不连通 ; 4.任意去掉一个非悬挂点 ,树就变得不连通 ; 5.任意添加一条边 ,就可得到唯一的圈 . 注 :3,4两条性质说明 ,就连通的意义而言 ,树具有极小性 . 子图 生成子图 生成树 最小生成树 最小生成树的 Kruskal算法和 管梅谷 算法 避圈和破圈 三角形中到三个顶点距离之和最小的点 Steiner点 推广 Steiner树 直角距离 最优性问题案例二 - 图书馆购书策略 一 . 问题
12、的提出 某学校图书馆准备添置一些新书。为了满足广大学生的需求， 图书馆对具有代表性的 300位同学中进行了调查。要求被调查的学生在科技图书、中国小说、外国文学、教辅读物等十大类书籍中选出自己的最喜欢的三种并排出顺序。（调查结果略） 假定这十种图书每册的平均价格为（元 /册） 图书种类 1 2 3 4 5 6 7 8 9 10 平均价格 22 20 24 18 18 16 20 12 15 14 请你帮图书馆出个主意，应该按照怎样的比例添置新书。这里，既要考虑经费、图书馆藏书量等因素，又要尽最大可能满足学生希望。 (2005-B DVD租赁 ) 二 . 分析与建模 经费问题：通常图书馆购置新书的
13、经费是有限的，所以希望越小越好。 藏书量问题：藏书量通常是考量图书馆规模等级的重要指标。因此，总希望尽可能大。 尽最大可能满足学生希望： 这是一种所谓消费者的偏好问题，经济学中采用效用函数的方法处理。 -就是定义一个递增（有时也可能是递减）的函数来表示消费者对不同商品的喜好程度，来度量原来不能度量的东西，把偏序改为全序。 设：第 j类图书的平均单价为 ，进货量为 ， 则进货总量和经费总量分别为： 于是对于藏书量和经费的目标可分别表示为： jc jxjjj xcj jx)10,2,1( jj jxm a x j jjxcm in 关于效用函数： 首先根据学生的喜好程度的排序，定义一个权值：这里可以将
