第五节动态规划 动态规划是运筹学的一个分支,它是解决多 阶段决策过程最优化的一种数学方法.大约产生 于50年代.1951年美国数学家贝尔曼 (R. Bellman)等人,根据一类多阶段决策问题的 特点,把多阶段决策问题变换为一系列互相联系 单阶段问题,然后逐个加以解决。与此同时,他 提出了解决这类问题的“最优性原理”,研究了 许多实际问题,从而创建了解决最优化问题的 种新的方法--动态规划.他的名著“动态规划” 于1957年出版,该书是动态规划的第一本著作
第五节 动态规划 动态规划是运筹学的一个分支，它是解决多 阶段决策过程最优化的一种数学方法．大约产生 于50年代．1951年美国数学家贝尔曼 (R．Bellman)等人，根据一类多阶段 决策问题的 特点，把多阶段决策问题变换为一系列互相联系 单阶段问题，然后逐个加以解决。与此同时，他 提出了解决这类问题的“最优性原理”，研究了 许多实际问题，从而创建了解决最优化问题的一 种新的方法——动态规划．他的名著“动态规划” 于1957年出版，该书是动态规划的第一本著作．
动态规划模型的分类,根据多阶段决策过程的时间参量是离散的还是连续 的变量:;过程分为离散决策过程和连续决策过程.根据决策过程的演变是确定 性的还是随杋性的,过程又可分为确定性决策过程和随机性决策过程.组合起 来就有离散确定性、离散随杋性、连续确定性、连续随杋性四种决策过程模 型.本部分主要研究离散决策过程,介绍动态规划的基本概念、理论和方法 并通过几个典型的问题来说明它的应用,这些都是整个动态规划的基本内容 根据多阶段决策过程的 根据决策过程的 时间参量 演变 确定性 随机性 离散 连续 决策过程 决策过程 决策过程 决策过程 离散确定性)离散确定性 续确定性 连续随机性 决策过程 决策过程 决策过程 决策过程
动态规划模型的分类，根据多阶段决策过程的时间参量是离散的还是连续 的变量；过程分为离散决策过程和连续决策过程．根据决策过程的演变是确定 性的还是随机性的，过程又可分为确定性决策过程和随机性决策过程．组合起 来就有离散确定性、离散随机性、连续确定性、连续随机性四种决策过程模 型．本部分主要研究离散决策过程，介绍动态规划的基本概念、理论和方法， 并通过几个典型的问题来说明它的应用，这些都是整个动态规划的基本内容． 离散 决策过程 连续 决策过程 根据多阶段决策过程的 时间参量 根据决策过程的 演变 确定性 决策过程 随机性 决策过程 离散确定性 决策过程 离散确定性 决策过程 连续确定性 决策过程 连续随机性 决策过程
1多阶段决策过程及实例 有一批军用物资需要从A地调运到E地,如下图所示,请求出 条从A到E的一条线路,使总的运输距离最短。图中线条上的数字为距离。 80ky A B2 4 A地 B地 C地 D地 E地
引例——有一批军用物资需要从A 地调运到E地，如下图所示，请求出一 条从 A 到 E 的一条线路，使总的运输距离最短。图中线条上的数字为距离。 A B2 C2 E B1 B3 C1 C3 D1 D2 4 3 5 8 10 12 14 18 10 12 9 4 5 8 9 7 7 3 4 11 1 多阶段决策过程及实例 B 地 C 地 D 地 E 地 A 地
①0 (B2 18 在生产和科学实验中,有一类活动的过程,由于它的特殊性,可将过程分为若干个 互相联系的阶段,在它的每一个阶段都需要作出决策,才能使整个过程达到最好的活动 效果.因此,各个阶段决策的选取不是任意确定的,它依赖于当前面临的状态,又影响 到以后的决策 如果一个问题的过程可以化分为若干个互相联系的阶段,而且每个阶段都需要作出 决策,而且当每个阶段的决策都确定之后,整个问题也就确定了,那么,这个问题就叫 做一个多阶段决策问题。动态规划就是解决这类问题的一个重要的数学方法
在生产和科学实验中，有一类活动的过程，由于它的特殊性，可将过程分为若干个 互相联系的阶段，在它的每一个阶段都需要作出决策，才能使整个过程达到最好的活动 效果．因此，各个阶段决策的选取不是任意确定的，它依赖于当前面临的状态，又影响 到以后的决策。 A B2 C2 E B1 B3 C1 C3 D1 D2 4 3 5 8 10 12 14 18 10 12 9 4 5 8 9 7 7 3 4 11 如果一个问题的过程可以化分为若干个互相联系的阶段，而且每个阶段都需要作出 决策，而且当每个阶段的决策都确定之后，整个问题也就确定了，那么，这个问题就叫 做一个多阶段决策问题。动态规划就是解决这类问题的一个重要的数学方法
10 12 A B2 18 B 如上图所示的线路网络,求A到E点的最短路线问题是动态规划中一个较为直 观的典型例子,现通过讨论它的解法,来说明动态规划方法的基本思想,并阐述它的 基本概念 如上图可知,从A点到E点可以分为4个阶段.从A到B为第一阶段,从B到C为第二 阶段.从D到E为第四阶段
如上图所示的线路网络，求 A 到 E 点的最短路线问题是动态规划中一个较为直 观的典型例子．现通过讨论它的解法，来说明动态规划方法的基本思想，并阐述它的 基本概念。． A B2 C2 E B1 B3 C1 C3 D1 D2 4 3 5 8 10 12 14 18 10 12 9 4 5 8 9 7 7 3 4 11 如上图可知，从A点到E点可以分为4个阶段．从A到B为第一阶段，从B到C为第二 阶段…从D到E为第四阶段