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

数学模型动态规划


动态规划
动态规划(dynamic programming)是运筹学的一个重要分支,它是解决多 阶段决策问题的一种有效的数量化方法.动态规划是由美国学者贝尔曼 (R.Bellman)等人所创立的.1951 年贝尔曼首先提出了动态规划中解决多阶 段决策问题的最优化原理,并给出了许多实际问题的解法.1957 年贝尔曼发 表了《动态规划》一书,标志着运筹学这一重要分支的诞生.

§1 动态规划的概念与原理
一、动态规划的基本概念 引例: 最短路线问题 美国黑金石油公司( The Black Gold Petroleum Company)最近在阿拉 斯加(Alaska)的北斯洛波(North Slope)发现了大的石油储量。为了大规 模开发这一油田,首先必须建立相应的输运网络,使北斯洛波生产的原油能 运至美国的 3 个装运港之一。在油田的集输站(结点 C)与装运港(结点 P1、 P2、P3)之间需要若干个中间站,中间站之间的联通情况如图 1 所示,图中线 段上的数字代表两站之间的距离 (单位: 10 千米) 。 试确定一最佳的输运线路, 使原油的输送距离最短。 解:最短路线有一个重要性质,即如果由起点 A 经过 B 点和 C 点到达终 点 D 是一条最短路线, 则由 B 点经 C 点到达终点 D 一定是 B 到 D 的最短路 (贝 尔曼最优化原理) 。此性质用反证法很容易证明,因为如果不是这样,则从 B 点到 D 点有另一条距离更短的路线存在,不妨假设为 B—P—D;从而可知路线 A—B—P—D 比原路线 A—B—C—D 距离短,这与原路线 A—B—C—D 是最短路 线相矛盾,性质得证。 根据最短路线的这一性质,寻找最短路线的方法就是从最后阶段开始, 由后向前逐步递推求出各点到终点的最短路线,最后求得由始点到终点的最 短路;即动态规划的方法是从终点逐段向始点方向寻找最短路线的一种方法。 按照动态规划的方法,将此过程划分为 4 个阶段,即阶段变量 k ? 1,2,3,4 ;取 过程在各阶段所处的位置为状态变量 xk ,按逆序算法求解。

1

10 8 M11 12
C

M31 6 4

8
P1

M21 6

7 M32 7 5 7 M33 4

6 M22

9

3 7 6 5
P2

10 M12

9 11 M23

11

6 M34 k=3

3 4 k=4

P3

k=1

k=2

当 k ? 4 时: 由结点 M31 到达目的地有两条路线可以选择,即选择 P1 或 P2;故: ?8? 选择 P2 f 4 ( x4 ? M 31 ) ? min? ? ? 6 ?6? 由结点 M32 到达目的地有三条路线可以选择,即选择 P1、P2 或 P3;故: ?4 ? ? ? f 4 ( x 4 ? M 32 ) ? min?3? ? 3 选择 P2 ?7 ? ? ? 由结点 M33 到达目的地也有三条路线可以选择,即选择 P1、P2 或 P3;故: ?7 ? ? ? f 4 ( x 4 ? M 33 ) ? min?6? ? 5 选择 P3 ?5 ? ? ? 由结点 M34 到达目的地有两条路线可以选择,即选择 P2 或 P3;故: ?3? 选择 P2 f 4 ( x4 ? M 34 ) ? min? ? ? 3 ?4? 当 k ? 3 时: 由结点 M21 到达下一阶段有三条路线可以选择,即选择 M31、M32 或 M33;故:

图1

2

?10 ? 6? ? ? f 3 ( x3 ? M 21 ) ? min? 7 ? 3 ? ? 10 ?6?5? ? ?

选择 M32

由结点 M22 到达下一阶段也有三条路线可以选择,即选择 M31、M32 或 M33; 故:
?9 ? 6? ? ? f 3 ( x3 ? M 22 ) ? min?7 ? 3? ? 10 ?5 ? 5? ? ?

选择 M32 或 M33

由结点 M23 到达下一阶段也有三条路线可以选择,即选择 M32、M33 或 M34; 故:
?11 ? 3? ? ? f 3 ( x3 ? M 23 ) ? min? 4 ? 5 ? ? 9 ?6?3? ? ?

选择 M33 或 M34

当 k ? 2 时: 由结点 M11 到达下一阶段有两条路线可以选择,即选择 M21 或 M22;故: ?8 ? 10? 选择 M22 f 2 ( x2 ? M 11 ) ? min? ? ? 16 ?6 ? 10? 由结点 M12 到达下一阶段也有两条路线可以选择,即选择 M22 或 M23;故: ?9 ? 10? 选择 M22 f 2 ( x2 ? M 12 ) ? min? ? ? 19 ?11? 9 ? 当 k ? 1 时: 由结点 C 到达下一阶段有两条路线可以选择,即选择 M11 或 M12;故: ?12 ? 16? 选择 M11 f1 ( x1 ? C ) ? min? ? ? 28 ?10 ? 19? 从而通过顺序(计算的反顺序)追踪(黑体标示)可以得到两条最佳的 输运线路:C—M11—M22—M32—P2;C—M11—M22—M33—P3。最短的输送距离是 280 千米。 一个多阶段决策过程最优化问题的动态规划模型通常包含以下要素。 1、阶段 阶段是过程中需要做出决策的决策点。描述阶段的变量称为阶段变量, 常用 k 来表示。阶段的划分一般是根据时间和空间的自然特征来进行的,但 要便于将问题的过程转化为多阶段决策的过程。阶段变量一般用 k ? 1,2,?, n 表示。

3

