第七章动态规划精选文档.ppt

《第七章动态规划精选文档.ppt》由会员分享，可在线阅读，更多相关《第七章动态规划精选文档.ppt（61页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第七章动态规划第七章动态规划本讲稿第一页，共六十一页Chapter 7 动态规划动态规划(Dynamic ProgrammingDynamic Programming)多阶段决策问题多阶段决策问题动态规划的基本概念动态规划的基本概念动态规划的求解步骤动态规划的求解步骤动态规划模型的建立动态规划模型的建立运用动态规划求解实际问题运用动态规划求解实际问题本章主要内容：本章主要内容：本章主要内容：本章主要内容：本讲稿第二页，共六十一页引言引言动态规划作为运筹学的一个重要分支是解决多阶段决策动态规划作为运筹学的一个重要分支是解决多阶段决策过程最优化的一种非常有效的方法。过程最优化的一种非常有效的方法。

2、1951年，美国数学家贝年，美国数学家贝尔曼（尔曼（R.Bellman）等人，根据一类多阶段决策问题的特）等人，根据一类多阶段决策问题的特点，把多阶段决策问题变换为一系列相互联系的单阶段决策点，把多阶段决策问题变换为一系列相互联系的单阶段决策问题，然后分阶段逐个加以解决。贝尔曼等人在研究和解决问题，然后分阶段逐个加以解决。贝尔曼等人在研究和解决了大量实际问题之后，提出了解决这类问题的了大量实际问题之后，提出了解决这类问题的所谓所谓“最最优性原理优性原理”，通常称为，通常称为“贝尔曼最优化原理贝尔曼最优化原理”，从而创建了，从而创建了解决最优化问题的一种新的方法解决最优化问题的一种新的方法 动态

3、规划动态规划（Dynamic Programming ）。）。贝尔曼的名著动态规划贝尔曼的名著动态规划于于1957年出版，这成了动态规划的第一本著作。年出版，这成了动态规划的第一本著作。本讲稿第三页，共六十一页引言引言动态规划的方法，在工程技术、企业管理、工农业生产动态规划的方法，在工程技术、企业管理、工农业生产及军事等部门中有着广泛的应用，并且获得了显著的效果。及军事等部门中有着广泛的应用，并且获得了显著的效果。在经济管理方面，动态规划可以用来解决最优路径问题、资在经济管理方面，动态规划可以用来解决最优路径问题、资源分配问题、生产调度问题、库存问题、装载问题、排序问源分配问题、生产调度问题、

4、库存问题、装载问题、排序问题、设备更新问题、生产过程最优控制问题等等，它是现代题、设备更新问题、生产过程最优控制问题等等，它是现代企业管理中的一种重要的决策方法。企业管理中的一种重要的决策方法。许多实际问题采用动态规划方法去处理，常比线性规划许多实际问题采用动态规划方法去处理，常比线性规划或非线性规划更加有效。特别对于离散性的问题，由于解析或非线性规划更加有效。特别对于离散性的问题，由于解析数学无法施展其术，而动态规划的方法就成为一种非常有效数学无法施展其术，而动态规划的方法就成为一种非常有效的工具。的工具。本讲稿第四页，共六十一页引言引言应特别指出的是，动态规划是解决某一类问题的一种方应特别

5、指出的是，动态规划是解决某一类问题的一种方法，是分析问题的一种途径，而不是一种特殊算法（如线性法，是分析问题的一种途径，而不是一种特殊算法（如线性规划是一种算法）。因而，它不象线性规划那样有一个标准规划是一种算法）。因而，它不象线性规划那样有一个标准的数学表达式和明确定义的一组规则，而必须对具体问题进的数学表达式和明确定义的一组规则，而必须对具体问题进行具体分析处理。因此，在学习动态规划时，除了对基本概行具体分析处理。因此，在学习动态规划时，除了对基本概念和方法正确地理解外，应以丰富的想象力去建立模型，用念和方法正确地理解外，应以丰富的想象力去建立模型，用创造性的技巧去求解。正如贝尔曼本人所说

6、：创造性的技巧去求解。正如贝尔曼本人所说：“由于动态规由于动态规划的最优化原理仅仅是一种基本原理，正是它的某种不确定划的最优化原理仅仅是一种基本原理，正是它的某种不确定性为你提供了发挥你创造性思维的巨大空间性为你提供了发挥你创造性思维的巨大空间!本章我们在学习动态规划基本概念、理论和方法的基础本章我们在学习动态规划基本概念、理论和方法的基础上，在通过一些典型的应用问题来说明它的应用。上，在通过一些典型的应用问题来说明它的应用。本讲稿第五页，共六十一页动态规划的基本概念和基本方法动态规划的基本概念和基本方法多阶段决策过程多阶段决策过程整个决策过程可按时间或空间顺序分解成若干相互联系整个决策过程可

7、按时间或空间顺序分解成若干相互联系的阶段，每一阶段都需作出决策，全部过程的决策是一个决的阶段，每一阶段都需作出决策，全部过程的决策是一个决策序列。策序列。多阶段决策过程最优化的目标：多阶段决策过程最优化的目标：达到整个活动过程的达到整个活动过程的总体总体效果最优，而非各效果最优，而非各单个单个阶段最阶段最优的简单总和。优的简单总和。请看如下典型案例请看如下典型案例最短路线问题最短路线问题本讲稿第六页，共六十一页动态规划的基本概念和基本方法动态规划的基本概念和基本方法B1AC3F2F1E3E2E1D3D2D1C4C2C1B2G第一阶段第一阶段第二阶段第二阶段第三阶段第三阶段第四阶段第四阶段第五阶

8、段第五阶段第六阶段第六阶段531368766835342138223335526643437597681310912131618该点到G点的最短距离本讲稿第七页，共六十一页动态规划的基本概念和基本方法动态规划的基本概念和基本方法动态规划方法的基本术语：动态规划方法的基本术语：1、阶段和阶段变量阶段和阶段变量对整个决策过程的自然划分，通常根据对整个决策过程的自然划分，通常根据时间顺序或空间特征时间顺序或空间特征来划分阶段，以便按阶段的次序逐段解决整个过程的优化问题。来划分阶段，以便按阶段的次序逐段解决整个过程的优化问题。阶段变量通常用阶段变量通常用k表示（表示（k=1，2，3，n）。）。2、状态

9、与状态变量状态与状态变量每个阶段开始时过程所处的自然状况或客观条件成为该阶段每个阶段开始时过程所处的自然状况或客观条件成为该阶段的状态。每个阶段的初始状况又是前一个阶段的终止状况（第的状态。每个阶段的初始状况又是前一个阶段的终止状况（第一阶段除外）。因此，一旦各个阶段的状态确定之后，整个过一阶段除外）。因此，一旦各个阶段的状态确定之后，整个过程也完全确定。从这个意义上说，多阶段决策过程也是各个状程也完全确定。从这个意义上说，多阶段决策过程也是各个状态的演变过程。态的演变过程。本讲稿第八页，共六十一页动态规划的基本概念和基本方法动态规划的基本概念和基本方法状态具有状态具有“无后效性无后效性”，即

10、当前阶段状态给定时，这个，即当前阶段状态给定时，这个阶段以后过程的演变与该阶段以前各阶段的状态无关。阶段以后过程的演变与该阶段以前各阶段的状态无关。一般把描述阶段状态的变量称为状态变量。通常用一般把描述阶段状态的变量称为状态变量。通常用sk表表示第示第k阶段的状态。第阶段的状态。第k阶段状态变量的允许取值范围称为阶阶段状态变量的允许取值范围称为阶段段k的状态集合。记作的状态集合。记作 Sk。3、决策与决策变量决策与决策变量当一个阶段的状态确定后，可以作出不同的当一个阶段的状态确定后，可以作出不同的决定或选择决定或选择，从而演变到下一阶段的某个状态，这种决定或选择称为决策。从而演变到下一阶段的某

11、个状态，这种决定或选择称为决策。描述决策的变量称为决策变量，通常用描述决策的变量称为决策变量，通常用uk表示，前面已经说表示，前面已经说过，决策要依据该阶段的状态，因此通常用过，决策要依据该阶段的状态，因此通常用uk(sk)表示第表示第k阶阶段处于状态段处于状态sk时的决策。决策变量的取值范围称为决策集合时的决策。决策变量的取值范围称为决策集合，表示为，表示为Dk(sk)。本讲稿第九页，共六十一页动态规划的基本概念和基本方法动态规划的基本概念和基本方法4、策略与子策略策略与子策略一组有序的一组有序的决策序列决策序列构成一个策略，从第构成一个策略，从第k阶段至第阶段至第n阶段的阶段的一个策略称为

12、后部子策略记为一个策略称为后部子策略记为 pk，n（uk，uk+1，un）。）。5、状态转移方程状态转移方程 在确定型多阶段决策过程中，一旦某阶段的状态和决策为已在确定型多阶段决策过程中，一旦某阶段的状态和决策为已知，下一阶段的状态便完全确定，用状态转移方程反映这种状知，下一阶段的状态便完全确定，用状态转移方程反映这种状态间的态间的演变规律演变规律，写作：，写作：（7.1）本讲稿第十页，共六十一页动态规划的基本概念和基本方法动态规划的基本概念和基本方法6、指标函数指标函数 衡量决策效果优劣的数量指标称为指标函数，具体可以是收衡量决策效果优劣的数量指标称为指标函数，具体可以是收益、成本、距离等指

