多目标最优化模型

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

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

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

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

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

6、换法步长加速法多维搜索法，方向加速法单纯形法随机搜索法'最速下降法壬勿t小蟾t详、#I拟牛顿法无约束梯度法共轲梯度法有约束梯度法3变尺度法力行方向法梯度投影法SUMT法化有约束为无约束SWIFT法、复形法单目标化方法多目标优化方法多重目标化方法、目标关联函数法网络优化方法1. 3最优化问题的求解步骤和数学模型（1）最优化问题的求解步骤最优化问题的求解涉及到应用数学，计算机科学以及各专业领域等等，是一个十分复杂的问题，然而它却是需要我们重点关心的问题之一。怎样研究分析求解这类问题呢？其中最关键的是建立数学模型和求解数学模型。一般来说，应用最优化方法解决实际问题可分为四个步骤进行：步骤1:

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

8、题设立变量，建立一个目标函数且无约束条件，这样的求函数极值或最大值最小值问题，我们称为无约束最优化问题。其数学模型为：minf(xhx2,Xn)目标函数例如：求一元函数y=f(x)和二元函数z=f(x,y)的极值。又例如：求函数f(x1，x2,x3)=3x2+4x2+6x：+2xx24xx32x2x3的极值和取得极值的点。有约束最优化问题数学模型由某实际问题设立变量，建立一个目标函数和若干个约束条件(等式或不等式)，这样的求函数极值或最大值最小值问题，我们称为有约束最优化问题。其数学模型为：minf(x1，x2，xn)目标函数gi(x1,x2,xn)=0i=1,2,，m约束条件有约束最优化问题

9、的例子：求函数f(x1,x2,x3)=x1x3xn在约束条件条件xi+x3+xn=2008,xi>0,i=1,2,，n下的最大值和取得最大值的点。线性规划问题数学模型由某实际问题设立变量，建立一个目标函数和若干个约束条件，目标函数和约束条件都是变量的线性函数，而且变量是非负的，这样的求函数最大值最小其标准数学模型为:目标函数约束条件目标函数约束条件值问题，我们称为线性最优化问题，简称为线性规划问题minf(xi,x2,.，xn)=cxiax2Cnxnaiixi82x2aimxn=bii=1,2,mxi-0矩阵形式：minf(X)=CTXAX=BX-0其中X=(Xi，X2，xn)T,C=(

10、Ci,C2,，Cn)T,B=(，达,，bm)T在线性规划问题中，关于约束条件我们必须注意以下几个问题。注1:非负约束条件xi>0(i=1,2,，n),一般来说这是实际问题要求的需要。如果约束条件为为至di,我们作变量替换Zi=xi-di至0;如果约束条件为XiEdi,我们作变量替换Zi=di-为至0。注2:在线性规划的标准数学模型中，约束条件为等式。如果约束条件不是等式，我们引入松驰变量，化不等式约束条件为等式约束条件。情况1:若约束条件为ai1x1+ai2x2+aimxn>bi,引入松驰变量原约束条件变为aMXi+ai2X2+amXnZi=bi。情况2:若约束条件为aiiXi+a

11、i2X2+amXn<bi,引入松驰变量原约束条件变为aMXi-ai2X2-amXn,Zi=6在其它最优化问题中，我们也常常采取上述方法化不等式约束条件为等式约束条件。实际问题中，我们经常遇到两类特殊的线性规划问题。一类是：所求变量要求是非负整数，称为整数规划问题；另一类是所求变量要求只取0或1,称为0-1规划问题。例如：整数规划问题x2-3.13s.t.22x1+34x2至285。X120,X2至0且为整数又例如：0-1规划问题maxz=3x1-2x2+5x3X十2x2-x3E2X+4x2+x3<4s.t.x1,x2,x3=0或1。Xx2m34x2x3£6非线性规划问题数

12、学模型由某实际问题设立变量，建立一个目标函数和若干个约束条件，如果目标函数或约束条件表达式中有变量的非线性函数，那么，这样的求函数最大值最小值问题，我们称为非线性规划最优化问题，简称为非线性规划问题。其数学模型为：minf(X1,X2，Xn)目标函数gi(X1,X2,Xn)=0i=1,2,m约束条件其中目标函数或约束条件中有变量的非线性函数。例如：非线性规划问题minf(x,y)=(x-1)2y4(x,y)=x+y-2，03o9(x,y)=y«0上述最优化问题中，目标函数是非线性函数，故称为非线性规划问题。前面介绍的四种最优化数学模型都只有一个目标函数，称为单目标最优化问题，简称为最

13、优化问题。多目标最优化问题数学模型由某实际问题设立变量，建立两个或多个目标函数和若干个约束条件，且目标函数或约束条件是变量的函数，这样的求函数最大值最小值问题，我们称为多目标最优化问题。其数学模型为：minfi(Xi,X2，Xn)i=1,2,，s目标函数gi(xi,X2,Xn)=0i=1,2,m约束条件上述模型中有s个目标函数，m个等式约束条件。例如：“生产商如何使得产值最大而且消耗资源最少问题”“投资商如何使得投资收益最大而且风险最小问题”等都是多目标最优化问题。§2经典最优化方法经典最优化方法包括无约束条件极值问题和等式约束条件极值问题两种，不等式约束条件极值问题可以化为等式约束

14、条件极值问题。经典的极值理论：首先，根据可微函数取极值的必要条件确定可能极值点；其次，根据函数取极值的充分条件判断是否取极值？是极大值？还是极小值？这种方法已经几百年的历史了。2. 1无约束条件极值设n元函数f(X)=f(Xi,X2，Xn),求f(X)的极值和取得极值的点。这是一个无约束条件极值问题，经典的极值理论如下。定理1(极值必要条件)：设n元函数f(X)=f(x,X2，Xn)具有偏导数,则f(X)在X=X处取得极值的必要条件为：|XM=0i=1,2,，n。XX-Xi定理在此不给出证明，读者可自己参看有关资料。注1:对于一元函数上述定理当然成立，只是偏导数应为导数；注2:定理只是在偏导数

15、存在的前提下的必要条件。如果函数在某一点偏导数不存在，那在这一点处仍然可能取得极值；注3:如果函数在某一点偏导数存在，且偏导数都等于零，那么函数在这一点处也不一定取得极值。例如，函数f(X,y)=VX2+y2在点(0,0)处偏导数不存在，但在这一点处函数仍然取得极小值零。函数f(X,y)=X3+y5在点(0,0)处偏导数存在，且偏导数都等于零，但在这一点处函数不取极值。定理1的作用在于，求出函数的可能极值点，然后，我们再研究这些点是否取得极值。对于许多实际问题来说，函数一定能够取得极大值或极小值，而函数的可能极值点(满足必要条件的点)又只有一点，则这一点当然是函数取得极大值或极小值的点。对于一

16、般函数而言，我们怎样判定函数在某点是否取极值？是极大值？还是极小值？我们有下面的极值的充分条件定理。定理2(极值充分条件)：设n元函数f(X)=f(Xi，X2，Xn)具有二阶偏导数，则f(X)在X=X*处取得极值的充分条件为:(1)i=2,3,，n;f|*=0-1X义-为一(2)黑塞矩阵?ffx；:2f：X2二X1；：2f-X1：X2If：x；?fX1-xnIfX2：Xn在X=X处正止或负止;(3)短f<cXncX1Ifxx：X2If-2Xn黑塞矩阵在X=X本章内容简要讲解理论,处正定时，函数取极小值；负定时，函数取极大值。注重实际应用，对于许多经典的定理都不进行证明，读者可自己参看有关

17、资料。例1:求函数f(%,X2,X3)=2x26x；4x2+2x1x2+2x2x3的极值。解：(1)根据极值存在的必要条件，确定可能取得极值的点:开fFf=-4x,2x2,=-12x22x,2x3,=-8x32x2-：X1/：X3.干干二f,一令=0,斛行(x),x2,x3)=(0,0,0)。：X1：X2仅3(2)根据极值存在的充分条件，确定(Xi，X2，X3)=(O,0,0)是否是极值点:计算-2Xi-4-2X2;2f=-12,二=-8;X3：2f二2,-X1-x2.224:2;'XfX3二X2X34-420、函数的黑塞矩阵为172f(0,0,0)=2-122<02咒20-12

18、2=320<0；2-8-4一一一42一因为4<0,=44>0,22-120所以黑塞矩阵负定，故函数在（X1,X2,X3）=（0,0,0）处取得极大值f（0,0,0）=02.2等式约束条件极值下面我们研究的是有若干个等式约束条件下，一个目标函数的极值问题，其数学模型为：目标函数约束条件minf(xl,Xn)s.t.gi(X1,X2,Xn)=0i=1,2,m拉格朗日（Lagrange）乘数法:(1)令mLf(X1,x2,xn)-igi(X1,X2,xn)i1称为上述问题的拉格朗日乘数函数，称A为拉格朗日乘数。（2）设f（X1，X2，XnMDgi（X1,X2，Xn）均可微，则得到方

19、程组（3）若（X1,X2，Xn,兀，九2，九m）是上述方程组的解，则点（X1，X2，Xn）可能为该问题的最优点。拉格朗日（Lagrange）乘数法的本质是：将求有约束条件极值问题转化为求无条件极值问题；所求得的点，即是取得极值的必要条件点。拉格朗日乘数法没有解决极值的存在性问题，但是，如果拉格朗日乘数函数具有二阶连续偏导数，我们也可以应用黑案矩阵来判定函数是否取得极值。在具体问题中，点（X1,%,，£）是否为最优点通常可由问题的实际意义决定。例2：求表面积为定值a2,而体积为最大的长方体的体积。解：设长方体的三棱长为x,y,z,体积为V;建立数学模型如下：maxV=xyz构造拉格朗日

20、乘数函数L（x,y,z）=xyz+凝2xy+2yz+2xza2）,则有解得x=y=z=gamaxV=a3为所求。6362.3不等式约束条件极值对于不等式约束条件极值问题:目标函数minf的为，Xn)s.t.gi(X1,X2,Xn)0i=1,2,m约束条件我们有与拉格朗日乘数法密切相关的方法库恩图克定理。定理3(库恩图克定理)：对于上述不等式约束条件极值问题，设f(x1,X2，4)m和gi(x1,X2，Xn)均可微，令L=f(x1,X2，Xn)+Z上igi(x1,X2,',Xn)i4假设九i存在，则在最优点X=X=(XX2，Xn)处，必满足下述条件:(D%;:Xjj=1,2,，n；(2)

21、gi(Xi,X2,出)£0i=1,2,，m;(3)、gi(Xi,X2,Xn)=0i=1,2,m;(4)根据库恩图克定理我们可以求解许多不等式约束条件极值问题，值得注意的是应用库恩一图克定理求解不等式约束条件极值问题，定理并没有解决最优解的存在性问题，因此，我们必须另行判断。例3:求解最优化问题(最优解存在)解：构造函数L(x,y,z)=(x1)2+y+%(x+y2)+%(y),比口=2(x1)+%=0改根据库恩图克定理则有=1+A上2=0cy%(x+y-2)=0&2y=01-0,2-0解得:X=1y=0,%=0,%=1；所求最优解为(x,y)=(1,0),最优值为0。

22、7;33.1线性规划线性规划设线性规划标准数学模型为:minf(X1,x2,xn)=c1x1c2x2+cnxn目标函数二s.t.1aixiai2x2amxn=bi=1,2,mi=1,2,n矩阵形式：minf(X)=CTX-约束条件目标函数约束条件AX二BX.0其中X=(x1，x2，xn)T,C=(Ci，C2,，cn)T,B=(b1,b2,，bm)T线性规划问题的求解有一整套理论体系，一般来说，应用单纯形法求解。此方法尽管比较复杂，然而在计算机上实现并不困难。解线性规划问题的单纯形法已在许多数学计算软件中实现，我们求解线性规划问题可根据需要，应用数学计算软件求解即可。在此，我们不系统研究其理论，

23、只是简单介绍线性规划的穷举法和单纯形法的基本思想。3.2线性规划的穷举法(1)穷举法基本原理和步骤步骤1:将线性规划问题化成矩阵的标准形式，设系数矩阵的秩R(A)=m,则对应线性方程组的基础解系自由变量的个数为n-m个。步骤2:穷举法求解：令。=%=.一=为65)=0,解得对应线性方程组一组解为(x1,x2，xn)；对应目标函数值为f(x1,x2，xn)=fi。从n个变量x中选n-m个作为自由变量，令它们的值为0,可得至UCm=C；组解。步骤3:确定最优解：如果最优解存在，则上述求解得到的对应Cm=C：个目标函数值中，最小者(或最大者)即为所求最小(或最大)最优值，对应的解为最优解。步骤4:证

24、明解为最优解：将最优解对应的自由变量看成参数匕工,，.；解对应线性方程组得为=bi°+如匕+bi2t2+bi(ne%Gi=1,2,，n。将对应线性方程组解xi=bi0bit,bi2t2,，bi(n.)t(n_m),i=1,2,，n代入目标函数得：f=f0,dt1d2t2''d(n_m)t(n_m)。如果di至0,i=1,2，n,则所求为最小值最优解；否则，线性规划问题无最小值最优解如果diE0,i=1,2,，n,则所求为最大值最优解；否则，线性规划问题无最大值最优解。例1:目标函数：maxf(X)=2x1-3x2x3解：约束条件的增广矩阵为：10100、A=12010

25、,R(A)=3;、01001,令x=x2=0,解得X=(0,0,5,10,4),f(X)=5;令x=x3=0,无解；令x1=x4=0,解得X=(0,5,5,0,-1),不满足非负条件，舍去；令x1=x5=0,解得X=(0,4,5,2,0),f(X)=17;令x2=x3=0,解得X=(5,0,0,5,4),f(X)=10;令x2=x4=0,解得X=(10,0,-5,0,4),不满足非负条件，舍去；令x2=x5=0,无解；5335令x3=x4=0,解得X=(5,2,0,0,3),f(X)=35;令x3=x5=0,解得X=(5,4,0,-3,0),不满足非负条件，舍去；令x4=x5=0,解得X=(2

26、,4,3,0,0),f(X)=19;所以maxf(X)=19,最优解为X=(2,4,3,0,0)。证明：令x4=t,x5=s解得x1=2-t+2s彳x2=4-S目标函数f(X)=19-1-s；x3=3t-2sX-0,i=1,5因为x4=t,x5=s非负，所以maxf(X)=19,故最优解存在。(2)单纯形法基本原理和步骤将线性规划问题化成矩阵的标准形式，设系数矩阵的秩R(A)=m，则对应线性方程组的基础解系的个数为nm个，即有nm个自由参数变量。选取nm个非基变量（自由参数变量）,不妨假设为xj=m+1n；解得线性规划问题的典式定理1:如果线性规划问题的上述典式中所有<0,j=m+1,，

27、n；贝X=（%，%，,0tm。，0）为最优解。定理2:如果线性规划问题的上述典式中存在某个%#>0,且对应月盟E0,i=1,2,，m；则线性规划问题无最优解。由定理1和定理2知，如果我们选择适当的nm个非基变量，就可以根据所求得的典式判断最优解的存在与否，从而求解该线性规划问题。单纯形法的思想是：选择适当的基变换（进基和退基），不断地变换典式，使得典式中目标函数值不断下降，从而求得最优解。其核心为如何选择进基和退基。进基规则和退基规则进基规则一一正检验数最小下标规则，即选取s=minj|%>0,由此确定xs为进基。退基规则：选取这样的下标J,（J表示第i个基变量的下标）由此确定Xj

28、r离基。单纯形法的基本步骤：步骤1:化线性规划问题为标准形式。步骤2:确定基变量，求得基本可行解和典式；是否满足最优解定理或最优解不存在定理的条件？判断最优解的情况。步骤3:根据进基规则和退基规则，选择进基和退基，进行基变换，求得对应典式。重复进行基变换，直到求出最优解或判断出无最优解为止。例2:解线性规划问题解：（1）约束条件的增广矩阵为：M1100”A=11010,R（A）=3;、62001所以非基变量个数为两个。（2）选取X1,X2作为非基变量，X3,X4,X5作为基变量，解得典式为不满足最优解定理和最优解不存在定理的条件，故必须进行基变换。（3）进行基变换选取进基：=2A0,%=1&g

29、t;0,根据s=minj|%A0得X1为进基选取退基:二min；,21根据H=min*|Pis>0,Jr=minJi|-=e,Pis>0得X5为离基"is-is进行基变换，求新基的典式：判断：不满足最优解定理和最优解不存在定理的条件，故继续进行基变换(4)继续进行基变换选取进基:1->0,根据s=minj|%a0得X2为进基。3选取退基:min9,2148aa根据H=min才_|Pis>0,Jr=minJi|y-=9,Pis>0得X3为离基"is"is进行基变换，求新基的典式：满足最优解定理的条件，根据定理最优解为V,119c131X

30、=(一,0,0),minf=o44243.2整数规划设纯整数线性规划数学模型为：minf(Xi,X2,Xn)=CXiC2X2CnXn目标函数广s.t.&iXi-ai2X2.-amXn=biX至0,Xi为整数i=1,2,mi=1,2,n约束条件这一类问题与一般线性规划比较起来，似乎是变简单了，但实际上恰恰相反，由于解集是一些离散的整数点集，使得单纯形法失去了应用的基础，求解变得困难而复杂。整数线性规划目前还缺乏统一的解法，这里只介绍分枝定界法，它是目前求解纯整数线性规划和混合整数线性规划最常用的方法，计算机求解整数线性规划的大多数程序也是以它为基础的。分枝定界法：考虑上述纯整数线性规划问

31、题，目标函数(1)解对应线性规划问题minf(Xi,X2,Xn)=CXiC2X2CnXns.t/9i1Xi+ai2X2+-+amXn=卜i=1,2,mi=1,2,n约束条件若无最优解，则原纯整数线性规划问题无最优解;若有最优解，最优点(X1,X2，Xn),目标函数最优值Z0二f(Xi,X2，Xn)。若最优点(Xi,X2，Xn)全为整数，则为原纯整数线性规划问题的最优解;若最优点（x1,x2，xn）不全为整数，则进行下一步。（2）定界和分枝定界：M0minf（x1,x2,xn）：;z0=m0其中Mo取原纯整数线性规划问题中，满足约束条件的某一整数可行解所对应的目标函数值。原纯整数线性规划问题的最

32、优解必须满足定界条件。分枝：选取（x1,x2，xn）中一个不为整数所对应的xk分枝，Ri和R2称为对应线性规划问题的两枝，也是两个新线性规划问题的约束条件。显然，原纯整数线性规划问题的最优解满足Ri或R2。（3）对R和R2进行剪枝和分枝解Ri对应的线性规划问题，对其进行剪枝和分枝：若无最优解，则原纯整数线性规划问题在Ri内无最优解。不需要对该区域继续讨论一一剪枝。若有最优解，最优点（x1,x2，xn）,目标函数的最优值Z1=f（x1,x2，xn）。若Zi=f（x?,xi，x?）AMo,则原纯整数线性规划问题在Ri内无最优解。不需要对该区域继续讨论一一剪枝。若最优点（丘以，X）全为整数,则可能为

33、原纯整数线性规划问题的最优解，定界：记M1=f（x,x2，xn）MM0,则Mi之mnf（x1，x?，xn）之m0,本分枝求解结束。若最优点（工,二,，王）不全为整数，对Ri继续进行分枝。完全类似，解R2对应线性规划问题，对其进行剪枝和分枝。依此类推，对所有分枝进行求解，剪枝，分枝，定界；直至求得最优解。（4）最优解的确定若某Mk=m0,则为最优解，求解结束。若所有分枝求解结束，则最后的上界Mk即为最优解。例3:应用分枝定界法，求解整数线性规划问题解：设原整数线性规划问题目标函数的最优值为z*,（i）求解线性规划问题：minz=x1+3x2得最优解为x1=8.12,x2=3.13；minz=17

34、.51。'x2之3.13记约束区域<22x1+34x2±285为R。x1>0,x2>0(2)对R进行分枝：选取最优解中不是整数的变量，例如x1，将R分成两个子区域R,R2X_9x2,3.13x1M8R:人22x134x2,285x1_0,x2_0x2_3.13R：22x134x2,285(3)定界：确定最优值z*的上下界。由(1)中求得的最优值知z*至17.51;而z*的上界可由R内的任意一个可行解确定，例如，、=7,x2=4即为一个可行解。故z*E19。从而，17.51Ez*E19。(4)在R内求最优解，得x1=9,x2=3.13;minz=18.39。(

35、5)在R2内求最优解，得X=8,x2=3.21;minz=17.62。(6)因为R1内最优解不全是整数，因而必须继续对R1分枝：(7)显然忆内无解，剪枝。在R11内求最优解，得为=9,x2=4;minz=21;为整数可行解。但因17.51Ez*E19,而21>19,故剪枝。(8)因为R2内最优解不全是整数，因而必须继续对R2分枝：(9)显然R22内无解，剪枝。在R21内求最优解，得x=6.77,x2=4;minz=18.77。(10)因为R21内最优解不全是整数，因而必须继续对R21分枝：(11)在R212内求最优解，得x1=6,x2=4.5;minz=19.5。因minz=19.5大于

