道路与交通系统分析精选文档.ppt

《道路与交通系统分析精选文档.ppt》由会员分享，可在线阅读，更多相关《道路与交通系统分析精选文档.ppt（135页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、道路与交通系统分析课件本讲稿第一页，共一百三十五页第一章 引论系统与系统工程系统与系统工程系统分析系统分析 主要内容和重点：主要内容和重点：系统的概念、特性与形态、系统工程方法论系统的概念、特性与形态、系统工程方法论的基本特点、系统分析的基本概念、系统分析的基本特点、系统分析的基本概念、系统分析的步骤的步骤 、系统的模型化、系统的模型化 、系统的最优化、系统的最优化 、系、系统评价统评价 、系统决策分析、系统决策分析 第一章第一章 系统工程与系统分系统工程与系统分析基本概念析基本概念 本讲稿第二页，共一百三十五页系统与系统工程系统与系统工程一、一、系统的概念、特性与形态系统的概念、特性与形态

2、所谓系统，是指由相互作用、相互依赖而又能所谓系统，是指由相互作用、相互依赖而又能相互区别的若干组成部分（单元）组合而成的，具相互区别的若干组成部分（单元）组合而成的，具有特定功能的有机整体。有特定功能的有机整体。系统四个特征：系统四个特征：整体性整体性相关性相关性目的性目的性环境适应性环境适应性本讲稿第三页，共一百三十五页一、一、系统的概念、特性与形态系统的概念、特性与形态系统形态可分为以下几类系统形态可分为以下几类：自然系统与人造系统自然系统与人造系统实体系统与概念系统实体系统与概念系统动态系统与静态系统动态系统与静态系统控制系统与行为系统控制系统与行为系统本讲稿第四页，共一百三十五页二、系

3、统工程二、系统工程 系统工程方法论的基本特点可归纳如下：系统工程方法论的基本特点可归纳如下：(1)研究方法上的整体性研究方法上的整体性(2)应用技术上的综合性应用技术上的综合性(3)处理问题上的科学性处理问题上的科学性按时间顺序可分为下述三个阶段：按时间顺序可分为下述三个阶段：系统规划阶段系统规划阶段(2)系统设计阶段系统设计阶段(3)系统制造和运行阶段系统制造和运行阶段本讲稿第五页，共一百三十五页问题的提出问题的提出系统计划系统计划概略设计概略设计目标的确定目标的确定具体条件的确定具体条件的确定系统分析系统分析方案确定方案确定详细设计详细设计试试 制制制制 造造运运 行行系系统统规规划划系系

4、统统设设计计系系统统制制造造与与运运行行构构思思 计计划划分分析析 设设计计改改进进 运运行行图图1 1 系统建立流程图系统建立流程图 本讲稿第六页，共一百三十五页 把把上上述述系系统统工工程程的的基基本本处处理理方方法法具具体体化化，那那就就是是在在系系统统工工程程中中最最常常使使用用的的系系统统分分析析、系系统统设设计计方方法法。这这种种方方法法不不但但用用于于系系统统设设计计阶阶段段，还还可可用用于于系系统统规规划划阶阶段段及及系系统统制制造造与与运运行行阶阶段段，以以求求得得系系统统的的合合理理规规划划、系系统统的的最最优优制制造造方方法法及系统的最优运行方式。及系统的最优运行方式。(

5、1)(1)系统分析；系统分析；(2)(2)系统设计；系统设计；(3)(3)系统的综合评价系统的综合评价。该方法大致可分为下列三个步骤该方法大致可分为下列三个步骤：本讲稿第七页，共一百三十五页分分 析析综综 合合评评 价价系统的要求系统的要求系统的设计系统的设计 图图2系统工程基本处理方法框图系统工程基本处理方法框图 本讲稿第八页，共一百三十五页系统分析系统分析一、系统分析的基本概念一、系统分析的基本概念 系系统统分分析析的的目目的的：通通过过分分析析比比较较各各种种替替代代方方案案的的费费用用、效效益益、功功能能和和可可靠靠性性等等各各项项技技术术经经济济指指标标，得得出出决决策策者者决决策策

6、所所必必须须的的资资料料和和信信息息，以便最后获得最优系统方案。图以便最后获得最优系统方案。图3表示。表示。系统问题系统问题系统分析系统分析最优系统方案最优系统方案 图图3系统分析的目的系统分析的目的本讲稿第九页，共一百三十五页系统分析可概括为以下几个步骤：系统分析可概括为以下几个步骤：(1)系统目的的分析和确定系统目的的分析和确定(2)系统模型化系统模型化(3)系统最优化系统最优化(4)对解的评价对解的评价具体的步骤流程如教本具体的步骤流程如教本P8图图1-4。一、系统分析的基本概念一、系统分析的基本概念 本讲稿第十页，共一百三十五页二、二、系统目的的分析与确定系统目的的分析与确定(1)(1

7、)对象系统的定义对象系统的定义(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、方案的最优解进行评价，对所设计的各个替代方案的最优解进行评价，通过分析和评价，从中选择在技术上是先进的，通过分析和评价，从中选择在技术上是先进的，在经济上是合理的方案作为最优系统方案。在经济上是合理的方案作为最优系统方案。对系统进行评价，首先必须确定评价基准，对系统进行评价，首先必须确定评价基准，即确定各种替代方案优先选用顺序的标准。评即确定各种替代方案优先选用顺序的标准。评价基准一般根据系统的具体情况而定。价基准一般根据系统的具体情况而定。本讲稿第十五页，共一百三十五页五、系统的评价五、系统的评价例例如如，在在评评价价系系统统的的费费用用和和效效益益时时，评评价价基基准准可以从下述三种基准中

12、选用。即：可以从下述三种基准中选用。即：（1 1）以以各各替替代代方方案案效效益益相相同同为为基基准准，选选择择费费用用最最小的方案为最优方案。小的方案为最优方案。（2 2）以以各各方方案案费费用用相相同同为为基基准准，选选择择效效益益最最大大的的方案为最优方案。方案为最优方案。（3 3）以以效效益益费费用用比比为为基基准准，选选择择效效益益费费用用比比最最大大的的方方案案为为最最优优方方案案。进进行行系系统统的的经经济济评评价价时，必须考虑到时间价值的影响。时，必须考虑到时间价值的影响。本讲稿第十六页，共一百三十五页六、系统决策分析六、系统决策分析 所所谓谓决决策策，就就是是根根据据客客观观

13、可可能能性性，借借助助于于一一定定的的理理论论、方方法法和和工工具具，进进行行科科学学的的分分析析、正正确确的的计计算算和和判判断断后后的的一一种种行行动动推推测测。决决策策科科学学是现代科学管理的关键。是现代科学管理的关键。系系统统决决策策分分析析就就是是根根据据系系统统评评价价的的结结果果，对对多多个个系系统统方方案案进进行行抉抉择择。人人们们对对确确定定条条件件下下的的情情况况，是是容容易易作作出出直直接接判判断断、进进行行决决策策的的，但但对对含含随随机机性性条条件件及及不不确确定定条条件件的的情情况况，进进行行决决策策就就困困难难了了，必必须须借借助助于于决决策策理理论论，第八章中予

14、以介绍。第八章中予以介绍。本讲稿第十七页，共一百三十五页第四章第四章 非线性规划非线性规划 预备知识预备知识一维搜索一维搜索无约束极值问题的解法无约束极值问题的解法有约束极值问题及求解（重点）有约束极值问题及求解（重点）在道路交通工程中的应用在道路交通工程中的应用 本讲稿第十八页，共一百三十五页一、一般描述一、一般描述目目标标函函数数或或约约束束条条件件出出现现非非线线性性函函数数时时，则则这这样样的的极极值值问问题题就就是是非非线线性性极极值值问问题题或或非非线线性性规划。规划。数学模型的一般形式如下：数学模型的一般形式如下：预备知识预备知识本讲稿第十九页，共一百三十五页预备知识预备知识有时

15、可写成：有时可写成：或或 本讲稿第二十页，共一百三十五页二、极值问题二、极值问题预备知识预备知识1 1、局部最优解和全局最优解、局部最优解和全局最优解2 2、多元函数和导数、多元函数和导数(重点重点)3 3、极值点存在的条件（、极值点存在的条件（重点重点）本讲稿第二十一页，共一百三十五页预备知识预备知识1 1、局部最优解和全局最优解、局部最优解和全局最优解定义定义1.1 1.1 可行点可行点 S S，若对每一个若对每一个，均有，均有 ，则称，则称 为非线性规划的为非线性规划的最优解或称为全局最优解或极小点。最优解或称为全局最优解或极小点。定义定义1.2 1.2 可行点可行点 S S，若存在若存

16、在 的某个的某个 领域领域 使得对每个使得对每个 ，有，有 ，则，则称称 为非线性规划的局部最优解或局部为非线性规划的局部最优解或局部极小点。极小点。本讲稿第二十二页，共一百三十五页2 2、多元函数和导数、多元函数和导数（1 1）偏导数）偏导数（2 2）梯度）梯度（3 3）方向导数）方向导数（4 4）海森矩阵）海森矩阵（5 5）正定矩阵）正定矩阵（6 6）多元函数的泰勒展开）多元函数的泰勒展开预备知识预备知识本讲稿第二十三页，共一百三十五页3 3、极值点存在的条件、极值点存在的条件 定理定理3.13.1（必要条件）（必要条件）定理定理3.23.2（充分条件）（充分条件）例：例：预备知识预备知识

17、本讲稿第二十四页，共一百三十五页三、目标函数的凸性讨论三、目标函数的凸性讨论（1 1）凸集）凸集（2 2）凸组合）凸组合（3 3）顶点）顶点（4 4）凸函数与凹函数）凸函数与凹函数（5 5）凸函数的性质）凸函数的性质（6 6）函数凸性的判定定理）函数凸性的判定定理（7 7）凸函数的极值）凸函数的极值预备知识预备知识本讲稿第二十五页，共一百三十五页四、凸规划四、凸规划可行点、可行域可行点、可行域其中其中 、为凸函数，此非线性规划为凸规划为凸函数，此非线性规划为凸规划 预备知识预备知识本讲稿第二十六页，共一百三十五页预备知识预备知识五、下降算法 下降迭代法的基本思想是：首先给出非线性下降迭代法的基

18、本思想是：首先给出非线性极值问题的最优解或局部最优解的一个初极值问题的最优解或局部最优解的一个初 始估始估计计 （称为初始点），然后，通过某种（称为初始点），然后，通过某种 迭迭 代算法得到一系列的可行点代算法得到一系列的可行点 ，,，希望点列，希望点列 的极限就是非线性极值问题的极限就是非线性极值问题的一个最优解或局部最优解的一个最优解或局部最优解 。本讲稿第二十七页，共一百三十五页五、下降算法五、下降算法产生点列的方法产生点列的方法：若若从从 点点出出发发，沿沿任任何何方方向向移移动动时时，在在S S中中都都不不存存在在可可行行点点使使目目标标函函数数值值下下降降，则则 是是非非线线性性极

19、极值值问问题题的的一一个个局局部部最最优优解解，迭迭代代结结束束。若若从从 出出发发至至少少存存在在一一个个方方向向，在在S S中中沿沿此此方方向向可可以以使使目目标标函函数数值值有有所所下下降降，则则选选定定能能使使目目标标函函数数值值下下降降的的某某个个方方向向 ，然然后后沿沿此此方方向向移移动动适适当当的的一一步步，得得到到下下一一个个迭迭代代点点 ，即在射线即在射线 上选取一个新的可行点上选取一个新的可行点使使 本讲稿第二十八页，共一百三十五页五、下降算法五、下降算法产生点列的方法产生点列的方法：其中其中 是一个向量，称为搜索方向，而是一个向量，称为搜索方向，而 是一个实是一个实数，称

20、为搜索步长或步长。当数，称为搜索步长或步长。当 和和 确定以后，由确定以后，由 就可以唯一确定就可以唯一确定 ，这样可以产生目标函数值下降，这样可以产生目标函数值下降且逼近非线性极值问题的最优解和局部最优解的序列且逼近非线性极值问题的最优解和局部最优解的序列 ,这种算法称为下降迭代算法。这种算法称为下降迭代算法。本讲稿第二十九页，共一百三十五页五、下降算法五、下降算法下降迭代算法的一般步骤如下：下降迭代算法的一般步骤如下：（1 1）选择初始点）选择初始点 ;（2 2）确定搜索方向）确定搜索方向 。（3 3）确确定定后后，在在射射线线 （00）上上选选取取一一适适当当的的步步长长 ，使使 ，如如

21、此此确确定出下一个点定出下一个点 。（4 4）检检验验所所得得点点 是是否否为为极极小小点点，或或满满足足精精度度要要求求的的近近似似极极小小点点。若若满满足足，则则迭迭代代结结束束，否否则则继继续进行迭代。续进行迭代。本讲稿第三十页，共一百三十五页五、下降算法五、下降算法迭代精度的确定迭代精度的确定：1.1.相继两次迭代的绝对误差：相继两次迭代的绝对误差：或或 2.2.相继两次迭代的相对误差：相继两次迭代的相对误差：或或 3.3.目标函数梯度的模：目标函数梯度的模：如如果果目目标标函函数数存存在在梯梯度度的的话话，可可以以根根据据目目标标函函数数在在最近迭代点处的梯度模足够小作为结束迭代的准

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

23、一维搜索或简称一维搜索。本讲稿第三十二页，共一百三十五页一维搜索一维搜索精确一维搜索法精确一维搜索法(1)(1)牛顿法牛顿法(2)(2)抛物线法抛物线法 (3)(3)二分法二分法 (4)(4)“成功成功-失败失败”法法 (5)(5)FibonacciFibonacci法法(6)(6)黄金分割法黄金分割法 (7)(7)初始区间和初始点的确定（进退算法初始区间和初始点的确定（进退算法 ）本讲稿第三十三页，共一百三十五页不精确一维搜索法不精确一维搜索法 一维搜索一维搜索 (1)(1)直接法直接法 (2)(2)二次插值法二次插值法本讲稿第三十四页，共一百三十五页精确精确一维搜索一维搜索 (1)(1)牛

24、顿法牛顿法牛顿法的基本思想是：用 在已知点 处的二阶Taylor展开式来近似代替 ,即 ，然后用二次函数 的极小点 作为 的近似极小点，参见图3-1。本讲稿第三十五页，共一百三十五页精确精确一维搜索一维搜索图3-1(1)(1)牛顿法牛顿法本讲稿第三十六页，共一百三十五页精确精确一维搜索一维搜索由由 ,令令 ，得，得类似，若已知类似，若已知 ，则有，则有 进进行行迭迭代代计计算算，得得一一点点列列 ，这这种种求求一一元元函函数数 极极小小值值问问题题的的一一维维搜搜索索方方法法称称为为牛牛 顿顿法法。当当 时时，则则迭迭代代结结束束，为为 近似极小值点，即近似极小值点，即 。习题习题(1)(1)

25、牛顿法牛顿法(一般公式一般公式)本讲稿第三十七页，共一百三十五页牛牛顿顿法法收收敛敛速速度度快快，但但是是它它对对函函数数要要求求二二次次可可微微，且且要要计计算算二二阶阶导导数数。另另外外还还要要求求初初始始点点 选选得得好好，否则可能得到的点列否则可能得到的点列 不收敛。不收敛。牛顿法产生的点列即使收敛，有时其极限也不一牛顿法产生的点列即使收敛，有时其极限也不一定是所要求的函数的极小值点，而只能保证它是定是所要求的函数的极小值点，而只能保证它是函数的驻点（一阶导数为函数的驻点（一阶导数为0 0的点）。驻点可能是极的点）。驻点可能是极小值点，也可能是极大值点，也可能不是极值点。小值点，也可能

26、是极大值点，也可能不是极值点。精确精确一维搜索一维搜索(1)(1)牛顿法牛顿法(特点特点)本讲稿第三十八页，共一百三十五页 精确精确一维搜索一维搜索 (2)(2)抛物线法抛物线法 牛顿法是用牛顿法是用 在点在点 的二阶的二阶TaylorTaylor展开式展开式 来来 逼逼近近，即即利利用用点点 的的函函数数值值 及及其其一一阶阶、二二阶阶导导数数值值 、来来构构造造二二次次函函数数 ,而抛物线法则是利用而抛物线法则是利用 在三个点在三个点 ，处处的的函函数数值值来来构构造造二二次次函函数数 ，使使它它满足满足 本讲稿第三十九页，共一百三十五页设设 ，则则 。令令 ，得得即即可求得的近似极小值点

27、。可求得的近似极小值点。上上式式就就是是 近近似似极极小小值值点点的的计计算算公公式式。为为求求出出近近似似极极小小值值点点 ，将将 代代入入方方程程组组，便便可可求得求得 、其中其中 其中其中 可得可得可得可得 将代入（将代入（4.84.8）或利）或利 精确精确一维搜索一维搜索 (2)(2)抛物线法抛物线法(一般公式一般公式)本讲稿第四十页，共一百三十五页 精确精确一维搜索一维搜索(2)(2)抛物线法抛物线法(特点特点)抛物线法与牛顿法一样，它并不能保证算法一定收敛，即在迭代过程中可能出现上一次迭代点与下一次迭代点充分接近,但并不是的近似极小值点。抛物线法与牛顿法一样，它并不能保证算法一定收

28、敛，即在迭代过程中可能出现上一次迭代点与下一次迭代点充分接近,但并不是的近似极小值点。抛物线法与牛顿法一样，它并不能保证抛物线法与牛顿法一样，它并不能保证算法一定收敛，即在迭代过程中可能出现上算法一定收敛，即在迭代过程中可能出现上一次迭代点一次迭代点 与下一次迭代点与下一次迭代点 充分接近充分接近,但并不是但并不是 的近似极小值点。的近似极小值点。迭代过程迭代过程抛物线法求解步骤抛物线法求解步骤.doc.doc迭代过程迭代过程迭代过程迭代过程迭代过程迭代过程 本讲稿第四十一页，共一百三十五页 精确精确一维搜索一维搜索 (3)(3)二分法二分法 若一区间若一区间 使使 且且 ，则在，则在 之间之

29、间一定有一个一定有一个 的极小值点的极小值点 使得使得 取取 ,若若 ,则用区间则用区间 代替区间代替区间 ，再取，再取 ；若；若 ,则用则用 代代替区间替区间 ，再取，再取 ；。经过。经过 次迭次迭代，设所得缩小的区间为代，设所得缩小的区间为 。若。若 或或 时，则取极小值时，则取极小值。迭代结束，否则继续进行迭代。迭代结束，否则继续进行迭代。本讲稿第四十二页，共一百三十五页 精确精确一维搜索一维搜索 每步迭代的计算量比较小每步迭代的计算量比较小,程序简单，而且总能程序简单，而且总能收敛于一个局部极小值点，但是收敛较慢。收敛于一个局部极小值点，但是收敛较慢。对称取点，每次迭代缩减率相同。对称

30、取点，每次迭代缩减率相同。习题习题(3)(3)二分法（特点）二分法（特点）本讲稿第四十三页，共一百三十五页 精确精确一维搜索一维搜索 (4)(4)“成功成功-失败失败”法法 是是一一种种启启发发式式算算法法。一一般般求求解解的的是是无无约约束束极极小化问题：小化问题：这里这里 表示整个实数域（表示整个实数域（）。）。如果遇到约束极小化问题如果遇到约束极小化问题则令则令 就等价转化为函数就等价转化为函数 的无约束极小化问题。的无约束极小化问题。(一般为确定搜索区间而用一般为确定搜索区间而用)本讲稿第四十四页，共一百三十五页 (4)(4)“成功成功-失败失败”法迭代步骤法迭代步骤1 1任任意意取取

31、定定一一初初始始点点 ，设设定定迭迭代代搜搜索索的的步长步长 及精度及精度 。2 2计算计算 及及 。3 3若若 ，则则称称此此步步向向前前搜搜索索成成功功，就就加加大大步步长长继继续续向向前前搜搜索索，即即用用 代代替替 ，用用步步长长 代代替替步长步长 ，继续向前搜索。继续向前搜索。若若 ，则则称称搜搜索索失失败败，向向后后搜搜索索 。首首先先看看是是否否？若若是是，则则极极小小值值点点取取 ,结结束束；否否则则,用用 代代替替步步长长 ,返返回回2 2，继继续续进进行行搜搜索。索。本讲稿第四十五页，共一百三十五页 精确精确一维搜索一维搜索考虑如下一维极小化问题考虑如下一维极小化问题其中其

32、中 要求在要求在 是单峰凸函数。是单峰凸函数。思路：任取思路：任取 则则（1 1）若）若 ，则可将搜索区间缩小为，则可将搜索区间缩小为（2 2）若若 ，则可将搜索区间缩小为，则可将搜索区间缩小为 如此下去，最终必越来越逼近最优解如此下去，最终必越来越逼近最优解 (5)(5)FibonacciFibonacci法法 本讲稿第四十六页，共一百三十五页 精确精确一维搜索一维搜索F F法的基本思路：对称取点法的基本思路：对称取点考虑考虑00，11极小化问题极小化问题 （1 1）选取两个初始点）选取两个初始点 、。（2 2）比较）比较 和和（3 3）进行下一次实验，重新选取）进行下一次实验，重新选取 和

33、和（4 4）若满足，）若满足，则停止，否则返（则停止，否则返（3 3）若给定的区间不是若给定的区间不是00，11，而是，而是 ，则给则给定的容许误差定的容许误差 ，下同。，下同。(5)(5)FibonacciFibonacci法法 本讲稿第四十七页，共一百三十五页 精确精确一维搜索一维搜索F F法对称取点取法：法对称取点取法：考虑考虑 极小化问题极小化问题 选取两个初始点选取两个初始点 、，使，使 (5)(5)FibonacciFibonacci法法 本讲稿第四十八页，共一百三十五页（1 1）由精度确定）由精度确定N N（2 2）计算计算N N次函数值，可获得最小的最终次函数值，可获得最小的最

34、终区间区间（3 3）适用于一般函数，在极小点附近效）适用于一般函数，在极小点附近效果好，精度较高，速度快果好，精度较高，速度快例：用例：用F F法求函数法求函数 的近似极小的近似极小点，要求缩短后的最终区间不大于原区间点，要求缩短后的最终区间不大于原区间【-1-1，3 3】的】的8 8。(5)(5)FibonacciFibonacci法的特点法的特点 精确精确一维搜索一维搜索本讲稿第四十九页，共一百三十五页 精确精确一维搜索一维搜索 (6)(6)黄金分割法（黄金分割法（0.1680.168法）法）它是它是FibonacciFibonacci法一种简化方法。黄金分割法是法一种简化方法。黄金分割法

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

36、转否则转5 5。本讲稿第五十一页，共一百三十五页 原始问题的变量 原始问题的松弛变量 精确精确一维搜索一维搜索 (6)(6)黄金分割法（黄金分割法（0.1680.168法）法）4 4：令：令 ,再令再令 ，并计算，并计算 ,转转6 6。5 5：令：令 ，再令，再令 ，并计算，并计算 ,转转6 6。6 6：令：令 ,返回步骤返回步骤3 3。本讲稿第五十二页，共一百三十五页 原始问题的变量 原始问题的松弛变量 精确精确一维搜索一维搜索 (6)(6)黄金分割法（黄金分割法（0.1680.168法）法）黄金分割法收敛速度是比较慢的，它的优点黄金分割法收敛速度是比较慢的，它的优点是不要求是不要求 可微，

37、且每次迭代，只需计算一可微，且每次迭代，只需计算一个函数值，因此，计算量小，程序简单。个函数值，因此，计算量小，程序简单。本讲稿第五十三页，共一百三十五页 原始问题的变量 原始问题的松弛变量 精确精确一维搜索一维搜索 (7)(7)初始区间和初始点的确定初始区间和初始点的确定 一一般般求求解解一一维维极极小小化化问问题题时时，都都要要求求先先确确定定一一个个较较好好的的初初始始点点或或一一个个含含有有极极小小值值点点的的初初始始搜搜索索区区间间。为为此此，下下面面我我们们来来给给出出一一种种确确定定一一维维极极小小化化问问题题的的初初始始搜搜索索区区间间和和初初始始点点的的算算法法进进退算法。退

38、算法。是是初初始始区区间间和和初初始始点点的的确确定定算算法法的的基基本本步步骤骤是是.doc.doc本讲稿第五十四页，共一百三十五页 原始问题的变量 原始问题的松弛变量 不精确不精确一维搜索一维搜索在实际计算中，一般做不到精确的一维搜索，在实际计算中，一般做不到精确的一维搜索，实际上，也没有必要做到这一点，因为精确的一实际上，也没有必要做到这一点，因为精确的一维搜索需要付出较高的代价，而对加速收敛作用维搜索需要付出较高的代价，而对加速收敛作用不太大，下面介绍两种较实用的不精确一维搜索不太大，下面介绍两种较实用的不精确一维搜索方法。方法。本讲稿第五十五页，共一百三十五页 不精确不精确一维搜索一

39、维搜索(2)(2)二次插值法二次插值法 特点：不精确一维搜索的方法简单，而且有特点：不精确一维搜索的方法简单，而且有时收敛速度还比精确一维搜索方法快得多。时收敛速度还比精确一维搜索方法快得多。(1)(1)直接法直接法 本讲稿第五十六页，共一百三十五页无约束极值问题的解法无约束极值问题的解法 一一般般求求解解无无约约束束极极值值问问题题的的算算法法基基本本上上都都是是下下降降算算法法。本本节节介介绍绍求求解解多多维维无无约约束束非非线线性性规规划划问问题题 比较常用有效的算法，包括最速下降法（梯度比较常用有效的算法，包括最速下降法（梯度法）、牛顿法和阻尼牛顿法、共轭梯度法、变法）、牛顿法和阻尼牛

40、顿法、共轭梯度法、变尺度法、直接搜索法等。尺度法、直接搜索法等。本讲稿第五十七页，共一百三十五页(1)最速下降法最速下降法(2)牛顿法牛顿法(3)阻尼牛顿法阻尼牛顿法(4)共轭梯度法共轭梯度法(5)变尺度法变尺度法(6)直接搜索法直接搜索法 无约束极值问题的解法无约束极值问题的解法 本讲稿第五十八页，共一百三十五页无约束极值问题的解法无约束极值问题的解法 (1)最速下降法最速下降法最最速速下下降降法法，也也叫叫梯梯度度法法，是是人人们们用用来来求求多多变变量量函函数数的的极极值值问问题题的的最最早早的的一一种种方方法法。后后来来提提出的不少方法基本上都是这种算法的改进算法。出的不少方法基本上都

41、是这种算法的改进算法。梯度法的基本思路梯度法的基本思路梯度法的迭代步骤梯度法的迭代步骤本讲稿第五十九页，共一百三十五页无约束极值问题的解法无约束极值问题的解法 最最速速下下降降法法其其实实并并不不是是一一种种非非常常理理想想的的求求解解非非线线性性极极值值问问题题的的算算法法，这这是是因因为为当当用用最最速速下下降降法法迭迭代代趋趋近近极极小小点点时时，其其搜搜索索路路径径呈呈直直角角锯锯齿齿状状（相相邻邻两两次次的的搜搜索索方方向向互互相相垂垂直直）。在在迭迭代代开开始始时时下下降降比比较较快快，但但是是当当迭迭代代点点列列接接近近极极小点时收敛速度会很慢。小点时收敛速度会很慢。(1)最速下

42、降法最速下降法本讲稿第六十页，共一百三十五页无约束极值问题的解法无约束极值问题的解法 (2)牛顿法牛顿法 一维极值问题的牛顿法，它容易推广到多一维极值问题的牛顿法，它容易推广到多维的情况，这个方法也是求解无约束极值问题维的情况，这个方法也是求解无约束极值问题的最早算法之一。的最早算法之一。牛顿法的基本思想牛顿法的基本思想 牛顿法的计算步骤牛顿法的计算步骤 牛顿法牛顿法的特点的特点本讲稿第六十一页，共一百三十五页无约束极值问题的解法无约束极值问题的解法 （3 3）阻尼牛顿法阻尼牛顿法 阻尼牛顿法的基本思想阻尼牛顿法的基本思想阻尼牛顿法的计算步骤阻尼牛顿法的计算步骤阻尼牛顿法的特点：阻尼牛顿法的特

43、点：阻尼牛顿法保持了牛顿法快速收敛的优点阻尼牛顿法保持了牛顿法快速收敛的优点,又不要求初点选得很好又不要求初点选得很好,因而在实际应用中取得了因而在实际应用中取得了较好的效果较好的效果,当然其迭代公式中也没有避免要求海当然其迭代公式中也没有避免要求海赛矩阵的逆阵。赛矩阵的逆阵。本讲稿第六十二页，共一百三十五页无约束极值问题的解法无约束极值问题的解法 (4)4)共轭梯度法共轭梯度法 基本思想基本思想:最最速速下下降降法法,步步骤骤简简单单，但但收收敛敛速速度度太太慢慢，而而牛牛顿顿法法和和阻阻尼尼法法收收敛敛速速度度快快，但但要要计计算算二二阶阶偏偏导导数数矩矩阵阵及及其其逆逆阵阵，计计算算量量