13、标，可以分为益、成本、距离等指标，可以分为k阶段指标函数，子过程指标阶段指标函数，子过程指标函数和最优指标函数。函数和最优指标函数。从从k阶段状态阶段状态sk出发，做出决策出发，做出决策uk所所产生的第产生的第k阶段指标称为阶段指标称为k阶段指标函数，记为阶段指标函数，记为vk(sk,uk)。从。从k阶段状态阶段状态sk出发，选择决策出发，选择决策uk，uk+1，un所产生的过程指标，称为所产生的过程指标，称为k子过程指标函数或子过程指标函数或简记为过程指标函数，记为简记为过程指标函数，记为Vk(sk,uk,uk+1,un)或或Vk,n。从。从k阶段阶段状态状态sk出发，对所有的子策略，最优的

14、过程指标函数称为最优出发，对所有的子策略，最优的过程指标函数称为最优指标函数，记为指标函数，记为fk(sk)，通常取，通常取Vk的最大值或最小值。的最大值或最小值。本讲稿第十一页，共六十一页动态规划的基本概念和基本方法动态规划的基本概念和基本方法通常要求动态规划的子过程指标满足递推关系通常要求动态规划的子过程指标满足递推关系常用的有连加和连乘的形式，分别为常用的有连加和连乘的形式，分别为（7.2）（7.3）本讲稿第十二页，共六十一页动态规划的基本概念和基本方法动态规划的基本概念和基本方法最有指标函数最有指标函数fk(sk)取式（取式（7.2）和（）和（7.3）的最优值，分别为：）的最优值，分别

15、为：式（式（7.4）和（）和（7.5）称为）称为动态规划的基本方程动态规划的基本方程。为了使递推方程。为了使递推方程有递推起点，需要确定最后一个状态有递推起点，需要确定最后一个状态sn的最优指标函数的最优指标函数fn(sn)的的值，称为值，称为终端条件终端条件。一般情况下，连和形式。一般情况下，连和形式fn(sn)=0，连乘形式，连乘形式fn(sn)=1。动态规划的数学模型由式动态规划的数学模型由式(8.4)或或(8.5)，边界条件及状态转移，边界条件及状态转移方程构成，如连加形式的数学模型为：方程构成，如连加形式的数学模型为：（7.4）（7.5）本讲稿第十三页，共六十一页动态规划的基本概念和

16、基本方法动态规划的基本概念和基本方法由式由式（7.4）和使和使（7.5）的形式知，计算顺序是从最后一个阶段开始的形式知，计算顺序是从最后一个阶段开始到第一个阶段结束，这种方法称为到第一个阶段结束，这种方法称为逆序算法逆序算法。也可以将基本方程改。也可以将基本方程改为前向递推：为前向递推：这时计算顺序是从第一阶段开始到最后一个阶段结束，这种算法称为这时计算顺序是从第一阶段开始到最后一个阶段结束，这种算法称为顺序算法顺序算法。本讲稿第十四页，共六十一页动态规划的基本概念和基本方法动态规划的基本概念和基本方法总结总结在明确了动态规划的基本概念和基本思想之后，在解决一个在明确了动态规划的基本概念和基本

17、思想之后，在解决一个实际问题建立动态规划模型时，步骤如下：实际问题建立动态规划模型时，步骤如下：（1）将问题的过程划分为恰当的阶段；）将问题的过程划分为恰当的阶段；（2）正确选择状态变量）正确选择状态变量sk，使它既能描述过程的演变，又，使它既能描述过程的演变，又能满足无后效性；能满足无后效性；（3）正确写出决策变量）正确写出决策变量uk及每阶段的允许决策集合及每阶段的允许决策集合Dk(sk)；（4）正确写出状态转移方程；）正确写出状态转移方程；（5）正确写出指标函数）正确写出指标函数Vk,n的关系，它满足下面三个性质：的关系，它满足下面三个性质：本讲稿第十五页，共六十一页动态规划的基本概念和

18、基本方法动态规划的基本概念和基本方法是定义在全过程和所有后部子过程上的数量函数；是定义在全过程和所有后部子过程上的数量函数；具有可分离性，并满足递推关系。即：具有可分离性，并满足递推关系。即：函数函数 对于变量对于变量Vk+1,n要严格单要严格单调。调。以上五点是构造动态规划模型的基础，是正确写出动态规划以上五点是构造动态规划模型的基础，是正确写出动态规划基本方程的基本要素。而一个问题的动态规划模型是否正确给基本方程的基本要素。而一个问题的动态规划模型是否正确给出，它集中反映在恰当地定义最优值函数和正确写出递推关系出，它集中反映在恰当地定义最优值函数和正确写出递推关系式及边界条件。简而言之，要

19、正确写出动态规划的基本方程。式及边界条件。简而言之，要正确写出动态规划的基本方程。本讲稿第十六页，共六十一页动态规划举例动态规划举例下面我们举一个动态规划的实际例子。下面我们举一个动态规划的实际例子。例7.1（基建投资问题）一家公司有三个工厂，每个工厂都需要进行扩建。公司用于扩建的资金总额为7万元。各工厂的投资方案及扩建后预期可得到的利润如下表：现在公司要确定对各厂投资多少，才能使公司的总利润达到最大？厂名方案1方案2方案3方案4投资数利润投资数利润投资数利润投资数利润一厂二厂三厂0000001125372338911344101113本讲稿第十七页，共六十一页动态规划举例动态规划举例解解.（

20、1）划分阶段：我们把每个工厂获得投资作为一个阶段，）划分阶段：我们把每个工厂获得投资作为一个阶段，k=1,2,3。（2）选择状态变量：选取第）选择状态变量：选取第k阶段可用的资金总额作为状态阶段可用的资金总额作为状态变量，记为变量，记为sk。（3）确定决策变量：选择分配给阶段）确定决策变量：选择分配给阶段k的投资数作为决策变的投资数作为决策变量，记为量，记为uk，决策集合记为，决策集合记为Dk。（4）状态转移方程：）状态转移方程：sk+1=sk-uk（5）定义定义 fk(sk)：第：第k阶段投资时可用的资金为阶段投资时可用的资金为sk，第，第k阶段阶段至第至第3阶段按阶段按最优投资策略最优投资

21、策略分配所余的资金，第分配所余的资金，第k阶段至第阶段至第3阶段阶段所创造的所创造的利润总和利润总和。本讲稿第十八页，共六十一页动态规划举例动态规划举例（6）建立动态规划基本方程：（逆序递推方程）建立动态规划基本方程：（逆序递推方程）（7）用逆序递推求解动态规划方程。）用逆序递推求解动态规划方程。k=3，状态集合，状态集合S3=0,1,2,3,4,5,6,7s301234567u3000,20,2,30,2,3,40,2,3,40,2,3,40,2,3,4v3(u3)000,70,7,110,7,11,130,7,11,130,7,11,130,7,11,13f3(u3)000,70,7,11

22、0,7,11,130,6,11,130,6,11,130,6,11,13u*300 2 3 4 4 4 4本讲稿第十九页，共六十一页动态规划举例动态规划举例k=2，状态集合，状态集合S2=0,1,2,3,4,5,6,7k=1时，状态集合时，状态集合S1=7s201234567u200,10,10,1,30,1,3,40,1,3,40,1,3,40,1,3,4v2(u2)00,30,30,3,90,3,9,110,3,9,110,3,9,110,3,9,11S301,02,13,2,04,3,1,05,4,2,16,5,3,27,6,4,3f300,07,011,7,013,11,0,013,1

23、3,7,013,13,11,713,13,13,11f2(u2)00,37,311,10,913,14,9,1113,16,16,1113,16,20,1813,16,20,24u*30 100 1 1 3 3 4s17u10,1,2,3v1(u1)0,5,8,10S27,6,5,4f224,20,16,14f1(u1)24,25,24,24u*1 1请问最优投资方案是请问最优投资方案是什么？采用顺序算法什么？采用顺序算法如何求解？如何求解？本讲稿第二十页，共六十一页动态规划应用举例动态规划应用举例例例7.2 生产与存储问题生产与存储问题 一个工厂生产的某种产品，在一定的时期一个工厂生产的某种

24、产品，在一定的时期内，增大生产批量，能够降低产品的单位成本，但若超过市场内，增大生产批量，能够降低产品的单位成本，但若超过市场的需求量，就会造成产品的挤压而增加存储的费用。因此如何的需求量，就会造成产品的挤压而增加存储的费用。因此如何正确地制定生产计划，使得在整个计划期内，生产和存储的总正确地制定生产计划，使得在整个计划期内，生产和存储的总费用最小，这就是生产与存储问题。举例如下：费用最小，这就是生产与存储问题。举例如下：假设某厂生产的一种产品，以后四个月的订单如下表所示。假设某厂生产的一种产品，以后四个月的订单如下表所示。合同规定月底前交货，生产每批产品的固定成本为合同规定月底前交货，生产每

