文档介绍：第九章动态规划(续)动态规划的基本原理动态规划方法的基本步骤动态规划方法应用举例本章以下内容豢堪齐卉磺闺史喘载坪怪共缨棠极轧罕胡膨丛烈覆哪吻笋折矣翠炒何出奖运筹学北京邮电大学动态规划运筹学北京邮电大学动态规划1最优化原理(贝尔曼最优化原理)作为一个全过程的最优策略具有这样的性质:对于最优策略过程中的任意状态而言,无论其过去的状态和决策如何,余下的诸决策必构成一个最优子策略。该原理的具体解释是,若某一全过程最优策略为:动态规划的基本原理则对上述策略中所隐含的任一状态而言,第k子过程上对应于该状态的最优策略必然包含在上述全过程最优策略p1*中,(n个阶段)。通常是根据时间或空间而划分的,或者在经由静态的数学规划模型转换为动态规划模型时,常取静态规划中变量的个数n,即k=n。,使它既能正确地描述过程的状态,,动态规划中的状态变量必须具备以下三个特征:(1)要能够正确地描述受控过程的变化特征。(2)要满足无后效性。即如果在某个阶段状态已经给定,那么在该阶段以后,过程的发展不受前面各段状态的影响,如果所选的变量不具备无后效性,就不能作为状态变量来构造动态规划的模型。(3)要满足可知性。即所规定的各段状态变量的值,可以直接或间接地测算得到。一般在动态规划模型中,状态变量大都选取那种可以进行累计的量。此外,在与静态规划模型的对应关系上,通常根据经验,线性与非线性规划中约束条件的个数,,常就是状态变量sk所代表的内容。(sk),根据经验,一般将问题中待求的量,选作动态规划模型中的决策变量。或者在把静态规划模型(如线性与非线性规划)转换为动态规划模型时,常取前者的变量xj为后者的决策变量uk。,至少要能正确反映状态转移规律。如果给定第k阶段状态变量sk的值,则该段的决策变量uk一经确定,第k+1段的状态变量sk+1的值也就完全确定,即有sk+1=Tk(sk,uk),正确地构造出目标与变量的函数关系——目标函数,目标函数应满足下列性质:(1)可分性,即对于所有k后部子过程,其目标函数仅取决于状态sk及其以后的决策uk,uk+1,┈,un,就是说它是定义在全过程和所有后部子过程上的数量函数。(2)要满足递推关系,即(3)函数对其变元Rk+1来说要严格单调。,它显然是满足上述三个性质的。所以上式可以写成::第一步先看问题,充分理解问题的条件、情况及求解目标。第二步结合前面讲到的理论和解题过程,考虑如何着手进行求解该问题的工作。分析针对该动态规划问题的“四大要素、一个方程”——这一步在开始时会感到困难,但是一定要下决心去思考,在思考过程中深入理解前文讲到的概念和理论。,或者说,把该问题作为习题独立的来做。第四步把自己的求解放到一边,看书中的求解方法,要充分理解教材中的论述。第五步对照自己的求解,分析成败。①状态变量及其可能集合xkXk②决策变量及其允许集合ukUk③状态转移方程xk+1=Tk(xk,uk