道路与交通系统分析.ppt

《道路与交通系统分析.ppt》由会员分享，可在线阅读，更多相关《道路与交通系统分析.ppt（135页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、目目 录录第一章第一章系统与系统分析概念系统与系统分析概念 第二章第二章 线性规划线性规划 第三章第三章动态规划动态规划第四章第四章非线性规划非线性规划第五章第五章图论图论第六章第六章排队论排队论（已学过）（已学过）第七章第七章预测预测 第八章第八章决策分析决策分析 第九章第九章经济分析与评价经济分析与评价第一章 引论 系统与系统工程系统与系统工程 系统分析系统分析 主要内容和重点：主要内容和重点：系统的概念、特性与形态系统的概念、特性与形态、系统工程方法、系统工程方法论的基本特点、论的基本特点、系统分析的基本概念系统分析的基本概念、系统分、系统分析的步骤析的步骤 、系统的模型化系统的模型化

2、、系统的最优化系统的最优化 、系统评价系统评价 、系统决策分析系统决策分析 第一章第一章 系系统统工程与系工程与系统统分分析基本概念析基本概念 系统与系统工程系统与系统工程 一、一、系统的概念、特性与形态系统的概念、特性与形态 所谓系统，是指由相互作用、相互依赖所谓系统，是指由相互作用、相互依赖而又能相互区别的若干组成部分（单元）组而又能相互区别的若干组成部分（单元）组合而成的，具有特定功能的有机整体。合而成的，具有特定功能的有机整体。系统四个特征：系统四个特征：整体性整体性 相关性相关性 目的性目的性 环境适应性环境适应性 一、一、系统的概念、特性与形态系统的概念、特性与形态系统形态可分为以

3、下几类系统形态可分为以下几类：自然系统与人造系统自然系统与人造系统 实体系统与概念系统实体系统与概念系统 动态系统与静态系统动态系统与静态系统控制系统与行为系统控制系统与行为系统 二、二、系统工程系统工程 系统工程方法论的基本特点可归纳如下：系统工程方法论的基本特点可归纳如下：(1)研究方法上的整体性研究方法上的整体性(2)应用技术上的综合性应用技术上的综合性(3)处理问题上的科学性处理问题上的科学性 按时间顺序可分为下述三个阶段：按时间顺序可分为下述三个阶段：系统规划阶段系统规划阶段(2)系统设计阶段系统设计阶段(3)系统制造和运行阶段系统制造和运行阶段 问题的提出问题的提出系统计划系统计划

4、概略设计概略设计目标的确定目标的确定具体条件的确定具体条件的确定系统分析系统分析方案确定方案确定详细设计详细设计试试 制制制制 造造运运 行行系系统统规规划划系系统统设设计计系系统统制制造造与与运运行行构构思思 计计划划分分析析 设设计计改改进进 运运行行图图1 1 系统建立流程图系统建立流程图 把把上上述述系系统统工工程程的的基基本本处处理理方方法法具具体体化化，那那就就是是在在系系统统工工程程中中最最常常使使用用的的系系统统分分析析、系系统统设设计计方方法法。这这种种方方法法不不但但用用于于系系统统设设计计阶阶段段，还还可可用用于于系系统统规规划划阶阶段段及及系系统统制制造造与与运运行行阶

5、阶段段，以以求求得得系系统统的的合合理理规规划划、系系统统的的最优制造方法及系统的最优运行方式。最优制造方法及系统的最优运行方式。(1)(1)系统分析；系统分析；(2)(2)系统设计；系统设计；(3)(3)系统的综合评价系统的综合评价。该方法大致可分为下列三个步骤该方法大致可分为下列三个步骤：分分 析析综综 合合评评 价价系统的要求系统的要求系统的设计系统的设计 图图2 系统工程基本处理方法框图系统工程基本处理方法框图 系统分析系统分析 一、一、系统分析的基本概念系统分析的基本概念 系系统统分分析析的的目目的的：通通过过分分析析比比较较各各种种替替代代方方案案的的费费用用、效效益益、功功能能和

6、和可可靠靠性性等等各各项项技技术术经经济济指指标标，得得出出决决策策者者决决策策所所必必须须的的资资料料和和信信息息，以以便便最最后后获获得得最最优优系系统统方方案案。图图3表表示。示。系统问题系统问题系统分析系统分析最优系统方案最优系统方案 图图3 系统分析的目的系统分析的目的 系统分析可概括为以下几个步骤：系统分析可概括为以下几个步骤：(1)系统目的的分析和确定系统目的的分析和确定(2)(2)系统模型化系统模型化(3)(3)系统最优化系统最优化(4)对解的评价对解的评价 具体的步骤流程如教本具体的步骤流程如教本P8图图1-4。一、系统分析的基本概念一、系统分析的基本概念 二、二、系统目的的

