文档介绍：概述
基本概念
基本思想
基本要求
基本解法
主要应用
一维资源分配
二维资源分配
生产计划与存储
授课内容
背包问题
不确定性采购
可靠性
设备更新
货郎担问题
排序
2017/8/4
)
20世纪50年代,美国数学家贝尔曼,解决多阶段决策过程的最优化的一种方法;
多阶段决策过程:可以按时间顺序分解成若干个相互联系的阶段,每阶段有若干个方案供选择。
一种动态的决策过程,最终目标是达到整体最优。
概述
2017/8/4
主要的应用:
最优路径问题;资源分配问题;排序问题;投资问题;装载问题;生产计划与库存问题;生产过程的最优控制等。
动态规划种类划分:
离散确定型;离散随机型;连续确定型;连续随机型。
2017/8/4
例:设从甘肃要铺一条煤气管道到北京,途中须经过陕西、山西、河北,每省设一个中间站。各省建站可供选择的地点及各段距离如下图,现要求选择一条铺管线路,使总距离最短。
2017/8/4
2017/8/4
阶段k:指对整个过程的自然划分,根据时间顺序或空间特征来划分阶段,目的是为了按照时间等次序来解决优化问题。
状态指各个阶段开始时候所处的自然状况或者客观条件,描述过程状态的变量为状态变量,可以用一个数、一组数或一向量。状态的设定需要满足无后效性要求。
基本概念
2017/8/4
sk——第k阶段的状态变量;Sk={sk}为第k阶段的状态集合。
决策表示当过程处于某一阶段的某个状态时候,可做出不同的决定,从而确定下个阶段的状态。
2017/8/4
策略按照顺序排列的各个阶段决策组成的序列。
P:允许策略集合
最优策略:使整个问题达到最优效果的策略。
2017/8/4
状态转移方程确定一个过程状态到另一个状态的演变过程。
指标函数衡量所选定的策略优劣的数量指标。
2017/8/4
最优策略:
最优指标函数:
2017/8/4