运筹学10动态规划课件

1、运筹学10动态规划动态规划Dynamic programming是解决多阶段决策过程（multi-step decision process）最优化的一种数量化方法，所以又名多阶段规划（multi-stage programming）五十年代贝尔曼(Richard Bellman)为代表的研究成果属于现代控制理论的一部分以长远利益为目标的一系列决策1951年提出了 “最优化原理”（principle of decision optimality）可归结为一个递推公式1957年动态规划动态规划应用等其它著作成功之处：把一个n维决策问题变换为n个一维最优化问题，一个一个地求解。这是经典极值方法所做

2、不到的，它几乎超越了所有现存的计算方法，特别是经典优化方法动态规划能够求出全局极大或极小，这也是其它优化方法很难做到的注意动态规划是求解某类问题的一种方法，是考察问题的一种途径，而不是一种特殊的算法，没有统一的数学模型和算法必须具体问题具体分析针对具体问题，运用动态规划的原理和方法，建立起相应的模型，然后再用动态规划方法去求解动态规划(dynamic programming)是运筹学的一个分支，是求解决策过程(decision process)最优化的数学方法。20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multi-step decision process)的

3、优化问题时，提出了著名的最优化原理(principle of optimality)，把多阶段过程转化为一系列单阶段问题，逐个求解，创立了解决这类过程优化问题的新方法动态规划。1957年出版了他的名著Dynamic Programming，这是该领域的第一本著作。动态规划问世以来，在经济管理、生产调度、工程技术和最优控制等方面得到了广泛的应用。例如最短路线、库存管理、资源分配、设备更新、排序、装载等问题，用动态规划方法比用其它方法求解更为方便。2511214106104131112396581052C1C3D1AB1B3B2D2EC2f5(E)=0问题的引入：最短路问题求上述问题中A到E的最短

4、路。2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D1)=5f5(E)=02511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f4(D1)=52511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C1)=8f4(D1)=52511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C2)=7f4(D1)=5f3(C1)=8251121

5、4106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f3(C1)=8f3(C2)=72511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B1)=20f3(C2)=7f3(C1)=82511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B2)=14f3(C2)=7f3(C1)=8f2(B1)

6、=202511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f2(B1)=20f2(B2)=142511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=202511214106104131112396581052C1C3D1AB1B3B2D2EC2f

7、4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=20状态 最优决策 状态 最优决策 状态 最优决策 状态 最优决策 状态A （ A，B2） B22511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=20状态 最优决策 状态 最优决策 状态 最优决策 状态 最优决策 状态A （ A，B2）

8、 B2 （B2，C1） C12511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=20状态 最优决策 状态 最优决策 状态 最优决策 状态 最优决策 状态A （ A，B2） B2 （B2，C1） C1 （C1，D1） D12511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3

9、(C2)=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=20状态 最优决策 状态 最优决策 状态 最优决策 状态 最优决策 状态A （ A，B2） B2 （B2，C1） C1 （C1，D1） D1 （D1，E） E从A到E的最短路径为19，路线为AB 2C1 D1 E 10.1 多阶段决策问题多阶段决策过程，是指这样的一类特殊的活动过程，问题可以按时间顺序分解成若干相互联系的阶段，在每一个阶段都要做出决策，全部过程的决策是一个决策序列。要使整个活动的总体效果达到最优的问题，称为多阶段决策问题。决策:在多个可行方案中选择或选定一个的过程或行为;策略:由一系列相互衔接的决策构成

10、的决策序列;策略集合:有可供选择的策略构成的集合;最优策略:在预定标准下达到最好效果的策略.静态决策 一次性决策动态决策 多阶段决策决策s1s2vu输入决策输出决策效应第一月s1s2v1u1第二月s3v2u2第三月s4v3u3例1 给定一个线路网络图,两点之间联线上的数字表示两点间的距离(或运费),试求一条由s到t的铺管线路,使总距离最短.adbetcfs9757845646547例2 某公司拟将50万元资金投放下属A、B、C三个部门，各部门在获得资金后的收益如表所示，求总收益最大的投资分配方案（投资数以10万元为单位）。投放资金(万元)01020304050收益（万元） A015202528

11、30B0010254570C01020304050例3 已知货物的单位重量i，单位体积i及价值pi如表所示，船的最大载重能力为W5，最大装载体积为V8，求最优装载方案。 iiipi11230234803236510.2 动态规划的基本概念和基本方程(1) 动态规划的基本概念阶段与阶段变量:将所要研究的问题,按时间或空间特征分成若干个互相联系的阶段.简称“阶段”我们就是要按阶段的顺序来求解.描述阶段的变量阶段变量,常用字母k来表示;状态、状态变量和状态集合各阶段开始时的客观条件叫做状态.描述各阶段状态的变量叫做状态变量,常用sk表示第阶段的状态变量； 状态变量sk的取值集合称为状态集合,用Sk表

12、示；动态规划中状态具有以下性质:某阶段状态一旦确定以后过程的状态变化不受这个状态以前的影响,也就是说某状态以后的过程和以前无关,只与当前状态有关,我们称这种特性为“无后效性.” 决策、决策变量和策略当个阶段的状态取定以后,就可以做出关于下一步的选择,从而确定下一阶段的状态,这种决定称为决策；表示决策的变量叫做决策变量,常用uk(sk)表示.第k阶段当状态为sk时的决策变量；在实际问题中决策变量的取值往往限制在一定的范围内,我们称此范围为允许决策集,常用Dk(sk)表示第k阶段从状态sk出发的允许决策集,因此有uk(sk) Dk(sk).各段决策确定后,整个问题的决策序列就构成了一个策略,用P1

13、,nu1(s1),u2(s2), ,un(sn)表示；使整个问题达到最优效果的的策略就是最优策略.动态规划中本阶段的状态是上一阶段的决策结果.如果给定了第k阶段的状态sk,本阶段的决策就为uk(sk),则第k+1段的状态uk+1也就完全确定了,它的关系可表示为:sk+1=Tk(sk,uk).由于它表示了由k到k=1段的状态转移规律,所以称为状态转移方程.T1s1s2v1 (s1, u1)u1(s1)T2s3v2 (s2 ,u2)u2 (s2)Tksksk+!vk (sk,uk)uk (sk)Tnsnsn+1vn (sn,un)un (sn)指标函数与最优值函数用于衡量所选定策略优劣的数量指标称

14、为指标函数.阶段指标函数vk(sk,xk)一个n段决策过程,从1到n叫作问题的原过程,对于任意一个给定的k ,从第k 到n段的过程称为原过程的一个后部子过程.V1,n(s1,p1,n)表示初始状态s1采用策略p1,n.时原过程指标函数值. Vkn=(sk,xk,sk+1,xk+1, ,sn,xn) (k=1,2, ,n) V1n=(s1,x1,s2,x2, ,sn,xn) 多段决策过程中从第k阶段到最终阶段的过程称为k-后部子过程，简称k-子过程。 Tksksk+!vk (sk,uk)uk (xk)Tnsnsn+1vn (sn,un)un (xn)指标函数应具有三个条件 指标函数在全过程和所有

