运筹学动态规划I.pptVIP

School of Business ECUST (4) 状态转移方程 (5) 递归方程 以 表示在第k阶段状态sk处时选择决策xk所实现的阶段效应，也即从阶段k的某个初始节点到达阶段k+1的某个初始节点之间的距离。 以 表示从第k+1阶段状态sk+1到终点的最短距离。 School of Business ECUST 动态规划的求解方法 逆序求解法 顺序求解法 School of Business ECUST 递归方程： School of Business ECUST School of Business ECUST 最优路径 最优策略 最短距离 School of Business ECUST 用动态规划方法处理静态问题 例：用动态规划方法解下列非线性规划问题 (1) 划分阶段：把这一问题看作一个三阶段的决策问题 第1阶段——决定x1的值 第2阶段——决定x2的值 第3阶段——决定x3的值 School of Business ECUST (2) 选择状态变量： 将约束条件x1, x2, x3的总和等于c看作资源总量，以s1,s2, s3分别表示第1,2,3阶段初的资源拥有量(状态变量)，s4表示第4个阶段(假想)初或第3个阶段末的资源拥有量，显然s1=c，s4=0 s1 s2 s3 s4 x1 x2 x3 School of Business ECUST (3) 确定决策变量与允许决策集： 在第1, 2, 3个阶段的决策变量分别为x1, x2, x3 (4) 状态转移方程： s1 s2 s3 s4 x1 x2 x3 School of Business ECUST (5) 递归方程： School of Business ECUST * 阶段之间的联系体现在下一阶段的初始状态收到当前阶段与当前阶段所作决策的影响。 * * 描述两个相继阶段状态之间的关系 第13讲 动态规划I School of Business ECUST 本讲提纲 1. 多阶段决策问题 2. 动态规划的基本概念与最优性原理 3. 动态规划模型的建立 School of Business ECUST 1. 多阶段决策问题 动态规划所研究的对象是多阶段决策问题。所谓多阶段决策问题是指决策过程可按照时间或空间分为若干个互相联系的阶段，决策者在每个阶段需作出决策，当前阶段的决策不仅决定当前阶段的效益，而且影响下一阶段的初始状态。问题是决策者在每个阶段应如何决策，使各阶段的效益之和达到最优。 School of Business ECUST 例1：最短路问题 小王要从A地走到E地，问其如何走可使路程最短？ School of Business ECUST 可将小王的决策分为四个阶段： 第1阶段：选择走到B1，B2，还是B3？ 第2阶段：选择走到C1，C2，还是C3？ 第3阶段：选择走到D1，还是D2？ 第4阶段：选择走到E(只有一种选择) 第4阶段： 如果小王处于D1：D1?E，路程：5 如果小王处于D2：D2?E，路程：2 第3阶段： 如果小王处于C1：C1 如果小王处于C2：C2 如果小王处于C3：C3 School of Business ECUST D1：3+5 D2：9+2 II D1：6+5 D2：5+2 D1：8+5 D2：10+2 II II 第2阶段： 如果小王处于B1 如果小王处于B2 如果小王处于B3 School of Business ECUST C1：12+3+5 C2：14+5+2 C3：10+10+2 II II C1：6+3+5 C2：10+5+2 C3：4+10+2 II II C1：13+3+5 C2：12+5+2 C3：11+10+2 II II 第1阶段： 小王位于A 最短路径： School of Business ECUST B1：2+12+3+5 B2：5+6+3+5 B3：1+12+5+2 II II School of Business ECUST 动态规划的思想 由最底部的小问题开始计算，然后循序向上，直至求出整个问题的答案。 将较小问题的计算结果进行存储，在计算较大问题过程中，如有需要可直接调用，无需每次重新计算。 动态规划是一种自下而上(bottom-up)解决问题的方式。 School of Business ECUST 拾火柴游戏：桌子上放30根火柴，每人一次可拾起1~3根，谁拾起最后1根火柴谁输，如果让你先拾，你有没有办法保证能赢得游戏？ School of