当前位置:首页 >> 工学 >>

运筹学课程07-动态规划


NEUQ

动态规划 Dynamic Programming

不要过河拆桥 追求全局最优

本章内容

NEUQ

多阶段决策过程的最优化 动态规划的基本概念和基本原理 动态规划方法的基本步骤 动态规划方法应用举例

NEUQ

一、多阶段决策过程的最优化
示例1 工厂生产安排): 示例1(工厂生产安排):
某种机器可以在高、低两种负荷下生产。 某种机器可以在高、低两种负荷下生产。高负荷生产 条件下机器完好率为0.7, 条件下机器完好率为0.7,即如果年初有u台完好机器投入 0.7 生产,则年末完好的机器数量为0.7u台。系数0.7称为完好 系数0.7 0.7称为完好 生产,则年末完好的机器数量为0.7 台机器的年产量为8 率。年初投入高负荷运行的u台机器的年产量为8u吨。系数 8称为单台产量。低负荷运行时,机器完好率为0.9,单台 称为单台产量。低负荷运行时,机器完好率为0.9, 0.9 产量为5 产量为5吨。设开始时有1000台完好机器,要制订五年计划, 设开始时有1000台完好机器,要制订五年计划, 1000台完好机器 每年年初将完好的机器一部分分配到高负荷生产, 每年年初将完好的机器一部分分配到高负荷生产,剩下的 机器分配到低负荷生产,使五年的总产量为最高。 机器分配到低负荷生产,使五年的总产量为最高。

NEUQ
推广: 推广:多阶段资源分配问题 设有数量为y的某种资源, 设有数量为y的某种资源,将它分别投入两 种生产方式A 已知收益函数分别是g(x) g(x)和 种生产方式A和B,已知收益函数分别是g(x)和 h(x), 为资源投入量。 h(x),x为资源投入量。设这种资源用于生产后 还可以回收一部分用于生产, 还可以回收一部分用于生产,A、B的回收率分别 0≤a≤1, 为a和b( 0≤a≤1,0≤b≤1 ), 对总数量为y的资源进行n个阶段的生产, 问:对总数量为y的资源进行n个阶段的生产, 应如何分配每个阶段投入A 的资源数量, 应如何分配每个阶段投入A、B的资源数量,才能 使总收益最大? 使总收益最大?

示例2 设备更新问题): 示例2(设备更新问题):

NEUQ

一般企业用于生产活动的设备, 一般企业用于生产活动的设备,刚买来 时故障少,经济效益高,即使进行转让, 时故障少,经济效益高,即使进行转让,处理 价值也高,随着使用年限的增加, 价值也高,随着使用年限的增加,就会逐渐变 为故障多,维修费用增加, 为故障多,维修费用增加,可正常使用的工时 减少,加工质量下降,经济效益差,并且, 减少,加工质量下降,经济效益差,并且,使 用的年限越长、处理价值也越低,自然, 用的年限越长、处理价值也越低,自然,如果 卖去旧的买新的,还需要付出更新费. 卖去旧的买新的,还需要付出更新费.因此就 需要综合权衡决定设备的使用年限, 需要综合权衡决定设备的使用年限,使总的经 济效益最好。 济效益最好。

NEUQ
示例3 连续生产过程的控制问题): 示例3 (连续生产过程的控制问题):

一般化工生产过程中, 一般化工生产过程中,常包含一系列完成 生产过程的设备, 生产过程的设备,前一工序设备的输出则是后 一工序设备的输入,因此,应该如何根据各工 一工序设备的输入,因此, 序的运行工况, 序的运行工况,控制生产过程中各设备的输入 和输出,以使总产量最大。 和输出,以使总产量最大。

示例4 示例4、最短路径问题

NEUQ

给定一个交通网络图如下, 给定一个交通网络图如下,其中两点之间的数字表示距离 或花费),试求从A点到 ),试求从 点到G点的最短距离(总费用最小)。 (或花费),试求从 点到 点的最短距离(总费用最小)。 1 5 A 3 B2 B1 6 8 7 6 C3 8 C4 1 2 3 4 5 6 3 C2 C1 3 5 3 3 4 D3 D2 3 3 E3 1 2 6 8 D1 2 2 5 E2 6 6 2 F2 E1 3 5

F1

4 G 3

NEUQ
示例5 生产与存储问题): 示例5(生产与存储问题):
某工厂生产并销售某种产品。 某工厂生产并销售某种产品。已知今后四个月市场需求 预测及每月生产j个单位产品的费用如下 个单位产品的费用如下: 预测及每月生产 个单位产品的费用如下:
? 0 c( j ) = ? ?3 + j j=0 j = 1,2,L6
月 需求 1 2 2 3 3 2 4 4

每月库存i个单位产品的费用 ),该厂最大 每月库存 个单位产品的费用E(i)=0.5i(千元),该厂最大 (千元), 库存容量为3个单位,每月最大生产能力为6个单位, 库存容量为3个单位,每月最大生产能力为6个单位,计划开 始和计划期末库存量都是零,试制定四个月的生产计划, 始和计划期末库存量都是零,试制定四个月的生产计划,在 满足用户需求条件下,使总费用最小。 满足用户需求条件下,使总费用最小。 每个月视为一个阶段, 每个月视为一个阶段, 每个阶段都须决定生产几个、 每个阶段都须决定生产几个、库存几个 上一个阶段的决策直接影响下一个阶段的决策

示例6 航天飞机飞行控制问题): 示例6(航天飞机飞行控制问题):

NEUQ

由于航天飞机的运动的环境是不断变化的, 由于航天飞机的运动的环境是不断变化的, 因此就要根据航天飞机飞行在不同环境中的情况, 因此就要根据航天飞机飞行在不同环境中的情况, 不断地决定航天飞机的飞行方向和速度(状态), 不断地决定航天飞机的飞行方向和速度(状态), 使之能最省燃料和实现目的(如软着落问题)。 使之能最省燃料和实现目的(如软着落问题)。

NEUQ
所谓多阶段决策问题是指一类活动过程, 所谓多阶段决策问题是指一类活动过程,它可以分 多阶段决策问题是指一类活动过程 为若干个相互联系的阶段,在每个阶段都需要作出决策。 为若干个相互联系的阶段,在每个阶段都需要作出决策。 这个决策不仅决定这一阶段的效益, 这个决策不仅决定这一阶段的效益,而且决定下一阶段 的初始状态。 的初始状态。 每个阶段的决策均确定以后,就得到一个决策序列, 每个阶段的决策均确定以后,就得到一个决策序列, 称为策略。多阶段决策问题就是求一个策略, 称为策略。多阶段决策问题就是求一个策略,使各阶段 的效益的总和达到最优。 的效益的总和达到最优。 决策 状态 1 状态 决策 2 状态 … 状态 决策 n

动态规划是用来解决多阶段决策过程最优化的一种 数量方法。其特点在于,它可以把一个n 数量方法。其特点在于,它可以把一个n 维决策问题变 换为几个一维最优化问题,从而一个一个地去解决。 换为几个一维最优化问题,从而一个一个地去解决。
10

