多目标最优化数学模型

《多目标最优化数学模型》由会员分享，可在线阅读，更多相关《多目标最优化数学模型（34页珍藏版）》请在装配图网上搜索。

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变量 变量是指最优化问题中所涉与的与约束条件和目标函数有关的待确定的量.一般来说,它们都有一些限制条件约束条件,与目标函数紧密关联.设问题中涉与的变量为；我们常常也用表示.3约束条件在最优化问题中,求目标函数的极值时,变量必须

3、满足的限制称为约束条件. 例如,许多实际问题变量要求必须非负,这是一种限制；在研究电路优化设计问题时,变量必须服从电路基本定律,这也是一种限制等等.在研究问题时,这些限制我们必须用数学表达式准确地描述它们. 用数学语言描述约束条件一般来说有两种：等式约束条件 不等式约束条件 或 注：在最优化问题研究中,由于解的存在性十分复杂,一般来说,我们不考虑不等式约束条件或.这两种约束条件最优化问题最优解的存在性较复杂.4目标函数在最优化问题中,与变量有关的待求其极值或最大值最小值的函数称为目标函数. 目标函数常用表示.当目标函数为某问题的效益函数时,问题即为求极大值；当目标函数为某问题的费用函数时,问题

4、即为求极小值等等.求极大值和极小值问题实际上没有原则上的区别,因为求的极小值,也就是要求的极大值,两者的最优值在同一点取到.12 最优化问题分类 最优化问题种类繁多,因而分类的方法也有许多.可以按变量的性质分类,按有无约束条件分类,按目标函数的个数分类等等. 一般来说,变量可以分为确定性变量,随机变量和系统变量等等,相对应的最优化问题分别称为：普通最优化问题,统计最优化问题和系统最优化问题.按有无约束条件分类：无约束最优化问题,有约束最优化问题.按目标函数的个数分类：单目标最优化问题,多目标最优化问题.按约束条件和目标函数是否是线性函数分类：线性最优化问题线性规划,非线性最优化问题非线性规划.

5、按约束条件和目标函数是否是时间的函数分类：静态最优化问题和动态最优化问题动态规划.按最优化问题求解方法分类：解析法间接法数值算法直接法数值算法梯度法多目标优化方法网络优化方法13 最优化问题的求解步骤和数学模型1最优化问题的求解步骤最优化问题的求解涉与到应用数学,计算机科学以与各专业领域等等,是一个十分复杂的问题,然而它却是需要我们重点关心的问题之一.怎样研究分析求解这类问题呢？其中最关键的是建立数学模型和求解数学模型.一般来说,应用最优化方法解决实际问题可分为四个步骤进行：步骤1：建立模型提出最优化问题,变量是什么？约束条件有那些？目标函数是什么？建立最优化问题数学模型：确定变量,建立目标函

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

7、求一元函数和二元函数的极值.又例如：求函数的极值和取得极值的点.有约束最优化问题数学模型由某实际问题设立变量,建立一个目标函数和若干个约束条件等式或不等式,这样的求函数极值或最大值最小值问题,我们称为有约束最优化问题.其数学模型为：目标函数约束条件有约束最优化问题的例子：求函数在约束条件条件下的最大值和取得最大值的点.线性规划问题数学模型由某实际问题设立变量,建立一个目标函数和若干个约束条件,目标函数和约束条件都是变量的线性函数,而且变量是非负的,这样的求函数最大值最小值问题,我们称为线性最优化问题,简称为线性规划问题.其标准数学模型为：目标函数约束条件矩阵形式： 目标函数约束条件其中 ,在线

8、性规划问题中,关于约束条件我们必须注意以下几个问题.注1：非负约束条件,一般来说这是实际问题要求的需要.如果约束条件为,我们作变量替换；如果约束条件为,我们作变量替换.注2：在线性规划的标准数学模型中,约束条件为等式.如果约束条件不是等式,我们引入松驰变量,化不等式约束条件为等式约束条件.情况1：若约束条件为,引入松驰变量原约束条件变为 .情况2：若约束条件为,引入松驰变量原约束条件变为 在其它最优化问题中,我们也常常采取上述方法化不等式约束条件为等式约束条件.实际问题中,我们经常遇到两类特殊的线性规划问题.一类是：所求变量要求是非负整数,称为整数规划问题；另一类是所求变量要求只取或,称为0-

9、1规划问题.例如：整数规划问题.又例如：0-1规划问题.非线性规划问题数学模型由某实际问题设立变量,建立一个目标函数和若干个约束条件,如果目标函数或约束条件表达式中有变量的非线性函数,那么,这样的求函数最大值最小值问题,我们称为非线性规划最优化问题,简称为非线性规划问题.其数学模型为：目标函数约束条件其中目标函数或约束条件中有变量的非线性函数.例如：非线性规划问题. 上述最优化问题中,目标函数是非线性函数,故称为非线性规划问题.前面介绍的四种最优化数学模型都只有一个目标函数,称为单目标最优化问题,简称为最优化问题.多目标最优化问题数学模型由某实际问题设立变量,建立两个或多个目标函数和若干个约束

