文档介绍：运筹帷幄之中
决胜千里之外
运筹学课件
动态规划
Dynamic Programming
动态规划
综述
最优化原理
确定性的定期多阶段决策问题
确定性的不定期多阶段决策问题
综述
动态规划所研究的对象是多阶段决策问题。
所谓多阶段决策问题是指一类活动过程,它可以分为若干个相互联系的阶段,在每个阶段都需要作出决策。这个决策不仅决定这一阶段的效益,而且决定下一阶段的初始状态。
每个阶段的决策确定以后,就得到一个决策序列,称为策略。多阶段决策问题就是求一个策略,使各阶段的效益的总和达到最优。
最优化原理
多阶段决策问题及实例
例1
例2
例3
多阶段决策问题
最优化原理
性质
用最优化原理求解例2
例1 多阶段资源分配问题
设有数量为x的某种资源,将它投入两种生产方式A和B中:以数量y投入生产方式A,剩下的量投入生产方式B,则可得到收入g(y)+h(x-y),其中g(y)和h(y)是已知函数,并且g(0)=h(0)=0;同时假设以y与x-y分别投入两种生产方式A,B后可以回收再生产,回收率分别为a与b。试求进行n个阶段后的最大总收入。
例1 续(1)
若以y与x-y分别投入生产方式A与B,在第一
阶段生产后回收的总资源为x1=ay+b(x-y),再将x1
投入生产方式A和B,则可得到收入g(y1)+h(x1-y1),
继续回收资源x2=ay1+b(x1-y1),……
若上面的过程进行n个阶段,我们希望选择n
个变量y,y1,y2,…,yn-1,使这n个阶段的总收入最大。
因此,我们的问题就变成:求y,y1,y2,…,yn-1,以使g(y)+h(x-y)+ g(y1)+h(x1-y1)+ …+g(yn-1)+h(xn-1-yn-1) 达到最大,且满足条件
x1=ay+b(x-y)
x2=ay1+b(x1-y1)
………
xn-1=ayn-2+b(xn-2-yn-2)
yi与xi均非负,i=1,2, …,n-1
例1 续(2)
例2 生产和存储控制问题
某工厂生产某种季节性商品,需要作下一
年度的生产计划,假定这种商品的生产周期需
要两个月,全年共有6个生产周期,需要作出
各个周期中的生产计划。
设已知各周期对该商品的需要量如下表所示:
周期
1
2
3
4
5
6
需求量
5
5
10
30
50
8
例2 续(1)
例2 续(2)
假设这个工厂根据需要可以日夜两班生产或只是日班生产,当开足日班时,每一个生产周期能生产商品15个单位,每生产一个单位商品的成本为100元。当开足夜班时,每一生产周期能生产的商品也是15个,但是由于增加了辅助性生产设备和生产辅助费用,每生产一单位商品的成本为120元。由于生产能力的限制,可以在需求淡季多生产一些商品储存起来以备需求旺季使用,但存储商品是需要存储费用的,假设每单位商品存储一周期需要16元,已知开始时存储为零,年终也不存储商品备下年使用,问应该如何作生产和存储计划,才能使总的生产和存储费用最小?