文档介绍：目录
动态规划原理和模型
一维动态规划求解方法
动态规划在经济和管理中的应用
概述
动态规划所研究的对象是多阶段决策问题
所谓多阶段决策问题,是指一类活动过程,它可以分为若干个相互联系的阶段,在每个阶段都需要做出决策。这个决策不仅影响该阶段的效益,还会决定下一阶段的初始状态。
在多阶段决策过程中,各个阶段的决策就构成了一个决策序列,称之为一个策略。多阶段决策问题就是求一个最优策略,使各阶段效益的总和达到最优。
1957年,美国数学家贝尔曼(Bellman)等人提出了解决多阶段决策过程优化问题的“最优化原理”,建立了数学规划的新分支——动态规划
动态规划是现代企业管理中的一种重要决策方法,可用于最优路径问题、资源分配问题、生产计划和库存问题、投资问题、装载问题、排序问题及生产过程的最优控制等。
一、动态规划的基本概念
:某运输公司拟将一批货物从A地运往E地,其间的交通系统网络如下图所示。图上节点表示地点,边表示两地之间的道路,边上的数字表示两地间的运输费用,求运输费用最低的运输路线。
A
B1
B2
B3
C1
C2
C3
D1
D2
E
4
3
4
5
11
1
7
3
3
5
8
12
6
4
4
6
9
(Stage)
将所给问题的过程,按时间或空间特征分解成若干互相联系的阶段,以便按次序求每阶段的解。
描述阶段的变量称为阶段变量,用字母k表示,,从A到E可分成四个阶段,k=1,2,3,4
(State)
状态就是阶段的起始时的客观条件,通常一个阶段有若干个状态,描述各阶段状态的变量称为状态变量,可用一个数、一组数或一向量来描述,常用sk表示第k阶段的状态变量。
状态变量sk的取值有一定的允许集合或范围,此集合称为状态集合(或状态允许集合),用Sk表示。,S1={A},S2={B1,B2,B3},S3={C1,C2,C3},S4={D1,D2}
状态具有无后效性,即若某阶段状态给定后,该阶段以后过程的演变,不再受以前各阶段状态的影响。
A
B1
B2
B3
C1
C2
C3
D1
D2
E
第2阶段
第3阶段
第4阶段
第1阶段的状态
第2阶段的状态
第1阶段
(Decision)
决策是指某阶段状态给定后,从该阶段演变到下一阶段某一状态的选择。用uk(sk)表示第k阶段,状态为sk时的决策变量。
决策变量的选取限制于某一范围,此范围称为允许决策集合,用Dk(sk)表示第k阶段从状态sk出发的允许决策集合, uk(sk) ∈ Dk(sk)
,u2(B1)表示第2阶段状态为B1时的决策变量, u2(B1)=C1或C3
第2阶段从状态B1 出发的允许决策集合D2(B1)={C1,C3}, 则有u2(B1) ∈ D2(B1)
(Policy)
各阶段决策确定后,组成的一个有序的决策序列就构成了一个策略。用
表示。当k=1时,称为策略;当k≠1时,为由第k阶段开始到最后阶段止的一个子策略,简称后部子策略。
可供选择策略的范围,为允许策略集;使整个问题达到最优效果的策略为最优策略,动态规划方法就是要从允许策略集中找出最优策略。
, 为一个策略。