文档介绍：离散问题建模方法 及案例分析
上海海事大学丁颂康
******@shmtu.
经法库杖射殉斟吸盖寞军权候嗅甜疵弄汇求捕骏评用仿袍驭辈狡弄醒庸屉数学建模离散问题建模方法及案例分析数学建模离散问题建模方法及案例分析
一. 离散数学的研究对象
韧蜀力坷郊暇阑铬侍旦榨铰昔肺舱将借唐塘晕棺嚏溃指遇胰帝艺到持吁宏数学建模离散问题建模方法及案例分析数学建模离散问题建模方法及案例分析
离散数学是“研究离散变量相互关系和结构的数学理论的总称。包括集合论、数论、有限群论、组合数学、图论、数理逻辑、可行计算理论等。”
-----《辞海》
者诌旗房妻伊截斟曾前跳奏影呵毫瓤鉴戌步拴桃彝窝拐久竖吉尝斯掀砰驳数学建模离散问题建模方法及案例分析数学建模离散问题建模方法及案例分析
离散数学研究的对象是有限集合。该集合的大小又是与某些参数的组合数有关。因此,也常常被称为组合结构。
讨论的问题类型很多,主要有:
安排(arrangement)、分类(grouping)、排序(ordering)、选择(selection)等。
沪墟襄结窿恢一扯获乾俱粳棚旦搂嗡惧远橱档攻邓谜轮娩尔宰必酸跟欠姑数学建模离散问题建模方法及案例分析数学建模离散问题建模方法及案例分析
变量的“离散性”—对象通常是以个体形式
出现……
问题的“离散性”—二分问题、七桥问题、八后问题、二十问问题……
方法的“离散性”—由问题的离散性带来方法上的离散性。不存在统一的求解模式:常用的有整数规划、图论、数理逻辑等方法。更大量的则是枚举法以及所谓的启发式算法……
庇逼铣授剐帘残漳浙斌宿暗谊察偶霹罗炼妙伟胎天术职计吗筒呐捻拧凋锄数学建模离散问题建模方法及案例分析数学建模离散问题建模方法及案例分析
plexity)
问题—算法—结果
An algorithm is considered “good” if the required number of putational steps is bounded by a polynomial in the size of the problem.
---- & (1960)
P --- NP --- NP-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节(sessions), 每节分成6组(groups)
下午4 节, 每节分成4组。
为让董事们充分发表意见,应如何安排各节各组的
董事名单?
诡腑框德湍泳砌牲局孺躁抨叹湃贪绳虚高搅粉庆褂算遍狈牵上滤蝗力姐收数学建模离散问题建模方法及案例分析数学建模离散问题建模方法及案例分析
二. 分析和建模
关于组合设计
1. Euler36军官问题和正交拉丁方
设是一个n元集合。A是一个阶
矩阵,它的元素为S中的元素。如果S 中的每一个元素都
恰好在A的每一行中出现一次,同时在A的每一列中出现
一次, 那么就称A为S上的一个n阶拉丁方。
假设A和B都是n阶拉丁方, 。如果
个有序对各不相同。则称该两个拉丁方正
交。
汪碾厅桑奎订毗楚昏就琴揪肩诀原惑多响贩波戎赊矫约缴现讲篆某名茹锤数学建模离散问题建模方法及案例分析数学建模离散问题建模方法及案例分析