25、批产品的固定成本为3千元，每批千元，每批生产的产品件数不限。每件产品的可变成本为生产的产品件数不限。每件产品的可变成本为1千元，每批产品千元，每批产品的最大生产生产能力为的最大生产生产能力为5件。产品每月的存储费为件。产品每月的存储费为0.5千元。设千元。设1月初有库存产品月初有库存产品1件，四月底不再留下产品。试在满足需要的前件，四月底不再留下产品。试在满足需要的前提下，如何组织生产才能使总的成本费用最低。提下，如何组织生产才能使总的成本费用最低。本讲稿第二十一页，共六十一页动态规划应用举例动态规划应用举例解解 按时间将问题的过程划分为按时间将问题的过程划分为4个阶段，即个阶段，即k=1,2

26、,3,4。设状态。设状态变量变量sk为第为第k月初的库存量；决策变量月初的库存量；决策变量uk为第为第k月的生产量。依月的生产量。依据题意，已知据题意，已知s1=1，s5=0。状态转移方程为：。状态转移方程为：阶段指标函数阶段指标函数v(sk,uk)为各阶段的生产存储总成本，即为各阶段的生产存储总成本，即月份 1 2 3 4订货量bk 3 3 2 4本讲稿第二十二页，共六十一页动态规划应用举例动态规划应用举例当当k=4时，时，s4的虽小可能值为的虽小可能值为0，即四月份没有存货，即四月份没有存货，s4的最大的最大可能值为可能值为 ，所以，所以s4=0,1,2,3,4。当当k=3时，时，s3=m

27、in0,1,2,3,min52+1-6,6=0,1,2,3,4,5。计。计算如下：算如下：s4本阶段费用s5f5(s5)d(s4,u4)+f5(s5)f4(s4)u4生产费用存储费用d(s4,u4)01234432103+43+33+23+1000.511.5276.565.52000000000076.565.5276.565.52本讲稿第二十三页，共六十一页动态规划应用举例动态规划应用举例 s3本阶段费用s4f4(s4)d(s3,u3)+f4(s4)f3(s3)u3生产费用存储费用d(s3,u3)023453+23+33+43+505678012376.565.51212.51313.51

28、21123453+13+23+33+43+50.54.55.56.57.58.50123476.565.5211.51212.51310.510.5本讲稿第二十四页，共六十一页动态规划应用举例动态规划应用举例 s3本阶段费用s4f4(s4)d(s3,u3)+f4(s4)f3(s3)u3生产费用存储费用d(s3,u3)20123403+13+23+33+41156780123476.565.52811.51212.51083012303+13+23+31.51.55.56.57.512346.565.52811.5129.58本讲稿第二十五页，共六十一页动态规划应用举例动态规划应用举例 当当k=

29、2时时s3本阶段费用s4f4(s4)d(s3,u3)+f4(s4)f3(s3)u3生产费用存储费用d(s3,u3)401203+13+2226723465.52811.59850103+12.52.56.5345.5288.58本讲稿第二十六页，共六十一页动态规划应用举例动态规划应用举例 s2本阶段费用s3f3(s3)d(s2,u2)+f3(s3)f2(s2)u2生产费用存储费用d(s2,u2)03453+33+43+506780121210.581817.51616123453+23+33+43+50.55.56.57.58.501231210.58817.51715.516.515.5本讲

30、稿第二十七页，共六十一页动态规划应用举例动态规划应用举例 s2本阶段费用s3f3(s3)d(s2,u2)+f3(s3)f2(s2)u2生产费用存储费用d(s2,u2)2123453+13+23+33+43+5156789012341210.58881716.515161715301234503+13+23+33+43+51.51.55.56.57.58.59.50123451210.5888813.51614.515.516.517.513.5本讲稿第二十八页，共六十一页动态规划应用举例动态规划应用举例k=1时时通过以上例子可以看出，利用动态规划方法求解多阶段问题，通过以上例子可以看出，利用动

31、态规划方法求解多阶段问题，之所以减少计算量，原因之一是充分利用了前阶段已计算好的之所以减少计算量，原因之一是充分利用了前阶段已计算好的结果。结果。s1本阶段费用s2f2(s2)d(s1,u1)+f2(s2)f1(s1)u1生产费用存储费用d(s1,u1)123453+23+33+43+50.55.56.57.58.501231615.51513.521.52222.52221.5本讲稿第二十九页，共六十一页动态规划应用举例动态规划应用举例例7.3 假定某厂在明年头4个月对燃料的需求量以及各月的固定订货费和单位存储费用如下表。如果每吨燃料的价格是800元，该厂每个月开始时采购，问每月应采购多少，