15、后部子过程上有定义；指标函数应具有可分离性，满足递推公式 Vkn=(sk,xk, Vkn+1( sk+1,xk+1, ,sn,xn)函数是一个关于变量Vk+1 n单调递增的函数。指标函数Vkn达到最优值，称为最优值函数。fk(sk)=opt. Vkn (sk,xk,sk+1,xk+1, ,sn,xn) (k=1,2, ,n) 使指标函数Vkn达到最优值的策略是从k开始的后部子过程的最优策略，记作pkn*=uk*,.un*,p1n*又是全过程的最优策略，简称最优策略。 指标函数的两种基本形式：(2) 最优化原理最优化原理 “最优策略具有的基本性质是：无论初始状态和初始决策如何，对于前面决策所造成

16、的某一状态而言，剩下的决策序列必构成最优策略”。AMB最优性原理的涵义 最优策略的任何一部分子策略，也是相应初始状态的最优策略。 每个最优策略只能由最优子策略构成。 显然，对于具有无后效性的多段决策过程而言，如果按照k后部子过程最优的原则来求各阶段状态的最优决策，那么这样构成的最优决策序列或策略一定具有最优性原理所提示的性质。 (3)动态规划基本方程多段决策过程的特点 每个阶段都要进行决策 相继进行的阶段决策构成的决策序列 前一阶段的终止状态又是后一阶段的初始状态阶段最优决策不能只从本阶段的效应出发，必须通盘考虑，整体规划。阶段k的最优决策不应该只是本阶段效应的最优，而必须是本阶段及其所有后续

17、阶段的总体最优，即关于整个k后部子过程的最优决策。多段决策过程中所要求解的是，从起始状态x1开始，进行一系列的决策，使目标 V 达到最优最优目标值 V*最优策略 使得目标达到最优的决策序列。最优路线 在采取最优策略时，系统从s1开始所经过的状态序列求解动态规划模型 找到最优策略、最优路线和最优目标值。 对于类指标函数设在阶段k的状态xk执行了任意选定决策uk后的状态是sk+1=Tk(sk,xk)。这时k-后部子过程就缩小为k+1后部子过程。根据最优性原理，对k+1后部子过程应采取最优策略，由于无后效性，k后部子过程的目标函数值为 给出边界条件：何在一起即构成动态规划的基本方程。类指标函数的基本

18、方程（逆序）为II类指标函数的基本方程（逆序）为适用于初始状态给定类指标函数的基本方程（顺序）为II类指标函数的基本方程（顺序）为同理适用于终止状态给定10.4 动态规划的求解方法(1) 基本求解过程动态规划建模递推回溯(2)动态规划逆推解法(3)动态规划顺推解法(1) 基本求解过程动态规划建模确定阶段与阶段变量明确状态变量和状态可能集合。确定决策变量和决策允许集合。确定状态转移方程。明确阶段效应和目标，即写出指标函数。确定阶段与阶段变量阶段的划分一般是按照决策进行的时间或空间上的先后顺序划分的，阶段数等于多段决策过程中从开始到结束所需要作出决策的数目，阶段变量用k表示。明确状态变量和状态可能

19、集合状态变量必须包含在给定的阶段上确定全部允许决策所需要的信息。状态变量的确定决定了整个决策过程是不是具有无后效性，因而也决定着能不能用动态规划方法来求解。状态可能集是关于状态的约束条件，因此为了求解必须正确地确定状态可能集。确定决策变量和决策允许集合。与静态问题相同，决策变量应能够反映对问题所作的决策，决策变量也应有其相应的约束条件，在建模时应明确决策允许集合Uk(sk)。确定状态转移方程。系统k阶段从状态sk出发作了决策uk(sk)之后的结果之一是系统状态的转移，这一结果直接影响系统往后的决策过程，因此必须明确状态的转移过程，即根据问题的内在关系，明确sk+1=Tk(sk,uk)中的函数T

20、k(sk,uk) 。递推运用基本方程的递推公式和边界条件，从k=n开始，由后向前逆推，从而逐步求得各阶段的最优决策和相应的最优值，最后求得f1(s1),将s1的值代入计算即得。回溯由s1和x1* ，利用状态转移方程计算出s2 ，从而确定x2* ，依此类推，最后确定xn* ，于是获得最优策略(2) 动态规划逆推解法例1 某旅行者希望从s地起到t地，其间的道路系统如图所示，图上圆圈表示途径的地方，称为节点，连结两地的箭线表示道路，其上的数字表示该段道路长度，箭头表示通行的方向。试求s到t的最短路。adbetcfs9757845646547第一阶段 第二阶段 第三阶段划分阶段 k=1,2,3 代表三

21、个阶段adbetcfs9757845646547状态变量sk取为k阶段所在地，则有： adbetcfs9757845646547边界条件 f4(t)=0k阶段决策是决定下一步走到哪里，uk(sk)取为下一步的所在点。 adbetcfs9757845646547由于第3阶段末已到达t，往后的距离自然是零，因此f4(t)=0对3阶段所有可能的状态S3=d, e, f计算f3( )如下也可以用表格方法计算如下t/tf3()u3()def5+07+04+0574tttv3(s3,u3)+f4(s4) f3(s3) u3(s3) adbetcfs9757845646547475对2阶段所有可能的状态s2

22、=a,b,c计算f2()如下也可以用表格方法计算如下d/de/ef/ff2()u2()abc7+55+54+56+75+74+46+48109fddf2(s2) u2(s2) v2(s2,u2)+f3(s3) adbetcfs97578456465474759108对1阶段所有可能的状态S1=s计算f1( )如下a/ab/bc/cf2()u2()s9+88+107+916c顺序回溯求最优策略、最优路线和最优目标函数值adbetcfs9757845646547475910816例2 某公司有资金10万元，若投资项目i（i=1,2,3）的投资额为 时,其效益分别为:问应如何分配投资树额才能使总收益

23、最大? 可列出它的静态模型: 分析:这是一个表面与时间没有任何关系的问题,但要用动态规划的方法去解则必须把它划分为“时段”.本题可划分为3各时段,每段只决定对一个投资项目的投资额.这样把问题分解为3阶段决策问题.解:当k=2时, 这是一个函数求极值问题,利用微分方法可求得该函数有极小值.s0s2x2要讨论 的具体情况: 减函数例3 用动态规划方法求解下列规划问题：解: (1) 建模 阶段划分：k=1,2,3 状态变量：阶段初始时刻可分配资源， 用s1,s2,s3表示，其中s1=6 决策变量：每阶段消耗资源量，用x1,x2,x3表示 状态转移方程： 指标函数：(2) 递推：(3) 回溯：(3)

24、动态规划顺推解法例1 某旅行者希望从s地起到t地，其间的道路系统如图所示，图上圆圈表示途径的地方，称为节点，连结两地的箭线表示道路，其上的数字表示该段道路长度，箭头表示通行的方向。试求s到t的最短路。adbetcfs9757845646547第一阶段 第二阶段 第三阶段划分阶段 k=1,2,3 代表三个阶段adbetcfs9757845646547状态变量sk取为k阶段所在地，则有： adbetcfs9757845646547边界条件 f0(s)=0k阶段决策是决定到达所在点的路线，uk(sk)取为到达的sk的路线。 adbetcfs9757845646547由于第0阶段末已到达s，往前的距离

25、自然是零，因此f0(s)=0对1阶段所有可能的状态S1=a, b, c计算f1( )如下也可以用表格方法计算如下s/sf1()u1()abc9+08+07+0987sasbscv1(s1,u1)+f0(s) f1(s1) u1(s1) adbetcfs97578456465478790对2阶段所有可能的状态s2=d,e,f计算f2()如下也可以用表格方法计算如下a/ab/bc/cf2()u2()def7+94+95+86+84+75+76+7111213cdceaf,cff2(s2) u2(s2) v2(s2,u2)+f1(s1) adbetcfs97578456465478791311120

26、对3阶段所有可能的状态S3=t计算f3(t)如下d/de/ef/ff3()u3()t5+117+124+1316dt逆序回溯求最优策略、最优路线和最优目标函数值adbetcfs9757845646547879131112160例2 某公司有资金10万元，若投资项目i（i=1,2,3）的投资额为 时,其效益分别为:问应如何分配投资树额才能使总收益最大? 可列出它的静态模型: 分析:这是一个表面与时间没有任何关系的问题,但要用动态规划的方法去解则必须把它划分为“时段”.本题可划分为3各时段,每段只决定对一个投资项目的投资额.这样把问题分解为3阶段决策问题.解:当k=2时, 当k=3时, 逆序回溯求

27、最优策略、最优路线和最优目标函数值10.5 动态规划的其他应用举例（1）资源分配问题（2）背包问题（3）生产与存储问题（4）系统可靠性问题（1）资源分配问题例2. 某公司拟将某种设备5台，分配给所属的甲、乙、丙三个工厂。各工厂获得此设备后，预测可创造的利润如表10-5所示，问这5台设备应如何分配给这3个工厂，使得所创造的总利润为最大？ 表10-5 盈利 工厂设备台数 甲 厂 乙 厂 丙 厂 0 0 0 0 1 3 5 4 2 7 10 6 3 9 11 11 4 12 11 12 5 13 11 12解：将问题按工厂分为三个阶段，甲、乙、丙三个厂分别编号为1、2、3厂。设 sk= 分配给第k个

28、厂至第3个厂的设备台数（k=1、2、3）。 xk=分配给第k个设备台数。 已知s1=5, 并有 从与的定义，可知以下我们从第三阶段开始计算。 第三阶段: 显然将台设备都分配给第3工厂时，也就是时，第3阶段的指标值（即第3厂的盈利）为最大，即 由于第3阶段是最后的阶段，故有 其中可取值为0,1,2,3,4,5。其数值计算见表106。 表106 01234500 0014 4126 623 11 1134 121245 12125 其中表示取3子过程上最优指标值时的决策，例如在表10-6中可知当=4时，有有此时，即当时，此时取（把4台设备分配给第3厂）是最优决策，此时阶段指标值（盈利）为12，最优

29、3子过程最优指标值也为12。 第二阶段： 当把台设备分配给第2工厂和第3工厂时，则对每个值，有一种最优分配方案，使最大盈利即最优2子过程最优指标函数值为 因为上式也可写成其数值计算如表107所示。表107 0123450 00104 51206 54 1023011 56 110 1424012 114 110 161,25012 512 116 114 110212 其中在的这一行里，当时，这里从表105中可知，把1台设备交给乙厂所得盈利数即可，知，这里从表106查即可知=11。同样可知当时，可知 ;当时，；当时，；当时， ；由于，不可能分2厂5台设备，故时，栏空着不填。从这些数值中取得最大

30、即得，即有=16。在此行中我们在取最大值的 上面加一横以示区别，也可知这时的最优决策为1或2。第一阶段：把台设备分配给第1，第2，第3厂时，最大盈利为其中可取值0,1,2,3,4,5.数值计算见表108 表10-8 然后按计算表格的顺序推算，可知最优分配方案有两个： 1.由于，根据，查表107可知，再由 ，求得。即分配给甲厂0台，乙厂2台，丙厂3台。 2.由于，根据 ，查表107可 0123455 316 9+10 12+5 13+0 21 0,2知，再由 ,求得，即分配给甲厂2台，乙厂2台，丙厂1台。这两种分配方案都能得到最高的总盈利21万元。 动态规划模型车间1车间2车间3 k=1k=2k

31、=3状态变量sk：尚未分配的设备台数s2s3s4决策变量xk：每个工厂分配的设备台数x1x2x3s2=s1-x1阶段ks1s3=s2-x2s4=s3-x3决策允许集合Dk(sk)：分配台数xk的范围0 x1 s10 x2 s20 x3 s3状态转移方程：状态如何随上一状态以及决策变化阶段指标vk(sk,xk)：每个工厂分配设备产生的效益v1(s1,x1)v2(s2,x2)v3(s3,x3)最优指标函数fk(sk)fk(sk)=maxvk(sk,xk)+fk+1(sk+1)终端条件fn(sn)f4(s4)=0 设有n种物品，每一种物品数量无限。第i种物品每件重量为wi公斤，每件价值ci元。现有一

32、只可装载重量为W公斤的背包，求各种物品应各取多少件放入背包，使背包中物品的价值最高。 这个问题可以用整数规划模型来描述。设xi为第i种物品装入背包的件数（i =1, 2, , n），背包中物品的总价值为z，则 Max z = c1x1+c2x2+ +cnxn s.t. w1x1+w2x2+wnxnW x1, x2, , xn0 且为整数。（2）背包问题 下面用动态规划逆序解法求解它。设阶段变量k：第k次装载第k种物品（k=1, 2, , n）状态变量sk：第k次装载时背包还可以装载的重量；决策变量uk = xk：第k次装载第k种物品的件数；决策允许集合：Dk(sk) = xk | 0 xksk

33、/wk，xk为整数；状态转移方程： sk+1 = sk wkxk；阶段指标： vk = ckxk；最优过程指标函数fk(sk)：第k到n阶段容许装入物品的最大使用价值；递推方程： fk(sk) = max ckxk+fk+1(sk+1) = max ckxk+fk+1(sk wkxk)； xDk(sk) 终端条件： fn+1(sn+1) = 0。例3.某咨询公司有10个工作日可以去处理四种类型的咨询项目，每种类型的咨询项目中待处理的客户数量、处理每个客户所需工作日数以及所获得的利润如表109所示。显然该公司在10天内不能处理完所有的客户，它可以自己挑选一些客户，其余的请其他咨询公司去做，应如何

34、选择客户使得在这10个工作日中获利最大？ 表109 咨询项目类型待处理客户数处理每个客户所需工作日数处理每个客户所获利润123443221347281120解：用动态规划来求解此题。我们把此问题分成四个阶段，第一阶段我们决策将处理多少个第一种咨询项目类型中的客户，第二阶段决策将处理多少个第二种咨询项目类型中的客户，第三阶段、第四阶段我们也将作出类似的决策。我们设分配给第k种咨询项目到第四种咨询项目的所有客户的总工作日（第k阶段的状态变量）。 =在第k种咨询项目中处理客户的数量（第k阶段的决策变量）。已知10并有 并从与的定义可知从第四阶段开始计算：显然将个工作日尽可能分配给第四类咨询项目，即时

35、，第四阶段的指标值为最大，其中，表示取不大于的最大整数，符号为取整符号，故有由于第四阶段是最后的阶段，故有因为至多为10，其数值计算见表1010。 表10100100010020030040050060070201802019020110011第三阶段：当把个工作日分配给第四类和第三类咨询项目时，则对每个值，都有一种最优分配方案，使其最大盈利即最优3子过程最优指标函数值为 因为因为至多为10，所以的取值可为0,1,2。其数值计算见表1011。 表1011 0 1 2000 1 00 200 300 40011 1 50011 1 60011 1 7 11+0 20 0 8020 11+0 22

36、 2 9020 11+0 22 2 10020 11+0 22 2 第二阶段： 同样以每个值都有一种最优分配方案，使其最大盈利即最优2子过程最优指标函数值为：因为，故有因为至多为10，所以的取值为0,1,2,3。其数值计算见表1012。表10-12 第一阶段： 我们已知，又因为 ，同样有 因为 ,故可取值为0,1,2, ,10。其数值计算见表1013。 表1013 从表1013可知，从而得10010，在表1012的的这一行可知，由，查表1011的的这一行可知，最后由，查表10-10的的这一行得，综上所述得最优解为：此时最大盈利为28。 实际上，背包问题我们也可以用整数规划来求解，如果背包携带物

37、品重量的限制为W公斤，这N种物品中第i种物品的重量为，价值为，第i种物品的总数量的，我们可以设表示携带第i种物品的数量，则其数学模型为：S.T. 且为整数。 我们不妨用此模型去求解例3，也一定得出同样的结果。 例4.某公司为主要电力公司生产大型变压器，由于电力采取预订方式购买，所以该公司可以预测未来几个月的需求量。为确保需求，该公司为新的一年前四个月制定一项生产计划，这四个月的需求如表1015所示。生产成本随着生产数量而变化。调试费为4，除了调度费用外，每月生产的头两台各花费为2，后两台花费为1。最大生产能力每月为4台，生产成本如表1016所示。表1015（3）生产存储问题 表1016每台变压

38、器在仓库中由这个月存到下个月的储存费为1，仓库的最大储存能力为3台，另外，知道在1月1日时仓库里存有一台变压器，要求在4月30日仓库的库存量为零。试问该公司应如何制定生产计划，使得四个月的生产成本和储存总费用最少？解：我们按月份来划分阶段，第i个月为第i阶段：（i=1,2,3,4). 设 为第k阶段期初库存量； k=1,2,3,4 为第k阶段生产量； k=1,2,3,4为第k阶段需求量； k=1,2,3,4，这已在表10-15中告诉我们。因为下个月的库存量等于上个月的库存量加上上个月的产量减去上个月的需求量，我们就得到了如下状态转移方程：因为，故有因为，故有由于必须要满足需求，则有通过移项得到

