管理远筹学 谢家平博士副教授 研究领域:系统建模与优化、生产与运作管理、物流与供应链管理 讲授课程:管理运筹学、管理系统工程、生产运作管理、 供应链管理、国际物流管理、企业资源计划 单位:上海财经大学国际工商管理学院供应链管理研究中心 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条不同路线 ▪ 现在的问题是如何选择一条费用最小的路线？