交通运输工程系统分析

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

1、交通运输工程系统分析Stillwatersrundeep.流静水深流静水深,人静心深人静心深Wherethereislife,thereishope。有生命必有希望。有生命必有希望交通运输工程系统分析交通运输工程系统分析使用教材：道路与交通工程系统分析，姚祖康主编，使用教材：道路与交通工程系统分析，姚祖康主编， 人民交通出版社，人民交通出版社，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

18、 0时时, , 表明在第表明在第3030秒秒第第n n辆车已通过红绿灯，否则，结论相反。辆车已通过红绿灯，否则，结论相反。模模 型型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

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

20、v*=40km/h =11m/s=11m/s，环城路上，环城路上v*=60v*=60公里公里/ /小时小时=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*

21、ttn =Sn(0) =Sn(0)， tnt tnt解：解：Sn(30)=-7(n-1)+(5.5)2+11(30-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被换出基。被换出基。确定换入基的变量确定换入基的变量确定换出基的变量确定换出基的变量故本例中第一次迭代将

22、故本例中第一次迭代将x1换入基变量，而将换入基变量，而将x5换出基变量。换出基变量。CbCj31000bibi/aijxb xjx1x2x3x4x5003x3x4x1001-13-1100010-1-215145-5/114/3-5/1最优解判断依据最优解判断依据Cj0400-3当前目标函数值当前目标函数值Z1=15经过行变换得到下面新的单纯形表经过行变换得到下面新的单纯形表确定换入基的变量确定换入基的变量确定换出基的变量确定换出基的变量故故x2换入，换入，x4换出换出CbCj31000bibi/aijxb xjx1x2x3x4x5013x3x2x10010101001/31/31/3-5/3

23、-2/31/329/314/329/3最优解判断依据最优解判断依据Cj000-4/3-1/3当前目标函数值当前目标函数值Z2=101/3x2=x1=最优解最优解最优目标函数值最优目标函数值Z2=101/32.4.3 约束方程为约束方程为和号情况的处理和号情况的处理 约束方程为约束方程为号时所添加松弛变量前面是号时所添加松弛变量前面是“”号，而约束号，而约束方程为方程为号时无须添加松弛变量，这两种情况均不能产生初始号时无须添加松弛变量，这两种情况均不能产生初始基本变量（前面的符号为基本变量（前面的符号为+1），故需要做特别处理。处理方法），故需要做特别处理。处理方法则是增加人工变量，例如：则是增

24、加人工变量，例如：将将左左边边方方程程组组转转换换为为右右边边标标准准形形式式式中式中 为系数符号分别为正负松弛变量，而为系数符号分别为正负松弛变量，而 为人工变量。为人工变量。由于人工变量与原线性规划问题无关，由于人工变量与原线性规划问题无关，最终解不能含有人工最终解不能含有人工变量，即最终解时的人工变量必须为变量，即最终解时的人工变量必须为0。要求解这样的问题必要求解这样的问题必须采用两阶段单纯形法。须采用两阶段单纯形法。阶段阶段1、虚拟含有人工变量的目标函数，即人工变量之和。虚拟含有人工变量的目标函数，即人工变量之和。采用采用单纯形法求解单纯形法求解当虚拟目标函数达到当虚拟目标函数达到0

25、时（此时所有人工变量均为时（此时所有人工变量均为0）的解，就可获得原线性规划问题的初始基本可行解；）的解，就可获得原线性规划问题的初始基本可行解；阶段阶段2、以第一阶段的解作为第二阶段的初始基本可行解，采用、以第一阶段的解作为第二阶段的初始基本可行解，采用单纯形法求解原问题的最优解。单纯形法求解原问题的最优解。详见详见P18-19，例，例2.5。2.4.4 改进型单纯形法改进型单纯形法 单纯形算法每一次迭代只计算单纯形算法每一次迭代只计算 ， ， ， 故其故其他变量的计算都与单纯形计算无关。根据这一特点，设计他变量的计算都与单纯形计算无关。根据这一特点，设计出通过矩阵运算直接从初始基本可行解计

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

27、法计算步骤：改进型单纯形法计算步骤：（1）计算初始基本可行解和）计算初始基本可行解和 ，确定进出基本变量集合的变量；，确定进出基本变量集合的变量；（2）计算）计算 、 、 ，确定新的进出基本变量集合的变量；，确定新的进出基本变量集合的变量； （3）计算）计算 、 ，确定新的进出基本变量集合的变量；，确定新的进出基本变量集合的变量；（4）重复）重复2、3步，直至获得最优解为止。步，直至获得最优解为止。 2.5 对偶理论及其对偶单纯形法对偶理论及其对偶单纯形法2.5.1 对偶关系对偶关系 每一个线性规划问题都有一个对应的另外一个线性规划每一个线性规划问题都有一个对应的另外一个线性规划问题，称之为对

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

29、阵与对偶问题约束条件的系数）原问题约束条件的系数矩阵与对偶问题约束条件的系数 矩阵互为转置关系；矩阵互为转置关系；（4）原、对偶问题的目标函数极大与极小对应；）原、对偶问题的目标函数极大与极小对应；（5）原、对偶问题的约束条件不等号方向相反；）原、对偶问题的约束条件不等号方向相反；（6）对偶问题的对偶问题即为原问题。）对偶问题的对偶问题即为原问题。原问题：原问题：对偶问题：对偶问题：原问题：原问题：对偶问题：对偶问题：2.5.2 对偶定理对偶定理 对原线性规划问题求解的同时，也获得了对偶线性规划问对原线性规划问题求解的同时，也获得了对偶线性规划问题的解。题的解。这就是对偶定理的核心内容。这就是

30、对偶定理的核心内容。定理定理1：弱对偶定律。弱对偶定律。原、对偶问题的任一基本可行解互为对原、对偶问题的任一基本可行解互为对 方目标函数的上、下界；方目标函数的上、下界；定理定理2：最优解定律。最优解定律。如果对称对偶线性规划问题存在可行如果对称对偶线性规划问题存在可行 解，并且其对应的目标函数值相等，则这些可行解就解，并且其对应的目标函数值相等，则这些可行解就 是该问题的最优解；是该问题的最优解； 定理定理3：主对偶定律。主对偶定律。如果原、对偶问题都是可行的，则它们如果原、对偶问题都是可行的，则它们 一定有最优解，其最优目标函数值相等；一定有最优解，其最优目标函数值相等； 定理定理4：互补

31、松弛定理。互补松弛定理。详见详见P24。可用于一个问题的最优解。可用于一个问题的最优解 寻求另一个问题的最优解。寻求另一个问题的最优解。2.5.3 对偶单纯形法对偶单纯形法 利用对偶定理求解原线性规划问题的一种方法。利用对偶定理求解原线性规划问题的一种方法。原问题的标准形式为：原问题的标准形式为：则基本可行解的条件是：基本变量则基本可行解的条件是：基本变量 ，即右端常，即右端常数为非负值。而符合最优解的条件是：各个非基本变量的相对数为非负值。而符合最优解的条件是：各个非基本变量的相对效益系数效益系数 （最小化问题时（最小化问题时 ）其对偶问题为：其对偶问题为：假设系数矩阵假设系数矩阵A可用列向

32、量可用列向量P1、P2、Pn表示，则上述约表示，则上述约束条件可改写成：束条件可改写成：上述最后一个式子就是判断原问题基本可行解是否为最优解的条上述最后一个式子就是判断原问题基本可行解是否为最优解的条件式。件式。因此，原问题最优解的判断依据就是满足对偶问题的约束因此，原问题最优解的判断依据就是满足对偶问题的约束条件。条件。对偶单纯形法是从对偶问题可行的系数阵（也即对偶单纯形法是从对偶问题可行的系数阵（也即 ）开始，变换到另一个对偶问题可行的系数阵，直到系数阵变为原开始，变换到另一个对偶问题可行的系数阵，直到系数阵变为原问题可行的（即问题可行的（即B0 ）为止。）为止。对偶单纯形法也采用单纯形表

33、进行对偶单纯形法也采用单纯形表进行行变换计算，表中相对收益系数行变换计算，表中相对收益系数 需保持为非正值（需保持为非正值（Max）或）或非负值（非负值（Min），而右端常数），而右端常数bi可以不是非负值，变换计算是使可以不是非负值，变换计算是使右端常数右端常数bi都变为非负值。当实现时，其解对原、对偶问题都是都变为非负值。当实现时，其解对原、对偶问题都是可行的，故是最优解。可行的，故是最优解。计算步骤：计算步骤：为使为使bi变为非负值，通过选择非基本变量置换基变为非负值，通过选择非基本变量置换基本变量来实现，首先选择本变量来实现，首先选择b为负最大的基本变量为负最大的基本变量xi退出基本变

34、退出基本变量集合，而后在系数量集合，而后在系数aij为为负值的非基本变量中选取比值为为负值的非基本变量中选取比值cj/aij为最大的（为最大的（aijZ2=39，需要进一步考察，需要进一步考察LP3可可行域内是否还有更优的整数解。如果行域内是否还有更优的整数解。如果Z3Z2，就不需要再去搜，就不需要再去搜寻最优解了，因为增加约束条件不会获得更优的解；寻最优解了，因为增加约束条件不会获得更优的解；（5）重复第二步，对非整数变量）重复第二步，对非整数变量x，按其两侧邻近整数值继续分，按其两侧邻近整数值继续分解解LP3的可行域，形成两个新的线性规划问题的可行域，形成两个新的线性规划问题LP4和和LP

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

36、划问题的最优解为最终本整数规划问题的最优解为LP4的最优解，即的最优解，即x1=0，x2=5，Z*=Z4*=40。上述解题过程可用下图来表示：。上述解题过程可用下图来表示：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；无可行解无可行解 上述树状图中每一个节点代表一个线性规划问题，当其解上述树状图

37、中每一个节点代表一个线性规划问题，当其解（1）为整数解时；（）为整数解时；（2）或为不可行解时；（）或为不可行解时；（3）或其解的目标）或其解的目标函数值函数值Z下限值（下限值（Max）或）或上限值（上限值（Min）时，均为终节点，不）时，均为终节点，不再继续向下分枝。否则，选择一个非整数变量，分岔出两个各增再继续向下分枝。否则，选择一个非整数变量，分岔出两个各增加一个约束条件的节点（新的线性规划问题），继续分别求解，加一个约束条件的节点（新的线性规划问题），继续分别求解，直至所有节点均为终节点为止。以终节点中目标函数值最大的可直至所有节点均为终节点为止。以终节点中目标函数值最大的可行整数解为

38、本问题的最终解。行整数解为本问题的最终解。 因此，其计算效率取决于如何尽快使各节点变成终节点，故因此，其计算效率取决于如何尽快使各节点变成终节点，故与进行分枝的非整数变量选择次序有关，一些规则：与进行分枝的非整数变量选择次序有关，一些规则：（1）选择分数值最大的非整数变量进行分枝；）选择分数值最大的非整数变量进行分枝；（2）按决策变量在目标函数中的权重（系数）最大（）按决策变量在目标函数中的权重（系数）最大（Max）或）或 最小（最小（Min）进行选择；）进行选择；（3）选择目标函数值最大（）选择目标函数值最大（Max）或最小（）或最小（Min）的非整数解先）的非整数解先 进行分枝；进行分枝；

39、（4）对新近解出的非整数解先进行分枝。）对新近解出的非整数解先进行分枝。第三章第三章 非线性规划非线性规划Non Linear Programming3.1 概述概述3.1.1 NLP模型：模型：现实中有很多的问题其目标函数或约束现实中有很多的问题其目标函数或约束条件是非线性的，这类问题称之为非线性规划问题，需要借条件是非线性的，这类问题称之为非线性规划问题，需要借助非线性规划方法求解。例如：助非线性规划方法求解。例如：转换为转换为因为上述是二元变量问题，可用图解法求解，详见因为上述是二元变量问题，可用图解法求解，详见P34图图3-1。20134652461-2可行域可行域g1约束条件约束条件

40、g2约束条件约束条件g4约束条件约束条件x1g3约束条件约束条件目标函数等值线目标函数等值线约束最优点约束最优点Z*=3.8，x1*=0.58，x2*=1.34非线性规划问题的一般形式：非线性规划问题的一般形式：对于无约束的非线性规划问题，可采用求导数的方法获得最优对于无约束的非线性规划问题，可采用求导数的方法获得最优解。对于有约束的非线性规划问题，目前仍然没有普遍适用的解。对于有约束的非线性规划问题，目前仍然没有普遍适用的方法求解，但是有三类方法可以求解一部分有约束的非线性规方法求解，但是有三类方法可以求解一部分有约束的非线性规划问题：划问题：（1）反复线性逼近，将）反复线性逼近，将LP方法

41、扩展到方法扩展到NLP中；中；（2）采用惩罚函数将有约束的非线性规划问题转变成无约束）采用惩罚函数将有约束的非线性规划问题转变成无约束 的非线性规划问题；的非线性规划问题；（3）将不等式约束问题等效转换为等式约束问题；将）将不等式约束问题等效转换为等式约束问题；将n维无维无 约束问题转化为一维无约束问题。约束问题转化为一维无约束问题。3.1.2 一维函数的极值问题一维函数的极值问题 回顾微积分学，一维连续函数的局部极值概念详见回顾微积分学，一维连续函数的局部极值概念详见P35图图3-2。全局极值概念：如果在某点。全局极值概念：如果在某点x*上，上，f(x*)在整个定义域上是极在整个定义域上是极

42、值（极大或极小），则称值（极大或极小），则称f(x*)是是f(x)的全局极值。的全局极值。 微积分学中的极值定理：一维连续函数微积分学中的极值定理：一维连续函数f(x)极值点的必要条极值点的必要条件是它的一阶导数件是它的一阶导数f(x)=0。但这一条件并不是充分条件，也即一。但这一条件并不是充分条件，也即一阶导数为阶导数为0的点不一定准是极值点。的点不一定准是极值点。 f(x)=0的点称之为驻点。的点称之为驻点。 判断驻点是否为极值点的充分条件：需要由二阶或更高阶判断驻点是否为极值点的充分条件：需要由二阶或更高阶导数来判断。假设一维连续函数导数来判断。假设一维连续函数f(x)存在一阶和二阶导数

43、，并且存在一阶和二阶导数，并且在在x0上，上， f(x0)=0， f(x0)0，则，则 当当f(x0)0时，时， f(x)在在x0处有极大值；处有极大值； 当当f(x0)0时，时，f(x)在在x0处有极小值；处有极小值；如果在驻点如果在驻点x0上，上，f(x0)=0，而，而x0又不是拐点，判断又不是拐点，判断x0是否为极值是否为极值点只有借助更高一阶的导数来进行。点只有借助更高一阶的导数来进行。3.1.3 多维函数的极值问题多维函数的极值问题 由于太复杂，讨论多维函数极值问题时一般都采用展开由于太复杂，讨论多维函数极值问题时一般都采用展开式的二阶逼近。假设目标函数式的二阶逼近。假设目标函数f(

44、X)是定义于是定义于n维欧氏空间的区维欧氏空间的区域域R中的多元函数中的多元函数f(x1, x2, , xn)，且在，且在R中的点中的点 处有处有连续的连续的n+1阶偏导数存在，则对该函数在阶偏导数存在，则对该函数在 附近的泰勒展附近的泰勒展开式取到二阶导数时，有：开式取到二阶导数时，有：上式可写成向量矩阵形式：上式可写成向量矩阵形式：或者简写成：或者简写成：上式中：上式中：一阶偏导数一阶偏导数 称之为目标函数称之为目标函数f(X)在在 处的梯度向量，处的梯度向量，简称梯度；二阶偏导数简称梯度；二阶偏导数 称之为目标函数称之为目标函数f(X)在在 处的处的海森矩阵（海森矩阵（Hessian M

45、atrix)，记作，记作 。类似一维函数极值问题，多维函数极值定理为：类似一维函数极值问题，多维函数极值定理为：（1）n维目标函数维目标函数f(X)在在R内存在极值点内存在极值点X*的必要条件是：的必要条件是：即梯度向量是一个即梯度向量是一个n维的零向量。满足上式的维的零向量。满足上式的X*只说明是多维只说明是多维函数函数f(X)的一个驻点，是否是极值点，还要做进一步的判断。的一个驻点，是否是极值点，还要做进一步的判断。（2）如果）如果n维目标函数维目标函数f(X) 在驻点在驻点X*附近的泰勒级数展开到二附近的泰勒级数展开到二阶近似，即：阶近似，即：亦即：亦即：a.若在若在X*附近的邻域内，对

