交通运输工程系统分析

《交通运输工程系统分析》由会员分享，可在线阅读，更多相关《交通运输工程系统分析（151页珍藏版）》请在装配图网上搜索。

1、交通运输工程系统分析 Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life,there is hope。有生命必有希望。有生命必有希望交通运输工程系统分析交通运输工程系统分析使用教材：道路与交通工程系统分析，姚祖康主编，使用教材：道路与交通工程系统分析，姚祖康主编，人民交通出版社，人民交通出版社，1996年年12月第一版；月第一版；参考书目：参考书目：1、交通运输工程学，沈志云、邓学均，人民交通、交通运输工程学，沈志云、邓学均，人民交通 出版社，出版社，2005年年5月第二版；月第二版；2、运筹学、运筹学(修订版修订版)，运筹学

2、教材编写组，运筹学教材编写组，清华大学出版社，清华大学出版社，1990年年1月第二版；月第二版；3、交通运输工程，冯树民，知识产权出版社，、交通运输工程，冯树民，知识产权出版社，2004年年10月第一版；月第一版；4、运筹学习题集、运筹学习题集(修订版修订版)，胡运权主编，清华大学，胡运权主编，清华大学 出版社，出版社，1995年年5月第二版。月第二版。第一章第一章 概概 论论1.1 系统与系统分析系统与系统分析（1）系统的定义）系统的定义 系统是由一些相互联系、相互依赖、互感相关的系统是由一些相互联系、相互依赖、互感相关的独立单元或部分组合而成的复杂集合，每个单元或独立单元或部分组合而成的复

3、杂集合，每个单元或部分具有各自的特性和功能，这些相关单元或部分部分具有各自的特性和功能，这些相关单元或部分按一定目的和结构方式协调统一在系统的整体中，按一定目的和结构方式协调统一在系统的整体中，以实现特定的系统功能。以实现特定的系统功能。（2 2）系统的属性）系统的属性普遍存在性（普遍存在性（Ubiquity)Ubiquity)天然与人造共存（工程系统是人造的）天然与人造共存（工程系统是人造的）物理与概念同在物理与概念同在局部与整体相互影响和协调性局部与整体相互影响和协调性系统的目的性系统的目的性系统的层次性系统的层次性系统范围和功能的界定人为性系统范围和功能的界定人为性涉及学科的广泛性和综合

4、性涉及学科的广泛性和综合性（3 3）工程系统分析）工程系统分析 采用系统分析的方法论对工程项目的立项可行性采用系统分析的方法论对工程项目的立项可行性研究、规划、设计、建设、以及营运决策中的重大研究、规划、设计、建设、以及营运决策中的重大问题或方案进行分析研究，并为决策层提供决策依问题或方案进行分析研究，并为决策层提供决策依据的过程。据的过程。有三大类系统分析：有三大类系统分析：1）资源最优配置问题）资源最优配置问题2）目标最大化问题：在有限的资源制约下，如何）目标最大化问题：在有限的资源制约下，如何 使系统的目标值最大化；使系统的目标值最大化；3）方案优选（或推荐方案）问题）方案优选（或推荐方

5、案）问题系统分析的方法论包括：系统分析的方法论包括：1）利用数学的、物理的、仿真的方法对工程分析对）利用数学的、物理的、仿真的方法对工程分析对象建立模型和进行象建立模型和进行定量的分析与研究定量的分析与研究；2）利用专家的工程经验和常识知识对工程分析对象）利用专家的工程经验和常识知识对工程分析对象进行进行定性的分析与研究定性的分析与研究；3）定量与定性方法相结合定量与定性方法相结合的系统分析方法；的系统分析方法；4）微观与宏观分析方法相结合。）微观与宏观分析方法相结合。系统分析方法论是一个多学科的综合体，从整体系统分析方法论是一个多学科的综合体，从整体和系统的观念认识和分析系统的各个组成单元特

6、性和和系统的观念认识和分析系统的各个组成单元特性和内在关系，以及各单元协调形成的系统整体特性。内在关系，以及各单元协调形成的系统整体特性。人造系统的目的是人为设定的，各个系统运营时人造系统的目的是人为设定的，各个系统运营时期的系统目的价值不一样，其效能也不一样，只有通期的系统目的价值不一样，其效能也不一样，只有通过系统分析才能为系统设定新的效能更高的系统目过系统分析才能为系统设定新的效能更高的系统目的，故系统分析具有以下成效：的，故系统分析具有以下成效：1）提供多种不同的可选方案；）提供多种不同的可选方案；2）充分有效的利用有限的资源；）充分有效的利用有限的资源；3）提供预定目的而资源消耗最小

7、的方案；）提供预定目的而资源消耗最小的方案；4）为工程项目决策层提供多方面决策依据；）为工程项目决策层提供多方面决策依据；5）提供方案实施后的效果分析。）提供方案实施后的效果分析。2、系统分析程序、系统分析程序 系统分析程序有以下五个步骤：系统分析程序有以下五个步骤：1）辨识系统的结构、单元组成、关联、特性、及）辨识系统的结构、单元组成、关联、特性、及 其存在的问题，确定系统的目标；其存在的问题，确定系统的目标；2）提出可供选择的系统方案；）提出可供选择的系统方案；3）分析与评价系统方案；）分析与评价系统方案；4）优选系统方案；）优选系统方案；5）实施和后续验证系统方案。）实施和后续验证系统方

8、案。（1）系统辨识与目标设定）系统辨识与目标设定 不同的系统有不同的结构、组成单元、单元之不同的系统有不同的结构、组成单元、单元之间的相关关系、整体与个体的性状，需要进行辨间的相关关系、整体与个体的性状，需要进行辨识。如：城市交通系统与公路交通系统就不一样。识。如：城市交通系统与公路交通系统就不一样。辨识的方法则是进行不同类型的调查，有现场调辨识的方法则是进行不同类型的调查，有现场调查、有问卷调查、有专家咨询等。对调查所获得的查、有问卷调查、有专家咨询等。对调查所获得的数据资料进行科学的分析与研究，以期获得系统的数据资料进行科学的分析与研究，以期获得系统的现状特性和存在的问题，为设定新的系统目

