数学模型MathematicalModel.ppt

《数学模型MathematicalModel.ppt》由会员分享，可在线阅读，更多相关《数学模型MathematicalModel.ppt（90页珍藏版）》请在三一办公上搜索。

1、数学模型Mathematical Model,卢 力,School of Software Engineering,现状,数学建模是一门新兴的学科，20世纪70年代初诞生于英、美等现代工业国家。在短短几十年的历史瞬间辐射至全球大部分国家和地区。20世纪80年代初，我国高等院校也陆续开设了数学建模课程，随着数学建模教学活动（包括数学建模课程、数学建模竞赛和数学（建模）实验课程等）的开展，这门课越来越得到重视，也深受广大学生的喜爱。由于新技术特别是计算机技术的飞速发展，大量的实际问题需要用计算机来解决，而计算机与实际问题之间需要用数学模型来沟通。社会对大学生的要求越来越高，大学生毕业后要适应社会的

2、需求，一到工作岗位就能创造价值。,教授赠言,课程特点,题材的实用性：教材的内容来自于实际。知识的广泛性：依赖于各方面的基础知识。内容的趣味性：有些问题就象是做游戏，引人入胜。教法的多样性：教师讲授方式，小组讨论方式，学生报告方式，课堂教学方式，课外教学方式等。,教学目的,培养学生解决实际问题的综合能力丰富灵活的想象能力抽象思维的简化能力一眼看穿的洞穿能力发散思维的联想能力与时俱进的开拓能力学以致用的应用能力,会抓重点的判断能力高度灵活的综合能力使用电脑的动手能力信息资料的查阅能力科研论文的写作能力团结协作的攻关能力,教学目的,培养学生解决实际问题的综合能力查阅文献、搜集资料的能力“双向翻译”能

3、力 运用数学思想进行综合分析能力综合运用知识的能力发现和创新能力观察力和想象力 提高撰写科研论文的能力团结合作精神和相互协调能力,教材,数学模型第三版姜启源，谢金星，叶俊高等教育出版社，2003,参考书,数学模型（第三版）习题参考解答姜启源，谢金星，叶俊高等教育出版社，2003数学建模（本科册）湖北省大学生数学建模竞赛专家组华中科技大学出版社，2006 数学建模与数学实验（第二版）赵静，但琦 高等教育出版社，2003,数学建模的理论与实践 吴翊，吴孟达，成礼智 国防科技大学出版社，1999 数学模型与数学建模 刘来福，曾文艺 北京师范大学出版社，2002,网站,全国大学生数学建模竞赛（官方网站

4、）China Undergraduate Mathematical Contest in Modeling(CUMCM)中国数学建模网（国防科技大学，湖南，中国最大的数学建模网站）华中数学建模 数模之家（山东数模）http:/北京诺亚数学建模科技有限公司 MCM/ICM 中国数学资源网 http:/,期刊,数学文化(香港出版，可免费下载全文)Journal of Mathematical Modeling and Application(巴西编辑出版，可免费下载全文)Journal of Mathematical Modelling and Algorithms Teaching Mathem

5、atics and its Applications Applied Mathematical Modelling Mathematical and Computer Modelling Mathematical Modelling and Applied Computing International Journal of Mathematical Modeling,Simulation and Applications,高校应用数学学报 工程数学学报 运筹学学报 数学的实践与认识 系统工程理论与实践 系统工程学报,成绩评定,平时成绩30%作业10%小论文20%结业考试70%,联系方式,Em

6、ailPhoneOfficeRoom N-305,主要讲授内容,第一章 建立数学模型 第二章 初等模型 第三章 简单的优化模型 第四章 数学规划模型 第五章 微分方程模型 第七章 差分方程模型,第一章 建立数学模型,1.1 从现实对象到数学模型1.2 数学建模的重要意义1.3 数学建模示例椅子能在不平的地面上放稳吗商人们怎样安全过河如何预报人口的增长1.4 数学建模的方法和步骤1.5 数学模型的特点和分类1.6 怎样学习数学建模,主要讲授内容,1.1 从现实对象到数学模型,本节讨论原型与模型模型分类航行问题航行问题建立数学模型的基本步骤数学模型和数学建模,原型（Prototype）：人们在社会

