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

运筹五 动态规划


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

1

动态规划 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
2

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

L

5 2 O 2 1 P B

M

8 4

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

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

例5.1.1 最短路问题
? 表现为明显的阶段性 ? 一条从A 到B 的最短路径 中的任何一段都是最短的
设Si 表示由i点到B点的最短路 径的长度 则有 ? d AC ? SC ? S A ? min? ?d ? S ? ? D? ? AD
4 A 16 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 动态规划的基本概念及递推公式
1、基本概念 1)阶段;把多阶段决策问题分为若干个相互联系的阶段,常用k表示 2)状态:每一阶段开始时所处的状态。某一阶段某一状态用状态变量s k
表示,第k阶段的所有状态集合用S k表示,各阶段所有状态集合用S表示,则 s k? S k?S, 动态规划中的状态必须满足无后效性。

3)决策:某一阶段k某一状态s k所作出的决策用决策变量x k(s k)表示,

第k阶段状态s k的允许决策集合用D k(s k)表示,第k阶段各状态的允许决 策集合用D k表示,所有各阶段各状态的允许决策集合用D 表示。则有 x k(s k)? D k(s k)? D k ? D

4)策略:指某一阶段某一状态到终点的顺序排列的决策组合的集合。用
Pk(s k)={ x k(s k),x k-1(s k-1),…,x 1(s 1)} 表示从第k阶段状态s k出发到终点的一个子策略。从第k阶段状态s k出发 到终点的允许策略集合为P。则Pk(s k)?P。

5)状态转移方程:反映相邻两个阶段的状态和决策变量之间的相互关系
s k-1=Tk[s k,x k(s k)] = g(sk, xk)
5

5.1.2 动态规划的基本概念及递推公式
6)直接效果函数:它是状态变量s k和决策变量x k(s k)的函数,记为:
d k[s k,x k(s k)]。

7)总效果函数:从第k阶段状态s k出发到终点的子策略
Pk(s k)的函数。记为:Vk= Vk [Pk(s k)]

8)最优效果函数:表示在某一阶段某一状态下,采取最优策略后到终点的最优效
果值。记为

f k ( sk ) ? Opt {Vk [ Pk ( sk )] | Pk ( sk ) ? P}
2、最优化原理和动态规划递推关系
f k (sk ) ? Opt {d k (sk , xk ) ? f k ?1 (sk ?1 )} xk k ? 1,2,...K

1、最优化原理:最优策略的子策略也是最优的。 2、递推关系: f k (sk ) ? Opt {d k (sk , xk ) ? f k ?1 (sk ?1 )}

xk

k ? 1,2,...K
k ? 1,2,...K
6

f k (sk ) ? Opt {d k (sk , xk ) ? f k ?1 (sk ?1 )} xk

3、动态规划的步骤 1)划分阶段 将所研究的问题划分为K个阶段,并对阶 段进行编号。一般按逆向编号; 2)确定状态变量s k 正确确定状态变量s k ,使它既能描 述过程的演变又能满足无后效性; 3)确定决策变量x k(s k)及其允许的决策集合 D k(s k); 4)写出状态转移方程 s k-1 = g (s k ,x k); 5)确定直接效果函数 6)列出最优指标函数的递推关系式 7)确定边界条件
7

5.2 动态规划模型举例
5.2.1 资源分配问题 例 5.2.1某公司有 4个推销员在北京、上海和广州三个市场 推销货物,这三个市场里推销人员数与收益的关系如表 5.2.1所示,试作出使总收益最大的分配方案。

表5.2.1推销人员数与收益
推销员 市场 北京 上海 广州 0 20 40 50 1 32 50 61 2 47 60 72 3 57 71 84 4 66 82 83

解 1、划分阶段 分成3个阶段,即K=3,并按逆向编号,广 州k=1,上海k=2,北京k=3,分配推销员的优先顺序为北京 —上海—广州; 2、确定状态变量s k 状态变量s k 表示第k阶段初尚未分配的 推销员数。显然有 s3= 4,s2和s1的可能取值范围为0 — 4。 8

