文本运筹学课件

第一节

动态规划原理AC2C1D2D1D3E3768B16B25

31488C3

3C43—最短路问题及其解法1最短路问题及其特点635322图6.1.1如图6.1.1所示，称它为线路网络图。其中的圆圈称为点，两点间的连线称为弧，弧上的数字称为弧长。要解决的问题是：求一条从起点A到终点E的连通弧，使其总弧长最短。称这类问题为最短路问题。ADEBC下面分析最短路问题的特点：★从A到E整个过程可以分成4个阶段阶段

1

2

3

4★每个阶段都有起点，用xk

表示第k阶段的起点，并称为状态变量。例如，第2阶段有两个起点B1

B2

,第2阶段状态有两个。★从每个起点出发有若干个选择，用uk

表示从第k阶段的状态xk出发所作的选择，并称为决策变量。例如，从B1

出发，有3种选择，或到C1

,或到C2

,或到C3

。所有决策变量组成的集合记为Dk

.★用fk(xk)表示从第k阶段的状态xk出发，到达终点的最短弧长，那么，问题就变成了求

f1(x1)=f

1(A)。或者，用fk

(xk

)表示从起点A到第k阶段的状态xk

的最短弧长，那么，问题就变成了求f5(x5

)=f

5(A)

。★可以看出，如果最短路经过第k阶段的状态xk，那么，从第k阶段的状态xk

出发，到达终点E的这条路线，对于从xk

出发到达终点E的所有路线来说，也一定是最短路线。AC2C1D2D1D3E53768B16B23148C3

3C436835322图6.1.2例如，在上例中，最短路线是：A

B1

C2

D1

E最短路线经过B1

，那么，从B1

出发到达终点E的这条路线，B1C2

D1

E对于从B1出发到达终点E的所有路线来说，一定是最短路线。如果不是这样，也就是说，这条路线对于从B1出发到达终点E的所有路线来说，不是最短路线，那么，会得到结论。出发到达终点E的所有路线中，比如，从B1最短路线是，B1C3D3EAC2C1D2D1D3E53768B16B23148C3

3C436835322图6.1.3那么，从A

出发到达终点E的最短路线应B1C3D3E该是AD1E这与A

B1是最短路线C2。2

最短路问题的逆序解法1）从最后—个阶段k=4开始，按

f4

的定义f

4

(

D1

)

32）k=3时f

4

(

D2

)

2f

4

(

D3

)

2Dd(

,

)

()C( )

minfC

DC1D2ff4d(

,

)

(D2)141113

8

2

min6

3

9其中，d(,

)表示两点间的弧长。上结果说明，从C1

到终点E的最短弧长是9，路径为C1

D1

E决策为u3

(C

1

)

D1D)C( )

minfC

DC2D2ff4d(

,

)

(d(

,

)

(D2)1421235

2

min3

3

6到终点E的最短弧长是上结果说明，从C26，路径为E决策为C2

D1u3

(

C

2

)

D1d(

C

,

D

)

fD

f

C

DC( )

minfd(

,

)

(

)(

D3

)43

3243

2333

2

min3

2

5到终点E的最短弧长是

上结果说明，从C35，路径为C3C3EE或决策为或D2D3u3

(

C

3

)

D2u3

(

C

3

)

D3Dd()C( )

minfd(CC4,,DD3ff4)

()

(D3)244243

4

2

min8

2

6到终点E的最短弧长是上结果说明，从C46，路径为EC4

D3决策为

u3

(

C

4

)

D33）k=2时C(

)

fB

Cd(

,

)331

33d(

B1

,C

1

)

f(

C

1

)f

2

(

B1

)

mind(

B1

,C

2

)

f

3

(

C

2

)

1

9

min3

6

96

5上结果说明，从B1

到终点E的最短弧长是9，路径为C2决策为u2

(B1

)

C

2B1D1,u3

(

C

2

)

D1E,u4

(

D1

)

EC

fB

Cd(

,

)

(

)f432

4(

B

)

mind(

B

,C

)

f(

C

)3

32

3d(

B2

,C

2

)

f

3

(

C

2

)228

6

min7

5

126

6上结果说明，从B2

到终点E的最短弧长是12，路径为C3D2

EB2,u3

(

C

3

)

D2

,(

u3

(

C

3

)

D3

)决策为u2

(B2

)

C

3,u4

(

D2

)

ED3C4决策为u2

(B2

)

C

4Eu4

(

D3

)

ED3,u3

(

C

4

)

D3

,或B2

B(

)

fA

Bd(

,

)f222(

A

)

mind(

A

,B1

)

f

2

(

B1

)4

3

12

min

5

9

14上结果说明，从A

到终点E的最短弧长是14，路径为决策为4）k=1时A

B1

C2Eu1

(

A

)

B1u3

(

C

2

)

D1D1u2

(

B1

)

C

2u4

(

D1

)

E至此，最短路问题得到解决。总结一下，上述解法的四个步骤，可以归纳为下面递推公式f

k

(

xk

)

min

d(

xk

,

xk

1

)

f

k

1

(

xk

1

)ukDkf

5

(

x5

)

0

,k

4

,3,2

,1其中，

xk

1

uk

(

xk

)是从状态

xk

出发，采取决策,

Dkuk

到达下一状态

xk

1

表示从状态

xk

出发的所有可能选取的决策集合；而f

5

(x5

)

0,称为边界条件。3

最短路问题的顺序解法1）k=2时，按f2f

2

(B1

)

5的定义f

2

(

B2

)

3用

fk

(xk

)表示从起点A到第k阶段的状态xk的最短弧长，那么，可以从前向后逐步求出起点A到各阶段起点的最短弧长，最后求出起点A到终点E的最短弧长及最短路径。按定义

f

1

(

x1

)

f

1

(

A

)

0

,

称为边界条件。f

3

(

C

1

)

mind(

B1

,C

1

)

f

2

(

B1

)

1

5

6B

B

CC( )

minfB2C22B2d(

,

)

f

(

)d(

,

)

f

(

)121

2238

3

min3

5

82）k=3时，按

f3

的定义f3

(

C

4

)

mind(

B2

,C

4

)

f

2

(

B2

)

6

3

93）k=4时，BB

Cd(

,

)C( )

minfd(B2C3

f,

)

f2B2(

)(

)1213337

3

min6

5

10

f

C

D)D( )

minfd(

C

,

D

)

fd(

,

)

((CC2)312131

114

3

8

min6

6

11)d()D( )

minfd(CC4,,DD3)ff3((CC4)333334

4

9

min3

10

13C

DD( )

minf3(

C

)d(

,

)

f3

2

3d(

C

2

,

D2

)

f

3

(

C

2

)d(

C

1

,

D2

)

f

3

(

C

1

)24

8

9

d(

C

4

,

D2

)

f

3

(

C

4

)

8

6

5

8

min3

10

134）k=5时，按

f5

的定义D

fD

Ed(

,

)

(

)f (

E

)

mind(

D

,

E

)

f (

D3

4

32

)42d(

D1

,

E

)

f

4

(

D1

)5

3

11

min2

13

142

13结果与逆序解法的结果相同。与逆序解法一样，可以把上述求解过程统一写成递推公式形式。minuk

1Dk

1f

k

(

xk

)

d(

xk

1

,

xk

)

f

k

1

(

xk

1

)f

1

(

x1

)

0

,k

2,3,4

,5二、动态规划的一些基本概念1

多阶段决策问题如果一个问题可以看成是一个前后相互关联具有链状结构的过程，如图6.1.4，那么，这个过程称为多阶段决策过程，这个问题称为多阶段决策问题。12n状态状态状态状态状态决策决策决策…图6.1.4多阶段决策问题中，各个阶段采用的决策，一般来说与时间有关。当每个阶段的决策都确定之后，整个问题也就确定了。2

阶段变量对于多阶段决策问题，可以分成若干个相互联系的阶段，把描述阶段数的变量叫阶段变量。阶段的划分一般是按照时间和空间的自然特征来划分。3

状态变量状态表示每个阶段开始所处的自然状况或条件，它描述了研究问题过程的状况，又称不可控因素。例如，在最短路问题中，状态就是某个阶段的出发位置。比如，第2阶段有两个出发位置，B1

，

B2

。描述状态的变量称为状态变量。它可以用一个数，一组数或一个向量来描述。通常用xk

表示第k阶段的某一状态。由于每一阶段一般都有若干个状态，所以，用x,

,xXmk1

2k

kk,x

来表示第k

阶段所有状态构成的集合。例如，在最短路问题中，各个阶段的状态集合分别为X

1

A

X

2

B1,B2X

3

C1

,C

2

,C

3

,C

4X

5

E

X

4

D1,

D2

,

D3

,状态变量一般要满足：1要能描述问题的变化过程。2给定某—阶段的状态，这个阶段以后过程的发展不受这个阶段以前各阶段状态的影响。也就是

程过去历史只能通过当前的状态去影响它的未来发展，当前状态是以往历史的一个总结。这种性质成为后无效性。3能直接或间接地计算出来。4

决策变量决策是当过程处于某个状态时，做出的决定或选择。描述决策的变量叫决策变量。通常用uk

(xk

)表示从第k阶段的状态xk出发的可行处所采用的决策。在第k阶段从xkx1决策集合通常用Dk

(xk

)，显然，uk

(xk

)

Dk

(xk

)5

策略当每一阶段的决策都确定以后，由初始状态出发到达终点

xn

,

每一阶段的决策uk

(

xk

)所构成的决策序列称为一个整体策k

1,2,n略，简称策略，记为p1,n(x1

)即p1,n(

x1

)

u1(

x1

),u2

(

x2

),,un

(

xn

)而pk

,n

(

xk

)

uk

(

xk

),uk

1

(

xk

1

),,un

(

xn

)称为一个后部k段子策略，p1,k

(

x1

)

u1(

x1

),u2

(

x2

),,uk

1

(

xk

)称为一个前部k段子策略。用P1,n

(x1

)表示整体策略构成的集合；用P1,k

(x1

)表示前部k段子策略构成的集合；用Pk,n

(xk

)表示后部k段子策略构成的集合；如果一个策略使得多阶段决策问题达到最优，那么此策略称为最优策略。6

状态转移方程由一个状态变到另一个状态的变化叫状态转移，它既与状态有关，又与决策有关。如果第k阶段状态xk

和决策uk

都确定之后，第k+1阶段的状态就随之确定，那么，就把这种对应关系记为xk

1

Tk

(

xk

,uk

)并称为由状态xk

到xk+1

的顺序状态转移方程。如果第k阶段状态xk

和第k-1阶段的决策uk-1都确定之后，第k-1阶段的状态就随之确定，那么，就把这种对应关系记为xk

1

Tk

1

(

xk

,uk

1

)并称为由状态xk

到xk-1

的逆序状态转移方程。7

指标函数衡量问题效果的数量指标叫做指标函数。由于策略分前部和后部子策略，所以，指标函数也分前部和后部两种情况来

。用Fk,n

(xk

,pk,n

)表示从第k阶段的状态xk

出发，的后部指标函数。采用策略

pk

,n

到达终点

xn1显然Fk,n

(

xk

,

pk

,n

)

Fk

,n

(

xk

,uk

;

xk

1

,uk

1

;;

xk

1

)如果上述过程采用的是最优策略pk,n那么，相应的后部指标函数记为f

k,n

(xk

,pk,n

)，并称为后部最优指标函数，简称最优函数，简记为f

k

(xk

)同理，可以

前部指标函数，前部最优指标函数。用F

1,k

(x1

,p1,k

)表示从第1阶段的状态x1

出发，到达第k+1阶段状态p1

,k采用策略

xk

的前部指标函数。如果上述过程采用的是最优策略p1,k那么，相应的前部指标函数记为并称为前部最优指标函数，简称最优函数，简f

1,k

(

x1

,

p1,k

)f

k

(

xk

)记为指标函数通常取下列形式：n（1）指标函数是阶段指标和的形式Fk

,n

d(

x

j

,u

j

)j

kk或

F

1

,k

d(

x

j

1

,u

j

)j

2它满足递推关系Fk,n

d(

xk

,uk

)

Fk

1

,n或F

1

,k

d(

uk

1

,

xk

)

F

1

,k

1（2）指标函数是阶段指标积的形式nFk

,n

d(

x

j

,u

j

)j

kkF

1,k

d(

x

j

1

,u

j

)或j

2它满足递推关系Fk

,n

d(

xk

,uk

)Fk

1

,n或F

1

,k

d(

uk

1

,

xk

)F

1

,k

1三最优化原理与动态规划方程最优化原理对于多阶段决策问题，作为整个过程的最优策略必然具有这样的性质：无论过去的状态和策略如何，就前面决策所形成的状态而言，余下的诸决策必然构成一个最优子策略。逆序动态规划方程考虑后部指标函数Fk,n

(xk

,pk,n

)及最优函数f

k

(

xk

)n当

Fk

,n

d(

x

j

,u

j

)

时j

kFk

,n

(

xk

,

pk

,n

)pk

,nPk

,nf

k

(

xk

)

opt)k

1,nd(

xk

,uk

)

Fk

1,n(

xk

1

,

p

opt(

uk

,

pk

1

,n

)Pk

,n

opt

d(

xk

,uk

)

f

k

1

(

xk

1

)uk

Dk于是得f

k

(

xk

)

opt

d(

xk

,uk

)

f

k

1

(

xk

1

)uk

Dkf

n1

(

xn1

)

0

,k

n,n

1,,2,1当n

j

kd(

,

)F

k

,nx

j

u

j

时同理可得f

k

(

xk

)

opt

d(

xk

,uk

)

f

k

1

(

xk

1

)uk

Dkf

n1

(xn1

)

0

,k

n,n

1,,2,13

顺序动态规划方程考虑前部指标函数F

1,k

(x1

,p1,k

)及最优函数f

k

(

xk

)k当

F

1,k

d(

x

j

1

,

x

j

)时j

2F

1

,k

(

x1

,

p1

,k

)optp1

,kP1

,kf

k

(

xk

)

)1,k

1d(

uk

1

,

xk

)

F

1,k

1

(

x1

,

p

opt(

uk

1

,

p1

,k

1

)P1

,k于是得d(

uk

1

,

xk

)

f

k

1

(

xk

1

)

optuk

1

Dk

1opt

d(

uk

1

,

xk

)

f

k

1

(

xk

1

)f

k

(xk

)

uk

1

Dk

1f

1

(

x1

)

0

,k

2

,3,,n

1当kj

2j

1

juF

1,kd(

,x

)时同理可得opt

d(

uk

1

,

xk

)

f

k

1

(

xk

1

)f

k

(

xk

)

uk

1

Dk

1f

1

(

x1

)

1,k

2

,3,,n

1动态规划第三节动态规划应用举例—分配问题分配问题是指这样一类问题：设有m种资源（如

，原材料，机器设备，劳动力等等），可以投入n种生产。问：将每种资源投入给各种生产各多少数量，才能使总效益最大？下面

m=1的资源分配问题设有数量为x0的某种资源，可投入n种生产。设以数量为xi

的资源投入第i种生产，所得的效益gi

(xi

)

，问如何分配这种资源，能使总效益最大静态模型数量为xi

的资源投入第i种生产所得的效益gi

(xi

)

,所以，总效益为g1

(

x1

)

g2

(

x2

)

gn

(

xn

)静态模型为另外，xi

的应满足约束x1

x2

xn

x0ni

1iximax(

)

xi

0

,i

1,2

,,ns.t

x1

2

ng

x

x

x0这个模型是一个静态模型，是线性或非线性规划。由于这个问题的特殊结构，它可以转化成一个多阶段决策问题。下面是资源分配问题的动态规划模型。用逆序解法。①

阶段变量选取n种生产过程作为阶段变量:

k=1，2，…，n；②状态变量把投入第k种生产至第n种生产的资源总量取为状态变量,

用sk表示③决策变量把投入第k种生产的物资数量xk

作为决策变量即，决策变量uk

xk阶段1生产第1种产品u1

x1阶段2生产第2种产品u2

x2阶段k生产第k种产品uk

xk阶段k+1生产第k+1种产品uk1

xk1阶段n生产第n种产品un

xn第k+1种生产第k阶段状态变量第k+1阶段状态变量sk

第k种生产至第n种生产的资源总量sk

1

至第n种生产的资源总量④

状态转移方程——第k种生产至第n种生产的资源总量-——第k+1种生产至第n种生产的资源总量状态转移方程是sk

1

sk

uk

sk

xk决策集合是D(

uk

)

uk

0

uk

xk

sk⑤

策略：u1

x1

,u2

x2

,,un

xn子策略：uk

xk

,uk

1

xk

1

,,un

xnsksk

1⑥阶段指标阶段指标函数：d(sk

,uk

)

gk

(xk

)n指标函数：

Fk

,n

g

j

(

x

j

)j

k第k阶段到终点的后部指标函数第k阶段的效益第k阶段到终点的效益令f

ksk

表示以数量sk的资源投入第k种生产至第n种生产时的最大效益；⑦

动态规划方程kk由最优化原理，得动态规划方程要完成的任务是：求u1

,u2

,,un使总效益达到最大，即F

1,n

达到最大f

1

(

s1

)f (

s

)

g

(

xk

)

f (

sk

xk

)k

k

1k

n,n

1,,2,1max0u

x

sk

k

kf

n1

(

sn1

)

0工厂设备数甲乙丙0000111141211125131112例题3.1

五台设备分配给甲，乙，丙三个工厂，每个厂得到设备后，年

情况如表3.1所示，问：分配给各厂设备各多少台，才能使各厂总

最大。表3.1解：阶段变量：按工厂分三个阶段，甲、乙、丙工厂分别 为1、2、3；状态变量：sk表示分配给第k个工厂至第n个工厂的设备数；决策变量：uk=xk表示分配给第k个工厂的设备数；状态转移方程：sk

1

sk

uk

sk

xkgkxk表示xk台设备分配到第k个工厂所获的利润值；f

ksk

表示sk台设备分配给第k个工厂至第n个工厂时所获的最大利润值；动态规划方程：xgs

maxfkkkkk

kk

3,2,1

f

sk

xk

,k

10

x

sf

4

s4

0下面从最后一个阶段开始计算。第三阶段：k=3xgs

maxf33333

3310

x

s由于f

4

s4

0

，所以333

3f

s3

x3

0xgmax0

x

s

xgmax333

30

x

s此时，s3表示分配给第3个工厂至第n个工厂的设备数，取值为：0，1，2，3，4，5现在，对每个s3的取值，来计算f

3

s3

此时当s3=0时，

由于

0

x3

s3

，所以

x3

0xgmaxf33330

x

00

3

max

g

0

0甲乙丙0000111141211125131112表3.1g3(0

)

03g

0

表示0台设备分配到第3个工厂所获的利润值gk

xk表示xk台设备分配到第k个工厂所获的利润值；解释：g3

(0

)

xgf333，所以x3

0当s3=1时，由于0

x3

s3或x3

1

，此时

maxg

0,

g

13

3

max0,4

4解释：

g3

(

0

),

g3

(

1

)

xgmax0

x31max333x

0

,11

甲乙丙000041211125131112表3.13g

1

4g3

1

表示1台设备分配到第3个工厂所获的利润值gk

xk表示xk台设备分配到第k个工厂所获的利润值；xgmaxf33330

x

22

3

3

3

maxg

0,

g

1,g

2，所以x3

0当s3=2时，由于0

x3

s3或

x3

1

或

x3

2

，此时

max0,4,6

6解释：g3

0,g3

1,g3

2甲乙丙000041211125131112表3.13g

2

6g3

2

表示2台设备分配到第3个工厂所获的利润值gk

xk表示xk台设备分配到第k个工厂所获的利润值；，此时当s3=3时，由于

0

x3

s3

，所以

x3

0xgmaxf33330

x

33

3

3

3

3

maxg

0,

g

1,g

2,

g

3

max0,4,6,11

11解释：g3

0,g3

1,g32,

g3

3或

x3

1

或

x3

2

或

x3

3甲乙丙0000111141211125131112表3.13g

3

11gk

xk表示xk台设备分配到第k个工厂所获的利润值；g3

3

表示3台设备分配到第3个工厂所获的利润值，所以当s3=4时，由于

0

x3

s3x3

0,1,2,3,4

，此时xgmaxf33330

x

44

maxg

0,

g

1,g

2,

g

3,

g

43

3

3

3

3

max0,4,6,11,12

12，所以当s3=5时，由于

0

x3

s3x3

0,1,2,3,4,5

，此时xgmaxf33330

x

55

3

3

3

3

3

3

maxg

0,

g

1,g

2,

g

3,

g

4,

g

5

max0,4,6,11,12,12

12将上述计算出的f

3

0,

f

3

1,

f

3

2,

f

3

3,

f

3

4,

f

3

5填入表3.2中表3.2x3g3

x3

f

3

s3x30123450000s310441204662304611113404611121245046111212125接下来计算第二阶段。第二阶段：k=2在此阶段中，动态规划方程为f

2

s2

max

g2x2

f

21

s2

x2

0

x2

s2

s

xxmax2222

32

2g

f

0

x

s此时，s2表示分配给第2个工厂至第n个工厂的设备数，取值为：0，1，2，3，4，5现在，对每个s2的取值，来计算f

2

s2当s2=0时，由于0

x2

s2，所以x2

0此时f

2

0

max

g2

x2

f

21

0

x2

0

x20

max

g

0

f

0

02

3

0甲乙丙0000111141211125131112g2(0

)

0表3.12g

0

表示0台设备分配到第2个工厂所获的利润值gk

xk表示xk台设备分配到第k个工厂所获的利润值；解释：

0f

2

0

max

g2

x2

f

21

0

x2

0

x202

3

max

g

0

f

0

0f

3

s30123450000111141212125121212表3.2f

3

0

02

3

2

3

max

g

0

f

1

0,

g

1

f

1

1当s2=1时，由于0

x2

s2，所以x2

0或

x2

1

，此时f

2

1

max

g2

x2

f

21

1

x2

0

x212

3

2

3

max

g

0

f

1,g

1

f

0

max

0

4,5

0

5解释：

max

g

0

f

1,g

1

f

02

3

2

3甲乙丙000041211125131112表3.12g

1

5g2

1

表示1台设备分配到第2个工厂所获的利润值gk

xk表示xk台设备分配到第k个工厂所获的利润值；f

3

s30123450000111141212125121212表3.2f

3

1

4为了简洁记录当s2=1时的计算过程，把f

2

1

max

g2

x2

f

21

1

x2

0

x21中的2

3

2

3

max

g

0

f

1,g

1

f

0

max

0

4,5

0g2

0

f

3

1,g2

1

f

3

00

4,5

0填入表3.3中表3.3x2g2

x2

f3

s2x2

f2s2x20123450000s2120＋45＋051345当s2=2时，由于0

x2

s2，所以x2

02

3

2

3

2

3

max

g

0

f

2,

g

1

f

1,g

2

f

0

max

0

6,5

4,10

0

10解释：或

x2

1

或

x2

2

，此时f

2

2

max

g2

x2

f

21

2

x2

0

x22

max

g20

f

320,g21

f

321

,g22

f

322

g2

0

f

3

2,

g2

1

f

3

1,g2

2

f

3

0甲乙丙000041211125131112表3.1g2

2

10g2

2

表示2台设备分配到第2个工厂所获的利润值gk

xk表示xk台设备分配到第k个工厂所获的利润值；f

3

s30123450000111141212125121212表3.2f

3

2

6为了简洁记录当s2=2时的计算过程，把2

3

2

3

2

3

max

g

0

f

2,

g

1

f

1,g

2

f

0

max

g20

f

320,g21

f

321

,g22

f

322

2f

2

max

0

6,5

4,10

0中的0

6,5

4,10

0填入表3.3中表3.3x2g2

x2

f

3

s2

x2

f2s2x20123450000s2120＋40＋65＋05+410＋051012345

max

g2

0

f

3

3,

g2

1

f

3

2,

g2

2

f

3

1

max

0

11,5

6,10

4,11

0

142

3

2

3,g

2

f

32,g

3

f

33

当s2=3时，由于0

x2

s2，所以x2

0或

x2

1

或

x2

2

或

x2

3

，此时f

2

3

max

g2

x2

f

21

3

x2

0

x23

max

g20

f

330,g21

f

3312

3,g

3

f

0

当s2=4时，由于0

x2

s2，所以x2

00

x2420

,g

1f

3

4

14

max

g20

f

3

max

0

12,5

11,10

6,11

4,11

0

16,g

3

f

43,g

4

f

44

2

3

2

3

max

g2

0

f

3

4,

g2

1

f

3

3,

g2

2

f

3

22

3

2

3,g

3

f

1,g

4

f

0

或

x2

1

或

x2

2

或

x2

3

或

x2

4

，此时f

2

4

max

g2

x2

f

21

4

x2

2

3

,g

2

f

42当s2=5时，由于0

x2

s2，所以x2

0f

2

5

max

g2

x2

f

21

5

x2

0

x2520

,g

1

f

3

5

15

max

g20

f

3此时,1,2,3,4,5

,

max

0

12,5

12,10

11,11

6,11

4,11

0

212

3

2

3

2

3,g

3

f

2,g

4

f

1,g

5

f

0

2

3

,g

2

f

52,g

3

f

53

,g

4

f

54,g

5

f

55

2

3

2

3

2

3

max

g2

0

f

3

5,

g2

1

f

3

4,

g2

2

f

3

3相关的数据填入表3.3中表3.3x2g2

x2

f

3

s2

x2

f

2s2

x2012345000010＋45＋051s22340＋60＋110＋125＋45＋65＋1110＋010＋410＋611＋011＋411＋0101416221,250+125+1210+1111+611+411+0212最后计算第一阶段。第一阶段：k=1在此阶段中，动态规划方程为f

1

s1

max

g1x1

f

11

s1

x10

x1

s1

max

g1x1

f

2

s1

x10

x1

s1由于是最后阶段，所以应该把所有资源全部用上，因此，只有s1=5这一种情况。，所以x1

0,1,2,3,4,5由于0

x1

s1下面计算f

1

5f

1

5

max

g1x1

f

11

5

x10

x15

max

g10

f

250,g11

f

251

,g12

f

252,g

3

f

53

,g

4

f

54,g

5

f

55

1

2

1

2

1

2

max

g1

0

f

2

5,g1

1

f

2

4,g1

2

f

2

3,g

3

f

2,g

4

f

1,g

5

f

0

1

2

1

2

1

2

max

0

21,3

16,7

14,9

10,12

5,13

0

21相关的数据填入表3.4中表3.4x1g1

x1

f

2

s1

x1f

1s1

x1012345s150+213+167+149+1012+513+0210,2最后，按照表格的顺序反推，可算出最优分配方案：得最优分配方案：甲工厂分配0台，乙工厂分配2台，丙工厂分配3台。1

x

5

0

5（1）由

x

0，再根据

s

s1

2

1，查表3.3，得x

222由

2x，再根据223

5

2

3s

s

x，查表3.2，得

3x

3得最优分配方案：甲工厂分配2台，乙工厂分配2台，丙工厂分配1台。（2）由

x

2，再根据

s

s

x

5

2

31

2

1

1，查表3.3，得x

22由2

2x223

3

2

1s

x，再根据s，查表3.2，得

3x

1说明：在求解资源分配问题时注意如下几个方面。（1）问题的识别配台例题3.1

五台设备分配给甲，乙，丙三个工厂，每个厂得到设备后，年

情况如表3.1所示，问：分

给各厂设备各多少

，才能使各厂总

最大。资源生产一种资源投入到3种生产此题是资源分配问题。（2）掌握资源分配问题的动态规划模型kkf (

s

)

g

(

xk

)

f (

sk

xk

)k

k

1k

n,n

1,,2,1max0u

x

sk

k

kf

n1

(

sn1

)

0gkxk表示xk台设备分配到第k个工厂所获的利润值；（3）找到gk

xk

0000111141211125131112丙乙甲工厂设备数表3.13g

1

43g

0

03g

2

63g

3

113g

4

123g

5

12资源生产111141211125丙乙甲工厂设备数表.12g

1

52g

0

02g

2

102g

3

112g

4

112g

5

11（4）用列表的方式计算f

k

(sk

)上例题中计算f

3

s3

时，用表3.2来完成；计算f

2s2

时，用表3.3来完成；计算f

1s1

时，用表3.4来完成。表3.2x3g3

x3

f

3

s3x30123450000s310441204662304611113404611121245046111212125表3.3x2g2

x2

f

3

s2

x2

f

2s2

x2012345000010＋45＋051s22340＋60＋110＋125＋45＋65＋1110＋010＋410＋611＋011＋411＋0101416221,250+125+1210+1111+611+411+0212表3.4x1g1

x1

f

2

s1

x1f

1s1

x1012345s150+213+167+149+1012+513+0210,2（5）最后，用逆向反推的方法求出最优解。例题3.2

某邮电局有四套通讯设备准备分配给甲、乙、丙三个地区。事先

了各地原有生产活动情况，在此基础上对各种分配方案的经济效益进行了估计，得表3.5的数据，例如甲地区原有生产活动的收益为38万元，当新增加一套设备时总收益为41万元，其他类推。试求这四套设备的分配方案，使三地区总利益最大。设备数01234地区甲3641486066乙4042586066丙4864687876表3.5解：阶段变量：问题分三个阶段，甲、乙、丙三个地区分别

为1、2、3；状态变量：sk表示分配给第k个地区至第n个地区的设备数；决策变量：uk=xk表示分配给第k个地区的设备数；状态转移方程：sk

1

sk

uk

sk

x