《多目标最优化模型》由会员分享,可在线阅读,更多相关《多目标最优化模型(39页珍藏版)》请在金锄头文库上搜索。
1、第六章 最优化数学模型1 最优化问题11 最优化问题概念12 最优化问题分类13最优化问题数学模型2经典最优化方法21无约束条件极值22等式约束条件极值23不等式约束条件极值3线性规划31线性规划32整数规划4最优化问题数值算法41直接搜索法42梯度法43罚函数法5多目标优化问题51多目标优化问题52单目标化解法53多重优化解法54目标关联函数解法55投资收益风险问题第六章 最优化问题数学模型1 最优化问题11 最优化问题概念 (1)最优化问题在工业、农业、交通运输、商业、国防、建筑、通信、政府机关等各部门各 领域的实际工作中,我们经常会遇到求函数的极值或最大值最小值问题,这一类 问题我们称之
2、为最优化问题。而求解最优化问题的数学方法被称为最优化方法。 它主要解决最优生产计划、最优分配、最佳设计、最优决策、最优管理等求函数 最大值最小值问题。最优化问题的目的有两个:求出满足一定条件下,函数的极值或最大值最 小值;求出取得极值时变量的取值。最优化问题所涉及的内容种类繁多,有的十分复杂,但是它们都有共同的 关键因素:变量,约束条件和目标函数。(2)变量 变量是指最优化问题中所涉及的与约束条件和目标函数有关的待确定的量。一般来说,它们都有一些限制条件(约束条件),与目标函数紧密关联。设问题中涉及的变量为x ,x,x ;我们常常也用X (x ,x,x )表示。1 2 n 1 2 n 3)约束
3、条件在最优化问题中,求目标函数的极值时,变量必须满足的限制称为约束条件。例如,许多实际问题变量要求必须非负,这是一种限制;在研究电路优化设计问题时,变量必须服从电路基本定律,这也是一种限制等等。在研究问题时, 这些限制我们必须用数学表达式准确地描述它们。用数学语言描述约束条件一般来说有两种:等式约束条件g (X)二0,i二1,2,mi不等式约束条件h (X) 0,i二1,2,ri或h (X) 0或h(X) 0。这两种约束条件最优化问题最优解的存在性较复杂。(4)目标函数 在最优化问题中,与变量有关的待求其极值(或最大值最小值)的函数称为 目标函数。目标函数常用f (X)二f (x ,x ,x
4、)表示。当目标函数为某问题的效益函数1 2 n时,问题即为求极大值;当目标函数为某问题的费用函数时,问题即为求极小值求极大值和极小值问题实际上没有原则上的区别,因为求f (X)的极小值,也就是要求-f (X)的极大值,两者的最优值在同一点取到。12 最优化问题分类最优化问题种类繁多,因而分类的方法也有许多。可以按变量的性质分类, 按有无约束条件分类,按目标函数的个数分类等等。一般来说,变量可以分为确定性变量,随机变量和系统变量等等,相对应的 最优化问题分别称为:普通最优化问题,统计最优化问题和系统最优化问题。按有无约束条件分类:无约束最优化问题,有约束最优化问题。按目标函数的个数分类:单目标最
5、优化问题,多目标最优化问题。按约束条件和目标函数是否是线性函数分类:线性最优化问题(线性规划), 非线性最优化问题(非线性规划)。按约束条件和目标函数是否是时间的函数分类:静态最优化问题和动态最优 化问题(动态规划)。按最优化问题求解方法分类:无约束解析法(间接法)古典微分法古典变分法极大值原理库恩-图克定理数值算法(直接法)斐波那西法 一维搜索法黄金分割法、插值法坐标轮换法步长加速法 多维搜索法方向加速法单纯形法随机搜索法最速下降法无约束梯度法q拟牛顿法共轭梯度法变尺度法数值算法(梯度法)有约束梯度法可行方向法梯度投影法SUMT法化有约束为无约束SWIFT法复形法单目标化方法 多目标优化方法
6、 0 , i = 1,2,,n下的最大值和取得最大值的点。13ni 线性规划问题数学模型 由某实际问题设立变量,建立一个目标函数和若干个约束条件,目标函数 和约束条件都是变量的线性函数,而且变量是非负的,这样的求函数最大值最小 值问题,我们称为线性最优化问题,简称为线性规划问题。其标准数学模型为:min f(x , x ,x ) = c x + c xFF c x目标函数12n1 12 2nna x F a xFF a x 二 bi = 1,2,m约束条件i1 1i 2 2im nix 0 i矩阵形式:minf (X)二 CtX目标函数AX=B约束条件X 0其中X = (x ,x,,x )t,
7、 C = (c ,c,,c )t, B = (b ,b,,b )t12 n12 n12 m在线性规划问题中,关于约束条件我们必须注意以下几个问题。注1:非负约束条件x 0 (i二1,2,n),一般来说这是实际问题要求的需要。i如果约束条件为x d,我们作变量替换z二x -d 0 ;如果约束条件为i ii i ix 0。i i i i i注 2 :在线性规划的标准数学模型中,约束条件为等式。 如果约束条件不是等式,我们引入松驰变量,化不等式约束条件为等式约束 条件。情况1:若约束条件为a x + a x + b a x b,引入松驰变量i1 1 i 2 2im n i原约束条件变为ax + a
8、x +b a x - z = b。i1 1 i 2 2 im n i i情况2:若约束条件为a x + a x + b a x 3.132s.t. 285。12x 0, x 0且为整数12又例如:0-1规划问题max z = 3 x - 2x + 5 x123x + 2 x 一 x 2123x + 4 x + x 4s.t. 12 3x , x , x = 0或 1。x + x 31 2 3124 x + x 623 非线性规划问题数学模型目标函数由某实际问题设立变量,建立一个目标函数和若干个约束条件,如果目标函 数或约束条件表达式中有变量的非线性函数,那么,这样的求函数最大值最小值 问题,我
9、们称为非线性规划最优化问题,简称为非线性规划问题。其数学模型为:min f (x ,x , x )1 2 ng (x ,x ,x )=0i =1,2,m约束条件i 1 2 n其中目标函数或约束条件中有变量的非线性函数。例如:非线性规划问题 min f(x,y)=(x-1)2 b yg (x,y)=xb y-201g (x,y)=-y 02上述最优化问题中,目标函数是非线性函数,故称为非线性规划问题。 前面介绍的四种最优化数学模型都只有一个目标函数,称为单目标最优化问 题,简称为最优化问题。 多目标最优化问题数学模型 由某实际问题设立变量,建立两个或多个目标函数和若干个约束条件,且目 标函数或约
10、束条件是变量的函数,这样的求函数最大值最小值问题,我们称为多 目标最优化问题。其数学模型为:min f (x ,x,,x )i = 1,2,s目标函数i 12ng (x , x,,x ) = 0 i = 1,2,,m 约束条件i 12n上述模型中有s个目标函数,m个等式约束条件。例如:“生产商如何使得产值最大而且消耗资源最少问题”“投资商如何使得投 资收益最大而且风险最小问题”等都是多目标最优化问题。2经典最优化方法经典最优化方法包括无约束条件极值问题和等式约束条件极值问题两种,不 等式约束条件极值问题可以化为等式约束条件极值问题。经典的极值理论:首先,根据可微函数取极值的必要条件确定可能极值点; 其次,根据函数取极值的充分条件判断是否取极值?是极大值?还是极小值?这 种方法已经几百年的历史了。21无约束条件极值设n元函数f (X)二f (x ,x ,x ),求f (X)的极值和取得极值的点。这是一12 n个无约束条件极值