系统工程课件：LEC03_系统工程的理论基础

《系统工程课件：LEC03_系统工程的理论基础》由会员分享，可在线阅读，更多相关《系统工程课件：LEC03_系统工程的理论基础（138页珍藏版）》请在金锄头文库上搜索。

1、3 系统工程的理论基础系统工程的理论基础 系系统统工工程程是是一一门门交交叉叉学学科科，其其最最基基础础的的理理论论涉涉及及系系统统最最优优化化、系系统统控控制制与与系系统统的的信信息处理三个方面。息处理三个方面。3.1 控制理论基础控制理论基础3.2 信息论基础信息论基础3.3 系统最优化理论系统最优化理论3.1 控制理论基础控制理论基础3.1.1 控制系统的描述： 外部,内部; 能控性,能观性,鲁棒性.3.1.2 系统最优控制: 容许控制,系统约束,性能指标, 极大值原理3.1.3 大系统理论控制论 创始人：维纳（N.Wiener，1894-1964） 美国数学家，控制论的创始人。其于19

2、48 年出版的控制论（CYBERNETICS) 一书标志了控制论的诞生。控制论的基本概念： 控制根据系统内外部条件对系统进行调节，以克服系统的不稳定性，使系统保持或达到某种特定的稳定状态，或使系统按照某种规律变化的过程。 控制系统控制系统 结构：一般由施控者、传递者和受控者三部分组成。 目的：控制系统的行为，达到既定的目标。 行为：在外界环境作用下系统作出的反应。 反馈：控制系统将输入的信息作用于受控对象后所产生的结果再一次送到输入端，并对信息的再输出发生影响的过程。 反馈种类： 正反馈 负反馈 大系统理论大系统理论 大系统一般是指规模庞大（维数很高）、结构复杂大系统一般是指规模庞大（维数很高

3、）、结构复杂（多层次、多关联）、目标众多（目标间往往有（多层次、多关联）、目标众多（目标间往往有冲突）、时标各异（同一系统中有多个时标）、冲突）、时标各异（同一系统中有多个时标）、位置分散，并常常具有随机性和不确定性的复杂位置分散，并常常具有随机性和不确定性的复杂系统，广泛存在于社会、政治、经济、生态、环系统，广泛存在于社会、政治、经济、生态、环境、工业等许多领域中。境、工业等许多领域中。大系统的主要特征之一体现在其结构复杂上。大大系统的主要特征之一体现在其结构复杂上。大系统结构取决于组成大系统的子系统集合和各子系统结构取决于组成大系统的子系统集合和各子系统之间的关联，并决定了大系统的功能，不

4、同系统之间的关联，并决定了大系统的功能，不同结构往往会产生不同的总体功能。由于大系统的结构往往会产生不同的总体功能。由于大系统的对象分散，变量数目众多，关联复杂，往往不宜对象分散，变量数目众多，关联复杂，往往不宜采用集中式结构，而多为递阶结构和分散结构。采用集中式结构，而多为递阶结构和分散结构。 大系统理论大系统理论研究大系统的结构方案，稳定性，最优化，建立模型的模型简化等问题称为大系统理论。3.2 信息论基础信息论基础随着科学技术的发展和社会进步，越来越多的事实证明，系统元素之间、子系统之间的相互联系和作用，系统与环境的相互联系和作用，都要通过交换、加工、利用信息来实现，系统的演化行为也需要

5、从信息观点来理解。因此，信息是系统工程的基本概念之一。两个基本问题：什么是信息和如何度量信息。 信息论基础信息论基础创始人：申农(C.E.Shannon) （1916-2001）美国科学家。1948年申农的“通讯的数学理论”（The mathematical Theory of communication)，长达数十页的论文，成了信息论正式诞生的里程碑。回顾20世纪的信息革命风暴，把信息论的创始人称为伟大的科学家并不为过。确实，他对人类贡献远远超过了一般的诺贝尔获奖者。 信息论基础信息论基础美国数学家申农（C.E.Shannon）和维纳以信息为主要研究对象，以信息的运动规律和应用方法为主要研究