44、太太大大，共共轭轭梯梯度度法法兼兼有有这这两两种种方方法法的的优优点点，它它比比最最速速下下降降法法的的收收敛敛速速度度要要快快得得多多同同时时又又避避免免了了像像牛牛顿顿法法所所要要求的海赛矩阵的计算，存贮和求逆。求的海赛矩阵的计算，存贮和求逆。本讲稿第六十三页，共一百三十五页无约束极值问题的解法无约束极值问题的解法 (4)4)共轭梯度法共轭梯度法 共轭梯度法是以一种叫共轭方向作为迭代的共轭梯度法是以一种叫共轭方向作为迭代的搜索方向的下降算法。搜索方向的下降算法。共轭方向概念共轭方向概念:共轭梯度法求解无约束二次规划思想共轭梯度法求解无约束二次规划思想共轭梯度法求解无约束二次规划步骤共轭梯度

45、法求解无约束二次规划步骤共轭梯度法求解非线性无约束极值问题思想共轭梯度法求解非线性无约束极值问题思想求解非线性无约束极值问题步骤求解非线性无约束极值问题步骤本讲稿第六十四页，共一百三十五页无约束极值问题的解法无约束极值问题的解法 共轭梯度法共轭梯度法的特点：的特点：共轭梯度法对一般目标函数的无约束优化问题的共轭梯度法对一般目标函数的无约束优化问题的求解具有较高的效率，因此在无约束优化算法中求解具有较高的效率，因此在无约束优化算法中占有重要的地位，是目前最常用的方法之一，由占有重要的地位，是目前最常用的方法之一，由于它的计算公式简单，存贮量少，可以用来求解于它的计算公式简单，存贮量少，可以用来求

