动态规划.pdf

引例1: 最短路问题
从上海到伊犁间有一个铁路网,某学生暑假打算到伊犁旅
6. 动态规划游,出于经济关系只能坐火车,而且要求费用最少。下图标出了
各种可能的行车路线,请为这位同学的决策做出指导。
动态规划建模——引例 C 1 F
动态规划模型基本概念 8 6 5
A
5 4
动态规划模型基本要素上海 4 D G 伊犁
5 4
3
动态规划基本定理 7
5 B 5 6 6
动态规划的示意图 E H
3 5
动态规划的应用求费用最小的方案
4
穷举法所有路径的费用?
Æ多阶段决策问题!
例2 生产计划问题动态规划的基本概念
工厂生产某种产品, 每单位(千件)的成本为1(千元), 每次开动态规划(dynamic programming)是运筹学的一个分支,是求解决策过程
工的固定成本为3(千元), 工厂每季度的最大生产能力为6(千最优化的数学方法。
件). 经调查, 市场对该产品的需求量第一、二、三、四季度分究多阶段决策过程的优化问题时,提出了著名的最优化原理,把多阶段过程
别为 2, 3, 2, 4(千件). 如果工厂在第一、二季度将全年的需求转化为一系列单阶段问题,逐个求解,创立了解决这类过程优化问题的新方
都生产出来, 自然可以降低成本(少付固定成本费), 但是对于第法——动态规划。
三、四季度才能上市的产品需付存储费, 每季每千件的存储费多阶段决策过程,是指这样的一类特殊的活动过程,问题可以按时间顺序或
(千元). 还规定年初和年末这种产品均无库存. 试制订一空间位置分解成若干相互联系的阶段,在每一个阶段都要做出决策,全部过
个生产计划, 即安排每个季度的产量, 使一年的总费用(生产成程的决策是一个决策序列。要使整个活动的总体效果达到最优的问题,称
本和存储费)最少. 为多阶段决策问题。
动态规划问世以来,在经济管理、生产调度、工程技术和最优控制等方面得
该规划问题看似一个线性规划或线性整数混合规划问题, 但实到了广泛的应用。例如最短路线、库存管理、资源分配、设备更新、排
际上由于问题的动态特性, 是不容易建立常规的规划问题的序、装载等问题,用动态规划方法比用其它方法求解更为方便。
(非常复杂)! 但可以分阶段进行决策,即多阶段决策问题. 需要虽然动态规划主要用于求解以时间划分阶段的动态过程的优化问题,但
引入新的方法——动态规划方法. 是一些与时间无关的静态规划(如线性规划、非线性规划),只要人为地引
进时间因素,把它视为多阶段决策过程,也可以用动态规划方法方便地求
解。
动态规划模型的基本要素动态规划模型的基本要素(续)
(1) 阶段(Step)——为了表示决策和过程的发展顺序,通常根据决策进行的(3)决策(Decision)——当一个阶段的状态确定后,可以作出各种选择从而演
先后次序、时间顺序或空间特征,将全过程来划分为若干阶段。阶段变量变到下一阶段的某个状态,这种选择手段称为决策(decision),在最优控制问
一般用k=1,2,..,n表示。题中也称为控制(control)。
在例1中由“上海”出发为第一阶段(k=1),