第10章-动态规划课件

第十章第十章 动态规划动态规划Dynamic Programming 1 动态规划的基本概念和方法2 动态规划的基本原理3 动态规划的应用举例运筹学运筹学Operations Research重点掌握重点掌握:1.动态规划的基本概念 2.动态规划的应用举例10.1 动态规划的基本概念和方法动态规划的基本概念和方法v2v3v4v7v5v9v6v8v1028512131071013112865885405847【例例10.1-1】最短路径问题最短路径问题 图图101表示从起点表示从起点v1到到终点终点v10之间各点的距离。求之间各点的距离。求v1到到v10的最短路径。的最短路径。图图101v1第1阶段第2阶段第3阶段第4阶段阶段：1217142019Min2+5,8+8,6+4=7逆逆标标法法第第10章章 动态规划动态规划Dynamic Programming Page 4 12 七月 2024动态规划问题具有以下动态规划问题具有以下基本特征基本特征 1.问问题题具具有有多多阶阶段段决决策策的的特特征征。阶阶段段可可以以按按时时间间划分，也可以按空间划分。划分，也可以按空间划分。2.每一阶段都有相应的每一阶段都有相应的“状态状态”与之对应。与之对应。3.每每一一阶阶段段都都面面临临一一个个决决策策，选选择择不不同同的的决决策策将将会会导导致致下下一一阶阶段段不不同同的的状状态态，同同时时，不不同同的的决决策策将将会会导致这一阶段不同的目标函数值。导致这一阶段不同的目标函数值。4.每每一一阶阶段段的的最最优优解解问问题题可可以以递递归归地地归归结结为为下下一一阶阶段段各各个个可可能能状状态态的的最最优优解解问问题题，各各子子问问题题与与原原问问题题具具有有完完全全相相同同的的结结构构。能能否否构构造造这这样样的的递递推推归归结结，是是解解决决动动态态规规划划问问题题的的关关键键。这这种种递递推推归归结结的的过过程程，称称为为“不变嵌入不变嵌入”。第第10章章 动态规划动态规划Dynamic Programming Page 5 12 七月 2024动态规划是解决多阶段决策过程最优化问题多阶段决策过程最优化问题的一种方法。是现代企业管理中的一种重要决策方法。用于解决最优路径问题、资源分配问题、生产计划与库存问题、投资问题、排序问题及生产过程的最优控制等问题。在处理某些优化问题时，常比线性规划或非线性规划方法更有效。第第10章章 动态规划动态规划Dynamic Programming Page 6 12 七月 20241.1 多阶段决策过程的最优化多阶段决策过程的最优化多阶段决策过程：多阶段决策过程：指这样一类特殊的活动过程，它们可以按时间顺序分解成若干相互联系的阶段，在每一阶段都要做出决策，全部过程的决策是一个决策序列。多阶段决策过程最优化的目标，是要达到整个整个活动过程的总体效果最优活动过程的总体效果最优，所以多阶段的决策并不是各阶段决策的简单总合。第第10章章 动态规划动态规划Dynamic Programming Page 7 12 七月 2024 由于各阶段决策间有机地联系着，本段决策的执行将影响到下一阶段的决策，以至于影响总体效果，所以决策者在每阶段决策时不应仅考虑本阶段最优，还应考虑对最终目标的影响，从而做出对全局来讲是最优的决策。动态规划就是符合这种要求的一种决策方法。动态规划方法与“时间时间”关系密切，随着时间过程的发展而决定各阶段的决策，产生一个决策序列，这就是“动态”的意思。对于静态问题，只要在问题中人为地引入“时间”因素，将问题看成多阶段的决策过程即可。第第10章章 动态规划动态规划Dynamic Programming Page 8 12 七月 2024例：生产与存贮问题 某工厂每月需供应市场一定数量的产品。供应需求所余产品应存入仓库，一般地，某月适当增加产量可降低生产成本，但超产部分存入仓库会增加库存费用，要确定一个逐月的生产计划，在满足需求条件下，使一年的生产与存贮费用之和最小。把每月作为一个阶段，全年分为12个阶段逐次决策。第第10章章 动态规划动态规划Dynamic Programming Page 9 12 七月 2024例：投资决策问题 某公司现有资金万元，在今后5年内考虑给、四个项目投资，这些项目的投资期限、回报率均不相同，问应如何确定这些项目每年的投资额，使到第5年末拥用资金的本利总额最大。看作5阶段决策问题。第第10章章 动态规划动态规划Dynamic Programming Page 10 12 七月 2024例：设备更新问题 企业在使用设备时都要考虑设备的更新问题，因为设备越陈旧所需的维修费用越多，但购买新设备则要一次性支出较大的费用。现在某企业要决策一台设备未来8年的更新计划，已预测了第j年购买设备的价格为kj，rj为设备经过j年后的残值，cj为设备连续使用j-1年后在第j年的维修费（j=18)，问应在哪年更新设备可使总费用最小。这是一个8阶段决策问题。第第10章章 动态规划动态规划Dynamic Programming Page 11 12 七月 20241.2动态规划的基本概念动态规划的基本概念(1)阶段(2)状态(3)决策和策略(4)状态转移(5)指标函数第第10章章 动态规划动态规划Dynamic Programming Page 12 12 七月 202495例例10.1-2、最短线路问题、最短线路问题 (状态状态)(决策决策)(方程方程)(目标目标)(思想思想)设某厂要把一批货运到城市出售，中部可经过城市，各城市间的交通线及距离如下图，问应选择什么路线，可使总距离最短？A12345678E864543356213987876阶段无后效性策略原理原理第第10章章 动态规划动态规划Dynamic Programming Page 13 12 七月 2024例例10.1-3：生产与存贮问题生产与存贮问题：某工厂生产并销售某种产品，已知今后4个月市场需求预测如下表，每月生产j单位产品费用为：c(j)=3+j 千元 (j=16)。每月库存j单位产品的费用为E(j)=0.5j(千元)。该厂最大库存容量为3个单位，每日最大生产能力为6个单位，计划开始和计划期末库存量都是零。试制定4个月的生产计划，在满足用户需求条件下总费用最小。假设第i+1个月的库存量是第i 个月可销量与该月用户需求量之差。而第i 个月的可销售量是本月初库存量和产量之和。(状态)(决策)(方程)(目标)i(月)1234gi(需求)2324阶段第第10章章 动态规划动态规划Dynamic Programming Page 14 12 七月 2024(1)阶段阶段(Stage)把问题的过程，按时间或空间特征分解成若干互相联系的阶段，以便按次序去求每阶段的解，常用k表示阶段变量。在例10.1-2和例10.1-3中，可知问题属于多阶段决策。例10.1-2，可把从到看成一个4阶段问题。例10.1-3，把每个月作为一个阶段，共分为4个阶段。第第10章章 动态规划动态规划Dynamic Programming Page 15 12 七月 2024(2)状态状态(State)各阶段开始时的自然状况或客观条件，叫状态状态。描述各阶段状态的变量为状态变量状态变量。常用sk表示第k阶段的状态变量，状态变量sk的取值集合用状态集合Sk表示。例10.1-2，第一阶段的状态为，第二阶段有三个状态，城市、。状态变量s2的集合S2=、,S3=、例10.1-3，把每月月初的产品库存量作为状态第第10章章 动态规划动态规划Dynamic Programming Page 16 12 七月 2024动态规划的状态具有如下性质：动态规划的状态具有如下性质：当某阶段状态给定以后，在这阶段以后过程的过去历史不受这段以前各段状态的影响不受这段以前各段状态的影响。即过程的过去历史只能通过当前状态去影响它未来的发展，称为无后效性无后效性。如果所选的变量不具备无后效性，就不能作为状态变量来构造动态规划模型。如例10.1-2中，当某段的初始状态所在的城市选定后，从这个城市以后的运货路线只与这个城市有关，不受以前的运货路线影响，有无后效性。第第10章章 动态规划动态规划Dynamic Programming Page 17 12 七月 2024(3)决策和策略决策和策略(Decision and Policy)当各阶段的状态取定后，就可以作出不同的决定（或选择），从而确定下一阶段的状态，这种决定称为决策决策。表示决策的变量称为决策变量决策变量，用uk(sk)表示第k个阶段当状态为sk时的决策变量。决策变量的取值范围称为允许决策集合允许决策集合，用Dk(sk)表示第k阶段从状态sk出发的允许决策集合。uk(sk)Dk(sk)第第10章章 动态规划动态规划Dynamic Programming Page 18 12 七月 2024例10.1-2，第二阶段的状态集合S2=、。从城市出发，可选择走城市、，即其允许决策集合D2()=、.如决策选择城市，则此时决策变量表示为：u2()=见例10.1-2例10.1-3，决策变量是各月的产品产量。见例10.1-3 第第10章章 动态规划动态规划Dynamic Programming Page 19 12 七月 2024各阶段决策确定后，整个问题的决策序列就构成一个策略。策略。用P1,n(u1,u2,un)表示。例10.1-2对每个实际问题，可供选择的策略有一定范围，称为允许策略集合允许策略集合，用P表示。使整个问题达到最优效果的策略称为最优策略最优策略。第第10章章 动态规划动态规划Dynamic Programming Page 20 12 七月 2024(4)状态转移状态转移方程方程 动态规划中本阶段的状态往往是上一阶段的决策结果。如果给定了第k阶段的状态sk，本阶段决策为uk(sk)，则第k+1阶段的状态为sk+1也就确定，关系如下：sk+1=Tk(sk,uk)由于它表示了k阶段到k1阶段的状态转移规律，故称为状态转移方程状态转移方程。例10.1-2：sk+1=uk(sk)如 u2()=(见例10.1-2)例10.1-3：第k+1阶段的库存量等于第k阶段库存量及产量的和，再减去当月的需求量，即：sk+1=(sk+uk)gk 见例10.1-3第第10章章 动态规划动态规划Dynamic Programming Page 21 12 七月 2024(5)指标函数指标函数 用于衡量所选定策略优劣的数量指标称为指指标函数标函数。一个n阶段决策过程，从第1阶段到第n阶段，叫问题的原过程原过程。对于任意一个给定的k(1kn)，从第k段到第n段的过程，称为原过程的一个后部子过程后部子过程。n1k.第第10章章 动态规划动态规划Dynamic Programming Page 22 12 七月 2024V1,n(s1,P1,n)表示初始状态为s1采用策略P1,n时原过程的效益值。Vk,n(sk,Pk,n)表示初始状态为sk采用策略Pk,n时后部子过程的效益值。第第10章章 动态规划动态规划Dynamic Programming Page 23 12 七月 2024最优指标函数记为fk(sk)，表示从第k阶段状态为sk，采用最优策略p*k,n到过程终止时的最佳效益值。fk(sk)=Vk,n(sk,P*k,n)=Opt Vk,n(sk,Pk,n)当k=1时，f1(s1)就是从初始状态s1到全过程结束的整体最优函数。最优第第10章章 动态规划动态规划Dynamic Programming Page 24 12 七月 2024例10.1-2，指标函数是距离。如第二阶段，状态为城市时，V2,4()表示从城市到城市的距离。见例10.1-2 而f2()表示从城市到城市的最短距离。本问题的总目标本问题的总目标f1(A)，即从城市到终点城市的最短距离。例10.1-3，衡量决策效果的指标函数是生产与存贮的费用，最优指标函数是指生产与存贮费用之和最低。本问题的总目标是求本问题的总目标是求f1(0)，即初始库存量为0时，第14月的最低总费用。见例10.1-3第第10章章 动态规划动态规划Dynamic Programming Page 25 12 七月 20241.3 动态规划的基本思想动态规划的基本思想结合例10.1-2最短路线问题介绍动态规划的基本思想。例10.1-2分为四个阶段，从第一阶段状态A开始，到第二阶段的城市、有三种选择。从第二阶段的某个状态出发，又有、三种选择，这样得出一个决策序列，即一个策略。即从到的一条路线。可用比较法把从到的所有路线的路长求出，加以比较。第第10章章 动态规划动态规划Dynamic Programming Page 26 12 七月 202495例例10.1-2、最短线路问题、最短线路问题 设某厂要把一批货运到城市出售，中部可经过城市，各城市间的交通线及距离如下图，问应选择什么路线，可使总距离最短？A12345678E864543356213987876第第10章章 动态规划动态规划Dynamic Programming Page 27 12 七月 2024用动态规划求解用动态规划求解：从过程的最后一个阶段开始，用逆序递推方法求解，逐步求出各段各点到终点的最短路线，最后求得到点的最短路线。用动态规划基本思想解例10.1-2。nn-11第第10章章 动态规划动态规划Dynamic Programming Page 28 12 七月 2024v2v3v4v7v5v9v6v8v1028512131071013112865885405847图图101v1第1阶段第2阶段第3阶段第4阶段阶段：1217142019Min2+5,8+8,6+4=7用用逆序法逆序法列表求解例列表求解例10.1-1 第第10章章 动态规划动态规划Dynamic Programming Page 29 12 七月 2024用逆序法列表求解例用逆序法列表求解例10.1-1 k=n=5 时，时，f5(v10)0 k=4，递推方程为，递推方程为 s4D4(s4)s5v4(s4,x4)v4(s4,x4)+f5(s5)f4(s4)最优决策最优决策x4*v7v7v10v1055+0=5*5v7 v10v8v8v10v1088+08*8v8 v10v9v9v10v1044+0=4*4v9 v10第第10章章 动态规划动态规划Dynamic Programming Page 30 12 七月 2024k=3，递推方程为，递推方程为表10-2 s3D3(s3)s4v3(s3,x3)v3(s3,x3)+f4(s4)f3(s3)最优决策最优决策x3*v5v5v7 7v v5 5v8 8v v5 5v9 9v7v8v92862+5=7*8+8=166+4=107v5v7 7v6v6 v7 7v v6 6v8 8v v6 6v9 9v7v8v9125812+5=175+8=138+4=12*12v6v9 910.1 动态规划的基本概念动态规划的基本概念第第10章章 动态规划动态规划Dynamic Programming Page 31 12 七月 2024v2v3v4v7v5v9v6v8v1028512131071013112865885405847图图101v1第1阶段第2阶段第3阶段第4阶段阶段：1217142019用用逆序法逆序法列表求解例列表求解例10.1-1 f4(s4)第第10章章 动态规划动态规划Dynamic Programming Page 32 12 七月 2024k=2，递推方程为，递推方程为表表10-3 s2D2(s2)s3v2(s2,x2)v2(s2,x2)+f3(s3)f2(s2)最优决策最优决策x2*v2v2 v5 5v v2 2 v6 6v5v6101310+7=17*13+12=2517v2 v5 5v3v3 v5 5v v3 3 v6 6v5v67107+7=14*10+12=2214v3v5 5v4v4 v5 5v v4 4 v6 6v5v6131113+7=20*11+12=2320v4v5 5第第10章章 动态规划动态规划Dynamic Programming Page 33 12 七月 2024k=1，递推方程为，递推方程为表10-4 s1D1(s1)s2v1(s1,x1)v1(s1,x1)+f2(s2)f1(s1)最优决策最优决策x1*v1v1v2 2v v1 1v3 3v v1 1v4 4v2v3v42852+17=19*8+14=225+20=2519v1v2 2最优值是表最优值是表10-4中中f1(s1)的值，从的值，从v1到到v10的最短路长为的最短路长为19。最短。最短路线从表路线从表10-4到表到表10-1回朔，查看最后一列最优决策，得到最回朔，查看最后一列最优决策，得到最短路径为：短路径为：v1 v2 v5 v7 v10第第10章章 动态规划动态规划Dynamic Programming Page 34 12 七月 2024作业：教材作业：教材P225 第第1题题下一节：基本原理下一节：基本原理 第第10章章 动态规划动态规划Dynamic Programming Page 35 12 七月 202410.2 动态规划的基本原理动态规划的基本原理第第10章章 动态规划动态规划Dynamic Programming Page 36 12 七月 2024一、最优化原理一、最优化原理 一个过程的最优策略具有这样的性质：即无论初始状态及初始决策如何，对于先前决策所形成的状态而言，其以后的所有决策必构成最优策略。即：最优策略的任一后部子策略总是最优的最优策略的任一后部子策略总是最优的。第第10章章 动态规划动态规划Dynamic Programming Page 37 12 七月 2024例10.1-2正是据这一原理求解的，从图中可看出，无论从哪一段的某状态出发到终点的最短路线，只与此状态有关，而与这点以前的状态、路线无关，即不受从点是如何到达这点的决策影响。而且从点到点的最短路线若经过sk点，则此路线由sk到点的后半部，必是由sk点到的最短路线。此特性用反证法易证。sk第第10章章 动态规划动态规划Dynamic Programming Page 38 12 七月 2024二、动态规划基本方程的基本要素二、动态规划基本方程的基本要素将问题的过程划分为恰当的阶段；正确选择状态变量sk，使它既能描述过程的演变，又要满足无后效性。确定决策变量uk及每阶段的允许决策集合Dk(sk)正确写出状态转移方程；根据题意明确指标函数Vk,n，最优指标函数fk(sk)及一段效益即阶段指标dk(sk,uk)的含义。正确列出最优指标函数的递推关系及边界条件，即基本方程。10.3 动态规划应用动态规划应用一、资源分配问题一、资源分配问题二、系统可靠性问题二、系统可靠性问题第第10章章 动态规划动态规划Dynamic Programming Page 40 12 七月 2024一.资源分配问题第第10章章 动态规划动态规划Dynamic Programming Page 41 12 七月 2024【例例10.3-1】公公司司有有资资金金8万万元元，投投资资A、B、C三三个个项项目目，一一个个单单位位投投资资为为2万万元元。每每个个项项目目的的投投资资效效益益率率与与投投入入该该项项目目的的资资金金有有关关。三三个个项项目目A、B、C的的投投资资效效益益(万万元元)和和投投入入资资金金（万万元元）的的关关系系见见表表10-5。求求对对三三个项目的最优投资分配，使总投资效益最大。个项目的最优投资分配，使总投资效益最大。项目项目投入资金投入资金ABC2万元万元89104万元万元1520286万元万元3035358万元万元384043表表10-5K=3第第10章章 动态规划动态规划Dynamic Programming Page 42 12 七月 2024【解解】设设xk为第为第k个项目的投资，该问题的静态个项目的投资，该问题的静态规划模型为规划模型为第第10章章 动态规划动态规划Dynamic Programming Page 43 12 七月 20241.阶段阶段k：每投资一个项目作为一个阶段，共：每投资一个项目作为一个阶段，共3个个阶段。阶段。k=1,2,3。2.状态变量状态变量sk：投资第：投资第k个项目个项目前前的资金数的资金数3.决策变量决策变量xk：第：第k个项目的投资额个项目的投资额决策允许集合：决策允许集合：0 xksk4.状态转移方程：状态转移方程：sk+1=skxk5.阶段指标：阶段指标：vk(sk，xk)见表见表10-5中的数据中的数据 递推方程：递推方程：第第10章章 动态规划动态规划Dynamic Programming Page 44 12 七月 2024终端条件：终端条件：f4(s4)=0数学模型为数学模型为 第第10章章 动态规划动态规划Dynamic Programming Page 45 12 七月 2024第第3阶段，阶段，s3取值为取值为0、2、4、6、8(分配给分配给C的金额的金额)0246800 002010 102401028 2846010 2835-3568010 2835 43 438K=1题题第第10章章 动态规划动态规划Dynamic Programming Page 46 12 七月 2024 第二阶段：第二阶段：当把资金分配给项目B和C时，则对每个值，有一种最优分配方案，使最大盈利即最优2子过程最优指标函数值为 第第10章章 动态规划动态规划Dynamic Programming Page 47 12 七月 2024因为上式也可写成其数值计算如表所示。024680 002 9+0 1004 91020+0 2806035 20+10350 37280439+3535+10 400 48410.3 动态规划应用动态规划应用说明说明:s2分配给分配给B,C,其中其中x2是分配给是分配给B的的,s3=s2-x2是分配给是分配给C的的k=3表的值表的值第第10章章 动态规划动态规划Dynamic Programming Page 48 12 七月 2024第一阶段：第一阶段：把资金分配给项目A、B、C时，最大盈利为其中可取值0,2,4,6,8.数值计算见表 然后按计算表格的顺序推算，可知最优分配方案：由于，根据，查表k=2可知，再由 ，求得。即分配给不分给项目A，分配给B项目4万元资金，分配给C项目4万元，最优值为48万元。024688 837 15+28 30+10 38+0 48 0k=3第第10章章 动态规划动态规划Dynamic Programming Page 49 12 七月 2024二、系统可靠性问题二、系统可靠性问题第第10章章 动态规划动态规划Dynamic Programming Page 50 12 七月 2024例例10.3-2.某科研项目组由三个小组用不同的手段分别研究，它们失败的概率各为0.40，0.60，0.80。为了减少三个小组都失败的可能性，现决定给三个小组中增派两名高级科学家，到各小组后，各小组科研项目失败概率如下表：问如何分派科学家才能使三个小组都失败的概率（即科研项目最终失败的概率）最小？高级科学家小组12300.400.600.8010.200.400.5020.150.200.3010.3 动态规划应用动态规划应用第第10章章 动态规划动态规划Dynamic Programming Page 51 12 七月 2024解：用逆序算法。设阶段：对第k个小组分派科学家看作决策的过程的第k个阶段，k=1,2,3。状态变量uk：表示给第k个小组至第3个小组分派科学家的人数。决策变量xk：对第k个小组分派的科学家人数，相应的失败概率为Pk(xk)；状态转移方程：递推关系：第第10章章 动态规划动态规划Dynamic Programming Page 52 12 七月 2024计算当k=3时，当k=2时，s3 f3*(s3)x3*008001050120302 x2s2f2(s2,x2)=P2(x2)f3*(s2-x2)f2*(s2)x2*012004804801030032030020180200160162第第10章章 动态规划动态规划Dynamic Programming Page 53 12 七月 2024当k=1时，最优解为 x1*=1，x2*=0，x3*=1；科研项目最终失败的概率为0.060。x1s1f1(s1,x1)=P1(x1)f2*(s1-x1)f2*(s2)x2*01220064 0060 0072 0060 1第第10章章 动态规划动态规划Dynamic Programming Page 54 12 七月 2024作业：教材作业：教材P226 第第2The End of Chapter 10