网络优化动态规划.ppt

《网络优化动态规划.ppt》由会员分享，可在线阅读，更多相关《网络优化动态规划.ppt（23页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、网络优化动态规划 Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life,there is hope。有生命必有希望。有生命必有希望动态规划问题的例子例（续例例（续例1.2）最短路问题最短路问题(ShortestPathProblem)许多网络优化问题要用到动态规划技术许多网络优化问题要用到动态规划技术S ST T特点：多阶段决策特点：多阶段决策-子决策仍然最优子决策仍然最优-动态规划动态规划(DP)(DP)技术技术动态规划动态规划 R.E.Bellman(1950s)R.E.Bellman(1950s)2所所谓谓决决策策(Dec

2、ision(Decision Making)Making)，就就是是人人们们为为了了达达到到一一定定的的目目的的，从从若若干干个个可可能能的的策策略略(Policy)(Policy)（如如行行动动、方方案案）中中选选取取最最好好的的策策略略的的过过程程.一一般般来来说说，一个决策模型包含三个最基本的因素：一个决策模型包含三个最基本的因素：（1 1）自自然然状状态态（或或简简称称状状态态,StateState）：这这是是指指决决策策活活动动中中决决策策者者无无法法控控制制的的一一些些因因素素，即即决决策策时时客客观观对对象象所所具具备备的的基基本本条条件件.状状态态的的集集合合称称为为状状态集合

3、或状态空间态集合或状态空间.（2 2）策策略略：这这是是指指决决策策活活动动中中决决策策者者可可以以采采取取的的行行动动方方案案.策策略略的的集集合合称称为策略集合或策略空间为策略集合或策略空间.（3 3）益损值：这是指决策活动中决策者可以采取不同的策略，在不同的自）益损值：这是指决策活动中决策者可以采取不同的策略，在不同的自然状态下所获得的收益或损失值然状态下所获得的收益或损失值.它是策略和状态的函数，也是决策活动它是策略和状态的函数，也是决策活动的目标和基础的目标和基础.4.1.1多阶段决策决策模型模型战略决策战略决策(高层决策高层决策)、战术决策、战术决策(中层决策中层决策)、操作决策、

4、操作决策(基本决策基本决策)单目标决策、多目标决策单目标决策、多目标决策单阶段决策（一次决策）、多阶段决策单阶段决策（一次决策）、多阶段决策确定型决策、非确定型决策或风险型决策（随机决策、模糊决策）确定型决策、非确定型决策或风险型决策（随机决策、模糊决策）3多多阶阶段决策段决策过过程程多阶段决策（多阶段决策（Multi-Stage Decision MakingMulti-Stage Decision Making），是将决策问题），是将决策问题的的全过程全过程恰当地划分为若干个相互联系的子过程（每个子过程恰当地划分为若干个相互联系的子过程（每个子过程为一个为一个阶段阶段），以便按照一定的次序

5、去求解），以便按照一定的次序去求解.阶段一般是根据阶段一般是根据时间和空间的自然特征来划分，以便于问题的求解为目的时间和空间的自然特征来划分，以便于问题的求解为目的.描描述阶段的变量称为述阶段的变量称为阶段变量阶段变量，一般用，一般用k k表示表示.从第从第k k个阶段开始个阶段开始点到全过程终点的过程称为点到全过程终点的过程称为后部子过程后部子过程，或，或k k子过程子过程.在在多多阶阶段段决决策策问问题题中中，状状态态表表示示每每个个阶阶段段开开始始时时所所处处的的自自然然状状况况或或客客观观条条件件.描描述述过过程程状状态态的的变变量量称称为为状状态态变变量量，一一般般用用xk表表示第示

6、第k k个阶段的状态变量个阶段的状态变量.当当过过程程处处于于某某个个阶阶段段的的某某个个状状态态时时，从从该该状状态态演演变变为为下下一一个个阶阶段段某某状状态态的的选选择择，称称为为决决策策（抉抉择择，DecisionDecision）.描描述述决决策策的的变变量量称称为为决决策策变变量量，一一般般用用u uk k表表示示第第k k个个阶阶段段的的决决策策变变量量，而而用用U Uk k(x(xk k)表示第表示第k k个阶段个阶段x xk k状态下的所有允许决策的集合状态下的所有允许决策的集合.4状态转移方程状态转移方程 无后效性的多无后效性的多阶阶段决策段决策过过程程动态规划中，多阶段决

7、策问题具有动态规划中，多阶段决策问题具有无后效性无后效性（马尔科夫性质），（马尔科夫性质），即当某阶段的状态一旦确定即当某阶段的状态一旦确定,则此后过程的演变不再受此前各状则此后过程的演变不再受此前各状态和决策的影响态和决策的影响,或者说或者说“未来与过去无关未来与过去无关”.”.即由状态即由状态xk出发出发的后部子过程可以看成一个以的后部子过程可以看成一个以xk为初始状态的独立过程为初始状态的独立过程.相应于后部子过程（相应于后部子过程（k k子过程）的决策序列称为子过程）的决策序列称为子策略子策略，记为，记为pk,n(xk)，所有允许子策略的集合记为，所有允许子策略的集合记为Pk,n(xk

8、).).由所有各阶段的决策组成的决策序列称为由所有各阶段的决策组成的决策序列称为全过程策略全过程策略，或简称，或简称策略策略，记为，记为p1,n(x1).).可供选择的所有全过程策略的集合构成可供选择的所有全过程策略的集合构成允允许策略许策略集合，记为集合，记为P1,n(x1).).其中能使总体性能达到最优的策略其中能使总体性能达到最优的策略称为称为最优策略最优策略，一般记为，一般记为 5一般记为一般记为 无后效性的多无后效性的多阶阶段决策段决策过过程程-准则函数及可分性准则函数及可分性准则函数准则函数/指标函数（指标函数（Criterion FunctionCriterion Functio

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

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

11、）,为任一允许策略，则为任一允许策略，则 因为因为所以所以,是最优策略是最优策略 证毕证毕 8“全过程的最优策略具有这样的性质：不管该最优策略上某状全过程的最优策略具有这样的性质：不管该最优策略上某状态以前的状态和决策如何，对该状态而言，余下的诸决策必定态以前的状态和决策如何，对该状态而言，余下的诸决策必定构成最优子策略构成最优子策略.”.”即：最优策略的任一后部子策略都是最优即：最优策略的任一后部子策略都是最优的的.4.1.3 4.1.3 最优化原理最优化原理 这只是最优性定理的一个推论，即最优策略的必要条件这只是最优性定理的一个推论，即最优策略的必要条件.9建立动态规划模型的基本过程是：建

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

13、程动态规划基本方程 10逆序递推逆序递推 k=1k=n kk=2 fk(xk)表示第k阶段初始状态为xk时，k后部子过程的最优准则函数11顺序递推顺序递推 fk(xk+1)表示第k阶段（结束）状态为xk+1时，起始阶段到k阶段（可以称为k前部子过程）的最优准则函数k=1k=n kk=2 优点：1、动态规划方法可以处理广泛的实际优化问题；2、可以得到各阶段的一系列最优解.缺点：隐式枚举方法-指数算法,当问题规模较大时,也会遇到维数障碍(维数灾)的问题.12例例4.1 4.1（资资源源分分配配问问题题）某某公公司司现现有有M台台设设备备准准备备分分配配给给该该公公司司所所属属的的N家家工工厂厂.当

14、当分分配配台台uk设设备备给给工工厂厂k时时，工工厂厂k利利用用这这些些设设备备为为公公司司创创造造的的利利润润（假假设设非非负负）为为gk(uk)(假假设设为为非非降降函函数数).应当如何分配设备资源，使得公司总利润最大？应当如何分配设备资源，使得公司总利润最大？上述问题可能是非线性整数规划上述问题可能是非线性整数规划,甚至甚至gk(uk)没有显式表达式没有显式表达式43应用动态规划方法的几个例子工厂k设备数1230123404677025680357813状态变量状态变量xk -第第k k阶段初分配者手中拥有的设备台数阶段初分配者手中拥有的设备台数.由题意可知由题意可知 x0=M，xN+1

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

16、fk(xk)表示将手中资源表示将手中资源xk分配给工厂分配给工厂k,k+1,N 时的最大利润，时的最大利润，原问题即为计算原问题即为计算f1(M)M=4M=4，N=3N=3，边界条件，边界条件 f4(x4)=f4(0)=0k k=3=3时：时：（增函数）（增函数）具体计算（例）具体计算（例）15资源分配问题资源分配问题k k=2=2时：时：16资源分配问题资源分配问题k k=1=1时：时：最优解最优解 ,最大利润为最大利润为 .推广推广1 1：二维（或多维）资源分配问题二维（或多维）资源分配问题 推广推广2 2：非线性整数规划问题：非线性整数规划问题 ，如：如：M=4,N=3M=4,N=317

