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

网

络

优

化

NetworkOptimization/netopt清华大学数学科学系谢金星办公室：理科楼2266#（电话：62787812）Email:jxie@/~jxie/courses/netopt清华大学课号：70420133第4章动态规划(DynamicProgramming)倍便谦朱欢图掌醇擒肉萝葛备仪桂梁冻苹婶废涟毡惨庶淋吊滚云辈柿涸剖网络优化-第4章动态规划网络优化-第4章动态规划1动态规划问题的例子例（续例1.2）最短路问题

(ShortestPathProblem)许多网络优化问题要用到动态规划技术ST特点：多阶段决策-子决策仍然最优-动态规划(DP)技术动态规划–R.E.Bellman(1950’s)恿瞬拾脆蚊群出轻练抱丑捷烯芬率辫诛箍砸蕉波却教费婚估肚拧唉乐自缚网络优化-第4章动态规划网络优化-第4章动态规划2所谓决策(DecisionMaking)，就是人们为了达到一定的目的，从若干个可能的策略(Policy)（如行动、方案）中选取最好的策略的过程.一般来说，一个决策模型包含三个最基本的因素：（1）自然状态（或简称状态,State）：这是指决策活动中决策者无法控制的一些因素，即决策时客观对象所具备的基本条件.状态的集合称为状态集合或状态空间.（2）策略：这是指决策活动中决策者可以采取的行动方案.策略的集合称为策略集合或策略空间.（3）益损值：这是指决策活动中决策者可以采取不同的策略，在不同的自然状态下所获得的收益或损失值.它是策略和状态的函数，也是决策活动的目标和基础.

4.1.1多阶段决策模型

战略决策(高层决策)、战术决策(中层决策)、操作决策(基本决策)单目标决策、多目标决策单阶段决策（一次决策）、多阶段决策确定型决策、非确定型决策或风险型决策（随机决策、模糊决策）今几使削禹剥含痪余贯封日环拣撮和一游儿绚拙谅坑腕惟式揭弟虹丈狰鞋网络优化-第4章动态规划网络优化-第4章动态规划3多阶段决策过程多阶段决策（Multi-StageDecisionMaking），是将决策问题的全过程恰当地划分为若干个相互联系的子过程（每个子过程为一个阶段），以便按照一定的次序去求解.阶段一般是根据时间和空间的自然特征来划分，以便于问题的求解为目的.描述阶段的变量称为阶段变量，一般用k表示.从第k个阶段开始点到全过程终点的过程称为后部子过程，或k子过程.在多阶段决策问题中，状态表示每个阶段开始时所处的自然状况或客观条件.描述过程状态的变量称为状态变量，一般用xk表示第k个阶段的状态变量.当过程处于某个阶段的某个状态时，从该状态演变为下一个阶段某状态的选择，称为决策（抉择，Decision）.描述决策的变量称为决策变量，一般用uk表示第k个阶段的决策变量，而用Uk(xk)表示第k个阶段xk状态下的所有允许决策的集合.朴叠诡耳殉舔焊惰纳尝代道蹈盖着肠木像厘声珍庐泻劲遣孕殃摆漓隐晴秩网络优化-第4章动态规划网络优化-第4章动态规划4状态转移方程

无后效性的多阶段决策过程动态规划中，多阶段决策问题具有无后效性（马尔科夫性质），即当某阶段的状态一旦确定,则此后过程的演变不再受此前各状态和决策的影响,或者说“未来与过去无关”.即由状态xk出发的后部子过程可以看成一个以xk为初始状态的独立过程.相应于后部子过程（k子过程）的决策序列称为子策略，记为pk,n(xk)，所有允许子策略的集合记为Pk,n(xk).由所有各阶段的决策组成的决策序列称为全过程策略，或简称策略，记为p1,n(x1).可供选择的所有全过程策略的集合构成允许策略集合，记为P1,n(x1).其中能使总体性能达到最优的策略称为最优策略，一般记为崔晋戮倦袭衬摸捏哟秧淖告徊沦虞匠违北涨坪熏题梯辞积磁援砸临使溢辕网络优化-第4章动态规划网络优化-第4章动态规划5一般记为 无后效性的多阶段决策过程-准则函数及可分性准则函数/指标函数（CriterionFunction）是衡量策略好坏的尺度(益损值).定义在全过程上的准则函数相当于目标函数，一般记为V1,n(x1;p1,n

)，或简记为V1,n定义在k子过程上的准则函数，记为Vk,n(xk;pk,n

),简记为Vk,n

准则函数在第k阶段一个阶段内的取值称为第k阶段的准则函数，记为vk(xk;uk)最优性原理中，准则函数具有（阶段）可分性，即华敌刊禹泌乎庸仿啪胺缕婶二替雌穗玄醇旧摩酪锅纶蔑算售二扼赂酒怜酞网络优化-第4章动态规划网络优化-第4章动态规划64.1.2最优性定理定理4.1设有一个准则函数可分的无后效性的多阶段决策过程,阶段变量k=1,2,…,n,允许策略是最优策略的充要条件是:对任意1<k<n,当初始状态为x1时,有 (4.3)式中,,即是由给定的初始状态x1和子策略p1，k-1所确定的第k阶段的状态.证明:必要性.设允许策略是最优策略，则

恤壬掷胀收酌友陛播减您很敌涂图括冈禹扁龙陛兔兑树疲疙立绅赛惶勤吐网络优化-第4章动态规划网络优化-第4章动态规划7最优性定理充分性.设允许策略满足定理的条件（4.3）,

