数学建模培训讲座 (2).ppt

《数学建模培训讲座 (2).ppt》由会员分享，可在线阅读，更多相关《数学建模培训讲座 (2).ppt（232页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数学建模培训主讲教师：任驰远建模一般步骤及范例建模一般步骤及范例2评阅标准及论文写作评阅标准及论文写作4试题分析及论文导读试题分析及论文导读3 3建模一般思维方法建模一般思维方法3 12评阅标准及论文写作评阅标准及论文写作4试题分析及论文导读试题分析及论文导读3 3建模一般思维方法建模一般思维方法3 1建模一般步骤及范例建模一般步骤及范例群体思维方法群体思维方法 平等地位、相互尊重、充分交流平等地位、相互尊重、充分交流杜绝武断评价杜绝武断评价不要回避责任不要回避责任不要对交流失去信心不要对交流失去信心 发散性思维方法发散性思维方法借助于一系列问题来展开思路借助于一系列问题来展开思路这个问题与什

2、么问题相似？这个问题与什么问题相似？如果将问题分解成两个或几个部分会怎样？如果将问题分解成两个或几个部分会怎样？极限情形（或理想状态）如何？极限情形（或理想状态）如何？综合问题的条件可得到什么结果？综合问题的条件可得到什么结果？要实现问题的目标需要什么条件？要实现问题的目标需要什么条件？借助于下意识的联想（灵感）来展开思路借助于下意识的联想（灵感）来展开思路抓住问题的个别条件或关键词展开联想或猜想抓住问题的个别条件或关键词展开联想或猜想综合所得到的联想和猜想，得到一些结论综合所得到的联想和猜想，得到一些结论进一步思考找出新思路和方法进一步思考找出新思路和方法建模一般步骤及范例建模一般步骤及范例

3、2评阅标准及论文写作评阅标准及论文写作4试题分析及论文导读试题分析及论文导读3 33 1建模一般思维方法建模一般思维方法 数学建模的一般步骤数学建模的一般步骤问题分析问题分析模型假设模型假设建立模型建立模型模型求解模型求解模型分析模型分析模型检验模型检验模型应用模型应用问问题题分分析析了解实际背景了解实际背景明确建模目的明确建模目的搜集有关信息搜集有关信息掌握对象特征掌握对象特征形成一个形成一个比较清晰比较清晰的的问题问题模模型型假假设设针对问题特点和建模目的针对问题特点和建模目的作出合理的、简化的假设作出合理的、简化的假设在合理与简化之间作出折中在合理与简化之间作出折中建建立立模模型型用数学

4、的语言、符号描述问题用数学的语言、符号描述问题发挥想象力发挥想象力使用类比法使用类比法尽量采用简单的数学工具尽量采用简单的数学工具 数学建模的一般步骤数学建模的一般步骤模型模型求解求解各种数学方法、软件和计算机技术各种数学方法、软件和计算机技术.如结果的误差分析、统计分析、如结果的误差分析、统计分析、模型对数据的稳定性分析模型对数据的稳定性分析.模型模型分析分析模型模型检验检验与实际现象、数据比较，与实际现象、数据比较，检验模型的合理性、适用性检验模型的合理性、适用性.模型应用模型应用 数学建模的一般步骤数学建模的一般步骤1、问题分析、问题分析 问题的前期分析问题的前期分析 包括：包括：明确问

5、题、分析条件、分析数据明确问题、分析条件、分析数据 为什么问题前期分析至关重要？为什么问题前期分析至关重要？数学建模问题往往含混不清数学建模问题往往含混不清,可能的原因有可能的原因有:*提出问题的人未能清楚地表述问题提出问题的人未能清楚地表述问题.*不同领域的人交流出现故障不同领域的人交流出现故障.*各领域的应用者提出问题时，未给出恰当各领域的应用者提出问题时，未给出恰当的条件的条件.*未能准确理解问题未能准确理解问题.对问题进行充分的前期分析以前对问题进行充分的前期分析以前,过早着手决过早着手决问题问题,往往会陷入一些意想不到的陷阱往往会陷入一些意想不到的陷阱,或者偏离或者偏离解决问题的方向

6、解决问题的方向.(1)明确问题明确问题例例1 一家大商业印刷公司的经理就关于应该雇一家大商业印刷公司的经理就关于应该雇 多少推销员的问题征询你的意见多少推销员的问题征询你的意见.“究竟需要做什么？究竟需要做什么？”为明确问题为明确问题,可向有关人员询问如下问题：可向有关人员询问如下问题：1.公司的规模有多大？公司的规模有多大？2.该公司的推销员的工作方式？该公司的推销员的工作方式？遇到一个新问题时遇到一个新问题时,首先应问自己首先应问自己着眼点着眼点是对各类推销队伍的工作效果进行分析是对各类推销队伍的工作效果进行分析 原问题原问题“推销员人数问题推销员人数问题”明确为：明确为：（1 1）不同规