7、实践中所关心和研究的现实世界中的事物或对象。在科技技术等领域通常使用系统、过程等词汇代之。如机械系统、电力系统、生态系统、生命系统、社会系统等。又如钢铁冶炼过程、导弹飞行过程、化学反应过程、污染扩散过程、生产销售过程、计划决策过程等。系统的观点能让人们更好地认识和把握事物。人们所关心和研究的事物或系统总是存在着矛盾，矛盾就是问题，研究事物或系统就是去解决问题。事物或系统总是处于运动变化的过程之中，如何把握它们在运动变化过程中的规律性，是研究事物或系统的根本问题。,原型与模型,把“现实对象”、“实际问题”、“研究对象”以及“系统”等都称为事物的原型。模型（Model）：指为了一定的目的，根据原型

8、特有的内在规律，将原型所具有的本质属性的某一部分信息经过简化、浓缩、提炼而构造的原型替代物。模型不是原型原封不动的复制品。一个原型，为了不同的目的可以有多种不同的模型。如放在展厅里的飞机模型应该在外形上逼真，但不一定能飞；而参加航模竞赛的模型飞机要具有良好的飞行性能，在外观上不必苛求；在飞机设计、试制过程中用到的数学模型和计算机模拟，则只要求在数量规律上真实反映飞机的飞行动态特性，毫不涉及飞机的实体。模型的基本特征是由构造模型的目的决定的。,用模型替代原型的方式来分类：物质模型和理想模型物质模型（形象模型）直观模型 将原型的尺寸按比例缩小或放大，主要追求外观上的逼真。玩具、照片、沙盘、火箭模型

9、、物理模型 主要指科技工作者为一定目的根据相似原理构造的模型。不仅可以显示原型的外形或某些特征，而且可以用来进行模拟实验，间接地研究原型的某些规律。波浪水箱中的舰艇、风洞中的飞机、地震模拟、,模型分类,理想模型（抽象模型）思维模型指通过人们对原型的反复认识，将获取的知识以经验形式直接储存于人脑中，从而可以根据思维或直觉作出相应的决策。司机开车、钳工的操作、符号模型指在一些约定或假设下借助于专门的符号、线条等，按一定形式组合起来描述模型。地图、电路图、建筑图、分子结构图、,数学模型由数字、字母或其它数学符号组成的，描述现实对象数量规律的数学公式、图形或算法。计算机模拟 计算机模拟或者计算机模型是

10、用来模拟一个特定系统抽象模型的计算机程序。电子游戏,甲乙两地相距750千米，船从甲到乙顺水航行需30小时，从乙到甲逆水航行需50小时，问船的速度是多少?用 x 表示船速，y 表示水速，列出方程：(x+y)30=750,(x y)50=750求解得：x=20 km/h，y=5 km/h答：船速为 20 千米/小时。,航行问题,作出简化假设（船速、水速为常数）；用符号表示有关量（x,y 分别表示船速和水速）；用物理定律（匀速运动的距离等于速度乘以时间）列出数学式子（二元一次方程组）；求解得到数学解（x=20,y=5）；回答原问题（船速为20千米/小时）。,航行问题建立数学模型的基本步骤,数学模型或

11、模型(Mathematical Model)对于现实世界的一个特定对象，为了一个特定目的，根据其特有的内在规律，做出一些必要的简化假设，运用适当的数学工具，得到的一个数学结构。数学模型不是原型的复制品，而是为一定的目的对原型所作的一种抽象模拟。它用数学式子、数学符号、程序及图表等刻画客观事物本质属性与内在联系，是对现实世界的抽象、简化而又本质的描述。数学模型源于现实，又高于现实。它或者能解释特定事物现象的现实性态；或者能预测特定对象的将来的性态；或者能提供处理特定对象的最优决策或控制等等，最终达到解决实际问题的目的。,数学模型和数学建模,数学建模或建模(Mathematical Modelin

12、g)建立数学模型的全过程（包括表述、求解、解释、检验等）。,1.2 数学建模的重要意义,电子计算机的出现及飞速发展，数学以空前的广度和深度向一切领域渗透，数学建模作为用数学方法解决实际问题的第一步，越来越受到人们的重视。在一般的工程技术领域，数学建模仍然大有用武之地；在高新技术领域，数学建模几乎是必不可少的工具；数学进入一些新领域，为数学建模开辟了许多处女地。一门科学只有成功地运用数学时，才算达到了完善的地步。马克思,数学建模的具体应用分析与设计预报与决策控制与优化规划与管理,数学建模,计算机技术,知识经济,1.3 数学建模示例,1.3.1 椅子能在不平的地面上放稳吗?1.3.2 商人们怎样安

