数学模型动态规划

1、精品动态规划动态规划 (dynamicprogramming)是运筹学的一个重要分支，它是解决多阶段决策问题的一种有效的数量化方法动态规划是由美国学者贝尔曼(R Bellman）等人所创立的 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 点有另一条

3、距离更短的路线存在， 不妨假设为 B P D ；从而可知路线 A B P D 比原路线 A B C D 距离短，这与原路线 A B C D 是最短路线相矛盾，性质得证。根据最短路线的这一性质， 寻找最短路线的方法就是从最后阶段开始， 由后向前逐步递推求出各点到终点的最短路线，最后求得由始点到终点的最短感谢下载载精品路；即动态规划的方法是从终点逐段向始点方向寻找最短路线的一种方法。 按照动态规划的方法，将此过程划分为 4 个阶段，即阶段变量 k 1,2,3,4 ；取过程在各阶段所处的位置为状态变量 xk ，按逆序算法求解。M 31810P1M 2176864M 11M 323126977CM 2

4、2P2796105M 33M 12115114P3M 23634M 34k=1k=2k=3k=4图 1当 k 4 时：由结点 M 31 到达目的地有两条路线可以选择，即选择P1 或 P2 ；故：8f 4 (x4M 31 )min6选择 P26由结点 M 32 到达目的地有三条路线可以选择，即选择P1 、P2 或 P3；故：感谢下载载精品4f 4 (x4M 32)min33选择 P27由结点 M 33到达目的地也有三条路线可以选择，即选择P1、P2 或 P3；故：7f 4 (x4M 33)min65选择 P35由结点 M 34 到达目的地有两条路线可以选择，即选择P2或 P3；故：f 4 (x4

5、M34)min33选择 P24当 k 3时：由结点 M 21到达下一阶段有三条路线可以选择，即选择M 31、M 32 或M 33 ；故：106f3 (x3 M 21 ) min7310选择 M3265由结点 M 22到达下一阶段也有三条路线可以选择，即选择M 31、M 32 或M 33 ；故：96f 3 ( x3 M 22 )min 7310选择M32或M3355由结点 M 23到达下一阶段也有三条路线可以选择，即选择M 32、M 33 或M 34 ；故：113f3 (x3 M 23 )min 459选择 M33或 M3463当 k 2 时：由结点 M 11 到达下一阶段有两条路线可以选择，即

6、选择 M 21 或 M 22 ；故：f 2 ( x2810M 11 ) min16 选择 M22610感谢下载载精品由结点 M 12 到达下一阶段也有两条路线可以选择，即选择M 22 或 M 23 ；故：f 2 (x2M12 )910选择 M22min19119当 k1 时：由结点 C 到达下一阶段有两条路线可以选择，即选择M 11 或 M 12；故：f1 (x1C)1216选择 M11min281019从而通过顺序（计算的反顺序）追踪（黑体标示）可以得到两条最佳的输运线路： C M 11M 22 M 32 P2； CM 11 M 22 M 33 P3。最短的输送距离是 280 千米。一个多阶

7、段决策过程最优化问题的动态规划模型通常包含以下要素。1 、阶段阶段是过程中需要做出决策的决策点。 描述阶段的变量称为阶段变量， 常用 k 来表示。阶段的划分一般是根据时间和空间的自然特征来进行的，但要便于将问题的过程转化为多阶段决策的过程。阶段变量一般用 k 1,2, ,n 表示。2 、状态状态（ state ）表示每个阶段开始时过程所处的自然状况。它应能描述过程的特征并且无后效性， 即当某阶段的状态变量给定时， 这个阶段以后过程的演变与该阶段以前各阶段的状态无关。 通常还要求状态是直接或间接可以观测的。描述状态的变量称状态变量（statevariable）。变量允许取值的范围称允许状态集合

8、(set of admissible states)。用 xk 表示第 k 阶段的状态变量，它可以是一个数或一个向量。用D k 表示第 k 阶段的允许状态集合。n 个阶段的决策过程有n1 个状态变量， xn 1 表示 xn 演变的结果。根据过程演变的具体情况， 状态变量可以是离散的或连续的。为了计算的方便感谢下载载精品有时将连续变量离散化； 为了分析的方便有时又将离散变量视为连续的。 状态变量简称为状态。3 决策当一个阶段的状态确定后， 可以作出各种选择从而演变到下一阶段的某个状态，这种选择手段称为决策（ decision ），在最优控制问题中也称为控制（control）。描述决策的变量称决策

9、变量 （decision variable），变量允许取值的范围称允许决策集合（set of admissible decisions）。用 uk ( x k ) 表示第 k 阶段处于状态 xk 时的决策变量，它是 xk 的函数，用 U k (uk ) 表示 uk 的允许决策集合。决策变量简称决策。4 策略决策组成的序列称为策略（policy ）。由初始状态 x1 开始的全过程的策略记作p1n ( 1 ) ，即1n ( 1 )1 (1 ),2(2 ),n (n ).xp xuxuxux由第 k 阶段的状态 xk 开始到终止状态的后部子过程的策略记作pkn ( xk ) ，即pkn ( xk )

10、 uk ( xk ), un (xn ) ， k1,2, n1.类似地，由第 k 到第 j 阶段的子过程的策略记作pkj (xk ) uk ( xk ),u j ( x j ) .可供选择的策略有一定的范围，称为允许策略集合(setofadmissiblepolicies) ，用 P1n ( x 1 ), Pkn ( x k ), Pkj ( x k) 表示。5. 状态转移方程在确定性过程中， 一旦某阶段的状态和决策为已知，下阶段的状态便完全确定。用状态转移方程（ equation of state transition ）表示这种演变规律，写作xk 1T (xk , uk ),k1,2, n

11、.（1 ）6.指标函数和最优值函数指标函数 (objective function)是衡量过程优劣的数量指标， 它是定义在全过程和所有后部子过程上的数量函数，用Vkn (xk , uk , xk 1 , xn 1 ) 表示，k1,2,n 。指标函数应具有可分离性，即Vkn 可表为 xk , uk ,Vk 1n 的函数，记感谢下载载精品为Vkn ( xk , uk , xk 1 , xn 1 )k (xk , uk ,Vk 1n ( xk 1 ,uk 1, xk 2 , xn 1 )并且函数k 对于变量 Vk 1 n 是严格单调的。过程在第 j阶段的阶段指标取决于状态 x j和决策 u j ，用

12、 v j ( x j ,u j) 表示。指标函数由 v j ( j1,2,n) 组成，常见的形式有：n阶段指标之和，即Vkn (xk ,uk , xk 1 , , xn 1 )v j ( x j , u j ) ，j kn阶段指标之积，即Vkn ( xk ,uk , xk 1, xn 1 )v j ( x j ,u j ) ，jk阶段指标之极大（或极小） ，即Vkn( xk , uk , xk 1 , , xn 1 ) max(min) v j ( x j ,u j ) .k jn这些形式下第 k 到第 j 阶段子过程的指标函数为 Vkj ( xk , uk , xk 1 , x j1 ) 。

13、根据状态转移方程指标函数Vkn 还可以表示为状态 xk和策略 pkn 的函数，即Vkn ( xk , pkn ) 。 在 xk 给 定时指 标函 数 Vkn 对 pkn 的最优值称为最 优值 函数（optimal value function），记为 fk ( xk ) ，即fk ( xk )opt Vkn ( xk , pkn ) ，pkn Pkn ( xk )其中 opt 可根据具体情况取max 或 min 。7 最优策略和最优轨线使指标函数 Vkn 达到最优值的策略是从k 开始的后部子过程的最优策略，记作 pkn* uk* , un* 。 p1n* 是全过程的最优策略， 简称最优策略（o

14、ptimalpolicy ）。从初始状态 x1( x1* ) 出发，过程按照 p1n*和状态转移方程演变所经历的状态序列 x1* , x2* , xn*1 称最优轨线（ optimal trajectory）。二、基本方程：对于 n 阶段的动态规划问题，在求子过程上的最优指标函数时，k 子过程与 k 1子过程有如下递推关系：f k ( xk )optvk ( xk , uk ) f k 1 ( xk1 ), kn, ,1（ 2）uk U k ( uk )f n 1 ( xn 1 )c在上述方程中，当为加法时取 fn 1 ( xk 1 )0 ；当为乘法时，取 f n 1 ( xk 1 ) 1。三

15、、最优化原理感谢下载载精品动态规划的最优化原理是美国学者R Bellman首先提出的，其表述如下：“作为整个过程的最优策略应具有这样的性质，无论过去的状态和决策如何，对于前面的决策所形成的状态而言，余下的诸决策必须构成最优策略” 也就是说最优策略的任一子策略都是最优的最优化原理还阐述这样一个事实，对全过程的任一状态点xk ，我们不考虑 xk 以前的决策， 只保证 xk 以后的决策是最优的。 显然，由于 k 的任意性（k =1 ， 2 ， ， n ）就保证了全过程的决策是最优的最优化原理为动态规划从最后阶段的优化开始， 逐步向前一阶段优化扩展直至第一阶段， 从而达到全程优化的方法奠定了理论基础&

16、#167;2 动态规划模型的建立与求解根据动态规划的概念不难看出，在用动态规划方法解决实际问题时，必须首先明确本问题中的阶段、状态、决策、策略以及考察指标，并建立状态转移方程，然后根据k 阶段最优指标的大小找出与之对应的最优子策略，直至找出问题的最优解我们把找出实际问题中的阶段、状态、决策、策略以及考察指标，并建立状态转移方程这一过程称为建立动态规划模型应该说建立动态规划模型是解决动态规划问题的第一步，也是非常重要的一步 模型建立的是否简捷、准确，直接关系到问题最优解的筛选及准确性，因此，建立动态规划模型是十分重要的其步骤可归纳如下：（1 ）将所要解决的问题恰当地划分为若干阶段，经常是按事物发

17、展的时间和空间来划分不同阶段，各阶段的首尾要互相衔接；（2 ）正确地选择状态变量xk ，确定它在每一阶段的取值范围；这一步是形成动态模型的关键，状态变量xk 是动态规划模型中最重要的参数。一般来说，状态变量 xk 应该具有以下三个特征：要能够用来描述决策过程的演变特征；满足无后效性，即若某阶段状态已经给定后，则以后过程的进展不受以前各个状态的影响，也就是说，过去的历史只通过当前的状态去影响未来的感谢下载载精品发展；递推性，即由 k 阶段的状态变量 xk 及决策变量 uk 可以计算出 k1 阶段的状态变量 xk 1（ 3）选择决策变量 uk ，确定允许决策集合 D k (uk ) 。, .（ 4

18、）正确写出状态转移方程xk 1(k ,k ),k1,2,T xun（ 5）建立指标函数，一般用rk ( xk ,uk ) 描述阶段效应， f k ( xk ) 表示从 kn 阶段的最优子策略函数 .（ 6 ）建 立 动态 规 划 基本 方程 。 对 每 一 对 xk ， uk ( xk ) 计 算 不 同指 标 值rk (xk ,uk ( xk )f k 1 ( xk 1 ) 把这些指标值进行比较取出最优的一个，所谓最优是根据实际问题的需要确定指标值的最大者或最小者，即f k ( xk )optrk ( xk ,uk ( xk )f k 1 ( xk 1 )uk D k (uk )f n 1

19、( xn 1 ) c kn, n 1, ,1在动态规划基本方程中，rk (xk ,uk ( xk ) ， xk 1T ( xk ,uk ), k 1,2, , n.都是已知函数，最优子策略 f k ( xk ) 与 f k 1 ( xk 1 ) 之间是递推关系，要求出 f k ( xk ) 及 uk ( xk ) 需要先求出 f k 1 ( xk 1 ) ，这就决定了用在动态规划基本方程求最优策略是逆着阶段的顺序进行的，由 k = n ， n 1， 2 ，1 将上式依次逐步递推，直至全过程的优化结束， 即可求出动态规划问题的最优策略及最优指标值 称为动态规划的逆序算法。第三节动态规划方法应用一

20、、机器负荷分配问题例 1 ：某厂新购某种机床125 台，据估计，这种设备5 年后将被其他设备所代替，此机床如在高负荷状态下工作，年损坏率为1 ，年利润为 10 万元；2如在低负荷状态下工作，年损坏率为1 ，年利润为 6 万元；问应该如何安5排这些机床的生产负荷，才能使5 年内获得最大的利润？感谢下载载精品解：以年为阶段， k =1 ，2 ， 3， 4， 5取 k 年初完好的机床数为状态变量xk ，以 k 年初投入高负荷运行的机床数为决策变量 uk ，则低负荷运行的机床数为 xk u k ，于是状态转移方程为：xk 11 uk 4 (xk uk ) 0.8xk 0.3uk2 5以利润为目标函数，

21、则 k 年利润为：10uk6( xkuk )4uk6xk记 f k ( xk ) 表示从 k 年至 5 年末的最大总利润。则动态规划基本方程为：fk ( xk )max4uk6xkf k 1( xk1 )0ukx kxk1 0.8xk0.3ukx1125, x60f6 ( x6 )0k5,4,1下面具体求解注意到动态规划基本方程f k ( xk )max4uk6xk fk 1 (0.8xk0.3uk )0 uk xk所以 k5时f 5 ( x5 )max4u56x5f6 (x6 )10x5u5 x50u5x5当 k4 时f 4 ( x4 )max4u46x4f 5 (0.8x4 0.3u4 )

22、0u4x4max4u46x410(0.8x40.3u4 )0u4x4max u414x40u4x415x4u4x4当 k3时感谢下载载精品f 3 ( x3 )max4u3 6x3f 4 (0.8x3 0.3u3 )0 u3 x3max4u36x315(0.8x30.3u3 )0u3x3max0.5u318x30u3x318x3u30当 k2 时f 2 ( x2 )max4u26x2f3 (0.8x20.3u2 )0u 2 x2max4u26x218(0.8x20.3u2 )0u2x2max1.4u220.4x2 0u2x220.4x2u20当 k1 时f1( x1)max 4u16x1f2 (

23、0.8x10.3u1 )0 u1 x1max 4u16x120.4(0.8x10.3u1 )0u1 x1max2.12u122.32x10 u1x122.32x1万元)u1 022.32 125 2790(即第一年到第 5 年末的最大利润为 22.32 x1 ,而 x1125 。在按与计算过程相反的顺序推回去，可得最优计划为年份完好机床数高负荷机床数低负荷机床数kxk 1 0.8xk 0.3ukukxk uk第一年1250125第二年1000100第三年80080第四年64640感谢下载载精品第五年32320即前三年全部低负荷运转，后两年全部高负荷运转，最大利润为2790 万元。二、资源分配问

24、题所谓资源分配问题， 就是将一定数量的一种或若干种资源 （如原材料、机器设备、资金、劳动力等）恰当地分配给若干个使用者，以使资源得到最有效地利用。1 、一维分配问题设有某种资源可用于n 项活动，假设资源的数量为a ，已知用于第 i 项活动的资源数为 xi 时，可以得到的收益为gi ( xi )(i1,2,n) ，试确定资源的分配方案使收益最大？该问题的数学模型可以表示为max Zg1 (x1 )g2 ( x2 )gn (xn )s.t.x1x2xnax1, x2 , xn0当 gi ( xi )(i1,2, n) 为 线 性 函 数 时 ， 该 问 题 是 线 性 规 划 问 题 ， 当gi

25、( xi )(i1,2, n) 为非线性函数时， 该问题是非线性规划问题， 如果采用非线性规划求解，比较麻烦。可以将它看成多阶段决策问题， 利用动态规划求解。感谢下载载精品在应用动态规划方法处理这一类问题时，提出将资源分配给每项活动的过程看成一个阶段， 每个阶段都要确定对一种活动的资源投放量， 这时，状态变量 xk 可以选择 k 阶段初所拥有的资源量， 即 xk 是要在第 k 项到第 n 项活动间分配的资源量。决策变量uk 选择对活动k 的资源投放量，决策变量uk 的允许集合为0ukxk 。在选取上述状态变量和决策变量的情况下，状态转移方程为：xk 1xk uk去投放资源时的收益为指标函数，则

26、g k (uk )为阶段效益指标。记 f k ( xk ) 表示从 k 阶段至 n 阶段的最大总利润。则动态规划基本方程为：fk (xk )maxgk (uk） fk 1(xk 1)0uk xkfn 1(xn 1) 0k n, n 1, ,1例 2 ：某公司拟将 500 万元的资本投入所属的甲、乙、丙三个工厂进行技术改造，各工厂获得投资后年利润将有相应的增长，增长额如表 1 所示。试确定 500 万元资本的分配方案，以使公司总的年利润增长额最大。表 1投资额100 万元200 万元300 万元400 万元500 万元甲307090120130乙50100110110110丙4060110120

27、120解：将问题按工厂分为三个阶段k1,2,3，设状态变量xk （ k1,2,3 ）代感谢下载载精品表从第 k 个工厂到第3 个工厂的投资额，决策变量额。于是有状态转移方程为xk 1xkDk (uk ) uk | 0 ukxk 和递推关系式：f k ( xk )max gk (uk ) f k 1( xkuk )0 u k xkf4 (x4 )0uk 代表第 k 个工厂的投资 uk 、 允 许 决 策 集 合( k3,2,1)当 k3时：f3(x3 )max g3 (u3 ) 0max g3 (u3 )0 u3 x30 u 3 x3于是有表 2 ，表中 u3表示第三个阶段的最优决策。表 2（单

28、位：百万元）x3012345u3012345f 3 ( x3 )00.40.61.11.21.2当 k2 时：f 2( x2 ) max g2 (u2 ) f 3 ( x2 u2 )0 u2 x2于是有表 3 。表 3（单位：百万元）u 2g2 (u2 )f 3( x2 u2 )f2 (x2 )u2x201234500+00010+0.40.5+00.5120+0.60.5+0.41.0+01.0230+1.10.5+0.61.0+0.41.1+01.4240+1.20.5+1.11.0+0.61.1+0.41.1+01.61 ，250+1.20.5+1.21.0+1.11.1+0.61.1+

29、0.41.1+02.12当 k1 时：感谢下载载精品f1(x1) max g1 (u1) f2 (x1 u1 )0 u1 x1于是有表 4 。表 4u 1g1 (u1)f 2 ( x1 u1 )f1 ( x1 )u1x 101234550+2.10.3+1.60.7+1.40.9+1.01.2+0.51.3+02.10 ，2然后按计算表格的顺序反推算，可知最优分配方案有两个：（1 ）甲工厂投资 200 万元，乙工厂投资 200 万元，丙工厂投资 100 万元；（ 2）甲工厂没有投资，乙工厂投资 200 万元，丙工厂投资 300 万元。按最优分配方案分配投资（资源），年利润将增长 210 万元。

30、这个例于是决策变量取离散值的一类分配问题， 在实际问题中， 相类似的问题还有销售店的布局（分配）问题、设备或人力资源的分配问题等。2 、二维分配问题（ 1 ）设数量分别为 a, b 的两种资源分配给 n 个使用者，xi 分配第一种资源给第i 个使用者的数量，yi 分配第二种资源给第i 个使用者的数量，ri ( xi , yi ) 第 i 个阶段的收益，i 1,2, , n求总收益最大的分配方案nZmaxri ( xi , yi )i1nxia该问题的数学模型可以表示为i1nyibi1xi0 ,yi 0 , i 1,2, , n（2 ）二维分配问题的解法感谢下载载精品1 、逐次逼近法nZmaxr

31、i (xi , yi )i 1nxia由于i1nyibi1xi0 ,yi 0 , i 1,2, , n设nX (0)( x1(0) , x2(0 ) , , xn(0 ) ), 满足xi ai1xi0固定 x于 X ( 0) ,求下列一维问题的nmaxri ( x(i0 ) , yi )i1nyibi 1yi0 ,i1,2, n得最优解Y (0)( y1( 0) , y2(0) , , yn(0 ) ), 固定 y于 Y (0) ,求下列一维问题的n( 0)maxri (xi , y)ii 1nxiai 1xi0 , i1,2, , n得最优解X (1)( x1(1) , x2(1) , x(

32、n1) ), 固定 x于 X (1) ,求下列一维问题的感谢下载载精品nmaxri ( x(i1) , yi )i1nyibi 1yi0 ,i1,2, n得最优解Y (1)( y1(1) , y2(1) , yn(1) ),轮转若干步，直到满足精确度要求。2 、拉格郎日乘子法（1 ）估计一个拉格郎日乘子0（2 ）用动态规划法解一维问题nnmaxri ( xi , yi )yi i1i1nxiai1xi 0 ,yi0 ,i1,2, n若解不唯一，假设共有 m 个( x(1) ( ), y(1) (), ( x( 2) (), y( 2) ( ), (x(m ) (), y( m) ( )x(1)

33、 ( )(x(1) (), x(1)(), x(1)( )T , y(1) ( )( y(1)(), y(1)( ), y(1)( )T12n12nn（3）计算 F( )minyi( j ) ()j1,2,mj1inyi( j ) (G()max)j1,2, mji 1（4 ）判断n( k )(k ) ( k) ( )为最优解若存在jk, .b,则 (x),ys tyii1若 F()b,则增大, 转到 (1)若 G()b,则减少, 转到 (1)感谢下载载精品Fb G且 jny( j )b 则无解若( )( ),均有.,i1i.三、存贮控制问题在动态规划模型中 ,以时期为阶段 , 取各时期初的库

34、存量为状态变量 ;取各阶段的产量 ( 或采购量 ) 为决策变量 ,在确定决策变量时一般要考虑需求量、生产能力、库存限制等因素；指标函数取生产或采购费用。例 3 ：某工厂要制定今后四个时期某产品的生产计划， 估计今后四个时期内市场对该产品的需求如下表时期 k1234需求量 d k2324假设该厂生产每批产品的固定费用为2千元，若不生产为 0；每单位产品的成本为 1 千元；每件产品的每期保管费为0.5 千元；每个时期最大生产能力所允许的生产批量不超过5 个单位；最大库存量为 4个单位；假设开始时库存量为 1 个单位，要求第四期末库存在2个单位。试问该厂应如何安排各个时期的产量，才能满足市场需求的条件下使总费用最小？解：按四个时期将问题分为四个阶段，k=1,2,3,4取 k 期初库存量 xk 为状态变量； k 期内产量 uk 为决策变量，则状态转移方程为xk1xk uk dk由题意，第 k 期内的费用为rk (xk , uk ) 0.5xk21uk ,uk00,uk00.5xk2uk ,uk