7、分析与确定系统目的的分析与确定(1)(1)对象系统的定义对象系统的定义(2)(2)目的和目标的分析与确定目的和目标的分析与确定(3)(3)技术条件的分析和定义技术条件的分析和定义 (4)(4)系统功能的分析与定义系统功能的分析与定义(5)(5)根据概略模型探讨成功的可能性根据概略模型探讨成功的可能性(6)(6)若不能取得可以成功的技术条件时，则采若不能取得可以成功的技术条件时，则采取下述措施之一：取下述措施之一：修改概略模型；修改概略模型；重新对功能技术条件进行分析；重新对功能技术条件进行分析；重新对目的、目标进行分析。重新对目的、目标进行分析。这是系统分析的最初阶段，步骤与内容：这是系统分析

8、的最初阶段，步骤与内容：三、三、系统的模型化系统的模型化模型分类：模型分类：(1)(1)形象模型形象模型 (2)(2)抽象模型抽象模型 模拟模型。模拟模型。数学模型。数学模型。概念模型。概念模型。对模型的要求一般为：对模型的要求一般为：(1)(1)现实性。现实性。(2)(2)简洁性。简洁性。(3)(3)适应性。适应性。三、三、系统的模型化系统的模型化建立数学模型来说，可有以下几步：建立数学模型来说，可有以下几步：(1)(1)分析模型的使用目的和要求，并确定模型的功能。分析模型的使用目的和要求，并确定模型的功能。(2)(2)根根据据目目的的要要求求，从从时时间间和和空空间间等等方方面面来来明明确

9、确系系统统和和环境等的边界条件。环境等的边界条件。(3)(3)确确定定构构成成系系统统功功能能的的最最小小单单位位，也也就就是是说说把把系系统统划划分分成成若若干干可可以以模模型型化化的的单单元元（或或子子系系统统），它它可可根根据据模型的使用目的来确定。模型的使用目的来确定。(4)(4)分分析析和和掌掌握握模模型型化化对对象象（单单元元或或子子系系统统）的的特特点点，主要因素和逻辑结构，最后建立模型。主要因素和逻辑结构，最后建立模型。(5)(5)应应用用最最优优化化理理论论和和系系统统控控制制理理论论，分分析析和和明明确确整整个个系统的特点，同时讨论适用的最优化方法。系统的特点，同时讨论适用

10、的最优化方法。四、四、系统的系统的最优最优化化 系系统统最最优优化化是是通通过过模模型型进进行行的的。图图1-41-4所所示示的的框框图图中中，表表示示了了系系统统最最优优化化的的一一般般步步骤骤，图图中中分分别别就就数数学学模模型型、图图象象模模型型等等表示了最优化过程。表示了最优化过程。上上述述最最优优化化方方法法的的具具体体内内容容将将在在第第二二章章至第六章中详细介绍。至第六章中详细介绍。五、五、系统的系统的评价评价 系统评价就是指从技术和经济等多个方系统评价就是指从技术和经济等多个方面对所设计的各个替代方案的最优解进行评面对所设计的各个替代方案的最优解进行评价，通过分析和评价，从中选

11、择在技术上是价，通过分析和评价，从中选择在技术上是先进的，在经济上是合理的方案作为最优系先进的，在经济上是合理的方案作为最优系统方案。统方案。对系统进行评价，首先必须确定评价基准，对系统进行评价，首先必须确定评价基准，即确定各种替代方案优先选用顺序的标准。即确定各种替代方案优先选用顺序的标准。评价基准一般根据系统的具体情况而定。评价基准一般根据系统的具体情况而定。五、五、系统的系统的评价评价例例如如，在在评评价价系系统统的的费费用用和和效效益益时时，评评价价基基准可以从下述三种基准中选用。即：准可以从下述三种基准中选用。即：（1 1）以以各各替替代代方方案案效效益益相相同同为为基基准准，选选择

12、择费费用最小的方案为最优方案。用最小的方案为最优方案。（2 2）以以各各方方案案费费用用相相同同为为基基准准，选选择择效效益益最最大的方案为最优方案。大的方案为最优方案。（3 3）以以效效益益费费用用比比为为基基准准，选选择择效效益益费费用用比比最最大大的的方方案案为为最最优优方方案案。进进行行系系统统的的经经济济评价时，必须考虑到时间价值的影响。评价时，必须考虑到时间价值的影响。六、六、系统系统决策分析决策分析 所所谓谓决决策策，就就是是根根据据客客观观可可能能性性，借借助助于于一一定定的的理理论论、方方法法和和工工具具，进进行行科科学学的的分分析析、正正确确的的计计算算和和判判断断后后的的

13、一一种种行行动动推推测。决策科学是现代科学管理的关键。测。决策科学是现代科学管理的关键。系系统统决决策策分分析析就就是是根根据据系系统统评评价价的的结结果果，对对多多个个系系统统方方案案进进行行抉抉择择。人人们们对对确确定定条条件件下下的的情情况况，是是容容易易作作出出直直接接判判断断、进进行行决决策策的的，但但对对含含随随机机性性条条件件及及不不确确定定条条件件的的情情况况，进进行行决决策策就就困困难难了了，必必须须借借助助于于决策理论，第八章中予以介绍。决策理论，第八章中予以介绍。第四章第四章 非线性规划非线性规划 预备知识预备知识 一维搜索一维搜索 无约束极值问题的解法无约束极值问题的解

14、法 有约束极值问题及求解有约束极值问题及求解（重点）（重点）在道路交通工程中的应用在道路交通工程中的应用 一、一般描述一、一般描述 目目标标函函数数或或约约束束条条件件出出现现非非线线性性函函数数时时，则则这这样样的的极极值值问问题题就就是是非非线线性性极极值值问问题题或或非线性规划。非线性规划。数学模型的一般形式如下：数学模型的一般形式如下：预备知识预备知识预备知识预备知识有时可写成：有时可写成：或或 二、极值问题二、极值问题预备知识预备知识1 1、局部最优解和全局最优解、局部最优解和全局最优解2 2、多元函数和导数、多元函数和导数(重点重点)3 3、极值点存在的条件（、极值点存在的条件（重

15、点重点）预备知识预备知识1 1、局部最优解和全局最优解、局部最优解和全局最优解定义定义1.1 1.1 可行点可行点 S S，若对每一个若对每一个，均有，均有 ，则称，则称 为非线性规划的为非线性规划的最优解或称为全局最优解或极小点。最优解或称为全局最优解或极小点。定义定义1.2 1.2 可行点可行点 S S，若存在若存在 的某个的某个 领域领域 使得对每个使得对每个 ，有，有 ，则，则称称 为非线性规划的局部最优解或局部为非线性规划的局部最优解或局部极小点。极小点。2 2、多元函数和导数、多元函数和导数（1 1）偏导数）偏导数（2 2）梯度）梯度（3 3）方向导数）方向导数（4 4）海森矩阵）

16、海森矩阵（5 5）正定矩阵）正定矩阵（6 6）多元函数的泰勒展开）多元函数的泰勒展开预备知识预备知识3 3、极值点存在的条件、极值点存在的条件 定理定理3.13.1（必要条件）（必要条件）定理定理3.23.2（充分条件）（充分条件）例：例：预备知识预备知识三、目标函数的凸性讨论三、目标函数的凸性讨论（1 1）凸集）凸集（2 2）凸组合）凸组合（3 3）顶点）顶点（4 4）凸函数与凹函数）凸函数与凹函数（5 5）凸函数的性质）凸函数的性质（6 6）函数凸性的判定定理）函数凸性的判定定理（7 7）凸函数的极值）凸函数的极值预备知识预备知识四、凸规划四、凸规划可行点、可行域可行点、可行域其中其中 、

17、为凸函数，此非线性规划为凸为凸函数，此非线性规划为凸规划规划 预备知识预备知识预备知识预备知识五、下降算法 下降迭代法的基本思想是：首先给出非线下降迭代法的基本思想是：首先给出非线性极值问题的最优解或局部最优解的一个初性极值问题的最优解或局部最优解的一个初 始估计始估计 （称为初始点），然后，通过某种（称为初始点），然后，通过某种 迭迭 代算法得到一系列的可行点代算法得到一系列的可行点 ，,，希望点列，希望点列 的极限就是非线性极的极限就是非线性极值问题的一个最优解或局部最优解值问题的一个最优解或局部最优解 。五、五、下降算法下降算法产生点列的方法产生点列的方法：若若从从 点点出出发发，沿沿任

18、任何何方方向向移移动动时时，在在S S中中都都不不存存在在可可行行点点使使目目标标函函数数值值下下降降，则则 是是非非线线性性极极值值问问题题的的一一个个局局部部最最优优解解，迭迭代代结结束束。若若从从 出出发发至至少少存存在在一一个个方方向向，在在S S中中沿沿此此方方向向可可以以使使目目标标函函数数值值有有所所下下降降，则则选选定定能能使使目目标标函函数数值值下下降降的的某某个个方方向向 ，然然后后沿沿此此方方向向移移动动适适当当的的一一步步，得得到下一个迭代点到下一个迭代点 ，即在射线即在射线 上选取一个新的可行点上选取一个新的可行点使使 五、五、下降算法下降算法产生点列的方法产生点列的

19、方法：其中其中 是一个向量，称为搜索方向，而是一个向量，称为搜索方向，而 是一个是一个实数，称为搜索步长或步长。当实数，称为搜索步长或步长。当 和和 确定以后，确定以后，由由 就可以唯一确定就可以唯一确定 ，这样可以产生目标函，这样可以产生目标函数值下降且逼近非线性极值问题的最优解和局部最数值下降且逼近非线性极值问题的最优解和局部最优解的序列优解的序列 ,这种算法称为下降迭代算法。这种算法称为下降迭代算法。五、五、下降算法下降算法下降迭代算法的一般步骤如下：下降迭代算法的一般步骤如下：（1 1）选择初始点）选择初始点 ;（2 2）确定搜索方向）确定搜索方向 。（3 3）确确定定后后，在在射射线

20、线 （00）上上选选取取一一适适当当的的步步长长 ，使使 ，如如此此确确定出下一个点定出下一个点 。（4 4）检检验验所所得得点点 是是否否为为极极小小点点，或或满满足足精精度度要要求求的的近近似似极极小小点点。若若满满足足，则则迭迭代代结结束束，否否则则继继续进行迭代。续进行迭代。五、五、下降算法下降算法迭代精度的确定迭代精度的确定：1.1.相继两次迭代的绝对误差：相继两次迭代的绝对误差：或或 2.2.相继两次迭代的相对误差：相继两次迭代的相对误差：或或 3.3.目标函数梯度的模：目标函数梯度的模：如如果果目目标标函函数数存存在在梯梯度度的的话话，可可以以根根据据目目标标函函数数在在最最近近

21、迭迭代代点点处处的的梯梯度度模模足足够够小小作作为为结结束束迭迭代代的的准则。即准则。即 一维搜索一维搜索 为为了了确确定定极极小小化化点点列列 ,在在每每次次迭迭代代时时要要沿沿确确定定的的搜搜索索方方向向 ,在在射射线线 上上，确确定一个适当的步长定一个适当的步长 ,使使 且且 。在在不不少少非非线线性性最最优优化化的的下下降降算算法法中中,步步长长 的的选选取取要要求求目目标标函函数数 在在点点 的的值下降最多，即步长值下降最多，即步长 满足满足也也就就是是求求一一元元函函数数 （）的的极极小小值值点点 。这这种种确确定定迭迭代代步步长长 的的方方法法称称为为精确一维搜索或简称一维搜索。

22、精确一维搜索或简称一维搜索。一维搜索一维搜索 精确一维搜索法精确一维搜索法(1)(1)牛顿法牛顿法(2)(2)抛物线法抛物线法 (3)(3)二分法二分法 (4)(4)“成功成功-失败失败”法法 (5)(5)FibonacciFibonacci法法(6)(6)黄金分割法黄金分割法 (7)(7)初始区间和初始点的确定初始区间和初始点的确定（进退算法（进退算法 ）不精确一维搜索法不精确一维搜索法 一维搜索一维搜索 (1)(1)直接法直接法 (2)(2)二次插值法二次插值法精确精确一维搜索一维搜索 (1)(1)牛顿法牛顿法牛顿法的基本思想是：用 在已知点 处的二阶Taylor展开式来近似代替 ,即 ，

23、然后用二次函数 的极小点 作为 的近似极小点，参见图3-1。精确精确一维搜索一维搜索 图3-1(1)(1)牛顿法牛顿法精确精确一维搜索一维搜索 由由 ,令令 ，得，得类似，若已知类似，若已知 ，则有，则有 进进行行迭迭代代计计算算，得得一一点点列列 ，这这种种求求一一元元函函数数 极极小小值值问问题题的的一一维维搜搜索索方方法法称称为为牛牛 顿顿法法。当当 时时，则则迭迭代代结结束束，为为 近似极小值点，即近似极小值点，即 。习题习题(1)(1)牛顿法牛顿法(一般公式一般公式)牛牛顿顿法法收收敛敛速速度度快快，但但是是它它对对函函数数要要求求二二次次可可微微，且且要要计计算算二二阶阶导导数数。

24、另另外外还还要要求求初初始始点点 选得好，否则可能得到的点列选得好，否则可能得到的点列 不收敛。不收敛。牛顿法产生的点列即使收敛，有时其极限也牛顿法产生的点列即使收敛，有时其极限也不一定是所要求的函数的极小值点，而只能不一定是所要求的函数的极小值点，而只能保证它是函数的驻点（一阶导数为保证它是函数的驻点（一阶导数为0 0的点）。的点）。驻点可能是极小值点，也可能是极大值点，驻点可能是极小值点，也可能是极大值点，也可能不是极值点。也可能不是极值点。精确精确一维搜索一维搜索(1)(1)牛顿法牛顿法(特点特点)精确精确一维搜索一维搜索 (2)(2)抛物线法抛物线法 牛顿法是用牛顿法是用 在点在点 的

25、二阶的二阶TaylorTaylor展开式展开式 来来 逼逼近近，即即利利用用点点 的的函函数数值值 及及其其一一阶阶、二二阶阶导导数数值值 、来来构构造造二二次次函函数数 ,而抛物线法则是利用而抛物线法则是利用 在三个点在三个点 ，处处的的函函数数值值来来构构造造二二次次函函数数 ，使使它满足它满足 设设 ，则则 。令令 ，得得即可求得的近似极小值点。即可求得的近似极小值点。上上式式就就是是 近近似似极极小小值值点点的的计计算算公公式式。为为求求出出近近似似极极小小值值点点 ，将将 代代入入方方程程组组，便便可可求得求得 、其中其中 其中其中 可得可得可得可得 将代入（将代入（4.84.8）或