13、全过河?1.3.3 如何预报人口的增长?,1.3.1 椅子能在不平的地面上放稳吗？,问题将四条腿一样长的正方形椅子放在不平的地面上，是否总能设法使它的四条腿同时着地，即放稳？模型假设地面为连续曲面（无台阶等）；只要有一点着地就视为椅脚已经着地，即将与地面的接触视为几何上的点接触；地面相对平坦，使椅子在任意位置至少三只脚同时着地；椅子的中心不动。,模型构成,用数学语言把椅子位置和四只脚着地的关系表示出来,椅子位置,利用正方形（椅脚连线）的对称性,用（对角线与 x 轴的夹角）表示椅子位置,四只脚着地,四个距离(四只脚),A,C 两脚与地面距离之和记为 f()B,D 两脚与地面距离之和记为 g(),

14、两个距离,椅脚与地面距离为零距离是 的函数,正方形ABCD绕O点旋转,f(),g()是连续函数,对任意，f()、g()中至少有一个为 0，即有 f()g()=0.,数学问题,已知：f(),g()是连续函数；对任意，f()g()=0；且 g(0)=0，f(0)0.证明：存在0，使 f(0)=g(0)=0.,地面为连续曲面,椅子在任意位置至少三只脚着地,f()=g()=0.,四只脚着地,模型求解,给出一种简单、粗糙的证明方法,将椅子逆时针旋转90，对角线AC和BD互换。由 g(0)=0，f(0)0，知 f(/2)=0，g(/2)0.令 h()=f()g()，则 h(0)0 和 h(/2)0.由 f

15、,g 的连续性知 h 为连续函数,根据连续函数的介值定理，必存在 0(0,/2)，使 h(0)=0，即 f(0)=g(0).因为对任意，f()g()=0，所以 f(0)=g(0)=0.,评注和思考,建模的关键：椅子的位置变量 及距离函数 f()、g(),正方形的对称性及旋转 90 不是关键。考察四脚呈长方形的椅子,1.3.2 商人们怎样安全过河,问题(智力游戏),3名商人 3名随从,三个商人各带一个随从乘船渡河，这只小船只能容纳两人，由他们自行划行。随从们密约，在河的任一岸，一旦他们的人数比商人们多，就杀人越货。但是如何乘船渡河的大权掌握在商人们手中。,试为商人们制定一个安全渡河的方案。,问题

16、分析这是一个状态转移问题，即多步决策过程。状态(State)变量、决策(Decision)变量，状态转移规律决策：每一步（此岸到彼岸或彼岸到此岸）船上的人员要求：在安全的前提下（两岸的随从数不比商人数多），经有限步使全体人员过河。,此岸,彼岸,模型假设记渡河过程中此岸的商人数为 x，随从数为 y，x,y=0,1,2,3此岸的状态可用向量(x,y)表示，共有 16 种可能的状态对商人安全的状态：(3,y)(其中 y=0,1,2,3)，表示商人全在此岸；(0,y)(其中 y=0,1,2,3)，表示商人全在对岸；(x,y)(其中 x=y=1,2)，表示两岸商人和随从一样多。这些状态的集合称为允许状态

17、集合，记做 S。S=(x,y)x=3,y=0,1,2,3;x=0,y=0,1,2,3;x=y=1,2,此岸,彼岸,状态转移需经状态运算来实现。摆一次渡就可以改变现有状态，这种状态运算正是要选择的策略，也称为决策，用向量(u,v)表示，即 u 名商人和 v 名随从乘船。显然允许决策集合为D=(u,v)1 u+v 2小船从此岸到彼岸或从彼岸到此岸的每一次航行，都造成状态的一次转移。用 s1(x,y),s2(x,y),表示状态的变化过程，sk S。用 dk(x,y)表示状态 sk(x,y)下的决策，dk D。,因为 k 为奇数时，小船离开此岸；k 为偶数，到达此岸，所以状态转移满足下列关系：sk+1