NEUQ
不包含时间因素的静态决策问题( 不包含时间因素的静态决策问题(本质上是一次决策问 也可以适当地引入阶段的概念, 题)也可以适当地引入阶段的概念,作为多阶段的决策问 题用动态规划方法来解决。 题用动态规划方法来解决。 某些线性规划、 某些线性规划、非线性规划等静态规划问题也可以通过 适当地引入阶段的概念,应用动态规划方法加以解决。 适当地引入阶段的概念,应用动态规划方法加以解决。 DP是上个世纪五十年代贝尔曼 是上个世纪五十年代贝尔曼(B.E.Bellman)为代表 是上个世纪五十年代贝尔曼 为代表 的研究成果,属于现代控制理论的一部分。其最优化原理, 的研究成果,属于现代控制理论的一部分。其最优化原理, 可归结为一个递推公式。 可归结为一个递推公式。 注意:动态规划是求解某类多阶段决策问题的一种方法, 注意:动态规划是求解某类多阶段决策问题的一种方法,是 考察问题的一种途径 不是一种算法。 途径, 考察问题的一种途径,不是一种算法。必须对具体问题进 行具体分析,运用动态规划的原理和方法, 行具体分析,运用动态规划的原理和方法,建立相应的模 然后再用动态规划方法去求解。 型,然后再用动态规划方法去求解。

NEUQ
动态规划思想示例: 动态规划思想示例:

2 B1 4 4 A 3 2 4 B3 7 3 5 1 8 3 B2 7 2 1 6

C1 6

8

D1 7 C2 5

10 E

1 6 C3

D

6 2

Β4

NEUQ
以上求从A到 的最短路径问题 的最短路径问题, 以上求从 到E的最短路径问题,可以转化为四个性质完 全相同,但规模较小的子问题, 全相同,但规模较小的子问题,即分别从 Di 、 i 、 i、 C B A到E的最短路径问题。 的最短路径问题。 第四阶段: 终点只有一个; 第四阶段:两个始点 D1 和 D2 ,终点只有一个;
阶段4 阶段 本阶段始点 状态) (状态) D1 D2 本阶段各终点(决策) 本阶段各终点(决策) E 10 6 10 6 到E的最短距离 的最短距离 本阶段最优终点 最优决策) (最优决策 E E

分析得知: 的最短路径唯一。 分析得知:从D1 和 D2 到E的最短路径唯一。

NEUQ
第三阶段:有三个始点 终点有D 第三阶段:有三个始点C1,C2,C3,终点有 1,D2,对始点 和终点进行分析和讨论分别求C 和终点进行分析和讨论分别求 1,C2,C3到D1,D2 的最短路 径问题: 径问题:
阶段3 阶段 本阶段始点 状态) (状态) C1 C2 C3 本阶段各终点(决策) 本阶段各终点(决策) D1 8+10=18 7+10=17 1+10=11 D2 6+6=12 5+6=11 6+6=12 到E的最短距离 的最短距离 12 11 11 本阶段最优终点 最优决策) (最优决策 D2 D2 D1

分析得知:如果经过 ,则最短路为C 分析得知:如果经过C1,则最短路为 1-D2-E; ; 如果经过C ,则最短路为C 如果经过 2,则最短路为 2-D2-E; ; 如果经过C 则最短路为C 如果经过 3,则最短路为 3-D1-E。 。

NEUQ
第二阶段:有 4个始点 1,B2,B3,B4 , 终点有C1,C2,C3 。 对始 第二阶段 : 个始点B 终点有 个始点 点和终点进行分析和讨论分别求B 点和终点进行分析和讨论分别求 1,B2,B3,B4到C1,C2,C3 的最 短路径问题: 短路径问题:
阶段2 阶段 本阶段始点 状态) (状态) B1 B2 B3 B4 本阶段各终点(决策) 本阶段各终点(决策) C1 2+12=14 4+12=16 4+12=16 7+12=19 C2 1+11=12 7+11=18 8+11=19 5+11=16 C3 6+11=17 2+11=13 3+11=14 1+11=12 到E的最短 本阶段最优终 的最短 最优决策) 点(最优决策 距离 12 13 14 12 C2 C3 C3 C3

分析得知:如果经过B1,则走B1-C2-D2-E; 分析得知:如果经过 则走 ; 如果经过B 则走B 如果经过 2,则走 2-C3-D1-E; ; 如果经过B 则走B 如果经过 3,则走 3-C3-D1-E; ; 如果经过B 则走B 如果经过 4,则走 4-C3-D1-E。 。

NEUQ
第一阶段:只有 个始点 个始点A,终点有B 第一阶段:只有1个始点 ,终点有 1,B2,B3,B4 。对始点和终 点进行分析和讨论分别求A到 的最短路径问题: 点进行分析和讨论分别求 到B1,B2,B3,B4的最短路径问题:
阶段1 阶段 本阶段始 状态) 点(状态 状态 A 本阶段各终点(决策) 本阶段各终点(决策) B1 4+12=16 B2 3+13=16 B3 3+14=17 B4 2+12=14 到E的最 的最 短距离 14 本阶段最优终 最优决策) 点(最优决策 最优决策

B4

最后,可以得到:从A到E的最短路径为 → B4→ C3→ D1→ E 最后,可以得到: 到 的最短路径为A→ 的最短路径为

NEUQ
以上计算过程及结果,可用下图表示,可以看到, 以上计算过程及结果,可用下图表示,可以看到,以上方 法不仅得到了从A到 的最短路径 同时, 的最短路径, 法不仅得到了从 到D的最短路径,同时,也得到了从图中 任一点到E的最短路径 的最短路径。 任一点到 的最短路径。
12 B1 4 14 A 3 2 B3 3 13 4 B2 2 4 8 3 1 C3 11 1 6 7 11 C2 5 D2 6 6 7 2 6 1 12 C1 6 8 10 D1 10 0 E

14 7 5

B4
12

以上过程,仅用了 次加法 计算效率远高于穷举法。 次加法, 以上过程,仅用了22次加法,计算效率远高于穷举法。

NEUQ

二、动态规划的基本概念和基本原理
基本概念
1、阶段: 、阶段: 把一个问题的过程,恰当地分为若干个相互联系的阶段, 把一个问题的过程,恰当地分为若干个相互联系的阶段,以便 阶段 于按一定的次序去求解。 于按一定的次序去求解。
一个数 一组数 描述阶段的变量称为阶段变量 阶段的划分, 阶段变量。 描述阶段的变量称为阶段变量。阶段的划分,一般是根据时间 一个向 年、月、 和空间的自然特征来进行的,但要便于问题转化为多阶段决策。 和空间的自然特征来进行的,但要便于问题转化为多阶段决策。 量 路段

2、状态:表示每个阶段开始所处的自然状况或客观条件。通常 、状态:表示每个阶段开始所处的自然状况或客观条件。 自然状况或客观条件 一个阶段有若干个状态,描述过程状态的变量称为状态变量 状态变量。 一个阶段有若干个状态,描述过程状态的变量称为状态变量。 状态变量的取值有一定的允许集合或范围,此集合称为状态 状态变量的取值有一定的允许集合或范围,此集合称为状态 允许集合。 允许集合。

NEUQ
3、决策:表示当过程处于某一阶段的某个状态时,可以作 、决策:表示当过程处于某一阶段的某个状态时, 出不同的决定,从而确定下一阶段的状态,这种决定称为决策 决策。 出不同的决定,从而确定下一阶段的状态,这种决定称为决策。 描述决策的变量,称为决策变量。 描述决策的变量,称为决策变量。决策变量是状态变量的函 决策变量 可用一个数、一组数或一向量(多维情形)来描述。 数。可用一个数、一组数或一向量(多维情形)来描述。 在实际问题中决策变量的取值往往在某一范围之内, 在实际问题中决策变量的取值往往在某一范围之内,此范围 称为允许决策集合 允许决策集合。 称为允许决策集合。 4、多阶段决策过程 、 可以在各个阶段进行决策,去控制过程发展的多段过程; 可以在各个阶段进行决策,去控制过程发展的多段过程; 其发展是通过一系列的状态转移来实现的; 其发展是通过一系列的状态转移来实现的; 系统在某一阶段的状态转移不但与系统的当前的状态和决 策有关,而且还与系统过去的历史状态和决策有关。 策有关,而且还与系统过去的历史状态和决策有关。

其状态转移方程如下(一般形式) 其状态转移方程如下(一般形式)

NEUQ

s2 = T1 ( s1 , u1 ) s3 = T2 ( s1 , u1 , s2 , u2 ) LL sk + 1 = Tk ( s1 , u1 , s2 , u2 , L , s k , uk )
图示如下: 图示如下:

状态转移方程是确定 过程由一个状态到另 一个状态的演变过程。 一个状态的演变过程。 如果第k阶段状态变量 如果第 阶段状态变量 sk的值、该阶段的决策 的值、 变量一经确定, 变量一经确定,第k+1 阶段状态变量s 阶段状态变量sk+1的值 也就确定。 也就确定。

s1

u1 1

s2

u2 2

s3



sk

uk k

sk+1

能用动态规划方法求解的多阶段决策过程是一类特殊的多 阶段决策过程,即具有无后效性的多阶段决策过程。 阶段决策过程,即具有无后效性的多阶段决策过程。

无后效性(马尔可夫性) 无后效性(马尔可夫性) NEUQ 如果某阶段状态给定后, 如果某阶段状态给定后,则在这个阶段以后过程的发展不 受这个阶段以前各段状态的影响; 受这个阶段以前各段状态的影响; 过程的过去历史只能通过当前的状态去影响它未来的发展; 过程的过去历史只能通过当前的状态去影响它未来的发展;

状态变量要满足无后效性的要求;
如果状态变量不能满足无后效性的要求,应适当地改变状 如果状态变量不能满足无后效性的要求, 态的定义或规定方法。 态的定义或规定方法。 状态具有无后效性的多阶段决策过程的状态转移方程如下

s 2 = T1 ( s1 , u1 ) s 3 = T2 ( s 2 , u 2 ) LL s k + 1 = Tk ( s k , u k )

动态规划中能 处理的状态转移 方程的形式。 方程的形式

NEUQ
5、策略:是一个按顺序排列的决策组成的集合。在实际问题 策略:是一个按顺序排列的决策组成的集合。 允许策略集合。 可供选择的策略有一定的范围,称为允许策略集合 中,可供选择的策略有一定的范围,称为允许策略集合。从允 许策略集合中找出达到最优效果的策略称为最优策略 最优策略。 许策略集合中找出达到最优效果的策略称为最优策略。 6、状态转移方程:是确定过程由一个状态到另一个状态的 状态转移方程: 演变过程,描述了状态转移规律。 演变过程,描述了状态转移规律。 7、指标函数和最优值函数:用来衡量所实现过程优劣的一 指标函数和最优值函数: 种数量指标, 指标函数。指标函数的最优值,称为最优值函 种数量指标,为指标函数。指标函数的最优值,称为最优值函 在不同的问题中,指标函数的含义是不同的, 数。在不同的问题中,指标函数的含义是不同的,它可能是距 利润、成本、产量或资源消耗等。 离、利润、成本、产量或资源消耗等。 动态规划模型的指标函数,应具有可分离性,并满足递推 动态规划模型的指标函数,应具有可分离性,并满足递推 关系。 关系。

小结: 小结:

NEUQ
无后效性

动态规划本质上是多阶段决策过程; 动态规划本质上是多阶段决策过程; 概念 : 阶段变量k﹑状态变量sk﹑决策变量uk; 方程 :状态转移方程 s k +1 = Tk ( s k , u k ) 指标: 指标: Vk ,n = Vk ,n (sk , uk , sk +1 , uk +1 ,L, sn+1 )
效益

f k ( s k ) = opt V k ,n ( s k , u k ,L , s n +1)
{u k ,L,u n }
Vk ,n ( sk , uk , sk +1 , uk +1 , L , sn +1 )
可递推

= ? k [ s k , u k , V k + 1 , n ( s k + 1 , u k + 1 , L , s n + 1 )]
指标函数形式: 指标函数形式: 和、 积

NEUQ
原过程的一个后部子过程: 原过程的一个后部子过程: 对于任意给定的k( ),从第 段到第n段的过 对于任意给定的 (1 ≤ k≤n),从第 段到第 段的过 ),从第k段到第 程称为原过程的一个后部子过程 原过程的一个后部子过程的策略: 原过程的一个后部子过程的策略: 后部子过程的策略

从第 k 阶段初始状态 s k 开始到第 n 阶段的 .决策组成的序列 . 记为:p k ,n (s k )

V1,n (s1 , p1,n ) ? ?在初始状态为 s1时采用原过程策略 p1,n 所对应 的指标函数 Vk , n ( s k , p k , n ) ? ?在第 k 阶段状态为 s k 时采用后部子过程

NEUQ

策略 p k , n 所对应的指标函数 使指标函数 Vk ,n (s k , p k ,n )达到最优的策略 最优策略 p*k,n :

最优值函数 f k (s k ) ? ? 从第 k 阶段状态 s k 开始到过程终
f k (s k ) = V k , n (s k , p * k , n ) = opt Vk ,n sk , pk ,n
pk , n∈Pk , n

止采用最优策略 p *k , n 时的指标函数值

(

)

f 1 (s1 ) ? ?初始状态为 s1时全过程采用最优策略 p *1,n 所对应的指标函数值

解多阶段决策过程问题, 解多阶段决策过程问题,求出 最优策略,即最优决策序列 最优策略,即最优决策序列

NEUQ

{ u , u ,L , u }
最优轨线,即执行最优策略时的状态序列 最优轨线 即执行最优策略时的状态序列 即执行最优策略时的
* * * { s1 , s 2 ,L , s n }

* 1

* 2

* n

f1(s1)

最优目标函数值
* V 1,n

=

* V 1,n

* ( s1

* 从 k 到终点最优策略 * * , u1 ,L , s n , u n )

子策略的最优目标函数值

f (s ) = o p t v
k k

{u

k

,L ,

u n}

k ,n

(s , u
k

k

,L ,

s

n +1

)

