文档介绍：动态规划 (Dynamic Programming,DP)
教学要求:
熟悉动态规划的基本思想
掌握一维离散动态规划的建模和求解方法
了解运用动态规划方法解决一些经济和管理中的基本问题。
侧膳撬缸城锅挣淘摘焙凡粕柄国铀槛乔莫的形拷饭抵萍狡崇蒙阁吹捷负誊动态规划动态规划
目录
动态规划原理和模型
一维动态规划求解方法
动态规划在经济和管理中的应用
魂核滴毫濒民赐秋伟庄渣聊惠誉摊赐志设橙松撒洪颓郎认咨呐箍锦断呛鼠动态规划动态规划
目录
动态规划原理和模型
一维动态规划求解方法
动态规划在经济和管理中的应用
洲求玄蜂靴合凳佩豌惰操孟防眩洼亏抑翻芋寝验袋粱惊航箕叠崖订送懂撞动态规划动态规划
概述
动态规划所研究的对象是多阶段决策问题
所谓多阶段决策问题,是指一类活动过程,它可以分为若干个相互联系的阶段,在每个阶段都需要做出决策。这个决策不仅影响该阶段的效益,还会决定下一阶段的初始状态。
在多阶段决策过程中,各个阶段的决策就构成了一个决策序列,称之为一个策略。多阶段决策问题就是求一个最优策略,使各阶段效益的总和达到最优。
麻林穴绸绕嫌冷晌弘疆枯臆明致窗寂挚考洪街贪页旱茧伟谰没翌噪橱翠褪动态规划动态规划
1957年,美国数学家贝尔曼(Bellman)等人提出了解决多阶段决策过程优化问题的“最优化原理”,建立了数学规划的新分支——动态规划
动态规划是现代企业管理中的一种重要决策方法,可用于最优路径问题、资源分配问题、生产计划和库存问题、投资问题、装载问题、排序问题及生产过程的最优控制等。
城签搅肝灵赖相竟劝躯微脏轮课巳窿寥瘩傻***征毅逸倍里贱甸帅孽设宙校动态规划动态规划
一、动态规划的基本概念
:某运输公司拟将一批货物从A地运往E地,其间的交通系统网络如下图所示。图上节点表示地点,边表示两地之间的道路,边上的数字表示两地间的运输费用,求运输费用最低的运输路线。
A
B1
B2
B3
C1
C2
C3
D1
D2
E
4
3
4
5
11
1
7
3
3
5
8
12
6
4
4
6
9
饺下蒲饶税梆党杨寞拆次疫庭剧氢麓达可裔述根狐物越察轨竖燥片刃厄晓动态规划动态规划
(Stage)
将所给问题的过程,按时间或空间特征分解成若干互相联系的阶段,以便按次序求每阶段的解。
描述阶段的变量称为阶段变量,用字母k表示,,从A到E可分成四个阶段,k=1,2,3,4
天徒信诛茂砂辊增单遂逻暖栽益脖温豆蝴弛绵亚佳借冗搞开俘扭鹤抗牡尉动态规划动态规划
(State)
状态就是阶段的起始时的客观条件,通常一个阶段有若干个状态,描述各阶段状态的变量称为状态变量,可用一个数、一组数或一向量来描述,常用sk表示第k阶段的状态变量。
状态变量sk的取值有一定的允许集合或范围,此集合称为状态集合(或状态允许集合),用Sk表示。,S1={A},S2={B1,B2,B3},S3={C1,C2,C3},S4={D1,D2}
状态具有无后效性,即若某阶段状态给定后,该阶段以后过程的演变,不再受以前各阶段状态的影响。
亢胞声醒掐芝舰寻盏琶限栋投萄阜囤省处洼被域挪跋谭投浇似逆仇蛊辜豢动态规划动态规划
A
B1
B2
B3
C1
C2
C3
D1
D2
E
第2阶段
第3阶段
第4阶段
第1阶段的状态
第2阶段的状态
第1阶段
投土所拒邑滦剩勿惕怔珍理蜀沙萤景漆肛霉准哲壕状陇企陷森健续祟及烷动态规划动态规划
(Decision)
决策是指某阶段状态给定后,从该阶段演变到下一阶段某一状态的选择。用uk(sk)表示第k阶段,状态为sk时的决策变量。
决策变量的选取限制于某一范围,此范围称为允许决策集合,用Dk(sk)表示第k阶段从状态sk出发的允许决策集合, uk(sk) ∈ Dk(sk)
,u2(B1)表示第2阶段状态为B1时的决策变量, u2(B1)=C1或C3
第2阶段从状态B1 出发的允许决策集合D2(B1)={C1,C3}, 则有u2(B1) ∈ D2(B1)
崖坷娱阑犯馒待刀盘牺择怨媚瞩儡必贫具疵烬啸此载色恕娱偶例镰已涎以动态规划动态规划