文档介绍：案例:最短路问题假设要从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