7、模的销售队伍会有什么影响；）不同规模的销售队伍会有什么影响；（2 2）怎样从他们的销售工作中获取最大的收益）怎样从他们的销售工作中获取最大的收益.明确了工作的目标明确了工作的目标,即设置好问题的目标态即设置好问题的目标态.(2)条件及数据分析条件及数据分析 设置好问题的目标态，着手工作还需要做设置好问题的目标态，着手工作还需要做以下工作：以下工作：1.1.收集必要的资料和数据。收集必要的资料和数据。2.2.分析现有的数据和条件，使问题进一步分析现有的数据和条件，使问题进一步 明确化。明确化。怎样收集数据和资料？怎样收集数据和资料？可在各类图书馆、网上查阅、向专家询问、可在各类图书馆、网上查阅、

8、向专家询问、通过试验来得到通过试验来得到。收集数据应列入工作计划，并注意：收集数据应列入工作计划，并注意：1.1.向有关人员调查情况应事先设计好问题；向有关人员调查情况应事先设计好问题；2.事先确定所需资料清单、资料来源、事先确定所需资料清单、资料来源、收集方式。收集方式。有条理的收集计划可以为后期的工作有条理的收集计划可以为后期的工作创造良好的条件创造良好的条件 对收集到的或者现有的资料和数据要做对收集到的或者现有的资料和数据要做仔细分析，使问题进一步明确仔细分析，使问题进一步明确。5.哪些条件是可以变动的？等等哪些条件是可以变动的？等等2.数据来源是否可靠？数据来源是否可靠？3.所给条件有

9、什么意义？所给条件有什么意义？4.哪些条件是本质的？哪些条件是本质的？还应该分析还应该分析1.从数据中可得到什么信息？从数据中可得到什么信息？建建模模过过程程中中的的几几个个要要点点模型的整体设计模型的整体设计合理的假设合理的假设建立数学表达式建立数学表达式建立数学结构建立数学结构时刻时刻牢记牢记建模建模目的目的2、建立模型建立模型完整的数学模型应该同时描述出完整的数学模型应该同时描述出有关因素之间的有关因素之间的数量关系数量关系和和结构关系结构关系。应清楚变量、变量之间的数学表达式在整个应清楚变量、变量之间的数学表达式在整个模型中的模型中的地位地位和和作用作用.例例1 考虑一个简化的城镇供水

10、系统考虑一个简化的城镇供水系统,水是由水库水是由水库经由管道流入水箱经由管道流入水箱,再由水箱向各用户供水再由水箱向各用户供水.问题：问题：怎样才能怎样才能有效地保障有效地保障各用户的正常用水各用户的正常用水？(1)(1)模型的整体设计模型的整体设计按下述步骤对模型进行整体设计按下述步骤对模型进行整体设计 1.分析系统的组成部分分析系统的组成部分（研究对象、实体）（研究对象、实体）相关实体有：水库相关实体有：水库,管道管道,水箱和用户水箱和用户.*实体间的实体间的结构关系结构关系可表示如下：可表示如下：水库水库管道管道水箱水箱用户用户*以上各实体都可能是我们的研究对象以上各实体都可能是我们的研

11、究对象.*应分析相对于各个实体的因素对供水的影响应分析相对于各个实体的因素对供水的影响2.分析各实体之间的关系分析各实体之间的关系,找出联系各实体找出联系各实体的变量的变量.实体之间的作用关系图实体之间的作用关系图 各各实实体体之之间间的的关关系系 管道与水箱：管道的水流量管道与水箱：管道的水流量水库与管道：水库的水深水库与管道：水库的水深水箱与用户：出水口的水流量水箱与用户：出水口的水流量 （或有效水深（或有效水深）用户：总用水量用户：总用水量 3.根据各实体的相互关系，根据各实体的相互关系，提炼整理需考虑提炼整理需考虑的变量的变量以及变量之的关系表达式以及变量之的关系表达式.假设假设“水库

12、能保证管道所需的水流量水库能保证管道所需的水流量”，现需考虑现需考虑t 时刻以下变量：时刻以下变量：*总需水量总需水量D(t)；*水箱的有效储水量水箱的有效储水量Q(t)及及 QM；或流出水流量或流出水流量F（t）及）及 FM；*管道能提供的供水量管道能提供的供水量G(t)及及GM.分析各变量的特征：分析各变量的特征：*D(t)不可控，但可以对其进行描述；不可控，但可以对其进行描述；*G(t)是可控变量。是可控变量。4.4.用数学语言描述用数学语言描述要解决的问题要解决的问题 选择适当的函数选择适当的函数G(t)，使得，使得有有 Q(t)=G(t)F(t),F(t)=D(t),0G(t)GM，

