当前位置:首页 >> 管理学 >>

运筹学第5章:动态规划


管理与人文学院
1999,4 ,

忻展红

第五章 动态规划
不要过河拆桥

动态规划 Dynamic programming
五十年代贝尔曼(B. 五十年代贝尔曼 E. Bellman)为代表的研究成果 为代表的研究成果 属于现代控制理论的一部分 以长远利益为目标的一系列决策 最优化原理, 最优化原理,可归结为一个递推公式
2 E 1 1 F 2 7 3 G 4 K J I H 3 3 4 2 5 2 N M L 5 2 8 4 P O 2 1 B

5.1 动态规划的最优化原理及其算法
5.1.1 求解多阶段决策过程的方法 例5.1.1 最短路问题
A 3 D 5 4 C 4 7

2

决策树法
H E I C I F J A I F J D J G K

可以枚举出20条路径,其中最短的路径长度为 可以枚举出 条路径,其中最短的路径长度为16 条路径
3

例5.1.1 最短路问题
表现为明显的阶段性 一条从A 到B 的最短路径 一条从 中的任何一段都是最短的
i B 设Si 表示由 点到 点的最短路 径的长度 则有 dAC + SC SA = min d + S AD D
A 16 4 C 12 5 4 7 3 D 14 F 8 E 9 H 10

2 1 1 2 7 3 G 11

3 3 L 7 5 2 M 4 8 4 N 5 P 1 O 2 2 1 B 0

I 8

4 2

因此我们可以从 向回搜索最短路 因此我们可以从B向回搜索最短路 因此我们可以从 标记法 标记法 如何找出最短路径 如何找出最短路径

J 6

5 2

4

最优性原理 "最优策略的一部分也是最优的

K 7 3 2 1
4

6

5

4

阶段

5.1.2 动态规划的基本概念及递推公式
状态
– – – 最短路问题中, 最短路问题中,各个节点就是状态 生产库存问题中, 生产库存问题中,库存量是状态 物资分配问题中,剩余的物资量是状态 物资分配问题中,

控制变量(决策变量 控制变量 决策变量) 决策变量
– 最短路问题中,走哪条路 最短路问题中, – 生产库存问题中,各阶段的产品生产量 生产库存问题中, – 物资分配问题中,分配给每个地区的物资量 物资分配问题中,

阶段的编号与递推的方向 阶段的编号与递推的方向 编号与递推的
– 一般采用反向递推,所以阶段的编号也是逆向的 一般采用反向递推, – 当然也可以正向递推
5

动态规划的步骤
1,确定问题的阶段和编号 , 2,确定状态变量 ,
– 用 Sk 表示第 k 阶段的状态变量及其值

3,确定决策变量 ,
– 用 xk 表示第 k 阶段的决策变量,并以 xk*表示该阶段的最优 阶段的决策变量, 表示该阶段的最优 决策

