系统工程考试复习资料ppt课件

1、系统工程琥珀课后资源网系统工程概论系统工程概论系统工程定义系系 统统 定定 义义方 法 论1-1 1-1 系系 统统 的的 定定 义义系统工程概论系统工程概论1-2 1-2 系统工程的定义系统工程的定义系统工程定义系统工程定义系 统 定 义方 法 论0, 0305 . 1402212121xxxxxxx1x2O1020304010203040(3,4)(15,10)最优解X=(15,10)最优值Z=8540221xx305 . 121xxmax Z=3x1+4x2例例3.2.2动画演示动画演示006346321212121xxxxxxxx、246x1x2246最优解X=(3,1)最优值Z=5(

2、3,1)min Z=x1+2x2例例3.2.3动画演示动画演示006346321212121xxxxxxxx、246x1x2246有无穷多个最优解即具有多重解,通解为X23,1X11,3 01 ,)1 ()2() 1 (XXX 当=0.5时=(x1,x2)=0.5(1,3)+0.5(3,1)=(2,2) min Z=5x1+5x2例例3.2.4动画演示动画演示006346321212121xxxxxxxx、246x1x2246无界解(无最优解)max Z=x1+2x2例例3.2.5动画演示动画演示x1x2O10203040102030400,050305 .140221212121xxxxxx

3、xx5050无可行解即无最优解max Z=3x1+4x2例例3.2.6动画演示动画演示由以上例题可知，线性规由以上例题可知，线性规划的解有划的解有4种方式：种方式：1.有独一最优解有独一最优解(例例3.2.2例例3.2.3) 2.有多重解有多重解(例例3.2.4) 3.有无界解有无界解(例例3.2.5)4.无可行解无可行解(例例3.2.6) 1、2情形为有最优解，3、4情形为无最优解例例1-2 1-2 知知 ，求其可达矩阵。，求其可达矩阵。解解: :0100100101001100A1100110101101101AI11011101111111011100110101101101110011

4、0101101101)AI (2系统工程概论系统工程概论系统模型系 统 分 析系统建模方法系统建模方法建模方法之二：构造模型解析法建模方法之二：构造模型解析法223)AI (110111011111110111001101011011011101110111111101)AI ()AI ()AI (1101110111111101)AI (M2系统工程概论系统工程概论系统模型系 统 分 析系统建模方法系统建模方法建模方法之二：构造模型解析法建模方法之二：构造模型解析法解：做区域划分表，见下表。解：做区域划分表，见下表。i R(ei) A(ei) R(ei)A(ei)1 1 1,2,7 12 1

5、,2 2,7 23 3,4,5,6 3 34 4,5,6 3,4,6 4,65 5 3,4,5,6 5 6 4,5,6 3,4,6 4,67 1,2,7 7 7由表由表1.1，可达性矩阵，可达性矩阵M可划分为：可划分为：例例1-3 对可达性矩阵进展区域划分。对可达性矩阵进展区域划分。10000110111000001000001110000111100000001100000017654321M1 2 3 4 5 6 77216543212e ,e ,e,e ,e ,e ,eP,P)S( 系统工程概论系统工程概论系统模型系 统 分 析系统建模方法系统建模方法建模方法之二：构造模型解析法建模方法

6、之二：构造模型解析法 据此对据此对M进展初等变换进展初等变换行和列的顺行和列的顺序变卦，化成对角分块矩阵的方式。序变卦，化成对角分块矩阵的方式。 子系统子系统 子系统子系统 子系统子系统 子系统子系统11101100111100100111011117216543M3 4 5 6 1 2 7系统工程概论系统工程概论系统模型系 统 分 析系统建模方法系统建模方法建模方法之二：构造模型解析法建模方法之二：构造模型解析法2) 2) 级别划分级别划分 级别划分是在每一个区域内进展的。级别划分是在每一个区域内进展的。假设对于假设对于 ，有，有那么那么 为最上级单元。为最上级单元。Sei)e (A)e (

7、R)e (Riiiie系统工程概论系统工程概论系统模型系 统 分 析系统建模方法系统建模方法建模方法之二：构造模型解析法建模方法之二：构造模型解析法在一个多级构造的最上级的单元，没有更高的级可达，在一个多级构造的最上级的单元，没有更高的级可达，它的可达集只包括它本身和与它同级的强衔接单元。而它的可达集只包括它本身和与它同级的强衔接单元。而它的先行集那么包括它本身、可以到达它的下级单元以及它的先行集那么包括它本身、可以到达它的下级单元以及与它同级的强衔接单元。故而与它同级的强衔接单元。故而 ，当按上，当按上述条件找到最上级单元后，把他们暂时去掉，再用同样的述条件找到最上级单元后，把他们暂时去掉，

8、再用同样的方法求出次一级单元，以此类推。那么系统方法求出次一级单元，以此类推。那么系统S中的一个区域中的一个区域P的级别划分可用下式表示。的级别划分可用下式表示。)e (R)e (A)e (Riii系统工程概论系统工程概论系统模型系 统 分 析系统建模方法系统建模方法建模方法之二：构造模型解析法建模方法之二：构造模型解析法L,L,L)P(l213 接着对上面的例子中的接着对上面的例子中的P1,P2进展级别划分：进展级别划分：系统工程概论系统工程概论系统模型系 统 分 析系统建模方法系统建模方法建模方法之二：构造模型解析法建模方法之二：构造模型解析法 i R(ei) A(ei) R(ei)A(e

9、i)l3 3 3,4,5,6 3 3l2 4 4,5,6 3,4,6 4,6l1 5 5 3,4,5,6 5 l2 6 4,5,6 3,4,6 4,6l1:e5 l2 :e4,e6 l3:e3即：即：同样对同样对P2有：有：e,e,e)P(72123 e,e ,e,e)P(364513 接下来将接下来将M按级别划分的结果进展变换，得：按级别划分的结果进展变换，得：系统工程概论系统工程概论系统模型系 统 分 析系统建模方法系统建模方法建模方法之二：构造模型解析法建模方法之二：构造模型解析法11101100111110111011100017213645M5 4 6 3 1 2 74、 建立构造矩

10、阵建立构造矩阵1浓缩阵浓缩阵 系统中的恣意两个单元系统中的恣意两个单元ei和和ej假设在同一个最大回路集假设在同一个最大回路集中，那么可达性矩阵中，那么可达性矩阵M相应的相应的行和列上的元素完全一样。可行和列上的元素完全一样。可将这两个单元当作一个系统单将这两个单元当作一个系统单元对待，从而可以削减相应的元对待，从而可以削减相应的行和列，得到的可达性矩阵行和列，得到的可达性矩阵M叫做叫做M的浓缩阵。例中的浓缩阵。例中e4 ,e6相应的行和列元素完相应的行和列元素完全一样，将全一样，将e6除去得浓缩阵除去得浓缩阵M。 5 4 3 1 2 7 5 4 3 1 2 7 5 1 0 0 5 1 0 0

11、 4 1 1 0 4 1 1 0 0 0M= 3 1 1 1M= 3 1 1 1 1 1 1 0 01 0 0 2 2 0 1 1 00 1 1 0 7 7 1 1 11 1 1系统工程概论系统工程概论系统模型系 统 分 析系统建模方法系统建模方法建模方法之二：构造模型解析法建模方法之二：构造模型解析法 (2)从属阵从属阵(记为记为M) M=MI 对上面的例子，对上面的例子，M可写为：可写为： 5 4 3 1 2 7M=MI= 5 0 0 0 4 1 0 0 0 3 1 1 0 1 0 0 0 2 0 1 0 0 7 1 1 0 从从M中先找出一、二级之间的关系，中先找出一、二级之间的关系，m

12、45=1，阐明阐明e4 e5，然后去掉，然后去掉e5所在的行和列，在找出第二所在的行和列，在找出第二级与第三级的关系，级与第三级的关系， m34=1 ，那么有，那么有e3 e4。系统工程概论系统工程概论系统模型系 统 分 析系统建模方法系统建模方法建模方法之二：构造模型解析法建模方法之二：构造模型解析法 同样，在区域同样，在区域P2中有，中有， m21=1，e2 e1 m72=1，e7 e2 由此可得，构造矩阵由此可得，构造矩阵E 5 4 3 1 2 7 E=5 0 0 0 4 1 0 0 0 3 0 1 0 1 0 0 0 2 0 1 0 0 7 0 1 0 根据根据E，可以绘制系统多层次构

13、造图如右上，可以绘制系统多层次构造图如右上，1574,632系统工程概论系统工程概论系统模型系 统 分 析系统建模方法系统建模方法建模方法之二：构造模型解析法建模方法之二：构造模型解析法系统工程概论系统工程概论系统模型系 统 分 析系统建模方法系统建模方法建模方法之二：构造模型解析法建模方法之二：构造模型解析法构造模型解析法的建模步骤：构造模型解析法的建模步骤：小结：写出邻接矩阵写出邻接矩阵A;由由A推出可达性矩阵推出可达性矩阵M=(I A)n;各要素的级别划分各要素的级别划分 a)划分区域划分区域 b)在区域内进展级别划分在区域内进展级别划分 c)按划分结果对按划分结果对M进展初等变换进展初

