数学模型动态规划

1动态规划动态规划(dynamicprogramming)是运筹学的一个重要分支，它是解决多阶段决策问题的一种有效的数量化方法．动态规划是由美国学者贝尔曼(R．Bellman）等人所创立的．1951年贝尔曼首先提出了动态规划中解决多阶段决策问题的最优化原理，并给出了许多实际问题的解法．1957年贝尔曼发表了《动态规划》一书，标志着运筹学这一重要分支的诞生．§1动态规划的概念与原理一、动态规划的基本概念引例:最短路线问题美国黑金石油公司（TheBlackGoldPetroleumCompany）最近在阿拉斯加（Alaska）的北斯洛波（NorthSlope）发现了大的石油储量。为了大规模开发这一油田，首先必须建立相应的输运网络，使北斯洛波生产的原油能运至美国的3个装运港之一。在油田的集输站（结点C）与装运港（结点P1、P2、P3）之间需要若干个中间站，中间站之间的联通情况如图1所示，图中线段上的数字代表两站之间的距离（单位：10千米）。试确定一最佳的输运线路，使原油的输送距离最短。解：最短路线有一个重要性质，即如果由起点A经过B点和C点到达终点D是一条最短路线，则由B点经C点到达终点D一定是B到D的最短路（贝尔曼最优化原理）。此性质用反证法很容易证明，因为如果不是这样，则从B点到D点有另一条距离更短的路线存在，不妨假设为B—P—D；从而可知路线A—B—P—D比原路线A—B—C—D距离短，这与原路线A—B—C—D是最短路线相矛盾，性质得证。根据最短路线的这一性质，寻找最短路线的方法就是从最后阶段开始，由后向前逐步递推求出各点到终点的最短路线，最后求得由始点到终点的最短路；即动态规划的方法是从终点逐段向始点方向寻找最短路线的一种方法。按照动态规划的方法，将此过程划分为4个阶段，即阶段变量4,3,2,1k；取过程在各阶段所处的位置为状态变量kx，按逆序算法求解。2当4k时：由结点M31到达目的地有两条路线可以选择，即选择P1或P2；故：668min)(3144Mxf选择P2由结点M32到达目的地有三条路线可以选择，即选择P1、P2或P3；故：3734min)(3244Mxf选择P2由结点M33到达目的地也有三条路线可以选择，即选择P1、P2或P3；故：5567min)(3344Mxf选择P3由结点M34到达目的地有两条路线可以选择，即选择P2或P3；故：343min)(3444Mxf选择P2当3k时：由结点M21到达下一阶段有三条路线可以选择，即选择M31、M32或M33；故：CP3P2P1M11M12M21M22M23M31M32M33M34101286911107697511468643776534k=1k=2k=3k=4图13105637610min)(2133Mxf选择M32由结点M22到达下一阶段也有三条路线可以选择，即选择M31、M32或M33；故：10553769min)(2233Mxf选择M32或M33由结点M23到达下一阶段也有三条路线可以选择，即选择M32、M33或M34；故：93654311min)(2333Mxf选择M33或M34当2k时：由结点M11到达下一阶段有两条路线可以选择，即选择M21或M22；故：16106108min)(1122Mxf选择M22由结点M12到达下一阶段也有两条路线可以选择，即选择M22或M23；故：19911109min)(1222Mxf选择M22当1k时：由结点C到达下一阶段有两条路线可以选择，即选择M11或M12；故：2819101612min)(11Cxf选择M11从而通过顺序（计算的反顺序）追踪（黑体标示）可以得到两条最佳的输运线路：C—M11—M22—M32—P2；C—M11—M22—M33—P3。最短的输送距离是280千米。一个多阶段决策过程最优化问题的动态规划模型通常包含以下要素。1、阶段阶段是过程中需要做出决策的决策点。描述阶段的变量称为阶段变量，常用k来表示。阶段的划分一般是根据时间和空间的自然特征来进行的，但要便于将问题的过程转化为多阶段决策的过程。阶段变量一般用nk,,2,1表示。42、状态状态（state）表示每个阶段开始时过程所处的自然状况。它应能描述过程的特征并且无后效性，即当某阶段的状态变量给定时，这个阶段以后过程的演变与该阶段以前各阶段的状态无关。通常还要求状态是直接或间接可以观测的。描述状态的变量称状态变量（statevariable）。变量允许取值的范围称允许状态集合(setofadmissiblestates)。用kx表示第k阶段的状态变量，它可以是一个数或一个向量。用kD表示第k阶段的允许状态集合。n个阶段的决策过程有1n个状态变量，1nx表示nx演变的结果。根据过程演变的具体情况，状态变量可以是离散的或连续的。为了计算的方便有时将连续变量离散化；为了分析的方便有时又将离散变量视为连续的。状态变量简称为状态。3决策当一个阶段的状态确定后，可以作出各种选择从而演变到下一阶段的某个状态，这种选择手段称为决策（decision），在最优控制问题中也称为控制（control）。描述决策的变量称决策变量（decisionvariable），变量允许取值的范围称允许决策集合（setofadmissibledecisions）。用)(kkxu表示第k阶段处于状态kx时的决策变量，它是kx的函数，用)(kkuU表示ku的允许决策集合。决策变量简称决策。4策略决策组成的序列称为策略（policy）。由初始状态1x开始的全过程的策略记作)(11xpn，即)}(,),(),({)(221111nnnxuxuxuxp.由第k阶段的状态kx开始到终止状态的后部子过程的策略记作)(kknxp，即)}(,),({)(nnkkkknxuxuxp，1,,2,1nk.类似地，由第k到第j阶段的子过程的策略记作)}(,),({)(jjkkkkjxuxuxp.可供选择的策略有一定的范围，称为允许策略集合(setofadmissiblepolicies)，用)(),(),(11kkjkknnxPxPxP表示。5.状态转移方程在确定性过程中，一旦某阶段的状态和决策为已知，下阶段的状态便完全确定。用状态转移方程（equationofstatetransition）表示这种演变规律，写作.,,2,1),,(1nkuxTxkkk（1）6.指标函数和最优值函数指标函数(objectivefunction)是衡量过程优劣的数量指标，它是定5义在全过程和所有后部子过程上的数量函数，用),,,,(11nkkkknxxuxV表示，nk,,2,1。指标函数应具有可分离性，即knV可表为nkkkVux1,,的函数，记为)),,,(,,(),,,,(1211111nkkknkkkknkkkknxxuxVuxxxuxV并且函数k对于变量nkV1是严格单调的。过程在第j阶段的阶段指标取决于状态jx和决策ju，用),(jjjuxv表示。指标函数由),,2,1(njvj组成，常见的形式有：阶段指标之和，即nkjjjjnkkkknuxvxxuxV),(),,,,(11，阶段指标之积，即nkjjjjnkkkknuxvxxuxV),(),,,,(11，阶段指标之极大（或极小），即),((min)max),,,,(11jjjnjknkkkknuxvxxuxV.这些形式下第k到第j阶段子过程的指标函数为),,,(11jkkkkjxxuxV。根据状态转移方程指标函数knV还可以表示为状态kx和策略knp的函数，即),(knkknpxV。在kx给定时指标函数knV对knp的最优值称为最优值函数（optimalvaluefunction），记为)(kkxf，即),(opt)()(knkknxPpkkpxVxfkknkn，其中opt可根据具体情况取max或min。7最优策略和最优轨线使指标函数knV达到最优值的策略是从k开始的后部子过程的最优策略，记作},,{***nkknuup。*1np是全过程的最优策略，简称最优策略（optimalpolicy）。从初始状态)(*11xx出发，过程按照*1np和状态转移方程演变所经历的状态序列},,,{*1*2*1nxxx称最优轨线（optimaltrajectory）。二、基本方程：对于n阶段的动态规划问题，在求子过程上的最优指标函数时，k子过程与1k子过程有如下递推关系：cxfnkxfuxvxfnnkkkkkuUukkkkk)(1,,)},(),({opt)(1111)(（2）在上述方程中，当为加法时取0)(11knxf；当为乘法时，取1)(11knxf。三、最优化原理动态规划的最优化原理是美国学者R．Bellman首先提出的，其表述如下：6“作为整个过程的最优策略应具有这样的性质，无论过去的状态和决策如何，对于前面的决策所形成的状态而言，余下的诸决策必须构成最优策略”．也就是说最优策略的任一子策略都是最优的．最优化原理还阐述这样一个事实，对全过程的任一状态点kx，我们不考虑kx以前的决策，只保证kx以后的决策是最优的。显然，由于k的任意性（k=1，2，…，n）就保证了全过程的决策是最优的．最优化原理为动态规划从最后阶段的优化开始，逐步向前一阶段优化扩展直至第一阶段，从而达到全程优化的方法奠定了理论基础．§2动态规划模型的建立与求解根据动态规划的概念不难看出，在用动态规划方法解决实际问题时，必须首先明确本问题中的阶段、状态、决策、策略以及考察指标，并建立状态转移方程，然后根据k阶段最优指标的大小找出与之对应的最优子策略，直至找出问题的最优解．我们把找出实际问题中的阶段、状态、决策、策略以及考察指标，并建立状态转移方程这一过程称为建立动态规划模型．应该说建立动态规划模型是解决动态规划问题的第一步，也是非常重要的一步．模型建立的是否简捷、准确，直接关系到问题最优解的筛选及准确性，因此，建立动态规划模型是十分重要的．其步骤可归纳如下：（1）将所要解决的问题恰当地划分为若干阶段，经常是按事物发展的时间和空间来划分不同阶段，各阶段的首尾要互相衔接；（2）正确地选择状态变量kx，确定它在每一阶段的取值范围；这一步是形成动态模型的关键，状态变量kx是动态规划模型中最重要的参数。一般来说，状态变量kx应该具有以下三个特征：①要能够用来描述决策过程的演变特征；②满足无后效性，即若某阶段状态已经给定后，则以后过程的进展不受以前各个状态的影响，也就是说，过去的历史只通过当前的状态去影响未来的发展；③递推性，即由k阶段的状态变量kx及决策变量ku可以计算出1k阶段的状态变量1kx（3）选择决策变量ku，确定允许决策集合)(kkuD。（4）正确写出状态转移方程.,,2,1),,(1nkuxTxkkk（5）建立指标函数，一般用),(kkkuxr描述阶段效应，)(kkxf表示从nk阶段的最优子策略函数.（6）建立动态规划基本方程。对每一对kx，)(kkxu计算不同指标值7)())(,(11kkkkkkxfxuxr．把这些指标值进行比较取出最优的一个，所谓最优是根据实际问题的需要确定指标值的最大者或最小者，即1,,1,)()}())(,()(1111)(nnkcxfxfxuxroptxfnnkkkkkkuDukkkkk在动态规划基本方程中，))(,(kkkkxuxr，.,,2,1),,(1nkuxTxkkk都是已知函数，最优子策略)(kkxf与)(11kkxf之间是递推关系，要求出)(kkxf及)(kkxu需