网络优化动态规划.ppt

1,网 络 优 化,Network Optimization /netopt,清华大学数学科学系 谢金星 办公室：理科楼2266# （电话：62787812） Email: /jxie/courses/netopt,清华大学课号：70420133,第4章动态规划 (Dynamic Programming),2,动态规划问题的例子,例（续例1.2）最短路问题 (Shortest Path Problem),许多网络优化问题要用到动态规划技术,S,T,特点：多阶段决策 - 子决策仍然最优 - 动态规划(DP)技术,动态规划 R.E. Bellman (1950s),3,所谓决策(Decision Making)，就是人们为了达到一定的目的，从若干个可能的策略(Policy)（如行动、方案）中选取最好的策略的过程. 一般来说，一个决策模型包含三个最基本的因素： （1）自然状态（或简称状态, State）：这是指决策活动中决策者无法控制的一些因素，即决策时客观对象所具备的基本条件. 状态的集合称为状态集合或状态空间. （2）策略：这是指决策活动中决策者可以采取的行动方案. 策略的集合称为策略集合或策略空间. （3）益损值：这是指决策活动中决策者可以采取不同的策略，在不同的自然状态下所获得的收益或损失值. 它是策略和状态的函数，也是决策活动的目标和基础.,4.1.1 多阶段决策模型,战略决策(高层决策)、战术决策(中层决策)、操作决策(基本决策) 单目标决策、多目标决策 单阶段决策（一次决策）、多阶段决策 确定型决策、非确定型决策或风险型决策（随机决策、模糊决策）,4,多阶段决策过程,多阶段决策（Multi-Stage Decision Making），是将决策问题的全过程恰当地划分为若干个相互联系的子过程（每个子过程为一个阶段），以便按照一定的次序去求解. 阶段一般是根据时间和空间的自然特征来划分，以便于问题的求解为目的. 描述阶段的变量称为阶段变量，一般用k表示. 从第k个阶段开始点到全过程终点的过程称为后部子过程，或k子过程.,在多阶段决策问题中，状态表示每个阶段开始时所处的自然状况或客观条件. 描述过程状态的变量称为状态变量，一般用xk表示第k个阶段的状态变量.,当过程处于某个阶段的某个状态时，从该状态演变为下一个阶段某状态的选择，称为决策（抉择，Decision）. 描述决策的变量称为决策变量，一般用uk表示第k个阶段的决策变量，而用Uk(xk)表示第k个阶段xk状态下的所有允许决策的集合.,5,状态转移方程,无后效性的多阶段决策过程,动态规划中，多阶段决策问题具有无后效性（马尔科夫性质），即当某阶段的状态一旦确定,则此后过程的演变不再受此前各状态和决策的影响, 或者说“未来与过去无关”. 即由状态xk出发的后部子过程可以看成一个以xk为初始状态的独立过程.,相应于后部子过程（k子过程）的决策序列称为子策略，记为pk,n(xk) ，所有允许子策略的集合记为Pk,n(xk).,由所有各阶段的决策组成的决策序列称为全过程策略，或简称策略，记为p1,n(x1). 可供选择的所有全过程策略的集合构成允许策略集合，记为P1,n(x1) .其中能使总体性能达到最优的策略称为最优策略，一般记为,6,一般记为,无后效性的多阶段决策过程 - 准则函数及可分性,准则函数/指标函数（Criterion Function）是衡量策略好坏的尺度(益损值). 定义在全过程上的准则函数相当于目标函数，一般记为 V1,n(x1; p1,n ) ，或简记为V1,n 定义在k子过程上的准则函数，记为Vk,n(xk; pk,n ) ,简记为Vk,n 准则函数在第k阶段一个阶段内的取值称为第k阶段的准则函数，记为vk(xk; uk),最优性原理中，准则函数具有（阶段）可分性，即,7,4.1.2 最优性定理,定理4.1 设有一个准则函数可分的无后效性的多阶段决策过程,阶段变量k=1,2,n,允许策略 是最优策略的充要条件是: 对任意1kn, 当初始状态为x1时, 有 (4.3) 式中 , ,即 是由给定的初始状态x1和子策略p1，k-1所确定的第k阶段的状态.,证明: 必要性. 设允许策略 是最优策略，则,8,最优性定理,充分性. 设允许策略 满足定理的条件（4.3）, 为任一允许策略，则,因为,所以, 是最优策略,证毕,9,“全过程的最优策略具有这样的性质：不管该最优策略上某状态以前的状态和决策如何，对该状态而言，余下的诸决策必定构成最优子策略. ”即：最优策略的任一后部子策略都是最优的.,4.1.3 最优化原理,这只是最优性定理的一个推论，即最优策略的必要条件.,10,建立动态规划模型的基本过程是： （1） 正确划分阶段，选择阶段变量k. （2） 对每个阶段，正确选择状态变量xk. 选择状态变量时应当注意两点：一是要能够正确描述受控过程的演变特性，二是要满足无后效性. （3） 对每个阶段，正确选择决策变量uk . （4） 列出相邻阶段的状态转移方程： xk+1= Tk(xk, uk). （5） 列出按阶段可分的准则函数V1,n .,假设问题的目标是极小化,42 动态规划基本方程,11,逆序递推,fk(xk)表示第k阶段初始状态为xk时，k后部子过程的最优准则函数,12,顺序递推,fk(xk+1)表示第k阶段（结束）状态为xk+1时，起始阶段到k阶段（可以称为k前部子过程）的最优准则函数,优点：1、动态规划方法可以处理广泛的实际优化问题； 2、可以得到各阶段的一系列最优解.,缺点：隐式枚举方法 - 指数算法, 当问题规模较大时, 也会遇到维数障碍(维数灾)的问题.,13,例4.1 （资源分配问题） 某公司现有M台设备准备分配给该公司所属的N家工厂. 当分配台uk设备给工厂k时，工厂k利用这些设备为公司创造的利润（假设非负）为gk(uk)(假设为非降函数). 应当如何分配设备资源，使得公司总利润最大？,上述问题可能是非线性整数规划, 甚至gk(uk)没有显式表达式,43 应用动态规划方法的几个例子,14,状态变量xk - 第k阶段初分配者手中拥有的设备台数. 由题意可知 x0 = M， xN+1 = 0,资源分配问题,阶段k的准则函数为,共有N个工厂，可以把问题分解为N个阶段： 当阶段k=N时，把手中设备分配给工厂N； 当阶段k=N-1时，把手中设备分配给工厂N-1； 依次类推； 在任意阶段k时，把手中设备分配给工厂k； 当阶段k=1时，把手中设备分配给工厂1.,决策变量uk - 第k阶段分配给工厂k的设备台数（ ）,15,资源分配问题,用fk(xk) 表示将手中资源xk分配给工厂k,k+1, N 时的最大利润，原问题即为计算 f1(M),M=4，N=3，边界条件 f4(x4) = f4(0) =0,k=3时： （增函数）,具体计算（例）,16,资源分配问题,k=2时：,17,资源分配问题,k=1时：,最优解 ,最大利润为 .,推广1： 二维（或多维）资源分配问题,推广2：非线性整数规划问题 ， 如：,M=4, N=3,18,例4.2 （Single-level Uncapacitated Lotsizing） 某工厂生产某种产品用以满足市场需求,且已知在时段t中的市场需求为dt . 在某时段t, 如果开工生产, 则生产开工所需的生产准备费为st , 单件产品的生产费为ct . 在某时段t期末, 如果有产品库存, 单件产品的库存费为ht . 假设初始库存为0, 不考虑能力限制, 工厂应如何安排生产, 可以保证按时满足生产, 且使总费用最小? （Wagner Whitin，1958）,单产品、无能力限制的批量问题,假设在时段t, 产品的生产量为xt , 期末产品的库存为It (I0 =0); 用二进制变量yt表示在时段t工厂是否进行生产准备.,19,可以只考虑,当ct为常数，目标函数变为,单产品、无能力限制的批量问题,可以证明：一定存在满足条件 的最优解.,假设费用均非负，则在最优解中 ，即,用ft表示当t时段初始库存为0时，从t时段到T 时段的子问题的最优费用值,最优值（费用）为 f1 . 计算复杂性为,20,旅行商问题 - 动态规划方法,例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）的值对 都已经通过计算得到，则最优环游的最小费用为,21,上述算法的时间和空间复杂度都是非多项式的. 但是，如果与完全枚举法所需进行的（n-1）！次环游的枚举相比，其计算量的节省是明显的.,旅行商问题 - 动态规划方法,计算中所需的加法和比较的次数等于,如果我们把C（S，k）的每个