运筹学第八章动态规划

运筹学第八章动态规划8.1 动态规划的研究对象和特点

动态规划(DynamicProgramming)是一项重要的数量规划方法，由美国数学家贝尔曼(R..Bellman)和徳赖费斯（Dreyfus）等人在二十世纪中叶提出的。1957年，贝尔曼发表了动态规划方面的第一本著作〈〈DynamicProgramming〉〉,标志着运筹学的又一个分支动态规划的建立。动态规划被广泛应用于企业经营、工业工程、资源理论、最佳控制理论和商业决策理论中，并且取得了一定的经济效果。第2页,共90页，2024年2月25日，星期天

一、动态规划的研究对象

动态规划最初是根据多阶段决策问题的特点，由贝尔曼等人提出了解决此类问题的“最优化原理”，并且进一步成功地解决了许多实际问题，才得到大家的充分重视。

1.多阶段决策又称序贯决策问题，通常它可以按时间顺序分成若干个相互联系的阶段，在每一个阶段都需要作出一个决策，每一个阶段作出的决策又称为子策略，每个阶段作出的子策略就组成此多阶段决策问题的策略集。实际工作中我们很难遇到不影响未来决策的当前决策，决策者经常面临的问题通常是要他们作出一系列决策，而这些决策中的每一个均依赖于先前决策的结果，动态规划就可被用来解决很多此类问题。

2.动态规划也可以应用于解决某些与时间无关的问题。例如：把固定数量的几种资源在若干用途上进行配置，这个问题被划分成几个步骤来求解，用这种方法求最后的决策就好象它和时间有关似的，这就进一步扩大了动态规划解决问题的范围。

第3页,共90页，2024年2月25日，星期天二、动态规划的特点

1.动态规划根据问题的具体情况，把整个问题划分成数个阶段，而变成数个部分问题。当这些部分问题由阶段的顺序而贯通，则形成一项多重阶段的程序（过程）。2.动态规划对整个问题的求解，通常是从一个阶段的部分问题开始，逐个逆序向前推求解。对某些问题也可以反过来从最前一个阶段顺序向后推求解。但逆序求解是动态规划的一个显著特点。3.动态规划在每一个阶段求得自以往各阶段至本阶段的最佳解，并将此项最佳解带入次阶段。4.动态规划的目标是全局（系统）的最优化，而不仅是局部（本阶段）的优化。5.动态规划与运筹学的其它分支不同，它没有标准的数学表达式和解题规则，但却是更一般性的解题方法。一个动态规划问题公式的格式在性质上和复杂程度上会与其它动态规划问题大不一样，其差异取决于问题的结构。解题时要有丰富的想象力和创造性技巧。总之，应用动态规划可把一个复杂的难以下手的大问题变成一系列较易于各个解决的小问题，然后可以一个一个求解。所以许多问题用动态规划求解，常较运筹学的其它方法更有效果。第4页,共90页，2024年2月25日，星期天三、动态规划数学模型的类型

动态规划分为离散确定性、离散随机性，连续确定性、连续随机性四种决策类型。本章主要研究离散型动态规划，这也正是动态规划的核心内容和特色所在

第5页,共90页，2024年2月25日，星期天

8.2动态规划的基本概念与

最优化原理

第6页,共90页，2024年2月25日，星期天一、多阶段决策问题（漫游数学家问题）

这是一个典型的多阶段决策问题，通过这个例子，有助于我们更好的理解动态规划的基本概念和基本思路。例8—1有一个智慧比金钱多的应用数学家渴望进行一次旅行。假设他住在城市1，而渴望到城市10（见图8-1表示可能的路线和花费）。这是一个长途的旅行，要求必须进行3次中间停留，中间站可以选择。他希望为这次旅行付出的花费最小，那么他将选择那些城市作为自己的中间站？

第7页,共90页，2024年2月25日，星期天

0站1站2站3站4站.

图8-1

684712441526381097413411369553第8页,共90页，2024年2月25日，星期天分析：他可以采用枚举法，列出所有18种可能的路线来解决这个问题。是否有更好的方法？例如：假设我们在城市5，可通过城市8，也可通过城市9到达城市10，很明显我们会选城市9而不会选城市8。因为（8+3）＜（9+5）,

即（5—9—10）这条路花费较少,由于可按三种不同的路线到达城市5，可以看出枚举法将做不少不必要的工作。这个相当简单的观察为我们提供了一种解题的思路。若我们处在第3站，可通过城市8或9到达城市10可用表8—1说明表8—1

