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

动态规划(完整)


第七章 动态规划
主要内容:
§7.1多阶段决策问题 §7.2 动态规划的基本概念和基本原理

§7.3 动态规划应用举例

例 求解最短路问题
A1 2 Q 4 3 A3 A2 6 3 2 4 4 1 5 B3 B2 3 7 4 B1 4 6 3 3 C2 1 C1 3 4 T









分阶段的最短路径
? ? ? ? ? ? ? Ⅳ : C1—T Ⅲ --Ⅳ : B1—C1—T Ⅱ--Ⅲ--Ⅳ :A2—B1—C1—T Ⅰ--Ⅱ--Ⅲ --Ⅳ: Q—A2—B1—C1—T Q--A3—B1—C1—T Q--A3—B2—C2—T 3 4 7
11 11 11

最短路径
11

4

A1 2
11

7 4 3

B1
7

1 4
3

6
7

C1

Q

4 3

A2
8

2 4 4 1 5

6 3 3 3 C2
4

3 4 T

B2
6

A3

B3









最短路径解的特点
? 1、可以将全过程求解分为若干阶段求解;-----多阶段决策问题 ? 2、在全过程最短路径中,将会出现阶段的最 优路径;-----递推性 ? 3、前面的终点确定,后面的路径也就确定了, 且与前面的路径(如何找到的这个终点)无关; -----无后效性 ? 3、逐段地求解最优路径,势必会找到一个全 过程最优路径。-----动态规划

§7.1多阶段决策问题
? 动态规划是解决多阶段最优决策的方法,
由美国数学家贝尔曼(R. Bellman) 于 1951 年首先提出; ? 1957年贝尔曼发表动态规划方面的第一部 专著“动态规划”, 标志着运筹学的一 个 新分支的创立。

? 动态规划将复杂的多阶段决策问题分解为

一系列简单的、离散的单阶段决策问题,
采用顺序求解方法, 通过解一系列小问题

达到求解整个问题目的;
? 动态规划的各个决策阶段不但要考虑本阶

段的决策目标, 还要兼顾整个决策过程的
整体目标, 从而实现整体最优决策.

动态规划的分类:
? 离散确定型
? 离散随机型

? 连续确定型
? 连续随机型

动态规划的特点:
? 动态规划没有准确的数学表达式和定义 精确的算法, 它强调具体问题具体分析,

依赖分析者的经验和技巧。
? 与运筹学其他方法有很好的互补关系, 尤

其在处理非线性、离散性问题时有其独
到的特点。

通常多阶段决策过程的发展是通过状态的一系列变换来
实现的。一般情况下,系统在某个阶段的状态转移除与本阶 段的状态和决策有关外,还可能与系统过去经历的状态和决 策有关。因此,问题的求解就比较困难复杂。而适合于用动 态规划方法求解的只是一类特殊的多阶段决策问题,即具有 “无后效性”的多阶段决策过程。 所谓无后效性,又称马尔柯夫性,是指系统从某个阶段往后 的发展,仅由本阶段所处的状态及其往后的决策所决定,与

系统以前经历的状态和决策(历史)无关。
具有无后效性的多阶段决策过程的特点是系统过去的历史, 只能通过现阶段的状态去影响系统的未来,当前的状态就是 后过程发展的初始条件。

动态规划的应用
? 动态规划在工程技术, 企业管理, 军事部 门有广泛的应用; 可解决资源分配, 生产

调度, 库存管理, 路径优化, 设备更新, 投
资规划, 排序问题和生产过程的最优控制

等问题;

§7.2 动态规划的基本概念和基本思想

一、基本概念
使用动态规划方法求解决策问题首先要将 问题改造成符合动态规划求解要求的形式, 要涉及以下概念: (1)阶段 (3)决策与策略 (2)状态 (4)状态转移方程

(5)指标函数

(6)基本方程

(1) 划分阶段 把一个复杂决策问题按时间或空间特 征分解为若干(n)个相互联系的阶段 (stage), 以便按顺序求解; 阶段变量描述当前所处的阶段位置,一

般用下标 k 表示;

(2) 确定状态
每阶段有若干状态(state), 表示某一阶段决策 面临的条件或所处位置及运动特征的量,称为 状态。反映状态变化的量叫作状态变量。 k 阶段的状态特征可用状态变量 sk 描述;

每一阶段的全部状态构成该阶段的状态集合Sk,
并有sk?Sk。每个阶段的状态可分为初始状态

和终止状态,或称输入状态和输出状态,阶
段的初始状态记作sk ,终止状态记为sk+1 ,也 是下个阶段的初始状态。

(3) 决策、决策变量 所谓决策就是确定系统过程发展的方案, 决策的实质是关于状态的选择,是决策者 从给定阶段状态出发对下一阶段状态作出 的选择。 用以描述决策变化的量称之决策变量, 和状态变量一样,决策变量可以用一个数, 一组数或一向量来描述.也可以是状态变量 的函数,记以 xk ? xk ( sk ) ,表示于 k 阶段状 态 sk 时的决策变量.

决策变量的取值往往也有一定的容许范围,
称之允许决策集合.决策变量 xk(sk)的允许决

策集用 XK(SK)表示, xk(sk) ?XK(SK) , 允许决
策集合实际是决策的约束条件。

(4)策略和允许策略集合
策略(Policy)也叫决策序列.策略有全过程

策略和 k 部子策略之分,全过程策略是指具
有n 个阶段的全部过程,由依次进行的 n 个 阶段决策构成的决策序列,简称策略,表示 为 p1,n {x1 , x2 ,? , xn } 。从 k 阶段到第 n 阶段, 依次进行的阶段决策构成的决策序列称为 k 部子策略,表示为 pk ,n {xk , xk ?1 ,?, xn } ,显然当 k=1时的 k 部子策略就是全过程策略。

(5) 状态转移方程
状态转移确定从一个状态到另一个状态的转

移过程, 由状态转移方程描述: sk+1 = T (sk, xk);
状态转移方程在大多数情况下可以由数学公 式表达, 如: sk+1 = sk + xk;

(6) 指标函数
用来衡量策略或子策略或决策的效果的 某种数量指标,就称为指标函数。它是定义 在全过程或各子过程或各阶段上的确定数量 函数。对不同问题,指标函数可以是诸如费 用、成本、产值、利润、产量、耗量、距离、 时间、效用,等等。

(1)阶段指标函数(也称阶段效应)
用vk(sk , xk)表示第 k 段处于状态 sk且所作

决策为 xk 时的指标,则它就是第 k 段指标函
数,简记为vk 。 (2)过程指标函数(也称目标函数) 用f(sk , xk)表示第k子过程的指标函数。表

示处于第 k 段 sk 状态且所作决策为xk时,
从 sk 点到终点的距离。由此可见, f(sk , xk)

不仅跟当前状态 sk 有关,

还跟该子过程策略 pk(sk) 有关,严格说来,应
表示为 fk(sk , pk(sk)) 。它是由各阶段的阶段

指标函数 vk(sk , xk)累积形成的,对于 k 部子
过程的指标函数可以表示为:

f k ,n ? f k ,n ( sk , xk , sk ?1 , xk ?1 ,? , sn , xn ) ? vk ( s k , xk ) ? vk ?1 ( sk ?1 , xk ?1 ) ? ? ? vn ( sn , xn )
式中?,表示某种运算,可以是加、减、、 乘、除、开方等.

多阶段决策问题中,常见的目标函数形式
之一是取各阶段效应之和的形式,即:

fk ?

?v
i ?k

n

k

( sk , u k )

有些问题,如系统可靠性问题,其目标函 数是取各阶段效应的连乘积形式,
f k ? ? vk ( sk , uk )
i ?k n

(7) 最优解
用 fk* (sk) 表示第 k 子过程指标函数Fk(sk , pk(sk))

在状态 sk 下的最优值,即:

f k (sk ) ? opt {Fk (sk , pk (sk ))} k ? 1, 2,?, n
pk ?PK ( sk )

?

称 fk(sk) 为第 k 子过程上的最优指标函数; 与它相应的子策略 pk(sk) 称为状态 sk 下的最 优子策略,记为 pk*(sk)

例 用动态规划求解最短路问题
A1 2 Q 4 3 A3 6 3 A2 2 4 4 1 5 B3 B2 3 6 3 3 C2 7 4 B1 4

1 C1 3 4 T

最短路的求解:

阶段: 可分为4个阶段, k = 1, ..., 4。
状态: 可用城市编号, S1={Q}, S2={A1,A2,A3}, S3={B1,B2,B3}, S4={C1,C2}, S5={T} Q 决策: 决策变量也可用城市编号; 状态转移方程: sk+1= xk; 阶段指标函数:

A1 2 4 3 A3 6 3 A2

7 4

B1 4

1 C1 3 4 3 C2 T

2 4 4 1 5

6 B2 3 B3 3

vk ? sk , xk ? ? csk xk
过程指标(阶段递推)函数:

f k ( sk ) ? min ?vk ( sk , xk ) ? f
?

? k ?1

( sk ?1 )?

k=4 f4 (C1) = 3, k=3 f3(B1)=min{1+f4(C1)=4*, 4+f4(C2)=8}=4 f3(B2)=min{6+f4(C1)=9, 3+f4(C2)=7*}=7 f3(B3)=min{3+f4(C1)=6*, 3+f4(C2)=7}=6 f4 (C2) = 4

A1 2 Q 4 3 A3 6 3 A2

7 4

B1 4

1 C1 3 4 3 C2 T

2 4 4 1 5

6 B2 3 B3 3

k=2

f2(A1) = min{7+ f3(B1), 4+ f3(B2), 6+ f3(B3) } = min{11*, 11*, 12} = 11
f2(A2) = min{3+ f3(B1), 2+ f3(B2), 4+ f3(B3) } = min{7*, 9, 10 } = 7 f2(A3) = min{4+ f3(B1), 1+ f3(B2), 5+ f3(B3) } = = min{8*, 8*, 11 } = 8 k=1 f1(Q) = min{2+f2(A1), 4+f2(A2), 3+f2(A3)} = min{13, 11*, 11* } = 11 最短路是:Q? A2 ? B1 ? C1 ? T,p={A2,B1,C1,T} Q? A3 ? B1 ? C1 ? T ,p={A3,B1,C1,T}

Q? A3 ? B2 ? C2 ? T ,p={A3,B2,C2,T}

二、动态规划的最优性原理
? 整个过程的最优策略应具有这样的性质: 无 论过去的状态和决策如何, 对前面的决策所 形成的状态而言, 后续的诸决策必须构成最 优策略; ? 上一条成立的条件是阶段递推函数严格单 调。

在例题中,求解最短路线的计算公式可以概 括写成:

? f5? ( s5 ) ? 0 ? ? ? ? min ? f k ( sk ) ? x ?X ( s ){vk ( sk , xk ( sk )) ? f k ?1 ( sk ?1 )} k k k ? ?k ? 4,3, 2,1 ?
其中,vk 在这里表示从状态 sk 到由决策 xk
所决定的状态 sk+1 之间的距离。f5(s5)=0 是边

界条件,表示全过程到第四阶段终点结束。

一般地,对于 n 个阶段的决策过程,假设只
考虑指标函数是“和”与“积”的形式,第 k

阶段和第 k+1 阶段间的递推公式可表示如下:
当过程指标函数为下列“和”的形式时 ? k k k k k k pk ?PK ( sk ) n

f (s ) ? opt { f (s , p (s ))}

? opt

pk ?Pk ( sk ) i ? k

? v (s , x )
i i i

相应的函数基本方程为 :

? f ? (s ) ? 0 ? n ?1 n ?1 ? ? ? ? f k ( sk ) ? opt {vk ( sk , xk ( sk )) ? f k ?1 ( sk ?1 )} xk ? X k ? ? k ? n, n ? 1,? , 2,1 ?

当过程指标函数为下列“积”的形式时

fk (sk ) ? opt { fk (sk , pk (sk ))}
pk ?PK ( sk )

? opt

pi ?Pk ( si ) i ? k

vi ( si , xi ) ?

n

相应的函数基本方程为 :

? f ? (s ) ? 1 ? n ?1 n ?1 ? ? ? ? f k ( sk ) ? opt {vk ( sk , xk ( sk )) ? f k ?1 ( sk ?1 )} xk ? X k ? ? k ? n, n ? 1,? , 2,1 ?

动态规划的优缺点
动态规划的优点 ? 可以解决线性, 非线性, 整
动态规划的缺点: ? 没有标准的模型可供应用, 构 模依赖于个人的经验和技巧; ? 状态变量需满足无后效性, 有 较大的局限性; ? 动态规划的维数灾难限制了

数规划无法有效求解的复
杂问题;

? 容易找到全局最优解;
? 可以得到一组解;

对规模较大问题的求解效率;

§7.3 动态规划方法应用
动态规划的步骤:

1. 将问题按时间或空间划分为满足递推关系

的若干阶段, 对非时序问题可人为地引入

“时段”概念;
2. 正确选择状态变量 sk, 满足:

可知性: 正确描述动态过程演变, 可直接或
间接确定状态变量的值;

无后效性: 后面的决策与前面的决策无关;

3. 确定决策变量 xk以及允许决策集合Xk; 4. 写出状态转移方程 sk+1 = T (sk , xk); 5. 决策变量的取值范围 6. 写出过程指标函数(阶段函数)的递推 关系, 应满足: a) 是定义在所有阶段上的数量函数; b) 具有可分离性,并满足递推关系; c) 阶段函数应严格单调。

动态规划应用举例:
1. 最优路径问题 2. 资源配置问题 3. 生产与库存问题 4. 机器负荷分配问题 5. 复合系统工作可靠性问题 6. 二维背包问题 7. 设备更新问题 8. 货郎担问题 9. 非线性规划的求解

1.最优路径问题
某厂要确定一种新产品在今后五年内的价格,并已拟定只在 5、6、7、8元这四种单价中进行选择。据预测,今后五年 不同价格下每年盈利(万元)见下表,但是各相邻年度价 格增减不得超过1元。问今后五年内每年定价各为多少,可 逾七五年总利润最大。

价格/元 盈利/万元 第一年 第二年 第三年 第四年 第五年 5 6 7 8 9 7 6 8 2 5 5 7 4 8 9 6 5 6 7 6 8 4 3 4

价格/ 元

盈利/万元 第一年 第二年 第三年 第四年 第五年
37

5
6 7

9
35

2
5
36 38

24 28 28

4
8 9

18 22 23 17

13

8

5
6 7
14 11 10

8
4 3
4 3 4

7 6

5

8

8

7

30

6

6

4

解:1、建立动态规划模型: 阶段:以年划分阶段,k=5,4,3,2,1; 状态变量sk为每个阶段初的价格,则Sk={5,6,7,8}; 决策变量xk为每年所确定的价格,则Xk={5,6,7,8}; 状态转移方程: k ?1 k

s

?x

阶段指标函数vk(sk ,xk)为每个阶段选择xk所取得的盈 利;例如v1(sk ,5)=9 过程指标函数为第k阶段状态为sk时到最后一个阶段 的总利润。 ? f ? (s ) ? 0 基本函数方程为: 6 6 ?
? ? f k ( sk ) ? max {vk ( sk , xk ) ? f k ?1? ( sk ?1 )} ? xk ?X k ( sk ) ? ?k ? 5, 4,3, 2,1 ?

2、逆序求解:
? k=5 ? f5(s5,x5) v5(s5,x5)+ f6*(s6) ? s x 5 6 7 ? ? 5 8+0 ? 6 4+0 ? 7 3+0 ? 8 f5*(s5) x5 *

8
8 4 3 4 5 6 7 8

4+0

? k=4 ? f4(s4,x4) v4(s4,x4)+ f5*(s5) ? s x 5 6 7 ? 5 5+8 5+4 ? 6 6+8 6+4 6+3 ? 7 7+4 7+3 ? 8 6+3

f4*(s4) x4 *

8
13 5 14 5 11 6,8 10 7

7+4 6+4

? k=3 ? f3(s3,x3) v3(s3,x3)+ f4*(s4) ? s x 5 6 7 ? ? 5 4+13 4+14 ? 6 8+13 8+14 8+11 ? 7 9+14 9+11 ? 8 6+11

f3*(s3) x3 *

8
18 22 9+10 23 6+10 17 6 7 6 7

? k=2 ? f2(s2,x2) v2(s2,x2)+ f3*(s3) ? s x 5 6 7 ? ? 5 2+18 2+22 ? 6 5+18 5+22 5+23 ? 7 5+22 5+23 ? 8 7+23

f2*(s2) x2 *

8
24 28 5+17 28 7+17 30 6 7 7 7

? k=1 ? f1(s1,x1) v1(s1,x1)+ f2*(s2) ? s x 5 6 7 8 ? 5 9+24 9+28 ? 6 7+24 7+28 7+28 ? 7 6+28 6+28 6+30 ? 8 8+28 8+30
S1=8 X1=8 s2=8

f1*(s1) x1 * 37 35 36 38 6 6,7 8 8
x5=5

x2=7 s3=7 x3=6 s4=6 x4=5 s5=5

2. 资源配置问题
如何将有限的资源分配给若干种生产活动,并使资源
利用的收益最大是经济活动中常见的问题,动态规划 可以求解一些线性规划无法解决的资源配置问题。 一般的资源分配问题可以描述为如下的规划问题: max: z = g1(x1) + g2(x2) + . . . + gn(xn) x1 + x2 + . . . + xn = a xi ? 0 i = 1, . . ., n

例:某厂为扩大生产能力,拟订购某种成套4— 6套,以分配给其所辖1、2、3个分厂使用。 预计个分厂分的不同套数的设备后,每年创

造的利润(万元)如下表所示。该厂应订购
几套设备并如何分配,才能使每年预计创利

总额最大?
分 利润(万元) 厂 0套 1套 2套 1 0 3 5 2 0 4 6 3 0 2 5 3套 6 7 9 4套 7 8 8 5套 6 9 8 6套 5 10 7

建立动态规划模型:

1.
2. 3.

阶段与分厂相联系, 阶段 k 只考虑分配分厂 k 的设备套数;
状态变量 sk 表示 k 分厂可分配的设备套数; 决策变量 xk 表示决定在 k 分厂使用的设备套数;

4.
5.

状态转移方程: sk+1 = sk - xk;
阶段函数: vk(sk,xk)为k分厂使用设备xk时的获利 ,从第一分厂到第k分 厂的总获利

fk(sk)=max{ vk(sk,xk)+fk+1(sk+1)}
6. 基本状态方程
? f ? (s ) ? 0 4 ? 4 ? ? ? ? f k ( sk ) ? x max ){vk ( sk , xk ) ? f k ?1 ( sk ?1 )} k ? X k ( sk ? ?k ? 3, 2,1 ?

k=3
v,( s3, x3)+f 4 (s4) S 0 1 2 3 4 5 6 x 0 0+0 0+0 0+0 0+0 0+0 0+0 0+0 2+0 2+0 2+0 2+0 2+0 2+0 5+0 5+0 5+0 5+0 5+0 9+0 9+0 9+0 9+0 8+0 8+0 8+0 8+0 8+0 7+0 1 2 3 4 5 6 0 2 5 9 9 9 9 0 1 2 3 3 3 3
*

f 3 (s3)

*

x3

*

k = 2: s3 = s2 – x2
v 2( s2, x2)+f 3 (s3) S 0 1 2 3 4 5 6 x 0 0+0 0+2 0+5 0+9 0+9 0+9 0+9 4+0 4+2 4+5 4+9 4+9 4+9 6+0 6+2 6+5 6+9 6+9 7+0 7+2 7+5 7+9 8+0 8+2 8+5 9+0 9+2 10+0 1 2 3 4 5 6 0 4 6 9 13 15 16 0 1 1,2 0,1 1 2 3
*

f 2 (s2)

*

x2

*

k = 1:s2 = s1 - x1
* v1( s1, x1)+f 2 (s2) * f 1 (s1)

x1

*

0 4 5 6 0+13 0+15 0+16

1 3+9 3+13 3+15

2 5+6 5+9 5+13

3 6+4 6+6 6+9

4 7+0 7+4 7+6

5 6+0 6+4

6 13 16 5+0 18 0 1 1,2

因此得到:x1 = 2 ,s2=6-2=4, x2 = 1 ,s3=4-1=3 , x3 = 3
x1 =1 ,s2=6-1=5, x2 = 2 ,s3=5-2=3 , x3 = 3

即:p={2,1,3}或{1,2,3}获利18万元

3. 复合系统的工作可靠性问题
例: 为保证设备可靠运行, 一些关键部件往往由多个器

件并联运行, 如果器件 i 的失效概率为 pi, 则 xi 个器
件并联工作的可靠性为(1 - pixi), 假定每个器件的采 购费用为 ci, 在满足总采购费用不超过预算限制 C 的前提下, 使设备可靠性最高的规划问题可以描述 为:
max: z = ? (1 ?
i ?1 n

p ixi )

s.t.

?c
i ?1

n

i

xi ? c

该问题为整数非线性规划,可以用动态规 划求解,设关键器件数n = 3,总费用为

120万元。器件的单价与可靠性如下表:
器件号i
1 2 3

单价(万元)
30 15 20

失效概率pi
0.1 0.2 0.5

建立动态规划模型:
阶段与器件挂钩,第 k 阶段仅考虑器件k的采购数量; sk 表示k 阶段可使用的采购费用;

xk 表示 k阶段决定购买k 器件的数量;
状态转移方程: sk+1 = sk - ck xk; 递推阶段函数:vk(sk,xk)=1-pkxk

总可靠性fk(sk) = max { ( 1 - pkxk) fk+1(sk+1)}

基本状态方程:
? f ? (s ) ? 0 ? 4 4 ? ? ? ? f k ( sk ) ? x max ){vk ( sk , xk ) * f k ?1 ( sk ?1 )} k ? X k ( sk ? ?k ? 3, 2,1 ?

k=3
S 20 30 40 50 60 70 75 x v (x)+f4 (s4 ) 1 2 0.5*1 0.5*1 0.5*1 0.5*1 0.5*1 0.5*1 0.5*1 (1-0.25)*1 (1-0.25)*1 (1-0.25)*1 (1-0.25)*1 (1-0.25)*1 f 3* (s3 ) 3 0.5 0.5 0.75 0.75 (1-0.125) *1 0.875 (1-0.125) *1 0.875 (1-0.125) *1 0.875 1 1 1 1 3 3 3 x3 *

k = 2: s3 = s2 – c2x2
S 35 40 50 60 70 80 90 v (x)*f 3(s3) x 1 0.8*0.5 0.8*0.5 0.8*0.5 0.96*0.5 0.8*0.75(s3=60-15=45) 0.96*0.5 0.8*0.75 0.8*0.875 0.8*0.875 f 2*(s2) 2 3 4 0.4 0.4 0.48 0.48 1 1 2 2 2 2 2 x2*

0.96*0.75 0.992*0.5 0.72 0.96*0.75 0.992*0.5 0.9984*0.5 0.72 0.96*0.875 0.992*0.5 0.9984*0.5 0.84

k = 1:s2 = s1 –c1 x1
v (x)*f 2(s2 ) 1 65 70 80 90 100 110 120 0.9*0.4 0.9*0.4 0.9*0.48 0.9*0.48(s2=90-30=60) 0.9*0.72 0.9*0.72 0.9*0.84 0.99*0.4 0.99*0.48 0.99*0.48 2 0.36 0.36 0.432 0.432 0.648 0.648 0.756 1 1 1 1 1 1 1 f 1* (s1 ) x1 *

因此得到:
x1 = 1 ,s2=120-30=90, x2 = 2 ,s3=90-2*15=60 , x3 = 3

即:p={1,2,3} 可靠性为0.756

4、生产调度(生产与库存)问题
某厂根据市场预测,确认今后4个月该厂 的一种主要产品每月的需求的量d为3,2, 3,2万件。已知每月生产固定费用b为2 千元,但若当月不生产则为0;产品成本 c为1千元/件,贮存费用h为 0.2千元/万件 /月。最大存贮能力w为4万件。若第1月 初五库存产品,第4月末也不留库存,则 该厂怎样安排生产,才能使今后4个月的 总费用最少?

建立动态规划模型: 1、阶段与时间相联系, 阶段 k表示月份 2、状态变量 sk 表示 k 月初的库存量; 3、决策变量 xk 表示 k月的产量; 4、若dk为需求量,则状态转移方程: sk+1 = sk +xkdk; 5、阶段函数: vk(sk,xk)为k月的生产费用 , 过程函数: fk(sk)为从第一月到第k月的总生产费用 fk(sk)=max{ vk(sk,xk)+fk+1(sk+1)} 6. 基本状态方程
?b ? cxk ? hxk , 当xk ? 0 vk ? sk , xk ? ? ? hsk , 当xk ? 0 ?

? f 5 ? ( s5 ) ? 0 ? ? ? ? min ? f k ( sk ) ? x ?X ( s ){vk ( sk , xk ) ? f k ?1 ( sk ?1 )} k k k ? ? k ? 4, 3, 2,1 ?

k=4
这是最后一个月,需求为2,无库存s5=0。由 状态方程知:s4=2-x4,x4?0,则s4只能是0,1,2
f4(s4,x4) s4 x4 0 1 2 0.2s4 0 2+x4+0.2s4 1 2 4 3.2 0.4 4 3.2 0.4 2 1 0 f4 (s4)
*

x4

*

k=3
这是第3个月,需求为3。由状态方程知: s4=s3+x3-3,又由于 2? s4 ? 0,即2? s3+x3-3 ? 0,s3 ≤ w=4则s3取值是0,1,2,3,4。 X3={x3|3≤s3+x3≤5,s3=0,1,2,3,4}
f 3 (s 3 ,x 3 ) 0.2s 3 +f 4 * (s 4 ) 3 +0.2s 3 +f 4 * (s 4 ) 2+x s3 x3 0 1 2 3 4 0 1 2 8.2 7.6 5 3 9 8.4 5.8 4 9.2 6.6 5 7.4 7.4 6.6 5.8 4.6 4 5 4 3 0 0 f 3 * (s 3 ) x3 *

4.6 4

7.4 6.8 4.2

k=2

这是第2个月,需求为2。第一个月无库存 s1=0,s2 =s1+x1-3=x1-3,又因x1 ≤5,则s2取值 是0,1,2。由状态方程知:s3=s2+x2-2,又由 于 4? s3 ? 0,即4? s2+x2-2 ? 0; X2={x2|2≤s2+x2≤6 且x2 ≤5,s2=0,1,2}
f2(s2,x2) 0.2s2+f3*(s3) 2+0.2s2+f3*(s3) 2+x s2 x2 0 1 2 0 1 2 3 4 5 11.4 10.6 7.8 2 1 0 f2*(s2) x2*

11.4 11.6 11.8 11.8 10.6 10.8 11 10.8 11.2 7.8 10 10.2 10 10.4

k=1

这是第1个月,需求为3。第一个月无库存 s1=0,s2 =x1-3=x1-3,又因x1 ≤5,s2取值是0, 1,2。X1={x1|3≤x1≤5}

f1(s1,x1) 2+x1+0.2s1+f1 (s1) f1 (s1) x1 s1 x1 3 4 5

*

*

*

0 16.4 16.6 14.8 14.8

5

5 设备更新问题
设备在使用全过程中会遭受磨损, 使用一段 时间后就要维修, 而且使用的时间越长, 维 修费用越高, 设备使用多少时间在经济上最 合算, 就是设备更新问题。

例: 某设备的年效益和年均维修费用如下表,

如何在未来的5年内进行更新决策。
使用年限 效益 r 维修费u 更新费c 0 5 0.5 0.5 1 4.5 1 1.5 2 4 1.5 2.2 3 3.75 2 2.5 4 3 2.5 3

分析:
? 阶段 k = 1, 2, 3, 4, 5;

?
?

sk 表示 k 年初设备已使用的年限;
xk 为 k 年初决定设备是继续使用还是更新的决

策变量: xk = 1表示继续使用, xk = 0表示更新;
? 状态转移方程: sk+1 = sk + 1,xk=1;

sk+1 = 1,xk=0

?阶段函数:
vk(sk) = r(skxk) - u(skxk) - c(sk)(1-xk ) r(0) - u(0) - c(sk) (xk= 0)

vk(sk) =
r(sk) - u(sk ) ?递推函数: fk(sk) = max{vk(sk) + fk+1(sk+1)} (xk= 1)

?

k = 5 状态变量 s5 可取 1, 2, 3, 4 f5(1) = maxx1=0,1{r(0) - u(0) - c(1), r(1) - u(1)} = max {5-0.5-1.5, 4.5-1}= 3.5 (x5*=1) f5(2)=max{5-0.5-2.2, 4-1.5}= 2.5 (x5*=1) f5(3)=max{5-0.5-2.5, 3.75-2}= 2 (x5*=0) f5(4)=max{5-0.5-3, 3-2.5} = 1.5 (x5*=0)

v 5 (s 5 ,x 5 )+f 6 * (s 6 ) r(0)-u(0)--c(1) s x 1 2 3 4 r(1)-U(1) 0 1 3 3.5 2.3 2.5 2 1.75 1.5 0.5

f 5 * (s 5 )

x

* 5

3.5 2.5 2 1.5

1 1 0 0

? k=4

状态变量 s4 可取 1, 2, 3 (x4* = 0) (x4* = 0) (x4* = 0)
f 4 (s 4 ) r(1)-U(1)+f5*(s5) 0 6.5 5.8 5.5 1 5 4.5 3.25 6.5 5.8 5.5
*

f4(1) = max{r(0)-u(0)-c(1)+f5(1), r(1)-u(1)+ f5(2)}
= max {5-0.5-1.5+3.5, 4.5-1+2.5} = 6.5 f4(2) = max {5-0.5-2.2+3.5, 4-1.5+2} = 5.8 f4(3) = max {5-0.5-2.5+3.5, 3.75-2+1.5} = 5.5
v 4 (s 4 ,x 4 )+f 5 (s 5 ) r(0)-u(0)--c(1)+f5*(s5) s x 1 2 3
*

? k=3

状态变量 s3 可取 1, 2,

f3(1) = max{r(0) - u(0) - c(1) + f4(1), r(1) - u(1) + f4(2)} = max {5-0.5-1.5+6.5, 4.5-1+5.8} = 9.5 f3(2) = max {5-0.5-2.2+6.5, 4-1.5+5.5} = 8.8
v 3 (s 3 ,x 3 )+f 4 * (s 4 ) r(0)-u(0)--c(1)+f4*(s4) s x 1 2 0 9.5 8.8 r(1)-U(1)+f4*(s4) 1 9.3 8 9.5 8.8

(x3* = 0) (x3* = 0)
f 3 * (s 3 )

? k=2 状态变量 s2 可取 1, f2(1) = max{r(0) - u(0) - c(1) + f3(1), r(1) - u(1) + f3(2)} = max {5-0.5-1.5+9.5, 4.5-1+8.8} = 12.5 (x2* = 0)

v 2 (s 2 ,x 2 )+f 3 (s 3 ) r(0)-u(0)--c(1)+f3*(s3) s x 1 0 12.5 r(1)-U(1)+f3*(s3) 1 12.3

*

f 2 (s 2 )

*

12.5

k = 1时状态变量 s1 只能取 0 f1(0) = max{r(0) - u(0) - c(0) + f2(1), r(0) - u(0) + f2(1)} = max{5-0.5-0.5+12.5, 5-0.5+12.5} = 17 (x1* = 1)

v 1 (s 1 ,x 1 )+f 2 (s 2 ) r(0)-u(0)--c(1)+f2*(s2) s x 0 0 16.5 r(1)-U(1)+f2*(s2) 1 17

*

f 1 (s 1 )

*

17

最优策略为: k= 1 2 更新 更新 3 更新 4 不更新 5

不更新

6、机器负荷分配问题
有某种机床,可以在高低两种不同的负荷下进行生产,在高

负荷下生产时,产品的年产量为 g ,与年初投入生产的机床
数量 u1 的关系为 g=g(u1)=8u1 ,这时,年终机床完好台数将 为,au1 ( a为机床完好率, 0 < a< 1 ,设 a=0.7 )。在低负荷 下生产时,产品的年产量为 h ,和投入生产的机床数量的关 系为 h=h(u2)=5u2 ,相应的机床完好率为 b ( 0<b<2 ,设 b=

0.9 ),一般情况下 ( a < b )。假设某厂开始有 x1=1000 台完
好的机床,现要制定一个五年生产计划,问每年开始时如何 重新分配完好的机床在两种不同的负荷下生产的数量,以使

在5年内产品的总产量为最高。

解:首先构造这个问题的动态规划模型。 1.分阶段:设阶段变量 k 表示年度,因此, 阶段总数 n = 5 。 2. 状态变量:用 sk 表示第 k 年度初拥有的 完好机床台数,同时也是第 k-1 年度末时 的完好机床数量。 3. 决策变量:用 uk 表示第 k 年度中分配 于高负荷下生产的机床台数。于是 sk-uk 便 为该年度中分配于低负荷下生产的机床台 数。

4.状态转移方程为:

sk ?1 ? au k ? b ( sk ? u k ) ? 0.7u k ? 0.9( sk ? uk ) ? 0.9 sk ? 0.2u k k ?1 , 2 , ? , 6
5.决策变量的取值:在第 k 段为

U k (s k ) ? {u k 0 ? u k ? s k }

6.阶段指标函数 令 vk(sk,uk ) 表示由第 k 年的状态 sk 出发,采
取uk分配方案的产品产量.

vk (sk , uk ) ? 8uk ? 5( sk ? uk )
7.条件最优目标函数递推方程 令 fk(sk ) 表示由第 k 年的状态 sk 出发,采取 最优分配方案到第5年度结束这段时间的产品 产量,根据最优化原理有以下递推关系:

f k ( sk ) ? max ?vk ( sk , uk ) ? f k ?1* ( sk ?1 )?
uk ?U k

? max{[8uk ? 5( sk ? uk )] ? f k ?1[0.7uk ? 0.9( sk ? uk )]}
uk ?U k

k ?1 , 2 , ? , 5 f 6 ( s6 ) ? 0

下面采用逆序递推计算法,从第5年度开始递
推计算. K=5 时有

f 5 ( s5 ) ? max {[8u5 ? 5( s5 ? u5 )] ? f 6 ( sk )}
0 ? uk ? s 5

? max {[8u5 ? 5( s5 ? u5 )]}
0 ? uk ? s 5

显然,当 u5*=s5 时,f5(s5) 有最大值,相应

的有 f5(s5) = 8s5 。

K=4 时有:

f 4 ( s4 ) ? max {[8u4 ? 5( s4 ? u4 )]
0? u4 ? s4

? f 5 [0.7u4 ? 0.9( s4 ? u4 )]}
? max {[8u4 ? 5( s4 ? u4 )] ?
0? u4 ? s4

? 8[0.7u4 ? 0.9( s4 ? u4 )]}

? max {13 .6u4 ? 12 .2( s4 ? u4 )}
0 ? u4 ? s 4

因此,当 u4*= s4 时,有最大值 f4(s4)=13.6s4
K=3 时有:

f 3 ( s3 ) ? max {[8u3 ? 5( s3 ? u3 )] ? f 4 ( s4 )}
0 ? u3 ? s3

? max {17 .55 u3 ? 17 .22( s3 ? u3 )}
0? u3 ? s3

可见,当 u3*= s3 时,有最大值 f3(s3) =17.55s3 。 K=2 时有:

f 2 ( s2 ) ? max {[8u2 ? 5( s2 ? u2 )] ? f 3 ( s3 )}
0 ? u2 ? s 2

? max {[8u2 ? 5( s2 ? u2 )] ?
0? u2 ? s2

? 17.55[0.7u2 ? 0.9( s2 ? u2 )]}
? max {[ 20 .25 u2 ? 20 .8( s2 ? u2 )]
0 ? u2 ? s 2

此时,当 u2*= 0 时有最大值,即 f2(s2)=20.8s2, 其中 s2=0.7u1+0.9(s1-u1)

K=1 时有: f1 ( s1 ) ? max {8u1 ? 5( s1 ? u1 ) ?
0? u1 ? s1

? 20.8[0.7u1 ? 0.9( s1 ? u1 )]}

? max { 22 .55 u1 ? 23 .7( s1 ? u1 )}
0 ? u1 ? s1

当 u1*= 0 时, 有最大值,即 f1(s1)=23.7s1 , 因

为 s1=1000 , 故 f1(s1)=23700 个产品。
按照上述计算顺序寻踪得到下述计算结果:

u ? 0 s1 ? 1000 g1 ( s1 , u1 ) ? 5000 f1 ( s1 ) ? 23700 u ? 0 s2 ? 900 g2 ( s2 , u2 ) ? 4500 f 2 ( s2 ) ? 18720
* 1 * 2

u ? s3 s3 ? 810 g3 ( s3 , u3 ) ? 6480 f 3 ( s3 ) ? 14216

u ? s4 s4 ? 567 g4 ( s4 , u4 ) ? 4536 f 4 ( s1 ) ? 7711
u ? s5 s5 ? 387 g3 ( s3 , u3 ) ? 3176 f1 ( s1 ) ? 3176

* 3 * 4 * 5

上面所讨论的最优决策过程是所谓始端
状态固定,终端状态自由.如果终端也附加

上一定的约束条件,那么计算结果将会与之
有所差别.例如,若规定在第五个年度结束

时,完好的机床数量为500台(上面只有278
台),问应该如何安排五年的生产,使之在满

足这一终端要求的情况下产量最高?
解:由状态转移方程

s k ?1 ? au k ? b(s k ? u k ) ? 0.7u k ? 0.9(s k ? u k ) 有
s 6 ? 0.7u 5 ? 0.9(s5 ? u 5 ) ? 500 由此式得
u 5 ? 4.5s5 ? 2500
当 k=5 时有

f 5 (s 5 ) ? max {8u 5 ? 5(s 5 ? u 5 )}
0? u k ?s 5

? 8(4.5u 5 ? 2500 ? 5(s 5 ? 4.5u 5 ? 2500 ) )

? 18.5s5 ? 7500
当 k=4 时有

f 4 (s 4 ) ? max {[8u 4 ? 5(s 4 ? u 4 )] ? f 5 (s 5 )}
0? u 4 ?s 4

? max {8u 4 ? 5(s 4 ? u 4 ) ? 18.5u 5 ? 7500 }
0? u 4 ?s 4

? max {8u 4 ? 5(s 4 ? u 4 ) ?
0? u 4 ?s 4

? 18.5[0.7u 4 ? 0.9(s 4 ? u 4 )] ? 7500 }
? max {21.7s 4 ? 0.75u 4 ? 7500 }
0? u 4 ?s 4

显 然 , 只 有 取

u4*=0 , 有 最 大 值

f4(s4)=21.4s4-7500

当 k=3 时有: f 3 (s 3 ) ? max {[8u 3 ? 5(s 3 ? u 3 )] ? f 4 (s 4 )}
0? u 3 ?s 3

? max {[8u 3 ? 5(s 3 ? u 3 )] ?
0? u 3 ?s 3

? 21.7[0.7u 3 ? 0.9(s 3 ? u 3 )] ? 7500 }
? max {?1.3u 3 ? 24.5s 3 ? 7500 }
0? u 3 ?s3

显 然 , 只 有 取 u3*=0 , f3(s3) 有 最 大 值

f3(s3)=24.5s3-7500 。

当 k=2 时有:

f 2 (s 2 ) ? max {[8u 2 ? 5(s 2 ? u 2 )] ? f 3 (s 3 )}
0? u 2 ?s 2

? max {[8u 2 ? 5(s 2 ? u 2 )] ?
0? u 2 ?s 2

? 24.5[0.7u 2 ? 0.9(s 2 ? u 2 )] ? 7500 }
? max {?1.9u 2 ? 27.1s 2 ? 7500 }
0? u 2 ?s 2

显 然 , 只 有 取 u2*=0 , f2(s2) 有 最 大 值 f2(s2)=27.1s2-7500 。

当 k=1 时有:

f1 (s1 ) ? max {8u 1 ? 5(s1 ? u 1 ) ? f 2 (s 2 )}
0 ? u1 ? s1

? max {8u 1 ? 5(s1 ? u 1 ) ?
0 ? u1 ? s1

? 27.1[0.7 u 1 ? 0.9(s1 ? u 1 )] ? 7500 }

? max {?2.4u1 ? 29.4s1 ? 7500 }
0 ? u1 ? s1

显 然 , 只 有 取 u1*=0 , f1(s1) 有 最 大 值 f1(s1)=29.4s1-7500 。

s1 ? 1000 (台)
* 1 * 1

u ?0
* 1
* 2

s2 ? 0.7u ? 0.9(s1 ? u ) ? 0.9s1 ? 900 u ? 0
s 3 ? 0.7u ? 0.9(s 2 ? u ) ? 0.9s 2 ? 810 u ? 0
* 2 * 2 * 3

s 4 ? 0.7u ? 0.9(s 3 ? u ) ? 0.9s 3 ? 729 u ? 0
* 3 * 3 * 4

s 5 ? 0.7u ? 0.9(s 4 ? u ) ? 0.9s 4 ? 656 * * u 5 ? 4.5s 5 ? 2500 ? 454 s 5 ? u 5 ? 204
* 4 * 4

s 6 ? 0.7u 5 ? 0.9(s5 ? u 5 ) ? 500
f1 ( s1 ) ? 29.4s1 ? 7500 ? 29400 ? 7500 ? 21900

7、非线性规划问题求解
某公司拥有资金 10 万元,若投资于项目 i (i=

1,2,3) 的投资额为 xi 时,其收益分别为
g1(x1)=4x1 , g2(x2)=9x2 , g3(x3)=2x32 ,问应如何 分配投资数额才能使总收益最大? 这是一个与时间无明显关系的静态最优化 问题,可列出其静态模型为:

max z ? 4 x1 ? 9 x 2 ? 2 x ? x1 ? x 2 ? x3 ? 10 满足 ? (i ? 1,2,3) ? xi ? 0
2 3

我们可以人为地赋予它“时段”的概念,

用动态规划方法求解
解:(解法1)首先用逆序构造动态规划模型。

1.分阶段:设阶段变量 k 表示依次对第 k 个
项目投资,因此,阶段总数 n = 3。

(k=1,2,3)

2. 状态变量:用 sk 表示已经对第 1 至 第
k-1 个项目投资后的剩余资金;即第 k 段

初拥有的可以分配给第 k 到第3个项目的
资金额 (单位:万元) 。 3. 决策变量:用 xk 表示对第 k 个项目投 资 的资金数量(单位:万元)。

4.状态转移方程为: s k ?1 ? s k ? x k 5.决策变量的取值: 0 ? xk ? sk

6. 基本方程为:
最优指标函数 fk(sk) 表示第 k 阶段,初 始状态为 sk 时,从第 k 到第 3 个项目所获 最大收益

? f k (sk ) ? max {g k ( xk ) ? f k ?1 (sk ?1 )} ? 0 ? xk ? s k ? ? f 4 (s4 ) ? 0 ?

k ? 3,2,1

当 k=3 时:

f 3 (s 3 ) ? max {2 x }
0? x 3 ?s3 2 3

取 x ? s3 得
2 3

? 3

f 3 (s 3 ) ? max {2 x } ? 2s
0? x 3 ?s3 2 3

当 k=2 时:
2 ? max {9x 2 ? 2s 3 } f 2 (s 2 ) ? max {9x 2 ? f 3 (s 3 )} 0? x ?s
0? x 2 ?s 2
2 2

? max {9 x 2 ? 2(s 2 ? x 2 ) }
2 0? x 2 ?s 2

令 h 2 (s 2 , x 2 ) ? 9x 2 ? 2 ? (s 2 ? x 2 )

2

dh 2 由 ? 9 ? 4 ? (s 2 ? x 2 ) ? (?1) ? 0 dx 2 9 解得 x 2 ? s2 ? 4
而 d h2 ?4?0 2 dx 2
2

所以

9 x 2 ? s2 ? 是极小点 4
2 2

极大值只可能在 [0 ,s2] 端点取得,

f 2 (0) ? 2s

或 f 2 (s 2 ) ? 9s 2

当 f 2 (0) ? f 2 (s 2 ) 时解得 s 2 ? 9 2

f 所以当 s 2 ? 9 2 时, 2 (0) ? f 2 ( s 2 )

此时应有 x ? 0
当 s 2 ? 9 2 时, f 2 (0) ? f 2 ( s 2 )

? 2

此时应有 x ? s 2
当 k=1 时:

? 2

f 1 ( s1 ) ? max {4 x1 ? f 2 ( s 2 )}
0 ? x1 ? s1

假定 s2 ? 9 / 2 这时取 f 2 ( s2 ) ? 9s2
f 1 (10) ? max {4x 1 ? 9s1 ? 9x 1 }
0? x1 ?10

? max {9s1 ? 5x 1} ? 9s1
0 ? x1 ?10

但此时 s 2 ? s1 ? x1 ? 10 ? 0 ? 10 ? 9 2
矛盾,所以舍去 sk < 9/2

假定 s2 ? 9 / 2 这时取 f 2 ( s2 ) ? 2s
0 ? x1 ?10

2 2
2

f 1 (10 ) ? max {4 x1 ? 2( s1 ? x1 ) }



h1 ( s1 , x1 ) ? 4 x1 ? 2 ? ( s1 ? x1 )

2

dh1 由 ? 4 ? 4 ? ( s1 ? x1 ) ? ( ?1) ? 0 dx1
解之得驻点 x1 ? s1 ? 1
d h1 而 ?1? 0 2 dx1 所以 x1 ? s1 ? 1
2

是极小值

故 极大值只能在 [0,10] 的端点取得,比

较[0,10]两个端点的函数值

? 当 x1 ? 0 时
而当 x1 ? 10 时
? 1 ? 1

f1 (10) ? 200
f1 (10) ? 40

? x ?0 s 2 ? s1 ? x ? 10 ? 0 ? 10 * ? s2 ? 9 2 ? x2 ? 0
故 s3 ? s2 ? x ? 10 ? 0 ? 10
所以 x ? s3 ? 10
? 3

? 2

即全部资金投于第3个项目

(解法2) 用顺序解法
1. 阶段划分: (同上) 和决策变量

2. 状态变量: 用 sk 表示可用于第1到第 k-1
个项目投资的金额,即对第 k 个项目到第3

个项目投资后的剩余资金数量。
3. 决策变量: (同上)

4. 状态转移方程:

s 4 ? 10
k ?1, 2 , 3

sk ? sk ?1 ? xk

5. 决策变量的取值范围:

0 ? xk ? sk ?1

k ?1, 2 , 3

6. 最优指标函数: 令 fk(sk+1) 表示第 k 段投资额 sk+1 为时,第1
到第 k 项目所获的最大收益,此时顺序解法 的基本方程为:

? f k (sk ?1 ) ? max {g k ( xk ) ? f k ?1 (sk )} ? 0? xk ? sk ?1 ? ? f 0 (s1 ) ? 0 ?

k ? 1,2,3

当 k=1 时,有

f1 ( s2 ) ? max { g1 ( x1 ) ? f 0 ( s1 )}
0? x1 ? s 2

? max { 4 x1 } ? 4 s2
0 ? x1 ? s 2

x ? s2

? 1

当 k=2 时,有

f 2 ( s 3 ) ? max [9 x 2 ? f 1 ( s 2 )]
0 ? x 2 ? s3

? max [9 x 2 ? 4 s 2 ]

? max [9 x 2 ? 4( s3 ? x 2 )]
0 ? x 2 ? s3

0 ? x 2 ? s3

? max [5 x 2 ? 4 s3 ]
0 ? x 2 ? s3

? 9s 3
当 k=3 时,有
0 ? x3 ? s 4 2 3

x ? s3
* 2

f 3 ( s 4 ) ? max [2 x ? f 2 ( s3 )]
? max [2 x ? 9( s 4 ? x3 )]
0 ? x3 ? s 4 2 3



h( s4 , x3 ) ? 2 x ? 9 ? ( s4 ? x3 )
2 3



dh ? 4 x3 ? 9 ? 0 dx3

?

d h ?4 2 dx3

2

? x3 = 9/4 为极小点。

极大值应在[0,s4] =[ 0,10 ] 端点取得

当 x3 ? 0 时 当 x3 ? 10 时

?

x ? 10
* 3

? 3

f 3 (10 ) ? 90 f 3 (10 ) ? 200

再由状态转移方程逆推:

s3 ? s4 ? x ? 10 ? 10 ? 0

得 x ?0

? 2

s2 ? s3 ? x ? 0
得 x ? s2 ? 0
? 1

? 2


赞助商链接
相关文章:
动态规划习题集全
动态规划习题集 - 动态规划专题训练 护卫队 【问题描述】 护卫车队在一条单行的街道前排成一队,前面河上是一座单行的桥。因为街道是一条单行道,所以任 何车辆...
《算法分析与设计》期末考试复习题纲(完整版)_图文
《算法分析与设计》期末考试复习题纲(完整版)_工学_高等教育_教育专区。信息与...一个问题可用动态规划算法或贪心算法求解的关键特征是问题的( B )。 A.重叠子...
运筹学试卷及答案完整版
运筹学试卷及答案完整版 - 《运筹学》模拟试题及参考答案 一、判断题(在下列各题中,你认为题中描述的内容为正确者,在题尾括号 内写“√” ,错误者写“×”...
(5) 算法分析与设计 动态规划 一_进阶_教学视频大全
计算机专业学生主要教材:《计算机算法设计与分析》 第四版 王晓东 编著适合ACM队员,大三,大四计算机专业学生。视频教程,羽天培训学院全套教学,在线学习进阶课程,(5)...
动态规划动态转移方程大全
41 线性动态规划 4 ---找数 线性扫描 sum:=f+g[j]; (if sum=Aim then getout; if sum<Aim then inc(i) else inc(j);) 42 线性动态规划 5 ---...
信息学奥赛-动态规划测试讲解_初中其他_教学视频大全
掌握动态规划算法16道测试习题的讲解在期末作业里可以下载到测试题目和标程由于数据量太大,没有上传,如需要可以qq20396035联系视频教程,润玉教育全套教学,在线学习...
一堆石头分两堆问题分析
一堆石头分两堆问题分析_计算机软件及应用_IT/计算机_专业资料。石头分两堆问题如何使用动态规划排列解决的过程详解 经典的 N-P 问题分析 石头分两堆使其...
运筹学--第七章 动态规划
第7章 动态规划 25页 免费如要投诉违规内容,请到百度文库投诉中心;如要提出功能...现需找出明年的最优生产方案,使该厂能在完成合同的情况下使全 年的生产费用最...
历届NOIP搜索算法全集 动态规划
历届 NOIP 搜索算法全集 转自:oifans 用动态规划来解背包问题 在历届 NOIP 竞赛中,有 4 道初赛题和 5 道复赛题均涉及到背包问题,所谓的背包问题,可 以描述...
更多相关标签: