第八章-动态规划ppt课件.ppt

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

1、第八章第八章 动态规划动态规划第一节第一节 动态规划原理和模型动态规划原理和模型第二节第二节 一维动态规划求解方法一维动态规划求解方法第三节第三节 动态规划在经济和管理中的应用动态规划在经济和管理中的应用第一节第一节 动态规划原理和模型动态规划原理和模型一、引例与动态规划的基本概念一、引例与动态规划的基本概念二、动态规划的原理二、动态规划的原理三、动态规划模型的建立三、动态规划模型的建立动态规划是动态规划是5050年初由美国数学家年初由美国数学家R.BellmanR.Bellman等人提出等人提出的解决多阶段决策过程优化问题的的解决多阶段决策过程优化问题的“最优化原理最优化原理”基础上建立起来

2、的。基础上建立起来的。动态规划是将一个较复杂的多阶段决策问题分解为动态规划是将一个较复杂的多阶段决策问题分解为若干相互关联的较容易求解的子决策问题，而每一若干相互关联的较容易求解的子决策问题，而每一个子决策问题都有多种选择，并且当一个子决策问个子决策问题都有多种选择，并且当一个子决策问题确定以后，将影响另一个子决策问题，从而影响题确定以后，将影响另一个子决策问题，从而影响到整个问题的决策。到整个问题的决策。一、动态规划的基本概念一、动态规划的基本概念动态规划模型分为（动态规划模型分为（1 1）离散模型；（）离散模型；（2 2）连续模）连续模型。本章只讨论与离散模型有关原理和方法。这型。本章只讨

3、论与离散模型有关原理和方法。这对连续模型也适用。对连续模型也适用。下面通过一个多阶段决策过程的例子引入动态规下面通过一个多阶段决策过程的例子引入动态规划的基本概念、原理和方法。划的基本概念、原理和方法。例例8.18.1（最短路问题）某运输公司拟将一批货物从（最短路问题）某运输公司拟将一批货物从A A地运往地运往E E地，其间的交通系统网络如图地，其间的交通系统网络如图8-18-1所示。图上所示。图上节点表示地点，边表示两地之间的道路，边上的数字节点表示地点，边表示两地之间的道路，边上的数字表示两地间的运输费用，求运输费用最低的运输路线。表示两地间的运输费用，求运输费用最低的运输路线。相关的概念

4、相关的概念:AB1B2B3C1C2C3D1D2E第2阶段第3阶段第4阶段第1阶段5412331136444165798(1)(1)阶段阶段 将所给问题的过程，按时间或空间特征分解将所给问题的过程，按时间或空间特征分解成若干互相联系的阶段，按次序去求每阶段的解，成若干互相联系的阶段，按次序去求每阶段的解，用字母用字母k k表示阶段变量。表示阶段变量。AB1B2B3C1C2C3D1D2E第2阶段第3阶段第4阶段第1阶段的状态第2阶段的状态第1阶段541233113644416579s1状态状态A，s2?S1=A，S2=B1、B2、B3，S3=C1、C2、C3，S4=D1、D2。8(2)(2)状态状

5、态 状态就是阶段的起始位置。通常一个阶段包含若干个状态。状态就是阶段的起始位置。通常一个阶段包含若干个状态。第第k k阶段的状态就是该阶段所有始点的集合。描述各阶段状态阶段的状态就是该阶段所有始点的集合。描述各阶段状态的变量称为状态变量。常用的变量称为状态变量。常用s sk k表示第表示第k k阶段的状态变量。状态阶段的状态变量。状态变量的取值集合称为状态集合，用变量的取值集合称为状态集合，用S Sk k表示。表示。3 3）决策）决策决策是某阶段状态给定之后，从该状态演变到下一阶决策是某阶段状态给定之后，从该状态演变到下一阶段某一状态的选择。表示决策的变量称为决策变量，段某一状态的选择。表示决

