数学建模离散问题建模方法及案例分析

离散问题建模方法及案例分析上海海事大学丁颂康[e-mail]一.离散数学的研究对象•离散数学是“研究离散变量相互关系和结构的数学理论的总称。包括集合论、数论、有限群论、组合数学、图论、数理逻辑、可行计算理论等。”-----《辞海》•离散数学研究的对象是有限集合。该集合的大小又是与某些参数的组合数有关。因此，也常常被称为组合结构。•讨论的问题类型很多，主要有：•安排(arrangement)、分类(grouping)、排序(ordering)、选择(selection)等。•变量的“离散性”—对象通常是以个体形式出现……•问题的“离散性”—二分问题、七桥问题、八后问题、二十问问题……•方法的“离散性”—由问题的离散性带来方法上的离散性。不存在统一的求解模式：常用的有整数规划、图论、数理逻辑等方法。更大量的则是枚举法以及所谓的启发式算法……•关于算法复杂性(complexity)•问题—算法—结果•Analgorithmisconsidered“good”iftherequirednumberofelementarycomputationalstepsisboundedbyapolynomialinthesizeoftheproblem.----J.Edmonds&R.M.Karp(1960)•P---NP---NP-C二.离散问题建模方法根据许多数学家的描述，离散问题通常以以下三种形式出现：“Doesthearrangementexist?”“Howmanyarrangementsarethere?”“Whatisabestarrangement?”这就是存在性问题、计数问题和最优性问题。1.存在性问题案例----董事会会议安排MixWellForFruitfulDiscussion(MCM1997-B)一.问题的提出AnTostal公司董事会由29名董事(其中9名在职)组成。公司要召开为期一天的董事会会议。上午分3节(sessions),每节分成6组(groups)下午4节,每节分成4组。为让董事们充分发表意见，应如何安排各节各组的董事名单?二.分析和建模关于组合设计1.Euler36军官问题和正交拉丁方设是一个n元集合。A是一个阶矩阵,它的元素为S中的元素。如果S中的每一个元素都恰好在A的每一行中出现一次,同时在A的每一列中出现一次,那么就称A为S上的一个n阶拉丁方。假设A和B都是n阶拉丁方，。如果个有序对各不相同。则称该两个拉丁方正交。},,,{21naaaSnn)(),(ijijbBaA2n),(ijijba•正交拉丁方的存在性•1782年，Euler猜测，当时，n阶正交拉丁方都不存在。其中，2阶的不存在性是显然的。6阶的不存在性是Tarry在1900年证明的。也就是说，36军官问题确实没有解。•直到1960年，Euler的猜想最终被推翻。Shrikhande,Bose,Parker证明了：除了2和6两种特殊情况，n阶正交拉丁方都存在。)4(mod2n•2.Steiner三元系设S是一个n元集合，B是由S的一些三元子集组成的集合。如果S中的任意一对不同的元素，都恰好同时包含在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证明了：STS(n)存在当且仅当或者。Steiner三元系的图形表示：23.1n)1(2.2n16kn36k3.Steiner三元系的推广—平衡不完全区组设计•Steiner三元系还可以向两个方向推广：1)将“三元子集”推广到k元子集；2)将“唯一的”推广到大家重复λ次。•于是就有了平衡不完全区组设计的概念：•设S是一个n元集合，B是由S的一些k元子集(或称k元组)组成的集合。如果S中的任意一对不同的元素，都恰好同时包含在B的λ个k元子集中,则称（S,B）组成一个区组长度为k,相遇数为λ的平衡不完全区组设计。记作B(k,λ;n)。•平衡不完全区组设计的存在性：•容易见到，B(k,λ;n)存在的必要条件是：1)；2)。•有人证明了，除了少数情况，以上条件也是充分的。回到原问题：由于董事会人数的关系，任意两位董事分在同组的次数不可能做到完全平衡。只能力求平衡。以九名在职董事为例，可以安排如下：)1()1(nnkk)1()1(nk组别123456上午第一节152948367--上午第二节39681--2457上午第三节4--27183569组别1234下午第一节123495867下午第二节194563728下午第三节253478916下午第四节2638591472.计数问题案例----截断切割(CMCM1997-B)•一.问题的提出•截断切割是指将物体沿某个切割平面切成两部分。•从一个长方体内加工出一个已知尺寸、位置预定的长方体(两个长方体对应的平面相互平行)，通常要经过6次切割。•假定切割费用与切割时扫过的面积成正比，则需要考虑的不同切割方案的总数是多少？••（其它要求和其它问题略）•二.分析和结果•首先考虑到一共需要切割6次。按照排列，不同方案应该有种。•然而，因为如果两次相继的加工是切割一对相互平行的平面，那么交换其顺序对整个切割费用将不产生任何影响。•这种相互平行的平面一共有3对。其中的1对在加工顺序中相邻的共5!种，有某2对相邻的共4!种，3对都相邻的有3!种。•根据组合学中的容斥原理便可得到结果：•(种)720!6426!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()51,0(ihgfedcba二.问题的分析和建模最小连接问题:树—连通无圈图.树的性质:1.任意两点间存在唯一的路;2.边数等于点数减1;3.任意去掉一条边,树就变得不连通;4.任意去掉一个非悬挂点,树就变得不连通;5.任意添加一条边,就可得到唯一的圈.注:3,4两条性质说明,就连通的意义而言,树具有极小性.•子图—生成子图—生成树•最小生成树•最小生成树的Kruskal算法和管梅谷算法—避圈和破圈•三角形中到三个顶点距离之和最小的点—Steiner点•推广—Steiner树•直角距离最优性问题案例二----图书馆购书策略•一.问题的提出•某学校图书馆准备添置一些新书。为了满足广大学生的需求，图书馆对具有代表性的300位同学中进行了调查。要求被调查的学生在科技图书、中国小说、外国文学、教辅读物等十大类书籍中选出自己的最喜欢的三种并排出顺序。（调查结果略）假定这十种图书每册的平均价格为（元/册）图书种类12345678910平均价格22202418181620121514请你帮图书馆出个主意，应该按照怎样的比例添置新书。这里，既要考虑经费、图书馆藏书量等因素，又要尽最大可能满足学生希望。(2005-BDVD租赁)二.分析与建模•经费问题：通常图书馆购置新书的经费是有限的，所以希望越小越好。•藏书量问题：藏书量通常是考量图书馆规模等级的重要指标。因此，总希望尽可能大。•尽最大可能满足学生希望：这是一种所谓消费者的偏好问题，经济学中采用效用函数的方法处理。---就是定义一个递增（有时也可能是递减）的函数来表示消费者对不同商品的喜好程度，来度量原来不能度量的东西，把偏序改为全序。•设：第j类图书的平均单价为，进货量为，则进货总量和经费总量分别为：•于是对于藏书量和经费的目标可分别表示为：jcjxjjjxcjjx)10,2,1(jjjxmaxjjjxcmin•关于效用函数：首先根据学生的喜好程度的排序，定义一个权值：这里可以将学生偏爱的三类以及其它类的图书分别赋值7,5,3,1，记第j类图书的权为；•构造出购书方案总的效用函数：“尽最大可能满足学生希望”的目标就是：jwjjjxwjjjxwmaxjjxmaxjjjxcminjjjxwmaxjjjxwmaxcxcjjjjjXxtosubject综合起来，便得到原问题的数学模型：这是一个多目标最优化问题。根据本问题的特点，可以采用将次要目标改成约束的方法，即将它改为：谢谢2011.7