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

安徽科技学院 最优化技术 第一页，共三十六页，2022年，8月28日 B A C D E F G 本例中分为k=1,2,3,4,5,6 ，共六个阶段。 (1)阶段 将所给问题的过程，按时间或空间特征分解成若干相互联系的阶段，以便按次序去求每个阶段的解，常用字母k表示阶段变量. 第二页，共三十六页，2022年，8月28日 (2)状态 各阶段开始时的客观条件叫做状态。描述各阶段状态的变量称为状态变量，常用sk表示第k阶段的状态变量，状态变量sk的取值集合称为状态集合，用Sk表示。 无后效性：当某阶段状态给定以后，在这阶段以后过程的发展不受这段以前的各阶段的影响。即当前的阶段是过去历史的一个完整总结，过程的过去历史只能通过当前状态去影响它未来的发展。 第三页，共三十六页，2022年，8月28日 状态变量可以是一个数或一个向量。在本例中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} 第四页，共三十六页，2022年，8月28日 (3)决策和策略 当一个阶段的状态确定后，可以作出各种选择从而演变到下一阶段的某个状态，这种选择手段称为决策，在最优控制问题中也称为控制。 描述决策的变量称决策变量，变量允许取值的范围称允许决策集合。用uk(sk)表示第 k阶段处于状态sk时的决策变量，它是 sk的函数，用 Dk(sk)表示 sk的允许决策集合。 决策变量简称决策。 第五页，共三十六页，2022年，8月28日 由第k个状态sk开始到终止状态的后部子过程的策略记作 类似地，由第k到第j阶段的子过程的策略记作 可供选择的策略有一定的范围，称为允许策略集合， 用 表示 决策组成的序列称为策略。由初始状态s1开始的全过程的策略记作 第六页，共三十六页，2022年，8月28日 在本例中，从第二阶段的状态B1出发，可选择下一段的C1,C2,C3，即允许决策集合为。 D2(B1)={C1,C2,C3} 如果决定选择C3则可表示为： u2 (B1)=C3 表示 一个策略 第七页，共三十六页，2022年，8月28日 (4)状态转移方程 在确定性过程中，一旦某阶段的状态和决策为已知，下阶段的状态便完全确定。用状态转移方程表示这种演变规律，写作 本例中状态转移方程： (5)指标函数 用于衡量所选定策略优劣的数量指标称为指标函数. 第八页，共三十六页，2022年，8月28日 阶段指标函数：指第k阶段，从状态sk出发，采取决策uk时的效益，用d(sk,uk)表示。 过程指标函数：是定义在全过程和后部子过程上确定的数量函数。 一个n段决策过程,从1到n叫作问题的全过程； 对于任意一个给定的k ,从第k到n段的过程称为全过程的一个后部子过程. V1,n(s1,p1,n)表示在第1阶段，状态为s1，采用策略p1,n时，原过程的指标函数值； Vk,n(sk,pk,n)表示在第k阶段，状态为sk，采用策略pk,n时，后部子过程的指标函数值。 第九页，共三十六页，2022年，8月28日 fk(sk)与Vk,n(sk,pk,n) 间的关系为： 当k=1时f1(s1)就是从初始状态到全过程的整体最优函数. 其中opt可根据具体情况取max或min 指标函数的最优值称为最优指标函数，记为fk(sk)，表示从第k阶段状态sk采用最优策略p*k,n到过程中止时的最佳效益。 第十页，共三十六页，2022年，8月28日 本例中，指标函数是距离，如第二阶段， 阶段指标：状态为B1时d(B1,C2) 表示由B1出发采用决策到下一段C2点的两点距离； 过程指标： V2,6(B1)表示从B1到G 的距离，f2(B1)则表示从B1到G的最短距离。 第十一页，共三十六页，2022年，8月28日 三、基本思想与最优化原理 从例4的求解过程说明动态规划的基本思想： 例4 最短路问题 如图所示，给定一个线路网络图，要从A地向F地铺设一条输油管道，各点间 连线上的数字表示距离，问应选择什么路线，可使总距离最短？ A B1 B2 C1 C2 C3 D1 D2 D3 E1 E2 F 4 8 5 4 4 6 6 5 3 3 3 3 3 2 4 8 2 C4 7 7 8 5 4 5 1 第十二页，共三十六页，2022年，8月28日 A B1 B2 C1 C2 C3 D1 D2 D3 E1 E2 F 4 8 5 4 4 6 6 5 3 3 3 3 3 2 4 8 2 C4 7 7 8 5 4