运筹学第八章动态规划课件.ppt

2023/4/111第1页，此课件共90页哦8.18.1动态规划的研究对象和特点 动态规划动态规划(Dynamic Programming)(Dynamic Programming)是一项重要的数量规划方是一项重要的数量规划方法，由美国数学家贝尔曼法，由美国数学家贝尔曼(R.Bellman)(R.Bellman)和徳赖费斯（和徳赖费斯（DreyfusDreyfus）等人在二十世纪中叶提出的。等人在二十世纪中叶提出的。19571957年，贝尔曼发表了动态规划方面年，贝尔曼发表了动态规划方面的第一本著作的第一本著作Dynamic ProgrammingDynamic Programming,标志着运筹学的标志着运筹学的又一个分支动态规划的建立。又一个分支动态规划的建立。动态规划被广泛应用于企业经营、工业工程、资源理论、动态规划被广泛应用于企业经营、工业工程、资源理论、最佳控制理论和商业决策理论中，并且取得了一定的经济效最佳控制理论和商业决策理论中，并且取得了一定的经济效果。果。2第2页，此课件共90页哦一、动态规划的研究对象 动态规划最初是根据多阶段决策问题的特点，由贝尔曼等人提出了动态规划最初是根据多阶段决策问题的特点，由贝尔曼等人提出了解决此类问题的解决此类问题的“最优化原理最优化原理”，并且进一步成功地解决了许多实际问题，并且进一步成功地解决了许多实际问题，才得到大家的充分重视。才得到大家的充分重视。1.多阶段决策又称序贯决策问题，通常它可以按时间顺序分成若干个多阶段决策又称序贯决策问题，通常它可以按时间顺序分成若干个相互联系的阶段，在每一个阶段都需要作出一个决策，每一个阶段作出相互联系的阶段，在每一个阶段都需要作出一个决策，每一个阶段作出的决策又称为子策略，每个阶段作出的子策略就组成此多阶段决策问题的决策又称为子策略，每个阶段作出的子策略就组成此多阶段决策问题的策略集。实际工作中我们很难遇到不影响未来决策的当前决策，决策的策略集。实际工作中我们很难遇到不影响未来决策的当前决策，决策者经常面临的问题通常是要他们作出一系列决策，而这些决策中的每一者经常面临的问题通常是要他们作出一系列决策，而这些决策中的每一个均依赖于先前决策的结果，动态规划就可被用来解决很多此类问题。个均依赖于先前决策的结果，动态规划就可被用来解决很多此类问题。2.动态规划也可以应用于解决某些与时间无关的问题。例如：把固定数量动态规划也可以应用于解决某些与时间无关的问题。例如：把固定数量的几种资源在若干用途上进行配置，这个问题被划分成几个步骤来求解，的几种资源在若干用途上进行配置，这个问题被划分成几个步骤来求解，用这种方法求最后的决策就好象它和时间有关似的，这就进一步扩大了动用这种方法求最后的决策就好象它和时间有关似的，这就进一步扩大了动态规划解决问题的范围。态规划解决问题的范围。3第3页，此课件共90页哦二二 、动态规划、动态规划的特点的特点 1.动态规划根据问题的具体情况，把整个问题划分成数个阶段，而变成数动态规划根据问题的具体情况，把整个问题划分成数个阶段，而变成数个部分问题。当这些部分问题由阶段的顺序而贯通，则形成一项多重阶段个部分问题。当这些部分问题由阶段的顺序而贯通，则形成一项多重阶段的程序（过程）。的程序（过程）。2.动态规划对整个问题的求解，通常是从一个阶段的部分问题开始，逐个逆序向动态规划对整个问题的求解，通常是从一个阶段的部分问题开始，逐个逆序向前推求解。对某些问题也可以反过来从最前一个阶段顺序向后推求解。但逆序求前推求解。对某些问题也可以反过来从最前一个阶段顺序向后推求解。但逆序求解是动态规划的一个显著特点。解是动态规划的一个显著特点。3.动态规划在每一个阶段求得自以往各阶段至本阶段的最佳解，并将此项动态规划在每一个阶段求得自以往各阶段至本阶段的最佳解，并将此项最佳解带入次阶段。最佳解带入次阶段。4.动态规划的目标是全局（系统）的最优化，而不仅是局部（本阶段）的优化。动态规划的目标是全局（系统）的最优化，而不仅是局部（本阶段）的优化。5.动态规划与运筹学的其它分支不同，它没有标准的数学表达式和解题动态规划与运筹学的其它分支不同，它没有标准的数学表达式和解题规则，但却是更一般性的解题方法。一个动态规划问题公式的格式在规则，但却是更一般性的解题方法。一个动态规划问题公式的格式在性质上和复杂程度上会与其它动态规划问题大不一样，其差异取决于性质上和复杂程度上会与其它动态规划问题大不一样，其差异取决于问题的结构。解题时要有丰富的想象力和创造性技巧。问题的结构。解题时要有丰富的想象力和创造性技巧。总之，应用动态规划可把一个复杂的难以下手的大问题变成一总之，应用动态规划可把一个复杂的难以下手的大问题变成一系列较易于各个解决的小问题，然后可以一个一个求解。所以许多问系列较易于各个解决的小问题，然后可以一个一个求解。所以许多问题用动态规划求解，常较运筹学的其它方法更有效果。题用动态规划求解，常较运筹学的其它方法更有效果。4第4页，此课件共90页哦三、动态规划数学模型的类型三、动态规划数学模型的类型 J 动态规划分为离散确定性、离散随机性，连续确定性、连续随机性四种决策类型。本章主要研究离散型动态规划，这也正是动态规划的核心内容和特色所在 5第5页，此课件共90页哦第6页，此课件共90页哦一、多阶段决策问题（漫游数学家问题）这是一个典型的多阶段决策问题，通过这个例子，有助于我们更好的理解动态规划的基本概念和基本思路。例81 有一个智慧比金钱多的应用数学家渴望进行一次旅行。假设他住在城市1，而渴望到城市10（见图8-1表示可能的路线和花费）。这是一个长途的旅行，要求必须进行3次中间停留，中间站可以选择。他希望为这次旅行付出的花费最小，那么他将选择那些城市作为自己的中间站？7第7页，此课件共90页哦 0站站 1站站 2站站 3站站 4站站 .图图 8-1 6847124415263810974134113695538第8页，此课件共90页哦分析：他可以采用枚举法，列出所有18种可能的路线来解决这个问题。是否有更好的方法？例如：假设我们在城市5，可通过城市8，也可通过城市9到达城市10，很明显我们会选城市9而不会选城市8。因为（8+3）（9+5）,即（5910）这条路花费较少,由于可按三种不同的路线到达城市5，可以看出枚举法将做不少不必要的工作。这个相当简单的观察为我们提供了一种解题的思路。若我们处在第3站，可通过城市8或9到达城市10可用表81说明 表81 第3站城市Min（f）最佳路径858-10939-109第9页，此课件共90页哦 现在假定在第2站，并问哪一条路到城市10最近，花费最小。若在城市5，最小花费是11，即Min9+5,8+3=11，将选择路径（5910）。同理若在城市6最小花费是12，Min7+5,12+3=12，将选择（6810）。城市7最小费用8，Min-,5+3=8，将选择路径为（7910），结果列于表82 表82第2站城市 Min（f）最佳路径5115-9-106126-8-10787-9-1010第10页，此课件共90页哦 现在假定在第1站，用类似方法可知：由城市2到城市10的最小费用为Min3+11,-,4+8=12，路径为（25910）。第一站计算结果为表83 表83 第1站城市Min（f）最佳路径2122-7-9-103143-7-9-104124-5-9-1011第11页，此课件共90页哦最后假定在第0站即城市1也就是起点，那么由城市1到城市10最小花费的路线，应由城市1到第一站的哪个城市呢？由Min4+12,3+14,11+12=16 可知花费最小的路线为（127910），第0站计算结果见表84 表84第0站城市Min（f）最佳路径11612791012第12页，此课件共90页哦5263810974134113469712553446181234053111281214121613第13页，此课件共90页哦 阶段和阶段变量.状态和状态变量.决策和决策变量.策略和最优策略.指标函数 .状态转移方程 .第14页，此课件共90页哦 1.阶段（Stage）和阶段变量 把所给问题的过程，按照时间或空间恰当地划分为若干个相互联系的阶段，以便于求解。描述阶段的变量称为阶段变量，通常用K表示阶段变量。如例8-1可分为4个阶段，当K=2时，表示对第2阶段求解。15第15页，此课件共90页哦2.状态（State）和状态变量 状态表示某阶段的初始位置，它既是该段某支路的始点，同时也是前一阶段某支路的终点。通常一个阶段，包含若干个状态。描述过程状态的变量，称为状态变量，可用一个数、一组数或一个向量表示。用SK K表示，如例81中，阶段2有三个状态。则状态变量S2 2可取，S2 2=3表示第二阶段在状态3城市3处考虑问题 16第16页，此课件共90页哦3.决策Deciding和决策变量 决策就是某阶段状态给定以后，从该状态演变到下一阶段某状态的选择。描述决策的变量，称为决策变量（它是改变状态变量的机会，可能以概率方式出现），常用XK(SK)表示第K阶段当状态为SK时的决策变量，它是状态SK的函数。在实际问题中，决策变量的取值往往限制在某一范围之内，此范围称为允许决策集合，通常用DK(SK)表示第K阶段的关于SK状态的允许决策集合。显然有 XK(SK)DK(SK)17第17页，此课件共90页哦4策略（Strategies）和最优策略 由过程的第K阶段开始到终点为止的过程称为问题的后部子过程。由后部子过程的每个阶段的决策组成的决策函数序列 XK(SK)，XK+1(SK+1)Xn(Sn)就称为子过程的策略，简称子策略。并记为：PK.n(SK)=XK(SK)，XK+1(SK+1).Xn(Sn)当K=1时，则此决策函数序列就是全过程的一个策略，简称策略，记为P1.n(S1)。可供选择的策略范围，称为允许策略集合用P表示。使问题达到最优效果的策略，称为最优策略。例81中：X1(1)=2,X2(2)=7,X3(7)=9,X4(9)=10就是一个策略，且为最优策略。18第18页，此课件共90页哦5指标函数和最优指标函数值 阶段指标函数是用来表示某阶段给定状态和决策取得效应的一种数量指标。它是定义在第K阶段上的一个数量函数。用v K.N表示：v K.N=v K.N(SK,XK)过程指标函数（简称指标函数；又称目标函数）是用来衡量所考查过程效应的一种数量指标。它是定义在从第K阶段到终点过程上的一个数量函数。用 V K.N表示：V K.N=V K.N(SK,XK.SK+1,XK+1SN+1)(k=1,2N)当初始状态给定时过程的策略就确定了，因而指标也就确定了，所以指标函数又是初始状态和策略的函数即：V K.N=V K.N(SK，P K.N(SK)19第19页，此课件共90页哦5指标函数和最优指标函数值 指标函数VK.N的最优值，称为相应的最优指标函数值记为：FK(SK)=opt VK N(SK，PK.N(SK)式中opt是optimization(最优化)的缩写，根据问题不同取Max或Min。在不同问题中指标的涵义不同，可以是距离、费用、收益、产品产量、资源消耗等。从例81中：VK.N表示第k阶段的点SK到终点城市10的花费。FK(SK)=MinVK,N表示SK到城市10的最小花费。20第20页，此课件共90页哦6.状态转移方程 状状态态转移方程表示从阶段k到阶段k+1的状态转移规律的表达式。多级决策过程中，如给定了第K阶段的状态变量SK和决策变量XK(SK)，则下一阶段K+1阶段状态变量的值也就确定了。即 SK+1=TK(SK,XK(SK)上式又称为状态转移函数。21第21页，此课件共90页哦三、动态规划数学模型的构造条件 1.能够恰当地划分问题的阶段，把问题化为多阶段决策过程；2.正确地选择状态变量 动态规划中的状态要能描述受控过程的演变特征：满足无后效性和可知性。22第22页，此课件共90页哦 无后效性如果过程某阶段的状态给定，则在这个阶段以后过程的发展不受前面各个阶段的影响，只和当前状态及今后的决策有关，过程前面的状态和决策只能通过形成的当前状态去影响过程未来的发展，即重要的是当前的状态和今后的决策而于过去的状态和决策无关。可知性各阶段状态变量的值直接或间接均为已知。23第23页，此课件共90页哦3.能确定决策变量及各阶段的允许决策集合；4.能写出状态转移方程；5.根据实际问题，列出指标函数VK,N，要满足递推关系。VK,N(SK,XK,SK+1,XK+1,SN+1)=SK,XK,VK+1.N(SK+1,XK+1,SN+1)一般是求和或求积的关系。24第24页，此课件共90页哦 四、最优化原理和基本方程 1.最优化原理 最优策略具有这样的性质：无论过去状态和决策如何，对前面决策所形成的某一状态而言，余下的决策序列必须构成最优策略。25第25页，此课件共90页哦2.动态规划的基本方程 利用最优化原理，把多阶段决策问题的求解过程分解为一个连续的递推过程，由后向前逐步推算。求解时，各阶段以前的状态和决策，对后部子过程来说，只充当其初始条件，并不影响后面过程的最优策略。据此可得出动态规划的递推关系：为使关系式表达方便,可对问题增加第N+1阶段此时有：FN+1(SN+1)=e e为一常数FN+1(SN+1)=e又称为动态规划的边界条件。26第26页，此课件共90页哦2.动态规划的基本方程 对于任何第K阶段（1KN）当 VK,N=vj(Sj,Xj)时则有 FK(SK)=opt vK(SK,XK)+Fk+1(SK+1)XK(SK)DK(SK)sKSK 27第27页，此课件共90页哦2.动态规划的基本方程又当 VK,N=vj(Sj，Xj)时则有Fn+1(Sn+1)0Fk(Sk)=optVk(Sk,Xk)Fk+1(Sk+1)Xk(Sk)Dk(Sk)SkSk再有状态转移函数Sk+1=Tk(Sk,Xk(Sk)问题就可以求解啦 28第28页，此课件共90页哦例82：求X1、X2、X3在满足约束条件：X1+X2+X3=C Xi0 (i=1,2,3)之下，使函数F(X1、X2、X3)=X1X2X3 MaxK:按变量将问题划分为3 个阶段，每个阶段只决定X1、X2、X3 其中一个变量的值。SK:表示第K个阶段初尚未分配出的数值，S1=CXK：表示第K个阶段分配给的数值,0XKSK状态转移函数：Sk+1=SKXK (K=1、2、3)各个阶段效益按乘积组合，所以基本方程为：FK(SK)=max XK Fk+1(Sk+1)(K=1,2,3)0XKSK F4(S4)=129第29页，此课件共90页哦 例83 某公司有资金1000万元，拟投资项目有3 个，已知对第i个项目投资Xi万元，净收益为g i(Xi)，应如何分配资金才能使公司总的净收益最大？这个问题与时间无明显关系，我们可按项目将问题分为三个阶段，每个阶段只考虑对一个项目的投资额。K=3状态变量SK表示第K个阶段初未分配资金额。决策变量XK表示第K个阶段分配给第K个项目的投资额。状态转移函数为：SK+1=SK-XK （K=1、2、3）指标函数 基本方程为：FK(SK)=max g K(XK)+FK+1(SK+1)(K=1,2,3)0XK SK F4(S4)=030第30页，此课件共90页哦 8.2 动态规划的基本概念与最优化原理 根据动态规划的基本思路和最优化原理，一般列出其基本方程即可对实际问题进行求解，但有些问题由于结构的不同，其基本方程可能有特殊性，关键是要灵活地创造性地应用动态规划的最优化原理和思想。31第31页，此课件共90页哦8.3 动态规划的求解与应用一、动态规划的解法 动态规划的求解有两种基本方法：逆序解法（后向动态规划）、顺序解法（前向动态规划）（一）逆序解法 逆序解法的寻优方向与实际决策过程的行进方向相反，它是从最后一个阶段开始逐段向前推进，从而求得全过程的最优策略，这种方法更体现动态规划的本质和最优化原理：不管过去如何，只求未来更优。前面我们建立的动态规划模型均是按逆序方法建立的，它也是求解动态规划问题的主要方法。例84 用动态规划逆序法求解例例82解：基本方程为：FK(SK)=Max XK Fk+1(Sk+1)(K=1,2,3)0XKSK F4(S4)=1状态转移函数为：Sk+1=SKXK (K=1、2、3)32第32页，此课件共90页哦8.3 动态规划的求解与应用第阶段，K=3 F3(S3)=Max X3 F4(S4)0X3 S3 =Max X3 1 0X3 S3 =S3 X3 =S3 第阶段，K=2 F2(S2)=Max X2 F3(S3)0X2S2 =Max X2 S3 0X2S2 =Max X2 (X2-S2)=Max(S2/2)2-(X2-S2/2)2 =(S2/2)2 X2=S2/233第33页，此课件共90页哦8.3 动态规划的求解与应用第阶段，K=1 F1(S1)=Max X1 F2(S2)0X1 S1 =Max X1 (S2/2)2 =Max X1 (S1-X1/2)2 =(S1/3)3 X1=S1/3由于初始状态S1=C 所以：S1=C X1*=C/3 F1 (C)=(C/3)3 S2=C-X1*=2C/3 X2*=C/3 F2(S2)=(C/3)2 S3=S2-X2*=C/3 X3*=S3=C/3 F3(S3)=(C/3)所以最优策略为：X1*=X2*=X3*=C/3最优指标函数的值为：F1 (S1)=F1 (C)=(C/3)334第34页，此课件共90页哦8.3 动态规划的求解与应用（二）顺序解法 顺序解法的寻优方向与实际决策过程的行进方向相同，它是从第一个阶段（始点）开始，逐段向后推进，从而求得全过程的最优策略。顺序解法的阶段变量、状态变量设置同逆序解法相同，而最优指标函数FK(SK+1)表示第K阶段末的结束状态为SK+1时，从第一阶段到第K阶段所得到的最大收益。一般选择第K阶段末（即第K+1阶段）的状态作为第K阶段的状态变量 状态转移方程为：SK=TK(SK+1,XK)基本方程为：FK(SK+1)=opt VK(SK+1,XK)+FK-1(SK)XK(SK+1)DK(SK+1)F0(S1)=0 式中FK(SK+1)指第K阶段状态为SK+1时从始点到第K阶段的最优指标函数值；VK(SK+1,XK)表示第阶段末状态为SK+1时，决策变量为XK时本阶段的效益值35第35页，此课件共90页哦8.3 动态规划的求解与应用 逆序解法和顺序解法两者的解题方向不同，但结果是一致的。在解动态规划问题时，顺序解法有时比较困难，甚至有些问题根本无法采用顺序解法，而逆序解法在大多数情况下都比较方便。一般来讲，当过程的终点状态给定时，可采用顺序解法，当过程的起点状态和终点状态都给定时，则逆序解法和顺序解法都会得到最优结果，只给定初始状态时则无法采用顺序解法，因大多数问题均只有初始状态，所以常用逆序解法。求解动态规划问题时，除了我们介绍的数学解析方法，对离散型问题可能用表格法更合适，下面我们将结合具体应用问题进行介绍。36第36页，此课件共90页哦二、动态规划的应用 动态规划的应用范围很广，解题的方法也各有不同。下面我们将介绍一些典型应用问题，进一步加深对动态规划的理解和解题技巧的掌握。（一）资源分配问题（一维资源分配问题）资源分配问题，是指将供应量有限的一种或若干种资源（如原材料、资金、机器、劳力、食品等）分配给若干用户，而使目标函数最优。设有某种原料总量为M，拟用来进行N种生产活动。若分配数量为Xi的原料用于第i种生产活动，其收益为gi(Xi)，问应如何分配才能使N种生产活动的总收益最大？这类问题可写成静态规划问题：Max g1(X1)+g2(X2)+g n(X n)X1+X2+Xn=M Xi0 i=1,2,3,n37第37页，此课件共90页哦（一）资源分配问题（一维资源分配问题）在用动态规划方法求解此类问题时，一般地将N种活动作为一个互相衔接的整体，由于要确定分给每种活动的资源数，所以通常把资源分配给一个或几个使用者的过程划分为若干个阶段，每个阶段都要确定分配给某一种活动的资源量，并且首先要对N种活动指定分配的阶段序号。由于将阶段联系在一起的是所有生产活动都在争取的资源，因此状态变量就要按照资源分配来确定。把第K个阶段的状态变量SK定义为第K阶段初所拥有的资源量，即将要在第K种活动到第N种活动之间分配的资源量。这样我们在确定第K个阶段的资源分配时就不需要考虑第K个阶段以前的资源分配情况。决策变量XK定义为第K个阶段对资源的分配量，即对第K种活动的资源分配量。38第38页，此课件共90页哦（一）资源分配问题（一维资源分配问题）状态变量的约束条件是：0SKM 决策变量的约束条件是：0XKSK 此时状态转移函数是：SK+1=SK-XK即第K+1阶段初的资源拥有量等于第K阶段初的资源拥有量与分配量之差。显然，它满足无后效性。阶段指标函数为对第K个阶段分配资源XK时的收益：VK(SK,XK)=gK(XK)目标函数FK(SK)为从第K个阶段到第N个阶段按最优分配方案分配资源后的最大总收益，则动态规划的基本方程为 FK(SK)=Max g K(SK)(XK)+FK+1(SK+1)(K=1,2,3,-,n)0XKSK Fn+1(Sn+1)=039第39页，此课件共90页哦（一）资源分配问题（一维资源分配问题）例8-6 某机械公司购置五台先进设备，需分给所属的甲，乙，丙三个工厂。各工厂获得这些设备后，每年为公司提供的盈利（万元）见表85：表85 单位：万元 设备数工厂012345甲03791213乙0510111111丙04611121240第40页，此课件共90页哦（一）资源分配问题（一维资源分配问题）问如何分配这些设备才能使公司得到的盈利额最大。此问题当设Xi(i=1,2,3)为分配给第i个工厂的设备数时，gi(Xi)为第i个工厂的盈利时，可以写成静态规划问题:Maxg1(X1)+g2(X2)+g3(X3)X1+X2+X3=5 Xi 0 i=1,2,3 无法用单纯形方法求解，枚举法比较麻烦。故采用动态规划的方法，特别当工厂和设备数量增大时，采用动态规划的方法更方便一些。41第41页，此课件共90页哦（一）资源分配问题（一维资源分配问题）解：将问题按工厂划分为三个阶段，三个工厂的编号分别记为1，2，3。SK表示分配给第K个工厂到第3个工厂的设备台数，XK表示 分配给第K个工厂的设备台数：S1=5 SK+1=SK-XK VK(XK)表示XK台设备分配到第K 个工厂得到的盈利值。FK(SK)表示SK台设备分配到第K个工厂至第三个工厂所得的最大盈利。因此有递推关系：FK(SK)=Max VK(XK)+FK+1(SK-XK)(K=1,2,3)0XKSK (K=1,2,3)F4 (S4)=042第42页，此课件共90页哦（一）资源分配问题（一维资源分配问题）现从最后一个阶段向前递推求解：阶段 K=3 设把S3台设备（S3=0，1，2，3，4，5）全部分配给工厂3时，则最大盈利值为：F3(S3)=Max V3(X3)X3=0,1,2,3,4,5因为只有一个工厂，给不同台数的盈利就是每种情况下的最大盈利。因此最优方案是把全部设备放到工厂3去。数值计算及决策见表86x3s3V3(x3)+F4(S4)F3(s3)x3*01234500001044120466230461111340461112124504611121212543第43页，此课件共90页哦（一）资源分配问题（一维资源分配问题）阶段 K=2 设把S2台（S2=0，1，2，3，4，5）设备全部分给工厂3、工厂2时，则最大盈利值为：F2(S2)=Max V2(X2)+F3(S2-X2)X2=0,1,2,3,4,5 选择X2数值使F2(S2)最大决策及计算结果如表67：x2s2V2(X2)+F3(S2-X2)F2(s2)X2*012345000010+45+05120+65+410+010230+115+610+411+014240+125+1110+611+411+0161&250+125+1210+1111+611+411+021244第44页，此课件共90页哦（一）资源分配问题（一维资源分配问题）阶段 K=1 设把S1台设备（S1=5）分配给1，2，3三个工厂，则最大盈利值为：F1(S1)=Max V1(X1)+F2(S1-X1)X1=0,1,2,3,4,5现选取X1的值，使F1(S1)最大，数值计算见表68由表中可知：最优方案有二个：(1)X1=0 X2=2 X3=3 F1(S1)=21 (2)X1=2 X2=2 X3=1 F1(S1)=21如资源是连续的，则解题时首先必须将问题进行离散化处理，如本问题不是5台设备而是50万元人民币，那么我们可以每10万元为单位进行分割，当然也可以1万元为单位分割，但计算工作量会大幅度提高，因此分割单位的选择十分重要 x1s1V1(X1)+F2(S1-X1)F1(s1)X1*01234550+213+167+149+1012+513+0210&245第45页，此课件共90页哦(二)资源分配问题（考虑资源回收的问题）例8-7某个公司新购某种机床125台。这种设备5年后将被其它新设备代替，此机床如在高负荷状态下工作年损坏率为1/2，每台年收益为10万元；如在低负荷下工作年损坏率为1/5，每台年收益为6万元。问应如何安排这些机床的生产负荷，才能使5年内所获收益最大？46第46页，此课件共90页哦(二)资源分配问题（考虑资源回收的问题）解：按年度划分为5个阶段，用K表示阶段序号。状态变量SK 为第K年拥有完好设备的数量，决策变量XK 为第K年中处于高负荷工作的设备数量，决策变量(SKXK)为第K年中处于低负荷工作的设备数量状态转移函数即第K+1年年初完好的设备台数:SK+1=SK1/2 XK 1/5(SKXK)=4/5 SK3/10 XK第K阶段允许决策集合为 DK(SK)=XK/0XKSK VK(SK,XK)为第K年度的收益则 VK=VK(SK,XK)=10 XK+6(SKXK)=6SK+4XK47第47页，此课件共90页哦(二)资源分配问题（考虑资源回收的问题）因此基本方程为:FK(SK)=Max 6SK+4XK+FK+1(SK+1)0XKSK K=1,2,3,4,5 F6(S6)=0 下面求解问题：阶段 K=5 F6(S6)=0 有：F5 (S5)=Max4X5+6S5 0X5 S5 因为4X5+6S5随X5单调递增，所以取X5=S5 此时：X5 =S5 F5 (S5)=10S5 48第48页，此课件共90页哦(二)资源分配问题（考虑资源回收的问题）阶段 K=4 F4(S4)=Max4X4+6S4+F5(S5)0X4S4 =Max 4X4+6S4+10S5 =Max 4X4+6S4+8S4-3X4 =Max X4 +14S4 0X4S4因为X4+14S4单凋递增。所以取X4=S4此时 X4 =S4 F4(S4)=15S449第49页，此课件共90页哦(二)资源分配问题（考虑资源回收的问题）阶段 K=3 F3(S3)=Max 4X3+6S3+F4(S4)=Max 4X3+6S3+15S4 =Max 4X3+6S3+15(0.8 S3-0.3X3 =Max 18S3(1/2)X3 0X3 S3 由于18S3(1/2)X3随X3单调递减所以取X3=0此时：X3 =0 F3 (S3)=18S3 50第50页，此课件共90页哦(二)资源分配问题（考虑资源回收的问题）阶段 K=2 F2(S2)=Max 4 X2+6 S2+F3(S3)=Max 4 X2+6 S2+18S3 =Max 4 X2+6 S2+18(0.8 S2-0.3 X2)=Max 20.4 S2-1.4 X2 0X2S2同理取 X2=0此时 X2 =0 F2(S2)=20.4S251第51页，此课件共90页哦(二)资源分配问题（考虑资源回收的问题）阶段 K=1 F1(S1)=Max 4 X1+6 S1+F2(S2)=Max 4 X1+6 S1+20.4 S2 =Max 4 X1+6 S1+20.4(0.8 S1-0.3 X1)=Max 22.32 S1-2.12 X1 0X1S1同理取X1=0此时 X1=0 F1(S1)=22.32 S152第52页，此课件共90页哦(二)资源分配问题（考虑资源回收的问题）将S1=125代入得:F1(S1)=F1(125)=22.32X125=2790(万元)即公司五年内可获得最大收益值为2790万元，最优生产计划方案为表69所示 表69而且5年结束后，尚有32-(1/2)x32=16台设备处于完好状态。如初始状态S1=125加以改变，我们也不需要重新开始计算，借助状态转移函数，我们可以很快得到最佳策略，这也是动态规划问题的一个显著特点。年份项目12345状态S125100806432高负荷X1=0X2=0X3=0X4=64X5=32低负荷125100800053第53页，此课件共90页哦（三）生产与存贮问题例8-8 某造船股份有限责任公司根据合同，从现在起连续4年每年年未要向客户提供型号相同的大型远洋客船，每年的交货数及生产每条船的生产费用见表810所示。该公司的生产能力设计为每年6条船。每个计划年度造船公司固定费用为60万元。若造出的船当年不交货，则每条船积压一年的损失为40万元。假定开始时及第四年年未交货后均无积压船只，问公司应如何安排四年的生产计划，使所支付总费用最经济？年度 项目一二三四生产费用（CK)百万元/条 6.0 6.0 6.3 6.5 需交付船（dK）条/年度 1 3 2 254第54页，此课件共90页哦（三）生产与存贮问题解：按年度划分阶段，四年分为4个阶段，k=1，2，3，4。状态变量SK为第K阶段初存储的船只数量。状态变量SK需要满足以下条件：不能超过本年和以后各年交船数的总和 0SK di为保证按时交船，每年年初的存船数加上本年度的最大可能生产量不得小于本年度的交船数 SK+6dK此外，还有S1=S5=0 决策变量XK为第K阶段生产的船只数,且XK必须满足以下条件：某年末所拥有的存船数，不应超过本年度及以后各年交船数的总和：XK+SK di某年初所拥有的存船数加上当年生产船只数量，不应少于本年度的交船数 XK+SK dK55第55页，此课件共90页哦（三）生产与存贮问题 状态转移函数 S K=S K+X K d K=1,2,3,4即第K年初的存船数加上第K年船只的生产数，再减去第K年交付的船数，就等于第K+1年初的存船数。第K阶段的指标函数VK就是第K年度生产费用与存贮费用两部分之和。0.6+C K X K+0.4S K 当X K 0 V K(S K,X K)K=1,2,3,4 0.4S K 当 X K=0 动态规划的基本方程为：F K(S K)=Min V K(S K,X K)+Fk+1(Sk+1)(K=1,2,3,4)0X K 6 F5(S5)=056第56页，此课件共90页哦（三）生产与存贮问题阶段，K=4，d4=2 S40,1,2 X42,1,0 0.6+6.5X4+0.4S 4 当X 4 0 V4=0.4 S 4 当 X4=0计算结果见表611所示 表611 阶段决策表 阶段k 期初存船（S4）可能的生产量（X4）本期 费用（V 4）期末 存船（S5）以后各期费用F5(S5)总费用V4+F5 最佳生产量（X4）40213.60013.62117.5007.51200.8000.8057第57页，此课件共90页哦（三）生产与存贮问题阶段，K=3，D3=2，故:S30,1,2,3,4 0.6+6.3X3+0.4S3 当X 3 0 V 3=0.4 S3 当 X 3=0计算结果如下表612 表612 阶段决策表 阶段k 期初 存船（S3）可能的生产量（X3）本期 费用（V 3）期末 存船（S4）以后各期费用F4(S4)总费用V3+F4 最佳生产量（X3）30213.2013.626.8 4319.517.527425.820.826.61 1 7.3 0 13.6 20.9 3213.617.521.1319.920.820.758第58页，此课件共90页哦（三）生产与存贮问题 表612(续)阶段决策表 阶段k 期初 存船（S3）可能的生产量（X3）本期 费用（V 3）期末 存船（S4）以后各期费用F4(S4)总费用V3+F4 最佳生产量（X3）32 0 0.8 0 13.6 14.4 0 1 7.7 1 7.5 15.2 2 14 2 0.8 14.83 01.2 17.58.70 18.1 20.88.94 0 1.6 2 0.8 2.4059第59页，此课件共90页哦（三）生产与存贮问题阶段，K=2，D2=3，故S 20,1,2,3,4,5 0.6+6.5X2+0.4S2 当X2 0 V2=0.4 S2 当 X2=0计算结果见表613所示 表613 阶段决策表 阶段k 期初 存船（S2）可能的生产量（X2）本期 费用（V 2）期末 存船（S3）以后各期费用F3(S3)总费用 V2+F3 最佳生产量（X2）20318.6026.645.2 5424.6120.745.3530.6214.445.0636.638.745.360第60页，此课件共90页哦（三）生产与存贮问题 表613(续1)阶段决策表 阶段k期初存船（S2）可能的生产量（X2）本期费用（V2）期末存船（S3）以后各期费用F3(S3)总费用V2+F3最佳生产量（X2）21213026.639.64 or 6319120.739.7425214.439.453138.739.763742.439.4217.4026.6343 or 5213.4120.734.1319.4214.433.8425.438.734.1531.442.433.861第61页，此课件共90页哦 阶段k期初存船（S2）可能的生产量（X2）本期费用（V2）期末存船（S3）以后各期费用F3(S3)总费用V2+F3最佳生产量（X2）230 1.2026.6 27.8017.8120.7 28.5213.8214.428.2319.83 8.728.5425.84 2.428.2401.6120.7 22.3018.2214.422.6214.23 8.722.9320.24 2.422.6502.0214.416.4 0 18.63 8.717.3214.64 2.417.0表613(续2)阶段决策62第62页，此课件共90页哦（三）生产与存贮问题阶段，K=1，D1=1，故S1=0,X11,2,3,4,5,6 V1=0.6+6.0X1计算结果见表614 表614 阶段决策表 阶段k 期初 存船（S1）可能的 生产量（X1）本期 费用（V 1）期末 存船（S2）以后各期费用F2(S2)总费用 V1+F2 最佳生产量（X1）101 6.6 0 45.0 51.6 1212.6139.452.0318.6233.852.4424.6327.852.4530.6422.352.9636.6516.4 53.063第63页，此课件共90页哦（三）生产与存贮问题 由表6-14 知，第1年应该生产1艘船，整个过程的最小费用为F1（0）=51.6百万元。由递推关系可得问题的最佳策略，详见表515 公司最佳生产方案 即第1年船厂应该安排生产1艘船，第2年安排生产5艘船，第3年不安排生产，第4年安排生产2艘船，船厂按此策略安排生产计划才能既满足客户要求又能使支出总费用最小，总费用为5160万元 年度期初存船 (S k）最佳生产量（X k）期末 存船（Sk+1）本期费用VK(SK)最小总费用min(VK+Fk+1)10106.651.6205230.645.032000.814.4402013.613.664第64页，此课件共90页哦（四）背包问题 背包问题又称装载问题，如汽车，火车，轮船，飞机，宇宙飞船等工具的装载问题，还可用于机械加工中零部件的最优加工，下料等问题，具有广泛的实用价值。典型的背包问题是讲有一位登