3、确定决策变量x k 决策变量x k 表示分配给第k阶段市场 的推销员数。显然有,x k ? s k ; 4、确定状态转移方程 根据前面定义的状态变量s k和决策 变量x k的意义,可得其状态转移方程为s k-1 =s k - x k ; 5、确定直接效果函数 d k (s k,x k) 它表示第k阶段初有推 销员数s k,分配给第k市场x k个推销员时所产生的直接效 益。这些效益指标由表5.2.1给出; 6、最优指标函数 由于三个市场的总效益等于三个市场的 效益之和,即其指标函数为累加形式。所以最优指标函 数为 7、边界条件 f0 (s 0) = 0 。 各阶段计算过程见教材P(138—139)

9

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

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

max f ( x) ? ? vk xk
k

? wk xk ? 30 ? ? k ? ? ?0 k 项未入选 ? xk ? ? ? ?1 k 项入选 ?

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

解:设项目选择的顺序为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、总效益递推公式

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

12

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

13

例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?0 估计第一阶段,即第4月份初库存的可能状态:

0? s1 ? 30?6?7?12=5,所以, s1 ?[0,5]

14

5.2.4 目标函数为乘积形式的动态规划
有 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%

15

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

解:四个季度为四个阶段,采用阶段编号与季度顺序一致。

设 sk 为第k季初的库存量,则边界条件为 s1=s5=0
设 xk 为第k季的生产量,设 yk 为第k季的订货量; sk ,xk ,yk 都取实数,状态转移方程为 sk+1=sk+xk - yk

仍采用反向递推,但注意阶段编号是正向的
目标函数为
4

f1 ( x ) ?

x1 , x2 , x3 , x4 i ?1

min ? (0.005xi2 ? si )
16

生产–库存管理问题(连续变量)
第一步:(第四季度) 总效果 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) 得:

17

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

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

18

生产–库存管理问题(连续变量)
第四步:(第一、二、三、四季度) 总效果 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。
19

5.2.6动态规划方法求解非线性规划
max f ( x ) ? x1 ? x2 ? x3 ? x1 ? x2 ? x3 ? 27 ? ? x1 , x2 , x3 ? 0 解: 这是一个资源分配问题。设分配次序为x1, x2, x3,阶段正向 编号,但逆向递推,由约束条件可得边界条件 s1=27, s4=0。 第三阶段:(给 x3分配) f 3 ( x3 ) ? x 3 由边界条件和状态转移方程有:s4=s3?x3=0,即 x3*= s3; 因此有, f 3* ( s3 ) ? s3
第二阶段:(给 x2分配)

f 2 ( s2 , x2 ) ? x2 ? f 3* ( s3 )

由状态转移方程有:s3=s2?x2,代入上式得,

f 2 ( s2 , x 2 ) ? x 2 ? s2 ? x 2 ?f 2 ?x 2 ? 1 2 x 2 ? 1 2 s 2 ? x 2 ? 0 解得, x 2 ? s2 2 ,
?

f 2? ( s2 ) ? 2s2

20

5.2.6动态规划方法求解非线性规划
第一阶段:(给 x1分配)
f1 ( s1 , x1 ) ? x1 ? f 2* ( s2 ) ? x1 ? 2s2

由状态转移方程有:s2=s1?x1=27 ?x1 ,代入上式得,

f1 ( s1 , x1 ) ? x1 ? 2( 27 ? x1 ) ?f 1 ?x1 ? 1 2 x1 ? 1 解得, 回溯得, x 1 ? 9,
?

54 ? 2 x1 ? 0 f1? ( s1 ) ? 9

? ? ? x1 ? x2 ? x3 ?9

21

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

22


