当前位置:首页 >> 工学 >>

管理运筹学第6章-动态规划


6.动态规划( 6.动态规划(dynamic programming) 动态规划
多阶段决策问题( §1. 多阶段决策问题(multi stage decision process)
例l 设从A 设从A到E铺设输油管道,中间经过三个站。---最短路问题 铺设输油管道,中间经过三个站。---最短路问题
C1 B1 4 A 3 5 B3 B2 3 5 5 2 2 C4 7 5 4 6 C3 C2 3 2 1 D2 7 5 5 6 2 D1 3 E

7.动态规划( 7.动态规划(dynamic programming) 动态规划
多阶段决策问题( §1. 多阶段决策问题(multi stage decision process)
例l 设从A 设从A到E铺设输油管道,中间经过三个站。 铺设输油管道,中间经过三个站。

最短路问题的特性:如果最短路通过点p,则这条路线从p至终 点的部分,对于从p至终点的所有路线(称为p的后部路线)而言, 必定也是最短的路线。

7.动态规划( 7.动态规划(dynamic programming) 动态规划
多阶段决策问题( §1. 多阶段决策问题(multi stage decision process)
例l 设从A 设从A到E铺设输油管道,中间经过三个站。 铺设输油管道,中间经过三个站。
C1 (5) B1(10) 4 A(12) 3 5 B2(10) 3 5 B3(7) 5 2 2 C4(12) 7 5 4 6 C2(8)5 3 C3(5) 2 1 D2 (5) 7 5 2 6 D1(3) 3 E

7.动态规划( 7.动态规划(dynamic programming) 动态规划
多阶段决策问题( §1. 多阶段决策问题(multi stage decision process)
多阶段决策问题: 多阶段决策问题 随时间顺序或空间位置的变化而变化的活动过程(此即 动态的含义)。 适合于动态规划方法求解的仅是一类特殊的多阶段决策 问题,即具有所谓无后效性 无后效性的多阶段决策过程。 无后效性 无后效性又称为马尔科夫性 马尔科夫性(Markovianproperty)。是 马尔科夫性 指系统从某个阶段往后的发展演变,完全由系统本阶段所处 的状态及决策所决定,与系统以前的状态及决策无关。过去 的经历只能通过当前的状态去影响它未来的发展,即当前的 状态就是往后发展的初始条件,而系统以前的状态与决策已 经通过当前的状态反映出来。

7.动态规划( 7.动态规划(dynamic programming) 动态规划
多阶段决策问题( §1. 多阶段决策问题(multi stage decision process)
动态规划在一定条件下,也可以解决一些与时间无关 的“静态”最优化问题,只要人为地赋予“时段”的概念, 从而将静态问题变成为一个多阶段决策问题,这就是所谓静 态问题的动态处理。

7.动态规划( 7.动态规划(dynamic programming) 动态规划
§2 动态规划的基本概念和最优性原理
? 阶段(stage) 阶段( 阶段变量 k ? 状态 状态(state) 状态变量 sk,允许状态集合 Sk ? 决策(decision) xi(si) 决策( ? 策略(policy) p1n={x1(s1),x2(s2), ,xn(sn)}, 策略( ),…,x )},k后部子过程 ,k 后部子过程策略, pkn ? 状态转移方程(state transfer equation) sk+1=T(sk,xk(sk)) 状态转移方程( k+1 ? 最 优 指 标 函 数 第 k 阶 段 的 状 态 sk, 当 采 取 最 优 策 略 ( xk, xk+1,… xn)后,从阶段k到阶段n可获得的总效应,称为最优指标 函数,记为fk(sk)。

7.动态规划( 7.动态规划(dynamic programming) 动态规划
§2 动态规划的基本概念和最优性原理
? 最优性原理 最优性原理: “作为整个过程的最优策略具有这样的性质:无论过去的 状态和决策如何,相对于前面决策所形成的状态而言,余下的 决策序列必然构成最优子策略。”

§3. 动态规划模型及求解方法
3.1 动态规划的数学模型
1). 动态规划的函数方程(基本函数方程) 动态规划的函数方程(基本函数方程)

§3. 动态规划模型及求解方法
3.1 动态规划的数学模型
2). 建立动态规划模型的步骤

? 划分阶段k 划分阶段k ? 确定状态变量及其取值范围sk,Sk 确定状态变量及其取值范围s ? 确定决策变量及其取值范围xk,Dk 确定决策变量及其取值范围x ? 建立状态转移方程 xk+1=T(xk,sk) k+1 ? 确定阶段效应rk(xk,sk)和最优指标函数fk(sk) 确定阶段效应r 和最优指标函数f ? 建立动态规划的函数方程

§3. 动态规划模型及求解方法
3.2 动态规划的求解方法

逆序解法( 逆序解法(backward induction method) 最优指标函数形式是加法型

最优指标函数形式是乘法型

§3. 动态规划模型及求解方法
3.2 动态规划的求解方法

顺序解法( 顺序解法(forward induction method) 最优指标函数形式是加法型 sk-1=T(sk,xk(sk)) k=1,2,…,n k=1 ,n

最优指标函数形式是乘法型s k=1 最优指标函数形式是乘法型sk-1=T(sk,xk(sk)) k=1,2,…,n ,n

货物k

重量ak 3 4 5

收费ck 4 5 6

§4 动态规划的应用
4.1背包问题:(物流配装) 背包问题: 物流配装)

1 2 3

现有载重量为20吨的卡车,装载三种不同的货物。 20吨的卡车 例 1 现有载重量为 20 吨的卡车 , 装载三种不同的货物。 已知这 三种货物的单件重量和装载收费如表,又规定2 货物和3 三种货物的单件重量和装载收费如表 , 又规定 2 # 货物和 3 # 货物 都至多装两件。问如何装载这三种货物, 都至多装两件 。 问如何装载这三种货物 , 可使该车一次运输的 货物收费最多? 货物收费最多? 为是k#货物的装载件数.整数规划为: k#货物的装载件数 解:设xi为是k#货物的装载件数.整数规划为: f=4 max f=4x1+5x2十6x3 20, s.t.3x1+4x2十5x3≤20, x2 ≤2,x3 ≤2, 整数, xj≥0,整数, j=1,2,3。

货物k

重量ak 3 4 5

收费ck 4 5 6

4.1 背包问题

1 2 3

状态: k#至 货物允许的装载重量。 状态:sk ——k#至3#货物允许的装载重量。 k# 决策: k#货物的装载件数 决策:xk——k#货物的装载件数。 k#货物的装载件数。 阶段指标r k#货物装载 阶段指标rk(sk,xk)——k#货物装载xk件时的收益: k#货物装载x 件时的收益: rk(sk,xk)=ckxk 转移方程: 转移方程:Tk(sk,xk)—— sk+1= sk-akxk k+1 最优指标:fk(sk)——k#至3#货物允许载重sk时采取最佳决策所 最优指标: k#至 货物允许载重s k# 能获得的最大收益。 能获得的最大收益。 基本方程(递归方程) 基本方程(递归方程)为:

货物k

重量ak 3 4 5

收费ck 4 5 6

4.1 背包问题
逆序解法求解 : 第一步:k=3 第一步:k=3,有方程

1 2 3

S3={0,1,…,20},由于3#货物至多装载2件,a3=5,因此,决策集合为:

s3 D3(s3)

0-4 {0}

5-9 {0,1}

10-20 {0,1,2}

货物k

重量ak 3 4 5

收费ck 4 5 6

4.1 背包问题
逆序解法求解 : 第一步:k=3 第一步:k=3,有方程

1 2 3

S3={0,1,…,20},由于3#货物至多装载2件,a3=5,因此,决策集合为: s3 6x3+f4(s3-5x3) f3(s3) x3* x3=0 0-4 5-9 10-20 0+0 0+0 0+0 x3=1 6+0 6+0 x3=2 12+0 0 6 12 0 1 2

货物k

重量ak 3 4 5

收费ck 4 5 6

4.1 背包问题
第二步:k=2 有方程: 第二步:k=2,有方程:

1 2 3

S2={0,1,…,20},由于2#货物至多装载2件,a2=4,因此,决策集合为:

s2 D2(s2)

0-3 {0}

4-7 {0,1}

8-20 {0,1,2}

货物k

重量ak 3 4 5

收费ck 4 5 6

4.1 背包问题
ti +ui ti 0 5 10 ui 0 0 5 10 4 4 9 14 8 8 13 18 0-3 4 5-7 8 9 10-12 13 14-17 18-20 s2

1 2 3

5x2+f3(s2-4x2) x2=0 x2=1 x2=2 0+0 0+0 5+0 0+6 5+0 0+6 5+0 10+0 0+6 5+6 10+0 0+12 5+6 10+0 0+12 5+6 10+6 0+12 5+12 10+6 0+12 5+12 10+12

f3(s2) 0 5 6 10 11 12 16 17 22

x2* 0 1 0 2 1 0 2 1 2

货物k

重量ak 3 4 5

收费ck 4 5 6

4.1 背包问题
第三步:k=1,有方程: k=1 有方程:

1 2 3

s2= s1-3x1
显然S1={20},D1(20)={0,1,…,6}

由顺序追踪法,得最优解为: s1=20 s2=8 s3=0 或 s1=20 s2=5 s3=5 x*1=4 x*2=2 x*3=0 x*1=5 x*2=0 x*3=1

4.2 生产计划问题
库存问题: 例2.生产—库存问题: 生产 库存问题 已知: 个阶段需考虑,市场各阶段的需求为d 已知:有n个阶段需考虑,市场各阶段的需求为dk, 生产能力为 生产固定成本K 单位产品成本(追加) bk,生产固定成本K,单位产品成本(追加)为C,库存费 h,库存能力E,初始和未尾的库存为 库存能力E,初始和未尾的库存为0 (n=5 h,库存能力E,初始和未尾的库存为0。(n=5) 各阶段的生产数x 使满足市场需求的条件下总费用最小。 求:各阶段的生产数xk,使满足市场需求的条件下总费用最小。 解: 状态: 状态:sk ——k阶段初的库存量。s0=0,s5=0,0≤ sk≤ E k阶段初的库存量 决 策 : xk——k 阶 段 的 生 产 量 。 0 ≤ xk≤ bk,dk-sk≤ xk≤ Ek sk+dk 阶段指标: 阶段指标:rk(sk,xk)——k阶段的费用: k阶段的费用: rk(sk,xk)=K[xk/(xk+0.01)]+Cxk+hsk 01)]+Cx 转移方程: 转移方程:Tk(sk,xk) —— sk+1= sk+xk-dk k+1 最优指标: 量为s 最优指标:fk(sk) ——k阶段初的库存量为sk时,后阶段的最少 k阶段初的库存量为 费用值。 费用值。

4.2 生产计划问题
库存问题: 例2.生产—库存问题: 生产 库存问题 已知: 个阶段需考虑,市场各阶段的需求为d 已知:有n个阶段需考虑,市场各阶段的需求为dk, 生产能力为 生产固定成本K 单位产品成本(追加) bk,生产固定成本K,单位产品成本(追加)为C,库存费 h,库存能力E,初始和未尾的库存为 库存能力E,初始和未尾的库存为0 (n=5 h,库存能力E,初始和未尾的库存为0。(n=5) 各阶段的生产数x 使满足市场需求的条件下总费用最小。 求:各阶段的生产数xk,使满足市场需求的条件下总费用最小。 解: 基本方程为: 基本方程为:

见P209/例7-5 209/

4.2 生产计划问题
例3.库存—销售问题 : 库存 销售问题 已知: 个阶段需考虑,库存能力E 市场各阶段的进价为c 已知:有n个阶段需考虑,库存能力E,市场各阶段的进价为ck, 售价为p 初始库存为s 未尾的库存为0 售价为pk, 初始库存为s0,未尾的库存为0。 各阶段的进货和售货计划,使总利润最大。 求:各阶段的进货和售货计划,使总利润最大。 解: 状态: 阶段初的库存量。 状态:sk —— k阶段初的库存量。s0,sn+1=0,0 ≤ sk ≤ E 阶段初的库存量 决策: 阶段的销售量和进货量。 决策:uk,vk——k阶段的销售量和进货量。 阶段的销售量和进货量 0 ≤ uk ≤ sk,0 ≤ vk ≤ E-sk+uk 阶段指标: rk(sk,uk ,vk)——k阶段的利润: 阶段指标 阶段的利润: 阶段的利润 rk(sk,uk ,vk)= pk uk-ck vk 转移方程: 转移方程:Tk(sk,vk)—— sk+1= sk+vk-dk 最优指标: 阶段初的库存量为s 最优指标:fk(sk)——k阶段初的库存量为 k时,后阶段的最大 阶段初的库存量为 利润。 利润。

4.2 生产计划问题
例3.库存—销售问题 : 库存 销售问题 已知: 个阶段需考虑,库存能力E 市场各阶段的进价为c 已知:有n个阶段需考虑,库存能力E,市场各阶段的进价为ck, 售价为p 初始库存为s 未尾的库存为0 售价为pk, 初始库存为s0,未尾的库存为0。 各阶段的进货和售货计划,使总利润最大。 求:各阶段的进货和售货计划,使总利润最大。 解: 基本方程为: 基本方程为:

见P214/例7-6 214/

4.3 资源分配问题
一维模型: 一维模型:

二维模型: 二维模型:

4.3 资源分配问题
状态变量:(sk,tk),其中sk,tk分别表示分配给第k个到第n个使 状态变量: 其中s 分别表示分配给第k个到第n 用者两种资源的总数量; 用者两种资源的总数量; 决策变量: 其中x 分别表示分配给第k 决策变量:(xk,yk),其中xk,yk分别表示分配给第k个使用者两 种资源的数量。 种资源的数量。 阶段指标: 为第k阶段收益函数。 阶段指标:gk(xk,yk)为第k阶段收益函数。 最优指标:f(sk,tk)为以数量分别为sk,tk两种资源分配给第k个 最优指标: 为以数量分别为s 两种资源分配给第k 到第n个使用者可获得的最大收益 可获得的最大收益。 到第n个使用者可获得的最大收益。 状态转移方程: 状态转移方程: k=n,nsk+1=sk-xk, tk+1=tk-yk k=n,n-1,…,1 , k+1 k+1 及: s1=a, sn+1=0; t1=b, tn+1=0; n+1 n+1 基本方程 :

4.4 设备更新问题
已知 : 需考虑n年的设备更新计划,t为设备使用年龄,r(t)为 需考虑n 年的设备更新计划, 为设备使用年龄, r(t)为 年龄为t的设备一年内的生产收入(递减) 为年龄为t 年龄为t的设备一年内的生产收入(递减),u(t) 为年龄为t的 设备一年内的维修费(递增) 为年龄为t 设备一年内的维修费 ( 递增 ) , c(t) 为年龄为 t 的设备卖掉的 折旧费(递减) 为购置新设备费。 折旧费(递减),p为购置新设备费。 年的设备更新计划,使总收入最大。 求:n年的设备更新计划,使总收入最大。 解: 状态: 年设备的年龄。 状态:sk ——第k年设备的年龄。s0=0,sk=t 第 年设备的年龄 决策: 年设备更新或继续使用。 决策:xk——第k年设备更新或继续使用。 第 年设备更新或继续使用 为更新, 令xk=0为更新,xk=1为继续使用 为更新 为继续使用 阶段指标r 年的利润: 阶段指标 k(sk,xk)——k年的利润: 年的利润 rk(sk,xk)=r(skxk)-u(skxk)-(1-xk)(p-c(sk)) 转移方程: 转移方程:Tk(sk,xk)—— sk+1= 1+skxk 最优指标: 已用了s 年到第n年的最大收益 最优指标:fk(sk)——已用了 k年的设备,第k年到第 年的最大收益 已用了 年的设备, 年到第 年的最大收益.

4.4 设备更新问题
已知 :需考虑n年的设备更新计划,t为设备使用年龄,r(t)为 需考虑n 年的设备更新计划, 为设备使用年龄, r(t)为 年龄为t的设备一年内的生产收入(递减) 为年龄为t 年龄为t的设备一年内的生产收入(递减),u(t) 为年龄为t的 设备一年内的维修费(递增) 为年龄为t 设备一年内的维修费 ( 递增 ) , c(t) 为年龄为 t 的设备卖掉的 折旧费(递减) 为购置新设备费。 折旧费(递减),p为购置新设备费。 年的设备更新计划,使总收入最大。 求:n年的设备更新计划,使总收入最大。 解: 基本方程为: 基本方程为:

见P230/例7-9 230/

§4 动态规划的应用
4.1 背包问题:(物流配装) 背包问题: 生产计划问题: 4.2 生产计划问题:(生产—库存问题,库存—销售问题) 4.3 资源分配问题: (一维模型,二维模型) 资源分配问题: 设备更新问题: 4.4 设备更新问题:(车辆更新)
商人过河问题 商人过河问题: 问题 三名商人各带一名随从,要乘一只最多能容纳二人的小 船过河,随从们密约,在河的任一岸,一旦他们的人数比商 人的多,就杀人越货。但如何乘船的大权操在商人的手中, 商人们已获得了这项密约,请你为商人制定一个安全过河的 方案。

商人过河问题
状态:设渡河过程中,此岸商人数为x(x= x(x=0 状态 设渡河过程中,此岸商人数为x(x=0,1,2,3),随从数为 设渡河过程中 y=0 状态( x,y)表示此岸的商人和随从数 表示此岸的商人和随从数。 y(y=0,1,2,3), 状态 ( x,y) 表示此岸的商人和随从数 。 彼 岸的状态为( x,3 y)。 岸的状态为(3-x,3-y)。 共有16种可能的状态。其中商人安全的状态为: 16种可能的状态 共有16种可能的状态。其中商人安全的状态为: y=0 (3, y) y=0,1,2,3; (0, y) y=0,1,2,3 y=0 k=1 记为S (k, k) k=1,2; 记为S。 决策:运载向量为:(决策 运载向量为:(-1)k(m,n) 运载向量为:( 为D。 状态转移方程: 状态转移方程: Sk+1=Sk+Dk, m,n=0,1,2,且1<=m+n<=2,记 m,n=0,1,2,且1<=m+n<=2,记 m+n<=2,

满足: 满足:S0=(3,3), Sl=(0,0),Dk∈D,Sk∈S


赞助商链接
相关文章:
第6章 动态规划-习题6.2
第6章 动态规划-习题6.2 北京林业大学运筹学课件北京林业大学运筹学课件隐藏>> 投x1 辆超负荷车 s1=1000 状态 s 投 x2 辆超负荷 投 x3 辆超负车 状态 ...
运筹学--第七章 动态规划
第7章 动态规划 25页 免费如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行反馈。 运筹学--第七章 动态规划 运筹学的重要学习...
第6讲 动态规划
第6 章 动态规划 6.1 动态规划概述 动态规划运筹学的一个分支,是求解决策过程最优化的数学方法。20 世纪 50 年代美 国数学家贝尔曼(Rechard Bellman)等人在...
管理运筹学
管理运筹学_第六章 43页 1财富值 管理运筹学_第五章 46页 1财富值 管理运筹...(20 分,共 10 题,每题 2 分,选出一个正确的答案) 选择( 1.动态规划是...
《管理运筹学》第四版课后习题解析(下)
第 10 章动态规划 1.解: 最优解为 A―B2―C1―D1―E 或 A―B3―C1―...使用管理运筹学软件,结果如下。 从节点 1 到节点 6 的最大流 *** 起点终点...
电力出版社运筹学答案 第六章
电​力​出​版​社​运​筹​学​答​案第6 章训练题 一....用动态规划方法求解 2 题至 13 题。 2. max z ? x1 x 2 x3 2 3 3....
《管理运筹学》习题集
管理运筹学》习题集_管理学_高等教育_教育专区。自治区重点产业紧缺人才专业...试建立这个问题的目标规划模型,并用 LINGO 软件求解。 第 5 章 动态规划 1....
运筹学习题集(第六章)
运筹学习题集(第六章) - 判断题 判断正误,如果错误请更正 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 1...
管理运筹学第四版 第三章习题6答案(P35)
管理运筹学第四版 第三章习题6答案(P35) - 《数据、模型和决策》作业一 学号:2461604112 姓名:王康兵班级:2016 秋 MBA2 周末班 一、第三章线性规划问题的...
2015管理运筹学重点
2015管理运筹学重点_管理学_高等教育_教育专区。一、考试知识点 第二章 线性规划...离散确定型动态规划的标号算法(练习题 6.1) 6.2 运用动态规划原理求解生产...
更多相关文章: