动态规划肖健华

动态规划肖健华1第1页，共40页，2023年，2月20日，星期三动态规划（dynamicprogramming）是运筹学的一个分支，是求解多阶段决策过程的最优化数学分支。动态规划的“动态性”主要体现在研究对象的时序性上。2第2页，共40页，2023年，2月20日，星期三所谓多阶段决策问题是指这样一类活动过程：它可以分解为若干个相互联系的阶段，在每一阶段分别对应着一组可供选取的决策集合，即构成过程的每个阶段都需要进行一次决策的决策问题。将各阶段的决策综合起来构成一个决策序列，称为一个策略。3第3页，共40页，2023年，2月20日，星期三动态规划模型的分类决策过程的演变是否确定：确定性动态规划和随机性动态规划状态变量的取值是否连续：连续性动态规划和离散性动态规划动态规划分为四大类：连续确定性离散确定性连续随机性离散随机性4第4页，共40页，2023年，2月20日，星期三§7.1动态规划的基本理论动态规划三个例子最短路线问题资源分配问题静态非线性规划问题的动态求解5第5页，共40页，2023年，2月20日，星期三例1：最短路线问题设有一个旅行者从下图中的A点出发，途中要经过B、C、D等处，最后到达终点E。从A到E有很多条路线可以选择，各点之间的距离如图中所示，问该旅行者应选择哪一条路线，使从A到E的总路线最短？6第6页，共40页，2023年，2月20日，星期三例2：资源分配问题7第7页，共40页，2023年，2月20日，星期三例3：静态非线性规划问题的动态求解8第8页，共40页，2023年，2月20日，星期三7.1.1多阶段决策过程的数学描述多阶段决策问题的示意图下图表明：多阶段决策过程可分为若干个相互联系的阶段，每一个都要求作出相应的决策，以使整个过程达到最佳的活动效果。9第9页，共40页，2023年，2月20日，星期三任何一个阶段(Stage，即决策点)都是由输入(Input)、决策(Decision)、阶段指标函数(PayoffFunction)和输出(Output)构成的，其中输入输出也称为状态(State)，输入称为输入状态，输出称为输出状态。前一个阶段的输出状态为后一个阶段的输入状态。10第10页，共40页，2023年，2月20日，星期三7.1.2动态规划的基本概念1.阶段：是过程中需要作出决策的决策点，描述阶段的变量称为阶段变量，常用k表示，具有N个阶段的决策过程，其阶段变量k=1,2,…,N2.状态：是动态规划中最关键的一个参数，第k阶段的状态变量用Sk表示，它既反映前面各阶段决策的结局，又是本阶段作出决策的出发点和依据。Sk应包含该阶段之前决策过程的全部信息，做到从该阶段后做出的决策同之前的状态决策相互独立。这种性质在本书中被称为无后效性或健忘性。11第11页，共40页，2023年，2月20日，星期三12第12页，共40页，2023年，2月20日，星期三4.状态转移律13第13页，共40页，2023年，2月20日，星期三5.策略与子策略14第14页，共40页，2023年，2月20日，星期三6.指标函数15第15页，共40页，2023年，2月20日，星期三16第16页，共40页，2023年，2月20日，星期三17第17页，共40页，2023年，2月20日，星期三7.最优指标函数18第18页，共40页，2023年，2月20日，星期三7.1.3动态规划的数学模型一、动态规划问题的解题思路动态规划问题的复杂性在于各阶段之间的相互联系，由此使得各阶段局部最优不能保证全局最优。用动态规划方法解题的基本思路：将一个n阶段的决策问题转化为依次求解n个具有递推关系的单阶段决策问题，从而简化计算过程。19第19页，共40页，2023年，2月20日，星期三两种基本求解方法动态规划问题的求解有两种基本方法。逆序解法：从问题的最后一个阶段开始，逆多阶段决策的实际过程反向寻优。顺序解法：从问题的最初阶段开始，同多阶段决策的实际过程顺序寻优。20第20页，共40页，2023年，2月20日，星期三将一个多阶段的决策问题转化为依次求解多个单阶段的决策问题时，一个重要特征是将前面的解传递，并纳入下一阶段一并考虑，即做到求解的各阶段具有递推性。21第21页，共40页，2023年，2月20日，星期三二、动态规划的数学模型：最优化原理思路：从某一状态出发，寻找最优选择时，它是从下述所有可能的组合中进行优化选取的：将本阶段决策的指标效益值加上从下阶段开始采取最优策略时的指标效益值。这是一种递推关系式，按逆序算法时可以从最后一个阶段反推到过程的开始。22第22页，共40页，2023年，2月20日，星期三最优化原理美国的贝尔曼（Bellman）由上述思路提出求解动态规划的最优化原理：作为整个过程的最优策略具有这样的性质，无论过去的状态和决策如何，对先前决策形成的状态而言，余下的诸决策必须构成最优策略。23第23页，共40页，2023年，2月20日，星期三动态规划的基本方程24第24页，共40页，2023年，2月20日，星期三25第25页，共40页，2023年，2月20日，星期三边界条件26第26页，共40页，2023年，2月20日，星期三为构造和求解动态规划的数学模型，需要明确模型中有关阶段的划分、状态变量、决策变量、允许决策集合和状态转移方程的确定等，并注意以下各点。27第27页，共40页，2023年，2月20日，星期三（1）状态变量的确定是构造动态规划模型中最关键的一步，要求：①状态变量首先应描述反映研究过程的演变特征；②状态变量应包含到达这个状态前的足够信息，并无后效性；③状态变量还应具有可知性，即规定的状态变量的值可通过直接或间接的方法测知。注：状态变量可以是连续的或离散的，单个数据或多个数据。28第28页，共40页，2023年，2月20日，星期三（2）决策变量是对过程进行控制的手段，复杂的问题中决策变量也可以是多维的向量，它的取值可能是离散的，也可能是连续的，允许决策集合相当于线性规划问题的约束条件。29第29页，共40页，2023年，2月20日，星期三30第30页，共40页，2023年，2月20日，星期三31第31页，共40页，2023年，2月20日，星期三§7.2确定性动态规划确定性动态规划是阶段的输出状态完全由其输入状态和决策所决定的动态规划。确定性动态规划解决的问题可能包含经济管理的方方面面，可以说最短路线问题，可以是资源配置问题，也可以是其他的规划问题。32第32页，共40页，2023年，2月20日，星期三7.2.1最短路线问题例1：33第33页，共40页，2023年，2月20日，星期三7.2.2资源分配问题

所谓资源分配问题是指：将数量一定的某些资源（例如资金、机器设备、原材料、物资、劳力等）恰当地分配给若干个使用者，而使总的目标函数值为最优。资源分配问题本身是线性规划或非线性规划的一类静态问题人为引入时间因素，将其视为按阶段进行的多阶段决策问题，再按动态规划方法求解。34第34页，共40页，2023年，2月20日，星期三35第35页，共40页，2023年，2月20日，星期三36第36页，共40页，2023年，2月20日，星期三37第37页，共40页，2023年，2月20日，星期三38第38页，共40页，2023年，2月20日，星期三例