NEUQ
5 ○

阶段
问题分成4个阶段: 问题分成 个阶段: 个阶段 k=1,2,3,4 , , , k=1: 第一阶段,甘肃 : 第一阶段, k=3: 第三阶段:山西 : 第三阶段: 线路: 线路: 5 8, 5

10 2 8 9○ 8 ○ 4 6 8 9 6 1 3 6 ○ 7 ○ 2 ○ 10 ○4 7 3 甘肃 9 3 北京 ○ 6 1 8 ○ 4 7 ○ 河北 山西 陕西 陕西 5 河北

线路: 线路: 1 2, 3,1 4 1

6 9,

6 8,

7 7 9, 8,

9

NEUQ
状态 sk
第k阶段的状态变量 阶段的状态变量 5
5 ○ 8

10 2 9 ○ Sk ={sk} 第k阶段的状态集合 ○ 阶段的状态集合 8 4 6 8 9 6 1 3 6 ○ 7 ○ 2 ○ 10 ○ 4 9 7 3 甘肃 ○ 6 1 3 北京 第一阶段的状态: 1 第一阶段的状态: ○ 4 8 ○ 7 ○ 河北 山西 陕西 第二阶段的状态: 2 3 4 第二阶段的状态: ○ ○ ○

s4

第4阶段的状态变量 阶段的状态变量

s4=8
S5 ={10}

第4阶段的状态 阶段的状态

8 ○

S3 ={s3} ={5,6,7} , ,

个阶段的决策过程有个n+1状态变量 注:n个阶段的决策过程有个 个阶段的决策过程有个 状态变量 sn+1表示 n演变的结果 表示s

决策
允许决策集合

NEUQ

U k (s k ) ? ?决策变量 u k ( s k )允许取值的范围
8 10 ○ 4 9 北京 ○ 河北
8 ○

u k (s k ) ? ? ? 第k阶段处于状态s k时的决策变量
5
5 ○

8 96 6 ○ 6 1
7 ○

u 2 (3)

山西

10 2 9 ○ 4 6 1 7 ○ 2 ○ 3 7 3 甘肃 3 4 8 ○ 陕西

u 2 (3) = 7

阶段当状态为3时的决策变量 第2阶段当状态为 时的决策变量 阶段当状态为 可取值为:5,6,7 可取值为: , , 决策 3 → 7 , , U 2 (3) ={5,6,7}

策略

p1,n (s1 ) ? ? ? 从第一阶段初始状态s1开始到 第n阶段全过程的策略

NEUQ

P={ 策略 } ——允许策略集合

即 p 1, n (s1 ) = {u 1 (s1 ), u 2 (s 2 ), L u n (s n )}

策略:{ 1→2, 2→5, 5→9, 9 → 10 } = p1, 4 (1) 最优策略=最短的行进路线 最优策略 最短的行进路线

如{ 1→3, 3→7,7→9, 9 → 10} = p1, 4 (1)

最优策略:使整个问题达到最优效果的策略 最优策略: 5 5 ○ 10 ○ 8 9 2 8 ○ 4 6 8 96 最短路问题: 最短路问题: 1 3 6 ○ 7 ○ 2 ○ 10 ○ 4 9 7 3 甘肃 ○ 6 1 3 策略 = 行进方案 北京 4 8 ○ 策略 河北 7 ○ 山西 陕西

最短路问题: 最短路问题:

10 ○

8 4

8 ○ 9 ○

5

北京 原过程的一个策略: 原过程的一个策略:

河北

8 9 6 6 ○ 6 1
7 ○

5 ○

山西

10 2 9 ○ NEUQ 4 6 1 7 ○ 2 ○ 3 7 3 甘肃 3 4 8 ○ 陕西

{ 1→ 3, 3→7, 7→9, 9 → 10 } = p1, 4 (1)
p 2, 4 (3) = { 3→7, 7→9, 9 → 10 } p 3, 4 (7 ) ={ 7→9, 9 → 10 p 4, 4 (9 ) = { 9 → 10 }
p 3, 4 (5) = { 5→8, 8 → 10

后部子过程 的策略 后部子过程 的策略 后部子过程 的策略

}

}

or{ 5→9,

9 → 10 }

(生产与存储问题)某工厂生产并销售某种产品。NEUQ 生产与存储问题)某工厂生产并销售某种产品。 已知今四个月市场需求预测如下表, 已知今四个月市场需求预测如下表,又每月生产 j个单位产品的费用为 个单位产品的费用为
? 0 c( j ) = ? ?3 + j j =0 j = 1,2,L6
i月 月 g(i)需求 需求 1 2 2 3 3 2 4 4

每月库存i个单位产品的费用 千元), 每月库存 个单位产品的费用E(i)=0.5i(千元),该厂最 个单位产品的费用 千元),该厂最 大库存容量为3个单位 每月最大生产能力为6个单位 个单位, 个单位, 大库存容量为 个单位,每月最大生产能力为 个单位,计 划开始和计划期末库存量都是零,试制定四个月的生产计划, 划开始和计划期末库存量都是零,试制定四个月的生产计划, 在满足用户需求条件下,使总费用最小。 在满足用户需求条件下,使总费用最小。

阶段
k=1,2,3,4 阶段的状态变量 第k阶段的状态变量sk =第k个月月初的库存量 阶段的 第 个月月初的库存量

S1={0}, 2={0,1,2,3}, 3={0,1,2,3},S4={0,1,2,3} S S

NEUQ

决策变量 u k (s k ) = 第k月月初库存量为 s k时产品的产量
U1(0)={2,3,4,5}
p 1, 4 (0 ) =

U2 (1) ={2,3,4,5}

U3(2) ={0,1,2,3}

U4 (1)={3}

一个策略 一个 一个策略=一个生产方案 策略 一个生产方案

{ 2,3,2,4 } p 1, 4 (0 ) = { 2,5,0,4 }

费用:23(千元) 费用:21(千元)

最优策略: 最优策略: 使总费用最小的生产方案

最优化原理(基本原理) 最优化原理(基本原理)

NEUQ

作为整个过程的最优策略具有这样的性质: 作为整个过程的最优策略具有这样的性质:无论 过去的状态和决策如何, 过去的状态和决策如何,相对于前面的决策所形 s 成的当前状态而言,余下的决策序列必然构成最 成的当前状态而言, 优子策略。 也就是说, 优子策略。”也就是说,一个最优策略的子策略 也是最优的。 也是最优的。
1

对最短路问题: 对最短路问题:

NEUQ

f k (s k ) = 从第 k阶段状态为 s k 到 E 点的最短距离

找最短路线的方法:
从最后一阶段开始,用由后向前的方法,求出各点到终点的 从最后一阶段开始,用由后向前的方法, 最短路线,最后,求得由起点到终点的最短路线。 最短路线,最后,求得由起点到终点的最短路线。

最短路问题的基本方程: 最短路问题的基本方程: 基本方程
?f k (s k ) = min uk ? ? f 5 (s 5 ) = 0
10 ○

{d (s k , u k ) +
5 8 9 6 6 ○ 6 1
7 ○ 5 ○

f k + 1 (s k + 1 )} k=4,3,2,1

8

8 ○

4 9 北京 ○ 河北

山西

10 2 9 ○ 4 6 1 7 ○ 2 ○ 3 7 3 甘肃 3 4 8 ○ 陕西

, 求 f1 (1)

对于生产与存储问题:某工厂生产并销售某种产品。 对于生产与存储问题:某工厂生产并销售某种产品。已知今 四个月市场需求预测如下表,又每月生产j个单位产品费用为 四个月市场需求预测如下表,又每月生产 个单位产品费用为
i月 月 g(i)需求 需求 1 2 2 3 3 2 4 4

NEUQ

? 0 c(j)= ? ?3 + j

j = 0 j = 1, 2 , L 6

每月库存i个单位产品的费用 每月库存 个单位产品的费用E(i)=0.5i(千元),该厂最大库存 千元),该厂最大库存 个单位产品的费用 千元), 容量为3个单位 每月最大生产能力为6个单位 个单位, 个单位, 容量为 个单位,每月最大生产能力为 个单位,计划开始和计 划期末库存量都是零,试制定四个月的生产计划, 划期末库存量都是零,试制定四个月的生产计划,在满足用户 需求条件下,使总费用最小。 需求条件下,使总费用最小。 阶段k=1,2,3,4 阶段 , , , 状态变量 s k =第k个月月初的库存量 第 个月月初的库存量

决策变量 u k (s k ) = 第 k月月初库存量为 s k时产品的产量
状态转移方程: 状态转移方程:

sk +1 = uk + sk ? g (k )

最优值函数f k ( s k ):第k月月初库存为s k时,从本月到 计划结束的最小总费用

求1(0) f

最大生产能力为6个单位, 最大库存容量为3个单位 个单位, 最大生产能力为 个单位, 最大库存容量为 个单位, NEUQ 个单位 库存费E(i)=0.5i, , 库存费 计划开始和计划期末库存量为零
i月 月 g(i)需求 需求 1 2 2 3 3 2 4 4

生产费用 ? 0 c( j ) = ? ?3 + j

j=0 j = 1, 2, L 6

f k ( s k ):第 k月月初库存为 s k时,从本月到计划结束 的最小总费用 当k=4时, 求f 4 ( s 4 ) 时 s 4 = 0,1,2,3

u4(s4)对应的总费用 生产费 库存费 = c (u 4 ) + E ( s 4 ) 对应的总费用=生产费 对应的总费用 生产费+库存费

f 4 (s 4 ) = min {c (u 4 ) + E ( s 4 )}
u4

s4 u4
f 4 (s4 )

0 4 7 4

1 3 6.5 3

2 2 6 2

3 1 5.5 1

u *4

最大生产能力为6个单位, 最大生产能力为 个单位, 个单位 最大库存容量为 个单位, s3 最大库存容量为3个单位 个单位, 库存费E(i)=0.5i, , 库存费 计划开始和计划期末库存量为零 0
i月 月 g(i)需求 需求 1 2 2 3 3 2 4 4

s4 NEUQ
0
f4 (1 )

生产费用 ? 0 c( j ) = ? ?3 + j

j=0 1 j = 1, 2, L 6 u3 = 0 f4 (2)

1

当k=3时, 求f 3 ( s3 ) 时

s 3 = 0 ,1 , 2 , 3

2 3

u3 =1 2

分析 f 3 (3): s 3 = 3时, 3 (s 3 ) = u 3 (3 ) = 0 ,1 , 2 当 u u3(3)对应的总费用 生产费 库存费= c (u 3 ) + E ( 3 ) 对应的总费用=生产费 对应的总费用 生产费+库存费

