2022年多目标最优化模型 .pdf
《2022年多目标最优化模型 .pdf》由会员分享,可在线阅读,更多相关《2022年多目标最优化模型 .pdf(43页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、第六章最优化数学模型1 最优化问题11 最优化问题概念12 最优化问题分类13 最优化问题数学模型2 经典最优化方法21 无约束条件极值22 等式约束条件极值23 不等式约束条件极值3 线性规划31 线性规划32 整数规划4 最优化问题数值算法41 直接搜索法42 梯度法43 罚函数法5 多目标优化问题51 多目标优化问题52 单目标化解法53 多重优化解法54 目标关联函数解法55 投资收益风险问题名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页,共 43 页 - - - -
2、 - - - - - 第六章最优化问题数学模型1 最优化问题11 最优化问题概念(1)最优化问题在工业、农业、交通运输、商业、国防、建筑、通信、政府机关等各部门各领域的实际工作中, 我们经常会遇到求函数的极值或最大值最小值问题,这一类问题我们称之为 最优化问题 。而求解最优化问题的数学方法被称为最优化方法。它主要解决最优生产计划、最优分配、最佳设计、最优决策、最优管理等求函数最大值最小值问题。最优化问题的目的有两个: 求出满足一定条件下, 函数的极值或最大值最小值;求出取得极值时变量的取值。最优化问题所涉及的内容种类繁多,有的十分复杂,但是它们都有共同的关键因素:变量,约束条件和目标函数。(2
3、)变量变量是指最优化问题中所涉及的与约束条件和目标函数有关的待确定的量。一般来说,它们都有一些限制条件(约束条件),与目标函数紧密关联。设问题中涉及的变量为nxxx,21;我们常常也用),(21nxxxX表示。(3)约束条件在最优化问题中, 求目标函数的极值时, 变量必须满足的限制称为约束条件 。例如,许多实际问题变量要求必须非负,这是一种限制;在研究电路优化设计问题时,变量必须服从电路基本定律,这也是一种限制等等。在研究问题时,这些限制我们必须用数学表达式准确地描述它们。用数学语言描述约束条件一般来说有两种:等式约束条件miXgi, 2, 1,0)(不等式约束条件riXhi,2 , 1,0)
4、(或riXhi,2 , 1,0)(注:在最优化问题研究中,由于解的存在性十分复杂,一般来说,我们不考虑不等式约束条件0)(Xh或0)(Xh。这两种约束条件最优化问题最优解的存在性较复杂。(4)目标函数在最优化问题中,与变量有关的待求其极值(或最大值最小值)的函数称为目标函数。目标函数常用),()(21nxxxfXf表示。当目标函数为某问题的效益函数时,问题即为求极大值;当目标函数为某问题的费用函数时,问题即为求极小值等等。求极大值和极小值问题实际上没有原则上的区别,因为求)(Xf的极小值,也就是要求)(Xf的极大值,两者的最优值在同一点取到。名师资料总结 - - -精品资料欢迎下载 - - -
5、 - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页,共 43 页 - - - - - - - - - 12 最优化问题分类最优化问题种类繁多,因而分类的方法也有许多。可以按变量的性质分类,按有无约束条件分类,按目标函数的个数分类等等。一般来说, 变量可以分为确定性变量,随机变量和系统变量等等,相对应的最优化问题分别称为:普通最优化问题,统计最优化问题和系统最优化问题。按有无约束条件分类:无约束最优化问题,有约束最优化问题。按目标函数的个数分类:单目标最优化问题,多目标最优化问题。按约束条件和目标函数是否是线性函数分类:线性最优化问
6、题 (线性规划),非线性最优化问题(非线性规划) 。按约束条件和目标函数是否是时间的函数分类:静态最优化问题和动态最优化问题(动态规划)。按最优化问题求解方法分类:解析法(间接法)图克定理库恩极大值原理有约束古典变分法古典微分法无约束数值算法(直接法)随机搜索法单纯形法方向加速法步长加速法坐标轮换法多维搜索法插值法黄金分割法斐波那西法一维搜索法数值算法(梯度法)复形法法法化有约束为无约束梯度投影法可行方向法有约束梯度法变尺度法共轭梯度法拟牛顿法最速下降法无约束梯度法SWIFTSUMT多目标优化方法目标关联函数法多重目标化方法单目标化方法网络优化方法名师资料总结 - - -精品资料欢迎下载 -
7、- - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页,共 43 页 - - - - - - - - - 13 最优化问题的求解步骤和数学模型(1)最优化问题的求解步骤最优化问题的求解涉及到应用数学,计算机科学以及各专业领域等等,是一个十分复杂的问题, 然而它却是需要我们重点关心的问题之一。怎样研究分析求解这类问题呢?其中最关键的是建立数学模型和求解数学模型。一般来说,应用最优化方法解决实际问题可分为四个步骤进行:步骤 1:建立模型提出最优化问题,变量是什么?约束条件有那些?目标函数是什么?建立最优化问题数学模型:确定变量,建立
8、目标函数,列出约束条件建立模型 。步骤 2:确定求解方法分析模型,根据数学模型的性质,选择优化求解方法确定求解方法 。步骤 3:计算机求解编程序(或使用数学计算软件) ,应用计算机求最优解计算机求解 。步骤 4:结果分析对算法的可行性、收敛性、通用性、时效性、稳定性、灵敏性和误差等等作出评价 结果分析 。(2)最优化问题数学模型最优化问题的求解与其数学模型的类型密切相关,因而我们有必要对最优化问题的数学模型有所掌握。一般来说,最优化问题的常见数学模型有以下几种:无约束最优化问题数学模型由某实际问题设立变量, 建立一个目标函数且无约束条件,这样的求函数极值或最大值最小值问题,我们称为无约束最优化
9、问题 。其数学模型为:),(m i n21nxxxf目标函数例如:求一元函数)(xfy和二元函数),(yxfz的极值。又例如:求函数323121232221321242643),(xxxxxxxxxxxxf的极值和取得极值的点。有约束最优化问题数学模型由某实际问题设立变量, 建立一个目标函数和若干个约束条件(等式或不等式) ,这样的求函数极值或最大值最小值问题,我们称为有约束最优化问题 。其数学模型为:),(m i n21nxxxf目标函数mixxxgni, 2, 10),(21约束条件有约束最优化问题的例子:求函数nxxxxxxf31321),(在约束条件条件nixxxxin,2 , 1,0
10、,200831下的最大值和取得最大值的点。线性规划问题数学模型由某实际问题设立变量,建立一个目标函数和若干个约束条件,目标函数和约束条件都是变量的线性函数,而且变量是非负的, 这样的求函数最大值最小名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页,共 43 页 - - - - - - - - - 值问题,我们称为线性最优化问题,简称为线性规划问题 。其标准数学模型为:nnnxcxcxcxxxf221121),(m i n目标函数0, 2, 12211iinimiixmibxax
11、axa约束条件矩阵形式:XCXfT)(m i n目标函数0XBAX约束条件其中TnxxxX),(21,TncccC),(21,TmbbbB),(21mnmmnnaaaaaaaaaA212222111211在线性规划问题中,关于约束条件我们必须注意以下几个问题。注 1:非负约束条件), 2, 1(0nixi,一般来说这是实际问题要求的需要。如果约束条件为iidx,我们作变量替换0iiidxz;如果约束条件为iidx,我们作变量替换0iiixdz。注 2:在线性规划的标准数学模型中,约束条件为等式。如果约束条件不是等式, 我们引入松驰变量, 化不等式约束条件为等式约束条件。情况 1:若约束条件为i
12、nimiibxaxaxa2211,引入松驰变量02211inimiiibxaxaxaz原约束条件变为iinimiibzxaxaxa2211。情况 2:若约束条件为inimiibxaxaxa2211,引入松驰变量0)(2211nimiiiixaxaxabz原约束条件变为iinimiibzxaxaxa2211在其它最优化问题中, 我们也常常采取上述方法化不等式约束条件为等式约束条件。实际问题中, 我们经常遇到两类特殊的线性规划问题。一类是:所求变量要求是非负整数, 称为整数规划问题 ;另一类是所求变量要求只取0或1,称为 0-1名师资料总结 - - -精品资料欢迎下载 - - - - - - -
13、- - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页,共 43 页 - - - - - - - - - 规划问题 。例如:整数规划问题213minxxz且为整数0,0285342213.3.21212xxxxxts。又例如: 0-1 规划问题321523m a xxxxz10,6434422.3213221321321或xxxxxxxxxxxxxts。非线性规划问题数学模型由某实际问题设立变量, 建立一个目标函数和若干个约束条件,如果目标函数或约束条件表达式中有变量的非线性函数,那么,这样的求函数最大值最小值问题,我们称为非线性规划最优化问题, 简称
14、为 非线性规划问题 。 其数学模型为:),(m i n21nxxxf目标函数mixxxgni, 2, 10),(21约束条件其中目标函数或约束条件中有变量的非线性函数。例如:非线性规划问题yxyxf2) 1(),(m i n0),(02),(21yyxgyxyxg。上述最优化问题中,目标函数是非线性函数,故称为非线性规划问题。前面介绍的四种最优化数学模型都只有一个目标函数,称为单目标最优化问题,简称为最优化问题。多目标最优化问题数学模型由某实际问题设立变量, 建立两个或多个目标函数和若干个约束条件,且目标函数或约束条件是变量的函数,这样的求函数最大值最小值问题,我们称为 多目标最优化问题 。其
15、数学模型为:sixxxfni, 2, 1),(m i n21目标函数mixxxgni, 2, 10),(21约束条件上述模型中有 s个目标函数, m个等式约束条件。例如: “生产商如何使得产值最大而且消耗资源最少问题”“投资商如何使得投资收益最大而且风险最小问题”等都是多目标最优化问题。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页,共 43 页 - - - - - - - - - 2 经典最优化方法经典最优化方法包括无约束条件极值问题和等式约束条件极值问题两种,不等式约束条
16、件极值问题可以化为等式约束条件极值问题。经典的极值理论:首先,根据可微函数取极值的必要条件确定可能极值点;其次,根据函数取极值的充分条件判断是否取极值?是极大值?还是极小值?这种方法已经几百年的历史了。21 无约束条件极值设 n元函数),()(21nxxxfXf,求)(Xf的极值和取得极值的点。这是一个无约束条件极值问题,经典的极值理论如下。定理 1 (极值必要条件): 设 n元函数),()(21nxxxfXf具有偏导数,则)(Xf在*XX处取得极值的必要条件为:nixfXXi,2, 10|*。定理在此不给出证明,读者可自己参看有关资料。注 1:对于一元函数上述定理当然成立,只是偏导数应为导数
17、;注 2:定理只是在偏导数存在的前提下的必要条件。如果函数在某一点偏导数不存在,那在这一点处仍然可能取得极值;注 3:如果函数在某一点偏导数存在,且偏导数都等于零,那么函数在这一点处也不一定取得极值。例如,函数232),(yxyxf在点)0,0(处偏导数不存在,但在这一点处函数仍然取得极小值零。函数53),(yxyxf在点)0,0(处偏导数存在,且偏导数都等于零,但在这一点处函数不取极值。定理 1 的作用在于, 求出函数的可能极值点,然后,我们再研究这些点是否取得极值。对于许多实际问题来说, 函数一定能够取得极大值或极小值,而函数的可能极值点(满足必要条件的点)又只有一点,则这一点当然是函数取
18、得极大值或极小值的点。对于一般函数而言, 我们怎样判定函数在某点是否取极值?是极大值?还是极小值?我们有下面的极值的充分条件定理。定理 2(极值充分条件):设n 元函数),()(21nxxxfXf具有二阶偏导数,则)(Xf在*XX处取得极值的充分条件为:(1)nixfXXi,3 ,20|*;名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页,共 43 页 - - - - - - - - - (2)黑塞矩阵2222122222212212212212nxnnnxfxxfxxfxxf
19、xfxxfxxfxxfxf在*XX处正定或负定;(3)黑塞矩阵在*XX处正定时,函数取极小值; 负定时,函数取极大值。本章内容简要讲解理论, 注重实际应用,对于许多经典的定理都不进行证明,读者可自己参看有关资料。例 1:求函数322123222132122462),(xxxxxxxxxxf的极值。解: (1)根据极值存在的必要条件,确定可能取得极值的点:21124xxxf,31222212xxxxf,23328xxxf令0321xfxfxf,解得)0,0 ,0(),(321xxx。(2) 根据极值存在的充分条件,确定)0 ,0, 0(),(321xxx是否是极值点:计算4212xf,12222
20、xf,8232xf;2212xxf,0312xxf,2322xxf;函数的黑塞矩阵为8202122024)0,0 ,0(2f因为04,04412224,03208202122024;所以黑塞矩阵负定,故函数在)0 ,0 ,0(),(321xxx处取得极大值0)0 ,0,0(f。22 等式约束条件极值下面我们研究的是有若干个等式约束条件下,一个目标函数的极值问题, 其数学模型为:),(m i n21nxxxf目标函数名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页,共 43 页
21、- - - - - - - - - mixxxgtsni,2, 10),(.21约束条件拉格朗日( Lagrange)乘数法 :(1)令),(),(21121nimiinxxxgxxxfL称为上述问题的拉格朗日乘数函数,称i为拉格朗日乘数。(2)设),(21nxxxf和),(21nixxxg均可微,则得到方程组nixxxgLnjxgxfxLniimijiijj, 2, 10),(, 2, 10211(3)若),(2121mnxxx是上述方程组的解, 则点),(21nxxx可能为该问题的最优点。拉格朗日(Lagrange)乘数法的本质是: 将求有约束条件极值问题转化为求无条件极值问题;所求得的点
22、,即是取得极值的必要条件点。拉格朗日乘数法没有解决极值的存在性问题,但是,如果拉格朗日乘数函数具有二阶连续偏导数,我们也可以应用黑塞矩阵来判定函数是否取得极值。在具体问题中, 点),(21nxxx是否为最优点通常可由问题的实际意义决定。例 2:求表面积为定值2a,而体积为最大的长方体的体积。解:设长方体的三棱长为zyx,,体积为V;建立数学模型如下:xyzVmax0, 0,0222. .2zyxayzxzxyts构造拉格朗日乘数函数)222(),(2axzyzxyxyzzyxL,则有0)(20)(20)(2yxxyzLzxxzyLzyyzxL解得azyx66,3366maxaV为所求。名师资料
23、总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页,共 43 页 - - - - - - - - - 23 不等式约束条件极值对于不等式约束条件极值问题:),(m i n21nxxxf目标函数mixxxgtsni, 2, 10),(.21约束条件我们有与拉格朗日乘数法密切相关的方法库恩图克定理。定理 3 (库恩图克定理): 对于上述不等式约束条件极值问题, 设),(21nxxxf和),(21nixxxg均可微,令),(),(21121nimiinxxxgxxxfL假设i存在,则在最优点*
24、XX),(21nxxx处,必满足下述条件:(1)mijiijjnjxgxfxL1,2, 10;(2)mixxxgni, 2, 10),(21;(3)mixxxgnii,2, 10),(21;(4)0i。根据库恩图克定理我们可以求解许多不等式约束条件极值问题,值得注意的是应用库恩图克定理求解不等式约束条件极值问题,定理并没有解决最优解的存在性问题,因此,我们必须另行判断。例 3:求解最优化问题(最优解存在)yxyxf2) 1(),(m i n0),(02),(21yyxgyxyxg解:构造函数)()2() 1(),(212yyxyxzyxL,根据库恩图克定理则有0,000)2(010) 1(22
25、121211yyxyLxxL解得:1, 0, 0, 121yx;所求最优解为)0 ,1 (),(yx,最优值为0。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页,共 43 页 - - - - - - - - - 3 线性规划31 线性规划设线性规划标准数学模型为:nnnxcxcxcxxxf221121),(m i n目标函数nixmibxaxaxatsiinimii,2 , 10,2 , 1.2211约束条件矩阵形式:XCXfT)(m i n目标函数0XBAX约束条件其中T
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 2022年多目标最优化模型 2022 多目标 优化 模型
限制150内