多目标最优化数学模型

1、第六章最优化数学模型§1最优化问题11最优化问题概念12最优化问题分类13最优化问题数学模型§2经典最优化方法21无约束条件极值22等式约束条件极值23不等式约束条件极值§3线性规划31线性规划32整数规划§4最优化问题数值算法41直接搜索法42梯度法43罚函数法§5多目标优化问题51多目标优化问题52单目标化解法53多重优化解法54目标关联函数解法55投资收益风险问题第六章最优化问题数学模型§ 1最优化问题1. 1 最优化问题概念(1) 最优化问题在工业、农业、交通运输、商业、国防、建筑、通信、政府机关等各部门各 领域的实际工作中，

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

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

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

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

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

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

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

9、例子：求函数 f (XnX2,X3 X-!X3 xn在约束条件条件Xi X3x =2008, Xi 0,i =1,2/ ,n下的最大值和取得最大值的点。 线性规划问题数学模型由某实际问题设立变量，建立一个目标函数和若干个约束条件，目标函数和约束条件都是变量的线性函数， 而且变量是非负的，这样的求函数最大值最小值问题，我们称为线性最优化问题，简称为 线性规划问题。其标准数学模型为:m i f (%,X2, ,Xn)二 GXi C2X2CnXn目标函数aMXi - ai2X2 amXn 二 3Xi _0= 1,2, ,m约束条件矩阵形式:m i f(X)二 C X目标函数约束条件AX =BX _0

10、其中 X =(为公2, ,Xn)T，C =(G,C2,汀，B = (0 , b? , , bm )丁ai1ai2a21a22aina2n©mi a m2amn在线性规划问题中，关于约束条件我们必须注意以下几个问题。注1:非负约束条件Xi _0 (i =1,2/ ,n), 般来说这是实际问题要求的需要如果约束条件为Xi _di，我们作变量替换Zi =Xi - di 0 ;如果约束条件为X - di，我们作变量替换 乙=di - Xi 0。注2:在线性规划的标准数学模型中，约束条件为等式。如果约束条件不是等式，我们引入松驰变量，化不等式约束条件为等式约束 条件情况1 ：若约束条件为a a

11、i2x2 丁 aimxn - b，引入松驰变量Zi 二厲必 ai2X2 aimXn原约束条件变为ai1X1 - ai2x2亠 aimXn -zi =3。情况2：若约束条件为ai1X1 ai2X aimX - bi，引入松驰变量Zi 二 bi -(ai1X1ai2X2amXn) 0原约束条件变为ai1X1 ai2X aimXn zi = b在其它最优化问题中，我们也常常采取上述方法化不等式约束条件为等式约 束条件。实际问题中，我们经常遇到两类特殊的线性规划问题。一类是：所求变量要 求是非负整数，称为整数规划问题；另一类是所求变量要求只取0或1，称为0-1 规划问题。例如：整数规划问题min z=

12、 3x2x2 _3.13s.t. *22论 +34x2 X 285。&启0,X2二0且为整数又例如：0-1规划问题m a:z =3% -2x2 - 5x3X +2x2 x3 W 2Xi +4X2 +X3 兰 4卡s.t.x1,x2,x 0或 1。x| + x2 兰 3|' 4x2 x3 _ 6 非线性规划问题数学模型由某实际问题设立变量，建立一个目标函数和若干个约束条件， 如果目标函 数或约束条件表达式中有变量的非线性函数， 那么，这样的求函数最大值最小值 问题，我们称为非线性规划最优化问题，简称为非线性规划问题。其数学模型为：m i f (Xi,X2,，Xn)目标函数gi(X

13、i,X2, ,Xn) =0 i =1,2, ,m约束条件其中目标函数或约束条件中有变量的非线性函数。例如：非线性规划问题m i f (x, y) = (x-1)2 yG(x, y) =x+y2 兰0* 。®2(x, y) = yO上述最优化问题中，目标函数是非线性函数，故称为非线性规划问题。前面介绍的四种最优化数学模型都只有一个目标函数，称为单目标最优化问题，简称为最优化问题。 多目标最优化问题数学模型由某实际问题设立变量，建立两个或多个目标函数和若干个约束条件， 且目 标函数或约束条件是变量的函数， 这样的求函数最大值最小值问题，我们称为多 目标最优化问题。其数学模型为：m i血区

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

15、值设n元函数f (X)二f(X-X2,，Xn)，求f (X)的极值和取得极值的点。这是一 个无约束条件极值问题，经典的极值理论如下。定理1(极值必要条件):设n元函数f(X)二f(xX2，,人)具有偏导数，则f(X) 在X = X *处取得极值的必要条件为：X X = °i = 1,2， ，n。Xi -定理在此不给出证明，读者可自己参看有关资料。注1:对于一元函数上述定理当然成立，只是偏导数应为导数；注2:定理只是在偏导数存在的前提下的必要条件。如果函数在某一点偏导数不 存在，那在这一点处仍然可能取得极值；注3:如果函数在某一点偏导数存在，且偏导数都等于零，那么函数在这一点处 也不一

16、定取得极值。例如，函数f(x,y)=3x2 y2在点(°,°)处偏导数不存在，但在这一点处函 数仍然取得极小值零。函数 f(x, y)=x3 y5在点(°,°)处偏导数存在，且偏导数 都等于零，但在这一点处函数不取极值。定理1的作用在于，求出函数的可能极值点，然后，我们再研究这些点是否 取得极值。对于许多实际问题来说，函数一定能够取得极大值或极小值，而函数的可能 极值点(满足必要条件的点)又只有一点， 则这一点当然是函数取得极大值或极 小值的点。对于一般函数而言，我们怎样判定函数在某点是否取极值？是极大值？还是 极小值？我们有下面的极值的充分条件定理。定

17、理2 (极值充分条件)：设n元函数f(X)二f (x!, x2 / ,xn)具有二阶偏导数，则 f (X)在X二X*处取得极值的充分条件为：(!)-卜之*=°i = 2,3, ,n ；:xf(2)黑塞矩阵:x2 jx1:xvxn：2f：x2：xn在X = X*处正定或负定;.做&1CXX2?f；2f2f:x2；x3=2 ；函数的黑塞矩阵为2f (0,0,0) =-4202-12202一8(3) 黑塞矩阵在X二X*处正定时，函数取极小值；负定时，函数取极大值。 本章内容简要讲解理论，注重实际应用，对于许多经典的定理都不进行证明， 读者可自己参看有关资料。例 1:求函数 f(xx

18、2,x3) - -2xf - 6x22 -4x3 ' 2轨-2x2x3 的极值。解：(1)根据极值存在的必要条件，确定可能取得极值的点：f:f；:f4x-i 2x?，12x2 2% 2x3，8x3 2x2-X;x2；:x3令-f f =0，解得(为,X2, x3)= (0,0,0);x2.:x3 根据极值存在的充分条件，确定(X!，X2，X3)= (0,0,0)是否是极值点:-2 2计算乂一8 ；J = 12 c-X?-420-42= 44>0，2-1222 -1202_8因为-4 :： 0，工 一320 ： 0 ；所以黑塞矩阵负定，f(0,0,0) = 0。故函数在(Xi,X2

19、,X3)=(0,0,0)处取得极大值2. 2 等式约束条件极值目标函数下面我们研究的是有若干个等式约束条件下， 一个目标函数的极值问题，其 数学模型为：m i rf (X1,X2, ,Xn)i =1,2, ,m约束条件S.t. gi (Xi,X2, ,Xn) =0拉格朗日(Lagrange)乘数法：m(1) 令L = f (XX?, ,Xn) ' 飞山为必,，Xn)i4称为上述问题的拉格朗日乘数函数，称打为拉格朗日乘数。(2) 设f(XX2，,Xn)和gi(X!,X2, ,Xn)均可微，则得到方程组図:Lgi(Xi,X2, ,Xn) =0J心，iXj i 4:Xjj =1,2, ,ni

20、 ",2, ,n36.:Lex:z解得maxV为所求。(3) 若(xx2, ,Xn,，2, m)是上述方程组的解，则点(x-! ,x2 / ,Xn)可能为 该问题的最优点。拉格朗日(Lagrange)乘数法的本质是：将求有约束条件极值问题转化为求无 条件极值问题；所求得的点，即是取得极值的必要条件点。拉格朗日乘数法没有解决极值的存在性问题，但是，如果拉格朗日乘数函数 具有二阶连续偏导数，我们也可以应用黑塞矩阵来判定函数是否取得极值。在具体问题中，点(2,2, 恳)是否为最优点通常可由问题的实际意义决定。例2:求表面积为定值a2，而体积为最大的长方体的体积。解：设长方体的三棱长为x,

21、y,z，体积为V ；建立数学模型如下：maxV =xyzr22xy+ 2xz + 2yz = a s.t.x 0,y0,z0构造拉格朗日乘数函数L(x, y,z) = xyz (2xy 2yz 2xz-a2)，则有=yz 2 ' (y z) = 0二 xz 2 ' (x z) = 0二 xy 2 ' (x y) = 0362. 3不等式约束条件极值对于不等式约束条件极值问题：m i f （Xi,X2,，Xn）目标函数s.t. gi（Xi,X2, x）乞0i =1,2, ,m约束条件我们有与拉格朗日乘数法密切相关的方法库恩一图克定理。定理3（库恩一图克定理）：对于上述不等

22、式约束条件极值问题，设f（X!，X2，,Xn）m和 gdXiX， X）均可微，令 L = f （捲必,Xn）''giXx, Xn）假设 i存在，则在最优点X = X =（xx2，,Xn）处，必满足下述条件：(1)m:L:f 、：Qii 0.Xj. Xji 4:：Xjj =1,2, ,n;(2)gi(X1,X2,Xn)乞 0i =1,2/ ,m ；(3)9(X1,X2,Xn) =0i =1,2/ ,m ；(4)打_0。根据库恩一图克定理我们可以求解许多不等式约束条件极值问题，值得注意 的是应用库恩一图克定理求解不等式约束条件极值问题，定理并没有解决最优解 的存在性问题，因此，我们

23、必须另行判断。例3:求解最优化问题（最优解存在）m i f （x, y）二（x -1）2 yPi（x, y） =x+y -2 兰0卫2（x, y） = -y 兰 0解：构造函数L(x, y,z) =(x-1)2 y /x y -2)2(-y)，= 2(x_1) +為=0 ex根据库恩一图克定理则有=1 +扎r _妇=0 cy入(x + y_2)=0入2 y = 0解得:. _0, 2 _0x = 1, y = 0, I = 0, ' 2 = 1;所求最优解为(x, y) = (1,0)，最优值为0§ 3线性规划3. 1线性规划设线性规划标准数学模型为：m i f (X!,X2

