数学模型动态规划

1、xk ，按逆序算法求解。.动态规划动态规划 (dynamic programming) 是运筹学的一个重要分支，它是解决多阶段决策问题的一种有效的数量化方法动态规划是由美国学者贝尔曼(rbellman ）等人所创立的 1951 年贝尔曼首先提出了动态规划中解决多阶段决策问题的最优化原理，并给出了许多实际问题的解法 1957 年贝尔曼发表了动态规划一书，标志着运筹学这一重要分支的诞生 1 动态规划的概念与原理一、动态规划的基本概念引例 : 最短路线问题美国黑金石油公司（ the black gold petroleum company ）最近在阿拉斯加（ alaska ）的北斯洛波（ north

2、 slope ）发现了大的石油储量。为了大规模开发这一油田，首先必须建立相应的输运网络，使北斯洛波生产的原油能运至美国的 3 个装运港之一。在油田的集输站（结点c）与装运港（结点p1 、p2、p3）之间需要若干个中间站，中间站之间的联通情况如图1 所示，图中线段上的数字代表两站之间的距离 （单位：10 千米）。试确定一最佳的输运线路，使原油的输送距离最短。解：最短路线有一个重要性质，即如果由起点a 经过 b 点和 c 点到达终点 d 是一条最短路线， 则由 b 点经 c点到达终点 d 一定是 b到 d的最短路（贝尔曼最优化原理） 。此性质用反证法很容易证明，因为如果不是这样，则从 b 点到 d

3、 点有另一条距离更短的路线存在， 不妨假设为 bpd；从而可知路线 a b p d 比原路线 abcd 距离短，这与原路线 abcd 是最短路线相矛盾，性质得证。根据最短路线的这一性质，寻找最短路线的方法就是从最后阶段开始，由后向前逐步递推求出各点到终点的最短路线，最后求得由始点到终点的最短路；即动态规划的方法是从终点逐段向始点方向寻找最短路线的一种方法。按照动态规划的方法，将此过程划分为 4 个阶段，即阶段变量 k 1,2,3,4 ；取过程在各阶段所处的位置为状态变量;.m 31810p1m 2176864m 11m 323126977cm 22p2796105m 33m 12115114p

4、3m 23634m 34k=1k=2k=3k=4当 k 4 时：图 1由结点 m31到达目的地有两条路线可以选择，即选择p1或 p2；故：f 4 (x4m 31 )min86选择 p62由结点 m32 到达目的地有三条路线可以选择，即选择p1、 p2 或 p3；故：4f 4 (x4m 32 )min33选择 p27由结点 m33到达目的地也有三条路线可以选择，即选择p1、 p2 或 p3 ；故：7f 4 (x4m 33 )min65选择 p35由结点 m到达目的地有两条路线可以选择，即选择p或 p；故：3423f 4 (x4m 34 )min33选择 p24当 k 3 时：由结点 m21 到达

5、下一阶段有三条路线可以选择，即选择m31、m32 或 m33；故：;.106f 3 ( x3m 21 )min7310选择 m3265由结点 m到达下一阶段也有三条路线可以选择，即选择m 、 m或 m ；22313233故：96f3 (x3m 22 )min7310选择 m 或m323355由结点 m到达下一阶段也有三条路线可以选择，即选择m 、 m或 m ；23323334故：113f 3 (x3m 23 )min459选择 m 或 m333463当 k 2 时：由结点 m11到达下一阶段有两条路线可以选择，即选择m21 或 m22；故：f 2 ( x2m 11 )81022min16选择

6、m610由结点 m到达下一阶段也有两条路线可以选择，即选择m或m ；故：122223f2 ( x2m 12 )91022min19选择 m119当 k 1 时：由结点 c到达下一阶段有两条路线可以选择，即选择m11 或 m12；故：f1 ( x1c)121611min28选择 m1019从而通过顺序（计算的反顺序）追踪（黑体标示）可以得到两条最佳的输运线路： cm11m22 m32p2；c m11m22 m33p3。最短的输送距离是 280 千米。一个多阶段决策过程最优化问题的动态规划模型通常包含以下要素。1、阶段阶段是过程中需要做出决策的决策点。描述阶段的变量称为阶段变量，常用 k 来表示。

7、阶段的划分一般是根据时间和空间的自然特征来进行的，但要便于将问题的过程转化为多阶段决策的过程。阶段变量一般用 k 1,2, , n 表示。;.2、状态状态（ state ）表示每个阶段开始时过程所处的自然状况。它应能描述过程的特征并且无后效性，即当某阶段的状态变量给定时，这个阶段以后过程的演变与该阶段以前各阶段的状态无关。通常还要求状态是直接或间接可以观测的。描述状态的变量称状态变量（state variable）。变量允许取值的范围称允许状态集合 (set of admissible states)。用 xk 表示第 k 阶段的状态变量，它可以是一个数或一个向量。用dk 表示第 k 阶段的允

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

9、第 k 阶段处于状态 xk 时的决策变量，它是xk 的函数，用 u k (uk ) 表示 uk 的允许决策集合。决策变量简称决策。4 策略决策组成的序列称为策略（ policy）。由初始状态 x1 开始的全过程的策略记作 p1n ( x1 ) ，即 p1n (x1 ) u1 ( x1 ), u2 ( x2 ), ,un ( xn ) .由第 k 阶段的状态 xk 开始到终止状态的后部子过程的策略记作pkn ( xk ) ，即pkn (xk ) uk ( xk ), , un ( xn ) ， k1,2, n1.类似地，由第 k 到第 j 阶段的子过程的策略记作pkj ( xk ) uk (xk

10、 ), ,u j ( x j ) .可供选择的策略有一定的范围，称为允许策略集合(set of admissiblepolicies) ，用 p( x), pkn( xk), p( x) 表示。1 n1kjk5. 状态转移方程在确定性过程中，一旦某阶段的状态和决策为已知，下阶段的状态便完全确定。用状态转移方程（equation of state transition）表示这种演变规律，写作xk 1t (xk , uk ),k1,2, n.（ 1）6.指标函数和最优值函数指标函数 (objective function)是衡量过程优劣的数量指标，它是定;.义在全过程和所有后部子过程上的数量函数，

11、用vkn ( xk ,uk , xk 1, xn 1 ) 表示，k 1,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 ，用 v j ( x j ,u j) 表示。指标函数由 v j ( j1,2, n) 组成，常见的形式有：n阶段指标之和，即vkn (xk , uk , xk 1 , , x

12、n 1 )v j (x j , u j ) ，jkn阶段指标之积，即vkn ( xk ,uk , xk 1, xn1 )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 ) 。根据状态转移方程指标函数vkn 还可以表示为状态 xk和策略 pkn的函数，即vkn ( xk , pkn ) 。 在 xk 给 定时指 标函 数 vkn 对 pkn 的 最

