当前位置：文档之家 › 运筹学课件(动态规划)

运筹学课件(动态规划)

  • 格式：ppt
  • 大小：225.00 KB
  • 文档页数：41

下载文档原格式

  / 41

合集下载

第07章 动态规划 《运筹学》PPT课件

第07章 动态规划 《运筹学》PPT课件
最优路径问题 资源分配问题 排序问题 投资问题 装载问题 生产计划与库存问题 生产过程的最优控制等
动态规划
模型分类
离散确定型 离散随机型 连续确定型 连续随机型
§1 多阶 段决 策过 程的 最优
化
多阶段决策问题
(Multi-Stage decision process)
决策u1 决策u2
决策uk
32
维护费
8 8 9 9 10 6 6 8 8 10 5 6 8 9 5 5 6 4 54Βιβλιοθήκη 新设备购置费 5050
52 52 55 60
旧设备折价
20 15 10 5 2 30 25 20 15 10 31 26 21 15 33 28 20 35 30
40
§1 多阶 段决 策过 程的 最优
化
3)连续生产过程的控制 问题：一般化工生产过程中，
本章 内容
多阶段决策过程的最优化 动态规划的基本概念和基本原理 动态规划模型的建立与求解 动态规划在经济管理中的应用 马氏决策规划简介
创始时间 创始人
上个世纪50年代
美国数学家贝尔曼 （Richard. Bellman)
是运筹学的一个主要分支 是解决多阶段决策过程的最优化的一
种方法多阶段决策过程： 多阶段决策过程的最优化的目标： 达到整个活动过程的总体效果最优 •主要用于解决：
不过，实际中尚有许多不包含时间 因素的一类“静态”决策问题，就其本 质而言是一次决策问题，是非动态决策 问题，但是也可以人为地引入阶段的概 念当作多阶段决策问题，应用动态规划 方法加以解决。
§1 多阶 段决 策过 程的 最优
化
4）资源分配问题：便属于这类静 态问题。如：某工业部门或公司，拟对 其所属企业进行稀缺资源分配，为此需 要制定出收益最大的资源分配方案。这 种问题原本要求一次确定出对各企业的 资源分配量，它与时间因素无关，不属 动态决策，但是，我们可以人为地规定 一个资源分配的阶段和顺序，从而使其 变成一个多阶段决策问题(后面我们将 详细讨论这个问题)。

运筹学课件

运筹学课件
f k （ sk ） = f 5 （ s5 ） = max
0≤ uk≤ sk
{ 8 uk + 5（ sk - uk ）+ fk+1（sk+1）}，k= 4，3，2，1 （ ， ， ， ， { 8 u5 + 5 （ s5 - u5 ）}
max
0≤ u5≤ s5
9、逆序递推求解动态规划基本方程。 、逆序递推求解动态规划基本方程。 k=5
uk* = s 3
5
动态规划 Dynamic Programming （DP） ）
动态规划——Dynamic Programming 动态规划
建立 DP 模型与求解 k=2 f2 （ s 2 ） =
0 ≤ u2 ≤ s2
Max
[ 9x2 + f3（s3）] = Max [ 9x2 + 2s32 ]
8.
建立动态规划基本方程：（逆序递推方程） 建立动态规划基本方程：（逆序递推方程） ：（逆序递推方程 fk （ s k ） = max
0 ≤ uk ≤ sk
[ gk（xk）+ fk+1（sk+1）] ，k = 3，2，1 ， ，
f4 （ s 4 ） = 0
4
动态规划 Dynamic Programming （DP） ）
3
动态规划 Dynamic Programming （DP） ）
动态规划——Dynamic Programming 动态规划
建立 DP 模型与求解
1. 动态规划结构图
k阶段 阶段
k+1阶段 阶段
max
sk

gk（xk） 0 ≤ uk ≤ sk
sk+1 = sk - uk

运筹学课件--动态规划