18、=sk+(-1)kdk.多步决策问题：求决策 dk D(k=1,2,n)，使状态 sk S，并按转移律由 s1(3,3)到达 sn+1(0,0)，n 越小越好.模型求解穷举法编程上机。如果计算过程中出现循环，说明问题无解。当问题比较简单时，可作如下分析。,第一次渡河：,第二次渡河：对于d1(0,1)由此可见，应排除单人渡河的方案。,第二次渡河：对于d1(1,1),第二次渡河：对于d1(0,2)因此，第二次渡河时，可采取的策略为：d1(1,1)d2(1,0)或d1(0,2)d2(0,1),这一方法实际上是一种搜索技术。类似进行以上分析，可寻找出渡河方案。,模型求解图解法,状态 s=(x,y)16

19、个格点,允许决策：移动 1 或 2 格;k 奇,左下移;k 偶,右上移,s1,sn+1,d1,d11给出安全渡河方案,评注和思考,规格化方法，易于推广,考虑 4 名商人各带一随从的情况,允许状态 S,S=(x,y)x=0,y=0,1,2,3;x=3,y=0,1,2,3;x=y=1,2,考虑汉诺塔的问题,背景人类文明发展到今天，人们越来越意识到地球资源的有限性，我们感受到“地球在变小”，人口与资源之间的矛盾日渐突出，人口问题已成为当前世界上被最普遍关注的问题之一，当然人口增长规律的发现以及人口增长的预测对一个国家制定比较长远的发展规划有着非常重要的意义。,1.3.3 如何预报人口的增长,世界人口

20、增长概况,中国人口增长概况,研究人口变化规律,控制人口过快增长,影响人口的因素很多：人口的多少，出生率、死亡率的高低，人口男女比例大小，人口年龄构成情况，工农业生产水平高低，各民族的风俗习惯，自然灾害，战争，人口迁移等。我们先把问题简化，只考虑人口增长的主要因素增长率（出生率 死亡率），其余因素暂不考虑，建立一个较粗的数学模型。在这个模型的基础上逐步考虑次要因素的影响，从而建立一个比一个与实际更加吻合的数学模型。下面仅介绍几个最简单、最典型的人口增长模型。,1、指数增长模型,两个基本模型,x(t)：时刻 t 的人口,基本假设：人口（相对）增长率 r 是常数,今年人口 x0，年增长率 r（保持不

21、变），,k 年后人口,随着时间增加，人口按指数规律无限增长（r 0）,最简单的人口增长模型,指数增长模型,马尔萨斯(Malthus)提出(1798),指数增长模型的应用及局限性与 19 世纪以前欧洲一些地区人口统计数据吻合适用于 19 世纪后迁往加拿大的欧洲移民后代可用于短期人口增长预测不符合 19 世纪后多数地区人口增长规律不能预测较长期的人口增长过程19 世纪后人口数据，人口增长率 r 不是常数（逐渐下降）,2、阻滞增长模型（Logistic模型）,人口增长到一定数量后，增长率下降的原因：自然资源、环境条件等因素对人口增长的阻滞作用阻滞作用随人口数量增加而变大,假设 r(x)为 x 的线性

22、函数：r(x)=r sx(r,s 0),r 固有增长率（x 很小时）,xm 人口容量（资源、环境能容纳的最大数量）,r 是 x 的减函数,x(t)S 形曲线,x 增加先快后慢,参数估计,用指数增长模型或阻滞增长模型作人口预报，必须先估计模型参数 r 或 r,xm,利用统计数据采用最小二乘法作拟合,例：美国人口数据（单位：百万）,专家估计,模型检验,用模型计算 2000 年美国人口，与实际数据比较,实际为281.4(百万),模型应用,加入 2000 年人口数据后重新估计模型参数,预报美国2010年的人口,Logistic 模型在经济领域中的应用(如耐用消费品的售量),数学建模的基本方法,机理分析