6、内容，以计算机、光导纤维等为主要研究工具，以扩展人类的信息功能为主要研究目标。 信息论基础信息论基础信息具有新内容或新知识的消息 信息是对事物存在方式、运动状态、相互 联系的特征的一种表达和陈述。表现为文字、图象、图形、语言、声音等形式。 信息论基础信息论基础信号最具体，它是一物理量，可测量、可显示、可描述，同时它又是载荷信息的实体 -信息的物理层表达 消息是具体的、非物理的，可描述为语言文字、符号、数据、图片，能够被感觉到，同时它也是信息的载荷体。是信息论中主要描述形式-信息的数学层表达信息是抽象的、非物理的，是哲学层表达。信息论基础信息论基础信息论的创立者香农将信息定义为“两次不确定性之差

7、”，即“不确定性的减少”。从通信角度看，信息是数据、信号等构成的消息所载有的内容。消息是信息的“外壳”，信息是消息的“内核”。从应用角度讲，信息是指能为人们所认识和利用的、但事先又不知道的消息、情况等，也就是说，信息对于收信者应该是有用的和未知的。信息论基础信息论基础以通信为例，凡通信过程至少涉及信息发送者（称为信源）以通信为例，凡通信过程至少涉及信息发送者（称为信源）和信息接收者（称为信宿），通信是信源和信宿之间的一和信息接收者（称为信宿），通信是信源和信宿之间的一种特定联系。信宿需要了解信源发出的信息的内容，但在种特定联系。信宿需要了解信源发出的信息的内容，但在得到信息前该内容是不知道的，

8、或称信宿对信息内容的得到信息前该内容是不知道的，或称信宿对信息内容的“猜测猜测”是具有不确定性的。是具有不确定性的。一旦信宿收到了信源发来的信息就消除了这种不确定性，一旦信宿收到了信源发来的信息就消除了这种不确定性，所以通信系统中传送的正是这种能够消除不确定性的信息，所以通信系统中传送的正是这种能够消除不确定性的信息，从而增加了系统的确定性。然而，实际的通信过程可能完从而增加了系统的确定性。然而，实际的通信过程可能完全消除了不确定性，也可能只是部分消除了不确定性，甚全消除了不确定性，也可能只是部分消除了不确定性，甚至完全没有消除不确定性，这取决于信息量的大小。因此至完全没有消除不确定性，这取决

9、于信息量的大小。因此将信息定义为不确定性的减少是完全合理的。将信息定义为不确定性的减少是完全合理的。3.3 系统最优化理论系统最优化理论系统工程，其核心目标之一是使系统运行在系统工程，其核心目标之一是使系统运行在最优状态，因此，系统最优化技术是其最最优状态，因此，系统最优化技术是其最重要的理论支撑。重要的理论支撑。系统最优化理论系统最优化理论系统优化理论主要包括系统优化理论主要包括线性规划、非线性规划、整线性规划、非线性规划、整数规划、动态规划数规划、动态规划等内容，等内容，如果考虑到最优化技术在不同应用领域中的拓展，如果考虑到最优化技术在不同应用领域中的拓展，还应包括还应包括排队论、对策论、

10、决策论排队论、对策论、决策论等，这些都属等，这些都属于运筹学的研究范畴。于运筹学的研究范畴。本本书书仅仅介介绍绍与与系系统统工工程程有有关关的的系系统统最最优优化化理理论论包包括：括： 线性规划、非线性规划、整数规划、动态规划线性规划、非线性规划、整数规划、动态规划3.3.1 线性规划线性规划线性规划上世纪30年代出现，40年代丹兹格提出单纯形法。线性规划主要研究的问题有两类：线性规划主要研究的问题有两类：1在给定数量的的人力、物力等资源下，如何科学地运用这些资源，以获得最大效益（去完成最大的任务），或在一定的条件下，寻求最优化的设计；2在给定任务的情况下，如何统筹安排，使用最小量的资源去完成

