本科毕业设计--全国数学建模竞赛常用建模方法探讨.doc

邯郸学院本科毕业论文题 目 全国大学生数学建模竞赛常用建模方法探讨 郑重声明本人的毕业论文（设计）是在指导教师 闫峰 的指导下独立撰写完成的。如有剽窃、抄袭、造假等违反学术道德、学术规范和侵权的行为，本人愿意承担由此产生的各种后果，直至法律责任，并愿意通过网络接受公众的监督。特此郑重声明。毕业论文（设计）作者（签名）： 年 月 日全国大学生数学建模竞赛常用建模方法探讨摘要请单击此处，然后输入中文摘要内容关键词：数学建模竞赛 初等方法 建模方法 微分方程 图论 线性规划Commonly used modeling method of the National Mathematical Contest in ModelingChai yunfei Directed by Professor YanfengABSTRACT在此处输入英文摘要内容KEY WORDS：mathematical contest elementary method modeling method differential equations graph theory linear programming23目 录全国大学生数学建模竞赛常用建模方法探讨I前言11 初等数学建模方法21.1 走路问题21.2 银行复利问题32 微分方程建模方法52.1 微分方程建模原理和方法52.2 人才分配问题模型73 差分和代数建模方法83.1 Malthus人口模型83.2 线性差分方程的解法94 数据差值与拟合方法104.1 拉格朗日插值法114.2 最小二乘法125 线性规划建模方法145.1 线性规划的一般理论145.2 合理下料问题166 图论建模方法176.1 图论的基本概念和简单的图论模型176.2 最短轨道问题186.3 求最小生成树186.4 模拟退火法原理196.5 应用举例19参考文献21附录22致谢23前言全国大学生数学建模竞赛创办于1992年，每年一届，目前已成为全国高校规模最大的基础性学科竞赛，也是世界上规模最大的数学建模竞赛。竞赛题目一般来源于工程技术和管理科学等方面经过适当简化加工的实际问题，不要求参赛者预先掌握深入的专门知识，只需要学过高等学校的数学课程。题目有较大的灵活性供参赛者发挥其创造能力。参赛者应根据题目要求，完成一篇包括模型的假设、建立和求解、计算方法的设计和计算机实现、结果的分析和检验、模型的改进等方面的论文。赛题一般涉及面宽-有社会，经济，管理，生活，环境，自然现象，工程技术，现代科学中出现的新问题等。一般都有一个比较确切的现实问题。本文将主要介绍一些常用的数学建模方法，包括初等数学建模方法、微分方程建模方法、差分和代数建模方法、数据差值与拟合方法、线性规划建模方法、图论建模方法等。1 初等数学建模方法在数学建模竞赛中，常会涉及到初等数学建模方法。对于一些机理简单的问题，常常应用静态、线性或逻辑的方法即可建立模型，使用初等数学方法或简单的微积分知识即可求解，此类模型称之为初等数学模型。初等数学建模方法很多，有比例关系、状态转移、量纲分析、类比建模等。本章主要列举了走路问题与银行复利问题，问题中涉及到了一些方法，通过这些知识方法的巧妙应用，可以开拓思路，提高分析解决实际问题的能力。1.1 走路问题人在匀速行走时，步行多大最省劲？把人行走时做的功看作是人体重心的势能和两脚运动的动能之和。试在此基础上，建立数学模型并对所得结果进行评价。设人体重M，腿重为,腿长为,步长为，速度为，单位时间内步数为n. 则由已知，人行走时所作的功是抬高人体重心所需势能与两腿运动所需动能之和。计算人体重心升高的势能将人的行走简化，设重心升高为h,则当较小时，取泰勒公式展开式前两项，得于是单位时间内重心升高所需势能为计算腿运动的动能如果将行走视为腿（均为直径）绕腰部的转动，则单位时间的动能为E=In其中I为转动惯量，I=l=l为角速度，=，ml.所以E=l=mv=于是单位时间行人行走所作的功为P= E+ E=+这是一个数学模型，问题转化为欲求：x为多大时，P最小。在中，求P的驻点，令=0，解得x=v。由nx=v,得n=若取M:m=4:1,代入且近似取l=1(米)，可得n5,即每秒5步，显然太快了，模型修改：是腿重集中在脚上，人行走所需动能为脚的直线运动的动能，则有=mvn=,其中 =+,同上解得 =3.这比较符合实际。1.2 银行复利问题一个人为了积累养老金，他每月按时到银行存100元，银行的年利率2，且可以任意分段按复利计算。试问此人5年后共积累了多少养老金？如果存款和复利按日计算，则他又有多少养老金？如果复利和存款连续计算呢？试建立数学模型并求解。按月存款和利息时，每月的利息为=记x为第k月末时的养老金数，则由题意得x=100x=100+100（1+）x=100+100（1+）+100（1+） x100+100（1+）+100（1+）五年末养老金为x=100=60000-1元6629.9元当复利和存款按日计算时，记y为第k天的养老金数，则每天的存款额为a=,每天的利率为r=.第k+1天的养老金数量与第k天的养老金数量的关系为y=+ y(1+r)= + y(1+)从第一天开始递推为y=ay=a+a(1+r)y= a+a(1+r) +a(1+r) y= a+a(1+r) +a(1+r)+ a(1+r)=a=-1在5年末时的养老金数为： （5年=5365=1825）y=-1=-16614.68元当存款和复利连续计算时，将1年分成m个相等的时间区间，则在每个时间区间中，存款为，每个区间的利息为,记第k个区间养老金的数目为z,类似与前面分析，5年后养老金为z=60000（元）=60000令m,即得连续存款和利息时，5年后的养老金为：Z=60000=60000(e-1)元6642.08元观察这三种不同情况下复利的计算问题，可以看出，将1年份为m等份，得出的计算公式具有一般性。当m分别取12和365时，就是前两种情况下的计算公式。另外，是m的单调函数，所以计算间隔越小，5年后的养老金数就越多，但不会超过连续存款和计息的极限值。由于存款和计息的间隔越小时，收益越大，且不需要一次到银行存较多的现金而是分批逐渐存入，对投资者的资金周转有利，所以在银行按复利计算时，建议存款者尽量采用小间隔的策略。2 微分方程建模方法在大多赛题中，要直接找出某些量之间的关系往往比较困难，但有时考虑其微小增量或变化率与这些变量之间的关系确是容易的，这种情形下我们常常采用微分关系式去描述其关系。2.1 微分方程建模原理和方法一般来说，任何事变问题中随时间变化发生变化的量与其它一些量之间的关系经常以微分方程的形式来表现。看这样一个问题：有一容器装有某种浓度的溶液，以流量v注入该容器浓度为c的同样溶液，假定溶液立即被搅拌均匀，并以v的流量流出混合后的溶液，试建立反映容器内浓度变化的数学模型。注意到 溶液浓度=因此，容器中溶液浓度会随溶质质量和溶液体积变化而发生变化。不妨设t时刻容器中溶质质量为s(t)，初始值为s,t时刻容器中溶液体积为V（t），初始值为V，则这段时间内有 （1）其中，c表示单位时间内注入溶液的浓度，c表示单位时间内流出溶液的浓度，当t很小时，在内 c= （2）对式（1）两端同除以，令0，则有 （3）此即问题的数学模型。它是针对液体溶液变化建立的，但它对气体和固体浓度变化同样适用。实际中，对面许多时变问题都可取微小的时间段去考察某些量之间的变化规律，从而建立问题的数学模型，这是数学建模中微分建模常用手段之一。通过对上述例子的了解，下面介绍几种常用微分方程建模方法。（1）按实验定律或规律建立的微分方程模型。刺激按摩充分依赖于各个学科领域中有关实验定律或规律以及某些重要的已知定理。此法建模要求建模者有宽广的知识视野才能对耨写具体问题采用某些熟知的实验定律。（2）分析微元变化规律建立微分方程模型。求解某些实际问题时，寻求一些微元之间的关系可以建立问题的数学模型。如上述问题中考察时间微元，从而建立的反应溶液浓度随时间变化的模型。此建模方法的出发点是考察某一变量的微小变化，即微元分析，找出其他一些变量与该微元间的关系式，从微分定义出发建立问题的数学模型。（3）近似模拟法。在许多实际问题中，有些现象的规律性并非一目了然，或有所了解亦是复杂的，这类问题常用近似模拟方法来建立问题的数学模型。一般通过一定的模型假设近似模拟实际现象，将问题做某些规范化处理后建立微分方程模型，然后分析，求解再与实际问题作比较，观察模型能否近似刻画实际现象。近似模拟法建模思路是建立能够近似刻画或反映实际现象的数学模型，因此在建模过程中经常做一些较合理的模型假设使问题简化，然后通过简化建立近似反映实际问题的数学模型2.2 人才分配问题模型每年大学毕业生中都要有一定比例的人员留在学校充实教师队伍, 其余人员将分配到国民经济其他部门从事经济和管理工作. 设t年教师人数为科学技术和管理人员数目为又设1外教员每年平均培养个毕业生, 每年人教育、科技和经济管理岗位退休、死亡或调出人员的比率为表示每年大学生毕业生中从事教师职业所占比率于是有方程 (1) (2)方程(1)有通解 (3)若设则于是得特解 (4)将(4)代入(2)方程变为 (5)求解方程(5)得通解 (6)若设则于是得特解 (7)(4)式和(7)式分别表示在初始人数分别为情况, 对应于的取值, 在t年教师队伍的人数和科技经济管理人员人数. 从结果看出, 如果取即毕业生全部留在教育界, 则当时, 由于必有而说明教师队伍将迅速增加. 而科技和经济管理队伍不断萎缩, 势必要影响经济发展, 反过来也会影响教育的发展. 如果将接近于零. 则同时也导致说明如果不保证适当比例的毕业生充实教师选择好比率, 将关系到两支队伍的建设, 以及整个国民经济建设的大局.3 差分和代数建模方法在一些问题中，许多数据都是以等间隔时间周期统计的。例如，银行中的定期存款是按设定的时间等间隔计息，外贸出口额按月统计，国民收入按年统计，产品的产量按月统计，等等。这些量是变量，通常这些变量为离散型变量。描述离散型变量之间的关系的数学模型为离散型模型。对取值是离散化的经济变量，差分方程是研究他们之间变化规律的有效方法。3.1 Malthus人口模型1798年英国人口学家和政治经济学家马尔萨斯以两个假设为前提：第一，食物为人类生存所必须；第二，人的性本能几乎无法限制，提出了闻名于世的人口指数增长模型，即Malthus人口模型：人口总数为,人口的出生率为b，死亡率为d。任取时段【,+】，在此时段中的出生人数为b，死亡人数为d。假设出生数及死亡数与及均成正比，而且以矩形取代了曲边梯形的面积。在时段【,+】中，人口增加量为-d，它应等于此时段中的出生人数与死亡人数之差，即d=bd=,其中=bd称为人口的净增长率。于是满足微分方程=. (1)若已知初始时刻=0时的人口总数为p0，那么还满足初始条件=0时，=p0. (2)可以求得微分方程(1)满足初始条件(2)的解为（设是常数）=p0e, (3)即人口总数按指数增长。模型参数的意义和作用：0为初始时刻（初始年度），p0为初始年度0的人口总数，为每年的人口净增长率，b为人口出生率，d为人口死亡率。Malthus人口模型所说的人口并不一定限于人，可以是认可一个生物群体，只要满足类似的性质即可。3.2 线性差分方程的解法方程 （ 1）其中为常数，称方程（1）为常系数线性方程。又称方程 （2）为方程（1）对应的齐次方程。如果（2）有形如的解，带入方程中可得： （3）称方程（3）为方程（1）、（2）的特征方程。显然，如果能求出（3）的根，则可以得到（2）的解。 基本结果如下： 若（3）有k个不同的实根，则（2）有通解： ， 若（3）有m重根，则通解中有构成项： 若（3）有一对单复根 ，令：，则（2）的通解中有构成项： 若有m 重复根：，则（2）的通项中有成项： 综上所述，由于方程（3）恰有k 个根，从而构成方程 （9）的通解中必有k个独立的任意常数。通解可记为： 如果能得到方程（1）的一个特解：，则（1）必有通解： + （11）（1） 的特解可通过待定系数法来确定。 例如：如果为n 的多项式，则当b不是特征根时，可设成形如形式的特解，其中为m次多项式；如果b是r重根时，可设特解：，将其代入（8）中确定出系数即可。4 数据差值与拟合方法在生产实践和科学研究中，常常有这样的问题：由实验或测量得到变量间的一批离散样点，要求由此建立变量之间的函数关系或得到样点之外的数据。与此有关的一类问题是当原始数据精度较高，要求确定一个初等函数（一般用多项式或分段多项式函数）通过已知各数据点（节点），即，或要求得函数在另外一些点（插值点）处的数值，这便是插值问题。4.1 拉格朗日插值法数据建模有两大方法：一类是插值方法，另一类是拟合函数一般的说，插值法比较适合数据准确或数据量小的情形。然而Lagrange插值有很多种，1阶，2阶,n阶。我们可以利用拉格朗日插值求方程，根据它的程序求原方程的图像。下面我具体介绍分析一下拉格朗日插值的算法设计及应用。已知函数y=f(x)在若干点的函数值=（i=0,1,n）一个差值问题就是求一“简单”的函数p(x)：p()=,i=0,1,n, (1)则p(x)为f(x)的插值函数，而f(x)为被插值函数会插值原函数，.,为插值节点，式（1）为插值条件，如果对固定点求f()数值解，我们称为一个插值节点，f()p()称为点的插值，当min(，.,)，max(，.,)时，称为内插，否则称为外插式外推，特别地，当p(x)为不超过n次多项式时称为n阶Lagrange插值。线性插值公式：设已知 ， 及=f() ,=f(),为不超过一次多项式且满足=,=,几何上，为过（，），（，）的直线，从而得到 =+（x-）. （2）为了推广到高阶问题，我们将式（2）变成对称式=（x）+(x).其中，（x）=,(x)=。均为1次多项式且满足（x）=1且(x)=0。或（x）=0且(x)=1。两关系式可统一写成= 。 （3）n阶Lagrange插值公式：设已知，.,及=f()(i=0,1,.,n),为不超过n次多项式且满足（i=0,1,.n）.易知=（x）+.+.其中，均为n次多项式且满足式（3）（i,j=0,1,.,n）,再由（ji）为n次多项式的n个根知=c.最后，由c=,i=0,1,.,n.总之，=，=式为n阶Lagrange插值公式，其中，（i=0,1,.n）称为n阶Lagrange插值的基函数。4.2 最小二乘法在两个观测量中，往往总有一个量精度比另一个高得多，为简单起见把精度较高的观测量看作没有误差，并把这个观测量选作x，而把所有的误差只认为是y的误差。设x和y的函数关系由理论公式yf（x；c1，c2，cm） （0-0-1）给出，其中c1，c2，cm是m个要通过实验确定的参数。对于每组观测数据（xi，yi）i1，2，N。都对应于xy平面上一个点。若不存在测量误差，则这些数据点都准确落在理论曲线上。只要选取m组测量值代入式（0-0-1），便得到方程组 yif（x；c1，c2，cm） （0-0-2） 式中i1，2，m.求m个方程的联立解即得m个参数的数值。显然Nm的情况下，式（0-0-2）成为矛盾方程组，不能直接用解方程的方法求得m个参数值，只能用曲线拟合的方法来处理。设测量中不存在着系统误差，或者说已经修正，则y的观测值yi围绕着期望值 摆动，其分布为正态分布，则yi的概率密度为,式中是分布的标准误差。为简便起见，下面用C代表（c1，c2，cm）。考虑各次测量是相互独立的，故观测值（y1，y2，cN）的似然函数.取似然函数L最大来估计参数C，应使 （0-0-3）取最小值：对于y的分布不限于正态分布来说，式（0-0-3）称为最小二乘法准则。若为正态分布的情况，则最大似然法与最小二乘法是一致的。因权重因子，故式（0-0-3）表明，用最小二乘法来估计参数，要求各测量值yi的偏差的加权平方和为最小。根据式（0-0-3）的要求，应有从而得到方程组 （0-0-4）解方程组（0-0-4），即得m个参数的估计值，从而得到拟合的曲线方程。然而，对拟合的结果还应给予合理的评价。若yi服从正态分布，可引入拟合的x2量， （0-0-5）把参数估计代入上式并比较式（0-0-3），便得到最小的x2值 （0-0-6）可以证明，服从自由度vN-m的x2分布，由此可对拟合结果作x2检验。由x2分布得知，随机变量的期望值为N-m。如果由式（0-0-6）计算出接近N-m（例如），则认为拟合结果是可接受的；如果，则认为拟合结果与观测值有显著的矛盾。5 线性规划建模方法线性规划建模方法主要用于解决生活、生产中的资源利用、人力调配、生产安排等问题，它是一种重要的数学模型。线性规划是运筹学中研究较早、发展较快、应用广泛、方法较成熟的一个重要分支，它是辅助人们进行科学管理的一种数学方法，研究线性约束条件下线性目标函数的极值问题的数学理论和方法。5.1 线性规划的一般理论一般的优化问题是指用“最好”的方式，使用或分配有限的资源即劳动力、原材料、机器、资金等，使得费用最小或利润最大。优化模型的一般形式为:min(或max) z=f（x） （1）st g（x）0.（i=1,2，m） （2） （x=（x，x，x）由（1）、（2）组成的模型属于约束优化。若只有（1）式就是无约束优化。f（x）称为目标函数，g（x）0称为约束条件。在优化模型中，如果目标函数f（x）和约束条件g（x）都是线性函数，则该模型称为线性规划。实际问题的线性规划模型的步骤：第一步：设置要求解的决策变量。决策变量选取得当，不仅能顺利地建立模型而且能方便地求解，否则很可能事倍功半。第二步：找出所有的限制，即约束条件，并用决策变量的线性方程或线性不等式来表示。当限制条件多，背景比较复杂时，可以采用图示或表格形式列出所有的已知数据和信息，从而避免“遗漏”或“重复”所造成的错误。第三步：明确目标要求，并用决策变量的线性函数来表示，标出对函数是取极大还是取极小的要求。决策变量的非负要求可以根据问题的实际意义加以确定。需要特别说明的是：要使用线性规划方法来处理一个实际问题，必须具备下面的条件：1.优化条件-问题的目标有极大化或极小化的要求,而且能用决策变量的线性函数来表示。2选择条件-有多种可供选择的可行方案，以便从中选取最优方案。3限制条件-达到目标的条件是有一定限制的（比如，资源的供应量有限度等），而且这些限制可以用决策变量的线性等式或线性不等式表示出来。此外，描述问题的决策变量相互之间应有一定的联系，有可能建立数学关系，即这些变量之间是内部相关的，这一点自然是不言而喻的。为了便于研究线性规划问题的理论与一般解法，人们需要将任意一个线性规划问题化为标准形式。n个变量的线性规划问题的标准形式为： Max (1) (2)0 (是的常数) （3）线性规划问题的标准形式：简记“LP”问题可通过以下手段将线性规划问题的一般形式转化为标准形式：1、目标函数转化 若问题的目标函数是求其极小值，即求： Min z=cx+cx+cx则可转化为求极大值问题，即求： max =-z=-( cx+cx+cx)2、约束条件转换 如果某一约束条件是线性不等式 或（），则通过引入松弛变量x0，将它转化为（或，其中的也称为剩余变量） 0反之，若有必要，也可等式约束等价的转化为两个不等式约束，即或3、变量的转换 若某个变量的约束条件为（或）则可令 （或），变为非负变量若某个变量无非负限制（称为自由变量），则可令代入原问题，将自由变量替换掉。5.2 合理下料问题假定有一批某种型号的圆钢长8厘米，需要截成2.5厘米的毛坯100根，长1.3厘米的毛坯200根，问应该怎样选择下料方式才能既满足需要又使总用料最少？根据经验，可将各种可能的方案列出来，解 设决策变量 （）表示第种方式所用的原材料根数，则问题的数学模型可归结为：求 （），使得 结果为：注：此问题结果不唯一，即可有多种方案，将结果应用到实际，由实际情况所限（根数为整数）也有多种选择，但最少用67根。考虑：还有没有其他标准？可以使切割后剩余的总余料最少。此时，相应的模型应为什么？这类问题的一般提法是：设某种原材料截取零件为的毛坯，由以往的经验，在一件原材料上可以有种不同的下料方式，每种下料方式可截得各种毛坯的个数以及每种零件的需要量已经给出。问应如何下料，才能既满足需要又使原材料消耗最少？另外，还有“合理配料问题”、“食谱问题”等也可归结为类似形式。6 图论建模方法图论作为离散数学的一个重要分支，在工程技术、自然科学和经济管理中的许多方面都能提供有力的数学模型来解决实际问题，所以吸引了很多研究人员去研究图论中的方法和算法。应该说，我们对图论中的经典例子或多或少还是有一些了解的，比如，哥尼斯堡七桥问题、中国邮递员问题、四色定理等等。图论方法已经成为数学模型中的重要方法。许多难题由于归结为图论问题被巧妙地解决。而且，从历年的数学建模竞赛看，出现图论模型的频率极大，比如：AMCM90B扫雪问题；AMCM91B寻找最优Steiner树；AMCM92B紧急修复系统的研制(最小生成树)AMCM94B计算机传输数据的最小时间(边染色问题)CMCM93B足球队排名(特征向量法)CMCM94B锁具装箱问题(最大独立顶点集、最小覆盖等用来证明最优性)CMCM98B灾情巡视路线(最优回路)等等。这里面都直接或是间接用到图论方面的知识。要说明的是，这里图论只是解决问题的一种方法，而不是唯一的方法。6.1 图论的基本概念和简单的图论模型首先给出图论中的一些基本概念。1一个图G由一个顶点集V和一个边的集E组成。E中每个元素e是连接顶点集 V中两个顶点u和v的边，称e与u，v关联。我们规定连接两个顶点u、v至多有一条边，且一条边的两个顶点不重合，这种图称为简单图。2顶点集为V，边集为E的图G通常记为G=（V，E）。图G1=（V1，E1）称为G的子图，如果 V1V， E1E。3顶点v的度(或“次”)是指与v相关联的边的个数。图G的度数之和为边数的两倍。4若图G中任意两个顶点u、v之间都存在连接它们的路，称G为连通图。5W=v0e1v1e2ekvk，其中eiE，vjV，ei与vi-1，vi关联，称W是图G的一条道路。v0是起点，vk是终点；各边相异的道路叫做行迹，各顶点相异的道路叫做轨道；起点和终点重合的道路为回路；起点和终点重合的轨道为圈；包含图中每条边的回路称为Euler回路；含Euler回路的图称为Euler图。6一个无圈的连通图称为树。树是最简单而最重要的一类图。树有下列重要性质：7如果图G=（V，E）的子图Gt=（Vt，Et）是一个树，且Vt=V，称G t是G的生成树。G连通的充要条件是G有生成树。生成树一般而言数量很大。8设对图G=（V，E）的每一条边e赋予一个实数W（e），称为e的权，G称为赋权图(加权图)。假设G是连通的赋权图，要找G的连通子图 G *=（V，E*），使得W（G*）=为最小。显然G*应为G的一个生成树。G的权最小的生成树称为 G的最小生成树。6.2 最短轨道问题背景：给定连接若干城市的铁路网，寻求从指定城市v0到各城v去的最短道路。数学模型：图G为一赋权图，对任给的vV(G)，寻求轨道P(v0,v)，使得W(P(v0,v)=minW(P),P取自所有v0到v的轨道集合其中W(P)是轨道P上各边权之和。这一问题可用迪克斯特拉(Dijkstra)算法解决。基本思想：从起点v0开始，逐步寻找到达各点的最短路，在每一步都对顶点记录一个数，称之为该点的标号，它表示v0到该点的最短距离的上界，或就是v0到该点的最短距离。实际上每一步都通过把至少一个具有T标号的点变成P标号(即把一个不是最短距离标号的顶点变成是最短距离标号的顶点)，这样最多经过|V(G)|-1步就可完成。步骤：记l(v)为v0到v的距离。(1) l(v0)=0，l(v) = ，(vv0)；S0=v0，i=0。(2) 对vSi，minl(v)，l(vi)+w(viv)代替l(v)；这样找到点vi1使得l(v)取最小值，v(i1)(Si的余集)。令S(i1)Siv(i+1)。(3) i=|V(G)|-1时停止，否则，i+1，转到(2)。实例：CMCM94A公路选址问题。6.3 求最小生成树背景：筑路选线问题 欲修筑连接n个城市的铁路，已知i城与j城之间的铁路造价为Cij。设计一个线路图，使总造价最低。分析：选线问题的数学模型是在连通加权图上求权最小的连通生成子图。显然，权最小的连通生成子图是一个生成树，即求取连通加权图上的权最小的生成树，这就归结为最小生成树问题。这个问题可由克罗斯克尔(Kruskal)算法解决。思路：从“边”着手选最小生成树。步骤：设G为由m个节点组成的连通赋权图。(1) 先把G中所有的边按权值大小由小到大重新排列，并取权最小的一条边为树T中的边。即选e1E，使得w(e1)min。(2) 从剩下的边中按(1)中的排列取下一条边。若该边与前面已取进T中的边构成一个回路，则舍弃该边，否则也把它取进T中。若e1，e2，ei已经选好，则从Ee1，e2，ei中选取ei1，使得Ge1，e2，ei，ei+1中无圈，且w(ei+1)=min。(3) 重复步骤(2)，直到T中有m1条边为止。则T为G的最小生成树。该算法的复杂度为O(eloge)，其中e是图G中的边数。6.4 模拟退火法原理模拟退火法(Simulated annealing, SA)是模拟热力学中经典粒子系统的降温过程，来求解极值问题。当孤立粒子系统的温度以足够慢的速度下降时，系统近似处于热力学平衡状态，最后系统将达到本身的最低能量状态，即基态，这相当于能量函数的全局极小点。其步骤如下(也称为Metropolis过程)：（1） 给定初始温度T0，及初始点，计算该点的函数值f(x)。（2） 随机产生扰动x，得到新点x=x+x，计算新点函数值f(x),及函数值差f=f(x)-f(x)。（3） 若f0，则接受新点，作为下一次模拟的初始点；（4） 若f0，则计算新点接受概率：，产生 0，1区间上均匀分布的伪随机数r,r0,1，如果p(f)r，则接受新点作为下一次模拟的初始点；否则放弃新点，仍取原来的点作为下一次模拟的初始点。6.5 应用举例1、CMCM91B(通讯网络中的极小生成树)是一个求STEINER生成树问题。2、CMCM 97A题97年全国大学生数模竞赛A题“零件的参数设计”，可以归结为非线性规划模型，由于目标函数很复杂，且又是一个多维函数，因此求解比较困难，为应用模拟退火法进行求解，将7个自变量的取值范围进行离散化，取步长为0.0001，这样，所有7个变量取值就组成了一个极为庞大的离散空间, 而这个问题变成组合优化模型。这个问题算法的状态调整规则是：每次从7个自变量中随机选取1-4个，让选取的自变量随机移动，考虑选取的自变量在两个方向移动组合，从中选取最佳的作为候选者，自变量移动的距离随着温度的降低而减少，为避免陷入局部极小，可以从多个随机选取的初始值开始计算，算法的其它步骤同上。3、CMCM 98B题98年全国大学生数学建模竞赛B题“水灾巡视问题”，是一个推销员问题，本题有53个点，所有可能性大约为exp(53),目前没有好方法求出精确解，既然求不出精确解，我们使用模拟退火法求出一个较优解，将所有结点编号为1到53，1到53的排列就是系统的结构，结构的变化规则是：从1到53的排列中随机选取一个子排列，将其反转或将其移至另一处，能量E自然是路径总长度。具体算法描述如下：步1： 设定初始温度T，给定一个初始的巡视路线。步2：步3 -8循环K次步3：步 4-7循环M次步4：随机选择路线的一段步5：随机确定将选定的路线反转或移动，即两种调整方式：反转、移动。步6：计算代价D，即调整前后的总路程的长度之差步7：按照如下规则确定是否做调整：如果D0，则按照EXP(-D/T)的概率进行调整步8：T*0.9-T，降温参考文献1 姜启源等编著.数学模型M.北京：高等教育出版社，20032 徐全智，杨晋浩编著.数学建模入门M.四川：成都电子科大出版社，19963 刘来福，曾文艺编著.问题解决的数学模型方法M.北京：北京师范大学出版社，19994 朱道元等编著.数学建模案例精选M.北京：科学出版社，20035 齐欢编著.数学模型方法M.武汉：华中理工大学出版社，19966 汪国强编著.数学建模优秀案例选编M.广州：华南理工大学出版社，19987 华罗庚，王元编著数学模型选谈M湖南：湖南教育出版社，19918 Saaty TL. The Analytic Hierarchy Process M.Mcgraw 2 Hill,19809 杨学桢.数学建模方法M.保定：河北大学出版社，200010王高雄，周之铭，朱思铭，王寿松.常微分方程M.北京：高等教育出版社，198311王兴宇，樊恺.数学模型方法M.武汉：华中理工大学出版社，1996 附录论文的附录依序编排为附录A，附录B。附录中的图、表、公式、参考文献另编排序号，与正文分开，一律用阿拉伯数字编码，但在编码前冠以附录序码，如：图A1；表B2；式(B3)；文献A5等。致谢四年的大学生活转眼就要说再见了，当自己终于可以从考研、找工作、毕业论文的压力下解脱出来，长长地吁出一口气时，我忽然间才意识到，原来四年已经过去，到了该告别的时候了。一念至此，竟有些恍惚，所谓白驹过隙、百代过客云云，想来便是这般惆怅了。 可是怅然之后，总要说些什么。大学四年，虽然读的是一所二流的大学，而且处在一个大学生泛滥的时代，我们的学历显得那么的微不足道，但是我依然踏踏实实的过完了这四年。从开始的新奇，到后来的迷茫，再到后来的坚定和努力。我无愧于这四年的大学生活，在即将给它画上句号的时候，我还是会带着微笑去回忆，这四年我成长了许多，从那么的稚嫩、懵懂变得成熟稳重。我会始终带着感恩去铭记这里，去铭记我的恩师们，你们辛苦了。 我在这里首先要感谢的是我的学位论文指导老师闫峰老师。这篇毕业论文从开题、资料查找、修改到最后定稿，如果没有她的心血，尚不知以何等糟糕的面目出现。我很自豪有这样一位老师，她值得我感激和尊敬。 感谢和我共度四年美好大学生活的2009级数学系本科班的全体同学。感谢数学系的所有授课老师，以及实习学校的指导老师，你们使我终身受益。感谢所有关心、鼓励、支持我的家人、亲戚和朋友。