第3站城市Min（f）最佳路径

8

5

8-------10

9

3

9-------10第9页,共90页，2024年2月25日，星期天

现在假定在第2站，并问哪一条路到城市10最近，花费最小。若在城市5，最小花费是11，即Min{9+5,8+3}=11，将选择路径（5—9—10）。同理若在城市6最小花费是12，Min{7+5,12+3}=12，将选择（6—8—10）。城市7最小费用8，Min{----,5+3}=8，将选择路径为（7—9—10），结果列于表8—2

表8—2第2站城市Min（f）最佳路径

5

11

5---9----106

126---8----10

7

87---9----10第10页,共90页，2024年2月25日，星期天

现在假定在第1站，用类似方法可知：由城市2到城市10的最小费用为Min{3+11,---,4+8}=12，路径为（2—5—9—10）。第一站计算结果为表8—3

表8—3

第1站城市Min（f）最佳路径

2

12

2----7---9----103

143-----7---9----10

4

124----5---9----10第11页,共90页，2024年2月25日，星期天最后假定在第0站即城市1也就是起点，那么由城市1到城市10最小花费的路线，应由城市1到第一站的哪个城市呢？由Min{4+12,3+14,11+12}=16可知花费最小的路线为（1—2—7—9—10），第0站计算结果见表8—4表8—4第0站城市Min（f）最佳路径

1

161—2—7—9—10第12页,共90页，2024年2月25日，星期天52638109741341134697125534461812340531112812141216第13页,共90页，2024年2月25日，星期天二、动态规划的基本概念

阶段和阶段变量.

状态和状态变量.

决策和决策变量.

策略和最优策略.

指标函数.

状态转移方程.

第14页,共90页，2024年2月25日，星期天

1.阶段（Stage）和阶段变量

把所给问题的过程，按照时间或空间恰当地划分为若干个相互联系的阶段，以便于求解。描述阶段的变量称为阶段变量，通常用K表示阶段变量。如例8-1可分为4个阶段，当K=2时，表示对第2阶段求解。第15页,共90页，2024年2月25日，星期天2.状态（State）和状态变量

状态表示某阶段的初始位置，它既是该段某支路的始点，同时也是前一阶段某支路的终点。通常一个阶段，包含若干个状态。描述过程状态的变量，称为状态变量，可用一个数、一组数或一个向量表示。用SK表示，如例8—1中，阶段2有三个状态。则状态变量S2可取{２，３，４}，S2=3表示第二阶段在状态3{城市3}处考虑问题．

第16页,共90页，2024年2月25日，星期天3.决策{Deciding}和决策变量

决策就是某阶段状态给定以后，从该状态演变到下一阶段某状态的选择。描述决策的变量，称为决策变量（它是改变状态变量的机会，可能以概率方式出现），常用XK(SK)表示第K阶段当状态为SK时的决策变量，它是状态SK的函数。在实际问题中，决策变量的取值往往限制在某一范围之内，此范围称为允许决策集合，通常用DK(SK)表示第K阶段的关于SK状态的允许决策集合。显然有XK(SK)∈DK(SK)第17页,共90页，2024年2月25日，星期天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表示。使问题达到最优效果的策略，称为最优策略。例8—1中：{X1(1)=2,X2(2)=7,X3(7)=9,X4(9)=10}就是一个策略，且为最优策略。第18页,共90页，2024年2月25日，星期天5．指标函数和最优指标函数值阶段指标函数是用来表示某阶段给定状态和决策取得效应的一种数量指标。它是定义在第K阶段上的一个数量函数。用vK..N表示：

vK..N=vK..N(SK,XK)

过程指标函数（简称指标函数；又称目标函数）是用来衡量所考查过程效应的一种数量指标。它是定义在从第K阶段到终点过程上的一个数量函数。用VK..N表示：

VK..N=VK..N(SK,XK.SK+1,XK+1――――SN+1)

(k=1,2――――N)当初始状态给定时过程的策略就确定了，因而指标也就确定了，所以指标函数又是初始状态和策略的函数即：

VK..N=VK..N(SK，PK..N(SK))