运筹学课件--动态规划
J 表示留在左岸的仆人人数
初始状态s1是T(3,3)
结束状态sn是 T(0,0)
可达状态有哪些?(3,J) (2,2) (1,1) (0,J) J 3 2 1 0
2013-6-9
A
1
运筹学课件
2
3
I
阶段指标——每阶段选定决策xk后所产生的效益，记
vk= vk(Sk， xk)。
指标函数——各阶段的总效益，记相应于Pkn的指标函数
2013-6-9 运筹学课件
动态规划模型的分类： 以“时间”角度可分成：
离散型和连续型。
从信息确定与否可分成：
确定型和随机型。
从目标函数的个数可分成： 单目标型和多目标型。
2013-6-9 运筹学课件
8.2基本概念与方程
1.基本概念
阶段（Stage）——分步求解的过程，用阶段变量k表示，k=1，，n 状态（State）——每阶段初可能的情形或位置，用状态变 量Sk表示。 按状态的取值是离散或连续，将动态规划问题分为
当 k 3，f Max f v
3 0
3 3
3
4
Max 3x 5s 13.6(0.9s 0.2x )
0
3 3
3
3
3
3
Max 0.28x 17.24s
0
3 3
3
3

x s , f 17.52s ,即第3年初将全部完好机器都 投入高负荷。
指标函数vkn=
v

5
表示第k至5年的总产量；
1
递推公式：f Max f v
6

f 0, k 5, ,1
2013-6-9
运筹学课件

运筹学课件 第六章 动态规划

运筹学课件 第六章 动态规划

求解规划问题可从最终阶段逐步推至最初阶段或从 最初阶段逐步推至最终阶段，我们称前者为逆序解 法，称后者为顺序解法。
动态规划的基本方程（逆序法）：
fk (sk) = opt { wk(sk,uk )⊙ f k+1(sk+1) }
fn+1(sn+1) = φ(sn+1) f k ( sk) — 从第k阶段状态sk到终点的最优效益值
fk (sk+1)=max { vk(xk ) + f k-1(sk) }
f0(x1)=0
0
0
0
0
0
17 14
1
0
3
14
4
01
5
15
01
8
12
7
11
4
8
5
0 10 2 0
20
29
4
4
7
13
7
5
11
8
6
16 3 0
4
30
5
3
0 18
40
40
4
连续型动态规划问题的求解
例:某公司有资金10万元，若投资于项目i的投资额 为xi（i = 1 , 2 , 3)时，其收益分别为 g 1(x1)=2 x12, g 2 ( x 2 ) = 9 x2 , g 3 ( x 3 ) = 4 x3, 问应如何分配投资
第六章 动态规划
6.1 引言 6.2 最优化原理及基本概念 6.3 应用举例
例 6.1
多阶段决策过程最优化
多阶段决策过程，是指一类特殊的过程，它们可以按 时间顺序分解成若干个相互联系的阶段，称为“时段”， 在每个时段都要做决策，全部过程的决策是一个决策序列。 多阶段决策问题也称为序贯决策问题。

运筹学教材课件(第四章动态规划)

运筹学教材课件(第四章动态规划)

最优解的存在性
对于多阶段决策问题，如果每个 阶段的决策空间是有限的，则存 在最优解。
最优解的唯一性
对于某些多阶段决策问题，可能 存在多个最优解。在这种情况下， 我们需要进一步分析问题的性质 和约束条件，以确定最优解的个 数和性质。
最优解的稳定性
在某些情况下，最优解可能受到 参数变化的影响。我们需要分析 最优解的稳定性，以确保最优解 在参数变化时仍然保持最优。
VS
详细描述
排序问题可以分为多种类型，如冒泡排序 、快速排序、归并排序等。动态规划可以 通过将问题分解为子问题，逐一求解最优 解，最终得到全局最优解。在排序问题中 ，动态规划可以应用于求解最小化总成本 、最大化总效益等问题。
04
动态规划的求解方法
逆推法
逆推法
从问题的目标状态出发，逆向推算出达到目标状态的 最优决策，直到达到初始状态为止。
案例二：投资组合优化问题
要点一
总结词
要点二
详细描述
投资组合优化问题是动态规划在金融领域的重要应用，通 过合理配置资产，降低投资风险并提高投资收益。
投资组合优化问题需要考虑市场走势、资产特性、风险偏 好等多种因素，通过动态规划的方法，可以确定最优的投 资组合，使得投资者在风险可控的前提下，实现收益最大 化。
详细描述
在背包问题中，给定一组物品，每个物品都有一定的重量和价值，要求在不超过背包容量的限制下， 选择总价值最大的物品组合。通过动态规划的方法，可以将背包问题分解为一系列子问题，逐一求解 最优解。
排序问题
总结词
排序问题是动态规划应用的另一个重要 领域，主要涉及到将一组元素按照一定 的顺序排列，以达到最优的目标。
本最小化和效率最大化。
感谢您的观看

运筹学课程动态规划课件

运筹学课程动态规划课件

