多目标最优化数学模型

1、第六章最优化数学模型§ 1 最优化问题1 1最优化问题概念1 2最优化问题分类2 3最优化问题数学模型§2经典最优化方法2 1无约束条件极值2 2等式约束条件极值3 3不等式约束条件极值§3线性规划3 1线性规划4 2整数规划§4最优化问题数值算法4 1直接搜索法4 2梯度法5 3罚函数法§5多目标优化问题5 1多目标优化问题5 2单目标化解法5 3多重优化解法5 4目标关联函数解法6 5投资收益风险问题第六章最优化问题数学模型§ 1 最优化问题1 1最优化问题概念（ 1）最优化问题在工业、农业、交通运输、商业、国防、建筑、通信、政府

2、机关等各部门各领域的实际工作中，我们经常会遇到求函数的极值或最大值最小值问题，这一类问题我们称之为最优化问题。而求解最优化问题的数学方法被称为最优化方法。它主要解决最优生产计划、最优分配、最佳设计、最优决策、最优管理等求函数最大值最小值问题。最优化问题的目的有两个：求出满足一定条件下，函数的极值或最大值最小值；求出取得极值时变量的取值。最优化问题所涉及的内容种类繁多，有的十分复杂，但是它们都有共同的关键因素：变量，约束条件和目标函数。（ 2）变量变量是指最优化问题中所涉及的与约束条件和目标函数有关的待确定的量。一般来说，它们都有一些限制条件（约束条件），与目标函数紧密关联。设问题中涉及的变量为

3、Xi,X2,Xn；我们常常也用X（Xi,X2,Xn）表示。（ 3）约束条件在最优化问题中，求目标函数的极值时，变量必须满足的限制称为约束条件。例如，许多实际问题变量要求必须非负，这是一种限制；在研究电路优化设计问题时，变量必须服从电路基本定律，这也是一种限制等等。在研究问题时，这些限制我们必须用数学表达式准确地描述它们。用数学语言描述约束条件一般来说有两种：等式约束条件gi(X) 0,i 1,2, ,m不等式约束条件hi(X)0,i 1,2, ,r或hi(X)0,i1,2,r注：在最优化问题研究中，由于解的存在性十分复杂，一般来说，我们不考虑不等式约束条件h（X）0或h（X）0。这两种约束条件

4、最优化问题最优解的存在性较复杂。（ 4）目标函数在最优化问题中，与变量有关的待求其极值（或最大值最小值）的函数称为目标函数。目标函数常用f（X）f（Xi，X2，,Xn）表示。当目标函数为某问题的效益函数时，问题即为求极大值；当目标函数为某问题的费用函数时，问题即为求极小值等等。求极大值和极小值问题实际上没有原则上的区别，因为求f（X）的极小值，也就是要求f（X）的极大值，两者的最优值在同一点取到。12最优化问题分类最优化问题种类繁多，因而分类的方法也有许多。可以按变量的性质分类，按有无约束条件分类，按目标函数的个数分类等等。一般来说，变量可以分为确定性变量，随机变量和系统变量等等，相对应的最优

5、化问题分别称为：普通最优化问题，统计最优化问题和系统最优化问题。按有无约束条件分类：无约束最优化问题，有约束最优化问题。按目标函数的个数分类：单目标最优化问题，多目标最优化问题。按约束条件和目标函数是否是线性函数分类：线性最优化问题（线性规划），非线性最优化问题（非线性规划）。按约束条件和目标函数是否是时间的函数分类：静态最优化问题和动态最优化问题（动态规划）。按最优化问题求解方法分类：解析法（间接法）数值算法（直接法）无约束有约束古典微分法古典变分法极大值原理库恩 图克定理维搜索法多维搜索法斐波那西法黄金分割法插值法坐标轮换法步长加速法方向加速法 单纯形法随机搜索法最速下降法无约束梯度法数值

6、算法（梯度法）有约束梯度法化有约束为无约束拟牛顿法共轭梯度法变尺度法可行方向法梯度投影法SUMT法SWIFT法复形法单目标化方法多目标优化方法多重目标化方法目标关联函数法网络优化方法1 3最优化问题的求解步骤和数学模型（ 1）最优化问题的求解步骤最优化问题的求解涉及到应用数学，计算机科学以及各专业领域等等，是一个十分复杂的问题，然而它却是需要我们重点关心的问题之一。怎样研究分析求解这类问题呢？其中最关键的是建立数学模型和求解数学模型。一般来说，应用最优化方法解决实际问题可分为四个步骤进行：步骤1：建立模型提出最优化问题，变量是什么？约束条件有那些？目标函数是什么？建立最优化问题数学模型：确定变

7、量，建立目标函数，列出约束条件建立模型。步骤2：确定求解方法分析模型，根据数学模型的性质，选择优化求解方法确定求解方法。步骤3：计算机求解编程序（或使用数学计算软件），应用计算机求最优解计算机求解。步骤4：结果分析对算法的可行性、收敛性、通用性、时效性、稳定性、灵敏性和误差等等作出评价结果分析（ 2）最优化问题数学模型最优化问题的求解与其数学模型的类型密切相关，因而我们有必要对最优化问题的数学模型有所掌握。一般来说，最优化问题的常见数学模型有以下几种：无约束最优化问题数学模型由某实际问题设立变量，建立一个目标函数且无约束条件，这样的求函数极值或最大值最小值问题，我们称为无约束最优化问题。其数学

