当前位置:首页 >> 管理学 >>

运筹学第八章 动态规划


第八章 动 态 规 划

8.1 8.2 8.3 8.4

动态规划的研究对象和特点 动态规划的基本概念与最优化原理 动态规划的求解与应用 随机动态规划

Page

1

8.1

动态规划的研究对象和特点

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

Page

2

一、动态规划的研究对象

?

?

?

动态规划最初是根据多阶段决策问题的特点,由贝尔曼等人 提出了解决此类问题的“最优化原理”,并且进一步成功地解决 了许多实际问题,才得到大家的充分重视。 1. 多阶段决策又称序贯决策问题,通常它可以按时间顺序分成若 干个相互联系的阶段,在每一个阶段都需要作出一个决策,每一 个阶段作出的决策又称为子策略,每个阶段作出的子策略就组成 此多阶段决策问题的策略集。实际工作中我们很难遇到不影响未 来决策的当前决策,决策者经常面临的问题通常是要他们作出一 系列决策,而这些决策中的每一个均依赖于先前决策的结果,动 态规划就可被用来解决很多此类问题。 2.动态规划也可以应用于解决某些与时间无关的问题。例如:把 固定数量的几种资源在若干用途上进行配置,这个问题被划分成 几个步骤来求解,用这种方法求最后的决策就好象它和时间有关 似的,这就进一步扩大了动态规划解决问题的范围。

Page

3

划的特点
? 1.动态规划根据问题的具体情况,把整个问题划分成数个阶段,而

?

? ? ?

?

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

三、动态规划数学模型的类型

?

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

Page

5

一、 多阶段决策问题(漫游数 学家问题)
?

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

? 例8—1

?

Page

7

2

3 4 4

5

9 8
8

4
1

3

3

4 6 1

7 6 12
5
7
3站

5
10

11
4
0站 图 1站 8-1

9

3

6

2站

4站 .

Page

8

他可以采用枚举法,列出所有18种可能的路 线来解决这个问题。是否有更好的方法? ? 例如:假设我们在城市5,可通过城市8,也可通 过城市9到达城市10,很明显我们会选城市9而不 会选城市8。因为(8+3)<(9+5), ? 即(5—9—10)这条路花费较少,由于可按三种不 同的路线到达城市5,可以看出枚举法将做不少不 必要的工作。这个相当简单的观察为我们提供了 一种解题的思路。 ? 若我们处在第3站,可通过城市8或9到达城市10 可用表8 — 1说明 城 市 Min( f ) 最佳路径 表8—1 第 3站
? 分析:
? ?

8 9

5 3

8-------10 9-------10
Page 9

? 现在假定在第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 第2站 城 市 Min( f )最佳路径 ? 5 11 5---9----10 ? 表8—2 6 12 6---8----10 7 8 7---9----10
Page 10

?

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

?

?

3 4

14 12

3-----7---9----10 4----5---9----10

Page

11

? 最后假定在第0站即城市1也就是起点,那么由城市 1到城市10最小花费的路线,应由城市1到第一站的 哪个城市呢?

由Min{4+12, 3+14, 11+12}=16 ? 可知花费最小的路线为(1—2—7—9—10),第0 站计算结果见表8—4 城 市 Min( f ) 最佳路径 ? 第0站 表8—4
?
1 16 1—2—7—9—10

Page

12

12
2 16 1

11

3
4
4

5
12 7

9
8

5

4
3 11

14 3

8
3 9

5 3

0 10

4

6

6 8

12 5

12 1

4
1

6
2

7
3 4
Page 13

?阶段和阶段变量. ?状态和状态变量. ?决策和决策变量. ?策略和最优策略. ?指标函数 .

?状态转移方程 .

1.

阶段(Stage)和阶段变量

把所给问题的过程,按照时间或空间恰 当地划分为若干个相互联系的阶段,以便于 求解。描述阶段的变量称为阶段变量,通常 用K表示阶段变量。如例8-1可分为4个阶段, 当K=2时,表示对第2阶段求解。

Page

15

2. 状态(State)和状态变量
状态表示某阶段的初始位置,它既是该段某支路的 始点,同时也是前一阶段某支路的终点。通常一个阶段, 包含若干个状态。

描述过程状态的变量,称为状态变量,可用一个数、
一组数或一个向量表示。用SK 表示,如例8—1中,阶段2 有三个状态。则状态变量S2可取{2,3,4},S2=3表示

第二阶段在状态3{城市3}处考虑问题.

Page

16

3. 决策

{Deciding}

和决策变量

决策就是某阶段状态给定以后,从该状态演变 到下一阶段某状态的选择。描述决策的变量,称为 决策变量(它是改变状态变量的机会,可能以概率 方式出现),常用XK(SK)表示第K阶段当状态为SK时 的决策变量,它是状态SK的函数。在实际问题中, 决策变量的取值往往限制在某一范围之内,此范围 称为允许决策集合,通常用DK(SK)表示第K阶段的 关于SK状态的允许决策集合。显然有 XK(SK)∈DK(SK)
Page 17

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}就是一个 策略,且为最优策略。
?
Page 18

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+1――――SN+1) (k=1,2――――N) ? 当初始状态给定时过程的策略就确定了,因而指标也就确定了, 所以指标函数又是初始状态和策略的函数即: ? V K..N = V K..N (SK,P K..N(SK))
? ?

Page

19

5.指标函数和最优指标函数值
?
? ? ? ? ?

指标函数VK..N的最优值,称为相应的最优指标函数值 记为: FK(SK)=opt VK N(SK,PK..N(SK)) 式中opt是optimization(最优化)的缩写,根据问题不 同取Max或Min。 在不同问题中指标的涵义不同,可以是距离、费用、 收益、产品产量、资源消耗等。 从例8—1中: VK..N表示第k阶段的点SK到终点城市10 的花费。 FK(SK)= MinVK,N表示SK到城市10的最小花费。

Page

20

6. 状态转移方程
状态转移方程表示从阶段 k到阶段k+1的状态转 移规律的表达式。 多级决策过程中,如给定了第K阶段的状态变量 SK和决策变量XK(SK),则下一阶段K+1阶段状态变量 的值也就确定了。 ? 即 SK+1 = TK(SK, XK(SK)) ? 上式又称为状态转移函数。
?