39、 另一方面，第k阶段的生产量必不大于同期的生产能力（4台），也不大于第k阶段至第四阶段的需求之和与第k阶段期初库存量之差，否则第k阶段的生产量就要超过从第k阶段至第四阶段的总需求，故有以下我们从第四阶段开始计算：从以上的状态转移方程可知这样就有 这里的阶段指标可以分成两部分，即生产成本与储存费，即为 由于第四阶段末要求库存为零，即有，这样可得 对于每个的可行值，的值列于表1017。 表1017表中当时，可知第四阶段要生产台，从表1016可知总成本为9，同样可以算出当为1,2,3时的情况，结果已列于表1017中。第三阶段：此时有：因为以及所以有例如，当第三阶段初库存量时，生产量为2时，则所以生产

40、成本为8，第三阶段末库存为2时，储存费为，而查1017表可知，这样可知，填入表1018中的栏内，其他结果如表1018所示 ： 表1018 第二阶段：因为所以有 计算结果如表1019所示。 表1019 第一阶段：因为故有计算结果见表1020。 表1020利用递推关系可以从表1020，表1019，表1018和表1017得到两组最优解： 这时有最低总成本29。 例5.某科研项目组由三个小组用不同的手段分别研究，它们失败的概率各为0.40，0.60，0.80。为了减少三个小组都失败的可能性，现决定给三个小组中增派两名高级科学家，到各小组后，各小组科研项目失败概率如下表： 问如何分派科学家才能使三个小组

