运筹学8-动态规划
从上面的计算过程中可以看出,在求解的各个阶段,我们利用了 k阶段与k+1阶段之间的递推关系:
一般情况,k阶段与k+1阶段的递推关系式可写为 fk(sk)= opt {vk(sk,uk(sk))+fk+1(uk(sk))} uk Dk(sk) k=n,n-1,…,1
边界条件为 fn+1(sn+1)=0
动态规划的最优性原理
作为整个过程的最优策略具有这样的性 质:即无论过去的状态和决策如何, 对前 面的决策所形成的状态而言, 余下的诸 决策必须构成最优策略。
如何解决这个问题呢?可以采取穷举法。
即把由A到G所有可能的每一条路线的距离都 算出来,然后互相比较找出最短者,相应地得出了 最短路线。这样,由A到G的6个阶段中,一共有 2×3×2×2×2×1=48条不同的路线,比较48条不 同的路线的距离值,才找出最短路线为
A→B1→C2→D1→E2→F2→G
相应最短距离为18。
2.1 动态规划的基本概念
1.阶段 描述阶段的变量称为阶段变量,常用k表示。
阶段的划分,一般是根据时间和空间的自然特 征来划分,但要便于把问题的过程能转化为多 阶段决策的过程。
2.状态 描述过程状态的变量称为状态变量。它可用
一个数、一组数或一向量(多维情形)来描述。 常用Sk表示第k阶段的状态变量。
第8章 动态规划的基本方法
本章篇目
8.1 • 多阶段决策过程及实例 8.2 • 动态规划的基本概念和基本方程 8.3 • 动态规划的最优性原理和最优性定理 8.4 • 动态规划和静态规划的关系
第1节 多阶段决策过程及实例
把一个问题可看作是一个前后关联具有链状结构 的多阶段过程(如图所示)就称为多阶段决策过程, 也称序贯决策过程。这种问题就称为多阶段决策过
3.决策 常用Dk(sk)表示第k阶段从状态sk出发的允许
决策集合,显然有uk(sk)∈Dk(sk)
4.策略 由每段的决策按顺序排列组成的决策函数序
列{uk(sk),…,un(sn)}称为k子过程策略,简称 子策略,记为pk,n(sk)。即
pk,n(sk)={uk(sk),uk+1(sk+1),…,un(sn)}
同理,从E2和E3出发,则有
ቤተ መጻሕፍቲ ባይዱ似地,可算得
且u1(A)=B1。于是得到从起点A到终点G的最短距离为18。 为了找出最短路线,再按计算的顺序反推之,可求出最优决策函
数序列{uk},即由u1(A)=B1,u2(B1)=C2,u3(C2)=D1,u4(D1)=E2,u5(E2)= F2,u6(F2)=G组成一个最优策略。因而,找出相应的最短路线为
Vk,n(sk,uk,sk+1,…,sn+1)=ψk[sk,uk,Vk+1,n
(sk+1,…,sn+1)]
常见的指标函数的形式如下
(1)过程和它的任一子过程的指标是它所包 含的各阶段的指标的和。即
n
Vk,n(sk,uk,…,sn+1)= vj(sj,uj) jk
(2)过程和它的任一子过程的指标是它所包 含的各阶段的指标的乘积。即
n
Vk,n(sk,uk,…,sn+1)= vj(sj,uj) jk
指标函数的最优值,称为最优值函数,记为 fk(sk) fk(sk)= opt Vk,n(sk,uk,…,sn+1)
{uk,, un
2.2 动态规划的基本思想和基本方程
生活中的常识告诉我们,最短路线有一个重要特性:如果由起点 A经过P点和H点而到达终点G是一条最短路线,则由点P出发经过H点 到达终点G的这条子路线,对于从点P出发到达终点的所有可能选择 的不同路线来说,必定也是最短路线。
上述最短路线问题的计算过程,也可借助图形直观 简明的表示出来。
逆序解法
顺序解法
动态规划逆序解法的基本方程
边界条件fn+1(sn+1)=0。式中sk+1=Tk(sk,uk)。 动态规划顺序解法的基本方程
边界条件为 0(s1)=0。 式中sk=Trk(sk+1,uk)。
第3节
动态规划的最优性原理 和最优性定理
程。
多阶段决策问题举例
最短路线问题 如下图,给定一个线路网络,两点之间连线上的数
字表示两点间的距离(或费用),试求一条由A到G 的铺管线路,使总距离为最短(或总费用最小)。
第2节
动态规划的基本概念和基 本方程
如图所示的线路网络
问题的要求是:在各个阶段选取一个恰当的 决策,使由这些决策组成的一个决策序列所 决定的一条路线,其总路程最短。
当k=1时,此决策函数序列称为全过程的一个策 略,简称策略,记为p1,n(s1)。
p1,n(S1)={u1(s1),u2(s2),…,un(sn)}
5.状态转移方程 若给定第k阶段状态变量sk的值,如果该段的
决策变量uk一经确定,第k+1阶段的状态变量 sk+1的值也就完全确定。即sk+1的值随sk和uk的 值变化而变化。这种确定的对应关系,记为
这种递推关系式称为动态规划的基本方程。
动态规划方法的基本思想归纳如下:
(1)动态规划方法的关键在于正确地写出基本的 递推关系式和恰当的边界条件(简言之为基本 方程)。
(2)在多阶段决策过程中,动态规划方法是既把 当前一段和未来各段分开,又把当前效益和未 来效益结合起来考虑的一种最优化方法。
(3)在求整个问题的最优策略时,由于初始状态 是已知的,而每段的决策都是该段状态的函数, 故最优策略所经过的各段状态便可逐次变换得 到,从而确定了最优路线。
下面按照动态规划的方法,将例1从最后一段开始计算,由后向前逐步 推移至 A点。 当k=6时,由 F1到终点G只有一条路线,故 f6(F1)=4。同理, f6(F2)=3。 当k=5时,出发点有 E1、E2、E3 三个。若从 E1出发,则有两个选择: ①至F1;②至F2则
其相应的决策为 us ( E1 ) = F1 这说明,由 E1 至终点 G的最短距离为 7,其最短路线是
sk+1=Tk(sk,uk)
6.指标函数和最优值函数
用来衡量所实现过程优劣的一种数量指标,称 为指标函数。常用Vk,n表示之。即
Vk,n=Vk,n(sk,uk,sk+1,…,sn+1),k=1,2,…,n
对于要构成动态规划模型的指标函数,应具有 可分离性,并满足递推关系。即Vk,n可以表示 为sk、uk、Vk+1,n的函数。记为