《全国大学生数学建模cumcm权威：丁颂康离散讲义》由会员分享，可在线阅读，更多相关《全国大学生数学建模cumcm权威：丁颂康离散讲义（36页珍藏版）》请在金锄头文库上搜索。
1、数模竞赛中的离散问题,上海海事大学 丁颂康,一.组合结构的存在性,案例一 无线电信道的分配(MCM2000-B) Radio Channel Assignment,一. 问题的提出二. 分析和建模-至少需要9个频段-归结为填数游戏-填法的存在性,案例二 实验数据分解(CMCM1992-B),一. 问题的提出组成蛋白质的若干种氨基酸可以形成不相同的组合。要求将蛋白质的分子量X 分解为几个氨基酸的已知分子量 之和。如果已知:分解结果如何？,二.分析与建模问题归结为求不定方程（Diophantus方程）的非负整数解。(或者有时将是0-1解)最简单的不定方程：这里 都是整数存在整数解的充分必要条件是其
2、中 为最大公约数。,案例三 董事会会议安排(MCM1997-B) Mix Well For Fruitful Discussion,一. 问题的提出 An Tostal公司董事会由29名董事(其中9名在职)组成。公司要召开为期一天的董事会会议:上午分3节(sessions), 每节分成6组(groups)下午分4节,每节分成4组。 为让董事们充分发表意见，应如何安排各节各组的董事名单?,二. 分析和建模 关于组合设计1. Euler36军官问题和正交拉丁方设 是一个n元集合。A是一个 阶 矩阵,它的元素为S中的元素。如果S 中的每一个元素都 恰好在A的每一行中出现一次,同时在A的每一列中出现
3、一次, 那么就称A为S上的一个n阶拉丁方。假设A和B都是n阶拉丁方， 。如果 个有序对 各不相同。则称该两个拉丁方正交。,正交拉丁方的存在性1782年，Euler猜测，当 时，n阶正交拉丁 方都不存在。 其中，2阶的不存在性是显然的。6阶的不存在性是 Tarry在1900年证明的。也就是说，36军官问题确实没 有解。直到1960年， Euler的猜想最终被推翻。Shrikhande, Bose, Parker证明了：除了2和6两种特殊情况， n阶正交 拉丁方都存在。,2. Steiner三元系设S是一个n元集合，B是由S的一些三元子集组成的 集合。如果S中的任意一对不同的元素，都恰好同时包 含
4、在B的唯一的一个三元子集中, 则称( 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证明了：S
5、TS(n)存在当且仅当 或者 。Steiner三元系的图形表示：,3. Steiner三元系的推广平衡不完全区组设计,Steiner三元系还可以向两个方向推广：1) 将“三元子集”推广到k元子集；2) 将“唯一的”推广到大家重复次。于是就有了平衡不完全区组设计的概念：设S是一个n元集合，B是由S的一些k元子集(或称k元 组) 组成的集合。如果S中的任意一对不同的元素，都 恰好同时在 B 中的个 k 元子集中出现, 则称 (S,B) 组 成一个区组长度为 k , 相遇数为的平衡不完全区组设 计。记作B(k,; n)。,平衡不完全区组设计的存在性：容易见到， B(k,; n)存在的必要条件是：1)
6、 ；2) 。有人证明了，除了少数情况，以上条件也是充分的。回到原问题：由于董事会人数的关系，任意两位董事分在同组的次数不可能做到完全平衡。只能力求平衡。以九名在职董事为例 ，可以安排如下：,二. 组合计数,案例四. 截断切割(CMCM1997-B),一.问题的提出截断切割是指将物体沿某个切割平面切成两部分。从一个长方体内加工出一个已知尺寸、位置预定的长方体(两个长方体对应的平面相互平行)，通常要经过6次切割。假定切割费用与切割时扫过的面积成正比，则需要考虑的不同切割方案的总数是多少？（其它要求和其它问题略）,二. 分析和结果首先考虑到一共需要切割6次。按照排列，不同方案应该有 种。然而，因为如
7、果两次相继的加工是切割一对相互平行的平面，那么交换其顺序对整个切割费用将不产生任何影响。这种相互平行的平面一共有3对。其中的1对在加工顺序中相邻的共5!种，有某2 对相邻的共4!种， 3对都相邻的有3!种。根据组合学中的容斥原理便可得到结果：(种),案例五.锁具装箱(CMCM1994-B),一. 问题的提出一种弹子锁的钥匙有5个槽。每个槽的高度可以用16中的某个数表示。工艺及其它原因, 5个槽的高度还有两个限制：1）至少有3个不同的数；2）相邻两槽的高度差不能为5。满足以上条件的不同锁具称为一批。问题：每一批锁共有多少把？（其它问题从略）,二. 分析与结果首先，一个五位数，每个位置的数有6种可
8、能。总共有 即7776种可能。其次，只出现一个数字的有6种。只出现两个数字的有 即450种可能。再次，相邻两位数字差5的情况比较复杂。这里采用枚举的方法。可得共1470种可能。最后，运用容斥原理，得到一批锁具的总数为(把),三.最优性问题,案例六 钻井的合理布局(CMCM1999-B),一. 问题的提出旧井坐标：( 0.50, 2.00 ) ( 1.41, 3.50 ) ( 3.00, 1.50 ) ( 3.37, 3.51 ) ( 3.40, 5.50 ) ( 4.72, 2.00 ) ( 4.72, 6.24 ) ( 5.43, 4.10 ) ( 7.57, 2.01 ) ( 8.38,
9、4.50 ) ( 8.98, 3.41 ) ( 9.50, 0.80 )撒网式钻探：新井位于坐标格点。如果预定井位与旧井距离小于给定的 , 则旧井的资料可以直接利用，不必再打新井。考虑以下不同情况，坐标架的最佳位置：1)坐标架允许平移或旋转；2)直角距离和欧氏距离。,案例七 通讯网络的最小Steiner树 (MCM1991-B)一.问题的提出9个通讯站位于以下坐标点处:要设计一个连接这9个通讯站的局部网络,使总费用最省。 (假定连线费用与距离成正比)。,二.问题的分析和建模最小连接问题：树连通无圈图。树的性质：1.任意两点间存在唯一的路；2.边数等于点数减1；3.任意去掉一条边,树就变得不连通
10、；4.任意去掉一个非悬挂点,树就变得不连通；5.任意添加一条边,就可得到唯一的圈。注：3、4两条性质说明, 就连通的意义而言, 树具有极小性。,子图生成子图生成树最小生成树最小生成树的Kruskal算法和管梅谷算法避圈和破圈三角形中到三个顶点距离之和最小的点 Steiner点 推广 Steiner树直角距离,案例八 彩票中的数学(CMCM-B),一. 问题的提出赛题列出了29种彩票的得奖方案和奖金数额(或比例)这里举出其中的两种：要求根据方案的具体情况，综合分析各种奖项出现的可能性、奖项和奖金额的设置以及对彩民的吸引力等因素评价各方案的合理性。,二. 分析与建模.假定和假设1彩民购买彩票的事件
11、及所选的号码都是随机的；2彩票的开奖是公平公正的，得奖号码的出现是等可能的；3彩票销售量是足够的，销售总额的50%足以支付各级奖金。.获奖概率的计算(略). 通常把一、二、三等奖称为高项奖。又依据返奖率50%的规定，单注彩票获奖额的数学期望,有 j =1, 2, 3 (其中 为第 j 等高项奖的分配比例)。于是单注彩票第 j 等高项奖奖金的期望值 j =1, 2, 3 iv. 吸引力的度量方法:衡量彩票设奖方案的好坏，可以用函数作为评价设奖方案的合理性的指标。其中 为奖金额对彩民的吸引力函数。它通常与平均收入、消费水平以及彩民的心理素养等总多因素有关。命题老师则是采用平均吸引力的概念定义的心理
12、曲线的方法。,另一种可供参考的方法是将高项奖奖金额的大小作为一个目标，而将中奖面的大小也就是总的获奖率作为一个目标，用多目标规划处理。即考虑两个目标：这两个目标又是相互矛盾的。通常可以用对两个目标加权的方法，或者将一个目标改为约束而转化为单目标问题。注：多目标优化也是一种常见的问题。,案例九 图书馆购书策略,一. 问题的提出某公共图书馆准备添置一些新书。为了更好地满足广大读者的需求，图书馆对具有代表性的300位读者进行了调查。 要求被调查的读者在科技图书、中国小说、外国文学、教辅读物等十大类书籍中选出自己的最喜欢的三种并排出顺序（调查结果略）。,假定这十种图书每册的平均价格为（元/册） 请你帮
13、图书馆出个主意，应该按照怎样的比例添置新书。这里，既要考虑经费、图书馆藏书量等因素，又要尽最大可能满足读者的希望。,二.分析与建模,1.目标:a. 购书所用经费-显然希望用尽可能少的费用；b. 图书馆藏书量-这是考核图书馆的一项重要指标，自然是尽可能大为好；c. 读者满意程度-尽可能最大限度满足读者的需求。按照题意，其中的目标c将是最主要的。,2. 关于读者需求对300名读者所作的调查结果, 和一种被称为“消费者偏好” 的经济学概念有关。它是指消费者根据自己的喜好程度对若干种商品排出的一种顺序。 这种偏好完全由消费者的主观意识决定的，结果因人而异。一般来说，如何描述这个序前后两项在喜好程度上的
14、差异没有统一的标准。 对于不同消费者来说，差别更大。其次，对于商品集合的不同子集(消费结果)，消费者究竟偏好哪一个, 也并不是都可以两两进行比较排出其顺序。这种结构在数学上称为偏序关系。要用数学工具处理，就必须对偏好程度进行量化，使原来不能比较的不同方案也能进行比较，把偏序改为全序。,偏好程度量化的一种方法就是设置一个指标体系。对每件商品分别赋以一个实数，作为它的权。按照消费者的偏好关系, 排在前面的商品赋以较大的权。这样一来, 不同消费方案，就可以通过权来进行比较了。消费者的消费方案,也就是他所选择的若干种商品(经济学里称为消费束)。将这些商品对应的权累加, 所得结果就是经济学范畴讨论的该种
15、消费方案的效用函数。值得注意的是：表示偏好的指标以及由它派生出来的效用函数不是唯一的。在不同的效用函数定义下，偏序到全序的转化效果也是不一样的。参照效用函数的概念, 可以对读者满意程度进行量化描述。,在对读者满意程度量化过程中，应当注意以下几个问题：1. 赋权：根据满意度排序，可以分别赋以 等值；也可分别赋以 等值；(见仁见智, 但效果将不同)。2. 注意人数的均匀性：在300位读者打分时，每类图书得到读者分的数量差别很大。为尽量减少这种不公平，可否考虑对没有选到的大类图书添补一个最小分值。使每类图书得分数都达到300个；3. 构造效用函数：将具有代表性的300位读者按照喜欢程度排序相应的得分相加，得到十大类图书的效用函数值 ；4. 读者满意程度最大化目标：如以 表示第j类图书的进书量，则目标可表示为：,
