6 动态优化与其他

第六讲动态优化模型与其他模型,第十二章动态优化模型12.1速降线问题与泛函简介12.2最短路问题与最小生成树第十一章马尔科夫链模型11.1健康与疾病，马氏链简介,12.1速降线问题与泛函简介,铅直平面内给定不在一条垂线上的2个点A,B，如图，求连接他们的光滑曲线，使质点在重力作用下沿该曲线以最短时间从A滑到B（摩擦力不记）,o,x,y,A,B,y=y(x),速降线问题,根据能量守恒定律，质点在曲线上任一点满足,为了求这条运动时间最短的曲线，记连接A,B的曲线为y=y(x)，曲线的弧长为：,于是质点沿曲线y=y(x)从A点滑到B点的时间可表为,y=y(x)在A,B两个端点应有：,速降线问题归结为求y=y(x),在满足上面的条件下，使得J(y(x)达到最小,最简泛函极值的必要条件-欧拉方程条件极值：哈密顿函数,12.2动态优化中的最短路问题与最小生成树,例1最短路径问题右图表示从起点A到终点E之间各点的距离。求A到E的最短路径。,5,2,8,7,12,20,14,19,19,最小生成树（最小支撑树）,定义1：一个无圈的连通图称为树,定义2：图G中，若任何2个点之间，至少有一条链，则称G是连通图,定理1：图G是树的充分必要条件是任意2个顶点之间恰好有一条链（1）从一个树中去掉任意一条边，则余下的图是不连通的。（2）在树中不相邻的两个点间添上一条边，则恰好得到一个圈。,找一个图G的最小生成树（最小支撑树）的方法,1、避圈法2、破圈法,6,5,4,4,7,5,2,1,3,2,5,6,1,5,7,4,4,3,第十一章马尔科夫链模型,系统在每个时期所处的状态是随机的,从一时期到下时期的状态按一定概率转移,下时期状态只取决于本时期状态和转移概率已知现在，将来与过去无关（无后效性）,描述一类重要的随机动态系统（过程）的模型,马氏链(MarkovChain)时间、状态均为离散的随机转移过程,通过有实际背景的例子介绍马氏链的基本概念和性质,例1.人的健康状况分为健康和疾病两种状态，设对特定年龄段的人，今年健康、明年保持健康状态的概率为0.8,而今年患病、明年转为健康状态的概率为0.7，,健康与疾病,人的健康状态随着时间的推移会随机地发生转变,保险公司要对投保人未来的健康状态作出估计,以制订保险金和理赔金的数额,若某人投保时健康,问10年后他仍处于健康状态的概率,Xn+1只取决于Xn和pij,与Xn-1,无关,状态与状态转移,状态转移具有无后效性,设投保时健康,给定a(0),预测a(n),n=1,2,设投保时疾病,n时状态概率趋于稳定值，稳定值与初始状态无关,状态与状态转移,例2.健康和疾病状态同上，Xn=1健康,Xn=2疾病,p11=0.8,p12=0.18,p13=0.02,死亡为第3种状态，记Xn=3,健康与疾病,p21=0.65,p22=0.25,p23=0.1,p31=0,p32=0,p33=1,设投保时处于健康状态，预测a(n),n=1,2,不论初始状态如何，最终都要转到状态3；一旦a1(k)=a2(k)=0,a3(k)=1,则对于nk,a1(n)=0，a2(n)=0,a3(n)=1,即从状态3不会转移到其它状态。,状态与状态转移,马氏链的基本方程,基本方程,马氏链的两个重要类型,1.正则链从任一状态出发经有限次转移能以正概率到达另外任一状态（如例1）。,w稳态概率,马氏链的两个重要类型,2.吸收链存在吸收状态（一旦到达就不会离开的状态i,pii=1）,且从任一非吸收状态出发经有限次转移能以正