大学精品课件：第七章 动态规划.ppt

1、第七章第七章 动动 态态 规规 划划(Dynamic programming)2、动态规划模型的建立和求解、动态规划模型的建立和求解3、动态规划的应用：、动态规划的应用：最短路问题；背包问题；最短路问题；背包问题；生产与存储问题；设备更新问题；复合系统工作可生产与存储问题；设备更新问题；复合系统工作可靠性问题；机器负荷问题；静态规划问题；资源分靠性问题；机器负荷问题；静态规划问题；资源分配问题。配问题。充分理解充分理解掌握技巧掌握技巧主要内容主要内容1 1、动态规划的基本概念、基本思想、动态规划的基本概念、基本思想一、多阶段决策问题的典型例子：一、多阶段决策问题的典型例子：第一节第一节 动态规

2、划概述动态规划概述1.生产决策问题生产决策问题但是但是不是一种算法。必须对具体问题进行具体分析，不是一种算法。必须对具体问题进行具体分析，运用动态规划的原理和方法，建立相应的模型，然运用动态规划的原理和方法，建立相应的模型，然后再用动态规划方法去求解。后再用动态规划方法去求解。动态规划是解决多阶段决策问题的一种有效方法。动态规划是解决多阶段决策问题的一种有效方法。例：已知工厂对某台机器的每月生产能力和需求方的需求例：已知工厂对某台机器的每月生产能力和需求方的需求量如下表，并且知道一月份生产前已有一台库存，现量如下表，并且知道一月份生产前已有一台库存，现制定制定3个月的生产计划，使生产与存储的总

3、成本最少？个月的生产计划，使生产与存储的总成本最少？月份月份需求量需求量生产能力生产能力存储限制存储限制 生产成本生产成本存储费存储费12328001502323700150333210002001月份月份2月份月份3月份月份S S1 1=1=1生产量生产量x x1 1S S2 2=S=S1 1+x+x1 1-D-D1 1生产量生产量x x2 2生产量生产量x x3 3S S3 3=S=S2 2+x+x2 2-D-D2 2V V1 1=800 x=800 x1 1+150S+150S1 1V V2 2=700 x=700 x2 2+150S150S2 2V V3 3=1000 x=1000 x

4、3 3+200S200S3 3S S4 4=0=02.机器负荷分配问题：机器负荷分配问题：年初完好年初完好机器机器S高负荷高负荷x低负荷低负荷(s-x)完好率完好率a(0a1)完好率完好率b(0b1)年产量年产量g(x)年产量年产量h(s-x)假定开始生产时完好的机器数量为假定开始生产时完好的机器数量为s1，要求制定一个要求制定一个五年计划，在五年计划，在每年开始时，决定如何重新分配完好的机器每年开始时，决定如何重新分配完好的机器在两种不同的负荷下生产的数量在两种不同的负荷下生产的数量，使在五年内产品的总产，使在五年内产品的总产量达到最高。量达到最高。第第1年年第第2年年第第5年年S S1 1