36、z*的上界，故剪枝。(12)在R211内求最优解，得为=7,x2=4;minz=19。所求原整数规划问题的最优解为:§4最优化问题数值算法x1=7,x2=4；minz=19。最优化问题的数值算法很多，常用的算法多为搜索法，本节只介绍搜索法的基本思想、无约束最优化问题的最速下降法(梯度法)和有约束最优化问题的罚函数法。4.1搜索算法考虑无约束最优化问题：minf(xi，X2，xn)我们已经讨论了这类问题的最优解条件，这必须用到函数的解析性质。我们的方法是，先利用必要条件求出平稳点，再应用充分条件判断是否是极值点。但是，我们必须求解一个n个变量n个方程的方程组，并且常常是非线性的。这只有

37、在特殊的情况下，才能求出它的精确解。在一般情况下，都不能用解析法求得精确解。更何况许多实际问题中，函数的解析表达式很难得到。因此，我们必须寻求一些切合实际问题的行之有效的数值解法。搜索算法就是我们常用的方法。(1)搜索算法的基本思想：假定目标函数f(X)极小值问题。首先，确定目标函数f(X)的初始点Xo；然后，按照一定规则产生一个点列Xk,这种规则称为算法；规则必须满足(1)点列Xk收敛；(2)点列Xk收敛到目标函数f(X)的极小值点。(2)搜索算法的基本步骤：选定初始点Xo(越接近最优点越好),允许误差o>O,令k=0。假定已得非最优点Xk,则选取一个搜索方向sk,满足：目标函数f(X

38、)下降，或gradf(Xk)V<0。选定搜索步长入>0,X+=Xk+限晟，满足：f(X1)=f(Xk+MSk)-f(Xk)。判断Xk书是否是最优点或是满足要求的近似解。假定给定精度要求为o>0,常用确定求近似解搜索结束的方法有：|gradf(Xki)卜：；梯度模确定法；|f(Xki)-f(Xk)卜：；目标函数差值绝对误差法；|Xk1-Xk|一一相邻搜索点绝对误差法。如果Xk书满足给定精度要求，则搜索完成，近似最优点为X*%Xk书；如果Xk书不满足给定精度要求，令k=k+1返回(2)继续搜索。注意1:我们的搜索算法一般得到的都是局部最优解注意2:确定求近似解搜索结束的方法还有目

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

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