u3 = f 3 ( s 3 ) = 第3月月初库存为 s 3时,从本月到计划结束2 3 的最小总费用 = m {C(u3(s3 )) + E(s3 ) + f4 (s4 )} in
u3 ( s3 )

f4 (3)

f 3 (3) =min C(0) + E(3) + f 4 (1), C(1) + E(3) + f 4 (2), C(2) + E(3) + f 4 (3)} {

s = min {C ( u3 ( 3 )) + E (3) + f 4 ( 4 )} 0 u ( 3)
3

s3 最大生产能力为6个单位, 最大库存容量为3个单位, s3 库存费E(i)=0.5i, 计划开始和计划期末库存量为零
i月 月 g(i)需求 需求 1 2 2 3 3 2 4 4

NEUQ

s4 u4
f 4 (s4 )

0 4 7 4

1 3 6.5 3

2 2 6 2
u3 ( s3 )

3 1 5.5 1

生产费用 ? 0 c( j ) = ? ?3 + j

j=0 j = 1, 2 , L 6

u *4

f3(s3 ) = mn{C(u3 (s3 )) + E(s3 ) + f4 (s4 )} i
0 2 3 4 5 1 1 2 3 4 0 1 2 2 3 3 0 1 2

s3 u3
f 3 (s 3

C + E + f 4 12 12 .5 13 13.5 11.5 12 12.5 13 8 11.5 12 12.5 8 11.5 12
* u 3 (s 3 )

)

12 2

11.5 1

8 0

8 0

NEUQ

i月 月 g(i)需求 需求

1 2

2 3

3 2

4 4

当k=2时, 求f 2 ( s 2 ) 时

s 2 = 0 ,1, 2 , 3

f 2 ( s 2 ) = 第 2月 月 初 库 存 为 s 2时 , 从 本 月 到 计 划 结 束 的最小总费用
u2(s2)对应的总费用 生产费 库存费 对应的总费用=生产费 对应的总费用 生产费+库存费

= c (u 2 ) + E ( s 2 )

f2 (s2 ) = mn{C(u2 ) + E(s2 ) + f3 (s3 )} i
u2 ( s2 )

k=3

s3 u3
f 3 (s 3
2 3

0 4 5 1

1 2 3 4 0 1

2 2 3

NEUQ 3
0 1 2

C + E + f 4 12 12 .5 13 13.5 11.5 12 12.5 13 8 11.5 12 12.5 8 11.5 12
* u 3 (s 3 )

)

12 2
u2 ( s2 )

11.5 1

8 0

8 0

in k=2时 当k=2时, f2 (s2 ) = m {C(u2 ) + E(s2 ) + f3 (s3 )}
s2 u2
C + E + f3
* u 2 (s 2 )

0 3 4 5 6 2 3

1 4 5 1

2 2 3 4 0 1

3 2 3

18 18.5 16 17 17.5 18 15.5 16.5 17 17.5 15 16 13.5 17 14.5 15.5 16 5 15.5 4 15 3 13.5 0

f 2 (s 2

)

NEUQ

i月 月 g(i)需求 需求

1 2

2 3

3 2

4 4

当k=1时, 求f1 ( s1 ) 时

s1 = 0

f 1 ( 0 ) = 第1月初库存为 0时,从第一个月到计划 结束的最低总费用
u1(0)对应的总费用 生产费 = c (u 1 ) 对应的总费用=生产费 对应的总费用

f1(0) = m {C(u1) + f2 (s2 )} in
u (0) 1

k=2

s2 u2
C + E + f3

NEUQ
0 3 4 5 6 2 3 1 4 5 1 2 2 3 4 0 1 3 2 3

18 18.5 16 17 17.5 18 15.5 16.5 17 17.5 15 16 13.5 17 14.5 15.5 16 5
u (0) 1

* u 2 (s 2 )

f 2 (s 2

)

15.5 4

15 3

13.5 0

in 当k=1时, f1(0) = m {C(u ) + f2 (s2 )} 时 1
s1 u1
0 2 3 4 5 21.5 21 21.5 22 21 2

C + f2

u 1* (0 ) = 2 结 :1(0) = 21 论 f * u 3 (2 ) = 0

u 1* (0 )

f 1 (0 )

* u 2 (0 ) = 5
* u 4 (0 ) = 4

最 生 方 : 优 产 案 第个 生 2个 1 月 产 , 第个 生 5 , 2 月 产个 第 个 生 0个 3 月 产 , 第 个 生 4个 4 月 产 , 总 用 21 费 =

k = 4时, f 4 (s 4 ) = min {c (u 4 ) + E ( s 4 )} u
4

= min {c (u 4 ) + E ( s 4 ) + f 5 ( s 5 )}
u4
3

NEUQ

in k = 3时,f3(s3 ) = m ){C(u3 ) + E(s3 ) + f4 (s4 )} u (s
3

m k = 2时, f2 (s2 ) = u (in) {C(u2 ) + E(s2 ) + f3 (s3 )} s
k = 1时, f1(0) = m {C(u1) + f2 (s2 )} in
u (0) 1
2 2

Qs1 = 0 f1(s1 ) = f1(0)= min){C (u1 ) + E ( s1 ) + f 2 (s 2 )} u (s
1 1

生产存储问题的基本方程: 生产存储问题的基本方程:
? ? ? ? ?

fk (sk ) = m {C(uk ) + E(sk ) + fk+1(sk+1 )} k = 4,3, 2,1 in

f 5 (s 5 ) = 0

uk ( sk )

其 sk+1 = sk +uk ? g(k) 中

NEUQ
最短路问题的基本方程: 最短路问题的基本方程:

? f k (s k ) = min uk ? ? f 5 (s 5 ) = 0

{d (s k , u k ) +

f k +1 (s k +1 )} k=4,3,2,1

三、动态规划方法建模基本要求与步骤
建模要素: 建模要素: 1)阶段数 k 阶段数 2)状态变量 sk 状态变量 3)决策变量 uk( sk ) 决策变量 状态转移方程 s k +1 = T (s k , u k ) 4)指标函数 Vk,n 指标函数 5)最优值函数 fk(sk) 最优值函数

NEUQ

NEUQ
DP建模基本要求: 建模基本要求: 建模基本要求 1)所研究的问题必须能够分成几个相互联系的阶 ) 而且在每一个阶段都具有需要进行决策的问题。 段,而且在每一个阶段都具有需要进行决策的问题。 2)在每一阶段都必须有若干个与该阶段相关的状 ) 建模时总是从与决策有关的条件中, 态,建模时总是从与决策有关的条件中,或是从问 题的约束条件中去选择状态变量。 题的约束条件中去选择状态变量。 一般情况下,状态是所研究系统在该阶段可能处 一般情况下, 于的情况或条件

状态的选取必须注意以下几个要点: 状态的选取必须注意以下几个要点:

NEUQ

(a)在所研究问题的各阶段,都能直接或间接确 )在所研究问题的各阶段, 定状态变量的取值(可知性) 定状态变量的取值(可知性) (b)能通过现阶段的决策,使当前状态转移成下 )能通过现阶段的决策, 一阶段的状态(反映过程的演变性 演变性) 一阶段的状态(反映过程的演变性) 即 能够给出状态转移方程 sk +1 = T sk , uk

(

)

(c)状态的无后效性 )状态的无后效性
即以第 k 阶段的状态 s k 为出发点的后部子过程 最优策略应与 s k 之前的过程无关 的

3) 具有明确的指标函数,且阶段指标值可以计算 具有明确的指标函数, 4) 能正确列出最优值函数的递推公式和边界条件

建立DP模型的步骤 建立DP模型的步骤 DP 1、划分阶段 、

NEUQ

划分阶段是运用动态规划求解多阶段决策问题的 第一步, 在确定多阶段特性后, 第一步 , 在确定多阶段特性后 , 按时间或空间先后顺 将过程划分为若干相互联系的阶段。 序 , 将过程划分为若干相互联系的阶段 。 对于静态问 题要人为地赋予“时间”概念,以便划分阶段。 题要人为地赋予“时间”概念,以便划分阶段。 2、正确选择状态变量 、 选择变量既要能确切描述过程演变又要满足无后 效性, 而且各阶段状态变量的取值能够确定。 一般地, 效性 , 而且各阶段状态变量的取值能够确定 。 一般地 , 状态变量的选择是从过程演变的特点中寻找。 状态变量的选择是从过程演变的特点中寻找。 3、确定决策变量及允许决策集合 、 通常选择所求解问题的关键变量作为决策变量, 通常选择所求解问题的关键变量作为决策变量,同 时要给出决策变量的取值范围, 即确定允许决策集合。 时要给出决策变量的取值范围 , 即确定允许决策集合 。

4、确定状态转移方程 、

NEUQ

根据k 阶段状态变量和决策变量,写出k+1阶段状态变 根据 阶段状态变量和决策变量,写出 阶段状态变 量,状态转移方程应当具有递推关系。 状态转移方程应当具有递推关系。 5、确定阶段指标函数和最优指标函数,建立动态规 、确定阶段指标函数和最优指标函数, 划基本方程 阶段指标函数是指第k 阶段的收益,最优指标函数 阶段指标函数是指第 阶段的收益, 是指从第k 阶段状态出发到第n 是指从第 阶段状态出发到第 阶段末所获得收益的最 优值,最后写出动态规划基本方程。 优值,最后写出动态规划基本方程。 以上五步是建立动态规划数学模型的一般步骤。 以上五步是建立动态规划数学模型的一般步骤。由于 动态规划模型与线性规划模型不同, 动态规划模型与线性规划模型不同,动态规划模型没有统 一的模式,建模时必须根据具体问题具体分析, 一的模式,建模时必须根据具体问题具体分析,只有通过 不断实践总结,才能较好掌握建模方法与技巧。 不断实践总结,才能较好掌握建模方法与技巧。

四、动态规划方法应用举例

NEUQ

动态规划常用基本方程: 动态规划常用基本方程:

? f k (sk ) = opt{g k (u k ) + f k +1 (sk +1 )} ? uk ? ? f n+1 (sn+1 ) = 0 ? ? f k (sk ) = opt{g k (u k ) ? f k +1 (sk +1 )} ? uk 或? ? f n+1 (sn+1 ) = 1 ?

k = n, n ? 1,L,2,1

k = n, n ? 1,L,2,1

1、最短路径问题 、

NEUQ