41、都失败的概率（即科研项目最终失败的概率）最小？ 高级科学家小组12300.400.600.8010.200.400.5020.150.200.30（4）系统可靠性问题 解：用逆序算法。设 阶段：每个研究小组为一个阶段，且阶段123小组123计算当n=3时，当n=2时， s3 f3*(s3) x3*008001050120302 x2s2f2(s2,x2)=P2(x2) f3*(s2-x2) f2*(s2) x2*012004804801030032030020180200160162当n=1时， 最优解为 x1*=1，x2*=0，x3*=1；科研项目最终失败的概率为0.060。 x1s1f1(

42、s1,x1)=P1(x1) f2*(s1-x1)f1*(s1)x1*01220064 0060 0072 0060 15动态规划的应用(2)*一、连续确定性动态规划 对于状态变量和决策变量只取连续值，过程的演变方式为确定性时，这种动态规划问题就称为连续确定性动态规划问题。5动态规划的应用(2)*机器负荷分配问题 例1 一种机器能在高低两种不同的负荷状态下工作。设机器在高负荷下生产时，产量函数为P1=8u1，其中u1为在高负荷状态下生产的机器数目，年完好率为a=0.7，即到年底有70的机器保持完好。在低负荷下生产时，产量函数为P2=5u2，其中u2为在低负荷状态下生产的机器数目，年完好率为b=0