第19页,共90页，2024年2月25日，星期天5．指标函数和最优指标函数值指标函数VK..N的最优值，称为相应的最优指标函数值记为：FK(SK)=optVKN(SK，PK..N(SK))式中opt是optimization(最优化)的缩写，根据问题不同取Max或Min。在不同问题中指标的涵义不同，可以是距离、费用、收益、产品产量、资源消耗等。从例8—1中：VK..N表示第k阶段的点SK到终点城市10的花费。FK(SK)=MinVK,N表示SK到城市10的最小花费。第20页,共90页，2024年2月25日，星期天6.状态转移方程

状态转移方程表示从阶段k到阶段k+1的状态转移规律的表达式。多级决策过程中，如给定了第K阶段的状态变量SK和决策变量XK(SK)，则下一阶段K+1阶段状态变量的值也就确定了。即SK+1=TK(SK,XK(SK))上式又称为状态转移函数。第21页,共90页，2024年2月25日，星期天三、动态规划数学模型的构造条件

1.能够恰当地划分问题的阶段，把问题化为多阶段决策过程；2.正确地选择状态变量动态规划中的状态要能描述受控过程的演变特征：满足无后效性和可知性。

第22页,共90页，2024年2月25日，星期天

无后效性——如果过程某阶段的状态给定，则在这个阶段以后过程的发展不受前面各个阶段的影响，只和当前状态及今后的决策有关，过程前面的状态和决策只能通过形成的当前状态去影响过程未来的发展，即重要的是当前的状态和今后的决策而于过去的状态和决策无关。可知性—各阶段状态变量的值直接或间接均为已知。第23页,共90页，2024年2月25日，星期天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页,共90页，2024年2月25日，星期天

四、最优化原理和基本方程

1.最优化原理最优策略具有这样的性质：无论过去状态和决策如何，对前面决策所形成的某一状态而言，余下的决策序列必须构成最优策略。第25页,共90页，2024年2月25日，星期天2.动态规划的基本方程利用最优化原理，把多阶段决策问题的求解过程分解为一个连续的递推过程，由后向前逐步推算。求解时，各阶段以前的状态和决策，对后部子过程来说，只充当其初始条件，并不影响后面过程的最优策略。据此可得出动态规划的递推关系：为使关系式表达方便,可对问题增加第N+1阶段此时有：

FN+1(SN+1)=ee为一常数FN+1(SN+1)=e又称为动态规划的边界条件。

第26页,共90页，2024年2月25日，星期天2.动态规划的基本方程

对于任何第K阶段（1≤K≤N）当

VK,N=∑vj(Sj,Xj)时则有FK(SK)=opt{vK(SK,XK)+Fk+1(SK+1)}

XK(SK)∈DK(SK)sK∈SK

第27页,共90页，2024年2月25日，星期天2.动态规划的基本方程又当

VK,N=

∏vj(Sj，Xj)时则有

Fn+1(Sn+1)≠0

Fk

(Sk)=opt{Vk(Sk,Xk)Fk+1(Sk+1)}

Xk

(Sk)∈Dk(Sk)Sk∈Sk再有状态转移函数

Sk+1=Tk

(Sk,Xk(Sk))

问题就可以求解啦

第28页,共90页，2024年2月25日，星期天例8—2：求X1、X2、X3在满足约束条件：

X1+X2+X3=CXi≧0(i=1,2,3)之下，使函数F(X1、X2、X3)=X1•X2•X3→MaxK:按变量将问题划分为3个阶段，每个阶段只决定X1、X2、X3

其中一个变量的值。SK:表示第K个阶段初尚未分配出的数值，S1=CXK：表示第K个阶段分配给的数值,0≤XK≤SK状态转移函数：Sk+1=SK—XK(K=1、2、3)各个阶段效益按乘积组合，所以基本方程为：

FK(SK)=max{XKFk+1(Sk+1)}(K=1,2,3)0≤XK≤SKF4(S4)=1第29页,共90页，2024年2月25日，星期天

例8—3某公司有资金1000万元，拟投资项目有3个，已知对第i个项目投资Xi万元，净收益为gi(Xi)，应如何分配资金才能使公司总的净收益最大？

这个问题与时间无明显关系，我们可按项目将问题分为三个阶段，每个阶段只考虑对一个项目的投资额。K=3状态变量SK表示第K个阶段初未分配资金额。决策变量XK表示第K个阶段分配给第K个项目的投资额。状态转移函数为：SK+1=SK-XK

（K=1、2、3）指标函数基本方程为：

FK(SK)=max{gK(XK)+FK+1(SK+1)}(K=1,2,3)0≤XK≤SK

