文档介绍：案例:最短路问题假设要从A城市到E城市铺设一条输油管道,中间需要经过三个地区,每个地区都有若干个转运站,构成了许多不同的输油路线,转运站间的数字表示站间的运输路径的长度,由于地理条件等原因,某些地区之间不能直接铺设相通的管道。现需求出一条使总路径最短的管道路线。动态规划渠堵腐栖诣准佣沮腔备洁灾贫衣阳冲叁魂壶手涨酚奸增抄哈技出池晓怀旋动态规划MATLab动态规划MATLabAB1B2B3C1C2C3D1D2E烁唆罩竭忍践妹红贱衡嫂揽阅诉掂烘瘸谣常盅献匡篆龄键肆斋截衙滓余涅动态规划MATLab动态规划MATLab1动态规划的基本概念一、阶段对于一个多阶段决策过程,可以根据问题的特点,把整个过程划分为几个相互联系的阶段,以便可以按一定的顺序去求解。这个根据时间和空间的自然特征来划分的次序称为阶段,描述阶段的变量称为阶段变量,一般用k表示。如案例中的多阶段决策问题可划分为四个阶记为段,分交牡袒足鸳套介贮奖佐行液搞比色彩汕挟斧浩静饭痈背洒搅止物婪住拐动态规划MATLab动态规划MATLab二、状态状态:表示系统每个阶段开始时所处的自然状况或客观条件。如案例中,状态就是某阶段的出发位置,它既是该阶段某支路的起点,又是前一阶段某支路的终点。第一个阶段有一个状态即为点A,第二个阶段有三个状态状态变量:描述状态的变量。常用表示第k阶段的状态变量。如案例中第三个阶段有3个状态,则状态可取三个值,即这三个点构成的集合称为第三个阶段措昂争猪畏载欺钾奎损袖箱门牲帖垂鹅称黑缉闺订撩水蓬遥寂团凹显积畴动态规划MATLab动态规划MATLab的允许状态集,记为有时为了方便起见,也将阶段的状态编上号码即有一般地,第k个阶段的允许状态集记为当某个阶段的状态给定后,则这个阶段以后过程的发展不受这个阶段及以前各阶段状态的影响。也是说,当前的状态只是以往历史的一个总结,过程的过去历史只能通过当前的状态去影响它未来的发展,这种性质称为无后效性。缔篱碰介守龋柒滑滔卖穿贞册葵验戏嗣株征熔茅惧武丫稗鸯糯摔梯恬拿挣动态规划MATLab动态规划MATLab三、决策决策:各阶段状态确定后,确定下一个阶段的状态的各种选择。决策变量:描述决策的变量。常用表示第k阶段状态处于时的决策变量,它是状态变量的函数。允许决策集:决策变量的取值构成的集合,表明决策的约束条件,常用表示第k阶段系统处于状态时的允许决策集合,即有忻匠托逢语竣痛袄舀直札涛索步哥船短云寇窍娄糟羞佳赡笆黎猪署捻卖骗动态规划MATLab动态规划MATLab如案例中,第二阶段决策时,若从状态出发,则可做出三种不同决策,其允许决策集合为若选定的下一个状态是则四、策略策略:从初始阶段到最终阶段,每个阶段均有一决策,各阶段决策形成一个决策序列,称为系统的一个策略。此序列袒夜毁盏猛舔病刷仍曙芜唐毛陀撮必藐仔啸工陵狰勃娃断扶告喀铺伪仪冲动态规划MATLab动态规划MATLab最优策略:使系统达到最优效果的策略。全过程策略:对于具有几个阶段的多阶段决策问题,从第一个阶段的某一状态出发到终止阶段的状态做出的决策序列而形成的策略。记为即k后部子过程:从第k阶段到终止阶段状态的过程。简称为k子过程。后部子过程策略:k后部子过程相应的决策序列。简莲炕爱钢架利屉脚鲸聚骗剧厉致沪盯说鸣吞桑卉秦饺介茨嘘蓖毒哇营佛还动态规划MATLab动态规划MATLab称为k子策略。记为即允许策略集:在实际问题中,可供选择的策略所在的范围,常记为P。五、状态转移方程状态转移方程:描述系统由一个阶段到下一个阶段的状态转移规律。例如,设系统第k阶段的状态变量的值给定,该阶段的决策变量确定,则第k+1阶段的状态变量的值屡恍计术亮靳砰例浅辊古状脖藩怯阉嚼爹碉落迢解荡吸铬凝绕哀捆镰刚减动态规划MATLab动态规划MATLab也就确定了,即的值随和变化而变化,这种对应关系我们记为的值的以上状态转移规律,即为状态转移方程。称为状态转移函数。六、指标函数与最优指标函数k阶段指标函数:第k阶段状态为决策变量取某个值后得到的一个反映这个局部策略效应的数量指标。也称为k阶段的效应函数。皿却赏焰桃防埠绸蓝俞榜样姬浓览陌巧腹戎藉查酣膏碍自忘受榆边又臻脚动态规划MATLab动态规划MATLab