5 A
3
1 B1 3
6
8 B2 7
6
C1 6 8
3 C2 5
3 C3 3
84 C4
2 D1
2
D2 1 2
3 D3
3
E1 3
5 5 E2 2
6 6
E3
F1 4
G 3 F2
1
2
3 4 运筹学课程动态规划
5
6
7
示例5（生产与存储问题）：
某工厂生产并销售某种产品。已知今后四个月市场需求 预测及每月生产j个单位产品的费用如下：
上一个阶段的决策直接影响下一个阶段的决策
运筹学课程动态规划
8
示例6（航天飞机飞行控制问题）：
由于航天飞机的运动的环境是不断变化的，因 此就要根据航天飞机飞行在不同环境中的情况， 不断地决定航天飞机的飞行方向和速度（状态）， 使之能最省燃料和实现目的（如软着落问题）。
运筹学课程动态规划
9
所谓多阶段决策问题是指一类活动过程，它可以分为若 干个相互联系的阶段，在每个阶段都需要作出决策。这 个决策不仅决定这一阶段的效益，而且决定下一阶段的 初
1 6
C3
D1
10
E
D2
6
运筹学课程动态规划
12
以上求从A到E的最短路径问题，可以转化为四个性质完
全相同，但规模较小的子问题，即分别从 Di 、 Ci 、Bi、
A到E的最短路径问题。
第四阶段：两个始点 D 1 和 D 2 ，终点只有一个；
本阶段始点 （状态）
D1 D2
本阶段各终点（决策） E 10 6
cj30j
j0 j1,2,6
月1 2 3
4
需求 2 3 2

运筹学-第3版-课件-第5章 动态规划


C1
2
1 2 2 3
D1 D2
3
2
A
B2
5
C2
6
E
4
2
B3
C3
3
D3
同样的理由，可以递推得其余阶段的铺设路线，如阶 段3在C1点的决策是D1，阶段4在D1点的决策只有E点； 由于到E点是整个铺设管道的终点，至此，决策过程完成， 铺设一条A点到E点的管道是由四个阶段的管道组成的， 如A---B3---C1---D1---E，它也称为一个策略。
B
阶段2
C
阶段3
D
阶段4
E
5
B1
4 4
6
3 6
C1
2
1 2
2
D1 D2 D3
3 4
2
A
B2
5
C2
6
E
2
3
B3
C3
3
在阶段2，从B3点出发，只有C1、C3两种可 选择的点， 如选C1,则C1就是阶段2在B3点的决策结果； C1点既是阶段2铺设管道的终点，又是阶段3 铺设管道的起点；
5
B1
4 4
6 3 6
使S= f ( xi ) 16 u j =
i 1 6 t
f ( x ) 16(5x
为最小，其中
i 1 i
6
j 1
1
4 x2 3x3 2 x4 x5 185)
100xi ,0 xi 15 f ( xi ) 120xi 300,15 < xi 30
第5章 动态规划
运 筹 帷 幄 之 中 Dynamic Programming
决 胜 千 里 之 外

运筹学课件 第五章动态规划

2013-11-30 11

(1)在第四阶段 此时只要再走一步即到终点⑩ (B地)。 目前状态 s4可以是⑧或⑨，可选择的下一状 态X4 是⑩ 所以f4 (8) =d4 (8, 10) =3, f4 (9)=d4 (9, 10)=4 (2)在第三阶段 在第三阶段，还需两步才能到达终点，此时 f3 ( s3)=min{d3 ( s3，X3)+f4 (s4)} 目前状态s3可 以是⑤、⑥、⑦，可选择的下一状态X3有两个 点⑧或⑨
通过计算，可知从 A地到 B地总路程最小 值为 11。
2013-11-30 16
三、动态规划的基本概念

1、阶段： 把所给问题的过程恰当地分为 若干个相互联系的阶段，以便能按一定的次序 去求解。描述阶段的变量称为阶段变量，常用 k 表示。 阶段的划分，一般是根据时间和空间的自然 特征来划分，但要便于把问题的过程能转化为 多阶段的决策过程，如例 1中可分为4个阶段来 求解，k=1, 2, 3, 4。
uk
2013-11-30 27
* pk ,n 表示sk sn的最优策略, 则最优值函数
基本方程 f k ( sk ) opt vk ( sk , u k ) f k 1 ( sk 1 ) u k Dk sk 1 Tk ( sk , u k ) k 1,2, , n f (s ) 0 n 1 n 1 这是一个逆推方程.
2013-11-30 20
4.策略 策略：决策按顺序构成的序列，用p表示。
p k ,n ( sk ) : 第k阶段起至第n阶段止的策略 pk ,n ( sk ) {uk ( sk ), uk 1 ( sk 1 )... , un ( sn )} 当k 1时. p1,n ( s1 )为全过程策略. p1,n ( s1 ) P ,n ( s1 ) 1

运筹学课件动态规划


C4 A — B— C — D — E
f2(C1)=7,f3(C2)=8,f3(C3)=10,f3(c4)=9
阶段1
阶段2 阶段3 阶段4
S0={A} S1={B1,B2} S2={C1,C2,C3,C4 } S3={D1,D2} S4={E}
f3(D1)=11,f4(D2)=13
案例---资源分配
D1 5 E
D2 2
[引例] 马车驿站问题
f(C1)=8
阶段 起点 1A
终点
B1 B2
可选路线
AB1 AB2
路线数 2
f(B1)=8
B1 5 A
f(A)=313 8
B2
2 3 6
7 6
C1 6
f(C2)=85
C2 3
f(C3)=54
3 C3 3
84
f(B2)=11 C4
f(C1)=5
A —B— C —
最k优=4化原理
(Optimality principle) :
最k优=3策略具备这样的决性策质：:无D1论初E始 状态与初始决策如何,以后诸决策对 以第一个决策所形成的状态作为初 始状态的过程而言,必决然策构：成D2最优E策 策略.通俗地说:最优策略的子策略 也k是=2最优的.
例 A13—k如,其=B1，子1—在策C导略2入—:B案D11—例—C中决E2决决，,—策最策策最D：短：：1优A距—CC策12离E略B,为1DD是11 C2—D1—E, D1—E也决是策最：优C3的。D2
（4）状态转移方程 （5）递归方程（k→n）
1、划分为4个阶段 2、用点集表示各阶段的状态 S1=｛A｝;s2= ｛B1,B2,B3｝, s3= ｛C1,C2,C3｝; s4= ｛D1,D2｝ 3、指标函数：Vk，4（i）为第k阶段第i点到E点的距离 4、最优值函数fk（i）为i点到E的最短距离 5、决策变量xk=d[i,j]为第k阶段第i状态的选择 6、边界条件： f5（E）=0 7、基本方程： fk（i）=min｛d[i,j]+ fk+1（j） ｝(k=1,2,3,4)

运筹学课件(动态规划)


（二）、动态规划的基本思想 1、动态规划方法的关键在于正确地写出基本的递推 关系式和恰当的边界条件（简称基本方程）。要做到 这一点，就必须将问题的过程分成几个相互联系的阶 段，恰当的选取状态变量和决策变量及定义最优值函 数，从而把一个大问题转化成一组同类型的子问题， 然后逐个求解。即从边界条件开始，逐段递推寻优， 在每一个子问题的求解中，均利用了它前面的子问题 的最优化结果，依次进行，最后一个子问题所得的最 优解，就是整个问题的最优解。
d( B1,C1 ) + f1 (C1 ) 3+1 f2 ( B1 ) = min d( B1,C2 ) + f1 (C2 ) = min 3+3 d( B1,C3 ) + f1 (C3 ) 1+4 4 = min 6 = 4 (最短路线为B1→C1 →D) 5
3
2 A 4 B2 B1 2 1 3
最优策略为（30，20），此时最大利润为105万元。
f 2 ( 40)
g2 ( y) y 0 ,10 ,, 40
max
f1 ( 40 y )
90
最优策略为（20，20），此时最大利润为90万元。
f 2 (30)
g2 ( y) y 0 ,10 , 20 , 30
max
f1 (30 y )
70
最优策略为（20，10），此时最大利润为70万元。
f 2 ( 20) ma 0 ,10 , 20
50
最优策略为（20，0），此时最大利润为50万元。
f 2 (10) maxg 2 ( y ) f1 (10 y )
3 2 A 4 B2 B1 2 3 1 3 1
C1 C2 4 3
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

3 2 A 4 B2 B1 2 3 1 3 1
C1 C2 4 3
1 D
C3
最短路线为
A→B1→C1 →D
练习：
1 5 A 3 B2 C1 6 8 5 D2 3 8 4 D3 3 E3 1 D1 2 2 E1 5 6 3 5 2 6 F2 F1 4 G
B1
6 8 7
3
C2
3
3
2
E2
6
C3
3
C4
最优路线为：A → B1 → C2 → D1 → E2 → F2 → G
20 50 20
30 65 30
40 80 40
50 85 50
60 85 60
利润
f1(x) ＝ g1(x)
最优策略
第二阶段：求 f2(x)。此时需考虑第一、第二个工厂如 何进行投资分配，以取得最大的总利润。
f 2 (60)
g2 ( y ) y 0 ,10 ,, 60
max
f1 (60 y )
g 2 (0) f1 (60) 0 85 g (10) f (50) 20 85 1 2 g 2 (20) f1 (40) 40 80 max g 2 (30) f1 (30) max50 65 120 g (40) f (20) 55 50 1 2 g 2 (50) f1 (10) 60 20 65 0 g 2 (60) f1 (0)
最优策略为（40，20），此时最大利润为120万元。 同理可求得其它 f2(x) 的值。
f 2 (50)
g2 ( y) y 0 ,10 ,, 50
max
f1 (50 y )
g 2 (0) f1 (50) g (10) f ( 40) 1 2 g 2 ( 20) f1 (30) 105 g 2 (30) f1 ( 20) g 2 ( 40) f1 (10) g 2 (50) f1 (0)
max
f1 (30 y )
70
最优策略为（20，10），此时最大利润为70万元。
f 2 ( 20) max g 2 ( y ) f1 ( 20 y )
y 0 ,10 , 20
50
最优策略为（20，0），此时最大利润为50万元。
f 2 (10) maxg 2 ( y ) f1 (10 y )
4、策略：是一个按顺序排列的决策组成的集合。在 实际问题中，可供选择的策略有一定的范围，成为允 许策略集合。从允许策略集合中找出达到最优效果的 策略称为最优策略。 5、状态转移方程：是确定过程由一个状态到另一个 状态的演变过程，描述了状态转移规律。 6、指标函数和最优值函数：用来衡量所实现过程优 劣的一种数量指标，为指标函数。指标函数的最优值， 称为最优值函数。在不同的问题中，指标函数的含义 是不同的，它可能是距离、利润、成本、产量或资源 消耗等。
动 态 规 划
(Dynamic programming)
动态规划的基本思想
最短路径问题
投资分配问题 背包问题
动态规划是用来解决多阶段决策过程最优 化的一种数量方法。其特点在于，它可以把一 个n 维决策问题变换为几个一维最优化问题，从 而一个一个地去解决。
需指出：动态规划是求解某类问题的一种 方法，是考察问题的一种途径，而不是一种算 法。必须对具体问题进行具体分析，运用动态 规划的原理和方法，建立相应的模型，然后再 用动态规划方法去求解。
第三阶段：求 f3(x)。此时需考虑第一、第二及第三个 工厂如何进行投资分配，以取得最大的总利润。
f 3 (60)
g3 ( y ) y 0 ,10 ,, 60
max
f 2 (60 y )
g3 (0) f 2 (60) 0 120 g (10) f (50) 25 105 2 3 g3 (20) f 2 (40) 60 90 max g3 (30) f 2 (30) max85 70 155 g (40) f (20) 100 50 2 3 g3 (50) f 2 (10) 110 20 115 0 g3 (60) f 2 (0)
路长＝18
三、投资分配问题
现有数量为a（万元）的资金，计划分配给n 个工厂, 用于扩大再生产。 假设：xi 为分配给第i 个工厂的资金数量（万元） ； gi(xi)为第i 个工厂得到资金后提供的利润值（万元）。 问题是如何确定各工厂的资金数，使得总的利润为 n 最大。 据此，有下式： m ax Z g i ( x i )
C1
C2 4 C3 3
1 D
3 1
d( B2,C1 ) + f1 (C1 ) 2+1 f2 ( B2 ) = min d( B2,C2 ) + f1 (C2 ) = min 3+3 d( B2,C3 ) + f1 (C3 ) 1+4 3 = min 6 = 3 (最短路线为B2→C1 →D) 5
3
3 1
解：整个计算过程分三个阶段，从最后一个阶段开始。
第一阶段（C →D）： C 有三条路线到终点D 。
显然有 f1 (C1 ) = 1 ； f1(C2 ) = 3 ； f1 (C3 ) = 4
3
2 A 4 B2 B1 2 1 3
C1
C2 4 C3 3
1 D
3 1
第二阶段（B →C）： B 到有六条路线。
（三）、建立动态规划模型的步骤 1、划分阶段 划分阶段是运用动态规划求解多阶段决策问题的第一 步，在确定多阶段特性后，按时间或空间先后顺序， 将过程划分为若干相互联系的阶段。对于静态问题要 人为地赋予“时间”概念，以便划分阶段。
2、正确选择状态变量
选择变量既要能确切描述过程演变又要满足无后效性， 而且各阶段状态变量的取值能够确定。一般地，状态 变量的选择是从过程演变的特点中寻找。 3、确定决策变量及允许决策集合 通常选择所求解问题的关键变量作为决策变量，同时 要给出决策变量的取值范围，即确定允许决策集合。
（二）、动态规划的基本思想 1、动态规划方法的关键在于正确地写出基本的递推 关系式和恰当的边界条件（简称基本方程）。要做到 这一点，就必须将问题的过程分成几个相互联系的阶 段，恰当的选取状态变量和决策变量及定义最优值函 数，从而把一个大问题转化成一组同类型的子问题， 然后逐个求解。即从边界条件开始，逐段递推寻优， 在每一个子问题的求解中，均利用了它前面的子问题 的最优化结果，依次进行，最后一个子问题所得的最 优解，就是整个问题的最优解。
d( B1,C1 ) + f1 (C1 ) 3+1 f2 ( B1 ) = min d( B1,C2 ) + f1 (C2 ) = min 3+3 d( B1,C3 ) + f1 (C3 ) 1+4 4 = min 6 = 4 (最短路线为B1→C1 →D) 5
3
2 A 4 B2 B1 2 1 3
y 0 ,10 ,
20 最优策略为（10，0）或（ 0 ， 10 ） ，此时最大利润 为20万元。
f2(0) ＝0。最优策略为（0，0），最大利润为0万元。 得到下表
投资 利润
0 0
10 20
20 50
30 70
40 90
50 105
60 120
f2(x) 最优策略
(0,0) (10,0) (20,0) (20,10) (20,20) (30,20) (40,20) (0,10)
二、最短路径问题
例一、从A 地到D 地要铺设一条煤气管道,其中需经过 两级中间站，两点之间的连线上的数字表示距离，如 图所示。问应该选择什么路线，使总距离最短？
3
2 A 4 B2 B1 2 1 3 C2 4 C3 3
C1
1 D
3 1
3
2 A 4 B2 B1 2 1 3
C1
C2 4 C3 3
1 D
最优策略为（30，20），此时最大利润为105万元。
f 2 ( 40)
g2 ( y) y 0 ,10 ,, 40
max
f1 ( 40 y )
90
最优策略为（20，20），此时最大利润为90万元。
f 2 (30)
g2 ( y) y 0 ,10 , 20 , 30
gk(y) ＋ fk－1(x－y)
所以，根据动态规划的最优化原理，有下式：
f k ( x ) maxg k ( y ) f k 1 ( x y )
0 y x
其 中k 2.3..n
如果a 是以万元为资金分配单位，则式中的y 只取 非负整数0，1，2，…，x。上式可变为：
2、在多阶段决策过程中，动态规划方法是既把当前 一段和未来一段分开，又把当前效益和未来效益结合 起来考虑的一种最优化方法。因此，每段决策的选取 是从全局来考虑的，与该段的最优选择答案一般是不 同的. 3、在求整个问题的最优策略时，由于初始状态是已 知的，而每段的决策都是该段状态的函数，故最优策 略所经过的各段状态便可逐段变换得到，从而确定了 最优路线。 最优化原理：作为整个过程的最优策略具有这样的 性质：无论过去的状态和决策如何，相对于前面的决 策所形成的状态而言，余下的决策序列必然构成最优 子策略。”也就是说，一个最优策略的子策略也是最 优的。
4、确定状态转移方程
根据k 阶段状态变量和决策变量，写出k+1阶段状态变 量，状态转移方程应当具有递推关系。
5、确定阶段指标函数和最优指标函数，建立动态规 划基本方程
阶段指标函数是指第k 阶段的收益，最优指标函数是 指从第k 阶段状态出发到第n 阶段末所获得收益的最优 值，最后写出动态规划基本方程。 以上五步是建立动态规划数学模型的一般步骤。由 于动态规划模型与线性规划模型不同，动态规划模型 没有统一的模式，建模时必须根据具体问题具体分析， 只有通过不断实践总结，才能较好掌握建模方法与技 巧。