学习-运筹学-p第七章

1.

在70年代， 了两本饶有 的数学家自传。一本是美籍波兰数学家乌 （

Ulam

1909—

）

写的《Adventures

of

a

Mathematician》，另一本是数学家（Richard

Bellman，1920—）写的《TheEyeofHurricane》（飓风眼），两位都是当代闻名的应用数学大师。1970年，

数学会和SIAM宣布，第一届维纳应用数学奖授予Bellman。SIAM：Society

for

Industrial

and

Applied

Mathematics2.

二次年成立后，工业和应用数学大力支持应用数学，1952，随着数学向各个领，

都有相当比例的数学家域渗透，许多

在工作。著名的公司（RAND，即Research

andNew

Development）就产生了Bellman。3.

1950年，Bellman开始研究多段多层决策问题，产生了一种数学技巧，就是今天的动态规划，1957年他写的《动态规划》一书，标志这一分支的产生。4.动态规划模型的分类（1）

离散(Ⅰ)确定性(Ⅱ)随机性（2）

连续(Ⅰ)确定性(Ⅱ)随机性5.本课程仅学习离散确定性动态规划。第一节动态规划的基本思想和方法一.动态规划研究的对象1.例1如图6-1是一个有向网络图，从点运到点，其两点之间连线上数字表示两点之间距离，今求选择一条由到的线路，使总距离为最短。1241AC2B1DC3B2C14456142如何解决这个问题呢？可以采取穷举法。即把到的所有路线的距离算出来，然后比较找出显著最短者，相应找到了最短路线。把A到B1，B2分为第一阶段B1到C1，C2，C3，B2到C1，C2，C3分为第二阶段C1D，C2D

，C3D分为第三阶段称A为第一阶段的状态

B1，B2为第二阶段的状态C1，C2，C3为第三阶段的状态这样从A到D共有=1×2×3×1=6条不同路线，比较6条不同路线的距离值，找出A

B2

C3D为最短路线，其长为7。2.例1的方法不宜推广。当阶段，状态很多时计算量是十分惊人的，例如阶段=100，每一阶段有10个状态，则两点之间的所有路线

数=1099条连最快计算机也难完成，只能另辟蹊径。3.(1)有这样一类活动过程，若将该过程划分为若干个互相联系的阶段，在它的每一个阶段都需要作出决策，并且每一个阶段的决策确定以后，常影响下一个阶段决策，从而影响整个过程的活动路线，则称此过程为多阶段决策过程。动态规划是解决多阶段决策最优化的

法。各个阶段所确定的决策就构成一个决策序列，称为一个策略。即图6-1种一条路线就是一条策略。动态规划开始形成时，阶段是时间段。就有了“动态”含义。但不同实际问题的动态规划模型一样，所以动态规划研究的范围也就广泛了。例如设备分配问题，生产存贮问题，设备更新问题等。二.动态规划的基本方法1.基本概念（1）阶段（stage）（Ⅰ）对所给问题的过程，恰当的分成若干个相互联系的最小子过程，这最小子过程就称为阶段。用j表示阶段变量（Ⅱ）例如ABi(i=1,2)（2）状态（state）（Ⅰ）某阶段的出发位置称为状态。用Sj表示j阶段的状态（Ⅱ）例S1

=A，S2=B1或B2，S3=

C1,C2或C3（Ⅲ）Sj状态是j阶段出发点，是j-1的终点，如B1是2阶段始点，却是1阶段的终点（3）决策（Decision）决策是j阶段状态给定后，从该状态演变到j+1阶段状态的选择。用xj(sj)表示，简记xj。例如x2(B2)表示第二阶段开始于B2等，下一步所取的状态，它可取C1,C2或C3xj(sj)中的最优决策记为xj*(sj)

，或xj*（4）指标(index)在多阶段决策过程最优化问题中，数量指标函数是用来决定所实现过程的优劣的一种指标，它是状态和决策的函数。用dj(sj,xj)表示状态sj至xj之间的数量关系。指标dj(sj,xj)在不同问题中，含义也不同，可能是距离、利润、成本或资源消耗等。例如在图6-1中，d2(B1,C2)

，表示距离。(5)

累积指标（index

of

convergence）nj

j（Ⅰ）称

dj

(

s

j

,

x

j

)为状态s

j

至终点的累积指标n（Ⅱ）

f

j

(s

j

)=min

d

j

(s

j

,x

j

)为最小累积指标。j

jn（=max

d

j

(s

j

,x

j

)为最大累积指标。）j

j*（Ⅲ）

f

j

(s

j

)表示s

j

到终点D

的最短路长。（6）公式

f

j

(s

j

)=min

d

j

(s

j

,x

j

)

f

j

1

(x

j

)

Bellman公式（作为作业证明）2.基本思想和方法(1)生活中，大家均有这样的经验。

从校门出发，经过则从馆，体育馆而到宿舍的这条路线是最短的论，馆出发，经体育馆到宿舍的路线也是最短校门馆

体育馆

宿舍（2）这种生活经验推广到：若存在一条最短路p0p1

p2p3

…

pkpk+1

…

pn

（1）则pkpk+1

…

pn也是从pk到pn的最短路事实上，若存在从pk

pn更短的路，

pk

pk+1’

pk+1’…

pn-1’pn（2）则p0pk

pk+1’

pk+1’…

pn-1’pn比（1）更短路，

。(3)路的这一特性，它启发着 找最短路的方法。就是从最后一段开始，用由后向前逐步递推的方法，找出各点到D点的最短路线，最后求得由A点到D点的最短路线(4)因此，动态规划的方法是从终点逐段向始点方向寻找最短路线的 法。始点终点动态规划寻优方向行进方向3.图6-1解决步骤：1241AC2B1DC3B2C14456142（3f1

(

A)

minx1

*

A

B2（4）f1(A)=

d1(A1,B2)+

d2(B2

,

C3)+

d3(C3,D)即A到D的最短路线为A

B2

C3

D

。最短长为7（5）[注]上述步骤中：f1(A)的值仅计算得到最短路长具体最短路可从f1(A)中知AB2

，再f2(B2)从中知B2

C3

，最后从f3(C3)知C3

D

，即A

B2

C3

D

。三.Bellman定理从上面的计算过程中知，知道了阶段和阶段j+1之间关系是：

f

s

f

c

d

c

,

Di

1,2,3

f

s

mind

s

,

x

f

(x

)3 j

3 i

3 ij

j

j

j

j

j1

jj

2,1此递推关系时，要先求f3

,

f2

,

f1

，即要倒过来的顺序进行，从而从终点开始逐段向起点方向寻找最优途径。2.动态规划最优化原理“作为整个过程的最优策略具有这样的性质：即无论过去的状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。”这个原理是由

R.Bellman首先把多阶段决策问题的求解过程看成。利用这个原理，可以续的递推过程，由后向前逐步推算。在求解时，各状态前面的状态和决策，对其后面的问题来讲，只不过相当于其初始条件而已，并不影响后面过程的最优策略。动态规划的步骤：第一步：确定阶段，状态，指标第二步：计算最优累积指标，以及最优决策及累积指标递推关系第三步：f1(s1)就是s1到终点的最优化数值*

*

*x1

(s1)，x2

(s2),…,xn

(sn)就是最优决策，也称策略集合。动态规划的标号法：每一个结点sj上方标号为：[fj(sj)，xj*

(sj)]，且规定终点D的标号为[0,D]。特点：（Ⅰ）一目了然（优点）（Ⅱ）fj(sj)，xj*

(sj)还是要计算，虽多一道工序，（繁琐点），但易计算。第二节 动态规划应用举例i

ix

0,x

是整数1

2

ns.t.x

x

x

a一.资源分配问题所谓分配问题，就是将供应量有限的一种或若干种资源（例如设备，，劳力等），分配给若干个使用者，而使目标函数为最优。设有某种设备，总套数为a，用于几个工厂。若分配数量xi用于第i个工厂生产，其收益为gi(xi)。问应如何分配，使几个工厂的总收益为最大？(1)此问题是可写成静态规划问题：max

g1

x1

g2

x2

gn

xn

（2）（ⅰ）此问题当gi(xi)是线性函数时，是一个线性规划问题。此问题当gi(xi)是非线性函数时，是一个非线性规划问题。当较大，具体求解是比较麻烦。这类问题可转化为一个多阶段决策问题来求解。3.例1.某公司购置了四套设备分配给下属三个工厂，设备分到厂后，每年可创造的产值如表所示，问如何分配使公司的总产值最大？产值表 单位：万元设备数 工厂—二三00001502050270457039075804105110100[注]穷举法：所有分配方案最多有5×5×5=125种方案，在125个分配方案中比较最优的办法显然不足取！4.

解题将问题分为三个阶段。今设有n个阶段(n=3)设sj为分配给第j个工厂至第n个工厂的设备总套数，且将s1,s2,…sn为n个状态。xj为分给第j个工厂的设备套数。则

sj+1

=

sj-

xj

(sj=

xj

+

sj+1)dj(sj,xj)=分给第j个工厂xj个设备所产生产值dj(sj)=sj套设备分配给第j个工厂至第n个工厂带来最大产值，则由最优化原理知，

f4

(s4

)

0d

(s

,

x

)

f

(s

)f

(s

)

maxj1

j1j

j

jj

j0x

j

s

j（3）第3阶段0

x3s3f3

(s3

)

max

d3

(s3

,

x3

)阶段s3x

3d3

(s3

,

x3

)f3

(s3

)00001150503

阶段22707033808044100100（4）第2阶段设把s2台设备(s2=0,1,2,3,4)分配工厂二、三时，则对每一个s2值，有一种最优分配方案，使最大产值为f2

(s2

)

max

d2

(s2

,

x2

)

f3

(s3

)0x2

s2其中s2=0,1,2,3,4（ⅰ）当

s2

0

时32

22f

(0)

max

d

(0,0)

f

(0)

0

0

0x

02∴x

0

1（ⅱ）

s2f

2

(1)

max

d

2

(1,x2

)

f3

(1

x2

)x2

0,1

max

d

2

(1,0)

f3

(1),

d

2

(1,1)

f3

(0)220

0

0

50

max

50,

x

0

2（ⅲ）

s

2

2

3

2

32

2d

2

(2,2)

f

3

(0)d

2

(2,0)

f

3

(2)

f

(2)

max

d

(2,

x

)

f

(2

x

)

maxd

2

(2,1)

f

(1)x2

0,1,

2

45

0

0

70

max

20

50

702x

0或1

3（ⅳ）

s23

32

3

22

2d3

(3,3)

f3

(0)d3

(3,2)

f

3

(1)

d

(3,1)

f

(2)

d

2

(3,0)

f

3

(3)f

(3)

max

d

(3,

x

)

f

(3

x

)

maxx2

0,1,

2,3

9575

0

45

50

20

70

0

80

2x

2

4（ⅴ）

s2

max

2

3322

322d

2

(4,4)

f3

(0)d

(4,3)

f

(1)

max

d

(4,2)

f

(2)d

(4,1)

f

(3)

d

2

(4,0)

f3

(4)d

(4,

x

)

f3

(4

x2

)

f

2

(4)

x2

0,1,2,3,4

110

0

75

50

20

80

0

100

max

45

70

125，x2

3将上面计算结果汇表：阶段s2x2x

2d

2

(s2

,

x2

)f

3(s3

)

f

3

(s2

x2

)f

2

(s2

)0000001000500+50120020+02000700+7011205020+50245045+0300801222045705095375040010012080234570125375