43、.9。设开始生产时共有1000台完好的机器，请问每年应该如何把完好机器分配给高、低两种负荷下生产，才能使得5年内生产的产品总产量最高。5动态规划的应用(2)*解 建立动态规划模型： 分为5个阶段，每个阶段为1年。设状态变量sk表示在第k阶段初拥有的完好机器数目；k=1,2,3,4,5。 决策变量xk表示第k阶段中分配给高负荷状态下生产的机器数目；k=1,2,3,4,5。显然sk-xk为分配给低负荷状态下生产的机器数目。 状态转移方程为 sk+1=0.7xk+0.9(sk-xk) 阶段指标 rk(sk,xk)=8xk+5(sk-xk) 最优指标函数 ，其中k=1,2,3,4,5。 f6(s6)=

44、0。5动态规划的应用(2)*第5阶段： 因为f5(s5)是x5的线性单调增函数，故有x5* =s5，于是有f5(s5)=8s5。第4阶段： 5动态规划的应用(2)* 同样的，f4(s4)是x4的线性单调增函数，有x4*=s4 ，f4(s4)=13.6s4。 对前几个阶段依次类推，可得 f3(s3)=17.5s3， f2(s2)=20.75s2， f1(s1)=23.72s1。 因为期初共有完好机器1000台，故s1=1000。有f1(s1)=23.72s123720，即5年最大的产量为23720台。得最优解为 ， ， ， 。 这意味着前两年应把年初完好机器完全投入低负荷生产，后三年应把年初完好

45、机器完全投入高负荷生产。5动态规划的应用(2)* 下一步工作是确定每年初的状态，按照从前向后的顺序依次计算出每年年初完好的机器数目。已知s1=1000,根据状态转移方程，有:5动态规划的应用(2)* 上面所讨论的最优策略过程，初始端状态s1=1000台是固定的，终点状态s6没有要求。这种情况下得到最优决策称为初始端固定终点自由的最优策略。 如果终点附加一定的条件，则问题就称为“终端固定问题”。例如，规定在第5年度结束时仍要保持500台机器完好（而不是278台），应如何安排生产才能使得总产量最大？ 下面来分析： 根据终点条件有 可得5动态规划的应用(2)* 显然，由于固定了终点的状态，x5的取值

46、受到了约束。因此有 类似的， 容易解得 ，f4(s4)=21.7s4-7500。5动态规划的应用(2)* 依次类推，得 f3(s3)=24.5s3-7500 f2(s2)=27.1s2-7500 f1(s1)=29.4s1-7500 再采用顺序方法递推计算各年的状态，有 s1=1000， 5动态规划的应用(2)* 可见，为了使终点完好的机器数量增加到500台，需要安排前四年中全部完好机器都要投入低负荷生产，且在第5年，也只能全部投入高负荷。 相应的最优指标为 f1(s1)=29.4s1-750021900。 可以看到，因为增加了附加条件，总产量f1(s1)要比终点自由情况下的产量要低。二、离散

47、随机性动态规划 随机型的动态规划是指状态的转移律是不确定的，即对给定的状态和决策，下一阶段的到达状态是具有确定概率分布的随机变量，这个概率分布由本阶段的状态和决策完全确定。随机型动态规划的基本结构如下图： 5动态规划的应用(2)* sk状态 xk决策概率k阶段的收益p1p2pN.k+1阶段的状态sk+1c1c2cN 1 2N5动态规划的应用(2)* 图中N表示第k+1阶段可能的状态数，p1、p2、pN为给定状态sk和决策xk的前提下，可能达到下一个状态的概率。ci为从k阶段状态sk转移到k+1 阶段状态为i时的指标函数值。 在随机性的动态规划问题中，由于下一阶段到达的状态和阶段的效益值不确定，只能根据各阶段的期望效益值进行优化。离散随机性动态规划 例2 某公司承担一种新产品研制任务，合同要求三个月内交出一件合格的样品，否则将索赔2000元。根据有经验的技术人员估计，试制品合格的概率为0.4，每次试制一批的装配费为200元，每件产品的制造成本为100元。每次试制的周期为1个月。问该如何安排试制，