Page

21

三、动态规划数学模型的构造条件

1.能够恰当地划分问题的阶段,把问题化为多阶段 决策过程; ? 2.正确地选择状态变量
? 动态规划中的状态要能描述受控过程的演变特征:

满足无后效性和可知性。

Page

22

? 无后效性——如果过程某阶段的状态给定,则在这

个阶段以后过程的发展不受前面各个阶段的影响, 只和当前状态及今后的决策有关,过程前面的状态 和决策只能通过形成的当前状态去影响过程未来的 发展,即重要的是当前的状态和今后的决策而于过 去的状态和决策无关。
? 可知性—各阶段状态变量的值直接或间接均为已知。

Page

23

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)] 一般是求和或求积的关系。
Page 24

本方程
1.最优化原理

最优策略具有这样的性质:无论过去状态和决 策如何,对前面决策所形成的某一状态而言,余下 的决策序列必须构成最优策略。
示意图解释:

M A

B

Page

25

2.动态规划的基本方程

利用最优化原理,把多阶段决策问题的求解过程分解 为一个连续的递推过程,由后向前逐步推算。求解时,各 阶段以前的状态和决策,对后部子过程来说,只充当其初 始条件, 并不影响后面过程的最优策略。据此可得出动 态规划的递推关系: ? 为使关系式表达方便,可对问题增加第N+1阶段此时有: ? FN+1(SN+1)=e e为一常数 ? FN+1(SN+1)=e又称为动态规划的边界条件。
?

?
Page 26

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

Page

27

2.动态规划的基本方程

又当 则有

VK,N = ∏v j ( 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))
问题就可以求解啦

Page

28

例 8—X 2+X :求 X 、X2、X3在满足约 ? + X =C 1 ? X ≧0 (i=1,2,3) 束条件:
1 2 3

i

? 之下,使函数F(X1、X2、X3) = X1?X2?X3 → Max ? K:按变量将问题划分为3 个阶段,每个阶段只决定X1、X2、

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

Page

29

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

? 这个问题与时间无明显关系,我们可按项目将问题分

? ? ? ?

为三个阶段,每个阶段只考虑对一个项目的投资额。 K=3 状态变量SK表示第K个阶段初未分配资金额。 决策变量XK表示第 K个阶段分配给第K个项目的投资额。 V ? ? g (X ) 状态转移函数为:SK+1 = SK - XK ( K =1、2、3) 指标函数
3 k, 3 i i i ?k

? 基本方程为: ? FK (SK )=max {g K (XK )+ FK+1(SK+1)} ? 0≤XK ≤SK ? F4 (S4) = 0

( K=1,2,3 )

Page

30

?

根据动态规划的基本思路和最优化原理, 一般列出其基本方程即可对实际问题进行求 解,但有些问题由于结构的不同,其基本方 程可能有特殊性,关键是要灵活地创造性地 应用动态规划的最优化原理和思想。

Page

31

8.3 动态规划的求解与应用
? 一、动态规划的解法

动态规划的求解有两种基本方法:逆序解法(后向动 态规划)、顺序解法(前向动态规划) ? (一)逆序解法 ? 逆序解法的寻优方向与实际决策过程的行进方向相反, 它是从最后一个阶段开始逐段向前推进,从而求得全过程 的最优策略,这种方法更体现动态规划的本质和最优化原 理:不管过去如何,只求未来更优。 ? 前面我们建立的动态规划模型均是按逆序方法建立的,它 也是求解动态规划问题的主要方法。
?
? 例8—4 用动态规划逆序法求解例例8—2 ? 解:基本方程为: ? FK (SK)=Max {XK Fk+1 (Sk+1)} (K=1,2,3) ? 0≤XK≤SK ? F4 (S4) = 1 ? 状态转移函数为:Sk+1= SK—XK (K=1、2、3)
Page 32

8.3 动态规划的求解与应用
? 第Ⅲ阶段,K=3 ? F3 (S3 ) = Max {X3 ·F4(S4 )} ? 0≤X3 ≤S3 ? = Max{ X3 ?1} ? 0≤X3 ≤S3 ? = S3 ? X3 = S3 ? 第Ⅱ阶段,K=2 ? F2 (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) 2 ? X2= S2/2
Page 33

8.3 动态规划的求解与应用
? ? ? ? ? ? ? ? ? ? ? ? ?

第Ⅰ阶段,K=1 F1 (S1 )= Max {X1 ? F2 (S2)} 0≤X1 ≤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)3
Page 34

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)} F0 (S1) = 0 式中FK (SK+1)指第K阶段状态为SK+1 时从始点到第K阶段的最优指标函数值;VK (SK+1, XK)表示第K 阶段末状态为SK+1时,决策变量为XK时本阶段的效益值.
Page 35

XK (SK+1)∈DK (SK+1)

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

二、动态规划的应用
?
? ? ? ? ? ? ?

动态规划的应用范围很广,解题的方法也各有不同。下面我 们将介绍一些典型应用问题,进一步加深对动态规划的理解和 解题技巧的掌握。 (一)资源分配问题(一维资源分配问题) 资源分配问题,是指将供应量有限的一种或若干种资源 (如原材料、资金、机器、劳力、食品等)分配给若干用户, 而使目标函数最优。 设有某种原料总量为M,拟用来进行N种生产活动。若分配 数量为Xi的原料用于第i种生产活动,其收益为gi (Xi),问应如 何分配才能使N种生产活动的总收益最大? 这类问题可写成静态规划问题: Max [ g1(X1) +g2(X2)+ … +g n( X n ) ] X1+X2+…+Xn= M Xi≧0 i=1,2,3, … n
Page 37

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

(一)资源分配问题(一维资源分配问题)
? 状态变量的约束条件是: 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 {g K (SK) (XK)+ FK +1(SK+1)} (K=1,2,3,---,n) 0≤XK≤SK Fn+1(Sn+1) = 0
Page 39

(一)资源分配问题(一维资源分配问题)
? 例8-6 某机械公司购置五台先进设备,需分给所属的