11、这项任务。线线性性规规划划问问题题：求一组变量，使之满足线性约束条件，且具有线性的目标函数取最大（或最小）值的一类最优化问题。线性规划数学模型一般形式 目标函数：满足约束条件: 例例3-3-1 (3-3-1 (生产计划问题生产计划问题) 某工厂有三种原料某工厂有三种原料B1、B2和和B3，储量分别为，储量分别为170千克、千克、100千克和千克和150千克。现用此三种原料生产两种产品千克。现用此三种原料生产两种产品A1和和A2。已知每生产。已知每生产1千克千克A1需要原料需要原料5千克千克B1、2千克千克B2和和1千克千克B3。每生产。每生产1千克千克A2需要原料需要原料2千克千克B1、3千克

12、千克B2和和5千克千克B3。又知每千克。又知每千克A1产品利润为产品利润为10元，每千克元，每千克A2产品产品利润为利润为18元。元。问在工厂现有资源条件下，应如何安排生产，才使工厂获得问在工厂现有资源条件下，应如何安排生产，才使工厂获得最大利润。最大利润。B1(kg)B2(kg)B3(kg)利润(元)A152110A223518总量170100150解：设安排生产A1、A2产品的产量分别为和 ，则根据题意，数学模型为 s.t.求解方法：求解方法： 1. 图解法图解法 2. 单纯形法单纯形法例3-3-2 运输问题运输问题（产销平衡） 从两个仓库（发点）运送库存原棉到三个纺织厂（收点），两仓库的

13、库存量、三个纺织厂的需求量、每吨原棉从个仓库运到工厂的所需运费如下表：问问：在保证各个纺织厂的需求都得到满足的条件下，应采用哪一种运送原棉的方案使得运费最少？工厂工厂1 工厂工厂2工厂工厂3库存量库存量（吨）（吨） 仓库仓库121350仓库仓库222430需求量需求量(吨吨)40152580s.t.求解方法：求解方法： 1. 表上作业法表上作业法 2. 单纯形法单纯形法线性规划模型三个基本要素：线性规划模型三个基本要素： 决策变量决策变量 目标函数目标函数 约束条件约束条件线性规划问题的标准形：线性规划问题的标准形：s.t.Max z = c1x1 + c2x2 + + cnxn Max z=

14、cTx(LP) s.t. Ax = b x0线性规划问题的标准形描述：线性规划问题的标准形描述： 目标函数求最大目标函数求最大 决策变量均非负决策变量均非负 约束条件为等式约束条件为等式 右端常数项非负右端常数项非负线性规划问题的标准形的转化方法：线性规划问题的标准形的转化方法： 1）若若约约束束条条件件不不是是等等式式，则则加加松松弛弛变变量量（）或减剩余变量（）或减剩余变量（）；）； 2）若若目目标标函函数数求求最最小小，则则对对应应目目标标函函数数反反号后求最大；号后求最大； 3）若若有有的的条条件件的的右右端端常常数数为为负负，则则将将该该条条件件的的两两边同乘以边同乘以-1； 4）若

15、若某某变变量量没没有有非非负负约约束束，则则可可引引入入两两非非负负变变量量，将该变量表示成两非负变量之差。将该变量表示成两非负变量之差。 5) 若某变量为负，引入新变量等于该变量的反号若某变量为负，引入新变量等于该变量的反号.例例 将下列线性规划模型化为标准形将下列线性规划模型化为标准形s.t.相关的概念相关的概念 相关的概念相关的概念 图解法求解图解法求解主要讲解图解法（对两个决策变量有效）；主要讲解图解法（对两个决策变量有效）；和单纯形法（决策变量个数不限）。和单纯形法（决策变量个数不限）。用图解法求解线性规划问题时不必将线性用图解法求解线性规划问题时不必将线性规划模型化为标准形式，其求

16、解过程一般规划模型化为标准形式，其求解过程一般经历以下几步：以两个决策变量为轴在平经历以下几步：以两个决策变量为轴在平面上建立直角坐标系；图示由线性等式和面上建立直角坐标系；图示由线性等式和不等式构成的约束条件，标出可行域；图不等式构成的约束条件，标出可行域；图示并移动目标函数，寻找最优解。示并移动目标函数，寻找最优解。图解法求解图解法求解图解法求解图解法求解图解法求解图解法求解练习练习: 用图解法解线性规划问题用图解法解线性规划问题min z=-x1-3x2s.t. x1+ x26-x1+2x28x1 0, x20可行域可行域目标函数等值线目标函数等值线最优解最优解64-860x1x2线性规