24、, ,Xj 二C2X2CnXn-约束条件目标函数约束条件©Xi +ai2X2 +aimXn =bii =1,2,ms.t*X 0i =1,2，,n矩阵形式：mif(X)二CTXAX = BX _0其中 X =(X!,X2, ,Xn)T , C=(G,C2, ,Cn)T , B = (0 , b? , , bm线性规划问题的求解有一整套理论体系，一般来说，应用单纯形法求解。此 方法尽管比较复杂，然而在计算机上实现并不困难。解线性规划问题的单纯形法 已在许多数学计算软件中实现，我们求解线性规划问题可根据需要， 应用数学计 算软件求解即可。在此，我们不系统研究其理论，只是简单介绍线性规划的

25、穷举 法和单纯形法的基本思想。3.2 线性规划的穷举法(1) 穷举法基本原理和步骤步骤1：将线性规划问题化成矩阵的标准形式，设系数矩阵的秩R(A)二m，则对应线性方程组的基础解系自由变量的个数为n - m个。步骤2：穷举法求解：令心二人2大"=Xi(n)=0，解得对应线性方程组一组解为(XpX2, , xn)；对应目标函数值为 f (x1, x2 / ,xn) = fi。从n个变量X中选n-m个作为自由变量，令它们的值为0,可得到 瞎虫：® 组解。步骤3：确定最优解：如果最优解存在，则上述求解得到的 对应需二CT个目标 函数值中，最小者(或最大者)即为所求最小(或最大)最优

26、值，对应的解为最 优解。步骤4：证明解为最优解： 将最优解对应的自由变量看成参数t1,t2/' ,t(n _m);解对应线性方程组得Xi = b0 + b + 匕2上2 +bi(n_m)t(n_m),i = 1,2；八,n。 将对应线性方程组解 X =bo +b£ +b2t2 +0(5)1"),i=1,2,n代入目标函数得：f曲1 d2t2 d(n利)t(n“)。如果di _0, i =1,2，n，则所求为最小值最优解；否则，线性规划问题无最 小值最优解。如果di <0, i =1,2, ,n，则所求为最大值最优解；否则，线性规划问题无最 大值最优解。例 1:

27、目标函数：max f (X) = 2% 3x2 - x3一一 2 -X32XX5 + + + X1X1X2-0, i =1,234,5解：约束条件的增广矩阵为：10100 'A=12010, R(A) = 3;卫1001 ;令为=X2 =0，解得 X =(0,0,5,10,4), f(X) =5 ;令为=X3 =0，无解；令为=& =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 -X0，解

28、得 (10,05,0,4)，不满足非负条件，舍去;令X2 = X5 =0，无解；5335令 X3 =X4 =0，解得 X =(5-,0,0-), f(X)=222令XX5 =0,解得X = (5,4,0,-3,0)，不满足非负条件，舍去；令 X4 =X5 =0，解得 X =(2,4,3,0,0), f(X) =19 ；所以 maX f(X) =19，最优解为 X =(2,4,3,0,0)。证明：令x4 =t,x5 =s解得Xi =2 t +2s目标函数f(X) =19 t s；x2 = 4 sx3 = 3 t - 2 sX _0, i =1,5因为x4 =t,x5二s非负，所以max f (X

29、) = 19，故最优解存在。(2) 单纯形法基本原理和步骤 将线性规划问题化成矩阵的标准形式，设系数矩阵的秩R(A)二m ,则对应线性方程组的基础解系的个数为n-m个，即有n-m个自由参数变量。 选取n - m个非基变量(自由参数变量),不妨假设为Xj, j=m1,，n ； 解得线性规划问题的典式"nXi =W - £ %Xj (i =1,2，,m)j =m41*0 nmin f = f - Z jXj (i =1,2，,m)j =m卅Xj -0j =1,2, ,n定理1:如果线性规划问题的上述典式中所有< 0, j = m 1,n ；则X =(>1, >

30、2,Cm,。,0)为最优解。定理2：如果线性规划问题的上述典式中存在某个'm.k 0，且对应i(m k)乞0,i =1,2，,m ;则线性规划问题无最优解。由定理1和定理2知，如果我们选择适当的n-m个非基变量，就可以根据 所求得的典式判断最优解的存在与否，从而求解该线性规划问题。单纯形法的思想是：选择适当的基变换(进基和退基)，不断地变换典式， 使得典式中目标函数值不断下降， 从而求得最优解。其核心为如何选择进基和退 基。 进基规则和退基规则进基规则一一正检验数最小下标规则，即选取 s二min j | j Q，由此确 定xs为进基。退基规则：选取这样的下标Jr( Ji表示第i个基变量

31、的下标)二 min宀飞 0is由此确定Xj离基。a八任Jr =m i nJ |=二 is 0is 单纯形法的基本步骤：步骤1:化线性规划问题为标准形式。步骤2:确定基变量，求得基本可行解和典式；是否满足最优解定理或最优解不存在定理的条件？判断最优解的情况。 步骤3:根据进基规则和退基规则，选择进基和退基，进行基变换，求得对应典式。重复进行基变换，直到求出最优解或判断出无最优解为止。例2:解线性规划问题x-ix2m i rl - -2捲-x2x2 x3 = 5一捲 + x2 + X4 = 0 s.t.6% +2x2 +x5 =21N _0, i =1,2,3,4,5解：(1)约束条件的增广矩阵为