41、最优解a阶收敛定义：对于收敛于最优解X*的序列Xk,若存在与k无关的数0<P(收和a21,当k从某个k0开始时，有|Xki-X*|</Xk-X*L则称序列Xk收敛的阶为a,或称a阶收敛当口=1时，称迭代序列Xk为线性收敛；当1cum2时，称迭代序列Xk为超线性收敛；当a=2时，称迭代序列XJ为二阶收敛一般来说，线性收敛是比较慢的，而二阶收敛则是很快的，超线性收敛介于二者之间。如果一个算法具有超线性以上的收敛速度，我们就认为是一个好的算法了。4.2无约束最优化问题的梯度法无约束最优化问题的计算方法很多。无约束最优化问题的计算方法分为两大类：一类是解析法，包括经典最优化方法，最速下降法

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

43、允许误差50,令k=0。步骤2:假定已得非最优点Xk,计算梯度gradf(Xk),选取搜索方向Sk=-gradXk)步骤3:选定搜索步长标0,X«=Xk+刈£,满足：“Xk+、Sk)=min“Xk十九4)。步骤4:判断Xk书是否是最优点或是满足要求的近似解。根据精度要求，检验是否满足收敛性判断准则：|gradf(Xk+)|。或|f(Xc)-f(Xk)|名或|Xk书-Xk|如果Xk中满足给定精度要求，则搜索完成，近似最优点为X*定Xk书;如果Xk书不满足给定精度要求，令k=k+1返回(2)继续搜索例1:应用最速下降法求解minf(X)=x；+25x；。解：(1)选定初始点X0

