管理远筹学 谢家平博士副教授 研究领域:系统建模与优化、生产与运作管理、物流与供应链管理 讲授课程:管理运筹学、管理系统工程、生产运作管理、 供应链管理、国际物流管理、企业资源计划 单位:上海财经大学国际工商管理学院供应链管理研究中心 E-mail:jiapingxie@sina.com.cn 电话:55036936(H)65903541(O)
管理运筹学 谢家平 博士 副教授 研究领域：系统建模与优化、生产与运作管理、物流与供应链管理 讲授课程：管理运筹学、管理系统工程、生产运作管理、 供应链管理、国际物流管理、企业资源计划 单 位：上海财经大学国际工商管理学院供应链管理研究中心 E-mail：jiaping_xie@sina.com.cn 电 话：55036936(H) 65903541(O)
SHUFE 第八章动态规划 动态规划 Dynamic Programming 研究多阶段决策的最优化问题的方法。 多阶段决策问题含有一个描述过程时序或空间演变的阶段 变量,将复杂问题划分成若干阶段,根据“最优性原理”, 逐段解决而最终实现全局最优。 经济、管理、工业生产、工程技术等领域,许多问题可归 结为多阶段决策问题。 些用线性规划、非线性规划处理有困难的问题,往往可 以用动态规划方便地求解。 动态规划是美国运筹学家贝尔曼( R Bellman等人1959年提 出的。 上海财经大学国际工商管理学院
上海财经大学国际工商管理学院 SHUFE 2 第八章 动态规划 • 动态规划Dynamic Programming ▪ 研究多阶段决策的最优化问题的方法。 ▪ 多阶段决策问题含有一个描述过程时序或空间演变的阶段 变量，将复杂问题划分成若干阶段，根据“最优性原理” ， 逐段解决而最终实现全局最优。 ▪ 经济、管理、工业生产、工程技术等领域，许多问题可归 结为多阶段决策问题。 ▪ 一些用线性规划、非线性规划处理有困难的问题，往往可 以用动态规划方便地求解。 ▪ 动态规划是美国运筹学家贝尔曼(R.Bellman)等人1959年提 出的
SHUFE 第一节多阶段决策问题 问题的提出 多阶段决策: ■经济管理决策中,有些管理决策问题可以按时序或空间演 变划分成多个阶段,呈现出明显的阶段性; 于是可把这类决策问题分解成几个相互联系的阶段,每个 阶段即为一个子问题; 原有问题的求解就化为逐个求解几个简单的阶段子问题; ■每个阶段的决策一旦确定,整个决策过程也随之确定,此 类问题称为多阶段决策问题。 例如: 企业生产物流:可分为物料供应、生产制造、分销零售等 阶段。 最短路问题ε可以按空间顺序划分阶段。 上海财经大学国际工商管理学院
上海财经大学国际工商管理学院 SHUFE 3 第一节 多阶段决策问题 • 多阶段决策： ▪ 经济管理决策中，有些管理决策问题可以按时序或空间演 变划分成多个阶段，呈现出明显的阶段性； ▪ 于是可把这类决策问题分解成几个相互联系的阶段，每个 阶段即为一个子问题； ▪ 原有问题的求解就化为逐个求解几个简单的阶段子问题； ▪ 每个阶段的决策一旦确定，整个决策过程也随之确定，此 类问题称为多阶段决策问题。 • 例如： ▪ 企业生产物流：可分为物料供应、生产制造、分销零售等 阶段。 ▪ 最短路问题：可以按空间顺序划分阶段。 一、 问题的提出
SHUFE 第一节多阶段决策问题 最短路问题 BB 生产商 城 港 进口港 市 某公司一 从生产厂Q到某公司T选择那条路线使总运费最低(路程最短)? 上海财经大学国际工商管理学院
上海财经大学国际工商管理学院 SHUFE 4 第一节 多阶段决策问题 • 从生产厂Q到某公司T选择那条路线,使总运费最低(路程最短)？ • 最短路问题 Q T A1 A2 A3 B1 B2 B3 C1 C1 2 4 3 7 4 6 4 2 4 4 2 5 1 4 6 3 3 3 3 4 生 产 商 某 公 司 出 口 港 进 口 港 城 市 阶段1 阶段2 阶段3 阶段4
SHUFE 第一节多阶段决策问题 这是一个多阶段决策问题,它可分为四个阶段: 第一阶段:从Q(制造厂)到A(出口港); 第二阶段:从4(出口港到B(进口港); 第三阶段:从B(进口港)到C(城市); 第四阶段:从C(城市)到T某公司) 每个阶段选取的路线不同,对应从Q到7就有一系列不同 的运输路线: 从始点Q到终点T共有3×3×2×1=18条不同路线 现在的问题是如何选择一条费用最小的路线? 上海财经大学国际工商管理学院
上海财经大学国际工商管理学院 SHUFE 5 第一节 多阶段决策问题 • 这是一个多阶段决策问题，它可分为四个阶段： ▪ 第一阶段：从Q(制造厂)到A(出口港)； ▪ 第二阶段：从A(出口港)到B(进口港)； ▪ 第三阶段：从B(进口港)到C(城市)； ▪ 第四阶段：从C(城市)到T(某公司)。 • 每个阶段选取的路线不同，对应从Q到T就有一系列不同 的运输路线: ▪ 从始点Q到终点T共有3×3×2×1=18条不同路线 ▪ 现在的问题是如何选择一条费用最小的路线？
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 )