F4(S4)=0第30页,共90页，2024年2月25日，星期天

8.2动态规划的基本概念与最优化原理

根据动态规划的基本思路和最优化原理，一般列出其基本方程即可对实际问题进行求解，但有些问题由于结构的不同，其基本方程可能有特殊性，关键是要灵活地创造性地应用动态规划的最优化原理和思想。第31页,共90页，2024年2月25日，星期天8.3动态规划的求解与应用一、动态规划的解法动态规划的求解有两种基本方法：逆序解法（后向动态规划）、顺序解法（前向动态规划）（一）逆序解法逆序解法的寻优方向与实际决策过程的行进方向相反，它是从最后一个阶段开始逐段向前推进，从而求得全过程的最优策略，这种方法更体现动态规划的本质和最优化原理：不管过去如何，只求未来更优。前面我们建立的动态规划模型均是按逆序方法建立的，它也是求解动态规划问题的主要方法。例8—4用动态规划逆序法求解例例8—2解：基本方程为：

FK(SK)=Max{XKFk+1(Sk+1)}(K=1,2,3)0≤XK≤SKF4(S4)=1状态转移函数为：Sk+1=SK—XK(K=1、2、3)第32页,共90页，2024年2月25日，星期天8.3动态规划的求解与应用第Ⅲ阶段，K=3F3(S3)=Max{X3

·F4(S4)}0≤X3≤S3

=Max{X3

•1}0≤X3≤S3

=S3

X3=S3

第Ⅱ阶段，K=2F2(S2)=Max{X2

•F3(S3)}0≤X2≤S2=Max{X2

•S3}0≤X2≤S2=Max{X2

•(X2-S2)}=Max{(S2/2)2-(X2-S2/2)2}=(S2/2)2X2=S2/2第33页,共90页，2024年2月25日，星期天8.3动态规划的求解与应用第Ⅰ阶段，K=1F1(S1)=Max{X1•F2(S2)}0≤X1≤S1

=Max{X1

•(S2/2)2}=Max{X1

•(S1-X1/2)2}=(S1/3)3X1=S1/3由于初始状态S1=C所以：

S1=CX1*=C/3F1(C)=(C/3)3S2=C-X1*=2C/3X2*=C/3F2(S2)=(C/3)2S3=S2-X2*=C/3X3*=S3=C/3F3(S3)=(C/3)所以最优策略为：X1*=X2*=X3*=C/3最优指标函数的值为：F1(S1)=F1(C)=(C/3)3第34页,共90页，2024年2月25日，星期天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页,共90页，2024年2月25日，星期天8.3动态规划的求解与应用

逆序解法和顺序解法两者的解题方向不同，但结果是一致的。在解动态规划问题时，顺序解法有时比较困难，甚至有些问题根本无法采用顺序解法，而逆序解法在大多数情况下都比较方便。一般来讲，当过程的终点状态给定时，可采用顺序解法，当过程的起点状态和终点状态都给定时，则逆序解法和顺序解法都会得到最优结果，只给定初始状态时则无法采用顺序解法，因大多数问题均只有初始状态，所以常用逆序解法。求解动态规划问题时，除了我们介绍的数学解析方法，对离散型问题可能用表格法更合适，下面我们将结合具体应用问题进行介绍。第36页,共90页，2024年2月25日，星期天二、动态规划的应用

动态规划的应用范围很广，解题的方法也各有不同。下面我们将介绍一些典型应用问题，进一步加深对动态规划的理解和解题技巧的掌握。

（一）资源分配问题（一维资源分配问题）资源分配问题，是指将供应量有限的一种或若干种资源（如原材料、资金、机器、劳力、食品等）分配给若干用户，而使目标函数最优。设有某种原料总量为M，拟用来进行N种生产活动。若分配数量为Xi的原料用于第i种生产活动，其收益为gi(Xi)，问应如何分配才能使N种生产活动的总收益最大？这类问题可写成静态规划问题：

Max[g1(X1)+g2(X2)+…+gn(Xn)]X1+X2+…+Xn=MXi≧0i=1,2,3,…n第37页,共90页，2024年2月25日，星期天（一）资源分配问题（一维资源分配问题）