46、解比较大的问题。对于交通系统规划中遇到的极值比较大的问题。对于交通系统规划中遇到的极值问题，这方法是效果较好的算法。问题，这方法是效果较好的算法。(4)4)共轭梯度法共轭梯度法 本讲稿第六十五页，共一百三十五页无约束极值问题的解法无约束极值问题的解法 (5)5)变尺度法变尺度法变尺度法的基本思想变尺度法的基本思想变尺度法的变尺度法的计算步骤计算步骤本讲稿第六十六页，共一百三十五页无约束极值问题的解法无约束极值问题的解法 (5)5)变尺度法变尺度法变尺度法的特点：变尺度法的特点：变尺度法也是求解无约束极值问题的一种变尺度法也是求解无约束极值问题的一种有效算法。由于它既避免了计算二阶导数海赛有效算

47、法。由于它既避免了计算二阶导数海赛矩阵及其求逆过程，又比梯度法的收敛速度快，矩阵及其求逆过程，又比梯度法的收敛速度快，特别是对高维极值问题具有显著的优越性特别是对高维极值问题具有显著的优越性。本讲稿第六十七页，共一百三十五页有约束极值问题的解法有约束极值问题的解法 道道路路工工程程与与交交通通系系统统规规划划中中经经常常遇遇到到许许多多问问题题的的数数学学模模型型描描述述大大多多是是非非线线性性最最优优化化问问题题，变变量量和和约约束束条条件件一一般般比比较较多多，规规模模较较大大，所所以以约约束束非非线线性性最最优优化化方方法法在在道道路路与与交交通通工工程程系系统统分分析析中中极极其其重要

