系统工程-第六章动态规划.ppt

第六章 动态规划,6.1 动态规划的基本原理和基本方程 6.2 机器负荷分配问题 6.3 资源分配问题 6.4 背包问题 6.5 连续型动态规划问题,6.1 动态规划的基本原理和基本方程,6.1.1 动态规划的最优性原理 6.1.2 动态规划的基本概念 6.1.3 动态规划的基本方程 6.1.4 建立动态规划的数学模型 6.1.5 动态规划的求解,6.1.1 动态规划的最优性原理,6.1 动态规划的基本原理和基本方程, 动态规划是解决多阶段决策问题的一种数学方法。 所谓多阶段决策问题，是指对系统运行过程中若干相继阶段的每一段都要作出决策，并使整个过程达到最优的一类问题。,50年代，美国数学家贝尔曼(Richard Bellman)等人，根据多阶段决策问题的性质，提出了解决这类问题的“最优性原理”，并研究了许多实际问题，从而建立了一种新的最优化方法动态规划（Dynamic Programming)。,表述一：一个最优策略具有这样的性质，不论初始状态及初始决策如何，对于该决策所造成的某一状态而言，下余的所有决策必构成一个最优策略。,表述二：假设对任意的时刻t，不论过程在时刻t以前的历史状态如何，若按时刻t的状态而言，过程今后的行为是最优的。则整个过程的行为亦必是最优的。(无后效性),表述三：如图，假设采取了最优策略，得到了某个系统运动的最优轨线，该最优轨线将状态空间中的点（起点）与点（终点）连接起来，现在最优轨线上取某个中间点，从而将最优线分为、两段，则子轨线也是最优的。,6.1 动态规划的基本原理和基本方程,6.1.1 动态规划的最优性原理,表示每个阶段开始所处的自然状况或客观条件。又称不可控因素。描述过程状态的变量称为状态变量，用si 表示。显然，si 既是阶段（i-1）的结束状态，又是阶段 i 的起始状态。,将整个系统过程恰当地分为若干个相互联系的阶段，以便能按一定的次序求解。描述阶段的变量称为阶段变量，常用i 表示。阶段数用n表示。,(2)状态（State）,(1)阶段（Stage）,6.1 动态规划的基本原理和基本方程,6.1.2 动态规划的基本概念,(3)决策（Decision）,(4)策略（Policy）各阶段的决策组成的一个决策序列称为一个策略，记为：,从阶段i开始的过程，称为i子过程，它包含阶段i，阶段i+1，阶段n。i子过程的决策序列称为i子策略，记为,6.1 动态规划的基本原理和基本方程,阶段指标(或阶段收益)，是衡量每一阶段决策优劣的数量指标。指标函数是衡量全过程策略或i子过程策略优劣的数量指标,指标函数的最优值称为最优指标函数，记为 f1(s1) 或 fi (si)。,（5）状态转移方程,由某一阶段的一个状态到下一阶段的另一状态的演变称为状态转移。描述状态转移规律的方程称为状态转移方程。记为 si+1 = gi (si , xi) gi称为状态转移函数。,（6）阶段指标、指标函数、最优指标函数,6.1 动态规划的基本原理和基本方程,6.1 动态规划的基本原理和基本方程,6.1.3 动态规划的基本方程,(1) 动态规划的基本方程(逆序递推公式),(2) 动态规划的基本方程(正序递推公式),6.1 动态规划的基本原理和基本方程,6.1.4 建立动态规划的数学模型,（1）划分阶段,按照时间、空间、变量等进行划分。,（2）确定状态变量Si和状态集合,（3）确定决策变量xi及允许决策集合,（4）建立状态转移方程 si-1= g(si, xi) 或 si+1= g(si, xi),（5）确定各阶段的阶段收益,（6）确定指标函数，建立动态规划的基本方程,（7）确定边界条件,6.1 动态规划的基本原理和基本方程,6.1.5 动态规划的求解,(1) 动态规划求解的基本方程(逆序递推公式),(2) 动态规划的求解的基本方程(正序递推公式),6.1 动态规划的基本原理和基本方程,6.1.5 动态规划的求解,6.1 动态规划的基本原理和基本方程,6.1.5 动态规划的求解,例：用动态规划方法(逆序递推公式)求解下面问题,试确定一条由A到D的最短铺设管道路线。,解：整个计算过程分为三个阶段来进行，首先从最后一个阶段开始按照逆序算法进行计算。 第三阶段：找出第三阶段各起点C1, C2, C3到终点D的最短路线。 在第三阶段，由始点C1, C2, C3到终点D的可行路线是唯一的，因此有,6.1 动态规划的基本原理和基本方程,第二阶段：找出第二阶段的始点B1, B2到终点D的最短路线。,最短路线为B1C2D。,最短路线B2C3D。,6.1 动态规划的基本原理和基本方程,第一阶段：找出第一阶段的起点A到终点D的最短路线,于是得到该问题的最优策略为,即最短路线为AB1C2D， 相应的最短距离为12。,6.1 动态规划的基本原理和基本方程,6.2 机器负荷分配问题,6.2.1 问题描述 6.2.2 静态规划模型 6.2.3 动态规划模型及其求解,6.2.1 问题描述,6.2 机器负荷分配问题, 有某种机器Q台 可以在高、低两种负荷下安排生产 机器的月完好率分别为a(高负荷)与 b (低负荷) 每台机器的月收益分别为c (高负荷)和d (低负荷) 。 要求:制定连续几个月的生产计划，合理分配机器负荷，使总收益为最高。,6.2.2 静态规划模型,6.2 机器负荷分配问题,设xij为第j月在第i种负荷下安排生产的机器台数，其中i=1表示高负荷，i=2表示底负荷，j=1,2,n（不妨假设计划期是从1月份开始），则根据题意，可以建立下面的线性规划模型,6.2.3 动态规划模型及其求解,6.2 机器负荷分配问题,设：Q=100台，a=0.5，b=0.8，c=10万元，d=6万元，n=4个月。,max,6.2 机器负荷分配问题,求解过程,6.2 机器负荷分配问题,即，前两个月全部安排低负荷生产，后两个月全部安排高负荷生产，这样可以获得最高总收益2040万元。,6.2 机器负荷分配问题,6.2 机器负荷分配问题,6.3 资源分配问题,6.3.1 问题描述 6.3.2 静态规划模型 6.3.3 动态规划模型及其求解,6.3.1 问题描述,6.3 资源分配问题,设有数量为a的资源，计划分配给n个项目。设xi (i=1, 2, , n)为分配给第i个项目的资源量，gi(xi)为第i个项目得到数量为xi的资源后可提供的收益，问如何分配资源a，可使总收益为最高？,6.3.2 静态规划模型,6.3 资源分配问题,6.3.3 动态规划模型及其求解,6.3 资源分配问题,例： 某工业部门拟将40万元的资金分配给4个工厂供扩建用。各个工厂获得投资可提高的利润如下表所列。试确定使总利润为最大的资金分配方案。,各个工厂使用资金可提供利润情况 （单位：万元）,6.3 资源分配问题,求解过程,分析：这个问题属于资源分配问题，这里的资源是资金。设资金的分配是以10万元为单位的，故xi的取值为0，10，si 。,把该问题分为四个阶段来考虑：,6.3 资源分配问题,6.3 资源分配问题,6.3 资源分配问题,6.3 资源分配问题,6.3 资源分配问题,6.3 资源分配问题,6.3 资源分配问题,6.3 资源分配问题,6.4 背包问题,6.4.1 问题描述 6.4.2 静态规划模型 6.4.3 动态规划模型及其求解,6.4.1 问题描述,6.4 背包问题,背包问题的原始意义：一个旅行者要从n种物品的每一种中挑选若干件装入他的背包中，已知第i种物品的重量及价值分别为ai和ci (i=1, 2, n)，又知这位旅行者所能承受的最大重量为a。问他应如何选择这n种物品的件数，才能使得价值为最大？,6.4.2 静态规划模型,6.4 背包问题,6.4.3 动态规划模型及其求解,6.4 背包问题,例： 用动态规划方法求解下列的背包问题,6.4 背包问题,求解过程,把该问题分为三个阶段来考虑：,6.4 背包问题,分析：这个问题属于背包问题，其中n=3，a=5，我们的问题是求,第三阶段：,第二阶段：,6.4 背包问题,现在回过头来求 和,6.4 背包问题,最后，再计算,故该背包问题的最优解为,相应的目标函数最大值为13。,6.5 连续型动态规划问题,6.5.1 问题描述 6.5.2 连续型动态规划模型及其求解 作业,6.5.1 问题描述,6.5 连续型动态规划问题,动态规划按其状态变量的取值情况可以分为离散型和连续型。 如果状态变量取值为离散数据，则称为离散型动态规划； 如果状态变量取值为连续数据，则称为连续型动态规划。,(1) 连续型动态规划的基本方程(逆序递推公式),(2) 连续型动态规划的基本方程(正序递推公式),6.5 连续型动态规划问题,6.5.2 连续型动态规划模型及其求解,例： 用动态规划方法求解下列的非线性规划问题,6.5.2 连续型动态规划模型及其求解,6.5 连续型动态规划问题,求解过程,6.5 连续型动态规划问题,6.5 连续型动态规划问题,6.5 连续型动态规划问题,6.5 连续型动态规划问题,6.5 连续型动态规划问题,例： 用动态规划方法求解下列线性规划问题,解：例6-3所采用的方法是正序算法，本例采取逆序算法。把确定变量 的取值作为第i个阶段，并令为 第i个阶段的决策变量， 为第i阶段的状态变量， 为i阶段的最优指标函数，其中 i=1, 2, 3，则该问题的阶段状态转移方程为,6.5 连续型动态规划问题,显然，问题是求,第三阶段：,第二阶段：,6.5 连续型动态规划问题,第一阶段：,6.5 连续型动态规划问题,用动态规划方法求解下列线性规划问题：,6.5 连续型动态规划问题,作业：,