46、于一切附近的邻域内，对于一切X，有：，有：则称海森阵则称海森阵H(X*)在点在点X*处是正定（处是正定（Positive Definite）的，则）的，则点点X*为极小值点；为极小值点；c. 若若H(X*) =0，即，即H(X*)为不定时，为不定时，f(X)在在X*处无极值。处无极值。b. 类似地，若类似地，若则称海森阵则称海森阵H(X*)在点在点X*处是负定（处是负定（Negative Definite）的，）的，则点则点X*为极大值点；为极大值点；举例说明，举例说明，P37例例3.2，求解下列目标函数的极值点和极值，求解下列目标函数的极值点和极值解：由必要条件得：解：由必要条件得：联立上述

47、方程可得：联立上述方程可得：X*=1，1 。由充分条件得：由充分条件得：故海森阵故海森阵H(X*)为正定，为正定，X*=1，1 为极小值点，函数极值为为极小值点，函数极值为4。3.1.4 目标函数的凸性讨论目标函数的凸性讨论 前面讨论了多元目标函数的极值问题，但都是局部极值。在前面讨论了多元目标函数的极值问题，但都是局部极值。在非线性规划中希望求解出全局极值（最优解）。一般而言，在可非线性规划中希望求解出全局极值（最优解）。一般而言，在可行域内最优解点必为极值点，但反过来却未必成立。在什么条件行域内最优解点必为极值点，但反过来却未必成立。在什么条件下二者相同呢？找到这个条件就可以通过极值点求解

48、最优解。下二者相同呢？找到这个条件就可以通过极值点求解最优解。定理：当多元目标函数定理：当多元目标函数f(X)在可行域内为一凸函数时，函数的极在可行域内为一凸函数时，函数的极值就是最优解值。值就是最优解值。定义：设函数定义：设函数f(X)为定义在为定义在n维欧氏空间（维欧氏空间（E）中某个凸集）中某个凸集S上的上的函数，若对于任一函数，若对于任一0a0，则，则af(X)也是凸集也是凸集 S内的一个凸函数；内的一个凸函数；（2）设）设f1(X) 、f2(X)均是凸集均是凸集S内的凸函数，且内的凸函数，且a、b0，则，则af1(X) +bf2(X)也是凸集也是凸集S内的一个凸函数，即凸函数的线性组

49、合也内的一个凸函数，即凸函数的线性组合也 是凸函数；是凸函数；（3）若）若X1、X2为凸函数为凸函数f(X)中的两个极值点，则其连线上的任何中的两个极值点，则其连线上的任何 点都是点都是f(X)的极值点。的极值点。 凸函数的极值点凸函数的极值点=最优值点，因此，凸函数的最优解只要考最优值点，因此，凸函数的最优解只要考察它的一阶条件即可。察它的一阶条件即可。3.1.5 NLP的一般解题方法的一般解题方法 如果目标函数是凸函数，可行域是凸集，则只要求解目如果目标函数是凸函数，可行域是凸集，则只要求解目标函数的一阶导数就可以求出最优解。但是对于一般的标函数的一阶导数就可以求出最优解。但是对于一般的N

50、LP问题，存在以下几个难点：问题，存在以下几个难点：（1）目标函数的一阶偏导数很难求出或者根本就无法求出，）目标函数的一阶偏导数很难求出或者根本就无法求出， 无法判断目标函数的凸性；无法判断目标函数的凸性；（2）有些目标函数根本不满足凸性的要求；）有些目标函数根本不满足凸性的要求；（3）为了求解极值点，需要求解梯度函数等于）为了求解极值点，需要求解梯度函数等于0的微分方程的微分方程 组，组， 这些方程组有时是非线性的，非常难以求解。这些方程组有时是非线性的，非常难以求解。 因此，有时求解因此，有时求解NLP问题时需采用数值解法，称之为直问题时需采用数值解法，称之为直接法。而直接法和解析法统称为

51、寻优法（或搜索法）。对于接法。而直接法和解析法统称为寻优法（或搜索法）。对于前者称之为直接搜索法；对于后者称之为解析搜索法。前者称之为直接搜索法；对于后者称之为解析搜索法。 直接搜索法有：直接搜索法有：坐标轮换法、步长加速法、顺序单纯形法、以及坐标轮换法、步长加速法、顺序单纯形法、以及随机方向搜索法等；随机方向搜索法等；解析搜索法有：解析搜索法有：最速下降法、共轭梯度法、最速下降法、共轭梯度法、DEP法（变尺度法）、法（变尺度法）、以及惩罚函数法等。以及惩罚函数法等。后面章节中将分别介绍这两类方法中的代表。但是，搜索法的基后面章节中将分别介绍这两类方法中的代表。但是，搜索法的基本步骤大体相同，

52、本步骤大体相同，都采用迭代的计算步骤都采用迭代的计算步骤，如下所示：，如下所示：（1）选择初始近似点）选择初始近似点X0（越靠近局部最优解越好）；（越靠近局部最优解越好）；（2）如果已经求解出第）如果已经求解出第k次近似解次近似解Xk，但，但Xk还不是所要求精度的还不是所要求精度的局部最优解的近似值，要求进一步寻优，可以选择一个寻优方向局部最优解的近似值，要求进一步寻优，可以选择一个寻优方向Pk，称，称Pk为在为在Xk点处的搜索方向，使得沿点处的搜索方向，使得沿Pk方向目标函数值方向目标函数值f(X)下下降（降（Min）或上升（）或上升（Max）的速度最快；）的速度最快；（3）在）在Pk确定以

53、后，由确定以后，由Xk点出发，以点出发，以Pk为方向，作向量为方向，作向量Xk+ Pk，其中其中，0，称为步长因子，即在方向，称为步长因子，即在方向Pk上定出搜索的步长上定出搜索的步长=k，使得使得Xk+1 =Xk+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点为初始点为初始近似点，转入第二轮搜索。注意：搜索方向近似

54、点，转入第二轮搜索。注意：搜索方向Pk和搜索步长和搜索步长k构构成了每次迭代计算的成了每次迭代计算的修正量修正量，它们往往是决定算法好坏的重要，它们往往是决定算法好坏的重要因素。因素。 从理论上讲，从理论上讲，Pk尽可能的指向问题的最优解或使得尽可能的指向问题的最优解或使得f(X) 值值的寻优最快的方向。在确定搜索方向的寻优最快的方向。在确定搜索方向Pk后，从后，从Xk出发，取出发，取k，使得使得f(X)沿沿Pk方向取最优值，即方向取最优值，即 这种计算的好处：这种计算的好处：1）将一个多维的无约束极值问题转化为）将一个多维的无约束极值问题转化为沿沿P Pk k（k0）方向的一维搜索问题；）方

55、向的一维搜索问题；2）保证了大量搜索问题的收）保证了大量搜索问题的收敛性。由此看来，一维搜索问题是解决敛性。由此看来，一维搜索问题是解决NLP问题的最基本和最重问题的最基本和最重要的问题。要的问题。3.2 一维搜索问题求解方法一维搜索问题求解方法 欲求解一元函数欲求解一元函数f(x)的极小值（的极小值（Minf(x)，从已经得到的迭，从已经得到的迭代点代点xk出发，沿搜索方向出发，沿搜索方向Pk前进所得到的新点前进所得到的新点xk+1=xk +kPk，总是，总是位于通过位于通过xk点的点的Pk方向上，见下图。由于此时方向上，见下图。由于此时x和和P已确定（为已已确定（为已知数），故函数知数），