为任一允许策略，则

因为所以,是最优策略

证毕

钓犊啥让嚷殷个觅翼武迟沙预阀奎救阅父究焕里俯剁摄冕汝选河狐雷痹周网络优化-第4章动态规划网络优化-第4章动态规划8“全过程的最优策略具有这样的性质：不管该最优策略上某状态以前的状态和决策如何，对该状态而言，余下的诸决策必定构成最优子策略.”即：最优策略的任一后部子策略都是最优的.4.1.3最优化原理这只是最优性定理的一个推论，即最优策略的必要条件.浊逐说挂娜脊吭悲牢沏局泅瘁酌凿简抑冲想焙哩喝恕典崭队赘簧姚威跪褥网络优化-第4章动态规划网络优化-第4章动态规划9建立动态规划模型的基本过程是：（1）

正确划分阶段，选择阶段变量k.（2）

对每个阶段，正确选择状态变量xk.选择状态变量时应当注意两点：一是要能够正确描述受控过程的演变特性，二是要满足无后效性.（3）

对每个阶段，正确选择决策变量uk.（4）

列出相邻阶段的状态转移方程：xk+1=Tk(xk,uk).（5）列出按阶段可分的准则函数V1,n.假设问题的目标是极小化4．2动态规划基本方程挎撒酋盘丝材剁铱穆故祟占扳箭絮滤譬腐蛤矗适吧誓抖把永燕对峡泽钦孰网络优化-第4章动态规划网络优化-第4章动态规划10逆序递推k=1k=n

kk=2

fk(xk)表示第k阶段初始状态为xk时，k后部子过程的最优准则函数

屹楔配崔捍胃研邵弄旨碍若赞觉值卢系痞屁思蓝驰遇碳袒轿锹捂佐遏敬摔网络优化-第4章动态规划网络优化-第4章动态规划11顺序递推fk(xk+1)表示第k阶段（结束）状态为xk+1时，起始阶段到k阶段（可以称为k前部子过程）的最优准则函数

k=1k=n

kk=2

优点：1、动态规划方法可以处理广泛的实际优化问题；2、可以得到各阶段的一系列最优解.缺点：隐式枚举方法-指数算法,当问题规模较大时,也会遇到维数障碍(维数灾)的问题.

无纶照餐肋与病注咋丰狱纳令耻躁沾扭曳芦疆格缠命她债纸啊店担冬蒙栖网络优化-第4章动态规划网络优化-第4章动态规划12例4.1（资源分配问题）

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

工厂k设备数

1

2

301234046770256803578词匡戮聚录汉集釜殴吝砰淤贿义玻弊绿脊冉痕釉翅啊淬眼曼历毫澎烹凛粕网络优化-第4章动态规划网络优化-第4章动态规划13状态变量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的设备台数（）状态转移方程亨酗漾梅绊淆舜腔暖由铅堆更添翁贩综量讣音荡字逗世负杭维殉幕沈灌糜网络优化-第4章动态规划网络优化-第4章动态规划14资源分配问题用fk(xk)

表示将手中资源xk分配给工厂k,k+1,…,N时的最大利润，原问题即为计算f1(M)

M=4，N=3，边界条件f4(x4)=f4(0)=0k=3时：（增函数）

具体计算（例）

袜孩垫祁胎拢载痔氮岁眼芬莹慈斩赎忌讽锑汛黔躯奴佑炽茁烷鞋面触森酉网络优化-第4章动态规划网络优化-第4章动态规划15资源分配问题k=2时：

捎祝虾掣箕幻痴进寄认隔抿卸绪漱侍褪周慧气贰扮淹贷这乞昌界杯刚掳羌网络优化-第4章动态规划网络优化-第4章动态规划16资源分配问题k=1时：最优解,最大利润为. 推广1：二维（或多维）资源分配问题推广2：非线性整数规划问题，如：M=4,N=3金奢卿梳燕汲渔崩答做岭挎吹钱俐拢楞例淹镜彬迸谁揖臭鳞粉艺刘琶敌活网络优化-第4章动态规划网络优化-第4章动态规划17例4.2（Single-levelUncapacitatedLotsizing）某工厂生产某种产品用以满足市场需求,且已知在时段t中的市场需求为dt.在某时段t,如果开工生产,则生产开工所需的生产准备费为st,单件产品的生产费为ct.在某时段t期末,如果有产品库存,单件产品的库存费为ht.假设初始库存为0,不考虑能力限制,工厂应如何安排生产,可以保证按时满足生产,且使总费用最小?（Wagner–Whitin，1958）单产品、无能力限制的批量问题

假设在时段t,产品的生产量为xt,期末产品的库存为It(I0=0);用二进制变量yt表示在时段t工厂是否进行生产准备.富伪渐妮描灾巍颤竞毖骑央茵砒政秤谴非踞抓快登碳兴颜榜妈荒笼轿闹掏网络优化-第4章动态规划网络优化-第4章动态规划18可以只考虑当ct为常数，目标函数变为

单产品、无能力限制的批量问题可以证明：一定存在满足条件的最优解.假设费用均非负，则在最优解中，即用ft表示当t时段初始库存为0时，从t时段到T时段的子问题的最优费用值最优值（费用）为f1.计算复杂性为辆剩随归迈凛授盖待秘爆借芳北寿拟拌敖肄化培肿羽厢沾葬五慰尊哑帅打网络优化-第4章动态规划网络优化-第4章动态规划19旅行商问题-动态规划方法例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）的值对