48、。重要。算算法法大大多多相相当当复复杂杂，没没有有一一种种对对一一切切有有约约束束极极值值问题的求解都普遍有效的算法问题的求解都普遍有效的算法。许许多多方方法法求求得得的的解解大大多多不不能能保保证证是是全全局局最最优优解解，而只能是局部最优解。而只能是局部最优解。本讲稿第六十八页，共一百三十五页有约束极值问题的解法有约束极值问题的解法 解法思路：一般基本上的处理是将非线性约束解法思路：一般基本上的处理是将非线性约束极值问题转化成无约束极值问题，例如惩罚函极值问题转化成无约束极值问题，例如惩罚函数法；将非线性极值问题转化成线性规划问题数法；将非线性极值问题转化成线性规划问题或用二次规划来逐次逼

49、近，将复杂的约束问题或用二次规划来逐次逼近，将复杂的约束问题转化成简单问题来处理转化成简单问题来处理 本讲稿第六十九页，共一百三十五页有约束极值问题的解法有约束极值问题的解法 解的最优性条件解的最优性条件：紧约束、紧约束指标集的定义紧约束、紧约束指标集的定义 定理：定理：最优性的一阶必要条件最优性的一阶必要条件定理：定理：最优性的充分条件最优性的充分条件例例 本讲稿第七十页，共一百三十五页有约束极值问题的解法有约束极值问题的解法 广义拉格朗日乘子法：（如前述）广义拉格朗日乘子法：（如前述）惩罚函数法：惩罚函数法：惩惩罚罚函函数数法法是是求求解解约约束束极极值值问问题题一一种种重重要要而而常常用

50、用方方法法。通通过过将将约约束束极极值值问问题题转转化化成成一一系系列列无无约约束束极极值值问问题题来来求求解解的的，所所以以称称为为序序列列无无约约束束极极小小化化技技术术，或或称称SUMT法法。惩惩罚罚函函数数法法是是序序列列无无约约束束极极小小化化技技术术之之一一，又又称称其其为为SUMT外外点法。点法。本讲稿第七十一页，共一百三十五页有约束极值问题的解法有约束极值问题的解法 惩罚函数法构造思路：惩罚函数法构造思路：惩罚函数法的计算步骤：惩罚函数法的计算步骤：例例：本讲稿第七十二页，共一百三十五页有约束极值问题的解法有约束极值问题的解法 碰壁函数法碰壁函数法:碰碰壁壁函函数数法法跟跟惩惩