第八章动态规划.

第八章动态规划第一节动态规划原理和模型第二节一维动态规划求解方法第三节动态规划在经济和管理中的应用第一节动态规划原理和模型一、引例与动态规划的基本概念二、动态规划的原理三、动态规划模型的建立动态规划是50年初由美国数学家R.Bellman等人提出的解决多阶段决策过程优化问题的“最优化原理”基础上建立起来的。动态规划是将一个较复杂的多阶段决策问题分解为若干相互关联的较容易求解的子决策问题，而每一个子决策问题都有多种选择，并且当一个子决策问题确定以后，将影响另一个子决策问题，从而影响到整个问题的决策。一、动态规划的基本概念动态规划模型分为（1）离散模型；（2）连续模型。本章只讨论与离散模型有关原理和方法。这对连续模型也适用。下面通过一个多阶段决策过程的例子引入动态规划的基本概念、原理和方法。例8.1．（最短路问题）某运输公司拟将一批货物从A地运往E地，其间的交通系统网络如图8-1所示。图上节点表示地点，边表示两地之间的道路，边上的数字表示两地间的运输费用，求运输费用最低的运输路线。相关的概念:AB1B2B3C1C2C3D1D2E第2阶段第3阶段第4阶段第1阶段5412331136444165798(1)阶段将所给问题的过程，按时间或空间特征分解成若干互相联系的阶段，按次序去求每阶段的解，用字母k表示阶段变量。AB1B2B3C1C2C3D1D2E第2阶段第3阶段第4阶段第1阶段的状态第2阶段的状态第1阶段541233113644416579s1状态A，s2?S1={A}，S2={B1、B2、B3}，S3={C1、C2、C3}，S4={D1、D2}。8(2)状态状态就是阶段的起始位置。通常一个阶段包含若干个状态。第k阶段的状态就是该阶段所有始点的集合。描述各阶段状态的变量称为状态变量。常用sk表示第k阶段的状态变量。状态变量的取值集合称为状态集合，用Sk表示。3）决策决策是某阶段状态给定之后，从该状态演变到下一阶段某一状态的选择。表示决策的变量称为决策变量，用uk(sk)表示第阶段，状态为sk时的决策变量，它是状态变量的函数。实际问题中，决策变量的选取往往受到某些条件的影响而限制于某一范围，此范围称为允许决策集合。AB1B2B3C1C2C3D1D2E第2阶段第3阶段第4阶段第1阶段的状态第2阶段的状态第1阶段541233113644416579在例8.1中，u2(B1)就表示第2阶段状态为B1时的决策变量（它或等于C1或等于C3），即，从第2阶段的状态B1出发，可到达下一阶段的C1或者C3，所以这一阶段的允许决策集D2(B1)={C1,C3}。84）策略各阶段决策确定后，组成的一个有序的决策序列就构成了一个策略。称为全过程的一个策略，简称策略。称为由第k阶段开始到最后阶段止的一个子策略，简称后部子策略。使整个问题到达最优效果的策略称为最优策略。动态规划方法就是要从允许策略集中找出最优策略。)}(,),(),({11,nnkkkknksususup)}(,),({11,1nnnsusupAB1B2B3C1C2C3D1D2E第2阶段第3阶段第4阶段第1阶段的状态第2阶段的状态第1阶段541233113644416579pA,E{A,B2,C3,D2,E}就是一个策略。8pB2,E{B2,C3,D2,E}就是一个子策略。AB1B2B3C1C2C3D1D2E第2阶段第3阶段第4阶段第1阶段的状态第2阶段的状态第1阶段541233113644416579状态转移方程为sk+1=uk(sk)85）状态转移方程它是确定过程由某一阶段的一个状态到下一阶段另一状态的演变过程，用sk+1=Tk(sk,uk)表示。该方程描述了由第k阶段到第k+1阶段的状态转移规律。因此又称其为状态转移函数。指标函数是用来衡量多阶段决策过程优劣的一种数量指标。一个n阶段决策过程，从1到n称为问题的原过程，对于任意一个给定的k（1≤k≤n），从第k阶段到第n阶段的过程称为原过程的一个后部子过程。用V1,n(s1,p1,n)表示初始状态为s1采用策略p1,n时，原过程的指标函数值。Vk,n(sk,pk,n)表示在第k阶段，状态为sk采用策略pk,n时，后部子过程的指标函数值。从第k阶段状态sk采用最优策略p*k,n到过程终止时的最佳效益值，称为最优指标函数。记为fk(sk)。6）指标函数),(),()(,,*,,,nkknkpnkknkkkpsVoptimumpsVsfnkAB1B2B3C1C2C3D1D2E第2阶段第3阶段第4阶段第1阶段的状态第2阶段的状态第1阶段541233113644416579V2,4(B1)：表示在第2阶段，状态为B1时，从B1到E的距离。f2(B1)则表示从B1到E的最短距离。8二、动态规划的原理在例8.1中，整个运输路程分为四个阶段，见图8.2。下面给出求解的全过程。这里我们采用倒推的方法，即从终点（E）到起点（A）。1．第4阶段，即从E到D，从E出发倒推到下一站D，它可通过D1，也可通过D2，所需费用分别为5和3。如果现处于状态D1，到终点E的最佳路线费用：f4(D1)=5，最优策略：u4(D1)=E。如果现处于状态D2，到终点E的最佳路线费用：f4(D2)=3，最优策略：u4(D2)=E。第3阶段，当从E到达D后，有两个状态D1和D2；若处于状态D1，则可到达C1或C2，则费用分别为9或7。若处于状态D2，则可到达C1或C2或C3，费用分别为8或12或5。从E经D1到达C1或C2的费用，应加上E到达D1这段的费用，所以费用分别为5+9=14、5+7=12；从E经D2到达C2或C2或C3的费用，应加上E到达D2这段的费用，所以费用分别为3+8=11、3+12=15、3+5=8。如果现在处于C1，则到达终点E的最小费用为：最小费用路线为相应的最优决策u3(C1)=D2。如果现在处于C2，则到达终点E的最小费用为：最小费用路线为。相应的最优决策:1231257min)(12)(7min)(241423DfDfCf113859min)(8)(9min)(241413DfDfCfEDC21EDC12123)(DCu如果现在处于C3，到达终点E的最小费用为：最小费用路线为相应的最优决策8}35min{)}(5min{)(2433DfCfEDC23233)(DCu3．第2阶段，同上。如果现处于B1，到达终点E的最小费用为：最小费用路线为相应的最优决策如果现处于B2，则到达终点E的最小费用为：最小费用路线为相应的最优决策如果现处于B3，则到达终点E的最小费用为：最小费用路线为相应的最优决策1284113min)(4)(3min)(331312CfCfBfEDCB231312)(CBu15126124114min)(6)(4)(4min)(33231322CfCfCfBfEDCB212122)(CBu12126111min)(6)(1min)(331332CfCfBfEDCB213132)(CBu4．在第1阶段A处，则到达终点E的最小费用为：最小费用路线为：相应的最优决策：所以，整个问题的最小费用路线为：最优策略为：{，，，}。161211153124min)(11)(3)(4min)(3222121BfBfBfAfEDCBA23111)(BAuEDCBA23111)(BAu312)(CBu233)(DCuEDu)(24在每一阶段的求解，都利用了第k阶段和第k+1阶段的如下关系：0)(1,2,3,4)}(),(min{)(5511sfksfusdsfkkkkkkk这种关系称为动态规划的基本方程。所谓最优化原理是：一个过程的最优决策具有这样的性质：无论初始状态及初始决策如何，对于先前决策所形成的状态而言，其以后的所有决策应构成最优策略。三、动态规划模型的建立用动态规划解决实际问题，就要建立动态规划模型，为此需要解决如下问题：1.划分阶段2.确定状态变量和决策变量以及相应的取值范围3.建立状态转移方程4.确定指标函数，建立动态规划的基本方程5.确定边界条件1.划分阶段按照时间、空间、变量划分为若干阶段。建立动态规划模型要求每个阶段问题具有同一模式。2.确定状态变量和决策变量以及相应的取值范围决策过程可用状态演变描述。状态必须包含表示系统情况和确定决策所需要的全部信息，反映过程的演变特征。无后效性。找出状态变量在各阶段的取值范围。决策变量由系统最优化的目的所决定。3.建立状态转移方程根据状态变量和决策变量的含义，写出状态转移方程。4.确定指标函数，建立动态规划的基本方程选取指标函数，根据指标函数建立最优指标函数递推关系,即基本方程5.确定边界条件增加研制费：万元新产品成功的概率甲乙丙0120.600.800.850.400.700.900.300.600.70例8.2.有一工厂研制甲、乙、丙三种新产品，估计这三种新产品研制成功的概率分别为：0.6、0.4、0.3。由于工厂急于推出新产品，决定再加拨2万元研制费，以提高新产品研制成功的概率。据估计，把增加的研制费用于各种新产品研制时，研制成功的概率见下表。现把这批研制费分配给各新产品（不分配、分配给1万元或分配给2万元），使这三种新产品都研制成功的概率最大。应怎样分配。划分阶段把对某一种新产品增加研制费用作为一个阶段，将整个过程分为三个阶段。对甲产品增加研制费用记为第1阶段、对乙产品增加研制费用记为第2阶段、对丙产品增加研制费用记为第3阶段。K=1,2,3。状态变量把有可能提供的研制费用作为状态变量，记为sk，它的取值范围是：0、1、2决策变量把给第k种新产品的研制费用的数量作为决策变量uk，它由决策者决定，不能超过当时拥有的金额sk建立状态转移方程sk+1=sk-uk确定指标函数确定边界条件由于开始时可用的金额为2万元，而最后将全部用完，所以s1=2，s4=0个阶段研制成功的概率表示第k),(1)(1,2,3)},(),(max{)(4411kkkkkkkkkkuspsfksfuspsf第二节一维动态规划求解方法一、逆推法二、顺推法逆推法是从最后一个阶段开始，逐阶段向前，直至第一阶段，即可求出全过程最优策略和指标函数的最优值。例8.3．用逆推法求解例8.2。一、逆推法增加研制费（万元）uk各阶段状态s（可提供的资金）、决策变量u的取值第一阶段第二阶段第三阶段012uk=sk-sk+1S1=0S1=1S1=2u1=s1-s2S2=0S2=1S2=2u2=s2-s3S3=0S3=1S3=2u3=s3-s4,s4=0增加研制费（万元）新产品成功的概率甲乙丙0120.600.800.850.400.700.900.300.600.70第三阶段)}(),(max{)(4433333sfuspsf04s33us•s3=0•s3=1•s3=230.0}130.0max{)}0()0,0(max{)0(433fpf0*3u60.0}160.0max{)}0()1,1(max{)1(433fpf1*3u70.0}170.0max{)}0()2,2(max{)2(433fpf2*3u第二阶段)}(),(max{)(22222222usfuspsf12.0}30.040.0max{)}0()0,0(max{)0(322fpf0*2u•s2=0•s2=1•s2=224.03.07.06.04.0max)11()1,1()01()0,1(max)1(32322