运筹学第6章new.ppt

第六章 动态规划 状态转移律也称为状态转移方程. 在动态规划中，本阶段的状态往往是上一个阶段状态和上一个阶段决策作用的结果。设第k阶段状态为sk，做出的决策为xk（sk），则第k+1阶段的状态sk+1随之确定，他们之间的关系可以表示为： sk+1=Tk（sk，xk） 这种表示从第k阶段到第k+1阶段状态转移规律的方程称为状态转移方程，它反映了系统状态转移的递推规律。例如例1中，上一阶段的决策就是下一阶段的状态，所以状态转移方程为： sk+1= xk（sk） 当k=1时，f1（s1）就是从初始状态s1出发到终止状态的最优函数。在不同的问题中，指标函数可以是利润、成本、距离、产品质量或资源消耗等。在最短路线问题中，第k阶段的指标函数vk（sk，xk）通常也用dk（sk，xk）表示。 例如例1中，d2（B2，C3）表示第二阶段中由点B2到点C3的距离，fk（sk）表示从第k阶段点sk到终点E的最短距离，f1（A）就是所求从A到E的最短距离。 指标函数 (Return function) 是衡量对决策过程进行控制的效果的数量指标。分为k阶段指标函数、过程指标函数及最优指标函数。 指标函数的最优值称为最优指标函数，记作 k阶段指标函数 从k阶段状态sk出发，选择决策xk所产生的第k阶段指标，称为k阶段指标函数,记为vk(sk,xk)。 从k阶段状态sk出发，选择决策xk,xk+1,…,xn所产生的过程指标，称为k子过程指标函数或简称过程指标函数，记为 Vk(sk,xk,xk+1,…,xn)或Vk，n为阶段数。 过程指标函数 最优指标函数 从k阶段状态sk出发，对所有的子策略，最优的过程指标函数称为最优指标函数，记为fk(sk)，通常取Vk的最大值或最小值。 （Opt＝optimization 表示“max”或“min” 三.最优化原理与动态规划基本模型 贝尔曼(R.Bellman)最优化原理:作为整个过程的最优策略具有这样的性质,无论过去的状态和决策如何,对先前决策所形成的状态而言,余下的诸决策必构成最优策略. 根据这一原理,计算动态规划问题的逆序法递推关系式称为动态规划基本方程: 其中, 称为边界条件. 动态规划数学模型由 、边界条件及状态转移方程构成。 用动态规划求解例1: 2 5 1 12 14 10 6 10 4 13 11 12 3 9 6 5 8 10 5 2 C1 C3 D1 A B1 B3 B2 D2 E C2 动态规划基本方程为: 用 表示从某一阶段的初始状态到下一阶段初始状态的支路距离，用 表示第k阶段的xk到终点E的最短距离。如f2(B1)表示从第2阶段的B1 到终点E的最短距离。 2 5 1 12 14 10 6 10 4 13 11 12 3 9 6 5 8 10 5 2 C1 C3 D1 A B1 B3 B2 D2 E C2 f5(E)=0 2 5 1 12 14 10 6 10 4 13 11 12 3 9 6 5 8 10 5 2 C1 C3 D1 A B1 B3 B2 D2 E C2 f4(D1)=5 f5(E)=0 2 5 1 12 14 10 6 10 4 13 11 12 3 9 6 5 8 10 5 2 C1 C3 D1 A B1 B3 B2 D2 E C2 f4(D2)=2 f5(E)=0 f4(D1)=5 2 5 1 12 14 10 6 10 4 13 11 12 3 9 6 5 8 10 5 2 C1 C3 D1 A B1 B3 B2 D2 E C2 f4(D2)=2 f5(E)=0 f3(C1)=8 f4(D1)=5 2 5 1 12 14 10 6 10 4 13 11 12 3 9 6 5 8 10 5 2 C1 C3 D1 A B1 B3 B2 D2 E C2 f4(D2)=2 f5(E)=0 f3(C2)=7 f4(D1)=5 f3(C1)=8 2 5 1 12 14 10 6 10 4 13 11 12 3 9 6 5 8 10 5 2 C1 C3 D1 A B1 B3 B2 D2 E C2 f4(D2)=2 f5(E)=0 f3(C3)=12 f4(D1)=5 f3(C1)=8 f3(C2)=7 2 5 1 12 14 10 6 10 4 13 11 12 3 9 6 5 8 10 5 2 C1 C3 D1 A B1 B3 B2 D2 E C2 f4(D2)=2 f5(E)=0 f3(C3)=12 f4(D1)=5 f2(B1)=20 f3(C2)=7 f3(C1)=8 * * 6.1