56、故函数f(x)变成以步长因子变成以步长因子为变量的一元函数，此问为变量的一元函数，此问题就变成了题就变成了取何值时，使得取何值时，使得f(xk+1)=f(xk +kPk)为极小值的求单为极小值的求单变量函数极值问题。变量函数极值问题。目标函数等值线目标函数等值线目标函数极值，极值点目标函数极值，极值点X*X1X2PkP*Xk+Pk 点点称将求解最佳步长称将求解最佳步长k，使得：，使得：的过程为一维搜索，常用的一维搜索法有黄金分割法、二次插值的过程为一维搜索，常用的一维搜索法有黄金分割法、二次插值法、法、Fibonacci法等。法等。3.2.1 一维搜索区间的确定一维搜索区间的确定 从从X1点出

57、发，跨出步长点出发，跨出步长h，得，得X2=X1+h，分别算出这两点的目，分别算出这两点的目标函数值标函数值f1=f(X1)，f2=f(X2)，然后比较其大小，再确定搜索方向。，然后比较其大小，再确定搜索方向。（1）若）若f1f2，则将步长加倍，向右搜索，分别得，则将步长加倍，向右搜索，分别得X3=X2+2h，X4 =X3+4h，Xk=Xk-1+2 h，并计算出与其相应的目标函数值，并计算出与其相应的目标函数值f(Xk)，直至目标函数值增加为止，如下图所示：，直至目标函数值增加为止，如下图所示：X1X2X3X4X5Xf(X)h 2h4h8h（2）若）若f1f2，所以向右搜索，得：，所以向右搜索

58、，得：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 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。比较两种结果，

59、可得极小点所在区域为。比较两种结果，可得极小点所在区域为3，7。同理，令同理，令X1=8，h=1，也可得到相同结果，详见，也可得到相同结果，详见P41。3.2.2 Fibonacci搜索法搜索法 假设单变量目标函数假设单变量目标函数y=f(X)是定义在区间是定义在区间a，b上的向下上的向下单凸的函数，即存在唯一的最优点单凸的函数，即存在唯一的最优点X*，若在此区间任意选取，若在此区间任意选取a1、b1（a10的的情况下，作如下几次等价变换和计算：情况下，作如下几次等价变换和计算：（1）令）令y=xa，当，当x=a，b时，时，y=0，ba。此时，原问题变成。此时，原问题变成FP1：（2）再令）再

60、令则原问题转化为标准的则原问题转化为标准的0，1搜索区间的问题搜索区间的问题FP2：（3）搜索次数（迭代次数）的计算。由于）搜索次数（迭代次数）的计算。由于0，而而从此式中可以计算出搜索次数从此式中可以计算出搜索次数n。（4）初始点的确定：）初始点的确定：（5）后续计算点：）后续计算点：计算比较计算比较 ：a）若）若令令 ，第二次试验点为：，第二次试验点为：b）若）若 缩小后的区间为缩小后的区间为（6）结束计算判断：若）结束计算判断：若 成立，则结束迭代计算，成立，则结束迭代计算，令令 为最优解的近似值；否则继续迭为最优解的近似值；否则继续迭代计算，直至达到计算精度为止。代计算，直至达到计算精

61、度为止。举例说明，举例说明，P44-45例例3.4。3.2.3 黄金分割法（黄金分割法（Golden Section Partition） 是是Fibonacci法的一种简化方法，对于法的一种简化方法，对于Fibonacci法，若迭代法，若迭代次数为次数为n，则每次迭代后搜索区间长度缩小的比例为：，则每次迭代后搜索区间长度缩小的比例为：即：即：可以证明，当可以证明，当n时，时， ，证明详见，证明详见P45-46。如果以不变的搜索区间缩小率如果以不变的搜索区间缩小率0.618代替代替Fibonacci法每次不法每次不同的搜索区间缩小率，就得到所谓的同的搜索区间缩小率，就得到所谓的0.618法，或

62、黄金分割法。法，或黄金分割法。假设第假设第k次迭代后，保留区间为次迭代后，保留区间为显然：显然：x+y=akbk，而且，而且此时，此时，然后计算这两点上的函数值然后计算这两点上的函数值 按照前面的方法作判断，选择进一按照前面的方法作判断，选择进一步搜索区间，即：步搜索区间，即： 是原区间长度的是原区间长度的0.618倍，倍，反复迭代直反复迭代直至达到精度为止。至达到精度为止。举例举例P46-47例例3.5。3.2.4 二次插值法（自学）二次插值法（自学）3.3 3.3 多变量无约束极值问题多变量无约束极值问题3.3.1 3.3.1 最速下降法（梯度法）最速下降法（梯度法） 思路：寻求使目标函数

63、思路：寻求使目标函数f(X)下降（下降（MinMin）或上升（）或上升（MaxMax）最快）最快的搜索方向的搜索方向Pk和最佳步长和最佳步长k。 假设无约束假设无约束NLP问题目标函数问题目标函数f(X)具有一阶和二阶偏导数，具有一阶和二阶偏导数，X*为其局部最优解，且令为其局部最优解，且令X0为为X*的初始近似解，的初始近似解，Xk为为X*的第的第k次次迭代近似解。迭代近似解。如果从如果从Xk点出发，寻找第点出发，寻找第k+1次的近似逼近，则在次的近似逼近，则在Xk点选择使目点选择使目标函数标函数f(X)下降的方向下降的方向Pk作为第作为第k+1次搜索的方向次搜索的方向Xk+1 =Xk+kP

64、k， k0，计算，计算f(Xk+kPk)，希望值，希望值f(X)下降最快。根据微积分学可知，下降最快。根据微积分学可知，函数函数f(X)在在Xk点处数值下降最快的方向是该点处的负梯度方向，点处数值下降最快的方向是该点处的负梯度方向，即即Pk=f(Xk)；而上升最快的为：；而上升最快的为： Pk=f(Xk)。搜索方向确定之后，还需要确定搜索步长，最佳搜索步长为：搜索方向确定之后，还需要确定搜索步长，最佳搜索步长为：也可用解析式直接计算：也可用解析式直接计算：最速下降法基本步骤：最速下降法基本步骤：（1）给定初始近似点）给定初始近似点X0En及其梯度模允许误差：及其梯度模允许误差： 令令k=0；（

65、2）计算）计算Pk=f(Xk)；（3）判别式）判别式Pk= f(Xk)如果成立，则认为如果成立，则认为Xk便是近便是近 似极小值点，否则转入下一步；似极小值点，否则转入下一步；（4）若）若f(Xk)，则利用一维搜索法求出最优步长，则利用一维搜索法求出最优步长k k， 即：即：（5）令）令Xk+1=Xk kf(Xk)，以其作为新的近似点，返回第二步。，以其作为新的近似点，返回第二步。计算实例说明详见计算实例说明详见P50-51例例3.7。3.3.2 步长加速法简介（步长加速法简介（Pattern Search） 基本步骤：基本步骤：（1）任选一初始近似点）任选一初始近似点B1，以它为基点进行搜索

66、；，以它为基点进行搜索；（2）为每一个独立变量）为每一个独立变量xi（i=1，2，n）选定步长：）选定步长：（2）（3）计算初始基点）计算初始基点B1的目标函数值的目标函数值f(B1)，对于点，对于点B1+1，若，若f(B1+1)f(B1)，即，即B1+1点没有点没有B1点好，则试验点好，则试验B11点，如果它比点，如果它比B1点好，则以它为临时矢点点好，则以它为临时矢点T11，否则就以，否则就以B1为临时为临时矢点，即：矢点，即：（3）对于下一个独立变量对于下一个独立变量x2进行同样的摄动，此时用临时矢点进行同样的摄动，此时用临时矢点T12代代替原来的基点替原来的基点B1，一般有：，一般有：

67、 当当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=

