ch动态规划.ppt

Page 1第五章动态规划第一节多阶段决策过程及实例Page 2动态规划是运筹学的重要分支之一,它是解决多阶段决策过程最优化的一种方法。该法是由美国数学家贝尔曼(R. Bellman)等人在本世纪50年代首先提出的。“动态规划”一书是动态规划方面的第一本著作。目前,动态规划已成功地用于解决资源分配、货物装运、设备更新、生产计划以及复合系统可靠性等许多问题。Page 3动态规划动态规划引例1:某旅客需从A号站到达E号站,试指出一条最短路径。交通状况如图所示。箭头表示旅行路线,箭头旁边数字表示距离。[解] 一种习惯求解法是首先计算所有可能路线的距离,然后经比较选出一条最短路线,这称为显枚举或穷举法,当维数增大时,该法计算量将急剧增大,从而变得不可行。动态规划是采用递推方式计算,分4个阶段。Page 4动态规划动态规划最短路径为:A→B1→C3→D2→E24ED1D2C3C2C1B2B1A533766452123第4阶段第3阶段第2阶段第1阶段18Page 5动态规划动态规划引例2:机器负荷分配问题(P155 例2)制订五年计划,可以看做一个五阶段动态规划问题。Page 6第二节动态规划的基本概念Page (stage)原问题可分为若干个子问题,每一子问题称为一个阶段,用k 表示。k=1,2,….,n 称为阶段变量。(state)每一阶段开始时所处的状态(位置),称为状态,用表示。如引例1中,状态集第二节第二节动态规划的基本概念动态规划的基本概念Sk3 1 2 3{ , , }S C C C?Page 8动态规划的基本概念动态规划的基本概念3. 决策(decision)从某一阶段某一状态出发,向下一阶段某一状态演变的选择。表示第k个阶段从出发的决策变量。表示第k个阶段从出发的允许决策集合。如:( ) :k kU SD ( ) :k kSkSkS2 1 1 2 3D ( )={C , , }B C C2 1 1U ( )=CBPage 94. 策略(policy)一个按顺序排列的决策组成的集合。从第一阶段开始至终止:从第k 阶段开始至终止:1 1 1 1 2 2 n n( )={U (S ),U (S ),......,U (S )}nP Sk k k+1 k+1 n n( )={U (S ),U (S ),......,U (S )}kn kP S(后部子策略)动态规划的基本概念动态规划的基本概念Page 105. 状态转移由一个状态转移到下一个状态的演变过程,用方程1 k k k=T (S ,U )kS?(状态转移方程)若状态给定,决策变量确定,则第k+1阶段的状态就确定了。T称为状态转移函数。kSkU1kS?动态规划的基本概念动态规划的基本概念