17、划模型及单纯形法线性规划模型及单纯形法矩阵形式：矩阵形式：线性规划的标准形式：线性规划的标准形式： Max cTx(LP) s.t. Ax = b x0其中其中, c , x Rn b Rm A m n 矩阵矩阵线性规划模型及单纯形法线性规划模型及单纯形法线性规划的规范形式：线性规划的规范形式： Max cTx (P) s.t. Ax b x0其中其中, c , x Rn b Rm A m n 矩阵矩阵线性规划模型及单纯形法线性规划模型及单纯形法 线性规划模型及单纯形法线性规划模型及单纯形法定理定理3-3-4 考虑考虑(LP) , 条件同上，设条件同上，设 x* 为极点为极点, 存在分解存在分

18、解 A = B , N ，其中，其中B为为m阶非奇异矩阵，使阶非奇异矩阵，使 xT = xBT, xNT , 这里这里 xB = B-1b0, xN =0， 相应相应 cT = cBT, cNT 。那么，。那么， 1）若）若 cNT- cBT B-1N0, 则则 x* - opt. 2）若）若 cj- cBT B-1pj 0, 且且 B-1pj0, 则则 (LP) 无有界解无有界解 .线性规划的单纯形法线性规划的单纯形法表格单纯形法表格单纯形法1、原理及算法过程、原理及算法过程 Max cTx(LP) s.t. Ax = b x0其中其中, c , x Rn b Rm A m n 矩阵，秩（矩

19、阵，秩（A）= m 线性规划的单纯形法线性规划的单纯形法单纯形法原理及算法过程单纯形法原理及算法过程算法过程算法过程 (考虑一般步考虑一般步, k = 0,1,2, )设设 x(k) 为极点为极点, 对应分解对应分解 A = B , N ，使，使 xT = xBT, xNT , 这里这里 xB = B-1b0, xN =0， 相应相应 cT = cBT, cNT 。那么，。那么， 1）若）若 cNT- cBT B-1N0, 则则 x(k) opt，停；，停； 2）否则，存在）否则，存在 cj- cBT B-1pj 0, a）若若 B-1pj0, 则则 (LP) 无有界解，停；无有界解，停； b

20、）若存在）若存在 (B-1pj)i 0, 取取 = min(B-1b)i / (B-1pj)i | (B-1pj)i 0 = (B-1b)r /(B-1pj)r 0 线性规划的单纯形法线性规划的单纯形法单纯形法原理及算法过程单纯形法原理及算法过程得到得到 x(k+1) = x(k) + d 是极点是极点其中其中, dT = dBT, dNT , 这里这里 j dB = -B-1pj , dN = (0, . , 1, ,0)T有有, cTx(k+1) = cTx(k) + cTd = cTx(k) + (cj - cBTB-1pj) cTx(k) 所以，所以，x(k+1) 比比 x(k) 好好

21、 重复这个过程，直到停机。重复这个过程，直到停机。单纯形法基本步骤单纯形法基本步骤 单纯形法基本步骤单纯形法基本步骤 线性规划的单纯形法线性规划的单纯形法 表格单纯形法表格单纯形法2、单纯形表：、单纯形表：设设 x 为初始极点为初始极点, 相应分解相应分解 A = B , N fxBTxNTRHS目标行目标行1cBTcNT01行行约束行约束行0BNbM行行1列列m列列n-m列列1列列作变换，使前作变换，使前m+1列对应的列对应的m+1阶矩阵变为单位矩阶矩阵变为单位矩阵。相当于该表左乘阵。相当于该表左乘 1 cBT -1 1 - cBT B-1 0 B 0 B-1 = 线性规划的单纯形法线性规划

22、的单纯形法表格单纯形法表格单纯形法得到：得到： 检验数检验数fxBTxNTRHS目标行目标行10TcNT - cBT B-1NcBTB-1 b1行行 xB0IB-1NB-1bM行行1列列m列列n-m列列1列列为了计算方便，我们对规范形式建立如为了计算方便，我们对规范形式建立如下单纯形表：下单纯形表：（注：引入了注：引入了m个松弛变量个松弛变量）线性规划的单纯形法线性规划的单纯形法表格单纯形法表格单纯形法考虑：考虑： bi 0 i = 1 , , m Max z = c1 x1 + c2 x2 + + cn xn s.t. a11 x1 + a12 x2 + + a1n xn b1 a21 x1

