《数学模型动态规划.doc》由会员分享，可在线阅读，更多相关《数学模型动态规划.doc（27页珍藏版）》请在金锄头文库上搜索。
1、精品文档动态规划动态规划(dynamic programming)是运筹学的一个重要分支，它是解决多阶段决策问题的一种有效的数量化方法动态规划是由美国学者贝尔曼(RBellman）等人所创立的1951年贝尔曼首先提出了动态规划中解决多阶段决策问题的最优化原理，并给出了许多实际问题的解法1957年贝尔曼发表了动态规划一书，标志着运筹学这一重要分支的诞生1动态规划的概念与原理一、动态规划的基本概念引例: 最短路线问题美国黑金石油公司（The Black Gold Petroleum Company）最近在阿拉斯加（Alaska）的北斯洛波（North Slope）发现了大的石油储量。为了大规模开发
2、这一油田，首先必须建立相应的输运网络，使北斯洛波生产的原油能运至美国的3个装运港之一。在油田的集输站（结点C）与装运港（结点P1、P2、P3）之间需要若干个中间站，中间站之间的联通情况如图1所示，图中线段上的数字代表两站之间的距离（单位：10千米）。试确定一最佳的输运线路，使原油的输送距离最短。解：最短路线有一个重要性质，即如果由起点A经过B点和C点到达终点D是一条最短路线，则由B点经C点到达终点D一定是B到D的最短路（贝尔曼最优化原理）。此性质用反证法很容易证明，因为如果不是这样，则从B点到D点有另一条距离更短的路线存在，不妨假设为BPD；从而可知路线ABPD比原路线ABCD距离短，这与原路
3、线ABCD是最短路线相矛盾，性质得证。根据最短路线的这一性质，寻找最短路线的方法就是从最后阶段开始，由后向前逐步递推求出各点到终点的最短路线，最后求得由始点到终点的最短路；即动态规划的方法是从终点逐段向始点方向寻找最短路线的一种方法。按照动态规划的方法，将此过程划分为4个阶段，即阶段变量；取过程在各阶段所处的位置为状态变量，按逆序算法求解。CP3P2P1M11M12M21M22M23M31M32M33M34101286911107697511468643776534k=1k=2k=3k=4图1 当时：由结点M31到达目的地有两条路线可以选择，即选择P1或P2；故： 选择P2由结点M32到达目的
4、地有三条路线可以选择，即选择P1、P2或P3；故： 选择P2由结点M33到达目的地也有三条路线可以选择，即选择P1、P2或P3；故： 选择P3由结点M34到达目的地有两条路线可以选择，即选择P2或P3；故： 选择P2当时：由结点M21到达下一阶段有三条路线可以选择，即选择M31、M32或M33；故： 选择M32由结点M22到达下一阶段也有三条路线可以选择，即选择M31、M32或M33；故： 选择M32或M33由结点M23到达下一阶段也有三条路线可以选择，即选择M32、M33或M34；故： 选择M33或M34当时：由结点M11到达下一阶段有两条路线可以选择，即选择M21或M22；故： 选择M22
5、由结点M12到达下一阶段也有两条路线可以选择，即选择M22或M23；故： 选择M22当时：由结点C到达下一阶段有两条路线可以选择，即选择M11或M12；故： 选择M11从而通过顺序（计算的反顺序）追踪（黑体标示）可以得到两条最佳的输运线路：CM11M22M32P2；CM11M22M33P3。最短的输送距离是280千米。一个多阶段决策过程最优化问题的动态规划模型通常包含以下要素。1、阶段阶段是过程中需要做出决策的决策点。描述阶段的变量称为阶段变量，常用k来表示。阶段的划分一般是根据时间和空间的自然特征来进行的，但要便于将问题的过程转化为多阶段决策的过程。阶段变量一般用表示。2、状态状态（stat
6、e）表示每个阶段开始时过程所处的自然状况。它应能描述过程的特征并且无后效性，即当某阶段的状态变量给定时，这个阶段以后过程的演变与该阶段以前各阶段的状态无关。通常还要求状态是直接或间接可以观测的。描述状态的变量称状态变量（state variable）。变量允许取值的范围称允许状态集合(set of admissible states)。用表示第阶段的状态变量，它可以是一个数或一个向量。用表示第阶段的允许状态集合。个阶段的决策过程有个状态变量，表示演变的结果。根据过程演变的具体情况，状态变量可以是离散的或连续的。为了计算的方便有时将连续变量离散化；为了分析的方便有时又将离散变量视为连续的。状态变
7、量简称为状态。3 决策当一个阶段的状态确定后，可以作出各种选择从而演变到下一阶段的某个状态，这种选择手段称为决策（decision），在最优控制问题中也称为控制（control）。描述决策的变量称决策变量（decision variable），变量允许取值的范围称允许决策集合（set of admissible decisions）。用表示第阶段处于状态时的决策变量，它是的函数，用表示的允许决策集合。决策变量简称决策。4 策略决策组成的序列称为策略（policy）。由初始状态开始的全过程的策略记作，即.由第阶段的状态开始到终止状态的后部子过程的策略记作，即，.类似地，由第到第阶段的子过程的策略
8、记作.可供选择的策略有一定的范围，称为允许策略集合(set of admissible policies)，用表示。5. 状态转移方程在确定性过程中，一旦某阶段的状态和决策为已知，下阶段的状态便完全确定。用状态转移方程（equation of state transition）表示这种演变规律，写作 （1）6. 指标函数和最优值函数指标函数(objective function)是衡量过程优劣的数量指标，它是定义在全过程和所有后部子过程上的数量函数，用表示，。指标函数应具有可分离性，即可表为的函数，记为并且函数对于变量是严格单调的。过程在第阶段的阶段指标取决于状态和决策，用表示。指标函数由组成
9、，常见的形式有：阶段指标之和，即 ，阶段指标之积，即 ，阶段指标之极大（或极小），即.这些形式下第到第阶段子过程的指标函数为。根据状态转移方程指标函数还可以表示为状态和策略的函数，即。在给定时指标函数对的最优值称为最优值函数（optimal value function），记为，即，其中可根据具体情况取或。7 最优策略和最优轨线使指标函数达到最优值的策略是从开始的后部子过程的最优策略，记作。是全过程的最优策略，简称最优策略（optimal policy）。从初始状态出发，过程按照和状态转移方程演变所经历的状态序列称最优轨线（optimal trajectory）。二、基本方程：对于阶段的动态规
10、划问题，在求子过程上的最优指标函数时，子过程与子过程有如下递推关系： （2）在上述方程中，当为加法时取；当为乘法时，取。三、最优化原理动态规划的最优化原理是美国学者RBellman首先提出的，其表述如下：“作为整个过程的最优策略应具有这样的性质，无论过去的状态和决策如何，对于前面的决策所形成的状态而言，余下的诸决策必须构成最优策略”也就是说最优策略的任一子策略都是最优的最优化原理还阐述这样一个事实，对全过程的任一状态点，我们不考虑以前的决策，只保证以后的决策是最优的。显然，由于k 的任意性（k =1，2，n）就保证了全过程的决策是最优的最优化原理为动态规划从最后阶段的优化开始，逐步向前一阶段优
11、化扩展直至第一阶段，从而达到全程优化的方法奠定了理论基础2动态规划模型的建立与求解根据动态规划的概念不难看出，在用动态规划方法解决实际问题时，必须首先明确本问题中的阶段、状态、决策、策略以及考察指标，并建立状态转移方程，然后根据k 阶段最优指标的大小找出与之对应的最优子策略，直至找出问题的最优解我们把找出实际问题中的阶段、状态、决策、策略以及考察指标，并建立状态转移方程这一过程称为建立动态规划模型应该说建立动态规划模型是解决动态规划问题的第一步，也是非常重要的一步模型建立的是否简捷、准确，直接关系到问题最优解的筛选及准确性，因此，建立动态规划模型是十分重要的其步骤可归纳如下：（1）将所要解决的
12、问题恰当地划分为若干阶段，经常是按事物发展的时间和空间来划分不同阶段，各阶段的首尾要互相衔接；（2）正确地选择状态变量，确定它在每一阶段的取值范围；这一步是形成动态模型的关键，状态变量是动态规划模型中最重要的参数。一般来说，状态变量应该具有以下三个特征： 要能够用来描述决策过程的演变特征；满足无后效性，即若某阶段状态已经给定后，则以后过程的进展不受以前各个状态的影响，也就是说，过去的历史只通过当前的状态去影响未来的发展；递推性，即由k 阶段的状态变量及决策变量可以计算出阶段的状态变量（3）选择决策变量，确定允许决策集合。（4）正确写出状态转移方程（5）建立指标函数，一般用描述阶段效应，表示从阶
13、段的最优子策略函数.（6）建立动态规划基本方程。对每一对，计算不同指标值把这些指标值进行比较取出最优的一个，所谓最优是根据实际问题的需要确定指标值的最大者或最小者，即 在动态规划基本方程中，都是已知函数，最优子策略与之间是递推关系，要求出及需要先求出，这就决定了用在动态规划基本方程求最优策略是逆着阶段的顺序进行的，由 k = n ，n 1，2，1将上式依次逐步递推，直至全过程的优化结束，即可求出动态规划问题的最优策略及最优指标值称为动态规划的逆序算法。第三节 动态规划方法应用一、机器负荷分配问题例1：某厂新购某种机床125台，据估计，这种设备5年后将被其他设备所代替，此机床如在高负荷状态下工作
14、，年损坏率为，年利润为10万元；如在低负荷状态下工作，年损坏率为，年利润为6万元；问应该如何安排这些机床的生产负荷，才能使5年内获得最大的利润？解：以年为阶段，k =1，2，3，4，5取k年初完好的机床数为状态变量，以k年初投入高负荷运行的机床数为决策变量，则低负荷运行的机床数为，于是状态转移方程为：以利润为目标函数，则k年利润为：记 表示从年至5年末的最大总利润。则动态规划基本方程为：下面具体求解注意到动态规划基本方程所以时当时当时当时当时即第一年到第5年末的最大利润为。在按与计算过程相反的顺序推回去，可得最优计划为年份k完好机床数高负荷机床数低负荷机床数第一年1250125第二年1000100第三年80080第四年64640第五年32320即前三年全部低负荷运转，后两年全部高负荷运转，最大利润为2790万元。二、资源分配问题所谓资源分配问题，就是将一定数量的一种或若干种资源（如原材料、机器设备、资金、劳动力等）恰当地分配给若干个使用者，以使资源得到最有效地利用。1、一维分配问题 设有某种资源可用于项活动，假设资源的数量为，已知用于第项活动的资源数为时，可以得到的收益为，试确定资源的分
