第七章_动态规划

1、第七章第七章 动动 态态 规规 划划 (Dynamic programming)动态规划的基本概念、基本思想动态规划的基本概念、基本思想动态规划模型的建立和求解动态规划模型的建立和求解动态规划的应用：动态规划的应用：背包问题；生产背包问题；生产经营问题；设备更新问题；复合系统经营问题；设备更新问题；复合系统工作可靠性问题工作可靠性问题 第一节第一节 动态规划动态规划 动态规划动态规划(Dynamic Programming)是用来解决是用来解决多阶段决策过程最优化的一种数量方法。其特多阶段决策过程最优化的一种数量方法。其特点在于，它可以把一个点在于，它可以把一个n 维决策问题变换为几个维决策问

2、题变换为几个一维最优化问题，从而一个一个地去解决。一维最优化问题，从而一个一个地去解决。 需指出：动态规划是求解某类问题的一种需指出：动态规划是求解某类问题的一种方法，是考察问题的一种途径，而不是一种算方法，是考察问题的一种途径，而不是一种算法。必须对具体问题进行具体分析，运用动态法。必须对具体问题进行具体分析，运用动态规划的原理和方法，建立相应的模型，然后再规划的原理和方法，建立相应的模型，然后再用动态规划方法去求解。用动态规划方法去求解。一、多阶段决策问题的典型例子：一、多阶段决策问题的典型例子： 1 . 1 . 生产决策问题生产决策问题：企业在生产过程中，由于：企业在生产过程中，由于需求

3、是随时间变化的，因此企业为了获得全年的最需求是随时间变化的，因此企业为了获得全年的最佳生产效益，就要在整个生产过程中逐月或逐季度佳生产效益，就要在整个生产过程中逐月或逐季度地地根据库存和需求决定生产计划。根据库存和需求决定生产计划。 2. 2. 机器负荷分配问题机器负荷分配问题：某种机器可以在高低两：某种机器可以在高低两种不同的负荷下进行生产。在高负荷下进行生产时，种不同的负荷下进行生产。在高负荷下进行生产时，产品的年产量产品的年产量g和投入生产的机器数量和投入生产的机器数量u1的关系为的关系为g=g(u1)12n状态状态决策决策状态状态决策决策状态状态状态状态决策决策 这时，机器的年完好率为

4、这时，机器的年完好率为a，即如果年初完好机，即如果年初完好机器的数量为器的数量为u，到年终完好的机器就为，到年终完好的机器就为au, 0a1。 在低负荷下生产时，产品的年产量在低负荷下生产时，产品的年产量h和投入生产和投入生产的机器数量的机器数量u2的关系为的关系为 h=h(u2) 假定开始生产时完好的机器数量为假定开始生产时完好的机器数量为s s1 1。要求制。要求制定一个五年计划，在定一个五年计划，在每年开始时，决定如何重新每年开始时，决定如何重新分配分配完好的完好的机器在两种不同的负荷下生产的数量机器在两种不同的负荷下生产的数量，使在五年内产品的总产量达到最高。使在五年内产品的总产量达到

5、最高。 相应的机器年完好率相应的机器年完好率b b, 0 , 0 b b11。 3. 3. 航天飞机飞行控制问题：由于航天飞机的航天飞机飞行控制问题：由于航天飞机的运动的环境是不断变化的，因此就要根据航天飞机运动的环境是不断变化的，因此就要根据航天飞机飞行在不同环境中的情况，不断地决定航天飞机的飞行在不同环境中的情况，不断地决定航天飞机的飞行方向和速度（状态），使之能最省燃料和实现飞行方向和速度（状态），使之能最省燃料和实现目的（如软着落问题）。目的（如软着落问题）。 不包含时间因素的静态决策问题（本质上是一不包含时间因素的静态决策问题（本质上是一次决策问题）也可以适当地引入阶段的概念，作为次

6、决策问题）也可以适当地引入阶段的概念，作为多阶段的决策问题用动态规划方法来解决。多阶段的决策问题用动态规划方法来解决。 4 4 . 线性规划、非线性规划等静态的规划问题也线性规划、非线性规划等静态的规划问题也可以通过适当地引入阶段的概念，应用动态规划方可以通过适当地引入阶段的概念，应用动态规划方法加以解决。法加以解决。 5 . 最短路问题最短路问题：给定一个交通网络图如下，其：给定一个交通网络图如下，其中两点之间的数字表示距离（或花费），试求从中两点之间的数字表示距离（或花费），试求从A点点到到G点的最短距离（总费用最小）。点的最短距离（总费用最小）。123456AB1B2C1C2C3C4D1

7、D2D3E1E2E3F1F2G531368763685338422213335256643二、解题思路二、解题思路三、应用范围三、应用范围1、动态、动态2、静态、静态四、缺点四、缺点1、建模后，没有统一的方法、建模后，没有统一的方法2、维数障碍、维数障碍 一、基本概念一、基本概念 1、阶段：、阶段： 把一个问题的过程，恰当地分为若干个相互联系的把一个问题的过程，恰当地分为若干个相互联系的阶段阶段，以便于按一定的次序去求解。，以便于按一定的次序去求解。 描述阶段的变量称为描述阶段的变量称为阶段变量阶段变量,用用k表示表示。阶段的划分，。阶段的划分，一般是根据时间和空间的自然特征来进行的，但要便于

8、一般是根据时间和空间的自然特征来进行的，但要便于问题转化为多阶段决策。问题转化为多阶段决策。2、状态：表示每个阶段开始所处的、状态：表示每个阶段开始所处的自然状况或客观自然状况或客观条件条件。通常一个阶段有若干个状态，描述过程状态的。通常一个阶段有若干个状态，描述过程状态的变量称为变量称为状态变量状态变量,用用Sk表示表示。年、月、年、月、路段路段一个数、一个数、一组数、一组数、一个向一个向量量 状态变量的取值有一定的允许集合或范围，此集合状态变量的取值有一定的允许集合或范围，此集合称为称为状态允许集合状态允许集合。第二节第二节 动态规划的基本概念动态规划的基本概念 3、决策：表示当过程处于某

9、一阶段的某个状态时，、决策：表示当过程处于某一阶段的某个状态时，可以作出不同的决定，从而确定下一阶段的状态可以作出不同的决定，从而确定下一阶段的状态，这这种决定称为种决定称为决策决策。 描述决策的变量，称为描述决策的变量，称为决策变量决策变量,用用Uk(Sk )。决策变。决策变量是状态变量的函数。可用一个数、一组数或一向量量是状态变量的函数。可用一个数、一组数或一向量（多维情形）来描述。（多维情形）来描述。 在实际问题中决策变量的取值往往在某一范围之内，在实际问题中决策变量的取值往往在某一范围之内，此范围称为此范围称为允许决策集合允许决策集合,用用Dk(Sk )表示表示。 4 4、状态转移方程

10、、状态转移方程状态转移方程是确定过程由状态转移方程是确定过程由一个状态到另一个状态的演一个状态到另一个状态的演变过程。如果第变过程。如果第k阶段状态阶段状态变量变量sk的值、该阶段的决策的值、该阶段的决策变量一经确定，第变量一经确定，第k+1阶段阶段状态变量状态变量sk+1的值也就确定。的值也就确定。),(),(),(221112211231112kkkkusususTsususTsusTs 图示如下：图示如下：12ks1u1s2u2s3skuksk+1 能用动态规划方法求解的多阶段决策过程是一类能用动态规划方法求解的多阶段决策过程是一类特殊的多阶段决策过程，即特殊的多阶段决策过程，即具有无后

11、效性具有无后效性的多阶段的多阶段决策过程。决策过程。 如果状态变量不能满足无后效性的要求，应适当如果状态变量不能满足无后效性的要求，应适当地改变状态的定义或规定方法。地改变状态的定义或规定方法。),(),(),(122231112kkkkusTsusTsusTs 动态规划中能动态规划中能处理的状态转移处理的状态转移方程的形式方程的形式。 状态具有无后效性的多阶段决策过程的状态转状态具有无后效性的多阶段决策过程的状态转移方程如下移方程如下无后效性无后效性( (马尔可夫性马尔可夫性) ) 如果某阶段状态给定后，则在这个阶段以后过程如果某阶段状态给定后，则在这个阶段以后过程的发展不受这个阶段以前各段

12、状态的影响；的发展不受这个阶段以前各段状态的影响； 过程的过去历史只能通过当前的状态去影响它未过程的过去历史只能通过当前的状态去影响它未来的发展；来的发展； 构造动态规划模型时，要充分注意是否满构造动态规划模型时，要充分注意是否满足无后效性的要求；足无后效性的要求；状态变量要满足无后效性的要求状态变量要满足无后效性的要求； 5 5、策略：是一个按顺序排列的决策组成的集合。在、策略：是一个按顺序排列的决策组成的集合。在实际问题中，可供选择的策略有一定的范围，称为实际问题中，可供选择的策略有一定的范围，称为允允许策略集合许策略集合。从允许策略集合中找出达到最优效果的。从允许策略集合中找出达到最优效

13、果的策略称为策略称为最优策略最优策略。全过程策略：全过程策略：U U1 1(S(S1 1), U), U2 2(S(S2 2), U), Un n(S(Sn n) )P P1n1n=U=Ui i(S(Si i), i=1,n), i=1,n子过程策略：子过程策略：U Uk k(S(Sk k), U), Uk+1k+1(S(Sk+1k+1), U), Un n(S(Sn n) )P Pknkn=U=Ui i(S(Si i), i=k,n), i=k,n6 6、阶段指标：、阶段指标：V Vk k(S(Sk k, U, Uk k),k),k阶段，阶段，S Sk k状态下，作出状态下，作出U Uk k

14、决决策带来的效果。策带来的效果。在不同的问题中，指标的含义是不同的，它在不同的问题中，指标的含义是不同的，它可能是距离、利润、成本、产量或资源消耗等。可能是距离、利润、成本、产量或资源消耗等。7 7、指标函数：、指标函数：V Vknkn(S(Sk k, P, Pknkn),k),k阶段，阶段，S Sk k状态下，作出状态下，作出P Pknkn子策略带来的效果。子策略带来的效果。动态规划模型的指标函数，应具有可分动态规划模型的指标函数，应具有可分离性，并满足离性，并满足递推递推关系。关系。 阶段指标与指标函数的关系有两种：阶段指标与指标函数的关系有两种：1）指标函数是它所含有的各阶段的阶段指标之

15、和。）指标函数是它所含有的各阶段的阶段指标之和。即即Vkn(Sk,Pkn）= Vj(Sj, Uj),j=k,n那么有那么有Vkn(Sk,Pkn）= Vk (Sk,Uk）+ Vk+1 n(Sk+1,Pk+1 n）2）指标函数是它所含有的各阶段的阶段指标之积。）指标函数是它所含有的各阶段的阶段指标之积。即即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

16、,Pkn)opt表示最优化，常取表示最优化，常取max或或min。 1、Bellman最优性定理最优性定理一个过程的最优策略具有这样的性质：即无论初始状一个过程的最优策略具有这样的性质：即无论初始状态及初始决策如何，对于先前决策所形成的状态而言，态及初始决策如何，对于先前决策所形成的状态而言，其以后所有的决策应构成最优策略。其以后所有的决策应构成最优策略。换句话说，最优策略只能由最优子策略构成。换句话说，最优策略只能由最优子策略构成。2、思想方法：在求解过程中，各阶段的状态和决策，、思想方法：在求解过程中，各阶段的状态和决策，对其后面的阶段来说，只影响其初始状态，而不影响对其后面的阶段来说，只

17、影响其初始状态，而不影响后面的最优策略。后面的最优策略。无后效性无后效性方法：方法：“顺序编号，逆序求解顺序编号，逆序求解”二、动态规划的基本思想和基本方程二、动态规划的基本思想和基本方程 3、基本方程、基本方程 根据最优性定理，可以写出动态规划递推方程，根据最优性定理，可以写出动态规划递推方程，即基本方程：即基本方程： Vkn(Sk,Pkn）= Vj(Sj, Uj),j=k,n时，时， fk(Sk)=opt Vk (Sk,Uk）+ fk+1(Sk+1) fn+1(Sn+1)=0Vkn(Sk,Pkn）= Vj(Sj, Uj),j=k,n时，时， fk(Sk)=opt Vk (Sk,Uk） fk

18、+1(Sk+1) fn+1(Sn+1)=1其中的其中的fn+1(Sn+1)为边界条件。为边界条件。 三、建立动态规划模型的步骤三、建立动态规划模型的步骤 1 1、划分阶段、划分阶段划分阶段是运用动态规划求解多阶段决策问题的第一划分阶段是运用动态规划求解多阶段决策问题的第一步，在确定多阶段特性后，按时间或空间先后顺序，步，在确定多阶段特性后，按时间或空间先后顺序，将过程划分为若干相互联系的阶段。对于静态问题要将过程划分为若干相互联系的阶段。对于静态问题要人为地赋予人为地赋予“时间时间”概念，以便划分阶段。概念，以便划分阶段。 2 2、正确选择状态变量、正确选择状态变量选择变量既要能确切描述过程演

19、变又要满足无后效性，选择变量既要能确切描述过程演变又要满足无后效性，而且各阶段状态变量的取值能够确定。一般地，状态而且各阶段状态变量的取值能够确定。一般地，状态变量的选择是从过程演变的特点中寻找。变量的选择是从过程演变的特点中寻找。 3 3、确定决策变量及允许决策集合、确定决策变量及允许决策集合通常选择所求解问题的关键变量作为决策变量，同时通常选择所求解问题的关键变量作为决策变量，同时要给出决策变量的取值范围，即确定允许决策集合。要给出决策变量的取值范围，即确定允许决策集合。 4 4、确定状态转移方程、确定状态转移方程根据根据k 阶段状态变量和决策变量，写出阶段状态变量和决策变量，写出k+1阶

20、段状态变阶段状态变量，状态转移方程应当具有递推关系。量，状态转移方程应当具有递推关系。 5 5、确定阶段指标函数和最优指标函数，建立动态规、确定阶段指标函数和最优指标函数，建立动态规划基本方程划基本方程 阶段指标函数是指第阶段指标函数是指第k 阶段的收益，最优指标函数阶段的收益，最优指标函数是指从第是指从第k 阶段状态出发到第阶段状态出发到第n 阶段末所获得收益的最阶段末所获得收益的最优值，最后写出动态规划基本方程。优值，最后写出动态规划基本方程。 以上五步是建立动态规划数学模型的一般步骤。由于以上五步是建立动态规划数学模型的一般步骤。由于动态规划模型与线性规划模型不同，动态规划模型没有统动态

21、规划模型与线性规划模型不同，动态规划模型没有统一的模式，建模时必须根据具体问题具体分析，只有通过一的模式，建模时必须根据具体问题具体分析，只有通过不断实践总结，才能较好掌握建模方法与技巧。不断实践总结，才能较好掌握建模方法与技巧。 例一、从例一、从A 地到地到D 地要铺设一条煤气管道地要铺设一条煤气管道,其中需经过其中需经过两级中间站，两点之间的连线上的数字表示距离，如两级中间站，两点之间的连线上的数字表示距离，如图所示。问应该选择什么路线，使总距离最短？图所示。问应该选择什么路线，使总距离最短？ AB1B2C1C2C3D24333321114 第三节第三节 动态规划应用举例动态规划应用举例一

22、、最短路径问题一、最短路径问题 解：整个计算过程分三个阶段，从最后一个阶段开始。解：整个计算过程分三个阶段，从最后一个阶段开始。 第三阶段（第三阶段（C D）：）： C 有三条路线到终点有三条路线到终点D 。 AB1B2C1C2C3D24333321114DC1C2C3显然有显然有 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第

23、二阶段（第二阶段（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 6 = 3 5AB1B2C1C2C3D24333321114DC1C2C3B1B2(最短路线为最短路线为B2C1 D)第一阶段（第一阶段（ A B ）：）： A 到到B 有二条路线。有二条路线。 f3(A)1

24、 = 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 路长为路长为 6表上作业法表上作业法K=3C1C2C3DDD134DDD000DDDK=2B1C13C1阶段阶段k状态状态Sk决策决策Uk阶

25、段指标阶段指标Vk状态转状态转移移Sk+1fk+1(Sk+1) fk(Sk) 最优策略最优策略Uk*134134C2C331C2C3465C1B2C1C2312C1C2C313436K=1AB2B124B1B2C14367B15C3求从求从A到到E的最短路径的最短路径路线为路线为AB2C1 D1 E ，最短路径为最短路径为1919AB2B1B3C1C3D1D2EC25214112610104312111396581052练习：练习：1 现有数量为现有数量为a的资源，用于生产的资源，用于生产n种产品，第种产品，第i种产品种产品分配分配xi，带来gi(xi)收益，问如何分配使总收益最大？收益，问如

26、何分配使总收益最大？ nixaxxgZiniiniii.2.1 0)(max11据此，有下式：据此，有下式：二、资源分配问题二、资源分配问题1、一维资源分配、一维资源分配 求解：求解：阶段：阶段： k=1，2，,n,对应第对应第k种产品分配资源的过程种产品分配资源的过程状态状态Sk:表示可供分配第表示可供分配第k种到第种到第n种资源的总量种资源的总量决策变量决策变量xk:表示分配给第表示分配给第k种产品的资源量种产品的资源量状态转移方程状态转移方程: Sk+1= Sk xk阶段指标函数阶段指标函数:V k= gk(xk) 基本方程基本方程: fk(Sk)=maxgk(xk) +fk+1(Sk+

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

28、阶段指标函数阶段指标函数: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,X*=(0,2,0) 设备设备工厂工厂012A037B0510C046*练习：某公司打算在练习：某公司打算在3

29、个不同的地区设置个不同的地区设置4个销售点，个销售点，根据市场部门估计，在不同地区设置不同数量的销根据市场部门估计，在不同地区设置不同数量的销售点每月可得到的利润如表所示。试问在各地区如售点每月可得到的利润如表所示。试问在各地区如何设置销售点可使每月总利润最大。何设置销售点可使每月总利润最大。 地地区区销售点销售点01234123000161210251714302116322217 x1=2，x2=1，x3=1，f3(4)=47 有一个徒步旅行者，其可携带物品重量的限度为有一个徒步旅行者，其可携带物品重量的限度为a 公公斤，设有斤，设有n 种物品可供他选择装入包中。已知每种物品种物品可供他选

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

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

32、第k种物品的件数种物品的件数状态转移方程状态转移方程: S1 =5,S2= S1 2x2, S3= S2 2x3阶段指标函数阶段指标函数:V 1= 8x1, V 2= 5x2 ,V 3= 12x3基本方程基本方程: fk(Sk)=maxVk +fk+1(Sk+1)(k=3,2,1) f4(S4)=0求解见板书求解见板书 练习：某厂生产三种产品，各种产品重量与利润练习：某厂生产三种产品，各种产品重量与利润的关系如表所示。现将此三种产品运往市场出售，的关系如表所示。现将此三种产品运往市场出售，运输能力总重量不超过运输能力总重量不超过 6 吨，问如何安排运输，使吨，问如何安排运输，使总利润最大？总利

33、润最大？种类种类 1 2 3重量（吨重量（吨/ /公斤）公斤） 2 3 4 单件利润（元）单件利润（元） 80 130 180最优方案：最优方案：X1 = =（0.2.00.2.0）X2 = =（1.0.11.0.1）Z=260=260四、复合系统工作可靠性问题四、复合系统工作可靠性问题 某种机器的工作系统由某种机器的工作系统由n个部件串联组成，只要有一个部个部件串联组成，只要有一个部件失灵，整个系统就不能正常工作。为了提高系统工作的件失灵，整个系统就不能正常工作。为了提高系统工作的可靠性，在每个部件上均装有主要元件的备用件，并设计可靠性，在每个部件上均装有主要元件的备用件，并设计了备用元件自

34、动投入装备，显然，备用元件越多，整个系了备用元件自动投入装备，显然，备用元件越多，整个系统工作的可靠性就越大，但备用元件增多也会导致系统的统工作的可靠性就越大，但备用元件增多也会导致系统的成本、重量体积相应增大，工作精度降低，因此，在考虑成本、重量体积相应增大，工作精度降低，因此，在考虑上述限制条件下，如何选择各部件的备用元件数，使整个上述限制条件下，如何选择各部件的备用元件数，使整个系统的工作可靠性最大？系统的工作可靠性最大？ 建模：设部件建模：设部件i装有装有xi个备用元件时，正常工作的概率为个备用元件时，正常工作的概率为Pi(xi),那么整个系统正常工作的概率那么整个系统正常工作的概率Z

35、= Pi(xi)（i=1，,n）,设部件设部件i的单位重量级的单位重量级wi,那么总重量不超那么总重量不超过过w的情况下的情况下,如何配备备用件如何配备备用件,使使Z最大最大?且为整数,0)(max11iniiiiniixxxPz用动态规划方法求解阶段：阶段： k=1，2，n,对应给第对应给第k个部件分配配件的过程个部件分配配件的过程状态状态Sk:表示可供分配第表示可供分配第k个到第个到第n个部件的总重量个部件的总重量决策变量决策变量xk:表示分配给第表示分配给第k个部件配备的备用件数个部件配备的备用件数状态转移方程状态转移方程: Sk+1 =Skwkxk阶段指标函数阶段指标函数:V k=Pk

36、(xk)基本方程基本方程: fk(Sk)=maxVk fk+1(Sk+1)(k=n,2,1) fk+1(Sk+1)=1例例:三个科研小组分别对某一项目的一个部件研究三个科研小组分别对某一项目的一个部件研究,成功率分成功率分别为别为0.6,0.4,0.2,为提高成功率为提高成功率,可以给各组增加人员可以给各组增加人员,现有现有2个个人可以加入到研究工作中人可以加入到研究工作中,问如何分配人手问如何分配人手,使项目总成功率使项目总成功率最大最大?成功率成功率 一 二 三0 0 0.6 0.4 0.21 1 0.8 0.6 0.52 2 0.85 0.8 0.7阶段：阶段： k=1，2，3,对应给第

37、对应给第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(Sk)最优策最优策略略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