物流系统工程课件第四讲 动态规划和仿真方法.ppt

第二章 物流系统分析方法主要内容 n2.1 线性规划方法 n2.2 动态规划方法 *n2.3 系统模拟方法 *n2.4 系统评价方法 n2.5 系统决策方法1动态规划是运筹学的另一个分支，它是解决多阶段决策最优化的一种数学方法该法在工程技术、企业管理、工农业生产及军事部门都有广泛的应用如企业管理方面的最优路径、资源分配、生产调度、库存控制、设备更新等问题与线性规划相比，动态规划不存在一个标准的数学表达式以及明确定义的一组求解规则对于每一种具体情况，必须导出具体的算式2.2 动态规划方法 22.2 动态规划方法主要内容 u2.2.1 多阶段决策过程及实例 u2.2.2 动态规划的求解方法 u2.2.3 动态规划的基本原理和基本概念u2.2.4 动态规划在多阶段决策中的应用3在生产、工程、科学实验中，有这样一类活动，由于它的特殊性，可将过程分为若干个互相联系的阶段，每一个阶段都要做出决策，从而使整个过程达到最佳效果因此，各阶段的决策既依赖于当前所处的各个状态，又影响以后的发展当各阶段的决策确定后，就组成了一个决策序列，从而也就决定了整个过程的一条活动路线这样一个前后关联且具有链状结构的多阶段过程如图2-1所示，就称为多阶段决策过程。

2.2.1 多阶段决策过程及实例4图2-1 多阶段决策过程示意图在多阶段决策问题中，各阶段做出的决策，一般与时间有关，决策依赖于当前的状态，又随即引起状态的转移，一个决策的序列就是在变化的状态中产生出来的，故有“动态”的含义但是，一些与时间无关的静态规划问题，只要人为的引入“时段”因素，也可视为多阶段决策过程来处理5[例2-5] 最短路线问题如图2-2所示为一交通线路网络，现在要铺设从A点至E点的线路，中间要经过3个地区B、C、D地区B和C分别可在区内3个地点设站，地区D可在两个地点设站图中各点之间的连线表示两点间可铺路，连线上的数字表示两点间的距离要求选择一条A点至E点的最短路线返回顺返回逆6最短路线问题具有如下重要性质：若已经给定从始点S到终点T的最短路线，如图2-3中的实线所示，则从其上任一中间点P到终点T的部分路线也必然是P点到终点T的所有可选择的路线中的最短路线根据最短路线问题的这一重要性质，我们可以从最后一个阶段开始， 由终点向始点方向逐阶段递推，寻找各点到终点的最短路线，当递推到始点时，就找到了始点到终点的最短路线这种由后向前逆序递推的方法，正 是动态规划通常采用的寻优途径，常用于解决运输规划中路线选择、物流渠 道的设计及管道铺设等问题。

72.2.2 动态规划的求解方法主要内容 l一、逆序递推法 l二、顺序递推法 8l 一、逆序递推法Ø1、问题描述 下面介绍用逆序递推的方法求解例2-2的最短路线问题首先把从A 到E的全过程分成4个阶段，用k表示阶段变量，第1阶段，有一个初始状 态A，3条可供选择的支路AB1、AB2、AB3；第2阶段，有3个初始状态 Bl、B2、B3，它们分别有2、3、2条可供选择的支路……用dk（sk，sk+1）表示在第 k 阶段由初始状态sk到下阶段的初始状 态sk+1的支路的距离例如，d3(C2，D1)表示在第3阶段，由 C2到 D1的 距离，即 d3(C2，D1)=2用 fk(sk) 表示从第k阶段的 sk 到终点E的最短 距离例如，f3(C1)表示从第3阶段的C1到终点E的最短距离，f3(C1)＝7 Ø2、定义图2-2中，过程的始点是A，终点是E所谓逆序递推就是逆着过 程的行进方向，由终点到始点，一个阶段随着一个阶段地递推2.2.2 动态规划的求解方法返回 9Ø3、计算过程p (1) 第一步：阶段k=4有两个初始状态D1和D2，起点A 到E的全过程最短路线在第4阶段经过哪个点，还不能确定，只能考虑到所有选择，分别得到D1和D2到终点E的最短距离f4(D1)=3、f4(D2)=4. 10p(2) 第二步：阶段k=3。

假设全过程最短路线在第3阶段经过C1点，那么C1至 第4阶段只有一条路(C1→D1)，所以 类似，假设全过程最短路线在第3阶段经过C2点，那么C2至 第4阶段有两条路(C2→D1，C2→D2 )，所以 由C2到E的最短路线是C2→D1 →E，最短距离是5假设全过程最短路线在第3阶段经过C3点，那么C3至第4阶段有两条路(C3→D1 ，C3→D2)，所以C3到E的最短路线有两条：C3→D1 →E， C3→D2→E，最短距离是9311p(3) 第三步：阶段k=2类似，可计算由B1到E的最短路线是B1→C2 →D1 →E，最短距离是12由B2到E的最短路线是B2→C2 →D1 →E，最短距离是10由B3到E的最短路线是B3→C2 →D1 →E，最短距离是10312`p(4) 第四步：阶段k=1计算由A到E的最短路线是A → B3→C2 →D1 →E，最短距离是14313A到E的最短路线为A→B3→C2→D1→E，如图2-4中双线所示，最短距离是14 在使用逆序递推法求解过程中，每个阶段中都求出本阶段各个初始状态到终点E的最短路径和最短距离，当逆序递推至过程的始点A时，便得到全过程的最短路径和最短距离，同时得到各中间点到终点E的最短路径和最短距离，如图2-4中所示（节点上方的数字为该点到终点E的最短距离）14l二、 顺序递推法Ø1、问题描述同样，首先把从A到E的全过程分成4个阶段，用k表示阶段变量，第 1阶段，有三个结束状态B1、B2、B3，各有1条可供选择的支路，分别是 AB1、AB2、AB3；第2阶段，有3个结束状态Cl、C2、C3，可供选择的支 路分别为(B1C1、B2C1)、(B1C2、B2C2、B3C2)、(B2C3、B3C3)，……。

我们用dk（sk-1，sk）表示在第k阶段由上阶段的结束状态sk-1到该阶 段的结束状态sk的支路的距离例如，d3(C2，D1)表示在第3阶段，由 C2 到 D1的距离，即 d3(C2，D1)=2用 fk(sk)表示从起点A到第k阶段的结束 状态sk的最短距离例如，f2(C1)表示从起点A到第2阶段的结束状态C1的 最短距离f2(C1)＝10 Ø2、定义图2-2中，过程的始点是A，终点是E所谓顺序递推就是顺着过程的行进方 向，由起点到终点，一个阶段随着一个阶段地递推返回 15Ø 3、计算过程在使用顺序递推法求解过程中，每个阶段中都求出起点A到本阶段各个结束状态的最短路径和最短距离，当顺序递推至过程的终点E时，便得到全过程的最短路径和最短距离，同时得到起点A到各中间点的最短路径和最短距离 p(1) 阶段k=1. 有三个结束状态B1、B2、B3，起点A 到E的全过程最短路线在第1阶段经过哪个点，还不能确定，只能考虑到所有选择，分别得到起点A到B1、B2、B3的最短距离f1(B1)=3、f1(B2)=6.、f1(B3)=4. 16p(2)阶段k=2假设全过程最短路线在第2阶段经过C1点，那么上一阶段至点C1有两条路(B1→C1 ，B2→C1)，所以 因此，A到C1 的最短路线有两条，分别是A→B1→C1，A→B2→C1，最短距离都是10.类似，假设在第2阶段经过C2点，那么上一阶段至点C2有三条路(B1→C2 ，B2→C2，B3→C2).因此，A到C2 的最短路是A→B3→C2，最短距离是9。

假设全过程最短路线在第2阶段经过C3点，那么上一阶段至点C3有两条路(B2→C3 ，B3→C3)，所以因此，A到C3 的最短路是A→B3→C3，最短距离是7317p(3) 阶段k=3课堂练习18p(3) 阶段k=3类似以上作法，可计算f3(D1)、f3(D2)：上一阶段至点D1有三条路(C1→D1 ，C2→D1 ，C3→D1)，所以因此，A到D1 的最短路是A→B3→C2→D1，最短距离是11.上一阶段至点D2有两条路(C2→D2 ，C3→D2)，所以因此，A到D2 的最短路有两条，分别是A→B3→C2→D2，A→B3→C3→D2，最短距离都是12319p (4) 阶段k=4因此，A到E的最短路是A→B3→C2→D1→E，最短距离是14.使用顺序递推法求解例2-2，得到A到E的全过程最短路线为A→B3→C2→D1→E，如图2-4中双线所示，最短距离是14返回320l一、 动态规划的基本原理动态规划的最优性原理是“一个最优策略具有这样的性质：无论初始状态和初始策略如何，对前面的策略所形成的状态而言，其后策略必构成最优”简言之，一个最优策略的子策略总是最优的 “最优性原理”是动态规划的核心和理论基础。

各种动态规划模型的建 立及求解，都是根据这一原理进行的根据这一原理，在求解动态规划问题时，可从终点逐段向始点逆序求解，如图2-5a所示,也可以从始点向终点顺序求解，如图2-5b所示 2.2.3 动态规划的基本原理和基本概念2122l 二、 动态规划的基本概念Ø1、阶段（Stage）应用动态规划方法时，问题必须能划分成若干个阶段，而且在每一个阶 段都可做出不同的决策阶段的划分一般是根据时间和空间的自然特征来划 分，且要便于把问题的过程转化为多阶段决策过程描述阶段的变量称为阶 段变量，通常用 k 表示约定按照决策方向顺序编号，如图2-5所示Ø2、状态（State）表示每个阶段所处的客观条件，通常一个阶段有若干个状态描述过程 状态的变量称为状态变量，我们用变量sk表示，它表示第k阶段的状态变量 例如，第二阶段有3种状态：B1、B2、B3，则可表示为s2={B1，B2，B3}动态规划问题中的状态变量必须具有如下两个性质：ü(1）无后效性在决策过程中，某一阶段的状态一经确定，则以后过程 的发展仅仅取决于此时的状态，而与此时以前的状态和决策无关ü(2）可知性在每一个阶段，状态变量的值必须是已知的，或者是可求 得的。

23l一、运输中的最短路问题 l二、 背包问题有一个人带一个背包上山，可携带物品重量限度为W kg，设有n种物品可供选择已知第i种物品重量为Wi kg，上山过程中的作用（价值）是携带数量xi的函数ci（xi）问应如何选择携带物品，使总的作用最大这就是著名的背包问题，类似的问题有工厂里的下料问题，运输中的货物装载问题 2.2.4 动态规划在多阶段决策中的应用242.3 系统模拟方法主要内容 u2.3.1 系统模拟的基本概念u2.3.2 计算机仿真u2.3.3 物流系统仿真252.3.1 系统模拟的基本概念主要内容 l一、 定义和目的l二、 特点l三、系统仿真在物流系统中的应用l四、模拟的分类262.3.1 系统模拟的基本概念l一、定义和目的 Ø1、定义 模拟就是对系统的模型进行实验的一种方法，或者说，是对现实系统或假设系统的模型进行的一种试验272.3.1 系统模拟的基本概念Ø2、目的模拟的目的大体上有以下几个方面：• (1)在建立一个真实系统之前，必须对系统的行为和性能作出预测和 评价，尤其是对于大规模的复杂系统因此，系统模拟往往作为可行 性研究中的一种手段§ (2)在建立真实系统前，或者系统已经建立，模拟的目的通常是用于 各备选方案的比较，从而使设计更加合理，对现有系统进一步改进， 使组织管理工作更加完善。

ü例如，矿山设计阶段，对生产运营过程的计算机模拟，可为设备的选择 及运输线路方案的确定提供依据；ü城市地铁设计或改造阶段，对线路最大通过能力和运输量的计算机模拟 ，为设计方案的比较提供了依据§ (3) 其次模拟还可以用于培训有关人员，这样省时省钱可避免一些不 必要的损失例如，对司机，飞行驾驶员，调度人员的模拟训练等28l 二、特点系统仿真具有一系列的优点，因而得到广泛的应用，主要特点有：§ 1 、利用仿真模型可将复杂事物抽象化，了解系统的可行性和可靠 性，检验理论的正确性，寻求解决问题的途径§ 2、 利用仿真可避免在实际系统上试验期过长的弊病，节省人力、物 力§ 3、 某些复杂系统既不能用实验方法，又不能用解析方法时。