道路与交通系统分析课件.ppt

目录 第一章系统与系统分析概念第二章线性规划第三章动态规划第四章非线性规划第五章图论第六章排队论 已学过 第七章预测第八章决策分析第九章经济分析与评价 第一章引论 系统与系统工程系统分析主要内容和重点 系统的概念 特性与形态 系统工程方法论的基本特点 系统分析的基本概念 系统分析的步骤 系统的模型化 系统的最优化 系统评价 系统决策分析 第一章系统工程与系统分析基本概念 系统与系统工程 一 系统的概念 特性与形态所谓系统 是指由相互作用 相互依赖而又能相互区别的若干组成部分 单元 组合而成的 具有特定功能的有机整体 系统四个特征 整体性相关性目的性环境适应性 一 系统的概念 特性与形态 系统形态可分为以下几类 自然系统与人造系统实体系统与概念系统动态系统与静态系统控制系统与行为系统 二 系统工程 系统工程方法论的基本特点可归纳如下 研究方法上的整体性 2 应用技术上的综合性 3 处理问题上的科学性按时间顺序可分为下述三个阶段 系统规划阶段 2 系统设计阶段 3 系统制造和运行阶段 问题的提出 系统计划 概略设计 目标的确定具体条件的确定 系统分析 方案确定 详细设计 试制 制造 运行 系统规划 系统设计 系统制造与运行 构思计划 分析设计 改进运行 图1系统建立流程图 把上述系统工程的基本处理方法具体化 那就是在系统工程中最常使用的系统分析 系统设计方法 这种方法不但用于系统设计阶段 还可用于系统规划阶段及系统制造与运行阶段 以求得系统的合理规划 系统的最优制造方法及系统的最优运行方式 1 系统分析 2 系统设计 3 系统的综合评价 该方法大致可分为下列三个步骤 分析 综合 评价 系统的要求 系统的设计 图2系统工程基本处理方法框图 系统分析 一 系统分析的基本概念系统分析的目的 通过分析比较各种替代方案的费用 效益 功能和可靠性等各项技术经济指标 得出决策者决策所必须的资料和信息 以便最后获得最优系统方案 图3表示 系统问题 系统分析 最优系统方案 图3系统分析的目的 系统分析可概括为以下几个步骤 系统目的的分析和确定 2 系统模型化 3 系统最优化 4 对解的评价具体的步骤流程如教本P8图1 4 一 系统分析的基本概念 二 系统目的的分析与确定 对象系统的定义 2 目的和目标的分析与确定 3 技术条件的分析和定义 4 系统功能的分析与定义 5 根据概略模型探讨成功的可能性 6 若不能取得可以成功的技术条件时 则采取下述措施之一 修改概略模型 重新对功能技术条件进行分析 重新对目的 目标进行分析 这是系统分析的最初阶段 步骤与内容 三 系统的模型化 模型分类 形象模型 2 抽象模型 模拟模型 数学模型 概念模型 对模型的要求一般为 1 现实性 2 简洁性 3 适应性 三 系统的模型化 建立数学模型来说 可有以下几步 1 分析模型的使用目的和要求 并确定模型的功能 2 根据目的要求 从时间和空间等方面来明确系统和环境等的边界条件 3 确定构成系统功能的最小单位 也就是说把系统划分成若干可以模型化的单元 或子系统 它可根据模型的使用目的来确定 4 分析和掌握模型化对象 单元或子系统 的特点 主要因素和逻辑结构 最后建立模型 5 应用最优化理论和系统控制理论 分析和明确整个系统的特点 同时讨论适用的最优化方法 四 系统的最优化 系统最优化是通过模型进行的 图1 4所示的框图中 表示了系统最优化的一般步骤 图中分别就数学模型 图象模型等表示了最优化过程 上述最优化方法的具体内容将在第二章至第六章中详细介绍 五 系统的评价 系统评价就是指从技术和经济等多个方面对所设计的各个替代方案的最优解进行评价 通过分析和评价 从中选择在技术上是先进的 在经济上是合理的方案作为最优系统方案 对系统进行评价 首先必须确定评价基准 即确定各种替代方案优先选用顺序的标准 评价基准一般根据系统的具体情况而定 五 系统的评价 例如 在评价系统的费用和效益时 评价基准可以从下述三种基准中选用 即 1 以各替代方案效益相同为基准 选择费用最小的方案为最优方案 2 以各方案费用相同为基准 选择效益最大的方案为最优方案 3 以效益费用比为基准 选择效益费用比最大的方案为最优方案 进行系统的经济评价时 必须考虑到时间价值的影响 六 系统决策分析 所谓决策 就是根据客观可能性 借助于一定的理论 方法和工具 进行科学的分析 正确的计算和判断后的一种行动推测 决策科学是现代科学管理的关键 系统决策分析就是根据系统评价的结果 对多个系统方案进行抉择 人们对确定条件下的情况 是容易作出直接判断 进行决策的 但对含随机性条件及不确定条件的情况 进行决策就困难了 必须借助于决策理论 第八章中予以介绍 第四章非线性规划 预备知识一维搜索无约束极值问题的解法有约束极值问题及求解 重点 在道路交通工程中的应用 一 一般描述目标函数或约束条件出现非线性函数时 则这样的极值问题就是非线性极值问题或非线性规划 数学模型的一般形式如下 预备知识 预备知识 有时可写成 或 二 极值问题 预备知识 1 局部最优解和全局最优解2 多元函数和导数 重点 3 极值点存在的条件 重点 预备知识 1 局部最优解和全局最优解定义1 1可行点S 若对每一个 均有 则称为非线性规划的最优解或称为全局最优解或极小点 定义1 2可行点S 若存在的某个领域使得对每个 有 则称为非线性规划的局部最优解或局部极小点 2 多元函数和导数 1 偏导数 2 梯度 3 方向导数 4 海森矩阵 5 正定矩阵 6 多元函数的泰勒展开 预备知识 3 极值点存在的条件定理3 1 必要条件 定理3 2 充分条件 例 预备知识 三 目标函数的凸性讨论 1 凸集 2 凸组合 3 顶点 4 凸函数与凹函数 5 凸函数的性质 6 函数凸性的判定定理 7 凸函数的极值 预备知识 四 凸规划可行点 可行域其中 为凸函数 此非线性规划为凸规划 预备知识 预备知识 五 下降算法 下降迭代法的基本思想是 首先给出非线性极值问题的最优解或局部最优解的一个初始估计 称为初始点 然后 通过某种迭代算法得到一系列的可行点 希望点列 的极限就是非线性极值问题的一个最优解或局部最优解 五 下降算法 产生点列的方法 若从点出发 沿任何方向移动时 在S中都不存在可行点使目标函数值下降 则是非线性极值问题的一个局部最优解 迭代结束 若从出发至少存在一个方向 在S中沿此方向可以使目标函数值有所下降 则选定能使目标函数值下降的某个方向 然后沿此方向移动适当的一步 得到下一个迭代点 即在射线上选取一个新的可行点使 五 下降算法 产生点列的方法 其中是一个向量 称为搜索方向 而是一个实数 称为搜索步长或步长 当和确定以后 由就可以唯一确定 这样可以产生目标函数值下降且逼近非线性极值问题的最优解和局部最优解的序列 这种算法称为下降迭代算法 五 下降算法 五 下降算法 迭代精度的确定 1 相继两次迭代的绝对误差 或2 相继两次迭代的相对误差 或3 目标函数梯度的模 如果目标函数存在梯度的话 可以根据目标函数在最近迭代点处的梯度模足够小作为结束迭代的准则 即 一维搜索 为了确定极小化点列 在每次迭代时要沿确定的搜索方向 在射线上 确定一个适当的步长 使且 在不少非线性最优化的下降算法中 步长的选取要求目标函数在点的值下降最多 即步长满足也就是求一元函数 的极小值点 这种确定迭代步长的方法称为精确一维搜索或简称一维搜索 一维搜索 精确一维搜索法 牛顿法 2 抛物线法 3 二分法 4 成功 失败 法 5 Fibonacci法 6 黄金分割法 7 初始区间和初始点的确定 进退算法 不精确一维搜索法 一维搜索 1 直接法 2 二次插值法 精确一维搜索 1 牛顿法牛顿法的基本思想是 用在已知点处的二阶Taylor展开式来近似代替 即 然后用二次函数的极小点作为的近似极小点 参见图3 1 精确一维搜索 图3 1 1 牛顿法 精确一维搜索 由 令 得类似 若已知 则有进行迭代计算 得一点列 这种求一元函数极小值问题的一维搜索方法称为牛顿法 当时 则迭代结束 为近似极小值点 即 习题 1 牛顿法 一般公式 牛顿法收敛速度快 但是它对函数要求二次可微 且要计算二阶导数 另外还要求初始点选得好 否则可能得到的点列不收敛 牛顿法产生的点列即使收敛 有时其极限也不一定是所要求的函数的极小值点 而只能保证它是函数的驻点 一阶导数为0的点 驻点可能是极小值点 也可能是极大值点 也可能不是极值点 精确一维搜索 1 牛顿法 特点 精确一维搜索 2 抛物线法 牛顿法是用在点的二阶Taylor展开式来逼近 即利用点的函数值及其一阶 二阶导数值 来构造二次函数 而抛物线法则是利用在三个点 处的函数值来构造二次函数 使它满足 设 则 令 得即可求得的近似极小值点 上式就是近似极小值点的计算公式 为求出近似极小值点 将代入方程组 便可求得 其中其中可得可得将代入 4 8 或利 精确一维搜索 2 抛物线法 一般公式 精确一维搜索 2 抛物线法 特点 精确一维搜索 3 二分法 若一区间使且 则在之间一定有一个的极小值点使得取 若 则用区间代替区间 再取 若 则用代替区间 再取 经过次迭代 设所得缩小的区间为 若或时 则取极小值 迭代结束 否则继续进行迭代 精确一维搜索 每步迭代的计算量比较小 程序简单 而且总能收敛于一个局部极小值点 但是收敛较慢 对称取点 每次迭代缩减率相同 习题 3 二分法 特点 精确一维搜索 4 成功 失败 法迭代步骤 1 任意取定一初始点 设定迭代搜索的步长及精度 2 计算及 3 若 则称此步向前搜索成功 就加大步长继续向前搜索 即用代替 用步长代替步长 继续向前搜索 若 则称搜索失败 向后搜索 首先看是否 若是 则极小值点取 结束 否则 用代替步长 返回2 继续进行搜索 精确一维搜索 考虑如下一维极小化问题其中要求在是单峰凸函数 思路 任取则 1 若 则可将搜索区间缩小为 2 若 则可将搜索区间缩小为如此下去 最终必越来越逼近最优解 5 Fibonacci法 精确一维搜索 F法的基本思路 对称取点考虑 0 1 极小化问题 1 选取两个初始点 2 比较和 3 进行下一次实验 重新选取和 4 若满足 则停止 否则返 3 若给定的区间不是 0 1 而是 则给定的容许误差 下同 5 Fibonacci法 精确一维搜索 F法对称取点取法 考虑极小化问题选取两个初始点 使 5 Fibonacci法 1 由精度确定N 2 计算N次函数值 可获得最小的最终区间 3 适用于一般函数 在极小点附近效果好 精度较高 速度快例 用F法求函数的近似极小点 要求缩短后的最终区间不大于原区间 1 3 的8 5 Fibonacci法的特点 精确一维搜索 精确一维搜索 6 黄金分割法 0 168法 它是Fibonacci法一种简化方法 黄金分割法是不用导数的一维搜索方法中比较常用的一种方法 考虑极小化问题 黄金分割法计算上面问题的极小值点的步骤如下 原始问题的变量原始问题的松弛变量 精确一维搜索 6 黄金分割法 0 168法 1 设定最后区间长度精度 令 0 618 2 计算令 3 若 则结束 取极小值点 1 2 否则 若 则转4 否则转5 原始问题的变量原始问题的松弛变量 精确一维搜索 6 黄金分割法 0 168法 4 令 再令 并计算 转6 5 令 再令 并计算 转6 6 令 返回步骤3 原始问题的变量原始问题的松弛变量 精确一维搜索 6 黄金分割法 0 168法 黄金分割法收敛速度是比较慢的 它的优点是不要求可微 且每次迭代 只需计算一个函数值 因此 计算量小 程序简单 原始问题的变量原始问题的松弛变量 精确一维搜索 7 初始区间和初始点的确定 一般求解一维极小化问题时 都要求先确定一个较好的初始点或一个含有极小值点的初始搜索区间 为此 下面我们来给出一种确定一维极小化问题的初始搜索区间和初始点的算法 进退算法 是初始区间和初始点的确定算法的基本步骤是 doc 原始问题的变量原始问题的松弛变量 不精确一维搜索 在实际计算中 一般做不到精确的一维搜索 实际上 也没有必要做到这一点 因为精确的一维搜索需要付出较高的代价 而对加速收敛作用不太大 下面介绍两种较实用的不精确一维搜索方法 不精确一维搜索 2 二次插值法特点 不精确一维搜索的方法简单 而且有时收敛速度还比精确一维搜索方法快得多 1 直接法 无约束极值问题的解法 一般求解无约束极值问题的算法基本上都是下降算法 本节介绍求解多维无约束非线性规划问题比较常用有效的算法 包括最速下降法 梯度法 牛顿法和阻尼牛顿法 共轭梯度法 变尺度法 直接搜索法等 1 最速下降法 2 牛顿法 3 阻尼牛顿法 4 共轭梯度法 5 变尺度法 6 直接搜索法 无约束极值问题的解法 无约束极值问题的解法 1 最速下降法 最速下降法 也叫梯度法 是人们用来求多变量函数的极值问题的最早的一种方法 后来提出的不少方法基本上都是这种算法的改进算法 梯度法的基本思路梯度法的迭代步骤 无约束极值问题的解法 最速下降法其实并不是一种非常理想的求解非线性极值问题的算法 这是因为当用最速下降法迭代趋近极小点时 其搜索路径呈直角锯齿状 相邻两次的搜索方向互相垂直 在迭代开始时下降比较快 但是当迭代点列接近极小点时收敛速度会很慢 1 最速下降法 无约束极值问题的解法 2 牛顿法 一维极值问题的牛顿法 它容易推广到多维的情况 这个方法也是求解无约束极值问题的最早算法之一 牛顿法的基本思想牛顿法的计算步骤牛顿法的特点 无约束极值问题的解法 3 阻尼牛顿法 阻尼牛顿法的基本思想阻尼牛顿法的计算步骤阻尼牛顿法的特点 阻尼牛顿法保持了牛顿法快速收敛的优点 又不要求初点选得很好 因而在实际应用中取得了较好的效果 当然其迭代公式中也没有避免要求海赛矩阵的逆阵 无约束极值问题的解法 4 共轭梯度法 基本思想 最速下降法 步骤简单 但收敛速度太慢 而牛顿法和阻尼法收敛速度快 但要计算二阶偏导数矩阵及其逆阵 计算量太大 共轭梯度法兼有这两种方法的优点 它比最速下降法的收敛速度要快得多同时又避免了像牛顿法所要求的海赛矩阵的计算 存贮和求逆 无约束极值问题的解法 4 共轭梯度法 共轭梯度法是以一种叫共轭方向作为迭代的搜索方向的下降算法 共轭方向概念 共轭梯度法求解无约束二次规划思想共轭梯度法求解无约束二次规划步骤共轭梯度法求解非线性无约束极值问题思想求解非线性无约束极值问题步骤 无约束极值问题的解法 共轭梯度法的特点 共轭梯度法对一般目标函数的无约束优化问题的求解具有较高的效率 因此在无约束优化算法中占有重要的地位 是目前最常用的方法之一 由于它的计算公式简单 存贮量少 可以用来求解比较大的问题 对于交通系统规划中遇到的极值问题 这方法是效果较好的算法 4 共轭梯度法 无约束极值问题的解法 5 变尺度法 变尺度法的基本思想变尺度法的计算步骤 无约束极值问题的解法 5 变尺度法 变尺度法的特点 变尺度法也是求解无约束极值问题的一种有效算法 由于它既避免了计算二阶导数海赛矩阵及其求逆过程 又比梯度法的收敛速度快 特别是对高维极值问题具有显著的优越性 有约束极值问题的解法 道路工程与交通系统规划中经常遇到许多问题的数学模型描述大多是非线性最优化问题 变量和约束条件一般比较多 规模较大 所以约束非线性最优化方法在道路与交通工程系统分析中极其重要 算法大多相当复杂 没有一种对一切有约束极值问题的求解都普遍有效的算法 许多方法求得的解大多不能保证是全局最优解 而只能是局部最优解 有约束极值问题的解法 解法思路 一般基本上的处理是将非线性约束极值问题转化成无约束极值问题 例如惩罚函数法 将非线性极值问题转化成线性规划问题或用二次规划来逐次逼近 将复杂的约束问题转化成简单问题来处理 有约束极值问题的解法 解的最优性条件 紧约束 紧约束指标集的定义定理 最优性的一阶必要条件定理 最优性的充分条件 例 有约束极值问题的解法 广义拉格朗日乘子法 如前述 惩罚函数法 惩罚函数法是求解约束极值问题一种重要而常用方法 通过将约束极值问题转化成一系列无约束极值问题来求解的 所以称为序列无约束极小化技术 或称SUMT法 惩罚函数法是序列无约束极小化技术之一 又称其为SUMT外点法 有约束极值问题的解法 惩罚函数法构造思路 惩罚函数法的计算步骤 例 有约束极值问题的解法 碰壁函数法 碰壁函数法跟惩罚函数法一样 也是将约束极值问题转化无约束极值问题 也是属于序列无约束极小化技术 它要求约束极值问题的可行约束集连通且内部非空 所以有别于SUMT外点法 称其为SUMT内点法 碰壁函数法要求约束极值问题的可行集S连通且内部intS非空 所以可行集中没有等式约束 有约束极值问题的解法 碰壁函数法构造思路 碰壁函数法的计算步骤 有约束极值问题的解法 可行方向法 动态规划的基本原理最短路径问题资源分配问题一般数学规划问题 第四章动态规划 动态规划的基本原理 概述 动态规划是运筹学的一个分支 它是解决多阶段决策过程最优化的一种数学方法 所谓多阶段决策过程是指这样一类决策过程 它可以分为若干个互相联系的阶段 在每一阶段分别对应着一组可以选取的决策 在每一阶段都需要作出决策 从而使整个过程达到最好的效果 当各个阶段决策确定后 就构成了一个决策序列 称为一个策略 动态规划问题的解题思路 是将一个n阶段的决策问题转化为依次求解n个具有递推关系的单阶段的决策问题 从而简化计算过程 这种转化的实现是从终点E出发一步步进行反推 这种算法称为逆序算法 动态规划的基本概念和方法 动态规划的基本原理 动态规划的基本概念和方法 从解题的过程看出 将一个多阶段的决策问题转化为依次求解多个单阶段的决策问题时 一个重要特征是将前面的解传递并纳入下一个阶段一并考虑 即做到求解的各阶段间具有递推性 动态规划的基本原理 动态规划的基本概念和方法 1 阶段 stage 是指一个问题需要作出决策的步数 通常用k来表示问题包含的阶段数 称为阶段变量 k的编号方法有两种 1 顺序编号法 即初始阶段编号为1 以后随进程逐渐增大 2 逆序编号法 令最后一个阶段编号为1 往前推时编号逐渐增大 动态规划的基本原理 动态规划的基本概念和方法 2 状态 state 各阶段的状态通常用状态变量x来描述 它既反映前面各阶段决策的结局 又是本阶段作出决策的出发点和依据 第k阶段的状态变量xk应包含该阶段之前决策过程的全部信息 做到从该阶段后做出的决策同这之前的状态和决策相互独立 动态规划的基本原理 动态规划的基本概念和方法 3 决策 decision 是指某阶段初从给定的状态出发 决策者在面临的若干种不同方案中做出的选择 决策变量uk xk 表示第k阶段状态为xk时对方案的选择 决策变量的取值要受到一定范围的限制 用Dk xk 表示k阶段状态为xk时决策允许的取值范围 称允许决策集合 uk xk Dk xk 动态规划的基本原理 动态规划的基本概念和方法 4 策略 Policy 和子策略 subpolicy 动态规划问题各阶段决策组成的序列总体称作一个策略 含n个阶段的动态规划问题的策略可写为 p1 n u1 x1 u2 x2 un xn 把从某一阶段开始到过程最终的决策序列称为问题的子过程策略或子策略 从k阶段起的子策略pk n uk xk uk 1 xk 1 un xn 动态规划的基本原理 动态规划的基本概念和方法 5 状态转移律从xk的某一状态值出发 当决策变量uk xk 的取值决定后 下一阶段状态变量xk 1的取值也就随之确定 这种从上阶段的某一状态值到下阶段某一状态值的转移的规律称为状态转移律 下一阶段状态xk 1的取值是上阶段状态变量xk和上阶段决策变量uk xk 的函数 记为 xk 1 T xk uk xk 或 xk 1 T xk uk 动态规划的基本原理 动态规划的基本概念和方法 6 指标函数衡量实现过程优劣的一种数量指标 分为阶段指标函数和过程的指标函数 阶段指标函数是对应某一阶段状态和从该状态出发的一个阶段的决策的某种效益度量 用vk xk uk 表示 过程指标函数是指从状态xk k 1 n 出发至过程最终 当采取某种子策略时 所得到的效益值 这个值既与xk的状态值有关 又与xk以后所选取的策略有关 它是两者的函数值 记作Vk n xk uk xk 1 uk 1 xn 动态规划的基本原理 动态规划的基本概念和方法 常见的指标函数的形式是 1 过程和它的任一子过程的指标是它所包含的各阶段的指标的和 Vk n xk uk xk 1 xn vk xk uk Vk 1 n xk 1 xn 2 过程和它的任一子过程的指标是它所包含的各阶段的指标的乘积 则Vk n xk uk xk 1 xn vk xk uk Vk 1 n xk 1 xn 动态规划的基本原理 动态规划的基本概念和方法 过程指标函数的最优值 称为最优指标函数 它是指从第k阶段的状态xk开始到第n阶段终止状态 采取最优策略所得到的指标函数值 对应于从状态xk出发的最优子策略 过程指标函数值记作fk xk 于是有fk xk optVk n式中opt代表最优化 根据效益值的具体含义可以是求最大或求最小 动态规划的基本原理 求从A到E的最短路径 最短路径问题 状态最优决策状态最优决策状态最优决策状态最优决策状态 A A B2 B2 状态最优决策状态最优决策状态最优决策状态最优决策状态 A A B2 B2 B2 C1 C1 状态最优决策状态最优决策状态最优决策状态最优决策状态 A A B2 B2 B2 C1 C1 C1 D1 D1 状态最优决策状态最优决策状态最优决策状态最优决策状态 A A B2 B2 B2 C1 C1 C1 D1 D1 D1 E E从A到E的最短路径为19 路线为A B2 C1 D1 E 所谓资源分配问题 就是将数量一定的一种或若干种资源 例如原材料 资金 设备 劳力等 恰当地分配给若干个使用者 使目标函数为最优 资源分配问题 资源分配问题 4万元资金 如何分配给A B C三个项目 使总效益最大 4万元 2