8、模型为：minf（xi，x2，,a）目标函数例如：求一元函数yf（x）和二元函数zf（x,y）的极值。又例如：求函数f（x1,x2,x3）3x124x226x322x1x24x1x32x2x3的极值和取得极值的点。有约束最优化问题数学模型由某实际问题设立变量，建立一个目标函数和若干个约束条件（等式或不等式），这样的求函数极值或最大值最小值问题，我们称为有约束最优化问题。其数学模型为：gi(x1,x2,xn)0i1,2,m约束条件有约束最优化问题的例子：求函数f(Xi,X2,X3)X1X3Xn在约束条件条件XiX3Xn2008,Xi0,i1,2,n下的最大值和取得最大值的点。线性规划问题数学模型

9、由某实际问题设立变量，建立一个目标函数和若干个约束条件，目标函数和约束条件都是变量的线性函数，而且变量是非负的，这样的求函数最大值最小值问题，我们称为其标准数学模型为：cnXn目标函数1,2, ,m约束条件目标函数约束条件,cn)T ， B (b1,b2, ,bm)T线性最优化问题，简称为线性规划问题。其标准数学模型为：minf(X1,X2,Xn)c1X1c2X2ai1X1ai2X2aimXnbiiXi0矩阵形式：minf(X)CTXAXBX0其中X(X1,X2,Xn)T，C(c1,c2,在线性规划问题中，关于约束条件我们必须注意以下几个问题。注1：非负约束条件Xi0(i1,2,n)，一般来说

10、这是实际问题要求的需要。如果约束条件为Xidi，我们作变量替换ziXidi0；如果约束条件为Xidi，我们作变量替换zidiXi0。注2：在线性规划的标准数学模型中，约束条件为等式。如果约束条件不是等式，我们引入松驰变量，化不等式约束条件为等式约束条件。情况1：若约束条件为ai1X1ai2X2aimXnbi，引入松驰变量原约束条件变为ai1X1ai2X2aimXnzibi。情况2：若约束条件为ai1X1ai2X2aimXnbi，引入松驰变量原约束条件变为ai1X1ai2X2aimXnzibi在其它最优化问题中，我们也常常采取上述方法化不等式约束条件为等式约束条件。实际问题中，我们经常遇到两类特

11、殊的线性规划问题。一类是：所求变量要求是非负整数，称为整数规划问题；另一类是所求变量要求只取0或1，称为0-1规划问题。例如：整数规划问题X23.13s.t.22X134X2285X10,X20且为整数又例如：0-1规划问题maxz3x12x25x3x14x2x34s.t.x1,x2,x30或1。x1x234x2x36非线性规划问题数学模型由某实际问题设立变量，建立一个目标函数和若干个约束条件，如果目标函数或约束条件表达式中有变量的非线性函数，那么，这样的求函数最大值最小值问题，我们称为非线性规划最优化问题，简称为非线性规划问题。其数学模型为：约束条件minf(x1,x2,xn)目标函数gi(

12、x1,x2,xn)0i1,2,m其中目标函数或约束条件中有变量的非线性函数。例如：非线性规划问题minf(x,y)(x1)2yg1(x,y)xy20。g2(x,y)y0上述最优化问题中，目标函数是非线性函数，故称为非线性规划问题。前面介绍的四种最优化数学模型都只有一个目标函数，称为单目标最优化问题，简称为最优化问题。多目标最优化问题数学模型由某实际问题设立变量，建立两个或多个目标函数和若干个约束条件，且目标函数或约束条件是变量的函数，这样的求函数最大值最小值问题，我们称为多目标最优化问题。其数学模型为：minfi(x1,x2,xn)i1,2,s目标函数gi(x1,x2,xn)0i1,2,m约束

13、条件上述模型中有s个目标函数，m个等式约束条件。例如：“生产商如何使得产值最大而且消耗资源最少问题”“投资商如何使得投资收益最大而且风险最小问题”等都是多目标最优化问题。§2经典最优化方法经典最优化方法包括无约束条件极值问题和等式约束条件极值问题两种，不等式约束条件极值问题可以化为等式约束条件极值问题。经典的极值理论：首先，根据可微函数取极值的必要条件确定可能极值点；其次，根据函数取极值的充分条件判断是否取极值？是极大值？还是极小值？这种方法已经几百年的历史了。21无约束条件极值设n元函数f(X)f(Xi，X2，,Xn),求f(X)的极值和取得极值的点。这是一个无约束条件极值问题，经

14、典的极值理论如下。定理1(极值必要条件)：设n元函数f(X)f(Xi，X2，,Xn)具有偏导数，则f(X)在XX*处取得极值的必要条件为：fXi|xi 1,2, ,n定理在此不给出证明，读者可自己参看有关资料。注1:对于一元函数上述定理当然成立，只是偏导数应为导数；注2:定理只是在偏导数存在的前提下的必要条件。如果函数在某一点偏导数不存在，那在这一点处仍然可能取得极值；注3:如果函数在某一点偏导数存在，且偏导数都等于零，那么函数在这一点处也不一定取得极值。例如，函数f(x,y)3x2y2在点(0,0)处偏导数不存在，但在这一点处函数仍然取得极小值零。函数f(x,y)x3y5在点(0,0)处偏导

15、数存在，且偏导数都等于零，但在这一点处函数不取极定理1的作用在于，求出函数的可能极值点，然后，我们再研究这些点是否取得极值。对于许多实际问题来说，函数一定能够取得极大值或极小值，而函数的可能极值点(满足必要条件的点)又只有一点，则这一点当然是函数取得极大值或极小值的点。对于一般函数而言，我们怎样判定函数在某点是否取极值？是极大值？还是极小值？我们有下面的极值的充分条件定理。定理2(极值充分条件)：设n元函数f(X)f(xi,x2,xn)具有二阶偏导数，则f(X)在XX*处取得极值的充分条件为：(1)fIxX*0i2,3,n；(2)黑塞矩阵2fxi22fx2 xi2fxi x22f2-x2xi

16、xnx2 xn*4、L *、X处正止或负止;2fxn xi2fxx x2(3)黑塞矩阵在XX*处正定时，函数取极小值；负定时，函数取极大值。本章内容简要讲解理论，注重实际应用，对于许多经典的定理都不进行证明，读者可自己参看有关资料。例i:求函数f函？2?3)2x26x24x322xix22x2x3的极值。解：(i)根据极值存在的必要条件，确定可能取得极值的点:fxi4xi 2x2 ,fx2i2x2 2x, 2x3 ,fx38x3 2x2令fff0,解得(为乃)(0,0,0)xix2x3(2)根据极值存在的充分条件，确定(xi,x2,x3)(0,0,0)是否是极值点:2f计算-4X12f-2X2

17、122fX38；2f2f0,2f2；Xi X2XiX3X2 X3函数的黑塞矩阵为2 f (0,0,0)2122因为 4 0212442122所以黑塞矩阵负定, 故函数在(为？2, %)(0,0,0)处取得极大值f (0,0,0) 0。2.2等式约束条件极值下面我们研究的是有若干个等式约束条件下，一个目标函数的极值问题，其数学模型为:minf (X1, X2, ,Xn)目标函数st. .gi(X1,X2,Xn)01,2, ,m约束条件拉格朗日(Lagrange)乘数法：(1)令L f (x，X2,Xmigi(X1,X2, ,Xn) i 1称为上述问题的拉格朗日乘数函数，称i为拉格朗日乘数。)均可

18、微，则得到方程组(2)设faL，内)和gi(x1，X2,x(3)若(X1,X2,Xn,1,2,m)是上述方程组的解，则点(X1,X2,Xn)可能为该问题的最优点。拉格朗日(Lagrange)乘数法的本质是：将求有约束条件极值问题转化为求无条件极值问题；所求得的点，即是取得极值的必要条件点。拉格朗日乘数法没有解决极值的存在性问题，但是，如果拉格朗日乘数函数具有二阶连续偏导数，我们也可以应用黑案矩阵来判定函数是否取得极值。在具体问题中，点(X1,xL,X?)是否为最优点通常可由问题的实际意义决定。例2:求表面积为定值a2,而体积为最大的长方体的体积。解：设长方体的三棱长为x,y,z,体积为V;建立

19、数学模型如下：maxVxyz构造拉格朗日乘数函数L(x,y,z)xyz(2xy2yz2xza2),则有解得- a , maxV 6、,636为所求。2.3不等式约束条件极值对于不等式约束条件极值问题:目标函数minf(xi,X2，,Xn)s.t.gi(Xi,X2,Xn)0i1,2,m约束条件我们有与拉格朗日乘数法密切相关的方法库恩图克定理。定理3(库恩图克定理)：对于上述不等式约束条件极值问题，设f(Xi，X2，,4)和gi(Xi,X2,Xn)均可微，令 Lf(X1,X2, ,Xn)假设i存在，则在最优点X X(DLXjfXj_9i Xj(2) gi(Xi,X2,Xn)0(3) igi(Xi,

20、X2, ,Xn) 0migi (Xi,X2, ,Xn) i i(X，x2, ,Xn)处，必满足下述条件:j i,2, ,n；i i,2,m ；i i,2,m；(4)i0根据库恩一图克定理我们可以求解许多不等式约束条件极值问题，值得注意的是应用库恩一图克定理求解不等式约束条件极值问题，定理并没有解决最优解的存在性问题，因此，我们必须另行判断。例3:求解最优化问题(最优解存在)解：构造函数L(x,y,z)(x1)2y1(xy2)2(y),2(x1)i0x1120根据库恩图克定理则有yi(xy2)02y0i0,20解得：X1,y0,10,21；所求最优解为(X,y)(1,0),最优值为0§

21、3线性规划3. 1线性规划设线性规划标准数学模型为：min f(xi,X2, ,Xn) CiXi C2X2cn xn目标函数aiiXi2X2s.t.xi0amXn bi i1,2,mi 1,2,n约束条件矩阵形式： min f(X) CTX目标函数其中AX BX 0约束条件X (Xi,X2, ,Xn)T, C(Cl,C2, ,Cn)T, B (bi,b2, ,bm)T线性规划问题的求解有一整套理论体系，一般来说，应用单纯形法求解。此方法尽管比较复杂，然而在计算机上实现并不困难。解线性规划问题的单纯形法已在许多数学计算软件中实现，我们求解线性规划问题可根据需要，应用数学计算软件求解即可。在此，我

22、们不系统研究其理论，只是简单介绍线性规划的穷举法和单纯形法的基本思想。3.2线性规划的穷举法(1)穷举法基本原理和步骤步骤1:将线性规划问题化成矩阵的标准形式，设系数矩阵的秩R(A)m,则对应线性方程组的基Xi(n m) 0 ,解得对应线性方程组一组解为础解系自由变量的个数为nm个步骤2:穷举法求解：令X1Xi2(X1,X2,Xn)；对应目标函数值为f(X,X2,Xn)工。从n个变量x中选nm个作为自由变量，令它们的值为0,可得到CmCn1m组解。步骤3:确定最优解：如果最优解存在，则上述求解得到的对应CnmCn1m个目标函数值中，最小者(或最大者)即为所求最小(或最大)最优值，对应的解为最优

23、解。步骤4:证明解为最优解：将最优解对应的自由变量看成参数t1,t2,t(nm)；解对应线性方程组得Xibi0b1t1bi2t2b(nm)t(nm),i1,2,n。将对应线性方程组解Xbiobi1t1bi2t2bi(nm)t(nm),i1,2,n代入目标函数得：ffo讯d2t2d(nm)t(nm)。如果di0,i1,2,n，则所求为最小值最优解；否则，线性规划问题无最小值最优解。如果di0,i1,2,n，则所求为最大值最优解；否则，线性规划问题无最大值最优解。例1:目标函数：maXf(X)2X13x2x3解：约束条件的增广矩阵为：10100R(A) 3;A1201001001X2(0,0,5,

24、10,4), f(X) 5;令XiX30,无解;令XiX4(0,5,5,0, 1),不满足非负条件，舍去;令XiX50,解得X(0,4,5,2,0),f(X)17;令X2X30,解得X(5,0,0,5,4),f(X)10；令X2X40,解得X(10,0,5,0,4),不满足非负条件，舍去;令X2X50,无解；令XX40,解得X(5,5,0,0,3),f(X)35;222令X3X50,解得X(5,4,0,3,0),不满足非负条件，舍去；令X4x50 ,解得X(2,4,3,0,0), f(X) 19；所以maxf(X)19,最优解为X(2,4,3,0,0)。证明：令X4t,X5s解得X12t2sx

25、24s目标函数f(X)19ts;X33t2sX0,i1,5因为X4t,X5s非负，所以maxf(X)19,故最优解存在。(2)单纯形法基本原理和步骤将线性规划问题化成矩阵的标准形式，设系数矩阵的秩R(A)m,则对应线性方程组的基础解系的个数为nm个，即有nm个自由参数变量。选取nm个非基变量(自由参数变量)，不妨假设为Xj,jm1,n；解得线性规划问题的典式定理1:如果线性规划问题的上述典式中所有j0,jm1,n；则X(1,2,m,0,0)为最优解。定理2:如果线性规划问题的上述典式中存在某个mk0,且对应i(mk)0,i1,2,m;则线性规划问题无最优解。由定理1和定理2知，如果我们选择适当

26、的nm个非基变量，就可以根据所求得的典式判断最优解的存在与否，从而求解该线性规划问题。单纯形法的思想是：选择适当的基变换(进基和退基)，不断地变换典式，使得典式中目标函数值不断下降，从而求得最优解。其核心为如何选择进基和退基。进基规则和退基规则进基规则一一正检验数最小下标规则，即选取sminj|j0,由此确定Xs为进基。退基规则：选取这样的下标Jr(Ji表示第i个基变量的下标)由此确定xJr离基。单纯形法的基本步骤：步骤1:化线性规划问题为标准形式。步骤2:确定基变量，求得基本可行解和典式；是否满足最优解定理或最优解不存在定理的条件？判断最优解的情况。步骤3:根据进基规则和退基规则，选择进基和

27、退基，进行基变换，求得对应典式。重复进行基变换，直到求出最优解或判断出无最优解为止。例2:解线性规划问题解：(1)约束条件的增广矩阵为：11100A11010,R(A)3;62001所以非基变量个数为两个。(2)选取X1,X2作为非基变量，X3,X4,X5作为基变量，解得典式为不满足最优解定理和最优解不存在定理的条件，故必须进行基变换(3)进行基变换选取进基：120,210,根据sminj|j0得X1为进基选取退基:5 21min 1，21"6，根据min | is 0 , Jr min Ji I1 isisis0得X5为离基进行基变换，求新基的典式：判断：不满足最优解定理和最优解不

28、存在定理的条件，故继续进行基变换(4)继续进行基变换选取进基:选取退基:2 1 0 ,根据s39 21 21叫丁,金min j | j 0得X2为进基。is 0得X3为离基。根据min|is0,JrminJi|1isis进行基变换，求新基的典式：满足最优解定理的条件，根据定理最优解为11 91(4,4，0，2，0)， min f313.2整数规划设纯整数线性规划数学模型为:min f(x1，x2, ,xn) C1X1 C2X2cn xn目标函数,ai1x1 s.t.Xi2X2aim Xnbi0, X为整数i 1,2, ,mi 1,2, ,n约束条件这一类问题与一般线性规划比较起来，似乎是变简单

29、了，但实际上恰恰相反，由于解集是一些离散的整数点集，使得单纯形法失去了应用的基础，求解变得困难而复杂。整数线性规划目前还缺乏统一的解法，这里只介绍分枝定界法，它是目前求解纯整数线性规划和混合整数线性规划最常用的方法，计算机求解整数线性规划的大多数程序也是以它为基础的。分枝定界法：考虑上述纯整数线性规划问题，(1)解对应线性规划问题ai1X1ai2X2s.t.Xi0minf(X1,X2,Xn)C1X1C2X2cnXn目标函数约束条件aimXnbii1,2,mi1,2,n若无最优解，则原纯整数线性规划问题无最优解；若有最优解，最优点(X1,X2,Xn),目标函数最优值z0f(X1,X2,Xn)o若

30、最优点(X1,X2,Xn)全为整数，则为原纯整数线性规划问题的最优解;若最优点(X1,X2,Xn)不全为整数，则进行下一步(2)定界和分枝定界：M0minf(X1,X2,Xn)z0m0其中Mo取原纯整数线性规划问题中，满足约束条件的某一整数可行解所对应的目标函数值。原纯整数线性规划问题的最优解必须满足定界条件。分枝：选取(X1,X2,Xn)中一个不为整数所对应的Xk分枝，R1和R2称为对应线性规划问题的两枝，也是两个新线性规划问题的约束条件。显然，原纯整数线性规划问题的最优解满足R或R2。(3)对W和R2进行剪枝和分枝解R1对应的线性规划问题，对其进行剪枝和分枝:若无最优解，则原纯整数线性规划

31、问题在R内无最优解。不需要对该区域继续讨论一一剪枝若有最优解，最优点(X1,X2,Xn),目标函数的最优值Z1f(X1,X2,Xn)若 Zif(Xi，X2,Xn)M0，则原纯整数线性规划问题在Ri内无最优解。不需要对该区域继续讨论剪枝。若最优点(x;x2,xn)全为整数，则可能为原纯整数线性规划问题的最优解，定界：记M1f(x1,x2,xn)M0,则Miminf(x1，X2,Xn)m0,本分枝求解结束。若最优点(X；X；,Xn)不全为整数，对Ri继续进行分枝。完全类似，解R2对应线性规划问题，对其进行剪枝和分枝。依此类推，对所有分枝进行求解，剪枝，分枝，定界；直至求得最优解。(4)最优解的确定

32、若某Mkm。，则为最优解，求解结束。若所有分枝求解结束，则最后的上界Mk即为最优解。例3:应用分枝定界法，求解整数线性规划问题解：设原整数线性规划问题目标函数的最优值为z*,(1)求解线性规划问题：minzx13x2得最优解为Xi8.12,X23.13；minz17.51。3.13记约束区域 22x134x2285为R0,x20(2)对R进行分枝：选取最优解中不是整数的变量，例如Xi,将R分成两个子区域Ri,R2x1 9x2 3.13x18x23.1322x134X2 2850,X2 034X2 2850,X2 0(3)定界：确定最优值z*的上下界。由(1)中求得的最优值知z*17.51;而z

33、*的上界可由R内的任意一个可行解确定，例如，X17,x24即为一个可行解。故z*19。从而，17.51z*19。(4)在R1内求最优解，得x19,X23.13;minz18.39。(5)在R2内求最优解，得x18,X23.21;minz17.62。(6)因为R1内最优解不全是整数，因而必须继续对R1分枝：(7)显然R12内无解，剪枝。在R1内求最优解，得x19,X24;minz21;为整数可行解。但因17.51z*19,而2119,故剪枝。(8)因为R2内最优解不全是整数，因而必须继续对R2分枝：(9)显然R22内无解，剪枝。在R21内求最优解，得x16.77,x24；minz18.77。(1

34、0)因为R21内最优解不全是整数，因而必须继续对R21分枝：(11)在R212内求最优解，得x16,x24.5；minz19.5。因minz19.5大于z*的上界，故剪枝。(12)在R211内求最优解，得x17,x24；minz19。所求原整数规划问题的最优解为：x17,x24；minz19。§4最优化问题数值算法最优化问题的数值算法很多，常用的算法多为搜索法，本节只介绍搜索法的基本思想、无约束最优化问题的最速下降法(梯度法)和有约束最优化问题的罚函数法。4 1搜索算法考虑无约束最优化问题：minf(x1,x2,xn)我们已经讨论了这类问题的最优解条件，这必须用到函数的解析性质。我们

35、的方法是，先利用必要条件求出平稳点，再应用充分条件判断是否是极值点。但是，我们必须求解一个n个变量n个方程的方程组，并且常常是非线性的。这只有在特殊的情况下，才能求出它的精确解。在一般情况下，都不能用解析法求得精确解。更何况许多实际问题中，函数的解析表达式很难得到。因此，我们必须寻求一些切合实际问题的行之有效的数值解法。搜索算法就是我们常用的方法。(1)搜索算法的基本思想：假定目标函数f(X)极小值问题。首先，确定目标函数f(X)的初始点X0；然后，按照一定规则产生一个点列Xk，这种规则称为算法；规则必须满足(1)点列Xk收敛；(2)点列Xk收敛到目标函数f(X)的极小值点。(2)搜索算法的基

36、本步骤：选定初始点X0(越接近最优点越好)，允许误差0，令k0。假定已得非最优点Xk，则选取一个搜索方向Sk，满足：目标函数f(X)下降，或gradf(Xk)?Sk0o选定搜索步长k0，Xk1XkkSk，满足：f(Xk1)f(XkkSk)f(Xk)。判断Xk1是否是最优点或是满足要求的近似解。假定给定精度要求为0，常用确定求近似解搜索结束的方法有：|gradf(Xk1)|梯度模确定法；|f(Xki)f(Xk)目标函数差值绝对误差法；|Xk1XkI相邻搜索点绝对误差法。如果Xki满足给定精度要求，则搜索完成，近似最优点为X*Xki；如果Xki不满足给定精度要求，令kk1返回(2)继续搜索。注意1

37、:我们的搜索算法一般得到的都是局部最优解。注意2:确定求近似解搜索结束的方法还有目标函数差值相对误差法;If(Xk1)f(Xk)|If(Xk)|Xk 1 Xk I|Xk|相邻搜索点相对误差法(3)搜索算法的关键因素：从搜索算法的基本步骤中，我们知道，搜索算法的关键因素为：一是搜索方向，二是搜索步长。搜索方向的选择，一般考虑既要使它尽可能的指向极小值点，又要不至于花费太多的计算量。搜索步长的选择，既要确保目标函数的下降性质，又要考虑近似解的精度要求，还要考虑算法的计算量，问题十分复杂。常用方法有，固定步长法，最优步长法和变步长法。固定步长法(简单算法)是选取k0为固定值。方法简单，但是有时不能保

38、证目标函数的下降性质。最优步长法(一维搜索算法)是选取k使得，这是一个关于单变量的函数求极小值问题，这样确定的步长称为最优步长。变步长法(可接受点算法)是任意选取只要使得f(Xk1)f(Xk)即可这种选取步长的方法，确保了目标函数的下降性质，尽管每次选取的步长不是最优的，但实践证明，方法能达到更好的数值效果。总之，当搜索方向确定以后，步长就是决定最优化算法好坏的重要因素，因此，我们必须特别注重步长的选取问题。(4)搜索算法的收敛性：搜索算法的收敛性是指，由某算法得到的点列XJ能够在有限步骤内收敛到目标函数f(X)的最优点或能够在有限步骤内达到满足精度要求的目标函数f(X)的最优点的近似值。显然

39、，只有具有收敛性质的算法才有意义。搜索算法的收敛速度：作为一个好的算法，还必须要求它以较快的速度收敛于最优解。阶收敛定义：对于收敛于最优解X*的序列Xk,若存在与k无关的数0和1,当k从某个心开始时，有|Xk1X*|XkX*I成立，则称序列Xk收敛的阶为，或称阶收敛当1时，称迭代序列Xk为线性收敛；当12时，称迭代序列Xk为超线性收敛；当2时，称迭代序列Xk为二阶收敛。一般来说，线性收敛是比较慢的，而二阶收敛则是很快的，超线性收敛介于二者之间。如果一个算法具有超线性以上的收敛速度，我们就认为是一个好的算法了。42无约束最优化问题的梯度法无约束最优化问题的计算方法很多。无约束最优化问题的计算方法

40、分为两大类：一类是解析法，包括经典最优化方法，最速下降法(梯度法)，共轭梯度法，牛顿法和变尺度法等。另一类是直接法，包括坐标轮换法，步长加速法，方向加速法和单纯形法等。所谓解析法就是在方法的计算过程中，应用到了函数的解析性质(可导性质等)；所谓直接法就是在方法的计算过程中，仅仅涉及目标函数值的计算，而不涉及函数导数等解析性质。我们在这里只介绍最速下降法(梯度法)。最速下降法理论根据：早在1847年，法国著名数学家Cauchy就曾提出，从任意给定点出发，函数沿哪个方向下降最快的问题。这个问题已从理论上解决了，即沿着函数在该点的负梯度方向前进时，函数下降最快。这就是最速下降法的理论根据。最速下降法

41、的搜索步骤：步骤1：选定初始点X0(越接近最优点越好)，允许误差0，令k0。步骤2：假定已得非最优点Xk，计算梯度gradf(Xk)，选取搜索方向Skgradf(Xk)步骤3：选定搜索步长k0，Xk1XkkSk，满足：f(XkkSk)minf(XkSk)。0步骤4：判断Xk1是否是最优点或是满足要求的近似解。根据精度要求，检验是否满足收敛性判断准则：|gradf(Xki)|或|f(Xki)f(Xk)|或|XkiX*如果Xk1满足给定精度要求，则搜索完成，近似最优点为X*Xk1；如果Xk1不满足给定精度要求，令kk1返回(2)继续搜索。例1：应用最速下降法求解minf(X)x1225x22。解：

42、(1)选定初始点X0(2,2)，允许误差0.2，置k:0收敛判断准则|f(Xk1)f(Xk)|。Sk 2x1, 50x2 |X Xk2)计算梯度gradf(Xk)，选取搜索方向Skgradf(Xk)gradf(Xk)2x1,50x2|XXk第一点搜索计算：gradf(Xo)4,100,So4,100(3)选定搜索步长k0,Xk1XkkSk,满足：第一点搜索计算：求最优步长解得00.02。(4)判断Xki是否是最优点或是满足要求的近似解。第一点搜索计算：Xi(1.92,0)验证收敛判断准则|f(X1)f(X°)|100.310.02,不满足，继续搜索依次类推，直到搜索到最优解或满足精度

43、要求为止搜索计算列表如下：搜索步长k搜索方向Sk搜索点Xk函数值f(Xk)X2(0,0)为最优解4.3罚函数法对于约束最优化问题也有许多种方法，本段只介绍把约束最优化问题转化为无约束最优化问题的一种求解方法一一罚函数法。分为等式约束最优化问题和不等式约束最优化问题两种情况讨论。(1)等式约束最优化问题的罚函数法首先，考虑等式约束最优化问题假定上述等式约束最优化问题的最优解存在。若记DX|gi(X)0,i1,2,m,XRn,m构造辅助函数T(X,M)f(X)Mgi(X)2罚函数i1其中M0(罚因子)是一个充分大的正数。定理1:若对于某确定数M0,无约束最优化问题的最优解X*D,则X*必为原等式约

44、束最优化问题的最优解。m证明：设无约束最优化问题minT(X,M)f(X)Mgi(X)2i1的最优解X*D,则有：gi(X)0i1,2,m而当XD时，T(X,M)f(X)所以minf(X)minT(X,M)T(X*,M)f(X*)即X*为原等式约束最优化问题的最优解。定理2:设f(X)和gi(X)0,i1,2,均为连续函数，若对于任意正数M0,无约束最优化问题的最优解X*(M)D,且limX*(M)X*,M则limX*(M)X*为原等式约束最优化问题的最优解。M定理2的证明请参看有关参考资料。根据定理1和定理2,我们就可以将通过构造罚函数的方法化为无约束最优化问题求解，这种方法称为罚函数法。罚

45、函数法的步骤：(等式约束最优化问题罚函数法)m步骤1:构造罚函数T(X,M)f(X)Mgi(X)2,i1选定M10,允许误差0,令k:1;步骤2:求无约束问题minT(X,Mk)的最优解X；步骤3:判断X；是否是最优点或是满足要求的近似解。根据精度要求，检验是否满足收敛性判断准则：m或gi(X；)2i1如果满足收敛性判断准则，则X*X；,结束搜索；否则，令k:k1,取Mk1Mk0,返回(2),继续搜索。下面我们通过一个简单的例子来说明等式约束最优化问题的罚函数法。例2:应用罚函数法求解非线性规划问题解：构造罚函数：T(X,Mk)x12x2Mk(x21)2求罚函数的最优解：应用解析法工2x1,1

46、2x22Mk(X21)X1x2令上述两式等于零，解得x10,x21 Mk令Mk得x10,x21为所求最优解。2 2)不等式约束最优化问题的罚函数法对于，不等式约束最优化问题假定上述不等式约束最优化问题的最优解存在。由于不等式约束条件gi(X)0,i1,2,m等价于等式约束条件因而，上述不等式约束最优化问题可以转化为问题类似问题(1)构造罚函数则将上述等式约束最优化问题的求解转化为下面无约束最优化问题的求解：定理3：若对于某确定数M0，无约束最优化问题的最优解X*D，则X*必为原不等式约束最优化问题的最优解，其中DX|gi(X)0,i1,2,m,XRn。定理4:设(1)f(X)和gi(X)0,i