44、=(2,2),允许误差8=0.2,置k:=0收敛判断准则|f(Xk+)-f(Xk)|名。(2)计算梯度gradf(X。，选取搜索方向Sk=-gradf(Xk)graQXI=2x1,50x2)|x3，Sk=-2x1,-50x21|x%第一点搜索计算：gradf(Xo)=4,100,So=-4,-100)(3)选定搜索步长嬴>0,X«=Xk+嬴sk,满足：第一点搜索计算：求最优步长解得乂电0.02。(4)判断Xk书是否是最优点或是满足要求的近似解。第一点搜索计算：Xi=(1.92,0)验证收敛判断准则|f(Xi)f(X。)卜100.31%0.02,不满足，继续搜索依次类推，直到搜索

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

46、t;0,无约束最优化问题的最优解X*wD,则X*必为原等式约束最优化问题的最优解。m证明：设无约束最优化问题minT(X,M)=f(X)Mxgi(X)2iT的最优解X*wD,则有:gi（x）=0而当XwD时，T(X,M)=f(X)所以minf(X)=minT(X,M)=T(X*,M)=f(X*)即X*为原等式约束最优化问题的最优解。定理2:设f(X)和g.X)=0,i=1,2,，m均为连续函数，若对于任意正数M>0,无约束最优化问题的最优解X*(M)皂D,且limX*(M)=X*,M:：则limX*(M)=X*为原等式约束最优化问题的最优解。MF定理2的证明请参看有关参考资料。根据定理1

47、和定理2,我们就可以将通过构造罚函数的方法化为无约束最优化问题求解，这种方法称为罚函数法。罚函数法的步骤：(等式约束最优化问题罚函数法)m步骤1：构造罚函数T(X,M)=f(X)+MZgi(X)2,i1选定M1>0,允许误差s>0,令k：=1;步骤2:求无约束问题minT(X,Mk)的最优解Xk；步骤3:判断Xk是否是最优点或是满足要求的近似解。根据精度要求，检验是否满足收敛性判断准则：m2或“gi(Xk)i1如果满足收敛性判断准则，则X*定X：,结束搜索；否则，令k:=k+1,取Mk+AMkA0,返回(2),继续搜索。下面我们通过一个简单的例子来说明等式约束最优化问题的罚函数法。

48、例2:应用罚函数法求解非线性规划问题解：构造罚函数：T(X,Mk)=X2x|Mk(x2-1)2求罚函数的最优解：应用解析法工=2x1,T=2x2+2Mk(x2-1)X1：x2令上述两式等于零，解得x1=0,x2=Mk1Mk令MkT8得Xi=0,X2=1为所求最优解。(2) 不等式约束最优化问题的罚函数法对于，不等式约束最优化问题假定上述不等式约束最优化问题的最优解存在。由于不等式约束条件gi(X)之0,i=1,2,，m等价于等式约束条件因而，上述不等式约束最优化问题可以转化为问题类似问题(1)构造罚函数则将上述等式约束最优化问题的求解转化为下面无约束最优化问题的求解:定理3:若对于某确定数M&

49、gt;0,无约束最优化问题的最优解X*wD,则X*必为原不等式约束最优化问题的最优解，其中D=X|gi(X)20,i=1,2,，m,XeRn)0定理4:设(1)f(X)和g.X)=0,i=1,2,，m均为连续函数；(2)原不等式约束最优化问题的最优解X*存在；(3)数列Mk满足0<M1<M2<<Mk<且limMk="；k二(4)对任意MkA0,问题minT(X,M)的最优解Xk=X(Mk)都存在,且有界；(5)点列Xk存在极限点；则：点列XJ的极限点是原不等式约束最优化问题的最优解。罚函数法的步骤：(不等式约束最优化问题罚函数法)m步骤1:构造罚函数T(