地到D 地要铺设一条煤气管道,其中需经过两级中 从A 地到 地要铺设一条煤气管道 其中需经过两级中 间站,两点之间的连线上的数字表示距离,如图所示。 间站,两点之间的连线上的数字表示距离,如图所示。 问应该选择什么路线,使总距离最短? 问应该选择什么路线,使总距离最短?
3 2 A 4 B2 B1 1 2 3 1 C3 C2 4 3 3 C1 1 D

3 2 A 4 B2 B1 1 2 3 1 3

C1 C2 4 C3 3

NEUQ
1 D

解:整个计算过程分三个阶段,从最后一个阶段开始。 整个计算过程分三个阶段, 第一阶段( 第一阶段(C →D): C 有三条路线到终点 。 ): 有三条路线到终点D 显然有 f1 (C1 ) = 1 ; f1(C2 ) = 3 ; f1 (C3 ) = 4

3 2 A 4 B2 B1 1 2 3 1 3

C1 C2 4 C3 3

NEUQ
1 D

第二阶段(B →C): B 到C 有六条路线。 有六条路线。 第二阶段( ):

d( B1,C1 ) + f1 (C1 ) 3+1 f2 ( B1 ) = min d( B1,C2 ) + f1 (C2 ) = min 3+3 d( B1,C3 ) + f1 (C3 ) 1+4 4 = min 6 = 4 (最短路线为 1→C1 →D) 最短路线为B 最短路线为 5

3 2 A 4 B2 B1 1 2 3 1 3

C1 C2 4 C3 3

NEUQ
1 D

d( B2,C1 ) + f1 (C1 ) 2+1 f2 ( B2 ) = min d( B2,C2 ) + f1 (C2 ) = min 3+3 d( B2,C3 ) + f1 (C3 ) 1+4 3 = min 6 = 3 (最短路线为 2→C1 →D) 最短路线为B 最短路线为 5

3 2 A 4 B2 B1 1 2 3 1 3

C1 C2 4 C3 3

NEUQ
1 D

第三阶段( A → B ): A 到B 有二条路线。 有二条路线。 第三阶段(

f3(A)1 = d(A, B1 )+ f2 ( B1 ) =2+4=6 + + = f3 (A)2 = d(A, B2 )+ f2 ( B2 ) =4+3=7 + + = + ∴ f3 (A) = min d(A, B1 )+ f2 ( B1 ) = min{6,7}=6 { } d(A, B2 )+ f2 ( B2 ) + (最短路线为 最短路线为A→B1→C1 →D) 最短路线为

NEUQ
3 2 A 4 B2 B1 1 2 3 1 C3 C2 4 3 3 C1 1 D

最短路线为

A→B1→C1 →D

路长为 6

2、资源分配问题 、

NEUQ

某公司有资金a万元,拟投资于 个项目 已知对第i个项 个项目, 某公司有资金 万元,拟投资于n个项目,已知对第 个项 万元 目投资x 万元,收益为g 目投资 i万元,收益为 i (xi),问应如何分配资金可使总收 , 益最大? 益最大? 解:阶段k=1,2, …,n 阶段 状态变量sk :在第k阶段时可以用于投资 在第 阶段时可以用于投资 到第n个项目的资金数 第k到第 个项目的资金数 到第 决策变量uk

:第k个项目的投资额 个项目的投资额
Uk = {uk | 0 ≤ uk ≤ sk }

状态转移方程: 状态转移方程: sk+1 = sk -uk 指标函数Vk,n 最优值函数

∑ g (u )
i=k i i

n

求1(a) f

f k ( sk ) 第k至第 个项目的最大总收益 至第n个项目的最大总收益 至第

NEUQ

建立递推公式: 建立递推公式:

f k (s k

) = 0max s { ≤u ≤
k k

g k (u k

)+

f k + 1 (s k + 1

)}

边界条件: 边界条件:

f n +1 (s n +1 ) = 0

k=n,n-1, …,2,1

资源分配问题的动态规划基本方程: 资源分配问题的动态规划基本方程:

? f k (sk ) = max {g k (u k ) + f k +1 (sk +1 )} 0≤uk ≤ sk ? ? f n+1 (sn+1 ) = 0

k = n, n ? 1,L,2,1

资源分配问题示例
某有色金属公司拟拨出50万元对所 某有色金属公司拟拨出 万元对所 属三家冶炼厂进行技术改造, 属三家冶炼厂进行技术改造,若以 十万元为最少分割单位, 十万元为最少分割单位,各厂收益 与投资的关系如下表: 与投资的关系如下表:

阶段 k=1,2,3 , , 决策变量 uk:

NEUQ

给工厂k的投资额 给工厂 的投资额

0 ≤ uk ≤ sk

状态变量 sk: 在第k阶段时可供工 在第 阶段时可供工 到工厂3分配的 厂k到工厂 分配的 到工厂 资金数 状态转移方程:

工厂 1 投资额
1 2 3 4 5 4.5 7 9 10.5 12

2

3

2 4.5 7.5 11 15

5 7 8 10 13

sk+1 = sk -uk g k (uk)=给工厂 投资 给工厂k投资 十万元) uk (十万元)的收益
指标函数 Vk,n = ∑gi (ui )
i=k 3

问:对三个工厂如何分配, 对三个工厂如何分配, 才能使总收益达到最大? 才能使总收益达到最大?

fk( sk ) 在工厂 ,可供分配的资金数为sk时, =在工厂 在工厂k,
投资工厂k至工厂 所得的最大总收益 投资工厂 至工厂3所得的最大总收益 至工厂
= max {g k (u uk 0 ≤ u k ≤ sk
k

NEUQ

)+

f k + 1 (s k + 1

)}
工厂 1 投资额
1 2 3 4 5 4.5 7 9 10.5 12 2 4.5 7.5 11 15 5 7 8 10 13 2 3

求 f 1( 5 ) 基本方程: 基本方程:

? f k (sk ) = max{gk (uk ) + f k +1 (sk +1 )} 0≤uk ≤sk ? k = 3,2,1 ? f 4 (s 4 ) = 0 f 3 (s3 ) = max {g 3 (u3 )} k=3
0≤u3 ≤ s3

s3
u3

0 0 0 0

1 1 5 1

2 2 7 2

3 3 8 3

4 4 10 4

5 5 13 5

f 3 ( s3 )
u
* 3

k=2

f 2 (s2 ) = max {g 2 (u2 ) + f 3 (s3 )}
0≤u2 ≤s2

NEUQ
工厂 1 投资额
1 2 3 4 5 4.5 7 9 10.5 12 2 4.5 7.5 11 15 5 7 8 10 13 2 3

sk+1 = sk -uk
s3
u3

f 3 ( s3 )
u
* 3

0 0 0 0

1 1 5 1

2 2 7 2

3 3 8 3

4 4 10 4

5 5 13 5

s2
u2 g2 + f3
f 2 (s2 )
u
* 2

4 5 0 1 2 3 0 0 1 0 1 2 0 1 2 3 0 1 2 3 4 0 1 2 3 4 5 0 5 2 7 7 4.5 8 9 9.5 7.5 10 10 11.512.511 13 12 12.514.5 16 15 12.5 16 5 7 0 9.5 3 2 4 0 0 0或1 或

f1 (s1 ) = max{g1 (u1 ) + f 2 (s2 )}
0≤u1 ≤ s1

工厂 1 投资额
1 4.5 7 9 10.5 12

2

3 NEUQ 5 7 8 10 13

k=1

2 4.5 7.5 11 15

sk+1 = sk -uk

2 3 4 5

s2
u2 g2 + f3
f 2 (s2 )
u
* 2

0 0 0 0 0

4 5 2 3 0 1 0 1 2 0 1 2 3 0 1 2 3 4 0 1 2 3 4 5 5 2 7 7 4.5 8 9 9.5 7.5 10 10 11.512.511 13 12 12.514.5 16 15 12.5 16 5 7 9.5 3 2 4 0 0或1 或 1 5

s1
u1
0 1 2

最大总收益: 最大总收益:
3 4 5

g1(u1) + f2 (s2 ) 16 17 16.5 16 15.5 12 17 f1 ( s1 )

f 1 (5) = 17 (十万元)
最优策略: 最优策略: * * * u1 = 1 , u 2 = 3 , u 3 = 1

u1

*

1

NEUQ
3、复合系统工作可靠性问题
系统由n个部件串联组成,每一个部件上装有备用件, 系统由 个部件串联组成,每一个部件上装有备用件,部件 个部件串联组成 i(i=1,2, …,n)上装有 i个备用元件时,正常工作的概率为 i 上装有x 上装有 个备用元件时,正常工作的概率为p )。设装一个 部件的设备元件费用为c 重量w 设装一个i部件的设备元件费用为 ( xi )。设装一个 部件的设备元件费用为 i ,重量 i为, 要求总费用不超过C,总重量不超过W, 要求总费用不超过 ,总重量不超过 ,问如何选择各个部 件的备用元件数,使整个系统的工作可靠性最大? 件的备用元件数,使整个系统的工作可靠性最大?

= Π pi (ui )
n i=k

设A---整个系统正常工作,Ai—部件i正常工作NEUQ A = A A LA , 1 2 n

则 ( A) = P( A )P( A )L ( A ) = Π pi ( xi ) P P n 1 2
n
n

数 模 为 求 ax P = Π pi ( xi ) 学 型 : m
满足:

i= 1

∑c x
i= 1
n

n

i= 1

i

i

≤C
≤W
非线性规 划问题

∑w x
1 i= i

i

xi ≥ 0且 整 为 数

NEUQ
个部件=n个阶段 解: n个部件 个阶段 个部件 部件k上所装的备用元件数 决策变量uk = 部件 上所装的备用元件数xk 状态变量: 状态变量:

sk =第k个到第 个部件可使用的总费用 个到第n个部件可使用的总费用 个到第 yk =第k个到第 个部件容许的总重量 个到第n个部件容许的总重量 个到第
状态转移方程: 状态转移方程: ?sk+1 = sk ?ckuk 指标函数Vk,n

? ? yk+1 = yk ? w uk k
n i=k

= Π pi (ui )

NEUQ

在部件k, 最优指标函数fk(sk, yk )= 在部件 ,可使用 的总费用为 sk,总重量为 yk 时,从部件k 从部件 到部件n的系统工作可靠性的最大值 到部件 的系统工作可靠性的最大值
求 f 1 (C , W

)

复合系统工作可靠性的动态规划基本方程为 复合系统工作可靠性的动态规划基本方程为: 基本方程

? u k ∈U K ? f (s , y ) = 1 ? n +1 n +1 n +1

f k (s k , y k ) = max {p k (u k ) f k +1 (s k +1 , y k +1 )} k = n, n ?1,L,2,1
与问 题无 关

