SHUFE 第一节多阶段决策问题 、动态规划的标号法 1L.B,B 4,C 3,T 8,B1 7,C2 0 B T 4,T 8,B 6,C B 最短路径:Q→A3→B1→C1→T 上海财经大学国际工商管理学院
上海财经大学国际工商管理学院 SHUFE 6 第一节 多阶段决策问题 • 最短路径：Q→ A3→ B1→ C1→T 二、动态规划的标号法 Q T A1 A2 A3 B1 B2 B3 C1 C2 2 4 3 7 4 6 4 2 4 4 2 5 1 4 6 3 3 3 3 4 阶段1 阶段2 阶段3 阶段4 0 3,T 4,T 4,C1 7,C2 6,C1 11,B1 ,B2 8,B1 8,B1 11,A3
SHUFE 第一节多阶段决策问题 三、多阶段决策的基本特征 最短路的基本特征 从始点Q到终点T的最短路径:Q→A3→、B1→C1→T,则 从中点43到终点T的最短路径必为:A3→B1→C1→T, 从中点B到终点T的最短路径必为: 推广:从始点Q到终点T的最短路径: Q→S1→S2 k+ →SnT,则 从中点Sk到终点T的最短路径必为:Sk→Sk+r→…→ 上海财经大学国际工商管理学院
上海财经大学国际工商管理学院 SHUFE 7 第一节 多阶段决策问题 • 最短路的基本特征 ▪ 从始点Q到终点T 的最短路径：Q→ A3→ B1→ C1→T，则 从中点A3 到终点T 的最短路径必为：A3→ B1→ C1→T， 从中点B1 到终点T 的最短路径必为：B1→ C1→T，…。 ▪ 推广：从始点Q到终点T 的最短路径： Q → S1→ S2→ … → Sk→ Sk+1→ … → Sn→T，则 从中点Sk 到终点T 的最短路径必为： Sk→ Sk+1→ … → Sn→T。 三、 多阶段决策的基本特征
SHUFE 第二节动态规划原理 、动态规划的基本概念 阶段sge) 处理多阶段决策,需将全过程划为若干阶段,每个阶段进 行一次抉择。 ■各阶段按一定顺序联接在一起组成统一的整体。 用k表示阶段变量。 阶段编号 顺序编号 逆序编号 上海财经大学国际工商管理学院
上海财经大学国际工商管理学院 SHUFE 8 第二节 动态规划原理 • 阶段(stage) ▪ 处理多阶段决策，需将全过程划为若干阶段，每个阶段进 行一次抉择。 ▪ 各阶段按一定顺序联接在一起组成统一的整体。 ▪ 用k表示阶段变量。 ▪ 阶段编号 • 顺序编号 • 逆序编号 一、动态规划的基本概念
SHUFE 第二节动态规划原理 状态( state) 状态表示过程发展中某阶段的起始状况。 过程的发展可以通过各阶段状态的演变来描述。 状态可用一个变量来描述,称为状态变量,用S表示。 选取的状态变量必须满足无后效性。 某阶段的状态给定后,则过程未来发展不受该阶段以前 各阶段状态的影响。 第k阶段可能有若千状态,用S表示阶段k的状态集合, SA(表示第阶段的第i个状态 上海财经大学国际工商管理学院
上海财经大学国际工商管理学院 SHUFE 9 第二节 动态规划原理 • 状态(state) ▪ 状态表示过程发展中某阶段的起始状况。 ▪ 过程的发展可以通过各阶段状态的演变来描述。 ▪ 状态可用一个变量来描述，称为状态变量，用Sk表示。 ▪ 选取的状态变量必须满足无后效性。 • 某阶段的状态给定后，则过程未来发展不受该阶段以前 各阶段状态的影响。 ▪ 第 k 阶段可能有若干状态，用Sk表示阶段k的状态集合， ▪ sk (i)表示第k阶段的第 i 个状态
SHUFE 第二节动态规划原理 决策( decision) 从上一阶段某状态演变到下一阶段某状态要作一次选择, 称为决策。 用变量x(S表示第k阶段状态为s时的决策,称为决策变 量,简记xk ■决策变量的取值被限制在某一范围内,此范围称为允许决 策集合X(③Sb 上海财经大学国际工商管理学院
上海财经大学国际工商管理学院 SHUFE 10 第二节 动态规划原理 • 决策(decision) ▪ 从上一阶段某状态演变到下一阶段某状态要作一次选择， 称为决策。 ▪ 用变量xk (sk )表示第k阶段状态为sk时的决策，称为决策变 量，简记xk ▪ 决策变量的取值被限制在某一范围内，此范围称为允许决 策集合Xk (sk )