13、优值称为最优值 函数（ optimal value function），记为 fk ( xk ) ，即f k ( xk )opt vkn ( xk , pkn ) ，pkn pkn ( xk )其中 opt 可根据具体情况取max 或 min 。7 最优策略和最优轨线使指标函数vkn 达到最优值的策略是从 k 开始的后部子过程的最优策略，记作 pkn*uk* , un* 。 p1n* 是全过程的最优策略， 简称最优策略（ optimalpolicy ）。从初始状态 x1 (x1* ) 出发，过程按照p1n* 和状态转移方程演变所经历的状态序列 x1* , x2* , x*n 1 称最优轨线（

14、optimal trajectory）。二、基本方程：对于 n 阶段的动态规划问题，在求子过程上的最优指标函数时， k 子过程与 k 1子过程有如下递推关系：f k ( xk )opt vk ( xk , uk ) f k 1 ( xk 1 ), kn, ,1uk u k ( uk )（ 2）f n 1 ( xn 1 )c在 上 述方 程 中， 当 为 加 法 时 取 f n 1 ( xk 1 )0 ；当 为 乘 法 时 ， 取f n 1 ( xk 1 ) 1。三、最优化原理动态规划的最优化原理是美国学者rbellman 首先提出的，其表述如下：;.“作 整个 程的最 策略 具有 的性 ，无

15、去的状 和决策如何， 于前面的决策所形成的状 而言，余下的 决策必 构成最 策略” 也就是 最 策略的任一子策略都是最 的最 化原理 述 一个事 ， 全 程的任一状 点 xk ，我 不考虑 xk 以前的决策， 只保 xk 以后的决策是最 的。 然，由于 k 的任意性（ k =1，2， n）就保 了全 程的决策是最 的最 化原理 划从最后 段的 化开始，逐步向前一 段 化 展直至第一 段，从而达到全程 化的方法奠定了理 基 2 动态规划模型的建立与求解根据 划的概念不 看出，在用 划方法解决 ，必 首先明确本 中的 段、状 、决策、策略以及考察指 ，并建立状 移方程，然后根据 k 段最 指 的大