10、条件,且目标函数或约束条件是变量的函数,这样的求函数最大值最小值问题,我们称为多目标最优化问题.其数学模型为：目标函数约束条件 上述模型中有个目标函数,个等式约束条件.例如：生产商如何使得产值最大而且消耗资源最少问题投资商如何使得投资收益最大而且风险最小问题等都是多目标最优化问题.2 经典最优化方法 经典最优化方法包括无约束条件极值问题和等式约束条件极值问题两种,不等式约束条件极值问题可以化为等式约束条件极值问题. 经典的极值理论：首先,根据可微函数取极值的必要条件确定可能极值点；其次,根据函数取极值的充分条件判断是否取极值？是极大值？还是极小值？这种方法已经几百年的历史了.21 无约束条件极

11、值 设元函数,求的极值和取得极值的点.这是一个无约束条件极值问题,经典的极值理论如下.定理1极值必要条件：设元函数具有偏导数,则在处取得极值的必要条件为：. 定理在此不给出证明,读者可自己参看有关资料.注1：对于一元函数上述定理当然成立,只是偏导数应为导数；注2：定理只是在偏导数存在的前提下的必要条件.如果函数在某一点偏导数不存在,那在这一点处仍然可能取得极值；注3：如果函数在某一点偏导数存在,且偏导数都等于零,那么函数在这一点处也不一定取得极值.例如,函数在点处偏导数不存在,但在这一点处函数仍然取得极小值零.函数在点处偏导数存在,且偏导数都等于零,但在这一点处函数不取极值.定理1的作用在于,

12、求出函数的可能极值点,然后,我们再研究这些点是否取得极值.对于许多实际问题来说,函数一定能够取得极大值或极小值,而函数的可能极值点满足必要条件的点又只有一点,则这一点当然是函数取得极大值或极小值的点.对于一般函数而言,我们怎样判定函数在某点是否取极值？是极大值？还是极小值？我们有下面的极值的充分条件定理.定理2极值充分条件：设元函数具有二阶偏导数,则在处取得极值的充分条件为：1；2黑塞矩阵在处正定或负定；3黑塞矩阵在处正定时,函数取极小值；负定时,函数取极大值. 本章内容简要讲解理论,注重实际应用,对于许多经典的定理都不进行证明,读者可自己参看有关资料.例1：求函数的极值.解：1根据极值存在的

13、必要条件,确定可能取得极值的点：,令,解得 .2根据极值存在的充分条件,确定是否是极值点：计算 ,；,；函数的黑塞矩阵为 因为 ,；所以黑塞矩阵负定,故函数在处取得极大值.22 等式约束条件极值下面我们研究的是有若干个等式约束条件下,一个目标函数的极值问题,其数学模型为：目标函数约束条件拉格朗日Lagrange乘数法：1令 称为上述问题的拉格朗日乘数函数,称为拉格朗日乘数.2设和均可微,则得到方程组3若是上述方程组的解,则点可能为该问题的最优点. 拉格朗日Lagrange乘数法的本质是：将求有约束条件极值问题转化为求无条件极值问题；所求得的点,即是取得极值的必要条件点. 拉格朗日乘数法没有解决

14、极值的存在性问题,但是,如果拉格朗日乘数函数具有二阶连续偏导数,我们也可以应用黑塞矩阵来判定函数是否取得极值.在具体问题中,点是否为最优点通常可由问题的实际意义决定.例2：求表面积为定值,而体积为最大的长方体的体积.解：设长方体的三棱长为,体积为；建立数学模型如下： 构造拉格朗日乘数函数,则有解得 , 为所求.23 不等式约束条件极值 对于不等式约束条件极值问题：目标函数约束条件我们有与拉格朗日乘数法密切相关的方法库恩图克定理.定理3库恩图克定理：对于上述不等式约束条件极值问题,设和均可微,令假设存在,则在最优点处,必满足下述条件：1；2；3；4. 根据库恩图克定理我们可以求解许多不等式约束条

15、件极值问题,值得注意的是应用库恩图克定理求解不等式约束条件极值问题,定理并没有解决最优解的存在性问题,因此,我们必须另行判断.例3：求解最优化问题最优解存在解：构造函数,根据库恩图克定理则有解得： ；所求最优解为,最优值为.3 线性规划31 线性规划设线性规划标准数学模型为：目标函数约束条件矩阵形式： 目标函数约束条件其中 ,线性规划问题的求解有一整套理论体系,一般来说,应用单纯形法求解.此方法尽管比较复杂,然而在计算机上实现并不困难.解线性规划问题的单纯形法已在许多数学计算软件中实现,我们求解线性规划问题可根据需要,应用数学计算软件求解即可.在此,我们不系统研究其理论,只是简单介绍线性规划的

16、穷举法和单纯形法的基本思想.3.2 线性规划的穷举法1穷举法基本原理和步骤步骤1：将线性规划问题化成矩阵的标准形式,设系数矩阵的秩,则对应线性方程组的基础解系自由变量的个数为个.步骤2：穷举法求解：令,解得对应线性方程组一组解为；对应目标函数值为. 从个变量中选个作为自由变量,令它们的值为0,可得到组解.步骤3：确定最优解：如果最优解存在,则上述求解得到的对应个目标函数值中,最小者或最大者即为所求最小或最大最优值,对应的解为最优解.步骤4：证明解为最优解：将最优解对应的自由变量看成参数；解对应线性方程组得 .将对应线性方程组解代入目标函数得：. 如果,则所求为最小值最优解；否则,线性规划问题无