32、才能在保证供应的情况下使总成本最少？月份i需求量i固定订货费Ki单位存储费hi1234214220015010010050404040本讲稿第三十页，共六十一页动态规划应用举例动态规划应用举例解 设zi和ui(i=1,2,3,4)分别是月份i的订货量和期末存货量，则在采用顺序计算时，其基本方程是：下面按各阶段分别计算如下（为了简单起见，金额以百元为单位）：阶段1：1=2，0u11+4+2=7，见下表：本讲稿第三十一页，共六十一页动态规划应用举例动态规划应用举例u1f1(z1|u1)=c1(z1)+0.5u1最优值最优解z1=23456789f1(u1)z1*012345671826.53543

33、.55260.56977.51826.53543.55260.56977.523456789阶段阶段2：2=1 1，00u24+2=6，见下表：，见下表：本讲稿第三十二页，共六十一页动态规划应用举例动态规划应用举例u2f2(z2|u2)=c2(z2)+0.4u2+f2(u2+2-z2)最优值最优解z2=01234567f2(u2)z2*01234560+26.5=25.60.4+35=35.40.8+43.5=44.31.2+52=53.21.6=60.5=62.12+69=712.4+77.5=79.99.5+18=27.59.9+26.5=36.410.3+35=45.310.7+43.5

34、=54.211.1+52=63.111.5+60.5=7211.9+69=80.935.944.853.762.671.580.444.353.258.17179.952.761.670.379.461.17078.969.578.477.926.535.444.352.761.169.577.9000,34567本讲稿第三十三页，共六十一页动态规划应用举例动态规划应用举例阶段阶段3：3=4，0u32，见下表：，见下表：阶段阶段4：4=2，u4=0，见下表：，见下表：u3f3(z3|u3)=c3(z3)+0.4u3+f3(u3+3-z3)最优值最优解z3=0123456f3(u3)z3*012

35、0+61.1=61.10.4+69.5=69.90.8+77.9=78.79+52.7=61.79.4+61.1=70.59.8+69.5=79.361.370.178.960.469.778.559.568.878.167.977.276.359.567.976.3456u4f4(z4|u4)=c4(z4)+0.4u4+f3(u4+4-z4)最优值最优解z4=012f4(u4)z4*00+76.3=76.39+67.9=76.917+59.5=76.576.30本讲稿第三十四页，共六十一页动态规划应用举例动态规划应用举例例例7.4 资源分配问题资源分配问题 设某种资源，如资金、材料、机器设备

36、、劳设某种资源，如资金、材料、机器设备、劳动力等，可以投入动力等，可以投入n种生产。如果以数量为种生产。如果以数量为xi的资源投入第的资源投入第i种产种产品的生产，所得的效益为品的生产，所得的效益为g（xi）(i=1,2,n)。问如何分配这种。问如何分配这种资源，才能使总的经济效益最大。资源，才能使总的经济效益最大。公司有资金公司有资金8万元，投资万元，投资A、B、C三个项目单位投资为三个项目单位投资为2万万元。每个项目的投资效益率与投入该项目的资金有关。三个项元。每个项目的投资效益率与投入该项目的资金有关。三个项目的投资项目（万元）与投入资金目的投资项目（万元）与投入资金（万元）的关系如下表

37、。求对三个（万元）的关系如下表。求对三个项目的最有投资分配，使总投资收项目的最有投资分配，使总投资收益最大。益最大。A B C2万元4万元6万元8万元 8 9 10 15 20 28 30 35 35 38 40 43项目项目投入资金投入资金本讲稿第三十五页，共六十一页动态规划应用举例动态规划应用举例解解 阶段阶段k：每投资一个项目作为一个阶段，：每投资一个项目作为一个阶段，k=1,2,3,4。k=4为为虚设的阶段虚设的阶段状态变量状态变量sk：投资第：投资第k项目前的资金数项目前的资金数决策变量决策变量uk：第：第k阶段的投资额阶段的投资额状态转移方程：状态转移方程：sk+1=sk-uk阶段