23、,测试分析,根据对客观事物特性的认识，找出反映内部机理的数量规律,将对象看作“黑箱”，通过对量测数据的统计分析，找出与数据拟合最好的模型,机理分析没有统一的方法，主要通过实例研究(Case Studies)来学习。以下建模主要指机理分析。,二者结合,用机理分析建立模型结构，用测试分析确定模型参数,1.4 数学建模的方法和步骤,足够的精度，即要求把本质的关系和规律反映进去，把非本质的东西去掉。简单、便于处理。依据要充分，即要依据科学规律、经济规律等来建立公式和图表。尽量借鉴标准形式。模型所表示的系统要能操纵和控制，便于检验和修改。,数学建模的基本要求,数学建模的一般步骤,模型准备,模型假设,模型

24、构成,模型求解,模型分析,模型检验,模型应用,不合格,不合格,合格,合格,模型准备,了解实际背景,明确建模目的,搜集有关信息,掌握对象特征,形成一个比较清晰的“问题”,模型假设,针对问题特点和建模目的,作出合理的、简化的假设,在合理与简化之间作出折中,假设的依据 对问题内在规律的认识，对现象、数据的分析，以及二者的综合 想像力、洞察力、判断力以及经验等 合理性的原则 目的性原则：从原型中抽象出与建模目的有关的因素，简化掉与建模目的无关的或关系不大的因素。简明性原则：所给出的假设条件要简单、准确，有利于构造模型。真实性原则：假设条件要符合情理，简化带来的误差应满足实际问题所能允许的误差范围。全面

25、性原则：在对事物原型本身作出假设的同时，还要给出原型所处的环境条件。,模型构成,用数学的语言、符号描述问题的内在规律,发挥想像力,使用类比法,尽量采用简单的数学工具,建立包含常量、变量等的数学模型,模型求解,各种数学方法、软件和计算机技术,对求解结果进行数学上的分析如结果的误差分析、统计分析、模型对数据的灵敏性及稳定性分析等,模型分析,模型检验,与实际现象、数据比较，检验模型的合理性、适用性,模型应用,应用中可能发现新问题，需继续完善,数学模型没有固定的模式，也不要求都要经过上述这些步骤，有时各步骤之间的界限也不那么分明，因此建模不要拘泥于形式上的按部就班，而应采取灵活的表达形式。进一步对上述

26、建模的一般步骤分析，可以将数学建模的全过程分为表述、求解、解释、验证四个阶段，并且通过这些阶段完成从现实对象到数学模型，再从数学模型回到现实对象的循环，如下图所示。,数学建模的全过程,现实对象的信息,数学模型,现实对象的解答,数学模型的解答,(归纳),(演绎),表述,求解,解释,验证,根据建模目的和信息将实际问题“翻译”成数学问题,选择适当的数学方法求得数学模型的解答,将数学语言表述的解答“翻译”回实际对象,用现实对象的信息检验得到的解答,实践,现实世界,数学世界,除去一些变量 在机理分析中和在一定的条件下，常将描述分布参数系统的偏微分方程，简化为集中参数的常微分方程。在统计分析中，则采用主成

27、分分析法、向后回归法（淘汰法）和逐步回归方法，以减少变量个数，或在建模前，采用正交试验方法，在众多因素（变量）中找出对指标有显著影响的少量因素，再进行优选试验，进而建立模型。合并一些变量 在构造模型时，将一些性质相同或相似的变量合并成少数有代表性的变量，尽管这样做降低了模型的精度，但只要能满足建模的基本要求，则是可行的。,常用简化模型的方法,改变变量的性质 常用的方法是，将某些非主要的或暂时的变量看作常量，将连续变量看作离散变量，或把离散变量看作连续变量。改变变量之间的函数关系 当处理非线性问题遇到困难或建模精度要求不高时，常将非线性函数在某一点处展开（Taylor展开），取前两项作为近似表达

28、式，即用线性关系逼近非线性关系式。也可以采用二次函数或其他研究比较透彻的函数逼近，而使模型简化。在随机性模型中，常采用一些熟悉的概率分布函数，如正态分布、指数分布等去代替不太好处理的概率分布函数。,改变约束关系 如增加一些约束，或去掉一些约束，对约束进行一些修改等。又如在求解数学规划时，若要求目标函数的极大值，而真正解不一定能找到时，则增加约束后求得的可行解一般是偏低的，称之为保守解或悲观解；去掉一些约束求得的解往往偏高，称之为冒进解或乐观解。虽然它们都不是问题的真正的解，但可以通过它们了解真正解的范围，这对问题进行初步评价是有用的。模型结构的转换 若某种在理论上很简单，但求解困难，甚至无法求