17、最小值最优解. 如果,则所求为最大值最优解；否则,线性规划问题无最大值最优解.例1：目标函数：解：约束条件的增广矩阵为：,；令,解得；令,无解；令,解得,不满足非负条件,舍去；令,解得；令,解得；令,解得,不满足非负条件,舍去；令,无解；令,解得；令,解得,不满足非负条件,舍去；令,解得；所以,最优解为.证明：令解得 目标函数；因为非负,所以,故最优解存在.2单纯形法基本原理和步骤将线性规划问题化成矩阵的标准形式,设系数矩阵的秩,则对应线性方程组的基础解系的个数为个,即有个自由参数变量.选取个非基变量自由参数变量,不妨假设为；解得线性规划问题的典式定理1：如果线性规划问题的上述典式中所有；则为

18、最优解.定理2：如果线性规划问题的上述典式中存在某个,且对应；则线性规划问题无最优解.由定理1和定理2知,如果我们选择适当的个非基变量,就可以根据所求得的典式判断最优解的存在与否,从而求解该线性规划问题.单纯形法的思想是：选择适当的基变换进基和退基,不断地变换典式,使得典式中目标函数值不断下降,从而求得最优解.其核心为如何选择进基和退基.进基规则和退基规则进基规则正检验数最小下标规则,即选取,由此确定为进基.退基规则：选取这样的下标表示第个基变量的下标 由此确定离基.单纯形法的基本步骤：步骤1：化线性规划问题为标准形式.步骤2：确定基变量,求得基本可行解和典式；是否满足最优解定理或最优解不存在

19、定理的条件？判断最优解的情况.步骤3：根据进基规则和退基规则,选择进基和退基,进行基变换,求得对应典式.重复进行基变换,直到求出最优解或判断出无最优解为止.例2：解线性规划问题解：1约束条件的增广矩阵为：,；所以非基变量个数为两个.2选取作为非基变量,作为基变量,解得典式为不满足最优解定理和最优解不存在定理的条件,故必须进行基变换.3进行基变换选取进基： ,根据得为进基.选取退基：,根据,得为离基.进行基变换,求新基的典式：判断：不满足最优解定理和最优解不存在定理的条件,故继续进行基变换.4继续进行基变换选取进基： ,根据得为进基.选取退基：,根据,得为离基.进行基变换,求新基的典式：满足最优

20、解定理的条件,根据定理最优解为.32 整数规划设纯整数线性规划数学模型为：目标函数约束条件 这一类问题与一般线性规划比较起来,似乎是变简单了,但实际上恰恰相反,由于解集是一些离散的整数点集,使得单纯形法失去了应用的基础,求解变得困难而复杂.整数线性规划目前还缺乏统一的解法,这里只介绍分枝定界法,它是目前求解纯整数线性规划和混合整数线性规划最常用的方法,计算机求解整数线性规划的大多数程序也是以它为基础的.分枝定界法：考虑上述纯整数线性规划问题,1解对应线性规划问题目标函数约束条件若无最优解,则原纯整数线性规划问题无最优解；若有最优解,最优点,目标函数最优值.若最优点全为整数,则为原纯整数线性规划

21、问题的最优解；若最优点不全为整数,则进行下一步.2定界和分枝定界：其中取原纯整数线性规划问题中,满足约束条件的某一整数可行解所对应的目标函数值.原纯整数线性规划问题的最优解必须满足定界条件.分枝：选取中一个不为整数所对应的分枝,和称为对应线性规划问题的两枝,也是两个新线性规划问题的约束条件.显然,原纯整数线性规划问题的最优解满足或.3对和进行剪枝和分枝解对应的线性规划问题,对其进行剪枝和分枝：若无最优解,则原纯整数线性规划问题在内无最优解.不需要对该区域继续讨论剪枝.若有最优解,最优点,目标函数的最优值.若,则原纯整数线性规划问题在内无最优解.不需要对该区域继续讨论剪枝.若最优点全为整数,则可

22、能为原纯整数线性规划问题的最优解,定界：记,则,本分枝求解结束.若最优点不全为整数,对继续进行分枝.完全类似,解对应线性规划问题,对其进行剪枝和分枝.依此类推,对所有分枝进行求解,剪枝,分枝,定界；直至求得最优解.4最优解的确定若某,则为最优解,求解结束.若所有分枝求解结束,则最后的上界即为最优解.例3：应用分枝定界法,求解整数线性规划问题解：设原整数线性规划问题目标函数的最优值为,1求解线性规划问题：得最优解为 ；.记约束区域为.2对进行分枝：选取最优解中不是整数的变量,例如,将分成两个子区域.,3定界：确定最优值的上下界.由1中求得的最优值知；而的上界可由内的任意一个可行解确定,例如,即为