甲,乙,丙三个工厂。各工厂获得这些设备后,每年 为公司提供的盈利(万元)见表8—5:
? 表8 —5 设备数
0 1 2 3 4 5

单位:

万元
工厂
? 甲 ?

0 0 0

3 5 4

7 10 6

9 11 11

12 11 12

13 11 12

乙 丙

Page

40

(一)资源分配问题(一维资源分配问题)
?

? ? ? ? ?

问如何分配这些设备才能使公司得到的盈利额最大。 此问题当设Xi (i=1,2,3)为分配给第i个工厂的设备数时, gi(Xi) 为第i个工厂的盈利时,可以写成静态规划问题: Max[g1(X1)+g2(X2)+g3(X3)] X1+X2+X3=5 Xi ≧0 i=1,2,3 无法用单纯形方法求解,枚举法比较麻烦。 故采用动态规划的方法,特别当工厂和设备数量增大 时,采用动态规划的方法更方便一些。

Page

41

(一)资源分配问题(一维资源分配问题)
? 解:将问题按工厂划分为三个阶段,三个工厂的编号分别
? ? ? ?

? ? ? ?

记为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) 0≤XK≤SK (K=1,2,3) F4 (S4) = 0
Page 42

(一)资源分配问题(一维资源分配问题)
? 现从最后一个阶段向前递推求解: ? 阶段Ⅲ 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 * x V (x ) +F (S ) F (s ) x 4 4 3 3 3 3 3 3 ? 0 1 2 3 4 5 ?s3
?0 ?1 ?2 ?3 ? 4 ? 5
Page

0 0 0 0 0 0
43

0 4 4 4 4 4 6 6 6 6 11 11 11 12 12 12 4 6 11 12 12

0 1 2 3 4 5

(一)资源分配问题(一维资源分配问题)
?

阶段Ⅱ K=2 ? 设把S2台(S2=0,1,2,3,4,5)设备全部分给工厂3、 工厂2时,则最大盈利值为: F2 (S2)=Max [V2 (X2)+ F3 (S2- X2)] ?x X2= 0,1,2,3,4,5 V2 (X2)+ F3 (S2- X2) F2 (s2) X2* 2 s ? 选择 F2 6—7: 0 X2数值使 1 3 4 5 2 2 (S2)最大决策及计算结果如表
? 0

0 0+4 0+6 0+11 0+12 0+12
Page 44

0 5+0 5+4 5+6 5+11 5+12 10+0 10+4 10+6 10+11 11+0 11+4 11+6 11+0 11+4 11+0 5 10 14 16 21

0 1 2 2 1&2 2

1 2 3 4 5

(一)资源分配问题(一维资源分配问题)
?

? ? ? ?
s1
5

阶段Ⅰ 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
x1
0 0+21 1 3+16 V1 (X1)+ F2 (S1 - X1) 2 7+14 3 9+10 4 12+5 5 13+0 21 0&2

F1 (s1) X1*

? 由表中可知:最优方案有二个: ? (1) X1=0 X2=2 X3=3 F1(S1)=21 ? (2) X1=2 X2=2 X3=1 F1 (S1)=21 ? 如资源是连续的,则解题时首先必须将问题进行离散化处理,如本问题不是5台设备

而是50万元人民币,那么我们可以每10万元为单位进行分割,当然也可以1万元为单 位分割,但计算工作量会大幅度提高,因此分割单位的选择十分重要

?

Page

45

(二)资源分配问题(考虑资源回收的问题)
? 例8-7.某个公司新购某种机床125台。这种

设备5年后将被其它新设备代替,此机床如 在高负荷状态下工作年损坏率为1/2,每台 年收益为10万元;如在低负荷下工作年损坏 率为1/5,每台年收益为6万元。问应如何安 排这些机床的生产负荷,才能使5年内所获 收益最大?

Page

46

(二)资源分配问题(考虑资源回收的问题)
?

? ? ? ? ? ? ?

解:按年度划分为5个阶段,用K表示阶段序号。状态变量 SK 为第K年拥有完好设备的数量,决策变量XK 为第K年中 处于高负荷工作的设备数量,决策变量(SK—XK )为第K年 中处于低负荷工作的设备数量 状态转移函数即第K+1年年初完好的设备台数: SK+1 = SK—1/2 XK —1/5(SK—XK) = 4/5 SK—3/10 XK 第K阶段允许决策集合为 DK (SK)={ XK / 0≤XK≤SK } VK (SK, XK)为第K年度的收益则 VK = VK (SK, XK)=10 XK +6(SK—XK)=6SK +4XK
Page 47

(二)资源分配问题(考虑资源回收的问题)
? ? ? ? ? ? ? ? ? ? ? ?

因此基本方程为: FK (SK)=Max {6SK +4XK + FK+1 (SK+1)} 0≤XK≤SK K=1,2,3,4,5 F6 (S6 )=0 下面求解问题: 阶段Ⅴ K = 5 F6 (S6 )=0 有: F5 (S5 )= Max{4X5 +6S5 } 0≤X5 ≤S5 因为4X5 +6S5随X5单调递增,所以取X5 = S5 此时: X5 = S5 F5 (S5 ) = 10S5
Page 48

(二)资源分配问题(考虑资源回 收的问题)
? 阶段Ⅳ K= 4 F4 (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
Page 49

(二)资源分配问题(考虑资源回 收的问题)
? 阶段Ⅲ 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 } ? 0≤X3 ≤S3 ? 由于18S3 –(1/2) X3随X3单调递减所以取X3 =0 ? 此时: ? X3 = 0 ? F3 (S3 ) = 18S3
Page 50

(二)资源分配问题(考虑资源回 收的问题)
? 阶段Ⅱ 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} ? 0≤X2≤S2 ? 同理取 X2=0 ? 此时 ? X2 = 0 ? F2 (S2) = 20 .4S2
Page 51

(二)资源分配问题(考虑资源回 收的问题)
? 阶段Ⅰ 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} 0≤X1≤S1 同理取X1=0 此时 X1 = 0 F1 (S1) = 22.32 S1
Page 52

虑资源回收的问题)
? 将S1 =125代入得:

F1 (S1)= F1 (125) =22.32X125=2790(万元) ? 即公司五年内可获得最大收益值为2790万元,最优生产 计划方案为表6—9所示 表6 —9 1 年份 2 3 4 5
项目 状态S 高负荷 低负荷 125 100 80 64 32

X1=0
125

X2=0
100

X3=0
80

X4=64
0

X5=32
0

? 而且5年结束后,尚有32-(1/2)x32=16台设备处于完好状态。 ? 如初始状态S1= 125加以改变,我们也不需要重新开始计算,

借助状态转移函数,我们可以很快得到最佳策略,这也是动 态规划问题的一个显著特点。
Page 53

(三)生产与存贮问题
? 例8-8 某造船股份有限责任公司根据合同,从现在起连续4年每

年年未要向客户提供型号相同的大型远洋客船,每年的交货数 及生产每条船的生产费用见表8—10所示。
年度 一 项目 二 三 四

生产费用(CK)百万元/条
需交付船(dK)条/年度

6.0
1

6.0
3

6.3
2

6.5
2

?

该公司的生产能力设计为每年6条船。每个计划年度造船公 司固定费用为60万元。若造出的船当年不交货,则每条船积压 一年的损失为40万元。假定开始时及第四年年未交货后均无积 压船只,问公司应如何安排四年的生产计划,使所支付总费用 最经济?

Page

54

(三)生产与存贮问题
? 解:按年度划分阶段,四年分为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
Page 55

(三)生产与存贮问题
? 状态转移函数 ? 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) 0≤X K ≤6 F5 (S5 ) = 0

Page

56

(三)生产与存贮问题
? 阶段Ⅳ,K=4,d4=2

S4∈{0,1,2} X4∈{2,1,0} ? 0.6 + 6.5X4+ 0.4S 4 当X 4 >0 ? V4 = ? 0.4 S 4 当 X4= 0 ? 计算结果见表6—11所示 阶段k 期初 可能的 本期 期末 以后各 总费用 ? 表6—11 阶段 Ⅳ 决策表 期费用 V +F 生产量
?
存船 (S4)
0

费用 存船 (X4) ( V ) (S ) F (S ) 5 5 4 5
2 13.6 0 0

4

5

最佳 生产量 (X4)
2

4

13 .6

1
2

1
0

7.5
0.8

0
0

0
0

7.5
0.8

1
0

Page

57

(三)生产与存贮问题
? 阶段Ⅲ,K=3,D3=2,故: S3∈{0,1,2,3,4}
? ?

0.6 + 6.3X3+ 0.4S3 V3=

当X 3 >0

?

0.4 S3 ? 计算结果如下表6—12 阶段k 期初 可能的 本期 期末 ? 表6存船 —12 生产量 阶段 费用Ⅲ决策表 存船
(S3)
3 0

当 X 3= 0
以后各 总费用 最佳 期费用 V3+F4 生产量 (X3) F4(S4)
13.6 7.5 0.8 13.6 7.5 0.8 26.8 27 26.6 20.9 21.1 20.7 3 4

(X3) ( V ) (S ) 3 4
2 3 4 1 13.2 19.5 25.8 7.3 13.6 19.9 0 1 2 0 1 2

1

2 3

Page

58

(三)生产与存贮问题
?
?
阶段k

表6—12(续)

阶段Ⅲ决策表
以后各 总费用 最佳 期费用 V3+F4 生产量 (X3) F4(S4)
13.6 7.5 0.8 7.5 0.8 14.4 15.2 14.8 8.7 8.9 0 0

期初 可能的 本期 期末 生产量 存船 费用 存船 (S3) (X3) ( V 3) (S4)
2 0 1 2 3 0 1 0.8 7.7 14 1.2 8.1 0 1 2 1 2

3

4

0

1.6

2

0.8

2.4

0

Page

59

(三)生产与存贮问题
? 阶段Ⅱ,K=2,D2=3,故S 2∈{0,1,2,3,4,5}

? ? ? ?

0.6 + 6.5X2+ 0.4S2 当X2 >0 V2= 当 X2= 0

0.4 S2 ? 计算结果见表6—13所示 阶段 k6— 期初 可能的阶段 本期 期末 ? 表 13 Ⅱ决策表
存船 (S2)
2 0 3 18.6 0

以后各 总费用 最佳 期费用 V2+F3 生产量 生产量 费用 存船 (X2) ( V ) (S ) F (S ) (X2) 3 3 2 3
26.6 45.2

4
5 6
Page 60

24.6
30.6 36.6

1
2 3

20.7
14.4 8.7

45.3
45.0 45.3

5

(三)生产与存贮问题
?

表6—13 (续1)
期初 存船 (S2) 可能的 生产量 (X2)

阶段Ⅱ决策表
本期 费用 ( V 2) 期末 存船 (S 3 ) 以后各 期费用 F3 (S3) 总费用 V2+F3 最佳生 产量 (X2)

阶段k

2

1

2 3 4 5 6

13 19 25 31 37 7.4 13.4 19.4

0 1 2 3 4 0 1 2

26.6 20.7 14.4 8.7 2.4 26.6 20.7 14.4

39.6 39.7 39.4 39.7 39.4 34 34.1 33.8

4 or 6

2

1 2 3

3 or 5

4
5

25.4
31.4

3
4

8.7
2.4

34.1
33.8

Page

61

表6—13 (续2)
阶段k 期初 存船 (S2) 可能的 生产量 (X2) 本期 费用 ( V 2)

阶段Ⅱ决策
期末 存船 (S3 ) 以后各 期费用 F3 (S3) 总费用 V2+F3 最佳生 产量 (X2)

2

3

0 1 2 3 4

1.2 7.8 13.8 19.8 25.8 1.6 8.2 14.2 20.2

0 1 2 3 4 1 2 3 4

26.6 20.7 14.4 8.7 2.4 20.7 14.4 8.7 2.4

27.8 28.5 28.2 28.5 28.2 22.3 22.6 22.9 22.6

0

4

0 1 2 3

0

5

0
1 2

2.0
8.6 14.6

2
3 4

14.4
8.7 2.4

16.4
17.3 17.0

0

Page

62

