第四篇动态规划_.docx

《第四篇动态规划_.docx》由会员分享，可在线阅读，更多相关《第四篇动态规划_.docx（17页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第四篇动态规划_第四章动态规划1引言1.1动态规划的发展及研究内容动态规划dynamicprogramming是运筹学的一个分支，是求解多阶段决策问题的最优化方法。20世纪50年代初R.E.Bellman等人在研究多阶段决策经过(multistepdecisionprocess)的优化问题时，提出了著名的最优性原理principleofoptimality，把多阶段经过转化为一系列单阶段问题，逐个求解，创立了解决这类经过优化问题的新方法动态规划。1957年出版了他的名著（DynamicProgramming），这是该领域的第一本著作。动态规划问世以来，在经济管理、生产调度、工程技术和最优控制等

2、方面得到了广泛的应用。例如最短道路、库存管理、资源分配、设备更新、排序、装载等问题，用动态规划方法比用其它方法求解更为方便。固然动态规划主要用于求解以时间划分阶段的动态经过的优化问题，但是一些与时间无关的静态规划如线性规划、非线性规划，只要人为地引进时间因素，把它视为多阶段决策经过，可以以用动态规划方法方便地求解。应指出，动态规划是求解某类问题的一种方法，是考察问题的一种途径，而不是一种特殊算法如线性规划是一种算法。因此，它不象线性规划那样有一个标准的数学表达式和明确定义的一组规则，而必须对详细问题进行详细分析处理。因而，在学习时，除了要对基本概念和方法正确理解外，应以丰富的想象力去建立模型，

3、用创造性的技巧去求解。例1最短道路问题下面是一个线路网，连线上的数字表示两点之间的距离或费用。试寻求一条由A到G距离最短或费用最省的道路。例2生产计划问题工厂生产某种产品，每单位千件的成本为1千元，每次开工的固定成本为3千元，工厂每季度的最大生产能力为6千件。经调查，市场对该产品的需求量第一、二、三、四季度分别为2，3，2，4千件。假如工厂在第一、二季度将全年的需求都生产出来，自然能够降低成本少付固定成本费，但是对于第三、四季度才能上市的产品需付存储费，每季每千件的存储费为0.5千元。还规定年初和年末这种产品均无库存。试制定一个生产计划，即安排每个季度的产量，使一年的总费用生产成本和存储费最少

4、。1.2决策经过的分类根据经过的时间变量是离散的还是连续的，分为离散时间决策经过discrete-timedecisionprocess和连续时间决策经过continuous-timedecisionprocess；根据经过的演变是确定的还是随机的，分为确定性决策经过deterministicdecisionprocess和随机性决策经过stochasticdecisionprocess，其中应用最广的是确定性多阶段决策经过。2基本概念、基本方程和计算方法2.1动态规划的基本概念和基本方程一个多阶段决策经过最优化问题的动态规划模型通常包含下面要素。2.1.1阶段阶段(step)是对整个经过的自