23、一个可行解.故.从而,.4在内求最优解,得 ；.5在内求最优解,得 ；.6因为内最优解不全是整数,因而必须继续对分枝：7显然内无解,剪枝.在内求最优解,得 ；为整数可行解.但因,而,故剪枝.8因为内最优解不全是整数,因而必须继续对分枝：9显然内无解,剪枝.在内求最优解,得 ；.10因为内最优解不全是整数,因而必须继续对分枝：11在内求最优解,得 ；.因大于的上界,故剪枝.12在内求最优解,得 ；.所求原整数规划问题的最优解为：；.4 最优化问题数值算法最优化问题的数值算法很多,常用的算法多为搜索法,本节只介绍搜索法的基本思想、无约束最优化问题的最速下降法梯度法和有约束最优化问题的罚函数法.41

24、 搜索算法考虑无约束最优化问题： 我们已经讨论了这类问题的最优解条件,这必须用到函数的解析性质.我们的方法是,先利用必要条件求出平稳点,再应用充分条件判断是否是极值点.但是,我们必须求解一个个变量个方程的方程组,并且常常是非线性的.这只有在特殊的情况下,才能求出它的精确解.在一般情况下,都不能用解析法求得精确解.更何况许多实际问题中,函数的解析表达式很难得到.因此,我们必须寻求一些切合实际问题的行之有效的数值解法.搜索算法就是我们常用的方法.1搜索算法的基本思想：假定目标函数极小值问题.首先,确定目标函数的初始点；然后,按照一定规则产生一个点列,这种规则称为算法；规则必须满足1点列收敛；2点列

25、收敛到目标函数的极小值点.2搜索算法的基本步骤：选定初始点越接近最优点越好,允许误差,令.假定已得非最优点,则选取一个搜索方向,满足： 目标函数下降,或.选定搜索步长,满足：.判断是否是最优点或是满足要求的近似解.假定给定精度要求为,常用确定求近似解搜索结束的方法有：梯度模确定法；目标函数差值绝对误差法；相邻搜索点绝对误差法.如果满足给定精度要求,则搜索完成,近似最优点为；如果不满足给定精度要求,令返回2继续搜索.注意1：我们的搜索算法一般得到的都是局部最优解.注意2：确定求近似解搜索结束的方法还有目标函数差值相对误差法；相邻搜索点相对误差法.3搜索算法的关键因素：从搜索算法的基本步骤中,我们

26、知道,搜索算法的关键因素为：一是搜索方向,二是搜索步长.搜索方向的选择,一般考虑既要使它尽可能的指向极小值点,又要不至于花费太多的计算量.搜索步长的选择,既要确保目标函数的下降性质,又要考虑近似解的精度要求,还要考虑算法的计算量,问题十分复杂.常用方法有,固定步长法,最优步长法和变步长法.固定步长法简单算法是选取为固定值.方法简单,但是有时不能保证目标函数的下降性质.最优步长法一维搜索算法是选取使得,这是一个关于单变量的函数求极小值问题,这样确定的步长称为最优步长.变步长法可接受点算法是任意选取,只要使得即可.这种选取步长的方法,确保了目标函数的下降性质,尽管每次选取的步长不是最优的,但实践证

27、明,方法能达到更好的数值效果.总之,当搜索方向确定以后,步长就是决定最优化算法好坏的重要因素,因此,我们必须特别注重步长的选取问题.4搜索算法的收敛性：搜索算法的收敛性是指,由某算法得到的点列能够在有限步骤内收敛到目标函数的最优点或能够在有限步骤内达到满足精度要求的目标函数的最优点的近似值.显然,只有具有收敛性质的算法才有意义.搜索算法的收敛速度：作为一个好的算法,还必须要求它以较快的速度收敛于最优解.阶收敛定义：对于收敛于最优解的序列,若存在与无关的数和,当从某个开始时,有 成立,则称序列收敛的阶为,或称阶收敛.当时,称迭代序列为线性收敛；当时,称迭代序列为超线性收敛；当时,称迭代序列为二阶

28、收敛.一般来说,线性收敛是比较慢的,而二阶收敛则是很快的,超线性收敛介于二者之间.如果一个算法具有超线性以上的收敛速度,我们就认为是一个好的算法了.42 无约束最优化问题的梯度法无约束最优化问题的计算方法很多.无约束最优化问题的计算方法分为两大类：一类是解析法,包括经典最优化方法,最速下降法梯度法,共轭梯度法,牛顿法和变尺度法等.另一类是直接法,包括坐标轮换法,步长加速法,方向加速法和单纯形法等. 所谓解析法就是在方法的计算过程中,应用到了函数的解析性质可导性质等；所谓直接法就是在方法的计算过程中,仅仅涉与目标函数值的计算,而不涉与函数导数等解析性质.我们在这里只介绍最速下降法梯度法. 最速下

29、降法理论根据：早在1847年,法国著名数学家Cauchy就曾提出,从任意给定点出发,函数沿哪个方向下降最快的问题.这个问题已从理论上解决了,即沿着函数在该点的负梯度方向前进时,函数下降最快.这就是最速下降法的理论根据. 最速下降法的搜索步骤：步骤1：选定初始点越接近最优点越好,允许误差,令.步骤2：假定已得非最优点,计算梯度,选取搜索方向 步骤3：选定搜索步长,满足：.步骤4：判断是否是最优点或是满足要求的近似解.根据精度要求,检验是否满足收敛性判断准则：或或如果满足给定精度要求,则搜索完成,近似最优点为；如果不满足给定精度要求,令返回2继续搜索.例1：应用最速下降法求解.解：1选定初始点,允

30、许误差,置收敛判断准则 .2计算梯度,选取搜索方向, 第一点搜索计算：,3选定搜索步长,满足： 第一点搜索计算：求最优步长解得.4判断是否是最优点或是满足要求的近似解.第一点搜索计算：验证收敛判断准则 ,不满足,继续搜索.依次类推,直到搜索到最优解或满足精度要求为止.搜索计算列表如下：搜索步长搜索方向 搜索点函数值为最优解43 罚函数法对于约束最优化问题也有许多种方法,本段只介绍把约束最优化问题转化为无约束最优化问题的一种求解方法罚函数法.分为等式约束最优化问题和不等式约束最优化问题两种情况讨论.1 等式约束最优化问题的罚函数法首先,考虑等式约束最优化问题假定上述等式约束最优化问题的最优解存在

31、.若记 ,构造辅助函数 罚函数其中罚因子是一个充分大的正数.定理1：若对于某确定数,无约束最优化问题的最优解,则必为原等式约束最优化问题的最优解.证明：设无约束最优化问题 的最优解,则有： 而当时,所以即为原等式约束最优化问题的最优解.定理2：设和均为连续函数,若对于任意正数,无约束最优化问题的最优解,且,则为原等式约束最优化问题的最优解.定理2的证明请参看有关参考资料. 根据定理1和定理2,我们就可以将通过构造罚函数的方法化为无约束最优化问题求解,这种方法称为罚函数法.罚函数法的步骤：等式约束最优化问题罚函数法步骤1：构造罚函数 , 选定,允许误差,令；步骤2：求无约束问题 的最优解；步骤3

32、：判断是否是最优点或是满足要求的近似解.根据精度要求,检验是否满足收敛性判断准则：或 如果满足收敛性判断准则,则,结束搜索；否则,令,取,返回2,继续搜索.下面我们通过一个简单的例子来说明等式约束最优化问题的罚函数法.例2：应用罚函数法求解非线性规划问题解：构造罚函数：求罚函数的最优解：应用解析法, 令上述两式等于零,解得 令得 为所求最优解.2 不等式约束最优化问题的罚函数法 对于,不等式约束最优化问题假定上述不等式约束最优化问题的最优解存在. 由于不等式约束条件等价于等式约束条件因而,上述不等式约束最优化问题可以转化为问题类似问题1构造罚函数则将上述等式约束最优化问题的求解转化为下面无约束

33、最优化问题的求解：定理3：若对于某确定数,无约束最优化问题的最优解,则必为原不等式约束最优化问题的最优解,其中.定理4：设1和均为连续函数； 2原不等式约束最优化问题的最优解存在； 3数列满足且； 4对任意,问题的最优解都存在,且有界； 5点列存在极限点；则：点列的极限点是原不等式约束最优化问题的最优解.罚函数法的步骤：不等式约束最优化问题罚函数法步骤1：构造罚函数 , 选定,允许误差,令；步骤2：求无约束问题 的最优解；步骤3：判断是否是最优点或是满足要求的近似解.根据精度要求,检验是否满足收敛性判断准则：或 如果满足收敛性判断准则,则,结束搜索；否则,令,取,返回2,继续搜索.例3：应用罚

34、函数法求解非线性规划问题解：构造罚函数 求的极小值点当时,显然上两式不能同时等于零,所以,此时不存在极小值点. 当时,有令上面两式等于零：,；解得的极小值点为当取不同值时,可得到相应的值,计算如下表1101001000-0.25-0.04545-0.004950-0.00049950-0.4375-0.1415-0.004975-0.00049980根据定理得,原问题的极小值点为,极小值为.5 多目标优化问题在许多实际的最优化问题中,常常遇到目标函数是几个的情况,这一类问题我们称之为多目标优化问题.例如,投资方向选择问题,我们不仅要求投资的收益最大,而且要求投资的风险最小.再例如,购买商品问题

35、,我们既要考虑商品的价格,又要考虑商品的质量,甚至还要考虑商品的性能等等. 所谓多目标优化问题是指：目标函数是两个或两个以上的最优化问题.其数学模型为：目标函数约束条件例1：求解多目标优化问题和解：易求时,.例2：求解多目标优化问题和解：显然,无最优解.51 多目标优化问题的解多目标优化问题解的存在性极其复杂,这是由多目标优化问题的目标函数多个性和目标函数相互之间的复杂性质决定的.由于目标函数在很多情况下不可能同时达到最大值或最小值,因而,多目标最优化问题很少有最优解,而实际问题又要求我们做出决择,求得一个比较好的解.什么样的解才是我们需要的解呢？对于同一个问题不同的要求导致不同的求解标准,从

36、而就会得到不同的求解结果.为此,我们给出多目标最优化问题的条件最优解概念.最优解：满足约束条件且使所有目标函数达到要求的最大值或最小值的点称为多目标优化问题的最优解.可行解：满足多目标优化问题的约束条件的点称为可行解.条件最优解：满足多目标优化问题的约束条件且满足根据需要设定条件的可行解称为条件最优解.对于一个多目标优化问题,即使最优解存在,要求解它也是十分困难的,特殊情况下,我们也只好用搜索法求解.更何况它常常还不存在最优解,因而我们必须寻求其求解条件最优解的方法.为了求得满足我们要求的解,常常不得不设定一些新的条件,从而求得条件最优解.设定新条件的方法是我们求解多目标优化问题的基本方法.下

37、面的单目标化方法、多重目标函数方法和目标关联函数方法都是针对目标函数设定新条件的方法.52 单目标化解法 将原多目标优化问题多个目标函数转化成为只有一个目标函数的单目标优化问题求解的方法称为单目标化方法.1单目标化解法的基本思想步骤1：构造一个新的目标函数 满足性质：在约束条件的区域内是的单调增函数.特别注意：构造新目标函数也可以根据实际问题,将定义为的不减函数.步骤2：建立单目标优化数学模型目标函数约束条件步骤3：求解上述单目标优化数学模型得到：单目标优化问题的最优解,从而可得到原多目标优化问题的最优解或条件最优解.2 单目标优化问题最优解的性质 单目标优化问题的最优解与原多目标最优化问题的

38、最优解有着密切的内在关系.下面的定理揭示了两者之间最重要的一种关系.定理1：设是的单调增函数,原多目标最优化问题的最优解存在,则单目标优化问题的最优解存在,且为原多目标最优化问题的最优解.证明：显然,单目标优化问题的最优解存在.设原多目标最优化问题的最优解为,则在该点处,目标函数都取得最小值.设单目标最优化问题的最优解为,则在该点处,目标函数取得最小值.显然,1 2 又因为,是的单调增函数,根据1有：所以, ,故必有 即为原多目标最优化问题的最优解.定理告诉我们：如果多目标最优化问题的最优解存在,则只需求解一个单目标最优化问题就可以得到.但是,如果多目标最优化问题的最优解不存在呢？则单目标最优

39、化问题的最优解可能存在,也可能不存在.当原多目标最优化问题的最优解不存在,而单目标最优化问题的最优解存在时,我们称解为单目标条件最优解.这种解在一定程度上反应了原多目标最优化问题的性质,因此,在实践中常常被选用.3 单目标化的常用目标函数当多目标最优化问题的最优解不存在时,应用单目标化求解方法寻求条件最优解,构造目标函数是关键.新的目标函数反应了原多目标之间的复杂关系,因而,必须根据实际问题构造目标函数,以比较准确地反应实际问题的性质.下面是几种常用的目标函数.均衡优化函数 权重优化函数 其中为大于零的权重系数平方和优化函数 平方和均衡优化函数 其中为大于零的权重系数例2：求解多目标优化问题和

40、解：问题涉与两个目标函数,可应用单目标化方法求解.1构造单目标函数 2求解模型 得最优解为,此时.3易知原问题最优解存在可通过作图验证,所以最优解为,此时 ,.53 多重优化解法 根据实际问题的性质,将原多目标优化问题转化成为多重单目标优化问题的方法称为多重优化法.1多重优化方法的基本思想根据多目标优化问题目标函数的性质,确定目标函数优化对象和优化次序.建立多重优化数学模型第一重优化： 其中为中的某一函数 求解得解集为第二重优化： 其中为中的某一函数求解得解集为依次类推,进行重优化第重优化： 其中为中的某一函数求解得解集为,即为多重优化问题的最优解集.原多目标优化问题的最优解集或条件最优解集为

41、.值得特别注意的是,我们不一定对所有目标函数进行多重优化,也可以根据需要只选取某几个目标函数进行多重优化,甚至只选取某一个目标函数进行优化.2多重优化问题最优解的性质啥地方放水电费v松岛枫松岛枫松岛枫松岛枫第三方第三方第三方的生产V型二万 多重优化问题的最优解与原多目标最优化问题的最优解也有着密切的内在关系.下面的定理揭示了两者之间的相互关系.定理2：设原多目标最优化问题的最优解存在,则多重优化问题第一重优化： 其中为中的某一函数 解集为第二重优化： 其中为中的某一函数解集为依次类推第重优化： 其中为中的某一函数 解集为的最优解必存在,且为原多目标最优化问题的最优解.定理的证明留给读者自己练习

42、.例3：求解多目标优化问题和解：问题涉与两个目标函数,可应用多重优化方法求解.1求解第一重优化：的解集为,此时2求解第二重优化：得解为,此时.3易知原问题最优解存在可以通过作图验证,所以最优解为,此时,.54 目标关联函数方法 在多目标最优化问题数学模型中,如果我们只是选定某一个目标函数称为主目标做为目标,而固定其余目标函数称为次目标在允许取值范围内为常数,则得到下列单目标优化数学模型： 其中为中的某一函数,其中为的某排列如果上述问题有解,则与其余目标函数的取值有关.目标关联函数方法的基本思想就是：固定某些目标函数的取值,求关于另一部分目标函数的最优解的方法. 为了讨论方便,我们以双目标优化问