在用动态规划方法求解此类问题时，一般地将N种活动作为一个互相衔接的整体，由于要确定分给每种活动的资源数，所以通常把资源分配给一个或几个使用者的过程划分为若干个阶段，每个阶段都要确定分配给某一种活动的资源量，并且首先要对N种活动指定分配的阶段序号。由于将阶段联系在一起的是所有生产活动都在争取的资源，因此状态变量就要按照资源分配来确定。把第K个阶段的状态变量SK定义为第K阶段初所拥有的资源量，即将要在第K种活动到第N种活动之间分配的资源量。这样我们在确定第K个阶段的资源分配时就不需要考虑第K个阶段以前的资源分配情况。决策变量XK定义为第K个阶段对资源的分配量，即对第K种活动的资源分配量。

第38页,共90页，2024年2月25日，星期天（一）资源分配问题（一维资源分配问题）状态变量的约束条件是：0≤SK≤M

决策变量的约束条件是：0≤XK≤SK

此时状态转移函数是：SK+1=SK-XK即第K+1阶段初的资源拥有量等于第K阶段初的资源拥有量与分配量之差。显然，它满足无后效性。阶段指标函数为对第K个阶段分配资源XK时的收益：

VK(SK,XK)=gK(XK)

目标函数FK(SK)为从第K个阶段到第N个阶段按最优分配方案分配资源后的最大总收益，则动态规划的基本方程为

FK(SK)=Max{gK(SK)(XK)+FK+1(SK+1)}(K=1,2,3,---,n)0≤XK≤SKFn+1(Sn+1)=0第39页,共90页，2024年2月25日，星期天（一）资源分配问题（一维资源分配问题）例8-6某机械公司购置五台先进设备，需分给所属的甲，乙，丙三个工厂。各工厂获得这些设备后，每年为公司提供的盈利（万元）见表8—5：表8—5单位：万元

设备数工厂

012345甲

03791213乙

0510111111丙046111212第40页,共90页，2024年2月25日，星期天（一）资源分配问题（一维资源分配问题）问如何分配这些设备才能使公司得到的盈利额最大。此问题当设Xi(i=1,2,3)为分配给第i个工厂的设备数时，gi(Xi)为第i个工厂的盈利时，可以写成静态规划问题:

Max[g1(X1)+g2(X2)+g3(X3)]X1+X2+X3=5Xi≧0i=1,2,3

无法用单纯形方法求解，枚举法比较麻烦。故采用动态规划的方法，特别当工厂和设备数量增大时，采用动态规划的方法更方便一些。第41页,共90页，2024年2月25日，星期天（一）资源分配问题（一维资源分配问题）解：将问题按工厂划分为三个阶段，三个工厂的编号分别记为1，2，3。SK表示分配给第K个工厂到第3个工厂的设备台数，XK表示分配给第K个工厂的设备台数：

S1=5SK+1=SK-XK

VK(XK)表示XK台设备分配到第K个工厂得到的盈利值。

FK(SK)表示SK台设备分配到第K个工厂至第三个工厂所得的最大盈利。因此有递推关系：

FK(SK)=Max{VK(XK)+FK+1(SK-XK)}(K=1,2,3)0≤XK≤SK(K=1,2,3)F4(S4)=0第42页,共90页，2024年2月25日，星期天（一）资源分配问题（一维资源分配问题）现从最后一个阶段向前递推求解：阶段ⅢK=3

设把S3台设备（S3=0，1，2，3，4，5）全部分配给工厂3时，则最大盈利值为：F3(S3)=Max[V3(X3)]X3=0,1,2,3,4,5因为只有一个工厂，给不同台数的盈利就是每种情况下的最大盈利。因此最优方案是把全部设备放到工厂3去。数值计算及决策见表8—6

x3s3

V3(x3)+F4(S4)F3(s3)x3*01234500

00104

41204662304611113404611121245046111212125第43页,共90页，2024年2月25日，星期天（一）资源分配问题（一维资源分配问题）

阶段Ⅱ

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)最大决策及计算结果如表6—7：

x2s2

V2(X2)+F3(S2-X2)F2(s2)X2*01234500

0010+45+0

5120+65+410+010230+115+610+411+014240+125+1110+611+411+0161&250+125+1210+1111+611+411+0212第44页,共90页，2024年2月25日，星期天（一）资源分配问题（一维资源分配问题）

阶段Ⅰ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)最大，数值计算见表6—8由表中可知：最优方案有二个：