47、1,2,m均为连续函数；(2)原不等式约束最优化问题的最优解X*存在；(3)数列Mk满足0M1M2Mk且limMk；k(4)对任意Mk0,问题minT(X,M)的最优解XkX(Mk)都存在，且有界;(5)点列XJ存在极限点；则：点列Xk的极限点是原不等式约束最优化问题的最优解。罚函数法的步骤：(不等式约束最优化问题罚函数法)m步骤1：构造罚函数T(X,M)f(X)Mmin(0,gi(X)2，i1选定M10，允许误差0，令k:1；步骤2：求无约束问题minT(X,Mk)的最优解Xk*；步骤3：判断Xk*是否是最优点或是满足要求的近似解。根据精度要求，检验是否满足收敛性判断准则：m或gi(Xk)2

48、i1如果满足收敛性判断准则，则X*Xk*，结束搜索；否则，令k:k1，取Mk1Mk0，返回(2)，继续搜索。例3：应用罚函数法求解非线性规划问题m解：构造罚函数T(X,M)f(X)Mmin(0,gi(X)2i1求T(X,Mk)的极小值点当Xi2x0,或Xi。时，显然上两式不能同时等于零，所以，此时T(X,Mk)不存在极小值点。当X12X20,X10时，有令上面两式等于零：-0,-0;XiX2解得T(X,Mk)的极小值点为当Mk取不同值时，可得到相应的Xk值，计算如下表1101001000-0.25-0.04545-0.004950-0.00049950-0.4375-0.1415-0.0049

49、75-0.00049980根据定理得，原问题的极小值点为X*(0,0),极小值为f(X*)0§5多目标优化问题在许多实际的最优化问题中，常常遇到目标函数是几个的情况，这一类问题我们称之为多目标优化问题。例如，投资方向选择问题，我们不仅要求投资的收益最大，而且要求投资的风险最小。再例如，购买商品问题，我们既要考虑商品的价格，又要考虑商品的质量，甚至还要考虑商品的性能等等。所谓多目标优化问题是指：目标函数是两个或两个以上的最优化问题。其数学模型为：minfi(x1,x2,xn)i1,2,s目标函数gi(Xi,X2,Xn)0i1,2,m约束条件例1：求解多目标优化问题minX2和miny解

50、：易求x0,y1时，minx20,miny1。例2:求解多目标优化问题maxx2和miny解：显然，无最优解。5.1多目标优化问题的解多目标优化问题解的存在性极其复杂，这是由多目标优化问题的目标函数多个性和目标函数相互之间的复杂性质决定的。由于目标函数在很多情况下不可能同时达到最大值或最小值，因而，多目标最优化问题很少有最优解，而实际问题又要求我们做出决择，求得一个比较好的解。什么样的解才是我们需要的解呢？对于同一个问题不同的要求导致不同的求解标准，从而就会得到不同的求解结果。为此，我们给出多目标最优化问题的条件最优解概念。最优解：满足约束条件且使所有目标函数达到要求的最大值或最小值的点称为多

51、目标优化问题的最优解。可行解：满足多目标优化问题的约束条件的点称为可行解。条件最优解：满足多目标优化问题的约束条件且满足根据需要设定条件的可行解称为条件最优解。对于一个多目标优化问题，即使最优解存在，要求解它也是十分困难的，特殊情况下，我们也只好用搜索法求解。更何况它常常还不存在最优解，因而我们必须寻求其求解条件最优解的方法。为了求得满足我们要求的解，常常不得不设定一些新的条件，从而求得条件最优解。设定新条件的方法是我们求解多目标优化问题的基本方法。下面的“单目标化方法、多重目标函数方法和目标关联函数方法”都是针对目标函数设定新条件的方法。52单目标化解法将原多目标优化问题多个目标函数转化成为

52、只有一个目标函数的单目标优化问题求解的方法称为单目标化方法。(1)单目标化解法的基本思想步骤1：构造一个新的目标函数ff(f1,f2,fs)满足性质：在约束条件的区域内f(fi，f2，,fs)是fi,f2,fs的单调增函数。特别注意：构造新目标函数也可以根据实际问题，将f(fi，f2，,fs)定义为fi,f2,fs的不减函数。步骤2：建立单目标优化数学模型minff(f1,f2,fs)目标函数gi(x1,x2,xn)0i1,2,m约束条件步骤3：求解上述单目标优化数学模型得到：单目标优化问题的最优解，从而可得到原多目标优化问题的最优解或条件最优解。（ 2） 单目标优化问题最优解的性质单目标优化

53、问题的最优解与原多目标最优化问题的最优解有着密切的内在关系。下面的定理揭示了两者之间最重要的一种关系。定理1：设f(fi,f2，,fs)是fi,f2,fs的单调增函数，原多目标最优化问题的最优解存在，则单目标优化问题的最优解存在，且为原多目标最优化问题的最优解。证明：显然，单目标优化问题的最优解存在。设原多目标最优化问题的最优解为X*，则在该点处，目标函数f1,f2,fs都取得最小值。设单目标最优化问题的最优解为Y*，则在该点处，目标函数f(fl,f2,fs)取得最小值f(Y*)。显然，1)fi(X*)fi(Y*)i1,2,s2)f(X*)f(Y*)又因为，f(fi，f2，fs)是fi,f2,fs的单调增函数，根据1)有：f(X*)f(Y*)所以，f(X*)f(Y*)，故必有fi(X*)fi(Y*)ii,2,s即Y*为原多目标最优化问题的最优解。定理告诉我们：如果多目标最优化问题的最优解存在，则只需求解一个单目标最