50、X,M)=f(X)+M£mi0(gi(X)j,i1选定M1>0,允许误差8A0,令k：=1;步骤2:求无约束问题minT(X,Mk)的最优解Xk;步骤3:判断Xk是否是最优点或是满足要求的近似解。根据精度要求，检验是否满足收敛性判断准则：m或"gi(Xk)2>i1.*如果满足收敛性判断准则，则X*定Xk,结束搜索；否则，令k:=k+1,取Mk卡Mka。，返回(2),继续搜索例3:应用罚函数法求解非线性规划问题m解：构造罚函数T(X,M)=f(X)Mmi0(gi(X)2i1求T(X,Mk)的极小值点当-xi2+X2a。,或xia。时，显然上两式不能同时等于零,所以

51、，此时T(X,Mk)不存在极小值点。当一x12+x20,x1。时，有令上面两式等于零:解得T(X,Mk)的极小值点为当Mk取不同值时，可得到相应的Xk值，计算如下表1101001000-0.25-0.04545-0.004950-0.00049950-0.4375-0.1415-0.004975-0.00049980根据定理得，原问题的极小值点为X*=(0,0),极小值为f(X*)=0§ 5 多目标优化问题在许多实际的最优化问题中，常常遇到目标函数是几个的情况，这一类问题我们称之为多目标优化问题。例如，投资方向选择问题，我们不仅要求投资的收益最大，而且要求投资的风险最小。再例如，购买

52、商品问题，我们既要考虑商品的价格，又要考虑商品的质量，甚至还要考虑商品的性能等等。所谓多目标优化问题是指：目标函数是两个或两个以上的最优化问题。其数学模型为：minfi(xi,x2,xn)i=1,2,，s目标函数gi(xi,x2,xn)=0i=1,2,m约束条件例1：求解多目标优化问题minx2和miny解：易求x=0,y=1时，minx2=0,miny=1。例2:求解多目标优化问题maxx2和miny解：显然，无最优解。5.1多目标优化问题的解多目标优化问题解的存在性极其复杂，这是由多目标优化问题的目标函数多个性和目标函数相互之间的复杂性质决定的。由于目标函数在很多情况下不可能同时达到最大值

53、或最小值，因而，多目标最优化问题很少有最优解，而实际问题又要求我们做出决择，求得一个比较好的解。什么样的解才是我们需要的解呢？对于同一个问题不同的要求导致不同的求解标准，从而就会得到不同的求解结果。为此，我们给出多目标最优化问题的条件最优解概念。最优解：满足约束条件且使所有目标函数达到要求的最大值或最小值的点称为多目标优化问题的最优解。可行解：满足多目标优化问题的约束条件的点称为可行解。条件最优解：满足多目标优化问题的约束条件且满足根据需要设定条件的可行解称为条件最优解。对于一个多目标优化问题，即使最优解存在，要求解它也是十分困难的，特殊情况下，我们也只好用搜索法求解。更何况它常常还不存在最优

54、解，因而我们必须寻求其求解条件最优解的方法。为了求得满足我们要求的解，常常不得不设定一些新的条件，从而求得条件最优解。设定新条件的方法是我们求解多目标优化问题的基本方法。下面的“单目标化方法、多重目标函数方法和目标关联函数方法”都是针对目标函数设定新条件的方法。5.2单目标化解法将原多目标优化问题多个目标函数转化成为只有一个目标函数的单目标优化问题求解的方法称为单目标化方法。(1)单目标化解法的基本思想步骤1:构造一个新的目标函数f=f(f1,f2，fs)满足性质：在约束条件的区域内f(fi,f2,，fs)是fl,f2,，fs的单调增函数。特别注意：构造新目标函数也可以根据实际问题，将f(fi,f2,，fs)定义为fl,f2,，fs的不减函数。步骤2：建立单目标优化数学模型minf=f(fi,f2,，fs)目标函数gi(Xi,X2,Xn)=0i=1,2,m约束条件步骤3:求解上述单目标优化数学模型得到：单目标优化问题的最优解，从而可得到原多目标优化问题的最优解或条件最优解。(2)单目标优化问题最优解的性质单目标优化问题的最优解与原多目