4,状态转移方程 , sk-1= g(sk, xk) 反向编号 sk+1= g(sk, xk) 正向编号 5,直接效果 , – 直接一步转移的效果 dk(sk, xk) 6,总效果函数 ,
– 指某阶段某状态下到终端状态的总效果,它是一个递推公式 指某阶段某状态下到终端状态的总效果,
fk (sk , xk ) = hk (dk (sk , xk ), fk1(sk1, xk1 )
6

动态规划的步骤
– hk 是一般表达形式,求当前阶段当前状态下的阶段最优 是一般表达形式, 总效果
(1) 如最短路问题,是累加形式,此时有 如最短路问题,是累加形式,

终端的边际效果一般为 f0(s0, x0)=0 (2)如串联系统可靠性问题,是连乘形式,此时有 如串联系统可靠性问题, 如串联系统可靠性问题 是连乘形式,

终端的边际效果一般为 f0(s0,x0)=1

从第1阶段开始,利用边际效果和边界条件, 从第1阶段开始,利用边际效果和边界条件,可以递推到最后 阶段 7

5.2 动态规划模型举例
5.2.1 产品生产计划安排问题
某工厂生产某种产品的月生产能力为10件 例1 某工厂生产某种产品的月生产能力为 件,已知今后四个月 的产品成本及销售量如表所示.如果本月产量超过销售量时, 的产品成本及销售量如表所示.如果本月产量超过销售量时,可 以存储起来备以后各月销售,一件产品的月存储费为2元 以存储起来备以后各月销售,一件产品的月存储费为 元,试安 排月生产计划并做到: 排月生产计划并做到: 1,保证满足每月的销售量,并规定计划期初和期末库存为零; ,保证满足每月的销售量,并规定计划期初和期末库存为零; 2,在生产能力允许范围内,安排每月生产量计划使产品总成本 ,在生产能力允许范围内, (即生产费用加存储费 最低. 即生产费用加存储费)最低 即生产费用加存储费 最低.

8

例1 产品生产计划安排
设xk为第 阶段生产量,则有直接成本 为第k阶段生产量 阶段生产量, dk(sk, xk)= ck xk+2sk 状态转移公式为 sk-1= sk+ xk- yk 总成本递推公式

第一阶段: 即第 月份) 即第4月份 第一阶段:(即第 月份 由边界条件和状态转移方程 s0=s1+x1-y1= s1+x1–6=0 得 s1+x1= 6 或 x1= 6 – s1 估计第一阶段,即第 月份初库存的可能状态: 月份初库存的可能状态 估计第一阶段,即第4月份初库存的可能状态: s1 ∈[0,5] 第一阶段
9

第一阶段最优决策表
s1 0 1 2 3 4 5 x1 6 5 4 3 2 1 f1(s1, x1) 456 382 308 234 160 86

第二阶段:最大可能库存量 7 件 第二阶段: 由状态转移方程: 由状态转移方程: s1=s2+x2-12≥0 及 ≥ x2≤10,可知 s2∈[2,7],min x2=5 , , 由阶段效果递推公式有: 由阶段效果递推公式有: f2(2,10)=d2(2,10)+f1*(0,6) =2×2+80×10+456=1260 × × 得第二阶段最优决策表, 得第二阶段最优决策表,如下 阶段最优决策表

5 6 7 s2 x2 2 3 4 5 1026* 6 948* 954 7 870* 876 882 s1=0 s1=1 s1=2

8

9 1182* 1110 1038 966 894 s1=4

10

x2* f2(s2,x2*) 1260 1182 1104 1026 948 870
10

1104* 1032 960 888 s1=3

1260* 10 1188 9 1116 8 1044 7 972 6 900 5 s1=5

第二阶段最优决策表

s2 2 3 4 5 6 7

x2* f2(s2,x2*) 10 1260 9 1182 8 1104 7 1026 6 948 5 870

第三阶段:最大可能库存量 4 件 第三阶段: 由状态转移方程: 由状态转移方程: s2=s3+x3-7≥2 及 ≥ x3≤10,可知 s3∈[0,4],min x3=5 , , 由阶段效果递推公式有: 由阶段效果递推公式有: f3(1,10)=d3(1,10)+f2*(4,8) =2×1+72×10+1104=1826 × × 得第三阶段最优决策表,如下 得第三阶段最优决策表, 阶段最优决策表
9 1908 1832 1756 1680 1604 s2=6 10 1902* 1826* 1750* 1674* 1598* s2=7 x3* f3(s3,x3*) 10 10 10 10 10 1902 1826 1750 1674 1598
11

5 6 7 8 s3 x3 0 1 1838 2 1768 1762 3 1698 1692 1686 4 1628 1622 1616 1610 s2=2 s2=3 s2=4 s2=5

第三阶段最优决策表

第四阶段:初始库存量 s4=0 第四阶段: 由状态转移方程: 由状态转移方程: s3=s4+x4-6≥0 ≥ 可知 x4≥6,由阶段效果递推公式有: ,由阶段效果递推公式有: f4(0,6)=d4(0,6)+f3*(0,10) =70×6+1902=2322 × 得第四阶段最优决策表, 得第四阶段最优决策表,如下 阶段最优决策表

回 溯 得 此 表
12

生产–库存管理问题 连续变量) 库存管理问题(连续变量 例2 生产 库存管理问题 连续变量
设某厂计划全年生产某种产品A.其四个季度的订货量分别为 设某厂计划全年生产某种产品 .其四个季度的订货量分别为600 公斤, 公斤 公斤, 公斤和 公斤和1200公斤.已知生产产品 的生产费 公斤. 公斤,700公斤,500公斤和 公斤 已知生产产品A的生产费 用与产品的平方成正比,系数为0.005.厂内有仓库可存放产品, 用与产品的平方成正比,系数为 .厂内有仓库可存放产品, 存储费为每公斤每季度1元 求最佳的生产安排使年总成本最小. 存储费为每公斤每季度 元.求最佳的生产安排使年总成本最小.

解:四个季度为四个阶段,采用阶段编号与季度顺序一致. 四个季度为四个阶段,采用阶段编号与季度顺序一致. 设 sk 为第 季初的库存量,则边界条件为 s1=s5=0 为第k季初的库存量 季初的库存量, 为第k季的生产量 季的生产 为第k季的订货量 季的订货量; 设 xk 为第 季的生产量,设 yk 为第 季的订货量; sk ,xk ,yk 都取实数,状态转移方程为 sk+1=sk+xk - yk 都取实数, 仍采用反向递推, 仍采用反向递推,但注意阶段编号是正向的 目标函数为

f1( x) = min ∑(0.005xi2 + si )
x1 , x2 , x3 , x4 i=1
13

4

生产–库存管理问题 连续变量) 库存管理问题(连续变量 例2 生产 库存管理问题 连续变量
第一步:(第四季度 总效果 f4(s4,x4)=0.005 x42+s4 第一步: 第四季度) 第四季度 由边界条件有: 由边界条件有: s5= s4 + x4 – y4=0,解得:x4*=1200 – s4 ,解得: 将x4*代入 f4(s4,x4)得: 代入 得 f4*(s4)=0.005(1200 – s4)2+s4=7200 –11 s4+0.005 s42 第二步: 第三 四季度) 第三, 第二步:(第三,四季度 总效果 f3(s3,x3)=0.005 x32+s3+ f4*(s4) 将 s4= s3 + x3 – 500 代入 f3(s3,x3) 得:

14

生产–库存管理问题 连续变量) 库存管理问题(连续变量 例2 生产 库存管理问题 连续变量
第三步: 第二 第二, 四季度) 第三步:(第二,三,四季度 总效果 f2(s2,x2)=0.005 x22+s2+ f3*(s3) 将 s3= s2 + x2 - 700 代入 f2(s2,x2) 得:

注意:最优阶段总效果仅是当前状态的函数,与其后的决 注意:最优阶段总效果仅是当前状态的函数, 策无关
15

生产–库存管理问题 连续变量) 库存管理问题(连续变量 例2 生产 库存管理问题 连续变量
第四步: 第一 第一, 四季度) 第四步:(第一,二,三,四季度 总效果 f1(s1,x1)=0.005 x12+s1+ f2*(s2) 将 s2= s1 + x1 – 600= x1 – 600 代入 f1(s1,x1) 得:

由此回溯:得最优生产 库存方案 由此回溯:得最优生产–库存方案 回溯 x1*=600,s2*=0; x2*=700,s3*=0; x3*=800,s4*=300; , ; , ; , ; x4*=900. .
16

5.2.2 资源分配问题
某公司有9个推销员在全国三个不同市场推销货物 个推销员在全国三个不同市场推销货物, 例3 某公司有 个推销员在全国三个不同市场推销货物,这三个市 场里推销人员数与收益的关系如下表, 场里推销人员数与收益的关系如下表,试作出使总收益最大的分 配方案. 配方案.

解:设分配人员的顺序为市场1, 2, 3,采用反向阶段编号. 设分配人员的顺序为市场 ,采用反向阶段编号. 为第k阶段尚未分配的人员数 阶段尚未分配的人员数, 设 sk 为第 阶段尚未分配的人员数,边界条件为 s3=9 为第k阶段分配的推销人员数 仍采用反向递推, 阶段分配的推销人员数; 设 xk 为第 阶段分配的推销人员数;仍采用反向递推, 状态转移方程为 sk–1=sk – xk 目标函数为

f3 ( x) = min ∑d( xi )
x1 , x2 , x3 i=1
17

3

第一阶段: 例3 第一阶段:给第三市场分配
s1 有0~9种可能,第一阶段最优决策表如下: 种可能,第一阶段最优决策表如下: 种可能

为什么与例 的第一阶段的表有差别? 为什么与例1 的第一阶段的表有差别?
18

第二阶段: 例3 第二阶段:给第二市场分配

s2 有0~9种可能,第二阶段最优决策表如下: 种可能,第二阶段最优决策表如下: 种可能

19

第三阶段: 例3 第三阶段:给第一市场分配

由边界条件 s3=9,第三阶段最优决策表如下: ,第三阶段最优决策表如下:

x3 s3 9

0 1 2 3 4 5 6 7 8 9 x3* f3* 211 213 218 217 215 208 206 202 201 200 2 218

得决策过程:x3*=2, x2*=0, x1*=7, f3*=218 得决策过程: 市场1 市场3 即 市场 分配 2人,市场 不分配 ,市场 分配 7人 人 市场2 人 最优解与分配的顺序有关吗? 最优解与分配的顺序有关吗?
20

5.2.2 资源分配问题
例4 项目选择问题
某工厂预计明年有A,B,C,D四个新建项 四个新建项 某工厂预计明年有 目,每个项目的投资额 wk及其投资后的 如下表所示.投资总额为30万元 万元, 收益 vk如下表所示.投资总额为 万元, 问如何选择项目才能使总收益最大. 问如何选择项目才能使总收益最大.

上述问题的静态规划模型如下: 上述问题的静态规划模型如下:

max f ( x) = ∑vk xk
k

∑wk xk ≤ 30 k 0 k 项未入选 xk = 1 k 项入选

这是一类0-1规划问题 这是一类 规划问题 该问题是经典的旅行背包问题 该问题是经典的旅行背包问题 (Knapsack) 该问题是 NP-complete

21

例4 项目选择问题
解:设项目选择的顺序为A, B, C, D; 设项目选择的顺序为 1,阶段 k=1, 2, 3, 4 分别对应 D, C, B, A项目的选择过程 , 项目的选择过程 2,第 k 阶段的状态 sk,代表第 k 阶段初尚未分配的投资额 , 3,第 k 阶段的决策变量 xk,,代表第 k 阶段分配的投资额 , 4,状态转移方程为 sk–1= sk– wk xk , 5,直接效益 dk(sk ,xk)= vk 或 0 , 6,总效益递推公式 ,

该问题的难点在于各阶段的状态的确定,当阶段增加时, 该问题的难点在于各阶段的状态的确定,当阶段增加时,状 态数成指数增长.下面利用决策树来确定各阶段的可能状态. 态数成指数增长.下面利用决策树来确定各阶段的可能状态.
22

23

第一阶段(项目D) 例4 第一阶段(项目 )的选择过程 s1<8 时,x1只能取 ;w1=8, v1=5 只能取0;
s1 3 5 8 15 18 20 30 x1 d1(s1, x1) s0= s1-w1x1 f0(s0, x0*) f1(s1, x1*) 0 0 3 0 0 0 0 5 0 0 0 0 8 0 1 5 0 0 5 0 0 15 0 1 5 7 0 5 0 0 18 0 1 5 10 0 5 0 0 20 0 1 5 12 0 5 0 0 30 0 1 5 22 0 5 条件 x4=x2=1 x3=0 x4=x3=1 x2=0 x3=x2=1 x4=0 x3=x2=0 x4=1 x4=x3=0 x2=1 x4=x2=0 x3=1 x4=x3 =x2=0

24

第二阶段(项目C) 例4 第二阶段(项目 )的选择过程

25

第三阶段(项目B) 例4 第三阶段(项目 )的选择过程 w3=10
s3 15 30 x3 d3(s3, x3) s2= s3-w3x3 f2(s2, x2*) f3(s3, x3*) 0 0 15 9 9* 1 8 5 0 8 0 0 30 14 14 1 8 20 14 22*

v3=8 条件 x4=1 x4=0
v4=12 条件

第四阶段(项目 ) 第四阶段(项目A)的选择过程
s4 30 x4 0 1

w4=15 d4(s4, x4) s3= s4-w4x4 f3(s3, x3*) f4(s4, x4*) 0 30 22 22* 12 15 9 21

项目 A B C D

决策 x4=0 x3=1 x2=1 x1=1 总额

投资额 0 10 12 8 30

直接收益 vk 0 8 9 5 22

26

5.2.3 串联系统可靠性问题
三部机器串联生产某种产品,由于工艺技术问题, 例5 有 A, B, C 三部机器串联生产某种产品,由于工艺技术问题,产品 常出现次品.统计结果表明, 常出现次品.统计结果表明,机器 A, B, C 产生次品的概率分别为 pA=30%, PB=40%, PC=20%, 而产品必须经过三部机器顺序加工才能 完成.为了降低产品的次品率, 万元进行技术改造, 完成.为了降低产品的次品率,决定拨款 5 万元进行技术改造,以 便最大限度地提高产品的成品率指标.现提出如下四种改进方案: 便最大限度地提高产品的成品率指标.现提出如下四种改进方案: 方案1: 不拨款,机器保持原状; 方案 不拨款,机器保持原状; 方案2: 加装监视设备, 万元; 方案 加装监视设备,每部机器需款 1 万元; 方案3: 加装设备, 万元; 方案 加装设备,每部机器需款 2 万元; 方案4: 同时加装监视及控制设备, 万元; 方案 同时加装监视及控制设备,每部机器需款 3 万元; 采用各方案后,各部机器的次品率如下表. 采用各方案后,各部机器的次品率如下表.

不拨款 拨款 1 万元 拨款 2 万元 拨款 3 万元

A 30% 20% 10% 5%

B 40% 30% 20% 10%

C 20% 10% 10% 6%

27

例5 串联机器可靠性问题
为三台机器分配改造拨款,设拨款顺序为A, 解:为三台机器分配改造拨款,设拨款顺序为 B, C,阶段序号反 , 拨款的效果. 向编号为 k,即第一阶段计算给机器 C 拨款的效果. , 设 sk 为第 k 阶段剩余款,则边界条件为 s3=5; 阶段剩余款, ; 阶段的拨款额 拨款额; 设 xk 为第 k 阶段的拨款额; 状态转移方程为 sk-1=sk-xk; 目标函数为 max R=(1-PA)(1-PB)(1-PC) 仍采用反向递推

第一阶段 :对机器 C 拨款的效果 R1(s1,x1)=d1(s1,x1)× R0(s0,x0)= d1(s1,x1) ×
x1 s1 0 1 2 3 4 5 0 0.8 0.8 0.8 0.8 0.8 0.8 1 2 3 R1 (s1, x1*) 0 0.8 1 0.9 1, 2 0.9 3 0.94 3 0.94 3 0.94 x1*

0.9 0.9 0.9 0.9 0.9

0.9 0.9 0.9 0.9

0.94 0.94 0.94

28

第二阶段最优决策表

第二阶段 :对机器 B, C 拨款 ,
的效果 由于机器 A 最多只需 3 万元, 万元, 故 s2 ≥ 2 递推公式: 递推公式:

x1 x1* s1 0 1 2 3 4 5
x2 s2 2 3 4 5

R1 (s1, x1*) 0 0.8 1 0.9 1, 2 0.9 3 0.94 3 0.94 3 0.94
0 0.54 0.564 0.564 0.564 1 0.63 0.63 0.658 0.658 2

R2(s2,x2)=d2(s2,x2)× R1(s1,x1*) × 例:R2(3,2)=d2(3,2)× × R1(1,1)=(1-0.2) ×0.9=0.72 得第二阶段最优决策表

3

x2* 2 2,3 3 3

0.64 0.72 0.72 0.72 0.81 0.752 0.81

R2 (s2, x2*) 0.64 0.72 0.81 0.81

29

第二阶段最优决策表
x2 x2* s2 2 3 4 5 R2 (s2, x2*) 2 0.64 2,3 0.72 3 0.81 3 0.81

第三阶段 :对机器 A, B, C 拨 ,
款的效果 边界条件: 边界条件:s3 = 5 递推公式: 递推公式:

R3(s3,x3)=d3(s3,x3)× R2(s2,x2*) × 例:R3(5,3)=d3(5,3)× × R2(2,2)=(1-0.05) ×0.64=0.608 得第三阶段最优决策表

0 1 2 3 s3 x3 x3* R3(s3, x3*) 5 0.567 0.648 0.648 0.608 1,2 0.648
有多组最优解. 回溯 :有多组最优解. I:x3=1, x2=3, x1=1, R3=0.8 ×0.9 ×0.9=0.648 :

II:x3=2, x2=2, x1=1, R3= 0.9×0.8×0.9=0.648 : × × III: x3=2, x2=3, x1=0, R3= 0.9×0.9×0.8 =0.648 × ×
30

例6 用动态规划解非线性规划

m f ( x) = x1 + x2 + x3 ax x1 + x2 + x3 = 27 x1, x2, x3 ≥ 0

31

动态规划总结
二大类:生产-库存问题;资源分配问题 二大类:生产 库存问题 库存问题;
. 一 生产- 库存问题 状态转移公式 sk1 = sk + xk yk 离散型 状态和控制变量 连续型 . 二 资源分配问题 状态转移公式 sk1 = sk xk 累加 目标函数 累乘 离散型 状态和控制变量 连续型
32

赞助商链接
相关文章:
运筹学及应用案例-动态规划
运筹学及应用案例-动态规划_经济/市场_经管营销_专业资料。运筹学-动态规划徐州工程学院数理学院 案例分析报告 课程名称 案例分析题目 专班姓学业级名号 运筹学及应...
运筹学--第七章 动态规划
运筹学动态规划 29页 5财富值 第7章 动态规划 25页 免费如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行反馈。 ...
运筹学实验_动态规划
运筹学实验_动态规划_城乡/园林规划_工程科技_专业资料。实验二用 MATLAB 解决...5 6 6 6 0 4 5 6 6 6 0 1 2 3 4 5 6 6 6 6 第三阶段: 设...
运筹学之动态规划(东南大学)
运筹学动态规划(东南大学)_管理学_高等教育_教育专区。运筹学 ...对于第 三,四季度才能上市的产品需付存储费,每季每千件的存储费为 0.5(千...
运筹学各章的作业题答案
《管理运筹学》各章的作业 ---复习思考题及作业题 第一章 绪论 复习思考题 ...第五章 动态规划 思考题 主要概念及内容: 多阶段决策过程;阶段及阶段变量;状态...
动态规划习题详解
动态规划动态规划运筹学的一个分支,它是解决多阶段决策过程最优化问题的一种...下面第 5 年度开始,用逆推归纳法进行计算. 1)k=5 时,有 f 5 ( s5 ) ...
动态规划讲解大全(含例题及答案)
动态规划讲解大全动态规划(dynamic programming)是运筹学的一个分支,是求解决策...5,4}; //5 个物体各自的重量 int v[] = {6,3,5,4,6}; //5 个...
运筹学动态规划
MATLAB 基础及在运筹学中的应用 第 7 章 动态规划动态规划是 Bellman 在 1957 年提出的解多阶决策问题的方法,在那个时期,线性规划很 流行,它是研究静态问题的,...
运筹学运输问题、整数规划、目标规划和动态规划_图文
运筹学运输问题、整数规划、目标规划和动态规划_经济学_高等教育_教育专区。运筹学-线性规划案例 整数规划案例一 案例二 案例三 动态规划案例四:某开发区养老保险...
动态规划--运筹学课程设计
运筹学——动态规划 80页 免费 运筹学—第七章 动态规划... 52页 1下载券...湖南农业大学 综合设计报告 综合设计 动态规划算法 学生姓名:曾俊扬学号:...
更多相关标签: