动态规划问题的基本要素和最优化原理PPT课件

精品课程运筹学，第二节动态规划问题的基本要素和优化原理，2.1动态规划的基本概念，2.2动态规划的基本思想，创建2.3动态规划模型的步骤，1，阶段：适当分几个阶段，按一定顺序解答问题的过程。 描述阶段的变量称为阶段变量。 阶段划分一般是根据时间和空间的自然特征进行的，但问题很容易转化为多阶段决策。 2、状态：显示各阶段开始的自然状况和客观条件。 一个阶段通常有几种状态，描述进程状态的变量称为状态变量。 另外，一个整数，一组整数，一个向量，状态变量的可取值有一定的容许集合或范围，这个集合被称为状态容许集合。 2.1动态规划的基本概念，精品课程运筹学，3，决策：决策过程处于某一阶段时，作出不同的决策，决策下一阶段的状态。 的双曲馀弦值。 描述决策的变量称为决策变量。 决策变量是状态变量的函数。 可以用一个数字、一组数字或向量(对于多维)来描述。 在实际问题中，决策变量的值大多在某个范围内，这个范围被称为“允许决策的集合”。 在某一阶段系统的状态转移不仅与系统的当前状态和决策有关，还与系统的过去状态和决策有关。 4、多阶段决策过程可以在各阶段作出决策，控制过程发展的多阶段过程，其发展是通过一系列状态转变实现的，精品课程运筹学，图为：状态转变方程式是确定过程从一个状态向另一个状态转变的过程如果确定了第k级的状态变量sk的值和该级的确定变量，则还确定了第k 1级的状态变量sk 1的值。 其状态转移方程式如下：动态规划方法可解的多阶段决策过程是一种特殊的多阶段决策过程，即无回味的多阶段决策过程。 精品课程运筹学，状态变量无法满足没有后果的要求，必须适当变更状态的定义和规定方法。 动态规划中可处理的状态转移方程的形式。 不具有状态后发性的多阶段决策过程的状态转移方程如下：没有后发性(马尔可夫性)，给定一阶段状态后，该阶段以后的过程的发展不受该阶段以前各阶段状态的影响，过程的过去历史在当前状态下只能影响未来的发展， 构建动态规划模型时，必须十分注意是否满足无后验效应的要求，状态变量必须满足后验要求，精品课程运筹学、5、策略：排序决策的集合。 在实际问题中，可选择的战略有一定的范围，被称为容许战略集合。 从允许的策略集合中找出能达到最佳效果的策略称为最佳策略。 6、状态转移方程：在确定过程中从一个状态向另一个状态的转移过程中，描述了状态转移规则. 7、指标函数和最优值函数：是衡量已实现过程优劣的数量指标，是指标函数。 指标函数的最佳值称为最佳值函数。 在不同的问题中，指标函数的含义不同，它可以是距离、效益、成本、产量或资源消费。 动态规划模型的指标函数可分离，应满足递归关系。 精品课程运筹学，总结：指标函数形式：和，无积，可递归推移的精品课程运筹学，解多阶段决策过程问题，f1(s1)、k到目标的最优策略子策略的最优目标函数值、精品课程运筹学、1、动态规划方法要点是正确写入基本递归关系式和适当的边界条件(简称基本方程式)。为此，必须将问题过程分为几个阶段，适当选择状态变量和决策变量，定义最优值函数，将大问题转换为同一类型的子问题组，逐个解决。 也就是说，从边界条件逐步求出优势，在各个子问题的求解中，利用之前子问题的最优化结果，依次进行，最后子问题中得到的最优解是整个问题的最优解。 2.2动态规划的基本思想，精品课程运筹学，2，在多阶段决策过程中，动态规划方法是把当前段落和未来段落分开，把当前利益和未来利益结合起来考虑的最佳方法。 优化原理：作为整个过程的优化策略，与过去的状态和决策无关，对于前一决策形成的状态，剩馀的决策序列必定构成最佳子策略。 “也就是说，最优策略的子策略也是最优的。 3、在寻求整个问题的最优策略时，由于初始状态是已知的，各阶段的决定是该阶段的状态的函数，所以最优策略通过的各阶段的状态阶段性地变化，决定最优路径。精品课程运筹学、2.3构建动态规划模型的步骤1，阶段划分阶段是使用动态规划求解多阶段决策问题的第一步，在确定了多阶段特性后，按时间和空间的前后顺序将过程划分为若干相互关系的阶段。 对于静态问题，为了划分阶段必须人为地给出“时间”这一概念。 2、正确选择状态变量，必须正确描述过程的演变，满足后验的有效性。 而且，各阶段状态变量的值不能确定。 一般来说，状态变量的选择是从过程的进化特征中找出的。 3 .决策变量的确定和决策集的授权通常是通过选择已解决问题的关键变量作为决策变量并给出决策变量的可能范围来确定决策集的授权。 精品课程运筹学、4、确定状态转移方程式根据k阶段状态变量和决定变量，导出k 1阶段状态变量，状态转移方程式应具有递归关系。 5、确定阶段指标函数和最优指标函数，建立动态规划基本方程的阶段指标函数是第k阶段的收益，最优指标函数是从第k阶段状态到第n阶段结束获得的收益的最优值，最后编写动态规划