(1)X1=0X2=2X3=3F1(S1)=21(2)X1=2X2=2X3=1F1(S1)=21如资源是连续的，则解题时首先必须将问题进行离散化处理，如本问题不是5台设备而是50万元人民币，那么我们可以每10万元为单位进行分割，当然也可以1万元为单位分割，但计算工作量会大幅度提高，因此分割单位的选择十分重要

x1s1V1(X1)+F2(S1-X1)F1(s1)X1*01234550+213+167+149+1012+513+0210&2第45页,共90页，2024年2月25日，星期天(二)资源分配问题（考虑资源回收的问题）例8-7．某个公司新购某种机床125台。这种设备5年后将被其它新设备代替，此机床如在高负荷状态下工作年损坏率为1/2，每台年收益为10万元；如在低负荷下工作年损坏率为1/5，每台年收益为6万元。问应如何安排这些机床的生产负荷，才能使5年内所获收益最大？第46页,共90页，2024年2月25日，星期天(二)资源分配问题（考虑资源回收的问题）

解：按年度划分为5个阶段，用K表示阶段序号。状态变量SK

为第K年拥有完好设备的数量，决策变量XK

为第K年中处于高负荷工作的设备数量，决策变量(SK—XK)为第K年中处于低负荷工作的设备数量状态转移函数即第K+1年年初完好的设备台数:SK+1=SK—1/2XK

—1/5(SK—XK)=4/5SK—3/10XK第K阶段允许决策集合为

DK(SK)={XK/0≤XK≤SK}VK(SK,XK)为第K年度的收益则VK=VK(SK,XK)=10XK+6(SK—XK)=6SK+4XK第47页,共90页，2024年2月25日，星期天(二)资源分配问题（考虑资源回收的问题）因此基本方程为:FK(SK)=Max{6SK+4XK+FK+1(SK+1)}0≤XK≤SKK=1,2,3,4,5F6(S6)=0下面求解问题：阶段ⅤK=5F6(S6)=0有：F5(S5)=Max{4X5+6S5}0≤X5≤S5

因为4X5+6S5随X5单调递增，所以取X5=S5

此时：

X5=S5

F5(S5)=10S5

第48页,共90页，2024年2月25日，星期天(二)资源分配问题（考虑资源回收的问题）阶段ⅣK=4F4(S4)=Max{4X4+6S4+F5(S5)}0≤X4≤S4=Max{4X4+6S4+10S5}=Max{4X4+6S4+8S4-3X4}=Max{X4+14S4}0≤X4≤S4因为X4+14S4单凋递增。所以取X4=S4此时

X4=S4

F4(S4)=15S4第49页,共90页，2024年2月25日，星期天(二)资源分配问题（考虑资源回收的问题）阶段ⅢK=3F3(S3)=Max{4X3+6S3+F4(S4)}=Max{4X3+6S3+15S4}=Max{4X3+6S3+15(0.8S3-0.3X3}=Max{18S3

–(1/2)X3}0≤X3≤S3

由于18S3

–(1/2)X3随X3单调递减所以取X3=0此时：

X3=0F3(S3)=18S3

第50页,共90页，2024年2月25日，星期天(二)资源分配问题（考虑资源回收的问题）阶段ⅡK=2F2(S2)=Max{4X2+6S2+F3(S3)}=Max{4X2+6S2+18S3}=Max{4X2+6S2+18(0.8S2-0.3X2)}=Max{20.4S2-1.4X2}0≤X2≤S2同理取X2=0此时

X2=0F2(S2)=20.4S2第51页,共90页，2024年2月25日，星期天(二)资源分配问题（考虑资源回收的问题）阶段ⅠK=1F1(S1)=Max{4X1+6S1+F2(S2)}=Max{4X1+6S1+20.4S2}=Max{4X1+6S1+20.4(0.8S1-0.3X1)}=Max{22.32S1-2.12X1}0≤X1≤S1同理取X1=0此时

X1=0F1(S1)=22.32S1第52页,共90页，2024年2月25日，星期天(二)资源分配问题（考虑资源回收的问题）将S1=125代入得:F1(S1)=F1(125)=22.32X125=2790(万元)

即公司五年内可获得最大收益值为2790万元，最优生产计划方案为表6—9所示表6—9而且5年结束后，尚有32-(1/2)x32=16台设备处于完好状态。如初始状态S1=125加以改变，我们也不需要重新开始计算，借助状态转移函数，我们可以很快得到最佳策略，这也是动态规划问题的一个显著特点。年份项目12345状态S125100806432高负荷X1=0X2=0X3=0X4=64X5=32低负荷1251008000第53页,共90页，2024年2月25日，星期天（三）生产与存贮问题例8-8某造船股份有限责任公司根据合同，从现在起连续4年每年年未要向客户提供型号相同的大型远洋客船，每年的交货数及生产每条船的生产费用见表8—10所示。该公司的生产能力设计为每年6条船。每个计划年度造船公司固定费用为60万元。若造出的船当年不交货，则每条船积压一年的损失为40万元。假定开始时及第四年年未交货后均无积压船只，问公司应如何安排四年的生产计划，使所支付总费用最经济？年度项目一二三四生产费用（CK)百万元/条

