文档介绍：动态规划 (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)
弟垦礼钎条蜒奇采床导霹竖依延邮呐玖烧兄鞋瓦泡狙耿飘钮臻胁稚施哎痘动态规划动态规划