13、0Q(t)QM，同时成立同时成立.建模工作的整体设计建模工作的整体设计:1）确定需求函数确定需求函数D（t），是保证有效控制，是保证有效控制的基础；的基础；2）制定恰当的评价指标，以评价方案的优劣；制定恰当的评价指标，以评价方案的优劣；3）求出相对于评价指标最优的水箱供水方案；求出相对于评价指标最优的水箱供水方案；4）分析各种参数对方案的影响；分析各种参数对方案的影响；5）分析随机因素的影响分析随机因素的影响.模型整体设计的作用模型整体设计的作用 1）可将整个建模过程分解为一些可串行可将整个建模过程分解为一些可串行 或并行的子任务。或并行的子任务。2）可把握住工作的重点、要点和难点可把握住工作

14、的重点、要点和难点.做出模型的整体设计后，着手建立模型做出模型的整体设计后，着手建立模型之前，撰写一份工作提纲之前，撰写一份工作提纲.建议建议:(2)做出假设 根据对象的特征和建模的目的对问题进行根据对象的特征和建模的目的对问题进行必要的、合理的简化，用精确的语言做出假必要的、合理的简化，用精确的语言做出假设，是建模的设，是建模的关键步骤关键步骤。合合理理假假设设的的作作用用 简化问题简化问题 明确问题明确问题 限定模型的限定模型的适用范围适用范围 一个实际问一个实际问题不经过简题不经过简化假设化假设,很难很难抽象转化为抽象转化为数学问题。数学问题。例例2 飞行管理问题中有叙述：飞行管理问题中

15、有叙述：“对以下对以下数据数据进行进行计算计算（方向角误差（方向角误差不超过不超过0.01度度）”如何理解？如何理解？通过假设：通过假设：*所给飞行方向角数据的误差不超过所给飞行方向角数据的误差不超过0.01度度.或或 *数据的运算结果误差限控制为数据的运算结果误差限控制为0.01度度.使问题完全明确使问题完全明确.例例3 渔业管理问题中关于渔业管理问题中关于“季节性集中产卵繁季节性集中产卵繁殖殖”,如何理解如何理解“产卵孵化期是一年的产卵孵化期是一年的最后四最后四个月个月”？最优捕鱼策略最优捕鱼策略 飞行管理模型飞行管理模型 有以下几种假设有以下几种假设:*产卵是均匀地分布在整个四个月的期间

16、内，产卵是均匀地分布在整个四个月的期间内，从而孵化也是均匀进行从而孵化也是均匀进行.*产卵时间服从方差很小的正态分布产卵时间服从方差很小的正态分布.*鱼群的个体在后四个月的第一天集中产卵，鱼群的个体在后四个月的第一天集中产卵，在最后一天孵化出来在最后一天孵化出来.哪一条哪一条“最好最好”？第三种与第二种没有本质的差别，第三种与第二种没有本质的差别，处理较容易处理较容易.分析：分析：第一种不符合鱼类的生物学实际；第一种不符合鱼类的生物学实际；第二种比较符合实际，但大大增加了解决第二种比较符合实际，但大大增加了解决问题的难度；问题的难度；假设起到简化问题的作用假设起到简化问题的作用 假设假设“渔场

17、是非开放式的，不与其它水域发生渔场是非开放式的，不与其它水域发生关系，从而构成独立的生态群落关系，从而构成独立的生态群落”将建立的数学模型限定在一定的适用范围将建立的数学模型限定在一定的适用范围.设计假设应遵循的原则设计假设应遵循的原则 *假设应是有依据的，基于对问题内在规律假设应是有依据的，基于对问题内在规律的认识和对数据及现象的分析；的认识和对数据及现象的分析；*善于辨别问题的主次，抓主要因素，尽量善于辨别问题的主次，抓主要因素，尽量使问题简化使问题简化.*避免过于简单、过于详细或不合理避免过于简单、过于详细或不合理.例例4 渔业管理问题中有条件：渔业管理问题中有条件：“平均每条平均每条4

18、 龄鱼的产卵量为龄鱼的产卵量为1.109105个，个，3 龄鱼的产卵量龄鱼的产卵量为这个数的一半，为这个数的一半，2 龄鱼和龄鱼和1 龄鱼不产卵龄鱼不产卵”.分析分析：为了计算鱼群的产卵量，需明确此条件：为了计算鱼群的产卵量，需明确此条件.*“平均每条鱼的产卵量平均每条鱼的产卵量”理解为对所有鱼的理解为对所有鱼的平均，平均，故在计算总产卵量时，不考虑雌雄区别故在计算总产卵量时，不考虑雌雄区别.有两种假设：有两种假设：*雌雄鱼的比例是雌雄鱼的比例是1:1；哪一种较为合理？哪一种较为合理？最优捕鱼策略最优捕鱼策略 可假设：可假设：*每到次年初，头一年的每到次年初，头一年的1、2、3 龄鱼均增龄鱼均

