简单的数学建模PPT参考幻灯片.ppt

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,数学建模,1,数学模型,（,Mathematical Model,）,是用数学符号、数学式子、程序、图形等对实际课题 本质属性的抽象而又简洁的刻划，它或 能解释某些客观现象，或能预测未来的发展规律，或能为控制某一现象的发展提供某种意义下的最优策略或较好策略。,数学建模,（,Mathematical Modeling,）,应用知识从实际课题中抽象、提炼出数学模型的过程。,1.1,数学模型与数学建模,2,1.,了解问题的实际背景，明确建模目的，收集掌握必要的数据资料。,2.,在明确建模目的，掌握必要资料的基础上，通过对资料的分析计算，找出起主要作用的因素，经必要的精炼、简化，提出若干符合客观实际的假设。,3.,在所作假设的基础上，利用适当的数学工具去刻划各变量之间的关系，建立相应的数学结构,即建立数学模型。,4.,模型求解。,5.,模型的分析与检验。,在难以得出解析解时，也应当借助,计算机,求出数值解。,1.2,数学建模的一般步骤,实体信息,(,数据,),假设,建模,求解,验证,应用,3,1.3,数学模型的分类,分类标准,具体类别,对某个实际问题了解的深入程度,白箱模型、灰箱模型、黑箱模型,模型中变量的特征,连续型模型、离散型模型或确定性模型、随机型模型等,建模中所用的数学方法,初等模型、微分方程模型、差分方程模型、优化模型等,研究课题的实际范畴,人口模型、生 态系统模型、交通,流模型、经 济模型、基因模型等,4,例,1,某人平时下班总是按预定时间到达某处，然,然后他妻子开车接他回家。有一天，他比平时提早,了三十分钟到达该处，于是此人就沿着妻子来接他,的方向步行回去并在途中遇到了妻子，这一天，他,比平时提前了十分钟到家，问此人共步行了多长时,间？,1.4,一些简单实例,似乎条件不够哦。,换一种想法，问题就迎刃而解了。假如他的妻子遇到他后仍载着他开往会合地点，那么这一天他就不会提前回家了。提前的十分钟时间从何而来？,显然是由于节省了从相遇点到会合点，又从会合点返回相遇点这一段路的缘故，故由相遇点到会合点需开,5,分钟。而此人提前了三十分钟到达会合点，故相遇时他已步行了二十五分钟。,请思考一下，本题解答中隐含了哪些假设,？,5,例,2,交通灯在绿灯转换成红灯时，有一个过渡状态,亮一段时间的黄灯。请分析黄灯应当亮多久。,设想一下黄灯的作用是什么，不难看出，黄灯起的是警告的作用，意思是马上要转红灯了，假如你能停住，请立即停车。停车是需要时间的，在这段时间内，车辆仍将向前行驶一段距离,L,。这就是说，在离街口距离为,L,处存在着一条停车线（尽管它没被画在地上），见图。对于那些黄灯亮时已过线的车辆，则应当保证它们仍能穿过马路。,马路的宽度,D,是容易测得 的，问题的关键在 于,L,的确定。为确定,L,，还应当将,L,划分为两段：,L1,和,L2,，,其中,L1,是司机在发现黄灯亮及判断应当刹车的反应时间内驶过的路程 ，,L2,为刹车制动后车辆驶过的路程。,L1,较容易计算，交通部门对司机的平均反应时间,t1,早有测算，反应时间过长将考不出驾照），而此街道的行驶速度,v,也是交管部门早已定好的，目的是使交通流量最大，可另建模型研究，从而,L1=v*t1,。刹车距离,L2,既可用曲线拟合方法得出，也可利用牛顿第二定律计算出来。,黄灯究竟应当亮多久现在已经变得清楚多了。第一步，先计算出,L,应多大才能使看见黄灯的司机停得住车。第二步，黄灯亮的时间应当让已过线的车顺利穿过马路，即,T,至少应当达到,（,L+D,）,/v,。,D,L,6,2.,初等模型举例,7,常见类型,定性模型,经验公式（拟合、插值）,量纲分析,比例模型,8,2.1,崖高的估算,假如你站在崖顶且身上带着一只具有跑表功,能的计算器，你也许会出于好奇心想用扔下,一块石头听回声的方法来估计山崖的高度，,假定你能准确地测定时间，你又怎样来推算,山崖的高度呢，请你分析一下这一问题。,我有一只具有跑 表功能的计算器。,9,方法一,假定空气阻力不计，可以直接利用自由落体运动的公式,来计算。例如，设,t,=4,秒，,g,=9.81,米,/,秒,2,，则可求得,h,78.5,米。,我学过微积分，我可以做,得更好，呵呵。,10,除去地球吸引力外，对石块下落影响最大的当 属,空气阻力,。根据流体力学知识，此时可设空气阻力正比于石块下落的速度，阻力系 数,K,为常数，因而，由牛顿第二定律可得：,令,k,=,K,/,m,，,解得,代入初始条件,v,(0)=0,，得,c,=,g/k,，故有,再积分一次，得：,11,若设,k,=0.05,并仍设,t,=4,秒，则可求 得,h,73.6,米。,听到回声再按跑表，计算得到的时间中包含了,反应时间,进一步深入考虑,不妨设,平均反应时间,为,0.1,秒，假如仍 设,t,=4,秒，扣除反应时间后应 为,3.9,秒，代入 式,，求得,h,69.9,米。,多测几次，取平均值,再一步深入考虑,代入初始条 件,h,(,0,)=,0,，得到计算山崖高度的公式：,将,e,-kt,用泰勒公式展开并 令,k,0+,，即可得出前面不考虑空气阻力时的结果。,12,还应考虑,回声,传回来所需要的时间。为此，令石块下落 的真正时间 为,t,1,，声音传回来的时间记 为,t,2,，还得解一个方程组：,这一方程组是,非线性,的，求解不太容易，为了估算崖高竟要去解一个非线性主程组似乎不合情理,相对于石块速度，声音速度要快得多，我们可 用方法二先求一次,h,，令,t,2,=h,/,340,，校正,t,，求石块下落时间,t,1,t-t,2,将,t,1,代入式,再算一次，得出崖高的近似值。例如，若,h=,69.9,米，则,t,2,0.21,秒，故,t,1,3.69,秒，求得,h,62.3,米。,13,2.2,录像带还能录多长时间,录像机上有一个四位计数器，一盘,180,分钟,的录像带在开始计数时为,0000,，到结束时计,数为,1849,，实际走时为,185,分,20,秒。我们从,0084,观察到,0147,共用时间,3,分,21,秒。若录像,机目前的计数为,1428,，问是否还能录下一个,60,分钟的节目？,14,r,R,l,由,得到,又 因和 得,积分得到,即,从而有,我们希望建立一个录像带已录像时 间,t,与计数器计 数,n,之间的函数关系。为建立一个正确的模型，首 先必须搞清哪些量是常量，哪些量是变量。首先，录像 带的厚 度,W,是常量，它被绕在一个半径 为,r,的园盘上，见图。磁带转动中线速 度,v,显然也是常数，否则图象声音必然会失真。此外，计数器的读 数,n,与转过的圈数有关，从而与转过的角 度,成正比。,15,r,R,l,此式中的三个参数,W,、,v,和,r,均不易精确测得，虽然我们可以从上式解出,t,与,n,的函数关系，但效果不佳，故令,则可将上式简化为：,故,令,上式又可化简记成,t=an,2,+bn,16,t=an,2,+bn,r,R,l,上式以,a,、,b,为参数显然是一个十分明智的做法，它为公式的最终确立即参数求解提供了方便。将已知条件代入，得方程组：,从后两式中消 去,t,1,，解得,a=,0.0000291,b=,0.04646,故,t=,0.0000291,n,2,+0.04646,n,，令,n=,1428,，得到,t=,125.69,（分）由于一盒录像带实际可录像时间为,185.33,分，故尚可录像时间 为,59.64,分，已不能再录下一个,60,分钟的节目了。,17,在解决实际问题时，注意观察和善于想象是十分重要的，观察与想象不仅能发现问题隐含的某些属性，有时还能顺理成章地找到解决实际问题的钥匙。本节的几个例子说明，猜测也是一种想象力。没有合理而又大胆的猜测，很难做出具有创新性的结果。开普勒的三大定律（尤其是后两条）并非一眼就能看出的，它们隐含在行星运动的轨迹之中，隐含在第谷记录下来的一大堆数据之中。历史上这样的例子实在太多了。在获得了一定数量的资料数据后，人们常常会先去猜测某些结果，然后试图去证明它。猜测一经证明就成了定理，而定理一旦插上想象的翅膀，又常常会被推广出许多更为广泛的结果。即使猜测被证明是错误的，结果也决不是一无所获的失败而常常是对问题的更为深入的了解。,2.3,最短路径与最速方案问题,18,例,5,（最短路径问题）,设有一个半径为,r,的圆形湖，圆心为,O,。,A,、,B,位于湖的两侧，,AB,连线过,O,，见图。,现拟从,A,点步行到,B,点，在不得进入湖中的限,制下，问怎样的路径最近。,A,B,O,r,将湖想象成凸出地面的木桩，在,AB,间拉一根软线，当线被拉紧时将得到最短路径。根据这样的想象，猜测 可以如下得到最短路径：过,A,作圆的切线切圆于,E,，过,B,作圆的切线切圆 于,F,。最短路径为由线 段,AE,、弧,EF,和线段,FB,连接而成的连续曲线（根据对称性，,AE,，,弧,EF,，,FB,连接而成的连续曲线也是）。,E,F,E,F,19,以上只是一种猜测，现在来证明这一猜测是正确的。为此，先介绍一下凸集与凸集的性质。,定义,2.1,（,凸集,）称集合,R,为凸集，若,x,1,、,x,2,R,及,0,，,1,，,总有,x,1,+,（,1,+,）,x,2,R,。即若,x,1,、,x,2,R,，则,x,1,、,x,2,的连线必整个地落 在,R,中。,定理,2.2,（,分离定理,）对平面中的凸 集,R,与,R,外的一点,K,，存在直线,l,l,分离,R,与,K,，即,R,与,K,分别位于,l,的两侧（注：对一般的凸 集,R,与,R,外的一点,K,，则存在超平面分 离,R,与,K,），见图。,k,l,R,下面证明猜想,20,猜测证明如下：,（方法一）,显然，由,AE,、,EF,、,FB,及,AE,，,EF,，,FB,围成的区域,R,是一凸集。利用,分离定理,易证最短径不可能经过,R,外的点，若不然，设,为最短路径，,过,R,外的一点,M,，则必存在直 线,l,分离,M,与,R,，由于路径,是连续曲线，由,A,沿,到,M,，必交,l,于,M,1,，由,M,沿,到,B,又必交,l,于,M,2,。这样，直线 段,M,1,M,2,的长度必小于路 径,M,1,MM,2,的长度，与,是,A,到,B,的最短路径矛盾，至此，我们已证明最短路径必在凸集,R,内。不妨设路径经湖的上方到达,B,点，则弧,EF,必在路径,F,上，又直线段,AE,是由,A,至,E,的最短路径，直线,FB,是由,F,到,B,的最短路径，猜测得证。,A,B,O,r,E,F,E,F,M,1,M,2,M,l,21,还可用,微积分,方法求弧长，根据计算证明满足限止条件的其他连续曲线必具有更大的长度；此外，本猜测也可用,平面几何,知识加以证明等。,根据猜测不难看出，,例,5,中的条件可以大大放松，可以不必 设,AB,过圆心，甚至可不必设湖是圆形的。例如对 下图，我们可断定由,A,至,B,的最短路径必 为,l,1,与,l,2,之一，其证明也不难类似给出。,A,B,l,1,l,2,D,到此为止，我们的研讨还只局限于平面之中，其实上述猜测可十分自然地推广到一般空间中去。,1973,年，,J.W.Craggs,证明了以上结果：,若可行区域的边界是光滑曲面。则最短路径必由下列弧组成，它们或者是空间中的自然最短曲线，或者是可行区域的边界弧。而且，组成最短路径的各段弧在连接点处必定相切。,22,例,6,一辆汽车停于,A,处并垂直于,AB,方向，此,汽车可转的最小圆半径为,R,，求不倒车而由,A,到,B,的最短路径。,解,（情况,1,）,若,|AB|,2,R,，最短路径由 弧,AC,与切线,BC,组成（见,图,）。,（情况,2,）,若,|AB|,0,为推力，,fS,，故由连续函数的性质存在 某,TT,，,S,（,T,）,=S,但这一结果与,=(t),是最优方案下的车速的假设矛盾，因为用我们猜测的推车方法推车，只 需,T,时间即可将车推到修车处，而,TT,。,o,t,A,T,T,A,S,y=at,y=-b(t-T),26,3.,微分方程建模,27,常用技巧,工程师原则,房室系统建模,竞争项的统计筹算律,集中参数法与分布参数法,灵敏度分析,稳定性分析,28,3.1,为什么要用三级火箭来发射人造卫星,构造数学模型，以说明为什么不能用一级火箭而必须用多级火箭来发射人造卫星？为什么一般都采用三级火箭系统？,1,、为什么不能用一级火箭发射人造卫星,?,（,1,）卫星能在轨道上运动的最低速度,假设：,（,i,）卫星轨道为过地球中心的某一平面上的圆，卫星,在此轨道上作匀速圆周运动。,（,ii,）地球是固定于空间中的均匀球体，其它星球对卫,星的引力忽略不计。,分析：,根据牛顿第三定律，地球对卫星的引力为,:,在地面有,:,得,:,k,=,gR,2,R,为地球半径，约为,6400,公里,故引力,:,假设,(ii),29,dm,m-dm,v,u-v,假设,(i),卫星所受到的引力也就是它作匀速圆周运动的向心力,故又有,:,从而,:,设,g=9.81,米,/,秒,2,，得,:,卫星离地面高度,(,公里,),卫星速度,(,公里,/,秒,),100,200,400,600,800,1000,7.80,7.69,7.58,7.47,7.37,7.86,（,2,）火箭推进力及速度的分析,假设：,火箭重力及空气阻力均不计,分析：,记火箭在时刻,t,的质量和速度分别为,m,(,t,),和,(,t,),有：,记火箭喷出的气体相对于火箭的速度为,u,（常数），,由动量守恒定理：,0,和,m,0,一定的情况下，火箭速度,(t),由喷发速度,u,及质量比决定。,故：,由此解得：,(,3.11,),30,（,2,）火箭推进力及速度的分析,现将火箭,卫星系统的质量分成三部分：,（,i,）,m,P,（有效负载，如卫星）,（,ii,）,m,F,（燃料质量）,（,iii,）,m,S,（结构质量,如外壳、燃料容器及推进器）。,最终质量为,m,P,+,m,S,，初始速度为,0,，,所以末速度：,根据目前的技术条件和燃料性能，,u,只能达到,3,公里,/,秒，即使发射空壳火箭，其末速度也不超过,6.6,公里,/,秒。目前根本不可能用一级火箭发射人造卫星,火箭推进力在加速整个火箭时，其实际效益越来越低。如果将结构质量在燃料燃烧过程中,不断减少，那么末速度能达到要求吗？,31,2,、理想火箭模型,假设：,记结构质量,m,S,在,m,S,+,m,F,中占的比例为,，假设火箭能随时抛弃无用的结构，结构质量与燃料质量以,与（,1-,）的比例同时减少。,建模,:,由,得到：,解得：,理想火箭与一级火箭最大的区别在于，当火箭燃料耗尽时，结构质量也逐渐抛尽，它的最终质量为,m,P,，,所以最终速度为：,只要,m,0,足够大，我们可以使卫星达到我们希望它具有的任意速度。,考虑到空气阻力和重力等因素，估计（按比例的粗略估计）发射卫星要使,=10.5,公里,/,秒才行，则可推算出,m,0,/,m,p,约为,51,即发射一吨重的卫星大约需要,50,吨重的理想火箭,32,3,、理想过程的实际逼近,多级火箭卫星系统,记火箭级数为,n,，当第,i,级火箭的燃料烧尽时，第,i,+1,级火箭立即自动点火，并抛弃已经无用的第,i,级火箭。用,m,i,表示第,i,级火箭的质量，,m,P,表示有效负载。,先作如下假设：,（,i,）设各级火箭具有相同的,即,i,级火箭中,m,i,为结构质量，（,1-,）,m,i,为燃料质量。,（,ii,）,设燃烧级初始质量与其负载质量之比保持不变，并记比值为,k,。,考虑二级火箭：,由,3.11,式，当第一级火箭燃烧完时，其末速度为：,当第二级火箭燃尽时，末速度为：,该假设有点强加的味道，先权作讨论的方便吧,33,又由假设（,ii,），,m,2,=,km,P,，,m,1,=,k,(,m,2,+,m,P,),，代入上式，仍设,u,=3,公里,/,秒，且为了计算方便，近似取,=0.1,，则可得：,要使,2,=10.5,公里,/,秒，则应使,:,即,k,11.2,，而,:,类似地，可以推算出三级火箭：,在同样假设下,:,要使,3,=10.5,公里,/,秒，则,(,k,+1)/(0.1,k,+1)3.21,，,k3.25,，而,（,m,1,+,m,2,+,m,3,+,m,P,）,/,m,P,77,。,三级火箭比二级火箭几乎节省了一半,是否三级火箭就是最省呢？最简单的方法就是对四级、五级等火箭进行讨论。,34,考虑,N,级火箭：,记,n,级火箭的总质量（包含有效负载,m,P,）为,m,0,，在相同的假设下可以计算出相应的,m,0,/,m,P,的值，见表,3,-,2,n,（级数）,1 2 3 4 5 ,（理想）,火箭质量（吨）,/149 77 65 60 50,表,3,-,2,由于工艺的复杂性及每节火箭都需配备一个推进器，所以使用四级或四级以上火箭是不合算的，三级火箭提供了一个最好的方案。,当然若燃料的价钱很便宜而推进器的价钱很贵切且制作工艺非常复杂的话，也可选择二级火箭。,35,4,、火箭结构的优化设计,3,中已经能说过假设,(ii),有点强加的味道；现去掉该假设，在各级火箭具有相同,的粗糙假设下，来讨论火箭结构的最优设计。,W,1,=m,1,+m,n,+m,P,W,2,=m,2,+m,n,+m,P,W,n,=m,n,+m,P,W,n+1,=m,P,记,应用（,3.11,）可求得末速度：,记,则,又,问题化为，在,n,一定的条件下，求使,k,1,k,2,k,n,最小,解条件极值问题：,或等价地求解无约束极值问题：,可以解出最优结构设计应满足：,火箭结构优化设计讨论中我们得到与假设（,ii,）相符的结果，这说明前面的讨论都是有效的！,36,3.2,药物在体内的分布,何为房室系统？,在用微分方程研究实际问题时，人们常常采用一种叫,“,房室系统,”,的观点来考察问题。根据研究对象的特征或研究的不同精度要求，我们把研究对象看成一个整体（单房室系统）或将其剖分成若干个相互存在着某种联系的部分（多房室系统）。,房室具有以下特征：它由考察对象均匀分布而成，房室中考察对象的数量或浓度（密度）的变化率与外部环境有关，这种关系被称为,“,交换,”,且交换满足着总量守衡。在本节中，我们将用房室系统的方法来研究药物在体内的分布。在下一节中，我们将用多房室系统的方法来研究另一问题。,交换,环境,内部,单房室系统,均匀分布,37,药物的分解与排泄（输出）速率通常被认为是与药物当前的浓度成正比的，即：,药物分布的单房室模型,单房室模型是最简单的模型，它假设：体内药物在任一时刻都是均匀分布的，设,t,时刻体内药物的总量为,x,(,t,),；系统处于一种动态平衡中，即成立着关系式：,药物的输入规律与给药的方式有关。下面，我们来研究一下在几种常见的给药方式下体内药体的变化规律。,机体,环境,药物总量,图,3-8,假设药物均匀分布,38,情况,1,快速静脉注射,机体,环境,只输出不输入房室,其解为：,药物的浓度：,与放射性物质类似，医学上将血浆药物浓度衰减一半所需的时间称为药物的血浆半衰期：,负增长率的,Malthus,模型,在快速静脉注射时，总量为,D,的药物在瞬间被注入体内。设机体的体积为,V,，则我们可以近似地将系统看成初始总量为,D,，浓度为,D/V,，只输出不输入的房室，即系统可看成近似地满足微分方程：,（,3.12,）,39,情况,2,恒速静脉点滴,机体,环境,恒定速率输入房室,药物似恒速点滴方式进入体内，即,:,则体内药物总量满足：,（,x,(0)=0,）,（,3.13,）,这是一个一阶常系数线性方程，其解为：,或,易见,：,称为稳态血药浓度,对于多次点滴，设点滴时间为,T,1,，两次点滴之间的间隔时间设为,T,2,，,则在第一次点滴结束时病人体内的药物浓度可由上式得出。其后,T,2,时间内为情况,1,。故：,（第一次）,0,t,T,1,T,1,t,T,1,+,T,2,类似可讨论以后各次点滴时的情况，区别只在初值上的不同。第二次点滴起，患者,体内的初始药物浓度不为零。,40,情况,3,口服药或肌注,y(t),x(t),K,1,y,K,1,x,环境,机体,外部药物,口服药或肌肉注射时，药物的吸收方式与点滴时不同，药物虽然瞬间进入了体内，但它一般都集中与身体的某一部位，靠其表面与肌体接触而逐步被吸收。设药物被吸收的速率与存量药物的数量成正比，记比例系数为,K,1,，即若记,t,时刻残留药物量为,y,(,t,),，则,y,满足：,D,为口服或肌注药物总量,因而：,所以：,解得：,从而药物浓度：,41,图,3-9,给出了上述三种情况下体内血药浓度的变化曲线。容易看出，快速静脉注射能使血药浓度立即达到峰值，常用于急救等紧急情况；口服、肌注与点滴也有一定的差异，主要表现在血药浓度的峰值出现在不同的时刻，血药的有效浓度保持时间也不尽相同。,图,3-9,我们已求得三种常见给药方式下的血药浓度,C,(,t,),，当然也容易求得血药浓度的峰值及出现峰值的时间，因而，也不难根据不同疾病的治疗要求找出最佳治疗方案。,42,新药品、新疫苗在临床应用前必须经过较长时间的基础研究、小量试制、中间试验、专业机构评审及临床研究。当一种新药品、新疫苗研制出来后，研究人员必须用大量实验搞清它是否真的有用，如何使用才能发挥最大效用，提供给医生治病时参考。在实验中研究人员要测定模型中的各种参数，搞清血药浓度的变化规律，根据疾病的特点找出最佳治疗方案（包括给药方式、最佳剂量、给药间隔时间及给药次数等），这些研究与试验据估计最少也需要数年时间。在,2003,年春夏之交的,SARS,（非典）流行期内，有些人希望医药部门能赶快拿出一种能治疗,SARS,的良药或预防,SARS,的有效疫苗来，但这只能是一种空想。,SARS,的突如其来，形成了,“,外行不懂、内行陌生,”,的情况。国内权威机构一度曾认为这是,“,衣原体,”,引起的肺炎，可以用抗生素控制和治疗。但事实上，抗生素类药物对,SARS,的控制与治疗丝毫不起作用。以钟南山院士为首的广东省专家并不迷信权威，坚持认为,SARS,是病毒感染引起的肺炎，两个月后（,4,月,16,日），世界卫生组织正式确认,SARS,是冠状病毒的一个变种引起的非典型性肺炎（注：这种确认并非是由权威机构定义的，而是经对猩猩的多次实验证实的）。发现病原体尚且如此不易，要攻克难关，找到治疗、预防的办法当然就更困难了，企图几个月解决问题注定只能是一种不切实际的幻想。,43,上述研究是将机体看成一个均匀分布的同质单元，故被称单房室模型，但机体事实上并不是这样。药物进入血液，通过血液循环药物被带到身体的各个部位，又通过交换进入各个器官。因此，要建立更接近实际情况的数学模型就必须正视机体部位之间的差异及相互之间的关联关系，这就需要多房室系统模型。,I,II,k,12,k,21,两房室系统,图,3-10,图,3-10,表示的是一种常见的两房室模型，其间的,k,12,表示由室,I,渗透到室,II,的变化率前的系数，而,k,21,则表示由室,II,返回室,I,的变化率前的系数，它们刻划了两室间的内在联系，其值应当用实验测定，使之尽可能地接近实际情况。,当差异较大的部分较多时，可以类似建立多房室系统，即,N,房室系统,44,4.,离散优化模型,45,常用技巧,计算复杂性分析,算法设计,精确算法,近似算法,算法计算量估计、算法优劣比较,46,比较算法的好坏，从不同的角度出发，有各种不同的标准。在这里，我们仅就算法的计算速度作一个十分粗略的比较。,例,1,（整理问题）给定,n,个实数,a,1,a,2,a,n,，要求将它整理成由小到大排列（或由大到小排列）的顺序：,b,1,b,2,b,n,，,b,1,b,2,b,n,。,（算法,1,）取出,a,1,a,2,a,n,中的最小者，令其为,b,1,。从,a,1,a,2,a,n,中去除,b,1,，在余下的,n,1,个数中选出最小者，令其为,b,2,，,，直至得到,b,1,b,2,b,n,。,容易看出，为了排出,b,1,b,2,b,n,，算法工作了 次比较。,（算法,2,）,步,0,b,1,a,1,步,1,设已有,b,1,b,k,(1,kn,),，将按两分法比较的方式把,a,k,+1,排入其中：若,b,1,b,i,a,k+1,b,i,+1,b,k,，令（,b,1,b,2,b,k,b,k,+1,）（,b,1,b,i,a,k,+1,b,i,+1,b,k,）。若,k,+1,b,4,，可再和,b,6,比（若,a,8,b,4,则和,b,2,比），易见，只要比,3,次即可排入,a,8,，由于,r,log,2,k,+1,，算法的总经较次数不超过,令 ，设计算机每秒可作,C,次比较，则算法,1,与算法,2,整理,a,1,a,2,a,n,所用的时间分别为,若,n,=100,万，,C=100,万次,/,秒，则,t,1,5.8,天，而,t,2,20,秒。可见在较大规模的整理问题时，算法,2,明显优于算法,1,。,48,现设一台每小时能作,M,次运算的计算机，并设求解某一问题已有了两个不同的算法。算法,A,对规模为,n,的实例约需作,n,2,次运算而算法,B,则约需作,2,n,次运算。于是，运用算法,A,在一小时内可解一个规模为 的实例，而算法,B,则只能解一个规模为,log,2,M,的实例。两者的差别究竟有多大呢？让我们来对比一下。假如计算机每秒可作,100,万次运算，则算法,A,一小时大约可解一个规模为,n,=60000,的实例，而算法,B,在一小时内只能解一个规模 的实例且,n,每增加,1,，算法,B,求解时所化的时间就将增加,1,倍。例如算法,B,求解一个,n,=50,的实例将连续运算,357,年多。,现设计算速度提高了,100,倍，这对计算机来讲已是一个相当大的改进。此时算法,A,可解问题的规模增大了,10,倍，而算法,B,可解问题的规模只增加了,log,2,1000,，对任意正整数,N,，总可找到一个大于,N,的正整数,n,及,D,的一个规模为,n,的实例，对这一实例有,fB,(,D,n,)=,O,(2,kn,),，则称,B,为求解问题,D,的一个指数算法。,多项式算法被称为是“好”的算法即所谓有效算法，而指数算法则一般被认为是“坏”算法，因为它只能求解规模极小的实例。,50,下面的表,1,列出了在规模大约为,n,时各类算法的计算量，而表,8-15,则反映了当计算机速度提高,10,倍、,100,倍时，各类算法在,1,小时内可求解的问题的模型的增长情况，（前三个是多项式时间的，后两个是指数时间的）,表,1,几个多项式和指数时间复杂性函数增长情况,算法要求的计算量,规模,n,的近似值,10,100,1000,n,10,100,1000,n,log,n,33,664,9966,n,3,10,3,10,6,10,9,2,n,1024,1.2710,30,1.0510,301,n,!,3628800,10,158,410,2567,51,表,2 1,小时内可解的问题实例的规模,算法要求的计算量,用现在计算机,用快,10,倍计算机,用快,100,倍计算机,n,N,1,10,N,1,100,N,1,n,log,n,N,2,8.2,N,2,67,N,2,n,3,N,3,2.15,N,3,4.64,N,3,2,n,N,4,N,4,+3.32,N,4,+6.64,n,!,N,5,N,5,+2,N,5,+3,由定义,1,知,4,n,2,与,2,n,2,都是,O,(,n,2,),，,n,log,n,+3,n,是,O,(,n,log,n,),，我们在以后分析时间复杂性函数时也往往忽略常系数和增长速度较慢的项，因为前者可通过提高计算机速度来提高效率，而后者增长速度最快的项才是决定效率的关键因素。,六个最初的,NP,难问题,52,（,1,）（,3,满足问题，简记,3,SAT,问题）每一个句子都是一个三项式的,SAT,问题，称为,3,SAT,问题。,例如，就是,3,SAT,的一个实例。,2,）（三维匹配问题,3DM,）,X,、,Y,、,Z,是三个不相交的集合，,|,X,|=|,Y,|=|,Z,|=,q,，。问：,M,中是否包含一个匹配,M,，使得 （等价问题是求最大三维匹配）。,注：这里给出的是标准形式，一般可不必要求,|,X,|=|,Y,|=|,Z,|,，表示笛卡尔乘积。,三维匹配问题是下一章中二维匹配（,2DM,）问题的推广，,2,DM,是,P,问题而,3,DM,是,NP,完全的。一个匹配是指,M,的一个子集合,(,x,i,y,i,z,i,),，,x,i,X,，,y,i,Y,，,z,i,Z,，且当下标不同时，它们分别取三个集合中的不同元素。,3DM,可作如下形象的解释：记一单身男人集合为,X,，一单身女人集合为,Y,，此外还有一个住房集合,Z,。其间存在一相容关系（例如有些人之间不愿组成家庭，或不愿住某一住房），这样就给出了一个集合,，,M,是由问题给出的，表示了所有可能组合。所求的匹配即组成的一组家庭（包括住房），其中不能有重婚，也不能让不同的两个家庭住进同一住房。,53,（,3,）（划分问题）给定一正整集合,A,=,a,1,a,2,a,n,，问是否存在,A,的一个子集,A,使得 ，即是否可将,A,中的数分成总和相等的两部分。,（,4,）（顶点复盖问题,VC,）给定一个图,G,=,（,V,，,E,）及一个正整数,K,|,V,|,，问,G,中是否有不超过,K,个顶点的复盖。（一个顶点的子集称为,G,的一个复盖，若它至少包含,G,中任一边的两个端点之一）。,（,5,）（哈密顿圈问题,HC,）见例,8.9,。,（,6,）（团问题）给定图,G,=,（,V,，,E,）及一正整数,K,|,V,|,，问是否存在图,G,中的一个团,V,，,|,V,|,K,。（,G,的一个顶点的子集,V,称为,G,的一个团，若,V,中任意两点间都有,E,中的边相连）。,图,8.5,表达了上述六个问题及,SAT,问题之间的多项式转化关系，即,SAT3SAT,，,3SAT3DM,及,3SATVC,等等。,54,例,2.,（婚姻问题）,在遥远的地方有一位酋长，他想把三个女儿嫁出去。假定三个女儿为,A,、,B,、,C,，三位求婚者为,X,、,Y,、,Z,。每位求婚者对,A,、,B,、,C,愿出的财礼数视其对她们的喜欢程度而定,（见下表）：,X Y Z,A 3 5 26,B 27 10 28,C 1 4 7,问酋长应如何嫁女，才能获得最多的财礼（从总体上讲，他的女婿最喜欢他的女儿）。,55,例,2.,显然是指派问题的实例，但它也可以看成是两分图赋权匹配问题的实例。,用三个点表示酋长的三个女儿，将它们放在一边。再用三个点表示求婚者，将它们放在另一边。在有可能结婚的两人之间画一条边，并在边上写上求婚者对这种结婚愿付出的财礼数，得到右图。右图是一个特殊的图，它的顶点可以分成两个子集，只有分属不同子集的点才可能有边相连（但也可以无边），这样的图称为两分图。,定义,3.(,匹配,),图,G,的一个匹配是指边集,E,的一个子集,M,，,M,中的任意两条边,均不具有公共的顶点。,容易看出，酋长要解的问题是在上面的两分图中找出一个具有最大权和的,匹配，读者不难由此得到一般两分图最大权匹配问题的数学模型。,以上举的是一个,P,问题，下面来看一个,NP,难问题,56,例,3,（装箱问题,Bin,packing,）有一批待装箱的物品,J,=,p,1,p,n,，,p,j,的长度为,l,(,p,j,),。现有一批容量为,C,的箱子（足够数量），要求找到一种装箱方法，使得所用的箱子数最少。,例,3,是一个一维的装箱问题。例如，我们有一批具有相同长度的钢材，如果想取出几根已知长度的钢料生产某种设备，当然会希望少用几根原始钢材以减少浪费。此时，我们就遇到了一个一维的,Binpacking,问题。当我们想从购买来的三夹板上锯出,n,块已知长、宽的板来制作家具时，遇到的是二维,Binpacking,问题。而当我们真正想把一批已知长、宽、高的物体装入具有相同尺寸的箱子时，又遇到了三维的。下面的定理 告诉我们，即使是一维的,Binpacking,问题也是,NP,完全的，故二维和三维的,Binpacking,问题更不可能是,P,问题（它们也是,NP,完全的）。,定理,1.,（一维）,Binpacking,问题是,NP,完全的。,证明：,易见，划分问题可转化为,Binpacking,问题。事实上，,取 ，,J,=,c,1,c,n,可划分为两个相等的集合的充要条件是,它们可装入两只容量为,C,的箱中。,57,存在两种不同类型的,Bin,-,packing,问题。第一类不允许整理，必须按给定的顺序装箱，称为,on,-,line,问题；第二类允许先对物品加以整理，然后再装箱，称为,off-line,问题。,（一）,on-line,排序问题的近似算法,1.NF,（,Next Fit,）算法,步,1,将,P,1,装入,B,1,中。,步,2,装,P,i,(,i,=2,n,),。设,B,j,是具有最大足码的非空箱，若,P,i,可继续装入,B,j,则将其装入，否则将,P,i,装入,B,j+,1,中，即装入下一空箱中（前面的箱子将不再使用）。,记,NF,算法使用的箱子数为,NF,（,L,），则：,NF(L)2OPT(,L,),，且,2,是紧的，即不能被减小。,58,2.FF,（,First Fit,）算法,步,1,将,P,1,装入,B,1,中。,步,2,装,P,i,i,=2,n,。找出最小的,j,使,P,i,可装入,B,j,中，将,P,i,装入其中，在装,箱结束前，每一箱子的剩余空间均有可能被继续利用。,定理,2,设,FF(,L,),为用,FF,算法将,L,中的物品装箱所用的箱数，则有,FF(,L,)1.7OPT(,L,)+1,，且,1.7,是紧的，即不能被减小，（证明有较大难度，,从略）。,3.BF,（,Best Fit,）算法,步,1,装,P,1,装入,B,1,中。,步,2,装,P,i,i,=2,n,。在能够装下,P,i,的箱中找出已装得最多（即剩余空间,最小）的一只,B,j,，将,P,i,装入,B,j,。,定理,3,设,BF(,L,),为用,BF,算法将,L,中物品装箱所用的箱数，则有,BF,（,L,）,1.7OPT(,L,)+1,，且,1.7,是紧的，（证明从略）。,59,5.,逻辑模型,60,例,1,拟将一批尺寸为,124,的的商品装入尺寸为,666,的正方体包装箱中，问是否存在一种装法，使装入的该商品正好充满包装箱。,解,将正方体剖分成,27,个,222,的小正方体，并,按下图所示黑白相间地染色。,再将每一,222,的小正方体剖分成,111,的小正方体。,易见，,27,个,222,的正方体中，有,14,个是黑的，,13,个是白的（或,13,黑,14,白），故经两次剖分，共计有,112,个,111,的黑色小正方体和,104,个,111,的白色小正方体。,虽然包装箱的体积恰好是商品体积的,27,倍，但容易看到，不论将商品放置在何处，它都将占据,4,个黑色和,4,个白色的,111,小正方体的位置，故商品不可能充满包装箱。,61,德国著名的艺术家,Albrecht Drer(1471-1521),于,1514,年曾铸造了一枚名为“,Melencotia I”,的铜币。令人奇怪的是在这枚铜币的画面上充满了数学符号、数字及几何图形。这里，我们仅研究铜币右上角的数字问题,例,2.,Drer,魔方（或幻方）问题,62,所谓的魔方是指由,1n,2,这,n,2,个正整数按一定规则排列成的一个,n,行,n,列的正方形。,n,称为此魔方的阶。,Drer,魔方,：,4,阶，每一行之和为,34,，每一列之和为,34,，对角线（或反对角线）之和是,34,，每个小方块中的数字之和是,34,，四个角上的数字加起来也是,34,什么是,Drer,魔方,多么奇妙的魔方！,铜币铸造时间：,1514,年,6