(三)生产与存贮问题
? 阶段Ⅰ,K=1,D1=1,故S1 =0, X1∈{1,2,3,4,5,6} ? V1=0.6+6.0X1 ? 计算结果见表6—14

? 表6—14
阶段k 期初 存船 (S1)
0

阶段Ⅰ决策表
可能的 本期 期末 生产量 费用 存船 (X1) ( V ) (S ) 1 2
1
2 3 4 5 6

以后各 总费用 最佳 期费用 V1+F2 生产量 (X1) F2(S2)
45.0
39.4 33.8 27.8 22.3 16.4

1

6.6
12.6 18.6 24.6 30.6 36.6

0
1 2 3 4 5

51.6
52.0 52.4 52.4 52.9 53.0

1

Page

63

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

公司最佳生产方案

年度
1 2 3 4
?

期初存船 (S k)
0 0 2 0

最佳生产量 (X k)
1 5 0 2

期末 存船 本期费用 最小总费用 min(VK+Fk+1 ) VK (SK) (Sk+1)
0 2 0 0 6.6 30.6 0.8 13.6 51.6 45.0 14.4 13 .6

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

Page

64

(四)背包问题
?

背包问题又称装载问题,如汽车,火车,轮船,飞机, 宇宙飞船等工具的装载问题,还可用于机械加工中零部件 的最优加工,下料等问题,具有广泛的实用价值。 典型的背包问题是讲有一位登山运动员,它的背包的 载重量不能超过a千克,现有n种物品可供选择装入背包, 第i种物品的单位重量是ai千克,第i种物品的价值是携带 数量Xi的函数Ci(Xi) (i=1,2,---,n),那么运动员应如何 选择各种物品的数量,而使总价值最大?

?

?
Page 65

(四)背包问题
? 例8-9,某公司有三种货物需要装飞机运输,各种货物的重

量和可能获得的收益见表8—16。飞机允许装载能力为6吨, 问应如何装载才能使公司获得最大收益? ? 表8—16
货物种类(i) 货物重量(W i)吨 收益(Vi)(千克)

1 2
3

2 3
4

80 130
180

? 解:按货物种类划分阶段:K=1表示装载第1种货物;

K=2表示装载第2种货物;K=3表示装载第3种货物。 ? 状态变量SK表示第K阶段可以利用的装载能力。 ? S1=6 SK={0,1,2,3,4,5,6} K=2,3
Page 66

(四)背包问题
? 决策变量XK为第K种货物的装载数量。
? 允许决策集合:XK ∈DK (SK ) ={0,1,2,---,[ SK / a K ]} ?

K=1, 2, 3

状态转移函数:SK+1=SK—WKXK

? 阶段指标函数为:VK XK
? 动态规划基本方程:

?
? ?

FK (SK)= Max {VKXK + FK+1(SK+1)}
XK∈DK (SK ) F4(S4) = 0

( K=3,2,1 )

Page

67

(四)背包问题
? 阶段Ⅲ K=3

W3=4, V3=180, S3∈{0,1,2…., 6} ? 因为X3∈{0,1,…, [S3/4]}={0,1} 所以:F3 (S3)=Max{180X3+0} ? X ∈(0,1) S3∈{0,1,2,…, 6} * 阶段 X33 180X3 F3 (S3) X3 ? 计算结果如下表 8— S3 0 17 1
3 0 0 0 0

S4
0

1
2 3 4 5 6

0
0 0 0 0 0 180+0 180+0 180+0

0
0 0 180 180 180

0
0 0 1 1 1

1
2 3 0 1 2

Page

68

(四)背包问题
阶段Ⅱ K=2 W2=3, V2=130, S2∈{0,1,2,3,4,5,6} ? 因为: X2∈{0,1,…, [S2/3]}= {0,1,2} S3=S2—3X2 ? 所以: F2 (S2)= Max{130X2+F3 (S3)} = Max {130X2+F3 (S23X )} 2 阶段 X2 130X2+F3 (S3) F2 (S2) X2* S3 ? 计算结果如下表 8— S2 0 18 1 2
?
?

2

0

0

0

0

0

1
2 3 4 5 6

0
0 0 0+180 0+180 0+180 130 +0 130 +0 130 +0 130 +0 260+0

0
0 130 180 180 260

0
0 1 0 0 2

1
2 0 4 5 0

Page

69

(四)背包问题
? 阶段Ⅰ K=1 W1=2, V1=80, S1=6 ? 因为: X1∈{0,1,…, [6/2]}={0,1,2,3} S2=S1-2X1 ? 所以: F1 (S1)=Max{80X1+F2 (S2)} =Max {80X1+F2 (S1-2X1)} ? X1∈{0,1,2,3} S1=6 计算结果见表8—19

阶段

X2 S2
0 0+260 6

80X1+F2 (S2)
1 2 3 240+0 80+180 160+0

F1 (S1)
260

X1*
0 &1

S2
6&4

1

? 即最优方案有二个为: ? (1) X1 =0 X2=2 X3 =0 F1 (S1 )=260(千元) ? (2) X1 =1 X2 =0 X3 =1 F1 (S1 )=260(千元) ? 公司可获得的最大收益为260万元,此时飞机装载

第2种货物2件或装载第1种货物和第3种货物各1件。 ? 本问题只有重量一个约束称为一维背包问题,当 再加上其它约束条件则变成多维背包问题,其解题方 法和一维背包问题类似,只是状态变量是多维的.
Page 70

(五)货郎担问题
货郎担问题的一般提法是有一个货郎从某城镇出发, 经过若干个城镇一次,且仅一次最后仍回到原出发的城镇, 问应如何选择行走路线可使总行程最短,这是运筹学中的 一个著名问题。 ? 设V1,V2,……VN是已知的N个城镇,城镇Vi到城镇Vj的距 离为Dij,现求从城镇V1出发,经各城镇一次且仅一次最后 返回城镇V1的最短路程。如N比较大时,用枚举法显然是不 合适的。 ? 虽然货郎担问题也是求最短路,但与数学家漫游世界 问题以及其它最短路问题均有很大的不同。建立动态规划 模型时,如按城镇将问题划分为N个阶段,则状态变量不 好选择,不易满足动态规划状态无后效性的特征。
?
Page 71