19、增1岁，将岁，将5龄鱼归并为龄鱼归并为4龄鱼龄鱼.合理性解释合理性解释：事实上，资料表明此种鱼的寿：事实上，资料表明此种鱼的寿命一般为命一般为3年，另一方面经过捕捞后年，另一方面经过捕捞后4 龄鱼的数龄鱼的数量很少，可以忽略不计量很少，可以忽略不计.对于假设：对于假设：*有时需要对假设以及假设的推论进行检验；有时需要对假设以及假设的推论进行检验；问题问题：当年的当年的4 龄鱼，第二年如何处理？龄鱼，第二年如何处理？*应意识到隐含的假设应意识到隐含的假设.3、求解模型、求解模型求数学模型的解重要而困难求数学模型的解重要而困难求解纯数学问题求解纯数学问题求解数学模型求解数学模型 *涉及不同数学分支

20、的知识，同时还需借助涉及不同数学分支的知识，同时还需借助与背景知识与背景知识.*针对现实问题建立的数学模型，往往仅可求针对现实问题建立的数学模型，往往仅可求数值解数值解.*有类问题可采用分析法得到问题的实际解有类问题可采用分析法得到问题的实际解答答(如微分方程定性分析如微分方程定性分析).4、模型解的分析和检验、模型解的分析和检验始于现实世界并终于现实世界始于现实世界并终于现实世界数学建数学建模工作模工作最终要得到现最终要得到现实问题的解答实问题的解答 求出模型的数学解以后，求出模型的数学解以后，必须对解的意义进行分析、检验必须对解的意义进行分析、检验需讨论以下类似问题：需讨论以下类似问题：1

21、.这个解说明了什么问题？这个解说明了什么问题？2.是否达到了建模的目的？是否达到了建模的目的？3.模型的适用范围怎样？模型的适用范围怎样？4.所建模型是否合理？是否合乎实际？是否有所建模型是否合理？是否合乎实际？是否有 原理性错误、常识性错误？原理性错误、常识性错误？o 量纲一致性检验；量纲一致性检验；o假设的合理性检验；假设的合理性检验；o对模型参数的灵敏度分析；对模型参数的灵敏度分析；o模模型型及及模模型型解解的的误误差差分分析析，分分析析误误差差及及误误差差的的来源等；来源等；o参数或变量的临界值；参数或变量的临界值；模型与模型解的分析与检验，通常需要做模型与模型解的分析与检验，通常需要

22、做以下几类工作：以下几类工作：一个例子：一个例子：Google搜索引擎的奥妙搜索引擎的奥妙o引言n互联网的高速发展使得网络上的信息量爆炸似的增长，高效搜索信息越来越重要，信息引擎已经成为除电子邮件之外的第二大互联网网应用。n在众多搜索引擎中，Google以其庞大的搜索量，快速而精确的搜索结果和极高的知名度成为搜索引擎的代名词。n可是你知道它是如何工作的吗？1、Google及其查询过程2、搜索引擎需要完成的工作o从页面上可以看到，与关键词“math modeling”匹配的结果有3000多万条；与关键词“数学建模”匹配的关键词有130多万条；用户需要的显然不是所有，而是其中最重要的，如何实现快速

23、的搜索，如何合理定义网页的重要性无疑是Google制胜的关键。o如何最快速最精确的提供搜索结果？o搜索引擎完成的工作：n自动下载尽可能多的网页；n建立快速有效的索引；n根据相关性对网页进行公平准确的排序。2、搜索引擎需要完成的工作o从页面上可以看到，与关键词“math modeling”匹配的结果有3000多万条；与关键词“数学建模”匹配的关键词有130多万条；用户需要的显然不是所有，而是其中最重要的，如何实现快速的搜索，如何合理定义网页的重要性无疑是Google制胜的关键。o如何最快速最精确的提供搜索结果？o搜索引擎完成的工作：n自动下载尽可能多的网页；n建立快速有效的索引；n根据相关性对网

24、页进行公平准确的排序。o它要用到图论中的遍历（Traverse)算法。n图论中所讨论的的图由一些节点和连接这些节点的弧组成。如果我们把中国的城市当成节点，连接城市的国道当成弧，那么全国的公路干线网就是图论中所说的图。关于图的算法有很多，但最重要的是图的遍历算法，也就是如何通过弧访问图的各个节点。n以中国公路网为例，我们从北京出发，看一看北京和哪些城市直接相连，比如说和天津、济南、石家庄、南京、沈阳、大同直接相连。我们可以依次访问这些城市，然后我们看看都有哪些城市和这些已经访问过的城市相连，比如说北戴河、秦皇岛与天津相连，青岛、烟台和济南相连，太原、郑州和石家庄相连等等，我们再一次访问北戴河这些