5、高负荷高负荷X X1 1S5=ax4+b(s4-x4)S S2 2=ax=ax1 1+b(sb(s1 1-x-x1 1)高负荷高负荷x x2 2高负荷高负荷x5S3=ax2+b(s2-x2)V V1 1=g(x=g(x1 1)+)+h(sh(s1 1-x-x1 1)V2=g(x2)+h(s2-x2)V5=g(x5)+h(s5-x5)3.最短路问题最短路问题：给定一个交通网络图如下，其：给定一个交通网络图如下，其中两点之间的数字表示距离（或花费），试求从中两点之间的数字表示距离（或花费），试求从A点点到到G点的最短距离（总费用最小）。点的最短距离（总费用最小）。123456AB1B2C1C2C3

6、C4D1D2D3E1E2E3F1F2G531368763685338422213335256643 4.4.不包含时间因素线性规划、非线性规划等静不包含时间因素线性规划、非线性规划等静态的规划问题（本质上是一次决策问题）也可以通态的规划问题（本质上是一次决策问题）也可以通过适当地引入阶段的概念，应用动态规划方法加以过适当地引入阶段的概念，应用动态规划方法加以解决。解决。0max11iniiinixcxxz例例:分割问题分割问题cx1x2xnx3二、解题思路二、解题思路：把多阶段的决策问题转化为依次把多阶段的决策问题转化为依次求解多个单阶段的决策问题。求解多个单阶段的决策问题。(以最短路问题为例

7、以最短路问题为例)41234AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G5313687636853384222133352566435637597681310912131618三、应用范围三、应用范围1、动态、动态2、静态、静态四、缺点四、缺点1、建模后，没有统一的方法、建模后，没有统一的方法2、维数障碍、维数障碍五、分类五、分类1、确定型（连续型、离散型）、确定型（连续型、离散型）2、随机型（连续型、离散型）、随机型（连续型、离散型）一、基本概念一、基本概念 1、阶段：、阶段：把一个问题的过程，恰当地分为若干个相互联系的把一个问题的过程，恰当地分为若干个相互联系的阶段阶段，以

8、，以便于按一定的次序去求解。便于按一定的次序去求解。描述阶段的变量称为描述阶段的变量称为阶段变量阶段变量,用用k表示表示。阶段的划分，一般。阶段的划分，一般是根据时间和空间的自然特征来进行的，但要便于问题转化为多是根据时间和空间的自然特征来进行的，但要便于问题转化为多阶段决策。阶段决策。2、状态：表示每个阶段开始所处的、状态：表示每个阶段开始所处的自然状况或客观条件自然状况或客观条件。通。通常一个阶段有若干个状态，描述过程状态的变量称为常一个阶段有若干个状态，描述过程状态的变量称为状态变量状态变量,用用Sk表示表示。年、月、年、月、路段路段一个数、一个数、一组数、一组数、一个向一个向量量 状态

9、变量的取值有一定的允许集合或范围，此集合称为状态变量的取值有一定的允许集合或范围，此集合称为状态状态允许集合允许集合。第二节第二节 动态规划的基本概念动态规划的基本概念 3、决策：表示当过程处于某一阶段的某个状态时，、决策：表示当过程处于某一阶段的某个状态时，可以作出不同的决定，从而确定下一阶段的状态可以作出不同的决定，从而确定下一阶段的状态，这这种决定称为种决定称为决策决策。描述决策的变量，称为描述决策的变量，称为决策变量决策变量,用用Uk(Sk)。决策变。决策变量是状态变量的函数。可用一个数、一组数或一向量量是状态变量的函数。可用一个数、一组数或一向量（多维情形）来描述。（多维情形）来描述

10、。在实际问题中决策变量的取值往往在某一范围之内，在实际问题中决策变量的取值往往在某一范围之内，此范围称为此范围称为允许决策集合允许决策集合,用用Dk(Sk)表示表示。4 4、状态转移方程、状态转移方程状态转移方程是确定过程由一状态转移方程是确定过程由一个状态到另一个状态的演变过个状态到另一个状态的演变过程。如果第程。如果第k阶段状态变量阶段状态变量sk的的值、该阶段的决策变量一经确值、该阶段的决策变量一经确定，第定，第k+1阶段状态变量阶段状态变量sk+1的的值也就确定。值也就确定。),(),(),(221112211231112kkkkusususTsususTsusTs 图示如下：图示如下

11、：12ks1u1s2u2s3skuksk+1 能用动态规划方法求解的多阶段决策过程是一类能用动态规划方法求解的多阶段决策过程是一类特殊的多阶段决策过程，即特殊的多阶段决策过程，即具有无后效性具有无后效性的多阶段的多阶段决策过程。决策过程。如果状态变量不能满足无后效性的要求，应适当如果状态变量不能满足无后效性的要求，应适当地改变状态的定义或规定方法。地改变状态的定义或规定方法。),(),(),(122231112kkkkusTsusTsusTs 动态规划中能动态规划中能处理的状态转移处理的状态转移方程的形式方程的形式。状态具有无后效性的多阶段决策过程的状态转状态具有无后效性的多阶段决策过程的状态

12、转移方程如下移方程如下无后效性无后效性(马尔可夫性马尔可夫性)如果某阶段状态给定后，则在这个阶段以后过程如果某阶段状态给定后，则在这个阶段以后过程的发展不受这个阶段以前各段状态的影响；的发展不受这个阶段以前各段状态的影响；过程的过去历史只能通过当前的状态去影响它未过程的过去历史只能通过当前的状态去影响它未来的发展；来的发展；构造动态规划模型时，要充分注意是否满足构造动态规划模型时，要充分注意是否满足无后效性的要求；无后效性的要求；5、策略：是一个按顺序排列的决策组成的集合。在实际问、策略：是一个按顺序排列的决策组成的集合。在实际问题中，可供选择的策略有一定的范围，称为题中，可供选择的策略有一定

13、的范围，称为允许策略集合允许策略集合。从允许策略集合中找出达到最优效果的策略称为从允许策略集合中找出达到最优效果的策略称为最优策略最优策略。全过程策略：全过程策略：U1(S1),U2(S2),Un(Sn)P1n=Ui(Si),i=1,n子过程策略：子过程策略：Uk(Sk),Uk+1(Sk+1),Un(Sn)Pkn=Ui(Si),i=k,n6、阶段指标：、阶段指标：Vk(Sk,Uk),k阶段，阶段，Sk状态下，作出状态下，作出Uk决策带决策带来的效果。在不同的问题中，指标的含义是不同的，它可来的效果。在不同的问题中，指标的含义是不同的，它可能是距离、利润、成本、产量或资源消耗等。能是距离、利润、

14、成本、产量或资源消耗等。7、指标函数：、指标函数：Vkn(Sk,Pkn),k阶段，阶段，Sk状态下，作出状态下，作出Pkn子策子策略带来的效果。动态规划模型的指标函数，应具有可分离略带来的效果。动态规划模型的指标函数，应具有可分离性，并满足性，并满足递推递推关系。关系。阶段指标与指标函数的关系有两种：阶段指标与指标函数的关系有两种：1）指标函数是它所含有的各阶段的阶段指标之和。）指标函数是它所含有的各阶段的阶段指标之和。即即Vkn(Sk,Pkn）=Vj(Sj,Uj),j=k,n那么有那么有Vkn(Sk,Pkn）=Vk(Sk,Uk）+Vk+1 n(Sk+1,Pk+1 n）2）指标函数是它所含有的

15、各阶段的阶段指标之积。）指标函数是它所含有的各阶段的阶段指标之积。即即Vkn(Sk,Pkn）=Vj(Sj,Uj),j=k,n 那么有那么有Vkn(Sk,Pkn）=Vk(Sk,Uk）Vk+1 n(Sk+1,Pk+1 n）8、最优指标函数：指标函数的最优值，称为、最优指标函数：指标函数的最优值，称为最优指标最优指标函数函数。用。用fk(Sk)=optVkn(Sk,Pkn)opt表示最优化，常取表示最优化，常取max或或min。1、Bellman最优性定理最优性定理一个过程的最优策略具有这样的性质：即无论初始状一个过程的最优策略具有这样的性质：即无论初始状态及初始决策如何，对于先前决策所形成的状态而

16、言，态及初始决策如何，对于先前决策所形成的状态而言，其以后所有的决策应构成最优策略。其以后所有的决策应构成最优策略。换句话说，最优策略只能由最优子策略构成。换句话说，最优策略只能由最优子策略构成。2、思想方法：在求解过程中，各阶段的状态和决策，、思想方法：在求解过程中，各阶段的状态和决策，对其后面的阶段来说，只影响其初始状态，而不影响对其后面的阶段来说，只影响其初始状态，而不影响后面的最优策略。后面的最优策略。无后效性无后效性方法：方法：“顺序编号，逆序求解顺序编号，逆序求解”二、动态规划的基本思想和基本方程二、动态规划的基本思想和基本方程 3、基本方程、基本方程 根据最优性定理，可以写出动态

17、规划递推方程，根据最优性定理，可以写出动态规划递推方程，即基本方程：即基本方程：Vkn(Sk,Pkn）=Vj(Sj,Uj),j=k,n时，时，fk(Sk)=opt Vk(Sk,Uk）+fk+1(Sk+1)(k=n,n-1,1)fn+1(Sn+1)=0Vkn(Sk,Pkn）=Vj(Sj,Uj),j=k,n时，时，fk(Sk)=opt Vk(Sk,Uk）fk+1(Sk+1)(k=n,n-1,1)fn+1(Sn+1)=1其中的其中的fn+1(Sn+1)为边界条件。为边界条件。三、建立动态规划模型的步骤三、建立动态规划模型的步骤 1 1、划分阶段、划分阶段划分阶段是运用动态规划求解多阶段决策问题的第一

18、划分阶段是运用动态规划求解多阶段决策问题的第一步，在确定多阶段特性后，按时间或空间先后顺序，步，在确定多阶段特性后，按时间或空间先后顺序，将过程划分为若干相互联系的阶段。对于静态问题要将过程划分为若干相互联系的阶段。对于静态问题要人为地赋予人为地赋予“时间时间”概念，以便划分阶段。概念，以便划分阶段。2 2、正确选择状态变量、正确选择状态变量选择变量既要能确切描述过程演变又要满足无后效性，选择变量既要能确切描述过程演变又要满足无后效性，而且各阶段状态变量的取值能够确定。一般地，状态而且各阶段状态变量的取值能够确定。一般地，状态变量的选择是从过程演变的特点中寻找。变量的选择是从过程演变的特点中寻

19、找。3 3、确定决策变量及允许决策集合、确定决策变量及允许决策集合通常选择所求解问题的关键变量作为决策变量，同时通常选择所求解问题的关键变量作为决策变量，同时要给出决策变量的取值范围，即确定允许决策集合。要给出决策变量的取值范围，即确定允许决策集合。4 4、确定状态转移方程、确定状态转移方程根据根据k 阶段状态变量和决策变量，写出阶段状态变量和决策变量，写出k+1阶段状态变阶段状态变量，状态转移方程应当具有递推关系。量，状态转移方程应当具有递推关系。5 5、确定阶段指标函数和最优指标函数，建立动态规、确定阶段指标函数和最优指标函数，建立动态规划基本方程划基本方程 阶段指标函数是指第阶段指标函数

20、是指第k 阶段的收益，最优指标函数阶段的收益，最优指标函数是指从第是指从第k 阶段状态出发到第阶段状态出发到第n 阶段末所获得收益的最阶段末所获得收益的最优值，最后写出动态规划基本方程。优值，最后写出动态规划基本方程。以上五步是建立动态规划数学模型的一般步骤。由于以上五步是建立动态规划数学模型的一般步骤。由于动态规划模型与线性规划模型不同，动态规划模型没有统动态规划模型与线性规划模型不同，动态规划模型没有统一的模式，建模时必须根据具体问题具体分析，只有通过一的模式，建模时必须根据具体问题具体分析，只有通过不断实践总结，才能较好掌握建模方法与技巧。不断实践总结，才能较好掌握建模方法与技巧。例一、

21、从例一、从A 地到地到D 地要铺设一条煤气管道地要铺设一条煤气管道,其中需经过其中需经过两级中间站，两点之间的连线上的数字表示距离，如两级中间站，两点之间的连线上的数字表示距离，如图所示。问应该选择什么路线，使总距离最短？图所示。问应该选择什么路线，使总距离最短？AB1B2C1C2C3D24333321114 第三节第三节 动态规划应用举例动态规划应用举例一、最短路径问题一、最短路径问题 解：整个计算过程分三个阶段，从最后一个阶段开始。解：整个计算过程分三个阶段，从最后一个阶段开始。第三阶段（第三阶段（C D）：）：C 有三条路线到终点有三条路线到终点D。AB1B2C1C2C3D2433332

22、1114DC1C2C3显然有显然有 f3(C1)=1 ；f3(C2)=3 ；f3(C3)=4 d(B1,C1)+f3(C1)3+1 f2(B1)=min d(B1,C2)+f3(C2)=min 3+3 d(B1,C3)+f3(C3)1+4 4 =min 6 =4 5第二阶段（第二阶段（B C）：）：B 到到C 有六条路线。有六条路线。AB1B2C1C2C3D24333321114DC1C2C3B1B2(最短路线为最短路线为B1C1 D)d(B2,C1)+f3(C1)2+1 f2(B2)=min d(B2,C2)+f3(C2)=min 3+3 d(B2,C3)+f3(C3)1+4 3 =min

23、6 =3 5AB1B2C1C2C3D24333321114DC1C2C3B1B2(最短路线为最短路线为B2C1 D)第一阶段（第一阶段（A B）：）：A 到到B 有二条路线有二条路线。f3(A)1=d(A,B1)f2(B1)246 f3(A)2=d(A,B2)f2(B2)437 f1(A)=min =min6,7=6d(A,B1)f2(B1)d(A,B2)f2(B2)(最短路线为最短路线为AB1C1 D)AB1B2C1C2C3D24333321114DC1C2C3B1B2AAB1B2C1C2C3D24333321114DC1C2C3B1B2A最短路线为最短路线为 AB1C1 D 路长为路长为

24、6表上作业法表上作业法K=3C1C2C3DDD134DDD000DDDK=2B1C13C1阶段阶段k 状态状态Sk决策决策Uk阶段指标阶段指标Vk状态转移状态转移Sk+1fk+1(Sk+1)fk(Sk)Uk*134134C2C331C2C3465C1B2C1C2312C1C2C313436K=1AB2B124B1B2C14367B15C3AB1B2C1C2C3D24333321114*求从求从A到到E的最短路径的最短路径路线为路线为AB2C1 D1 E，最短路径为最短路径为1919AB2B1B3C1C3D1D2EC25214112610104312111396581052练习：练习：1 现有数

25、量为现有数量为a的资源，用于生产的资源，用于生产n种产品，第种产品，第i种产品种产品分配分配xi，带来gi(xi)收益，问如何分配使总收益最大？收益，问如何分配使总收益最大？nixaxxgZiniiniii.2.1 0)(max11据此，有下式：据此，有下式：二、资源分配问题二、资源分配问题一维资源分配一维资源分配 求解：求解：阶段：阶段：k=1，2，,n,对应第对应第k种产品分配资源的过程种产品分配资源的过程状态状态Sk:表示可供分配第表示可供分配第k种到第种到第n种产品分配资源的总种产品分配资源的总量量决策变量决策变量xk:表示分配给第表示分配给第k种产品的资源量种产品的资源量状态转移方程

26、状态转移方程:Sk+1=Sk xk阶段指标阶段指标:V k=gk(xk)基本方程基本方程:fk(Sk)=maxgk(xk)+fk+1(Sk+1)(k=n,n-1,1)fn+1(Sn+1)=0 例例:两台设备分配给三个工厂两台设备分配给三个工厂,这三个工厂使用这几台设备所产这三个工厂使用这几台设备所产生的效益分别为如下表生的效益分别为如下表,问如何分配使效益最大问如何分配使效益最大?设设备备工厂工厂012A037B0510C046阶段：阶段：k=1，2，3,对应第对应第k个工厂分配设备的过程个工厂分配设备的过程状态状态Sk:表示可供分配第表示可供分配第k个到第个到第3个工厂的设备的台数个工厂的设

27、备的台数决策变量决策变量xk:表示分配给第表示分配给第k个工厂的设备数个工厂的设备数状态转移方程状态转移方程:Sk+1=Sk xk阶段指标阶段指标:V k=gk(xk)基本方程基本方程:fk(Sk)=maxgk(xk)+fk+1(Sk+1)(k=3,2,1)f4(S4)=0阶段阶段k状态状态Sk决策决策Uk阶段指阶段指标标Vk状态转状态转移移Sk+1fk+1(Sk+1)fk(Sk)最优策最优策略略Uk*K=3021012046000000046012K=200000001010144500512012051021640691002K=12012037210105010870因此因此z*=10,

28、X*=(0,2,0)设备设备工厂工厂012A037B0510C046*练习：某公司打算在练习：某公司打算在3个不同的地区设置个不同的地区设置4个销售点，个销售点，根据市场部门估计，在不同地区设置不同数量的销根据市场部门估计，在不同地区设置不同数量的销售点每月可得到的利润如表所示。试问在各地区如售点每月可得到的利润如表所示。试问在各地区如何设置销售点可使每月总利润最大。何设置销售点可使每月总利润最大。地地区区销售点销售点01234123000161210251714302116322217建模：建模：阶段：阶段：k=1，2，3,对应第对应第k个地区分配销售点的过程个地区分配销售点的过程状态状态S

29、k:表示可供分配第表示可供分配第k个到第个到第3个地区的销售点的数量个地区的销售点的数量决策变量决策变量xk:表示分配给第表示分配给第k个地区的销售点数量个地区的销售点数量状态转移方程状态转移方程:Sk+1=Sk xk阶段指标阶段指标:V k=gk(xk)基本方程基本方程:fk(Sk)=maxgk(xk)+fk+1(Sk+1)(k=3,2,1)f4(S4)=0地地区区销售点销售点01234123000161210251714302116322217 x1=2，x2=1，x3=1，f3(4)=47 有一个徒步旅行者，其可携带物品重量的限度为有一个徒步旅行者，其可携带物品重量的限度为a 公公斤，设

30、有斤，设有n 种物品可供他选择装入包中。已知每种物品种物品可供他选择装入包中。已知每种物品的重量及使用价值（作用），问此人应如何选择携带的重量及使用价值（作用），问此人应如何选择携带的物品（各几件），使所起作用（使用价值）最大？的物品（各几件），使所起作用（使用价值）最大？物品物品 1 2 j n重量（公斤重量（公斤/件）件）a1 a2 aj an每件使用价值每件使用价值 c1 c2 cj cn 这就是背包问题。类似的还有工厂里的下料问题、这就是背包问题。类似的还有工厂里的下料问题、运输中的货物装载问题、人造卫星内的物品装载问题运输中的货物装载问题、人造卫星内的物品装载问题等。等。三、背包问题

31、三、背包问题设设xj 为第为第j 种物品的装件数（非负整数）则问题的数学种物品的装件数（非负整数）则问题的数学模型如下：模型如下：).2.1(0max1njxaxaxcZjnijjjnjjj 且且为为整整数数例题：求下面背包问题的最优解例题：求下面背包问题的最优解物品物品 1 2 3重量（公斤）重量（公斤）3 2 5使用价值使用价值 8 5 12Maxz=8x1+5x2+12x3 3x1+2x2+5x35 x1,x2,x30,且为整数且为整数用动态规划方法求解阶段：阶段：k=1，2，3,对应第对应第k种物品的选择过程种物品的选择过程状态状态Sk:表示可供分配第表示可供分配第k种到第种到第3种物

32、品的重量种物品的重量决策变量决策变量xk:表示分配给第表示分配给第k种物品的件数种物品的件数状态转移方程状态转移方程:S1=5,S2=S1 3x1,S3=S2 2x2阶段指标阶段指标:V 1=8x1,V 2=5x2,V 3=12x3基本方程基本方程:fk(Sk)=maxVk+fk+1(Sk+1)(k=3,2,1)f4(S4)=0阶段阶段k状态状态Sk决策决策Uk阶段指阶段指标标Vk状态转状态转移移Sk+1fk+1(Sk+1)fk(Sk)最优策最优策略略Uk*K=30213500001000012012300000000001200001K=225015210005*10205105301200

33、125100K=1501085212512*因此因此z*=13,X*=(1,1,0)01131Maxz=8x1+5x2+12x3 3x1+2x2+5x35 x1,x2,x30,且为整数且为整数 练习：某厂生产三种产品，各种产品重量与利润练习：某厂生产三种产品，各种产品重量与利润的关系如表所示。现将此三种产品运往市场出售，的关系如表所示。现将此三种产品运往市场出售，运输能力总重量不超过运输能力总重量不超过 6 吨，问如何安排运输，使吨，问如何安排运输，使总利润最大？总利润最大？种类种类 1 2 3重量（吨重量（吨/公斤）公斤）2 3 4 单件利润（元）单件利润（元）80 130 180Maxz=

34、80 x1+130 x2+180 x3 2x1+3x2+4x36 x1,x2,x30，且为整数，且为整数用动态规划方法求解阶段：阶段：k=1，2，3,对应第对应第k种产品的选择过程种产品的选择过程状态状态Sk:表示可供分配第表示可供分配第k种到第种到第3种产品的重量种产品的重量决策变量决策变量xk:表示分配给第表示分配给第k种物品的件数种物品的件数状态转移方程状态转移方程:S1=6,S2=S1 2x1,S3=S2 3x2阶段指标阶段指标:V 1=80 x1,V 2=130 x2,V 3=180 x3基本方程基本方程:fk(Sk)=maxVk+fk+1(Sk+1)(k=3,2,1)f4(S4)=

35、0求解见板书求解见板书最优方案：最优方案：X1=（0 0，2 2，0 0）X2=（1 1，0 0，1 1）Z=260=260四、机器负荷问题四、机器负荷问题例：已知在第一年初有例：已知在第一年初有1000台完好机器，用于高低负荷生产，台完好机器，用于高低负荷生产，高负荷生产时完好率高负荷生产时完好率0.7,产值每台产值每台10万元，低负荷生产时万元，低负荷生产时完好率完好率0.8,产值每台产值每台8万元，作五年决策方案，使产值最万元，作五年决策方案，使产值最大？大？解：阶段：解：阶段：k=1,2,5,对应第对应第k年制定生产计划的过程年制定生产计划的过程状态状态Sk:表示第表示第k年初完好的机

36、器数量年初完好的机器数量决策变量决策变量xk:表示第表示第k年用于高负荷生产的数量年用于高负荷生产的数量状态转移方程状态转移方程:Sk+1=0.7 xk+0.8(Sk xk)=0.8Sk 0.1xk阶段指标阶段指标:V k=10 xk+8(Sk-xk)=8Sk+2xk基本方程基本方程:fk(Sk)=maxVk+fk+1(Sk+1)(k=5,4,3,2,1)f6(S6)=0求解见板书求解见板书五、求解静态规划问题五、求解静态规划问题求解：求解：Maxz=4x12-x22+2x32+12 3x1+2x2+x39 x1,x2,x30解：阶段：解：阶段：k=1,2,3,对应给第对应给第k个变量赋值的过

37、程个变量赋值的过程状态状态Sk:决策变量决策变量xk:表示第表示第k个变量的值个变量的值状态转移方程状态转移方程:S1=9,S2=S1 3x1,S3=S2 2x2阶段指标函数阶段指标函数:V 1=4x12,V 2=-x22,V 3=2x32+12基本方程基本方程:fk(Sk)=maxVk+fk+1(Sk+1)(k=3,2,1)f4(S4)=0求解见板书求解见板书六、复合系统工作可靠性问题六、复合系统工作可靠性问题 某种机器的工作系统由某种机器的工作系统由n个部件串联组成，只要有一个部个部件串联组成，只要有一个部件失灵，整个系统就不能正常工作。为了提高系统工作的件失灵，整个系统就不能正常工作。为

38、了提高系统工作的可靠性，在每个部件上均装有主要元件的备用件，并设计可靠性，在每个部件上均装有主要元件的备用件，并设计了备用元件自动投入装备，显然，备用元件越多，整个系了备用元件自动投入装备，显然，备用元件越多，整个系统工作的可靠性就越大，但备用元件增多也会导致系统的统工作的可靠性就越大，但备用元件增多也会导致系统的成本、重量体积相应增大，工作精度降低，因此，在考虑成本、重量体积相应增大，工作精度降低，因此，在考虑上述限制条件下，如何选择各部件的备用元件数，使整个上述限制条件下，如何选择各部件的备用元件数，使整个系统的工作可靠性最大？系统的工作可靠性最大？建模：设部件建模：设部件i装有装有xi个

39、备用元件时，正常工作的概率为个备用元件时，正常工作的概率为Pi(xi),那么整个系统正常工作的概率那么整个系统正常工作的概率Z=Pi(xi)（i=1，,n）,设部件设部件i的单位重量级的单位重量级wi,那么总重量不超那么总重量不超过过w的情况下的情况下,如何配备备用件如何配备备用件,使使Z最大最大?且为整数,0)(max11iniiiiniixxxPz用动态规划方法求解阶段：阶段：k=1，2，n,对应给第对应给第k个部件分配配件的过程个部件分配配件的过程状态状态Sk:表示可供分配第表示可供分配第k个到第个到第n个部件的总重量个部件的总重量决策变量决策变量xk:表示分配给第表示分配给第k个部件配

40、备的备用件数个部件配备的备用件数状态转移方程状态转移方程:Sk+1=Skwkxk阶段指标阶段指标:V k=Pk(xk)基本方程基本方程:fk(Sk)=maxVk fk+1(Sk+1)(k=n,2,1)fk+1(Sk+1)=1例例:三个科研小组分别对某一项目的一个部件研究三个科研小组分别对某一项目的一个部件研究,成功率分成功率分别为别为0.6,0.4,0.2,为提高成功率为提高成功率,可以给各组增加人员可以给各组增加人员,现有两现有两个人可以加入到研究工作中个人可以加入到研究工作中,问如何分配人手问如何分配人手,使项目总成功使项目总成功率最大率最大?成功率成功率 一 二 三0 0 0.6 0.4

41、 0.21 1 0.8 0.6 0.52 2 0.85 0.8 0.7阶段：阶段：k=1，2，3,对应给第对应给第k个小组分配人手的过程个小组分配人手的过程状态状态Sk:表示可供分配第表示可供分配第k个到第个到第3个小组的总人数个小组的总人数决策变量决策变量xk:表示分配给第表示分配给第k个小组的人数个小组的人数状态转移方程状态转移方程:Sk+1=Skxk阶段指标阶段指标:V k=Pk(xk)基本方程基本方程:fk(Sk)=maxVk fk+1(Sk+1)(k=3,2,1)f4(S4)=1阶段阶段k状态状态Sk决策决策Uk阶段指阶段指标标Vk状态转状态转移移Sk+1fk+1(Sk+1)fk(S

42、k)最优策最优策略略Uk*K=30210120.20.50.70001110.20.50.7012K=2000.400.20.0801010.410.50.20.600.20.12020120.40.60.8210.70.50.20.280.300.1601K=120120.60.80.852100.30.20.080.180.160.0680因此因此z*=0.18,X*=(0,1,1)小组小组人手人手一一二二三三00.60.40.210.80.60.520.850.80.7*例例:分割问题分割问题阶段：阶段：k=1，2，,n,对应给第对应给第k个变量赋值的过程个变量赋值的过程状态状态Sk:表

43、示可供分配第表示可供分配第k个到第个到第n个变量赋值的总和个变量赋值的总和决策变量决策变量xk:表示给第表示给第k个变量赋的值个变量赋的值状态转移方程状态转移方程:Sk+1=Skxk阶段指标阶段指标:V k=xk基本方程基本方程:fk(Sk)=maxVk fk+1(Sk+1)(k=n,2,1)fn+1(Sn+1)=1求解见板书求解见板书0max11iniiinixcxxz七、生产与存储问题七、生产与存储问题例：已知工厂对某台机器的每月生产能力和需求方的需求例：已知工厂对某台机器的每月生产能力和需求方的需求量如下表，并且知道一月份生产前已有一台库存，现量如下表，并且知道一月份生产前已有一台库存，

44、现制定制定3个月的生产计划，使生产成本最少？个月的生产计划，使生产成本最少？月份月份需求量需求量生产能力生产能力存储限制存储限制 生产成本生产成本存储费存储费12328001502323700150333210002001月份月份2月份月份3月份月份S S1 1=1=1生产量生产量x x1 1S S2 2=S=S1 1+x+x1 1-D-D1 1生产量生产量x x2 2生产量生产量x x3 3S S3 3=S=S2 2+x+x2 2-D-D2 2V V1 1=800 x=800 x1 1+150S+150S1 1V V2 2=700 x=700 x2 2+150S150S2 2V V3 3=1

45、000 x=1000 x3 3+200S200S3 3S S4 4=0=0建立动态规划模型建立动态规划模型阶段：阶段：k=1，2，3,对应第对应第k月制定生产计划的过程月制定生产计划的过程状态状态Sk:表示第表示第k月初生产前的库存量月初生产前的库存量决策变量决策变量xk:表示第表示第k月生产量月生产量状态转移方程状态转移方程:Sk+1=Sk+xk Dk阶段指标阶段指标:V k=第第k月生产费用月生产费用+库存费用库存费用基本方程基本方程:fk(Sk)=min Vk+fk+1(Sk+1)(k=3,2,1)f4(S4)=0阶段阶段k状态状态Sk决策决策Uk阶段指阶段指标标Vk状态转状态转移移Sk

46、+1fk+1(Sk+1)fk(Sk)最优策最优策略略Uk*K=301323000220000003000220032K=21215500300045502212100017000130002200400039002K=112317502550124550390063006450因此因此z*=6300,X*=(2,2,3)*月份月份需求需求量量生产生产能力能力存储存储限制限制生产生产成本成本存储存储费费1232800150232370015033321000200*2八、设备更新问题八、设备更新问题 经济学上常说的设备更新问题即是：某种设备应经济学上常说的设备更新问题即是：某种设备应该在多少年后

47、进行更换，方能使计划期内的总收该在多少年后进行更换，方能使计划期内的总收入最大？入最大？三种函数关系三种函数关系效益函数效益函数rk(t):在第在第k年设备已使用年设备已使用 t年，再使用一年的收益年，再使用一年的收益维修费用函数维修费用函数Uk(t):在第在第k年设备已使用年设备已使用 t年，再使用一年的年，再使用一年的维修费用维修费用更新费用函数更新费用函数Ck(t):在第在第k年卖掉一台役龄为年卖掉一台役龄为t年的设备，买年的设备，买进一台新设备的更新净费用进一台新设备的更新净费用建立动态规划模型阶段：阶段：k=1，2，,n对应第对应第k年制定更新计划的过程年制定更新计划的过程状态状态S

48、k:表示第表示第k年初的设备役龄年初的设备役龄决策变量决策变量xk=0 表示更新设备表示更新设备 1 表示不更新设备表示不更新设备状态转移方程状态转移方程:Sk+1=Sk+1 xk=1 时时 1 xk=0 时时阶段指标阶段指标:V k=rk(Sk)-Uk(Sk)xk=1 时时 rk(0)-Uk(0)-Ck(Sk)xk=0 时时 基本方程基本方程:fk(Sk)=maxVk+fk+1(Sk+1)(k=n,n-1,1)fn+1(Sn+1)=0举例举例 设某台新设备的年效益及年均维修费、更新净设某台新设备的年效益及年均维修费、更新净费用费用(万元万元)如表所示，试确定今后如表所示，试确定今后5年内的更新年内的更新策略，使总收益最大？策略，使总收益最大？012345rk(t)54.543.7532.5Uk(t)0.511.522.53Ck(t)0.51.52.22.533.5解：如前所述建立动态规划模型，求解见板书。解：如前所述建立动态规划模型，求解见板书。