运筹学本科-动态规划.ppt

动态规划 Dynamic Programming（DP） 第七章 动态规划 动态规划 Dynamic Programming（DP） 引言 动态规划作为运筹学的一个重要分支是解决多阶段决策过程最优化的一种非常有效的方法。 动态规划 Dynamic Programming（DP） 引言 动态规划的方法，在工程技术、企业管理、工农业生产及军事等部门中有着广泛的应用，并且获得了显著的效果。 动态规划 Dynamic Programming（DP） 引言 由于动态规划的方法在众多方面的应用，使他已经成为现代企业管理中的一种重要的决策方法。 此外，许多实际问题采用动态规划方法去处理，常比线性规划或非线性规划更加有效。 特别对于离散型的问题，由于解析数学无法施展其术，而动态规划方法就成为一种非常有效的工具。 动态规划 Dynamic Programming（DP） 多阶段决策过程的最优化 多阶段决策过程： 整个决策过程可按时间或空间顺序分解成若干相互联系 的阶段，每一阶段都需作出决策，全部过程的决策是一个决策序列。 动态规划 Dynamic Programming（DP） 动态规划典例 例——最短路线问题 动态规划 Dynamic Programming（DP） 动态规划典例----最短路问题 寻找A点到G点的最短线路 动态规划 Dynamic Programming（DP） 动态规划典例----最短路问题 A点到G点的最短线路如下，最短距离18。 动态规划 Dynamic Programming（DP） 动态规划的基本概念 1、阶段（stage） 对整个决策过程的自然划分，通常根据时间顺序或空间特征来划分阶段，以便按阶段的次序逐段解决整个过程的优化问题。阶段变量通常用k表示（k = 1，2，3，…，n）。 2、状态（state） 每个阶段开始时过程所处的自然状况或客观条件。它应能描述过程的特征并具有“无后效性”，即当前阶段状态给定时，这个阶段以后过程的演变与该阶段以前各阶段的状态无关。 状态变量 —— sk（state variable） 状态集合 —— Sk（set of admissible states） 动态规划 Dynamic Programming（DP） 动态规划的基本概念 3、决策（decision） 当一个阶段的状态确定后，可以作出不同的决定或选择，从而演变到下一阶段的某个状态，这种决定或选择称为决策。 决策变量 —— uk（sk） （decision variable）简记为 uk 决策集合 —— Dk（sk）（set of admissible decision） 4、策略（policy） 一组有序的决策序列构成一个策略，从第k阶段至第n阶段的一个策略称为后部子策略记为 pk，n →（uk，uk+1，…，un）。 动态规划 Dynamic Programming（DP） 动态规划的基本概念 5、状态转移方程（equation of state transition） 在动态规划中，本阶段的状态往往是上一阶段的状态和决策共同作用的结果。当给定了上一阶段的状态sk ,以及作出了本阶段的决策uk 后,则下一阶段（K+1阶段）的状态sk+1 便完全确定。用状态转移方程反映这种状态间的演变规律，写作： sk+1 = Tk（sk，uk） k =1，2，…，n 6、阶段指标值---函数（objective value in a stage） 衡量在一个阶段某个状态下各决策所对应的某种数量指标或效果，通常表示为 vk（sk，uk）。 动态规划 Dynamic Programming（DP） 动态规划的基本概念 7、指标函数（objective function）——过程指标值 衡量在选定某策略时，其优劣的数量指标。 动态规划 Dynamic Programming（DP） 动态规划的基本概念 8、最优指标函数（optimal value function） 从第k阶段状态 sk 出发，采用最优策略 p*k，n 到终止时的后部子过程指标函数值。 动态规划 Dynamic Programming（DP） 动态规划的基本思想与原理 动态规划发展的早期，从简单逻