5、然划分。通常根据时间顺序或空间顺序特征来划分阶段，以便按阶段的次序解优化问题。阶段变量一般用nk,2,1表示。在例1中由A出发为1k，由)2,1(iBi出发为2k，依此下去从)2,1(iFi出发为6k，共6n个阶段。在例2中根据第一、二、三、四季度分为4,3,2,1k，共四个阶段。2.1.2状态状态state表示每个阶段开场时经过所处的自然状况。它应能描绘经过的特征并且无后效性，即当某阶段的状态变量给定时，这个阶段以后经过的演变与该阶段以前各阶段的状态无关。通常还要求状态是直接或间接能够观测的。描绘状态的变量称状态变量statevariable。变量允许取值的范围称允许状态集合(setofad

6、missiblestates)。用kx表示第k阶段的状态变量，它能够是一个数或一个向量。用kX表示第k阶段的允许状态集合。在例1中2x可取21,BB，或将iB定义为)2,1(ii，则12x或2，而2,12X。n个阶段的决策经过有1n个状态变量，1nx表示nx演变的结果。在例1中7x取G，或定义为1，即17x。根据经过演变的详细情况，状态变量能够是离散的或连续的。为了计算的方便有时将连续变量离散化；为了分析的方便有时又将离散变量视为连续的。状态变量简称为状态。2.1.3决策当一个阶段的状态确定后，能够作出各种选择进而演变到下一阶段的某个状态，这种选择手段称为决策decision，在最优控制问题中

7、也称为控制control。描绘决策的变量称决策变量decisionvariable，变量允许取值的范围称允许决策集合setofadmissibledecisions。用)(kkxu表示第k阶段处于状态kx时的决策变量，它是kx的函数，用)(kkxU表示kx的允许决策集合。在例1中)(12Bu可取21,CC或3C，可记作3,2,1)1(2u，而3,2,1)1(2U。决策变量简称决策。2.1.4策略决策组成的序列称为策略policy。由初始状态1x开场的全经过的策略记作)(11xpn，即)(,),(),()(221111nnnxuxuxuxp.由第k阶段的状态kx开场到终止状态的后部子经过的策略记

8、作)(kknxp，即)(,),()(nnkkkknxuxuxp，1,2,1nk.类似地，由第k到第j阶段的子经过的策略记作)(,),()(jjkkkkjxuxuxp.可供选择的策略有一定的范围，称为允许策略集合(setofadmissiblepolicies)，用)(),(),(11kkjkknnxPxPxP表示。2.1.5.状态转移方程在确定性经过中，一旦某阶段的状态和决策为已知，下阶段的状态便完全确定。用状态转移方程equationofstatetransition表示这种演变规律，写作.,2,1),(1nkuxTxkkkk1在例1中状态转移方程为)(1kkkxux。2.1.6.指标函数和

9、最优值函数指标函数(objectivefunction)是衡量经过优劣的数量指标，它是定义在全经过和所有后部子经过上的数量函数，用),(11nkkkknxxuxV表示，nk,2,1。指标函数应具有可分离性，即knV可表为nkkkVux1,的函数，记为),(,(),(1211111nkkknkkkknkkkknxxuxVuxxxuxV并且函数k对于变量nkV1是严格单调的。经过在第j阶段的阶段指标取决于状态jx和决策ju，用),(jjjuxv表示。指标函数由),2,1(njvj组成，常见的形式有：阶段指标之和，即nkjjjjnkkkknuxvxxuxV),(),(11，阶段指标之积，即nkjjj

10、jnkkkknuxvxxuxV),(),(11，阶段指标之极大或极小，即),(min)max),(11jjjnjknkkkknuxvxxuxV.这些形式下第k到第j阶段子经过的指标函数为),(11jkkkkjxxuxV。根据状态转移方程指标函数knV还能够表示为状态kx和策略knp的函数，即),(knkknpxV。在kx给定时指标函数knV对knp的最优值称为最优值函数optimalvaluefunction，记为)(kkxf，即),(opt)()(knkknxPpkkpxVxfkknkn，其中opt可根据详细情况取max或min。2.1.7最优策略和最优轨线使指标函数knV到达最优值的策略是

11、从k开场的后部子经过的最优策略，记作,*nkknuup。*1np是全经过的最优策略，简称最优策略optimalpolicy。从初始状态)(*11xx出发，经过根据*1np和状态转移方程演变所经历的状态序列,*1*2*1nxxx称最优轨线optimaltrajectory。2.1.8递归方程如下方程称为递归方程1,),(),(opt)(10)(11)(11nkxfuxvxfxfkkkkkxUukknnkkk或2在上述方程中，当为加法时取0)(11knxf；当为乘法时，取1)(11knxf。动态规划递归方程是动态规划的最优性原理的基础，即：最优策略的子策略，构成最优子策略。用状态转移方程1和递归方

12、程2求解动态规划的经过，是由1nk逆推至1k，故这种解法称为逆序解法。当然，对某些动态规划问题，可以采用顺序解法。这时，状态转移方程和递归方程分别为：nkuxTxkkkk,1),(111，nkxfuxvxfxfkkkkkxUukkkkk,1),(),(opt)(10(111)(1111111或纵上所述，假如一个问题能用动态规划方法求解，那么，我们能够按下列步骤，首先建立起动态规划的数学模型：i将经过划分成恰当的阶段。ii正确选择状态变量kx，使它既能描绘经过的状态，又知足无后效性，同时确定允许状态集合kX。iii选择决策变量ku，确定允许决策集合)(kkxU。iv写出状态转移方程。v确定阶段指

13、标),(kkkuxv及指标函数knV的形式阶段指标之和，阶段指标之积，阶段指标之极大或极小等。vi写出基本方程即最优值函数知足的递归方程，以及端点条件。3逆序解法的计算框图以自由终端、固定始端、指标函数取和的形式的逆序解法为例给出计算框图，其它情况容易在这个基础上修改得到。一般化的自由终端条件为1111,2,1),()(nininnnixxf(3)其中为已知。固定始端条件可表示为*111xxX。假如状态kx和决策ku是连续变量，用数值方法求解时需根据精度要求进行离散化。设状态kx的允许集合为nknixXkkik,2,1,2,1|.决策)(kikixu的允许集合为nkninjuUkkijkiki

14、,2,1,2,1,2,1|)(.状态转移方程和阶段指标应对kx的每个取值kix和kiu的每个取值)(jkiu计算，即),()(jkikikkuxTT，),()(jkikikuxvv。最优值函数应对kx的每个取值kix计算。基本方程能够表为.1,2,2,1,2,1),(opt)(),(),()()()(1)()(nkninjxfxfuxTfuxvxfkkikijkjkikjkikikkjkikikkijk4根据3，4逆向计算出)(*11xf，为全经过的最优值。记状态kix的最优决策为)(*kikixu，由*1x和)(*kikixu根据状态转移方程计算出最优状态，记作*kx。并得到相应的最优决策，

15、记作)(*kkxu。于是最优策略为)(,),(),(*2*2*1*1nnxuxuxu。算法程序的框图如下。图的左边部分是函数序列的递推计算，可输出全经过最优值)(*11xf，假如需要还能够输出后部子经过最优值函数序列)(kikxf和最优决策序列)(*kikxu。计算经过中存)(kikxf是备计算1kf之用，在1kf算完后可用1kf将kf替换掉；存)(*kikxu是备右边部分读)(*kkxu之用。图的右边部分是最优状态和最优决策序列的正向计算，可输出最优策略)(,),(),(*2*2*1*1nnxuxuxu和最优轨线,*2*1nxxx。4动态规划与静态规划的关系动态规划与静态规划线性和非线性规划

16、等研究的对象本质上都是在若干约束条件下的函数极值问题。两种规划在很多情况下原则上能够互相转换。动态规划能够看作求决策nuuu,21使指标函数),(2111nnuuuxV，到达最优最大或最小的极值问题，状态转移方程、端点条件以及允许状态集、允许决策集等是约束条件，原则上能够用非线性规划方法求解。一些静态规划只要适当引入阶段变量、状态、决策等就能够用动态规划方法求解。下面用例子讲明。例3用动态规划解下列非线性规划nkkkug1)(max；s.t.nkkkuau10,.其中)(kkug为任意的已知函数。解按变量ku的序号划分阶段，看作n段决策经过。设状态为nxxx,21，取问题中的变量nuuu,21

17、为决策。状态转移方程为.,2,1,11nkuxxaxkkk取)(kkug为阶段指标，最优值函数的基本方程为注意到01nx)()(max)(110kkkkxukkxfxgxfkk；1,2,1,0nnkaxk；0)0(1nf.根据逆序解法求出对应于kx每个取值的最优决策)(*kkxu，计算至)(1af后即可利用状态转移方程得到最优状态序列*kx和最优决策序列)(*kkxu。与静态规划相比，动态规划的优越性在于：i能够得到全局最优解。由于约束条件确定的约束集合往往很复杂，即便指标函数较简单，用非线性规划方法也很难求出全局最优解。而动态规划方法把全经过化为一系列构造类似的子问题，每个子问题的变量个数大

18、大减少，约束集合也简单得多，易于得到全局最优解。十分是对于约束集合、状态转移和指标函数不能用分析形式给出的优化问题，能够对每个子经过用枚举法求解，而约束条件越多，决策的搜索范围越小，求解也越容易。对于这类问题，动态规划通常是求全局最优解的唯一方法。ii能够得到一族最优解。与非线性规划只能得到全经过的一个最优解不同，动态规划得到的是全经过及所有后部子经过的各个状态的一族最优解。有些实际问题需要这样的解族，即便不需要，它们在分析最优策略和最优值对于状态的稳定性时也是很有用的。当最优策略由于某些原因不能实现时，这样的解族能够用来寻找次优策略。iii能够利用经历提高求解效率。假如实际问题本身就是动态的

19、，由于动态规划方法反映了经过逐段演变的前后联络和动态特征，在计算中能够利用实际知识和经历提高求解效率。如在策略迭代法中，实际经历能够帮助选择较好的初始策略，提高收敛速度速度。动态规划的主要缺点是：i没有统一的标准模型，也没有构造模型的通用方法，甚至还没有判定一个问题能否构造动态规划模型的准则。这样就只能对每类问题进行详细分析，构造详细的模型。对于较复杂的问题在选择状态、决策、确定状态转移规律等方面需要丰富的想象力和灵敏的技巧性，这就带来了应用上的局限性。ii用数值方法求解时存在维数灾curseofdimensionality。若一维状态变量有m个取值，那么对于n维问题，状态kx就有nm个值，对

20、于每个状态值都要计算、存储函数)(kkxf，对于n稍大即便3n的实际问题的计算往往是不现实的。目前还没有克制维数灾的有效的一般方法。5若干典型问题的动态规划模型5.1最短道路问题对于例1一类最短道路问题shortestPathProblem，阶段按经过的演变划分，状态由各段的初始位置确定，决策为从各个状态出发的走向，即有)(1kkkxux，阶段指标为相邻两段状态间的距离)(,(kkkkxuxd，指标函数为阶段指标之和，最优值函数)(kkxf是由kx出发到终点的最短距离或最小费用，基本方程为;1,),()(,(min)(11)(nkxfxuxdxfkkkkkkxukkkk.0)(11nnxf利用

21、这个模型能够算出例l的最短道路为GFEDCAB22121，相应的最短距离为18。5.2生产计划问题对于例2一类生产计划问题Productionplanningproblem，阶段按计划时间自然划分，状态定义为每阶段开场时的储存量kx，决策为每个阶段的产量ku，记每个阶段的需求量已知量为kd，则状态转移方程为.,2,1,0,1nkxduxxkkkkk(5)设每阶段开工的固定成本费为a，生产单位数量产品的成本费为b，每阶段单位数量产品的储存费为c，阶段指标为阶段的生产成本和储存费之和，即00,),(kkkkkkubuacxuxv(6)指标函数knV为kv之和。最优值函数)(kkxf为从第k段的状态

22、kx出发到经过终结的最小费用，知足.1,),(),(min)(11nkxfuxvxfkkkkkUukkkk其中允许决策集合kU由每阶段的最大生产能力决定。若设经过终结时允许存储量为01nx，则终端条件是.0)(011nnxf757构成该问题的动态规划模型。5.3资源分配问题一种或几种资源包括资金分配给若干用户，或投资于几家企业，以获得最大的效益。资源分配问题resourceallocatingProblem能够是多阶段决策经过，可以以是静态规划问题，都能构造动态规划模型求解。下面举例讲明。例4机器能够在高、低两种负荷下生产。u台机器在高负荷下的年产量是)(ug，在低负荷下的年产量是)(uh，高

23、、低负荷下机器的年损耗率分别是1a和1b1011ab。现有m台机器，要安排一个n年的负荷分配计划，即每年初决定多少台机器投入高、低负荷运行，使n年的总产量最大。假如进一步假设uug)(，uuh)(0，即高、低负荷下每台机器的年产量分别为和，结果将有什么特点。解年度为阶段变量nk,2,1。状态kx为第k年初完好的机器数，决策ku为第k年投入高负荷运行的台数。当kx或ku不是整数时，将小数部分理解为一年中正常工作时间或投入高负荷运行时间的比例。机器在高、低负荷下的年完好率分别记为a和b，则11aa，11bb，有ba。由于第k年投入低负荷运行的机器台数为kkux，所以状态转移方程是)(1kkkkux

24、baux8阶段指标kv是第k年的产量，有)()(),(kkkkkkuxhuguxv9指标函数是阶段指标之和，最优值函数)(kkxf知足.1,2,0),(),(max)(110nkmxxfuxvxfkkkkkkxukkkk(10)及自由终端条件.0,0)(111mxxfnnn11当kv中的hg,用较简单的函数表达式给出时，对于每个k能够用解析方法求解极值问题。十分，若uug)(，uuh)(，10中的)(),(1kkkkkxfuxv将是ku的线性函数，最大值点必在区间kkxu0的左端点0ku或右端点kkxu获得，即每年初将完好的机器全部投入低负荷或高负荷运行。习题四1.设某工厂有1000台机器，生产两种产品BA、，若投入y台机器生产A产品，则纯收入为y5，若投入y台机器生产B种产品，则纯收入为y4，又知：生产A种产品机器的年折损率为20%，生产B产品机器的年折损率为10%，问在5年内怎样安排各年度的生产计划，才能使总收入最高？(最好给出Matlab的求解程序)。2.有四个工人，要指派他们分别完成4项工作，每人做各项工作所消耗的时间如方法求解。3.为保证某一设备的正常运转，需备有三种不同的零件321,EEE。若增加备用零件的数量，可提高设备正常运转的可靠性，但增加了费用，而投资额仅为8000元。已此页面能否是列表页或首页？未找到适宜正文内容。