数学建模(浙江大学杨启帆)

数学建模教学数学模型（MathematicalModel）是用数学符号、数学式子、程序、图形等对实际课题本质属性的抽象而又简洁的刻划，它或能解释某些客观现象，或能预测未来的发展规律，或能为控制某一现象的发展提供某种意义下的最优策略或较好策略。数学建模（MathematicalModeling）应用知识从实际课题中抽象、提炼出数学模型的过程。数学模型的分类分类标准具体类别对某个实际问题了解的深入程度白箱模型、灰箱模型、黑箱模型模型中变量的特征连续型模型、离散型模型或确定性模型、随机型模型等建模中所用的数学方法初等模型、微分方程模型、差分方程模型、优化模型等研究课题的实际范畴人口模型、生态系统模型、交通流模型、经济模型、基因模型等1.逻辑、图论模型例1在每一次人数不少于6人的聚会中必可找出这样的3人，他们或者彼此均认识或者彼此均不认识。利用图的方法来描述该问题。将人看成顶点，两人彼此都认识用实线连，否则虚线。证明：§1.相识问题（拉姆齐问题）问题转化为在一个6阶图中必存在实线三角形或虚线三角形。υ2υ1υ3υ4υ6υ5υ1υ2υ3υ4任取一顶点，不妨v1考察υ2υ3、υ2υ4和υ3υ4υ2υ3、υ2υ4和υ3υ4只能是虚线，否则得证但这样三角形υ2υ3υ4的三边均为虚线不妨取υ1υ2、υ1υ3、υ1υ4实线与υ1相连的边必然有：实线条数不小于3或虚线条数不小于3拉姆齐问题也可这样叙述：6阶2色完全图中必含有3阶单色完全图。其他类似可推出的结果：命题5.1任一6阶2色完全图中至少含有两个3阶单色完全图。证明：前面证明必存在3阶单色完全图，不妨设υ1υ2υ3为红色完全图υ1υ5、υ2υ5、υ3υ5中至少有两条黑色、故υ1υ5与υ2υ5中至少有一条是黑色若υ4υ5υ6也是红色三角形，命题已得证故至少一边与υ1υ2υ3的边异色，不妨设υ4υ5黑色υ1υ4、υ2υ4、υ3υ4至少应有两条黑色，不妨设υ1υ4、υ2υ4黑色所以存在第二个3阶单色完全图。υ2υ1υ3υ4υ6υ5命题5.27阶2色完全图至少含有4个3阶单色安全图。命题5.318阶2色完全图中必含有4阶单色完全图。对拉姆齐问题的认识不能仅仅停留在例5.1的水平上。利用逻辑推理方法，实际上还可获得一大批结果。例2.（婚姻问题）在遥远的地方有一位酋长，他想把三个女儿嫁出去。假定三个女儿为A、B、C，三位求婚者为X、Y、Z。每位求婚者对A、B、C愿出的财礼数视其对她们的喜欢程度而定,（见下表）：XYZA3526B271028C147问酋长应如何嫁女，才能获得最多的财礼（从总体上讲，他的女婿最喜欢他的女儿）。例2显然是指派问题的实例，但它也可以看成是两分图赋权匹配问题的实例。用三个点表示酋长的三个女儿，将它们放在一边。再用三个点表示求婚者，将它们放在另一边。在有可能结婚的两人之间画一条边，并在边上写上求婚者对这种结婚愿付出的财礼数，得到右图。右图是一个特殊的图，它的顶点可以分成两个子集，只有分属不同子集的点才可能有边相连（但也可以无边），这样的图称为两分图。定义3.(匹配)图G的一个匹配是指边集E的一个子集M，M中的任意两条边均不具有公共的顶点。容易看出，酋长要解的问题是在上面的两分图中找出一个具有最大权和的匹配，读者不难由此得到一般两分图最大权匹配问题的数学模型（注：两分图最大权匹配可用匈牙利算法或最小费用最大流算法求解）。德国著名的艺术家AlbrechtDürer(1471-1521)于1514年曾铸造了一枚名为“MelencotiaI”的铜币。令人奇怪的是在这枚铜币的画面上充满了数学符号、数字及几何图形。这里，我们仅研究铜币右上角的数字问题§2.Dürer魔方（或幻方）问题所谓的魔方是指由1~n2这n2个正整数按一定规则排列成的一个n行n列的正方形。n称为此魔方的阶。Dürer魔方：4阶，每一行之和为34，每一列之和为34，对角线（或反对角线）之和是34，每个小方块中的数字之和是34，四个角上的数字加起来也是34什么是Dürer魔方铜币铸造时间：1514年构造魔方是一个古老的数学游戏，起初它还和神灵联系在一起，带有深厚的迷信色彩。传说三千二百多年前（公元前2200年），因治水出名皇帝大禹就构造了三阶魔方（被人们称“洛书”），至今还有人把它当作符咒用于某些迷信活动，大约在十五世纪时，魔方传到了西方，著名的科尼利厄斯·阿格里帕（1486-1535）先后构造出了3~9阶的魔方。如何构造魔方奇数（不妨n=5）阶的情况Step1:在第一行中间写1Step2:每次向右上方移一格依次填按由小到大排列的下一个数，向上移出界时填下一列最后一行的小方格；向右移出界时填第一列上一行的小方格。若下面想填的格已填过数或已达到魔方的右上角时，改填刚才填的格子正下方的小方格，继续Step2直到填完12345678910111213141516171819202122232425偶数阶的情况偶数阶的魔方可以利用奇数阶魔方拼接而成，拉尔夫·斯特雷奇给出了一种拼接的方法，这里不作详细介绍五阶没人知道有多少个！！！三阶1个反射和中心旋转生成8个四阶880个反射和中心旋转生成7040个魔方数量随阶数n增长的速度实在是太惊人了！同阶魔方的个数允许构成魔方的数取任意实数允许取实数n阶魔方A、B，任意实数α、βαA+βB是n阶魔方具有指定性质的魔方全体构成一个线性空间问题已发生了实质性变化注：刻画一个线性空间只需指出它的维数并求出此线性空间的一组基底松驰问题的讨论1在第一行中共有4种取法，为保持上述性质的成立，第二行中的1还有两种取法。当第二行的1也取定后，第三行与第四行的1就完全定位了，故一共可作出8个不同的最简方阵，称之为基本魔方并记之为Q1，…，Q8仍以4阶方阵为例。令R为行和，C为列和，D为对角线和，S为小方块和定义0-方：R=C=D=S=0定义1-方：R=C=D=S=4R=C=D=S=1的方阵构成的线性空间具有什么样的性质？类似于构造n维欧氏空间的标准基，利用0和1我们来构造一些R=C=D=S=1的最简单的方阵。00101000010000011Q01000010100000012Q00100100000110003Q01000001001010004Q10000010000101005Q10000001010000106Q00011000001001007Q00010100100000108Q显然，Dürer空间（简称D空间）中任何一个元素都可以用Q1，Q2，…，Q8来线性表示，但它们能否构成D空间的一组基呢？是否线性无关？821,,,QQQ容易看出：076328541QQQQQQQQQ1，…，Q8这8个基本方是线性相关的，即至少存在一个Qj，可以通过其它7个基本方的线性组合得到。这8个基本方的地位是等同的，故可不妨设j=8。下面验证Q1，Q2，…，Q7是否线性相关。071iiiQr令：，即6542317713526426174534375621rrrrrrrrrrrrrrrrrrrrrrrrrrrr0000000000000000=等号两边对应元素相比较，得r1=r2=…=r7=0，所以是线性无关721,,,QQQ721,,,QQQ是D空间的最小生成集。令D即解方程组：772211QdQdQd114155127698111051323166542317713526426174534375621dddddddddddddddddddddddddddd=解得D=76543215336788QQQQQQQ研究AlbrechtDürer铸造的铜币§3信息的度量与应用怎么度量信息首先分析一下问题的认识过程1.对一问题毫无了解，对它的认识是不确定的2.通过各种途径获得信息，逐渐消除不确定性3.对这一问题非常的了解，不确定性很小黑箱不确定度A灰箱不确定度B白箱不确定度C信息I信息II对于系统，可以利用守恒关系有A+I=B，得I=B-A。可否用消除不确定性的多少来度量信息！几个例子：例3当你要到大会堂去找某一个人时，甲告诉你两条消息：（1）此人不坐在前十排，（2）他也不坐在后十排；乙只告诉你一条消息：此人坐在第十五排。问谁提供的信息量大？乙虽然只提供了一条消息，但这一条消息对此人在什么位置上这一不确定性消除得更多，所以后者包含的信息量应比前者提供的两条消息所包含的总信息量更大例4假如在盛夏季节气象台突然预报“明天无雪”的消息。在明天是否下雪的问题上，根本不存在不确定性，所以这条消息包含的信息量为零。是否存在信息量的度量公式基于前面的观点，美国贝尔实验室的学者香农（Shannon）应用概率论知识和逻辑方法推导出了信息量的计算公式InhiswordsIjustwonderedhowthingswereputtogether.ClaudeElwoodShannon(April30,1916-February24,2001)hasbeencalledthefatherofinformationtheory.Shannon提出的四条基本性质（不妨称它们为公理）公理1信息量是该事件发生概率的连续函数公理2如果事件A发生必有事件B发生，则得知事件A发生的信息量大于或等于得知事件B发生的信息量。公理3如果事件A和事件B的发生是相互独立的，则获知A、B事件将同时发生的信息量应为单独获知两事件发生的信息量之和。公理4任何信息的信息量均是有限的。将某事件发生的信息记为M，该事件发生的概率记为p，记M的信息量为I（M）。上述公理怎样推出信息量的计算公式呢定理1满足公理1—公理4的信息量计算公式为I(M)=－Clogap，其中C是任意正常数，对数之底a可取任意为不为1的正实数。各种信息量单位若取a=2,C=1，此时信息量单位称为比特若取a=10,C=1，此时信息量单位称为迪吉特若取a=e,C=1，此时信息量单位称为奈特平均信息量（熵）问题设某一实验可能有N种结果，它们出现的概率分别为p1,…,pN,则事先告诉你将出现第i种结果的信息，其信息量为－log2pi，而该实验的不确定性则可用这组信息的平均信息量（或熵）来表示NiiippH12log例5投掷一枚骼子的结果有六种，即出现1—6点、出现每种情况的概率均为1/6，故熵H=log26≈2.585（比特）。投掷一枚硬币的结果为正、反面两种，出现的概率均为1/2，故熵H=log22=1（比特）。向石块上猛摔一只鸡蛋，其结果必然是将鸡蛋摔破，出现的概率为1，故熵H=log21=0从例子可以看出，熵实质上反映的是问题的“模糊度”，熵为零时问题是完全清楚的，熵越大则问题的模糊程度也越大离散型概率分布的随机试验，熵的定义为：NiiippH12log连续型概率分布的随机试验，熵的定义为:dxxpxppH)(log)()(2熵具有哪些有趣的性质定理2若实验仅有有限结果S1,…,Sn，其发生的概率分别为P1,…,Pn，则当时，此实验具有最大熵。nppn11此定理既可化为条件极值问题证明之，也可以利用凸函数性质来证明，请大家自己去完成定理3若实验是连续型随机试验，其概率分布P(x)在[a,b]区间以外均为零，则当P(x)平均分布时具有最大熵。定理4对于一般连续型随机试验，在方差一定的前提下，正态分布具有最大的熵。定理5最大熵原理，即受到相互独立且均匀而小的随机因素影响的系统，其状态的概率分布将使系统的熵最大。上述结果并非某种巧合。根据概率论里的中心极限定理，若试验结果受到大量相互独立的随机因素的影响，且每一因素的影响均不突出时，试验结果服从正态分布。最大熵原理则说明