26、利）或利 精确精确一维搜索一维搜索 (2)(2)抛物线法抛物线法(一般公式一般公式)精确精确一维搜索一维搜索(2)(2)抛物线法抛物线法(特点特点)抛物线法与牛顿法一样，它并不能保证算法一定收敛，即在迭代过程中可能出现上一次迭代点与下一次迭代点充分接近,但并不是的近似极小值点。抛物线法与牛顿法一样，它并不能保证算法一定收敛，即在迭代过程中可能出现上一次迭代点与下一次迭代点充分接近,但并不是的近似极小值点。抛物线法与牛顿法一样，它并不能保证抛物线法与牛顿法一样，它并不能保证算法一定收敛，即在迭代过程中可能出现上算法一定收敛，即在迭代过程中可能出现上一次迭代点一次迭代点 与下一次迭代点与下一次迭代

27、点 充分接近充分接近,但并不是但并不是 的近似极小值点。的近似极小值点。迭代过程迭代过程抛物线法求解步骤抛物线法求解步骤.doc.doc迭代过程迭代过程迭代过程迭代过程迭代过程迭代过程 精确精确一维搜索一维搜索 (3)(3)二分法二分法 若一区间若一区间 使使 且且 ，则在，则在 之间一定有一个之间一定有一个 的极小值点的极小值点 使得使得 取取 ,若若 ,则用区间则用区间 代替区间代替区间 ，再取，再取 ；若；若 ,则用则用 代替区间代替区间 ，再取，再取 ；。经过。经过 次迭代，设所得缩小的区间为次迭代，设所得缩小的区间为 。若。若 或或 时，则取极小值时，则取极小值。迭代结束，否则继续进

28、行迭代。迭代结束，否则继续进行迭代。精确精确一维搜索一维搜索 每步迭代的计算量比较小每步迭代的计算量比较小,程序简单，而程序简单，而且总能收敛于一个局部极小值点，但是收敛且总能收敛于一个局部极小值点，但是收敛较慢。较慢。对称取点，每次迭代缩减率相同。对称取点，每次迭代缩减率相同。习题习题(3)(3)二分法二分法（特点）（特点）精确精确一维搜索一维搜索 (4)“(4)“成功成功-失败失败”法法 是是一一种种启启发发式式算算法法。一一般般求求解解的的是是无无约约束束极极小化问题：小化问题：这里这里 表示整个实数域（表示整个实数域（）。）。如果遇到约束极小化问题如果遇到约束极小化问题则令则令 就等价

29、转化为函数就等价转化为函数 的无约束极小化问题。的无约束极小化问题。(一般为确定搜索区间而用一般为确定搜索区间而用)(4)“(4)“成功成功-失败失败”法迭代步法迭代步骤骤1 1任任意意取取定定一一初初始始点点 ，设设定定迭迭代代搜搜索索的的步长步长 及精度及精度 。2 2计算计算 及及 。3 3若若 ，则则称称此此步步向向前前搜搜索索成成功功，就就加加大大步步长长继继续续向向前前搜搜索索，即即用用 代代替替 ，用用步步长长 代替步长代替步长 ，继续向前搜索。继续向前搜索。若若 ，则则称称搜搜索索失失败败，向向后后搜搜索索 。首首先先看看是是否否？若若是是，则则极极小小值值点点取取 ,结结束束

30、；否否则则,用用 代代替替步步长长 ,返返回回2 2，继续进行搜索。，继续进行搜索。精确精确一维搜索一维搜索 考虑如下一维极小化问题考虑如下一维极小化问题其中其中 要求在要求在 是单峰凸函数。是单峰凸函数。思路：任取思路：任取 则则（1 1）若）若 ，则可将搜索区间缩小为，则可将搜索区间缩小为（2 2）若若 ，则可将搜索区间缩小为，则可将搜索区间缩小为 如此下去，最终必越来越逼近最优解如此下去，最终必越来越逼近最优解 (5)(5)FibonacciFibonacci法法 精确精确一维搜索一维搜索 F F法的基本思路：对称取点法的基本思路：对称取点考虑考虑00，11极小化问题极小化问题 （1 1

31、）选取两个初始点）选取两个初始点 、。（2 2）比较）比较 和和（3 3）进行下一次实验，重新选取）进行下一次实验，重新选取 和和（4 4）若满足，）若满足，则停止，否则返（则停止，否则返（3 3）若给定的区间不是若给定的区间不是00，11，而是，而是 ，则则给定的容许误差给定的容许误差 ，下同。，下同。(5)(5)FibonacciFibonacci法法 精确精确一维搜索一维搜索 F F法对称取点取法：法对称取点取法：考虑考虑 极小化问题极小化问题 选取两个初始点选取两个初始点 、，使，使 (5)(5)FibonacciFibonacci法法（1 1）由精度确定）由精度确定N N（2 2）计

32、算计算N N次函数值，可获得最小的最次函数值，可获得最小的最终区间终区间（3 3）适用于一般函数，在极小点附近效）适用于一般函数，在极小点附近效果好，精度较高，速度快果好，精度较高，速度快例：用例：用F F法求函数法求函数 的近似极小的近似极小点，要求缩短后的最终区间不大于原区点，要求缩短后的最终区间不大于原区间【间【-1-1，3 3】的】的8 8。(5)(5)FibonacciFibonacci法的特点法的特点 精确精确一维搜索一维搜索 精确精确一维搜索一维搜索 (6)(6)黄金分割法（黄金分割法（0.1680.168法）法）它是它是FibonacciFibonacci法一种简化方法。黄金分

33、割法法一种简化方法。黄金分割法是不用导数的一维搜索方法中比较常用的一是不用导数的一维搜索方法中比较常用的一种方法。种方法。考虑考虑 极小化问题极小化问题黄金分割法计算上面问题的极小值点的步骤黄金分割法计算上面问题的极小值点的步骤如下：如下：原始问题的变量 原始问题的松弛变量 精确精确一维搜索一维搜索 (6)(6)黄金分割法（黄金分割法（0.1680.168法）法）1 1：设定最后区间长度精度：设定最后区间长度精度 ，令，令 =0.618 =0.618。2 2：计算：计算 令令 。3 3：若：若 ，则结束，取极小值点则结束，取极小值点 （1/21/2）；否则，若；否则，若 ,则转则转4 4，否则

34、转，否则转5 5。原始问题的变量 原始问题的松弛变量 精确精确一维搜索一维搜索 (6)(6)黄金分割法（黄金分割法（0.1680.168法）法）4 4：令：令 ,再令再令 ，并计算，并计算 ,转转6 6。5 5：令：令 ，再令，再令 ，并计算，并计算 ,转转6 6。6 6：令：令 ,返回步骤返回步骤3 3。原始问题的变量 原始问题的松弛变量 精确精确一维搜索一维搜索 (6)(6)黄金分割法（黄金分割法（0.1680.168法）法）黄金分割法收敛速度是比较慢的，它的黄金分割法收敛速度是比较慢的，它的优点是不要求优点是不要求 可微，且每次迭代，只需可微，且每次迭代，只需计算一个函数值，因此，计算量

35、小，程序简计算一个函数值，因此，计算量小，程序简单。单。原始问题的变量 原始问题的松弛变量 精确精确一维搜索一维搜索 (7)(7)初始区间和初始点的确定初始区间和初始点的确定 一一般般求求解解一一维维极极小小化化问问题题时时，都都要要求求先先确确定定一一个个较较好好的的初初始始点点或或一一个个含含有有极极小小值值点点的的初初始始搜搜索索区区间间。为为此此，下下面面我我们们来来给给出出一一种种确确定定一一维维极极小小化化问问题题的的初初始始搜搜索索区区间间和和初初始始点的算法点的算法进退算法。进退算法。是是初初始始区区间间和和初初始始点点的的确确定定算算法法的的基基本本步步骤骤是是.doc.do

36、c 原始问题的变量 原始问题的松弛变量 不精确不精确一维搜索一维搜索 在实际计算中，一般做不到精确的一维在实际计算中，一般做不到精确的一维搜索，实际上，也没有必要做到这一点，因搜索，实际上，也没有必要做到这一点，因为精确的一维搜索需要付出较高的代价，而为精确的一维搜索需要付出较高的代价，而对加速收敛作用不太大，下面介绍两种较实对加速收敛作用不太大，下面介绍两种较实用的不精确一维搜索方法。用的不精确一维搜索方法。不精确不精确一维搜索一维搜索 (2)(2)二次插值法二次插值法 特点：不精确一维搜索的方法简单，而特点：不精确一维搜索的方法简单，而且有时收敛速度还比精确一维搜索方法快得且有时收敛速度还

37、比精确一维搜索方法快得多。多。(1)(1)直接法直接法 无约束极值问题的解法无约束极值问题的解法 一一般般求求解解无无约约束束极极值值问问题题的的算算法法基基本本上上都都是是下下降降算算法法。本本节节介介绍绍求求解解多多维维无无约约束束非非线线性规划问题性规划问题 比较常用有效的算法，包括最速下降法（梯比较常用有效的算法，包括最速下降法（梯度法）、牛顿法和阻尼牛顿法、共轭梯度法、度法）、牛顿法和阻尼牛顿法、共轭梯度法、变尺度法、直接搜索法等。变尺度法、直接搜索法等。(1)最速下降法最速下降法 (2)牛顿法牛顿法 (3)阻尼牛顿法阻尼牛顿法 (4)共轭梯度法共轭梯度法 (5)变尺度法变尺度法 (

38、6)直接搜索法直接搜索法 无约束极值问题的解法无约束极值问题的解法 无约束极值问题的解法无约束极值问题的解法 (1)最速下降法最速下降法最最速速下下降降法法，也也叫叫梯梯度度法法，是是人人们们用用来来求求多多变变量量函函数数的的极极值值问问题题的的最最早早的的一一种种方方法法。后后来来提提出出的的不不少少方方法法基基本本上上都都是是这这种种算算法法的的改改进算法。进算法。梯度法的基本思路梯度法的基本思路梯度法的迭代步骤梯度法的迭代步骤无约束极值问题的解法无约束极值问题的解法 最最速速下下降降法法其其实实并并不不是是一一种种非非常常理理想想的的求求解解非非线线性性极极值值问问题题的的算算法法，这

