1、第六章第六章 动态规划动态规划第一节：现实中的动态规划问题第二节：动态规划基本概念第三节：动态规划的基本方法第四节：动态规划的应用 第六章 动态规划多式联运 是一种以实现货物整体运输最优化为目标的联合运输组织形式，它以集装箱为媒介，把水路、公路、以及铁路等多种运输方式有机地结合起来，构筑连续的、综合性的一体化货物运输网络。在集装箱多式联运系统中，各种运输方式的组织优化直接关系到货物运输的费用、时间和运输质量。第一节：现实中的动态规划问题 一、两地之间集装箱货物运输有三种可选的运输方式（公路、铁路、水路运输） 二、集装箱的中转过程有很好的衔接 三、集装箱运量不可以分割，在某两个特定的地点之间，只
2、能选择一种运输方式 四、集装箱运量对运输价格及运输时间没有明显的影响 五、集装箱运输能力几乎不受限制 六、运输时间须控制在合理范围之内（如集装箱干线船的班期）。通常情况下，多式联运组织优化问题具有如下几个方面的特点：ZH物流公司是一家大型的集装箱多式联运经营企业，在成都设有内陆集装箱货运站（ CFS），经营成都 上海间集装箱货物运输服务，其多式联运通道的主要节点城市为南京与郑州。现有一个货主需要将 2个 20英尺的集装箱从成都运往上海，运输路线为成都 -郑州 -南京 -上海，要求在货物起运后 25-30小时之内到达目的地。第一节：现实中的动态规划问题成都 -郑州 郑州 -南京 南京 -上海公路
3、运输 1474 704 349铁路运输 1353 695 303水路运输 / / 392运输方式 铁路运输 公路运输 水路运输运载工具速度 (km/h)70 100 36运输方式 铁路运输 公路运输 水路运输中转时间 (h) 7 3 18如何制定运输方式组合优化方案使在满足客户需求的条件下降低集装箱运输总成本？5Sk+1S2多多 阶段决策问题阶段决策问题阶段、决策、策略动态规划动态规划 的的 基本基本 特性（特性（ 多 阶段决策问题的 基本基本 特性特性）第二节 动态规划基本概念Sk Sk+1 Sn TSnQ = S1反证法反证法 容易得证。若 S1 , , Sk , Sk+1 , , Sn
4、, T 全程最优则 Sk+1 , , Sn , T 子程最优动态规划 方法方法 的 基本思路基本思路最短路问题1 2 3 4340476117811阶段阶段A124374632441514633334A3B1Q A2 B2B3TC1C2 标号法标号法三、决策是指人们对某一阶段活动中各种不同的 行为 或 方案 或 途径 等的一种 选择选择 。用 xk表示第 k段的决策，称为第 k段 决策变量 。 由于决策随状态而变 ,所以决策变量 xk是状态变量 sk的函数 ,记为 xk= xk(sk)动态规划动态规划 的的 基本概念基本概念一 、 阶段把所研究的问题恰当的划分成若干个相互联系的阶段。用k =
5、1， 2， ， n 表示阶段序号，称为 阶段变量 。二、状态状态表示某段的初始条件。用 sk表示第 k段的状态，称为第 k段状态变量 。 sk Skk阶段的允许决策集合8四、状态转移方程sk+1与 sk,xk之间必须能够建立一种明确的数量对应关系，记为Tk(sk,xk), 即有sk+1 = Tk(sk,xk) 这种明确的数量关系称为 状态转移方程 。五、策略由各阶段决策 xk构成的决策序列 ,称为 全过程策略全过程策略 ,简称 策略 ,记为p1(s1),有p1(s1) = x1(s1),x2(s2), ,xn(sn)pk(sk) = xk(sk),xk+1(sk+1), ,xn(sn) Pk称
6、为 第第 k子过程策略子过程策略 ，简称 子策略 。 P1而9六、指标函数(1) 阶段指标函数用 vk(sk,xk)表示第 k段处于 sk状态且所作决策为 xk时的指标，则它就是 第 k段指标函数 ，简记为 vk。 P1(2) 过程指标函数用 fk(sk,xk)表示 第 k子过程的指标函数 。它是各 vk的累积效应。常用函数常用函数 ：fk(sk,xk) = vi(si,xi)ni= kfk(sk,xk) = vi(si,xi)ni= k积函数积函数和函数和函数七 、 最优解(1) 最优指标函数fk*(sk) = opt fk(sk, pk(sk), k=1,2, ,n pk Pk(2) 最优策略能使上式成立的子策略 pk*称为 最优子策略最优子策略 ，记为pk* (sk) = xk*(sk), ,xn*(sn)特别当 k=1时 ,称为 最优策略最优策略 ，记为p1* (s1) = x1*(s1), ,xk*(sk), ,xn*(sn) (3) 最优决策构成最优策略的决策 称为 最优决策最优决策 ，记为 xk*。 (4) 最优值 ： 最优策略对应的最优指标 f *1