68、B2+2(B3B2)=2B3B2；.，（i）继续上述过程，对于第）继续上述过程，对于第i个模矢，如果个模矢，如果f(Ti0)f(Bi)，则以，则以Ti0为为Bi+1，而且不将此模矢延长，继续搜索；若，而且不将此模矢延长，继续搜索；若f(Ti0)f(Bi) ，则应退，则应退回到回到Bi，并在，并在Bi附件继续搜索。如果能得出新的下降点，建立新附件继续搜索。如果能得出新的下降点，建立新的模矢，否则将步长缩小，以进行更加精确的搜索，直至搜索步的模矢，否则将步长缩小，以进行更加精确的搜索，直至搜索步长缩小到要求精度时，可以停止搜索。长缩小到要求精度时，可以停止搜索。3.4 多变量有约束求解极值问题多变

69、量有约束求解极值问题 有约束多变量极值问题一般形式：有约束多变量极值问题一般形式： 有约束有约束NLP问题解法的基本思路为问题解法的基本思路为：（1）将不等式约束转化为等式约束；）将不等式约束转化为等式约束；（2）将有约束的求解极值问题等效的转化为无约束求解极值问）将有约束的求解极值问题等效的转化为无约束求解极值问 题。题。 以下介绍工程上常用的求解有约束多元以下介绍工程上常用的求解有约束多元NLP的方法，即拉的方法，即拉格朗日乘子法和惩罚函数法。格朗日乘子法和惩罚函数法。3.4.1 等式约束条件下的拉格朗日乘子法等式约束条件下的拉格朗日乘子法 对于具有等式约束条件的多元对于具有等式约束条件的

70、多元NLP极值问题：极值问题：构造拉格朗日函数（构造拉格朗日函数（Lagrange Function）：）：式中式中i i为待定的拉格朗日系数或乘数。为待定的拉格朗日系数或乘数。可以证明上述约束极值问题等价于可以证明上述约束极值问题等价于minL(X, )。此时问题变成。此时问题变成具有具有n+m个变量，即个变量，即x1，x2，xn，和和1，2，m的无约束的无约束极值问题。对这极值问题。对这n+m个变量求一阶导数，可得极值点必要条件：个变量求一阶导数，可得极值点必要条件：上述后上述后m个方程恰是原问题中的约束条件，如果求解上述个方程恰是原问题中的约束条件，如果求解上述n+m个个方程得方程得mi

71、nL(X, )的解为：的解为：则有则有故有结论：若故有结论：若X*和和*是是minL(X, )的解，则的解，则X*必为原问题必为原问题minf(X)的解。详见的解。详见P53例例3.8。3.4.2 不等式约束条件下的拉格朗日乘子法不等式约束条件下的拉格朗日乘子法 对于不等式约束条件下的多元对于不等式约束条件下的多元NLP问题，需要在约束条件中问题，需要在约束条件中加入松弛变量，使之变成等式约束条件即可采用上述的拉格朗日加入松弛变量，使之变成等式约束条件即可采用上述的拉格朗日乘子法求解。对于约束条件：乘子法求解。对于约束条件：引入松弛变量引入松弛变量S使得：使得：详见详见P54例例3.9。3.4

72、.3 惩罚函数法（惩罚函数法（SUMT法）法） 类似于拉格朗日乘子法，类似于拉格朗日乘子法，SUMT法也是将有约束的多元法也是将有约束的多元NLP问题转化为无约束的多元问题转化为无约束的多元NLP问题。对于：问题。对于：其新的目标函数为：其新的目标函数为：式中式中(X, )为惩罚函数，为惩罚函数，为惩罚因子。只有当满足约束条件时，为惩罚因子。只有当满足约束条件时，上式第二项（惩罚项）才不起作用，此时惩罚函数的极值点就上式第二项（惩罚项）才不起作用，此时惩罚函数的极值点就是原函数的极值点。是原函数的极值点。1、外点法、外点法 将惩罚函数将惩罚函数(X, )定义于可行域之外的方法称之为外点惩定义于

73、可行域之外的方法称之为外点惩罚函数法。对于问题：罚函数法。对于问题：其惩罚函数的一般形式为：其惩罚函数的一般形式为：式中式中这就保证了在可行域内这就保证了在可行域内(X, )的解与的解与f(X)的解等价性，而在可行的解等价性，而在可行域之外将受到惩罚。域之外将受到惩罚。将上述惩罚函数将上述惩罚函数(X, )的近似解序列看成以惩罚因子的近似解序列看成以惩罚因子k为参数为参数的一条轨迹，当取的一条轨迹，当取01 12k，且且 时，时，点列点列X, k将从可行域外沿着这条轨迹向可行域的约束边界运将从可行域外沿着这条轨迹向可行域的约束边界运动，最后达到约束边界上的最优点动，最后达到约束边界上的最优点X

74、*。说明详见说明详见P55-56例例3.10。其优点其优点（1）对等式约束问题较简单；（）对等式约束问题较简单；（2）初始点容易选取。）初始点容易选取。其缺点：只适用于最优解在约束条件（可行域）边界的问题。其缺点：只适用于最优解在约束条件（可行域）边界的问题。2、内点法、内点法 对于问题：对于问题：定义惩罚函数定义惩罚函数上式右边第二项称之为障碍项，显然当上式右边第二项称之为障碍项，显然当X向可行域边界移动时，向可行域边界移动时，即即gj(X) 0时，时， (X, k) ， k称为障碍因子。当称为障碍因子。当k逐步减逐步减少时，障碍项所起的作用也就越来越小，所求解出的少时，障碍项所起的作用也就

75、越来越小，所求解出的min(X, k) 的解的解(X, k)也就逼近原问题的极小值解也就逼近原问题的极小值解X*。 说明详见说明详见P56-57例例3.11。 第四章第四章 动态规划动态规划（Dynamic Programming）4.1 动态规划原理动态规划原理4.1.1 概述概述 不同于线性和非线性规划问题不与时间发生关系（称之为不同于线性和非线性规划问题不与时间发生关系（称之为静态规划问题），而动态规划问题牵涉到时间或阶段性因素，静态规划问题），而动态规划问题牵涉到时间或阶段性因素，任何一个阶段作决策不是孤立的，而是与整个问题所有阶段都任何一个阶段作决策不是孤立的，而是与整个问题所有阶段

76、都有关联，不能只考虑本阶段的决策，要考虑动态规划问题整条有关联，不能只考虑本阶段的决策，要考虑动态规划问题整条链上的所有问题，形成一条决策链。链上的所有问题，形成一条决策链。 各个阶段的决策构成一个决策序列，各个阶段的决策构成一个决策序列，称之为策略称之为策略，对应于，对应于某一策略，系统会达到某种特定的效果。这种系统效果一般采某一策略，系统会达到某种特定的效果。这种系统效果一般采用定量的指标体系来衡量，用定量的指标体系来衡量，解决动态规划问题的目的则是选择解决动态规划问题的目的则是选择一种策略，使得采用指标衡量的系统效果最优，称这一策略为一种策略，使得采用指标衡量的系统效果最优，称这一策略为

77、最优策略。最优策略。 R. Bellman1951年提出解决多阶段决策问题的最优化原理年提出解决多阶段决策问题的最优化原理（The Principle of Optimality），称之为动态规划法。），称之为动态规划法。 举例说明，举例说明，P58例例4.1，最短路径问题，最短路径问题ABDGCEHKFILNJMPQ15271352224034422148352G2Q1求解沿箭头方向从求解沿箭头方向从A到到Q的最短路径。这个问题的特点则是完成的最短路径。这个问题的特点则是完成既定目标需要一个过程，既定目标需要一个过程，这个过程或与时间有关这个过程或与时间有关，或可以分成若或可以分成若干个阶段

78、。干个阶段。解例解例4.1：（：（1）直接枚举法）直接枚举法 将所有的可能路径罗列出来，再比较大小，得出最短路径。将所有的可能路径罗列出来，再比较大小，得出最短路径。得出结果：最短路径为得出结果：最短路径为A-S-E-I-L-N-Q，最短路径长度为，最短路径长度为13，详见，详见P59。由于每条路径有。由于每条路径有6个路段，要做个路段，要做5次加法计算，总共有次加法计算，总共有20条条路径，要做路径，要做100次加法计算，还要做次加法计算，还要做19次比较，才能最后计算出次比较，才能最后计算出上述结果，很麻烦。上述结果，很麻烦。（2）更快的算法）更快的算法动态规划法动态规划法 令令fi 表示