6.0

6.06.36.5需交付船（dK）条/年度

1

3

2

2第54页,共90页，2024年2月25日，星期天（三）生产与存贮问题解：按年度划分阶段，四年分为4个阶段，k=1，2，3，4。状态变量SK为第K阶段初存储的船只数量。状态变量SK需要满足以下条件：⑴不能超过本年和以后各年交船数的总和

0≤SK≤Σdi⑵为保证按时交船，每年年初的存船数加上本年度的最大可能生产量不得小于本年度的交船数SK+6≥dK⑶此外，还有S1=S5=0

决策变量XK为第K阶段生产的船只数,且XK必须满足以下条件：⑴某年末所拥有的存船数，不应超过本年度及以后各年交船数的总和：

XK+SK≤Σdi⑵某年初所拥有的存船数加上当年生产船只数量，不应少于本年度的交船数

XK+SK≥dK第55页,共90页，2024年2月25日，星期天（三）生产与存贮问题

状态转移函数

SK=SK+XK

–dK=1,2,3,4即第K年初的存船数加上第K年船只的生产数，再减去第K年交付的船数，就等于第K+1年初的存船数。第K阶段的指标函数VK就是第K年度生产费用与存贮费用两部分之和。

0.6+CKXK+0.4SK

当XK>0VK(SK,XK)K=1,2,3,40.4SK

当XK=0动态规划的基本方程为：

FK(SK)=Min{VK(SK,XK)+Fk+1(Sk+1)}(K=1,2,3,4)0≤XK≤6F5(S5)=0第56页,共90页，2024年2月25日，星期天（三）生产与存贮问题阶段Ⅳ，K=4，d4=2S4∈{0,1,2}X4∈{2,1,0}0.6+6.5X4+0.4S4

当X4>0V4=0.4S4

当X4=0计算结果见表6—11所示表6—11阶段Ⅳ决策表

阶段k

期初存船（S4）可能的生产量（X4）本期费用（V4）期末存船（S5

）以后各期费用F5(S5)

总费用V4+F5

最佳生产量（X4）40213.60013.62117.5007.51200.8000.80第57页,共90页，2024年2月25日，星期天（三）生产与存贮问题阶段Ⅲ，K=3，D3=2，故:S3∈{0,1,2,3,4}0.6+6.3X3+0.4S3

当X3>0V3=0.4S3

当X3=0计算结果如下表6—12

表6—12阶段Ⅲ决策表阶段k

期初存船（S3）可能的生产量（X3）本期费用（V3）期末存船（S4）以后各期费用F4(S4)

总费用V3+F4最佳生产量（X3）30213.2013.626.84319.517.527425.820.826.61

17.3013.620.9

3

213.617.521.1319.920.8

20.7第58页,共90页，2024年2月25日，星期天（三）生产与存贮问题

表6—12(续)阶段Ⅲ决策表阶段k

期初存船（S3）可能的生产量（X3）本期费用（V3）期末存船（S4）以后各期费用F4(S4)

总费用V3+F4最佳生产量（X3）3200.8013.6

14.4017.717.515.221420.8

14.8301.217.58.7018.120.88.9401.620.8

2.40第59页,共90页，2024年2月25日，星期天（三）生产与存贮问题阶段Ⅱ，K=2，D2=3，故S2∈{0,1,2,3,4,5}

0.6+6.5X2+0.4S2

当X2>0V2=0.4S2

当X2=0计算结果见表6—13所示表6—13阶段Ⅱ决策表

阶段k

期初存船（S2）可能的生产量（X2）本期费用（V2）期末存船（S3

）以后各期费用F3(S3)

总费用V2+F3最佳生产量（X2）20

318.6026.645.25424.6120.745.3530.6214.445.0636.638.745.3第60页,共90页，2024年2月25日，星期天（三）生产与存贮问题