(五)货郎担问题
? 我们按下面的方法建立动态规划模型。
? 设S表示从V1到Vi中间所有可能经过的城市集合,S实际上

是包含除V1到Vi两个点之外其它各点的集合,但S中点的个 数要随阶段数改变。 ? 状态变量(i,S)表示:从V1 点出发,经过S集合中所有 点一次最后到达Vi。 ? 决策变量PK(i,S)表示:从V1经K个中间城镇的S集合到 Vi城镇的最短路线上邻接Vi的前一个城镇。 ? 最优指标函数FK(i ,S)为从V1出发经由K 个城镇的S集合 到Vi城镇的最短距离。
Page 72

(五)货郎担问题
? 则动态规划的顺序递推关系为:

?
? ? ?

FK ( i, S )=Min{FK-1(j,S/{j})+Dji} j∈S F0 ( i, ?)=d1i ? 为空集 (K=1,2,……,n-1, i=2,3,……,N)

Page

73

(五)货郎担问题
? 例8-10

有一位推销保险的先生,他的业务范围涉及中国大 陆4个城市,城市间的距离见表8—20 ,如他从城市1出发, 经过每个城市一次且仅一次,最后又返回城市1,那么他应 如何安排行进路线,使总的行程距离最小? ? 表8—20 城市之间距离
城市Vi 城市Vi 1 2 3 4

1 2 3 4

0 8 5 6

6 0 8 5

7 9 0 5

9 7 8 0

Page

74

(五)货郎担问题
? 解:动态规划基本方程为 ? FK ( i, S )=Min{FK-1(j,S/{j})+Dji}

j∈S F0 ( i, ?)=d1i ? ? 为空集 (K=1,2,3 i=2,3,4) ? F0(2,?)=d12=6 F0 (3, ?)=d13=7 F0 (4, ?)=d14 =9
? ?
?城市V i

城市Vi 表8—20 1 2 3

1

2 城市之间距离

3

4

0 8 5

6 0 8

7 9 0

9 7 8

?

4
Page 75

6

5

5

0

(五)货郎担问题
? 阶段Ⅰ K=1时,表示从城市V1出发,中间经过1个城市

到达城市Vi的最短距离为: ? F1 (2,{3})=F0 (3, ?)+ d32=7+8=15 ?)+d42=9+5=14 ? F1 (3,{2})=F0 (2, ?)+d23=6+9=15 ?)+d43=9+5=14 ? F1 (4,{2})=F0 (2, ?)+d24=6+7=13 城市Vi 1 2 ?)+d =7+8=15 城市V 34
i