2、状态 状态(state)表示每个阶段开始时过程所处的自然状况。它应能描述过 程的特征并且无后效性,即当某阶段的状态变量给定时,这个阶段以后过程 的演变与该阶段以前各阶段的状态无关。通常还要求状态是直接或间接可以 观测的。 描述状态的变量称状态变量(state variable) 。变量允许取值的范围称 允许状态集合(set of admissible states)。用 xk 表示第 k 阶段的状态变量, 它可以是一个数或一个向量。用 Dk 表示第 k 阶段的允许状态集合。 n 个阶段的决策过程有 n ? 1 个状态变量, xn ?1 表示 xn 演变的结果。 根据过程演变的具体情况,状态变量可以是离散的或连续的。为了计算的方 便有时将连续变量离散化;为了分析的方便有时又将离散变量视为连续的。 状态变量简称为状态。 3 决策 当一个阶段的状态确定后,可以作出各种选择从而演变到下一阶段的某 个状态,这种选择手段称为决策(decision) ,在最优控制问题中也称为控制 (control) 。 描述决策的变量称决策变量(decision variable) ,变量允许取值的范围称 允许决策集合(set of admissible decisions) 。用 uk ( x k ) 表示第 k 阶段处 于状态 xk 时的决策变量,它是 xk 的函数,用 U k (uk ) 表示 uk 的允许决策集合。 决策变量简称决策。 4 策略 决策组成的序列称为策略(policy) 。由初始状态 x1 开始的全过程的策略 记作 p1n ( x1 ) ,即 p1n ( x1 ) ? {u1 ( x1 ),u2 ( x2 ),?, un ( xn )} . 由第 k 阶段的状态 xk 开始到终止状态的后部子过程的策略记作 pkn ( xk ) ,即 pkn ( xk ) ? {uk ( xk ),?, un ( xn )}, k ? 1,2, ?, n ? 1. 类似地,由第 k 到第 j 阶段的子过程的策略记作 pkj ( xk ) ? {uk ( xk ),?, u j ( x j )}. 可 供选择 的策略 有一定 的范围 ,称为 允许策 略集合 (set of admissible policies),用 P1n ( x1 ), Pkn ( x k ), Pkj ( x k ) 表示。 5. 状态转移方程 在确定性过程中,一旦某阶段的状态和决策为已知,下阶段的状态便 完全确定。用状态转移方程( equation of state transition )表示这种演 变规律,写作 xk ?1 ? T ( xk , uk ), k ? 1,2,?, n. (1) 6. 指标函数和最优值函数 指标函数(objective function) 是衡量过程优劣的数量指标,它是定
4

义在全过程和所有后部子过程上的数量函数,用 Vkn ( xk , uk , xk ?1 ,?, xn ?1 ) 表示,
k ? 1,2,?, n 。指标函数应具有可分离性,即 Vkn 可表为 xk , uk ,Vk ?1n 的函数,记



Vkn ( xk , uk , xk ?1 ,?, xn?1 ) ? ? k ( xk , uk ,Vk ?1n ( xk ?1 , uk ?1 , xk ?2 ?, xn?1 )) 并且函数 ? k 对于变量 Vk ?1n 是严格单调的。
过程在第 j 阶段的阶段指标取决于状态 x j 和决策 u j ,用 v j ( x j , u j ) 表示。指 标函数由 v j ( j ? 1,2,?, n) 组成,常见的形式有: 阶段指标之和,即 阶段指标之积,即

Vkn ( xk , uk , xk ?1 ,?, xn ?1 ) ? ? v j ( x j , u j ) ,
j ?k

n

Vkn ( xk , uk , xk ?1 ,?, xn ?1 ) ? ? v j ( x j , u j ) ,
j ?k

n

阶段指标之极大(或极小) ,即 Vkn ( x k , uk , xk ?1 ,?, xn ?1 ) ? max (min) v j ( x j , u j ) .
k ? j ?n

这些形式下第 k 到第 j 阶段子过程的指标函数为 Vkj ( xk , uk , xk ?1 ?, x j ?1 ) 。 根据状态转移方程指标函数 Vkn 还可以表示为状态 xk 和策略 p kn 的函数,即

Vkn ( xk , pkn ) 。 在 xk 给 定 时 指 标 函 数 Vkn 对 p kn 的 最 优 值 称 为 最 优 值 函 数 (optimal value function) ,记为 f k ( xk ) ,即 f k ( xk ) ? opt Vkn ( xk , pkn ) ,
pkn ?Pkn ( xk )

7

其中 opt 可根据具体情况取 max 或 min 。 最优策略和最优轨线 使指标函数 Vkn 达到最优值的策略是从 k 开始的后部子过程的最优策

* * * * 略,记作 pkn ? {uk ,?, un } 。 p1 n 是全过程的最优策略,简称最优策略(optimal
* * policy) 。从初始状态 x1 ( ? x1 ) 出发,过程按照 p1 n 和状态转移方程演变所经历

* * * 的状态序列 {x1 。 , x2 ,?, xn ?1} 称最优轨线(optimal trajectory)

二、基本方程: 对于 n 阶段的动态规划问题,在求子过程上的最优指标函数时, k 子过程 与 k ? 1 子过程有如下递推关系: f ( x ) ? opt {vk ( xk , u k ) ? f k ?1 ( xk ?1 )}, k ? n,?,1 ? ? k k uk ?U k ( uk ) (2) ? ? f ( x ) ? c ? n?1 n?1 在 上 述 方 程 中 , 当 ? 为 加 法 时 取 f n ?1 ( xk ?1 ) ? 0 ; 当 ? 为 乘 法 时 , 取

f n ?1 ( xk ?1 ) ? 1 。 三、最优化原理 动态规划的最优化原理是美国学者 R. Bellman 首先提出的, 其表述如下:
5

“作为整个过程的最优策略应具有这样的性质,无论过去的状态和决策如何, 对于前面的决策所形成的状态而言,余下的诸决策必须构成最优策略” .也就 是说最优策略的任一子策略都是最优的. 最优化原理还阐述这样一个事实,对全过程的任一状态点 xk ,我们不考 虑 xk 以前的决策,只保证 xk 以后的决策是最优的。显然,由于 k 的任意性(k =1,2,?,n)就保证了全过程的决策是最优的.最优化原理为动态规划从 最后阶段的优化开始,逐步向前一阶段优化扩展直至第一阶段,从而达到全 程优化的方法奠定了理论基础.

§2 动态规划模型的建立与求解
根据动态规划的概念不难看出,在用动态规划方法解决实际问题时,必 须首先明确本问题中的阶段、状态、决策、策略以及考察指标,并建立状态 转移方程,然后根据 k 阶段最优指标的大小找出与之对应的最优子策略,直 至找出问题的最优解.我们把找出实际问题中的阶段、状态、决策、策略以 及考察指标,并建立状态转移方程这一过程称为建立动态规划模型.应该说 建立动态规划模型是解决动态规划问题的第一步,也是非常重要的一步.模 型建立的是否简捷、准确,直接关系到问题最优解的筛选及准确性,因此, 建立动态规划模型是十分重要的. 其步骤可归纳如下: (1)将所要解决的问题恰当地划分为若干阶段,经常是按事物发展的时间和 空间来划分不同阶段,各阶段的首尾要互相衔接; (2)正确地选择状态变量 xk ,确定它在每一阶段的取值范围;这一步是形成 动态模型的关键,状态变量 xk 是动态规划模型中最重要的参数。一般来说, 状态变量 xk 应该具有以下三个特征: ①要能够用来描述决策过程的演变特征; ②满足无后效性,即若某阶段状态已经给定后,则以后过程的进展不受以前 各个状态的影响,也就是说,过去的历史只通过当前的状态去影响未来的 发展; ③递推性,即由 k 阶段的状态变量 xk 及决策变量 uk 可以计算出 k ? 1 阶段的 状态变量 xk ?1 (3)选择决策变量 uk ,确定允许决策集合 Dk (uk ) 。 (4)正确写出状态转移方程 xk ?1 ? T ( xk , uk ), k ? 1,2,?, n. (5)建立指标函数,一般用 rk ( xk , uk ) 描述阶段效应, f k ( xk ) 表示从 k ? n 阶段 的最优子策略函数. ( 6 ) 建 立 动 态 规 划 基 本 方 程 。 对 每 一 对 xk , uk ( xk ) 计 算 不 同 指 标 值
6

rk ( xk , uk ( xk )) ? f k ?1 ( xk ?1 ) .把这些指标值进行比较取出最优的一个,所谓最优 是根据实际问题的需要确定指标值的最大者或最小者,即 ? f k ( x k ) ? opt ?rk ( x k , u k ( x k )) ? f k ?1 ( x k ?1 )} ? u k ?Dk ( u k ) ? ? ? f n ?1 ( x n ?1 ) ? c k ? n, n ? 1, ?,1 在动态规划基本方程中, rk ( xk , u k ( xk )) , xk ?1 ? T ( xk , uk ), k ? 1,2,?, n. 都 是已知函数, 最优子策略 f k ( xk ) 与 f k ?1 ( xk ?1 ) 之间是递推关系, 要求出 f k ( xk ) 及 uk ( xk ) 需要先求出 f k ?1 ( xk ?1 ) ,这就决定了用在动态规划基本方程求最优策略 是逆着阶段的顺序进行的,由 k = n ,n –1,?2,1 将上式依次逐步递推, 直至全过程的优化结束, 即可求出动态规划问题的最优策略及最优指标值. 称 为动态规划的逆序算法。

第三节
一、机器负荷分配问题

动态规划方法应用

例 1:某厂新购某种机床 125 台,据估计,这种设备 5 年后将被其他设备所代 1 替,此机床如在高负荷状态下工作,年损坏率为 ,年利润为 10 万元; 2 1 如在低负荷状态下工作,年损坏率为 ,年利润为 6 万元;问应该如何安 5 排这些机床的生产负荷,才能使 5 年内获得最大的利润? 解:以年为阶段,k =1,2,3,4,5 取 k 年初完好的机床数为状态变量 xk , 以 k 年初投入高负荷运行的机床数为决策变量 uk ,则低负荷运行的机床 数为 xk ? u k ,于是状态转移方程为: 1 4 xk ?1 ? u k ? ( xk ? u k ) ? 0.8 xk ? 0.3u k 2 5 以利润为目标函数,则 k 年利润为: 10uk ? 6( xk ? uk ) ? 4uk ? 6xk 记 f k ( xk ) 表示从 k 年至 5 年末的最大总利润。则动态规划基本方程为:

7

? f k ( xk ) ? max ?4uk ? 6 xk ? f k ?1 ( xk ?1 )} 0 ?u k ? xk ? ? xk ?1 ? 0.8 xk ? 0.3uk ? ? x1 ? 125, x6 ? 0 ? f (x ) ? 0 ? 6 6 ?k ? 5,4,?,1 ?
下面具体求解

? 注意到动态规划基本方程 ? f k ( x k ) ? max ?4u k ? 6 x k ? f k ?1 (0.8 x k ? 0.3u k )} ?
0 ? u k ? xk

所以 k ? 5 时 当k ? 4时

f 5 ( x5 ) ? max ?4u5 ? 6 x5 ? f 6 ( x6 )} ? 10 x5
0?u5 ? x5

u 5 ? x5

f 4 ( x 4 ) ? max ?4u 4 ? 6 x 4 ? f 5 (0.8 x 4 ? 0.3u 4 )} ? max ?4u 4 ? 6 x 4 ? 10(0.8 x 4 ? 0.3u 4 )} ? max ?u 4 ? 14x 4 }
0? u 4 ? x4 0? u 4 ? x4 0 ?u 4 ? x4

? 15x 4
当 k ? 3时

u 4 ? x4

f 3 ( x3 ) ? max ?4u 3 ? 6 x3 ? f 4 (0.8 x3 ? 0.3u 3 )} ? max ?4u 3 ? 6 x3 ? 15(0.8 x3 ? 0.3u 3 )} ? max ?? 0.5u 3 ? 18x3 }
0?u3 ? x3 0?u3 ? x3 0?u3 ? x3

? 18x3
当k ? 2时

u3 ? 0

f 2 ( x 2 ) ? max ?4u 2 ? 6 x 2 ? f 3 (0.8 x 2 ? 0.3u 2 )} ? max ?4u 2 ? 6 x 2 ? 18(0.8 x 2 ? 0.3u 2 )} ? max ?? 1.4u 2 ? 20.4 x 2 }
0 ? u 2 ? x2 0 ? u 2 ? x2 0 ? u 2 ? x2

? 20.4 x 2
当 k ? 1时

u2 ? 0

8

f1 ( x1 ) ? max?4u1 ? 6 x1 ? f 2 (0.8 x1 ? 0.3u1 )} ? max?4u1 ? 6 x1 ? 20.4(0.8 x1 ? 0.3u1 )} ? max?? 2.12u1 ? 22.32x1 }
0?u1 ? x1 0?u1 ? x1 0?u1 ? x1

? 22.32x1 ? 22.32 ? 125 ? 2790(万元)
即第一年到第 5 年末的最大利润为 22.32x1 , 而x1 ? 125。 在按与计算过程相反的顺序推回去,可得最优计划为 年份 k 第一年 第二年 第三年 第四年 第五年 完好机床数 xk ?1 ? 0.8xk ? 0.3uk 125 100 80 64 32 高负荷机床数 uk 0 0 0 64 32 低负荷机床数 xk ? u k 125 100 80 0 0

u1 ? 0

即前三年全部低负荷运转,后两年全部高负荷运转,最大利润为 2790 万元。

9

二、资源分配问题
所谓资源分配问题,就是将一定数量的一种或若干种资源(如原材料、 机器设备、资金、劳动力等)恰当地分配给若干个使用者,以使资源得到最 有效地利用。 1、一维分配问题 设有某种资源可用于 n 项活动,假设资源的数量为 a ,已知用于第 i 项活 动的资源数为 x i 时,可以得到的收益为 g i ( xi ) (i ? 1,2,?, n) ,试确定资源的 分配方案使收益最大? 该问题的数学模型可以表示为 max Z ? g1 ( x1 ) ? g 2 ( x2 ) ? ? ? g n ( xn )

s.t. x1 ? x2 ? ? ? xn ? a x1 , x2 ,?, xn ? 0 当 g i ( xi ) (i ? 1,2,?, n) 为 线 性 函 数 时 , 该 问 题 是 线 性 规 划 问 题 , 当 g i ( xi ) (i ? 1,2,?, n) 为非线性函数时,该问题是非线性规划问题,如果采用 非线性规划求解,比较麻烦。可以将它看成多阶段决策问题,利用动态规划 求解。 在应用动态规划方法处理这一 类问题时,提出将资源分配给每项活动的 过程看成一个阶段,每个阶段都要确定对一种活动的资源投放量,这时,状 态变量 xk 可以选择 k 阶段初所拥有的资源量, 即 xk 是要在第 k 项到第 n 项活动 间分配的资源量。 决策变量 u k 选择对活动 k 的资源投放量,决策变量 u k 的允许集合为 0 ? u k ? xk 。 在选取上述状态变量和决策变量的情况下,状态转移方程为: xk ?1 ? xk ? uk 去投放资源时的收益为指标函数,则 g k (uk ) 为阶段效益指标。 记 f k ( xk ) 表示从 k 阶段至 n 阶段的最大总利润。则动态规划基本方程为:

?gk (uk)? fk ?1 ( xk ?1)} ? ? f k ( xk ) ? 0max ?u k ? xk ? ? ? f n ?1 ( xn ?1 ) ? 0 k ? n, n ? 1, ?,1

10

例 2:某公司拟将 500 万元的资本投入所属的甲、乙、丙三个工厂进行技 术改造,各工厂获得投资后年利润将有相应的增长,增长额如表 1 所示。试 确定 500 万元资本的分配方案,以使公司总的年利润增长额最大。 表1
投资额 甲 乙 丙 100 万元 200 万元 300 万元 400 万元 500 万元

30 50 40

70 100 60

90 110 110

120 110 120

130 110 120

解:将问题按工厂分为三个阶段 k ? 1,2,3 ,设状态变量 xk ( k ? 1,2,3 )代 表从第 k 个工厂到第 3 个工厂的投资额,决策变量 uk 代表第 k 个工厂的投资 额。于是有状态转移方程为

xk ?1 ? xk ? uk 、 允 许 决 策 集 合
(k ? 3,2,1)

Dk (uk ) ? {uk | 0 ? uk ? xk } 和递推关系式: f k ( xk ) ? max {g k (uk ) ? f k ?1 ( xk ? uk )}
0?u k ? xk

f 4 ( x4 ) ? 0 当 k ? 3 时: f3 ( x3 ) ? max {g3 (u3 ) ? 0} ? max {g3 (u3 )}
0 ? u 3 ? x3 0 ? u 3 ? x3

于是有表 2,表中 u3 表示第三个阶段的最优决策。 表2 x3 0 0 0 1 1 0.4 2 2 0.6 3 3 1.1 (单位:百万元) 4 5 4 1.2 5 1.2

u3
f3 ( x3 )

当 k ? 2 时:
f 2 ( x2 ) ? max {g 2 (u2 ) ? f 3 ( x2 ? u2 )}
0?u 2 ? x2

于是有表 3。 表3 u2
x2

0 1 2 3 4 5

0 0+0 0+0.4 0+0.6 0+1.1 0+1.2 0+1.2

1 0.5+0 0.5+0.4 0.5+0.6 0.5+1.1 0.5+1.2

g2 (u2 ) ? f3 ( x2 ? u2 ) 2 3

(单位:百万元) f 2 ( x2 ) u2 4 5 0 0.5 1.0 1.4 1.6 2.1 0 1 2 2 1,2 2

1.0+0 1.0+0.4 1.1+0 1.0+0.6 1.1+0.4 1.1+0 1.0+1.1 1.1+0.6 1.1+0.4 1.1+0
11

当 k ? 1 时:
f1 ( x1 ) ? max {g1 (u1 ) ? f 2 ( x1 ? u1 )}
0 ? u1 ? x1

于是有表 4。 表4 u1 x1 5

0 0+2.1

g1 (u1 ) ? f 2 ( x1 ? u1 ) 1 2 3 4 5 0.3+1.6 0.7+1.4 0.9+1.0 1.2+0.5 1.3+0

f1 ( x1 )
2.1

u1
0,2

然后按计算表格的顺序反推算,可知最优分配方案有两个: (1)甲工厂 投资 200 万元,乙工厂投资 200 万元,丙工厂投资 100 万元; (2)甲工厂没 有投资,乙工厂投资 200 万元,丙工厂投资 300 万元。按最优分配方案分配 投资(资源) ,年利润将增长 210 万元。 这个例于是决策变量取离散值的一类分配问题,在实际问题中,相类似 的问题还有销售店的布局(分配)问题、设备或人力资源的分配问题等。 2、二维分配问题 (1)设数量分别为 a , b 的两种资源分配给 n 个使用者, xi — 分配第一种资源给第 i个使用者的数量,

yi — 分配第二种资源给第 i个使用者的数量, ri ( xi , yi ) — 第i个阶段的收益, i ? 1,2,?, n 求总收益最大的分配方案 n ? Z ? max ri ( xi , y i ) ? ? i ?1 ? ?n ?? x i ? a ? i ?1 该问题的数学模型可以表示为 ? n ?? y i ? b ? i ?1 ? x ? 0 , y ? 0 , i ? 1,2, ? , n i ? i
(2)二维分配问题的解法

1、逐次逼近法

12

n ? Z ? max ri ( xi , y i ) ? ? i ?1 ? ?n ?? x i ? a ? i ?1 由于 ? n ?? y i ? b ? i ?1 ? x ? 0 , y ? 0 , i ? 1,2, ? , n i ? i





X ( 0)

?n ?? xi ? a ( 0) ( 0) ? ( x1( 0) , x2 ,?, xn ), 满足 ? i ?1 ?x ? 0 ? i
n ? max ri ( x (i 0 ) , yi ) ? ? i ?1 ? n ? ?? yi ? b ? i ?1 ? yi ? 0 , i ? 1,2,?, n ? ? 得最优解

固定x于X (0) , 求下列一维问题的

( 0) ( 0) Y (0) ? ( y1(0) , y2 ,?, yn ),

② 固定y于Y (0) , 求下列一维问题的
n ? (0) ?max? ri ( xi , y i ) i ?1 ? n ? ?? xi ? a ? i ?1 ? xi ? 0 , i ? 1,2,?, n ? ? 得最优解

(1) (1) (1) X (1) ? ( x1 , x2 ,?, xn ),

③ 固定x于X (1) , 求下列一维问题的

13

n ? max ri ( x (i 1) , yi ) ? ? i ?1 ? n ? ?? yi ? b ? i ?1 ? yi ? 0 , i ? 1,2,?, n ? ? 得最优解

(1) (1) (1) Y (1) ? ( y1 , y2 ,?, yn ), 轮转若干步,直到满足精确度要求。

2、拉格郎日乘子法 (1)估计一个拉格郎日乘子 ? ? 0 (2)用动态规划法解一维问题 n n ? max[ r ( x , y ) ? ? yi ] ? ? i i i ? i ?1 i ?1 ? ?n ?? xi ? a ? i ?1 ? xi ? 0 , yi ? 0 , i ? 1,2,?, n ? ? 若解不唯一,假设共有 m 个 ( x(1) (?), y(1) (?)),( x(2) (?), y(2) (?)),?, ( x(m) (?), y(m) (?))
(1) (1) (1) (1) (1) (1) x(1) (?) ? ( x1 (?), x2 (?),?, xn (?))T , y(1) (?) ? ( y1 (?), y2 (?),?, yn (?))T

(3)计算 F (? ) ? min ? yi( j ) (? )
j i ?1

n

j ? 1,2,?, m
j ? 1,2,?, m

G(? ) ? max? yi( j ) (? )
j i ?1

n

(4)判断 ①若存在 j ? k , s.t ? yi( k ) ? b, 则 ( x ( k ) (? ), y ( k ) (? ))为最优解
i ?1 n

②若 F (? ) ? b, 则增大?, 转到(1) ③若 G(? ) ? b, 则减少?, 转到(1) ④若 F (? ) ? b ? G(? ), 且?j, 均有? yi( j ) ? b.则无解.
i ?1 n

14

三、存贮控制问题
在动态规划模型中 ,以时期为阶段 , 取各时期初的库存量为状态变量 ;取 各阶段的产量(或采购量)为决策变量,在确定决策变量时一般要考虑需求量、 生产能力、库存限制等因素;指标函数取生产或采购费用。 例 3:某工厂要制定今后四个时期某产品的生产计划,估计今后四个时期内市 场对该产品的需求如下表 时期 k 1 2 3 4 需求量 dk 2 3 2 4

假设该厂生产每批产品的固定费用为 2 千元,若不生产为 0;每单位产品的成 本为 1 千元;每件产品的每期保管费为 0.5 千元;每个时期最大生产能力所 允许的生产批量不超过 5 个单位;最大库存量为 4 个单位;假设开始时库存 量为 1 个单位,要求第四期末库存在 2 个单位。试问该厂应如何安排各个时 期的产量,才能满足市场需求的条件下使总费用最小? 解:按四个时期将问题分为四个阶段,k=1,2,3,4 取 k 期初库存量 xk 为状态变量;k 期内产量 uk 为决策变量,则状态转移 方程为 xk ?1 ? xk ? uk ? dk 由题意,第 k 期内的费用为 ?2 ? 1 ? u k , u k ? 0 rk ( xk , uk ) ? 0.5 xk ? ? ?0 , uk ? 0 ?2 ? u k , u k ? 0 ? 0.5 xk ? ? ?0 , uk ? 0 记

f k ( xk ) 表示第 k 期至第 4 期末的最小总费用。则动态规划基本方程为:

?rk ( xk , uk)? fk ?1( xk ?1)} ? ? f k ( xk ) ? min uk ? ? ? f5 ( x5 ) ? 0 k ? 4,3,2,1
注意: xk ?1 ? xk ? uk ? dk

下面求解 当k ? 4时

x4 ? x5 ? u4 ? d4 ? 2 ? 4 ? u4 ? 6 ? u4 u4 ? 5, u4 ? 1, 2, 3, 4 ?

15

f k ( xk ) ? min?rk ( xk , uk) ? f k ?1 ( xk ?1 )}
uk

?2 ? uk ? min{0.5 xk ? ? ? f k ?1 ( xk ?1 )} uk 0 ? f 4 (1) ? 0.5 ? 1 ? 2 ? 5 ? 7.5 f 4 (2) ? 0.5 ? 2 ? 2 ? 4 ? 7 f 4 (3) ? 0.5 ? 3 ? 2 ? 3 ? 6.5
f 4 (4) ? 0.5 ? 4 ? 2 ? 2 ? 6

u4 ? 6 ? x4
u4 (1) ? 5 u4 (2) ? 4 u4 (3) ? 3 u4 (4) ? 2

当k ? 3时 注意: xk ?1 ? xk ? uk ? dk x3 ? 0, 1, 2, 3, 4 x3 ? u3 ? d3 ? x4 ? 1 , d3 ? 2 ,? x3 ? u3 ? 3 ? u3 ? 3 ? x3

u4 ? 4, x3 ? u3 ? 2 ? 4 ,x3 ? u3 ? 6, ? u3 ? 5 ? u3 ? min{5, 6 ? x3}

?0.5 ? 0 ? 2 ? 3 ? f 4 (1) ? f3 (0) ? min?0.5 ? 0 ? 2 ? 4 ? f 4 (2) ?0.5 ? 0 ? 2 ? 5 ? f (3) 4 ? ?5 ? 7.5 ? ? min?6 ? 7 ?7 ? 6.5 ? ? 12.5
?0.5 ? 1 ? 2 ? 2 ? ?0.5 ? 1 ? 2 ? 3 ? ? f 3 (1) ? min? ?0.5 ? 1 ? 2 ? 4 ? ? ?0.5 ? 1 ? 2 ? 5 ? ? 4 . 5 ? 7 .5 ?5.5 ? 7 ? ? min? ?6.5 ? 6.5 ? ?7.5 ? 6 ? 12 f 4 (1) f 4 ( 2) f 4 (3) f 4 (4)

u3 (0) ? 3

u3 (1) ? 2

16

?0.5 ? 2 ? 2 ? 1 ? f 4 (1) ?0.5 ? 2 ? 2 ? 2 ? f (2) ? 4 f3 (2) ? min? ?0.5 ? 2 ? 2 ? 3 ? f 4 (3) ? ?0.5 ? 2 ? 2 ? 4 ? f 4 (4) ?4 ? 7.5 ?5 ? 7 ? ? min? ?6 ? 6.5 ? ?7 ? 6 ? 11.5 ?0.5 ? 3 ? 2 ? 0 ? f 4 (1) ?0.5 ? 3 ? 2 ? 1 ? f (2) ? 4 f 3 (3) ? min? ?0.5 ? 3 ? 2 ? 2 ? f 4 (3) ? ?0.5 ? 3 ? 2 ? 3 ? f 4 (4) ?1.5 ? 7.5 ?4.5 ? 7 ? ? min? ?5.5 ? 6.5 ? ?6.5 ? 6 ?9 u3 (2) ? 1

u3 (3) ? 0

?0.5 ? 4 ? 2 ? 0 ? f 4 (2) ? f 3 (4) ? min?0.5 ? 4 ? 2 ? 1 ? f 4 (3) ?0.5 ? 4 ? 2 ? 2 ? f (4) 4 ? ?2 ? 7 ? ? min?5 ? 6.5 ?6 ? 6 ? ?9 u3 (4) ? 0

当 k ? 2时

x2 ? 0, 1, 2, 3, 4

注意: xk ?1 ? xk ? uk ? dk
17

0 ? x2 ? u2 ? d 2 ? x3 ? 4 , d 2 ? 3 ,? x2 ? u2 ? 3 ? u2 ? 3 ? x2 u2 ? 5, x2 ? u2 ? 3 ? 4 ,x2 ? u2 ? 7, ? 3 ? x2 ? u2 ? min{5, 7 ? x2 }

?0.5 ? 0 ? 2 ? 3 ? f3 (0) ? f 2 (0) ? min?0.5 ? 0 ? 2 ? 4 ? f3 (1) ?0.5 ? 0 ? 2 ? 5 ? f (2) 3 ? ?5 ? 12.5 ? ? min?6 ? 12 ?7 ? 11.5 ? ? 17.5
?0.5 ? 1 ? 2 ? 2 ? ?0.5 ? 1 ? 2 ? 3 ? ? f 2 (1) ? min? ?0.5 ? 1 ? 2 ? 4 ? ? ?0.5 ? 1 ? 2 ? 5 ? ?4.5 ? 12.5 ?5.5 ? 12 ? ? min? ?6.5 ? 11.5 ? ?7.5 ? 9 ? 16.5 f3 (0) f3 (1) f3 (2) f3 (3)

u2 (0) ? 3

u2 (1) ? 5

18

?0.5 ? 2 ? 2 ? 1 ? f3 (0) ?0.5 ? 2 ? 2 ? 2 ? f (1) 3 ? ? f 2 (2) ? min?0.5 ? 2 ? 2 ? 3 ? f3 (2) ?0.5 ? 2 ? 2 ? 4 ? f (3) 3 ? ? ?0.5 ? 2 ? 2 ? 5 ? f3 (4) ?4 ? 12.5 ?5 ? 12 ? ? ? min?6 ? 11.5 ?7 ? 9 ? ? ?8 ? 9 ? 16 u2 (2) ? 4

?0.5 ? 3 ? 2 ? 1 ? f3 (0) ?0.5 ? 3 ? 2 ? 2 ? f (1) 3 ? ? f 2 (3) ? min?0.5 ? 3 ? 2 ? 3 ? f3 (2) ?0.5 ? 3 ? 2 ? 4 ? f (3) 3 ? ? ?0.5 ? 3 ? 2 ? 5 ? f3 (4) ?1.5 ? 12.5 ?4.5 ? 12 ? ? ? min?5.5 ? 11.5 ?6.5 ? 9 ? ? ?7.5 ? 9 ? 14 u2 (3) ? 0

19

?0.5 ? 4 ? 2 ? 0 ? f3 (1) ?0.5 ? 4 ? 2 ? 1 ? f (2) ? 3 f 2 (4) ? min? ?0.5 ? 4 ? 2 ? 2 ? f3 (3) ? ?0.5 ? 4 ? 2 ? 3 ? f3 (4) ?2 ? 12 ?5 ? 11.5 ? ? min? ?6 ? 9 ? ?7 ? 9 ? 14 u 2 ( 4) ? 0

当 k ? 1 时 x1 ? 1 注意: 0 ? x1 ? u1 ? d1 ? x2 ? 4 , d1 ? 2 ,

? 1 ? u2 ? 5

?0.5 ? 1 ? 2 ? 1 ? f 2 (0) ?0.5 ? 1 ? 2 ? 2 ? f (1) 2 ? ? f1 (1) ? min?0.5 ? 1 ? 2 ? 3 ? f 2 (2) ?0.5 ? 1 ? 2 ? 4 ? f (3) 2 ? ? ?0.5 ? 1 ? 2 ? 5 ? f 2 (4) ?3 ? 17.5 ?4.5 ? 16.5 ? ? ? min?5.5 ? 16 ?6.5 ? 14 ? ? ?7.5 ? 14 ? 20.5

u1 (1) ? 4

至此计算出本问题第一至四期的最小总费用为 20.5 千元。在按计算顺序 反推回去,可以求出最优生产计划为 时期 k 需求量 dk 1 2
20

2 3

3 2

4 4

库存量 xk 产量 uk 四、设备更新问题

1 4

3 0

0 3

1 5

1、只考虑更新与继续使用(不更新)两种情况。 要考虑一种设备在 n 年内的更新问题.在每年年初需作出决策,是继续使 用还是更新. 令 t — 机龄 rk (t ) — 第k年机龄为t的一台设备运转一年带 来的收入额;

rk (t )是t的递减函数; u k (t ) — 第k年机龄为t的一台设备运转一年所 需要的维护费; u k (t )是t的递增函数; ck (t ) — 第k年卖掉一台机龄为 t的设备所得的折价; p — 购买一台新设备所需要 的费用 K — 表示不更新; R — 表示更新
以年为阶段,k =1,2,3,?,n 取 第 k 年 初 设 备 的 机 龄 为 状 态 变 量 xk , 决 策 变 量
K ? 1 , 不更新 u k ( xk ) ? ? ? 0 , 更新 R ,于是状态转移方程为: ? xk ? 1 , u k ? 1 xk ?1 ? u k xk ? 1 ? ? , uk ? 0 ? 1 阶段指标函数, g ( x k ) ? rk ( x k ) ? u k ( x k ) ? (1 ? u k )[c k ( x k ) ? p ]



? R : rk (0) ? u k (0) ? p ? c k ( x k ) ?? ? K : rk ( x k ) ? u k ( x k ) f k ( xk ) 表示从 k 年至 n 年末的最大总利润。则动态规划基本方程为:

? ? R : rk (0) ? u k (0) ? p ? c k ( x k ) ? f k ?1 (1) ? f k ( x k ) ? max? ? ? K : rk ( x k ) ? u k ( x k ) ? f k ?1 ( x k ?1 ) ? f (x ) ? 0 ? n ?1 n ?1

, k ? n, n ? 1,?,3,2,1

21

例:下表列出了某种设备的 5 年内各年的预测数据。求 5 年内各年的更新策 略,如果开始时设备机龄为 1 年,使 5 年总收益最大?
产品年代k-t  机龄 t 1 2 期前k-t=0 3 4 5 0 1 1 2 3 4 0 2 1 2 3 0 3 1 2 4 5 0 1 0 收入  r(t) 18 16 16 14 14 22 21 20 18 16 27 25 24 22 29 26 24 30 28 32 维护费 8 8 9 9 10 6 6 8 8 10 5 6 8 9 5 5 6 4 5 4 55 60 52 52 50 50 u(t) 新购费 p 旧设备折价c(t) 20 15 10 5 2 30 28 20 15 10 31 26 21 15 33 28 20 35 30 40

解:以年为阶段,k =1,2,3,4,5 ? ? R : rk (0) ? u k (0) ? p ? c k ( x k ) ? f k ?1 (1) ? f k ( x k ) ? max? 由? ? K : rk ( x k ) ? u k ( x k ) ? f k ?1 ( x k ?1 ) ? f (x ) ? 0 ? 6 k k=5 ,

, k ? 5,4,3,2,1

x5 ? 1, 2, 3, 4,5
r5 (0) ? u 5 (0) ? p ? c5 (1) ? f 6 (1) r5 (1) ? u 5 (1) ? f 6 (2) 32 ? 4 ? 60 ? 30 ? 0 ? ?2 ? 23 28 ? 5 ? 0 ? 23

? R: f 5 (1) ? max? ?K: ? R: ? max? ?K:

? R : r5 (0) ? u 5 (0) ? p ? c5 (2) ? f 6 (1) f 5 (2) ? max? ? K : r5 (2) ? u 5 (2) ? f 6 (3) ? R : 32 ? 4 ? 60 ? 20 ? 0 ? ?12 ? max? ? 18 ? K : 24 ? 6 ? 0 ? 18
22

? R: f 5 (3) ? max? ?K: ? R: ? max? ?K:

r5 (0) ? u 5 (0) ? p ? c5 (3) ? f 6 (1) r5 (3) ? u 5 (3) ? f 6 (4) 32 ? 4 ? 60 ? 15 ? 0 ? ?17 ? 13 22 ? 9 ? 0 ? 13

? R : r5 (0) ? u 5 (0) ? p ? c5 (4) ? f 6 (1) f 5 (4) ? max? ? K : r5 (4) ? u 5 (4) ? f 6 (5) ? R : 32 ? 4 ? 60 ? 10 ? 0 ? ?22 ? max? ?6 ? K : 16 ? 10 ? 0 ? 6
? R: f 5 (5) ? max? ?K: ? R: ? max? ?K: r5 (0) ? u 5 (0) ? p ? c5 (5) ? f 6 (1) r5 (5) ? u 5 (5) ? f 6 (6) 32 ? 4 ? 60 ? 2 ? 0 ? ?30 ?4 14 ? 10 ? 0 ? 4

第 5 年机龄为 1—5 年的设备均不更新 k=4 , x4 ? 1, 2, 3, 4,
? R: f 4 (1) ? max? ?K: ? R: ? max? ?K: r4 (0) ? u 4 (0) ? p ? c 4 (1) ? f 5 (1) r4 (1) ? u 4 (1) ? f 5 (2) 30 ? 4 ? 55 ? 28 ? 23 ? 22 ? 39 26 ? 5 ? 18 ? 39

? R : r4 (0) ? u 4 (0) ? p ? c 4 (2) ? f 5 (1) f 4 (2) ? max? ? K : r4 (2) ? u 4 (2) ? f 5 (3) ? R : 30 ? 4 ? 55 ? 21 ? 23 ? 15 ? max? ? 29 ? K : 24 ? 8 ? 13 ? 29

? R: f 4 (3) ? max? ?K: ? R: ? max? ?K:

r4 (0) ? u 4 (0) ? p ? c 4 (3) ? f 5 (1) r4 (3) ? u 4 (3) ? f 5 (4) 30 ? 4 ? 55 ? 15 ? 23 ? 9 ? 16 18 ? 8 ? 6 ? 16

23

? R : r4 (0) ? u 4 (0) ? p ? c 4 (4) ? f 5 (1) f 4 (4) ? max? ? K : r4 (4) ? u 4 (4) ? f 5 (5) ? R : 30 ? 4 ? 55 ? 5 ? 21 ? ?1 ? max? ?9 ? K : 14 ? 9 ? 4 ? 9

第 4 年机龄为 1—4 年的设备均不更新 k=3 ,

x3 ? 1, 2, 3,
r3 (0) ? u 3 (0) ? p ? c3 (1) ? f 4 (1) r3 (1) ? u 3 (1) ? f 4 (2) 29 ? 5 ? 52 ? 26 ? 39 ? 37 ? 48 25 ? 6 ? 29 ? 48
r3 (0) ? u 3 (0) ? p ? c3 (2) ? f 4 (1) r3 (2) ? u 3 (2) ? f 4 (3) 29 ? 5 ? 52 ? 20 ? 39 ? 31 ? 31 20 ? 8 ? 16 ? 28 r3 (0) ? u 3 (0) ? p ? c3 (3) ? f 4 (1) r3 (3) ? u 3 (3) ? f 4 (4) 29 ? 5 ? 52 ? 10 ? 39 ? 21 ? 21 16 ? 9 ? 9 ? 16 更新(机龄为3年) 更新(机龄为2年)

? R: f 3 (1) ? max? ?K: ? R: ? max? ?K:
? R: f 3 (2) ? max? ?K: ? R: ? max? ?K: ? R: f 3 (3) ? max? ?K: ? R: ? max? ?K:

k=2 ,

x2 ? 1, 2,
r2 (0) ? u 2 (0) ? p ? c 2 (1) ? f 3 (1) r2 (1) ? u 2 (1) ? f 3 (2) 43 ? 46 46

? R: f 2 (1) ? max? ?K: ? R: ? max? ?K:

? R : r2 (0) ? u 2 (0) ? p ? c 2 (2) ? f 3 (1) f 2 (2) ? max? ? K : r2 (2) ? u 2 (2) ? f 3 (3) ? R : 33 ? max? ? 33 更新(机龄为2年) ? K : 29
24

k=1 ,

x1 ? 1,
r1 (0) ? u1 (0) ? p ? c1 (1) ? f 2 (1) r1 (1) ? u1 (1) ? f 2 (2) 22 ? 6 ? 50 ? 20 ? 46 ? 32 ? 43 18 ? 8 ? 33 ? 43

? R: f1 (1) ? max? ?K: ? R: ? max? ?K:

因此,第 1 年不更新;第 2 年机龄为 2 年的更新;第 3 年机龄为 2 年、3 年的 更新,第 4 年、第 5 年均不更新。 2、考虑更新与继续使用(不更新)和大修三种情况。 费用不仅取决于机龄和购置的年限, 取决于上次大修后的时间。 令

t1 — 机龄, t2 — 上 次 大 修 的 时 , 间 rk (t1 , t 2 ) — 机龄为t1 , 上次大修时间为 t 2的一台设备在第 k阶段的收入额; uk (t1 , t 2 ) — 机龄为t1 , 上次大修时间为 t 2的一台设备在第 k阶段的运行费用;

Pk (t1 , t 2 ) — 机龄为t1 , 上次大修时间为 t 2的一台设备在第 k阶段的更新费用; M k (t1 , t 2 ) — 机龄为t1 , 上次大修时间为 t 2的一台设备在第 k阶段的大修费用;

K — 表示继续使用; R — 表示更新 ; O — 大修

? — —折旧系数 ( 0 ?? ?1 )

f k (t1 , t 2 ) — 机龄为t1 , 上次大修时间为 t 2的一台设备从第 k阶段到最后阶段 n的最佳总 则动态规划基本方程为:
? ? R : rk (0,0) ? u k (0,0) ? Pk (t1 , t 2 ) ? ?f k ?1 (1,0) ? ? ? f k (t1 , t 2 ) ? max? K : rk (t1 , t 2 ) ? u k (t1 , t 2 ) ? ?f k ?1 (t1 ? 1, t 2 ) ? ? O : r (t , t ) ? u (t , t ) ? M (t , t ) ? ?f (t ? 1, t ) k 1 2 k 1 2 k 1 2 k ?1 1 2 ? ? ? f (t , t ) ? 0 ? n ?1 1 2 k ? n, n ? 1,?,3,2,1

,

25


赞助商链接
相关文章:
数学建模动态规划库存问题
数学建模动态规划库存问题_数学_自然科学_专业资料。数学建模,动态规划,随机库存随机库存的分配摘要卖方管理库存(VMI,Vendor-Managed Inventory)是现代物流 中一个比较...
基于动态规划模型的生产计划安排
数学建模数学建模隐藏>> 2012 安师院数学建模选拔赛 承诺书 我们仔细阅读了安师院...张金币 日期: 2012 年 04 月 04 日 题目:基于动态规划模型的生产计划安排...
动态规划及其在资源分配中的应用
动态规划及其在资源分配中的应用摘要:在概述动态规划原理的基础上,提出了动态规划数学模型建模的主要步骤,将动态规划思 想运用到求解资源分配中,并通过一个实际...
2013年全国大学生数学建模B题_动态规划算法(附加四)
2013年全国大学生数学建模B题_动态规划算法(附加四)_营销/活动策划_计划/解决方案_实用文档。2013年全国大学生数学建模B题_动态规划算法 ...
实验四2求解动态规划模型
实验四2求解动态规划模型_数学_自然科学_专业资料。(一) 实验目的:用 WinQSB 软件求解动态规划中的背包问题及生产与存储问题。 (二) 内容与要求:求解下列两例。...
动态规划
3 1.3 动态规划的数学模型 动态规划的数学模型除包括式(7-2)外,还包括阶段的划分、各阶段的状态变量和决 策变量的选取、允许决策集合和状态转移律的确定等。 ...
ACM论文 张辰轩动态规划
动态规划实现中的问题 八。动态规划与其他算法的比较 九。动态规划的理论模型 一。引言动态规划是运筹学的一个分支, 是求解决策过程最优化的数学方法。 20 世纪 ...
动态规划法学习报告
动态规划法学习报告 - 现代控制理论学习报告 动态规划法 1、概述: 动态规划(dynamic programming)是运筹学的一个分支,是求解决策过程最优化的数学 方法。20 世纪 ...
中国数学建模-编程交流-动态规划算法_2
我们将前文所说的具有明显的阶 段划分和状态转移方程的动态规划称为标准动态规划,这种标准动态规划是在研究多阶段决 策问题时推导出来的,具有严格的数学形式,适合...
生产与库存的动态规划模型
生产与库存的动态规划模型_理学_高等教育_教育专区。数学模型课程设计课程设计(论文) 题目名称课程名称学生姓名学系 、专号业 生产与库存的动态规划模型 数学模型 黄...
更多相关标签: