运筹学-动态规划.ppt

第16章动态规划
动态规划是运筹学的一个分支,它是解决多阶段决策过程最优化的一种数学方法。该方法由美国数学家贝尔曼()等人在20世纪50年代初提出的
§1 多阶段决策问题
多阶段决策问题例子:
例16-1 最短路径问题:求图16-1中从A到F的最短路径。
将问题可分为五个阶段
每个阶段都要作出一个决策,决定向哪个点前进一步。各阶段的决策有机的联系着,本阶段的决策影响着下一阶段的决策,以至于影响整体效果,决策者在做决策时,不应尽考虑本阶段最优,还应考虑对最终目标的影响。各阶段的决策形成一个决策序列,通常称之为一个策略,不同的策略,其效果也不同。现在的问题就是要在允许的策略中,求出A到F的距离最短的策略。
第一阶段:从到A或B;
第二阶段:从B到C;
第三阶段:从C到D;
第四阶段:从D到E;
第五阶段:从E到F;
例16-2机器负荷分配问题:某种机器能在高低两种不同的负荷下工作,在高负荷下有台机器进行生产时,产品的产量,工作一年后完好的机器数为,在低负荷下有台机器进行生产时,产品的产量,工作一年后完好的机器数为。试制订一个五年计划,决定在每年年初如何分配完好的机器在两种不同负荷下生产的数量,才能使在五年内产品的产量为最高?
可将该问题按年划分为五个阶段:第一阶段即第一年;第二阶段即第二年;第三阶段即第三年;第四阶段即第四年;第五阶段即第五年。设开始时完好机器数量为x1
,第 k年能投入生产的机器数为xk,第 k年高负荷下工作的机器数为 uk 台,效益为 Rk ,则
原问题就是确定uk ,k=1,2,3,4,5,使最大。
例16-3部件的生产计划问题:某车间每月底要为下一个月提供出一定数量的部件给组装车间,各月份中生产这种部件所需工时不同,生产出来多余的部件可以存入库中,但库房的最高贮量为H=9,求某6个月中每月生产多少部件,才能使消耗的总工时最少?最小工时是多少?各月的需求量与单位工时如下表:
表7-1
月份
1
2
3
4
5
6
需求量
8
5
3
2
7
4
单位工时
11
18
13
17
20
10
将该问题按月份划分为六个阶段, Sk为第k月开始时的库存,
uk为第k 的生产量。
设为当第月开始时库为直至第6月止,生产部件累计工时的最小值,则
。即为要求的最小工时。
例16-4 原料分配问题:利用已有的12吨原料制造A、B 两种产品,已知每制造一吨 A产品需要原料4吨,每制造一吨 B 产品需要原料2吨,而两种产品在市场上的价格分别为每吨8千元和1万元,求如何安排生产计划能使总效益最大?
可将分配A、B两产品的产量看作两个阶段:第一阶段:确定生产A产品多少吨;第二阶段:确定生产B产品多少吨。求出使总效益最大的决策序列。
例16-5人员派谴问题:向三个售货区域派谴四名推销员,各区人数及效益如下表:
人数
区域
增加效益数
0
1
2
3
4
1
2
3
0
0
0
16
16
10
25
17
14
30
21
16
32
22
17
该问题可按区域分为三个阶段:第一阶段:确定向1区派几名推销员;第二阶段:确定向2区派几名推销员;第三阶段:确定向3区派几名推销员。求出使总效益最大的策略。
问如何派谴人员能使总效益最高?
例16-6货物装载问题:某海轮的总装载能力为 w 千吨(不妨设w=0,1,2, …,18千吨)需装载四种货物,规定海轮上每种货物不超过2件,各种货物的单位重量,单位运费如下表,问怎样装这些货物,才能使总运费最大?
表8-6
货物种类
单位重量
每件运费
1
2
3
4
5
1
3
4
9
1
4
7
将该问题按四种货物分为四个阶段,第k阶段确定第k种货
物的装运件数。设为第种货物的运费。求出使
最大的装运策略。
1. 阶段(Stage)
将问题恰当地划分成若干相互联系的阶段,通常用作为阶段变量。可按时间顺序或空间特征划分阶段。
2. 状态变量(State Variable)
描述过程状态的变量,可以用一个数,一组数或一个向量来描述,常用表示第阶段的状态变量。
不可控变量。
§2 动态规划的基本概念与基本原理
   动态规划的基本概念
最短路问题中,每个阶段状态表示该阶段初始点的集合。
状态集合用Sk表示,
S1={B1,B2}