运筹学第05章动态规划复习过程

格式：ppt
大小：722.00 KB
文档页数：65

下载文档原格式

运筹学第05章动态规划

动态规划模型
动态规划模型如下
u1 ,,u n
opt R rk xk , u k
n k 1
表示求和或加权求和 opt表示求最优(最大值或最小值) Xk表示k阶段状态可能的取值范围，称为状态可能集合 Uk表示k阶段决策可能的取值范围，称为决策允许集合
x1
决策 Z
x2 x1 表示决策所依赖的资源和环境
Z表示目标函数
x2 表示决策后的资源和环境状况
动态规划概念(2)
例如，前面讲过的生产计划问题就是一次决策
某工厂用三种原料生产三种产品，已知的条件如下表所示，试制订总利润最大的日生产计划
产品所需原料数量（公斤/ 件）原料P1 原料P2 原料P3 产品的利润（千元/ 件）产品Q1
贝尔曼方程
对于无后效性的多阶段决策过程，根据最优性原理和贝尔曼函数定义，可得
f k xk optrk xk , uk f k 1 xk 1 其中，xk 1 Tk xk , uk 称为动态规划基本方程，也称为贝尔曼方程
uk
动态规划问题求解步骤(1)
k阶段决策uk是决定下一步走到哪里，有
u1∈{a,b,c} u2(a)∈{d,f}，u2(b)∈{d,e} ，u2(c)∈{d,e,f} u3∈{t}
示例(5.2-3)
状态转移方程
xk+1=uk
阶段效应rk(xk , uk ) 取为从xk 走到uk 的路线长度，如r1(s , a) =9 贝尔曼函数 fk(xk ) 定义为从xk 走到 t 的最短路线贝尔曼方程
f k xk opt ri xi , ui
n u k ,,u n i k
为了将从初始状态xk 出发的k-后部子过程的最优策略和最终的最优策略相区别，称前者为条件最优策略

#5 运筹学讲义[目标规划、动态规划]

3. 由于甲资源供应比较紧张，不要超过现有量140。
试建立目标规划模型。
解：以产品 A,B 的单件利润比 2.5 :1 为权系数，模型如下：
min Z P1 d 1 2.5 P2 d 3 P2 d 4 P3 d 2 30x1 12x 2 d 1 d 1 2500 2 x x d d 140 1 2 2 2 x d d 60 1 3 3 x d d 100 2 4 4 x 60 1 x2 100 x 0 , d , d 0 ( l 1.2.3.4) l l 12
微积分；线性代数计算机编程微积分；线性代数计算机编程
应用统计微积分；线性代数
为了选修课程门数最少，应学习哪些课程？选修课程最少，且学分尽量多，应学习哪些课程？
0-1规划模型
课号 1 2 3 4 5 6 7 8 9 课名微积分线性代数最优化方法数据结构应用统计计算机模拟计算机编程预测理论数学实验所属类别数学数学数学；运筹学数学；计算机数学；运筹学计算机；运筹学计算机运筹学运筹学；计算机
min{d d } 2 x 2 x d d 12 2 1
3. 目标的优先级与权系数
在一个目标规划的模型中，为达到某一目标可牺牲其他一些目标，称这些目标是属于不同层次的优先级。优先级层次的高低可分别通过优先因子P1,P2,…表示。对于同一层次优先级的不同目标，按其重要程度可分别乘上不同的权系数。权系数是一个个具体数字，乘上的权系数越大，表明该目标越重要。现假定：
选课策略
课号
1 2 3 4 5 6 7 8 9
课名
微积分线性代数最优化方法数据结构应用统计计算机模拟计算机编程预测理论数学实验

管理运筹学第5章动态规划

递推关系的建立
根据阶段划分、状态转移方程和最优解的性质，建立递推关系。
递推关系的求解
通过递推关系求解各阶段的最优解，最终得到整个问题的最优解。
03
动态规划的求解方法
逆推法
总结词
逆推法是从目标状态出发，逆向推算出达到目标状态的最优决策，逐步推算出初始状态的最优决策。
详细描述
逆推法的基本思想是将问题分解为若干个相互联系的阶段，从最后阶段开始，依次向前推算出每个阶段的最优决策，直到达到初始状态。这种方法适用于具有重叠子问题和最优子结构的问题，可以避免重复计算，提高求解效率。
详细描述
资源分配问题通常需要考虑资源的约束条件、各部门或个体的需求和优先级，以及如何平衡各方利益。动态规划通过将问题分解为一系列子问题，逐一求解最优解，最终得到整体最优解。
生产与存储问题
总结词
生产与存储问题主要研究在生产过程中如何平衡生产与库存的关系，以最小化生产成本和库存成本。
详细描述
特点
动态规划适用于具有重叠子问题和最优子结构特性的问题，通过将原问题分解为子问题，逐个求解并存储子问题的解，避免了重复计算，提高了求解效率。
动态规划的重要性
解决复杂问题
动态规划能够解决一些复杂的问题，如资源分配、生产计划、物流调度等，这些问题通常难以通过传统方法求解。
提高计算效率
通过避免重复计算，动态规划能够显著提高计算效率，尤其在处理大规模问题时，能够大大减少计算时间和资源消耗。
05
动态规划的优化策略
多阶段决策优化
01
02
03
阶段划分
将问题划分为若干个相互关联的阶段，每个阶段都有自己的决策变量和状态转移方程。
状态转移

管理运筹学第5章动态规划

第一阶段：
* * * * 最优解： x = 0 x = 1 x = 0 x = 1 1 2 3 4
练习.
1.石油输送管道铺设最优方案的选择问题.下图中A为出发点,E为目的地,B,C,D分别为三个必须建立油泵加压站的地区,图中的线段表示管道可铺设的位置,线段旁的数字为铺设管道线所需的费用.问如何铺设管道才使总费用最小.
－
－－
0
0 0
0
0 0
－
－
0
0
0
0 1 1 1 1
20 20 20 20
20 20 20 1
第三阶段：
s3
0 1 2 3 4
x3
r ( s , x ) f ( s 4 x ) 3 3 3 4 3 3
0 1 2 －－－－－
f 3 ( s3 )
0 0 0 0 11
x *3
0 0 0 0 1
咨询项目类型待处理客户数处理每个客户所处理每个客需工作日数户所获利润
1 3 4 7 2 8 11 20
1 2 3 4
4 3 2 2
解：用动态规划来求解此题。我们把此问题分成四个阶段，第一阶段我们决策将处理多少个第一种咨询项目类型中的客户，第二阶段决策将处理多少个第二种咨询项目类型中的客户，第三阶段、第四阶段我们也将作出类似的决策。我们设 s k ＝分配给第k种咨询项目到第四种咨询项目的所有客户的总工作日（第k阶段的状态变量）。 x k =在第k种咨询项目中处理客户的数量（第k阶段的决策变量）。已知 s 1 ＝10 并有 s T ( s , x ) s 3 x , T ( s , x ) s x ,s 3 2 2 2 2 2
件重量为wi公斤，每件价值ci元。现有一只可装载重量W 公斤的背包，求各种物品应各取多少件放入背包，使背包中物品的价值最高。这个问题可以用整数规划模型来描述。设xi为第i种物品装入背包的件数（i =1, 2, …, n），背包中物品的总价值为z，则 Max z = c1x1+c2x2+ … +cnxn s.t. w1x1+w2x2+…+wnxn≤W x1, x2, …, xn0 且为整数。

运筹学第5章：动态规划

x1 , x 2 , x3 i 1
10
3
例3 第一阶段：给第三市场分配
s1 有0~9种可能，第一阶段最优决策表如下：
为什么与例1 的第一阶段的表有差别？
11
例3 第二阶段：给第二市场分配
s2 有0~9种可能，第二阶段最优决策表如下：
12
例3 第三阶段：给第一市场分配
由边界条件 s3=9，第三阶段最优决策表如下：
4
1838 1768 1762 1698 1692 1686 1628 1622 1616 1610 s 2 =2 s 2 =3 s 2 =4 s 2 =5
第三阶段最优决策表
第四阶段：初始库存量 s4=0 由状态转移方程： s3=s4+x4-60 可知 x46，由阶段效果递推公式有： f4(0,6)=d4(0,6)+f3*(0,10) =706+1902=2322 得第四阶段最优决策表，如下
得第三阶段最优决策表，如下
8 9 1908 1832 1756 1680 1604 s 2 =6 10 1902* 1826* 1750* 1674* 1598* s 2 =7 x 3 * f 3 (s 3 ,x3 *) 10 10 10 10 10 1902 1826 1750 1674 1598
将 s2= s1 + x1 – 600= x1 – 600 代入 f1(s1,x1) 得：
由此回溯：得最优生产–库存方案 x1*=600，s2*=0； x2*=700，s3*=0； x3*=800，s4*=300； x4*=900。
9
5.2.2 资源分配问题
例3 某公司有9个推销员在全国三个不同市场推销货物，这三个市
第三步：(第二、三、四季度) 总效果 f2(s2,x2)=0.005 x22+s2+ f3*(s3) 将 s3= s2 + x2 - 700 代入 f2(s2,x2) 得：

运筹学——动态规划

优子策略。该原理的具体解释是，若某一全过程
最优策略为：
p1
(s1 )
{u1
(s1 ),
u 2
(s2
),
,
u
k
(sk
),
u
n
(sn
)}
则对上述策略中所隐含的任一状态而言，
第k子过程上对应于该状态的最优策略必然包
含在上述全过程最优策略p1*中，即为
pk
(sk
)
{u
k
(sk
),
u
k 1
(sk
1
),
2．正确地定义状态变量sk，使它既能正确地描述过程的状态，又能满足无后效性．动态规划中的状态与一般控制系统中和通常所说的状态的概念是有所不同的，动态规划中的状态变量必须具备以下三个特征：
20
2021/7/26
(1)要能够正确地描述受控过程的变化特征。 (2)要满足无后效性。即如果在某个阶段状态已经给定，那么在
sk 1 Tk (sk ,uk (sk ))
上式称为多阶段决策过程的状态转移方程。有些问题的状态转移方程不一定存在数学表达式，但是它们的状态转移，还是有一定规律可循的。
12
2021/7/26
(六) 指标函数用来衡量策略或子策略或决策的效果的某种数量
指标，就称为指标函数。它是定义在全过程或各子过程或各阶段上的确定数量函数。对不同问题，指标函数可以是诸如费用、成本、产值、利润、产量、耗量、距离、时间、效用，等等。
7
2021/7/26
（二）状态、状态变量和可能状态集 1.状态与状态变量。用以描述事物(或系统)在某特定的时间与空间域中所处位置及运动特征的量，称为状态。反映状态变化的量叫做状态变量。状态变量必须包含在给定的阶段上确定全部允许决策所需要的信息。按照过程进行的先后，每个阶段的状态可分为初始状态和终止状态，或称输入状态和输出状态，阶段k的初始状态记作sk，终止状态记为sk+1 。但为了清楚起见，通常定义阶段的状态即指其初始状态。

第五章物流运筹学——动态规划

即由第阶段的状态利用这个原理，可以把多阶段决策问题求解过程表示成一个连续的递推过程，由后向前逐步计算。
的单件重量和装载收费如表5-1所示，又规由于它表示了由段到段的状态转移
因此，在物流管理中，如何进行决策，制定一个最优的设备维护更新策略，是非常重要的。
第三节动态规划模型的建立与求解
定货物2和货物3都至多装两件。问如何装但假设初始状态虽已给定，终点状态有多个，需比较到达不同终点状态的各个路径及最优指标函数值，以选取总效益最正确的终点状
3
• 【例5-1】〔生产与存储问题〕工厂在3个季度中
• 安排某种产品的生产方案。假设该季度生产此
种产x
x2
• 品〔吨〕，那么本钱为元。假设当季
生产的
• 每吨产品未销售a k 掉，那么进库，季末需付存储费，
• 产品每季的存储费为1元。现估计3个季度对该产
• 品的需求量分别为100吨，110吨和120吨，
3
j 仪器
1
2
3
10
9
14
9
12
10
6
5
8
7
• 【例5-4】〔机器负荷问题〕设某机器可以在高、
• 低两种不同的负荷下进行生产。假设年初x 有台
• 机器在高负荷下进行生产，那么产品年a产 8x
量
，
0.3
y
• 机器的年折损率
低
0.1
；假设年b 初5有y 台机器在
• 负荷下进行生产，那么产品年产量
，机器
的
• 年折损率
。假设初始时有性能正常的机器
1000
• 台，要求制定机器负荷的四年分配方案，确定每
年
8
A

管理运筹学第5章

B1
8 4
6
3
B2
2 4
42 B3 5
C1
1 4
6
D1 3
C2 3
E
4 3 D2 C3 3
v2,4= v2,4（s2 ,x2 ,x3 ,x4） = v2,4（B3 ,C2 ,D2 ,E）=9
v2,4= v2,4（s2 ,x2 ,x3 ,x4） = v2,4（B1 ,C2 ,D2 ,E）=11
v2,4= v2,4（s2 ,x2 ,x3 ,x4） = v2,4（B1 ,C3 ,D2 ,E）=13
Operational Research
(3) k=1，s1={0，1，…，8}，[1~3]
f1(s1) = max{ g1(s1,x1)+ f2(s1-x1)}
0≤x1≤s1
分别求出s1为不同值时的f1(s1)及x*1，计算结果如下表：
S1 0 1 2 3 4 5 6 7 8 x*1 0 0，1 0 0，3 4 5 4 4 ４ f1(s1) 0 5 26 40 ８0 ９0 10６ 1２0 1４0
短路，从最后一个阶段开始，由后向前逐步递推。
（1）当k=4时，S4 ={ D1 D2 } 按f4 的定义有
f4（D1）=3 f4（D2）=4 （2）当k=3时，S3 ={ C1 C2 C3 }
B1
8 4
6
f3(C1) = d3(C1 , D1)+ f4(D1) Min
2 A4
5
3
B2
2 4
d3(C1 , D2)+ f4(D2)
Operational Research
5．1．2．6 指标函数
(1)第k阶段指标函数： rk(sk,xk) 它是状态变量和决策变量

运筹学第五章动态规划

一、多阶段决策问题
根据问题本身的特点，可以将其求解的全过程划分为若干个相互联系的阶段（即将问题划分为许多个相互联系的子问题），在它的每一阶段都需要做出决策，并且在一个阶段的决策确定以后再转移到下一阶段。往往前一个阶段的决策要影响到后一个阶段的决策，从而影响整个过程。这样的决策过程称作多阶段决策过程。
描述决策变化的量称为决策变量。
常用uk uk sk 表示 k 阶段状策变量的取值的容许范围。
决策变量uk sk 的允许决策集用Uk sk 表示， uk sk Uk sk ，
允许决策集合实际是决策的约束条件。
三、动态规划求解的多阶段决策问题的特点
（2）设备更新问题企业在使用设备时都要考虑设备的更新问题。现某企业要决定一台设备未来 8 年的更新计划，已预测了第 j 年购买设备的价
格为 K j ，设Gj 为设备经过 j 年后的残值，C j 为设备连续使用
j 1年后在第 j 年的维修费 j 1, 2, ,8，问应在哪些年更
新设备可使总费用最小。
（4）资源分配问题某工业部门或公司，拟对其所属企业进行稀缺资源分配，为此需要制订出收益最大的资源分配方案。
（5）运输网络问题
图5-11 运输网络图示
多阶段决策过程最优化的目标：要达到整个活动过程的总体效果最优。
v1
第二节动态规划的基本概念和基本原理
一、动态规划的基本概念（1）阶段；（2）状态；（3）决策和策略；（4）状态转移；（5）指标函数
二、多阶段决策问题举例
（1）生产与存贮过程。
某工厂每月需供应市场一定数量的产品，并将所余产品存入仓库。一般某月适当增加产品可降低生产成本，但超产部分存入仓库会增加库存费用。要求确定一个逐月的生产计划，在满足需求条件下，使一年的生产与存贮费用之和最小。

运筹学第5章：动态规划

– 指某阶段某状态下到终端状态的总效果,它是一个递推公式指某阶段某状态下到终端状态的总效果,
fk (sk , xk ) = hk (dk (sk , xk ), fk1(sk1, xk1 )
6
动态规划的步骤
– hk 是一般表达形式,求当前阶段当前状态下的阶段最优是一般表达形式, 总效果
(1) 如最短路问题,是累加形式,此时有如最短路问题,是累加形式,
14
生产–库存管理问题连续变量) 库存管理问题(连续变量例2 生产库存管理问题连续变量
第三步: 第二第二, 四季度) 第三步:(第二,三,四季度总效果 f2(s2,x2)=0.005 x22+s2+ f3*(s3) 将 s3= s2 + x2 - 700 代入 f2(s2,x2) 得:
回溯得此表
12
生产–库存管理问题连续变量) 库存管理问题(连续变量例2 生产库存管理问题连续变量
设某厂计划全年生产某种产品A.其四个季度的订货量分别为设某厂计划全年生产某种产品 .其四个季度的订货量分别为600 公斤, 公斤公斤, 公斤和公斤和1200公斤.已知生产产品的生产费公斤. 公斤,700公斤,500公斤和公斤已知生产产品A的生产费用与产品的平方成正比,系数为0.005.厂内有仓库可存放产品, 用与产品的平方成正比,系数为 .厂内有仓库可存放产品, 存储费为每公斤每季度1元求最佳的生产安排使年总成本最小. 存储费为每公斤每季度元.求最佳的生产安排使年总成本最小.
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

1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

k 1,2, ,7
u k 1,2,3, k 1,2, ,7
动态规划解的概念(1)
最优目标值
在多阶段决策过程中，从起始状态x1开始，进行一系列的决策，使得目标R达到最优，我们把这种目标的值称为最优目标值，记为R*
最优策略
把使目标达到最优的决策序列称为最优策略，记为 {u1*, u2*,…, un*}
最优路线
在采用最优策略时，系统从x1开始所经过的状态序列称为最优路线，记为{x1*, x2*,…, xn+1*}
动态规划解的概念(2)
求解动态规划问题就是要找到最优策略、最优路线和最优目标值
动态规划最优性原理(1)
一个多阶段决策过程的最优策略具有这样的性质
无论其初始状态及其初始决策如何，对于前面决策所形成的某一状态而言，下余的决策序列必定构成最优策略
令 A 024 ， b15,0 80 0 , 2 00 T， 0C3, 5, 4
3 2 5
示例(5.1-3)
7
max R cuk vk k 1
x1 b
s
.t
.
xk Pu
1 vk k
b
xk xk ,
k
Puk v k , k 1,2, ,7
1, 2 ,
,7
v
k
0且为整数
,
u1
u2
u7
x1 周日 x2 周一 x3 … x7 周六 x8
r1
r2
r7
动态规划概念(5)
uk（k=1,2,3,4,5,6,7）表示第k天生产三种产品中的哪一种以及生产多少
x1=技术环境A、市场环境C和原料b xk+1=技术环境A、市场环境C和原料b +第k
天剩余的原料（k=1,2,3,4,5,6,7） rk=第k天生产产品获得的利润总利润=r1+ r2+ r3+ r4+ r5+ r6+ r7
.
x u
k k
X U
k k
k 1 , 2 , , n
Xk表示k阶段状态可能的取值范围，称为状态可能集合
Uk表示k阶段决策可能的取值范围，称为决策允许集合
动态规划建模
确定阶段
根据实际情况进行阶段划分
明确状态变量xk和状态可能集合Xk 确定决策变量uk(xk )和决策允许集合Uk 确定状态转移方程xk+1=Tk(xk , uk ) 明确阶段效应rk(xk , uk )和目标R
A、C和剩余的原料为x2
Z
动态规划概念(4)
如果上例中的生产计划不是只在一天里进行，而是连续一周，每天投入一定量的原料，剩余的原料后面可以继续使用，每天只允许生产一种产品并获得相应的利润。问怎样决策才能使一周的总利润最大？
解决这样的问题需要将决策过程分为多个阶段，本问题需要分为如下的7个阶段。
注：动态规划的建模和求解都是针对具有无后效性的多阶段决策过程
多阶段决策过程(3)
在具有无后效性的多阶段决策过程中，uk由 xk 决定，rk 和xk+1 由xk 和uk 决定，因此
决策可以写为 uk(xk ) 阶段效应可以写为 rk(xk , uk ) 状态xk+1=Tk(xk , uk ) 称为状态转移方程，其中
动态规划就是解决这种多阶段决策过程的方法
多阶段决策过程(1)
一般的多阶段决策过程表示如下
u1
u2
uk
x1 T1 x2 T2 x3 … xk Tk xk+1… xn
un Tn xn+1
r1
r2
rk
rn
其中包含n个决策子问题，每个子问题称为一个阶段，用变量k表示，称为阶段变量
xk描述k 阶段初系统的状况，称为状态变量
运筹学
第五章动态规划
本章重点
动态规划的四大要素、一个方程动态规划问题的建模与求解
动态规划概念(1)
前面介绍的线性规划研究的是一次性的决策
线性规划决策过程可以总结为
在给定资源和环境的情况下，决定变量的取值，使某个目标达到最大或最小值
这个决策过程可以表示如下图
u
其中u 表示决策变量
x1
➢每个阶段有一个输入状态和一个输出状态
➢一般把输入状态称为该阶段的阶段状态
多阶段决策过程(2)
uk 代表k 阶段对第k 子问题进行的决策，称uk为k
阶段的决策变量，uk的一组确定的取值称为一个
决策
rk 表示k 阶段从状态xk 出发做决策uk 之后产生的
后果，称为k 阶段的阶段效应
若在上述的多阶段决策过程中，系统 k 阶段以后的决策只与 k 阶段系统的状态 xk 有关，而与系统以前的决策无关，则称该多阶段决策过程具有无后效性
决策
x2 x1 表示决策所依赖的资源和环境
Z表示目标函数
Z
x2 表示决策后的资源和环境状况
动态规划概念(2)
例如，前面讲过的生产计划问题就是一次决策
某工厂用三种原料生产三种产品，已知的条件如下表所示，试制订总利润最大的日生产计划
产品所需原料数量产品Q1
（公斤/ 件）
（件）
原料P1
2
原料P2
0
示例(5.1-1)
前面讲过的生产计划问题
某工厂用三种原料生产三种产品，已知的条件如下表所示，如连续生产一周，每天投入一定量的原料，剩余的原料后面可以继续使用，每天只允许生产一种产品并获得相应的利润。试制订总利润最大的周生产计划(只建模，不求解)
产品所需原料数量产品Q1 产品Q2 产品Q3 原料可用量
（公斤/ 件）
（件）（件）（件）（公斤/日）
原料P1
2
3
0 1500
原料P2
0
2
4
800
原料P3
3
2
5 2000
产品的利润（千元/ 件）
3
5
4
示例(5.1-2)
设 uk1,2,3表示 k天第生产三种产种品的哪
设 xkxk1， xk2， xk3T表示 k天第开始生产的前数
2 3 0
Tk 是已知函数
多阶段决策过程中，从第k阶段到最终阶段的过程称为k-后部子过程，简称k-子过程
动态规划模型
动态规划模型如下
n
表示求和或加权求和
opt R
u 1 , ,u n
k
1
rk
xk ,u k
opt表示求最优(最大值或最小值)
x k 1 T k x k , u k
s
.t
原料P3
3
产品的利润（千元/ 件）
3
产品Q2
（件）
3 2 2
5
产品Q3
（件）
0 4 5
4
原料可用量（公斤/日）
1500 800 2000
动态规划概念(3)
设每天生产三种产品的件数分别为x1、x2、x3
其线性规划模型为
在这个模型中
u
模型中的A、b和C就是x1
模型中的X就是u
x1
决策
x2
模型中的f(X)=CX就是Z

运筹学第05章动态规划复习过程

合集下载