6、策的变量称为决策变量，用用u uk k(s(sk k)表示第阶段，状态为表示第阶段，状态为s sk k时的决策变量，它是时的决策变量，它是状态变量的函数。实际问题中，决策变量的选取往往状态变量的函数。实际问题中，决策变量的选取往往受到某些条件的影响而限制于某一范围，此范围称为受到某些条件的影响而限制于某一范围，此范围称为允许决策集合。允许决策集合。AB1B2B3C1C2C3D1D2E第2阶段第3阶段第4阶段第1阶段的状态第2阶段的状态第1阶段541233113644416579在例在例8.18.1中，中，u u2 2(B(B1 1)就表示第就表示第2 2阶段状态为阶段状态为B B1 1时的决策

7、变量（它或时的决策变量（它或等于等于C C1 1或等于或等于C C3 3），即，从第），即，从第2 2阶段的状态阶段的状态B B1 1出发，可到达下一出发，可到达下一阶段的阶段的C C1 1或者或者C C3 3，所以这一阶段的允许决策集，所以这一阶段的允许决策集D D2 2(B(B1 1)=C)=C1 1,C,C3 3。84 4）策略）策略各阶段决策确定后，组成的一个有序的决策序列就各阶段决策确定后，组成的一个有序的决策序列就构成了一个策略。构成了一个策略。称为全过程的一个策略，称为全过程的一个策略，简称策略。简称策略。称为由第称为由第k k阶段开始阶段开始到最后阶段止的一个子策略，简称后部子

8、策略。到最后阶段止的一个子策略，简称后部子策略。使整个问题到达最优效果的策略称为最优策略。使整个问题到达最优效果的策略称为最优策略。动态规划方法就是要从允许策略集中找出最优策动态规划方法就是要从允许策略集中找出最优策略。略。AB1B2B3C1C2C3D1D2E第2阶段第3阶段第4阶段第1阶段的状态第2阶段的状态第1阶段541233113644416579p pA,EA,EA,BA,B2 2,C,C3 3,D,D2 2,E,E就是一个策略。就是一个策略。8p pB2,EB2,EBB2 2,C,C3 3,D,D2 2,E,E就是一个子策略。就是一个子策略。AB1B2B3C1C2C3D1D2E第2阶

9、段第3阶段第4阶段第1阶段的状态第2阶段的状态第1阶段541233113644416579状态转移方程为状态转移方程为 sk+1=uk(sk)85 5）状态转移方程）状态转移方程 它是确定过程由某一阶段的一个状态到下一阶段另一状态的它是确定过程由某一阶段的一个状态到下一阶段另一状态的演变过程，用演变过程，用sk+1=Tk(sk,uk)表示。该方程描述了由第表示。该方程描述了由第k k阶段到阶段到第第k k+1+1阶段的状态转移规律。因此又称其为状态转移函数。阶段的状态转移规律。因此又称其为状态转移函数。指标函数是用来衡量多阶段决策过程优劣的一种数量指标。指标函数是用来衡量多阶段决策过程优劣的一

10、种数量指标。一个一个n 阶段决策过程，从阶段决策过程，从1到到n 称为问题的原过程，对于任意称为问题的原过程，对于任意一个给定的一个给定的k（1kn），从第），从第k 阶段到第阶段到第n 阶段的过程称为原阶段的过程称为原过程的一个后部子过程。过程的一个后部子过程。用用 V1,n(s1,p1,n)表示初始状态为表示初始状态为s1 采用策略采用策略p1,n 时，原过程的指时，原过程的指标函数值。标函数值。Vk,n(sk,pk,n)表示在第表示在第k 阶段，状态为阶段，状态为sk采用策略采用策略pk,n 时，后部子时，后部子过程的指标函数值。过程的指标函数值。从第从第k 阶段状态阶段状态 sk采用最

11、优策略采用最优策略 p*k,n 到过程终止时的最佳效到过程终止时的最佳效益值，称为最优指标函数。记为益值，称为最优指标函数。记为fk(sk)。6 6）指标函数）指标函数 AB1B2B3C1C2C3D1D2E第2阶段第3阶段第4阶段第1阶段的状态第2阶段的状态第1阶段541233113644416579V2,4(B1)：表示在第：表示在第2阶段，状态为阶段，状态为B1时，从时，从B1到到E的距离。的距离。f2(B1)则表示从则表示从B1到到E的最短距离。的最短距离。8二、动态规划的原理二、动态规划的原理 在例在例8.18.1中，整个运输路程分为四个阶段，见图中，整个运输路程分为四个阶段，见图8.

12、28.2。下面给出求解的全过程。这里我们采用倒推。下面给出求解的全过程。这里我们采用倒推的方法，即从终点（的方法，即从终点（E E）到起点（）到起点（A A）。）。1 1第第4 4阶段，即从阶段，即从E E到到D D，从，从E E出发倒推到下一站出发倒推到下一站D D，它可通过它可通过D D1 1，也可通过，也可通过D D2 2，所需费用分别为，所需费用分别为5 5和和3 3。如果现处于状态如果现处于状态D D1 1，到终点，到终点E E的最佳路线费用：的最佳路线费用：f f4 4(D(D1 1)=5)=5，最优策略：，最优策略：u u4 4(D(D1 1)=E)=E。如果现处于状态如果现处于

13、状态D D2 2，到终点，到终点E E的最佳路线费用：的最佳路线费用：f f4 4(D(D2 2)=3)=3，最优策略：，最优策略：u u4 4(D(D2 2)=E)=E。第第3 3阶段，当从阶段，当从E E到达到达D D后，有两个状态后，有两个状态D D1 1和和D D2 2；若处于状态若处于状态D D1 1，则可到达，则可到达C C1 1或或C C2 2，则费用分别为，则费用分别为9 9或或7 7。若处于状态若处于状态D D2 2，则可到达，则可到达C C1 1或或C C2 2或或C C3 3，费用分别为，费用分别为8 8或或1212或或5 5。从从E E经经D D1 1到达到达C C1

14、1或或C C2 2 的费用，应加上的费用，应加上E E到达到达D D1 1这段的这段的费用，所以费用分别为费用，所以费用分别为5+9=145+9=14、5+7=125+7=12；从从E E经经D D2 2到达到达C C2 2或或C2C2或或C C3 3 的费用，应加上的费用，应加上E E到达到达D D2 2这这段的费用，所以费用分别为段的费用，所以费用分别为3+8=113+8=11、3+12=153+12=15、3+5=83+5=8。如果现在处于如果现在处于C1C1，则到达终点，则到达终点E E的最小费用为：的最小费用为：最小费用路线为最小费用路线为 相应的最优决策相应的最优决策u u3 3(

15、C(C1 1)=D)=D2 2。如果现在处于如果现在处于C2C2，则到达终点，则到达终点E E的最小费用为：的最小费用为：最小费用路线为最小费用路线为 。相应的最优决策。相应的最优决策:如果现在处于如果现在处于C3，到达终点，到达终点E的最小费用为：的最小费用为：最小费用路线为最小费用路线为 相应的最优决策相应的最优决策3第第2阶段，同上。阶段，同上。如果现处于如果现处于B1，到达终点，到达终点E的最小费用为：的最小费用为：最小费用路线为最小费用路线为 相应的最优决策相应的最优决策如果现处于如果现处于B2，则到达终点，则到达终点E的最小费用为：的最小费用为：最小费用路线为最小费用路线为 相应的

16、最优决策相应的最优决策如果现处于如果现处于B3，则到达终点，则到达终点E的最小费用为：的最小费用为：最小费用路线为最小费用路线为 相应的最优决策相应的最优决策4在第在第1阶段阶段A处，则到达终点处，则到达终点E的最小费用为：的最小费用为：最小费用路线为：最小费用路线为：相应的最优决策：相应的最优决策：所以，整个问题的最小费用路线为：所以，整个问题的最小费用路线为：最优策略为：最优策略为：，。在每一阶段的求解，都利用了第在每一阶段的求解，都利用了第k阶段和第阶段和第k+1 阶阶段的如下关系：段的如下关系：这种关系称为动态规划的基本方程。这种关系称为动态规划的基本方程。所谓最优化原理是：一个过程的

17、最优决策具有这所谓最优化原理是：一个过程的最优决策具有这样的性质：无论初始状态及初始决策如何，对于样的性质：无论初始状态及初始决策如何，对于先前决策所形成的状态而言，其以后的所有决策先前决策所形成的状态而言，其以后的所有决策应构成最优策略。应构成最优策略。三、动态规划模型的建立三、动态规划模型的建立 用动态规划解决实际问题，就要建立动态规划模用动态规划解决实际问题，就要建立动态规划模型，为此需要解决如下问题：型，为此需要解决如下问题：1.划分阶段划分阶段2.确定状态变量和决策变量以及相应的取值范围确定状态变量和决策变量以及相应的取值范围3.建立状态转移方程建立状态转移方程4.确定指标函数，建立

18、动态规划的基本方程确定指标函数，建立动态规划的基本方程5.确定边界条件确定边界条件 1.1.划分阶段划分阶段 按照时间、空间、变量划分为若干阶段。按照时间、空间、变量划分为若干阶段。建立动态规划模型要求每个阶段问题具有同一模式。建立动态规划模型要求每个阶段问题具有同一模式。2.2.确定状态变量和决策变量以及相应的取值范围确定状态变量和决策变量以及相应的取值范围 决策过程可用状态演变描述。状态必须包含表示系统情况和确定决决策过程可用状态演变描述。状态必须包含表示系统情况和确定决策所需要的全部信息，反映过程的演变特征。无后效性。找出状态策所需要的全部信息，反映过程的演变特征。无后效性。找出状态变量

19、在各阶段的取值范围。决策变量由系统最优化的目的所决定。变量在各阶段的取值范围。决策变量由系统最优化的目的所决定。3.3.建立状态转移方程建立状态转移方程 根据状态变量和决策变量的含义，写出状态转移方程。根据状态变量和决策变量的含义，写出状态转移方程。4.4.确定指标函数，建立动态规划的基本方程确定指标函数，建立动态规划的基本方程 选取指标函数，根据指标函数建立最优指标函数递推关系选取指标函数，根据指标函数建立最优指标函数递推关系,即基本方即基本方程程5.5.确定边界条件确定边界条件 增加研制费：万元新产品成功的概率甲乙丙0120.600.800.850.400.700.900.300.600.

20、70例例8.2.8.2.有一工厂研制甲、乙、丙三种新产品，估计这三种新有一工厂研制甲、乙、丙三种新产品，估计这三种新产品研制成功的概率分别为：产品研制成功的概率分别为：0.60.6、0.40.4、0.30.3。由于工厂急于。由于工厂急于推出新产品，决定再加拨推出新产品，决定再加拨2 2万元研制费，以提高新产品研制成万元研制费，以提高新产品研制成功的概率。据估计，把增加的研制费用于各种新产品研制时，功的概率。据估计，把增加的研制费用于各种新产品研制时，研制成功的概率见下表。现把这批研制费分配给各新产品（不研制成功的概率见下表。现把这批研制费分配给各新产品（不分配、分配给分配、分配给1 1万元或分

21、配给万元或分配给2 2万元），使这三种新产品都研制万元），使这三种新产品都研制成功的概率最大。应怎样分配。成功的概率最大。应怎样分配。划分阶段划分阶段 把对某一种新产品增加研制费用作为一个阶段，将整个过程分把对某一种新产品增加研制费用作为一个阶段，将整个过程分为三个阶段。对甲产品增加研制费用记为第为三个阶段。对甲产品增加研制费用记为第1阶段、对乙产品增加研制费阶段、对乙产品增加研制费用记为第用记为第2阶段、对丙产品增加研制费用记为第阶段、对丙产品增加研制费用记为第3阶段。阶段。K=1,2,3。状态变量状态变量 把有可能提供的研制费用作为状态变量，记为把有可能提供的研制费用作为状态变量，记为sk

22、，它的取值范围，它的取值范围是：是：0、1、2 决策变量决策变量 把给第把给第k种新产品的研制费用的数量作为决策变量种新产品的研制费用的数量作为决策变量 uk，它由决策它由决策者决定，不能超过当时拥有的金额者决定，不能超过当时拥有的金额 sk建立状态转移方程建立状态转移方程 sk+1=sk-uk 确定指标函数确定指标函数 确定边界条件确定边界条件 由于开始时可用的金额为由于开始时可用的金额为2万元，而最后将全部用完，所以万元，而最后将全部用完，所以 s1=2，s4=0 第二节第二节 一维动态规划求解方法一维动态规划求解方法一、逆推法一、逆推法二、顺推法二、顺推法逆推法是从最后一个阶段开始，逐阶

23、段向前，直至逆推法是从最后一个阶段开始，逐阶段向前，直至第一阶段，即可求出全过程最优策略和指标函数的第一阶段，即可求出全过程最优策略和指标函数的最优值。最优值。例例8.38.3用逆推法求解例用逆推法求解例8.28.2。一、逆推法一、逆推法 增加研制费 （万元）uk各阶段状态s（可提供的资金）、决策变量u的取值第一阶段第二阶段第三阶段012uk=sk-sk+1S1=0S1=1S1=2u1=s1-s2S2=0S2=1S2=2u2=s2-s3S3=0S3=1S3=2u3=s3-s4,s4=0 增加研制费 （万元）新产品成功的概率甲乙丙0120.600.800.850.400.700.900.300.

24、600.70第三阶段 s3=0 s3=1 s3=2第二阶段 s2=0 s2=1 s2=2第一阶段只有S1=2s2=s1-0=2s3=s2-1=1最优解0-1-1 从最后一个阶段开始，逐阶段向前，直至第一阶段，即可求出全从最后一个阶段开始，逐阶段向前，直至第一阶段，即可求出全过程最优策略和指标函数的最优值。过程最优策略和指标函数的最优值。二、顺推法二、顺推法逆推法是从最后一个阶段开始，逐阶段向前，直至第一阶段，逆推法是从最后一个阶段开始，逐阶段向前，直至第一阶段，即可求出全过程最优策略和指标函数的最优值。如果过程是可即可求出全过程最优策略和指标函数的最优值。如果过程是可逆的，即对每一状态，都可从

25、状态转移方程逆的，即对每一状态，都可从状态转移方程 得得到到 ，则可用顺推法，由第一阶段开始，逐阶段向，则可用顺推法，由第一阶段开始，逐阶段向后，直至最后一个阶段后，直至最后一个阶段。下面再用顺推法求解例下面再用顺推法求解例8.28.2。例例8.48.4用顺推法求解例用顺推法求解例8.28.2基本方程为：基本方程为：第第1 1阶段阶段 ：最优策略是最优策略是：第第2 2阶段：阶段：最优策略是：最优策略是：第第3 3阶段：阶段：最优策略是：最优策略是：第第2 2阶段：阶段：最优策略是：最优策略是：最优策略是：最优策略是：最优策略是：最优策略是：第第3 3阶段：阶段：最优策略是：最优策略是：故，最

26、优策略是：故，最优策略是：第三节第三节 动态规划在经济和管理中的应用动态规划在经济和管理中的应用一、背包问题一、背包问题二、生产计划问题二、生产计划问题三、货物存储问题三、货物存储问题四、设备更新问题四、设备更新问题五、资源分配问题五、资源分配问题六、复合系统可靠性问题六、复合系统可靠性问题一、背包问题一、背包问题第一阶段：只第一阶段：只装第一种物品装第一种物品允许装入前允许装入前1 1种种物品的总重量物品的总重量s s2 2 允许装入前允许装入前2 2种种物品的总重量物品的总重量s s3 3 第二阶段：只第二阶段：只装第二种物品装第二种物品该段可装入该段可装入x x1 1w w1 1该段可装

27、入该段可装入x x2 2w w2 2s s2 2=s=s3 3-x-x1 1w w1 1价值：价值：p p1 1(x(x1 1)+p)+p2 2(x(x2 2)+)+一位旅行者携带背包旅游，已知他的背包所能承受的重量为一位旅行者携带背包旅游，已知他的背包所能承受的重量为w w千克，现有千克，现有n n种物品可供他选择装入包中，第种物品可供他选择装入包中，第i i种物品的单件种物品的单件重量为重量为wi 千克，其价值是携带数量千克，其价值是携带数量 xi 的函数的函数 pi(xi)。问旅行。问旅行者应如何选择携带物品的件数，使总价值最大？者应如何选择携带物品的件数，使总价值最大？划分阶段划分阶段

28、 将可装入物品按将可装入物品按1,2,n 排序，每段装一种物品，共划分为排序，每段装一种物品，共划分为n个阶段，个阶段，k=1,2,n.状态变量状态变量 在第在第k阶段开始时，背包中允许装入前阶段开始时，背包中允许装入前k种物品的总重量，种物品的总重量，记为记为sk+1决策变量决策变量 装入第装入第k 种物品的件数，记为种物品的件数，记为xk建立状态转移方程建立状态转移方程 sk=sk+1-wkxk允许决策集合允许决策集合 确定指标函数确定指标函数 fk(sk+1)表示在背包中允许装入物品的总重量不超过表示在背包中允许装入物品的总重量不超过sk+1千克，并采用最优策略只装前千克，并采用最优策略

29、只装前k种物品时的最大使用价值。种物品时的最大使用价值。确定边界条件确定边界条件 背包所能承受的重量为背包所能承受的重量为w千克千克 货物种类k单件重量w k单件价值c k123132308065例例8.58.5：有一最大载重量为：有一最大载重量为5 5吨的船，将装载吨的船，将装载3 3种货物，每种货物种货物，每种货物的单件重量和单件价值见表，怎样装载才能使装载的总价值最的单件重量和单件价值见表，怎样装载才能使装载的总价值最大？大？设第设第k 种货物装载的件数为种货物装载的件数为xk(k=1,2,3)，划分为，划分为3个阶段，个阶段，每一阶段装一种物品。每一阶段装一种物品。Sk+1表示在第表示

30、在第k 阶段开始时，允许装阶段开始时，允许装入前入前k 种物品的总重量。则种物品的总重量。则 sk=sk+1-wkxk01234500 10 1 20 1 2 30 1 2 3 40 1 2 3 4 50306090120150012345K=1货物种类k单件重量w k单件价值c k1231323080650123450000 10 10 10306090 0120 30150 60030609012015000000001234500 10 1 20 1 2 30 1 2 3 40 1 2 3 4 50306090120150012345K=20123450000 10 10 1030609

31、0 0120 30150 600306090120150000000K=3 s4=5X*3=2 所以最优策略是：所以最优策略是：第第1 1种货物装载种货物装载1 1件，第件，第2 2种货物不装，第种货物不装，第3 3种货物装载种货物装载2 2件。件。最优价值是最优价值是 s4=5S2012345f1(s2)0306090120150 x1*012345s3012345f2(s3)0306090120150 x2*000000二、生产计划问题二、生产计划问题 已知企业产品的生产费用、存储费用和市场的需求量，已知企业产品的生产费用、存储费用和市场的需求量，在其生产能力和存储能力许可的前提下，怎样制

32、定各个在其生产能力和存储能力许可的前提下，怎样制定各个时期的生产计划，既能完成交货任务，又使总支出最小。时期的生产计划，既能完成交货任务，又使总支出最小。某中转仓库要按月在月初供应一定数量的某种部件给总某中转仓库要按月在月初供应一定数量的某种部件给总装车间，由于生产条件的变化，生产车间在各月份中生装车间，由于生产条件的变化，生产车间在各月份中生产每单位这种部件所需耗费的工时不同，各月份的生产产每单位这种部件所需耗费的工时不同，各月份的生产量于当月的月底前，全部要存入仓库以备后用。已知总量于当月的月底前，全部要存入仓库以备后用。已知总装车间的各个月份的需求量以及在加工车间生产该部件装车间的各个月

33、份的需求量以及在加工车间生产该部件每单位数量所需工时见表每单位数量所需工时见表 设仓库容量为设仓库容量为H H=9=9，开始库存量为，开始库存量为2 2，最终库存量为，最终库存量为0 0，要制，要制定一个半年的逐月生产计划，既满足需要和仓库容量的限制，定一个半年的逐月生产计划，既满足需要和仓库容量的限制，又使生产这种部件的总耗费工时数最少。又使生产这种部件的总耗费工时数最少。月份月份K K0123456需求量需求量d d k k0853274单单位工位工时时a a k k111813172010第第k k月月库存量为库存量为s sk k生产量为生产量为u uk k库存量为库存量为s sk+1k

34、+1需求量为需求量为d dk ks sk+1k+1=s sk k+u+uk k-d-dk k当月生产当月入库当月生产当月入库sk为第为第k月需求送出之前，上阶段产品送入之后月需求送出之前，上阶段产品送入之后划分阶段划分阶段 按月份划分阶段，每个月为一个阶段，按月份划分阶段，每个月为一个阶段，k=1,2,6.状态变量状态变量 第第k阶段开始时（即本阶段需求送出之前，上阶段产品送入阶段开始时（即本阶段需求送出之前，上阶段产品送入之后）部件库存量，记为之后）部件库存量，记为sk决策变量决策变量 第第k阶段内的部件生产量，记为阶段内的部件生产量，记为uk建立状态转移方程建立状态转移方程 sk+1=sk

35、+uk-dk，最优指标函数最优指标函数 fk(sk)表示在第表示在第k阶段开始的库存量为阶段开始的库存量为sk时，从第时，从第k阶段到阶段到最后一阶段生产部件的最小累计工时数。最后一阶段生产部件的最小累计工时数。基本方程基本方程 确定边界条件确定边界条件 so=开始库存量开始库存量2，s7=0，u6=0K=6K=6K=5K=5最优决策为：最优决策为：最小累计工时数为：最小累计工时数为：K=4K=4第第4 4阶段的最优决策为：阶段的最优决策为：最小累计工时数为：最小累计工时数为：sk+1=sk+uk-dk,so=2，s7=0，u6=0第第6阶段不生产，故阶段不生产，故u6=0K=3K=3u3的允

36、许集合：的允许集合：K=2K=2sk+1=sk+uk-dk,u0,s9d4=2,d3=3K=1K=1sk+1=sk+uk-dkK=0K=0故各月最优生产计划为：故各月最优生产计划为：7 7，4 4，9 9，3 3，0 0，4 4。sk+1=sk+uk-dkd1=8,H=9,s0=2三、货物存储问题三、货物存储问题例例8.7考虑下面三个月的库存问题，在每月初，公司必须决考虑下面三个月的库存问题，在每月初，公司必须决定在本月内，应生产多少产品。在一个月内生产定在本月内，应生产多少产品。在一个月内生产x 单位的产单位的产品，所需成本为，其中，当时，。每月最多生产品，所需成本为，其中，当时，。每月最多

37、生产4个单位，个单位，每月的需求是随机的，或为每月的需求是随机的，或为1或为或为2单位。如果生产的数量大单位。如果生产的数量大于需求，就出现库存。每个月末检查库存，于需求，就出现库存。每个月末检查库存，1个单位的库存个单位的库存费用是费用是1元。因为库存能力有限，每月末的库存量不能超过元。因为库存能力有限，每月末的库存量不能超过3单位。但同时要求必须及时满足需求。在第单位。但同时要求必须及时满足需求。在第3个月末要把现个月末要把现有的库存以每单位有的库存以每单位2元的价格售出。在第元的价格售出。在第1月的月初，公司有月的月初，公司有1单位的库存。如何制定生产策略使三个月内的期望费用最单位的库存

38、。如何制定生产策略使三个月内的期望费用最小。小。解：划分阶段：将三个月份为三个阶段，每个月为一个阶段解：划分阶段：将三个月份为三个阶段，每个月为一个阶段状态变量：状态变量：sk表示第表示第k 个月初的库存数。则个月初的库存数。则s1=1。决策变量：决策变量：xk表示第表示第k月生产的单位数。月生产的单位数。显然有状态转移方程：显然有状态转移方程：sk+1=sk+xk-ak，其中，其中ak为一随机需求为一随机需求量或为量或为1或为或为2。fk(sk)表示第表示第k个月初的库存是个月初的库存是sk 时，第时，第k 个月至第个月至第3个月内个月内的最小期望费用。的最小期望费用。则第则第3个月的期望费

39、用是：个月的期望费用是：其中其中当当k=1，2时，有动态规划的基本方程：时，有动态规划的基本方程：其中其中 用逆序法求解得最优策略是用逆序法求解得最优策略是 即第一个月生产即第一个月生产3个单位，第二、第三个月不生产。个单位，第二、第三个月不生产。最小成本是最小成本是 元。元。四、设备更新问题四、设备更新问题现有一台效益函数为现有一台效益函数为r(t)的设备，其维修费用为的设备，其维修费用为u(t)、更新费、更新费用为用为c(t)，需要在，需要在n 年内的每年年初做出决策，是继续使用旧年内的每年年初做出决策，是继续使用旧设备还是更换一台新设备，使设备还是更换一台新设备，使n年总效益最大。年总效

40、益最大。设设r(t)：在第：在第k年设备已使用过年设备已使用过t年，再使用年，再使用1年时的效益。年时的效益。uk(t)：在第：在第k年设备已使用过年设备已使用过t年，再使用年，再使用1年时的维修费用。年时的维修费用。ck(t)：在第：在第k年卖掉一台已使用年卖掉一台已使用t年的设备，买进一台新设备年的设备，买进一台新设备的更新净费用。的更新净费用。a：折扣因子（：折扣因子（0a 1），表示一年以后的单位收入价值相当），表示一年以后的单位收入价值相当于现年的于现年的a单位。单位。如果年初决定把使用如果年初决定把使用t年的旧年的旧设备设备再再继续继续使用使用1年，年，则则在在这这一一年内所得回收

41、年内所得回收额为额为：如果年初决定把使用如果年初决定把使用t年的旧年的旧设备卖设备卖掉掉购买购买一台新一台新设备设备，则则在在这这一年内所得回收一年内所得回收额为额为：建立动态规划模型建立动态规划模型划分阶段：划分阶段：k（k=1,n）表示计划使用该设备的年限数。）表示计划使用该设备的年限数。状态变量状态变量sk：第：第k年初，设备已使用过的年数。年初，设备已使用过的年数。决策变量决策变量xk：第：第 k 年初更新，还是继续使用旧设备，分别用年初更新，还是继续使用旧设备，分别用R 和和 K 表示。表示。状态转移方程为：状态转移方程为：动态规划的基本方程为：动态规划的基本方程为：五、资源分配问题

42、五、资源分配问题设设有一原料，有一原料，总总量量为为a，用于生，用于生产产n种种产产品。若分配数量品。若分配数量xi 用用于生于生产产第第i种种产产品，其品，其产产生的效益生的效益为为ri(xi)。问问如何分配，才能如何分配，才能使生使生产产n种种产产品的品的总总收入最大？收入最大？建立动态规划建立动态规划划分阶段：将划分阶段：将n 种产品按的序号排列，每种产品为一个阶段，种产品按的序号排列，每种产品为一个阶段，分为分为n个阶段，个阶段，k=1,n。状态变量：状态变量：sk表示分配给第表示分配给第k个产品至第个产品至第n 种产品的资源数。种产品的资源数。决策变量：决策变量：xk表示分配给第表示

43、分配给第k个产品的资源数。个产品的资源数。状态转移方程：状态转移方程：sk+1=sk-xkfk(sk)表示在拥有资源表示在拥有资源sk，分配给第，分配给第k种产品至第种产品至第n 种产品所种产品所得到的最大总收入。得到的最大总收入。则有动态规划的基本方程：则有动态规划的基本方程：边界条件：因为在第边界条件：因为在第1阶段时的资源为总资源，到第阶段时的资源为总资源，到第n+1阶段阶段时资源已分配完毕，所以时资源已分配完毕，所以s1=a，sn+1=0，fn+1(sn+1)=0。六、复合系统可靠性问题六、复合系统可靠性问题例例8.9某厂某厂设计设计一种一种电电子子设备设备，由三种元件，由三种元件D1

44、，D2，D3组组成，已知成，已知这这三种元件的价格和可靠性如表三种元件的价格和可靠性如表8-8所示。要求在所示。要求在设计设计中所使用元件的中所使用元件的费费用不超用不超过过105元，元，试问应试问应如何如何设计设计使使设备设备的可靠性达到最大的可靠性达到最大(不考不考虑虑重量的限制重量的限制)。表表 8-8解：按元件种类划分为三个阶段，设状态变量解：按元件种类划分为三个阶段，设状态变量sk(k=1,2,3)表示能容许用在表示能容许用在Dk元件至元件至D3元件的总费用；决策变量元件的总费用；决策变量xk表表示在示在Dk元件上的并联个数；元件上的并联个数；Pk表示一个元件正常工作的概表示一个元件

45、正常工作的概率，则率，则 为为xk个个Dk元件不正常工作的概率，令最优元件不正常工作的概率，令最优值函数值函数fk(sk)表示由状态表示由状态sk开始从开始从Dk元件至元件至D3元件组成的系元件组成的系统的最大可靠性，因而有统的最大可靠性，因而有由于由于s1=105，故此问题求只要出，故此问题求只要出f1(105)即可即可.同理同理从而求得最优方案：从而求得最优方案：，即，即D1元件用元件用1个，个，D2元件用元件用2个，个，D3元件用元件用2个，其总费用为个，其总费用为100元，可元，可靠性为靠性为0.648。第四节第四节 Lingo软件对几类特殊动态规软件对几类特殊动态规划问题的实现划问题的实现略略谢谢 谢！谢！