4、背包问题

NEUQ

有一个徒步旅行者,其可携带物品重量的限度为 公斤, 有一个徒步旅行者,其可携带物品重量的限度为a 公斤,设有 n 种物品可供他选择装入包中。已知每种物品的重量及使用价值 种物品可供他选择装入包中。 作用),问此人应如何选择携带的物品(各几件), ),问此人应如何选择携带的物品 ),使所起 (作用),问此人应如何选择携带的物品(各几件),使所起 作用(使用价值)最大? 作用(使用价值)最大?
物品 重量(公斤/ 重量(公斤/件) 每件使用价值

1 a1 c1

2 a2 c2

… … …

j aj cj

… … …

n an cn

这就是背包问题。类似的还有工厂里的下料问题、 这就是背包问题。类似的还有工厂里的下料问题、运输中的 货物装载问题、人造卫星内的物品装载问题等。 货物装载问题、人造卫星内的物品装载问题等。

NEUQ
为第j 种物品的装件数(非负整数)则问题的数学模型如下: 设xj 为第 种物品的装件数(非负整数)则问题的数学模型如下:

max Z = ∑ c j x j
j =1

n

?n ?∑ a j x j ≤ a ? j =i ? x ≥ 0且为整数 ( j = 1.2.L.n) ? j
用动态规划方法求解, 用动态规划方法求解,令 fx(y) = 总重量不超过 y 公斤,包中只装有前 种物品时的最大 公斤,包中只装有前k 使用价值。 使用价值。 其中y , 其中 ≥0, k =1,2, …, n 。所以问题就是求 fn(a)

其递推关系式为: 其递推关系式为:

f k ( y ) = max
0≤ xk ≤

{c k x k y
ak

+ f k ? 1 ( y ? a k x k )}

NEUQ

其中

2 ≤ k ≤ n
? y ? f1 ( y ) = c1 ? ?a ? , ? ? 1? ? y ? 其中 ? ? a ? 表示不超过 ? ? 1? ? ? y ?? ? x1 = ? ? ? a ?? ? 1 ?? ? y 的最大整数 a1

当 k=1 时,有:

求下面背包问题的最优解

NEUQ

max Z = 8 x1 + 5 x 2 + 12 x 3 ? 3 x1 + 2 x 2 + 5 x 3 ≤ 5 ? ? x1 , x 2 , x 3 ≥ 0且为整数
解:a=5 ,问题是求 f3(5) =

物品 重量(公斤) 重量(公斤) 使用价值

1 3 8

2 2 5

3 5 12

f 3 ( 5 ) = max
0≤ x3 ≤ x 3 整数

{ 12 x 3 5
a3

+ f 2 ( 5 ? 5 x 3 )}

f 3 (5) = max { 12 x 3 + f 2 (5 ? 5 x 3 )}
0≤ x 3 ≤

NEUQ

=max { 12 x 3 + f 2 (5 ? 5 x 3 )}
0≤ x 3 ≤

5 a3 x 3整数

=max{ 12 x 3 + f 2 (5 ? 5 x 3 )}
x 3 0, = 1

5 5 x 3整数

? ? =max ?0 + f 2 (5), 12 + f 2 (0)? ( x 3 =1 ) ? ( x3 = 0 ) ?

f 2 ( 5) =

0≤ x 2 ≤

max { 5 x 2 + 5

f 1 (5 ? 2 x 2 )}

NEUQ

=max { 5 x 2 + f 1 (5 ? 2 x 2 )}
0≤ x 2 ≤

a2 x 2整数

= max { 5 x 2 + f 1 (5 ? 2 x 2 )}
x 2 0,, 2 = 1

5 2 x 2整数

? ? =max ?0 + f 1 (5), 5 + f 1 ( 3), 10 + f1 (1) ? ( x 2 =1 ) ( x2 = 2) ? ( x2 = 0 ) ?

NEUQ
f 2 (0) = max { 5 x 2 + f1 (0 ? 2 x 2 )}
0≤ x 2 ≤

=max { 5 x 2 + f1 (0 ? 2 x 2 )}
0≤ x 2 ≤

0 a2 x 2整数

=max{ 5 x 2 + f1 (0 ? 2 x 2 )}
x2 0 =

0 2 x 2整数

? ? =max ?0 + f1 (0) ? = f1 (0) ? ( x2 = 0 ) ?

? ? ∴ f 2 (5) = max?0 + f1 (5), 5 + f1 (3), 10 + f1 (1) ? ( x2 =1) ( x2 = 2 ) ? ( x2 = 0 ) ? = max{8, 5 + 8, 10} = 13 ( x1 = 1, x2 = 1)

5 f 1 (5) = c1 x1 = 8 × = 8 3 3 f 1 ( 3) = c1 x1 = 8 × = 8 3 1 f 1 (1) = c1 x1 = 8 × = 0 3 0 f 1 (0) = c1 x1 = 8 × = 0 3

( x1 = 1) ( x1 = 1) ( x1 = 0) ( x1 = 0)

NEUQ

NEUQ ? ? f2 (0) max?0 + f1 (0) ? = f1 (0) = 0 ( x1 = 0, x2 = 0) = ? ( x2 =0) ?

? ? ∴ f 3 ( 5 ) max ? 0 + f 2 ( 5 ), 12 + f 2 ( 0 ) ? = ( x3 =1) ? ( x3 =0) ? 12 + 0 } = max { 0 + 13 , = 13 ( x 1 = 1 , x 2 = 1 , x 3 = 0 )
所以, =(1 ),最优值为 所以,最优解为 X=( . 1 . 0),最优值为 Z = 13。 =( ), 。

NEUQ
5、机器负荷分配问题
一种机器能在高低两种不同的负荷状态下工作。 一种机器能在高低两种不同的负荷状态下工作。设机器在 高负荷下生产时,产量函数为 其中u 高负荷下生产时,产量函数为P1=8u1,其中 1为在高负荷 状态下生产的机器数目,年完好率为 状态下生产的机器数目,年完好率为a=0.7,即到年底有 ,即到年底有70 %的机器保持完好。在低负荷下生产时,产量函数为 的机器保持完好。在低负荷下生产时, P2=5u2,其中 2为在低负荷状态下生产的机器数目,年完 其中u 为在低负荷状态下生产的机器数目, 好率为b=0.9。设开始生产时共有1000台完好的机器,请问 。设开始生产时共有 台完好的机器, 好率为 台完好的机器 每年应该如何把完好机器分配给高、低两种负荷下生产, 每年应该如何把完好机器分配给高、低两种负荷下生产, 才能使得5年内生产的产品总产量最高。 才能使得 年内生产的产品总产量最高。 年内生产的产品总产量最高

NEUQ
解 建立动态规划模型: 建立动态规划模型: 分为5个阶段 每个阶段为1年 设状态变量s 个阶段, 分为 个阶段,每个阶段为 年。设状态变量 k表示在第 k阶段初拥有的完好机器数目;k=1,2,3,4,5。 阶段初拥有的完好机器数目; 阶段初拥有的完好机器数目 。 决策变量x 表示第k阶段中分配给高负荷状态下生产的 决策变量 k表示第 阶段中分配给高负荷状态下生产的 机器数目; 机器数目;k=1,2,3,4,5。显然 k-xk为分配给低负荷状态下生 。显然s 产的机器数目。 产的机器数目。 状态转移方程为 sk +1 = 0.7xk + 0.9(sk ? xk ) 阶段指标 rk(sk,xk)=8xk+5(sk-xk) 最优指标函数 f (s ) = max 8x +(s ? x ) + f (s 5
k k

0 ≤ xk ≤ sk

{

k

k

k

k +1

k +1

)}

其中k=1,2,3,4,5。 。 其中
f6(s6)=0。

NEUQ

阶段: 第5阶段: 阶段 因为f 因为 5(s5)是x5的线性单调增函数,故有 5* =s5, 是 的线性单调增函数,故有x 于是有f 于是有 5(s5)=8s5。 阶段: 第4阶段: 阶段 f 4 ( s4 ) = max {8 x4 + 5( s4 ? x4 ) + f 5 ( s5 )}

= max {8 x4 + 5( s4 ? x4 ) + 8s5 } = max {8 x4 + 5( s4 ? x4 ) + 8[0.7 x4 + 0.9( s4 ? x4 )]} = max { .6 x4 + 12.2( s4 ? x4 )} 13
0 ≤ x4 ≤ s 4 0 ≤ x4 ≤ s 4 0 ≤ x4 ≤ s 4

0 ≤ x4 ≤ s 4

NEUQ
同样地, 同样地,f4(s4)是x4的线性单调增函数,有x4*=s4 , 是 的线性单调增函数, f4(s4)=13.6s4。 对前几个阶段依次类推, 对前几个阶段依次类推,可得 f3(s3)=17.5s3, f2(s2)=20.75s2, f1(s1)=23.72s1。 因为期初共有完好机器1000台,故s1=1000。有f1(s1)=23.72s1 因为期初共有完好机器 台 。 * x2 x1* = 0 , = 0 年最大的产量为23720台。得最优解为 =23720,即5年最大的产量为 , 年最大的产量为 台 * * * x3 = s 3 , = s 4 , = s 5 。 x4 x5 这意味着前两年应把年初完好机器完全投入低负荷生产, 这意味着前两年应把年初完好机器完全投入低负荷生产, 后三年应把年初完好机器完全投入高负荷生产。 后三年应把年初完好机器完全投入高负荷生产。

NEUQ
下一步工作是确定每年初的状态, 下一步工作是确定每年初的状态,按照从前向后 的顺序依次计算出每年年初完好的机器数目。 的顺序依次计算出每年年初完好的机器数目。已知 s1=1000,根据状态转移方程,有: 根据状态转移方程, 根据状态转移方程
* * s 2 = 0.7 x1 + 0.9( s1 ? x1 ) = 0.9s1 = 900
* * s3 = 0.7 x 2 + 0.9( s 2 ? x 2 ) = 0.9 s 2 = 810 * * s 4 = 0.7 x3 + 0.9( s3 ? x3 ) = 0.7 s3 = 567

* * s5 = 0.7 x4 + 0.9( s4 ? x4 ) = 0.7 s4 = 397

NEUQ
上面所讨论的最优策略过程,初始端状态 上面所讨论的最优策略过程,初始端状态s1=1000 台是固定的,终点状态s 没有要求。 台是固定的,终点状态 6没有要求。这种情况下得到 最优决策称为初始端固定终点自由的最优策略。 最优决策称为初始端固定终点自由的最优策略。 如果终点附加一定的条件,则问题就称为“ 如果终点附加一定的条件,则问题就称为“终端 固定问题” 例如,规定在第5年度结束时仍要保持 固定问题”。例如,规定在第 年度结束时仍要保持 500台机器完好(而不是278台),应如何安排生产才 台机器完好(而不是 台),应如何安排生产才 台机器完好 能使得总产量最大? 能使得总产量最大? 下面来分析: 下面来分析: 根据终点条件有 可得

s6 = 0.7 x5 + 0.9( s5 ? x5 ) = 500 x5 = 4.5s5 ? 2500

NEUQ
显然,由于固定了终点的状态, 显然,由于固定了终点的状态,x5的取值受到了 约束。 约束。因此有 f 5 ( s5 ) = max{8(4.5s5 ? 2500) + 5( s5 ? 4.5s5 + 2500)}

= 18.5s5 ? 7500 类似, 类似,
f 4 ( s 4 ) = max {8 x4 + 5( s 4 ? x4 ) + f 5 ( s5 )} = max {8 x4 + 5( s4 ? x4 ) + 18.5s5 ? 7500} = max {21.7 s 4 ? 0.7 x4 ? 7500}
0≤ x 4 ≤ s 4 0≤ x 4 ≤ s 4 0 ≤ x4 ≤ s 4

* 容易解得 x 4 = 0 ,f4(s4)=21.7s4-7500。 。

NEUQ
* * * x3 = x2 = x1 = 0 依次类推,得 依次类推,

f3(s3)=24.5s3-7500 f2(s2)=27.1s2-7500 f1(s1)=29.4s1-7500 再采用顺序方法递推计算各年的状态, 再采用顺序方法递推计算各年的状态,有 s1=1000, ,
* * s 2 = 0.7 x1 + 0.9( s1 ? x1 ) = 0.9 s1 = 900
* * s3 = 0.7 x2 + 0.9( s 2 ? x2 ) = 0.9 s 2 = 810 * * s4 = 0.7 x3 + 0.9( s3 ? x3 ) = 0.7 s3 = 729 * * s5 = 0.7 x4 + 0.9( s4 ? x4 ) = 0.7 s4 = 656

NEUQ

可见,为了使终点完好的机器数量增加到 可见,为了使终点完好的机器数量增加到500台, 台 需要安排前四年中全部完好机器都要投入低负荷生产, 需要安排前四年中全部完好机器都要投入低负荷生产, 且在第5年 也只能全部投入高负荷。 且在第 年,也只能全部投入高负荷。 相应的最优指标为 f1(s1)=29.4s1-7500=21900。 = 。 可以看到,因为增加了附加条件,总产量f1(s1)要 可以看到,因为增加了附加条件,总产量 要 比终点自由情况下的产量要低。 比终点自由情况下的产量要低。

NEUQ
7、设备更新问题

一台设备的价格为P,运行寿命为n年,每年 一台设备的价格为 ,运行寿命为 年 的维修费用是设备役龄的函数,记为 的维修费用是设备役龄的函数,记为C(t),新设备 , 的役龄为t=0。 的役龄为 。旧设备出售的价格是设备役龄的函 年末, 数,记为S(t)。在n年末,役龄为 的设备残值为 记为 。 年末 役龄为t的设备残值为 R(t)。现有一台役龄为T的设备,在使用过程中, 。现有一台役龄为 的设备 在使用过程中, 的设备, 使用者每年都面临“继续使用” 使用者每年都面临“继续使用”或“更新”的策 更新” 略,

运行年份; 阶段 k :运行年份; 状态变量 x k :设备的役龄 t ; 决策变量 d k : e 新 ?R (R place)更 dk = ? eep 续 用 ?K (K )继 使 状态转移方程: 状态转移方程:

NEUQ

1 dk = R ? xk+1 = ? ?xk +1 dk = K
阶段指标: 阶段指标 :
?P+C(0) ?S(xk ) vk = ? C ? (xk ) ?P+C(0) ?S(t) =? C ? (t) dk = R dk = K dk = R dk = K

NEUQ
递推方程:

?P+C(0) ?S(xk ) + fk+1(xk+1) fk (xk ) = m ? in ?C(xk ) + fk+1(xk+1) ) ?P+C(0) ?S(t) + fk+1(1 =m ? in ) ?C(t) + fk+1(t +1
终端条件: fn(t)=-R(t)

dk = R dk = K dk = R dk = K

NEUQ
设具体数据如下: 设具体数据如下:
T C(t) S(t) R(t) 0 1 2 3 4 5 6 10 13 20 40 70 100 100 -- 32 21 11 5 0 0 -- 25 17 8 0 0 0 7 -0 0

=5, =2, 且 n =5 , T =2 , P =50
由上表开始,终端条件为: 由上表开始,终端条件为: (1)=-25, (2)=-17, (3)=f6 (1)=-25,f6 (2)=-17,f6(3)=-8 f6 (4)=f6 (5)=f6 (6)=f6(7)=0

对于 k =5:

NEUQ

) ?P+C(0) ?S(t) + f6(1 ? f5(t) = m ? in ? ) ?C(t) + f6(t +1 ?

d5 = R d5 = K

) ) ?P+C(0) ?S(1 + f6(1 ? ?50+10?32+(?25)? f5(1 = m ? ) in in ?=m ? ? C(1 + f6(2) ) 13+(?17) ? ? ? ? ?3? = m ? ? = ?4, in ??4?
* d5 = K

) ?P+C(0) ?S(2) + f6(1 ? ?50+10?21+(?25)? f5(2) = m ? in in ?=m ? ? ?20+(?8) ? ?C(2) + f6(3) ? 14 ? ? = m ? ? =12, in 12 ? ?
* d5 = K

) 11+(?25 ?P+C(0) ?S(3) + f6(1 ? ?50+10?NEUQ )? f5(3) = m ? in in ? ?=m ? ?40+0 ? ?C(3) + f6(4) ? ?24? * = m ? ? = 24, in d5 = R ?40? ) ?P+C(0) ?S(4) + f6(1 ? ?50+10?5+(?25)? in in f5(4) = m ? ?=m ? ? ?70+0 ? ?C(4) + f6(5) ?

) ?P+C(0) ?S(5) + f6(1 ? ?50+10?0+(?25)? f5(5) = m ? in in ?=m ? ? 100 ? +0 ? ?C(5) + f6(6) ? ? 35 ? = m ? ? =35, in 100 ? ? d =R
* 5

?30? = m ? ? = 30, in ?70?

* d5 = R

NEUQ
) ?P+C(0) ?S(6) + f6(1 ? ?50+10?0+(?25)? f5(6) = m ? in in ?=m ? ? 100 ? +0 ? ?C(6) + f6(7) ? ? 35 ? = m ? ? =35, in 100 ? ?
* d5 = R

( 1? P C0 ? + ( )?S t)+f5( ) in f4( )=m ? t ? Ct t 1 ? ( )+f5( + ) ?

d =R 4 d =K 4

P ( ) 1 1 5 1 2 4 ? +C 0 ?S( )+ f5( )? ? 0+ 0?3 +(? )? f4( ) =m ? 1 in in ?=m ? ? C1 + f5(2 () ) 1 + 2 3 1 ? ? ? ? 2? ? 4 =m ? ?=2 , in 4 2? ? 5 d* =R 4

) ?P + C(0) ? S(2) + f5 (1 ? f4 (2) = m ? in ? C(2) + f5 (3) ? ? ?50 +10 ? 21 + (?4)? in =m ? ? ?20 + 24 ? ?35? = m ? ? = 35 , in ?44?
* d4 = R

NEUQ

) 1 ?P+C(0) ?S(3 + f5( )? f4(3 = m ? ) in ? C(3 + f5(4) ) ? ? ?50+10?11+(?4)? =m ? in ? ?40+30 ? ?45? = m ? ? = 45, in ?70?
* d4 = R

NEUQ
1 ?P+C(0) ?S(4) + f5( )? f4(4) = m ? in ? C(4) + f5(5 ) ? ? 50 4 ? +10?5+(? )? in =m ? ? 70+35 ? ? ? 51 ? = m ? ? = 51, in 105 ? ?
* d4 = R

1 ?P+C(0) ?S(5) + f5( )? f4(5) = m ? in ? ?C(5) + f5(6) ? ?50+10?0+(?4)? =m ? in ? 100+35 ? ? ?56 ? = m ? ? = 56, in 135 ? ?
* d5 = R

NEUQ
对于 k =3:

?P+C(0) ?S(t) + f4(1)? f3(t) = m ? in ? ?C(t) + f4(t +1) ?
) ) ?P+C(0) ?S(1 + f4(1 ? f3(1 = m ? ) in ? ) ?C(1 + f4(2) ? ?50+10?32+24? in =m ? ? 13 ? +35 ? ?52? = m ? ? = 48, in ?48?
* d3 = K

d3 = R d3 = K

) ?P+C(0) ?S(2) + f4(1 ? ?50+10?21+24? f3(2) = m ? in in ?=m ? ? C(2) + f4(3) 20+45 ? ? ? ? ?63? = m ? ? = 63, in ?65?
* d3 = R

NEUQ

) 1 50 ?P+C(0) ?S(3 + f4( )? ? +10?11+24? ) in =m ? in f3(3 = m ? ? ? ) C(3 + f4(4) 40+51 ? ? ? ? 73 ? ? * = m ? ? = 73, in d3 = R ?91 ?

) ?P+C(0) ?S(4) + f4(1 ? ?50+10?5+24? f3(4) = m ? in in ?=m ? ? C(4) + f4(5) 70+56 ? ? ? ? ? 79 ? = m ? ? = 79, in 126 ? ?
* d3 = R

对于 k=2:
d2 = R 1 ?P+C(0) ?S(t) + f3( )? f2(t) = m ? in ? C(t) + f3(t +1 ) ? ? d2 = K 1 1 ?P+C(0) ?S( ) + f3( )? f2( ) = m ? 1 in ? 1 C( ) + f3(2) ? ? 50 ? +10?32+48? in =m ? ? 13+63 ? ? 76 ? ? * in d2 = K 或 d2 = R 者* = m ? ? = 76, 76 ? ?

NEUQ

1 ?P+C(0) ?S(2) + f3( )? ?50+10?21+48? f2(2) = m ? in in ?=m ? ? C(2) + f3(3 ) 20+73 ? ? ? ? 87 ? ? = m ? ? =87, in ?93?
* d2 = R

) ?P+C(0) ?S(3) + f3(1 ? ?50+10?11+48? NEUQ ? in in f2(3) = m ? ?=m ? ?40+79 ? ?C(3) + f3(4) ? ?97 ? = m ? ? = 73, in 97 119 ? ?
对于 k =1:
* d2 = R

) ?P+C(0) ?S(t) + f2(1 ? f1(t) = m ? in ? ) ?C(t) + f2(t +1 ?

d1 = R d1 = K

1 ?P+C(0) ?S(2) + f2( )? ?50+10?21+76? in in f1(2) = m ? ?=m ? ? ) ?20+97 ? ?C(2) + f2(3 ? 115 ? ? = m ? ? =115, in 117 ? ?
* d1 = R

由以上计算可知,本问题有两个决策, 由以上计算可知,本问题有两个决策,它们 对应的最小费用都是115。 对应的最小费用都是 。
这两个决策是

NEUQ

年份

1

2

3

4

5

决策 1 更新 更新 继续 更新 继续 决策 2 更新 继续 更新 更新 继续

例(季节工问题)某工厂的生产任务随季节波动,为降 季节工问题 方案2: 方案 : 255 )某工厂的生产任务随季节波动, NEUQ 245 245 245 255 低成本宜用季节临时工, 2 低成本宜用季节临时工,但熟练的生产工人临时难以 总费用: ×102 +[200×10 +2000×25] × × 总费用培训新手费用又高,各季节工人需用量如下表 200× 聘到, : 聘到,培训新手费用又高, +2000×5 +2000×45 =190000 × × 所示,每季节超过需用量聘用,每人浪费2000元, 所示,每季节超过需用量聘用,每人浪费 元 聘用或解聘费为200元乘上两个季节聘用人数之差的 聘用或解聘费为 元乘上两个季节聘用人数之差的 平方,问厂长一年中应如何聘用工人可使总花费最小? 平方,问厂长一年中应如何聘用工人可使总花费最小? 假定工资按实际工作时间计算, (假定工资按实际工作时间计算,则聘用人数可为分 数)

季度i 季度







冬 200

春 255

需用量g 需用量 k 255 220 240

方案1: 方案 : 255 220 240 200 255 总费用: 总费用: ×552 +200×352 +200×202 +200×402 200× × × × =1249000

已知:每季节超过需用量聘用,每人浪费2000元,聘用 NEUQ 和解聘费为200元乘上两个季节聘用人数之差的平方 3 4 阶段1 2
季度i 春 夏 秋 冬 200 春 255 需用量gk 255 220 240

求f1(255)

解:k=1,2,34 ,状态变量sk—第k-1季度聘用人数 s1=255 ,220≤s2≤255 ,240≤s3≤255 ,200≤s4≤255 255 255 255 决策变量uk—第k季度聘用人数 gk≤uk≤255 s 状态转移方程: k+1 = uk fk(sk)=第k-1季度聘用人数为sk人时,第k季度到 第4季度的最小总费用 =min{ 200(uk –uk-1)2 +2000(uk –gk) +fk+1(sk+1) } =min{ 200(uk –sk)2
gk≤uk≤255 gk≤uk≤255

+2000(uk –gk) +fk+1(uk) }

基本方程:

NEUQ

fk(sk)= min{200(uk –sk)2 +2000(uk –gk) +fk+1(uk) } ? gk≤uk≤255 ? ? k=4,3,2,1 ? f (s )=0 5 ? 5 求f1(255) 当k=4时 ,200≤s4≤255 f4(s4)= min{ 200(u4 –s4)2 +2000(u4 –g4) }
g4≤u4≤255

=200(255 –s4)2 u*4=255 当k=3时 ,240≤s3≤255 f3(s3)= min{200(u3 –s3)2 +2000(u3 –g3) +f4(u3) }
g3≤u3≤255

=min{200(u3 –s3)2 +2000(u3 –200) +200(255 –u3)2 }
200≤u3≤255

当k=3时 ,240≤s3≤255 f3(s3) =min{ 200(u3 –s3)2 +2000(u3 –200) +200(255 –u3)2 }
200≤u3≤255
2

NEUQ

令h = 200(u3 ? s3 ) + 2000(u3 ? 200) + 200(255 ? u3 )

2

u3 ∈ [200,255]

dh 则 = 400(u3 ? s3 ) + 2000? 400(255? u3 ) = 800u 3 ? 400 s3 ? 10000 du3 d 2h dh 1 令 = 0 得u3 = s3 + 125 且 2 = 800> 0 du3 2 du3

1 即u 3 = s 3 + 125为最小值点 2

所以f3(s3)= 200 125 ? 1 2 s3
2

(

)

2

= 50(250 ? s3 ) + 1000(s3 ? 150) + 50(260 ? s3 )
1 u 3 * = s 3 + 125 2

+ 2000 1 s3 ? 75 + 200 130 ? 1 s3 2 2
2

(

)

(

)

2

s 已知: 状态转移方程: k+1 = uk NEUQ fk(sk)= min{200(uk –sk)2 +2000(uk –gk) +fk+1(uk) }
gk≤uk≤255
2 2 = f3(s3) 50(250 ? s3 ) + 1000(s3 ? 150) + 50(260 ? s3 )

当k=2时 ,220≤s2≤255 } f2(s2)= min{200(u2 –s2)2 +2000(u2 –g2) +f3(u2) s =
g2≤u2≤255 =min{ 200(u2 –s2)2 +2000(u2 –240) +f (u ) } 3 2 240≤u2≤255 240≤u2≤255

=min{ 300u 2 2 + 200s2 2 ? (400s2 + 48000)u 2 + 5875000}

当k=2时 ,220≤s2≤255 NEUQ =min{ 300u 2 2 + 200s 2 2 ? (400s 2 + 48000)u 2 + 5875000} f2(s2)
令h = 300u2 + 200s2 ? (400s2 + 48000)u2 + 5875000 u 2 ∈ [240,255]
2 2

240≤u2≤255

dh = 600u 2 ? 400s 2 ? 48000 du2

dh 令 =0 du 2

2 得 u 2 = s 2 + 80 3

2 且 2 = 600 > 0 即u 2 = s 2 + 80为最小值点 3 du2

d 2h

所以f2(s2)=
2 2 2 2 300( s2 + 80) + 200s 2 ? (400s2 + 48000)( s2 + 80) + 5875000 3 3 2 200 2 , u 2 * = s 2 + 80 = s 2 ? 32000 s 2 + 3955000 3 3

s 状态转移方程: k+1 = uk 已知: NEUQ fk(sk)= min{200(uk –sk)2 +2000(uk –gk) +fk+1(uk) }
gk≤uk≤255 200 2 = s 2 ? 32000 s 2 + 3955000 f2(s2) 3

当k=1时,s1=255 f1(255)= min{ 200(u1 –s1)2 +2000(u1 –g1) +f2(u1) }
g1≤u1≤255 =min{ 200(u1 –255)2 +2000(u1 –220) + 200 u1 2 ? 32000u1 + 3955000 } 3 220≤u1≤255 1600 400 dh = u1 ? 132000 = 400(u1 ? 255) + 2000 + u1 ? 32000 3 3 du1 dh d 2 h 1600 令 = 0 得u1 = 247.5 且 = > 0即u1 = 247.5为最小值点 2 du1 3 du1 u1 * = 247.5 f1(255)=185000

s 状态转移方程: k+1 = uk f4(s4)= 200(255 –s4)2 u*4=255
f 3 (s3 ) = 50(250 ? s3 )2 + 1000(s3 ? 150) + 50(260 ? s3 )2
= f2(s2) 200 2 s2 3

NEUQ

1 u 3 * = s 3 + 125 2 2 u 2 * = s 2 + 80 ? 32000 s 2 + 3955000 3

f1(255)=185000 最优策略:u1 * = 247.5 最佳聘用方案:

u1* = 247.5
2 u 2 * = × 247.5 + 80 =245 3

1 u3 * = × 245+125 =247.5 2

u*4=255

夏季247.5人,秋季245人,冬季247.5人,春季255人时, 最少总费用:为185000元

NEUQ
7、 用动态规划方法求解某些非线性优化问题

max F = x1 x

2 2

x3

? x1 + x 2 + x 3 = c ( c > 0) ? ? x i ≥ 0 ( i = 1, 2, 3)

NEUQ

NEUQ


赞助商链接
相关文章:
动态规划2
5动态规划2 23页 2财富值喜欢此文档的还喜欢 运筹学课程作业——动态规... ...(十七) 分类: 算法与数据结构 2008-01-07 10:493178人阅读评论(4)收藏举报 ...
运筹学课程模型
运筹学课程模型_工学_高等教育_教育专区。江苏大学 运筹学课程模型 专班 业: ...Dk ( xk ) 为了把一个实际问题用动态规划的方法求解,需要构造动态规划的数学...
《运筹学》课程教学(自学)基本要求
幸福ing971贡献于2013-07-11 0.0分 (0人评价)暂无...《运筹学课程教学(自学)基本要求适用层次 自学学...的动态规划模型的表示 【重点掌握】 动态规划是规划...
《运筹学》课程教学大纲(新)
运筹学课程教学大纲一、课程基本信息课程名称 课程英文名称 课程编号 开课...(11) 动态规划:提出动态规划的最优化原理,并在此基础上建立动态规划数学模型, ...
07运筹学试卷A答案
学年第二学期 2007 级 管理类 本科 A 卷 课程名称 管理运筹学时间( 120 ...A .1 个 B .2 个 C .3 个 D .4 个 动态规划是解决( )决策过程最...
清华大学-《运筹学》课程教学大纲
清华大学-《运筹学课程教学大纲_理学_高等教育_教育...动态规划 (共 16 学时) 4-1 动态规划的基本方法...文档贡献者 蓝色兵心3322 贡献于2013-07-19 ...
运筹学在图书馆管理中的应用
运筹学课程设计运筹学在图书馆管理中的应用 班学 ...运筹学的许多分支如动态规划、整数、统筹方法、存储...文档贡献者 holyshit1238 贡献于2014-07-05 1/2 ...
运筹学感想
不得不说,运筹学课程对我来说是有难度的,动态规划、对策论这些 sounds ...文档贡献者 Meochenli 贡献于2016-09-07 1/2 相关文档推荐 对运筹学的理解与...
运筹学课程简介
运筹学课程简介 运筹学课程简介 06191340 运筹学 3 Operational Research ...动态规划的基本概念和基本方程★ 3. 动态规划的最优性原理和最优定理 4. ...
运筹学授课计划2009.2(信管07)
2008 /2009 学年 第二学期 授 课 计 划 课程名称:管理运筹学 授课班级:信...6 课堂 讲授 8-9 7 第六章 动态规划 主要介绍动态规划的基本原理及其应用。...
更多相关文章: