多目标最优化模型(34页).doc
《多目标最优化模型(34页).doc》由会员分享,可在线阅读,更多相关《多目标最优化模型(34页).doc(33页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、-第 1 页多目标最优化模多目标最优化模型型-第 2 页第六章第六章最优化数学模型最优化数学模型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)变量变量是指最优化问题中所涉及的与约束条件和目标函数有关的待确定的量。一般来说,它们都有一些限制条
3、件(约束条件),与目标函数紧密关联。设问题中涉及的变量为nxxx,21;我们常常也用),(21nxxxX表示。(3)约束条件在最优化问题中,求目标函数的极值时,变量必须满足的限制称为约束条件约束条件。例如,许多实际问题变量要求必须非负,这是一种限制;在研究电路优化设-第 3 页计问题时,变量必须服从电路基本定律,这也是一种限制等等。在研究问题时,这些限制我们必须用数学表达式准确地描述它们。用数学语言描述约束条件一般来说有两种:等式约束条件miXgi,2,1,0)(不等式约束条件riXhi,2,1,0)(或riXhi,2,1,0)(注:在最优化问题研究中,由于解的存在性十分复杂,一般来说,我们不
4、考虑不等式约束条件0)(Xh或0)(Xh。这两种约束条件最优化问题最优解的存在性较复杂。(4)目标函数在最优化问题中,与变量有关的待求其极值(或最大值最小值)的函数称为目标函数。目标函数。目标函数常用),()(21nxxxfXf表示。当目标函数为某问题的效益函数时,问题即为求极大值;当目标函数为某问题的费用函数时,问题即为求极小值等等。求极大值和极小值问题实际上没有原则上的区别,因为求)(Xf的极小值,也就是要求)(Xf的极大值,两者的最优值在同一点取到。12最优化问题分类最优化问题种类繁多,因而分类的方法也有许多。可以按变量的性质分类,按有无约束条件分类,按目标函数的个数分类等等。一般来说,
5、变量可以分为确定性变量,随机变量和系统变量等等,相对应的最优化问题分别称为:普通最优化问题,统计最优化问题和系统最优化问题。按有无约束条件分类:无约束最优化问题,有约束最优化问题。按目标函数的个数分类:单目标最优化问题,多目标最优化问题。按约束条件和目标函数是否是线性函数分类:线性最优化问题(线性规划),非线性最优化问题(非线性规划)。按约束条件和目标函数是否是时间的函数分类:静态最优化问题和动态最优化问题(动态规划)。按最优化问题求解方法分类:解析法(间接法)图克定理库恩极大值原理有约束古典变分法古典微分法无约束-第 4 页数值算法(直接法)随机搜索法单纯形法方向加速法步长加速法坐标轮换法多
6、维搜索法插值法黄金分割法斐波那西法一维搜索法数值算法(梯度法)复形法法法化有约束为无约束梯度投影法可行方向法有约束梯度法变尺度法共轭梯度法拟牛顿法最速下降法无约束梯度法SWIFTSUMT多目标优化方法目标关联函数法多重目标化方法单目标化方法网络优化方法13最优化问题的求解步骤和数学模型(1)最优化问题的求解步骤最优化问题的求解涉及到应用数学,计算机科学以及各专业领域等等,是一个十分复杂的问题,然而它却是需要我们重点关心的问题之一。怎样研究分析求解这类问题呢?其中最关键的是建立数学模型和求解数学模型。一般来说,应用最优化方法解决实际问题可分为四个步骤进行:步骤步骤 1:建立模型:建立模型提出最优
7、化问题,变量是什么?约束条件有那些?目标函数是什么?建立最优化问题数学模型:确定变量,建立目标函数,列出约束条件建立模型建立模型。步骤步骤 2:确定求解方法:确定求解方法分析模型,根据数学模型的性质,选择优化求解方法确定求解方法确定求解方法。步骤步骤 3:计算机求解:计算机求解编程序(或使用数学计算软件),应用计算机求最优解计算机求解计算机求解。步骤步骤 4:结果分析:结果分析对算法的可行性、收敛性、通用性、时效性、稳定性、灵敏性和误差等等作出评价结果分析结果分析。(2)最优化问题数学模型-第 5 页最优化问题的求解与其数学模型的类型密切相关,因而我们有必要对最优化问题的数学模型有所掌握。一般
8、来说,最优化问题的常见数学模型有以下几种:无约束最优化问题数学模型由某实际问题设立变量,建立一个目标函数且无约束条件,这样的求函数极值或最大值最小值问题,我们称为无约束最优化问题无约束最优化问题。其数学模型为:),(min21nxxxf目标函数例如:求一元函数)(xfy 和二元函数),(yxfz 的极值。又例如:求函数323121232221321242643),(xxxxxxxxxxxxf的极值和取得极值的点。有约束最优化问题数学模型由某实际问题设立变量,建立一个目标函数和若干个约束条件(等式或不等式),这样的求函数极值或最大值最小值问题,我们称为有约束最优化问题有约束最优化问题。其数学模型
9、为:),(min21nxxxf目标函数mixxxgni,2,10),(21约束条件有约束最优化问题的例子:求函数nxxxxxxf31321),(在约束条件条件nixxxxin,2,1,0,200831下的最大值和取得最大值的点。线性规划问题数学模型由某实际问题设立变量,建立一个目标函数和若干个约束条件,目标函数和约束条件都是变量的线性函数,而且变量是非负的,这样的求函数最大值最小值问题,我们称为线性最优化问题,简称为线性规划问题线性规划问题。其标准数学模型为:nnnxcxcxcxxxf221121),(min目标函数0,2,12211iinimiixmibxaxaxa约束条件矩阵形式:XCXf
10、T)(min目标函数0XBAX约束条件其中TnxxxX),(21,TncccC),(21,TmbbbB),(21在线性规划问题中,关于约束条件我们必须注意以下几个问题。注 1:非负约束条件),2,1(0nixi,一般来说这是实际问题要求的需要。如果约束条件为iidx,我们作变量替换0iiidxz;如果约束条件为-第 6 页iidx,我们作变量替换0iiixdz。注 2:在线性规划的标准数学模型中,约束条件为等式。如果约束条件不是等式,我们引入松驰变量,化不等式约束条件为等式约束条件。情况 1:若约束条件为inimiibxaxaxa2211,引入松驰变量原约束条件变为iinimiibzxaxax
11、a2211。情况 2:若约束条件为inimiibxaxaxa2211,引入松驰变量原约束条件变为iinimiibzxaxaxa2211在其它最优化问题中,我们也常常采取上述方法化不等式约束条件为等式约束条件。实际问题中,我们经常遇到两类特殊的线性规划问题。一类是:所求变量要求是非负整数,称为整数规划问题整数规划问题;另一类是所求变量要求只取0或1,称为 0-1规划问题规划问题。例如:整数规划问题又例如:0-1 规划问题321523maxxxxz非线性规划问题数学模型由某实际问题设立变量,建立一个目标函数和若干个约束条件,如果目标函数或约束条件表达式中有变量的非线性函数,那么,这样的求函数最大值
12、最小值问题,我们称为非线性规划最优化问题,简称为非线性规划问题非线性规划问题。其数学模型为:),(min21nxxxf目标函数mixxxgni,2,10),(21约束条件其中目标函数或约束条件中有变量的非线性函数。例如:非线性规划问题yxyxf2)1(),(min上述最优化问题中,目标函数是非线性函数,故称为非线性规划问题。前面介绍的四种最优化数学模型都只有一个目标函数,称为单目标最优化问题,简称为最优化问题。多目标最优化问题数学模型由某实际问题设立变量,建立两个或多个目标函数和若干个约束条件,且目标函数或约束条件是变量的函数,这样的求函数最大值最小值问题,我们称为多多目标最优化问题目标最优化
13、问题。其数学模型为:sixxxfni,2,1),(min21目标函数mixxxgni,2,10),(21约束条件上述模型中有s个目标函数,m个等式约束条件。-第 7 页例如:“生产商如何使得产值最大而且消耗资源最少问题”“投资商如何使得投资收益最大而且风险最小问题”等都是多目标最优化问题。2经典最优化方法经典最优化方法经典最优化方法包括无约束条件极值问题和等式约束条件极值问题两种,不等式约束条件极值问题可以化为等式约束条件极值问题。经典的极值理论:首先,根据可微函数取极值的必要条件确定可能极值点;其次,根据函数取极值的充分条件判断是否取极值?是极大值?还是极小值?这种方法已经几百年的历史了。2
14、1无约束条件极值设n元函数),()(21nxxxfXf,求)(Xf的极值和取得极值的点。这是一个无约束条件极值问题,经典的极值理论如下。定理定理 1(极值必要条件极值必要条件):设n元函数),()(21nxxxfXf具有偏导数,则)(Xf在*XX 处取得极值的必要条件为:定理在此不给出证明,读者可自己参看有关资料。注 1:对于一元函数上述定理当然成立,只是偏导数应为导数;注 2:定理只是在偏导数存在的前提下的必要条件。如果函数在某一点偏导数不存在,那在这一点处仍然可能取得极值;注 3:如果函数在某一点偏导数存在,且偏导数都等于零,那么函数在这一点处也不一定取得极值。例如,函数232),(yxy
15、xf在点)0,0(处偏导数不存在,但在这一点处函数仍然取得极小值零。函数53),(yxyxf在点)0,0(处偏导数存在,且偏导数都等于零,但在这一点处函数不取极值。定理 1 的作用在于,求出函数的可能极值点,然后,我们再研究这些点是否取得极值。对于许多实际问题来说,函数一定能够取得极大值或极小值,而函数的可能极值点(满足必要条件的点)又只有一点,则这一点当然是函数取得极大值或极小值的点。对于一般函数而言,我们怎样判定函数在某点是否取极值?是极大值?还是极小值?我们有下面的极值的充分条件定理。定理定理 2(极值充分条件极值充分条件):设n元函数),()(21nxxxfXf具有二阶偏导数,则)(X
16、f在*XX 处取得极值的充分条件为:(1)nixfXXi,3,20|*;-第 8 页(2)黑塞矩阵2222122222212212212212nxnnnxfxxfxxfxxfxfxxfxxfxxfxf在*XX 处正定或负定;(3)黑塞矩阵在*XX 处正定时,函数取极小值;负定时,函数取极大值。本章内容简要讲解理论,注重实际应用,对于许多经典的定理都不进行证明,读者可自己参看有关资料。例 1:求函数322123222132122462),(xxxxxxxxxxf的极值。解:(1)根据极值存在的必要条件,确定可能取得极值的点:令0321xfxfxf,解得)0,0,0(),(321xxx。(2)根据
17、极值存在的充分条件,确定)0,0,0(),(321xxx是否是极值点:计算4212xf,12222xf,8232xf;函数的黑塞矩阵为8202122024)0,0,0(2f因为04,04412224,03208202122024;所以黑塞矩阵负定,故函数在)0,0,0(),(321xxx处取得极大值0)0,0,0(f。22等式约束条件极值下面我们研究的是有若干个等式约束条件下,一个目标函数的极值问题,其数学模型为:),(min21nxxxf目标函数mixxxgtsni,2,10),(.21约束条件拉格朗日(拉格朗日(Lagrange)乘数法乘数法:(1)令),(),(21121nimiinxx
18、xgxxxfL-第 9 页称为上述问题的拉格朗日乘数函数,称i为拉格朗日乘数。(2)设),(21nxxxf和),(21nixxxg均可微,则得到方程组(3)若),(2121mnxxx是上述方程组的解,则点),(21nxxx可能为该问题的最优点。拉格朗日(Lagrange)乘数法的本质是:将求有约束条件极值问题转化为求无条件极值问题;所求得的点,即是取得极值的必要条件点。拉格朗日乘数法没有解决极值的存在性问题,但是,如果拉格朗日乘数函数具有二阶连续偏导数,我们也可以应用黑塞矩阵来判定函数是否取得极值。在具体问题中,点),(21nxxx是否为最优点通常可由问题的实际意义决定。例 2:求表面积为定值
19、2a,而体积为最大的长方体的体积。解:设长方体的三棱长为zyx,,体积为V;建立数学模型如下:xyzV max构造拉格朗日乘数函数)222(),(2axzyzxyxyzzyxL,则有解得azyx66,3366maxaV 为所求。23不等式约束条件极值对于不等式约束条件极值问题:),(min21nxxxf目标函数mixxxgtsni,2,10),(.21约束条件我们有与拉格朗日乘数法密切相关的方法库恩图克定理。定理定理 3(库恩库恩图克定理图克定理):对于上述不等式约束条件极值问题,设),(21nxxxf和),(21nixxxg均可微,令),(),(21121nimiinxxxgxxxfL假设i
20、存在,则在最优点*XX),(21nxxx处,必满足下述条件:(1)mijiijjnjxgxfxL1,2,10;(2)mixxxgni,2,10),(21;(3)mixxxgnii,2,10),(21;-第 10 页(4)0i。根据库恩图克定理我们可以求解许多不等式约束条件极值问题,值得注意的是应用库恩图克定理求解不等式约束条件极值问题,定理并没有解决最优解的存在性问题,因此,我们必须另行判断。例 3:求解最优化问题(最优解存在)解:构造函数)()2()1(),(212yyxyxzyxL,根据库恩图克定理则有0,000)2(010)1(22121211yyxyLxxL解得:1,0,0,121yx
21、;所求最优解为)0,1(),(yx,最优值为0。3线性规划线性规划31线性规划设线性规划标准数学模型为:nnnxcxcxcxxxf221121),(min目标函数nixmibxaxaxatsiinimii,2,10,2,1.2211约束条件矩阵形式:XCXfT)(min目标函数0XBAX约束条件其中TnxxxX),(21,TncccC),(21,TmbbbB),(21线性规划问题的求解有一整套理论体系,一般来说,应用单纯形法求解。此方法尽管比较复杂,然而在计算机上实现并不困难。解线性规划问题的单纯形法已在许多数学计算软件中实现,我们求解线性规划问题可根据需要,应用数学计算软件求解即可。在此,我
22、们不系统研究其理论,只是简单介绍线性规划的穷举法和单纯形法的基本思想。3.2线性规划的穷举法(1)穷举法基本原理和步骤步骤步骤 1 1:将线性规划问题化成矩阵的标准形式,设系数矩阵的秩mAR)(,则对应线性方程组的基础解系自由变量的个数为mn 个。步骤步骤 2 2:穷举法求解:令0)(21mniiixxx,解得对应线性方程组一组解为-第 11 页),(21nxxx;对应目标函数值为infxxxf),(21。从n个变量x中选mn 个作为自由变量,令它们的值为 0,可得到mnnmnCC组解。步骤步骤 3 3:确定最优解:如果最优解存在,则上述求解得到的对应mnnmnCC个目标函数值中,最小者(或最
23、大者)即为所求最小(或最大)最优值,对应的解为最优解。步骤步骤 4 4:证明解为最优解:将最优解对应的自由变量看成参数)(21,mnttt;解对应线性方程组得将对应线性方程组解nitbtbtbbxmnmniiiii,2,1,)()(22110代入目标函数得:)()(22110mnmntdtdtdff。如果nidi,2,1,0,则所求为最小值最优解;否则,线性规划问题无最小值最优解。如果nidi,2,1,0,则所求为最大值最优解;否则,线性规划问题无最大值最优解。例 1:目标函数:32132)(maxxxxXf解:约束条件的增广矩阵为:令021 xx,解得5)(),4,10,5,0,0(XfX;
24、令031 xx,无解;令041 xx,解得)1,0,5,5,0(X,不满足非负条件,舍去;令051 xx,解得17)(),0,2,5,4,0(XfX;令032 xx,解得10)(),4,5,0,0,5(XfX;令042 xx,解得)4,0,5,0,10(X,不满足非负条件,舍去;令052 xx,无解;令043 xx,解得235)(),23,0,0,25,5(XfX;令053 xx,解得)0,3,0,4,5(X,不满足非负条件,舍去;令054 xx,解得19)(),0,0,3,4,2(XfX;-第 12 页所以19)(maxXf,最优解为)0,0,3,4,2(X。证明:令sxtx54,解得5,1
25、,023422321ixstxsxstxi目标函数stXf19)(;因为sxtx54,非负,所以19)(maxXf,故最优解存在。(2)单纯形法基本原理和步骤将线性规划问题化成矩阵的标准形式,设系数矩阵的秩mAR)(,则对应线性方程组的基础解系的个数为mn 个,即有mn 个自由参数变量。选取mn 个非基变量基变量(自由参数变量),不妨假设为nmjxj,1,;解得线性规划问题的典式典式定理定理 1:如果线性规划问题的上述典式中所有nmjj,1,0;则)0,0,(21mX为最优解。定理定理 2:如果线性规划问题的上述典式中存在某个0km,且对应mikmi,2,1,0)(;则线性规划问题无最优解。由
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 多目标 优化 模型 34
限制150内