全国大学生数学建模竞赛常用建模方法探讨毕业论文

邯郸学院本科毕业论文邯郸学院本科毕业论文题题 目目 全国大学生数学建模竞赛常用建模方法探讨学学 生生 柴云飞指导教师指导教师 闫峰 教授年年 级级 2009 级级专专 业业 数学与应用数学二级学院二级学院 数学系（系、部）（系、部）邯郸学院数学系学院（系、部）2013 年 5 月 郑重声明郑重声明本人的毕业论文（设计）是在指导教师 闫峰 的指导下独立撰写完成的。如有剽窃、抄袭、造假等违反学术道德、学术规范和侵权的行为，本人愿意承担由此产生的各种后果，直至法律责任，并愿意通过网络接受公众的监督。特此郑重声明。毕业论文（设计）作者（签名）： 年 月 日I全国大学生数学建模竞赛常用建模方法探讨全国大学生数学建模竞赛常用建模方法探讨摘要请单击此处，然后输入中文摘要内容关键词：关键词：数学建模竞赛 初等方法 建模方法 微分方程 图论 线性规划IICommonly 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 programming1目目 录录全国大学生数学建模竞赛常用建模方法探讨.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致谢.231前前言言全国大学生数学建模竞赛创办于 1992 年，每年一届，目前已成为全国高校规模最大的基础性学科竞赛，也是世界上规模最大的数学建模竞赛。竞赛题目一般来源于工程技术和管理科学等方面经过适当简化加工的实际问题，不要求参赛者预先掌握深入的专门知识，只需要学过高等学校的数学课程。题目有较大的灵活性供参赛者发挥其创造能力。参赛者应根据题目要求，完成一篇包括模型的假设、建立和求解、计算方法的设计和计算机实现、结果的分析和检验、模型的改进等方面的论文。赛题一般涉及面宽-有社会，经济，管理，生活，环境，自然现象，工程技术，现代科学中出现的新问题等。一般都有一个比较确切的现实问题。本文将主要介绍一些常用的数学建模方法，包括初等数学建模方法、微分方程建模方法、差分和代数建模方法、数据差值与拟合方法、线性规划建模方法、图论建模方法等。21 初等数学建模方法在数学建模竞赛中，常会涉及到初等数学建模方法。对于一些机理简单的问题，常常应用静态、线性或逻辑的方法即可建立模型，使用初等数学方法或简单的微积分知识即可求解，此类模型称之为初等数学模型。初等数学建模方法很多，有比例关系、状态转移、量纲分析、类比建模等。本章主要列举了走路问题与银行复利问题，问题中涉及到了一些方法，通过这些知识方法的巧妙应用，可以开拓思路，提高分析解决实际问题的能力。1.1 走路问题人在匀速行走时，步行多大最省劲？把人行走时做的功看作是人体重心的势能和两脚运动的动能之和。试在此基础上，建立数学模型并对所得结果进行评价。设人体重 M，腿重为,腿长为 ,步长为，速度为 ，单位时间内步数为 n. 则mlxvnxv 由已知，人行走时所作的功是抬高人体重心所需势能与两腿运动所需动能之和。计算人体重心升高的势能将人的行走简化，设重心升高为 h,则lllhcos2sin1ll 2241lx当较小时，取泰勒公式展开式前两项，得lx21 ( llh228lx)lx82于是单位时间内重心升高所需势能为E势nMgMghnlx82lMgxv8计算腿运动的动能如果将行走视为腿（均为直径）绕腰部的转动，则单位时间的动能为E=In动2123其中 I 为转动惯量，I=l =l102r dm102rdr3133m2为角速度，=，ml .所以lvE=l =mv =动2n3m222lv6n2xmv63于是单位时间行人行走所作的功为P= E+ E=+势动lMgxv8xmv63这是一个数学模型，问题转化为欲求：x 为多大时，P 最小。在中，求 P 的驻点，令=0，解得 x=v。由 nx=v,得dxdpMgml34n=Mgml34若取 M:m=4:1,代入且近似取 l=1(米)，可得 n5,即每秒 5 步，显然太快了，模型修改：是腿重集中在脚上，人行走所需动能为脚的直线运动的动能，则有=mv n=,E动能212xv2m3其中 =+,PlMgxv8xv2m3同上解得 =3.这比较符合实际。nMgml341.2 银行复利问题一个人为了积累养老金，他每月按时到银行存 100 元，银行的年利率 2，且可以任意分段按复利计算。试问此人 5 年后共积累了多少养老金？如果存款和复利按日计算，则他又有多少养老金？如果复利和存款连续计算呢？试建立数学模型并求解。按月存款和利息时，每月的利息为=12110026001记 x 为第 k 月末时的养老金数，则由题意得kx =10014x =100+100（1+）26001x =100+100（1+）+100（1+）3600160012 x 100+100（1+）+100（1+）n600160011n五年末养老金为x=100=60000-1元6629.9 元6060)60011 (1)60011 (160)60011 ( 当复利和存款按日计算时，记 y 为第 k 天的养老金数，则每天的存款额为 a=k,每天的利率为 r=.第 k+1 天的养老金数量与第 k 天的养老金数量的关系为3651200365002y=+ y (1+r)= + y (1+)1k3651200k3651200k365002从第一天开始递推为y =a1y =a+a(1+r)2y = a+a(1+r) +a(1+r)32 y = a+a(1+r) +a(1+r) + a(1+r)=a=-1n21nnrr)1 (1)1 (1ranr)1 ( 在 5 年末时的养老金数为： （5 年=5365=1825）y=-1=-16614.68 元1825ra1825)1 (r36512002365001825)3650021 ( 当存款和复利连续计算时，将 1 年分成 m 个相等的时间区间，则在每个时间区间中，存款为，每个区间的利息为,记第 k 个区间养老金的数目为 z ,类似与前m1200m1002k面分析，5 年后养老金为z=m5m1200mmm5)10021 (1)10021 (1m12001)10021 (21005mmm5=60000（元）=600001)10021 (5mm1)5011 (5mm令 m,即得连续存款和利息时，5 年后的养老金为：Z=60000=60000(e-1)元6642.08 元limm1)10021 (5mm101观察这三种不同情况下复利的计算问题，可以看出，将 1 年份为 m 等份，得出的计算公式具有一般性。当 m 分别取 12 和 365 时，就是前两种情况下的计算公式。另外，是 m 的单调函数，所以计算间隔越小，5 年后的养老金数就越多，但不会超过mm5)5011 ( 连续存款和计息的极限值。由于存款和计息的间隔越小时，收益越大，且不需要一次到银行存较多的现金而是分批逐渐存入，对投资者的资金周转有利，所以在银行按复利计算时，建议存款者尽量采用小间隔的策略。2 微分方程建模方法在大多赛题中，要直接找出某些量之间的关系往往比较困难，但有时考虑其微小增量或变化率与这些变量之间的关系确是容易的，这种情形下我们常常采用微分关系式去描述其关系。2.1 微分方程建模原理和方法一般来说，任何事变问题中随时间变化发生变化的量与其它一些量之间的关系经常以微分方程的形式来表现。看这样一个问题：有一容器装有某种浓度的溶液，以流量 v1注入该容器浓度为 c1的同样溶液，假定溶液立即被搅拌均匀，并以 v2的流量流出混合后的溶液，试建立反映容器内浓度变化的数学模型。注意到 溶液浓度=溶液体积溶质质量因此，容器中溶液浓度会随溶质质量和溶液体积变化而发生变化。不妨设 t 时刻容器中溶质质量为 s(t)，初始值为 s ,t 时刻容器中溶液体积为 V（t） ，初始值为 V ，则这段时006间内有 （1）ttt,tvtvVtvctvcs212211其中，c 表示单位时间内注入溶液的浓度，c 表示单位时间内流出溶液的浓度，当12t 很小时，在内ttt, c = （2）2)()(tVtstvvVts)()(210对式（1）两端同除以，令0，则有tt （3）00212211)0(,)0(VVssvvdtdVvcvcdtds此即问题的数学模型。它是针对液体溶液变化建立的，但它对气体和固体浓度变化同样适用。实际中，对面许多时变问题都可取微小的时间段t去考察某些量之间的变化规律，从而建立问题的数学模型，这是数学建模中微分建模常用手段之一。通过对上述例子的了解，下面介绍几种常用微分方程建模方法。（1）按实验定律或规律建立的微分方程模型。刺激按摩充分依赖于各个学科领域中有关实验定律或规律以及某些重要的已知定理。此法建模要求建模者有宽广的知识视野才能对耨写具体问题采用某些熟知的实验定律。（2）分析微元变化规律建立微分方程模型。求解某些实际问题时，寻求一些微元之间的关系可以建立问题的数学模型。如上述问题中考察时间微元t，从而建立的反应溶液浓度随时间变化的模型。此建模方法的出发点是考察某一变量的微小变化，即微元分析，找出其他一些变量与该微元间的关系式，从微分定义出发建立问题的数学模型。（3）近似模拟法。在许多实际问题中，有些现象的规律性并非一目了然，或有所了解亦是复杂的，这类问题常用近似模拟方法来建立问题的数学模型。一般通过一定的模型假设近似模拟实际现象，将问题做某些规范化处理后建立微分方程模型，然后分析，求解再与实际问题作比较， ，观察模型能否近似刻画实际现象。近似模拟法建模思路是建立能够近似刻画或反映实际现象的数学模型，因此在建模过程中经常做一些较合理的模型假设使问题简化，然后通过简化建立近似反映实际问题的数学模型72.2 人才分配问题模型每年大学毕业生中都要有一定比例的人员留在学校充实教师队伍, 其余人员将分配到国民经济其他部门从事经济和管理工作. 设 t 年教师人数为),(1tx科学技术和管理人员数目为),(2tx又设 1 外教员每年平均培养个毕业生, 每年人教育、科技和经济管理岗位退休、死亡或调出人员的比率为),10(表示每年大学生毕业生中从事教师职业所占比率),10(于是有方程111xxdtdx (1)212)1 (xxdtdx (2)方程(1)有通解teCx)(11 (3)若设,)0(101xx则,101xC 于是得特解texx)(101 (4)将(4)代入(2)方程变为texxdtdx)(1022)1 ( (5)求解方程(5)得通解ttexeCx)(1022)1 ( (6)若设,)0(202xx则,110202xxC 于是得特解ttexexxx)(101020211 (7)(4)式和(7)式分别表示在初始人数分别为)0(),0(21xx情况, 对应于的取值, 在 t 年教师队伍的人数和科技经济管理人员人数. 从结果看出, 如果取, 1即毕业生全部留在教8育界, 则当t时, 由于,必有)(1tx而, 0)(2tx说明教师队伍将迅速增加. 而科技和经济管理队伍不断萎缩, 势必要影响经济发展, 反过来也会影响教育的发展. 如果将接近于零. 则, 0)(1tx同时也导致, 0)(2tx说明如果不保证适当比例的毕业生充实教师选择好比率, 将关系到两支队伍的建设, 以及整个国民经济建设的大局.3 差分和代数建模方法在一些问题中，许多数据都是以等间隔时间周期统计的。例如，银行中的定期存款是按设定的时间等间隔计息，外贸出口额按月统计，国民收入按年统计，产品的产量按月统计，等等。这些量是变量，通常这些变量为离散型变量。描述离散型变量之间的关系的数学模型为离散型模型。对取值是离散化的经济变量，差分方程是研究他们之间变化规律的有效方法。3.1 Malthus 人口模型1798 年英国人口学家和政治经济学家马尔萨斯以两个假设为前提：第一，食物为人类生存所必须；第二，人的性本能几乎无法限制，提出了闻名于世的人口指数增长模型，即 Malthus 人口模型：人口总数为)(tp,人口的出生率为 b，死亡率为 d。任取时段【t,t+dt】 ，在此时段中的出生人数为 b)(tpdt，死亡人数为 d)(tpdt。假设出生数及死亡数与)(tp及dt均成正比，而且以矩形取代了曲边梯形的面积。在时段【t,t+dt】中，人口增加量为)(dttp-)(tpd)(tp，它应等于此时段中的出生人数与死亡人数之差，即d)(tp=b)(tpdtd)(tpdt=a)(tpdt,其中a=bd 称为人口的净增长率。于是)(tp满足微分方程dttdp )(=a)(tp. (1)若已知初始时刻t=t0 时的人口总数为 p0，那么)(tp还满足初始条件9t=t0 时，)(tp=p0. (2)可以求得微分方程(1)满足初始条件(2)的解为（设a是常数）)(tp=p0e)0(tta, (3)即人口总数按指数增长。模型参数的意义和作用：t0 为初始时刻（初始年度） ，p0 为初始年度t0 的人口总数，a为每年的人口净增长率，b 为人口出生率，d 为人口死亡率。Malthus 人口模型所说的人口并不一定限于人，可以是认可一个生物群体，只要满足类似的性质即可。3.2 线性差分方程的解法方程)(.110nbxaxaxankknkn （ 1）其中kaaa,.,10为常数，称方程（1）为常系数线性方程。又称方程0.110nkknknxaxaxa （2）为方程（1）对应的齐次方程。如果（2）有形如nnx的解，带入方程中可得： 0.1110kkkkaaaa （3）称方程（3）为方程（1） 、 （2）的特征方程。显然，如果能求出（3）的根，则可以得到（2）的解。 基本结果如下： 若（3）有 k 个不同的实根，则（2）有通解： nkknnncccx.2211， 若（3）有 m 重根，则通解中有构成项： nmmncncc).(121 若（3）有一对单复根 i，令：ie，arctan,22，则（2）的通解中有构成项： ncncnnsincos2110 若有 m 重复根：i，ie，则（2）的通项中有成项： nncnccnncnccnmmmmnmmsin).(cos).(1221121 综上所述，由于方程（3）恰有 k 个根，从而构成方程 （9）的通解中必有 k 个独立的任意常数。通解可记为：nx 如果能得到方程（1）的一个特解：*nx，则（1）必有通解： nxnx+*nx （11） （1） 的特解可通过待定系数法来确定。 例如：如果)(),()(npnpbnbmmn为 n 的多项式，则当 b 不是特征根时，可设成形如)(nqbmn形式的特解，其中)(nqm为 m 次多项式；如果 b 是 r 重根时，可设特解：rnnb)(nqm，将其代入（8）中确定出系数即可。4 数据差值与拟合方法在生产实践和科学研究中，常常有这样的问题：由实验或测量得到变量间的一批离散样点，要求由此建立变量之间的函数关系或得到样点之外的数据。与此有关的一类问题是当原始数据),( ,),(),(1100nnyxyxyx精度较高，要求确定一个初等函数)(xPy （一般用多项式或分段多项式函数）通过已知各数据点（节点） ，即nixPyii, 1 , 0, )(，或要求得函数在另外一些点（插值点）处的数值，这便是插值问题。4.1 拉格朗日插值法数据建模有两大方法：一类是插值方法，另一类是拟合函数一般的说，插值法比较适合数据准确或数据量小的情形。然而 Lagrange 插值有很多种，1 阶，2 阶,n 阶。我们可以利用拉格朗日插值求方程，根据它的程序求原方程的图像。下面我具体介绍分析一下拉格朗日插值的算法设计及应用。11已知函数 y=f(x)在若干点ix的函数值iy= ixf（i=0,1, ,n）一个差值问题就是求一“简单”的函数 p(x)：p(ix)=iy,i=0,1, ,n, (1)则 p(x)为 f(x)的插值函数，而 f(x)为被插值函数会插值原函数，0 x，1x，2x，.,nx为插值节点，式（1）为插值条件，如果对固定点x求 f(x)数值解，我们称x为一个插值节点，f(x)p(x)称为x点的插值，当xmin(0 x，1x，2x，.,nx)，max(0 x，1x，2x，.,nx)时，称为内插，否则称为外插式外推，特别地，当 p(x)为不超过 n 次多项式时称为 n阶 Lagrange 插值。线性插值公式) 1 (1L：设已知0 x ，1x 及0y=f(0 x) ,1y=f(1x),)(1xL为不超过一次多项式且满足)(01xL=0y,)(11xL=1y,几何上，)(1xL为过（0 x，0y） ， （1x，1y）的直线，从而得到 )(1xL=0y+0101xxyy（x-0 x）. （2）为了推广到高阶问题，我们将式（2）变成对称式)(1xL=0l（x）0y+1l(x)1y.其中，0l（x）=101xxxx,1l(x)=010 xxxx。均为 1 次多项式且满足0l（x）=1 且1l(x)=0。或0l（x）=0 且1l(x)=1。两关系式可统一写成)(iixl=jiji01 。 （3）n 阶 Lagrange 插值公式)(xLn：设已知0 x，1x，2x，.,nx及iy=f(ix)(i=0,1,.,n),)(xLn为不超过 n 次多项式且满足iinyxL)(（i=0,1,.n）.易知)(xLn=0l（x）0y+.+)(xlnny.其中，)(xli均为 n 次多项式且满足式（3） （i,j=0,1,.,n）,再由jx（ji）为 n 次多项12式)(xli的 n 个根知)(xli=cniijjxx0.最后，由1)()(0nijjjijixxcxlc=nijjjixx0)(1,i=0,1,.,n.总之，)(xLn=iniiyxl0)(，)(xli=.0nijjjijxxxx式为 n 阶 Lagrange 插值公式，其中，)(xli（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 的概率密度为 22212,.,;exp21imiiiicccxfyyp,式中i是分布的标准误差。为简便起见，下面用 C 代表（c1，c2，cm） 。考虑各次测量是相互独立的，故观测值（y1，y2，cN）的似然函数NiiiNNCxfyL12221;21exp.21.13取似然函数 L 最大来估计参数 C，应使 min;1122NiiiiCxfy （0-0-3）取最小值：对于 y 的分布不限于正态分布来说，式（0-0-3）称为最小二乘法准则。若为正态分布的情况，则最大似然法与最小二乘法是一致的。因权重因子2/1ii，故式（0-0-3）表明，用最小二乘法来估计参数，要求各测量值 yi 的偏差的加权平方和为最小。根据式（0-0-3）的要求，应有mkCxfycccNiiiik,.,2 , 10;1122从而得到方程组 mkCCxfCxfyccNikiii,.,2 , 10;112 （0-0-4）解方程组（0-0-4） ，即得 m 个参数的估计值mccc,.,21，从而得到拟合的曲线方程mcccxf,.,;21。然而，对拟合的结果还应给予合理的评价。若 yi 服从正态分布，可引入拟合的 x2 量， NiiiiCxfyx1222;1 （0-0-5）把参数估计mcccc,.,21代入上式并比较式（0-0-3） ，便得到最小的 x2 值 Niiiicxfyx1222min;1 （0-0-6）可以证明，2minx服从自由度 vN-m 的 x2 分布，由此可对拟合结果作 x2 检验。由 x2 分布得知，随机变量2minx的期望值为 N-m。如果由式（0-0-6）计算出2minx接近N-m（例如mNx2min） ，则认为拟合结果是可接受的；如果22minmNx，则认为拟合结果与观测值有显著的矛盾。145 线性规划建模方法线性规划建模方法主要用于解决生活、生产中的资源利用、人力调配、生产安排等问题，它是一种重要的数学模型。线性规划是运筹学中研究较早、发展较快、应用广泛、方法较成熟的一个重要分支，它是辅助人们进行科学管理的一种数学方法，研究线性约束条件下线性目标函数的极值问题的数学理论和方法。5.1 线性规划的一般理论一般的优化问题是指用“最好”的方式，使用或分配有限的资源即劳动力、原材料、机器、资金等，使得费用最小或利润最大。优化模型的一般形式为:min(或 max) z=f（x） （1）st g（x）0.（i=1,2，m） （2） （x=（x1，x2，xn）T）由（1） 、 （2）组成的模型属于约束优化。若只有（1）式就是无约束优化。f（x）称为目标函数，gi（x）0 称为约束条件。在优化模型中，如果目标函数 f（x）和约束条件 gi（x）都是线性函数，则该模型称为线性规划。实际问题的线性规划模型的步骤：第一步：设置要求解的决策变量。决策变量选取得当，不仅能顺利地建立模型而且能方便地求解，否则很可能事倍功半。第二步：找出所有的限制，即约束条件，并用决策变量的线性方程或线性不等式来表示。当限制条件多，背景比较复杂时，可以采用图示或表格形式列出所有的已知数据和信息，从而避免“遗漏”或“重复”所造成的错误。第三步：明确目标要求，并用决策变量的线性函数来表示，标出对函数是取极大还是取极小的要求。决策变量的非负要求可以根据问题的实际意义加以确定。需要特别说明的是：要使用线性规划方法来处理一个实际问题，必须具备下面的条件：1.优化条件-问题的目标有极大化或极小化的要求,而且能用决策变量的线性函数来15表示。2 选择条件-有多种可供选择的可行方案，以便从中选取最优方案。3 限制条件-达到目标的条件是有一定限制的（比如，资源的供应量有限度等） ，而且这些限制可以用决策变量的线性等式或线性不等式表示出来。此外，描述问题的决策变量相互之间应有一定的联系，有可能建立数学关系，即这些变量之间是内部相关的，这一点自然是不言而喻的。为了便于研究线性规划问题的理论与一般解法，人们需要将任意一个线性规划问题化为标准形式。n 个变量的线性规划问题的标准形式为： Max snjjjxc1 (1). .ts njijijbxa1 mi, 3 , 2 , 1 (2)jx0 (ib是0的常数) （3）线性规划问题的标准形式：简记“LP”问题可通过以下手段将线性规划问题的一般形式转化为标准形式：1、目标函数转化 若问题的目标函数是求其极小值，即求： Min z=c1x1+c2x2+cnxn则可转化为求极大值问题，即求： max z=-z=-( c1x1+c2x2+cnxn)2、约束条件转换 如果某一约束条件是线性不等式 njijijbxa1或（njijijbxa1） ，则通过引入松弛变量 x1i0，将它转化为njiinjijbxxa1（或njiinjijbxxa1，其中的x1i也称为剩余变量） x1i0反之，若有必要，也可等式约束njijijbxa1等价的转化为两个不等式约束，即njijijbxa1或njijijbxa13、变量的转换 若某个变量的约束条件为xi1l（或xi1l）则可令16 jyjxjl（或jyjjxl ） ，jy变为非负变量若某个变量ix无非负限制（称为自由变量） ，则可令0,jjjjjxxxxx代入原问题，将自由变量替换掉。5.2 合理下料问题假定有一批某种型号的圆钢长 8 厘米，需要截成 2.5 厘米的毛坯 100 根，长 1.3 厘米的毛坯 200 根，问应该怎样选择下料方式才能既满足需要又使总用料最少？根据经验，可将各种可能的方案列出来，解 设决策变量jx （4 , 3 , 2 , 1j）表示第j种方式所用的原材料根数，则问题的数学模型可归结为：求jx （4 , 3 , 2 , 1j） ，使得 min 4321xxxxz ).4 , 3 , 2 , 1(020064210023. .432321jxxxxxxxtsj结果为：. 0,3100,3100, 0,32004321xxxxz注：此问题结果不唯一，即可有多种方案，将结果应用到实际，由实际情况所限（根数为整数）也有多种选择，但最少用 67 根。考虑：还有没有其他标准？可以使切割后剩余的总余料最少。此时，相应的模型应为什么？这类问题的一般提法是：设某种原材料截取零件为nAAA,21的毛坯，由以往的经验，在一件原材料上可以有nBBB,21种不同的下料方式，每种下料方式可截得各种毛坯的个数以及每种零件的需要量已经给出。问应如何下料，才能既满足需要又使原材料消耗最少？另外，还有“合理配料问题” 、 “食谱问题”等也可归结为类似形式。176 图论建模方法图论作为离散数学的一个重要分支，在工程技术、自然科学和经济管理中的许多方面都能提供有力的数学模型来解决实际问题，所以吸引了很多研究人员去研究图论中的方法和算法。应该说，我们对图论中的经典例子或多或少还是有一些了解的，比如，哥尼斯堡七桥问题、中国邮递员问题、四色定理等等。图论方法已经成为数学模型中的重要方法。许多难题由于归结为图论问题被巧妙地解决。而且，从历年的数学建模竞赛看，出现图论模型的频率极大，比如：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 图。186一个无圈的连通图称为树。树是最简单而最重要的一类图。树有下列重要性质：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*）=EeeW)(为最小。显然 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)算法解决。思路：从“边”着手选最小生成树。19步骤：设 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 个，让选取的自变量随机移动，考虑选取的自变量在两个方向移动组合，从中选取最佳的作为候选者，20自变量移动的距离随着温度的降低而减少，为避免陷入局部极小，可以从多个随机选取的初始值开始计算，算法的其它步骤同上。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，降温21参考文献参考文献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 22附附录录论文的附录依序编排为附录 A，附录 B。附录中的图、表、公式、参考文献另编排序号，与正文分开，一律用阿拉伯数字编码，但在编码前冠以附录序码，如：图 A1；表B2；式(B3)；文献A5等。23致致谢谢四年的大学生活转眼就要说再见了，当自己终于可以从考研、找工作、毕业论文的压力下解脱出来，长长地吁出一口气时，我忽然间才意识到，原来四年已经过去，到了该告别的时候了。一念至此，竟有些恍惚，所谓白驹过隙、百代过客云云，想来便是这般惆怅了。 可是怅然之后，总要说些什么。大学四年，虽然读的是一所二流的大学，而且处在一个大学生泛滥的时代，我们的学历显得那么的微不足道，但是我依然踏踏实实的过完了这四年。从开始的新奇，到后来的迷茫，再到后来的坚定和努力。我无愧于这四年的大学生活，在即将给它画上句号的时候，我还是会带着微笑去回忆，这四年我成长了许多，从那么的稚嫩、懵懂变得成熟稳重。我会始终带着感恩去铭记这里，去铭记我的恩师们，你们辛苦了。 我在这里首先要感谢的是我的学位论文指导老师闫峰老师。这篇毕业论文从开题、资料查找、修改到最后定稿，如果没有她的心血，尚不知以何等糟糕的面目出现。我很自豪有这样一位老师，她值得我感激和尊敬。 感谢和我共度四年美好大学生活的 2009 级数学系本科班的全体同学。感谢数学系的所有授课老师，以及实习学校的指导老师，你们使我终身受益。感谢所有关心、鼓励、支持我的家人、亲戚和朋友。