16、小找出与之 的最 子策略，直至找出 的最 解我 把找出 中的 段、状 、决策、策略以及考察指 ，并建立状 移方程 一 程称 建立 划模型 建立 划模型是解决 划 的第一步，也是非常重要的一步模型建立的是否 捷、准确，直接关系到 最 解的 及准确性，因此，建立 划模型是十分重要的其步 可 如下：（ 1）将所要解决的 恰当地划分 若干 段， 常是按事物 展的 和空 来划分不同 段，各 段的首尾要互相 接；（ 2）正确地 状 量 xk ，确定它在每一 段的取 范 ； 一步是形成 模型的关 ，状 量 xk 是 划模型中最重要的参数。一般来 ，状 量 xk 具有以下三个特征：要能 用来描述决策 程的演

17、特征； 足无后效性，即若某 段状 已 定后， 以后 程的 展不受以前各个状 的影响，也就是 ， 去的 史只通 当前的状 去影响未来的 展； 推性，即由 k 段的状 量 xk 及决策 量 uk 可以 算出 k1 段的状 量 xk 1（ 3） 决策 量 uk ，确定允 决策集合 d k (uk ) 。（ 4）正确写出状 移方程 xk 1t ( xk ,uk ), k 1,2,n.（ 5）建立指 函数，一般用 rk ( xk,uk ) 描述 段效 ，fk ( xk ) 表示从 kn 段的最 子策略函数 .（ 6 ）建 立 动 态 规 划 基 本 方程 。 对 每 一 对 xk ， uk ( xk )

18、 计 算不 同指 标值;.rk (xk ,uk ( xk ) f k 1 ( xk 1 ) 把 些指 行比 取出最 的一个，所 最 是根据 的需要确定指 的最大者或最小者，即f k ( xk )optrk ( xk , uk (xk )f k 1 (xk 1 )ukdk (u k )f n 1 ( xn 1 ) c kn, n 1, ,1在 划基本方程中， rk (xk ,uk ( xk ) ， xk 1t ( xk ,uk ), k1,2, , n.都是已知函数，最 子策略f k ( xk ) 与 f k 1 ( xk 1 ) 之 是 推关系，要求出 f k ( xk ) 及uk ( xk

19、) 需要先求出 f k 1 ( xk 1 ) ， 就决定了用在 划基本方程求最 策略是逆着 段的 序 行的，由 k = n ，n 1， 2，1 将上式依次逐步 推，直至全 程的 化 束， 即可求出 划 的最 策略及最 指 称 划的 逆序算法 。第三节动态规划方法应用一、机器负荷分配问题例 1：某厂新 某种机床125 台，据估 ， 种 5 年后将被其他 所代替，此机床如在高 荷状 下工作，年 坏率 1 ，年利 10 万元；2如在低 荷状 下工作，年 坏率 1 ，年利 6 万元； 如何安5排 些机床的生 荷，才能使5 年内 得最大的利 ？解：以年 段， k =1，2，3，4， 5取 k 年初完好的

20、机床数 状 量xk ，以 k 年初投入高 荷运行的机床数 决策 量 uk ， 低 荷运行的机床数 xk uk ，于是状 移方程 ：xk 11 uk4 (xk uk ) 0.8xk 0.3uk25以利 目 函数， k 年利 ：10uk6(xkuk )4uk6xk f k ( xk ) 表示从 k 年至 5 年末的最大 利 。 划基本方程 ：;.f k ( xk )max 4uk6xkf k 1( xk1 )0 ukxkxk1 0.8xk0.3ukx1125, x60f6 ( x6 )0k5,4,1下面具体求解注意到动态规划基本方程f k ( xk )max4uk6xkfk 1 (0.8xk 0.

21、3uk )0 uk xk所以 k5时f 5 ( x5 )max 4u5 6x5f6 (x6 )10x5u5 x50u5 x5当 k 4 时f 4 (x4 )max 4u46x4f 5 (0.8x40.3u4 )0 u4x 4max 4u46x410(0.8x40.3u4 )0 u4x4max u414x40 u4x415x4u4x4当 k3时f 3 ( x3 )max4u36x3f 4 (0.8x3 0.3u3 )0 u3x3max4u36x315(0.8x30.3u3 )0 u3 x3max0.5u318x30 u3 x318x3u30当 k2 时f 2 (x2 )max4u2 6x2f3

22、(0.8x20.3u2 )0u2x2max4u26x218(0.8x20.3u2 )0u2x 2max1.4u220.4x2 0u2x 220.4x2u20当 k1 时;.f1( x1)max 4u16x1f2 (0.8x10.3u1 )0 u1 x1max 4u16x120.4(0.8x10.3u1 )0u1 x1max 2.12u122.32x10u1 x122.32x122.32 125万元)u1 02790(即第一年到第5 年末的最大利润为 22.32 x1 ,而 x1125 。在按与计算过程相反的顺序推回去，可得最优计划为年份完好机床数高负荷机床数低负荷机床数kxk 10.8xk0.

23、3ukukxk uk第一年1250125第二年1000100第三年80080第四年64640第五年32320即前三年全部低负荷运转，后两年全部高负荷运转，最大利润为2790 万元。;.二、资源分配问题所谓资源分配问题，就是将一定数量的一种或若干种资源（如原材料、机器设备、资金、劳动力等）恰当地分配给若干个使用者，以使资源得到最有效地利用。1、一维分配问题设有某种资源可用于 n 项活动，假设资源的数量为a ，已知用于第 i 项活动的资源数为 xi 时，可以得到的收益为gi ( xi ) (i 1,2, n) ，试确定资源的分配方案使收益最大？该问题的数学模型可以表示为max z g1 ( x1

24、)g 2 ( x2 )g n (xn )s.t . x1x2xnax1 , x2 , xn0当 gi ( xi )(i 1,2, , n) 为 线 性 函 数 时 ， 该 问 题 是 线 性 规 划 问 题 ， 当gi ( xi ) (i1,2, , n) 为非线性函数时，该问题是非线性规划问题，如果采用非线性规划求解，比较麻烦。可以将它看成多阶段决策问题，利用动态规划求解。在应用动态规划方法处理这一 类问题时，提出将资源分配给每项活动的过程看成一个阶段，每个阶段都要确定对一种活动的资源投放量，这时，状态变量 xk 可以选择 k 阶段初所拥有的资源量， 即 xk 是要在第 k 项到第 n 项活

25、动间分配的资源量。决策变量uk 选择对活动k 的资源投放量，决策变量uk 的允许集合为0ukxk 。在选取上述状态变量和决策变量的情况下，状态转移方程为：xk 1xkuk去投放资源时的收益为指标函数，则g k (uk )为阶段效益指标。记 f k ( xk ) 表示从 k 阶段至 n 阶段的最大总利润。则动态规划基本方程为：fk (xk )maxgk (uk） fk 1(xk 1)0u k xkfn 1(xn 1) 0k n,n 1, ,1;.例 2：某公司拟将 500 万元的资本投入所属的甲、乙、丙三个工厂进行技术改造，各工厂获得投资后年利润将有相应的增长，增长额如表1 所示。试确定 500

26、 万元资本的分配方案，以使公司总的年利润增长额最大。表 1投资额100 万元200 万元300 万元400 万元500 万元甲307090120130乙50100110110110丙4060110120120解：将问题按工厂分为三个阶段k1,2,3 ，设状态变量 xk （ k1,2,3 ）代表从第 k 个工厂到第3 个工厂的投资额，决策变量uk 代表第 k 个工厂的投资额 。 于 是 有 状 态 转 移 方 程 为xk 1xkuk 、 允 许 决 策 集 合dk (uk ) uk | 0 ukxk 和递推关系式：f k ( xk )max gk (uk )f k 1( xk uk )(k 3,

27、2,1)0 ukxkf4 ( x4 ) 0当 k3时：f3(x3 )max g3 (u3 )0max g3 (u3 )0 u3 x30u 3 x3于是有表 2，表中 u3 表示第三个阶段的最优决策。表 2（单位：百万元）x3012345u3012345f 3 ( x3 )00.40.61.11.21.2当 k2 时：f 2( x2 )max g2 (u2 )f 3 ( x2u2 )0 u2x2于是有表 3。表 3（单位：百万元）u2g2 (u2 )f3 ( x2 u2 )f2 (x2 )u2x201234500+00010+0.40.5+00.5120+0.60.5+0.41.0+01.023

28、0+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+0.41.1+02.12;.当 k1 时：f1(x1) max g1 (u1) f2 (x1 u1 )0 u1 x1于是有表 4。表 4ug1(u1 ) f2 (x1 u1)f1 ( x1 )u11x101234550+2.10.3+1.60.7+1.40.9+1.01.2+0.51.3+02.10，2然后按计算表格的顺序反推算，可知最优分配方案有两个： （ 1）甲工厂投资 200 万元，乙工厂投资 2

29、00 万元，丙工厂投资 100 万元；（2）甲工厂没有投资，乙工厂投资 200 万元，丙工厂投资 300 万元。按最优分配方案分配投资（资源），年利润将增长 210 万元。这个例于是决策变量取离散值的一类分配问题，在实际问题中，相类似的问题还有销售店的布局（分配）问题、设备或人力资源的分配问题等。2、二维分配问题（ 1）设数量分别为 a, b 的两种资源分配给 n 个使用者，xi 分配第一种资源给第i 个使用者的数量，yi 分配第二种资源给第i 个使用者的数量，ri ( xi , yi ) 第 i 个阶段的收益，i 1,2, , n求总收益最大的分配方案nzmaxri ( xi , yi )i

30、1nxia该问题的数学模型可以表示为i 1nyibi 1xi 0 ,yi 0 , i 1,2, , n（ 2）二维分配问题的解法1、逐次逼近法;.nzmaxri (xi , yi)i 1nxia由于i1nyibi1xi0 ,yi0 , i1,2, , n设nx (0 )( x1(0) , x2(0 ) , , xn(0 ) ), 满足xi ai1xi0固定 x于 x ( 0) ,求下列一维问题的nmaxri ( x(i0 ) , yi )i1nyibi1yi0 ,i1,2, n得最优解y( 0)( y1( 0) , y2(0 ) , , yn(0 ) ), 固定 y于 y (0) ,求下列一维

31、问题的n( 0)maxri ( xi , yi)i1nxiai1xi0 ,i1,2,n得最优解x (1)( x1(1) , x2(1) , xn(1) ), 固定 x于 x (1) ,求下列一维问题的;.maxnn(1)ri ( xi , yi )i1yibi 1yi0 ,i1,2, n得最优解y(1)( y1(1) , y2(1) , yn(1) ),轮转若干步，直到满足精确度要求。2、拉格郎日乘子法（1）估计一个拉格郎日乘子0（2）用动态规划法解一维问题nnmaxri ( xi , yi )yi i1i1nxiai1xi 0 , yi0 , i 1,2, , n若解不唯一，假设共有 m 个

32、( x(1) ( ), y(1) (), ( x( 2) (), y( 2) (), (x(m ) (), y(m) ( )x(1) ( )(x1(1) (), x2(1) (), xn(1) ( )t , y(1) ()( y1(1) ( ), y2(1) ( ), , yn(1) ( )t（ 3）计算 f ( )nyi(j ) ( )j,mmin1,2,ji1nyi( j ) (g()max)j1,2,mji1（ 4）判断若存在jk, .n(k )b,则 ( k ) (),y( k) ( )为最优解s tyixi1若 f ()b,则增大, 转到 (1)若 g ()b,则减少, 转到 (1)

33、n若 f ()bg (),且 j ,均有y( j )b.则无解 .ii 1;.三、存贮控制问题在动态规划模型中 , 以时期为阶段 , 取各时期初的库存量为状态变量 ; 取各阶段的产量 ( 或采购量 ) 为决策变量 , 在确定决策变量时一般要考虑需求量、生产能力、库存限制等因素；指标函数取生产或采购费用。例 3：某工厂要制定今后四个时期某产品的生产计划， 估计今后四个时期内市场对该产品的需求如下表时期 k1234需求量 dk2324假设该厂生产每批产品的固定费用为 2 千元，若不生产为 0；每单位产品的成本为 1 千元；每件产品的每期保管费为 0.5 千元；每个时期最大生产能力所允许的生产批量不

34、超过 5 个单位；最大库存量为 4 个单位；假设开始时库存量为 1 个单位，要求第四期末库存在2 个单位。试问该厂应如何安排各个时期的产量，才能满足市场需求的条件下使总费用最小？解：按四个时期将问题分为四个阶段，k=1,2,3,4取 k 期初库存量 xk 为状态变量； k 期内产量 uk 为决策变量，则状态转移方程为xk1xk uk dk由题意，第 k 期内的费用为21uk ,uk 0rk (xk ,uk ) 0.5xk,uk000.5xk2uk ,uk00,uk0记 f k ( xk ) 表示第 k 期至第 4 期末的最小总费用。则动态规划基本方程为：fk (xk )min rk ( xk ,uk） fk 1( xk 1 )u kf5 (x5)0k4,3,2,1下面求解当 k4 时注意： xk 1xkukdkx4x5u4d42 4 u46 u4u45,u41, 2, 3, 4;.fk (xk ) min rk (xk ,uk） fk 1 (xk 1)ukmin 0.5xk2ukfk 1( xk 1 )u4 6 x40u kf4(1)0.512