1、100-100-1 1线性代数故事会线性代数故事会 数学建模融入数学建模融入课程的探索课程的探索广东工业大学广东工业大学郝志峰郝志峰20102010年年4 4月月2424日日100-100-2 2国家国家“十一五十一五”规划教材规划教材高等教育百门精品教材高等教育百门精品教材n线性代数、学习指导与典型例题线性代数、学习指导与典型例题100-100-3 3n线性代数(英文版)线性代数(英文版)100-100-4 4n线性代数(教育部新世纪网络课程线性代数(教育部新世纪网络课程建设工程)建设工程)100-100-5 5一、基础解系一、基础解系二、线性方程组二、线性方程组三、线性变换三、线性变换四、
2、矩阵乘法的迷雾四、矩阵乘法的迷雾五、常用的五、常用的“模型模型”100-100-6 6 在城市中,不时听到在城市中,不时听到人们抱怨塞车,这也成为人们抱怨塞车,这也成为不少城市的不少城市的“一景一景”。下。下面的例子一方面给出了交面的例子一方面给出了交通堵塞的部分数学解释,通堵塞的部分数学解释,另一方面也给基础解系一另一方面也给基础解系一个生动的刻划。个生动的刻划。一、基础解系一、基础解系繁忙的交通繁忙的交通右图是右图是20102010年年3 3月月2 2日,元宵节日,元宵节后上班第一天,后上班第一天,广州广州BRTBRT(Bus(Bus Rapid TransitRapid Transit,
3、中文名,中文名“不不让通让通”)工程实施后的照片。工程实施后的照片。100-100-7 7一、基础解系一、基础解系繁忙的交通繁忙的交通n例:设一个例:设一个“井井”字形环路,均为单字形环路,均为单向行驶,在八个出入口有一个记录口向行驶,在八个出入口有一个记录口(或收费站),可记录单位时间进出(或收费站),可记录单位时间进出5004005506505006004503501x2x3x4x 该路段的车辆数目,该路段的车辆数目,已知八个出入口在已知八个出入口在某一个时间段的数某一个时间段的数目如右图。目如右图。100-100-8 8n问问 路段上的车辆数目?路段上的车辆数目?4321,xxxx解解:
4、根据根据“入入 出出”的准测,四个的准测,四个“十字十字”路路口节点的方程为口节点的方程为:21324314400550)2(350500)3(600450)4(650500)1(xxxxxxxx(1)(4)(3)(2)节点一、基础解系一、基础解系繁忙的交通繁忙的交通100-100-9 9上述线性方程组的解为上述线性方程组的解为12345 012 0 01k3 5 012 0 01xxxx一、基础解系一、基础解系繁忙的交通繁忙的交通100-100-1010n问题问题:(1):(1)基础解系基础解系 在该问题中代表了什在该问题中代表了什么?么?n请您利用该结果对交通管理部门提出若干有用的请您利用
5、该结果对交通管理部门提出若干有用的建议建议.1111一、基础解系一、基础解系繁忙的交通繁忙的交通100-100-1111n思考题:图中是某一地区的公路交通网络图,所有的道思考题:图中是某一地区的公路交通网络图,所有的道路都是单行道,且道上不能停车,通行方向用箭头表示,路都是单行道,且道上不能停车,通行方向用箭头表示,标示的数字为高峰期每小时进出网络的车辆数。标示的数字为高峰期每小时进出网络的车辆数。(修订版,(修订版,20082008,p.13p.13,例,例1010)200200300300200200100100200200300300300A AB BC CD DE E 试从交通流量试从
6、交通流量平衡条件建立平衡条件建立起线性代数方起线性代数方程组,并对解程组,并对解作出符合实际作出符合实际意义的解释。意义的解释。一、基础解系一、基础解系繁忙的交通繁忙的交通100-100-1212一、基础解系一、基础解系二、线性方程组二、线性方程组三、线性变换三、线性变换四、矩阵乘法的迷雾四、矩阵乘法的迷雾五、常用的五、常用的“模型模型”100-100-1313n线性相关(修订版,线性相关(修订版,20082008,p.131p.131末):末):123201022,2221O+HH O2二、线性方程组二、线性方程组(1)化学方程式化学方程式已知化学反应方程式:已知化学反应方程式:该方程式共有
7、两种原该方程式共有两种原子,故可用子,故可用2 2维向量表示:维向量表示:100-100-1414n线性相关:线性相关:1231+=2二、线性方程组二、线性方程组(1)化学方程式化学方程式即:即:与方程式对应,有向量关系式:与方程式对应,有向量关系式:1231+-=20n注意:向量组注意:向量组线性相关线性相关的意义的意义 这些组分间可能发生化学反应。这些组分间可能发生化学反应。但:真实发生还需要所谓的但:真实发生还需要所谓的“反应条件反应条件”100-100-1515n确定确定 ,使两边原子数相等称,使两边原子数相等称为配平,方程为为配平,方程为138223242()()()()x C Hx
8、 Ox COxH O1234301080020221xxxx 1234301008002002210 xxxx Ax0-二、线性方程组二、线性方程组(1)化学方程式化学方程式 配平配平1234,x x x xn写成矩阵方程写成矩阵方程100-100-1616n已知一个化学反应系统内有七种组分:已知一个化学反应系统内有七种组分:并且已知这些组分中部分物质的量并且已知这些组分中部分物质的量(kmolkmol),注意到这些分子总共涉及三种原子,根据),注意到这些分子总共涉及三种原子,根据物质不灭定律,系统原子量保持恒定,于是有原子矩物质不灭定律,系统原子量保持恒定,于是有原子矩阵(修订版,阵(修订版
9、,20092009,p.22p.22、例、例3 3)4222263 7CHHCOCOH OCC H1011012CB4200206H0012100O422CHH OH、二、线性方程组二、线性方程组(1)化学方程式化学方程式 (非)齐次方程组(非)齐次方程组226COCOCC H、100-100-1717n根据物质不灭定律,系统原子量保持恒定,当考虑经过一根据物质不灭定律,系统原子量保持恒定,当考虑经过一定时间的变化,如何确定系统内的各组分含量时(修订版,定时间的变化,如何确定系统内的各组分含量时(修订版,20082008,p.114p.114、例、例7 7),有),有n上述两式一减,注意,非齐
10、次转化为齐次。上述两式一减,注意,非齐次转化为齐次。422226CHHCOCCOH3 7OH OCC HBnnnbnbbnnn 422226CHHCOCCOH3 7OH OCC HBnnnbnbbnnn 二、线性方程组二、线性方程组(1)化学方程式化学方程式 (非)齐次方程组(非)齐次方程组100-100-1818n在本例中,在本例中,n的秩为的秩为 ,则基础解系有,则基础解系有 个(需要由化学方个(需要由化学方法预先测定)齐次方程的解。法预先测定)齐次方程的解。422226CHHCOCO3 7H OCC H0B00nnnnnnn 7rr二、线性方程组二、线性方程组(1)化学方程式化学方程式
11、(非)齐次方程组(非)齐次方程组100-100-1919n若齐次方程组若齐次方程组 ,故通解中有四个任意常数,故通解中有四个任意常数,若测出若测出 则可算得:则可算得:3 7(B)3r二、线性方程组二、线性方程组(1)化学方程式化学方程式 (非)齐次方程组(非)齐次方程组22426COH OCH7C H0.2kmol1.2kmol1.05kmol10kmolnnnn2CHCO0.05kmol3.3kmol0.8kmolnnnn注意注意 (通解、特解),则可由得到的(通解、特解),则可由得到的转化量确定系统内各组分的含量转化量确定系统内各组分的含量nnn 100-100-2020n在本例中,在本
12、例中,n的秩为的秩为 ,则基础解系有,则基础解系有 个(需要由化学方个(需要由化学方法预先测定)齐次方程的解。法预先测定)齐次方程的解。422226CHHCOCO3 7H OCC H0B00nnnnnnn 7rr二、线性方程组二、线性方程组(1)化学方程式化学方程式 (非)齐次方程组(非)齐次方程组100-100-2121二、线性方程组二、线性方程组(2)剑桥食谱剑桥食谱 麦当劳是麦当劳是垃圾食品垃圾食品吗?吗?100-100-2222 世卫组织对垃圾食品的定义是:仅仅提世卫组织对垃圾食品的定义是:仅仅提供一些热量,别无其它营养素的食物,或是提供一些热量,别无其它营养素的食物,或是提供超过人体
13、需要,变成多余成分的食品。供超过人体需要,变成多余成分的食品。二、线性方程组二、线性方程组(2)剑桥食谱剑桥食谱 你进了麦当劳,同样价格的汉堡,你你进了麦当劳,同样价格的汉堡,你选选双层吉士汉堡包双层吉士汉堡包,还是,还是麦辣鸡腿汉堡麦辣鸡腿汉堡?双层吉士汉堡包里吉士能提供你半天的热量,生的双层吉士汉堡包里吉士能提供你半天的热量,生的生菜保留了原有的维生素生菜保留了原有的维生素C,烘焙的面包既富含维生素,烘焙的面包既富含维生素B,又是粗粮能帮助消化,你怎么不选?又是粗粮能帮助消化,你怎么不选?可你为什么就一定会选麦辣鸡腿汉堡呐?油炸的东可你为什么就一定会选麦辣鸡腿汉堡呐?油炸的东西产生亚硝酸盐
14、类物质,不易消化,这个你也知道的吧?西产生亚硝酸盐类物质,不易消化,这个你也知道的吧?100-100-2323 双层吉士汉堡包满足双层吉士汉堡包满足剑桥食谱剑桥食谱?二、线性方程组二、线性方程组(2)剑桥食谱剑桥食谱100-100-2424 上世纪上世纪8080年代很流行,剑桥大学年代很流行,剑桥大学HowardHoward博士博士(International Journal of Obesety,1978,2,321-International Journal of Obesety,1978,2,321-332332),修订版,),修订版,20082008,p.47p.47,例,例1616:
15、为使食品具有希望数量和比例的营养,在食谱中为使食品具有希望数量和比例的营养,在食谱中加入了多种食物,每种食物能提供需要的成分,但关加入了多种食物,每种食物能提供需要的成分,但关键是键是正确的比例正确的比例。例如:脱脂牛奶是蛋白质的主要来。例如:脱脂牛奶是蛋白质的主要来源,但含了过多的钙,于是可以考虑用大豆粉来提供源,但含了过多的钙,于是可以考虑用大豆粉来提供蛋白,它只含有少量的钙,但又含了过多的脂肪,于蛋白,它只含有少量的钙,但又含了过多的脂肪,于是又加上乳清,因它含的脂肪比较少,但乳清所含的是又加上乳清,因它含的脂肪比较少,但乳清所含的碳水化合物又多了,碳水化合物又多了,。该如何该如何取舍取
16、舍?二、线性方程组二、线性方程组(2)剑桥食谱剑桥食谱100-100-2525 一个食谱的简单例子:三种食物及其每包可食物所含的一个食谱的简单例子:三种食物及其每包可食物所含的营养素的数量如下:营养素的数量如下:脱脂牛奶脱脂牛奶食物食物(百克百克)营养素营养素(克克)大豆粉大豆粉乳清乳清 剑桥食谱每天剑桥食谱每天供应量(克)供应量(克)蛋白质蛋白质碳水化合物碳水化合物脂肪脂肪363651511313333345453 3 52 52 39 39 74 74 0 0 7 7 11 11 二、线性方程组二、线性方程组(2)剑桥食谱剑桥食谱100-100-2626设脱脂牛奶的用量为设脱脂牛奶的用量为
17、 个单位(个单位(100g100g),大豆面粉的),大豆面粉的用量为用量为 个单位,乳清的用量为个单位,乳清的用量为 个单位,表中的个单位,表中的三个营养成分列向量为:三个营养成分列向量为:使这个合成的营养与剑桥配方的要求相等,得到使这个合成的营养与剑桥配方的要求相等,得到 1 122331233651135234740711x ax ax axxx123365113335234744507113xxxAx=b二、线性方程组二、线性方程组(2)剑桥食谱剑桥食谱1x2x3x100-100-2727注意:选取非负解,可以多考虑几注意:选取非负解,可以多考虑几个方程组,从而出现无限多解。个方程组,从
18、而出现无限多解。剑桥食谱:剑桥食谱:给出了给出了3333种食物提供所种食物提供所需的需的3131种营养素。种营养素。二、线性方程组二、线性方程组(2)剑桥食谱剑桥食谱100-100-2828(1020)/4(2040)/4(1030)/4(4030)/4abcbadcaddbcxxxxxxxxxxxx二、线性方程组二、线性方程组(3)平板稳态温度的计算平板稳态温度的计算 俄罗斯著名代数学家柯斯特利金的优秀教俄罗斯著名代数学家柯斯特利金的优秀教材材代数学引论代数学引论第二卷:线性代数第二卷:线性代数已知平板的四周温度(可测,求平板上任一点的已知平板的四周温度(可测,求平板上任一点的温度),温度)
19、,与气象预测、地形测量对比与气象预测、地形测量对比100-100-292910.250.2507.50.25100.25150.25010.251000.250.25117.5abcdxxxx整理为整理为二、线性方程组二、线性方程组(3)平板稳态温度的计算平板稳态温度的计算 注意:注意:推广到网格,大规模稀疏矩阵的推广到网格,大规模稀疏矩阵的100-100-3030一、基础解系一、基础解系二、线性方程组二、线性方程组三、线性变换三、线性变换四、矩阵乘法的迷雾四、矩阵乘法的迷雾五、常用的五、常用的“模型模型”100-100-3131n书号的编制(书号的编制(20072007年年1 1月月1 1日
20、后):日后):以新的书:修订版,以新的书:修订版,20082008为例,有为例,有ISBN 978-7040249002国际标准书号国际标准书号中国中国出版社出版社社内码社内码校验位校验位若分别赋予权重若分别赋予权重,即即.9 7 870 40 2 4 9 0 02并求和:并求和:9+21+8+21+12+6+4+27+29+21+8+21+12+6+4+27+21101101 11 13 31 13 31 13 31 13 31 13 33 31 1图书图书注意:注意:(mod 10)(mod 10)1100三、线性变换三、线性变换(1)书号的编制书号的编制100-100-3232n书号的编
21、制(书号的编制(20072007年年1 1月月1 1日前):日前):ISBN 7040118823国际标准书号国际标准书号中文中文出版社出版社社内码社内码校验位校验位70 40 1 1 8 8 2310109 98 87 76 65 54 43 32 21 1三、线性变换三、线性变换(1)书号的编制书号的编制100-100-3333n注意:注意:(mod 11)(mod 11)事实上,这对任何一本正式出版的书都是对的,事实上,这对任何一本正式出版的书都是对的,n问题:问题:(1)(1)这两种编码方式的线性变换观点这两种编码方式的线性变换观点?校验位校验位.(2)(2)请您发现一本不编码体系中最
22、末一位是请您发现一本不编码体系中最末一位是 “X”X”的书。的书。(3)(3)国际标准期刊号国际标准期刊号 华南理工大学学报(自然科学版)华南理工大学学报(自然科学版)ISSN 1000 ISSN 1000565X565X (4)(4)这个方法如何推广到一般的情形这个方法如何推广到一般的情形?代数方法代数方法线性变换。线性变换。1760三、线性变换三、线性变换(1)书号的编制书号的编制100-100-3434n传说中,有一位古代将军命令他的传令兵发出一传说中,有一位古代将军命令他的传令兵发出一个个“进攻进攻”的信息,他要求该命令必须准确无误的信息,他要求该命令必须准确无误地发出,否则将处死传令
23、兵。这可急坏了这位传地发出,否则将处死传令兵。这可急坏了这位传令兵,要发一条信息并不难,难的是如何保证不令兵,要发一条信息并不难,难的是如何保证不出错,真是急得一身汗。出错,真是急得一身汗。正在此时,传令兵突然正在此时,传令兵突然急中生智急中生智,他毫不犹,他毫不犹豫地站在传令台上,向前挥舞豫地站在传令台上,向前挥舞“进攻进攻”的命令一的命令一百次,然后下来。结果当然是信息发了出去,而百次,然后下来。结果当然是信息发了出去,而且接受方也知道了且接受方也知道了“进攻进攻”。因为接受方虽不能。因为接受方虽不能保证一百次看到的都是保证一百次看到的都是“进攻进攻”,但可以几乎以,但可以几乎以概率为概率
24、为1 1的把握确定是的把握确定是“进攻进攻”。因为一百次样。因为一百次样本还是较大的,接受方理解为本还是较大的,接受方理解为“进攻进攻”的可能性的可能性很大。很大。三、线性变换三、线性变换(2)密码密码古代将军的命令古代将军的命令100-100-3535 现在用向量代数的语言来诠释传令兵的思想,现在用向量代数的语言来诠释传令兵的思想,假设发出的信息为假设发出的信息为a a,则传令兵发出的信息,则传令兵发出的信息是:是:当然我们有理由批评传令兵没有注意保密,当然我们有理由批评传令兵没有注意保密,因为这个信息有可能被间谍也窃取了。但考因为这个信息有可能被间谍也窃取了。但考虑到传令兵所处的环境,当然
25、也就不会追究虑到传令兵所处的环境,当然也就不会追究了。但现在的研究人员却需要考虑这一点,了。但现在的研究人员却需要考虑这一点,比如书号的模型就是一例。比如书号的模型就是一例。1001a(1,1,1,1)个三、线性变换三、线性变换(2)密码密码古代将军的命令古代将军的命令100-100-3636n低维低维高维高维:现代加密现代加密,解密的基本方法解密的基本方法.n人造卫星的信号人造卫星的信号.明文明文:发发:即即 (注注:1:1低维低维高维高维,2 2 线性变换线性变换)收收:若若:12345(,).0,1ia a a a aaX512345661(,).(mod 2)iia aaaaaaaY5
26、5 65 610000110100011001001100010110000111Y=XXE123456(,)b b b b b bZ61)2(mod0iib三、线性变换三、线性变换(2)密码密码现代通信现代通信100-100-3737则存在奇数个错则存在奇数个错,且一个错的可能性很大且一个错的可能性很大,这是因为这是因为若一个错的概率为若一个错的概率为 ,则,则 出三个错的出错概率为出三个错的出错概率为 出五个错的出错概率为出五个错的出错概率为若:若:则不能完全判断,若出错,至少有偶数个错,其概率至则不能完全判断,若出错,至少有偶数个错,其概率至少为少为故在民用电报中,上述方法是一个简便的方
27、法。故在民用电报中,上述方法是一个简便的方法。p3p5p2p)2(mod061iib三、线性变换三、线性变换(2)密码密码现代通信现代通信100-100-3838字母A B C D E F G H I J K L M 表值 1 2 3 4 5 6 7 8 9 10 11 12 13字母 N O P Q R S T U V W X Y Z表值14 15 16 17 18 19 20 21 22 23 24 25 26三、线性变换三、线性变换(3)密码密码 Hill密码的加密与解密密码的加密与解密n修订版,修订版,2008,p.57例例19,利用可逆矩阵法,利用可逆矩阵法n修订版,修订版,2008
28、,p.218例例4,利用线性变换,利用线性变换1123011112221012111AA,例:例:发:发:ACTION,编码为,编码为1、3、20、9、15、14100-100-3939n则乘以则乘以 可编成可编成“密码密码”:A三、线性变换三、线性变换(3)密码密码 Hill密码的加密与解密密码的加密与解密123167123981112344112155201220430121443 ,n收到信息:收到信息:6767、4444、4343、8181、5252、4343后,可用后,可用 恢复明码。恢复明码。1A100-100-4040n如何破译:关键是求得加密矩阵的逆如何破译:关键是求得加密矩阵
29、的逆解密矩阵解密矩阵 例如:只要分析出两个(例如:只要分析出两个(n n个)明文向量(线性个)明文向量(线性无关)与相应的密文向量。无关)与相应的密文向量。11332244babababa AA,三、线性变换三、线性变换(3)密码密码 Hill密码的加密与解密密码的加密与解密n如果:如果:13132424bbaabbaaA113132424bbaabbaaA100-100-4141一、基础解系一、基础解系二、线性方程组二、线性方程组三、线性变换三、线性变换四、矩阵乘法的迷雾四、矩阵乘法的迷雾五、常用的五、常用的“模型模型”100-100-4242n姜启源老师的姜启源老师的数学模型数学模型 例:
30、已知比赛无平局,只例:已知比赛无平局,只有胜负有胜负(如如:排球、乒乓球、排球、乒乓球、羽毛球、网球羽毛球、网球 等等),共有六,共有六支队伍,两两之间均比赛过,支队伍,两两之间均比赛过,结果如右图结果如右图:问:如何排定名次问:如何排定名次?123456思考思考1 1:“获胜获胜”是关键。于是,寻是关键。于是,寻找一条从起点不断获胜的路径;如:找一条从起点不断获胜的路径;如:1 46 3 2 5 1 46 3 2 5 4 56 3 12 4 56 3 12明显有不合理且不可行的地方。第一,解明显不唯一。第明显有不合理且不可行的地方。第一,解明显不唯一。第二,强队一失手,真成千古之恨。(比如巴
31、西负阿根廷,二,强队一失手,真成千古之恨。(比如巴西负阿根廷,阿根廷再负阿根廷再负,此种传递会得出极荒谬的结论。但注重,此种传递会得出极荒谬的结论。但注重“获胜获胜”是体育竞赛精神之所在,也是建模的基本依据。是体育竞赛精神之所在,也是建模的基本依据。四、矩阵乘法的迷雾四、矩阵乘法的迷雾(1)循环比赛循环比赛100-100-4343n思考思考 2:2:国际足联国际足联 积分制积分制 1 1队队:4:4胜胜1 1负负 8 8分分 2 2队队:3:3胜胜2 2负负 6 6分分 3 3队队:3:3胜胜2 2负负 6 6分分 4 4队队:2:2胜胜3 3负负 4 4分分 5 5队队:2:2胜胜3 3负负
32、 4 4分分 6 6队队:1:1胜胜4 4负负 2 2分分这时这时1 1,6 6两队名次立即分出。但两队名次立即分出。但2 2、3 3两队,两队,4 4、5 5 两队呢?以体育界常用的做法,两队呢?以体育界常用的做法,3 3胜胜2 2,故,故3 3在在2 2之前。之前。4 4胜胜5 5,故,故4 4在在5 5之前。于是名次为:之前。于是名次为:1 1,3 3,2 2,4 4,5 5,6 6。但问题或困惑随之而来,就但问题或困惑随之而来,就4 4、5 5而言,而言,5 5胜的是胜的是3 3和和6 6,而,而4 4胜的是胜的是5 5和和6 6。看一看对手的实力,。看一看对手的实力,我们又有理由说我
33、们又有理由说5 5会强一点,因为会强一点,因为534534。四、矩阵乘法的迷雾四、矩阵乘法的迷雾(1)循环比赛循环比赛100-100-4444n20102010年年CBACBA总决赛,目前广东宏远总决赛,目前广东宏远2:02:0新疆广汇新疆广汇 可可4 4月月1818日就在第二场日就在第二场比赛结束的一刹那,新疆外比赛结束的一刹那,新疆外援查尔斯与广东队员杜锋发援查尔斯与广东队员杜锋发生冲突,查尔斯一记猛拳将生冲突,查尔斯一记猛拳将广东队员杜锋打倒在地,场广东队员杜锋打倒在地,场面一度失去控制。面一度失去控制。为何比赛如此为何比赛如此激烈激烈?四、矩阵乘法的迷雾四、矩阵乘法的迷雾(1)循环比赛
34、循环比赛100-100-4545n这说明,排名的学问很深这说明,排名的学问很深 2009 2009年赛季,广东队正是在总决赛中以总年赛季,广东队正是在总决赛中以总比分比分4 4:1 1击败新疆队,夺得了总冠军。击败新疆队,夺得了总冠军。然而,时隔一年,双方不可同日而语,然而,时隔一年,双方不可同日而语,20102010年常规赛中,广东队(年常规赛中,广东队(3030胜胜2 2负),就曾在负),就曾在主客场主客场两负两负新疆队(新疆队(2727胜胜5 5负)。负)。预测:预测:20102010年赛季总冠军?年赛季总冠军?让我们让我们拭目以待拭目以待四、矩阵乘法的迷雾四、矩阵乘法的迷雾(1)循环比
35、赛循环比赛注:注:CBACBA十大冲突之首十大冲突之首的处罚结果:的处罚结果:4 4月月2020日,中国篮协公布了对日,中国篮协公布了对“CBACBA总决赛第二场中球员之间发生冲突总决赛第二场中球员之间发生冲突”事件的处罚结果。最终事件的处罚结果。最终广东队的杜锋和新疆队的外援查尔斯同时被通报批评,两家俱乐部广东队的杜锋和新疆队的外援查尔斯同时被通报批评,两家俱乐部各罚款各罚款5 5万,广东主场东莞赛区由于球迷不冷静被加罚万,广东主场东莞赛区由于球迷不冷静被加罚5 5万元。万元。100-100-4646n综合思路综合思路1 1、2 2,我们有以下的分析:,我们有以下的分析:取胜的价值有所不同。
36、由于积分制只关取胜的价值有所不同。由于积分制只关心取胜,不关心失败,所以取胜强队的价值心取胜,不关心失败,所以取胜强队的价值(即分数即分数)应高一些。依照此思想,在区分应高一些。依照此思想,在区分2 2、3 3和和4 4、5 5时,要给出更精细的分数。时,要给出更精细的分数。以以2 2、3 3为例为例,它们的精细分数为:它们的精细分数为:2 2 胜胜4 4、5 5、6 6,得,得 4+4+24+4+21010分分 3 3 胜胜1 1、2 2、4 4,得,得 8+6+48+6+41818分分四、矩阵乘法的迷雾四、矩阵乘法的迷雾(1)循环比赛循环比赛100-100-4747 以以4 4、5 5为例
37、为例,它们的精细分数为它们的精细分数为:4 4 胜胜5 5、6 6,得,得 4+24+26 6分分 5 5 胜胜3 3、6 6,得,得 6+26+28 8分分 需要说明的是这只是精细分数,不是说需要说明的是这只是精细分数,不是说由于由于108108,则,则2 2在在1 1之前。这只是为了区分同之前。这只是为了区分同一名次的。一名次的。从解决问题的角度来看,做到这里似乎从解决问题的角度来看,做到这里似乎目的达到了。但作为数学建模,这只是开始。目的达到了。但作为数学建模,这只是开始。我们只是有了些正确的思路,或解决问题的我们只是有了些正确的思路,或解决问题的技巧,还没有建立模型。现在,我们朝着模技
38、巧,还没有建立模型。现在,我们朝着模型的方向前进着。型的方向前进着。四、矩阵乘法的迷雾四、矩阵乘法的迷雾(1)循环比赛循环比赛100-100-4848n于是于是,我们转换为矩阵的做法试试看:我们转换为矩阵的做法试试看:令令设胜一场得设胜一场得2 2分分,负一场得负一场得0 0分分.记初始向量为记初始向量为(为什么为什么?)?)2222220e000100100100110000001011111000111010654321654321A四、矩阵乘法的迷雾四、矩阵乘法的迷雾(1)循环比赛循环比赛100-100-494910244668eeA21686181016eeA这就是区分这就是区分2 2
39、、3 3和和4 4、5 5的过程的过程这就是国际足协这就是国际足协四、矩阵乘法的迷雾四、矩阵乘法的迷雾(1)循环比赛循环比赛100-100-5050n注意到注意到n这给出了这给出了“矩阵相乘矩阵相乘”的一个解释的一个解释看对手看对手.2220200212322002012220102332200200122111100221101002eAeA 四、矩阵乘法的迷雾四、矩阵乘法的迷雾(1)循环比赛循环比赛100-100-5151n矩阵乘法矩阵乘法 (修订版,(修订版,20082008,p.27p.27)中)中 究竟究竟 是什么?是什么?n观察观察n注意:注意:当且仅当当且仅当 战胜战胜 。n所以
40、所以 表明有三个表明有三个 ,存在着,存在着 战胜战胜 ,战胜战胜 。CAB61ijikkjkcab16111612261336144615561666ca ba ba ba ba ba b0ijaij163cijkkk四、矩阵乘法的迷雾四、矩阵乘法的迷雾(1)循环比赛循环比赛100-100-5252一般的定理一般的定理:Perron PerronFrobeniusFrobenius 定理定理若若A A是非负、不可约矩阵,则是非负、不可约矩阵,则nnA xA xlimn 注意注意:约束条件不可分矩阵(约束条件不可分矩阵(分块矩阵分块矩阵)对应)对应的图是连通图的图是连通图100-100-535
41、3数模竞赛中的类似问题数模竞赛中的类似问题nCUMCM:92B:CUMCM:92B:足球排名足球排名(残缺矩阵残缺矩阵)nMCM:96B:MCM:96B:快速评卷快速评卷.nMCM:98B:ABCMCM:98B:ABC学院学院100-100-5454n思考题:通路矩阵(修订版,思考题:通路矩阵(修订版,20082008,p.23p.23,练习,练习4 4)1dn右图中示明了右图中示明了d d国三个城市,国三个城市,e e国三个城市,国三个城市,f f国两个城国两个城市相互之间的通路,市相互之间的通路,d d国和国和e e国之间的通路情况国之间的通路情况可以用下面的矩阵表示可以用下面的矩阵表示2
42、d3d1e2e3e2f1f123123110101110eeedddn问:问:e e国和国和f f国之间,国之间,d d国和国和f f国之间呢?国之间呢?四、矩阵乘法的迷雾四、矩阵乘法的迷雾(2)通路矩阵通路矩阵100-100-5555四、矩阵乘法的迷雾四、矩阵乘法的迷雾(3)Google(3)Google搜索搜索+PerronPerronFrobeniusFrobenius 定理的应用定理的应用100-100-5656搜索搜索 三明学院三明学院 获得约获得约370,000 370,000 条结条结果(启用了安全搜索功能),以下是果(启用了安全搜索功能),以下是第第1-101-10条。(用时条
43、。(用时0.130.13秒)秒)100-100-5757网络通讯网络通讯一个网络是由若干个一个网络是由若干个节点节点和和连线连线组成组成-计算机计算机-电视机电视机-卫星卫星-电话线电话线-有线电视有线电视-无线网络无线网络网络通讯:不网络通讯:不同的点有不同同的点有不同的线互联(图的线互联(图论思想)。论思想)。100-100-5858 HITS PageRank 100-100-5959 100-100-6060 通过检查整个网络通过检查整个网络链接结构链接结构,确定哪些网页确定哪些网页重要性重要性最高;然后进最高;然后进行超文本匹配分析,以确定哪些网行超文本匹配分析,以确定哪些网页与正在
44、执行的页与正在执行的特定搜索特定搜索相关。在相关。在综合考虑综合考虑整体重要性以及与特定查整体重要性以及与特定查询的相关性之后,询的相关性之后,Google 将最相将最相关最可靠的搜索结果放在首位。关最可靠的搜索结果放在首位。四、矩阵乘法的迷雾四、矩阵乘法的迷雾(3)Google(3)Google搜索搜索100-100-6161Page Rank,Google的搜索引擎的搜索引擎所用的排序系统。所用的排序系统。四、矩阵乘法的迷雾四、矩阵乘法的迷雾(3)Google(3)Google搜索搜索100-100-6262Page RankPage Rank通过对由超过通过对由超过 50,00050,0
45、00万万个变量和个变量和2020亿个词汇组成的方程进亿个词汇组成的方程进行计算,能够对网页的重要性做出行计算,能够对网页的重要性做出客观的评价。客观的评价。注意:注意:PageRankPageRank 并不计算直接链并不计算直接链接的数量,而是将从网页接的数量,而是将从网页 A A 指向指向网页网页 B B 的链接的链接解释解释为由网页为由网页 A A 对对网页网页 B B 所投的一票。这样,所投的一票。这样,PageRankPageRank 会根据网页会根据网页 B B 所收到的所收到的投票数量来评估该页的重要性。投票数量来评估该页的重要性。100-100-6363 n基本原理基本原理“从从
46、许多许多优质优质的网页链接的网页链接过来的网页,必定还是过来的网页,必定还是优质优质网页网页”q超链接超链接AABABA对对B B投一票投一票q若若A A的质量高(如的质量高(如QQQQ),则该投票),则该投票分数高分数高PageRankPageRank(衡量网页质量)(衡量网页质量)100-100-6464PageRankPageRank示意图示意图100-100-6565搜索者是独立的,搜索者是独立的,搜索的内容是独立的搜索的内容是独立的,()1 ()0 ()m ni ji jPaijN iaijN ii存在从网页 指向网页的超链接网页 不存在指向网页的超链接表示从网页向外的链接数目100
47、-100-6666Page Rank,Page Rank,GoogleGoogle的搜索引擎所的搜索引擎所用的排序系统。用的排序系统。例:六个页面的有向图例:六个页面的有向图100-100-6767100-100-6868 n问题:问题:已知已知GoogleGoogle矩阵(网页邻接矩矩阵(网页邻接矩阵),如何求出阵),如何求出PageRankPageRank?n首先,首先,PageRankPageRank可以表示为向量可以表示为向量qR R=R R1 1,R R2 2,R Rn n PageRankPageRank(衡量网页质量)(衡量网页质量)还是:还是:PerronPerronFrobe
48、niusFrobenius 定理定理100-100-6969 是是GoogleGoogle矩阵的主特征向量矩阵的主特征向量qGoogleGoogle矩阵矩阵P Pq记记P=PP=PT T(关注被链接)(关注被链接)qP P(注意每列为和(注意每列为和1 1向量,不为向量,不为1 1呢?)呢?)n令令 x=x=,则,则q求解求解 x x=P=Px x qP P的最大特征值为的最大特征值为1(1(主特征值主特征值)qx x是主特征值是主特征值1 1对应的特征向量对应的特征向量PageRankPageRank是主特征向量是主特征向量100-100-7070100-100-7171100-100-72
49、72n在网球比赛中,观众最兴奋、比赛最精彩之处在网球比赛中,观众最兴奋、比赛最精彩之处莫过于莫过于DeuceDeuce情形。情形。四、矩阵乘法的迷雾四、矩阵乘法的迷雾(4)(4)网球中的网球中的DeuceDeuce问题问题离散的马氏链离散的马氏链n右图是右图是20102010年年3 3月月7 7日,在广东省江日,在广东省江门市举行的门市举行的20102010年戴维斯杯网球赛年戴维斯杯网球赛亚洲亚洲/大洋洲第一组的比赛中,中大洋洲第一组的比赛中,中国队以国队以3 3比比2 2的总比分力克乌兹别克的总比分力克乌兹别克斯坦队,成功晋级下一轮。斯坦队,成功晋级下一轮。n图为:吴迪在比赛中回球。图为:吴
50、迪在比赛中回球。100-100-7373 乒乓球比赛也一样,乒乓球比赛也一样,9 9平、平、1010平、平、1111平、平、1212平、平、1313平、平、,观众的心都被提到,观众的心都被提到了嗓子眼了,呐喊的、跺脚的,没有一个了嗓子眼了,呐喊的、跺脚的,没有一个观众愿意此时离去观众愿意此时离去(心脏病除外心脏病除外)。这时有。这时有一个问题,一个问题,如果比赛一直平下去,那岂如果比赛一直平下去,那岂不是把观众紧张死了,这可能出现吗不是把观众紧张死了,这可能出现吗?当当然你会说,这决不可能。为什么然你会说,这决不可能。为什么?四、矩阵乘法的迷雾四、矩阵乘法的迷雾(4)(4)网球中的网球中的De