《道路与交通系统分析优秀PPT.ppt》由会员分享，可在线阅读，更多相关《道路与交通系统分析优秀PPT.ppt（135页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、道路与交通系统分析课件第一页，本课件共有135页第一章 引论系统与系统工程系统与系统工程系统分析系统分析 主要内容和重点：主要内容和重点：系统的概念、特性与形态、系统工程方法论系统的概念、特性与形态、系统工程方法论的基本特点、系统分析的基本概念、系统分析的基本特点、系统分析的基本概念、系统分析的步骤的步骤 、系统的模型化、系统的模型化 、系统的最优化、系统的最优化 、系、系统评价统评价 、系统决策分析、系统决策分析 第一章第一章 系统工程与系统分系统工程与系统分析基本概念析基本概念 第二页，本课件共有135页系统与系统工程系统与系统工程一、一、系统的概念、特性与形态系统的概念、特性与形态 所谓
2、系统，是指由相互作用、相互依赖而又所谓系统，是指由相互作用、相互依赖而又能相互区别的若干组成部分（单元）组合而成能相互区别的若干组成部分（单元）组合而成的，具有特定功能的有机整体。的，具有特定功能的有机整体。系统四个特征：系统四个特征：整体性整体性相关性相关性目的性目的性环境适应性环境适应性第三页，本课件共有135页一、一、系统的概念、特性与形态系统的概念、特性与形态系统形态可分为以下几类系统形态可分为以下几类：自然系统与人造系统自然系统与人造系统实体系统与概念系统实体系统与概念系统动态系统与静态系统动态系统与静态系统控制系统与行为系统控制系统与行为系统第四页，本课件共有135页二、系统工程二
3、、系统工程 系统工程方法论的基本特点可归纳如下：系统工程方法论的基本特点可归纳如下：(1)研究方法上的整体性研究方法上的整体性(2)应用技术上的综合性应用技术上的综合性(3)处理问题上的科学性处理问题上的科学性按时间顺序可分为下述三个阶段：按时间顺序可分为下述三个阶段：系统规划阶段系统规划阶段(2)系统设计阶段系统设计阶段(3)系统制造和运行阶段系统制造和运行阶段第五页，本课件共有135页问题的提出问题的提出系统计划系统计划概略设计概略设计目标的确定目标的确定具体条件的确定具体条件的确定系统分析系统分析方案确定方案确定详细设计详细设计试试 制制制制 造造运运 行行系系统统规规划划系系统统设设计
4、计系系统统制制造造与与运运行行构构思思 计计划划分分析析 设设计计改改进进 运运行行图图1 1 系统建立流程图系统建立流程图 第六页，本课件共有135页 把把上上述述系系统统工工程程的的基基本本处处理理方方法法具具体体化化，那那就就是是在在系系统统工工程程中中最最常常使使用用的的系系统统分分析析、系系统统设设计计方方法法。这这种种方方法法不不但但用用于于系系统统设设计计阶阶段段，还还可可用用于于系系统统规规划划阶阶段段及及系系统统制制造造与与运运行行阶阶段段，以以求求得得系系统统的的合合理理规规划划、系系统统的的最优制造方法及系统的最优运行方式。最优制造方法及系统的最优运行方式。(1)(1)系
5、统分析；系统分析；(2)(2)系统设计；系统设计；(3)(3)系统的综合评价系统的综合评价。该方法大致可分为下列三个步骤该方法大致可分为下列三个步骤：第七页，本课件共有135页分分 析析综综 合合评评 价价系统的要求系统的要求系统的设计系统的设计 图图2系统工程基本处理方法框图系统工程基本处理方法框图 第八页，本课件共有135页系统分析系统分析一、系统分析的基本概念一、系统分析的基本概念 系系统统分分析析的的目目的的：通通过过分分析析比比较较各各种种替替代代方方案案的的费费用用、效效益益、功功能能和和可可靠靠性性等等各各项项技技术术经经济济指指标标，得得出出决决策策者者决决策策所所必必须须的的
6、资资料料和和信信息息，以便最后获得最优系统方案。图以便最后获得最优系统方案。图3表示。表示。系统问题系统问题系统分析系统分析最优系统方案最优系统方案 图图3系统分析的目的系统分析的目的第九页，本课件共有135页系统分析可概括为以下几个步骤：系统分析可概括为以下几个步骤：(1)系统目的的分析和确定系统目的的分析和确定(2)系统模型化系统模型化(3)系统最优化系统最优化(4)对解的评价对解的评价具体的步骤流程如教本具体的步骤流程如教本P8图图1-4。一、系统分析的基本概念一、系统分析的基本概念 第十页，本课件共有135页二、二、系统目的的分析与确定系统目的的分析与确定(1)(1)对象系统的定义对象
7、系统的定义(2)(2)目的和目标的分析与确定目的和目标的分析与确定(3)(3)技术条件的分析和定义技术条件的分析和定义 (4)(4)系统功能的分析与定义系统功能的分析与定义(5)(5)根据概略模型探讨成功的可能性根据概略模型探讨成功的可能性(6)(6)若不能取得可以成功的技术条件时，则采取若不能取得可以成功的技术条件时，则采取下述措施之一：下述措施之一：修改概略模型；修改概略模型；重新对功能技术条件进行分析；重新对功能技术条件进行分析；重新对目的、目标进行分析。重新对目的、目标进行分析。这是系统分析的最初阶段，步骤与内容：这是系统分析的最初阶段，步骤与内容：第十一页，本课件共有135页三、系统
8、的模型化三、系统的模型化模型分类：模型分类：(1)(1)形象模型形象模型 (2)(2)抽象模型抽象模型 模拟模型。模拟模型。数学模型。数学模型。概念模型。概念模型。对模型的要求一般为：对模型的要求一般为：(1)(1)现实性。现实性。(2)(2)简洁性。简洁性。(3)(3)适应性。适应性。第十二页，本课件共有135页三、系统的模型化三、系统的模型化建立数学模型来说，可有以下几步：建立数学模型来说，可有以下几步：(1)(1)分析模型的使用目的和要求，并确定模型的功能。分析模型的使用目的和要求，并确定模型的功能。(2)(2)根根据据目目的的要要求求，从从时时间间和和空空间间等等方方面面来来明明确确系
9、系统统和和环环境等的边界条件。境等的边界条件。(3)(3)确确定定构构成成系系统统功功能能的的最最小小单单位位，也也就就是是说说把把系系统统划划分分成成若若干干可可以以模模型型化化的的单单元元（或或子子系系统统），它它可可根根据据模型的使用目的来确定。模型的使用目的来确定。(4)(4)分分析析和和掌掌握握模模型型化化对对象象（单单元元或或子子系系统统）的的特特点点，主主要要因因素和逻辑结构，最后建立模型。素和逻辑结构，最后建立模型。(5)(5)应应用用最最优优化化理理论论和和系系统统控控制制理理论论，分分析析和和明明确确整整个个系系统统的特点，同时讨论适用的最优化方法。的特点，同时讨论适用的最
10、优化方法。第十三页，本课件共有135页四、系统的最优化四、系统的最优化 系系统统最最优优化化是是通通过过模模型型进进行行的的。图图1-41-4所所示示的的框框图图中中，表表示示了了系系统统最最优优化化的的一一般般步步骤骤，图图中中分分别别就就数数学学模模型型、图图象象模模型型等等表表示示了了最最优化过程。优化过程。上上述述最最优优化化方方法法的的具具体体内内容容将将在在第第二二章章至至第六章中详细介绍。第六章中详细介绍。第十四页，本课件共有135页五、系统的评价五、系统的评价 系统评价就是指从技术和经济等多个方面对系统评价就是指从技术和经济等多个方面对所设计的各个替代方案的最优解进行评价，通过
11、所设计的各个替代方案的最优解进行评价，通过分析和评价，从中选择在技术上是先进的，在经分析和评价，从中选择在技术上是先进的，在经济上是合理的方案作为最优系统方案。济上是合理的方案作为最优系统方案。对系统进行评价，首先必须确定评价基准，对系统进行评价，首先必须确定评价基准，即确定各种替代方案优先选用顺序的标准。评价即确定各种替代方案优先选用顺序的标准。评价基准一般根据系统的具体情况而定。基准一般根据系统的具体情况而定。第十五页，本课件共有135页五、系统的评价五、系统的评价例例如如，在在评评价价系系统统的的费费用用和和效效益益时时，评评价价基基准可以从下述三种基准中选用。即：准可以从下述三种基准中
12、选用。即：（1 1）以以各各替替代代方方案案效效益益相相同同为为基基准准，选选择择费费用最小的方案为最优方案。用最小的方案为最优方案。（2 2）以以各各方方案案费费用用相相同同为为基基准准，选选择择效效益益最最大的方案为最优方案。大的方案为最优方案。（3 3）以以效效益益费费用用比比为为基基准准，选选择择效效益益费费用用比比最最大大的的方方案案为为最最优优方方案案。进进行行系系统统的的经经济济评评价价时，必须考虑到时间价值的影响。时，必须考虑到时间价值的影响。第十六页，本课件共有135页六、系统决策分析六、系统决策分析 所所谓谓决决策策，就就是是根根据据客客观观可可能能性性，借借助助于于一一定
13、定的的理理论论、方方法法和和工工具具，进进行行科科学学的的分分析析、正正确确的的计计算算和和判判断断后后的的一一种种行行动动推推测测。决决策策科学是现代科学管理的关键。科学是现代科学管理的关键。系系统统决决策策分分析析就就是是根根据据系系统统评评价价的的结结果果，对对多多个个系系统统方方案案进进行行抉抉择择。人人们们对对确确定定条条件件下下的的情情况况，是是容容易易作作出出直直接接判判断断、进进行行决决策策的的，但但对对含含随随机机性性条条件件及及不不确确定定条条件件的的情情况况，进进行行决决策策就就困困难难了了，必必须须借借助助于于决决策策理理论论，第八章中予以介绍。第八章中予以介绍。第十七
14、页，本课件共有135页第四章第四章 非线性规划非线性规划 预备知识预备知识一维搜索一维搜索无约束极值问题的解法无约束极值问题的解法有约束极值问题及求解（重点）有约束极值问题及求解（重点）在道路交通工程中的应用在道路交通工程中的应用 第十八页，本课件共有135页一、一般描述一、一般描述目目标标函函数数或或约约束束条条件件出出现现非非线线性性函函数数时时，则则这这样样的的极极值值问问题题就就是是非非线线性性极极值值问问题题或或非线性规划。非线性规划。数学模型的一般形式如下：数学模型的一般形式如下：预备知识预备知识第十九页，本课件共有135页预备知识预备知识有时可写成：有时可写成：或或 第二十页，本
15、课件共有135页二、极值问题二、极值问题预备知识预备知识1 1、局部最优解和全局最优解、局部最优解和全局最优解2 2、多元函数和导数、多元函数和导数(重点重点)3 3、极值点存在的条件（、极值点存在的条件（重点重点）第二十一页，本课件共有135页预备知识预备知识1 1、局部最优解和全局最优解、局部最优解和全局最优解定义定义1.1 1.1 可行点可行点 S S，若对每一个若对每一个，均有，均有 ，则称，则称 为非线性规划的为非线性规划的最优解或称为全局最优解或极小点。最优解或称为全局最优解或极小点。定义定义1.2 1.2 可行点可行点 S S，若存在若存在 的某个的某个 领域领域 使得对每个使得
16、对每个 ，有，有 ，则，则称称 为非线性规划的局部最优解或局部为非线性规划的局部最优解或局部极小点。极小点。第二十二页，本课件共有135页2 2、多元函数和导数、多元函数和导数（1 1）偏导数）偏导数（2 2）梯度）梯度（3 3）方向导数）方向导数（4 4）海森矩阵）海森矩阵（5 5）正定矩阵）正定矩阵（6 6）多元函数的泰勒展开）多元函数的泰勒展开预备知识预备知识第二十三页，本课件共有135页3 3、极值点存在的条件、极值点存在的条件 定理定理3.13.1（必要条件）（必要条件）定理定理3.23.2（充分条件）（充分条件）例：例：预备知识预备知识第二十四页，本课件共有135页三、目标函数的凸
17、性讨论三、目标函数的凸性讨论（1 1）凸集）凸集（2 2）凸组合）凸组合（3 3）顶点）顶点（4 4）凸函数与凹函数）凸函数与凹函数（5 5）凸函数的性质）凸函数的性质（6 6）函数凸性的判定定理）函数凸性的判定定理（7 7）凸函数的极值）凸函数的极值预备知识预备知识第二十五页，本课件共有135页四、凸规划四、凸规划可行点、可行域可行点、可行域其中其中 、为凸函数，此非线性规划为凸规为凸函数，此非线性规划为凸规划划 预备知识预备知识第二十六页，本课件共有135页预备知识预备知识五、下降算法 下降迭代法的基本思想是：首先给出非线下降迭代法的基本思想是：首先给出非线性极值问题的最优解或局部最优解的
18、一个初性极值问题的最优解或局部最优解的一个初 始估计始估计 （称为初始点），然后，通过某种（称为初始点），然后，通过某种 迭迭 代算法得到一系列的可行点代算法得到一系列的可行点 ，,，希望点列，希望点列 的极限就是非线性极值问的极限就是非线性极值问题的一个最优解或局部最优解题的一个最优解或局部最优解 。第二十七页，本课件共有135页五、下降算法五、下降算法产生点列的方法产生点列的方法：若若从从 点点出出发发，沿沿任任何何方方向向移移动动时时，在在S S中中都都不不存存在在可可行行点点使使目目标标函函数数值值下下降降，则则 是是非非线线性性极极值值问问题题的的一一个个局局部部最最优优解解，迭迭代
19、代结结束束。若若从从 出出发发至至少少存存在在一一个个方方向向，在在S S中中沿沿此此方方向向可可以以使使目目标标函函数数值值有有所所下下降降，则则选选定定能能使使目目标标函函数数值值下下降降的的某某个个方方向向 ，然然后后沿沿此此方方向向移移动动适适当当的的一一步步，得得到下一个迭代点到下一个迭代点 ，即在射线即在射线 上选取一个新的可行点上选取一个新的可行点使使 第二十八页，本课件共有135页五、下降算法五、下降算法产生点列的方法产生点列的方法：其中其中 是一个向量，称为搜索方向，而是一个向量，称为搜索方向，而 是一个实数，是一个实数，称为搜索步长或步长。当称为搜索步长或步长。当 和和 确
20、定以后，由确定以后，由 就可就可以唯一确定以唯一确定 ，这样可以产生目标函数值下降且逼近，这样可以产生目标函数值下降且逼近非线性极值问题的最优解和局部最优解的序列非线性极值问题的最优解和局部最优解的序列 ,这这种算法称为下降迭代算法。种算法称为下降迭代算法。第二十九页，本课件共有135页五、下降算法五、下降算法下降迭代算法的一般步骤如下：下降迭代算法的一般步骤如下：（1 1）选择初始点）选择初始点 ;（2 2）确定搜索方向）确定搜索方向 。（3 3）确确定定后后，在在射射线线 （00）上上选选取取一一适适当当的的步步长长 ，使使 ，如如此此确确定出下一个点定出下一个点 。（4 4）检检验验所所
21、得得点点 是是否否为为极极小小点点，或或满满足足精精度度要要求求的的近近似似极极小小点点。若若满满足足，则则迭迭代代结结束束，否否则则继继续进行迭代。续进行迭代。第三十页，本课件共有135页五、下降算法五、下降算法迭代精度的确定迭代精度的确定：1.1.相继两次迭代的绝对误差：相继两次迭代的绝对误差：或或 2.2.相继两次迭代的相对误差：相继两次迭代的相对误差：或或 3.3.目标函数梯度的模：目标函数梯度的模：如如果果目目标标函函数数存存在在梯梯度度的的话话，可可以以根根据据目目标标函函数数在在最近迭代点处的梯度模足够小作为结束迭代的准则。即最近迭代点处的梯度模足够小作为结束迭代的准则。即第三十
22、一页，本课件共有135页一维搜索一维搜索 为为了了确确定定极极小小化化点点列列 ,在在每每次次迭迭代代时时要要沿沿确确定定的的搜搜索索方方向向 ,在在射射线线 上上，确确定定一一个个适适当的步长当的步长 ,使使 且且 。在在不不少少非非线线性性最最优优化化的的下下降降算算法法中中,步步长长 的的选选取取要要求求目目标标函函数数 在在点点 的的值值下下降降最最多，即步长多，即步长 满足满足也也就就是是求求一一元元函函数数 （）的的极极小小值值点点 。这这种种确确定定迭迭代代步步长长 的的方方法法称称为为精确一维搜索或简称一维搜索。精确一维搜索或简称一维搜索。第三十二页，本课件共有135页一维搜索
23、一维搜索精确一维搜索法精确一维搜索法(1)(1)牛顿法牛顿法(2)(2)抛物线法抛物线法 (3)(3)二分法二分法 (4)(4)“成功成功-失败失败”法法 (5)(5)FibonacciFibonacci法法(6)(6)黄金分割法黄金分割法 (7)(7)初始区间和初始点的确定（进退算法初始区间和初始点的确定（进退算法 ）第三十三页，本课件共有135页不精确一维搜索法不精确一维搜索法 一维搜索一维搜索 (1)(1)直接法直接法 (2)(2)二次插值法二次插值法第三十四页，本课件共有135页精确精确一维搜索一维搜索 (1)(1)牛顿法牛顿法牛顿法的基本思想是：用 在已知点 处的二阶Taylor展开
24、式来近似代替 ,即 ，然后用二次函数 的极小点 作为 的近似极小点，参见图3-1。第三十五页，本课件共有135页精确精确一维搜索一维搜索图3-1(1)(1)牛顿法牛顿法第三十六页，本课件共有135页精确精确一维搜索一维搜索由由 ,令令 ，得，得类似，若已知类似，若已知 ，则有，则有 进进行行迭迭代代计计算算，得得一一点点列列 ，这这种种求求一一元元函函数数 极极小小值值问问题题的的一一维维搜搜索索方方法法称称为为牛牛 顿顿法法。当当 时时，则则迭迭代代结结束束，为为 近似极小值点，即近似极小值点，即 。习题习题(1)(1)牛顿法牛顿法(一般公式一般公式)第三十七页，本课件共有135页牛牛顿顿法
25、法收收敛敛速速度度快快，但但是是它它对对函函数数要要求求二二次次可可微微，且且要要计计算算二二阶阶导导数数。另另外外还还要要求求初初始始点点 选选得得好好，否则可能得到的点列否则可能得到的点列 不收敛。不收敛。牛顿法产生的点列即使收敛，有时其极限也不牛顿法产生的点列即使收敛，有时其极限也不一定是所要求的函数的极小值点，而只能保证一定是所要求的函数的极小值点，而只能保证它是函数的驻点（一阶导数为它是函数的驻点（一阶导数为0 0的点）。驻点可的点）。驻点可能是极小值点，也可能是极大值点，也可能不能是极小值点，也可能是极大值点，也可能不是极值点。是极值点。精确精确一维搜索一维搜索(1)(1)牛顿法牛
26、顿法(特点特点)第三十八页，本课件共有135页 精确精确一维搜索一维搜索 (2)(2)抛物线法抛物线法 牛顿法是用牛顿法是用 在点在点 的二阶的二阶TaylorTaylor展开式展开式 来来 逼逼近近，即即利利用用点点 的的函函数数值值 及及其其一一阶阶、二二阶阶导导数数值值 、来来构构造造二二次次函函数数 ,而抛物线法则是利用而抛物线法则是利用 在三个点在三个点 ，处处的的函函数数值值来来构构造造二二次次函函数数 ，使使它它满足满足 第三十九页，本课件共有135页设设 ，则则 。令令 ，得得即可求得的近似极小值点。即可求得的近似极小值点。上上式式就就是是 近近似似极极小小值值点点的的计计算算
27、公公式式。为为求求出出近近似似极极小小值值点点 ，将将 代代入入方方程程组组，便便可可求得求得 、其中其中 其中其中 可得可得可得可得 将代入（将代入（4.84.8）或利）或利 精确精确一维搜索一维搜索 (2)(2)抛物线法抛物线法(一般公式一般公式)第四十页，本课件共有135页 精确精确一维搜索一维搜索(2)(2)抛物线法抛物线法(特点特点)抛物线法与牛顿法一样，它并不能保证算法一定收敛，即在迭代过程中可能出现上一次迭代点与下一次迭代点充分接近,但并不是的近似极小值点。抛物线法与牛顿法一样，它并不能保证算法一定收敛，即在迭代过程中可能出现上一次迭代点与下一次迭代点充分接近,但并不是的近似极小
28、值点。抛物线法与牛顿法一样，它并不能保证抛物线法与牛顿法一样，它并不能保证算法一定收敛，即在迭代过程中可能出现上算法一定收敛，即在迭代过程中可能出现上一次迭代点一次迭代点 与下一次迭代点与下一次迭代点 充分接近充分接近,但并不是但并不是 的近似极小值点。的近似极小值点。迭代过程迭代过程抛物线法求解步骤抛物线法求解步骤.doc.doc迭代过程迭代过程迭代过程迭代过程迭代过程迭代过程 第四十一页，本课件共有135页 精确精确一维搜索一维搜索 (3)(3)二分法二分法 若一区间若一区间 使使 且且 ，则在，则在 之间一定有一个之间一定有一个 的极小值点的极小值点 使得使得 取取 ,若若 ,则用区间则
29、用区间 代替区间代替区间 ，再取，再取 ；若；若 ,则用则用 代代替区间替区间 ，再取，再取 ；。经过。经过 次迭次迭代，设所得缩小的区间为代，设所得缩小的区间为 。若。若 或或 时，则取极小值时，则取极小值。迭代结束，否则继续进行迭代。迭代结束，否则继续进行迭代。第四十二页，本课件共有135页 精确精确一维搜索一维搜索 每步迭代的计算量比较小每步迭代的计算量比较小,程序简单，而程序简单，而且总能收敛于一个局部极小值点，但是收敛且总能收敛于一个局部极小值点，但是收敛较慢。较慢。对称取点，每次迭代缩减率相同。对称取点，每次迭代缩减率相同。习题习题(3)(3)二分法（特点）二分法（特点）第四十三页
30、，本课件共有135页 精确精确一维搜索一维搜索 (4)(4)“成功成功-失败失败”法法 是是一一种种启启发发式式算算法法。一一般般求求解解的的是是无无约约束束极极小化问题：小化问题：这里这里 表示整个实数域（表示整个实数域（）。）。如果遇到约束极小化问题如果遇到约束极小化问题则令则令 就等价转化为函数就等价转化为函数 的无约束极小化问题的无约束极小化问题。(一般为确定搜索区间而用一般为确定搜索区间而用)第四十四页，本课件共有135页 (4)(4)“成功成功-失败失败”法迭代步骤法迭代步骤1 1任任意意取取定定一一初初始始点点 ，设设定定迭迭代代搜搜索索的的步步长长 及精度及精度 。2 2计算计
31、算 及及 。3 3若若 ，则则称称此此步步向向前前搜搜索索成成功功，就就加加大大步步长长继继续续向向前前搜搜索索，即即用用 代代替替 ，用用步步长长 代替步长代替步长 ，继续向前搜索。继续向前搜索。若若 ，则则称称搜搜索索失失败败，向向后后搜搜索索 。首首先先看看是是否否？若若是是，则则极极小小值值点点取取 ,结结束束；否否则则,用用 代代替替步步长长 ,返返回回2 2，继继续续进行搜索。进行搜索。第四十五页，本课件共有135页 精确精确一维搜索一维搜索考虑如下一维极小化问题考虑如下一维极小化问题其中其中 要求在要求在 是单峰凸函数。是单峰凸函数。思路：任取思路：任取 则则（1 1）若）若 ，
32、则可将搜索区间缩小为，则可将搜索区间缩小为（2 2）若若 ，则可将搜索区间缩小为，则可将搜索区间缩小为 如此下去，最终必越来越逼近最优解如此下去，最终必越来越逼近最优解 (5)(5)FibonacciFibonacci法法 第四十六页，本课件共有135页 精确精确一维搜索一维搜索F F法的基本思路：对称取点法的基本思路：对称取点考虑考虑00，11极小化问题极小化问题 （1 1）选取两个初始点）选取两个初始点 、。（2 2）比较）比较 和和（3 3）进行下一次实验，重新选取）进行下一次实验，重新选取 和和（4 4）若满足，）若满足，则停止，否则返（则停止，否则返（3 3）若给定的区间不是若给定的
33、区间不是00，11，而是，而是 ，则给则给定的容许误差定的容许误差 ，下同。，下同。(5)(5)FibonacciFibonacci法法 第四十七页，本课件共有135页 精确精确一维搜索一维搜索F F法对称取点取法：法对称取点取法：考虑考虑 极小化问题极小化问题 选取两个初始点选取两个初始点 、，使，使 (5)(5)FibonacciFibonacci法法 第四十八页，本课件共有135页（1 1）由精度确定）由精度确定N N（2 2）计算计算N N次函数值，可获得最小的最终次函数值，可获得最小的最终区间区间（3 3）适用于一般函数，在极小点附近效果）适用于一般函数，在极小点附近效果好，精度较高
34、，速度快好，精度较高，速度快例：用例：用F F法求函数法求函数 的近似极小的近似极小点，要求缩短后的最终区间不大于原区点，要求缩短后的最终区间不大于原区间【间【-1-1，3 3】的】的8 8。(5)(5)FibonacciFibonacci法的特点法的特点 精确精确一维搜索一维搜索第四十九页，本课件共有135页 精确精确一维搜索一维搜索 (6)(6)黄金分割法（黄金分割法（0.1680.168法）法）它是它是FibonacciFibonacci法一种简化方法。黄金分割法法一种简化方法。黄金分割法是不用导数的一维搜索方法中比较常用的一种是不用导数的一维搜索方法中比较常用的一种方法。方法。考虑考虑
35、 极小化问题极小化问题黄金分割法计算上面问题的极小值点的步骤如黄金分割法计算上面问题的极小值点的步骤如下：下：第五十页，本课件共有135页 原始问题的变量 原始问题的松弛变量 精确精确一维搜索一维搜索 (6)(6)黄金分割法（黄金分割法（0.1680.168法）法）1 1：设定最后区间长度精度：设定最后区间长度精度 ，令，令 =0.618 =0.618。2 2：计算：计算 令令 。3 3：若：若 ，则结束，取极小值点则结束，取极小值点 （1/21/2）；否则，若；否则，若 ,则转则转4 4，否则转，否则转5 5。第五十一页，本课件共有135页 原始问题的变量 原始问题的松弛变量 精确精确一维搜
36、索一维搜索 (6)(6)黄金分割法（黄金分割法（0.1680.168法）法）4 4：令：令 ,再令再令 ，并计算，并计算 ,转转6 6。5 5：令：令 ，再令，再令 ，并计算，并计算 ,转转6 6。6 6：令：令 ,返回步骤返回步骤3 3。第五十二页，本课件共有135页 原始问题的变量 原始问题的松弛变量 精确精确一维搜索一维搜索 (6)(6)黄金分割法（黄金分割法（0.1680.168法）法）黄金分割法收敛速度是比较慢的，它的优黄金分割法收敛速度是比较慢的，它的优点是不要求点是不要求 可微，且每次迭代，只需计可微，且每次迭代，只需计算一个函数值，因此，计算量小，程序简单。算一个函数值，因此，
37、计算量小，程序简单。第五十三页，本课件共有135页 原始问题的变量 原始问题的松弛变量 精确精确一维搜索一维搜索 (7)(7)初始区间和初始点的确定初始区间和初始点的确定 一一般般求求解解一一维维极极小小化化问问题题时时，都都要要求求先先确确定定一一个个较较好好的的初初始始点点或或一一个个含含有有极极小小值值点点的的初初始始搜搜索索区区间间。为为此此，下下面面我我们们来来给给出出一一种种确确定定一一维维极极小小化化问问题题的的初初始始搜搜索索区区间间和和初初始始点点的的算算法法进进退算法。退算法。是是初初始始区区间间和和初初始始点点的的确确定定算算法法的的基基本本步步骤骤是是.doc.doc第
38、五十四页，本课件共有135页 原始问题的变量 原始问题的松弛变量 不精确不精确一维搜索一维搜索在实际计算中，一般做不到精确的一维搜在实际计算中，一般做不到精确的一维搜索，实际上，也没有必要做到这一点，因为精索，实际上，也没有必要做到这一点，因为精确的一维搜索需要付出较高的代价，而对加速确的一维搜索需要付出较高的代价，而对加速收敛作用不太大，下面介绍两种较实用的不精收敛作用不太大，下面介绍两种较实用的不精确一维搜索方法。确一维搜索方法。第五十五页，本课件共有135页 不精确不精确一维搜索一维搜索(2)(2)二次插值法二次插值法 特点：不精确一维搜索的方法简单，而且特点：不精确一维搜索的方法简单，
39、而且有时收敛速度还比精确一维搜索方法快得多。有时收敛速度还比精确一维搜索方法快得多。(1)(1)直接法直接法 第五十六页，本课件共有135页无约束极值问题的解法无约束极值问题的解法 一一般般求求解解无无约约束束极极值值问问题题的的算算法法基基本本上上都都是是下下降降算算法法。本本节节介介绍绍求求解解多多维维无无约约束束非非线线性规划问题性规划问题 比较常用有效的算法，包括最速下降法（梯比较常用有效的算法，包括最速下降法（梯度法）、牛顿法和阻尼牛顿法、共轭梯度法、度法）、牛顿法和阻尼牛顿法、共轭梯度法、变尺度法、直接搜索法等。变尺度法、直接搜索法等。第五十七页，本课件共有135页(1)最速下降法
40、最速下降法(2)牛顿法牛顿法(3)阻尼牛顿法阻尼牛顿法(4)共轭梯度法共轭梯度法(5)变尺度法变尺度法(6)直接搜索法直接搜索法 无约束极值问题的解法无约束极值问题的解法 第五十八页，本课件共有135页无约束极值问题的解法无约束极值问题的解法 (1)最速下降法最速下降法最最速速下下降降法法，也也叫叫梯梯度度法法，是是人人们们用用来来求求多多变变量量函函数数的的极极值值问问题题的的最最早早的的一一种种方方法法。后后来来提提出出的的不少方法基本上都是这种算法的改进算法。不少方法基本上都是这种算法的改进算法。梯度法的基本思路梯度法的基本思路梯度法的迭代步骤梯度法的迭代步骤第五十九页，本课件共有135
41、页无约束极值问题的解法无约束极值问题的解法 最最速速下下降降法法其其实实并并不不是是一一种种非非常常理理想想的的求求解解非非线线性性极极值值问问题题的的算算法法，这这是是因因为为当当用用最最速速下下降降法法迭迭代代趋趋近近极极小小点点时时，其其搜搜索索路路径径呈呈直直角角锯锯齿齿状状（相相邻邻两两次次的的搜搜索索方方向向互互相相垂垂直直）。在在迭迭代代开开始始时时下下降降比比较较快快，但但是是当当迭迭代代点点列列接接近近极极小点时收敛速度会很慢。小点时收敛速度会很慢。(1)最速下降法最速下降法第六十页，本课件共有135页无约束极值问题的解法无约束极值问题的解法 (2)牛顿法牛顿法 一维极值问题
42、的牛顿法，它容易推广到多一维极值问题的牛顿法，它容易推广到多维的情况，这个方法也是求解无约束极值问题维的情况，这个方法也是求解无约束极值问题的最早算法之一。的最早算法之一。牛顿法的基本思想牛顿法的基本思想 牛顿法的计算步骤牛顿法的计算步骤 牛顿法牛顿法的特点的特点第六十一页，本课件共有135页无约束极值问题的解法无约束极值问题的解法 （3 3）阻尼牛顿法阻尼牛顿法 阻尼牛顿法的基本思想阻尼牛顿法的基本思想阻尼牛顿法的计算步骤阻尼牛顿法的计算步骤阻尼牛顿法的特点：阻尼牛顿法的特点：阻尼牛顿法保持了牛顿法快速收敛的优点阻尼牛顿法保持了牛顿法快速收敛的优点,又不要求初点选得很好又不要求初点选得很好,
43、因而在实际应用中取得因而在实际应用中取得了较好的效果了较好的效果,当然其迭代公式中也没有避免要当然其迭代公式中也没有避免要求海赛矩阵的逆阵。求海赛矩阵的逆阵。第六十二页，本课件共有135页无约束极值问题的解法无约束极值问题的解法 (4)4)共轭梯度法共轭梯度法 基本思想基本思想:最最速速下下降降法法,步步骤骤简简单单，但但收收敛敛速速度度太太慢慢，而而牛牛顿顿法法和和阻阻尼尼法法收收敛敛速速度度快快，但但要要计计算算二二阶阶偏偏导导数数矩矩阵阵及及其其逆逆阵阵，计计算算量量太太大大，共共轭轭梯梯度度法法兼兼有有这这两两种种方方法法的的优优点点，它它比比最最速速下下降降法法的的收收敛敛速速度度要
44、要快快得得多多同同时时又又避避免免了了像像牛牛顿顿法法所所要要求的海赛矩阵的计算，存贮和求逆。求的海赛矩阵的计算，存贮和求逆。第六十三页，本课件共有135页无约束极值问题的解法无约束极值问题的解法 (4)4)共轭梯度法共轭梯度法 共轭梯度法是以一种叫共轭方向作为迭共轭梯度法是以一种叫共轭方向作为迭代的搜索方向的下降算法。代的搜索方向的下降算法。共轭方向概念共轭方向概念:共轭梯度法求解无约束二次规划思想共轭梯度法求解无约束二次规划思想共轭梯度法求解无约束二次规划步骤共轭梯度法求解无约束二次规划步骤共轭梯度法求解非线性无约束极值问题思想共轭梯度法求解非线性无约束极值问题思想求解非线性无约束极值问题
45、步骤求解非线性无约束极值问题步骤第六十四页，本课件共有135页无约束极值问题的解法无约束极值问题的解法 共轭梯度法共轭梯度法的特点：的特点：共轭梯度法对一般目标函数的无约束优化问题共轭梯度法对一般目标函数的无约束优化问题的求解具有较高的效率，因此在无约束优化算的求解具有较高的效率，因此在无约束优化算法中占有重要的地位，是目前最常用的方法之法中占有重要的地位，是目前最常用的方法之一，由于它的计算公式简单，存贮量少，可以一，由于它的计算公式简单，存贮量少，可以用来求解比较大的问题。对于交通系统规划中用来求解比较大的问题。对于交通系统规划中遇到的极值问题，这方法是效果较好的算法。遇到的极值问题，这方
46、法是效果较好的算法。(4)4)共轭梯度法共轭梯度法 第六十五页，本课件共有135页无约束极值问题的解法无约束极值问题的解法 (5)5)变尺度法变尺度法变尺度法的基本思想变尺度法的基本思想变尺度法的变尺度法的计算步骤计算步骤第六十六页，本课件共有135页无约束极值问题的解法无约束极值问题的解法 (5)5)变尺度法变尺度法变尺度法的特点：变尺度法的特点：变尺度法也是求解无约束极值问题的一种有变尺度法也是求解无约束极值问题的一种有效算法。由于它既避免了计算二阶导数海赛矩阵效算法。由于它既避免了计算二阶导数海赛矩阵及其求逆过程，又比梯度法的收敛速度快，特别及其求逆过程，又比梯度法的收敛速度快，特别是对
47、高维极值问题具有显著的优越性是对高维极值问题具有显著的优越性。第六十七页，本课件共有135页有约束极值问题的解法有约束极值问题的解法 道道路路工工程程与与交交通通系系统统规规划划中中经经常常遇遇到到许许多多问问题题的的数数学学模模型型描描述述大大多多是是非非线线性性最最优优化化问问题题，变变量量和和约约束束条条件件一一般般比比较较多多，规规模模较较大大，所所以以约约束束非非线线性性最最优优化化方方法法在在道道路路与与交交通通工工程程系系统统分分析析中中极极其其重要。重要。算算法法大大多多相相当当复复杂杂，没没有有一一种种对对一一切切有有约约束束极极值值问题的求解都普遍有效的算法问题的求解都普遍
48、有效的算法。许许多多方方法法求求得得的的解解大大多多不不能能保保证证是是全全局局最最优优解解，而只能是局部最优解。而只能是局部最优解。第六十八页，本课件共有135页有约束极值问题的解法有约束极值问题的解法 解法思路：一般基本上的处理是将非线性约解法思路：一般基本上的处理是将非线性约束极值问题转化成无约束极值问题，例如惩束极值问题转化成无约束极值问题，例如惩罚函数法；将非线性极值问题转化成线性规罚函数法；将非线性极值问题转化成线性规划问题或用二次规划来逐次逼近，将复杂的划问题或用二次规划来逐次逼近，将复杂的约束问题转化成简单问题来处理约束问题转化成简单问题来处理 第六十九页，本课件共有135页有
49、约束极值问题的解法有约束极值问题的解法 解的最优性条件解的最优性条件：紧约束、紧约束指标集的定义紧约束、紧约束指标集的定义 定理：定理：最优性的一阶必要条件最优性的一阶必要条件定理：定理：最优性的充分条件最优性的充分条件例例 第七十页，本课件共有135页有约束极值问题的解法有约束极值问题的解法 广义拉格朗日乘子法：（如前述）广义拉格朗日乘子法：（如前述）惩罚函数法：惩罚函数法：惩惩罚罚函函数数法法是是求求解解约约束束极极值值问问题题一一种种重重要要而而常常用用方方法法。通通过过将将约约束束极极值值问问题题转转化化成成一一系系列列无无约约束束极极值值问问题题来来求求解解的的，所所以以称称为为序序
50、列列无无约约束束极极小小化化技技术术，或或称称SUMT法法。惩惩罚罚函函数数法法是是序序列列无无约约束束极极小小化化技技术术之之一一，又又称称其其为为SUMT外外点点法。法。第七十一页，本课件共有135页有约束极值问题的解法有约束极值问题的解法 惩罚函数法构造思路：惩罚函数法构造思路：惩罚函数法的计算步骤：惩罚函数法的计算步骤：例例：第七十二页，本课件共有135页有约束极值问题的解法有约束极值问题的解法 碰壁函数法碰壁函数法:碰碰壁壁函函数数法法跟跟惩惩罚罚函函数数法法一一样样，也也是是将将约约束束极极值值问问题题转转化化无无约约束束极极值值问问题题，也也是是属属于于序序列列无无约约束束极极小