29、解，或者某种模型，要求具有某种数据，而这种数据不具备或不易得到，只有改用其他形式的模型，即改变模型的结构。,模型结构的转换，需要在对问题透彻理解和想像的基础上，实现视角的转换，即从不同的角度观察问题，进而采用不同的数学工具来描述同一问题。在建模时，能否用数学工具描述某一问题的特征是建模的前提。当根据观测数据对回归法模型的参数或时序模型的参数进行估计时，系统可辨识性问题也就同时提出来了。当根据某物理场的信息估计偏微分方程中的某些参数时，如场的存在范围或边界条件，也遇到了数学物理反问题的适定性问题，这些数学建模的理论问题有待于在专门的问题中研究。,1.5 数学模型的特点和分类,模型的逼真性和可行性

30、费用与效率的折衷,模型的合理性与渐进性推陈出新,模型的强健性（稳定性）微小改变无大变化,模型的可转移性转移到其他领域,模型的非预制性Open-end problem,模型的条理性分析更全面、深入,模型的技艺性技术与艺术,模型的局限性近似的通用性与精确性,数学模型的特点,数学模型的分类,应用领域,人口、交通、经济、生态、,数学方法,初等数学、微分方程、规划、统计、,表现特性,描述、优化、预报、决策、,建模目的,了解程度,白箱,灰箱,黑箱,确定和随机,静态和动态,线性和非线性,离散和连续,白箱模型 其内在机理相当清楚的学科问题，包括力学、热学、电学等。主要是研究优化设计和控制等问题。灰箱模型 其内

31、在机理尚不十分清楚的现象和问题，包括生态、气象、经济、交通、化工、地质等。主要是建立和完善这些模型。黑箱模型其内在机理（数量关系）很不清楚的现象，如生理、医学、生命科学、社会科学等。主要是从定性研究朝定量化方向发展。,模型的分类在本课程中没什么重要意义，因为对一个现实问题而言，数学建模没有确定的模式，它与问题的性质、建模目的、建模者自身的数学素质有关，甚至还与建模者的灵性有关。,数学模型的评价标准,相似性,能够真实反映所研究对象的本质特征和运动规律,简明性,结构简明，便于理论分析、逻辑推理和数值计算,可检验性,能有效地说明和解释实际问题，并能检验其可靠程度,1.6 怎样学习数学建模,数学建模与

32、其说是一门技术，不如说是一门艺术,技术大致有章可循,艺术无法归纳成普遍适用的准则,想像力,洞察力,判断力,学习、分析、评价、改进别人做过的模型,亲自动手，认真做几个实际题目,经验,直觉,灵感,广博的知识,例1 某人家住 T 市，在外地工作，平时总是乘坐下午 5:30 到达 T 市的火车回去，他的妻子准时在车站接他。有一天此人提前半小时下班，乘火车 5:00 到达 T 市，然后步行回家。路上，他遇到了开车来接他的妻子，由此比平时早 10分钟 到家。问此人一共步行了多少时间？该问题涉及两个人，由于问题的叙述和提问都是站在“某人”的角度，而“某人”到达 T 市的时刻在变化，因此，顺着问题正面叙述的角

33、度看，条件不足。,培养想像力的两个例子,在考虑问题时，实际上忽视了另一个人的存在。这就是“妻子”，而“妻子”每天从家到火车站的时刻表是不变的，这就找到了一个“参照系”，转而站在“妻子”的角度观察问题。若“妻子”在这一天像往常一样继续开车到火车站（到火车站时刻为5:30）然后回家，那么他们就会在平时一样的时刻到家，这说明提前的10分钟是没有去车站省下的，即相遇时，妻子距火车站还有5分钟的路程，因此相遇时刻为5:25，这说明此人已步行了25分钟。,例2 某人第一天上午8:00由 A 处出发，于下午6:00到达 B 处，第二天上午8:00他又由 B 处出发仍沿原路返回，并于下午6:00回到 A 处。