17、例例4.2 4.2（Single-level Uncapacitated LotsizingSingle-level Uncapacitated Lotsizing）某工厂生产某种产品用以满足市场需求某工厂生产某种产品用以满足市场需求,且已知在时段且已知在时段t t中的市中的市场需求为场需求为dt.在某时段在某时段t t,如果开工生产如果开工生产,则生产开工所需的生则生产开工所需的生产准备费为产准备费为st,单件产品的生产费为单件产品的生产费为ct.在某时段在某时段t t期末期末,如果如果有产品库存有产品库存,单件产品的库存费为单件产品的库存费为ht.假设初始库存为假设初始库存为0,0,不考不

18、考虑能力限制虑能力限制,工厂应如何安排生产工厂应如何安排生产,可以保证按时满足生产可以保证按时满足生产,且使总费用最小且使总费用最小?（Wagner WhitinWagner Whitin，19581958）单产品、无能力限制的批量问题假设在时段假设在时段t t,产产品的生产量为品的生产量为xt ,期末产品的库存为期末产品的库存为It(I0=0);=0);用二进用二进制变量制变量yt表示在时表示在时段段t t工厂是否进行工厂是否进行生产准备生产准备.18可以只考虑可以只考虑当当ct为常数，目标函数变为为常数，目标函数变为 单产品、无能力限制的批量问题可以证明：一定存在满足条件可以证明：一定存在

19、满足条件 的最优解的最优解.假设费用均非负，则在最优解中假设费用均非负，则在最优解中 ，即，即 用用ft表示当表示当t t时段初始库存为时段初始库存为0 0时，从时，从t t时段到时段到T T 时段的子问题的最优费用值时段的子问题的最优费用值 最优值（费用）为最优值（费用）为 f1.计算复杂性为计算复杂性为 19旅行商问题旅行商问题-动态规划方法动态规划方法例例4.3 4.3 （旅行商问题，即（旅行商问题，即TSPTSP）NP-Hard NP-Hard记记n n个个城城市市为为1 1，2 2，n n.对对于于给给定定的的集集合合 和和 ，记记C C（S S，k k）是是由由城城市市1 1出出发

20、发，遍遍历历S S中中每每个个城城市市恰恰好好一一次次，最最后后终终止止在在城城市市k k的最优费用的最优费用.则当则当S S中只有一个元素中只有一个元素k k时，时，C C（S S，k k）=d1,k ；当当S S中有多于一个元素时，中有多于一个元素时，C C（S S，k k）=这这一一方方程程的的求求解解要要求求对对一一切切给给定定大大小小的的集集合合S S及及S S中中的的每每个个可可能能的的元素元素k k，计算，计算 C C（S S，k k）的值）的值.当当时时，如如果果C C（S S，k k）的的值值对对都都已已经经通过计算得到，则通过计算得到，则最优环游的最小费用最优环游的最小费用

21、为为 20上上述述算算法法的的时时间间和和空空间间复复杂杂度度都都是是非非多多项项式式的的.但但是是，如如果果与与完完全全枚枚举举法法所所需需进进行行的的（n-1n-1）！次次环环游游的的枚枚举举相相比比，其其计计算算量量的节省是明显的的节省是明显的.旅行商问题旅行商问题-动态规划方法动态规划方法 计算中所需的加法和比较的次数等于计算中所需的加法和比较的次数等于 如果我们把C（S，k）的每个值记录在一个存储单元中，则我们需要的空间数量为21例例4.4 4.4 用用动动态态规规划划法法求求解解如如下下几几何何规划（一种特殊的非线性规划）问题规划（一种特殊的非线性规划）问题几何规划几何规划令令 ，则目标函数为，则目标函数为对非负实数对非负实数u，令，令则原问题等价于求解则原问题等价于求解 f3(6)递推方程递推方程边界条件为边界条件为 22布置作 业目的掌握动态规划的基本概念和基本理论；掌握利用动态规划解决实际问题；内容网络优化第网络优化第115-118页页3;7（2）;9；10*(选做选做)23