32、:(1 1100A= 1 1 032 01 0 ，R(A)=3 ；0 b所以非基变量个数为两个(2) 选取XX2作为非基变量，X3,X4,xs作为基变量，解得典式为x3 = 5 X1 X2沧=禺一x2*X5 =21 6X1 2x2 min f = 一2捲x2 公 “ i =1,，5不满足最优解定理和最优解不存在定理的条件，故必须进行基变换(3) 进行基变换选取进基：> =2 0, 2 =1 0，根据s=minj|0得疋为进基。选取退基： v _ mi nV"5,21二21，1 6 6act根据v - mi门工|飞0，Jr =mi n Ji | 已飞q得Xs为离基'is&

33、#39; is进行基变换，求新基的典式:321X3=X2+ -X5236741X4=X2-7 X5236711X1=X2 _X5236mi n7 1*2 +13X5Xi _0, i =1,5判断：不满足最优解定理和最优解不存在定理的条件，故继续进行基变换。(4) 继续进行基变换1选取进基：2 = - 0，根据s = minj | j 0得x2为进基。3选取退基：v - mi nV?,21,4 8根据 -minl -is 0，Jr 二 min Ji | J - is 0 得 x 为离基 "is" is进行基变换，求新基的典式:93 x 1X2 =_ X3 +_X54241丄c

34、1X4 = +2x3X522«11111治=+ X3 X54243111min f =一+ x3+x5424kXi K0, i=1,，5满足最优解定理的条件，根据定理最优解为11 91X =（一，0, ,0）, min f4 4231。43. 2整数规划m i rf （人必，x）二C2X2'CnXns.t?3i1X1 +ai2X2+aimXn =bixi启0, xi为整数im ni =1,2/ ,mi =12 ,n目标函数-约束条件设纯整数线性规划数学模型为:这一类问题与一般线性规划比较起来， 似乎是变简单了，但实际上恰恰相反， 由于解集是一些离散的整数点集， 使得单纯形法失

35、去了应用的基础，求解变得困 难而复杂。整数线性规划目前还缺乏统一的解法，这里只介绍分枝定界法，它是目前求解纯整数线性规划和混合整数线性规划最常用的方法，计算机求解整数线性规划的大多数程序也是以它为基础的。分枝定界法：考虑上述纯整数线性规划问题，目标函数（1）解对应线性规划问题m i f （Xi,X2, ,Xn）二 GXi C2X2CnXn為为+ai2X2 +aimXn =bi1=1,2,，m切甫夂於s.t.约束条件>0i =1,2，,n若无最优解，则原纯整数线性规划问题无最优解；若有最优解，最优点（XX2，Xn），目标函数最优值Z0 = f （為必，,Xn）。若最优点&,XL，A

36、）全为整数，则为原纯整数线性规划问题的最优解；若最优点（X；,X；,，X；）不全为整数，则进行下一步。（2）定界和分枝定界： M0 _ min f （%, x2, , xn） _ z（）二 m0其中Mo取原纯整数线性规划问题中，满足约束条件的某一整数可行解所对 应的目标函数值。原纯整数线性规划问题的最优解必须满足定界条件。分枝：选取（XX2，,Xn）中一个不为整数所对应的Xk分枝，Xk 兰XkR4“ 82X2 + + aimXbii =1,2，,mx0i =1,2，,nXk - XkR2刍必 +ai2X2 + +aimXn =bii =1,2，,mM 王0i =1,2,nR和R2称为对应线性规

37、划问题的两枝，也是两个新线性规划问题的约束条件。显然，原纯整数线性规划问题的最优解满足R或R2。（3）对R和R2进行剪枝和分枝解R1对应的线性规划问题，对其进行剪枝和分枝：若无最优解，则原纯整数线性规划问题在R1内无最优解。不需要对该区域继续讨论一一剪枝。若有最优解，最优点（x1, x2/ ,xn），目标函数的最优值z f （x1, x2 / ,xn）。若Z1 =f（X1,X2, , Xn ） M 0，则原纯整数线性规划问题在 R内无最优解。不需要对该区域继续讨论一一剪枝。若最优点（X1,X2,，$）全为整数，则可能为原纯整数线性规划问题的最优解，定界：记 M! = f （%, x2, , x

38、n）乞 M 0，则 M ! _ min f 区，x2, , xn） _ m0，本分 枝求解结束。若最优点（Xi,X2，Xn）不全为整数，对R|继续进行分枝。完全类似，解R2对应线性规划问题，对其进行剪枝和分枝。依此类推，对所有分枝进行求解，剪枝，分枝，定界；直至求得最优解。（4）最优解的确定若某Mk = mo，则为最优解，求解结束。若所有分枝求解结束，则最后的上界 M k即为最优解 例3:应用分枝定界法，求解整数线性规划问题min z = x 3x2'x2 X3.13s.t. 22x34x285x0,x0且为整数解：设原整数线性规划问题目标函数的最优值为z*，（1）求解线性规划问题：m

39、in z = x 3x2x2 3.13s.t.22捲 + 34x2 32 8 5捲X 0, x2色0得最优解为 =8.12, x2 =3.13； minz=17.51x2 3.13记约束区域 22x34x285为R。论色0, x2色0（2）对R进行分枝：选取最优解中不是整数的变量，例如 捲，将R分成两个子区域R1,R。为色9X2 工3.1322X134x2 -285禺 - 0, x2 - 0X1 -8X2 兰3.13R?:22X134X2 - 285x1 > 0,x 0（3）定界：确定最优值z*的上下界。由（1）中求得的最优值知z* -17.51 ；而z*的上界可由R内的任意一个可行解确

40、定，例如， =7, X2=4即为一个可行解 故 z* <19。从而，17.5jzz19。(4) 在R 内求最优解，得x9,x2=3.13 ；minz =18.39。(5) 在R2 内求最优解，得花=8,X2= 3.21 ；minz = 17.62。(6) 因为R内最优解不全是整数，因而必须继续对 R分枝:X2 A4x9R11x2 X3.1322捲 +34x2 启 285 i为兰0, x2王0x2兰3x9R12x2 A 3.1322x, +34x2 色2 8 5i 为 3 0,x2 3 0(11)在 Ri2 内求最优解，得 X1 =6,X2 = 4.5 ； minz = 19.5(11)在

41、 Ri2 内求最优解，得 X1 =6,X2 = 4.5 ； minz = 19.5(7) 显然尺2内无解，剪枝在Rm内求最优解，得 x, =9, X2 =4 ； min z = 21 ;为整数可行解。但因17.51乞z* <19，而2119，故剪枝。(8) 因为R2内最优解不全是整数，因而必须继续对R2分枝：x2工4为兰8R21X2 3.1322X1 +34X2 启 285、_捲色0, x2启0x2兰3x8R22X23.1322X1 +34X2 兰 285i x( H 0, x2 H 0(11)在 Ri2 内求最优解，得 X1 =6,X2 = 4.5 ； minz = 19.5(11)在

42、 Ri2 内求最优解，得 X1 =6,X2 = 4.5 ； minz = 19.5(9) 显然R22内无解，剪枝在 R21 内求最优解，得 X1 =6.77,X2 -4 ； minz =18.77(10) 因为R21内最优解不全是整数，因而必须继续对 R21分枝:27x2工4x8x2 -3.1322x1 34x2 - 285% 0,x2 -0x6x2工4x8x2 -3.1322为 34x2 - 285为 - 0, x2 - 0(11)在 Ri2 内求最优解，得 X1 =6,X2 = 4.5 ； minz = 19.5因min z =19.5大于z*的上界，故剪枝。(12)在 R211 内求最优

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

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

45、数f (X)下降，或gradf (XQSk ： 0。 选定搜索步长k 0，Xk1二XkkSk，满足：f(Xk1) = f(Xk 'kSk)： f(Xk)。 判断Xk ,是否是最优点或是满足要求的近似解。假定给定精度要求为；7,常用确定求近似解搜索结束的方法有:| gradf (Xk i) | ：；|f(Xki)-f(Xk)|梯度模确定法；目标函数差值绝对误差法;| Xk 1 - Xk |：；相邻搜索点绝对误差法。如果Xk 1满足给定精度要求，贝U搜索完成，近似最优点为 X* Xk 1 ； 如果Xk 1不满足给定精度要求，令k = k 1返回(2)继续搜索注意1:我们的搜索算法一般得到的

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

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

48、够在有限步骤内达到满足 精度要求的目标函数f（X）的最优点的近似值。显然，只有具有收敛性质的算法 才有意义。搜索算法的收敛速度：作为一个好的算法，还必须要求它以较快的速度收敛 于最优解。:阶收敛定义：对于收敛于最优解X*的序列Xk，若存在与k无关的数0 ： - ：和： 一1，当k从某个k0开始时，有|X-X* 忙 1 |Xk -X*|>成立，则称序列Xk收敛的阶为，或称阶收敛。当:=1时，称迭代序列Xk为线性收敛；当12时，称迭代序列Xk为超线性收敛；当:=2时，称迭代序列Xk为二阶收敛。一般来说，线性收敛是比较慢的，而二阶收敛则是很快的，超线性收敛介于 二者之间。如果一个算法具有超线性

49、以上的收敛速度，我们就认为是一个好的算法了。4. 2无约束最优化问题的梯度法无约束最优化问题min f （X!,X2, ,xn）的计算方法很多。无约束最优化问题的计算方法分为两大类：一类是解析法，包括经典最优化方法，最速下降法（梯度法），共轭梯度法，牛顿法和变尺度法等。 另一类是直接法，包括坐标轮换法，步长加速法，方向加速法和单纯形法等。所谓解析法就是在方法的计算过程中， 应用到了函数的解析性质（可导性质 等）；所谓直接法就是在方法的计算过程中，仅仅涉及目标函数值的计算，而不 涉及函数导数等解析性质。我们在这里只介绍最速下降法（梯度法）。最速下降法理论根据：早在1847年，法国著名数学家Cau

50、chy就曾提出，从 任意给定点出发，函数沿哪个方向下降最快的问题。这个问题已从理论上解决了， 即沿着函数在该点的负梯度方向前进时，函数下降最快。这就是最速下降法的理 论根据。最速下降法的搜索步骤：步骤1:选定初始点X0 （越接近最优点越好），允许误差； 0，令k = 0。步骤2：假定已得非最优点Xk，计算梯度gradf（XQ，选取搜索方向Sk - -g r a dXk）步骤3:选定搜索步长 k 0，Xk 1二Xkk Sk，满足：f(Xkk Sk)二min f g SQ。步骤4:判断Xk i是否是最优点或是满足要求的近似解。根据精度要求，检验是否满足收敛性判断准则：|gradf(XkJ|：；或|

51、 f (Xk J - f (XQ或IX- -X"；如果Xk 1满足给定精度要求，则搜索完成，近似最优点为X* Xk .1 ；如果Xk 1不满足给定精度要求，令 k 1返回(2)继续搜索。例1:应用最速下降法求解 min f(Xx225x2。解：(1)选定初始点X。=(2,2)，允许误差: =0.2，置k = 0收敛判断准则| f (Xk J - f (XJ卜:；。(2) 计算梯度gradf (Xk)，选取搜索方向Sk =-gradf (XQTg r a dXk) =2为,50忌 |x 乳，Sk 叫-2音，-50x2 |x%第一点搜索计算：gradf (X。)=4,100， S

52、6; =-4,-100(3)选定搜索步长k 0，Xk1二Xk 'kSk，满足：f(Xkk Sk)二 min f (Xk Sk)第一点搜索计算：求最优步长' 2 2min f(X0 £) =(2 - 4 )2 25(2-100, )2解得 0.02 。(4)判断Xk 1是否是最优点或是满足要求的近似解第一点搜索计算：人=(1.92,0)验证收敛判断准则| f(Xj-f(X°)| T00.31 0.02，不满足，继续搜索依次类推，直到搜索到最优解或满足精度要求为止。搜索计算列表如下:搜索步长Ak搜索方向Sk搜索点Xk函数值f(Xk)X°=(2,2)10

53、4打=0.02S0=a-100Xj =(1.92,0)3.69人=0.5E=-3.84,0X2=(0,0)0£=0,0X2=(0,0)为最优解4. 3罚函数法对于约束最优化问题也有许多种方法，本段只介绍把约束最优化问题转化为无 约束最优化问题的一种求解方法一一罚函数法。 分为等式约束最优化问题和不等 式约束最优化问题两种情况讨论。(1)等式约束最优化问题的罚函数法首先，考虑等式约束最优化问题min f(X)s.t. gi(X)=O i =1,2, ,m假定上述等式约束最优化问题的最优解存在。若记 D 二X ©(X) =0, i =1,2, ,m, X Rn，m构造辅助函数T(X,M)二f(X) Mx gi(X)2 罚函数其中M 0 (罚因子)是一个充分大的正数。定理1：若对于某确定数M 0，无约束最优化问题mmin T(X,M ) = f (X) M g (X)2i#的最优解X* D，则X *必为原等式约