《《运筹学教程》胡云权 第五版 第四章 动态规划》由会员分享，可在线阅读，更多相关《《运筹学教程》胡云权 第五版 第四章 动态规划（55页珍藏版）》请在金锄头文库上搜索。
1、第四章 动态规划学习目标 多阶段决策过程 动态规划基本概念 动态规划基本思想 动态规划求解方法 动态规划应用【例1】从A点铺设一条管道到E点，图中两点间连线上数字表示两 点间距离。现需选一条由A到E的铺管线路，使总距离最短。1、最短路线问题多阶段决策过程的最优化AB2B1B3C1C2C3D1D2E阶段1阶段2阶段3阶段442 53461246379258453【例2】某种机器可以在高、低两种负荷下进行生产。高负荷年产 量8，年完好率0.7；低负荷年产量5，年完好率0.9。现有完好机器 1000台，需制定一个5年计划，以决定每年安排多少台机器投入 高、低负荷生产，使5年的总产量最大。多阶段决策过
2、程的最优化2、生产负荷问题12345S1=1000v1S2S3S4S5v2v3v4v5x1x2x3x4x5【例】某公司有资金10万元，若投资于项目i(i=1,2,3)xi时，收益分 别为g1(x1)=4x1，g2(x2)=9x2，g3(x3)=2x32 ，问应如何分配投资才能 使总收益最大？ 【解】目标函数 约束条件多阶段决策过程的最优化3、投资决策问题多阶段决策过程的最优化多阶段决策过程：可以按时间顺序分解成若干相互联系的阶段，在每一个 阶段都要做出决策，全过程所有阶段的决策形成一个决策序列。每个阶段的决策不仅决定这一阶段的收益，而且决定下一阶段的初 始状态。每个阶段的决策共同组成一个决策序
3、列，称为策略。多阶段决策过程最优化目标：整合活动过程的整体效果最优。多阶段决策问题：求一个策略，整合活动过程的整体效果最优。动态规划的基本概念和原理基本概念 阶段和阶段变量阶段：过程的划分，包括时间、空间的划分阶段变量：描述阶段的变量，用k表示，k=1, 2, , n 状态和状态变量状态：各阶段开始时的客观条件状态无后效性: 给定了某阶段状态，则在这阶段以后过程的发 展不受这阶段以前各阶段状态的影响。AB2B1B3C1C2C3D1D2E阶段1阶段2阶段3阶段4425346 12 46379258453动态规划的基本概念和原理基本概念 状态和状态变量sk： 第k个阶段的状态变量Sk ：第k个阶段
4、状态变量的集合，称状态集合AB2B1B3C1C2C3D1D2E阶段1阶段2阶段3阶段4425346 12 46379258453动态规划的基本概念和原理基本概念 决策和策略决策：决定（选择），一个阶段的状态到下一个阶段状态的选 择决策变量：描述决策的变量，用u表示uk(sk)： 第k阶段当状态为sk时的决策变量Dk(sk) ：第k阶段决策变量的集合，从状态sk出发的允许决策集合AB2B1B3C1C2C3D1D2E阶段1阶段2阶段3阶段4425346 12 46379258453动态规划的基本概念和原理基本概念 决策和策略策略：各阶段决策确定后，整个问题的决策序列就构成一个策 略pk,n(sk
5、) ：第k阶段起至第n阶段止的策略pk,n(sk )=uk (sk), uk+1 (sk+1), , un(sn) Pk,n(sk )：第k阶段起至第n阶段止策略的集合p1,n (s1)：全过程策略p1,n (s1)=u1 (s1), u2(s2), , un(sn) p*1,n (s1)：使目标达到最优的策略，最优策略，AB2B1B3C1C2C3D1D2E阶段1阶段2阶段3阶段4425346 12 46379258453动态规划的基本概念和原理基本概念 状态转移方程任一阶段的状态，由上一阶段状态和上一阶段决策的结果决 定。若给定第k阶段的状态sk，决策为uk(sk) ，则第k+1阶段的状 态
6、sk+1也就完全确定，它们之间的关系可用式（4.1）表示，称状体转移方程。Tk为变化算子（4.1）AB2B1B3C1C2C3D1D2E阶段1阶段2阶段3阶段4425346 12 46379258453动态规划的基本概念和原理基本概念 指标函数指标函数：衡量所选策略优劣的数量指标d(sk, uk) ：阶段指标函数，指第k段，从状态sk出发，采取策略uk的效益原过程：对于一个n段决策过程，从1到n叫做问题的原过程V1,n(s1, p1,n) ：初始状态为s1 ，采取策略p1,n时原过程的指标函数值后部子过程：任意给定k(1 k n)，从第k段到第n段的过程Vk,n(sk, pk,n)：第k 阶段状
7、态sk ,采取策略pk,n时, 后部子过程的指标函数值AB2B1B3C1C2C3D1D2E阶段1阶段2阶段3阶段4425346 12 46379258453基本概念 最优值函数f(sk) ：最优指标函数，从第k段状态sk出发，采取最优策略p*k,n到过程终止时的 最佳效益值。当k=1时，f1(s1)就是从初始状态s1到全过程结束的整体最优函数。动态规划的基本概念和原理AB2B1B3C1C2C3D1D2E阶段1阶段2阶段3阶段4425346 12 46379258453动态规划的基本思想AB2B1C1C3C4D1D2E1时段1时段2时段3时段4C2D3E2F时段5452368775845348
8、435 6 21343【例】选择一条运输线路，使得A到F的运费最小。【解】逆序递推方法动态规划的基本思想 AB2B1C1C3C4D1D2E1时段1时段2时段3时段4C2D3E2F时段5452368775845348 435 6 21343【解】动态规划的基本思想 AB2B1C1C3C4D1D2E1时段1时段2时段3时段4C2D3E2F时段5452368775845348 435 6 21343【解】动态规划的基本思想 AB2B1C1C3C4D1D2E1时段1时段2时段3时段4C2D3E2F时段5452368775845348 435 6 21343【解】按计算顺序反推得最优决策序列最优路线：动
9、态规划的基本思想 AB2B1C1C3C4D1D2E1时段1时段2时段3时段4C2D3E2F时段5452368775845348 435 6 21343可见，求解各阶段都利用了以下关系( 4.2a )( 4.2b )动态规划方法不仅可以得出从A到F的最短线路，而且得到任意中间阶段到F的最短线路。动态规划的基本思想定理：P = (x , x )是最优策略 对任何 k (1 k n )和允许状态s1 ,有P 对于以 s 为起点 的 k,nk推论（Bellman最优性原理）：若 k (1 k n ) ，子策略 P 是最优策略，则对任何1 nk 至 n子过程来说必为最优策略。动态规划的最优化原理一般的动
10、态规划基本方程可表示为动态规划的基本方程( 4.2a )( 4.2b )最优化原理：一个过程的最优策略具有这样的性质，无论初始状态及初始决策如何，对于先前决策所形成的状态而言，以后的决策应构成最优策略。1. 将多阶段决策过程划分阶段，恰当地选取状态变量、决策变量，定义最优 指标函数，把问题化为一族同类型的子问题，然后逐个分解。 2. 求解从边界条件开始，逆（或顺）过程进行，逐段递推寻优。在每一个子 问题求解时，都要使用已求出的子问题最优解，最后一个子问题的最优解 就是整个问题的最优解。 3. 动态规划方法是既把当前一段与未来各段分开，又把当前效益与未来效益 结合的一种最优化方法，因此每段的最有
11、决策选择是从全局考虑的，与该 段的最优选择一般不同。动态规划的基本思想动态规划的基本思想与最优化原理【练习】选择一条运输线路，使得A到F的运费最小。动态规划的基本思想与最优化原理动态规划的基本思想与最优化原理动态规划的基本思想与最优化原理动态规划的基本思想与最优化原理模型建立步骤 确定过程的分段，构造状 态变量； 设置决策变量，写出状态 转移； 列出阶段指标和指标函数 ； 写出基本方程，由此逐段 递推求解。动态规划模型建立关键：识别问题的多阶段特征，将其分 解为可用递推关系联系起来的若干子问题难点：状态变量的选择 可知性：过程演变的各阶段状态变量 的取值，能直接或间接确定 无后效性重点：明确指
12、标函数，得出基本方程（状态转移方程）【例】某公司有资金10万元，若投资于项目i(i=1,2,3)xi时，收益分 别为g1(x1)=4x1，g2(x2)=9x2，g3(x3)=2x32 ，问应如何分配投资才能 使总收益最大？ 【解】目标函数 约束条件动态规划模型建立（1）划分阶段将投资项目排序，依次对项目1、2、3投资，即把上述问题划 分为3个阶段，每个阶段投资一个项目，转化为3阶段决策过程。 （2）状态变量通常把决策变量设为原静态问题中的决策变量，即设状态变量一般为决策变量的累积量或随递推过程变化的 量。把每阶段可供使用的资金定位状态变量sk，初始状态s1=10，u1 为可分配用于第一个项目的
13、最大资金量。动态规划模型建立动态规划模型建立第一阶段 k=1第二阶段 k=2第三阶段 k=3（4）指标函数（5）基本方程（3）状态转移方程动态规划模型求解顺序解法AB2B1C1C3C4D1D2E1时段1时段2时段3时段4C2D3E2F时段5452368775845348 435 6 21343【上例】选择一条运输线路，使得A到F的运费最小。【解】顺序解法 AB2B1C1C3C4D1D2E1时段1时段2时段3时段4C2D3E2F时段5452368775845348 435 6 21343边界条件【解】顺序解法 AB2B1C1C3C4D1D2E1时段1时段2时段3时段4C2D3E2F时段54523
14、68775845348 435 6 21343【解】顺序解法 AB2B1C1C3C4D1D2E1时段1时段2时段3时段4C2D3E2F时段5452368775845348 435 6 21343【解】顺序解法 AB2B1C1C3C4D1D2E1时段1时段2时段3时段4C2D3E2F时段5452368775845348 435 6 21343动态规划解法比较 顺顺序解法逆序解法状态转移方程最优指标函数fk(sk+1) ：从起点到状态sk+1第k段的前部子过程最优效益值。fk(sk) ：从第k段状态sk出发，到终点的后部子过程最优效益值。基本方程动态规划应用生产经营【例】某机器可以在高低两种不同负
15、荷下工作，设机器在高负荷动态规划应用生产经营逆推求解动态规划应用生产经营动态规划应用生产经营最优策略动态规划应用生产经营即前两年完好的机器全部投入低负荷生产 ，后三年完好的机器全部投入高负荷生 产。状态变量动态规划应用资源分配【例】某公司拟将某种高效设备5台，分配给所属甲、乙、丙3厂。各厂获此设备后可产生的效益如下表。问应如何分配，可使所产生的总效益最大？ 效益厂设备台 数甲乙丙0000 1354 27106 391111 4121112 5131112【解】阶段k状态 sk决策uk 表示第k阶段分配的设备台数；状态转移sk+1 = sk- uk ；=1,2,3依次表示把设备分配给甲、乙、丙厂
16、的过 程表示在第k阶段初还剩有的可分台数 ；阶段指标 vk指标函数vk,3 =表示第k阶段分配后产生的效益 ；基本方程动态规划应用资源分配甲乙丙00 00 13 54 27106 391111 4121112 5131112 Skxkvkvk+fk+1fkP 30000+0001144+041 2266+062 331111+0113 441212+0124 551212+0125k动态规划应用资源分配kSkxkvkvk+fk+1fkknP0123452000+000-0 0 10 50+4 5+051-00 1 20 5 100+6 5+4 10+0102-00 1 2 30 5 10 110+11 5+6 10+4 11+0142-10 1 2 3 4 00 5 10 11 11 00+12 5+11 10+6 11+4 11+0 0+12161-3 2-21 2 3 4 55