25、城市，直到中国所有的城市都访问过一遍为止。这种图的遍历算法称为“广度优先算法”（BFS)，因为它先要尽可能广地访问每个节点所直接连接的其他节点。n外还有一种策略是从北京出发，随便找到下一个要访问的城市，比如是济南，然后从济南出发到下一个城市，比如说南京，再访问从南京出发的城市，一直走到头。然后再往回找，看看中间是否有尚未访问的城市。这种方法叫“深度优先算法”（DFS)，因为它是一条路走到黑。这两种方法都可以保证访问到全部的城市。需要记录已经访问过的城市，以防同一个城市访问多次或者漏掉哪个如何自动下载互联网所有的网页呢？o通过超链接，我们可以从任何一个网页出发，用图的遍历算法，自动地访问到每一个

26、网页并把它们存起来。完成这个功能的程序叫做网络爬虫，或者在一些文献中称为“机器人”（Robot)。o假定我们从一家门户网站的首页出发，先下载这个网页，然后通过分析这个网页，可以找到藏在它里面的所有超链接，也就等于知道了这家门户网站首页所直接连接的全部网页，诸如雅虎邮件、雅虎财经、雅虎新闻等等。我们接下来访问、下载并分析这家门户网站的邮件等网页，又能找到其他相连的网页。我们让计算机不停地做下去，就能下载整个的互联网。当然，我们也要记载哪个网页下载过了，以免重复。在网络爬虫中，我们使用一个称为“哈希表”(Hash Table)的列表而不是一个记事本纪录网页是否下载过的信息。o现在的互联网非常巨大，

27、不可能通过一台或几台计算机服务器就能完成下载任务。比如雅虎公司（Google 没有公开数目，这里举了雅虎的索引大小为例）宣称他们索引了 200 亿个网页，假如下载一个网页需要一秒钟，下载这 200 亿个网页则需要 634 年。因此，一个商业的网络爬虫需要有成千上万个服务器，并且由快速网络连接起来。如何建立这样复杂的网络系统，如何协调这些服务器的任务，就是网络设计和程序设计的艺术了。如何建立快速的索引？o世界上不可能有比二进制更简单的计数方法了，也不可能有比布尔运算更简单的运算了。尽管今天每个搜索引擎都宣称自己如何聪明、多么智能化，其实从根本上讲都没有逃出布尔运算的框框。o布尔代数简单得不能再简

28、单了。运算的元素只有两个1（TRUE，真)和 0（FALSE，假)。o你们也许会问这么简单的理论能解决什么实际问题。事实上在布尔代数提出后80 多年里，它确实没有什么像样的应用，直到 1938 年香农在他的硕士论文中指出用布尔代数来实现开关电路，才使得布尔代数成为数字电路的基础。所有的数学和逻辑运算，加、减、乘、除、乘方、开方等等，全部能转换成二值的布尔运算。o文献检索和布尔运算的关系n对于一个用户输入的关键词，搜索引擎要判断每篇文献是否含有这个关键词，如果一篇文献含有它，我们相应地给这篇文献一个逻辑值-真（TRUE,或 1），否则，给一个逻辑值-假（FALSE,或0）。n比如我们要找有关原子

29、能应用的文献，但并不想知道如何造原子弹：p写一个查询语句“原子能 AND 应用 AND(NOT 原子弹)”。p每一篇文献对于上面每一个条件，都有一个 True 或者 False 的答案，根据上述真值表就能算出每篇文献是否是要找的 网页。n当然在查询时，不能将每篇文献扫描一遍，来看看它是否满足上面三个条件，因此需要建立一个索引。n最简单索引的结构是用一个很长的二进制数表示一个关键字是否出现在每篇文献中。有多少篇文献，就有多少位数，每一位对应一篇文献，1 代表相应的文献有这个关键字，0 代表没有。p比如关键字“原子能”对应的二进制数是 .，表示第二、第五、第九、第十、第十六篇文献包含着个关键字。p

30、同样，我们假定“应用”对应的二进制数 .。那么要找到同时包含“原子能”和“应用”的文献时，只要将这两个二进制数进行布尔运算 AND。根据上面的真值表，我们知道运算结果是。表示第五篇，第十六篇文献满足要求。注意，计算机作布尔运算是非常非常快的。现在最便宜的微机都可以一次进行三十二位布尔运算，一秒钟进行十亿次以上。当然，由于这些二进制数中绝大部分位数都是零，我们只需要记录那些等于1的位数即可。o布尔运算它的最大好处是容易实现，速度快，这对于海量的信息查找是至关重要的。它的不足是只能给出是与否的判断，而不能给出量化的度量。因此，所有搜索引擎在内部检索完毕后，都要对符合要求的网页根据相关性排序，然后才

31、返回给用户。o查找关于“原子能的应用”的网页。我们第一步是在索引中找到包含这三个词的网页。现在任何一个搜索引擎都包含几十万甚至是上百万个多少有点关系的网页。那么哪个应该排在前面呢？显然我们应该根据网页和查询“原子能的应用”的相关性对这些网页进行排序。因此，这里的关键问题是如何度量网页和查询的相关性。如何确定网页和查询的相关性？o短语“原子能的应用”可以分成三个关键词：原子能、的、应用。根据我们的直觉，我们知道，包含这三个词多的网页应该比包含它们少的网页相关。n漏洞：就是长的网页比短的网页占便宜。o因此我们需要根据网页的长度，对关键词的次数进行归一化，也就是用关键词的次数除以网页的总字数。我们把