9、标和设现状特性和存在的问题，为设定新的系统目标和设计新的系统方案提供科学的依据。计新的系统方案提供科学的依据。（2）提出可选方案）提出可选方案 为了解决现状系统存在的问题，实现系统的新为了解决现状系统存在的问题，实现系统的新目标，需要提出若干个在技术、经济、政治上目标，需要提出若干个在技术、经济、政治上可行可行的系统方案的系统方案，以供进一步的分析与研究。，以供进一步的分析与研究。可行性概念包括：可行性概念包括：1 1）技术可行性系统方案：达到系统技术性能指标和）技术可行性系统方案：达到系统技术性能指标和 系统预定技术目标的可能性；系统预定技术目标的可能性；2 2）经济可行性系统方案：可用经济

10、资源的可能性；）经济可行性系统方案：可用经济资源的可能性；3 3）政治可行性系统方案：在国家和地方政府政策允）政治可行性系统方案：在国家和地方政府政策允 许范围以及行政主管部门决策层的许可性。许范围以及行政主管部门决策层的许可性。3）分析与评价可选系统方案）分析与评价可选系统方案 对上述若干可行系统方案进行技术、经济、政对上述若干可行系统方案进行技术、经济、政治可行性对比分析（定量治可行性对比分析（定量+定性方法），综合评价定性方法），综合评价各方案的优劣程度，从中找出综合评价最优方案。各方案的优劣程度，从中找出综合评价最优方案。分析与评价按照定量与定性的指标（技术的、分析与评价按照定量与定性

11、的指标（技术的、经济的、政治的）进行。经济的、政治的）进行。（4）系统方案选择与决策）系统方案选择与决策 系统系统分析人员向决策者提出推荐方案的过程，分析人员向决策者提出推荐方案的过程，可能最优方案不是决策者所要的（政治可行性存在可能最优方案不是决策者所要的（政治可行性存在问题），系统分析人员要向决策者指出各可行方案问题），系统分析人员要向决策者指出各可行方案的优劣（含实施风险）之处，并提出自己分析所得的优劣（含实施风险）之处，并提出自己分析所得出的推荐方案。出的推荐方案。（5）系统方案实施与后续验证）系统方案实施与后续验证 对选定的系统方案实施，并在实施过程中进行对选定的系统方案实施，并在实

12、施过程中进行跟踪分析与研究，验证系统实施的优劣性。跟踪分析与研究，验证系统实施的优劣性。3、系统分析模型与方法、系统分析模型与方法（1）系统分析模型）系统分析模型 定义：模型是对现实事物的简化、模拟、和抽定义：模型是对现实事物的简化、模拟、和抽象。用数学语言描述系统行为的模型称之为数学模象。用数学语言描述系统行为的模型称之为数学模型。型。数学模型的类型：数学模型的类型：1）宏观模型；）宏观模型；2）中观模）中观模型；型；3）微观模型；）微观模型；4）计算机模型；）计算机模型；5）仿真模）仿真模型；型；6）解析模型；）解析模型；7）确定型模型；）确定型模型；8）随机型模）随机型模型等。型等。建立

13、和实施数学模型是系统分析过程中的中心内容。建立和实施数学模型是系统分析过程中的中心内容。建立数学模型的步骤：建立数学模型的步骤：1）初步设计数学模型。可采用经验的、套用已有）初步设计数学模型。可采用经验的、套用已有 的、在已有的基础上进行修正、设计全新的；的、在已有的基础上进行修正、设计全新的；2）利用调查获得的反映系统特性和行为的数据资）利用调查获得的反映系统特性和行为的数据资 料去标定系统模型技术参数，初步验证模型的料去标定系统模型技术参数，初步验证模型的 科学合理性；科学合理性；3）使用系统模型对未来进行预测；）使用系统模型对未来进行预测；4）修正系统模型，经验证对需要修正的模型进行）修

14、正系统模型，经验证对需要修正的模型进行 修正，以保证模型的可用性、科学性、以及合修正，以保证模型的可用性、科学性、以及合 理性。理性。数数 学学 模模 型型采用数学语言，对实际问题的一个近似描述，以便于人们采用采用数学语言，对实际问题的一个近似描述，以便于人们采用数学的方法研究工程实际问题。数学的方法研究工程实际问题。数学模型的特征数学模型的特征1.1.实践性：有实际背景，有针对性。接受工程实践的检验；实践性：有实际背景，有针对性。接受工程实践的检验；2.2.应用性：注意实际问题的要求。强调模型的工程实用价应用性：注意实际问题的要求。强调模型的工程实用价 值；值；3.3.综合性：数学与其他工程

15、学科知识的综合应用。综合性：数学与其他工程学科知识的综合应用。建模举例建模举例数学建模（数学建模（Mathematical Modelling)Mathematical Modelling)是一种数是一种数学的思考方法，利用数学的语言和方法，通过抽学的思考方法，利用数学的语言和方法，通过抽象、简化建立能近似刻画并象、简化建立能近似刻画并“解决解决”工程实际问工程实际问题的强有力的数学工具。题的强有力的数学工具。下面给出一个数学建模的例子，重点说明：下面给出一个数学建模的例子，重点说明：(1)(1)如何做出合理的、简化的假设；如何做出合理的、简化的假设；(2)(2)如何选择参数、变量，用数学语言

16、确切的表述工如何选择参数、变量，用数学语言确切的表述工 程实际问题；程实际问题；(3)(3)如何分析模型的结果，解决或解释工程实际问如何分析模型的结果，解决或解释工程实际问 题，或根据工程实际情况改进模型。题，或根据工程实际情况改进模型。例：信号控制道路交叉口通行能力计算。例：信号控制道路交叉口通行能力计算。十字型道路交叉口绿灯时间十字型道路交叉口绿灯时间30s30s，最多可以通行多少辆汽车？，最多可以通行多少辆汽车？假设：假设：1.1.车辆类型相同，绿灯开始之后都从静止开始做匀加速运动；车辆类型相同，绿灯开始之后都从静止开始做匀加速运动；2.2.车辆净间距相同，车辆启动延迟时间相等；车辆净间

17、距相同，车辆启动延迟时间相等；3.3.均为直行车辆，不拐弯，单向单车道；均为直行车辆，不拐弯，单向单车道；4.4.交通秩序良好，不堵车。交通秩序良好，不堵车。参数和变量：参数和变量：车长车长L L、车距、车距D D、加速度、加速度a a、启动延迟、启动延迟T T、在时刻、在时刻 t t 第第 n n 辆车车头的位置辆车车头的位置 Sn(t)Sn(t)。用数轴表示车辆行驶道路用数轴表示车辆行驶道路,数轴的正向为汽车行驶方向数轴的正向为汽车行驶方向,数轴数轴原点为停车线的位置。于是原点为停车线的位置。于是,当当Sn(30)Sn(30)0 0时时,表明在第表明在第3030秒秒第第n n辆车已通过红绿