79、从点表示从点i（i=A, B，P）到终点到终点Q的最短距离，的最短距离，rij为为路段路段（i，j）的长度，如路段的长度，如路段A-B的长度为的长度为rAB。因此，。因此，fA 应等于应等于（rAB+fB）和（和（rAC+fC）中的较小者，即）中的较小者，即由于目前还不知道由于目前还不知道fB和和fC的值，故的值，故fA的值暂时还无法得知，需要的值暂时还无法得知，需要继续计算继续计算fB和和fC的值。的值。采用同样的方法对采用同样的方法对fB和和fC进行分析进行分析可见可见fB取决于取决于fD和和fE， fC取决于取决于fE和和fF。以此类推，直至终点前面的以此类推，直至终点前面的两个节点两个

80、节点N和和P，故这个问题可以从后面向前推算，即，故这个问题可以从后面向前推算，即从节点出来只有一个路段的节点有从节点出来只有一个路段的节点有G、K、N、J、M、P这六个，这六个，只需计算一次加法，对于其余九个节点需要计算只需计算一次加法，对于其余九个节点需要计算2次加法和次加法和1次次比较，故共比较，故共24次加法计算和次加法计算和9次比较，远比枚举法要快。次比较，远比枚举法要快。 最短路径追踪法：从起点最短路径追踪法：从起点A开始，沿着取最小值的点逐个向开始，沿着取最小值的点逐个向后追踪，直至终点为止。由后追踪，直至终点为止。由fA的算式可知的算式可知B点，由点，由fB可知可知E点，点，,

81、直至终点，即可得到最短路径的轨迹点序列。直至终点，即可得到最短路径的轨迹点序列。4.1.2 动态规划的基本概念动态规划的基本概念（1）阶段（）阶段（Stage） 一个阶段就是需要做出一个决策的子问题。阶段是按照决一个阶段就是需要做出一个决策的子问题。阶段是按照决策进行的时间或空间上的先后顺序划分的。用以描述阶段的变策进行的时间或空间上的先后顺序划分的。用以描述阶段的变量叫做阶段变量，用量叫做阶段变量，用k来表示。阶段数等于多阶段决策过程从开来表示。阶段数等于多阶段决策过程从开始到结束需做出的决策数目。例如例始到结束需做出的决策数目。例如例4.1，阶段，阶段1有有2条支路条支路（AB、AC）；阶

82、段）；阶段2有有4条支路（条支路（BD、BE、CE、CF）；阶段）；阶段3有有6条支路（条支路（DG、GH、EH、EI、FI、FJ）；）；，直至最末，直至最末一个阶段为止，总共有一个阶段为止，总共有6个阶段。个阶段。（2）状态（）状态（State） 状态表示某阶段的出发位置，它既是该阶段某支路的起点，状态表示某阶段的出发位置，它既是该阶段某支路的起点，又是前一阶段某一支路的终点。通常，一个阶段包含若干个状又是前一阶段某一支路的终点。通常，一个阶段包含若干个状态，如例态，如例4.1，阶段，阶段1有一个状态有一个状态A，阶段，阶段2有二个状态有二个状态B和和C，阶，阶段段3有三个状态有三个状态D、

83、E、F，。 描述状态的变量称之为状态变量，可为标量或向量。描述状态的变量称之为状态变量，可为标量或向量。常用常用Xk表示第表示第k阶段的状态集合，则第阶段的状态集合，则第k阶段状态变量集合为：阶段状态变量集合为：如例如例4.1中第三个阶段有中第三个阶段有D、E、F三个状态，用三个状态，用1、2、3编码，编码，可得：可得：X3=1，2，3，或，或X3=D，E，F 。（3）决策（）决策（Decision） 对于状态的选择就是决策。常用对于状态的选择就是决策。常用uk(xk)表示第表示第k阶段当状态阶段当状态为为xk时的决策变量。决策变量的取值限制在一定范围时，这一范时的决策变量。决策变量的取值限制

84、在一定范围时，这一范围称之为决策变量集合，用围称之为决策变量集合，用Uk(xk)来表示。显然来表示。显然uk(xk) Uk(xk)。（4）策略（）策略（Policy） 所有阶段决策序列组成策略，记为所有阶段决策序列组成策略，记为p1, n，n为阶段数，即为阶段数，即 p1, n=u1(x1)， u2(x2)，un(xn)第第k阶段至最末阶段的决策集合称之为阶段至最末阶段的决策集合称之为k子策略，即子策略，即 p1, n=uk(xk)， uk+1(xk+1)，un(xn)可供选择的策略范围称之为允许策略集合，从中系统效果最优的可供选择的策略范围称之为允许策略集合，从中系统效果最优的策略称之为最优

85、策略。策略称之为最优策略。（5）指标函数）指标函数 衡量实行决策优劣的数量指标就是指标函数（也称效用函数）衡量实行决策优劣的数量指标就是指标函数（也称效用函数），它定义于所有阶段和所有过程，即，它定义于所有阶段和所有过程，即 v1, n=v1, n(x1，u1，x2，u2 ，xn，un)k子策略指标函数为子策略指标函数为 vk, n=vk,n(xk，uk，xk+1， uk+1 ，xn，un)指标函数的物理意义可包括：距离、时间、费用、成本、利润、指标函数的物理意义可包括：距离、时间、费用、成本、利润、产量、资源消耗等。指标函数的最优值称之为最优指标函数。例产量、资源消耗等。指标函数的最优值称之

86、为最优指标函数。例如，例如，例4.1中的第中的第k点最优指标函数为点最优指标函数为fk(xk)，k=A，B，表示，表示从第从第k阶段阶段xk点到终点的最短距离。点到终点的最短距离。（6）状态转移方程）状态转移方程 如果第如果第k阶段的状态变量阶段的状态变量xk和决策变量和决策变量uk确定后，第确定后，第k+1阶段阶段的状态变量的状态变量xk+1和决策变量和决策变量uk+1也随之确定，这种连锁确定是通过也随之确定，这种连锁确定是通过状态转移方程完成的，记为状态转移方程完成的，记为xk+1=gk(xk, uk)，称之为，称之为xk+1xk的状态的状态转移方程。转移方程。4.1.3 最优化原理、动态

87、规划基本方程最优化原理、动态规划基本方程 动态规划整个过程是多阶段的，每一阶段都要求做出决策，动态规划整个过程是多阶段的，每一阶段都要求做出决策，并且（并且（1）下一阶段是在上一阶段决策的基础上做出决策，即本）下一阶段是在上一阶段决策的基础上做出决策，即本阶段的决策对下一阶段的决策有影响；（阶段的决策对下一阶段的决策有影响；（2）本阶段的决策一定）本阶段的决策一定要对整个动态规划全过程产生最优效果，但不一定是本阶段的最要对整个动态规划全过程产生最优效果，但不一定是本阶段的最优决策。优决策。 从例从例4.1可以看出：如果从可以看出：如果从AQ的最短路径轨迹为的最短路径轨迹为（xA， xB，xk，

88、xQ），），那么该轨迹线中的从任意第那么该轨迹线中的从任意第k点截断的后面点截断的后面部分也是从部分也是从k点到终点点到终点Q的最短路径，即的最短路径，即（xk，xk+1，xQ） 这这就是最优化原理的具体描述。就是最优化原理的具体描述。P63对最优化原理有定义，但太深对最优化原理有定义，但太深奥，语言太拗口。奥，语言太拗口。根据最优化原理，可通过逐段逆推先求解后面根据最优化原理，可通过逐段逆推先求解后面阶段最优决策的方法来求解全过程的最优决策。以最后阶段作为阶段最优决策的方法来求解全过程的最优决策。以最后阶段作为边界条件，从倒数第一阶段开始，逐步利用第边界条件，从倒数第一阶段开始，逐步利用第k