38、指标：阶段指标：vk(sk,xk)见上表中的数据见上表中的数据递推方程：递推方程：fk(uk)=maxvk(sk,uk)+fk+1(sk+1)终端条件：终端条件：f4(s4)=0数学模型为：数学模型为：本讲稿第三十六页，共六十一页动态规划应用举例动态规划应用举例k=4，终端条件，终端条件f4(s4)=0。k=3，0u3s3，s4=s3-u3。第。第3阶段表示投资项目阶段表示投资项目A、B后再投资后再投资项目项目C，s3表示按最优投资策略投资完表示按最优投资策略投资完A、B后将剩余资金全部后将剩余资金全部投入项目投入项目C。k=2，0u2s2，s3=s2-u2k=1，0u1s1，s2=s1-u1

39、，第，第1阶段开始投资项目阶段开始投资项目A，有资金，有资金8万万元，计算过程见下表：元，计算过程见下表：本讲稿第三十七页，共六十一页动态规划应用举例动态规划应用举例状态s3决策u3(s3)状态转移方程s4=s3-u3阶段指标v3(s3,u3)过程指标v3(s3,u3)+f4(s4)最优指标f3(s3)最优决策u*300000+0=00020200+0=0102201010+0=1040400+0=0284221010+0=10402828+0=2860600+0=0356241010+0=10422828+0=28603535+0=3580800+0=043826100+10=1044282

40、8+0=28623535+0=35804343+0=43本讲稿第三十八页，共六十一页动态规划应用举例动态规划应用举例s2u2(s2)s3v2(s2,u2)f3(s3)v2(s2,u2)+f3(s3)f2(s2)u*2000000+0=0002020100+10=1010020909+0=94040280+28=28280229109+10=194020020+0=206060350+35=35372249289+28=3742201020+10=306035035+0=358080430+43=43484269359+35=4444202820+28=4862351035+10=4580400

41、40+0=40本讲稿第三十九页，共六十一页动态规划应用举例动态规划应用举例 最优解为：最优解为：s1=8，u1=0，s2=s1-u1=8，u2=4，s3=s2-u2=4，u3=4，s4=s3-u3=0。s1u1(s1)s2v1(s1,u12)f2(s2)v1(s1,u1)+f2(s2)f1(s1)u*18080480+48=48480268378+37=4544152815+28=4362301030+10=408038038+0=38本讲稿第四十页，共六十一页动态规划应用举例动态规划应用举例例例7.5 某种设备可在高低两种不同的负荷下进行生产，设在高负某种设备可在高低两种不同的负荷下进行生产

42、，设在高负荷下投入生产的设备数量荷下投入生产的设备数量x，产量，产量g=10 x，设备年完好率为，设备年完好率为a=0.75；在低负荷下投入生产的设备数为；在低负荷下投入生产的设备数为y，产量为，产量为h=8y，年完好率为，年完好率为b=0.9。假定开始生产时完好的设备数量。假定开始生产时完好的设备数量s1=100。制定一个制定一个5年计划，确定每年投入高低两种负荷下生产的设备数年计划，确定每年投入高低两种负荷下生产的设备数量，使量，使5年内的总产量最大。年内的总产量最大。解：解：阶段阶段k：运行年份：运行年份(k=1,2,3,4,5,6)，k=1表示第表示第1年年初，年年初，k=6表示第表示

