重庆工商大学数学建模算法讲义第04章 动态规划

-56-第四章动态规划§1引言1.1动态规划的发展及研究内容动态规划（dynamicprogramming）是运筹学的一个分支，是求解决策过程（decisionprocess）昀优化的数学方法。20世纪50年代初R.E.Bellman等人在研究多阶段决策过程(multistepdecisionprocess)的优化问题时，提出了著名的昀优性原理（principleofoptimality），把多阶段过程转化为一系列单阶段问题，逐个求解，创立了解决这类过程优化问题的新方法—动态规划。1957年出版了他的名著《DynamicProgramming》，这是该领域的第一本著作。动态规划问世以来，在经济管理、生产调度、工程技术和昀优控制等方面得到了广泛的应用。例如昀短路线、库存管理、资源分配、设备更新、排序、装载等问题，用动态规划方法比用其它方法求解更为方便。虽然动态规划主要用于求解以时间划分阶段的动态过程的优化问题，但是一些与时间无关的静态规划（如线性规划、非线性规划），只要人为地引进时间因素，把它视为多阶段决策过程，也可以用动态规划方法方便地求解。应指出，动态规划是求解某类问题的一种方法，是考察问题的一种途径，而不是一种特殊算法（如线性规划是一种算法）。因而，它不象线性规划那样有一个标准的数学表达式和明确定义的一组规则，而必须对具体问题进行具体分析处理。因此，在学习时，除了要对基本概念和方法正确理解外，应以丰富的想象力去建立模型，用创造性的技巧去求解。例1昀短路线问题图1是一个线路网，连线上的数字表示两点之间的距离（或费用）。试寻求一条由A到G距离昀短（或费用昀省）的路线。图1昀短路线问题例2生产计划问题工厂生产某种产品，每单位（千件）的成本为1（千元），每次开工的固定成本为3（千元），工厂每季度的昀大生产能力为6（千件）。经调查，市场对该产品的需求量第一、二、三、四季度分别为2，3，2，4（千件）。如果工厂在第一、二季度将全年的需求都生产出来，自然可以降低成本（少付固定成本费），但是对于第三、四季度才能上市的产品需付存储费，每季每千件的存储费为0.5（千元）。还规定年初和年末这种产品均无库存。试制定一个生产计划，即安排每个季度的产量，使一年的总费用（生产成本和存储费）昀少。1.2决策过程的分类根据过程的时间变量是离散的还是连续的，分为离散时间决策过程（discrete-time-57-decisionprocess）和连续时间决策过程（continuous-timedecisionprocess）；根据过程的演变是确定的还是随机的，分为确定性决策过程（deterministicdecisionprocess）和随机性决策过程（stochasticdecisionprocess），其中应用昀广的是确定性多阶段决策过程。§2基本概念、基本方程和计算方法2.1动态规划的基本概念和基本方程一个多阶段决策过程昀优化问题的动态规划模型通常包含以下要素。2.1.1阶段阶段(step)是对整个过程的自然划分。通常根据时间顺序或空间顺序特征来划分阶段，以便按阶段的次序解优化问题。阶段变量一般用nk,,2,1L=表示。在例1中由A出发为1=k，由)2,1(=iBi出发为2=k，依此下去从)2,1(=iFi出发为6=k，共6=n个阶段。在例2中按照第一、二、三、四季度分为4,3,2,1=k，共四个阶段。2.1.2状态状态（state）表示每个阶段开始时过程所处的自然状况。它应能描述过程的特征并且无后效性，即当某阶段的状态变量给定时，这个阶段以后过程的演变与该阶段以前各阶段的状态无关。通常还要求状态是直接或间接可以观测的。描述状态的变量称状态变量（statevariable）。变量允许取值的范围称允许状态集合(setofadmissiblestates)。用kx表示第k阶段的状态变量，它可以是一个数或一个向量。用kX表示第k阶段的允许状态集合。在例1中2x可取21,BB，或将iB定义为)2,1(=ii，则12=x或2，而}2,1{2=X。n个阶段的决策过程有1+n个状态变量，1+nx表示nx演变的结果。在例1中7x取G，或定义为1，即17=x。根据过程演变的具体情况，状态变量可以是离散的或连续的。为了计算的方便有时将连续变量离散化；为了分析的方便有时又将离散变量视为连续的。状态变量简称为状态。2.1.3决策当一个阶段的状态确定后，可以作出各种选择从而演变到下一阶段的某个状态，这种选择手段称为决策（decision），在昀优控制问题中也称为控制（control）。描述决策的变量称决策变量（decisionvariable），变量允许取值的范围称允许决策集合（setofadmissibledecisions）。用)(kkxu表示第k阶段处于状态kx时的决策变量，它是kx的函数，用)(kkxU表示kx的允许决策集合。在例1中)(12Bu可取21,CC或3C，可记作3,2,1)1(2=u，而}3,2,1{)1(2=U。决策变量简称决策。2.1.4策略决策组成的序列称为策略（policy）。由初始状态1x开始的全过程的策略记作)(11xpn，即)}(,),(),({)(221111nnnxuxuxuxpL=.由第k阶段的状态kx开始到终止状态的后部子过程的策略记作)(kknxp，即)}(,),({)(nnkkkknxuxuxpL=，1,,2,1−=nkL.类似地，由第k到第j阶段的子过程的策略记作-58-)}(,),({)(jjkkkkjxuxuxpL=.可供选择的策略有一定的范围，称为允许策略集合(setofadmissiblepolicies)，用)(),(),(11kkjkknnxPxPxP表示。2.1.5.状态转移方程在确定性过程中，一旦某阶段的状态和决策为已知，下阶段的状态便完全确定。用状态转移方程（equationofstatetransition）表示这种演变规律，写作.,,2,1),,(1nkuxTxkkkkL==+（1）在例1中状态转移方程为)(1kkkxux=+。2.1.6.指标函数和昀优值函数指标函数(objectivefunction)是衡量过程优劣的数量指标，它是定义在全过程和所有后部子过程上的数量函数，用),,,,(11,++nkkknkxxuxVL表示，nk,,2,1L=。指标函数应具有可分离性，即nkV,可表为nkkkVux,1,,+的函数，记为)),,,(,,(),,,,(111,111,++++++=nkknkkkknkkknkxuxVuxxxuxVLLϕ并且函数kϕ对于变量nkV,1+是严格单调的。过程在第j阶段的阶段指标取决于状态jx和决策ju，用),(jjjuxv表示。指标函数由),,2,1(njvjL=组成，常见的形式有：阶段指标之和，即∑=++=nkjjjjnkkknkuxvxxuxV),(),,,,(11,L，阶段指标之积，即∏=++=nkjjjjnkkknkuxvxxuxV),(),,,,(11,L，阶段指标之极大（或极小），即),((min)max),,,,(11,jjjnjknkkknkuxvxxuxV≤≤++=L.这些形式下第k到第j阶段子过程的指标函数为),,,(1,+jkkjkxuxVL。根据状态转移方程指标函数nkV,还可以表示为状态kx和策略knp的函数，即),(,knknkpxV。在kx给定时指标函数nkV,对knp的昀优值称为昀优值函数（optimalvaluefunction），记为)(kkxf，即),(opt)(,)(knknkxPpkkpxVxfkknkn∈=，其中opt可根据具体情况取max或min。2.1.7昀优策略和昀优轨线使指标函数nkV,达到昀优值的策略是从k开始的后部子过程的昀优策略，记作},,{***nkknuupL=。*1np是全过程的昀优策略，简称昀优策略（optimalpolicy）。从初始状态)(*11xx=出发，过程按照*1np和状态转移方程演变所经历的状态序列},,,{*1*2*1+nxxxL称昀优轨线（optimaltrajectory）。-59-2.1.8递归方程如下方程称为递归方程⎪⎩⎪⎨⎧=⊗==++∈++1,,)},(),({opt)(10)(11)(11LnkxfuxvxfxfkkkkkxUukknnkkk或（2）在上述方程中，当⊗为加法时取0)(11=++nnxf；当⊗为乘法时，取1)(11=++nnxf。动态规划递归方程是动态规划的昀优性原理的基础，即：昀优策略的子策略，构成昀优子策略。用状态转移方程（1）和递归方程（2）求解动态规划的过程，是由1+=nk逆推至1=k，故这种解法称为逆序解法。当然，对某些动态规划问题，也可采用顺序解法。这时，状态转移方程和递归方程分别为：nkuxTxkkrkk,,1),,(1L==+，⎪⎩⎪⎨⎧=⊗==−+∈+++nkxfuxvxfxfkkkkkxUukkkrkk,,1)},(),({opt)(10(11)(11011L或）例3用lingo求解例1昀短路线问题。model:TitleDynamicProgramming;sets:vertex/A,B1,B2,C1,C2,C3,C4,D1,D2,D3,E1,E2,E3,F1,F2,G/:L;road(vertex,vertex)/AB1,AB2,B1C1,B1C2,B1c3,B2C2,B2C3,B2C4,C1D1,C1D2,C2D1,C2D2,C3D2,C3D3,C4D2,C4D3,D1E1,D1E2,D2E2,D2E3,D3E2,D3E3,E1F1,E1F2,E2F1,E2F2,E3F1,E3F2,F1G,F2G/:D;endsetsdata:D=531368766835338422123335526643;L=0,,,,,,,,,,,,,,,;enddata@for(vertex(i)|i#GT#1:L(i)=@min(road(j,i):L(j)+D(j,i)));end纵上所述，如果一个问题能用动态规划方法求解，那么，我们可以按下列步骤，首先建立起动态规划的数学模型：（i）将过程划分成恰当的阶段。（ii）正确选择状态变量kx，使它既能描述过程的状态，又满足无后效性，同时确定允许状态集合kX。（iii）选择决策变量ku，确定允许决策集合)(kkxU。（iv）写出状态转移方程。（v）确定阶段指标),(kkkuxv及指标函数knV的形式（阶段指标之和，阶段指标之积，阶段指标之极大或极小等）。（vi）写出基本方程即昀优值函数满足的递归方程，以及端点条件。§3逆序解法的计算框图-60-以自由终端、固定始端、指标函数取和的形式的逆序解法为例给出计算框图，其它情况容易在这个基础上修改得到。一般化的自由终端条件为1,1,11,,2,1),()(++++==nininnnixxfLϕ(3)其中ϕ为已知。固定始端条件可表示为}{}{*111xxX==。如果状态kx和决策ku是连续变量，用数值方法求解时需按照精度要求进行离散化。设状态kx的允许集合为nkninixXkkkik,,2,1,,,2,1},,,2,1|{LLL====.决策)(kikixu的允许集合为nkninjuUkkijkiki,,2,1,,,2,1},,,2,1|{)(LLL====.状态转移方程和阶段指标应对kx的每个取值kix和kiu的每个取值)(jkiu计算，即),()(jkikikkuxTT=，),()(jkikikuxvv=。昀优值函数应对kx的每个取值kix计算。基本方程可以表为.1,2,,,,,2,1,,,2,1),(opt)()),,((),()()()(1)()(LLLnkninjxfxfuxTfuxvxfkkikijkjkikjkikikkjkikikkijk====+=+（4）图2解法框图-61-按照（3），（4）逆向计算出)(*11xf，为全过程的昀优值。记状态kix的昀优决策为)(*kikixu，由*1x和)(*kikixu按照状态转移方程计算出昀优状态，记作*kx。并得