14、等变换建立构造矩阵建立构造矩阵 a)由由M推出浓缩阵推出浓缩阵M b)由由M推出从属阵推出从属阵MM-I c)由由M推出构造矩阵推出构造矩阵E5. 由由E画出层次构造图。画出层次构造图。m212P,P,P)S( L,L,L)P(l213 单纯形计算方法单纯形计算方法(Simplex Method)是先求出一个初始是先求出一个初始基可行解并判别它能否最优，假设不是最优，再换一个基基可行解并判别它能否最优，假设不是最优，再换一个基可行解并判别，直到得出最优解或无最优解。它是一种逐可行解并判别，直到得出最优解或无最优解。它是一种逐渐逼近最优解的迭代方法。渐逼近最优解的迭代方法。 当系数矩阵当系数矩阵

15、A中可以察看得到一个可行基时通常是中可以察看得到一个可行基时通常是一个单位矩阵或一个单位矩阵或m个线性无关的单位向量组成的矩阵，个线性无关的单位向量组成的矩阵，可以经过解线性方程组求得根本可行解。可以经过解线性方程组求得根本可行解。【例【例3.2.8】用单纯形法求以下线性规划的最优解】用单纯形法求以下线性规划的最优解12121212maxZ3x4x2xx40 x3x30 x ,x0系统工程概论系统工程概论线线 性性 规规 划划LPLP的数学模型的数学模型规范型规范型图解法图解法单纯形法单纯形法人工变量法人工变量法【解】化为规范型，参与松驰变量【解】化为规范型，参与松驰变量x3、x4那么规范型为

16、那么规范型为121231241234m ax Z3x4x2xxx40 x3xx30 x , x , x , x0系数矩阵系数矩阵2110A1301110B01rB1=2，B1是一个初始基是一个初始基,x3、x4为基变量，为基变量，x1、x2为非基变量，令为非基变量，令x1=0、x2=0由约束方程知由约束方程知x3=40、x4=30得到初始根本可行解得到初始根本可行解X(1)=(0,0,40,30)T 系统工程概论系统工程概论线线 性性 规规 划划LPLP的数学模型的数学模型规范型规范型图解法图解法单纯形法单纯形法人工变量法人工变量法以上得到的一组基可行解是不是最优解，可以从目的函以上得到的一组

17、基可行解是不是最优解，可以从目的函数中的系数看出。目的函数数中的系数看出。目的函数 Z=3x1+4x2中中x1的系数大于的系数大于零，假设零，假设x1为一正数，那么为一正数，那么Z的值就会增大，同样假设的值就会增大，同样假设x2不为零为一正数，也能使不为零为一正数，也能使Z的值增大；因此只需目的函数的值增大；因此只需目的函数中非基变量的系数大于零，那么目的函数就没有到达最中非基变量的系数大于零，那么目的函数就没有到达最大值，即没有找到最优解，判别线性规划问题能否到达大值，即没有找到最优解，判别线性规划问题能否到达最优解的数称为检验数，记作最优解的数称为检验数，记作j , j=1,2,n。 本例

18、中本例中1=3,2=4,3=0,4=0.参看表参看表3-1a。 最优解判别规范最优解判别规范 当一切检验数当一切检验数j0j=1，n时，根时，根本可行解为最优解。本可行解为最优解。 当目的函数中有基变量当目的函数中有基变量xi时，利用约束条件将目的函数中时，利用约束条件将目的函数中的的xi消去即可求出检验数。消去即可求出检验数。 系统工程概论系统工程概论线线 性性 规规 划划LPLP的数学模型的数学模型规范型规范型图解法图解法单纯形法单纯形法人工变量法人工变量法进基列出基行b i / a i 2，ai20i表3-1(a)XBx1x2x3x4bx3211040 x4130130j3400 (b)

19、x3x4j (c)x1 x2 j 基变量11018001/301/3105/311/330405/304/330103/51/518011/52/540011将3化为1乘以1/3后得到LPLP的数学模型的数学模型规范型规范型图解法图解法单纯形法单纯形法人工变量法人工变量法动画演示动画演示单纯形法全过程的计算，可以用列表的方法计算更为简单纯形法全过程的计算，可以用列表的方法计算更为简约，这种表格称为单纯形表表约，这种表格称为单纯形表表3-1。计算阐明：计算阐明：1.求初始基可行解，列出初始单纯形表，求出检验数。其求初始基可行解，列出初始单纯形表，求出检验数。其中基变量的检验数必为零；中基变量的检

20、验数必为零； 2.判别：判别： a假设假设jj，n得到最优解；得到最优解； b某个某个k0且且aiki=1，2,m那么线性规那么线性规划具有无界解。划具有无界解。 c假设存在假设存在k0且且aik (i=1,m)不全非正，那么不全非正，那么进展换基；进展换基；系统工程概论系统工程概论线线 性性 规规 划划LPLP的数学模型的数学模型规范型规范型图解法图解法单纯形法单纯形法人工变量法人工变量法3.换基：换基：a设设k0, xk为进基变量，求最小比值：为进基变量，求最小比值：iLikikbmina0a 第个比值最小第个比值最小 ，选最小比值对应行的基变量为出基，选最小比值对应行的基变量为出基变量，

21、假设有一样最小比值，那么任选一个。变量，假设有一样最小比值，那么任选一个。aLk为主为主元素；元素； (b求新的基可行解：用初等行变换方法将求新的基可行解：用初等行变换方法将aik 化为化为1, k列其它元素化为零包括检验数行得到新的可行基列其它元素化为零包括检验数行得到新的可行基及根本可行解，再判别能否得到最优解。及根本可行解，再判别能否得到最优解。系统工程概论系统工程概论线线 性性 规规 划划LPLP的数学模型的数学模型规范型规范型图解法图解法单纯形法单纯形法人工变量法人工变量法【例【例3.2.9】 用单纯形法求解用单纯形法求解123maxZx2xx1231231232x3x2x151xx

22、5x203xxx0、 、【解】将数学模型化为规范方式：【解】将数学模型化为规范方式：123maxZx2xx12341235j2x3x2xx151xx5xx203x0,j1,2,5不难看出不难看出x4、x5可作为初始基变量，单纯法计算结果如可作为初始基变量，单纯法计算结果如表表 3-2所示所示 。 系统工程概论系统工程概论线线 性性 规规 划划LPLP的数学模型的数学模型规范型规范型图解法图解法单纯形法单纯形法人工变量法人工变量法表3-2Cj12100bCBXBx1x2x3x4x50 x423210150 x51/3150120j12100 0 x42x2j 1x1 2x2 j 1/315012

23、0301713751/309022025601017/31/31250128/91/92/335/30098/91/97/3线线 性性 规规 划划LPLP的数学模型的数学模型规范型规范型图解法图解法单纯形法单纯形法人工变量法人工变量法动画演示动画演示什么是最大流？什么是最大流？4844122679容量：在某时期内弧容量：在某时期内弧(i，j)上的最大经过才干。记为上的最大经过才干。记为C (i，j)或或Cij 在上图中，在上图中，C12=4，C138，C234等，怎样安等，怎样安排运输方案，才干使在某一时期内从排运输方案，才干使在某一时期内从v1运到运到v6的物资最多，的物资最多，这样的问题就

24、是最大流问题，这样的问题就是最大流问题，网络中一切流来源于一网络中一切流来源于一个叫做发点的节点源个叫做发点的节点源 一切的流终止于一个叫做收点的节点一切的流终止于一个叫做收点的节点其他一切的节点叫做中间点转运点其他一切的节点叫做中间点转运点 经过每一条弧的流只允许沿着弧的箭头方向流动经过每一条弧的流只允许沿着弧的箭头方向流动目的是使得从发点到收点的总流量最大目的是使得从发点到收点的总流量最大系统工程概论系统工程概论图图 与与 网网 络络最短路问题最短路问题最大流问题最大流问题根本概念根本概念流量：弧流量：弧(i，j)的实践经过量，记为的实践经过量，记为f (i，j)或或f ij可行流：假设可

25、行流：假设f ij满足：满足： 1.对于一切弧对于一切弧(i，j)有有0f ijCij 2.对于发点对于发点vs有：有：vffjiissj3.对于收点对于收点vt有：有：vffijtjit那么称流量集合那么称流量集合f ij为网络的一个可行流，简记为为网络的一个可行流，简记为 f , v称为可行流的流量或值，记为称为可行流的流量或值，记为v(f).以下假设网络是一个简单连通图。以下假设网络是一个简单连通图。4.对于中间点点对于中间点点vm有：有：ijmjimff系统工程概论系统工程概论图图 与与 网网 络络最短路问题最短路问题最大流问题最大流问题根本概念根本概念链：从发点到收点的一条道路弧的方

26、向不一定都同向称链：从发点到收点的一条道路弧的方向不一定都同向称为链。从发点到收点的方向规定为链的方向。为链。从发点到收点的方向规定为链的方向。前向弧：与连的方向一样的弧称为前向弧。前向弧：与连的方向一样的弧称为前向弧。后向弧：与连的方向相反的弧称为后向弧。后向弧：与连的方向相反的弧称为后向弧。增广链增广链 设设 f 是一个可行流，假设存在一条从是一个可行流，假设存在一条从vs到到vt的链，满足：的链，满足：1.一切前向弧上一切前向弧上fij0那么该链称为增广链那么该链称为增广链前向弧前向弧后向弧后向弧8446952346容量容量流量流量想一想，这想一想，这是一条增广是一条增广链吗？链吗？系统

27、工程概论系统工程概论图图 与与 网网 络络最短路问题最短路问题最大流问题最大流问题根本概念根本概念【定理】设网络【定理】设网络G的一个可行流的一个可行流f，假设存在一条从，假设存在一条从vs到到vt的增的增广链，那么就可改良一个值更大的可行流广链，那么就可改良一个值更大的可行流f1，并且，并且val f1val f【证】设【证】设val fv 121212min C(i, j)f(i, j) | (i, j)min f(i, j) | (i, j)min,|, 令令 是是前前向向弧弧是是后后向向弧弧无无前前向向弧弧时时无无后后向向弧弧对改良的可行流对改良的可行流f1 ：1f(i,j)(i,j)

28、f (i,j)f(i,j)(i,j)f(i,j)(i,j) 不不在在增增广广链链上上是是前前向向弧弧是是后后向向弧弧1v(f )v(f)v(f) 则有则有系统工程概论系统工程概论图图 与与 网网 络络最短路问题最短路问题最大流问题最大流问题根本概念根本概念最大流的标号算法最大流的标号算法步骤步骤 1. 找出第一个可行流，例如一切弧的流量找出第一个可行流，例如一切弧的流量fij =0 2. 用标号的方法找一条增广链用标号的方法找一条增广链 A1：发点标号：发点标号， A2：选一个点：选一个点 vi 已标号并且另一端未标号的弧沿着某已标号并且另一端未标号的弧沿着某条链向收点检查：条链向收点检查：

29、假设弧的方向向前并且有假设弧的方向向前并且有fij0，那么，那么vj标号标号fji)当收点不能得到标号时，阐明不存在增广链，计算终了。当收点不能得到标号时，阐明不存在增广链，计算终了。当收点已得到标号时，阐明已找到增广链。当收点已得到标号时，阐明已找到增广链。【定理】可行流是最大流当且仅当不存在发点到收点的增广链【定理】可行流是最大流当且仅当不存在发点到收点的增广链系统工程概论系统工程概论图图 与与 网网 络络最短路问题最短路问题最大流问题最大流问题根本概念根本概念4. 调整流量调整流量 是后向弧是前向弧不在增广链上),(),(),(),(),(),(),(1jijifjijifjijifji

30、f得到新的可行流，去掉一切标号，从发点重新标号寻得到新的可行流，去掉一切标号，从发点重新标号寻觅增广链，直到收点不能标号为止。觅增广链，直到收点不能标号为止。3. 根据根据vi 的第一个标号反向跟踪得到一条增广链；的第一个标号反向跟踪得到一条增广链； 根据根据vi 的第二个标号求最小值得到调整量的第二个标号求最小值得到调整量系统工程概论系统工程概论图图 与与 网网 络络最短路问题最短路问题最大流问题最大流问题根本概念根本概念 684412267942202222046217【例】求以下图【例】求以下图v1 到到v6 的最大流及最大流量的最大流及最大流量【解】【解】1. 经过察看得到初始可行流经

31、过察看得到初始可行流2. 标号标号3. 得到增广链得到增广链系统工程概论系统工程概论图图 与与 网网 络络最短路问题最短路问题最大流问题最大流问题根本概念根本概念 68441226794211322304223重新标号得到增广链重新标号得到增广链 4.求调整量求调整量 5.调整可行流调整可行流 去掉一切标号，去掉一切标号，17 , 1 , 2 , 6 ,min 684412267942202222046217系统工程概论系统工程概论图图 与与 网网 络络最短路问题最短路问题最大流问题最大流问题根本概念根本概念68441226796411322306 求调整量求调整量 调整可行流调整可行流 去掉

32、一切标号，重新标号去掉一切标号，重新标号5标号不能继续进展，阐明不存在从发点到收点的增广链，标号不能继续进展，阐明不存在从发点到收点的增广链，得到最大流得到最大流.最大流量最大流量 v=6+3=9123 , 2 , 2 ,min系统工程概论系统工程概论图图 与与 网网 络络最短路问题最短路问题最大流问题最大流问题根本概念根本概念无向图最大流标号算法无向图最大流标号算法无向图不存在前向弧，可以了解为一切弧都是前向弧，对无向图不存在前向弧，可以了解为一切弧都是前向弧，对一端一端vi已标号另一端已标号另一端vj未标号的边只需满足未标号的边只需满足 Cijfij0 那么那么vj标号就可标号标号就可标号

33、Cijfij【例】求以下图【例】求以下图v1到那么到那么v7标的最大流标的最大流712920851486913161061082376513013239932系统工程概论系统工程概论图图 与与 网网 络络最短路问题最短路问题最大流问题最大流问题根本概念根本概念71292085148691316126108437671321537711712920851486913161271084376813316V=2910566系统工程概论系统工程概论图图 与与 网网 络络最短路问题最短路问题最大流问题最大流问题根本概念根本概念截集截集 将图将图GV，E的点集分割成两部分的点集分割成两部分_111s1t1

34、1vVvVVVV V 及及，则则箭箭尾尾在在箭箭头头在在的的弧弧集集合合（， 并且、1_1VV称为一个截集，截集中一切弧的容量之和称为截集的截量。称为一个截集，截集中一切弧的容量之和称为截集的截量。68441226796411322306以下图所示的截集以下图所示的截集为为 11(V ,V )(1,2),(3,4),(3,5) 11C(V ,V )62210 截截量量系统工程概论系统工程概论图图 与与 网网 络络最短路问题最短路问题最大流问题最大流问题根本概念根本概念68441226796401322106又如以下图所示的截集又如以下图所示的截集为为)6 , 5()4 , 5(),4 , 3(

35、),4 , 2(),(11，VV219624),(11VVC截量上图所示的截集为上图所示的截集为)5 , 3(),4 , 3(),5 , 2(),4 , 2(),(11VV92214),(11VVC截量一切截量中此截量最小且等于最大流量，此截集称为最小截集。一切截量中此截量最小且等于最大流量，此截集称为最小截集。【定理】最大流量等于最小截集的截量。【定理】最大流量等于最小截集的截量。系统工程概论系统工程概论图图 与与 网网 络络最短路问题最短路问题最大流问题最大流问题根本概念根本概念系统工程概论系统工程概论非非 线线 性性 规规 划划无约束无约束有约束有约束单变量寻优单变量寻优多变量寻优多变量

36、寻优 (1) (1) 梯度和梯度方向梯度和梯度方向 一个非线性函数一个非线性函数f(x)f(x)的梯度定的梯度定义义 最速下降法亦称梯度法最速下降法亦称梯度法Gradient MethodGradient Method，是，是由著名数学家柯西在由著名数学家柯西在18471847年提出来的，是一种最古老的年提出来的，是一种最古老的下降算法。最速下降法的根本思想是使目的函数沿其值下降算法。最速下降法的根本思想是使目的函数沿其值下降最快的方向前进，逐渐走向最优点。下降最快的方向前进，逐渐走向最优点。Tnxfxfxfxfxf,)(21系统工程概论系统工程概论非非 线线 性性 规规 划划无约束无约束有约

37、束有约束单变量寻优单变量寻优多变量寻优多变量寻优 最速下降法是以负梯度方向作为搜索最速下降法是以负梯度方向作为搜索方向的，梯度方向的单位向量为方向的，梯度方向的单位向量为 )()()(xfPxfxfs2 2最优梯度最优梯度 由于函数沿负梯度方向下降最快，所以取由于函数沿负梯度方向下降最快，所以取f fx x为迭代方向，设为迭代方向，设xkxk为迭代点，那么迭代公式为为迭代点，那么迭代公式为xk +1= xkxk +1= xk k k f fx x 这样，只需步长因子这样，只需步长因子kk知，就能求出下一个迭代点知，就能求出下一个迭代点xk xk +1+1，且，且f fx k+1 x k+1 f

38、 fx k x k ，如此反复进展，直到找，如此反复进展，直到找到最优点。到最优点。kkkkSxxfxfxx)()(1为步长 Sk Sk为从为从xkxk出发的单位梯度方向，称为搜索方出发的单位梯度方向，称为搜索方向。向。迭代公式可表示为迭代公式可表示为系统工程概论系统工程概论非非 线线 性性 规规 划划无约束无约束有约束有约束单变量寻优单变量寻优多变量寻优多变量寻优系统工程概论系统工程概论非非 线线 性性 规规 划划无约束无约束有约束有约束单变量寻优单变量寻优多变量寻优多变量寻优(3) (3) 最速下降法的根本概念最速下降法的根本概念 沿着负梯度方向选择步长时搜索步数最小的方法沿着负梯度方向选

39、择步长时搜索步数最小的方法称为最速下降法。这种方法每步需求计算最优步长，称为最速下降法。这种方法每步需求计算最优步长，使每走一步目的函数下降最多到达极值。使每走一步目的函数下降最多到达极值。)()(1kkkkSxfxf 沿着沿着SkSk的方向求的方向求minf(xk+1)minf(xk+1)时的步长时的步长k k，求最优步长时，是对函数求最优步长时，是对函数f fx k+1 x k+1 求极值，求极值，步长步长k k为变量。为变量。系统工程概论系统工程概论非非 线线 性性 规规 划划无约束无约束有约束有约束单变量寻优单变量寻优多变量寻优多变量寻优 k k的选取方法：的选取方法：1 1选择一个固

40、定值选择一个固定值 ，或选一系列逐渐见效的可，或选一系列逐渐见效的可变值；变值；2 2沿梯度方向找函数的一个极小值点，即沿沿梯度方向找函数的一个极小值点，即沿sk sk 方向求使得方向求使得f(x)f(x)最小的最小的 k k。令。令kkdf (xs )0d 求得求得k。系统工程概论系统工程概论非非 线线 性性 规规 划划无约束无约束有约束有约束单变量寻优单变量寻优多变量寻优多变量寻优检验能否满足收敛性判别准那么检验能否满足收敛性判别准那么()kf x假设满足，迭代停顿得到点假设满足，迭代停顿得到点x*=xk，否那么进入，否那么进入()0kkkkdf xdd，求得计算计算1kkkkxxd1kk转到转到(4) 最速下降法的步骤：最速下降法的步骤：任选任选0,0,0nxEk选择允许误差令；计算负梯度计算负梯度()()