相关文章:
运筹学5(动态规划)_图文.ppt
运筹学5(动态规划) - 第七章 动态规划 7.1 动态规划问题和基本概念 7.2 动态规划的基本原理 7.3 动态规划的应用 引言 动态规划与多阶段决策: 多阶段决策是...
运筹学第五章动态规划.ppt
运筹学第五章动态规划_数学_自然科学_专业资料 暂无评价|0人阅读|0次下载|举报文档 运筹学第五章动态规划_数学_自然科学_专业资料。动态规划 (Dynamic programming...
运筹与决策5动态规划_图文.ppt
运筹与决策5动态规划 - 第五章 动态规划 不要过河拆桥 动态规划 Dynami
运筹学5(动态规划)_图文.ppt
运筹学5(动态规划) - 第七章 动态规划 7.1 动态规划问题和基本概念 7.2 动态规划的基本原理 7.3 动态规划的应用 引言 动态规划与多阶段决策: 多阶段决策是...
运筹学教程五动态规划素材_图文.ppt
运筹学教程五动态规划素材 - 第五章 动态规划 不要过河拆桥 1 动态规划 Dy
运筹五 动态规划_图文.ppt
运筹五 动态规划_管理学_高等教育_教育专区。北京邮电大学林齐宁教授的运筹学授课教程 第五章 动态规划不要过河拆桥 1 动态规划 Dynamic programming ? ? ? ? ...
运筹学教程课件五 动态规划_图文.ppt
运筹学教程课件五 动态规划 - 第五章 动态规划 不要过河拆桥 1 动态规划 D
运筹学5(动态规划)_图文.ppt
运筹学5(动态规划) - 第七章 动态规划 7.1 动态规划问题和基本概念 7.2 动态规划的基本原理 7.3 动态规划的应用 引言 动态规划与多阶段决策: 多阶段决策是...
运筹学7动态规划.ppt
运筹学7动态规划_数学_自然科学_专业资料。运筹学7动态规划 第七 章动态规划 ...(22) v2 5 (27) v1 6 8 (16) v5 6 5 (10) 9 7 11 6 (22) ...
管理运筹学 第5章 动态规划_图文.ppt
管理运筹学 第5章 动态规划 - 第五章 动态规划 5.1. 动态规划的基本概念和最优化原理 5.2. 动态规划模型的建立与求解 5.3. 动态规划在经济管理中的应用 ...
运筹学第五章_动态规划1_图文.ppt
运筹学第五章_动态规划1 - 第五章 动态规划 动态规划简介 动态规划所解决的问题:多阶段问题 动态规划的核心。 核心: 在于将问题公式化,也可以说,动态规划是将...
运筹学:动态规划_图文.ppt
运筹学:动态规划 - 动态规划 不要过河拆桥 动态规划 Dynamic prog
运筹学5-1,5-2动态规划资料_图文.ppt
运筹学5-1,5-2动态规划资料 - 第五章 动态规划 美国数学家贝尔曼( R.
运筹学-动态规划_图文.ppt
运筹学-动态规划 - 动态规划 (Dynamic programming) 动态规划的基本思想 最短路径问题 投资分配问题 背包问题 动态规划是用来解决多阶段决策过程最优 化的一种...
运筹学5动态规划new_图文.pdf
运筹学5动态规划new - 决决决决 胜胜胜胜 千千千千 里里里里 之之之之 外外外外 动态规划 运运运运 筹筹筹筹 帷帷帷帷 幄幄幄幄 之之之之 中中中...
运筹学---动态规划_图文.ppt
运筹学---动态规划 - 这是关于运筹学里的动态规划的课件ppt... 运筹学---动态规划_理学_高等教育_教育专区。这...五、生产计划问题在企业生产经营活动中,经常会...
运筹学_5动态规划.ppt
运筹学_5动态规划 运筹学全全套教学课件!运筹学全全套教学课件!隐藏>> 4 动态规划 4.1 多阶段决策问题与动态规划 4.2 动态规划的基本概念 4.3 动态规划的步骤 4....
《运筹学》7动态规划_图文.ppt
运筹学》7动态规划 - 运筹学课件 运筹帷幄之中 Dynamic Programming 决胜 动态规划 千里之外第1页 综 述 1951 年,R ...
运筹08(第八章动态规划)_图文.ppt
运筹08(第八章动态规划) - 运筹学 OPERATIONS RESEARCH 2011-8-20 1 第八章 动态规划 §1 多阶段决策最优化问题举例 基本概念、 §2 基本概念、...
运筹(第八章动态规划)_图文.ppt
运筹(第八章动态规划) - 运筹学 OPERATIONS RESEARCH 2017/1/27 1 第八章 ? ? ? ? ? 动态规划 多阶段决策最优化问题举例 基本概念、基本方程...
更多相关文章: