动态规划 (1)

动态规划

运筹学的一个主要分支 解决多阶段决策过程的最优化的一种方法 多阶段决策过程：一类特殊的活动过程， 这类活动可以按时间顺序分解成若干个相 互联系的阶段，每个阶段都有若干个方案 可供选择。 多阶段决策过程的最优化的目标：达到整 个活动过程的总体效果最优

主要用于解决：最优路径问题， 资源分配问题， 排序问题 ,投资问题， 装载问题 生产计划与库存问题， 生产过程的最优控制等

离散确定型 离散随机型 动态规划 连续确定型 连续随机型

例1 设从甘肃要铺一条煤气管道到北京，途中须经 过三个省：陕西、山西、河北，每省设一个中 最 间站。各省建站可供选择的地点及各段距离如 短 下图，现要求选择一条甘肃到北京的铺管线路， 路 10 5 使总距离最短。 5 ○ 2 问 8 9 ○ 8 多阶段决策问题 ○ 4 6 题 8 9 210 1 3 5 8 ○ ○ ○ ○ ○ 1 4 6 9 10 ○ ○ ○ ○ ○

铺设方案1: 路长=21 策略 铺设方案2: 路长=16

10 ○

7 4 3 甘肃 9 ○ 3 北京 6 1 8 ○ 4 7 ○ 河北 山西 陕西

6 6 ○

7

3 ○

1 ○

一个策略

每一个阶段的决策合在一起构成一个铺设方案 每个策略对应一个路长 寻找路长最短的铺设方案 寻找最优策略

例2 (多阶段资源分配问题) 设有数量为y的某种资源，将它分别投入两种 生产方式A和B,已知收益函数分别是g(x)和 h(x),x为资源投入量。设这种资源用于生产后 还可以回收一部分用于生产，A、B的回收率 分别为a和b( 0≤a≤1,0≤b≤1 ), 问：对总数量为y的资源进行n个阶段的生产， 应如何分配每个阶段投入A、B的资源数量， 才能使总收益最大？ n个阶段的决策问题

例3(生产与存储问题)某工厂生产并销售某种产品。 已知今后四个月市场需求预测及每月生产j个单位 产品的费用如下： 0 c j 3 j j 0 j 1,2, 6月 1 23

32

44

需求 2

每月库存i个单位产品的费用E(i)=0.5i(千元),该 厂最大库存容量为3个单位，每月最大生产能力为 6个单位，计划开始和计划期末库存量都是零，试 制定四个月的生产计划，在满足用户需求条件下， 使总费用最小。 四个阶段的 每个月视为一个阶段， 决策问题 每个阶段都须决定生产几个、库存几个 上一个阶段的决策直接影响下一个阶段的决策

例4(投资决策问题)某公司现有资金Q万 元，在今后5年内决定给A、B、C、D四 个项目投资，这些项目的投资期限、回 报率均不相同，问应如何确定这些项目 每年的投资额，使到第5年末拥有资金的 本利总额最大。5个阶段的决 策问题

例5(设备更新问题)某企业要决定一台设 备未来8年的更新

计划，已预测了第j年 的购买设备的价格为Kj, Gj为设备经过j 年后的残值， Cj为设备连续使用j-1年后 在第j年的维修费(j=1,2, …,8),问应在哪 一年更新设备可使总费用最小每一年视为一个阶段， 每个阶段都须做决策： 继续使用旧设备还是购买新设备？ 8个阶段的决 策问题

上一个阶段的决策直接影响下一个阶段的决策

二、基本概念1、阶段 2、状态 3、决策 4、策略 5、状态转移方程

6、指标函数

1、阶段： 通常用k表示阶段 阶段是指对整个过程的自然划分 划分阶段的规则： 根据时间顺序或空间特征来划分阶段 目的：以便按次序来解优化问题 如最短路问题： 问题分成4个阶段： k=1,2,3,455 ○

k=1:第一阶段，甘肃 线路： 1 2,1 3,1 4 k=3:第三阶段：山西 河北 线路： 5 8,5 9, 6 8,6 9, 7 8, 7 9

10 2 ○ 8 9 8 ○ 4 6 8 9 2 ○ 6 1 7 ○ 3 6 ○ 10 ○4 7 3 甘肃 9 3 北京 ○ 6 1 8 ○ 4 7 ○ 河北 陕西 山西 陕西

各阶段开始时所处的自然状况 2、状态： 状态变量 sk 第k阶段的状态变量

变量

描述各阶段状态的变量 ，简称为状态

Sk ={sk}

第k阶段的状态集合 5

如最短路问题： 第一阶段的状态： 1 ○

第二阶段的状态： ○ 2 ○ 3 ○ 4 s4 第4阶段的状态变量 s4=8 S3 ={s3} ={5,6,7} S5 ={10}

10 2 9 ○ 8 4 6 8 ○ 9 2 ○ 6 1 7 ○ ○ 3 6 10 ○ 4 7 3 甘肃 9 3 北京 ○ 6 1 4 8 7 ○ ○ 河北 山西 陕西8 第4阶段的状态○

5 ○ 8

注：n个阶段的决策过程有个n+1状态变量 sn+1,表示sn演变的结果

例3(生产与存储问题)某工厂生产并销售某种 产品。已知今四个月市场需求预测如下表，又 每月生产j个单位产品的费用为 0 c j 3 j j 0 j 1,2, 6i月 1 2 3 3 2 4 4 g(i)需求 2

每月库存i个单位产品的费用E(i)=0.5i(千元), 该厂最大库存容量为3个单位，每月最大生产 能力为6个单位，计划开始和计划期末库存量 都是零，试制定四个月的生产计划，在满足用 户需求条件下，使总费用最小。 阶段k=1,2,3,4 第k阶段的状态变量sk =第k个月月初的库存量 S1={0}, S2={0,1,2,3}, S3={0,1,2,3},S4={0,1,2,3}

动态规划中的状态应具有以下性质：1、能描述过程的特征 2、具有无后效性 无后效性： 当某阶段的状态给定时，这个阶段以后过 程的演变与该阶段以前各阶段的状态无关 3、状态是直接或间接可以观测的8 48 ○ 9 ○

5

10 ○

北京

河北

8 96 6 ○ 6 17 ○

5 ○

山西

10 2 9 ○ 4 6 2 ○ 1 7 ○ 3 7 3 甘肃 3 4 8 ○ 陕西

当一个阶段的状态确定后，可以作出各种选 3、决策：允许决 择从而演变到下一阶段的某个状态，这种选 策集合 择手段称为决策 决策变量 描述决策的变量 ，简称为决策 u k sk

第k阶段处于状态 sk时的决策变量U k s k 决策变量 uk (sk )允许取值的范围8 10 ○ 4 9 北京 ○ 河北8 ○

5

8 96 6 ○ 6 17 ○

5 ○

u 2 3

山西

10 2 9 ○ 4 6 2 ○ 1 7 ○ 3 7 3 甘肃 3 4 8 ○ 陕西

第2阶段当状态为3时的决策变量 可取值为：5,6,7 决策 3 7 u2 3 7 U 2 3 ={5,6,7}

例3(生产与存储问题)某工厂生产并销售某种产品。 已知今后四个月市场需求预测及每月生产j个单位 产品的费用如下：月 1 2 3 3 2 4 4 需求 2

0 c j 3 j

j 0 j 1,2, 6

每月库存i个单位产品的费用E(i)=0.5i(千元),该 厂最大库存容量为3个单位，每月最大生产能力为 6个单位，计划开始和计划期末库存量都是零，试 制定四个月的生产计划，在满足用户需求条件下， 使总费用最小。 k=1,2,3,4 sk=第k个月月初的库存量 S1={0} S2={0,1,2,3} S3={0,1,2,3} S4={0,1,2,3} 决策变量 uk sk 第k月月初库存量为 sk时产品的产量

U1 0 ={2,3,4,5} U 2 1 ={2,3,4,5} U 3 2 ={0,1,2,3} U 4 1 ={3}

由各阶段的决策组成的序列称为策略 4、策略： p1,n s1 从第一阶段初始状态 s1开始到第n阶段全过程的策略 即p1,n s1 u1 s1 , u2 s2 , un sn

P 策略 ——允许策略集合8 ○

最优策略：使整个问题达到最优效果的策略5

最短路问题： 策略 =铺设方案

如{ 1 3, 3 7, 7 9, 9 10 } p1,4 1 策略：{ 1 2, 2 5, 5 9, 9 10 } p1,4 1 最优策略=最短的铺设路线

8 10 ○ 4 9 北京 ○ 策略 河北

8 9 6 6 ○ 6 1

5 ○

山西

7 ○

10 2 9 ○ 4 6 2 ○ 1 7 ○ 3 7 3 甘肃 3 4 8 ○ 陕西

例3(生产与存储问题)某工厂生产并销售某种产品。已知今四 个月市场需求预测如下表，又每月生产j个单位产品的费用为i月 1 2 3 3 2 4 4 g(i)需求 2

0 c j 3 j

j 0 j 1,2, 6

每月库存i个单位产品的费用E(i)=0.5i(千元),该厂最大库存 容量为3个单位，每月最大生产能力为6个单位，计划开始和计 划期末库存量都是零，试制定四个月的生产计划，在满足用户 需求条件下，使总费用最小。

k=1,2,3,4 sk=第k个月月初的库存量 决策变量 uk 第k阶段产品的产量 一个策略=一个生产方案p1, 4 0 2,3,2,4

费用：23(千元) p1, 4 0 2,5,0,4 费用：21(千元)

最优策略： 使总费用最小的生产方案

策略：由各阶段的决策组成的序列称为策略 p1,n s1 从第一阶段初始状态 s1开始到 原过程第n阶段全过程的策略

的策略

即p1,n s1 u1 s1 , u2 s2 , un sn 原过程： 一个n阶段决策过程，从1

到n叫作问题的原过程 原过程的一个后部子过程：对于任意给定的k(1 ≤ k≤n),从第k段到第 n段的过程称为原过程的一个后部子过程 原过程的一个后部子过程的策略：

决策组成的序列 记为：pk ,n sk

从第k阶段初始状态 sk 开始到第n阶段的

最短路问题：

10 ○

8 4

8 ○ 9 ○

5

北京

河北

8 9 6 6 ○ 6 17 ○

5 ○

山西

10 2 9 ○ 4 6 2 ○ 1 7 ○ 3 7 3 甘肃 3 4 8 ○ 陕西

原过程的一个策略： { 1 3, 3 7, 7 9, 9 10 } p1,4 1 p2, 4 3 { 3 7, 7 9, 9 10 } p3, 4 7 { 7 9, 9 10 p4, 4 9 { 9 10 } p3, 4 5 { 5 8, 8 10

后部子过 程的策略 后部子过 程的策略 后部子过 程的策略

}

}

or{ 5 9,

9 10 }

6、指标函数

最优策略 p *k ,n :使指标函数 Vk ,n sk , pk ,n 达到最优的策略最优值函数 f k sk 从第k阶段状态 s k 开始到过程终f k sk Vk ,n sk , p *k ,n opt Vk ,n s k , pk ,npk , n Pk , n

V1,n s1 , p1,n 在初始状态为 s1时采用原过程策略 p1,n 所对应 的指标函数 Vk ,n s k , pk ,n 在第k阶段状态为 sk时采用后部子过程 策略pk ,n 所对应的指标函数

用于衡量所选定的策略优劣的数量指标称为指标函数

止采用最优策略 p *k ,n 时的指标函数值

f1 s1 初始状态为 s1时全过程采用最优策略 p *1,n 所对应的指标函数值