《运筹学-第6章动态规划》由会员分享，可在线阅读，更多相关《运筹学-第6章动态规划（80页珍藏版）》请在金锄头文库上搜索。
1、2018/10/17,1,第六章 动态规划 Dynamic Programming，DP,美国数学家贝尔曼 （Richard. Bellman, (19201984) ),创始时间,上个世纪50年代,创始人,动态规划是运筹学的一个主要分支, 同时也是现代企业管理中的一种重要决策方法, 它是解决多阶段决策过程的最优化的一种方法。,2018/10/17,2,动态规划 模型分类,离散确定型,离散随机型,连续确定型,连续随机型,动态规划解决问题的思路独特,在处理某些优化问题时, 有时比线性规划或者非线性规划更有效.需要丰富的想象力去建立模型，并能用创造性的技巧去求解。,其中离散确定性是最基本的, 本章
2、主要介绍这种类型的问题,介绍动态规划的基本思想、原理和方法.,2018/10/17,3,本章主要内容,多阶段决策过程及其问题举例 最短路问题动态规划的基本概念和基本方程 动态规划应用举例 资源分配问题 背包问题 生产库存问题 ,2018/10/17,4,6.1 多阶段决策过程及其问题举例,动态规划研究的问题-多阶段决策问题（顺序决策问题） 研究的问题可以在时间或空间上划分为若干个相互联系阶段，称为”时段”。 在每一个时段都需要做出决策,每时段的决策将影响到下一时段的决策, 因此决策者每段决策时, 不仅要考虑本阶段目标最优,还应考虑最终目标的最优, 最终达到整个决策活动的总体目标最优.,2018
3、/10/17,5,动态规划方法与“时间”关系很密切，随着时间过程的发展而决定各时段的决策，产生一个决策序列，这就是“动态”的意思。然而，它也可以处理与时间无关的静态问题，只要在问题中人为地引入“时段”因素，就可以将其转化为一个多阶段决策问题。,2018/10/17,6,例1 最短路径问题,求从A到E的最短路径。 显然，这种运输网络问题是静态决策问题。但是，按照网络中点的分布，可以把它分为4个阶段，而作为多阶段决策问题来研究。,2018/10/17,7,第一种方法称做全枚举法或穷举法。它的基本思想是列举出所有可能发生的方案和结果，再对它们一一进行比较，求出最优方案。这里从A到E的路程共有3321
4、18条可能的路线，分别算出各条路线的距离，最后进行比较，可知最优路线。显然，当组成交通网络的节点很多时，用穷举法求最优路线的计算工作量将会十分庞大，而且其中包含着许多重复计算第二种方法贪心算法，即所谓“局部最优路径”法，是说某人从k出发，他并不顾及全线是否最短，只是选择当前最短途径，“逢近便走”，错误地以为局部最优会致整体最优，在这种想法指导下，所取决策必是A B3 C3 D1 E. 距离为：1+11+8+5=25,2018/10/17,8,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,第
5、1阶段,第4阶段,第3阶段,第2阶段,状态,第三种方法是动态规划方法。,2018/10/17,9,基本思想：如果起点A经过B1,C1,D1而到终点E，则由C1出发经D1到E点这条子路线，是从C1到E的最短路线。所以，寻找最短路线，应该从最后一段开始找，然后往前递推.设 sk：第k阶段初的状态（所处的结点）; xk (sk)：在sk状态时第k阶段所作的决策, 决定下一个状态的位置； d(sk,xk)：第k阶段，采取策略xk 所发生的距离; fk (sk)：在第k阶段，由sk状态开始到终点E的最短距离.,2018/10/17,10,2,5,1,12,14,10,6,10,4,13,11,12,3,
6、9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f5(E)=0,2018/10/17,11,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D1)=5,f5(E)=0,2018/10/17,12,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D2)=2,f5(E)=0,f4(D1)=5,2018/10/17,13,2,5,1,12,14,
7、10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D2)=2,f5(E)=0,f3(C1)=8,f4(D1)=5,2018/10/17,14,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D2)=2,f5(E)=0,f3(C2)=7,f4(D1)=5,f3(C1)=8,2018/10/17,15,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3
8、,D1,A,B1,B3,B2,D2,E,C2,f4(D2)=2,f5(E)=0,f3(C3)=12,f4(D1)=5,f3(C1)=8,f3(C2)=7,2018/10/17,16,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D2)=2,f5(E)=0,f3(C3)=12,f4(D1)=5,f2(B1)=20,f3(C2)=7,f3(C1)=8,2018/10/17,17,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D
9、1,A,B1,B3,B2,D2,E,C2,f4(D2)=2,f5(E)=0,f3(C3)=12,f4(D1)=5,f2(B2)=14,f3(C2)=7,f3(C1)=8,f2(B1)=20,2018/10/17,18,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D2)=2,f5(E)=0,f3(C3)=12,f4(D1)=5,f2(B3)=19,f3(C2)=7,f3(C1)=8,f2(B1)=20,f2(B2)=14,2018/10/17,19,2,5,1,12,14,10,6,
10、10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D2)=2,f5(E)=0,f3(C3)=12,f4(D1)=5,f2(B3)=19,f3(C2)=7,f3(C1)=8,f1(A)=19,f2(B2)=14,f2(B1)=20,2018/10/17,20,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D2)=2,f5(E)=0,f3(C3)=12,f4(D1)=5,f2(B3)=19,f3(C2)=7,f3(
11、C1)=8,f1(A)=19,f2(B2)=14,f2(B1)=20,状态 最优决策 状态 最优决策 状态 最优决策 状态 最优决策 状态,A （ A，B2） B2 （B2，C1） C1 （C1，D1） D1 （D1，E） E 从A到E的最短路径为19，路线为AB 2C1 D1 E,2018/10/17,21,多阶段决策过程及实例-标号法,4,3,7,5,9,7,6,8,13,10,9,12,13,16,18,该点到G点的最短距离,从G到A的解法称为逆序解法。,注：因为从A到G的最短路与从G到A的最短路是一样的， 因此也可以从A出发来找。从A到G的解法称为顺序解法。,2018/10/17,22
12、,综上所述可见，全枚举法虽可找出最优方案，但不是个好算法，局部最优法则完全是个错误方法，只有动态规划方法属较科学有效的算法。它的基本思想是，把一个比较复杂的问题分解为一系列同类型的更易求解的子问题，便于应用计算机。,2018/10/17,23,6.2 动态规划的基本概念和基本方程,(一) 基本概念和基本方程,(1) 阶段：k=1,，n,(2) 状态变量sk ：第k阶段的状态. 状态变量取值的集合成为状态集合，用Sk表示。状态集合可以是一离散取值的集合，也可以为一连续的取值区间，视具体问题而定,(3) 决策变量uk(sk) ：第k阶段的决定，Dk(sk)为决策变量的取值范围. 状态转移方程sk1
13、 T (sk,uk)：描述第k阶段与第k+1阶段的状态变量的关系,2018/10/17,24,(5)指标 v(sk ,uk) ：第k阶段状态sk情况下采取决策uk得到的结果（距离、得益、成本等） 指标函数是指各阶段指标的累计。即 V (sk,uk, , sn,un, sn+1)=vk(sk,uk)*vk+1(sk+1,uk+1)*vn(sn,un) 它表示从第k阶段的状态sk开始到第n阶段的终止状态的指标累计。式中*表示某种运算符，一般为加法运算或者乘积运算。,(6)最优指标函数fk (sk) ：它表示从第k阶段的状态sk开始到第n阶段的终止状态的过程，采取最优策略得到的指标函数值,阶段函数,
14、2018/10/17,25,逆推公式,或,多阶段决策问题中，常见的目标函数形式之一是取各阶段效益之和的形式.有些问题，如系统可靠性问题，其目标函数是取各阶段效益的连乘积形式. 总之，具体问题的目标函数表达形式需要视具体问题而定。,Max或者min,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,第1阶段,第4阶段,第3阶段,第2阶段,对例1,(1) 阶段：k1，2，4,(2) 状态变量：sk第k阶段初所处的位置, 状态集合 Sk 如S2 :=B1 , B2 , B3.,2018/10/17,
15、27,(3) 决策变量uk ：在第k段sk状态时决定选取的下一段的某点.,(4) 状态转移方程 ：sk1 uk ( sk),(5) 阶段效益：d(sk,uk)为第k段，采取决策uk 到下一状态的距离.,(6) 最优指标函数： fk (sk)：第k段，在sk状态时到终点E的最短距离.,逆推公式：,2018/10/17,28,（二）贝尔曼最优化原理：一个最优策略具有这样的性质，即不论初始状态与初始策略如何，对于先前决策所造成的状态而言，余下所有决策必构成最优决策。 也即：一个最优策略的子策略也是最优的。,2018/10/17,29,（三）解法步骤反向条件优化正向求最优解,2018/10/17,30,6.3 应用举例,例2 资源分配问题-1 例3 资源分配问题-2 例4 背包问题 例5 生产库存问题 例6 可靠性问题 例7 机器负荷分配问题 等等,2018/10/17,31,例 2 资源分配问题-1,某公司准备将5台设备分配给所属的三个子工厂，各工厂获得设备后的可盈利情况如表所示。问：如何分配这五台设备，才能使公司获得的收益最大？,