32、这个商称为“关键词的频率”，或者“单文本词汇频率”（Term Frequency)，概括地讲，如果一个查询包含关键词 w1,w2,.,wN,它们在一篇特定网页中的词频分别是:TF1,TF2,.,TFN。（TF:term frequency)。那么，这个查询和该网页的相关性就是:TF1+TF2+.+TFN。n漏洞：词“的”的词频对确定网页的主题几乎没有用。称这种词叫“应删除词”（Stopwords)，也就是说在度量相关性是不应考虑它们的频率。n另一个小的漏洞。在汉语中，“应用”是个很通用的词，而“原子能”是个很专业的词，后者在相关性排名中比前者重要。o需要给分解的关键词给一个权重。一个词预测主题

33、能力越强，权重就越大，反之，权重就越小。o我们很容易发现，如果一个关键词只在很少的网页中出现，我们通过它就容易锁定搜索目标，它的权重也就应该大。反之如果一个词在大量网页中出现，我们看到它仍然不很清楚要找什么内容，因此它应该小。概括地讲，假定一个关键词 在 个网页中出现过，那么 越大，的权重越小，反之亦然。在信息检索中，使用最多的权重是“逆文本频率指数”（Inverse document frequency 缩写为），它的公式为（）其中是全部网页数。比如，我们假定中文网页数是亿，应删除词“的”在所有的网页中都出现，即亿，那么它的log(10亿/10亿）=log(1)=。假如专用词“原子能”在两百

34、万个网页中出现，即万，则它的权重log(500)=6.2。又假定通用词“应用”，出现在五亿个网页中，它的权重=log(2)，则只有 0.7。也就只说，在网页中找到一个“原子能”的比配相当于找到九个“应用”的匹配。利用 IDF，上述相关性计算个公式就由词频的简单求和变成了加权求和，即 TF1*IDF1+TF2*IDF2.+TFN*IDFN。oTF/IDF（term frequency/inverse document frequency)的概念被公认为信息检索中最重要的发明。在搜索、文献分类和其他相关领域有广泛的应用。o其实，信息论的学者们已经发现并指出，其实 IDF 的概念就是一个特定条件下、

35、关键词的概率分布的交叉熵（Kullback-Leibler Divergence)。这样，信息检索相关性的度量，又回到了信息论。如何确定网页的排名？oPage Rank Google 的民主表决式网页排名技术nGoogle 革命性的发明是它名为“Page Rank”的网页排名算法，这项技术彻底解决了搜索结果排序的问题。oGoogle为了提供搜索者想要的信息，达到完美的搜索引擎功能，采用“网页级别(Pagebank)”与“页面分析”两种技术来确保检索质量与精确率，所谓Pagebank技术是基于整个网络的链接结构，按网页链接广泛程度来决定网页的重要性，而“页面分析”也就是前面所讲的相关性的分析。G

36、oogle将最相关和最可靠的结果放在搜索结果的顶端，一般而言，Pagebank对于排名的影响还是比页面分析高。oPagebank技术通过对多达80多亿个的网页进行重要性分析，利用网络链接结构对网页进行组织整理。基本的原理是：如果网页A链接到网页B，Google就认为“网页A投了网页B一票”，这是80多亿个网页之间的海选，每个网页都有选举权，也有被选举权，投票次数不限。初看起来这样的选举不是很有序，公平性似乎无从谈起，关键在于如何“计票”，一个网页的Pagebank并不是它的得票数。o假设Google数据库中网页的集合为W，该集合元素的格式为N，为了描述这些网页之间的关系，定义一个N*N的方阵G

37、=(gij).如果从网页j到网页i有超链接，则gij=1,否则为零，显然G是巨大的但是非常稀疏的矩阵，其中非零元素的总数即是网页之间超链接的总数。o计算得到该Markov链的平均分布为：x=(0.2330 0.2447 0.1965 0.1240 0.0777 0.1240)，这就是6个网页的Pagebank.编号为2的网页在选举中仅仅得到一票，但是它的Pagebank要高于其它得到一票的网页，原因在于它的一票来自网页ALPHA，这个网页的Pagebank也比较高，所以这是合理的。o理论问题解决了，又遇到实际问题。因为互联网上网页的数量是巨大的，上面提到的二维矩阵从理论上讲有网页数目平方之多个