23、 + a22 x2 + + a2n xn b2 am1 x1 + am2 x2 + + amn xn bm x1 ，x2 ， ，xn 0线性规划的单纯形法线性规划的单纯形法加入松弛变量：加入松弛变量： Max z = c1 x1 + c2 x2 + + cn xn s.t. a11 x1 + a12 x2 + + a1n xn + xn+1 = b1 a21 x1 + a22 x2 + + a2n xn + xn+2 = b2 am1 x1 + am2 x2 + + amn xn+ xn+m = bm x1 ，x2 ， ，xn ，xn+1 ， ，xn+m 0显然，显然，xj = 0 j = 1

24、, , n ; xn+i = bi i = 1 , , m 是基本可行是基本可行解解, 对应的基是单位矩阵。对应的基是单位矩阵。以下是初始单纯形表：以下是初始单纯形表： m m其中：f = - cn+i bi j = cj - cn+i aij 为检验数 cn+i = 0 i= 1,m i = 1 i = 1 an+i,i = 1 , an+i,j = 0 ( ji ) i , j = 1, , m建立实用单纯形表建立实用单纯形表 利用求解线性规划问题基本可行解（极点）的方法来求解较大规模的问题是不可行的。单纯形法的基本思路是有选择地取基本可行解，即是从可行域的一个极点出发，沿着可行域的边界移

25、到另一个相邻的极点，要求新极点的目标函数值不比原目标函数值差。 线性规划的单纯形法线性规划的单纯形法单单 纯纯 形形 法法初始基本可行解初始基本可行解是否最优解或是否最优解或无限最优解无限最优解? ?结束结束沿边界找新沿边界找新的基本可行解的基本可行解NY单纯形法的基本过程 例：用单纯形法的基本思路解前例的线性规划问题 Max z = 1500 x1 + 2500 x2 s.t. 3 x1 + 2 x2 + x3 = 65 2 x1 + x2 + x4 = 40 3 x2 + x5 = 75 x1 , x2 , x3 , x4 , x5 0线性规划的单纯形法线性规划的单纯形法线性规划的单纯形法

26、线性规划的单纯形法最优解最优解 x1 = 5 x2 = 25 x4 = 5（松弛标量，表示（松弛标量，表示B设备有设备有5个机时的剩余）个机时的剩余） 最优值最优值 z* = 70000 注意：单纯形法中，注意：单纯形法中， 1、每一步运算只能用矩阵初等、每一步运算只能用矩阵初等行变换；行变换； 2、表中第、表中第3列的数总应保持非负列的数总应保持非负（ 0）；）； 3、当所有检验数均非正（、当所有检验数均非正（ 0）时，得到最优单纯形表。时，得到最优单纯形表。线性规划的单纯形法线性规划的单纯形法习题* 习题* 习题 3.3.2 整数规划整数规划整数规划整数规划： 具有特殊约束条件的线性规划问

27、题。当用通常线性规划的求解方法（单纯形法、图解法）求出非整数解时，不能用简单的“舍入取整”的方法得到整数最优解，必须用整数规划的方法。求解方法求解方法： 1. 穷举法 2. 分枝定界法分枝定界法（要求会解一般线性规划问题） 3. 割平面法（要求会解一般线性规划问题）分枝定界法分枝定界法 分分枝枝定定界界法法是是一一种种计计算算与与分分析析判判断断相相结结合的求解整数规划的重要方法。合的求解整数规划的重要方法。分枝定界法求解整数规划的步骤：分枝定界法求解整数规划的步骤：（1）松弛：）松弛： 先先不不考考虑虑整整数数约约束束的的因因素素，利利用用线线性性规规划划求求解解方方法法（比比如如图图解解法

28、法、单单纯纯形形法法）求求出出不带整数约束的解；不带整数约束的解；（2）分枝：）分枝：（3）剪枝：）剪枝： 对对边边界界值值小小于于可可行行解解的的分分枝枝不不再再考考虑虑，即将这些分枝剪去。即将这些分枝剪去。 例：例： 背包问题，经典背包问题，经典0-1规划问题规划问题例：例： 求解整数规划问题求解整数规划问题解：先考虑没有整数约束问题解：先考虑没有整数约束问题（2）s.t.（1）s.t.1） 问 题 （ 2） 的 最 优 解 ： x1=4.81， x2=1.82，f(x)=356。x1、x2非整数，增加约束条件后再求解；2）在（2）中增加条件：x14后（将相应的问题记为（3），求得最优解为

