最优化原理：作为整个过程的最优策略具有这样的性质：无论过去的状态和决策如何，相对于前面 的决策所形成的状态而言，余下的决策序列必然构成最优子策略。”也就是说， 个最优策略的子策 略也是最优的 (三)建立动态规划模型的步骤 1、划分阶段 划分阶段是运用动态规划求解多阶段决策问题的第一步，在确定多阶段特性后，按时间或空间先后 顺序，将过程划分为若干相互联系的阶段。对于静态问题要人为地赋予“时间”概念，以便划分阶段。 2、正确选择状态变量 选择变量既要能确切描述过程演变又要满足无后效性，而且各阶段状态变量的取值能够确定。一般 地，状态变量的选择是从过程演变的特点中寻找。 3、确定决策变量及允许决策集合 通常选择所求解问题的关键变量作为决策变量，同时要给出决策变量的取值范围，即确定允许决策 集合 4、确定状态转移方程 根据k阶段状态变量和决策变量，写出k+1阶段状态变量，状态转移方程应当具有递推关系。 5、确定阶段指标函数和最优指标函数，建立动态规划基本方程 阶段指标函数是指第k阶段的收益，最优指标函数是指从第k阶段状态出发到第阶段末所获得收益 的最优值，最后写出动态规划基本方程 以上五步是津立动态规数学模型的一船先骤。由干动态规划草型与线性规划草型不同.动态规划 模型没有统一的模式，建模时必须根据具体问题具体分析，只有通过不断实践总结，才能较好掌握 建模方法与技巧。 5.3离散确定性动态规划模型的求解 见第5章PPT第18-23页。 5.4一般数学规划模型的动态规划解法 这里所说的一般数学规划模型包括线性规划、非线性规划、整数规划等，利用动态规划进行求解 时，主要思想是把依次决定各个变量的取值看成是一个多阶段的决策过程，因而模型中含有多少个 变量，求解就分成多少个阶段。约束条件的右端项表明可分配的资源数，用状态变量表示。 例背包问题及动态规划求解，见第5章PPT第25-32页。 第6章图与网络优化 6.1图的基本概念 由m个顶点v1,v2,vm与n条边e1,e2,…,en,两组基本元素组成的结构称为图，记为G=(V,E), 其中V={v1,2..,vm},E={e1,e2,…,en。 “结构指图中的点与边之间的关联关系。 在一个图中，只要确定了点边关联关系 无论如何改变顶点的位置，改变边的形状和大小，所得到 的新图都与原图是同一个图，也称为同构。 图论中的图是由点和点与点之间的联线所组成的。把点与点之间不带箭头的线叫做边，带箭头的线 叫做弧。 如果一个图是由点和边所构成的，称为无向图，记作G=(N,E),其中V表示图G的点集合，E表 示图G的边集合.连接点i,V的边记作i,,或者j,v. 如果一个图是由点和弧所构成的，那么称它为有向图，记作D=N,A),其中V表示有向图D的点集 合，A表示有向图D的弧集合。 -条方向从vi指向y的弧，记作(vi,). 一个图G或有向图D中的点数，记作p(G)或即(D),简记作印，边数或者弧数，记作q(G)或g(D),简记作q最优化原理：作为整个过程的最优策略具有这样的性质：无论过去的状态和决策如何，相对于前面 的决策所形成的状态而言，余下的决策序列必然构成最优子策略。”也就是说，一个最优策略的子策 略也是最优的。 （三）建立动态规划模型的步骤 1、划分阶段 划分阶段是运用动态规划求解多阶段决策问题的第一步，在确定多阶段特性后，按时间或空间先后 顺序，将过程划分为若干相互联系的阶段。对于静态问题要人为地赋予“时间”概念，以便划分阶段。 2、正确选择状态变量 选择变量既要能确切描述过程演变又要满足无后效性，而且各阶段状态变量的取值能够确定。一般 地，状态变量的选择是从过程演变的特点中寻找。 3、确定决策变量及允许决策集合 通常选择所求解问题的关键变量作为决策变量，同时要给出决策变量的取值范围，即确定允许决策 集合 4、确定状态转移方程 根据k 阶段状态变量和决策变量，写出k+1阶段状态变量，状态转移方程应当具有递推关系。 5、确定阶段指标函数和最优指标函数，建立动态规划基本方程 阶段指标函数是指第k 阶段的收益，最优指标函数是指从第k 阶段状态出发到第n 阶段末所获得收益 的最优值，最后写出动态规划基本方程。 以上五步是建立动态规划数学模型的一般步骤。由于动态规划模型与线性规划模型不同，动态规划 模型没有统一的模式，建模时必须根据具体问题具体分析，只有通过不断实践总结，才能较好掌握 建模方法与技巧。 5.3 离散确定性动态规划模型的求解 见第5章PPT第18-23页。 5.4 一般数学规划模型的动态规划解法 这里所说的一般数学规划模型包括线性规划、非线性规划、整数规划等，利用动态规划进行求解 时，主要思想是把依次决定各个变量的取值看成是一个多阶段的决策过程，因而模型中含有多少个 变量，求解就分成多少个阶段。约束条件的右端项表明可分配的资源数，用状态变量表示。 例 背包问题及动态规划求解，见第5章PPT第25-32页。 第6章 图与网络优化 6.1 图的基本概念 由m个顶点v1,v2,…,vm与n条边e1,e2,…,en，两组基本元素组成的结构称为图，记为G=（V，E）， 其中V={v1,v2,…,vm}，E={e1,e2,…,en}。 “结构”指图中的点与边之间的关联关系。 在一个图中，只要确定了点边关联关系，无论如何改变顶点的位置，改变边的形状和大小，所得到 的新图都与原图是同一个图，也称为同构。 图论中的图是由点和点与点之间的联线所组成的。把点与点之间不带箭头的线叫做边，带箭头的线 叫做弧。 如果一个图是由点和边所构成的，称为无向图，记作 G =(V，E )，其中V 表示图G 的点集合，E 表 示图G的边集合。连接点 vi,vjV 的边记作[vi,vj]，或者[vj,vi]。 如果一个图是由点和弧所构成的，那么称它为有向图，记作D =(V, A)，其中V 表示有向图D的点集 合，A 表示有向图D的弧集合。一条方向从vi指向vj的弧，记作(vi,vj)。 一个图G 或有向图D 中的点数,记作p(G)或p(D), 简记作p, 边数或者弧数, 记作q(G)或q(D), 简记作q