38、元素。如果我们假定有十亿个网页，那么这个矩阵 就有一百亿亿个元素。这样大的矩阵相乘，计算量是非常大的。Google 的两个创始人拉里佩奇（Larry Page）和谢尔盖布林(Sergey Brin)两人利用稀疏矩阵计算的技巧，大大的简化了计算量，并实现了这个网页排名算法。今天 Google 的工程师把这个算法移植到并行的计算机中，进一步缩短了计算时间，使网页更新的周期比以前短了许多。o今天，Google 搜索引擎比最初复杂、完善了许多。但是网页排名在 Google 所有算法中依然是至关重要的。在学术界,这个算法被公认为是文献检索中最大的贡献之一，并且被很多大学引入了信息检索课程(Informa

39、tion Retrieval)的教程。地面上存在着地面上存在着n个接收站与个接收站与n个发送站，而在通讯卫星上则个发送站，而在通讯卫星上则设置了若干种开关模式。开关模式可用矩阵设置了若干种开关模式。开关模式可用矩阵P=(pij)表示，若表示，若卫星可接收发送站卫星可接收发送站i发射的信息并将信息送回地面的接收站发射的信息并将信息送回地面的接收站j，矩阵中的元素，矩阵中的元素pij=1，否则，否则pij=0。通讯卫星上的接收发送。通讯卫星上的接收发送任务也可以用一个矩阵任务也可以用一个矩阵T=（tij）来表示，其元素）来表示，其元素tij为需经通为需经通讯卫星传递的由讯卫星传递的由i发点发送到发

40、点发送到j接收点的信息量的传送时间长接收点的信息量的传送时间长度。由于技术原因，当发送站度。由于技术原因，当发送站i在发送给接收站在发送给接收站j信息时，它信息时，它不能同时发送给别的接收站信息；同样，当接收站不能同时发送给别的接收站信息；同样，当接收站j在接收在接收发送站发送站i的信息时，也不能同时接收其他发送站发送的信息。的信息时，也不能同时接收其他发送站发送的信息。你的任务是：你的任务是：另一个例子：通讯卫星上的开关设置另一个例子：通讯卫星上的开关设置o设计一组开关模式，设计一组开关模式，k=1,r（注：（注：r应当尽可能小），使应当尽可能小），使得对任意给定的任务矩阵得对任意给定的任务

41、矩阵T，卫星开关设置均能完成要求，卫星开关设置均能完成要求的发接收任务。的发接收任务。o设计一个算法，在发接收任务设计一个算法，在发接收任务T给出后，可根据你设计的给出后，可根据你设计的开关模式（开关模式（k=1,r）求出各开关的使用时间）求出各开关的使用时间，使得在完，使得在完成预定传送任务的前提下使用各开关模式的总时间短。成预定传送任务的前提下使用各开关模式的总时间短。o同样由于技术上的原因，开关模式的总数同样由于技术上的原因，开关模式的总数r有一个上限。当有一个上限。当需要传送的任务数数量较大时，仍无法分派任务。要求想需要传送的任务数数量较大时，仍无法分派任务。要求想一些办法来解决这一困

42、难，（当然，这时可能要作出一些一些办法来解决这一困难，（当然，这时可能要作出一些牺牲，即传送时间可能会增加一些）。牺牲，即传送时间可能会增加一些）。即要求设计开关系统及使用方法，达到以下目的：设计开关系统及使用方法，达到以下目的：（1）开关数量要少（控制在一个合理的范围内）开关数量要少（控制在一个合理的范围内）（2）使用卫星上的开关时应尽量节省卫星租用）使用卫星上的开关时应尽量节省卫星租用时间时间（3）设计具体操作方法）设计具体操作方法问题及模型问题及模型问题的标准形式为：在地面上存在着问题的标准形式为：在地面上存在着n个收站与个收站与n个发战，而个发战，而在通讯卫星上则设置了若干种开关模式。

43、开关模式可用矩阵在通讯卫星上则设置了若干种开关模式。开关模式可用矩阵P=(pij)来表示，若卫星可接收发射站来表示，若卫星可接收发射站i发射的信息并将信息传送发射的信息并将信息传送回地面的接收站回地面的接收站j时，矩阵元素时，矩阵元素pij=1，否则，否则pij=0。通讯卫星。通讯卫星的接发任务也可用一矩阵的接发任务也可用一矩阵T=（tij）来表示，其元素）来表示，其元素tij为需经为需经通讯卫星传递的由通讯卫星传递的由i发点发送到发点发送到j接受点的信息量的传送时间接受点的信息量的传送时间长度。问题要求求长度。问题要求求r并设计一组开关模式并设计一组开关模式Pk，k=1,r及模式及模式Pk的

44、使用时间的使用时间k，使得在完成预定传送任务的前提下各开关，使得在完成预定传送任务的前提下各开关模式使用的总时间最短，即要求求解下面的问题：模式使用的总时间最短，即要求求解下面的问题：一个实例一个实例设设 这是一个有这是一个有3个发送站与个发送站与3个接收站的实例，个接收站的实例，tij在矩阵中已给出，例如在矩阵中已给出，例如由发站由发站1传送到收站传送到收站1的通讯量为的通讯量为3单位时间等。单位时间等。分析分析 容易看出，三个发站需传送的时间分别为容易看出，三个发站需传送的时间分别为6、5、5；而三个收站需接；而三个收站需接收的时间分别为收的时间分别为6、3、7。为完成全部传送任务，通讯卫

