《多目标最优化模型》由会员分享,可在线阅读,更多相关《多目标最优化模型(42页珍藏版)》请在金锄头文库上搜索。
1、第六章最优化数学模型 1最优化问题1. 1最优化问题概念1. 2最优化问题分类1. 3最优化问题数学模型 2经典最优化方法2. 1无约束条件极值2. 2等式约束条件极值2. 3不等式约束条件极值 3线性规划3. 1线性规划3. 2整数规划 4最优化问题数值算法4. 1直接搜索法4. 2梯度法4. 3罚函数法 5多目标优化问题5. 1多目标优化问题5. 2单目标化解法5. 3多重优化解法5. 4目标关联函数解法5. 5投资收益风险问题第八早最优化冋题数学模 1最优化问题1. 1最优化问题概念(1)最优化问题在工业、农业、交通运输、商业、国防、建筑、通信、政府机关等各部门各 领域的实际工作中,我们
2、经常会遇到求函数的极值或最大值最小值问题,这一类 问题我们称之为最优化问题。而求解最优化问题的数学方法被称为最优化方法。 它主要解决最优生产计划、最优分配、最佳设计、最优决策、最优管理等求函数 最大值最小值问题。最优化问题的目的有两个:求出满足一定条件下,函数的极值或最大值最 小值;求出取得极值时变量的取值。最优化问题所涉及的内容种类繁多,有的十分复杂,但是它们都有共同的 关键因素:变量,约束条件和目标函数。(2)变量变量是指最优化问题中所涉及的与约束条件和目标函数有关的待确定的量。 一般来说,它们都有一些限制条件(约束条件),与目标函数紧密关联。设问题中涉及的变量为X1,X2, ,Xn ;我
3、们常常也用X =(X1,X2,Xn)表示。(3)约束条件在最优化问题中,求目标函数的极值时,变量必须满足的限制称为 约束条件 例如,许多实际问题变量要求必须非负,这是一种限制;在研究电路优化设计问题时,变量必须服从电路基本定律,这也是一种限制等等。在研究问题时, 这些限制我们必须用数学表达式准确地描述它们。用数学语言描述约束条件一般来说有两种:等式约束条件gj(X)=o,i =1,2- ,m不等式约束条件hj(X) _o,i =12,r或 hj(X)乞 0,i =1,2,r注:在最优化问题研究中,由于解的存在性十分复杂,一般来说,我们不考虑不 等式约束条件h(X) 0或h(X):0。这两种约束
4、条件最优化问题最优解的存在性 较复杂。(4) 目标函数在最优化问题中,与变量有关的待求其极值(或最大值最小值)的函数称为 目标函数。目标函数常用f(X)二f(XX2,,Xn)表示。当目标函数为某问题的效益函数 时,问题即为求极大值;当目标函数为某问题的费用函数时,问题即为求极小值等等。求极大值和极小值问题实际上没有原则上的区别,因为求f (X)的极小值,也就是要求-f(X)的极大值,两者的最优值在同一点取到1. 2 最优化问题分类最优化问题种类繁多,因而分类的方法也有许多。可以按变量的性质分类, 按有无约束条件分类,按目标函数的个数分类等等。一般来说,变量可以分为确定性变量,随机变量和系统变量
5、等等,相对应的 最优化问题分别称为:普通最优化问题,统计最优化问题和系统最优化问题。按有无约束条件分类:无约束最优化问题,有约束最优化问题。按目标函数的个数分类:单目标最优化问题,多目标最优化问题。按约束条件和目标函数是否是线性函数分类:线性最优化问题(线性规划),非线性最优化问题(非线性规划)。按约束条件和目标函数是否是时间的函数分类:静态最优化问题和动态最优 化问题(动态规划)。按最优化问题求解方法分类:无约束解析法(间接法)有约束古典微分法 古典变分法 极大值原理库恩-图克定理斐波那西法一维搜索法*黄金分割法插值法数值算法(直接法)数值算法(梯度法):坐标轮换法步长加速法 多维搜索法丿方
6、向加速法单纯形法随机搜索法最速下降法 拟牛顿法无约束梯度法有约束梯度法共轭梯度法 变尺度法 可行方向法 .梯度投影法“SUMT 法化有约束为无约束 SWIFT法i复形法”单目标化方法 多目标优化方法多重目标化方法目标关联函数法 网络优化方法1. 3 最优化问题的求解步骤和数学模型(1)最优化问题的求解步骤最优化问题的求解涉及到应用数学, 计算机科学以及各专业领域等等,是一 个十分复杂的问题,然而它却是需要我们重点关心的问题之一。 怎样研究分析求 解这类问题呢?其中最关键的是建立数学模型和求解数学模型。 一般来说,应用 最优化方法解决实际问题可分为四个步骤进行:步骤1:建立模型提出最优化问题,变
7、量是什么?约束条件有那些?目标函数是什么?建立最 优化问题数学模型:确定变量,建立目标函数,列出约束条件一一建立模型。步骤2:确定求解方法分析模型,根据数学模型的性质,选择优化求解方法 确定求解方法。 步骤3:计算机求解编程序(或使用数学计算软件),应用计算机求最优解一一计算机求解。 步骤4:结果分析对算法的可行性、收敛性、通用性、时效性、稳定性、灵敏性和误差等等作出 评价一一结果分析。(2)最优化问题数学模型最优化问题的求解与其数学模型的类型密切相关,因而我们有必要对最优化问题的数学模型有所掌握。一般来说,最优化问题的常见数学模型有以下几种: 无约束最优化问题数学模型由某实际问题设立变量,建
8、立一个目标函数且无约束条件,这样的求函数极值或最大值最小值问题,我们称为 无约束最优化问题。其数学模型为:m i nf(Xi,X2,Xn)目标函数例如:求一元函数y = f (x)和二元函数z=f(x, y)的极值。又例如:求函数 f (Xi, X2, X33x2 4x2 6x3 2X1X2 -4X1X3 -2X2X3 的极值和取 得极值的点。 有约束最优化问题数学模型由某实际问题设立变量,建立一个目标函数和若干个约束条件 (等式或不等 式),这样的求函数极值或最大值最小值问题,我们称为 有约束最优化问题。其 数学模型为:m i nf(Xi,X2,,Xn)目标函数gi(Xi,X2/ ,Xn)
9、=0 i =1,2,m约束条件有约束最优化问题的例子:求函数 f (x1,x2,x3 x1x xn在约束条件条件Xi X3 Xn =2008, Xi _0,i =1,2,,n下的最大值和取得最大值的点。 线性规划问题数学模型由某实际问题设立变量,建立一个目标函数和若干个约束条件,目标函数和约束条件都是变量的线性函数,而且变量是非负的,这样的求函数最大值最小其标准数学模型为:目标函数约束条件目标函数约束条件值问题,我们称为线性最优化问题,简称为 线性规划问题m i nf (X1,X2, ,Xn)二 C1X1 QX? CnXn61X1 ai2X2aim x bii =1,2, ,mXi -0矩阵形
10、式:min f(X)=CTXAX 二 BX -0其中 X =(X1,X2, ,Xn)T,C=(C1,C2, ,Cn)T,B = (0, b?厂,bm) 丁在线性规划问题中,关于约束条件我们必须注意以下几个问题。注1:非负约束条件Xi _0 (i =1,2/ , n),般来说这是实际问题要求的需要。如果约束条件为Xj dj,我们作变量替换Zj =Xj -dj -0 ;如果约束条件为Xi _di,我们作变量替换 乙二di - Xi _0。注2:在线性规划的标准数学模型中,约束条件为等式。如果约束条件不是等式,我们引入松驰变量,化不等式约束条件为等式约束 条件。情况1:若约束条件为 ai2x2川aj
11、mXn _ d,引入松驰变量原约束条件变为 ai1x1- ai2x2 amXn - Zj = 0。情况2:若约束条件为aiiXi ai2X2亠亠amXn込6,引入松驰变量原约束条件变为ai1X1 - ai2x2川川aimxn z b在其它最优化问题中,我们也常常采取上述方法化不等式约束条件为等式约 束条件。实际问题中,我们经常遇到两类特殊的线性规划问题。一类是:所求变量要 求是非负整数,称为整数规划问题;另一类是所求变量要求只取0或1,称为0-1 规划问题。例如:整数规划问题x2 3.13s.t. 22为 +34x2 启2 8 5 。x0,x0且为整数又例如:0-1规划问题m axz = 3x
12、12x2 5x3+ 2x2 - x3 2X1 + 4x2 + x3 4亠s.t.x1,x2,x = 0 或1。X x2 空 34x2 x3 乞 6 非线性规划问题数学模型由某实际问题设立变量,建立一个目标函数和若干个约束条件, 如果目标函 数或约束条件表达式中有变量的非线性函数, 那么,这样的求函数最大值最小值 问题,我们称为非线性规划最优化问题,简称为非线性规划问题。其数学模型为:m i nf(X1,X2,,Xn)目标函数gi (X1,X2/ ,Xn) =0 i =1,2, ,m 约束条件其中目标函数或约束条件中有变量的非线性函数。例如:非线性规划问题min f(x, y) =(x-1)2
13、y(x, y) = x + y-2 兰 0 。(x, y) = y 兰 0上述最优化问题中,目标函数是非线性函数,故称为非线性规划问题。前面介绍的四种最优化数学模型都只有一个目标函数,称为单目标最优化问题,简称为最优化问题。 多目标最优化问题数学模型由某实际问题设立变量,建立两个或多个目标函数和若干个约束条件, 且目 标函数或约束条件是变量的函数, 这样的求函数最大值最小值问题,我们称为多 目标最优化问题。其数学模型为:min fj (Xi, X2,Xn)i =1,2,,s目标函数gi(xi,X2, ,Xn) =0 i =1,2, , m约束条件上述模型中有s个目标函数,m个等式约束条件。例如
14、:“生产商如何使得产值最大而且消耗资源最少问题”“投资商如何使得投资收益最大而且风险最小问题”等都是多目标最优化问题。 2经典最优化方法经典最优化方法包括无约束条件极值问题和等式约束条件极值问题两种,不 等式约束条件极值问题可以化为等式约束条件极值问题。经典的极值理论:首先,根据可微函数取极值的必要条件确定可能极值点; 其次,根据函数取极值的充分条件判断是否取极值?是极大值?还是极小值?这 种方法已经几百年的历史了。2. 1无约束条件极值设n元函数f (X)二f (Xi,X2,Xn),求f (X)的极值和取得极值的点。这是一 个无约束条件极值问题,经典的极值理论如下。定理1 (极值必要条件):设n元函数f (X)二f (xX2,,Xn)具有偏导数,则f (X) 在X二X *处取得极值的必要条件为:丁X * =j = I2, n。-Xj定理在此不给出证明,读者可自己参看有关资料。注1:对于一元函数上述定理当然成立,只是偏导数应为导数;注2:定理只是在偏导数存在的前提下的必要条件。如果函数在某一点偏导数不 存在,那在这一点处仍然可能取得极值;注3:如果函数在某一点偏导数存在,且偏导数都等于零,那么函数在这一点处 也不一定取得极值。例如,函数f (x,y)二3 x2 y2在点(0,0)处偏