18、灯，否则，结论相反。辆车已通过红绿灯，否则，结论相反。模模 型型1.1.停车位模型：停车位模型：Sn(0)=(n-1)(L+D)Sn(0)=(n-1)(L+D)；2.2.启动时间模型：启动时间模型：tn=(n-1)Ttn=(n-1)T；3.3.行驶模型：行驶模型：Sn(t)=Sn(0)+(1/2)a(t-tn)2,tSn(t)=Sn(0)+(1/2)a(t-tn)2,ttntn；参数估计：参数估计：L=5m L=5m，D=2mD=2m，T=1sT=1s，a=2m/sa=2m/s；解解:Sn(30)=-7(n-1)+(30-(n-1)2:Sn(30)=-7(n-1)+(30-(n-1)20 0，

19、解得，解得 n n 1919，且且t t1919=18s=18s30s=t 30s=t 成立。成立。答案：一个信号周期内最多答案：一个信号周期内最多1919辆车通过路口。辆车通过路口。改进：考虑到城市车辆的限速，在匀加速运动启动后，达到最改进：考虑到城市车辆的限速，在匀加速运动启动后，达到最高限速后，停止加速高限速后，停止加速,按最高限速通过上述道路交叉口。按最高限速通过上述道路交叉口。最高限速：校园内最高限速：校园内v*=15km/h=4m/sv*=15km/h=4m/s，长安街，长安街v*=40km/h v*=40km/h=11m/s=11m/s，环城路上，环城路上v*=60v*=60公里

20、公里/小时小时=17m/s=17m/s。取最高限速。取最高限速 v*=11m/sv*=11m/s，达到最高限速时间，达到最高限速时间tn*=v*/a+tn=5.5+n-1tn*=v*/a+tn=5.5+n-1。限速行驶模型：限速行驶模型：Sn(t)=Sn(0)+1/2a(tn*tn)Sn(t)=Sn(0)+1/2a(tn*tn)2+v*(t-tn*)2+v*(t-tn*)，ttn*ttn*=Sn(0)+1/2a(t-tn)=Sn(0)+1/2a(t-tn)2 2，tn*ttn tn*ttn =Sn(0)=Sn(0)，tnt tnt解：解：Sn(30)=-7(n-1)+(5.5)2+11(30-

21、5.5-(n-1)0 Sn(30)=-7(n-1)+(5.5)2+11(30-5.5-(n-1)0 得得 n n 17 17 且且t t1717*=5.5+16=21.5s30s=t*=5.5+16=21.5s0时，当前解不是时，当前解不是最优解，选择其中最大的最优解，选择其中最大的Cj为进入基的新变量为进入基的新变量(即即xj)，最小的，最小的bi/aij中的中的xi被换出基。被换出基。确定换入基的变量确定换入基的变量确定换出基的变量确定换出基的变量故本例中第一次迭代将故本例中第一次迭代将x1换入基变量，而将换入基变量，而将x5换出基变量。换出基变量。CbCj31000bibi/aijxb

22、xjx1x2x3x4x5003x3x4x1001-13-1100010-1-215145-5/114/3-5/1最优解判断依据最优解判断依据Cj0400-3当前目标函数值当前目标函数值Z1=15经过行变换得到下面新的单纯形表经过行变换得到下面新的单纯形表确定换入基的变量确定换入基的变量确定换出基的变量确定换出基的变量故故x2换入，换入，x4换出换出CbCj31000bibi/aijxb xjx1x2x3x4x5013x3x2x10010101001/31/31/3-5/3-2/31/329/314/329/3最优解判断依据最优解判断依据Cj000-4/3-1/3当前目标函数值当前目标函数值Z2

23、=101/3x2=x1=最优解最优解最优目标函数值最优目标函数值Z2=101/32.4.3 约束方程为约束方程为和号情况的处理和号情况的处理 约束方程为约束方程为号时所添加松弛变量前面是号时所添加松弛变量前面是“”号，而约束号，而约束方程为方程为号时无须添加松弛变量，这两种情况均不能产生初始号时无须添加松弛变量，这两种情况均不能产生初始基本变量（前面的符号为基本变量（前面的符号为+1），故需要做特别处理。处理方法），故需要做特别处理。处理方法则是增加人工变量，例如：则是增加人工变量，例如：将将左左边边方方程程组组转转换换为为右右边边标标准准形形式式式中式中 为系数符号分别为正负松弛变量，而为系

24、数符号分别为正负松弛变量，而 为人工变量。为人工变量。由于人工变量与原线性规划问题无关，由于人工变量与原线性规划问题无关，最终解不能含有人工最终解不能含有人工变量，即最终解时的人工变量必须为变量，即最终解时的人工变量必须为0。要求解这样的问题必要求解这样的问题必须采用两阶段单纯形法。须采用两阶段单纯形法。阶段阶段1、虚拟含有人工变量的目标函数，即人工变量之和。虚拟含有人工变量的目标函数，即人工变量之和。采用采用单纯形法求解单纯形法求解当虚拟目标函数达到当虚拟目标函数达到0时（此时所有人工变量均为时（此时所有人工变量均为0）的解，就可获得原线性规划问题的初始基本可行解；）的解，就可获得原线性规划

25、问题的初始基本可行解；阶段阶段2、以第一阶段的解作为第二阶段的初始基本可行解，采用、以第一阶段的解作为第二阶段的初始基本可行解，采用单纯形法求解原问题的最优解。单纯形法求解原问题的最优解。详见详见P18-19，例，例2.5。2.4.4 改进型单纯形法改进型单纯形法 单纯形算法每一次迭代只计算单纯形算法每一次迭代只计算 ，故其故其他变量的计算都与单纯形计算无关。根据这一特点，设计他变量的计算都与单纯形计算无关。根据这一特点，设计出通过矩阵运算直接从初始基本可行解计算出任一轮基本出通过矩阵运算直接从初始基本可行解计算出任一轮基本可行解的计算表，即改进型单纯形法。可行解的计算表，即改进型单纯形法。由

26、矩阵理论可知，任一轮单纯形计算表中的非基本变由矩阵理论可知，任一轮单纯形计算表中的非基本变量的系数列阵量的系数列阵 ，可以，可以通过对初始系数矩阵中相应的列阵通过对初始系数矩阵中相应的列阵 乘以基本变量系数矩阵的逆阵乘以基本变量系数矩阵的逆阵 后得到：后得到：也可以计算本轮单纯形计算表中的右端常数列阵也可以计算本轮单纯形计算表中的右端常数列阵B矢量即为基本变量值。而非基本变量的相对效益系数的计算矢量即为基本变量值。而非基本变量的相对效益系数的计算 改进型单纯形法计算步骤：改进型单纯形法计算步骤：（1）计算初始基本可行解和）计算初始基本可行解和 ，确定进出基本变量集合的变量；，确定进出基本变量集

27、合的变量；（2）计算）计算 、，确定新的进出基本变量集合的变量；，确定新的进出基本变量集合的变量；（3）计算）计算 、，确定新的进出基本变量集合的变量；，确定新的进出基本变量集合的变量；（4）重复）重复2、3步，直至获得最优解为止。步，直至获得最优解为止。2.5 对偶理论及其对偶单纯形法对偶理论及其对偶单纯形法2.5.1 对偶关系对偶关系 每一个线性规划问题都有一个对应的另外一个线性规划每一个线性规划问题都有一个对应的另外一个线性规划问题，称之为对偶问题。例如，一个求极大值的含有问题，称之为对偶问题。例如，一个求极大值的含有4个变量个变量和和2个约束条件的原线性规划问题：个约束条件的原线性规划

28、问题：就相应的有一个求极小值的含有就相应的有一个求极小值的含有2个变量和个变量和4个约束条件的对个约束条件的对偶线性规划问题。偶线性规划问题。原、对偶问题的对应关系：原、对偶问题的对应关系：（1）原问题的变量数与对偶问题的约束条件互为对应关系；）原问题的变量数与对偶问题的约束条件互为对应关系；（2）原问题目标函数的系数是对偶问题约束条件的右端常）原问题目标函数的系数是对偶问题约束条件的右端常 数，反之亦然；数，反之亦然；（3）原问题约束条件的系数矩阵与对偶问题约束条件的系数）原问题约束条件的系数矩阵与对偶问题约束条件的系数 矩阵互为转置关系；矩阵互为转置关系；（4）原、对偶问题的目标函数极大与

29、极小对应；）原、对偶问题的目标函数极大与极小对应；（5）原、对偶问题的约束条件不等号方向相反；）原、对偶问题的约束条件不等号方向相反；（6）对偶问题的对偶问题即为原问题。）对偶问题的对偶问题即为原问题。原问题：原问题：对偶问题：对偶问题：原问题：原问题：对偶问题：对偶问题：2.5.2 对偶定理对偶定理 对原线性规划问题求解的同时，也获得了对偶线性规划问对原线性规划问题求解的同时，也获得了对偶线性规划问题的解。题的解。这就是对偶定理的核心内容。这就是对偶定理的核心内容。定理定理1：弱对偶定律。弱对偶定律。原、对偶问题的任一基本可行解互为对原、对偶问题的任一基本可行解互为对 方目标函数的上、下界；

30、方目标函数的上、下界；定理定理2：最优解定律。最优解定律。如果对称对偶线性规划问题存在可行如果对称对偶线性规划问题存在可行 解，并且其对应的目标函数值相等，则这些可行解就解，并且其对应的目标函数值相等，则这些可行解就 是该问题的最优解；是该问题的最优解；定理定理3：主对偶定律。主对偶定律。如果原、对偶问题都是可行的，则它们如果原、对偶问题都是可行的，则它们 一定有最优解，其最优目标函数值相等；一定有最优解，其最优目标函数值相等；定理定理4：互补松弛定理。互补松弛定理。详见详见P24。可用于一个问题的最优解。可用于一个问题的最优解 寻求另一个问题的最优解。寻求另一个问题的最优解。2.5.3 对偶

31、单纯形法对偶单纯形法 利用对偶定理求解原线性规划问题的一种方法。利用对偶定理求解原线性规划问题的一种方法。原问题的标准形式为：原问题的标准形式为：则基本可行解的条件是：基本变量则基本可行解的条件是：基本变量 ，即右端常，即右端常数为非负值。而符合最优解的条件是：各个非基本变量的相对数为非负值。而符合最优解的条件是：各个非基本变量的相对效益系数效益系数 （最小化问题时（最小化问题时 ）其对偶问题为：其对偶问题为：假设系数矩阵假设系数矩阵A可用列向量可用列向量P1、P2、Pn表示，则上述约表示，则上述约束条件可改写成：束条件可改写成：上述最后一个式子就是判断原问题基本可行解是否为最优解的条上述最后

32、一个式子就是判断原问题基本可行解是否为最优解的条件式。件式。因此，原问题最优解的判断依据就是满足对偶问题的约束因此，原问题最优解的判断依据就是满足对偶问题的约束条件。条件。对偶单纯形法是从对偶问题可行的系数阵（也即对偶单纯形法是从对偶问题可行的系数阵（也即 ）开始，变换到另一个对偶问题可行的系数阵，直到系数阵变为原开始，变换到另一个对偶问题可行的系数阵，直到系数阵变为原问题可行的（即问题可行的（即B0）为止。）为止。对偶单纯形法也采用单纯形表进行对偶单纯形法也采用单纯形表进行行变换计算，表中相对收益系数行变换计算，表中相对收益系数 需保持为非正值（需保持为非正值（Max）或）或非负值（非负值（

33、Min），而右端常数），而右端常数bi可以不是非负值，变换计算是使可以不是非负值，变换计算是使右端常数右端常数bi都变为非负值。当实现时，其解对原、对偶问题都是都变为非负值。当实现时，其解对原、对偶问题都是可行的，故是最优解。可行的，故是最优解。计算步骤：计算步骤：为使为使bi变为非负值，通过选择非基本变量置换基变为非负值，通过选择非基本变量置换基本变量来实现，首先选择本变量来实现，首先选择b为负最大的基本变量为负最大的基本变量xi退出基本变退出基本变量集合，而后在系数量集合，而后在系数aij为为负值的非基本变量中选取比值为为负值的非基本变量中选取比值cj/aij为最大的（为最大的（aijZ2

34、=39，需要进一步考察，需要进一步考察LP3可可行域内是否还有更优的整数解。如果行域内是否还有更优的整数解。如果Z3Z2，就不需要再去搜，就不需要再去搜寻最优解了，因为增加约束条件不会获得更优的解；寻最优解了，因为增加约束条件不会获得更优的解；（5）重复第二步，对非整数变量）重复第二步，对非整数变量x，按其两侧邻近整数值继续分，按其两侧邻近整数值继续分解解LP3的可行域，形成两个新的线性规划问题的可行域，形成两个新的线性规划问题LP4和和LP5。LP4问题：问题：LP5问题：问题：（6）重复第三步，选择）重复第三步，选择LP4继续求解。在继续求解。在LP3问题的最后一个问题的最后一个单纯形表的

35、基础上加一行约束条件，通过行变换得：单纯形表的基础上加一行约束条件，通过行变换得：x1=0，x2=5，Z4=40。此为整数解，目标函数值。此为整数解，目标函数值Z4大于大于LP2的下限值的下限值Z2=39。（7）重复第四步，选择）重复第四步，选择LP5继续求解。但由于新增约束条件继续求解。但由于新增约束条件x1 2会违背第一个约束条件（因为此时会违背第一个约束条件（因为此时x24），故），故LP5不存在可不存在可行解。行解。最终本整数规划问题的最优解为最终本整数规划问题的最优解为LP4的最优解，即的最优解，即x1=0，x2=5，Z*=Z4*=40。上述解题过程可用下图来表示：。上述解题过程可用

36、下图来表示：LP1LP2LP3LP4LP5非整数解非整数解x1=2.25，x2=3.75，Z1=41.25；为分枝定界上限值。；为分枝定界上限值。整数解整数解x1=3，x2=3，Z2=39；为分枝定界；为分枝定界下限值。下限值。整数解整数解x1=0，x x2 2=5，Z4=40；为最优整数解；为最优整数解非整数解非整数解x1=1.8,x2=4,Z3=41；无可行解无可行解 上述树状图中每一个节点代表一个线性规划问题，当其解上述树状图中每一个节点代表一个线性规划问题，当其解（1）为整数解时；（）为整数解时；（2）或为不可行解时；（）或为不可行解时；（3）或其解的目标）或其解的目标函数值函数值Z下

37、限值（下限值（Max）或）或上限值（上限值（Min）时，均为终节点，不）时，均为终节点，不再继续向下分枝。否则，选择一个非整数变量，分岔出两个各增再继续向下分枝。否则，选择一个非整数变量，分岔出两个各增加一个约束条件的节点（新的线性规划问题），继续分别求解，加一个约束条件的节点（新的线性规划问题），继续分别求解，直至所有节点均为终节点为止。以终节点中目标函数值最大的可直至所有节点均为终节点为止。以终节点中目标函数值最大的可行整数解为本问题的最终解。行整数解为本问题的最终解。因此，其计算效率取决于如何尽快使各节点变成终节点，故因此，其计算效率取决于如何尽快使各节点变成终节点，故与进行分枝的非整数

38、变量选择次序有关，一些规则：与进行分枝的非整数变量选择次序有关，一些规则：（1）选择分数值最大的非整数变量进行分枝；）选择分数值最大的非整数变量进行分枝；（2）按决策变量在目标函数中的权重（系数）最大（）按决策变量在目标函数中的权重（系数）最大（Max）或）或 最小（最小（Min）进行选择；）进行选择；（3）选择目标函数值最大（）选择目标函数值最大（Max）或最小（）或最小（Min）的非整数解先）的非整数解先 进行分枝；进行分枝；（4）对新近解出的非整数解先进行分枝。）对新近解出的非整数解先进行分枝。第三章第三章 非线性规划非线性规划Non Linear Programming3.1 概述概述

39、3.1.1 NLP模型：模型：现实中有很多的问题其目标函数或约束现实中有很多的问题其目标函数或约束条件是非线性的，这类问题称之为非线性规划问题，需要借条件是非线性的，这类问题称之为非线性规划问题，需要借助非线性规划方法求解。例如：助非线性规划方法求解。例如：转换为转换为因为上述是二元变量问题，可用图解法求解，详见因为上述是二元变量问题，可用图解法求解，详见P34图图3-1。20134652461-2可行域可行域g1约束条件约束条件g2约束条件约束条件g4约束条件约束条件x1g3约束条件约束条件目标函数等值线目标函数等值线约束最优点约束最优点Z*=3.8，x1*=0.58，x2*=1.34非线性

40、规划问题的一般形式：非线性规划问题的一般形式：对于无约束的非线性规划问题，可采用求导数的方法获得最优对于无约束的非线性规划问题，可采用求导数的方法获得最优解。对于有约束的非线性规划问题，目前仍然没有普遍适用的解。对于有约束的非线性规划问题，目前仍然没有普遍适用的方法求解，但是有三类方法可以求解一部分有约束的非线性规方法求解，但是有三类方法可以求解一部分有约束的非线性规划问题：划问题：（1）反复线性逼近，将）反复线性逼近，将LP方法扩展到方法扩展到NLP中；中；（2）采用惩罚函数将有约束的非线性规划问题转变成无约束）采用惩罚函数将有约束的非线性规划问题转变成无约束 的非线性规划问题；的非线性规划

41、问题；（3）将不等式约束问题等效转换为等式约束问题；将）将不等式约束问题等效转换为等式约束问题；将n维无维无 约束问题转化为一维无约束问题。约束问题转化为一维无约束问题。3.1.2 一维函数的极值问题一维函数的极值问题 回顾微积分学，一维连续函数的局部极值概念详见回顾微积分学，一维连续函数的局部极值概念详见P35图图3-2。全局极值概念：如果在某点。全局极值概念：如果在某点x*上，上，f(x*)在整个定义域上是极在整个定义域上是极值（极大或极小），则称值（极大或极小），则称f(x*)是是f(x)的全局极值。的全局极值。微积分学中的极值定理：一维连续函数微积分学中的极值定理：一维连续函数f(x)

42、极值点的必要条极值点的必要条件是它的一阶导数件是它的一阶导数f(x)=0。但这一条件并不是充分条件，也即一。但这一条件并不是充分条件，也即一阶导数为阶导数为0的点不一定准是极值点。的点不一定准是极值点。f(x)=0的点称之为驻点。的点称之为驻点。判断驻点是否为极值点的充分条件：需要由二阶或更高阶判断驻点是否为极值点的充分条件：需要由二阶或更高阶导数来判断。假设一维连续函数导数来判断。假设一维连续函数f(x)存在一阶和二阶导数，并且存在一阶和二阶导数，并且在在x0上，上，f(x0)=0，f(x0)0，则，则 当当f(x0)0时，时，f(x)在在x0处有极大值；处有极大值；当当f(x0)0时，时，

43、f(x)在在x0处有极小值；处有极小值；如果在驻点如果在驻点x0上，上，f(x0)=0，而，而x0又不是拐点，判断又不是拐点，判断x0是否为极值是否为极值点只有借助更高一阶的导数来进行。点只有借助更高一阶的导数来进行。3.1.3 多维函数的极值问题多维函数的极值问题 由于太复杂，讨论多维函数极值问题时一般都采用展开由于太复杂，讨论多维函数极值问题时一般都采用展开式的二阶逼近。假设目标函数式的二阶逼近。假设目标函数f(X)是定义于是定义于n维欧氏空间的区维欧氏空间的区域域R中的多元函数中的多元函数f(x1,x2,xn)，且在，且在R中的点中的点 处有处有连续的连续的n+1阶偏导数存在，则对该函数

44、在阶偏导数存在，则对该函数在 附近的泰勒展附近的泰勒展开式取到二阶导数时，有：开式取到二阶导数时，有：上式可写成向量矩阵形式：上式可写成向量矩阵形式：或者简写成：或者简写成：上式中：上式中：一阶偏导数一阶偏导数 称之为目标函数称之为目标函数f(X)在在 处的梯度向量，处的梯度向量，简称梯度；二阶偏导数简称梯度；二阶偏导数 称之为目标函数称之为目标函数f(X)在在 处的处的海森矩阵（海森矩阵（Hessian Matrix)，记作，记作 。类似一维函数极值问题，多维函数极值定理为：类似一维函数极值问题，多维函数极值定理为：（1）n维目标函数维目标函数f(X)在在R内存在极值点内存在极值点X*的必要

45、条件是：的必要条件是：即梯度向量是一个即梯度向量是一个n维的零向量。满足上式的维的零向量。满足上式的X*只说明是多维只说明是多维函数函数f(X)的一个驻点，是否是极值点，还要做进一步的判断。的一个驻点，是否是极值点，还要做进一步的判断。（2）如果）如果n维目标函数维目标函数f(X)在驻点在驻点X*附近的泰勒级数展开到二附近的泰勒级数展开到二阶近似，即：阶近似，即：亦即：亦即：a.若在若在X*附近的邻域内，对于一切附近的邻域内，对于一切X，有：，有：则称海森阵则称海森阵H(X*)在点在点X*处是正定（处是正定（Positive Definite）的，则）的，则点点X*为极小值点；为极小值点；c.

46、若若H(X*)=0，即，即H(X*)为不定时，为不定时，f(X)在在X*处无极值。处无极值。b.类似地，若类似地，若则称海森阵则称海森阵H(X*)在点在点X*处是负定（处是负定（Negative Definite）的，）的，则点则点X*为极大值点；为极大值点；举例说明，举例说明，P37例例3.2，求解下列目标函数的极值点和极值，求解下列目标函数的极值点和极值解：由必要条件得：解：由必要条件得：联立上述方程可得：联立上述方程可得：X*=1，1 。由充分条件得：由充分条件得：故海森阵故海森阵H(X*)为正定，为正定，X*=1，1 为极小值点，函数极值为为极小值点，函数极值为4。3.1.4 目标函数

47、的凸性讨论目标函数的凸性讨论 前面讨论了多元目标函数的极值问题，但都是局部极值。在前面讨论了多元目标函数的极值问题，但都是局部极值。在非线性规划中希望求解出全局极值（最优解）。一般而言，在可非线性规划中希望求解出全局极值（最优解）。一般而言，在可行域内最优解点必为极值点，但反过来却未必成立。在什么条件行域内最优解点必为极值点，但反过来却未必成立。在什么条件下二者相同呢？找到这个条件就可以通过极值点求解最优解。下二者相同呢？找到这个条件就可以通过极值点求解最优解。定理：当多元目标函数定理：当多元目标函数f(X)在可行域内为一凸函数时，函数的极在可行域内为一凸函数时，函数的极值就是最优解值。值就是

48、最优解值。定义：设函数定义：设函数f(X)为定义在为定义在n维欧氏空间（维欧氏空间（E）中某个凸集）中某个凸集S上的上的函数，若对于任一函数，若对于任一0a0，则，则af(X)也是凸集也是凸集 S内的一个凸函数；内的一个凸函数；（2）设）设f1(X)、f2(X)均是凸集均是凸集S内的凸函数，且内的凸函数，且a、b0，则，则af1(X)+bf2(X)也是凸集也是凸集S内的一个凸函数，即凸函数的线性组合也内的一个凸函数，即凸函数的线性组合也 是凸函数；是凸函数；（3）若）若X1、X2为凸函数为凸函数f(X)中的两个极值点，则其连线上的任何中的两个极值点，则其连线上的任何 点都是点都是f(X)的极值

49、点。的极值点。凸函数的极值点凸函数的极值点=最优值点，因此，凸函数的最优解只要考最优值点，因此，凸函数的最优解只要考察它的一阶条件即可。察它的一阶条件即可。3.1.5 NLP的一般解题方法的一般解题方法 如果目标函数是凸函数，可行域是凸集，则只要求解目如果目标函数是凸函数，可行域是凸集，则只要求解目标函数的一阶导数就可以求出最优解。但是对于一般的标函数的一阶导数就可以求出最优解。但是对于一般的NLP问题，存在以下几个难点：问题，存在以下几个难点：（1）目标函数的一阶偏导数很难求出或者根本就无法求出，）目标函数的一阶偏导数很难求出或者根本就无法求出，无法判断目标函数的凸性；无法判断目标函数的凸性

50、；（2）有些目标函数根本不满足凸性的要求；）有些目标函数根本不满足凸性的要求；（3）为了求解极值点，需要求解梯度函数等于）为了求解极值点，需要求解梯度函数等于0的微分方程的微分方程 组，组，这些方程组有时是非线性的，非常难以求解。这些方程组有时是非线性的，非常难以求解。因此，有时求解因此，有时求解NLP问题时需采用数值解法，称之为直问题时需采用数值解法，称之为直接法。而直接法和解析法统称为寻优法（或搜索法）。对于接法。而直接法和解析法统称为寻优法（或搜索法）。对于前者称之为直接搜索法；对于后者称之为解析搜索法。前者称之为直接搜索法；对于后者称之为解析搜索法。直接搜索法有：直接搜索法有：坐标轮换

51、法、步长加速法、顺序单纯形法、以及坐标轮换法、步长加速法、顺序单纯形法、以及随机方向搜索法等；随机方向搜索法等；解析搜索法有：解析搜索法有：最速下降法、共轭梯度法、最速下降法、共轭梯度法、DEP法（变尺度法）、法（变尺度法）、以及惩罚函数法等。以及惩罚函数法等。后面章节中将分别介绍这两类方法中的代表。但是，搜索法的基后面章节中将分别介绍这两类方法中的代表。但是，搜索法的基本步骤大体相同，本步骤大体相同，都采用迭代的计算步骤都采用迭代的计算步骤，如下所示：，如下所示：（1）选择初始近似点）选择初始近似点X0（越靠近局部最优解越好）；（越靠近局部最优解越好）；（2）如果已经求解出第）如果已经求解出

52、第k次近似解次近似解Xk，但，但Xk还不是所要求精度的还不是所要求精度的局部最优解的近似值，要求进一步寻优，可以选择一个寻优方向局部最优解的近似值，要求进一步寻优，可以选择一个寻优方向Pk，称，称Pk为在为在Xk点处的搜索方向，使得沿点处的搜索方向，使得沿Pk方向目标函数值方向目标函数值f(X)下下降（降（Min）或上升（）或上升（Max）的速度最快；）的速度最快；（3）在）在Pk确定以后，由确定以后，由Xk点出发，以点出发，以Pk为方向，作向量为方向，作向量Xk+Pk，其中其中，0，称为步长因子，即在方向，称为步长因子，即在方向Pk上定出搜索的步长上定出搜索的步长=k，使得使得Xk+1=Xk

53、+kPk，满足满足f(Xk+1)f(Xk)（Min）或或 f(Xk+1)f(Xk)（Max）；）；（4）检验所得的新点）检验所得的新点Xk+1是否满足精度要求：是否满足精度要求：f(Xk+1)=f(Xk+1)f(Xk)如果满足，则如果满足，则Xk+1为局部近似最优解；否则，再以为局部近似最优解；否则，再以Xk+1点为初始点为初始近似点，转入第二轮搜索。注意：搜索方向近似点，转入第二轮搜索。注意：搜索方向Pk和搜索步长和搜索步长k构构成了每次迭代计算的成了每次迭代计算的修正量修正量，它们往往是决定算法好坏的重要，它们往往是决定算法好坏的重要因素。因素。从理论上讲，从理论上讲，Pk尽可能的指向问题

54、的最优解或使得尽可能的指向问题的最优解或使得f(X)值值的寻优最快的方向。在确定搜索方向的寻优最快的方向。在确定搜索方向Pk后，从后，从Xk出发，取出发，取k，使得使得f(X)沿沿Pk方向取最优值，即方向取最优值，即 这种计算的好处：这种计算的好处：1）将一个多维的无约束极值问题转化为）将一个多维的无约束极值问题转化为沿沿P Pk k（k0）方向的一维搜索问题；）方向的一维搜索问题；2）保证了大量搜索问题的收）保证了大量搜索问题的收敛性。由此看来，一维搜索问题是解决敛性。由此看来，一维搜索问题是解决NLP问题的最基本和最重问题的最基本和最重要的问题。要的问题。3.2 一维搜索问题求解方法一维搜

55、索问题求解方法 欲求解一元函数欲求解一元函数f(x)的极小值（的极小值（Minf(x)，从已经得到的迭，从已经得到的迭代点代点xk出发，沿搜索方向出发，沿搜索方向Pk前进所得到的新点前进所得到的新点xk+1=xk+kPk，总是，总是位于通过位于通过xk点的点的Pk方向上，见下图。由于此时方向上，见下图。由于此时x和和P已确定（为已已确定（为已知数），故函数知数），故函数f(x)变成以步长因子变成以步长因子为变量的一元函数，此问为变量的一元函数，此问题就变成了题就变成了取何值时，使得取何值时，使得f(xk+1)=f(xk+kPk)为极小值的求单为极小值的求单变量函数极值问题。变量函数极值问题。目

56、标函数等值线目标函数等值线目标函数极值，极值点目标函数极值，极值点X*X1X2PkP*Xk+Pk 点点称将求解最佳步长称将求解最佳步长k，使得：，使得：的过程为一维搜索，常用的一维搜索法有黄金分割法、二次插值的过程为一维搜索，常用的一维搜索法有黄金分割法、二次插值法、法、Fibonacci法等。法等。3.2.1 一维搜索区间的确定一维搜索区间的确定 从从X1点出发，跨出步长点出发，跨出步长h，得，得X2=X1+h，分别算出这两点的目，分别算出这两点的目标函数值标函数值f1=f(X1)，f2=f(X2)，然后比较其大小，再确定搜索方向。，然后比较其大小，再确定搜索方向。（1）若）若f1f2，则将

57、步长加倍，向右搜索，分别得，则将步长加倍，向右搜索，分别得X3=X2+2h，X4=X3+4h，Xk=Xk-1+2 h，并计算出与其相应的目标函数值，并计算出与其相应的目标函数值f(Xk)，直至目标函数值增加为止，如下图所示：，直至目标函数值增加为止，如下图所示：X1X2X3X4X5Xf(X)h 2h4h8h（2）若）若f1f2，所以向右搜索，得：，所以向右搜索，得：X3=X2+2h=3，f(X3)=15；X4=X3+4h=7，f(X4)=15；X5=X4+8h=15，f(X5)=111f(X4)；故故X3=3X*15=X5，作，作X6=(X4+X5)/2=11，f(X6)=47，取，取d=2

58、h=4h=4，Minf(X3)、f(X4)、f(X5)、f(X6)=f(X3)、或或f(X4)；若；若Xc=X3=3，则，则Xa=3-4=-1，Xb=3+4=7，故极小点所在区间为，故极小点所在区间为-1，7；若若Xc=X4=7，则，则Xa=7-4=3，Xb=7+4=11，故极小点所在区间为，故极小点所在区间为3，11。比较两种结果，可得极小点所在区域为。比较两种结果，可得极小点所在区域为3，7。同理，令同理，令X1=8，h=1，也可得到相同结果，详见，也可得到相同结果，详见P41。3.2.2 Fibonacci搜索法搜索法 假设单变量目标函数假设单变量目标函数y=f(X)是定义在区间是定义在

59、区间a，b上的向下上的向下单凸的函数，即存在唯一的最优点单凸的函数，即存在唯一的最优点X*，若在此区间任意选取，若在此区间任意选取a1、b1（a10的的情况下，作如下几次等价变换和计算：情况下，作如下几次等价变换和计算：（1）令）令y=xa，当，当x=a，b时，时，y=0，ba。此时，原问题变成。此时，原问题变成FP1：（2）再令）再令则原问题转化为标准的则原问题转化为标准的0，1搜索区间的问题搜索区间的问题FP2：（3）搜索次数（迭代次数）的计算。由于）搜索次数（迭代次数）的计算。由于0，而而从此式中可以计算出搜索次数从此式中可以计算出搜索次数n。（4）初始点的确定：）初始点的确定：（5）后

60、续计算点：）后续计算点：计算比较计算比较 ：a）若）若令令 ，第二次试验点为：，第二次试验点为：b）若）若 缩小后的区间为缩小后的区间为（6）结束计算判断：若）结束计算判断：若 成立，则结束迭代计算，成立，则结束迭代计算，令令 为最优解的近似值；否则继续迭为最优解的近似值；否则继续迭代计算，直至达到计算精度为止。代计算，直至达到计算精度为止。举例说明，举例说明，P44-45例例3.4。3.2.3 黄金分割法（黄金分割法（Golden Section Partition）是是Fibonacci法的一种简化方法，对于法的一种简化方法，对于Fibonacci法，若迭代法，若迭代次数为次数为n，则每次

61、迭代后搜索区间长度缩小的比例为：，则每次迭代后搜索区间长度缩小的比例为：即：即：可以证明，当可以证明，当n时，时，证明详见，证明详见P45-46。如果以不变的搜索区间缩小率如果以不变的搜索区间缩小率0.618代替代替Fibonacci法每次不法每次不同的搜索区间缩小率，就得到所谓的同的搜索区间缩小率，就得到所谓的0.618法，或黄金分割法。法，或黄金分割法。假设第假设第k次迭代后，保留区间为次迭代后，保留区间为显然：显然：x+y=akbk，而且，而且此时，此时，然后计算这两点上的函数值然后计算这两点上的函数值 按照前面的方法作判断，选择进一按照前面的方法作判断，选择进一步搜索区间，即：步搜索区

62、间，即：是原区间长度的是原区间长度的0.618倍，倍，反复迭代直反复迭代直至达到精度为止。至达到精度为止。举例举例P46-47例例3.5。3.2.4 二次插值法（自学）二次插值法（自学）3.3 3.3 多变量无约束极值问题多变量无约束极值问题3.3.1 3.3.1 最速下降法（梯度法）最速下降法（梯度法）思路：寻求使目标函数思路：寻求使目标函数f(X)下降（下降（MinMin）或上升（）或上升（MaxMax）最快）最快的搜索方向的搜索方向Pk和最佳步长和最佳步长k。假设无约束假设无约束NLP问题目标函数问题目标函数f(X)具有一阶和二阶偏导数，具有一阶和二阶偏导数，X*为其局部最优解，且令为其

63、局部最优解，且令X0为为X*的初始近似解，的初始近似解，Xk为为X*的第的第k次次迭代近似解。迭代近似解。如果从如果从Xk点出发，寻找第点出发，寻找第k+1次的近似逼近，则在次的近似逼近，则在Xk点选择使目点选择使目标函数标函数f(X)下降的方向下降的方向Pk作为第作为第k+1次搜索的方向次搜索的方向Xk+1=Xk+kPk，k0，计算，计算f(Xk+kPk)，希望值，希望值f(X)下降最快。根据微积分学可知，下降最快。根据微积分学可知，函数函数f(X)在在Xk点处数值下降最快的方向是该点处的负梯度方向，点处数值下降最快的方向是该点处的负梯度方向，即即Pk=f(Xk)；而上升最快的为：；而上升最

64、快的为：Pk=f(Xk)。搜索方向确定之后，还需要确定搜索步长，最佳搜索步长为：搜索方向确定之后，还需要确定搜索步长，最佳搜索步长为：也可用解析式直接计算：也可用解析式直接计算：最速下降法基本步骤：最速下降法基本步骤：（1）给定初始近似点）给定初始近似点X0En及其梯度模允许误差：及其梯度模允许误差：令令k=0；（2）计算）计算Pk=f(Xk)；（3）判别式）判别式Pk=f(Xk)如果成立，则认为如果成立，则认为Xk便是近便是近 似极小值点，否则转入下一步；似极小值点，否则转入下一步；（4）若）若f(Xk)，则利用一维搜索法求出最优步长，则利用一维搜索法求出最优步长k k，即：即：（5）令）令

65、Xk+1=Xk kf(Xk)，以其作为新的近似点，返回第二步。，以其作为新的近似点，返回第二步。计算实例说明详见计算实例说明详见P50-51例例3.7。3.3.2 步长加速法简介（步长加速法简介（Pattern Search）基本步骤：基本步骤：（1）任选一初始近似点）任选一初始近似点B1，以它为基点进行搜索；，以它为基点进行搜索；（2）为每一个独立变量）为每一个独立变量xi（i=1，2，n）选定步长：）选定步长：（2）（3）计算初始基点）计算初始基点B1的目标函数值的目标函数值f(B1)，对于点，对于点B1+1，若，若f(B1+1)f(B1)，即，即B1+1点没有点没有B1点好，则试验点好，

66、则试验B11点，如果它比点，如果它比B1点好，则以它为临时矢点点好，则以它为临时矢点T11，否则就以，否则就以B1为临时为临时矢点，即：矢点，即：（3）对于下一个独立变量对于下一个独立变量x2进行同样的摄动，此时用临时矢点进行同样的摄动，此时用临时矢点T12代代替原来的基点替原来的基点B1，一般有：，一般有：当当n个变量都被摄动之后，得临个变量都被摄动之后，得临时矢点时矢点T1n，并用原来的基点，并用原来的基点B1和新基点和新基点B B2 2建立了第一个模矢；建立了第一个模矢；（4）将第一个模矢延长一倍，得第二个模矢的初始临时矢点）将第一个模矢延长一倍，得第二个模矢的初始临时矢点T T2020=B=B1 1+2(B+2(B2 2BB1 1)=2B)=2B2 2BB1 1；（5）在）在T20附近进行与上述类似的搜索，建立临时矢点附近进行与上述类似的搜索，建立临时矢点T21，T22，T2n，以，以T2n为第三个基点为第三个基点B3，即，即T2n=B3，确立了第三个模矢：，确立了第三个模矢：T30=B2+2(B3B2)=2B3B2；.，（i）继续上述过程，对于第）继续上述过程，对于第i个模矢