第2节最优化原理与动态规划的数学模型.ppt

同理，k=4时有： 此时最短路径： 相应决策： A B1 B2 C1 C2 C3 D1 D2 D3 E1 E2 F 5 4 4 6 6 5 3 3 3 3 2 4 2 C4 7 5 4 5 1 k=5时，只有一个状态点F，则： 此时最短路径： A B1 B2 C1 C2 C3 D1 D2 D3 E1 E2 F 4 4 6 5 3 3 3 2 4 2 C4 7 5 4 5 类似于逆序解法，写出顺序解法的递推方程： 这里 一般，当初始状态给定时可用逆序解法，当中止状态给定时可用顺序解法。若问题给定了一个初始状态与一个中止状态，则两种方法均可使用。二者并无本质区别。 逆序解法与顺序解法的区别： 1.状态转移方式不同： 1 状态s1 决策u1 效益v1(s1,u1) s2 k 状态sk 决策uk 效益vk(sk,uk) sk+1 n 状态sn 决策un 效益vn(sn,un) sn+1 ... ... 状态s1 1 决策u1 效益v1(s2,u1) s2 k 状态sk 决策uk 效益vk(sk+1,uk) sk+1 n 状态sn 决策un 效益vn(sn+1,un) sn+1 ... ... 逆序解法: 顺序解法: 2.指标函数的定义不同： 逆序解法中，最优指标函数fk(sk)表示第k阶段从状态sk出发，到终点后部子过程最优效益值，f1(s1)是整体最优函数值 顺序解法中，最优指标函数fk(sk+1)表示第k阶段从状态sk+1出发，到起点前部子过程最优效益值，fn(sn+1)是整体最优函数值 3.基本方程形式不同： （1）当指标函数为阶段指标和形式： 逆序解法: 基本方程: 顺序解法: 基本方程: （2）当指标函数为阶段指标积形式： 逆序解法: 基本方程: 顺序解法: 基本方程: 根据过程演变的特征 五、动态规划模型的分类 确定性 随机性 根据状态变量的取值 离散型 连续型 综上，动态规划分为四种类型： ①离散确定型 ②离散随机型 ③连续确定型 ④连续随机型 安徽科技学院 最优化技术 一个多阶段决策过程最优化问题的动态规划模型通常包含以下要素： (1)阶段； (2)状态； (3)决策和策略； (4)状态转移；(5)指标函数 第二节 最优化原理与动态规划的数学模型 以例4为例说明这些概念： 二、基本概念 一、基本思路 将n个阶段的决策问题转化为依次求解n个具有递推关系的单阶段的决策问题，从而简化计算过程。 B A C D E F G 本例中分为k=1,2,3,4,5,6 ，共六个阶段。 (1)阶段 将所给问题的过程，按时间或空间特征分解成若干相互联系的阶段，以便按次序去求每个阶段的解，常用字母k表示阶段变量. (2)状态 各阶段开始时的客观条件叫做状态。描述各阶段状态的变量称为状态变量，常用sk表示第k阶段的状态变量，状态变量sk的取值集合称为状态集合，用Sk表示。 无后效性：当某阶段状态给定以后，在这阶段以后过程的发展不受这段以前的各阶段的影响。即当前的阶段是过去历史的一个完整总结，过程的过去历史只能通过当前状态去影响它未来的发展。 状态变量可以是一个数或一个向量。在本例中s2可取B1,B2, 或将Bi定义为i (i=1,2)，则s2=1,2，则 S2={1,2} S1={A} S2={B1,B2} S3={C1,C2,C3,C4} S4={D1,D2,D3} S5={E1,E2,E3} S6={F1,F2} (3)决策和策略 当一个阶段的状态确定后，可以作出各种选择从而演变到下一阶段的某个状态，这种选择手段称为决策，在最优控制问题中也称为控制。 描述决策的变量称决策变量，变量允许取值的范围称允许决策集合。用uk(sk)表示第 k阶段处于状态sk时的决策变量，它是 sk的函数，用 Dk(sk)表示 sk的允许决策集合。 决策变量简称决策。 由第k个状态sk开始到终止状态的后部子过程的策略记作 类似地，由第k到第j阶段的子过程的策略记作 可供选择的策略有一定的范围，称为允许策略集合， 用 表示 决策组成的序列称为策略。由初始状态s1开始的全过程的策略记作 在本例中，从第二阶段的状态B1出发，可选择下一段的C1,C2,C3，即允许决策集合为。 D2(B1)={C1,C2,C3} 如果决定选择C3则可表示为： u2 (B1)=C3 表示 一个策略 (4)状态转移方程 在确定性过程中，一旦某阶段的状态和决策为已知，下阶段的状态便完全确定。用状态转移方程表示这种演变规律，写作 本例中状态转移方程： (5)指标函数 用于衡量所选定策略优劣的数量指标称为指标函数. 阶段指标函数：指第k阶