系统工程考试复习资料学习教案

1、会计学1系统工程考试系统工程考试(kosh)复习资料复习资料第一页，共52页。0, 0305 . 1402212121xxxxxxx1x2O1020304010203040(3,4)(15,10)最优解X=(15,10)最优值Z=8540221xx305 . 121xxmax Z=3x1+4x2例例动画演示动画演示(ynsh)第2页/共52页第二页，共52页。006346321212121xxxxxxxx、246x1x2246最优解X=(3,1)最优值Z=5(3,1)min Z=x1+2x2例例动画演示动画演示(ynsh)第3页/共52页第三页，共52页。006346321212121xxxx

2、xxxx、246x1x2246有无穷多个(du )最优解即具有多重解,通解为X（2）（3,1）X（1）（1,3） 01 ,)1 ()2() 1 (XXX 当=0.5时=(x1,x2)=0.5(1,3)+0.5(3,1)=(2,2) min Z=5x1+5x2例例动画演示动画演示(ynsh)第4页/共52页第四页，共52页。006346321212121xxxxxxxx、246x1x2246无界解(无最优解)max Z=x1+2x2例例动画演示动画演示(ynsh)第5页/共52页第五页，共52页。x1x2O10203040102030400,050305 .140221212121xxxxxxx

3、x5050无可行(kxng)解即无最优解max Z=3x1+4x2例例动画演示动画演示(ynsh)第6页/共52页第六页，共52页。由以上例题由以上例题(lt)可知，线性可知，线性规划的解有规划的解有4种形式：种形式：1.有唯一有唯一(wi y)最优解最优解(例例例例 2.有多重解有多重解(例例 3.有无有无(yu w)界解界解(例例4.无可行解无可行解(例例 1、2情形为有最优解，情形为有最优解，3、4情形为无最优解情形为无最优解第7页/共52页第七页，共52页。0100100101001100A1100110101101101AI110111011111110111001101011011

4、011100110101101101)AI (2系统工程概论系统工程概论(giln)(giln)系统(xtng)模型系 统 分 析系统建模方法系统建模方法建模方法之二：结构模型解析法建模方法之二：结构模型解析法第8页/共52页第八页，共52页。223)AI (110111011111110111001101011011011101110111111101)AI ()AI ()AI (1101110111111101)AI (M2系统工程概论系统工程概论(giln)(giln)系统(xtng)模型系 统 分 析系统系统(xtng)建模方法建模方法建模方法之二：结构模型解析法建模方法之二：结构模型

5、解析法第9页/共52页第九页，共52页。例例1-3 对可达性矩阵进行区域对可达性矩阵进行区域(qy)划分划分。10000110111000001000001110000111100000001100000017654321M1 2 3 4 5 6 77216543212e ,e ,e,e ,e ,e ,eP,P)S( 系统工程概论系统工程概论(giln)(giln)系统模型系 统 分 析系统建模方法系统建模方法建模方法之二：结构模型解析法建模方法之二：结构模型解析法第10页/共52页第十页，共52页。11101100111100100111011117216543M3 4 5 6 1 2 7系

6、统工程概论系统工程概论(giln)(giln)系统(xtng)模型系 统 分 析系统建模方法系统建模方法建模方法之二：结构模型解析法建模方法之二：结构模型解析法第11页/共52页第十一页，共52页。Sei)e (A)e (R)e (Riiiie系统工程概论系统工程概论(giln)(giln)系统(xtng)模型系 统 分 析系统建模方法系统建模方法建模方法之二：结构模型解析法建模方法之二：结构模型解析法第12页/共52页第十二页，共52页。)e (R)e (A)e (Riii系统工程概论系统工程概论(giln)(giln)系统(xtng)模型系 统 分 析系统建模方法系统建模方法建模方法之二：

7、结构模型解析法建模方法之二：结构模型解析法L,L,L)P(l213 第13页/共52页第十三页，共52页。系统工程概论系统工程概论(giln)(giln)系统(xtng)模型系 统 分 析系统建模方法系统建模方法建模方法之二：结构模型解析法建模方法之二：结构模型解析法 i R(ei) A(ei) R(ei)A(ei)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

8、 第14页/共52页第十四页，共52页。系统工程概论系统工程概论(giln)(giln)系统(xtng)模型系 统 分 析系统建模方法系统建模方法建模方法之二：结构模型解析法建模方法之二：结构模型解析法11101100111110111011100017213645M5 4 6 3 1 2 7第15页/共52页第十五页，共52页。 5 4 3 1 2 7 5 4 3 1 2 7 5 1 0 05 1 0 0 4 1 1 0 04 1 1 0 0M = 3 1 1 1= 3 1 1 1 1 1 0 0 2 0 1 1 0 7 1 1 1系统工程概论系统工程概论(giln)(giln)系统(xtn

9、g)模型系 统 分 析系统建模方法系统建模方法建模方法之二：结构模型解析法建模方法之二：结构模型解析法第16页/共52页第十六页，共52页。系统工程概论系统工程概论(giln)(giln)系统(xtng)模型系 统 分 析系统建模方法系统建模方法建模方法之二：结构模型解析法建模方法之二：结构模型解析法第17页/共52页第十七页，共52页。1574,632系统工程概论系统工程概论(giln)(giln)系统(xtng)模型系 统 分 析系统建模方法系统建模方法建模方法之二：结构模型解析法建模方法之二：结构模型解析法第18页/共52页第十八页，共52页。系统工程概论系统工程概论(giln)(gil

10、n)系统(xtng)模型系 统 分 析系统系统(xtng)建模方法建模方法建模方法之二：结构模型解析法建模方法之二：结构模型解析法结构模型解析法的建模步骤：结构模型解析法的建模步骤：小结：1.写出邻接矩阵写出邻接矩阵A;2.由由A推出可达性矩阵推出可达性矩阵M=(I A)n;3.各要素的级别划分各要素的级别划分 a)划分区域划分区域 b)在区域内进行级别划分在区域内进行级别划分 c)按划分结果对按划分结果对M进行初等变换进行初等变换4.建立结构矩阵建立结构矩阵 a)由由M推出浓缩阵推出浓缩阵M b)由由M推出从属阵推出从属阵MM-I c)由由M推出结构矩阵推出结构矩阵E5. 由由E画出层次结构

11、图。画出层次结构图。m212P,P,P)S( L,L,L)P(l213 第19页/共52页第十九页，共52页。 单纯形计算方法单纯形计算方法(Simplex Method)是先求出一个初始是先求出一个初始(ch sh)基基可行解并判断它是否最优，若不是最优，再换一个基可行解并判断可行解并判断它是否最优，若不是最优，再换一个基可行解并判断，直到得出最优解或无最优解。它是一种逐步逼近最优解的迭代方，直到得出最优解或无最优解。它是一种逐步逼近最优解的迭代方法。法。 当系数矩阵当系数矩阵A中可以观察得到一个可行基时（通常是一个单位矩中可以观察得到一个可行基时（通常是一个单位矩阵或阵或m个线性无关的单位

12、向量组成的矩阵），可以通过解线性方程个线性无关的单位向量组成的矩阵），可以通过解线性方程组求得基本可行解。组求得基本可行解。【例用单纯形法求下列线性规划的最优解【例用单纯形法求下列线性规划的最优解12121212maxZ3x4x2xx40 x3x30 x ,x0系统工程概论系统工程概论(giln)(giln)线线 性性 规规 划划LPLP的数学模型的数学模型标准型标准型图解法图解法单纯形法单纯形法人工人工(rngng)(rngng)变量法变量法第20页/共52页第二十页，共52页。【解】化为标准型，加入【解】化为标准型，加入(jir)松驰变量松驰变量x3、x4则标准型为则标准型为1212312

13、41234m ax Z3x4x2xxx40 x3xx30 x , x , x , x0系数系数(xsh)矩阵矩阵2110A1301110B01r（B1）=2，B1是一个初始是一个初始(ch sh)基基,x3、x4为基变量，为基变量，x1、x2为非基变量，令为非基变量，令x1=0、x2=0由约束方程知由约束方程知x3=40、x4=30得得到初始到初始(ch sh)基本可行解基本可行解X(1)=(0,0,40,30)T 系统工程概论系统工程概论线线 性性 规规 划划LPLP的数学模型的数学模型标准型标准型图解法图解法单纯形法单纯形法人工变量法人工变量法第21页/共52页第二十一页，共52页。以上得

14、到的一组基可行解是不是最优解，可以从目标函数中的以上得到的一组基可行解是不是最优解，可以从目标函数中的系数看出。目标函数系数看出。目标函数 Z=3x1+4x2中中x1的系数大于零，如果的系数大于零，如果x1为为一正数，则一正数，则Z的值就会增大，同样若的值就会增大，同样若x2不为零为一正数，也能不为零为一正数，也能使使Z的值增大；因此只要目标函数中非基变量的系数大于零，的值增大；因此只要目标函数中非基变量的系数大于零，那么目标函数就没有达到那么目标函数就没有达到(d do)最大值，即没有找到最优解最大值，即没有找到最优解，判别线性规划问题是否达到，判别线性规划问题是否达到(d do)最优解的数

15、称为检验数最优解的数称为检验数，记作，记作j , j=1,2,n。 本例中本例中1=3,2=4,3=0,4=0.参看参看(cnkn)表表3-1（a）。）。 最优解判断标准最优解判断标准(biozhn) 当所有检验数当所有检验数j0（j=1，n）时，基本可行解为最优解。）时，基本可行解为最优解。 当目标函数中有基变量当目标函数中有基变量xi时，利用约束条件将目标函数中的时，利用约束条件将目标函数中的xi消去消去即可求出检验数。即可求出检验数。 系统工程概论系统工程概论线线 性性 规规 划划LPLP的数学模型的数学模型标准型标准型图解法图解法单纯形法单纯形法人工变量法人工变量法第22页/共52页第

16、二十二页，共52页。进基列出基行bi /ai2，ai20i表3-1(a)XBx1x2x3x4bx3211040 x4130130j3400 (b)x3x4j (c)x1 x2 j 基变量(binling)11018001/301/3105/311/330405/304/330103/51/518011/52/540011将3化为1乘以1/3后得到(d do)LPLP的数学模型的数学模型标准型标准型图解法图解法单纯形法单纯形法人工人工(rngng)(rngng)变量法变量法动画演示动画演示第23页/共52页第二十三页，共52页。单纯形法全过程的计算，可以用列表的方法计算更为简单纯形法全过程的计算

17、，可以用列表的方法计算更为简洁，这种表格洁，这种表格(biog)称为单纯形表（表称为单纯形表（表3-1）。）。计算计算(j sun)说明：说明：1.求初始求初始(ch sh)基可行解，列出初始基可行解，列出初始(ch sh)单纯形表，单纯形表，求出检验数。其中基变量的检验数必为零；求出检验数。其中基变量的检验数必为零； 2.判断：判断： （a）若）若j（j，n）得到最优解；）得到最优解； （b）某个）某个k0且且aik（i=1，2,m）则线性规划具）则线性规划具有无界解。有无界解。 （c）若存在）若存在k0且且aik (i=1,m)不全非正，则进行换基；不全非正，则进行换基；系统工程概论系统工

18、程概论线线 性性 规规 划划LPLP的数学模型的数学模型标准型标准型图解法图解法单纯形法单纯形法人工变量法人工变量法第24页/共52页第二十四页，共52页。3.换基：换基：（a）设）设k0, xk为进基变量为进基变量(binling)，求最小，求最小比值：比值：iLikikbmina0a 第个比值最小第个比值最小 ，选最小比值对应行的基变量为出基变量，若有，选最小比值对应行的基变量为出基变量，若有相同最小比值，则任选相同最小比值，则任选(rn xun)一个。一个。aLk为主元素；为主元素； (b）求新的基可行解：用初等行变换方法将）求新的基可行解：用初等行变换方法将aik 化为化为1, k列其

19、它元素化为零（包括检验数行）得到新的可行基列其它元素化为零（包括检验数行）得到新的可行基及基本及基本(jbn)可行解，再判断是否得到最优解。可行解，再判断是否得到最优解。系统工程概论系统工程概论线线 性性 规规 划划LPLP的数学模型的数学模型标准型标准型图解法图解法单纯形法单纯形法人工变量法人工变量法第25页/共52页第二十五页，共52页。【例用单纯形法求解【例用单纯形法求解(qi ji)123maxZx2xx1231231232x3x2x151xx5x203xxx0、 、【解】将数学模型化为标准【解】将数学模型化为标准(biozhn)形式：形式：123maxZx2xx12341235j2x

20、3x2xx151xx5xx203x0,j1,2,5不难看出不难看出x4、x5可作为初始基变量可作为初始基变量(binling)，单纯法计算结，单纯法计算结果如表果如表 3-2所示所示 。 系统工程概论系统工程概论线线 性性 规规 划划LPLP的数学模型的数学模型标准型标准型图解法图解法单纯形法单纯形法人工变量法人工变量法第26页/共52页第二十六页，共52页。表3-2Cj12100bCBXBx1x2x3x4x50 x423210150 x51/3150120j12100 0 x42x2j 1x1 2x2 j 1/3150120301713751/309022025601017/31/31250

21、128/91/92/335/30098/91/97/3线线 性性 规规 划划LPLP的数学模型的数学模型标准型标准型图解法图解法单纯形法单纯形法人工人工(rngng)(rngng)变量法变量法动画演示动画演示(ynsh)第27页/共52页第二十七页，共52页。什么什么(shn me)是是最大流？最大流？4844122679容量：在某时期内弧容量：在某时期内弧(i，j)上的最大通过上的最大通过(tnggu)能力。记为能力。记为C (i，j)或或Cij 在上图中，在上图中，C12=4，C138，C234等，怎样安排运等，怎样安排运输方案，才能使在某一时期内从输方案，才能使在某一时期内从v1运到运到

22、v6的物资最多，这样的的物资最多，这样的问题就是最大流问题，问题就是最大流问题，网络中所有流起源于一网络中所有流起源于一个个(y )叫做发点的节点叫做发点的节点（源）（源） 所有的流终止于一个叫做所有的流终止于一个叫做收点收点的节点的节点其余所有的节点叫做其余所有的节点叫做中间点中间点（转运点）（转运点） 通过每一条弧的流只允许沿着弧的箭头方向流动通过每一条弧的流只允许沿着弧的箭头方向流动目标目标是使得从发点到收点的总流量最大是使得从发点到收点的总流量最大系统工程概论系统工程概论图图 与与 网网 络络最短路问题最短路问题最大流问题最大流问题基本概念基本概念第28页/共52页第二十八页，共52页

23、。流量流量(liling)：弧：弧(i，j)的实际通过量，记为的实际通过量，记为f (i，j)或或f ij可行流：如果可行流：如果f ij满足满足(mnz)： 1.对于所有弧对于所有弧(i，j)有有0f ijCij 2.对于发点对于发点vs有：有：vffjiissj3.对于对于(duy)收点收点vt有：有：vffijtjit则称流量集合则称流量集合f ij为网络的一个可行流，简记为为网络的一个可行流，简记为 f , v称称为可行流的流量或值，记为为可行流的流量或值，记为v(f).以下假设网络是一个简单连通图。以下假设网络是一个简单连通图。4.对于中间点点对于中间点点vm有：有：ijmjimff

24、系统工程概论系统工程概论图图 与与 网网 络络最短路问题最短路问题最大流问题最大流问题基本概念基本概念第29页/共52页第二十九页，共52页。链：从发点到收点的一条路线（弧的方向链：从发点到收点的一条路线（弧的方向(fngxing)不一定都同向）称不一定都同向）称为链。从发点到收点的方向为链。从发点到收点的方向(fngxing)规定为链的方向规定为链的方向(fngxing)。前向弧：与连的方向相同前向弧：与连的方向相同(xin tn)的弧称为前向弧。的弧称为前向弧。后向弧：与连的方向后向弧：与连的方向(fngxing)相反的弧称为后向弧。相反的弧称为后向弧。增广链增广链 设设 f 是一个可行流

25、，如果存在一条从是一个可行流，如果存在一条从vs到到vt的链，满足：的链，满足：1.所有前向弧上所有前向弧上fij0则该链称为增广链则该链称为增广链前向弧前向弧后向弧后向弧8446952346容量容量流量流量想一想，这想一想，这是一条增广是一条增广链吗？链吗？系统工程概论系统工程概论图图 与与 网网 络络最短路问题最短路问题最大流问题最大流问题基本概念基本概念第30页/共52页第三十页，共52页。【定理】设网络【定理】设网络G的一个可行流的一个可行流f，如果存在，如果存在(cnzi)一条从一条从vs到到vt的增广的增广链，那么就可改进一个值更大的可行流链，那么就可改进一个值更大的可行流f1，并

26、且，并且val f1val f【证证】设设val fv 121212min C(i, j)f(i, j) | (i, j)min f(i, j) | (i, j)min,|, 令 是前向弧令 是前向弧是后向弧是后向弧无前向弧时无后向弧无前向弧时无后向弧对改进对改进(gijn)的可行流的可行流f1 ：1f(i,j)(i,j)f (i,j)f(i,j)(i,j)f(i,j)(i,j) 不在增广链上不在增广链上是前向弧是前向弧是后向弧是后向弧1v(f )v(f)v(f) 则有则有系统工程概论系统工程概论(giln)(giln)图图 与与 网网 络络最短路问题最短路问题最大流问题最大流问题基本概念基本

27、概念第31页/共52页第三十一页，共52页。最大流的标号最大流的标号(bioho)算法算法步骤步骤(bzhu) 1. 找出第一个可行流，例如所有弧的流量找出第一个可行流，例如所有弧的流量fij =0 2. 用标号的方法用标号的方法(fngf)找一条增找一条增广链广链 A1：发点标号（：发点标号（），）， A2：选一个点：选一个点 vi 已标号并且另一端未标号的弧沿着某条已标号并且另一端未标号的弧沿着某条链向收点检查：链向收点检查： 如果弧的方向向前并且有如果弧的方向向前并且有fij0，则，则vj标号（标号（fji)当收点不能得到标号时，说明不存在增广链，计算结束。当收点不能得到标号时，说明不存

28、在增广链，计算结束。当收点已得到标号时，说明已找到增广链。当收点已得到标号时，说明已找到增广链。【定理定理】可行流是最大流当且仅当不存在发点到收点的增广链可行流是最大流当且仅当不存在发点到收点的增广链系统工程概论系统工程概论图图 与与 网网 络络最短路问题最短路问题最大流问题最大流问题基本概念基本概念第32页/共52页第三十二页，共52页。4. 调整调整(tiozhng)流量流量 是后向弧是前向弧不在增广链上),(),(),(),(),(),(),(1jijifjijifjijifjif得到新的可行流，去掉所有标号，从发点重新得到新的可行流，去掉所有标号，从发点重新(chngxn)标号寻标号寻

29、找增广链，直到收点不能标号为止。找增广链，直到收点不能标号为止。3. 依据依据(yj)vi 的第一个标号反向跟踪得到一条增广链；的第一个标号反向跟踪得到一条增广链； 依据依据(yj)vi 的第二个标号求最小值得到调整量的第二个标号求最小值得到调整量系统工程概论系统工程概论图图 与与 网网 络络最短路问题最短路问题最大流问题最大流问题基本概念基本概念第33页/共52页第三十三页，共52页。 684412267942202222046217【例】求下图【例】求下图v1 到到v6 的最大流及最大流量的最大流及最大流量(liling)【解】【解】1. 通过观察得到通过观察得到(d do)初始可行流初始

30、可行流2. 标号标号(bioho)3. 得到增广链得到增广链系统工程概论系统工程概论图图 与与 网网 络络最短路问题最短路问题最大流问题最大流问题基本概念基本概念第34页/共52页第三十四页，共52页。 68441226794211322304223重新重新(chngxn)标号得标号得到增广链到增广链 4.求调整求调整(tiozhng)量量 5.调整调整(tiozhng)可行流可行流 去掉所有标号，去掉所有标号，17 , 1 , 2 , 6 ,min 684412267942202222046217系统工程概论系统工程概论图图 与与 网网 络络最短路问题最短路问题最大流问题最大流问题基本概念基

31、本概念第35页/共52页第三十五页，共52页。68441226796411322306 求调整求调整(tiozhng)量量 调整调整(tiozhng)可行流可行流 去掉所有标号去掉所有标号(bioho)，重新标号，重新标号(bioho)5标号不能继续进行，说明不存在从发点到收点的增广链，标号不能继续进行，说明不存在从发点到收点的增广链，得到最大流得到最大流.最大流量最大流量 v=6+3=9123 , 2 , 2 ,min系统工程概论系统工程概论图图 与与 网网 络络最短路问题最短路问题最大流问题最大流问题基本概念基本概念第36页/共52页第三十六页，共52页。无向图最大流标号无向图最大流标号(

32、bioho)算法算法无向图不存在无向图不存在(cnzi)前向弧，可以理解为所有弧都是前向弧前向弧，可以理解为所有弧都是前向弧，对一端，对一端vi已标号另一端已标号另一端vj未标号的边只要满足未标号的边只要满足 Cijfij0 则则vj标号就可标号（标号就可标号（Cijfij）【例】求下图【例】求下图v1到则到则v7标的标的(bio de)最最大流大流712920851486913161061082376513013239932系统工程概论系统工程概论图图 与与 网网 络络最短路问题最短路问题最大流问题最大流问题基本概念基本概念第37页/共52页第三十七页，共52页。71292085148691

33、316126108437671321537711712920851486913161271084376813316V=2910566系统工程概论系统工程概论(giln)(giln)图图 与与 网网 络络最短路最短路(dunl)(dunl)问题问题最大流问题最大流问题(wnt)(wnt)基本概念基本概念第38页/共52页第三十八页，共52页。截集截集 将图将图G（V，E）的点集分割）的点集分割(fng)成两部分成两部分_111s1t11vVvVVVV V及，则箭尾在箭头在的弧集合（， 及，则箭尾在箭头在的弧集合（， 并且、1_1VV称为一个截集，截集中所有称为一个截集，截集中所有(suyu)弧的

34、容量之和称为截集的截量。弧的容量之和称为截集的截量。68441226796411322306下图所示的截集为下图所示的截集为 11(V ,V )(1,2),(3,4),(3,5) 11C(V ,V )62210 截截量量系统工程概论系统工程概论(giln)(giln)图图 与与 网网 络络最短路问题最短路问题最大流问题最大流问题基本概念基本概念第39页/共52页第三十九页，共52页。68441226796401322106又如下又如下(rxi)图所示的截图所示的截集为集为)6 , 5()4 , 5(),4 , 3(),4 , 2(),(11，VV219624),(11VVC截量上图所示的截集为

35、上图所示的截集为)5 , 3(),4 , 3(),5 , 2(),4 , 2(),(11VV92214),(11VVC截量所有截量中此截量最小且等于最大流量所有截量中此截量最小且等于最大流量(liling)，此截集称为最小截集。，此截集称为最小截集。【定理【定理(dngl)】最大流量等于最小截集的截量。】最大流量等于最小截集的截量。系统工程概论系统工程概论图图 与与 网网 络络最短路问题最短路问题最大流问题最大流问题基本概念基本概念第40页/共52页第四十页，共52页。系统工程概论系统工程概论(giln)(giln)非非 线线 性性 规规 划划无约束无约束有约束有约束(yush(yush) )

36、单变量单变量(binling)(binling)寻优寻优多变量寻优多变量寻优 Tnxfxfxfxfxf,)(21第41页/共52页第四十一页，共52页。系统工程概论系统工程概论(giln)(giln)非非 线线 性性 规规 划划无约束无约束有约束有约束(yush(yush) )单变量单变量(binling)(binling)寻优寻优多变量寻优多变量寻优 )()()(xfPxfxfs（2 2）最优梯度）最优梯度 由于函数沿负梯度方向下降最快，所以取由于函数沿负梯度方向下降最快，所以取f f（x x）为迭代）为迭代方向，设方向，设x xk k为迭代点，则迭代公式为为迭代点，则迭代公式为x xk +

37、1k +1= x= xk k k k f f（x x） 这样，只要步长因子这样，只要步长因子k k已知，就能求出下一个迭代点已知，就能求出下一个迭代点x xk +1k +1，且，且f f（x x k+1 k+1 ） f f（x x k k ），如此反复进行，直到找到最优点。），如此反复进行，直到找到最优点。第42页/共52页第四十二页，共52页。kkkkSxxfxfxx)()(1为步长 Sk Sk为从为从xkxk出发的单位梯度方向，称为搜索出发的单位梯度方向，称为搜索(su (su su)su)方向。方向。迭代公式迭代公式(gngsh)(gngsh)可表示为可表示为系统工程概论系统工程概论(g

38、iln)(giln)非非 线线 性性 规规 划划无约束无约束有约束有约束单变量寻优单变量寻优多变量寻优多变量寻优第43页/共52页第四十三页，共52页。系统工程概论系统工程概论(giln)(giln)非非 线线 性性 规规 划划无约束无约束有约有约束束(yus(yush)h)单变量单变量(binling)(binling)寻优寻优多变量寻优多变量寻优(3) (3) 最速下降法的基本概念最速下降法的基本概念 沿着负梯度方向选择步长时搜索步数最小的方法称沿着负梯度方向选择步长时搜索步数最小的方法称为最速下降法。这种方法每步需要计算最优步长，使每为最速下降法。这种方法每步需要计算最优步长，使每走一步

39、目标函数下降最多（达到极值）。走一步目标函数下降最多（达到极值）。)()(1kkkkSxfxf 沿着沿着S Sk k的方向求的方向求minf(xminf(xk+1k+1) )时的步长时的步长 k k，求最优步长时，求最优步长时，是对函数是对函数f f（x x k+1 k+1 ）求极值，步长）求极值，步长 k k为变量。为变量。第44页/共52页第四十四页，共52页。系统工程概论系统工程概论(giln)(giln)非非 线线 性性 规规 划划无约束无约束有约有约束束(yus(yush)h)单变量单变量(binling)(binling)寻优寻优多变量寻优多变量寻优 k k的选取方法：的选取方法：

40、1 1）选择一个固定值）选择一个固定值 ，或选一系列逐步见效的可变值；，或选一系列逐步见效的可变值；2 2）沿梯度方向找函数的一个极小值点，即沿）沿梯度方向找函数的一个极小值点，即沿s sk k 方向求方向求使得使得f(x)f(x)最小的最小的 k k。令。令kkdf (xs )0d 求得求得 k k。第45页/共52页第四十五页，共52页。系统工程概论系统工程概论(giln)(giln)非非 线线 性性 规规 划划无约束无约束有约有约束束(yus(yush)h)单变量单变量(binling)(binling)寻优寻优多变量寻优多变量寻优检验是否满足收敛性判别准则检验是否满足收敛性判别准则()

41、kf x若满足，迭代停止得到点若满足，迭代停止得到点x*=xk，否则进入否则进入()0kkkkdf xdd，求得计算计算1kkkkxxd1kk转到转到(4) 最速下降法的步骤：最速下降法的步骤：任选任选0,0,0nxEk选择允许误差令；计算负梯度计算负梯度()()()kkkkf xf xdf x 和负梯度方向进行一维搜索，令进行一维搜索，令第46页/共52页第四十六页，共52页。系统工程概论系统工程概论(giln)(giln)非非 线线 性性 规规 划划无约束无约束有约有约束束(yus(yush)h)单变量单变量(binling)(binling)寻优寻优多变量寻优多变量寻优(5)(5)举例举例 设设f f（x x ）= x= x1 12 2 + 25x+ 25x2 22 2，并设初始点，并设初始点x x0 0 = 2,2= 2,2T T，试用，试用最速下降法求最小点。最速下降法求最小点。解解 1 1）求目标函数的梯度向量）求目标函数的梯度向量f f（x x）21