第六章(上课)运筹学动态规划04修改选编.ppt

(Dynamic programming);主要内容;概述;一、多阶段决策问题;多阶段决策问题的典型例子： 1 . 生产决策问题：企业在生产过程中，由于需求是随时间变化的，因此企业为了获得全年的最佳生产效益，就要在整个生产过程中逐月或逐季度地根据库存和需求决定生产计划。; 这时，机器的年完好率为a，即如果年初完好机器的数量为u，到年终完好的机器就为au, 0a1。; 3. 航天飞机飞行控制问题：由于航天飞机的运动的环境是不断变化的，因此就要根据航天飞机飞行在不同环境中的情况，不断地决定航天飞机的飞行方向和速度（状态），使之能最省燃料和实现目的（如软着落问题）。; 5 . 最短路问题：给定一个交通网络图如下，其中两点之间的数字表示距离（或花费），试求从A到G的最短距离（总费用最小）。;（1）阶段 （2）状态 （3）决策 （4）策略 （5）状态转移方程 （6）指标函数和最优值函数;; ;例1分为四阶段，k=1,2,3,4.;（2）状态;令 为k阶段初所处的位置。 ;（3）决策;（3）令决策变量sk为处于某阶段某状态（位置）时，选择下一个状态（位置）。 ;（4）策略;（5）状态转移方程;图示如下：;动态规划中能 处理的状态转移 方程的形式。;（6）指标函数和最优值函数;动态规划的指标函数应具有可分离性，并满足递推关系式， 函数记为：;指标函数的形式： ;积;最优值函数;小结:;指标: ;解多阶段决策过程问题，求出;k=4; ; ;;最优解（标号法）;动态规划的基本方程;动态规划基本思想：; 2、在多阶段决策过程中，动态规划方法是既把当前一段和未来一段分开，又把当前效益和未来效益结合起来考虑的一种最优化方法。因此，每段决策的选取是从全局来考虑的，与该段的最优选择答案一般是不同的。 3、在求整个问题的最优策略时，由于初始状态是已知的，而每段的决策都是该段状态的函数，故最优策略所经过的各段状态便可逐段变换得到，从而确定了最优路线。;四、动态规划递推求解方法;1、划分阶段k 划分阶段是运用动态规划求解多阶段决策问题的第一步，在确定多阶段特性后，按时间或空间先后顺序，将过程划分为若干相互联系的阶段。对于静态问题要人为地赋予“时间”概念，以便划分阶段。 2、正确选择状态变量sk 选择变量既要能确切描述过程演变又要满足无后效性，而且各阶段状态变量的取值能够确定。一般地，状态变量的选择是从过程演变的特点中寻找。 ;3、确定决策变量uk(sk)及允许决策集合Dk(sk) 通常选择所求解问题的关键变量作为决策变量，同时要给出决策变量的取值范围，即确定允许决策集合。 4、确定状态转移方程 根据k阶段状态变量和决策变量，写出k+1阶段状态变量，状态转移方程应当具有递推关系。 sk+1=Tk(sk,uk) Tk —函数关系;5、确定阶段指标函数和最优指标函数，建立动态规划基本方程 阶段指标函数是指第k 阶段的收益，最优指标函数是指从第k 阶段状态出发到第n 阶段末所获得收益的最优值，最后写出动态规划基本方程。 f k (sk ) = Opt [ Vk (sk ,uk ) + f k+1 (s k+1) ] fn+1 (s n+1 ) = 0 Opt 最优化（max,min）; 以上五步是建立动态规划数学模型的一般步骤。由于动态规划模型与线性规划模型不同，动态规划模型没有统一的模式，建模时必须根据具体问题具体分析，只有通过不断实践总结，才能较好掌握建模方法与技巧。 ;静态规划与动态规划的关系;逆推解法与顺推解法;逆序解法基本方程;顺序解法基本方程;五、动态规划最优性（最优化）原理和最优性定理;*;六、动态规划优缺点;七、动态规划问题应用举例;例一、从A 地到D 地要铺设一条煤气管道,其中需经过两级中间站，两点之间的连线上的数字表示距离，如图所示。问应该选择什么路线，使总距离最短？ ; 解：整个计算过程分三个阶段，从最后一个阶段开始。; d( B1,C1 ) + f3 (C1 ) 3+1 f2 ( B1 ) = min d( B1,C2 ) + f3 (C2 ) = min 3+3 d( B1,C3 ) + f3 (C3 )