最新2019-第六章动态规划-PPT课件

第五章动态规划§1多阶段决策过程及实例§2动态规划的基本概念和基本方程§3动态规划的最优性原理和最优性定理§4动态规划与静态规划的关系§1多阶段决策过程及实例在实际中，有一类问题可以看作是一活动的过程，由于它的特殊性，可将过程分为若干个相互联系阶段，在每个阶段都要依据该阶段所处的状态作出相应的决策，该决策又引起该阶段状态的转移，决定了下一阶段的状态，当每个阶段的决策确定后，由这些决策组成一个决策序列，即整个过程的一条活动路线。这类活动过程称为多阶段决策过程。这类问题称为多阶段决策问题。12n状态状态状态……状态状态决策决策决策例1最短路线问题如下图，是一线路网络，两点之间连线上的数字表示两点之间的距离（或费用）试求一条由A到G的铺管线路，使总距离为最短（或总费用最小）。1状态状态状态状态状态决策决策决策23456状态状态决策决策决策B2C3D2E3F2GB2C3D2E3F2GAV6,6=3AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G531368766835338422133355266432V1,6=24V5,6=9V4,6=11V3,6=14V2,6=21V1,6=24例2机器负荷分配问题某种机器可以在高低两种不同负荷下进行生产。在高负荷下进行生产时，产品的年产量g和投入生产的机器数u的关系为)(ugg。，为到年终时完好的机器数，器数为，即如果年初完好的机这时机器的完好率为10uuaaa在低负荷下进行生产时，产品的年产量h和投入生产的机器数u的关系为)(uhh。，这时机器的完好率为10bb达到最高。在五年内产品的总产量负荷下生产的数量，使在两种不同定如何分配完好的机器划，在每年开始时，决，要制定一个五年计机器数为假定开始生产时完好的1saugg机器的完好率高负荷下：)(buhh机器的完好率低负荷下：)(54321，，，，，为年开始时完好的机器数第isii1状态状态状态状态状态决策决策决策2345状态决策决策u1u2u3u4u5s2s3s4s5s6s1)(1112usbaus)(2223usbaus)(3334usbaus)(4445usbaus)()(5555,5ushugV54321，，，，，机器数为年初分配到高负荷下的第iuii)()(4445,55,4ushugVV)()(3335,45,3ushugVV)()(2225,35,2ushugVV)()(1115,25,1ushugVV1s)(5556usbaus5,4V5,5V5,3V5,2V5,1V设：§2动态规划的基本概念和基本方程2.1动态规划的基本概念1.阶段把过程依据一定的时间和空间特征恰当地划分为若干个相互联系的阶段，以便利用动态规划的方法求解。描述阶段的变量称为阶段变量，用k表示。k=1，2，…，n2.状态每个阶段开始所处的自然状况或客观条件，称为状态。状态是不可控的，是客观存在的。描述状态的变量称为状态变量，用sk表示。状态变量可以是一个数或一个向量。状态变量sk的取值范围称为可达状态集合，用Sk表示。例1中，S3={C1,C2,C3,C4}。状态变量的性质（无后效性）如果某阶段的状态给定后，则该阶段以后的过程的发展不受该阶段以前各阶段状态的影响。即过程的过去历史只能通过当前的状态去影响未来的发展，当前的状态是以往历史的总结，以后发展的依据。这个性质称为无后效性（即马尔科夫性）。无后效性的特征：在每个阶段所作的决策只依据当前的状态，和以往的状态无关。在选取状态变量时，一定要保证状态变量具有无后效性，否则不能利用动态规划的方法求解。3.决策在每个阶段所作的决定或选择称为决策或控制。决策依据与当前状态，又决定下一阶段的状态。描述决策的变量称为决策变量，用uk(sk)表示。他是状态变量sk的函数。决策变量的取值范围称为容许决策集合，用Dk(sk)表示。在例1中D1(A)={B1,B2}D2(B1)={C1,C2,C3}，D2(B2)={C2,C3,C4}D4(D1)={E2,E3}在例2中D1(s1)={u1(s1)|0≤{u1(s1)≤s1}D2(s2)={u2(s2)|0≤{u2(s2)≤s2}Dk(sk)={uk(sk)|0≤{uk(sk)≤sk}4.策略按一定顺序排列的决策序列集合称为策略。由过程的第k阶段开始到终止状态为止的过程，称为问题的后部子过程（或称为k子过程）。由k子过程的每个阶段的决策函数组成的决策函数序列集合{uk(sk),uk+1(sk+1),…,un(sn)}称为k子过程策略，简称为子策略，记为pk,n(sk)，即pk,n(sk)={uk(sk),uk+1(sk+1),…,un(sn)}当k=1时,此决策函数序列称为全过程的一个策略，简称为策略，记为p1,n(s1)。即p1,n(sk)={u1(s1),u2(s2),…,un(sn)}策略的取值范围称为容许策略集合，用P表示。在P中,使指标函数达到最优的策略称为最优策略。例1中，每一条线路就是一个策略，容许策略集合中有48个策略。A到G的最短线路就是最优策略。5.状态转移方程若给定第k个阶段状态变量sk的值，该阶段的决策变量uk的值一经确定，第k+1个阶段的状态变量sk+1的值也就完全确定了，即sk+1是sk和uk的函数，记为sk+1=Tk(sk,uk)该函数描述由第k个阶段到第k+1个阶段的状态转移规律,称为状态转移方程。)(1kkkkusbaus例1中，状态转移方程为例2中，状态转移方程为kkus16.指标函数和最优值函数用来衡量过程和子过程（策略和子策略）优劣的一种数量指标，称为指标函数。它是定义在全过程和后部子过程上的数量函数，用Vk,n表示。即nkspVssusVVknknknkkknknk,,2,1)]([),,,,(,,11,,指标函数的性质：动态规划中的指标函数应具有可分离性，并满足地推关系，的函数。，，可表示为即nkkknkVusV,1,)],,,,,,[),,,,211,11,nkkknkkknkkknkssusVusssusV（（即常见指标函数的形式（1）过程和子过程的指标函数可分解为它所包含的阶段的指标的和，即),(),,,,1,njjjnkkknkusvssusV（阶段的阶段指标。是第其中j),(jjusv),,,,),(),,,,211,11,nkkknkkknkkknkssusVusvssusV（（（2）过程和子过程的指标函数可分解为它所包含的阶段的指标的积，即njjjnkkknkusvssusV),(),,,,1,（),,,,),(),,,,211,11,nkkknkkknkkknkssusVusvssusV（（指标函数的最优值称为最优值函数，记为)kksf（),,,,)(1,},,{1nkkknkuuukkssusVsfoptnkk（它表示最优的k子策略p*k,n(sk)对应的指标函数值。9)(5)(7)(3)(4)(13525152616EfEfEfFfFf中，在例年的总产量的最高值。年到第从第时，年初完好的机器数为表示第中，在例5)(2ksksfkkk2.1动态规划的基本思想和基本方程最短路线的特征：如果由起点A经过P和H到达G是一条由A到G的最短路线，则由P到G的最短路线是P→H→G即最短路线的子线路是最短路线。根据最短路线的特征，求A到G的最短路线，可以采用由后向前逐步递推的方法，从最后一个阶段开始，求出每个点到G的最短路线，最后出A到G的最短路线。P1→H1→GP2→H2→GA1215831818315812min)(1Af12)(12Pf15)(22PfAB1B2C1C2C3C4D1D2D3E1E2E3F1F2G5313687668353384221333552664323)(4)(62616FfFfk时，)(5)(3min)(5261615FfFfEfk时，)(2)(5min)(261625FfFfEf)(6)(6min)(261635FfFfEf115)(FEuGFuFu)()(2616225)(FEu235)(FEu73543min53245min93646min437590)(2)(2min)(4251514EfEfDfk时，)(2)(1min)(352524EfEfDf)(3)(3min)(352534EfEfDf214)(EDu224)(EDu234)(EDu75272min69251min89353minAB1B2C1C2C3C4D1D2D3E1E2E3F1F2G531368766835338422133355266432437597680)(8)(6min)(3241413DfDfCfk时，)(5)(3min)(241423DfDfCf)(3)(3min)(342433DfDfCf113)(DCu123)(DCu233)(DCu136876min106573min98363minAB1B2C1C2C3C4D1D2D3E1E2E3F1F2G53136876683533842213335526643243759768)(4)(8min)(342443DfDfCf343)(DCu128468min13109120)(6)(3)(1min)(233231312CfCfCfBfk时，212)(CBuAB1B2C1C2C3C4D1D2D3E1E2E3F1F2G5313687668353384221333552664324375976813109121396)103131min)(6)(7)(8min)(43332322CfCfCfBf322)(CBu1612697108min13160)(3)(5min)(122121BfBfAfk时，11)(BAuAB1B2C1C2C3C4D1D2D3E1E2E3F1F2G531368766835338422133355266432437597681310912131618163135min1811)(BAu212)(CBu123)(DCu214)(EDu225)(FEuGFu)(26A→B1→C2→D1→E2→F2→G最短路线为：最优策略为：P*=0该题中，在求解过程中，利用了第k阶段与第k+1阶段之间的递推关系：)(),()(11)(minkkkkkSDukksfusvsfkKk0)(77sf1,2,3,4,5,6k一般情况，第k阶段与第k+1阶段之间的递推关系式可表示为：)(),()(11)(kkkkkSDukksfusvsfoptkKk0)(11nnsf121，，，，nnk该递推关系式称为动态规划的基本方程。边界条件),,,,)(1,},,{1nkkknkuuukkssusVsfoptnkk（)},,,,),({211,1},,{1nkkknkkkuuussusVusvoptnkk（)},,,,),({211,1},,{1nkkknkuukkussusVusvoptoptnkk（)}(),({11kkkkusfusvoptk0)(11