网络优化-第4章+动态规划.ppt

1,网络优化,NetworkOptimization,清华大学数学科学系谢金星办公室：理科楼2266#（电话：62787812）Email:jxie,清华大学课号：70420133,第4章动态规划(DynamicProgramming),2,动态规划问题的例子,例（续例1.2）最短路问题(ShortestPathProblem),许多网络优化问题要用到动态规划技术,S,T,特点：多阶段决策-子决策仍然最优-动态规划(DP)技术,动态规划R.E.Bellman(1950s),3,所谓决策(DecisionMaking)，就是人们为了达到一定的目的，从若干个可能的策略(Policy)（如行动、方案）中选取最好的策略的过程.一般来说，一个决策模型包含三个最基本的因素：（1）自然状态（或简称状态,State）：这是指决策活动中决策者无法控制的一些因素，即决策时客观对象所具备的基本条件.状态的集合称为状态集合或状态空间.（2）策略：这是指决策活动中决策者可以采取的行动方案.策略的集合称为策略集合或策略空间.（3）益损值：这是指决策活动中决策者可以采取不同的策略，在不同的自然状态下所获得的收益或损失值.它是策略和状态的函数，也是决策活动的目标和基础.,4.1.1多阶段决策模型,战略决策(高层决策)、战术决策(中层决策)、操作决策(基本决策)单目标决策、多目标决策单阶段决策（一次决策）、多阶段决策确定型决策、非确定型决策或风险型决策（随机决策、模糊决策）,4,多阶段决策过程,多阶段决策（Multi-StageDecisionMaking），是将决策问题的全过程恰当地划分为若干个相互联系的子过程（每个子过程为一个阶段），以便按照一定的次序去求解.阶段一般是根据时间和空间的自然特征来划分，以便于问题的求解为目的.描述阶段的变量称为阶段变量，一般用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,一般记为,无后效性的多阶段决策过程-准则函数及可分性,准则函数/指标函数（CriterionFunction）是衡量策略好坏的尺度(益损值).定义在全过程上的准则函数相当于目标函数，一般记为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-levelUncapacitatedLotsizing）某工厂生产某种产品用以满足市场需求,且已知在时段t中的市场需求为dt.在某时段t,如果开工生产,则生产开工所需的生产准备费为st,单件产品的生产费为ct.在某时段t期末,如果有产品库存,单件产品的库存费为ht.假设初始库存为0,不考虑能力限制,工厂应如何安排生产,可以保证按时满足生产,且使总费用最小?（WagnerWhitin，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）的每