1、系统工程概论系统工程概论系统工程定义系系 统统 定定 义义方 法 论系统的系统的系统的系统的3 3 3 3个基本特征个基本特征个基本特征个基本特征:系统是由元素组成的系统是由元素组成的 元素间相互作用、相互影响、相互依赖元素间相互作用、相互影响、相互依赖 由元素和元素间关系组成的整体具有特定功能由元素和元素间关系组成的整体具有特定功能1-1 1-1 系系 统统 的的 定定 义义系统工程概论系统工程概论1-2 1-2 系统工程的定义系统工程的定义系统工程定义系统工程定义系 统 定 义方 法 论 系统工程是一门新型学科,是以大规模复杂系统为研系统工程是一门新型学科,是以大规模复杂系统为研究对象的一
2、门跨专业的边缘学科。把自然科学和科学中究对象的一门跨专业的边缘学科。把自然科学和科学中的某些思想、理论、方法、策略、手段等根据总体协调的某些思想、理论、方法、策略、手段等根据总体协调的需要,有机地联系起来,把人们的输出科研和经济活的需要,有机地联系起来,把人们的输出科研和经济活动联系起来,应用数学方法和计算机等工具。动联系起来,应用数学方法和计算机等工具。x1x2O1020304010203040(3,4)(15,10)最优解X=(15,10)最优值Z=85max Z=3x1+4x2例例3.2.2动画演示动画演示246x1x2246最优解X=(3,1)最优值Z=5(3,1)min Z=x1+2
3、x2例例3.2.3动画演示动画演示246x1x2246有无穷多个最优解即具有多重解,通解为X(2)(3,1)X(1)(1,3)01 当=0.5时=(x1,x2)=0.5(1,3)+0.5(3,1)=(2,2)min Z=5x1+5x2例例3.2.4动画演示动画演示246x1x2246无界解(无最优解)max Z=x1+2x2例例3.2.5动画演示动画演示x1x2O10203040102030405050无可行解即无最优解max Z=3x1+4x2例例3.2.6动画演示动画演示由以上例题可知,线性规由以上例题可知,线性规划的解有划的解有4种形式种形式:1.有唯一最优解有唯一最优解(例例3.2.2
4、例例3.2.3)2.有多重解有多重解(例例3.2.4)3.有无界解有无界解(例例3.2.5)4.无可行解无可行解(例例3.2.6)1、2情形为有最优解,情形为有最优解,3、4情形为无最优解情形为无最优解例例1-2 1-2 已知已知 ,求其可达矩阵。,求其可达矩阵。解解:系统工程概论系统工程概论系统模型系 统 分 析系统建模方法系统建模方法建建模模方方法法之之二二:结结构构模模型型解解析析法法系统工程概论系统工程概论系统模型系 统 分 析系统建模方法系统建模方法建建模模方方法法之之二二:结结构构模模型型解解析析法法解:做区域划分表,见下表。解:做区域划分表,见下表。i R(ei)A(ei)R(e
5、i)A(ei)1 1 1,2,7 12 1,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 对可达性矩阵进行区域划分。对可达性矩阵进行区域划分。1 2 3 4 5 6 7系统工程概论系统工程概论系统模型系 统 分 析系统建模方法系统建模方法建建模模方方法法之之二二:结结构构模模型型解解析析法法 据此对据此对M进行初等变换进行初等变换行和列的顺行和列的顺序变更,化成对角分块矩阵的形式。序变更,化成对角分块矩阵的形式。
6、子系统子系统 子系统子系统 子系统子系统 子系统子系统3 4 5 6 1 2 7系统工程概论系统工程概论系统模型系 统 分 析系统建模方法系统建模方法建建模模方方法法之之二二:结结构构模模型型解解析析法法2)2)级别划分级别划分 级别划分是在每一个区域内进行的。级别划分是在每一个区域内进行的。如果对于如果对于 ,有,有则则 为最上级单元。为最上级单元。系统工程概论系统工程概论系统模型系 统 分 析系统建模方法系统建模方法建建模模方方法法之之二二:结结构构模模型型解解析析法法(在一个多级结构的最上级的单元,没有更高的级可达,在一个多级结构的最上级的单元,没有更高的级可达,它的可达集只包括它本身和
7、与它同级的强连接单元。而它的可达集只包括它本身和与它同级的强连接单元。而它的先行集则包括它本身、可以达到它的下级单元以及与它的先行集则包括它本身、可以达到它的下级单元以及与它同级的强连接单元。故而它同级的强连接单元。故而 ,当按上述,当按上述条件找到最上级单元后,把他们暂时去掉,再用同样的方条件找到最上级单元后,把他们暂时去掉,再用同样的方法求出次一级单元,以此类推。则系统法求出次一级单元,以此类推。则系统S中的一个区域中的一个区域P的的级别划分可用下式表示。级别划分可用下式表示。系统工程概论系统工程概论系统模型系 统 分 析系统建模方法系统建模方法建建模模方方法法之之二二:结结构构模模型型解
8、解析析法法 接着对上面的例子中的接着对上面的例子中的P1,P2进行级别划分:进行级别划分:系统工程概论系统工程概论系统模型系 统 分 析系统建模方法系统建模方法建建模模方方法法之之二二:结结构构模模型型解解析析法法 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有:有:接下来将接下来将M按级别划分的结果进行变换,得:按级别划分的结果进行变换,得:系统工程概论系统工程概论系统模型系 统 分
9、析系统建模方法系统建模方法建建模模方方法法之之二二:结结构构模模型型解解析析法法5 4 6 3 1 2 74、建立结构矩阵建立结构矩阵(1)浓缩阵)浓缩阵 系统中的任意两个单元系统中的任意两个单元ei和和ej若若在同一个最大回路集中,那么可达在同一个最大回路集中,那么可达性矩阵性矩阵M相应的行和列上的元素完相应的行和列上的元素完全相同。可将这两个单元当作一个全相同。可将这两个单元当作一个系统单元看待,从而可以削减相应系统单元看待,从而可以削减相应的行和列,得到的可达性矩阵的行和列,得到的可达性矩阵M 叫叫做做M的浓缩阵。例中的浓缩阵。例中ee4,4,e e6 6 相应的相应的行和列元素完全相同
10、,将行和列元素完全相同,将e e6 6除去得除去得浓缩阵浓缩阵M。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系统工程概论系统工程概论系统模型系 统 分 析系统建模方法系统建模方法建建模模方方法法之之二二:结结构构模模型型解解析析法法(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
11、 1 1 0 从从M中先找出一、二级之间的关系,中先找出一、二级之间的关系,m45=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
12、 0 1 0 0 7 0 1 0 根据根据E,可以绘制系统多层次结构图如右上,可以绘制系统多层次结构图如右上,1574,632系统工程概论系统工程概论系统模型系 统 分 析系统建模方法系统建模方法建建模模方方法法之之二二:结结构构模模型型解解析析法法系统工程概论系统工程概论系统模型系 统 分 析系统建模方法系统建模方法建建模模方方法法之之二二:结结构构模模型型解解析析法法结构模型解析法的建模步骤:结构模型解析法的建模步骤:小结:1.写出邻接矩阵写出邻接矩阵A;2.由由A推出可达性矩阵推出可达性矩阵M=(I A)n;3.各要素的级别划分各要素的级别划分 a)划分区域划分区域 b)在区域内进行级别
13、划分在区域内进行级别划分 c)按划分结果对按划分结果对M进行初等变换进行初等变换4.建立结构矩阵建立结构矩阵 a)由由M推出浓缩阵推出浓缩阵M b)由由M推出从属阵推出从属阵MM-I c)由由M推出结构矩阵推出结构矩阵E5.由由E画出层次结构图。画出层次结构图。单单纯纯形形计计算算方方法法(Simplex Method)是是先先求求出出一一个个初初始始基基可可行行解解并并判判断断它它是是否否最最优优,若若不不是是最最优优,再再换换一一个个基基可可行行解解并并判判断断,直直到到得得出出最最优优解解或或无无最最优优解解。它它是是一一种种逐逐步步逼近最优解的迭代方法。逼近最优解的迭代方法。当当系系数
14、数矩矩阵阵A中中可可以以观观察察得得到到一一个个可可行行基基时时(通通常常是是一一个个单单位位矩矩阵阵或或m个个线线性性无无关关的的单单位位向向量量组组成成的的矩矩阵阵),可以通过解线性方程组求得基本可行解。可以通过解线性方程组求得基本可行解。【例例3.2.8】用单纯形法求下列线性规划的最优解用单纯形法求下列线性规划的最优解系统工程概论系统工程概论线线 性性 规规 划划LPLP的数学模型的数学模型标准型标准型图解法图解法单纯形法单纯形法人工变量法人工变量法【解解】化为标准型,加入松驰变量化为标准型,加入松驰变量x3、x4则标准型为则标准型为系数矩阵系数矩阵r(B1)=2,B1是是一一个个初初始
15、始基基,x3、x4为为基基变变量量,x1、x2为为非非基基变变量量,令令x1=0、x2=0由由约约束束方方程程知知x3=40、x4=30得到初始基本可行解得到初始基本可行解X(1)=(0,0,40,30)T 系统工程概论系统工程概论线线 性性 规规 划划LPLP的数学模型的数学模型标准型标准型图解法图解法单纯形法单纯形法人工变量法人工变量法以上得到的一组基可行解是不是最优解,可以从目标函以上得到的一组基可行解是不是最优解,可以从目标函数中的系数看出。目标函数数中的系数看出。目标函数 Z=3x1+4x2中中x1的系数大于零,的系数大于零,如果如果x1为一正数,则为一正数,则Z的值就会增大,同样若
16、的值就会增大,同样若x2不为零为不为零为一正数,也能使一正数,也能使Z的值增大;因此只要目标函数中非基变的值增大;因此只要目标函数中非基变量的系数大于零,那么目标函数就没有达到最大值,即量的系数大于零,那么目标函数就没有达到最大值,即没有找到最优解,判别线性规划问题是否达到最优解的没有找到最优解,判别线性规划问题是否达到最优解的数称为检验数,记作数称为检验数,记作j,j=1,2,n。本例中本例中1=3,2=4,3=0,4=0.参看表参看表3-1(a)。)。最优解判断标准最优解判断标准 当所有检验数当所有检验数j0(j=1,n)时,基本)时,基本可行解为最优解。可行解为最优解。当目标函数中有基变
17、量当目标函数中有基变量xi时,利用约束条件将目标函数中时,利用约束条件将目标函数中的的xi消去即可求出检验数。消去即可求出检验数。系统工程概论系统工程概论线线 性性 规规 划划LPLP的数学模型的数学模型标准型标准型图解法图解法单纯形法单纯形法人工变量法人工变量法进基列出基行bi/ai2,ai20i表3-1(a)XBx1x2x3x4bx3211040 x4130130j3400(b)x3x4j(c)x1x2j基变量11018001/301/3105/311/330405/304/330103/51/518011/52/540011将3化为1乘以1/3后得到LPLP的数学模型的数学模型标准型标准
18、型图解法图解法单纯形法单纯形法人工变量法人工变量法动画演示动画演示单单纯纯形形法法全全过过程程的的计计算算,可可以以用用列列表表的的方方法法计计算算更更为为简简洁,这种表格称为单纯形表(表洁,这种表格称为单纯形表(表3-1)。)。计算说明:计算说明:1.求初始基可行解求初始基可行解,列出初始单纯形表,求出检验数。其,列出初始单纯形表,求出检验数。其中基变量的检验数必为零;中基变量的检验数必为零;2.判断:判断:(a)若)若j(j,n)得到最优解;)得到最优解;(b)某某个个k0且且aik(i=1,2,m)则则线线性性规规划划具有无界解。具有无界解。(c)若若存存在在k0且且aik(i=1,m)
19、不不全全非非正正,则则进进行行换基;换基;系统工程概论系统工程概论线线 性性 规规 划划LPLP的数学模型的数学模型标准型标准型图解法图解法单纯形法单纯形法人工变量法人工变量法3.换基:换基:(a)设)设k0,xk为进基变量,求最小比值:为进基变量,求最小比值:第第个个比比值值最最小小,选选最最小小比比值值对对应应行行的的基基变变量量为为出出基基变量,若有相同最小比值,则任选一个。变量,若有相同最小比值,则任选一个。aLk为主元素;为主元素;(b)求求新新的的基基可可行行解解:用用初初等等行行变变换换方方法法将将aik 化化为为1,k列列其其它它元元素素化化为为零零(包包括括检检验验数数行行)
20、得得到到新新的的可可行行基基及及基本可行解,再判断是否得到最优解。基本可行解,再判断是否得到最优解。系统工程概论系统工程概论线线 性性 规规 划划LPLP的数学模型的数学模型标准型标准型图解法图解法单纯形法单纯形法人工变量法人工变量法【例例3.2.9】用单纯形法求解用单纯形法求解【解解】将数学模型化为标准形式:将数学模型化为标准形式:不难看出不难看出x4、x5可作为初始基变量,单纯法计算结果如可作为初始基变量,单纯法计算结果如表表 3-2所示所示。系统工程概论系统工程概论线线 性性 规规 划划LPLP的数学模型的数学模型标准型标准型图解法图解法单纯形法单纯形法人工变量法人工变量法表3-2Cj1
21、2100bCBXBx1x2x3x4x50 x423210150 x51/3150120j121000 x42x2j1x12x2j1/3150120301713751/309022025601017/31/31250128/91/92/335/30098/91/97/3线线 性性 规规 划划LPLP的数学模型的数学模型标准型标准型图解法图解法单纯形法单纯形法人工变量法人工变量法动画演示动画演示什么是最大流?什么是最大流?4844122679容量容量:在某时期内弧:在某时期内弧(i,j)上的最大通过能力。记为上的最大通过能力。记为C(i,j)或或Cij 在上图中,在上图中,C12=4,C138,C
22、234等,怎样安排运输等,怎样安排运输方案,才能使在某一时期内从方案,才能使在某一时期内从v1运到运到v6的物资最多,这样的的物资最多,这样的问题就是最大流问题,问题就是最大流问题,网络中所有流起源于一网络中所有流起源于一个叫做个叫做发点发点的节点(源)的节点(源)所有的流终止于一个叫做所有的流终止于一个叫做收点收点的节点的节点其余所有的节点叫做其余所有的节点叫做中间点中间点(转运点)(转运点)通过每一条弧的流只允许沿着弧的箭头方向流动通过每一条弧的流只允许沿着弧的箭头方向流动目标目标是使得从发点到收点的总流量最大是使得从发点到收点的总流量最大系统工程概论系统工程概论图图 与与 网网 络络最短
23、路问题最短路问题最大流问题最大流问题基本概念基本概念流量:流量:弧弧(i,j)的实际通过量,记为的实际通过量,记为f(i,j)或或f ij可行流可行流:如果:如果f ij满足:满足:1.对于所有弧对于所有弧(i,j)有有0f ijCij 2.对于发点对于发点vs有:有:3.对于收点对于收点vt有:有:则称流量集合则称流量集合f ij为网络的一个可行流,简记为为网络的一个可行流,简记为 f ,v称为可行流的流量或值,记为称为可行流的流量或值,记为v(f).以下假设网络是一个简单连通图。以下假设网络是一个简单连通图。4.对于中间点点对于中间点点vm有:有:系统工程概论系统工程概论图图 与与 网网
24、络络最短路问题最短路问题最大流问题最大流问题基本概念基本概念链:链:从发点到收点的一条路线(弧的方向不一定都同向)称从发点到收点的一条路线(弧的方向不一定都同向)称为链。从发点到收点的方向规定为链的方向。为链。从发点到收点的方向规定为链的方向。前向弧:前向弧:与连的方向相同的弧称为前向弧。与连的方向相同的弧称为前向弧。后向弧:后向弧:与连的方向相反的弧称为后向弧。与连的方向相反的弧称为后向弧。增广链增广链 设设 f 是一个可行流,如果存在一条从是一个可行流,如果存在一条从vs到到vt的链,满足:的链,满足:1.所有前向弧上所有前向弧上fij0则该链称为增广链则该链称为增广链前向弧前向弧后向弧后
25、向弧8446952346容量容量流量流量想一想,这想一想,这是一条增广是一条增广链吗?链吗?系统工程概论系统工程概论图图 与与 网网 络络最短路问题最短路问题最大流问题最大流问题基本概念基本概念【定理定理】设网络设网络G的一个可行流的一个可行流f,如果存在一条从,如果存在一条从vs到到vt的增的增广链,那么就可改进一个值更大的可行流广链,那么就可改进一个值更大的可行流f1,并且,并且val f1val f【证证】设设val fv对改进的可行流对改进的可行流f1:系统工程概论系统工程概论图图 与与 网网 络络最短路问题最短路问题最大流问题最大流问题基本概念基本概念最大流的标号算法最大流的标号算法
26、步骤步骤 1.找出第一个可行流,例如所有弧的流量找出第一个可行流,例如所有弧的流量fij=0 2.用标号的方法找一条增广链用标号的方法找一条增广链 A1:发点标号(:发点标号(),),A2:选一个点:选一个点 vi 已标号并且另一端未标号的弧沿着某已标号并且另一端未标号的弧沿着某条链向收点检查:条链向收点检查:如果弧的方向向前并且有如果弧的方向向前并且有fij0,则,则vj标号(标号(fji)当收点不能得到标号时,说明不存在增广链,计算结束。当收点不能得到标号时,说明不存在增广链,计算结束。当收点已得到标号时,说明已找到增广链。当收点已得到标号时,说明已找到增广链。【定理定理】可行流是最大流当
27、且仅当不存在发点到收点的增广链可行流是最大流当且仅当不存在发点到收点的增广链系统工程概论系统工程概论图图 与与 网网 络络最短路问题最短路问题最大流问题最大流问题基本概念基本概念4.调整流量调整流量 得到新的可行流,去掉所有标号,从发点重新标号寻得到新的可行流,去掉所有标号,从发点重新标号寻找增广链,直到收点不能标号为止。找增广链,直到收点不能标号为止。3.依据依据vi 的第一个标号反向跟踪得到一条增广链;的第一个标号反向跟踪得到一条增广链;依据依据vi 的第二个标号求最小值得到调整量的第二个标号求最小值得到调整量系统工程概论系统工程概论图图 与与 网网 络络最短路问题最短路问题最大流问题最大
28、流问题基本概念基本概念 684412267942202222046217【例例】求下图求下图v1 到到v6 的最大流及最大流量的最大流及最大流量【解解】1.通过观察得到初始可行流通过观察得到初始可行流2.标号标号3.得到增广链得到增广链系统工程概论系统工程概论图图 与与 网网 络络最短路问题最短路问题最大流问题最大流问题基本概念基本概念 68441226794211322304223重新标号得到增广链重新标号得到增广链 4.求调整量求调整量 5.调整可行流调整可行流 去掉所有标号,去掉所有标号,684412267942202222046217系统工程概论系统工程概论图图 与与 网网 络络最短路
29、问题最短路问题最大流问题最大流问题基本概念基本概念68441226796411322306 求调整量求调整量 调整可行流调整可行流 去掉所有标号,重新标号去掉所有标号,重新标号5标号不能继续进行,说明不存在从发点到收点的增广链,标号不能继续进行,说明不存在从发点到收点的增广链,得到最大流得到最大流.最大流量最大流量 v=6+3=91系统工程概论系统工程概论图图 与与 网网 络络最短路问题最短路问题最大流问题最大流问题基本概念基本概念无向图最大流标号算法无向图最大流标号算法无向图不存在前向弧,可以理解为所有弧都是前向弧,对无向图不存在前向弧,可以理解为所有弧都是前向弧,对一端一端vi已标号另一端
30、已标号另一端vj未标号的边只要满足未标号的边只要满足 Cijfij0 则则vj标号就可标号(标号就可标号(Cijfij)【例例】求下图求下图v1到则到则v7标的最大流标的最大流71292085148691316106108237651301323993系统工程概论系统工程概论图图 与与 网网 络络最短路问题最短路问题最大流问题最大流问题基本概念基本概念7129208514869131612610843767132153771712920851486913161271084376813316V=2910566系统工程概论系统工程概论图图 与与 网网 络络最短路问题最短路问题最大流问题最大流问题基
31、本概念基本概念截集截集 将图将图G(V,E)的点集分割成两部分)的点集分割成两部分称为一个截集,截集中所有弧的容量之和称为截集的截量。称为一个截集,截集中所有弧的容量之和称为截集的截量。68441226796411322306下图所示的截集为下图所示的截集为系统工程概论系统工程概论图图 与与 网网 络络最短路问题最短路问题最大流问题最大流问题基本概念基本概念68441226796401322106又如下图所示的截集为又如下图所示的截集为上图所示的截集为上图所示的截集为所有截量中此截量最小且等于最大流量,此截集称为最小截集。所有截量中此截量最小且等于最大流量,此截集称为最小截集。【定理定理】最大
32、流量等于最小截集的截量。最大流量等于最小截集的截量。系统工程概论系统工程概论图图 与与 网网 络络最短路问题最短路问题最大流问题最大流问题基本概念基本概念系统工程概论系统工程概论非非 线线 性性 规规 划划无约束无约束有约束有约束单变量寻优单变量寻优多变量寻优多变量寻优(1)(1)梯度和梯度方向梯度和梯度方向 一个非线性函数一个非线性函数f(x)f(x)的梯度定义的梯度定义 最速下降法亦称梯度法(最速下降法亦称梯度法(Gradient MethodGradient Method),是由),是由著名数学家柯西在著名数学家柯西在18471847年提出来的,是一种最古老的下年提出来的,是一种最古老的
33、下降算法。最速下降法的基本思想是使目标函数沿其值下降算法。最速下降法的基本思想是使目标函数沿其值下降最快的方向前进,逐步走向最优点。降最快的方向前进,逐步走向最优点。系统工程概论系统工程概论非非 线线 性性 规规 划划无约束无约束有约束有约束单变量寻优单变量寻优多变量寻优多变量寻优 最最速速下下降降法法是是以以负负梯梯度度方方向向作作为为搜搜索索方向的,梯度方向的单位向量为方向的,梯度方向的单位向量为 (2 2)最优梯度)最优梯度 由于函数沿负梯度方向下降最快,所以取由于函数沿负梯度方向下降最快,所以取ff(x x)为迭代方向,设为迭代方向,设x xk k为迭代点,则迭代公式为为迭代点,则迭代
34、公式为x xk+1k+1=x=xk k k k f f(x x)这这样样,只只要要步步长长因因子子k k已已知知,就就能能求求出出下下一一个个迭迭代代点点x xk k+1+1,且且f f(x x k+1 k+1)f f(x x k k),如如此此反反复复进进行行,直直到到找找到到最优点。最优点。S Sk k为从为从x xk k出发的单位梯度方向,称为搜索方出发的单位梯度方向,称为搜索方向。向。迭代公式可表示为迭代公式可表示为系统工程概论系统工程概论非非 线线 性性 规规 划划无约束无约束有约束有约束单变量寻优单变量寻优多变量寻优多变量寻优系统工程概论系统工程概论非非 线线 性性 规规 划划无约
35、束无约束有约束有约束单变量寻优单变量寻优多变量寻优多变量寻优(3)(3)最速下降法的基本概念最速下降法的基本概念 沿着负梯度方向选择步长时搜索步数最小的方法沿着负梯度方向选择步长时搜索步数最小的方法称为最速下降法。这种方法每步需要计算最优步长,称为最速下降法。这种方法每步需要计算最优步长,使每走一步目标函数下降最多(达到极值)。使每走一步目标函数下降最多(达到极值)。沿着沿着S Sk k的方向求的方向求minf(xminf(xk+1k+1)时的步长时的步长 k k,求最优步求最优步长时,是对函数长时,是对函数f f(x x k+1 k+1)求极值,步长)求极值,步长 k k为变量。为变量。系统
36、工程概论系统工程概论非非 线线 性性 规规 划划无约束无约束有约束有约束单变量寻优单变量寻优多变量寻优多变量寻优 k k的选取方法:的选取方法:1 1)选择一个固定值)选择一个固定值,或选一系列逐步见效的可变,或选一系列逐步见效的可变值;值;2 2)沿梯度方向找函数的一个极小值点,即沿)沿梯度方向找函数的一个极小值点,即沿s sk k 方方向求使得向求使得f(x)f(x)最小的最小的 k k。令。令求得求得 k k。系统工程概论系统工程概论非非 线线 性性 规规 划划无约束无约束有约束有约束单变量寻优单变量寻优多变量寻优多变量寻优检验是否满足收敛性判别准则检验是否满足收敛性判别准则若满足,迭代
37、停止得到点若满足,迭代停止得到点x*=xk,否则进入否则进入计算计算转到转到(4)最速下降法的步骤:最速下降法的步骤:任选任选计算负梯度计算负梯度进行一维搜索,令进行一维搜索,令系统工程概论系统工程概论非非 线线 性性 规规 划划无约束无约束有约束有约束单变量寻优单变量寻优多变量寻优多变量寻优(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)系统工程概论系统工程概论非非 线线
38、 性性 规规 划划无约束无约束有约束有约束单变量寻优单变量寻优多变量寻优多变量寻优令令系统工程概论系统工程概论非非 线线 性性 规规 划划无约束无约束有约束有约束单变量寻优单变量寻优多变量寻优多变量寻优如此反复迭代,直到如此反复迭代,直到 为自定的非常小的正数,它决定搜索值的精度。为自定的非常小的正数,它决定搜索值的精度。迭代三步的结果为迭代三步的结果为 x1 x2 f(xx1 x2 f(xk k)初始点初始点 2 2 1042 2 1040 02.003 1.92 -0.003 3.692.003 1.92 -0.003 3.69 1 11.85 0.07 0.07 0.131.85 0.0
39、7 0.07 0.13 2 20.07 0.07 0 0.00490.07 0.07 0 0.0049系统工程概论系统工程概论非非 线线 性性 规规 划划无约束无约束有约束有约束单变量寻优单变量寻优多变量寻优多变量寻优(6 6)总结总结最速下降法的优点:最速下降法的优点:方法简单,每迭代一次计算量小,存储量少;方法简单,每迭代一次计算量小,存储量少;从一个不太好的初始点出发也能收敛到极小点。从一个不太好的初始点出发也能收敛到极小点。缺点是缺点是 收敛速度慢,特别是极小点附近收敛更慢;收敛速度慢,特别是极小点附近收敛更慢;最速下降法的收敛速度与变量的尺度关系很大;最速下降法的收敛速度与变量的尺度
40、关系很大;最速下降法对于小的扰动是不稳定的,而小的扰动在计算过程最速下降法对于小的扰动是不稳定的,而小的扰动在计算过程中是容易产生的,例如舍入误差的存在,或一维搜索时步长确定中是容易产生的,例如舍入误差的存在,或一维搜索时步长确定得不准确,这样就可能破坏方法的收敛性。得不准确,这样就可能破坏方法的收敛性。在远离极值点时收敛很快,但接近极值点时,由于在远离极值点时收敛很快,但接近极值点时,由于搜索步长减小以至收敛速度降低。通常和其他寻优方搜索步长减小以至收敛速度降低。通常和其他寻优方法结合起来使用。(先粗调,再细调)法结合起来使用。(先粗调,再细调)下面介绍求解该问题的下面介绍求解该问题的遗传算
41、法遗传算法遗传算法遗传算法的构造过程:的构造过程:第一步第一步第一步第一步:确定决策变量及其约束条件。:确定决策变量及其约束条件。s.t.-2.048 xi 2.048 (xi=1,2)第二步:第二步:第二步:第二步:建立优化模型。建立优化模型。max f(x1,x2)=100(x12-x22)2+(1-x1)2第三步;第三步;第三步;第三步;确定编码方法。确定编码方法。第四步:第四步:第四步:第四步:确定解码方法。确定解码方法。第五步:第五步:第五步:第五步:确定个体评价方法。确定个体评价方法。第六步:第六步:第六步:第六步:设计遗传算子。设计遗传算子。第七步:第七步:第七步:第七步:确定遗传算法的运行参数。确定遗传算法的运行参数。