29、： x1 =4，x2=2.1，f(x)=349。x2非整数，增加约束条件后再求解；3）在（2）中增加条件：x15后（将相应的问题记为（4），求得最优解为：x1 =5，x2=1.57，f(x)=341。 x2非整数，增加约束条件后再求解；4）在（2）中增加条件：x14，x2 2后（将相应的问题记为（5），求得最优解为：x1 =4，x2=2，f(x)=340。是整数解，停止计算；5）在（2）中增加条件：x14，x2 3后（将相应的问题记为（6），求得最优解为：x1 =10/7，x2=3，f(x)=327。停止计算；6）在（2）中增加条件：x15，x21后（将相应的问题记为（7），求得最优解为：x1

30、 =5.44，x2=1，f(x)=308。停止计算；7）在（2）中增加条件：x15，x2 2后（将相应的问题记为（8），无解。停止计算。 故原问题的最优解为： x1=4， x2=2， 最优值： f(x)=3403.3.3 非线性规划 如果目标函数或约束条件中存在任何非线性因子，则称为非线性规划。线性规划问题：最优解如果存在，则一定在可行解域的某一顶点达到；解法有单纯形法（一般方法）、图解法、等等；非线性规划问题：最优解不一定在约束区域的边界上达到，可能在约束区域上的某一点上达到。解法较多，无一般方法。 一般有解析法和数值法2种：解解析析法法（间间接接优优化化法法）：先建立数学模型（比较困难），

31、再用数学解析的方法求出数学方程的最优解。 数数值值法法（直直接接搜搜索索法法）：不需知道数学模型，在变量的取值上直接搜索，通过少数次试验，寻找其最优解； 例例： 设平面上有m个点，找覆盖这m个点的最小圆盘。 无约束的非线性规划问题，其解法有：区间消去法、Fibonacci法、最速下降法等； 例例： 设有n个商店，其位置和对货物的需求都是已知的，货物由m个仓库提供，仓库容量已知。决定这m个仓库建于何处，使仓库提供各商店货物时的运量与里程之积的总和最小。 有约束的非线性规划问题，其解法有：罚函数法、线性逼近法等。 非线性规划一般形式：非线性规划一般形式： 1、无约束非线性规划、无约束非线性规划 （

32、3-32） 2、有约束非线性规划、有约束非线性规划 （3-33） （3-34） s.t.相关概念和性质定义定义1 1 全局最优解定义定义2 2 局部最优解定义定义3 3 凸组合定义定义4 4 凸函数，严格凸函数，凹函数 几何意义（下单峰）定义定义5 5 凸规划 凸规划的解析解的性质：引理引理1 1引理引理2 2定理定理1 1，2 2，3 3定义定义1 全局最优解全局最优解 设设f(x)为目标函数，为目标函数，S为可行域，为可行域，x*S 。若对每一。若对每一个个x都有都有f(x) f(x*),则称则称x*为极小化问题（为极小化问题（3-36）的全局最优解（最小）。的全局最优解（最小）。定义定义

33、2 局部最优解局部最优解 设设f(x)为目标函数，为目标函数，S为可行域，为可行域， x*S 。若存在。若存在x*的一个邻域的一个邻域,使得对该邻域的每一个使得对该邻域的每一个x都有都有f(x) f(x*)，则称为极小化问题（，则称为极小化问题（3-36）的局部最优解）的局部最优解（最小）。（最小）。凸规划是非线性规划中一种重要的特殊情况，具有凸规划是非线性规划中一种重要的特殊情况，具有许多良好的解析性质，可以用解析解法求解。许多良好的解析性质，可以用解析解法求解。定义定义6 6 设 f(x) 存在一阶偏导数，称列向量 为 f(x) 在点 x=x1 x2 xnT 处的梯度。定义定义7 7 设

