动态规划问题.ppt

文档介绍：第一节动态规划问题
§ 多阶段决策问题
§ 动态规划问题举例
7/30/2018
§ 多阶段决策问题
所谓多阶段决策问题是指一类活动过程,它可以分为若干个相互联系的阶段,在每个阶段都需要作出决策。这个决策不仅决定这一阶段的效益,而且决定下一阶段的初始状态。
每个阶段的决策确定以后,就得到一个决策序列,称为策略。多阶段决策问题就是求一个策略,使各阶段的效益的总和达到最优.
1
2
n

状态
决策
状态
决策
状态
状态
决策
7/30/2018
动态规划是用来解决多阶段决策过程最优化的一种数量方法。其特点在于,它可以把一个n 维决策问题变换为几个一维最优化问题,从而一个一个地去解决。
需指出:动态规划是求解某类问题的一种方法,是考察问题的一种途径,而不是一种算法。必须对具体问题进行具体分析,运用动态规划的原理和方法,建立相应的模型,然后再用动态规划方法去求解。
§ 多阶段决策问题
7/30/2018
即在系统发展的不同时刻(或阶段)根据系统所处的状态,不断地做出决策;
动态决策问题的特点:
系统所处的状态和时刻是进行决策的重要因素;
找到不同时刻的最优决策以及整个过程的最优策略。
7/30/2018
每个阶段都要进行决策,目的是使整个过程的决策达到最优效果。
多阶段决策问题:
是动态决策问题的一种特殊形式;
在多阶段决策过程中,系统的动态过程可以按照时间进程分为状态相互联系而又相互区别的各个阶段;
1
2
n

状态
决策
状态
决策
状态
状态
决策
7/30/2018
多阶段决策问题的典型例子:
1 . 生产决策问题:企业在生产过程中,由于需求是随时间变化的,因此企业为了获得全年的最佳生产效益,就要在整个生产过程中逐月或逐季度地根据库存和需求决定生产计划。
§ 动态规划问题举例
7/30/2018
生产决策问题
某工厂生产某种季节性商品,需要作下一年度的生产计划,假定这种商品的生产周期需要两个月,全年共有6个生产周期,需要作出各个周期中的生产计划。设已知各周期对该商品的需要量如下表所示:
周期
1
2
3
4
5
6
需求量
5
5
10
30
50
8
7/30/2018
生产决策问题
假设这个工厂根据需要可以日夜两班生产或只是日班生产,当开足日班时,每一个生产周期能生产商品15个单位,每生产一个单位商品的成本为100元。当开足夜班时,每一生产周期能生产的商品也是15个,但是由于增加了辅助性生产设备和生产辅助费用,每生产一单位商品的成本为120元。由于生产能力的限制,可以在需求淡季多生产一些商品储存起来以备需求旺季使用,但存储商品是需要存储费用的,假设每单位商品存储一周期需要16元,已知开始时存储为零,年终也不存储商品备下年使用,问应该如何作生产和存储计划,才能使总的生产和存储费用最小?
7/30/2018
生产决策问题(续)
7/30/2018
生产决策问题(续)
5
7/30/2018