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

第二章 物流系统分析方法 主要内容 2.1 线性规划方法 2.2 动态规划方法 * 2.3 系统模拟方法 * 2.4 系统评价方法 2.5 系统决策方法 2.2 动态规划方法 动态规划是运筹学的另一个分支，它是解决多阶段决策最优化 的一种数学方法。该法在工程技术、企业管理、工农业生产及军事 部门都有广泛的应用。如企业管理方面的最优路径、资源分配、生 产调度、库存控制、设备更新等问题。 与线性规划相比，动态规划不存在一个标准的数学表达式以及 明确定义的一组求解规则。对于每一种具体情况，必须导出具体的 算式。 2.2 动态规划方法 主要内容 2.2.1 多阶段决策过程及实例 2.2.2 动态规划的求解方法 2.2.3 动态规划的基本原理和基本概念 2.2.4 动态规划在多阶段决策中的应用 2.2.1 多阶段决策过程及实例 在生产、工程、科学实验中，有这样一类活动，由于它的特殊性，可 将过程分为若干个互相联系的阶段，每一个阶段都要做出决策，从而使整 个过程达到最佳效果。因此，各阶段的决策既依赖于当前所处的各个状 态，又影响以后的发展。当各阶段的决策确定后，就组成了一个决策序 列，从而也就决定了整个过程的一条活动路线。这样一个前后关联且具有 链状结构的多阶段过程如图2-1所示，就称为多阶段决策过程。 图2-1 多阶段决策过程示意图 在多阶段决策问题中，各阶段做出的决策，一般与时间有关，决策依 赖于当前的状态，又随即引起状态的转移，一个决策的序列就是在变化的 状态中产生出来的，故有“动态”的含义。但是，一些与时间无关的静态规 划问题，只要人为的引入“时段”因素，也可视为多阶段决策过程来处理。 [例2-5] 最短路线问题。如图2-2所示为一交通线路网络，现在要铺设从A 点至E点的线路，中间要经过3个地区B、C、D。地区B和C分别可在区 内3个地点设站，地区D可在两个地点设站。图中各点之间的连线表示两 点间可铺路，连线上的数字表示两点间的距离。要求选择一条A点至E点 的最短路线。 最短路线问题具有如下重要性质：若已经给定从始点S到终点T的最短路 线，如图2-3中的实线所示，则从其上任一中间点P到终点T的部分路线也必 然是P点到终点T的所有可选择的路线中的最短路线。 根据最短路线问题的这一重要性质，我们可以从最后一个阶段开始，由 终点向始点方向逐阶段递推，寻找各点到终点的最短路线，当递推到始点 时，就找到了始点到终点的最短路线。这种由后向前逆序递推的方法，正是 动态规划通常采用的寻优途径，常用于解决运输规划中路线选择、物流渠道 的设计及管道铺设等问题。 2.2.2 动态规划的求解方法 主要内容 一、逆序递推法 二、顺序递推法 2.2.2 动态规划的求解方法 一、逆序递推法 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。所谓逆序递推就是逆着过程的行进方向，由终点到始点，一个阶段随着一个阶段地递推。 3、计算过程 (1) 第一步：阶段k=4。 有两个初始状态D1和D2，起点A 到E的全过程最短路线在第4阶段经 过哪个点，还不能确定，只能考虑 到所有选择，分别得到D1和D2到终 点E的最短距离f4(D1)=3、f4(D2)=4. (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，最短距离是9。 (3)