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

管理运筹学第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


赞助商链接
相关文章:
运筹学试卷及答案完整版
运筹学试卷及答案完整版_管理学_高等教育_教育专区。《运筹学》模拟试题及参考...0 ? 1 2 六、下图为动态规划的一个图示模型,边上的数字为两点间的距离,请...
动态规划习题答案
动态规划习题答案_工学_高等教育_教育专区。由复旦大学出版社出版,傅家良主编的运筹学方法与模型第八章动态规划习题答案2.某公司有资金 4 百万元向 A,B 和 C3 ...
运筹学及应用案例-动态规划
运筹学及应用案例-动态规划_经济/市场_经管营销_专业资料。运筹学-动态规划徐州工程学院数理学院 案例分析报告 课程名称 案例分析题目 专班姓学业级名号 运筹学及应...
动态规划讲解大全(含例题及答案)
(dynamic programming)是运筹学的一个分支,是求解...动态规划问世以来,在经济管理、生产调度、工程技术和...{1,3,4,6} {3,4,7} and {1,2,5,6} {...
运筹学实验_动态规划
运筹学实验_动态规划_城乡/园林规划_工程科技_专业资料。实验二用 MATLAB 解决动态规划问题问题:有一部货车每天沿着公路给四个售货店卸下 6 箱货物, 如果各零售...
动态规划--运筹学课程设计
运筹学_动态规划 88页 免费 运筹学——动态规划 80页 免费 运筹学—第七章 ...北京:清华大学出版社,2001:36-39 [6] 李荣均.运筹学(MBA 工商管理教材)[M...
运筹学各章的作业题答案
管理运筹学》各章的作业 ---复习思考题及作业题 第一章 绪论 复习思考题 ...第五章 动态规划 思考题 主要概念及内容: 多阶段决策过程;阶段及阶段变量;状态...
第五章 动态规划 山大刁在筠 运筹学讲义
第五章 动态规划教学重点:用递推的方法求解最短路线问题,有限资源分配问题,旅行售 货员问题,最优线路问题等。 教学难点:有限资源分配问题。 教学课时:10 学时 ...
运筹学中excel的运用(用excel解决线性规划、动态规划、...
运筹学中excel的运用(用excel解决线性规划、动态规划、排队论等问题)_电脑基础知识_IT/计算机_专业资料。用excel解决运筹学中基础模型的求解问题。1...
运筹学之动态规划(东南大学)
运筹学动态规划(东南大学)_管理学_高等教育_教育专区。运筹学 ...工厂每季度的最大生产能力为 6(千件).经调查,市场对该产品的需 求量第一,...
更多相关标签: