运筹学-动态规划.

第16章动态规划动态规划是运筹学的一个分支,它是解决多阶段决策过程最优化的一种数学方法。该方法由美国数学家贝尔曼（R.E.Bellman）等人在20世纪50年代初提出的§1多阶段决策问题多阶段决策问题例子：例16-1最短路径问题：求图16-1中从A到F的最短路径。将问题可分为五个阶段每个阶段都要作出一个决策，决定向哪个点前进一步。各阶段的决策有机的联系着，本阶段的决策影响着下一阶段的决策，以至于影响整体效果，决策者在做决策时，不应尽考虑本阶段最优，还应考虑对最终目标的影响。各阶段的决策形成一个决策序列，通常称之为一个策略，不同的策略，其效果也不同。现在的问题就是要在允许的策略中，求出A到F的距离最短的策略。第一阶段：从到A或B;第二阶段：从B到C;第三阶段：从C到D;第四阶段：从D到E;第五阶段：从E到F;例16-2机器负荷分配问题：某种机器能在高低两种不同的负荷下工作，在高负荷下有台机器进行生产时，产品的产量，工作一年后完好的机器数为，在低负荷下有台机器进行生产时，产品的产量，工作一年后完好的机器数为。试制订一个五年计划，决定在每年年初如何分配完好的机器在两种不同负荷下生产的数量，才能使在五年内产品的产量为最高？uus8u7.0vvs5v9.0可将该问题按年划分为五个阶段：第一阶段即第一年；第二阶段即第二年；第三阶段即第三年；第四阶段即第四年；第五阶段即第五年。设开始时完好机器数量为x1，第k年能投入生产的机器数为xk，第k年高负荷下工作的机器数为uk台，效益为Rk，则kkkkkkkkkkxuuxuRuxxx0,)(58),(9.07.01原问题就是确定uk，k=1,2,3,4,5,使最大。51kkR例16-3部件的生产计划问题：某车间每月底要为下一个月提供出一定数量的部件给组装车间，各月份中生产这种部件所需工时不同，生产出来多余的部件可以存入库中，但库房的最高贮量为H=9，求某6个月中每月生产多少部件，才能使消耗的总工时最少？最小工时是多少？各月的需求量与单位工时如下表：表7-1kkakd月份123456需求量853274单位工时111813172010kak将该问题按月份划分为六个阶段，Sk为第k月开始时的库存，uk为第k的生产量。设为当第月开始时库为直至第6月止，生产部件累计工时的最小值，则。即为要求的最小工时。)(kksfkks）（)(min)(11kkkkukksfuasfk)(11sf图7-2Kkkkkduss1kskdku例16-4原料分配问题：利用已有的12吨原料制造A、B两种产品，已知每制造一吨A产品需要原料4吨，每制造一吨B产品需要原料2吨，而两种产品在市场上的价格分别为每吨8千元和1万元，求如何安排生产计划能使总效益最大？可将分配A、B两产品的产量看作两个阶段：第一阶段：确定生产A产品多少吨；第二阶段：确定生产B产品多少吨。求出使总效益最大的决策序列。例16-5人员派谴问题：向三个售货区域派谴四名推销员，各区人数及效益如下表：人数区域增加效益数01234123000161610251714302116322217该问题可按区域分为三个阶段：第一阶段：确定向1区派几名推销员；第二阶段：确定向2区派几名推销员；第三阶段：确定向3区派几名推销员。求出使总效益最大的策略。问如何派谴人员能使总效益最高？例16-6货物装载问题：某海轮的总装载能力为w千吨（不妨设w=0,1,2,…,18千吨）需装载四种货物，规定海轮上每种货物不超过2件，各种货物的单位重量，单位运费如下表，问怎样装这些货物，才能使总运费最大？表8-6货物种类单位重量每件运费123451349147将该问题按四种货物分为四个阶段，第k阶段确定第k种货物的装运件数。设为第种货物的运费。求出使最大的装运策略。kRk41kkR1．阶段（Stage）将问题恰当地划分成若干相互联系的阶段，通常用作为阶段变量。可按时间顺序或空间特征划分阶段。k2．状态变量（StateVariable）描述过程状态的变量，可以用一个数，一组数或一个向量来描述，常用表示第阶段的状态变量。不可控变量。kks§2动态规划的基本概念与基本原理2.1动态规划的基本概念最短路问题中，每个阶段状态表示该阶段初始点的集合。状态集合用Sk表示，S1={B1，B2}3.决策变量（DecisionVariable）某阶段状态给定以后，由该状态演变到下一阶段某状态的选择称为决策，决策变量是描述决策的变量，常用)(kksu或)(kksd表示，它是第k阶段状态处于ks时的决策变量。决策变量的取值往往在一定的范围之内，用)(kksD表示允许决策集合，则有)()(kkkksDsu。例如，例8-2中的},,2,1,0{)(111ssD。若由第k阶段的状态变量ks和决策变量ku可确定出第1k阶段的状态变量1ks，则称此规律为状态转移方程，一般形式为),(1kkkkusTs。例如，例8-2中的状态转移方程为)(9.07.01kkkkusus4.策略（Policy）由过程的第一阶段开始到最后一阶段为止称为问题的全过程，由各阶段的决策)(kksu(i=1,2,…,n)构成的策略序列称为全过程策略（简称策略）记为nP,1，即)(,),(),()(22111,1nnnsusususP由第k阶段开始到最后一阶段为止的过程，称为k子过程，其策略称为k子过程策略（简称子策略）记为)(,),()(,nnkkknksususP在实际问题中，可供选择的策略有一定的范围，称之为允许策略集合，从中找出的效果最佳的策略称为最优策略。指标函数应具有可分离性，一般的形式有：,,,(,)knknkknVVsp,,,,()()(,)knknkkkknkknpPsfsoptVsp5.指标函数（ReturnFunction）指标函数（最大收益函数-MaximumReturnFunction，或最小成本函数-MinimumCostFunction）是反映策略优劣的一种数量指标，它是一个定义在全过程和所有后部子过程上的函数。),(,11,1nnpsV记-表示初始状态为s1采取策略p1,n时全过程的指标函数-第k阶段状态为sk采取策略pk,n时后部子过程的指标函数动态规划的方法就是在允许策略中寻求最优策略。指标函数的最优值，记为)(kksf,,(1)(,),(2)(,)nnknjjjknjjjjkjkVvsuVvsu6.最优策略和最优轨线称为后部子过程中的最优策略。使指标函数达到最优的策略1,1,11,(,)nnnVVsp*1,np称为全过程中的最优策略。得出的状态序列和状态转移方程按最优策略),(***1*,1kkknusTsp***121,,...,}nsss{称为最优轨线。*,,,),(nknkknkppsV达到最优值的策略使指标函数现在结合解决最短路线问题来介绍动态规划方法的基本思想，最短路线有一个重要特性：APHG如果由起点A经过P点和H点而到达终点G是一条最短路线，则由点P出发经过H点到达终点G的这条子路线，对于从点P出发到达终点的所有可能选择的不同路线来说，必定也是最短路线。16.2动态规划的基本定理和基本方程•贝尔曼（R.E.Bellman）最优性原理如下：•作为整个过程的最优策略具有这样的性质：•即无论过去的状态和决策如何，对于先前决策所形成的状态而言，其后的所有决策应构成最优策略。一般地：人们逐步认识到：对于不同类型问题所建立的严格定义的动态规划模型,必须对相应的最优性原理给以必要的验证。即是说，最优性原理不是对任何决策过程都普遍成立的。而且，“最优性原理”与动态规划基本方程并不是无条件等价的，两者之间也不存在确定的蕴含关系。反映动态规划基本方程的是最优性定理，它是策略最优性的充要条件。最优性原理仅仅是策略最优性的必要条件，它是最优性定理的推论。动态规划的基本方程或者最优性定理作为动态规划的理论基础。动态规划的最优性定理：设阶段数为n的多阶段决策过程，其阶段编号为k=1,…,n,初始状态为s1,允许策略是最优策略的充要条件是对任一个k,1＜k＜n和,s1∈S1有),...,,(**2*1*,1nnuuuP),~(),(),(,,)~(1,111,1)(*,11,1,,11,11,1nkknksPpkksPpnnpsVoptpsVoptpsVknknkkk当V是效益函数时，opt取max；当V是损失函数时，opt取min。其中),(~),,(111,1,1,1kkkknkknusTsppp11,1kksspk是由给定初始状态和子策略确定的第阶段状态。)~(~,knkksPs策略集合，记为为起始点有一个允许子以由上述最优性定理得到推论:确定的）和是由阶段状态注意：来说，必是最优策略（的子过程到为起点的对于以子策略它的的是最优策略，则对任意若允许策略*1,11**1*11*,*,1),(,1,kkkkkknknpssknkusTspnkkp此推论就是前面所说R.Bellman等人于20世纪50年代提出的的动态规划的“最优性原理”。它仅仅是最优策略的必要条件。即一个最优策略的子策略总是最优的。定理16.2.2),~(),(),(,,)~(1,111,1)(*,11,1,,11,11,1nkknksPpkksPpnnpsVoptpsVoptpsVknknkkk由最优性定理我们有),(),(),()(,11,1,)(*,,,.nkknkkkksPpnkknkkkpsVusVoptpsVsfknknk),(),(,11,1)(,)(1,1,1nkknksPpkkksuupsVoptusVoptknknkkkk)(),(11,)(kkkkksuusfusVoptkkk16.2.2基本方程：得到基本方程)(),()(11,)(kkkkksuukksfusVoptsfkkk0)(11nnsf终端指标函数定义在最短路线问题中，若找到了A→B1→C2→D1→E2→F是由A到F的最短路线，则D1→E2→F应该是由D1出发到F点的所有可能选择的不同路线中的最短路线。此特性用反证法易证。因为如果不是这样，则从点P到F点有另一条距离更短的路线存在，把它和原来最短路线由A点到达P点的那部分连接起来，就会得到一条由A点到F点的新路线，它比原来那条最短路线的距离还要短些。这与假设矛盾，是不可能的。16.3逆序解法和顺序解法根据最短路线这一特性，寻找最短路线的方法，就是从最后一段开始，用由后向逐步递推的方法，求出各点到F点的最短路线，最后求得由A点到F点的最短路线。所以，动态规划的方法是从终点逐段向始点方向寻找最短路线的一种方法。如图16-3表示。行进方向︱1︱2︱3︱4︱5︱始点终点动态规划寻优途径图16—3下面按照动态规划的方法，将例1从最后一段开始计算，由后向前逐步推移至A点。例16-1用动态规划求解最短路问题的距离到表示从的最短距离到表示从令)())(,(,)(kkkkkkkkkksussusdFssf53246min)(),()(),(min)(73543min)(),()(),(min)(,43)(4)(,52522415124242521415114142515EfEDdEfEDdDfEfEDdEfEDdDfkEfEfkFEuFEu)()(2515114)(EDu224)(EDu85453min)(),()(),(min)(105574min)(),()(),(min)(125875min)(),()(),(min)(343332423333242231412323242131411313