第4章动态规划 (Dynamic Programming) 网 络 优 化 Network Optimization http://www.csiam.edu.cn/netopt 清华大学课号：70420133 第4章动态规划 (Dynamic Programming) 清华大学数学科学系 谢金星 办公室：理科楼2266# （电话：62787812） Email:jxie@math.tsinghua.edu.cn http://faculty.math.tsinghua.edu.cn/~jxie/courses/netopt

动态规划问题的例子 S T 例（续例1.2）最短路问题 (Shortest Path Problem) 特点：多阶段决策 - 子决策仍然最优 - 动态规划(DP)技术 动态规划 – R.E. Bellman (1950’s) 许多网络优化问题要用到动态规划技术

4.1.1 多阶段决策模型 所谓决策(Decision Making)，就是人们为了达到一定的目的，从若干个可能的策略(Policy)（如行动、方案）中选取最好的策略的过程. 一般来说，一个决策模型包含三个最基本的因素： （1）自然状态（或简称状态, State）：这是指决策活动中决策者无法控制的一些因素，即决策时客观对象所具备的基本条件. 状态的集合称为状态集合或状态空间. （2）策略：这是指决策活动中决策者可以采取的行动方案. 策略的集合称为策略集合或策略空间. （3）益损值：这是指决策活动中决策者可以采取不同的策略，在不同的自然状态下所获得的收益或损失值. 它是策略和状态的函数，也是决策活动的目标和基础. 战略决策(高层决策)、战术决策(中层决策)、操作决策(基本决策) 单目标决策、多目标决策 单阶段决策（一次决策）、多阶段决策 确定型决策、非确定型决策或风险型决策（随机决策、模糊决策）

多阶段决策过程 多阶段决策（Multi-Stage Decision Making），是将决策问题的全过程恰当地划分为若干个相互联系的子过程（每个子过程为一个阶段），以便按照一定的次序去求解. 阶段一般是根据时间和空间的自然特征来划分，以便于问题的求解为目的. 描述阶段的变量称为阶段变量，一般用k表示. 从第k个阶段开始点到全过程终点的过程称为后部子过程，或k子过程. 在多阶段决策问题中，状态表示每个阶段开始时所处的自然状况或客观条件. 描述过程状态的变量称为状态变量，一般用xk表示第k个阶段的状态变量. 当过程处于某个阶段的某个状态时，从该状态演变为下一个阶段某状态的选择，称为决策（抉择，Decision）. 描述决策的变量称为决策变量，一般用uk表示第k个阶段的决策变量，而用Uk(xk)表示第k个阶段xk状态下的所有允许决策的集合.

无后效性的多阶段决策过程 动态规划中，多阶段决策问题具有无后效性（马尔科夫性质），即当某阶段的状态一旦确定,则此后过程的演变不再受此前各状态和决策的影响, 或者说“未来与过去无关”. 即由状态xk出发的后部子过程可以看成一个以xk为初始状态的独立过程. 状态转移方程 由所有各阶段的决策组成的决策序列称为全过程策略，或简称策略，记为p1,n(x1). 可供选择的所有全过程策略的集合构成允许策略集合，记为P1,n(x1) .其中能使总体性能达到最优的策略称为最优策略，一般记为 相应于后部子过程（k子过程）的决策序列称为子策略，记为pk,n(xk) ，所有允许子策略的集合记为Pk,n(xk).

无后效性的多阶段决策过程 - 准则函数及可分性 准则函数/指标函数（Criterion Function）是衡量策略好坏的尺度(益损值). 定义在全过程上的准则函数相当于目标函数，一般记为 V1,n(x1; p1,n ) ，或简记为V1,n 定义在k子过程上的准则函数，记为Vk,n(xk; pk,n ) ,简记为Vk,n 准则函数在第k阶段一个阶段内的取值称为第k阶段的准则函数，记为vk(xk; uk) 最优性原理中，准则函数具有（阶段）可分性，即 一般记为

4.1.2 最优性定理 定理4.1 设有一个准则函数可分的无后效性的多阶段决策过程,阶段变量k=1,2,…,n,允许策略 是最优策略的充要条件是: 对任意1<k<n, 当初始状态为x1时, 有 (4.3) 式中 , ,即 是由给定的初始状态x1和子策略p1，k-1所确定的第k阶段的状态. 证明: 必要性. 设允许策略 是最优策略，则

最优性定理 充分性. 设允许策略 满足定理的条件（4.3）, 为任一允许策略，则 因为 所以, 是最优策略 证毕

4.1.3 最优化原理 “全过程的最优策略具有这样的性质：不管该最优策略上某状态以前的状态和决策如何，对该状态而言，余下的诸决策必定构成最优子策略. ”即：最优策略的任一后部子策略都是最优的. 这只是最优性定理的一个推论，即最优策略的必要条件.

4．2 动态规划基本方程 建立动态规划模型的基本过程是： （1） 正确划分阶段，选择阶段变量k. （2）  对每个阶段，正确选择状态变量xk. 选择状态变量时应当注意两点：一是要能够正确描述受控过程的演变特性，二是要满足无后效性. （3）   对每个阶段，正确选择决策变量uk . （4）   列出相邻阶段的状态转移方程： xk+1= Tk(xk, uk). （5） 列出按阶段可分的准则函数V1,n . 假设问题的目标是极小化

k=1 k=n k k=2 逆序递推 fk(xk)表示第k阶段初始状态为xk时，k后部子过程的最优准则函数

顺序递推 fk(xk+1)表示第k阶段（结束）状态为xk+1时，起始阶段到k阶段（可以称为k前部子过程）的最优准则函数 k=n k k=2 顺序递推 fk(xk+1)表示第k阶段（结束）状态为xk+1时，起始阶段到k阶段（可以称为k前部子过程）的最优准则函数 优点：1、动态规划方法可以处理广泛的实际优化问题； 2、可以得到各阶段的一系列最优解. 缺点：隐式枚举方法 - 指数算法, 当问题规模较大时, 也会遇到维数障碍(维数灾)的问题.

4．3 应用动态规划方法的几个例子 例4.1 （资源分配问题） 某公司现有M台设备准备分配给该公司所属的N家工厂. 当分配台uk设备给工厂k时，工厂k利用这些设备为公司创造的利润（假设非负）为gk(uk)(假设为非降函数). 应当如何分配设备资源，使得公司总利润最大？   工厂k 设备数   1 2 3 4 6 7 5 8 上述问题可能是非线性整数规划, 甚至gk(uk)没有显式表达式

状态变量xk - 第k阶段初分配者手中拥有的设备台数. 由题意可知 x0 = M， xN+1 = 0 资源分配问题 共有N个工厂，可以把问题分解为N个阶段： 当阶段k=N时，把手中设备分配给工厂N； 当阶段k=N-1时，把手中设备分配给工厂N-1； 依次类推； 在任意阶段k时，把手中设备分配给工厂k； 当阶段k=1时，把手中设备分配给工厂1. 状态变量xk - 第k阶段初分配者手中拥有的设备台数. 由题意可知 x0 = M， xN+1 = 0 决策变量uk - 第k阶段分配给工厂k的设备台数（ ） 状态转移方程 阶段k的准则函数为

资源分配问题 用fk(xk) 表示将手中资源xk分配给工厂k,k+1,…, N 时的最大利润，原问题即为计算 f1(M) 具体计算（例） M=4，N=3，边界条件 f4(x4) = f4(0) =0 k=3时： （增函数）

资源分配问题 k=2时：

资源分配问题 k=1时： 最优解 ,最大利润为 . 推广1： 二维（或多维）资源分配问题 推广2：非线性整数规划问题 ， 如： M=4, N=3

单产品、无能力限制的批量问题 例4.2 （Single-level Uncapacitated Lotsizing） 某工厂生产某种产品用以满足市场需求,且已知在时段t中的市场需求为dt . 在某时段t, 如果开工生产, 则生产开工所需的生产准备费为st , 单件产品的生产费为ct . 在某时段t期末, 如果有产品库存, 单件产品的库存费为ht . 假设初始库存为0, 不考虑能力限制, 工厂应如何安排生产, 可以保证按时满足生产, 且使总费用最小? （Wagner – Whitin，1958） 假设在时段t, 产品的生产量为xt , 期末产品的库存为It (I0 =0); 用二进制变量yt表示在时段t工厂是否进行生产准备.

单产品、无能力限制的批量问题 假设费用均非负，则在最优解中 ，即 当ct为常数，目标函数变为 可以证明：一定存在满足条件 的最优解. 假设费用均非负，则在最优解中 ，即 当ct为常数，目标函数变为 可以证明：一定存在满足条件 的最优解. 可以只考虑 用ft表示当t时段初始库存为0时，从t时段到T 时段的子问题的最优费用值 最优值（费用）为 f1 . 计算复杂性为

例4.3 （旅行商问题，即TSP） NP-Hard 旅行商问题 - 动态规划方法 例4.3 （旅行商问题，即TSP） NP-Hard 记n个城市为1，2，…，n. 对于给定的集合 和 ， 记C（S，k）是由城市1出发，遍历S中每个城市恰好一次，最后终止在城市k的最优费用. 则当S中只有一个元素k时，C（S，k）= d1,k ； 当S中有多于一个元素时， C（S，k）= 这一方程的求解要求对一切给定大小的集合S及S中的每个可能的元素k，计算 C（S，k）的值. 当 时，如果C（S，k）的值对 都已经通过计算得到，则最优环游的最小费用为

旅行商问题 - 动态规划方法 计算中所需的加法和比较的次数等于 如果我们把C（S，k）的每个值记录在一个存储单元中，则我们需要的空间数量为 上述算法的时间和空间复杂度都是非多项式的. 但是，如果与完全枚举法所需进行的（n-1）！次环游的枚举相比，其计算量的节省是明显的.

几何规划 例4.4 用动态规划法求解如下几何规划（一种特殊的非线性规划）问题 令 ， ， ，则目标函数为 对非负实数u，令 则原问题等价于求解 f3(6) 递推方程 边界条件为

布 置 作 业 目的 掌握动态规划的基本概念和基本理论； 掌握利用动态规划解决实际问题； 内容 《网络优化》第115-118页 3; 　7（2）; 　9；　　10*(选做)