当前位置：文档之家 › 运筹学04动态规划1-123页文档

运筹学04动态规划1-123页文档

  • 格式：ppt
  • 大小：1.09 MB
  • 文档页数：123

下载文档原格式

  / 123

合集下载

动态规划(运筹学)

动态规划(运筹学)

k阶段的允许决策集合
四、状态转移方程 sk+1与sk,xk之间必须能够建立一种明确的数量对应关系，记为
Tk(sk,xk), 即有 sk+1 = Tk(sk,xk)
这种明确的数量关系称为状态转移方程。
五、策略
由各阶段决策xk构成的决策序列,称为全过程策略,简称策略,记为
p1(s1),有
p1(s1) = { x1(s1),x2(s2),… ,xn(sn)} ∈P1
xk∈Xk
f*n+1(sn+1) = 1 积 f*k(sk)xk=∈Xok pt {vk(sk,xk) ×fk+1*(sk+1)}
k = n, n-1, …, 2, 1 k = n, n-1, …, 2, 1
11
三、基本步骤
1°建立模型
(1) 划分阶段，设定 k (2) 设定状态变量 sk
(3) 设定决策变量 xk
3） 阶段指标函数。第k阶段装载 件货物时所创的利润 。 vk xk
4） 函数的基本方程为
fk
sk
opt
xk Dk sk
vk xk fk1 sk wk xk k 1, 2,3
sk 0,1, ,6
f4
s4
0
k=3时
w3 4, v3 18
s3 0,1, , 6
x3
0,1,
六、运输时间须控制在合理范围之内（如集装箱干线船的班期）。
ZH物流公司是一家大型的集装箱多式联运经营企业，在成都设有内 陆集装箱货运站（CFS），经营成都——上海间集装箱货物运输服务，其多式 联运通道的主要节点城市为南京与郑州。现有一个货主需要将2个20英尺的集装 箱从成都运往上海，运输路线为成都-郑州-南京-上海，要求在货物起运后2530小时之内到达目的地。

运筹学动态规划04

运筹学动态规划04
(Dynamic programming)
1
概述
1951年Bellman提出，1957《动态规划》
动态规划是解决多阶段决策问题的一种数学方法。 动态规划思想：把多阶段决策问题变换为一系列互相联系的 单阶段问题，然后逐个加以解决。即：把一个n 维决策问题 变换为几个一维最优化问题，从而一个一个地去解决。 需指出：动态规划是求解某类问题的一种方法，是考察问题 的一种途径，而不是一种算法。必须对具体问题进行具体分 析，运用动态规划的原理和方法，建立相应的模型，然后再 用动态规划求解方法去求解。 应用：最短路线、资源分配、生产调度问题
fk (s k ) opt V k n (s k ,u k , ,s n
u k ,,u n
,
) 1
在不同的问题中，指标函数的含义是不同的，它 可能是距离、利润、成本、产量或资源消耗等。
21
小结: 动态规划本质上是多阶段决策过程;
要求：无后效性
概念 : 阶段变量k﹑状态变量sk﹑决策变量uk
* 1
* 2
* n
最优目标函数值
* V1,n * * * 从 k 到终点最优策略 * * V1,n ( s1 , u1 ,, sn , un )
子策略的最优目标函数值
f s opt v s , u
k k
u
k
,,
un
k ,n
k
k
, , sn1

24
三、动态规划基本思想
1、动态规划方法的关键在于正确地写出基本的递推 关系式和恰当的边界条件（简称基本方程）。要做到 这一点，就必须将问题的过程分成几个相互联系的阶 段，恰当的选取状态变量和决策变量及定义最优值函 数，从而把一个大问题转化成一组同类型的子问题， 然后逐个求解。即从边界条件开始，逐段递推寻优， 在每一个子问题的求解中，均利用了它前面的子问题 的最优化结果，依次进行，最后一个子问题所得的最 优解，就是整个问题的最优解。

运筹学04-动态规划(2)

运筹学04-动态规划(2)

s4 7711
u
5
s5
s5
397
g5 (s5 ,u5 ) 3176
f5(s5) 13.6 s5 3176
s6 0.7u5 0.9(s5 u5 ) 0.7x5 278
乘积形式的目标函数
可靠性问题
……
部件1
部件2
部件n
一个工作系统由个部件串联组成。只要
有一个部件失灵，整个系统就不能工作。
随机型动态规划
某部门欲采购一批原料，原料价格在五周内可能有 所变动，已预测得该种原料今后五周内取不同价格 的概率如下表所示。试确定该部门在五周内购进这 批原料的最优策略，使采购价格的期望值最小
u
2
0
s2 900
g2 (s2 , u2 ) 4500 f2 (s2 ) 20.8s2 18720
u3 s3 s3 810 g3 (s3 ,u3 ) 6480 f3(s3) 17.55 s3 14216
u
4
s4
s4
567 g4 (s4 , u4 )
4536
f4(s4) 13.6
s数0k.与6数，u值k就均时表取，示连可一续以台变这机量样器。理在当解k它年：们度如有中果非正sk常整＝ 工示作一时台间机只床占在6k年/10度；只如有uk4=/100的.4，时就间表于 高负荷下工作。
2．状态转移方程为
sk1 auk b(sk uk ) 0.7uk 0.9(sk uk ),
dh1/dx1=4+4(s1-x1)(-1)=0 解得
x1=s1-1
而
d2h1/dx12=1>0
所以 x1=s1-1 是极小点， 比较[0，10]两个端点， x1=0时, f1(10) = 200 x1=10时, f1(10) = 40 所以 x1*=0

运筹学课件--动态规划

运筹学课件--动态规划
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
运筹学课件

运筹学(动态规划1)

运筹学(动态规划1)
9
2.动态规划的基本概念
（三）决策、决策变量和允许决策集合 所谓决策，就是确定系统过程发展的方案。 决策的实质是关于状态的选择，是决策者从给定 阶段状态出发对下一阶段状态作出的选择。 用以描述决策变化的量称之决策变量。和 状态变量一样，决策变量可以用一个数，一组数 或一向量来描述，也可以是状态变量的函数，记 以uk= uk(sk)，表示于阶段k状态sk时的决策变量。 决策变量的取值往往也有一定的允许范围， 称之允许决策集合。决策变量uk(sk)的允许决策 集用 Uk(sk) 表示 , uk(sk)∈ Uk(sk) 允许决策集合 实际是决策的约束条件。
sk 1 Tk ( sk , uk ( 划的基本概念
通常称式(5-1)为多阶段决策过程的状态转移方 程。有些问题的状态转移方程不一定存在数学 表达式，但是它们的状态转移，还是有一定规 律可循的。 (六) 指标函数 用来衡量策略或子策略或决策的效果的某 种数量指标，就称为指标函数。它是定义在全 过程或各子过程或各阶段上的确定数量函数。 对不同问题，指标函数可以是诸如费用、成本、 产值、利润、产量、耗量、距离、时间、效用， 等等。例如：图5—1的指标就是运费。
10
2.动态规划的基本概念
（四）、策略和允许策略集合 策略 (Policy) 也叫决策序列．策略有全过程 策略和k部子策略之分，全过程策略是指具有n个 阶段的全部过程，由依次进行的 n 个阶段决策构 成 的 决 策 序 列 ， 简 称 策 略 ， 表 示 为 p1,n{u1,u2,…,un}。从k阶段到第n阶段，依次进行 的阶段决策构成的决策序列称为 k部子策略,表示 为pk,n{uk,uk+1,…,un} ，显然当k=1时的k部子策略 就是全过程策略。 在实际问题中，由于在各个阶段可供选择的决策 有许多个，因此，它们的不同组合就构成了许多 可供选择的决策序列(策略)，由它们组成的集合， 称之允许策略集合，记作P1,n ，从允许策略集中， 找出具有最优效果的策略称为最优策略。 11

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

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

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

运筹学04动态规划1

S3
0 1 2
f3(S 3)
d
*
3
S3
3 4 5
f3(S 3)
d
*
3
0 4 7
0 1 2
9 10 11
3 4 5
店 数 0 1 2
2
区 1 0 3 7 2 0 5 10 3 0 4 7
店 数 3 4 5
区 1 12 14 15 2 14 16 16 3 9 10 11
k=2 时， 计算如下：
d
S3=S2-d2
4 E1 2 D1
动态规划的基本概念
阶段；
状态； 决策和策略；
状态转移；
指标函数。
1 阶段（Stage）
将所给问题的过程，按时间或 空间特征分解成若干个相互联系的 阶段，以便按次序去求每阶段的解。 用以描述阶段的变量叫作阶段变量， 一般以k表示阶段变量。
2 状态（State）
各阶段开始时的客观条件叫做 状态。描述各阶段状态的变量称为 状态变量，常用sk表示第k阶段的 状态变量，状态变量的取值集合称 为状态集合，用Sk表示。状态集合 可以是一离散取值的集合，也可以 为一连续的取值区间，视具体问题 而定。
动态规划是现代企业管理 中的一种重要决策方法，可用 于最优路径问题、资源分配问 题、生产计划和库存问题、投 资问题、装载问题、排序问题 及生产过程的最优控制等。
动态规划的基本原理
多阶段决策过程最优化 多阶段决策过程是指这样一类 特殊的活动过程，他们可以按时间 顺序分解成若干相互联系的阶段， 在每个阶段都要做出决策，全部过 程的决策是一个决策序列，所以多 阶段决策问题也称为序贯决策问题。
动态规划数学模型由最优指标函数递推表达式、边界 条件及状态转移方程构成。

运筹学：第4章 动态规划 动态规划第1节

?阶段指标k阶段状态下决定决策后所产生的效益记为?指标函数各阶段的总效益相应于由阶段k状态出发到终点的后部子策略pkn的指标函数记为?由阶段k状态sk出发到终点的所有可能的后部子策略产生的指标函数中最优者称最优指标函数记为??kkkxsts1????kkkkxsvv?knkknknpsvv?????knkknkkpsoptvsf?kksf?说明状态转移策略阶段指标指标函数?问题
opt {v k(sk
x k D k (sk )
1) 0，k
,x k ) n,n

fk 1(sk 1
1, ,2,1
)}
n
指标函数为阶段指标之 和，即 V kn v i(si ,xi )
或
i k
fk(sk )
fn 1(sn
opt {v k(sk
x k D k (sk )
1) 1，k
,x k ) n,n
P* 14
AB2C 1D1E
f1 19
最短路 最短距离
• 总结以上求解过程，可用如下递推方程表示
fk(s k
)
x
k
min
D k (sk
{v
)
k(s
k
,x
k
)
fk 1(sk 1 )}
f5(s5 ) 0，k 4,3,2,1
一般动态规划基本（逆序递推）方程表示为：
fk(sk )
fn 1(sn
表示两点间距离。现需选一条由A到E的旅行路线， 使总距离最短。
• 以上两个例子代表了这样一种特殊的决策 过程，该过程可分为互相联系的若干阶段， 每一阶段都需做出决策，从而形成全过程 的决策。这种把一个问题看作一个前后关 联具有链状结构的多阶段过程称为多阶段 决策过程，也称序贯决策过程，相应的问 题称为多阶段决策问题。

运筹学课程动态规划课件


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

运筹学课件(动态规划)


（二）、动态规划的基本思想 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)。

s3 ... sk
阶段k
状态
状态
sk+1 ... sn
阶段n
状态 sn+1
g1
g2
gk
gn
例1（不定阶段最短路线问题）
如图是一个五座城市的及其相连道路的交通图，线上的数字是对应的路 长。问：应如何选择行驶路线，才能使从A、B、C、D各城市到E城市的行 驶路程最短？
E
2
3
2
A
D
7
5
6
5
5
1
B
C
0.5
2 状态（State）
各阶段开始时的客观条件叫做状态。描述各阶段 状态的变量称为状态变量，常用sk表示第k阶段的状 态变量，状态变量的取值集合称为状态集合，用Sk 表示。状态集合可以是一离散取值的集合，也可以为 一连续的取值区间，视具体问题而定。
按照过程进行的先后，每个阶段的状 态可分为初始状态和终止状态，或称
fk(Sk)为当第k阶段初始状态为Sk时，从第k阶段 到最后阶段所得最大利润。
fk(Sk)=Max rk(dk) + fk+1(Sk+1)
dk (Sk)
k=1，2，3
f4(S4)= 0
k=3 时， 计算如下：
d d S3 f3(S3)
* 3
S3
f3(S3)
* 3
0 0 03 9 3
1 4 1 4 10 4
5
3
B1
4
C1
3
D3
5
E2
3
2
D2
4
F
4
2
E1
D1
A
B
C
D
E
F
4
A
3
4
1
C3
B2
2
2
3
C2
5
3
B1
4
C1
3
D3
5
E2
3
2
D2
4
F
4
2
E1
D1
A
B
C
D
E
F
4
A
3
4
1
C3
B2
2
2
3
C2
5
3
B1
4
C1
3
D3
5
E2
3
2
D2
4
F
4
2
E1
D1
A
B
C
D
E
F
4
A
3
4
1
C3
B2
2
2
3
C2
5
3
B1
4
C1
3
D3
5
E2
例 设备更新问题
企业在使用设备时都要考虑设备的更新问题，因 为设备越陈旧所需的维修费用越多，但购买新设备 则要一次性支出较大的费用。
多阶段决策问题
(Multi-Stage decision process)
多阶段决策过程特点:
决策d1
决策d2
决策dk
决策dn
状态 s1
阶段1
状态 s2
阶段2
状态
状态
在上面的计算过程中，利用了第k阶段与第k+1阶 段的关系：
fk(Sk)= Min r(Sk,dk(Sk))+fk+1(Sk+1)
dk(Sk)
k=1,2,3,4,5
f6(S6)=0
这种递推关系称为动态规划的函数基本方程。
贝尔曼(Ballman)最优化原理
作为整个过程的最优策略具有这样的性质:即无论 过去的状态和决策如何，对前面的决策所形成的状态 而言，余下的诸决策必须构成最优策略。这就是说， 不管引导到这个现时状态的头一个状态和决策是什么， 所有的未来决策应是最优的。
1.从A城市直达E城市，一个阶段。
2.从A城市通过其他B、C、D三城市之一到E城市，二个阶 段。 3.从A城市通过其他B、C、D三城市之二到E城市，三个阶 段。 4.从A城市通过其他B、C、D三城市各一次到E城市，四个 阶段。
例2（一定阶段最短路问题）
W先生每天驾车去公司上班。如图，W先生的住所位于A，公司位于F，图中的直线段代表公 路，交叉点代表路口，直线段上的数字代表两路口之间的平均行驶时间。现在W先生的问题是 要确定一条最省时的上班路线。
•正确地选择状态变量，使其具备两个必要特征：
（1）可知性：即过去演变过程的各阶段状态变量的取 值，能直接或间接地确定。
（2）能够确切地描述过程的演变且满足无后效性。
建立动态规划模型的要点：
•根据状态变量与决策变量的含义，正确写出状态转移
0
0000
1
5141
2
10 2 7 2
3
14 2,3 9 3
4
18 3 10 4
5 22 3 21 3 11 5
建立动态规划模型的要点：
•分析题意，识别问题的多阶段性，按时间或空间
的先后顺序适当地划分满足递推关系的若干阶段， 对非时序的静态问题要人为地赋予“时段”的概 念。
建立动态规划模型的要点：
2 7 9 10 - - - 10 2 3 9 12 14 14 - - 14 2,3, 4 10 14 17 18 16 - 18 3 5 11 15 19 21 20 16 21 3
k=1 时， 计算如下：
最优解：d*1 =3， d*2 =2，d*3 =0
即：在区1建3个分店，在区2建2个分店，而不在 区3建立分店。最大总利润=22。
动态规划数学模型由最优指标函数递推表达式、边界条件及状态转移方程构成。
fk(sk) Opt {rk(sk,dk}fk1(sk1)}, k1,2, ,n fn(sn)0dkDk(sk) sk1 Tr(sk,dk)
动态规划的优点：
•可把一个N维优化问题化成N个一维优化问题求解。 •DP方程中附加某些约束条件，可使求解更加容易。 •求得最优解以后，可得所有子问题的最优解。
3 决策和策略
（Decision and Policy）
当各段的状态确定以后，就可以做出不同的决定 （或选择），从而确定下一阶段的状态，这种决定 称为决策。决策变量用xk(Sk)表示，允许决策集合 用Dk(Sk)表示。
各个阶段决策确定后，整个问题的决策序列就构 成一个策略，用p1,n(x1,x2,…xn)表示。对每个实 际问题，可供选择的策略有一定的范围，称为允许 策略集合，用P表示。使整个问题达到最优效果的策 略就是最优策略。
A
B
C
D
E
F
4
A
3
4
1
C3
B2
2
2
3
C2
5
3
B1
4
C1
3
D3
5
E2
3
2
D2
4
F
4
2
E1
D1
A
B
C
D
E
F
4
A
3
4
1
C3
B2
2
2
3
C2
5
3
B1
4
C1
3
D3
5
E2
3
2
D2
4
F
4
2
E1
D1
A
B
C
D
E
F
4
A
3
4
1
C3
B2
2
2
3
C2
5
3
B1
4
C1
3
D3
5
E2
3
2
D2
4
F
4
2
E1
D1
A
B
C
D
E
F
4
A
3
4
1
4 状态转移方程
动态规划中本阶段的状态往往是上一阶段的决 策结果。如果给定了第k段的状态Sk ，本阶段决 策为xk(Sk) ，则第k+1段的状态Sk+1由公式： Sk+1=Tk（ Sk， xk）
确定，称为状态转移方程。
5 指标函数
用于衡量所选定策略优劣的数量指标称为指标函数
v(Sk,xk(Sk))。
第四章 动态规划
Dynamic Programming
本章内容重点
多阶段决策过程的最优化 动态规划的基本概念和基本原理 动态规划方法的基本步骤 动态规划方法应用举例
动态规划是解决多阶段决策过程最优化问题的一 种方法。由美国数学家贝尔曼（Bellman）等人在 20世纪50年代提出。他们针对多阶段决策问题的特 点，提出了解决这类问题的“最优化原理”，并成功 地解决了生产管理 、 工程技术等方面的许多实际问 题。
C3 4 D3
5 E2
2F
1
2
3
4
B2 2 C2 3 D2
E1
4
5
3
2
A3
B1 4 C1 3
D1
动态规划的基本概念 阶段； 状态； 决策和策略； 状态转移； 指标函数。
1 阶段（Stage）
将所给问题的过程，按时间或空间特征分解成若 干个相互联系的阶段，以便按次序去求每阶段的解。 用以描述阶段的变量叫作阶段变量，一般以k表示阶 段变量。
输入状态和输出状态，阶段k的初始 状态记作sk，终止状态记为sk+1。但
为了清楚起见，通常定义阶段的状态 即指其初始状态。
动态规划中的状态具有如下性质：
当某阶段状态给定以后，在这阶段以后的过程的 发展不受这段以前各段状态的影响。即：过程的过去 历史只能通过当前状态去影响它未来的发展，这称为 无后效性。如果所选定的变量不具备无后效性，就不 能作为状态变量来构造动态规划模型。