34、证明：途中至少存在一点，此人在两天中同一时刻到达该处。将问题设想成甲、乙两人在同一天分别从 A、B 两地相向而行，两人必在途中某处相遇，则结论的正确性就十分明显了。,练习题,1.（P23，9）为了培养想像力、洞察力和判断力，考察对象时除了从正面分析外，还常常需要从侧面或反面思考。试尽可能迅速地回答下面的问题：(1)某甲早上8:00从山下旅店出发，沿一条路径上山，下午5:00到达山顶并留宿。次日早8:00沿同一路径下山，下午5:00回到旅店。某乙说，甲必在两天中的同一时刻经过路径中的同一地点。为什么?(2)37支球队进行冠军争夺赛，每轮比赛中出场的每两支球队中的胜者及轮空者进行下一轮，直至比赛结

35、束。问共需进行多少轮比赛？如果是 n 支球队比赛呢？,(3)甲、乙两站之间有电车相通，每隔10分钟甲、乙两站相互发一趟车，但发车时刻不一定相同。甲乙之间有一中间站丙，某人每天在随机的时刻到达丙站，并搭乘最先经过丙站的那趟车，结果发现100天中约有90天到达甲站，约有10天到达乙站。问开往甲乙两站的电车经过丙站的时刻表是如何安排的。(4)一男孩和一女孩分别在离家 2 km和 1 km且方向相反的两所学校上学，每天同时放学后分别以 4 km/h 和2 km/h 的速度步行回家。一小狗以 6 km/h 的速度由男孩处奔向女孩，又从女孩处奔向男孩，如此往返直至回到家中。问小狗奔波了多少路程？如果男孩和

36、女孩上学时小狗也往返在他们之间，问当他们到达学校时小狗在何处？,2.模仿商人过河问题中的状态转移模型，做下面这个众所周知的智力游戏：人带着狗、鸡、米过河，船除需要人划之外，至多能载狗、鸡、米三者之一，而当人不在场时狗要吃鸡、鸡要吃米。试设计一个安全渡河方案，并使渡河次数尽量地少。,第 2 题将人、狗、鸡、米依次用四维向量中的四个分量表示：当一物在此岸时，相应分量记为 1，否则记为 0。如向量(1,0,1,0)表示人和鸡在此岸，狗和米在彼岸。这些向量称为状态向量。凡系统可以允许存在的状态称为可取状态。对本系统，可取状态向量为：(1,1,1,1)(0,0,0,0)(1,1,1,0)(0,0,0,1

37、)(1,1,0,1)(0,0,1,0)(1,0,1,1)(0,1,0,0)(1,0,1,0)(0,1,0,1)共 10 个，右边 5 个正好是左边 5 个的相反状态。,将船的依次运算也用向量表示：当一物在船上时，相应分量记为 1，否则记为 0。如向量(1,1,0,0)表示人和狗在船上。这些向量称为运算向量或决策向量。本系统的运算向量为：(1,1,0,0)(1,0,1,0)(1,0,0,1)(1,0,0,0)一次过河就是一个状态向量和一个运算向量的加法。在加法运算中，对每一分量采用二进制。(0+0=0,1+0=0+1=1,1+1=0)由于问题的要求，可取状态经过加法运算后仍是可取状态，这样的运算

38、称为可取运算。,根据上述假设，人、狗、鸡、米过河问题转化为：从状态(1,1,1,1)经过奇数次运算变为状态(0,0,0,0)的系统转移过程。做法如下：(表示不可取状态),用这种方法的优点在于使用计算机能求出所有的转移过程，并比较出最优者。当所有的转移过程都出现循环时，则问题无解。可以看出，当状态向量维数增加，约束条件复杂时，用这种方法能方便求解。另外，人、狗、鸡、米问题还可以用图论的方法求解。将本系统的 10 个可取状态用 10 个点表示，当且仅当某个可取状态经过本系统的运算向量而仍为可取状态，就连一条线，从而构成一个图 G。,问题变为在图 G 中找一条从顶点(1,1,1,1)到(0,0,0,0)的路径，每条路径就是一个解。由图可知，有二解，它们是等优的。,O,x,y,A,B,C,D,f()表示A,B与地面距离之和,g()表示C,D与地面距离之和,则由三点着地，有,A,C,A,B,C,D,