89、+1阶段以后的最阶段以后的最优子策略优子策略fk+1(xk+1)，求出第，求出第k阶段以后的最优策略阶段以后的最优策略fk(xk)，最终求得，最终求得f1(x1)。（2）动态规划（）动态规划（DP）模型）模型 DP建模程序：建模程序：1）阶段序数）阶段序数k=1，2，n；阶段数；阶段数=年；年；2）第）第k阶段的状态变量为阶段的状态变量为xk，状态变量集合为，状态变量集合为Xk；3）第）第k阶段的阶段的决策变量为决策变量为uk，允许决策变量集合为，允许决策变量集合为Uk；4）状态转移方程为：）状态转移方程为：xk+1 =gk(xk, uk)；5）确定各阶段的收益）确定各阶段的收益dk(xk,

90、uk)；6）建立）建立DP的的指标函数方程，求解最优指标函数指标函数方程，求解最优指标函数这里逆推算过程是从最末阶段这里逆推算过程是从最末阶段k=n开始，逐阶段逆推，直至推开始，逐阶段逆推，直至推算出算出u1和和f1(x1)为止，从而获得全过程的最优策略和指标函数最为止，从而获得全过程的最优策略和指标函数最优值。优值。4.2 动态规划应用之一动态规划应用之一资源分配问题资源分配问题 所谓资源分配问题就是将一种或若干种供应量有限的资源所谓资源分配问题就是将一种或若干种供应量有限的资源（如原材料、设备、资金、人力、能源等）分配给若干个使用（如原材料、设备、资金、人力、能源等）分配给若干个使用者，分

91、配方案使得目标函数达到最优。若只分配一种资源，其者，分配方案使得目标函数达到最优。若只分配一种资源，其总量为总量为a，用于投入，用于投入n个项目，则称之为一维资源分配问题；个项目，则称之为一维资源分配问题； 若资源多于一种，则称之为多维资源分配问题。本课程只若资源多于一种，则称之为多维资源分配问题。本课程只介绍一维资源分配问题。令介绍一维资源分配问题。令xj为分配于项目为分配于项目j的资源量，其收益的资源量，其收益函数为函数为gj(xj)，应该如何分配这种资源，使得这，应该如何分配这种资源，使得这n个项目的收益总个项目的收益总和最大？这个问题可写成静态数学规划模型：和最大？这个问题可写成静态数

92、学规划模型：上述模型可能是线性或非线性数学规划问题，但由于它的特殊上述模型可能是线性或非线性数学规划问题，但由于它的特殊性，也可以采用性，也可以采用DP的方法来求解。的方法来求解。应用动态规划方法求解一维资源分配问题的步骤：应用动态规划方法求解一维资源分配问题的步骤：（1）将上述问题的项目数（即变量个数）将上述问题的项目数（即变量个数n）作为）作为DP问题的阶问题的阶 段数；段数；（2）将上述问题中的变量（即每个项目分配到的资源量）将上述问题中的变量（即每个项目分配到的资源量xk） 作为作为DP问题的决策变量问题的决策变量uk ，等价于上述问题中的，等价于上述问题中的xk；（3）将每个阶段）将

93、每个阶段k可用的资源量作为状态变量可用的资源量作为状态变量xk 。经上述三个步骤的转换后，上述数学规划问题就变成了经上述三个步骤的转换后，上述数学规划问题就变成了DP问问题，可采用题，可采用DP方法求解。详见下图。方法求解。详见下图。 1 2 k n资源量资源量 ax1x2xkxnu1u2ukun显然，根据上述转换，有关系式显然，根据上述转换，有关系式x1=a, x2=x1u1, x3=x2u2, , xk=xk-1uk-1, , xn=xn-1un-1=x1(=a)(u1+u2+un-1)=un。其状态转移方程为：其状态转移方程为： xk+1=xkuk，1kn1；建立允许决策变量集合：建立允

94、许决策变量集合：Uk(xk)=uk 0ukxk；建立最优指标函数逆向推算方程：令建立最优指标函数逆向推算方程：令fk(xk)为以为以xk数量的可用资源数量的可用资源分配给第分配给第k个项目至第个项目至第n个项目所得到的最大总收益。根据最优化个项目所得到的最大总收益。根据最优化原理，有：原理，有：式中：式中：gk(uk)为向第为向第k个项目投入个项目投入u数量的资源所产生的收益，等数量的资源所产生的收益，等价于数学规划问题中的价于数学规划问题中的 gj(xj)。边界条件：边界条件：fn+1(xn+1)=0， fn(xn)= fn(un)= gn(un)。需要指出的是：当需要指出的是：当xk在在0

95、，a上连续变化时，计算机也无法对所上连续变化时，计算机也无法对所有的有的xk求解出求解出fk(xk)。因此，首先需要将可供分配的资源数离散化，。因此，首先需要将可供分配的资源数离散化，按照分割后的最小单位进行分配，即将按照分割后的最小单位进行分配，即将0，a分割成分割成m个等分个等分，令，令xk=0, , 2, , m(=a)。的大小可根据计算精度和计算的大小可根据计算精度和计算机容量来确定。说明详见机容量来确定。说明详见P65-68例例4.4（此题也可用整数规划求（此题也可用整数规划求解）。解）。4.3 动态规划应用之二动态规划应用之二生产库存问题生产库存问题采用采用P69的例的例4.5来说

96、明：某工厂生产某种产品有三个周期，开来说明：某工厂生产某种产品有三个周期，开始时的库存量为始时的库存量为0个单位（每个周期库存量不受限制），在每个个单位（每个周期库存量不受限制），在每个周期初生产周期初生产j个单位产品的成本为：个单位产品的成本为：每个周期内最后的库存量为每个周期内最后的库存量为j个单位，存贮费个单位，存贮费EIC(J)为为3j个单位，个单位，对应于各周期的产品需求量见下表。在满足每个周期产品需求量对应于各周期的产品需求量见下表。在满足每个周期产品需求量的前提下，如何确定每周期初的生产量，才能使得总费用（包括的前提下，如何确定每周期初的生产量，才能使得总费用（包括生产成本和存储

97、费）最小？生产成本和存储费）最小？周周 期期 k1 2 3需求量需求量Dk2 2 4解：采用解：采用DP方法求解生产库存问题，其步骤为：方法求解生产库存问题，其步骤为：（1）每一生产周期为一个决策阶段，）每一生产周期为一个决策阶段，K=1，2，3；每个周期初；每个周期初的生产量可根据本周期的需求量与上周期末的库存量来决定；的生产量可根据本周期的需求量与上周期末的库存量来决定；（2）当）当K=3，D3=4时，令上一周期末的库存量为时，令上一周期末的库存量为m，又因为要求，又因为要求最后一个周期（最后一个周期（K=3）的库存量为）的库存量为0，所以，最后一个周期，所以，最后一个周期（K=3）的最佳

98、生产量为：）的最佳生产量为：上述计算结果详见下表。上述计算结果详见下表。第第2周期末周期末库存量库存量 m201234本周期初的最本周期初的最优生产量优生产量x3(m2)43210本周期末的最本周期末的最优生产费优生产费f3(x3)403530250第三周期生产量与生产费用计算表第三周期生产量与生产费用计算表（3）当）当K=2，D=2时，要决定第二周期初的生产量时，要决定第二周期初的生产量x2(m)，使得第，使得第三周期初和第二周期初的生产费用之和以及与库存费之和最小。三周期初和第二周期初的生产费用之和以及与库存费之和最小。若上周期末的库存量为若上周期末的库存量为m，则第二周期初最多生产量是：

99、，则第二周期初最多生产量是：D2+D3-m。如果第二周期初的生产量为。如果第二周期初的生产量为z，则最优生产与库存决策的总费，则最优生产与库存决策的总费用为：用为：由于由于EIC2(m+z-D2)=3(m+z-D2)，且，且D2=2，故：，故：当当m=0时，时，2-0=2z2+4-0=6，则有：，则有：得得x2(0)=6，f2(x2(0)=62。当当m=1时，时，2-1=1z2+4-1=5，则有：，则有：得得x2(1)=5，f2(x2(1)=57。当当m=2时，时，2-2=0z2+4-2=4，则有：，则有：得得x2(2)=0，f2(x2(2)=40。当当m=3时，时，0z2+4-3=3，则有：

100、，则有：得得x2(3)=0，f2(x2(3)=38。当当m=4时，时，0z2+4-4=2，则有：，则有：得得x2(4)=0，f2(x2(4)=36。当当m=5时，时，0z2+4-5=1，则有：，则有：得得x2(5)=0，f2(x2(5)=34。当当m=6时，时，0z2+4-6=0，z=0，则有：，则有： f2(x2(6)=PC2(0)(=0)+EIC2(3)(=12)+f3(0)(=0)=12得得x2(6)=0，f2(x2(6)=12。第第1周期末周期末库存量库存量 m10123456本周期初的最优生本周期初的最优生产量产量x2(m1)6500000本周期末的最优生本周期末的最优生产费产费f2

101、(x2)62574038363412第二周期生产量与生产费用计算表第二周期生产量与生产费用计算表（4）当）当K=1，D1=2时，因为要求第一周期初的库存量时，因为要求第一周期初的库存量=0，故只，故只有有m=0一种情况，本周期最多可生产一种情况，本周期最多可生产D1+D2+D3-m=D1+D2+D3 =2+2+4=8，故，故Max(0, D-m)(=2)zD1+D2+D3 =2+2+4=8得得x1(0)=4，f1(x1(0)=86。获得第一周期生产。获得第一周期生产4个单位，由于第一个单位，由于第一周期末需求量为周期末需求量为2，则第一周期末库存量也为，则第一周期末库存量也为2；第二周期初库存

102、；第二周期初库存量为量为2的情况下，第二周期生产决策是的情况下，第二周期生产决策是x2(2)=0， f2(x2(2)=40；由；由于第二周期产品需求为于第二周期产品需求为2，故第二周期末没有库存；最后第三周，故第二周期末没有库存；最后第三周期由于产品需求为期由于产品需求为4，且本周期末库存量必须为，且本周期末库存量必须为0，故第三周期必，故第三周期必须生产须生产4个单位，计算结果可列表如下个单位，计算结果可列表如下生产周期生产周期123本周期生产量本周期生产量404本周期末库存量本周期末库存量200本周期生产成本本周期生产成本40040本周期库存成本本周期库存成本600本周期总成本本周期总成本

103、46040三个周期成本总和三个周期成本总和86可以看出第二周期整个不干活。可以看出第二周期整个不干活。4.4 动态规划应用之三动态规划应用之三任意两点任意两点 之间的最短路径计算之间的最短路径计算 求解两点之间最短路径问题属于阶段数确定的求解两点之间最短路径问题属于阶段数确定的DP问题，而问题，而任意两点之间最短路径问题可用求解阶段数不确定任意两点之间最短路径问题可用求解阶段数不确定DP问题的方问题的方法法策略迭代法解决问题，但解决的对象是任意两点之间有策略迭代法解决问题，但解决的对象是任意两点之间有连线的网络，这只有电信网络才有这种可能。连线的网络，这只有电信网络才有这种可能。4.4.1 策

104、略迭代法基本原理和步骤策略迭代法基本原理和步骤 令令f(i)表示从表示从i点出发到达点出发到达n点的最短距离，由最优化原理可点的最短距离，由最优化原理可知：知：式中：式中：Cik为为i点到点到j点连线上的属性物理量，如距离、时间、费用点连线上的属性物理量，如距离、时间、费用等。当等。当i到到j之间有连线时，之间有连线时，Cij为该连线上的属性物理量；当为该连线上的属性物理量；当i到到j之间没有连线时，之间没有连线时，Cij。 DP中的策略迭代法的基本步骤为：中的策略迭代法的基本步骤为：（1）根据先验知识或经验，给出一个不形成环的初始策略）根据先验知识或经验，给出一个不形成环的初始策略u0(i)

105、 =j, 表示从表示从i点出发下一个点是点出发下一个点是j，i、j=1, 2, , n-1，ij；（2）计算在这个策略下各点）计算在这个策略下各点i到固定点到固定点n的属性物理量（本问题的属性物理量（本问题 中专指距离）中专指距离）fk(i)=Ci, uk(i) +fkuk(i)，k=0, 1, 2, ; i=1, 2, , n-1。k为迭代次数；为迭代次数；（3）由指标函数）由指标函数fk(i)求解改进后的下一步新策略求解改进后的下一步新策略uk+1(i)， i=1, 2, , n-1，即：，即：uk+1(i)=MinCi,u+fk(uk(i), i=1, 2, , n-1;（4）重复第一、

106、二步，直至某）重复第一、二步，直至某k次迭代使得次迭代使得uk(i)=uk-1(i )，i=1, 2, , n-1为止，于是得到最优策略为止，于是得到最优策略fk(i)，i=1, 2, , n-1； 即从即从i点到点到n点的最短距离。点的最短距离。4.4.2 策略迭代法解的唯一性条件策略迭代法解的唯一性条件 唯一性定理：若初始策略唯一性定理：若初始策略u0(i ) 不构成回路，则以后各次不构成回路，则以后各次迭代所获得的策略迭代所获得的策略uk(i ) 也不构成回路，这样迭代一定是收敛也不构成回路，这样迭代一定是收敛的。的。采用采用P72-74的例的例4.6说明。说明。例例4.6 见下图，设有

107、见下图，设有1、2、3、4、5五个城市，各城市之间的距五个城市，各城市之间的距离示意在图上，试用策略迭代法求解离示意在图上，试用策略迭代法求解 i 城（城（i=1、2、3、4）到）到5城的最短距离和最短路径。城的最短距离和最短路径。232755510.5612345解解:（1）第一轮迭代：第一轮迭代：1）选取初始策略）选取初始策略u0(i)=5，4，5，3 即即u0(1)=5， u0(2)=4，u0(3)=5，u0(4)=3；2）计算采取策略）计算采取策略u0(i)时的指标函数值时的指标函数值f0(i)，即：，即：由于由于1、3两点都是一步直接到达两点都是一步直接到达5点，因此：点，因此：再计

108、算再计算2、4点：点：3）由）由f0(i)找出可以改进指标函数值的策略找出可以改进指标函数值的策略u1(i)，即将即将f0(i)代入：代入：从而求解出从而求解出u1(i)，即：，即：得：得： u1(1)=5，同理：，同理：得：得： u1(2)=3。依次类推。依次类推可得：可得： u1(3)=u1(4)= 5。 经第一轮迭代得：经第一轮迭代得： u1(i) =5，3，5，5。（2）第二轮迭代：）第二轮迭代：1）计算指标函数值）计算指标函数值f1(i)：2）根据）根据f1(i)推算推算u2(i)，得：，得：得得u2(1)=5同理可得：同理可得：u2(2)=3，u2(3)=4，u2(4)=5。所以，

109、经第一轮迭代所以，经第一轮迭代得：得：u2(i) =5，3，4，5。因为。因为u2(i) u1(i)，故需要，故需要进一步迭代计算。进一步迭代计算。（3）第三轮迭代：）第三轮迭代：1）由）由u2(i)计算计算f2(i), 可得：可得： f2(1)=2.0，f2(2)=5.0，f2(3)=4.0, f2(4)=4.5 2）由）由 f2(i)推算推算u3(i) ，可得：，可得： u3(1)=5，u3(2)=3，u3(3)=4， u3(4)=5，故，故u3(i)=5，3，4，5=u2(i) ，所以第三轮，所以第三轮的的 解即为最优解，其中最优策略为解即为最优解，其中最优策略为u*(i)=5，3，4，5， 根据最优策略可得最短距离和最短路径，如下表所示：根据最优策略可得最短距离和最短路径，如下表所示：最短路径最短路径最短距离最短距离最短路径最短路径最短距离最短距离 2 24.54.543