表6—13(续1)阶段Ⅱ决策表

阶段k

期初存船（S2）可能的生产量（X2）本期费用（V2）期末存船（S3

）以后各期费用F3(S3)

总费用V2+F3最佳生产量（X2）21213026.639.64or6

319120.739.7425214.439.453138.739.763742.439.42

17.4026.6343or5

213.4120.734.1319.4214.433.8425.438.734.1531.442.433.8第61页,共90页，2024年2月25日，星期天

阶段k

期初存船（S2）可能的生产量（X2）本期费用（V2）期末存船（S3

）以后各期费用F3(S3)

总费用V2+F3最佳生产量（X2）2301.2026.627.8017.8120.728.5213.8214.428.2319.838.728.5425.842.428.2401.6120.722.3018.2214.422.6214.238.722.9320.242.422.65

02.0214.416.4018.638.717.3214.642.417.0表6—13(续2)阶段Ⅱ决策第62页,共90页，2024年2月25日，星期天（三）生产与存贮问题阶段Ⅰ，K=1，D1=1，故S1=0,X1∈{1,2,3,4,5,6}V1=0.6+6.0X1计算结果见表6—14

表6—14阶段Ⅰ决策表阶段k

期初存船（S1）可能的生产量（X1）本期费用（V1）期末存船（S2）以后各期费用F2(S2)

总费用V1+F2最佳生产量（X1）10

16.60

45.0

51.61212.6139.452.0318.6233.852.4424.6327.852.4530.6422.352.9636.6516.453.0第63页,共90页，2024年2月25日，星期天（三）生产与存贮问题

由表6-14知，第1年应该生产1艘船，整个过程的最小费用为F1（0）=51.6百万元。由递推关系可得问题的最佳策略，详见表5—15

公司最佳生产方案

即第1年船厂应该安排生产1艘船，第2年安排生产5艘船，第3年不安排生产，第4年安排生产2艘船，船厂按此策略安排生产计划才能既满足客户要求又能使支出总费用最小，总费用为5160万元

年度期初存船(Sk）最佳生产量（Xk）期末存船（Sk+1）本期费用VK(SK)

最小总费用min(VK+Fk+1)10106.651.6205230.645.032000.814.4402013.613.6第64页,共90页，2024年2月25日，星期天（四）背包问题背包问题又称装载问题，如汽车，火车，轮船，飞机，宇宙飞船等工具的装载问题，还可用于机械加工中零部件的最优加工，下料等问题，具有广泛的实用价值。典型的背包问题是讲有一位登山运动员，它的背包的载重量不能超过a千克，现有n种物品可供选择装入背包，第i种物品的单位重量是ai千克，第i种物品的价值是携带数量Xi的函数Ci(Xi)(i=1,2,---,n)，那么运动员应如何选择各种物品的数量，而使总价值最大？

第65页,共90页，2024年2月25日，星期天（四）背包问题例8-9，某公司有三种货物需要装飞机运输，各种货物的重量和可能获得的收益见表8—16。飞机允许装载能力为6吨，问应如何装载才能使公司获得最大收益？表8—16解：按货物种类划分阶段：K=1表示装载第1种货物；K=2表示装载第2种货物；K=3表示装载第3种货物。状态变量SK表示第K阶段可以利用的装载能力。

S1=6SK={0，1，2，3，4，5，6}K=2，3货物种类（i）货物重量（Wi）吨收益（Vi）(千克)12802313034180第66页,共90页，2024年2月25日，星期天（四）背包问题决策变量XK为第K种货物的装载数量。允许决策集合：XK∈DK(SK)={0,1,2,---,[SK/aK]}K=1,2,3

状态转移函数：SK+1=SK—WKXK阶段指标函数为：VKXK动态规划基本方程：

FK(SK)=Max{VKXK+FK+1(SK+1)}(K=3,2,1)XK∈DK(SK)F4(S4)=0第67页,共90页，2024年2月25日，星期天（四）背包问题阶段ⅢK=3W3=4,V3=180,S3∈{0,1,2….,6}因为X3∈{0,1,…,[S3/4]}={0,1}所以：F3(S3)=Max{180X3+0}X3∈(0,1)S3∈{0,1,2,…,6}计算结果如下表8—17阶段

X3S3180X3F3(S3)

X3*S401300

00010

00120

00230

00340180+01801050180+01801160180+018012第68页,共