45、星总传送时间至少。为完成全部传送任务，通讯卫星总传送时间至少应为应为7单位时间，即的下界为单位时间，即的下界为7。由于技术上的原因，当发站由于技术上的原因，当发站i在发送给收站在发送给收站j信息时，它不能同时发送给别的信息时，它不能同时发送给别的收站信息；同样，当收站收站信息；同样，当收站j在接收发站在接收发站i的信息时，也不能同时接收其他发站的信息时，也不能同时接收其他发站发送的信息。这一要求说明，任一开关模式发送的信息。这一要求说明，任一开关模式Pk应具有以下性质：（应具有以下性质：（1）Pk的的每一行中有且只有一个每一行中有且只有一个1，每一列中也有且只有一个，每一列中也有且只有一个1；

46、（；（2）所有的）所有的1均位均位于不同的行列中。于不同的行列中。满足（满足（1）、（）、（2）的矩阵）的矩阵 被称为置换矩阵，被称为置换矩阵，n阶置换矩阵阶置换矩阵Pk共有共有n!个，当个，当n较大时，我们不可能在通讯卫星上设置这么多种不同的开关模式。因而，为较大时，我们不可能在通讯卫星上设置这么多种不同的开关模式。因而，为了设计出切实可行的开关模式，我们还得另想办法。了设计出切实可行的开关模式，我们还得另想办法。（问题）至少要多少种开关模式？（问题）至少要多少种开关模式？易见，必须有易见，必须有 （设计方法（设计方法1）注意到注意到Pk每行（或列）元素之和均为每行（或列）元素之和均为1，故

47、不管如何指派开关的使用时间，故不管如何指派开关的使用时间（即不论如何取（即不论如何取k），矩阵），矩阵均具有某些特殊的性质，例如其行和（及列和）均为同一常数。这样的矩均具有某些特殊的性质，例如其行和（及列和）均为同一常数。这样的矩阵构成一个线性空间（参见阵构成一个线性空间（参见Drer魔方），为减少开关模式的种类，可取此魔方），为减少开关模式的种类，可取此空间的一组基底作为开关模式。在使用这种开关模式时，无论空间的一组基底作为开关模式。在使用这种开关模式时，无论T的元素的元素tij怎怎么取，通讯卫星对每一发（收）点的开通时间总和是恒定的。在这种开关么取，通讯卫星对每一发（收）点的开通时间总和是

48、恒定的。在这种开关模式下，可按如下方式指派各开关模式的使用时间：模式下，可按如下方式指派各开关模式的使用时间：步步1 先将先将T改变为改变为 ，满足：满足：（1）T（2）记）记 ，步步2 用用Pk表示表示 ，即将，即将 分解为分解为（r为空间的维数）为空间的维数）将将T化为化为 的方法一般有无穷多种，如可如下化法：的方法一般有无穷多种，如可如下化法：令令 事实上，事实上，（即通讯卫星传送总时间的下界）。，（即通讯卫星传送总时间的下界）。令令 其中其中 用这种方法化例中的用这种方法化例中的T，得到，得到的任一行（或列）中元素之和均为的任一行（或列）中元素之和均为7。定义定义1 1称行和、列和均相

49、等的矩阵为双随机矩阵（称行和、列和均相等的矩阵为双随机矩阵（Doubly stochastic matrix）定理定理1 1（Birkhoff定理，定理，1944）任一）任一n阶双随机矩阵均可写成至多阶双随机矩阵均可写成至多 （n1）2+1个置换矩阵的非线性组合。个置换矩阵的非线性组合。的分解方法可如下进行：的分解方法可如下进行：步步1 选取由选取由Pij0可推出可推出 0的置换矩阵的置换矩阵P步步2 确定确定 步步3 取取 ，用，用 代替代替步步4 若若 =0，停；否则，返回步，停；否则，返回步1。例例2.2.为方便起见，我们来分解一个元素均为非负整数的为方便起见，我们来分解一个元素均为非负

50、整数的3阶双随机矩阵，阶双随机矩阵，（由（由Birkhoff定理，定理，r5）解：取解：取 ，=min 1,3,3 =1分解成分解成，再取，再取 因因min 5,5,3=3，又有，又有，取，取 于是又有于是又有 易得分解结果为：易得分解结果为：尚需解决的问题是如何求尚需解决的问题是如何求P，使得，使得Pij0必有必有 。读者不难发现，此问。读者不难发现，此问题可以通过求解一个两分图上的最大流（或最大匹配）来实现，计算量题可以通过求解一个两分图上的最大流（或最大匹配）来实现，计算量为为O(n4)，是多项式时间可解的。具体方法为：作一两分图，若，是多项式时间可解的。具体方法为：作一两分图，若 ，则