34、f(x) 存在二阶偏导数，称矩阵 为 f(x) 在点 x=x1 x2 xnT 处的Hesse矩阵。引引理理3 3 局部极小点的一阶必要条件：该点处的梯度为0。引引理理4 4 局部极小点的二阶必要条件：该点处的梯度为0，且Hesse矩阵半正定。定定理理2 2 局部极小点的二阶充分条件：该点处的梯度为0，且Hesse矩阵正定。定理定理3 3 凸规划问题的结论（简单介绍）练习:u数值迭代法的基本思想： 首先给一个初始解 x(0)，然后按某某种种规规则则（算法）找出比 x(0) 更好的解 x(1) ，再按此种规则找出比 x(1) 更好的解 x(2) ，可得到一个解序列 x(k) 。若这个序列有极限 x

35、* ，则极限值就是最优解。u数值迭代法的基本步骤： 1）选定初始迭代点 2）确定搜索方向 3）确定步长 ，产生下一个迭代点 4）检查得到的新点是否满足条件。是，停止迭代；不是，回到2）。无约束非线性规划问题的迭代算法无约束非线性规划问题的迭代算法最速下降法（算法3-1） 原原理理：每次迭代沿最速下降方向（负梯度方向）进行搜索，迈出最优步长，即一步达到该方向的最小点，再以此点为初始点，重复上述步骤，直至得到最优解为止。 广义牛顿法（算法3-2） 原原理理：用一个二次函数 局部地逼近，然后求此近似函数的极小点。共轭梯度法（算法3-3） 原原理理：以共轭方向为搜索方向，将共轭方向与最速下降原理相结合

36、。约束非线性规划问题的迭代算法约束非线性规划问题的迭代算法将迭代序列严格控制在可行域内，从而执行的迭代过程实际上为无约束优化过程；序列无约束优化方法，简称SUMT方法； 罚函数法（外点法）（一般约束） 障碍函数（内点法） ）（不等式约束）在迭代点附近的序列线性化或序列二次函数逼近方法（泰勒展开） 线性规划 二次规划（目标函数二次，约束条件一次，解法简单，拉格朗日乘子法）最速下降法最速下降法最最速速下下降降法法：是应用目标函数的负梯度方向作为每步迭代的搜索方向，在计算时每步都是沿负梯度方向取最优步长，因而此方法也称最优梯度法最优梯度法。最速下降法，只能使得目标函数在开始几步（离目标远时）下降较快

37、。最速下降法只是用一阶梯度的信息以确定下一步搜索方向，优点优点：算法比较简单；缺点缺点：收敛较慢，且越是接近极限点，收敛越慢。改进的算法改进的算法：共轭梯度法、变尺度法等。主要介绍最速下降法，它是其它优化方法的基础： 梯度：梯度：梯度方向：梯度方向：梯度方向的单位向量：梯度方向的单位向量：梯度的范数：梯度的范数：最优梯度最优梯度： 从一点 出发，按如下公式迭代 称为步长 问题问题：如何选择步长和搜索方向？ 搜索方向：负梯度方向 步长：固定步长？变步长？（变步长） 用近似最优步长公式，或用微分法步长：步长：其中其中H为为Hesee矩阵，二阶矩阵，二阶Hesee矩阵为：矩阵为：例子例子 求函数 的

38、最小值解：初值取 ，则习题* 3.3.4 动态规划动态规划 50年代初，由美国数学家年代初，由美国数学家Bellman提出。提出。 将将系系统统运运行行过过程程分分为为若若干干相相继继的的阶阶段段，而而在在每每个个阶阶段段都都要要做做出出决决策策的的过过程程，就就叫叫做做多多段段决决策策过过程程。多多段段决决策过程的每一段的结束状态，就是下一段的初始状态。策过程的每一段的结束状态，就是下一段的初始状态。 动动态态规规划划是是研研究究多多段段决决策策而而提提出出来来的的一一种种数数学学方方法法，它它的的中中心心思思想想是是所所谓谓的的“最最优优性性原原理理”，这这个个原原理理归归结结为为一一个个

39、基基本本递递推推关关系系式式，从从整整个个过过程程的的终终点点出出发发，由由后后向向前前，使使过过程程连连续续地地转转移移，一一步步一一步步地地推推到到始始点点，找找到到最优解最优解。 系系统统动动态态最最优优化化习习惯惯称称为为最最优优控控制制，它它与与系系统统静静态态最最优优化化的的区区别别在在于于其其自自变变量量是是时时间间的的函函数数，实实质质上上属属于于泛函极值的范畴。泛函极值的范畴。 一个多阶段决策过程最优化问题的动态规划模一个多阶段决策过程最优化问题的动态规划模型包括以下要素：型包括以下要素：（1）阶阶段段：对对整整个个系系统统的的自自然然划划分分（时时间间顺顺序序或或空空间间特

40、征），阶段变量一般用特征），阶段变量一般用k=1,2,，n表示。表示。（2）状状态态：表表示示每每个个阶阶段段开开始始时时过过程程所所处处的的自自然然状状况况，它应能描述过程的特征并且具有无后效性。它应能描述过程的特征并且具有无后效性。 状状态态变变量量：描描述述状状态态的的变变量量，用用 表表示示第第k阶阶段段的的状状态态变变量量（离离散散的的或或连连续续的的）；变变量量允允许许取取值值的的范范围围称称为允许状态集合，用为允许状态集合，用 表示第表示第k阶段的状态允许集合。阶段的状态允许集合。（3）决决策策：当当一一个个阶阶段段的的状状态态确确定定后后，可可以以作作出出各各种种选选择择从从而

41、而演演变变到到下下一一阶阶段段的的某某个个状状态态，这这种种选选择择手手段段称称为为决决策策或或控控制制。用用 表表示示第第k阶阶段段处处于于状状态态 时时的的决策变量，用决策变量，用 表示表示 的允许决策集合。的允许决策集合。 （4）策略：决策组成的序列。）策略：决策组成的序列。（5）状状态态转转移移方方程程：在在确确定定性性过过程程中中，当当某某阶阶段段的的状状态态和和决决策策已已知知时时，下下阶阶段段的的状状态态便便完完全全确确定定，表表示示这这种种演变规律的方程称为状态转移方程，记作：演变规律的方程称为状态转移方程，记作：， k=1,2,，n。（6）指指标标函函数数和和最最优优函函数数

42、：衡衡量量过过程程优优劣劣的的数数量量指指标标，是定义在全过程和后部子过程上的数量函数，用是定义在全过程和后部子过程上的数量函数，用 ， k=1,2,，n表示。表示。 根据状态转移方程，指标函数根据状态转移方程，指标函数 可以表示为状态可以表示为状态和和策策略略 的的函函数数，即即 。在在 给给定定时时，指指标标函函数数 对对 的最优值称为最优函数，的最优值称为最优函数，记为记为 ，即，即式中，式中，opt可取可取max或或min（7）最优策略和最优轨线：）最优策略和最优轨线：定理定理4定理定理5定理定理6 关键公式：关键公式： （73）、（）、（74） 3.3.4 动态规划动态规划3.3.4

43、 动态规划动态规划3.3.4 动态规划动态规划3.3.4 动态规划动态规划3.3.4 动态规划动态规划3.3.4 动态规划动态规划3.3.4 动态规划动态规划2511214106104131112396581052C1C3D1AB1B3B2D2EC2例例 求从求从A到到E的最短路径的最短路径2511214106104131112396581052C1C3D1AB1B3B2D2EC2f5(E)=03.3.4 动态规划动态规划2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D1)=5f5(E)=025112141061041311123965810

44、52C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f4(D1)=52511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C1)=8f4(D1)=52511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C2)=7f4(D1)=5f3(C1)=82511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f3(C1)=8f3(C2)=72

45、511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B1)=20f3(C2)=7f3(C1)=82511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B2)=14f3(C2)=7f3(C1)=8f2(B1)=212511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=1

46、9f3(C2)=7f3(C1)=8f2(B1)=21f2(B2)=142511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=212511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=21状态状态 最优决策最优决策 状态状态 最优决策最优决策 状态状态 最优决策最优决策 状态状态 最优决策最优决策 状态状态A （ A，B2） B2 （B2，C1） C1 （C1，D1） D1 （D1，E） E从从A到到E的最短路径为的最短路径为19，路线为，路线为AB 2C1 D1 E 3.3.5 多目标规划多目标规划 3.3.5多目标规划多目标规划 3.3.5多目标规划多目标规划 3.3.5多目标规划多目标规划 3.3.5多目标规划多目标规划 3.3.5多目标规划多目标规划 3.3.5多目标规划多目标规划 3.3.5多目标规划多目标规划