1 第八章 动态规划第八章 动态规划 Dynamic Programming 1 动态规划问题实例1 动态规划问题实例 2 动态规划的基本概念2 动态规划的基本概念 3 基本原理和基本方程3 基本原理和基本方程 4 动态规划的应用4 动态规划的应用 2 1动态规划问题实例1动态规划问题实例 许多问题用动态规划研究求解比线性规划、非线性规划更有 效，特别是离散性问题，解析数学无用武之地，而动态规划成 为得力工具； 某些情况下，用动态规划处理不仅能作定性描述分析，且 可利用计算机给出求其数值解的方法。 动态规划 许多问题用动态规划研究求解比线性规划、非线性规划更有 效，特别是离散性问题，解析数学无用武之地，而动态规划成 为得力工具； 某些情况下，用动态规划处理不仅能作定性描述分析，且 可利用计算机给出求其数值解的方法。 动态规划DP是运筹学的一个分支，是解决多阶段决策过程 最优化的一种数学方法（一种分析多阶段决策过程的数学方 法），这种方法可根据人们所采取的措施，一步步地控制过程 的发展，以实现预定的要求。 1951年美国数学家 是运筹学的一个分支，是解决多阶段决策过程 最优化的一种数学方法（一种分析多阶段决策过程的数学方 法），这种方法可根据人们所采取的措施，一步步地控制过程 的发展，以实现预定的要求。 1951年美国数学家R.E. Bellman等人根据一类多阶段决策问 题的特性，提出了解决这类问题的最优化原理，把多阶段过程 转化为一系列单阶段问题逐个求解，并研究了许多实际问题而 建立了动态规划。 等人根据一类多阶段决策问 题的特性，提出了解决这类问题的最优化原理，把多阶段过程 转化为一系列单阶段问题逐个求解，并研究了许多实际问题而 建立了动态规划。 3 1动态规划问题实例1动态规划问题实例 多阶段决策过程多阶段决策过程 由问题的特征可将决策过程按 时间、空间等方式分为若干互相联系的不同阶 段，在每个阶段有若干种不同方案可供选择，进 行决策，每个阶段的决策执行将影响到下一阶段 的决策，决策者根据全局最优在每一阶段做出决 策，从而使整个过程达到最优 由问题的特征可将决策过程按 时间、空间等方式分为若干互相联系的不同阶 段，在每个阶段有若干种不同方案可供选择，进 行决策，每个阶段的决策执行将影响到下一阶段 的决策，决策者根据全局最优在每一阶段做出决 策，从而使整个过程达到最优 4 1动态规划问题实例1动态规划问题实例 例5.1 最短路问题例5.1 最短路问题下图为一城市若干单向道路组成的交通 图，两点之间连线数字表示两点间的距离，问应该如何选择 路线，使A到G点路程最短 下图为一城市若干单向道路组成的交通 图，两点之间连线数字表示两点间的距离，问应该如何选择 路线，使A到G点路程最短 A A 5 6 3 1 B1 B2 E1 C2 C3 C4 3 8 7 6 C1 E2 E3 D1 D2 D3 F1 F2 G 6 8 3 5 3 3 8 4 2 2 1 2 3 3 6 3 5 5 2 6 3 4 1 2 34 56 ABi Bi Cj Cj Dk Dk El El Fm Fm G (i=12) (j=1,3) (k=1,2,3) (l=1,2,3) (m=1,2,3) 6阶段阶段 图图8-1 5 例5.2 机器负荷分配问题例5.2 机器负荷分配问题 某种机器可以在高低两种不同的负荷下进行生产在高负荷下 进行生产时，产品的年产量 某种机器可以在高低两种不同的负荷下进行生产在高负荷下 进行生产时，产品的年产量g和投入生产的机器数量和投入生产的机器数量u的关系 为 的关系 为 gg(u), 这时机器的年完好率为这时机器的年完好率为a（0a1)在低负荷下生 产时，产品的年产量h和投入生产的机器数量v的关系为 在低负荷下生 产时，产品的年产量h和投入生产的机器数量v的关系为h h(v), 这时机器的年完好率为这时机器的年完好率为b（ab1）假定开始生产时完 好的机器数量为 ）假定开始生产时完 好的机器数量为s1，要求制定一个五年计划,在每年开始时决 定机器在两种不同负荷下生产的数量, ，要求制定一个五年计划,在每年开始时决 定机器在两种不同负荷下生产的数量,使五年内产品的总产量 最高。 使五年内产品的总产量 最高。 状态1状态1 s s1 1 完好机器数完好机器数 阶段1 决策 高负荷 机器数 状态2 决策 高负荷 机器数 状态2 s s2 2 阶段2 决策 高负荷 机器数 状态2 决策 高负荷 机器数 状态2 s s3 3 阶段3 决策 高负荷 机器数 状态2 决策 高负荷 机器数 状态2 s s4 4 阶段4 决策 高负荷 机器数 状态2 决策 高负荷 机器数 状态2 s s5 5 阶段5 决策 高负荷 机器数 决策 高负荷 机器数 s s6 6 图图8-2 6 2 动态规划的基本概念2 动态规划的基本概念 (1)阶段（(1)阶段（stage）和阶段变量）和阶段变量 把所研究多段决策问题，按时间和空间先后 顺序划分为若干相互联系的决策阶段，以便按一定的次序求解每阶段的解 。描述阶段的变量称阶段变量，常用 把所研究多段决策问题，按时间和空间先后 顺序划分为若干相互联系的决策阶段，以便按一定的次序求解每阶段的解 。描述阶段的变量称阶段变量，常用k表示。表示。 (2)状态（(2)状态（state） 状态表示每个阶段开始时所处的自然状况或客观条件。描 述状态的变量称为状态变量，第 状态表示每个阶段开始时所处的自然状况或客观条件。描 述状态的变量称为状态变量，第k阶段的状态变量常用阶段的状态变量常用sk表示。表示。sk的所有可 能取值集合称为状态集合，用 的所有可 能取值集合称为状态集合，用Sk表示.状态既是前面阶段所作决策的结果， 又是本阶段作出决策的出发点和依据。 动态规划中要求状态必须具有 表示.状态既是前面阶段所作决策的结果， 又是本阶段作出决策的出发点和依据。 动态规划中要求状态必须具有无后效性无后效性，即如果某阶段状态给定后，这 阶段以后过程的发展不受这阶段以前各阶段状态的影响。换句话说，过程 的过去历史只能通过当前状态去影响它未来的发展。这一性质也称马尔科 夫性 ，即如果某阶段状态给定后，这 阶段以后过程的发展不受这阶段以前各阶段状态的影响。换句话说，过程 的过去历史只能通过当前状态去影响它未来的发展。这一性质也称马尔科 夫性 (3)决策（decision）(3)决策（decision）决策指决策者根据当前的状态，在若干种方案中作出 选择，达到下一阶段状态。表示决策的变量称决策变量 决策指决策者根据当前的状态，在若干种方案中作出 选择，达到下一阶段状态。表示决策的变量称决策变量，第第k阶段的决策变 量常用 阶段的决策变 量常用uk(sk)表示。决策变量的取值会受到状态变量的制约，被限制在某一 范围之内,称此范围为允许决策集合，常用 表示。决策变量的取值会受到状态变量的制约，被限制在某一 范围之内,称此范围为允许决策集合，常用Dk(sk)表示，显然表示，显然 uk(sk)Dk(sk) 7 2 2 动态规划的基本概念动态规划的基本概念 (4) 策略（(4) 策略（policy）各阶段决策决定后，整个问题的决策序列就构成一个策 略。设 各阶段决策决定后，整个问题的决策序列就构成一个策 略。设u1(s1), u2(s2) , un(sn)分别为各阶段的决策，用决策排列序列分别为各阶段的决策，用决策排列序列 p1 n (s1)u1(s1), u2(s2) , un(sn) 表示，简记表示，简记p1 n 。p1 n (s1) 允许取值的 范围称为 允许取值的 范围称为允许策略集合,允许策略集合,用用P1 n 表示表示, p1 n (s1) P1 n 。 由过程的第 。 由过程的第k阶段开始到终止状态的过程为后部子过程(阶段开始到终止状态的过程为后部子过程(k子过程),相应策略子过程),相应策略 pk n (sk)uk(sk), uk+1(sk+1) , un(sn) 称为称为k子过程策略子过程策略简记简记pk n (5)状态转移方程(5)状态转移方程 若给定第若给定第k阶段的状态为阶段的状态为sk，当采取决策变，当采取决策变uk(sk), 则第则第k+1 段的状态段的状态sk+1也就完全确定。上述过程可用也就完全确定。上述过程可用 sk+1Tksk, (uk) （8.1） 表示，上式刻画 ） 表示，上式刻画k段到段到k+1段的状态转移规律，称为段的状态转移规律，称为状态转移方程状态转移方程。 (6)指标函数和最优值函数(6)指标函数和最优值函数 用来衡量所选策略优劣的数量指标称为指标函 数。可分为阶段指标函数和过程指标函数两种。阶段指标函数是对某一阶段 的状态和决策产生的效益值的度量，用 用来衡量所选策略优劣的数量指标称为指标函 数。可分为阶段指标函数和过程指标函数两种。阶段指标函数是对某一阶段 的状态和决策产生的效益值的度量，用vk(sk, uk(sk) )表示; 过程指标函数是 指过程所包含的各阶段的状态和决策所产生的总的效益值，用 表示; 过程指标函数是 指过程所包含的各阶段的状态和决策所产生的总的效益值，用 Vk,nVk,n(sk, uk, sk+1, uk+1, ,sn,un) Vk,n(sk, pk n) 8 动态规划模型要求指标函数满足可分离性，即动态规划模型要求指标函数满足可分离性，即 (sk, uk, sk+1, uk+1, ,sn,un) (sk, uk, Vk+1,n(sk+1, uk+1, ,sn,un) ) 常见的指标函数形式为 1）全过程和任一后部子过程的指标函数等于各阶段指标函数之和(第一类) 2）全过程和任一后部子过程的指标函数等于各阶段指标函数之积(第二类) 最优指标函数 常见的指标函数形式为 1）全过程和任一后部子过程的指标函数等于各阶段指标函数之和(第一类) 2）全过程和任一后部子过程的指标函数等于各阶段指标函数之积(第二类) 最优指标函数 fk (sk,)表示从第表示从第k阶段状态阶段状态sk，采用最优策略，采用最优策略p*k n到过程终止 时的最佳效益值 当 到过程终止 时的最佳效益值 当k=1时，时， fk(s1) 就是从初始状态到全过程结束的整体最优函数就是从初始状态到全过程结束的整体最优函数 , , * , ,11 ()(,)(,) (,) k nk n k nk n kkk nkk nk nkk n pP k nkkkkn pP fsVspopt Vsp opt Vsusus ,11 (,)(,) n k nkkkknjjj jk Vsususvsu ,11 (,)(,) n k nkkkknjjj jk Vsususvsu (8.2) 9 3 动态规划基本原理和基本方程3 动态规划基本原理和基本方程 下面结合例5.1最短路问题介绍动态规划的基本原理。 求A到G的最短路的一种简单方法是穷举法：找出从A到G的所有路线和长度并 加以比较，从而找出最短路。这种方法计算量非常大。 下面介绍动态规划方法，采用逆序递推方法求解 下面结合例5.1最短路问题介绍动态规划的基本原理。 求A到G的最短路的一种简单方法是穷举法：找出从A到G的所有路线和长度并 加以比较，从而找出最短路。这种方法计算量非常大。 下面介绍动态规划方法，采用逆序递推方法求解f () 表示点表示点到到 G最短路的 距离 最短路的 距离 第一步第一步 k=6 开始 状态变量开始 状态变量s6可取可取F1,F2,指标函数指标函数f6(s6)为为F1和和F2表到表到G路长 的距离： 路长 的距离：f6(F1) =4；f6(F2) =3 第二步第二步 k=5，状态变量状态变量s5可取可取E1,E