43、题为例来说明目标关联函数方法的基本思想.双目标优化数学模型：1目标关联函数定义目标关联函数定义：选取目标函数作为主目标,作为次目标,固定,则得到单目标优化数学模型：记最优值为,则为的函数,即,称此函数为第一个目标关于第二个目标的目标关联函数.也称为主目标关于次目标的目标关联函数.类似地,我们可以定义第二个目标关于第一个目标的目标关联函数.2目标关联函数的求解对不同的值,解数学模型：得到目标关联函数,为第一目标关于第二目标的关联函数.注：关于的取值范围,在可行解集上3目标关联函数的性质性质1：设第一目标关于第二目标的关联函数为,如果原双目标优化问题最优解存在,则必在所对应的点取得.性质2：如果目

44、标关联函数在处不取得最小值,则原双目标优化问题不存在最优解.性质3：对于固定的值,目标关联函数所对应取值点为原双目标优化问题在固定第二目标的条件下的条件最优解. 上述三条性质比较简单,证明都不难,读者自己练习完成.4优劣解的概念目标关联函数还具有许多很好的性质,譬如单调函数的性质等等.当原双目标优化问题不存在最优解时,应用目标关联函数选取条件最优解最有效.为了对条件最优解有更深入的了解,下面我们引入优劣解的概念.优劣解的概念：设和为可行解,如果满足下列条件之一1,；2,；3,；则称是比优的解.性质4：任意可行解,要么对应目标关联函数一取值点对应的可行解；要么总存在某目标关联函数一取值点的可行解

45、优于该可行解.证明：以双目标最优化问题为例证明. 设为任意一可行解,记,目标函数关于目标函数的目标关联函数为； 根据目标关联函数的定义 . 设目标关联函数在点处对应的可行解为,则,所以,要么是比劣的解,要么对应目标关联函数一取值点对应的可行解. 根据性质4,我们求双目标优化问题的最优解或条件最优解,只需要求出它的两个目标关联函数,再根据目标关联函数求解即可.5 条件最优解的确定 一般来说,如果多目标优化问题存在最优解,我们就没有必要应用目标关联函数法求解,只需要应用单目标优化法或多重目标优化法.如果多目标优化问题不存在最优解,那末我们就可以应用目标关联函数法求其条件最优解.为什么要求条件最优解

46、呢？这是因为多目标优化问题现实生活中大量存在,需要解决,而它们往往又都不存在最优解,因而寻求在一定条件下的最优解.例如,企业如何确定生产方案,使得资源消耗最少,而效益最大问题、投资公司如何确定投资方案,使得风险最少,而效益最大问题、公交公司如何确定公交车运营方案,使得乘客满意度最大,而效益最好问题等等,都是多目标优化问题.显然,这些问题都没有最优解.因此,我们只能够寻求它们的条件最优解.由目标关联函数确定条件最优解的方法分为直接法和分析法.直接法：给定次目标函数的取值,直接求解关于主目标的对应单目标最优化问题,得到条件最优解.分析法：首先求出目标关联函数；然后通过分析目标关联函数的性质或图形,

47、选取条件最优解.55 投资风险问题某投资公司有一定数量的资金进行投资,现有投资方向可供选择.投资选择和资金分配的原则为：总体收益尽可能大,总体风险尽可能小.已知：投资收益率,其中为投资的收益,为投资资金；投资风险率,其中为投资的风险；定义投资总体风险.投资方向收 益 率0.20.30.30.40.60.6风 险 率0.30.30.40.50.50.6试建立投资风险问题的数学模型,并根据上列数据计算选择投资方向.投资效益与风险问题建模一、问题分析问题的性质本问题是一个投资关于效益与风险的双目标最优化决策问题.必须在总体收益尽可能大,总体风险尽可能小的原则下确定投资方向,即确定每个投资方向的投资资

48、金.二问题的主要因素 1每个投资方向的投资资金；2每个投资方向投资的收益率与收益； 3每个投资方向投资的风险率与风险； 4投资总收益； 5投资总体风险.关键因素为投资总收益与投资总体风险.三解决问题的难点 从本实际问题出发,投资的收益与风险是一对矛盾.一般来说,投资的收益越大,风险就会越大.因此,根本不存在投资的收益最大,同时风险又最小的投资方案.怎样协调收益与风险之间的矛盾？这是解决该问题的难点.四目标函数的确定 根据总体收益尽可能大,总体风险尽可能小的原则,建立数学模型时,我们的目标函数必须以总体收益和总体风险为基础. 1总体收益函数 2总体风险函数五数学建模的思路 1思路1建立双目标优化

49、模型以总体收益函数最大,总体风险函数最小为目标函数,建立双目标最优化模型.由于题目所给数据反应的收益最大和风险最小是矛盾的,因此,此模型无最优解.但模型反应了投资的追求,是建立其他模型的基础. 2思路2建立单目标优化模型 引入新的函数,从一定程度上反应收益最大和风险最小的目标,将此函数做为目标函数,建立单目标优化模型. 新的目标函数应该满足：收益越大,函数值越大；风险越小,函数值越大. 3思路3建立多重优化模型 对于投资者来说,有的重视的是收益,而将风险做为第二考虑；有的则重视的是风险,而将收益做为第二考虑.根据这种投资者的两种特点,我们可以分别建立两种模型.一是建立先优化收益,再优化风险的重

50、视收益二重优化模型；二是建立先优化风险,再优化收益的重视风险二重优化模型. 4思路4建立目标关联函数模型 对于有些投资者来说,选择投资方案的原则是：在固定总体风险的前提下,选择收益最大的投资方案.此时,最大收益实际上是总体风险的函数,求得该函数和该函数每一点处的投资方案,即为在固定总体风险的条件下,最佳的投资方案.同理,对于有些投资者来说,选择投资方案的原则如果是：在固定总体收益的前提下,选择风险最小的投资方案.此时,最小风险实际上是总体收益的函数,求得该函数和该函数每一点处的投资方案,即为在固定总体收益的条件下,最佳的投资方案.上述两函数揭示了收益和风险的内在关系,我们分别称为收益关于风险的

51、目标关联函数和风险关于收益的目标关联函数,统称为目标关联函数.二、模型建立一建模准备1总体收益函数和总体风险函数 总体收益函数总体风险函数2约束条件 设总投资资金为个单位,投资的投资资金为个单位, 则有：二双目标优化模型根据题意,我们以总体收益函数最大,总体风险函数最小为目标函数,建立双目标最优化模型.模型1双目标最优化模型：定理：对于题目所给数据,上述模型无最优解.证明：显然,投资方案的收益最大,；此时,投资风险也是最大,.所以,模型无最优解.由于模型无最优解,如何根据不同投资者的需要选择投资方案？成为解决问题的关键. 三单目标优化模型 为了满足不同投资者的需要,我们来建立一个调和收益和风险

52、矛盾的模型.为此,引入新的函数,反应收益最大和风险最小的目标,将此函数做为目标函数,建立单目标优化模型.1收益风险权重函数新的目标函数应该满足：收益越大,函数值越大；风险越小,函数值越大.我们定义一个常用的线性函数作为新的目标函数.定义1：收益风险权重函数其中为权重系数,它表示了投资者对收益和风险的重视程度.越大越重视收益,越小越重视风险.模型2线性优化模型：该模型可以根据投资者的不同类型,确定需要的投资方案.下面我们对投资者进行简单的分类.注重收益忽略风险型：只注重收益,不考虑风险,此时,.收益风险注重均衡型：均衡注重收益和风险,此时,.注重风险忽略收益型：只注重风险,不考虑收益.此时,.当

53、然,我们可以将投资者分成更多种类型,并确定权重系数,再求解模型,从而得到该类型投资者的最佳投资方案.四多重优化模型 1由问题分析中我们知道,有的投资者,首先重视的是收益,其次再是风险；还有些投资者则首先重视的是风险,而将收益做为第二考虑.根据投资者的两种特点,我们可以分别建立两种模型.一是建立先优化收益,再优化风险的重视收益二重优化模型；二是建立先优化风险,再优化收益的重视风险二重优化模型.2模型3收益第一风险第二模型：第一重优化设解集为第二重优化3模型4风险第一收益第二模型：设解集为第二重优化 上述二重优化模型,提供了两类投资者的最优投资方案.五目标关联函数模型 1根据投资选择方案的原则在固

54、定总体风险的前提下,选择收益最大的投资方案；建立收益关于风险的关联函数模型；求出该函数每一点处的最佳投资方案.模型5固定风险模型 其中2根据投资选择方案的原则在固定总体收益的前提下,选择风险最小的投资方案；建立风险关于收益的关联函数模型；求出该函数每一点处的最佳投资方案.模型6固定收益模型 其中模型5和模型6从理论上讲提供了任意类型投资者的最佳投资方案.三、模型求解和结果一模型1无最优解.二模型2是线性规划模型,应用数学计算软件求解得：目标函数值10三模型3：模型为线性规划模型,可以直接求解.第一重优化结果,其中.第二重优化结果.四模型4：模型为线性规划模型,可以直接求解.第一重优化结果,其中

55、.第二重优化结果.五模型5：模型为线性规划模型,可以直接求解或应用数学计算软件求解.对于分别求解得收益关于风险的目标关联函数固定风险的条件下,相应的最佳相应的投资方案为六模型6：模型为线性规划模型对于分别求解得风险关于收益的目标关联函数固定收益的条件下,相应的最佳投资方案为练习题1求函数的极值.2将拆成若干个正整数的和,使得它们的乘积最大.3证明周长一定的平面曲线围成面积最大的是圆周曲线.4用穷举法求解5应用单纯形法求解线性规划问题6应用分枝定界法,求解整数线性规划问题.7投资风险问题某投资公司有一定数量的资金进行投资,现有投资方向可供选择.投资选择和资金分配的原则为：总体收益尽可能大,总体风险尽可能小.已知：投资收益率,其中为投资的收益,为投资资金；投资风险率,其中为投资的风险；定义投资总体风险.投资方向收 益 率0.20.30.30.40.40.50.60.6风 险 率0.30.30.40.40.50.50.50.6试建立投资风险问题的数学模型,并根据上列数据计算选择投资方向.8在上题中将投资总体风险定义为,试建立投资风险问题的数学模型,并根据上题数据计算选择投资方向.参考资料1. 运筹学基础 何坚勇 编著 清华大学 20#7月2. 数学规划的原理何方法 俞玉森 主编 华中理工大学 1993年10月3. 最优化与最优化控制 蔡宣三 编著 清华大学 1983年1月34 / 34