运筹学动态规划.ppt

第八章动态规划多阶段决策过程:是指这样一类决策过程,它可以按时间分为若干阶段(称为时段),每一个阶段都需要做出决策,以便在过程的最终阶段得到最优结局。动态规划的一个重要特点是利用所谓的“最优化原理”,将问题用函数方程来表示(即递推方程),然后利用方程递推地进行计算、求解。.一、最短路线问题最短路线问题:是指给定始点和终点,并且已知由始点到终点的各种可能的途径,需要找出由始点到终点的最短路线。这里的最短路线可以是通常意义下的距离,也可以是运输的时间或运输费用等等。.例由A到D地要铺设一条煤气管道。其中须经过两级中间站,第一级中间站分别为B1和B2,第二级中间站分别为C1、C2、C3。两站之间有连线的就表示可铺设管道,没有连线的就表示不能铺设管道。连线中间的数字表示两点间铺设管道的长度,试确定一条由A点到D点的铺设管道的最短路线。:表示由当前的状态到终点之间的阶段数。如由A点到D点n=3;由B2到D点n=2等等。n=3n=2n=:表示当前所处的位置,称为状态变量。如s可以是A、B1、B2、C1、C2等等。.符号和概念AB2B1C3C2C1D21233134341Xn(s):称为决策变量,它表示由阶段数为n的某个状态s演变到下一个阶段的某个状态,决策者做出的一种选择。如,X2(B1)表示已处于B1状态,还有2个阶段就到达D点了,此时决策者可选择的地点;X2(B1)可取C1,C2或C3。.符号和概念AB2B1C3C2C1D21233134341fn(s):表示由阶段数为n的某个状态s至终点的最短距离。例如,f2(B1)表示由阶段数为2的状态B1沿最优路线到达终点的距离,即B1到D点的最短距离。显然本例就是要求f3(A)及f3(A)所确定的最短路线。.符号和概念AB2B1C3C2C1D21233134341d(s,Xn(s)):表示当前处于状态s时,选取决策变量Xn(s)后,由点s到点Xn(s)的距离。例如,d(B1,C3)=1,d(C2,D)=(A),有几种可供选择的路线AB2B1C3C2C1D21233134341.