最优化方法7第七章

1第七章动态规划动态规划是解决多阶段决策过程最优化问题的一种方法，它将多阶段决策问题转化成一系列比较简单的最优化问题．动态规划首先将复杂的问题分解成相互关联的若干阶段，每一个阶段都是一个最优化子问题，然后逐阶段的决策，当所有阶段决策都确定了，整个问题的决策也就确定了．动态规划中阶段可以用时间表示，这就是“动态”的含义．当然，对于与时间无关的一些静态问题也可以人为地引入“时间”转化成动态问题．2最短路径问题：给定一个交通网络图如下，其中两点之间的数字表示距离（或运费），试求从A点到G点的最短距离（总运输费用最小）。123456AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G531368763685338422213335256643背包问题有一个徒步旅行者，其可携带物品重量的限度为a公斤，设有n种物品可供他选择装入包中。已知每种物品的重量及使用价值（作用），问此人应如何选择携带的物品（各几件），使所起作用（使用价值）最大？物品12…j…n重量（公斤/件）a1a2…aj…an每件使用价值c1c2…cj…cn类似的还有工厂里的下料问题、运输中的货物装载问题、人造卫星内的物品装载问题等。4生产决策问题：企业在生产过程中，由于需求是随时间变化的，因此企业为了获得全年的最佳生产效益，就要在整个生产过程中逐月或逐季度地根据库存和需求决定生产计划。机器负荷分配问题：某种机器可以在高低两种不同的负荷下进行生产。要求制定一个五年计划，在每年开始时，决定如何重新分配完好的机器在两种不同的负荷下生产的数量，使在五年内产品的总产量达到最高。航天飞机飞行控制问题：由于航天飞机的运动的环境是不断变化的，因此就要根据航天飞机飞行在不同环境中的情况，不断地决定航天飞机的飞行方向和速度（状态），使之能最省燃料和完成飞行任务（如软着陆）。5§7.1动态规划基本原理一、动态规划的基本概念动态规划中所涉及到的概念有阶段、状态、决策与策略、状态转移、指标函数．(1)阶段将所给问题的过程，按时间或空间特征分解成若干互相联系的阶段，以便按顺序去求每阶段的解，常用字母k表示阶段变量．(2)状态各阶段开始时的客观条件叫做状态．描述各阶段状态的变量称为状态变量，常用sk表示第k阶段的状态变量，状态变量sk的取值集合称为状态集合，用Sk表示．动态规划中的状态必须具有无后效性，即当某阶段状态给定以后，在这阶段以后过程的发展不受这段以前各段状态的影响．也就是说，当前的状态是过去历史的一个完整总结，过程的过去历史只能通过当前状态去影响它未来的发展．6(3)决策和策略当各段的状态取定以后，就可以作出不同的决定(或选择)，从而确定下一阶段的状态，这种决定称为决策．表示决策的变量，称为决策变量，常用uk(sk)表示第k阶段当状态为sk时的决策变量．在实际问题中，决策变量的取值往往限制在一定范围内，称此范围为允许决策集合，常用Dk(sk)表示第k阶段从状态sk出发的允许决策集合，即uk(sk)∈Dk(sk)．7一个按顺序排列的决策组成的集合称为策略．一个n阶段决策过程，从第k阶段到第n阶段的过程称为问题的一个后部子过程，或k子过程．由k子过程的每一阶段的决策按顺序排列组成的策略序列称为k子策略，记为pk，n(sk)，即pk，n(sk)={uk(sk)，uk+1(sk+1)，uk+2(sk+2)，…，un(sn)}．当k=1时，p1，n(s1)就是全过程的一个策略．对每个实际问题，其k子过程可供选择的策略有一定范围，称为允许策略集合，记作Pk，n，使整个问题达到最优效果的策略就是最优策略．8(4)状态转移方程动态规划中本阶段的状态往往是上一阶段状态和上一阶段的决策结果．如果给定了第k阶段的状态sk，本阶段决策为uk，则第k+l阶段的状态sk+1也就完全确定，它们的关系可用公式sk+l＝Tk(sk，uk)表示．该公式表示了由第k阶段到第k+l阶段的状态转移规律，所以称为状态转移方程．9(5)指标函数用于衡量所选定策略优劣的数量指标称为指标函数，它是定义在全过程或子过程上的数量函数，是各阶段的状态和决策变量的函数．它分为阶段指标函数和过程指标函数两种．阶段指标函数是指第k阶段状态sk采取决策uk时的效益，用dk(sk，uk)表示．过程指标函数指在第k阶段状态为sk采用策略pk，n时，后部子过程的收益，用Vk,n(sk，pk，n)表示．Vk,n(sk，pk，n)与dk(sk，uk)之间的关系常见的有求和型和乘积型两种：或．nkjjjjnkknkusdpsV)()(,,，，nkjjjjnkknkusdpsV)()(,,，，10最优指标函数表示从第k阶段状态sk采用最优策略到过程终止时的最佳效益值，记为fk(sk)．fk(sk)与间的关系为式中opt表示最优化，根据具体问题表示为max或min．当k=1时，f1(s1)就是从初始状态s1到全过程结束的整体最优函数．)()()(,,*,,,,nkknkPpnkknkkkpsVoptpsVsfnknk，，,,()knkknVsp，11二、动态规划的基本方程动态规划方法基于贝尔曼(R.Bellman)提出的最优化原理：一个过程的最优策略具有这种性质，即不管先前的状态和决策如何，余下的所有决策必构成的最优子策略．最优性原理是动态规划理论的核心．这个原理说明，最优策略的任一后部子策略也是最优的．根据这个原理，在求解多阶段决策问题时，前面的各状态和决策，对其后面的子问题来说，只不过相当于其初始条件而已，并不影响后面过程的最优决策．因此，可以把多阶段决策问题求解过程表示成一个连续的递推过程，由后向前逐步计算．这要利用第k阶段与第k+1阶段之间的关系，通常如下：12)()(11))()(()(1111边界条件，已知，，，，，，，csfnnksfusdoptsfnnkkkkkukkK或．边界条件，已知，，，，，，，)()(11))()(()(1111csfnnksfusdoptsfnnkkkkkukkk该方程称为动态规划的基本方程．13三、动态规划的求解方法动态规划的求解有两种基本方法：逆序解法(后向动态规划方法)、顺序解法(前向动态规划方法)．当寻优的方向与多阶段决策过程的实际行进方向相反，从最后一段开始计算逐段前推，求得全过程的最优策略，称为逆序解法．与之相反，顺序解法的寻优方向与过程的行进方向相同，计算时从第一段开始逐段向后递推，计算后一阶段要用到前一阶段的求优结果，最后一段计算的结果就是全过程的最优结果．一般而言，如果已知过程的初始状态，则用逆序解法；如果已知过程的终止状态，则用顺序解法．这两种方法除了寻优方向不同外，状态转移方程、指标函数的定义和基本方程形式一般也有差异，但并无本质上的区别．下面主要介绍逆序解法．1s1ns14设已知初始状态为．1s第阶段：指标函数的最优值此为一维极值问题，不妨设有最优解，于是可有最优值．n),()()(nnnsDxnnusvoptsfnnn)(nnnsuu)(nnsf第阶段：类似地有其中*表示“+”或“”，，可解得最优解，于是最优值为．1n)(*),()(111)(11111nnnnnsDxnnsfusVoptsfnnn)(111nnnnusTs，)(111nnnsuu)(11nnsf15不妨设第k+1阶段的最优解为和最优值，则对于第阶段有)(111kkksuu)(11kksfk)(*)()(11)(kkkkksDxkksfusVoptsfkkk，其中，可解得最优解和最优值为．)(1kkkkusTs，)(kkksuu)(kksf依此类推，直到第1阶段，有，其中，可解得最优解和最优值为)(*)()(22111)(11111sfusVoptsfsDx，)(1112usTs，)(111suu)(11sf由于已知，则可知u1与．从而可知，按上面的过程反推回去，即可得到每一阶段和全过程的最优决策．1s)(11sf)(2222sfus，，16例7.1求解下面的优化问题．，，，，，321010..294)(max3212321ixxxxtsxxxXfi解这是一个静态问题，为了应用动态规划，先人为的赋予它“阶段”的概念．首先考虑x1的取值，然后考虑x2的取值，x3的取值，这样就将原问题划分为3个阶段，下面的关键是如何选择状态变量，使各后部子过程之间具有递推关系．通常可以把决策变量uk定义为原静态问题中的变量xk，即uk=xk(k=1，2，3)．状态变量一般为累计量或随递推过程变化的量．这里可以把个阶段的决策变量的最大可能取值定为状态变量sk，初始状态s1=10．这样就有17k=1时，s1=10，u1=x1；k=2时，s2=s1－u1，u2=x2；k=1时，s3=s2－u2，u3=x3．状态转移方程为sk+1=sk－uk，指标函数为其中，基本方程为33,),(kiiiikusdV11114),(uusd22229),(uusd233332),(uusd．，，，，0)(123)}(),({max)(44110sfksfusdsfkkkkksukkkk18当k=3时，，显然．}2{max)(2303333usfsu3*3su当k=2时，})(29{max)}(9{max)(222203320222222ususfusfsusu由高等数学知识可得2/92s时，**2220uus或者时，；时，．2/92s0*2u2/92s2*2su当k=1时，．)}(4{max)(22101111sfusfsu当时，，2*2su2229)(ssf)0(909}59{max)}(94{max)10(*1111100111100111usususufuu但是与矛盾，所以舍去；10*121uss2/92s19当时，0*2u22222)(ssf})10(24{max)10(21110011uufu由高等数学知识可得0*1u200)10(1f由状态转移方程顺推，得，显然应取10*121uss0*2u，所以10*223uss，而．103*3su所以最优解为TTTuuuxxx］，，［］，，［］，，［1000321321200maxz例1、从A地到E地要铺设一条煤气管道,其中需经过三级中间站，两点之间的连线上的数字表示距离，如图所示。问应该选择什么路线，使总距离最短？最短路径问题AB2B1B3C1C3D1D2E52141126101043121113965810521C221解：整个计算过程分四个阶段，从最后一个阶段开始。第四阶段（D→E）：D有两条路线到终点E。显然有AB2B1B3C1C3D1D2E52141126101043121113965810521C22)(;5)(2414DfDf22首先考虑经过的两条路线第三阶段（C→D）：C到D有6条路线。(最短路线为)AB2B1B3C1C3D1D2E5214126101043121113965810521C282953min)(),()(),(min)(2421141113DfDCdDfDCdCfEDC111C23AB2B1B3C1C3D1D2E5214126101043121113965810521C272556min)(),()(),(min)(2422141223DfDCdDfDCdCf(最短路线为)EDC22考虑经过的两条路线2C24AB2B1B3C1C3D1D2E5214126101043121113965810521C21221058min)(),()(),(min)(2423141333DfDCdDfDCdCf(最短路线