39、这是是因因为为当当用用最最速速下下降降法法迭迭代代趋趋近近极极小小点点时时，其其搜搜索索路路径径呈呈直直角角锯锯齿齿状状（相相邻邻两两次次的的搜搜索索方方向向互互相相垂垂直直）。在在迭迭代代开开始始时时下下降降比比较较快快，但但是是当当迭迭代代点点列接近极小点时收敛速度会很慢。列接近极小点时收敛速度会很慢。(1)最速下降法最速下降法无约束极值问题的解法无约束极值问题的解法 (2)牛顿法牛顿法 一维极值问题的牛顿法，它容易推广到一维极值问题的牛顿法，它容易推广到多维的情况，这个方法也是求解无约束极值多维的情况，这个方法也是求解无约束极值问题的最早算法之一。问题的最早算法之一。牛顿法的基本思想牛顿

40、法的基本思想 牛牛顿顿法的法的计计算步算步骤骤 牛牛顿顿法法的特点的特点无约束极值问题的解法无约束极值问题的解法 （3 3）阻尼牛顿法阻尼牛顿法 阻尼牛顿法的基本思想阻尼牛顿法的基本思想阻尼牛顿法的计算步骤阻尼牛顿法的计算步骤 阻尼牛顿法的特点：阻尼牛顿法的特点：阻尼牛顿法保持了牛顿法快速收敛的优阻尼牛顿法保持了牛顿法快速收敛的优点点,又不要求初点选得很好又不要求初点选得很好,因而在实际应用因而在实际应用中取得了较好的效果中取得了较好的效果,当然其迭代公式中也没当然其迭代公式中也没有避免要求海赛矩阵的逆阵。有避免要求海赛矩阵的逆阵。无约束极值问题的解法无约束极值问题的解法 (4)4)共轭梯度法

41、共轭梯度法 基本思想基本思想:最最速速下下降降法法,步步骤骤简简单单，但但收收敛敛速速度度太太慢慢，而而牛牛顿顿法法和和阻阻尼尼法法收收敛敛速速度度快快，但但要要计计算算二二阶阶偏偏导导数数矩矩阵阵及及其其逆逆阵阵，计计算算量量太太大大，共共轭轭梯梯度度法法兼兼有有这这两两种种方方法法的的优优点点，它它比比最最速速下下降降法法的的收收敛敛速速度度要要快快得得多多同同时时又又避避免免了了像像牛牛顿法所要求的海赛矩阵的计算，存贮和求逆。顿法所要求的海赛矩阵的计算，存贮和求逆。无约束极值问题的解法无约束极值问题的解法 (4)4)共轭梯度法共轭梯度法 共轭梯度法是以一种叫共轭方向作为迭共轭梯度法是以一

42、种叫共轭方向作为迭代的搜索方向的下降算法。代的搜索方向的下降算法。共轭方向概念共轭方向概念:共轭梯度法求解无约束二次规划思想共轭梯度法求解无约束二次规划思想共轭梯度法求解无约束二次规划步骤共轭梯度法求解无约束二次规划步骤共轭梯度法求解非线性无约束极值问题思想共轭梯度法求解非线性无约束极值问题思想求解非线性无约束极值问题步骤求解非线性无约束极值问题步骤无约束极值问题的解法无约束极值问题的解法 共轭梯度法共轭梯度法的特点：的特点：共轭梯度法对一般目标函数的无约束优化问共轭梯度法对一般目标函数的无约束优化问题的求解具有较高的效率，因此在无约束优题的求解具有较高的效率，因此在无约束优化算法中占有重要的

43、地位，是目前最常用的化算法中占有重要的地位，是目前最常用的方法之一，由于它的计算公式简单，存贮量方法之一，由于它的计算公式简单，存贮量少，可以用来求解比较大的问题。对于交通少，可以用来求解比较大的问题。对于交通系统规划中遇到的极值问题，这方法是效果系统规划中遇到的极值问题，这方法是效果较好的算法。较好的算法。(4)4)共轭梯度法共轭梯度法 无约束极值问题的解法无约束极值问题的解法 (5)5)变尺度法变尺度法变尺度法的基本思想变尺度法的基本思想变尺度法的变尺度法的计算步骤计算步骤无约束极值问题的解法无约束极值问题的解法 (5)5)变尺度法变尺度法变尺度法的特点：变尺度法的特点：变尺度法也是求解无

44、约束极值问题的一变尺度法也是求解无约束极值问题的一种有效算法。由于它既避免了计算二阶导数种有效算法。由于它既避免了计算二阶导数海赛矩阵及其求逆过程，又比梯度法的收敛海赛矩阵及其求逆过程，又比梯度法的收敛速度快，特别是对高维极值问题具有显著的速度快，特别是对高维极值问题具有显著的优越性优越性。有约束极值问题的解法有约束极值问题的解法 道道路路工工程程与与交交通通系系统统规规划划中中经经常常遇遇到到许许多多问问题题的的数数学学模模型型描描述述大大多多是是非非线线性性最最优优化化问问题题，变变量量和和约约束束条条件件一一般般比比较较多多，规规模模较较大大，所所以以约约束束非非线线性性最最优优化化方方

45、法法在在道道路路与与交交通通工工程程系统分析中极其重要。系统分析中极其重要。算算法法大大多多相相当当复复杂杂，没没有有一一种种对对一一切切有有约约束束极值问题的求解都普遍有效的算法极值问题的求解都普遍有效的算法。许许多多方方法法求求得得的的解解大大多多不不能能保保证证是是全全局局最最优优解，而只能是局部最优解。解，而只能是局部最优解。有约束极值问题的解法有约束极值问题的解法 解法思路：一般基本上的处理是将非线性约解法思路：一般基本上的处理是将非线性约束极值问题转化成无约束极值问题，例如惩束极值问题转化成无约束极值问题，例如惩罚函数法；将非线性极值问题转化成线性规罚函数法；将非线性极值问题转化成

46、线性规划问题或用二次规划来逐次逼近，将复杂的划问题或用二次规划来逐次逼近，将复杂的约束问题转化成简单问题来处理约束问题转化成简单问题来处理 有约束极值问题的解法有约束极值问题的解法 解的最优性条件解的最优性条件：紧约束、紧约束指标集的定义紧约束、紧约束指标集的定义 定理：定理：最优性的一阶必要条件最优性的一阶必要条件 定理：定理：最优性的充分条件最优性的充分条件 例例 有约束极值问题的解法有约束极值问题的解法 广义拉格朗日乘子法：（如前述）广义拉格朗日乘子法：（如前述）惩罚函数法：惩罚函数法：惩惩罚罚函函数数法法是是求求解解约约束束极极值值问问题题一一种种重重要要而而常常用用方方法法。通通过过

47、将将约约束束极极值值问问题题转转化化成成一一系系列列无无约约束束极极值值问问题题来来求求解解的的，所所以以称称为为序序列列无无约约束束极极小小化化技技术术，或或称称SUMT法法。惩惩罚罚函函数数法法是是序序列列无无约约束束极极小小化化技技术术之之一一，又又称称其其为为SUMT外点法。外点法。有约束极值问题的解法有约束极值问题的解法 惩罚函数法构造思路：惩罚函数法构造思路：惩罚函数法的计算步骤：惩罚函数法的计算步骤：例例：有约束极值问题的解法有约束极值问题的解法 碰壁函数法碰壁函数法:碰碰壁壁函函数数法法跟跟惩惩罚罚函函数数法法一一样样，也也是是将将约约束束极极值值问问题题转转化化无无约约束束极

48、极值值问问题题，也也是是属属于于序序列列无无约约束束极极小小化化技技术术，它它要要求求约约束束极极值值问问题题的的可可行行约约束束集集连连通通且且内内部部非非空空，所所以以有有别别于于SUMT外点法，外点法，称其为称其为SUMT内点法。内点法。碰碰壁壁函函数数法法要要求求约约束束极极值值问问题题的的可可行行集集S连连通通且且内内部部intS非非空空，所所以以可可行行集集中中没没有有等等式式约约束束 有约束极值问题的解法有约束极值问题的解法 碰壁函数碰壁函数法法构造思路构造思路：碰壁函数碰壁函数法的计算步骤法的计算步骤：有约束极值问题的解法有约束极值问题的解法可行方向法可行方向法:动态规划的基本

49、原理动态规划的基本原理 最短路径问题最短路径问题资源分配问题资源分配问题 一般数学规划问题一般数学规划问题第四章第四章 动态动态规划规划 动态规划的基本原理动态规划的基本原理概述：概述：动态规划是运筹学的一个分支，它是解决多阶动态规划是运筹学的一个分支，它是解决多阶段决策过程最优化的一种数学方法。所谓多阶段决策过程最优化的一种数学方法。所谓多阶段决策过程是指这样一类决策过程：它可以分段决策过程是指这样一类决策过程：它可以分为若干个互相联系的阶段，在每一阶段分别对为若干个互相联系的阶段，在每一阶段分别对应着一组可以选取的决策，在每一阶段都需要应着一组可以选取的决策，在每一阶段都需要作出决策，从而

50、使整个过程达到最好的效果。作出决策，从而使整个过程达到最好的效果。当各个阶段决策确定后，就构成了一个决策序当各个阶段决策确定后，就构成了一个决策序列，称为一个策略。列，称为一个策略。动态规划问题的解题思路动态规划问题的解题思路:是将一个是将一个n n 阶段的决策问题转化为依次求解阶段的决策问题转化为依次求解n n 个具有递推关系的单阶段的决策问题，从而个具有递推关系的单阶段的决策问题，从而简化计算过程。这种转化的实现是从终点简化计算过程。这种转化的实现是从终点E E 出发一步步进行反推，这种算法称为逆序算出发一步步进行反推，这种算法称为逆序算法。法。动态规划的基本概念和方法动态规划的基本概念和