43、第5年年末年年末(即第即第6年年初）年年初）状态变量状态变量sk：第：第k年年初的完好机器数年年初的完好机器数(k=1,2,3,4,5,6)，也是第，也是第k-1年年末完好的机器数，其中年年末完好的机器数，其中s6表示第表示第5年年末（即第年年末（即第6年年初）年年初）的完好机器数，的完好机器数，s1=100决策变量决策变量uk：第：第k年年初投入高负荷运行的机器数年年初投入高负荷运行的机器数状态转移方程：状态转移方程：sk+1=0.75uk+0.9(sk-uk)本讲稿第四十一页，共六十一页动态规划应用举例动态规划应用举例阶段指标：阶段指标：vk(sk,uk)=10uk+8(sk-uk)终端条

44、件：终端条件：f6(s6)=0递推方程：递推方程：fk(sk)表示第表示第k年年初分配年年初分配uk台设备用于高负荷生产时到第台设备用于高负荷生产时到第5年年末的最大产量。计算过程如下：年年末的最大产量。计算过程如下：本讲稿第四十二页，共六十一页动态规划应用举例动态规划应用举例本讲稿第四十三页，共六十一页动态规划应用举例动态规划应用举例本讲稿第四十四页，共六十一页动态规划应用举例动态规划应用举例由于由于s1=100，5年的最大总产量为年的最大总产量为f1(s1)=3443.74。由由x1*=x2*=x3*=0，x4*=s4，x5*=s5，设备的最优分配策略是：第，设备的最优分配策略是：第1至第

45、至第3年将设备全部用于低负荷运行，第年将设备全部用于低负荷运行，第4年和第年和第5年将设备全年将设备全部用于高负荷运转。每年投入高负荷的机器数及每年年初完好部用于高负荷运转。每年投入高负荷的机器数及每年年初完好的机器数为：的机器数为：s1=100 x1*=0,s2=0.75x1+0.9(s1-x1)=90 x2*=0,s3=0.75x2+0.9(s2-x2)=81x3*=0,s4=0.75x3+0.9(s3-x3)=73x4*=s4=73,s5=0.75x4+0.9(s4-x4)=55x5*=s5=55,s6=0.75x5+0.9(s5-x5)=41本讲稿第四十五页，共六十一页动态规划应用举例

46、动态规划应用举例例例7.6 设备更新问题设备更新问题在工业和交通运输企业中，经常遇到设备陈旧或部分损坏在工业和交通运输企业中，经常遇到设备陈旧或部分损坏因而需要重新购置的更新问题。因此，每隔一个时期，就要做因而需要重新购置的更新问题。因此，每隔一个时期，就要做出一项决策，是继续使用，还是把它更新。如果设备使用得太出一项决策，是继续使用，还是把它更新。如果设备使用得太久，就必然影响生产效率和产品质量，因而影响到利润。所以，久，就必然影响生产效率和产品质量，因而影响到利润。所以，在这两者之间要做出最佳选择。如果在一个有限时期内考虑这在这两者之间要做出最佳选择。如果在一个有限时期内考虑这类设备问题，

47、就可以用动态规划来解决。举例如下：类设备问题，就可以用动态规划来解决。举例如下：假定要考虑某种设备被在今后假定要考虑某种设备被在今后3年内的更新问题。在每年年内的更新问题。在每年年初作出一项决策，是继续使用还是更新。新的设备成本是年初作出一项决策，是继续使用还是更新。新的设备成本是10（单位千元，下同）。使用（单位千元，下同）。使用t年后的残值在年后的残值在t3时是时是s(t)=3-t；在在t3时是零。另一方面，使用时是零。另一方面，使用t年后每年所创造的利润在年后每年所创造的利润在t3时，时，是是p(t)=9-t2；而在；而在t3时，是零。问这时，是零。问这3年的每一年年初应年的每一年年初应

48、本讲稿第四十六页，共六十一页动态规划应用举例动态规划应用举例如何做出决策，才能使如何做出决策，才能使3年内总的利润达到最大？假定在第一年内总的利润达到最大？假定在第一年年初设备已使用了年年初设备已使用了1年。年。解：解：将每一年作为一个阶段，共三个阶段。每个阶段的将每一年作为一个阶段，共三个阶段。每个阶段的方案只有两个：继续使用和更新。相应的数量指标是这个阶方案只有两个：继续使用和更新。相应的数量指标是这个阶段的利润，如果按逆序计算，则可规定阶段段的利润，如果按逆序计算，则可规定阶段i(i=1,2,3)的状态的状态是第是第i年年初设备已使用的年限年年初设备已使用的年限Ti。设阶段。设阶段i的最

49、优指标函数是的最优指标函数是fi(Ti)，于是，基本方程是：，于是，基本方程是：继续使用继续使用更新更新继续使用继续使用更新更新本讲稿第四十七页，共六十一页动态规划应用举例动态规划应用举例化简得：化简得：分段计算如下：分段计算如下：阶段阶段3：见下表。：见下表。继续使用继续使用更新更新继续使用继续使用更新更新本讲稿第四十八页，共六十一页动态规划应用举例动态规划应用举例T3对设备所作出的决策最优值最优解继续使用更新f3(T3)决策12395-321951继续使用继续使用更新T2对设备所作出的决策最优值最优解继续使用更新f2(T2)决策1238+5=135+1=6-1+9=100+9=9-1+9=

50、81398继续使用更新更新阶段阶段2：见下表。见下表。本讲稿第四十九页，共六十一页动态规划应用举例动态规划应用举例T1对设备所作出的决策最优值最优解继续使用更新f1(T1)决策18+9=171+13=1417继续使用阶段阶段1：见下表。见下表。故第故第1年应继续使用，第年应继续使用，第2年应更新，第年应更新，第3年继续使用。这样，年继续使用。这样，3年的总利润年的总利润17万元达到最大值。万元达到最大值。本讲稿第五十页，共六十一页动态规划应用举例动态规划应用举例例例7.7 背包问题背包问题有一个人带背包上山，他可带物品重量的限度为有一个人带背包上山，他可带物品重量的限度为千克。千克。设有设有n