F1 (2,{4})=F0 (4, F1 (3,{4})= F0 (4,

F1 (4,{3})=F0 (3,
3

4

1 2
?

0 8
表8—20

6 0 5

7 9 5

9 7

3
4
Page

5
6

城市之间距离 0 8

8
0

76

(五)货郎担问题
? 阶段Ⅱ K=2时,表示从城市V1出发,中间经过2个城

市到达城市Vi的最短路程 ? F2 (2, {3, 4})=Min [F1 ( 3, {4} )+d32, F1 ( 4, {3} )=d42 ] ? =Min [14+8 , 15+5 ]=20 ? 因此P2 (2, {3, 4} ) = 4 ? F2 (3, {2, 4} ) = Min[14+9, 13+5]=18 ? 因此P2 (3, {2, 4} ) = 4 ? F2 (4,{2, 3}) = Min[14+7, 15+8]=22 ? 因此P2 (4, {2, 3} ) = 2

Page

77

(五)货郎担问题
? 阶段Ⅲ

K=3时,表示从城市V1出发,中间经过3个城 市到达城市V1的最短距离 ? F3(1,{2,3,4})=Min[F2 (2,{3, 4})+d21, F2 (3,{2, 4})+d31, F2 (4,{2, 3})+d41)] ? =Min [20+8, 18+5, 22+6 ]=23 ? 因此P3 (1,{2,3,4}) = 3
逆推回去,可知保险员的最佳行进路线是城市1→城市 2→城市4→城市3→城市1,最短的距离为23单位。 ? 货郎担问题当城市数目增加时,用动态规划求解计算 工作量显然很大,所以本方法仅适合N较小时采用。
?
Page 78

8.4 随机动态规划
?
在实际情况中,我们还会遇到一些和前面所研究的确
定性动态规划问题不同的情况,即随机动态规划。在确定 性动态规划中,状态转移和目标函数是状态变量的确定性 函数,即当本阶段的状态变量和决策变量确定后,下一个 阶段的状态变量也随之确定,目标函数值也相应确定下来。 在随机动态规划中,总是受到随机因素的影响,状态转移 不是确定的,而是呈现某种概率分布特征。研究和解放这 类问题的方法就称为随机动态规划

Page

79

一、不确定情况下的采购问题
? 例8—11 不确定情况下的采购问题 ? 某公司采购部主管需要在未来四周作出采购某种原料的

决策。由公司市场调查部预测人员提供的资料显示,未 来四周该原料的每周价格按以下概率变化见表8—21
?
价格
概率

150

170

200
0.4

0.25

0.35

? =1

?

现在的问题是,如在第一者周买入,就支付这周流行的 价格,但如果本周不买而推迟到未来三周的某周去买,则要 支付那一周的流行价格,如前三周都未采取行动购买,则第 四周由于生产经管活动的迫切需求必须买进而不管价格的高 低。问题是那周以什么价格购进可使公司所付原料费最小?

Page

80

一、不确定情况下的采购问题
? 解:问题中每周流行价格是一个随机变量,用动态规划求
? ? ?

?

?

解将问题按时间每周划分为一个阶段,共4个阶段K=4。 SK为状态变量,表示第K周市场上的价格。 XK为决策变量,XK=0,表示第K周不购买等待,XK=1,表 示第K周买进。 SKE表示第K周不购买等待,在以后几周购进的最优决策的 原料采购价格期望值。 FK (SK)表示如第K周市场价格为SK时,从第K周到第4周即 (4 — K)周内采取最优采购策略时的最小期望价格。 (K=1,2,3,4) F1(S1)则表示四周期间的最低期望价格。
Page 81

一、不确定情况下的采购问题
? 基本方程可写为:
? ?

FK (SK)=Min{SK, SKE} SK∈{150,170,200} K=1,2,3,4 F4(S4)=S4 即第4周必须购进或设S4E = +∞

? 由定义可知:SKE=FK+1(SK+1) ? =0.25FK+1 (150) + 0.35FK+1 (170) + 0.4FK+1

(200) ? 最优决策为:
? ? ?

1 ( 购进 ) XK=

当FK(SK)=SK,

0 ( 等待 )

当FK (SK)=SKE
Page 82

一、不确定情况下的采购问题
? 逆序推进求解:

? 阶段Ⅳ K=4 S4E =+∞ ? F4(S4)=Min{S4,S4E}=Min{S4,+∞}

?
? ?

=

150 X4=1 S4=150 170 X4=1 S4=170 200 X4=1 S4=200

? X4=1 即第4周无论市场上原料价格多少均必须购买。

Page

83

一、不确定情况下的采购问题
? 阶段Ⅲ K=3 ? S3E=0.25F4 (150) + 0.35F4 (170) + 0.4F4 (200) ? =0.25x150 + 0.35x170 + 0.4x200 ? =177 ? F3 (S3) = Min {S3, S3E }= Min{S3 , 177 } ? 150 X3=1 S3=150 ? = 170 X3=1 S3=170 ? 177 X3=0 S3=200 ? 上式表明第3周当原料价格为150元或170元时,应及时购进; 如价格为200元则等待第四周以期望价格177元购买。
Page 84

一、不确定情况下的采购问题
? 阶段Ⅱ K=2 ? S2E=0.25F3 (150) + 0.35F3 (170) + 0.4F3 (200) ? =0.25x150 + 0.35x170 + 0.4x177 ? =167.8 ? F2 (S2) = Min{S2 , S2E}= Min{S2 ,167.8} ? 150 X2=1 S2=150 ? = 167.8 X2=0 S2=170 ? 167.8 X2=0 S2=200 ? 上式表明当第2周原料价格为150元时购进;原料价格为 170元或200元时均不采购;而等待以后两周以期望价格 167.8元购进。
Page 85

一、不确定情况下的采购问题
? 阶段Ⅰ K=1 ? S1E = 0.25F2 (150 ) + 0.35F2 (170 ) + 0.4F2 ( 200 ) ? = 0.25x150 + 0.35x167.8 + 0.4x167.8 ? =163.35 ? F1 (S1) = Min{S1,S1E} = Min{S1, 163.35} ? 150 X1=1 S1=150 ? = 163.35 X1=0 S1=170, ? 163.35 X1=0 S1=200 ? 上式说明在第1周当原料价格为150元时即买进,当原料价

格为170元或200元时均不采购,而是等待在以后三周内以 期望价格163.35元购进。
Page 86

一、不确定情况下的采购问题
? 综合而言,问题的最优策略列于表8—22
? ? 表8—22

时间
状态

第一周

第二周

第三周

第四周

S k=150 S k=170 S k=200
?

X1=1 买进 X1=0 等待 X1=0 等待

X2=1 X2=0 X2=0

买进 等待 等待

X3=1 买进 X3=1 买进 X3=0 等待

X4=1 买进 X4=1 X4=1 买进 买进

公司按表8—22所示的策略进行原料的采购时原料的期 望价格为: ? F1 (S1)=150x0.25 + 163.35x0.35 + 163.35x0.40=160.01(元)
Page 87

二、随机生产计划问题
? 例8—12 ? 某机械企业签订了一份供货合同生产一套宇航装置,由于 技术上的要求较高,为了满足客户的要求,就必须多生产 一些产品,经推断生产产品的合格率为p=0.5。另当生产批 量为N时,合格品数Y是一个随机变量,服从于二项分布: ? P ( Y=K ) =CkN pK q N- K ? = CkN 0.5K 0.5 N- K ? = CkN 0.5N K=0,1,2-----,N
?

Page

88

二、随机生产计划问题
? 设生产一套装置的变动成本为100元,开工一次固定成本

为300元。如果一个批量中没有合格产品,则必须生产第 二批,因此需增加固定成本。企业最多可重复生产三个批 次,如此时仍无法满足客户要求,则企业的可测算损失为 1600元。企业应如何决策即在未来的三个生产过程中,每 次的生产批量为多少时,整个过程的期望成本最低? ? 解:将问题按生产批次划分为三个阶段,K=3,令状态变 量SK表示进入第K个阶段时,有待于得到的合格产品套数, SK={0,1}。 ? 决策变量XK表示进入第K次生产批次时的生产批量。 ? FK(SK)表示第K阶段状态变量为SK,决策变量的取值 为XK时,从第K阶段到以后各阶段总的最小期望成本。
Page 89

二、随机生产计划问题
? 动态规划的基本方程为: ? 0 当 SK=0 阶段K前已生产出合格产品 ? FK(SK)=Min ? FK (1) 当 SK=1 阶段K前未生产出合格产品 ? FK (1) =Min {VK (1) } ? FK (1) = Min [100XK+300sgn XK + C0 XK 0.5 XK Fk+1(1)+ 0.5 XK Fk+1 (0)] ? = Min [100XK+300sgn XK +0.5 XKFk+1 (1)] ( K=1,2,3 ) ? F4 (1)=1600表示整个过程(三个阶段)结束后,仍未生产出一件合格

品时企业的损失。 ? 式中: sgn XK ={1 / ( 当XK >0 ) or 0 / ( 当 XK =0 ) }

Page

90

二、随机生产计划问题
?

下面我们从第3阶段开始逆序求解:

? 阶段III K=3 ? F3 (1) = Min { 100X3+300 sgn X3 +1600x0.5X3 }

?

F3 (0)=0
X3 S3 0 1 0 0 1600 1200 900 800 800 850 1 2 V3 (S3) 3 4 5 0 800 F3 (S3)

? 计算结果列于表8—23

? 最优解: X3=3 or 4
?

Page

91

二、随机生产计划问题
? 阶段II K=2
?

?
?

F2 (1) = Min {100X2+300sgnX2+0.5X2F2 (1)} F2 (0)=0

计算结果列于表8—24 ? 表8—24 X2 S2 0 1 0 0 800 800 700 700 750 1 V2 (S2) 2 3 4 0 700 F2 (S2)

?
? 最优解X2=2 or 3

Page

92

二、随机生产计划问题
?

阶段I

K=1
F1(1) = Min {100X1+300sgnX1+0.5X1F2(1) F1(0)=0
F1(S1) 3 4

? ?

? 计算结果列于表8—25
?

X1

V1 (S1) 1 2

S1 1

0

700

750

675

688

744

675

? 最优解:X1=2

?

问题的最优策略是,第一次生产时,生产批量选2,如第一次已生产 出合格产品,则不再生产,否则第二次生产批量为2或3,如还未生产出 合格产品则进入第三次生产,批量为3或4,则整个策略的最小期望成本 为67500元.
Page 93


相关文章:
运筹学第八章 动态规划_图文.ppt
运筹学第八章 动态规划 - 第八章 动态规划 8.1 8.2 8.3 8.4 动态规划的研究对象和特点 动态规划的基本概念与最优化原理 动态规划的求解与应用 随机动态规划 ...
第八章 动态规划(运筹学讲义).ppt
运筹学讲义 第八章 动态规划 Dynamic Programming ? §1 动态规划问题实例 ? ? ? §2 动态规划的基本概念§3 基本原理和基本方程 §4 动态规划的应用 1 §1...
运筹(第八章动态规划)素材_图文.ppt
运筹(第八章动态规划)素材 - 运筹学 OPERATIONS RESEARCH 2018/10/13 1 第八章 ? ? ? ? ? 动态规划 多阶段决策最优化问题举例 基本概念、基...
运筹学[第八章动态规划的基本方法]山东大学期末考试知....doc
运筹学[第八章动态规划的基本方法]山东大学期末考试知识点复习_管理学_高等教育_教育专区。运筹学:山东大学期末考试知识点复习 山东大学期末考试知识点复习 第八章 ...
第八章 动态规划(运筹学-上海电力学院,施泉生_图文.ppt
第八章 动态规划(运筹学-上海电力学院,施泉生 - 第八章 动态规划 动态规划是解决多阶段决策过 程最优化问题的一种方法。由美国 数学家贝尔曼(Ballman)等人在 ...
运筹08(第八章动态规划)_图文.ppt
运筹08(第八章动态规划) - 运筹学 OPERATIONS RESEARCH 2011-8-20 1 第八章 动态规划 §1 多阶段决策最优化问题举例 基本概念、 §2 基本概念、...
运筹08(第八章动态规划)运筹学第五版课件(历史上最好的....ppt
运筹学 OPERATIONS RESEARCH 2012-8-18 1 第八章§1 动态规划 多阶段决策最优化问题举例 §2 §3 基本概念、基本方程与最优化原理离散确定性动态规划求解 §4 ...
运筹学动态规划_图文.ppt
运筹学动态规划 - 动态规划(Dynamic Programming) 动态规划是美国数学家Bellman创立的。Bellman50年代执教于普林 斯顿和斯坦福大学,后进入兰德(Rand)研究所...
运筹08(第八章动态规划)_图文.ppt
运筹08(第八章动态规划) - 运筹学 OPERATIONS RESEARCH 2012-10-13 1 第八章 §1 动态规划 多阶段决策最优化问题举例 §2 §3 基本概念、...
运筹08(第八章动态规划)_图文.ppt
运筹08(第八章动态规划) - 运筹学 OPERATIONS RESEARCH 2013-7-22 1 第八章 §1 动态规划 多阶段决策最优化问题举例 §2 §3 基本概念、基...
Ch8动态规划_图文.ppt
Ch8动态规划 - 山东大学工业工程运筹学课件... 运筹学 Operations Research 第八章 动态规划 Dynamic Programming 8.1 动态规划数学模型Mathematical Model of DP 8....
动态规划(运筹学讲义)_图文.ppt
动态规划(运筹学讲义) - 第八章 动态规划 Dynamic Programming §1 动态规划问题实例 动态规划的基本概念 §2 动态规划的基本概念 §3 基本原理和基本方程 动态...
运筹学动态规划_图文.ppt
运筹学动态规划 - 运筹学 课程主要内容 第一章 第二章 第三章 第四章 第五章 第七章 第八章 第九章 线性规划与单纯形法 对偶理论与灵敏度分析 运输问题 ...
运筹学习题集(第八章).doc
运筹学习题集(第八章) - 判断题 判断正误,如果错误请更正 第八章 动态规划 1.用动态规划求解一般线性规划问题是将约束条件数作为阶段数,变量作为状态。 2.动态...
第八章 动态规划_图文.ppt
第八章 动态规划_理学_高等教育_教育专区。运筹学 第八章 动态规划 ? ? 第一节 动态规划原理和模型第二节 一维动态规划求解方法 ? 第三节 动态规划在经济和...
运筹学动态规划_图文.ppt
运筹学动态规划 - 第八章 动态规划 ? 多阶段决策过程:是指这样一类决策过程,
100717_05_运筹学动态规划_图文.ppt
100717_05_运筹学动态规划 - 运筹学 课程主要内容 第一章 第二章 第三章 第四章 第五章 第七章 第八章 第九章 线性规划与单纯形法 对偶理论与灵敏度分析...
动态规划习题答案.doc
动态规划习题答案 - 由复旦大学出版社出版,傅家良主编的运筹学方法与模型第八章动态规划习题答案
运筹学课件8.动态规划(2010.6.10)_图文.ppt
运筹学课件8.动态规划(2010.6.10)_工学_高等教育_教育专区。合肥工业大学运筹学老师课件 第八章 动态规划 (Dynamic programming) 五十年代贝尔曼( 五十年代...
运筹学第8章动态规划.ppt
运筹学第七章 动态规划 52页 2财富值 运筹08(第八章动态规划)运... 40...7 8.2 动态规划模型举例 8.2.1 产品生产计划安排问题例1 某工厂生产某种...
更多相关文章: