多目标最优化模型

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：若约束条件为，引入松驰变量原约束条件变为 在其它最优化问题中，我们也常常采取上述方法化不等式约束条件为等式约束条件。实际问题中，我们经常遇到两类特殊的线性规划问题

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

10、，简称为最优化问题。 多目标最优化问题数学模型由某实际问题设立变量，建立两个或多个目标函数和若干个约束条件，且目标函数或约束条件是变量的函数，这样的求函数最大值最小值问题，我们称为多目标最优化问题。其数学模型为： 目标函数 约束条件 上述模型中有个目标函数，个等式约束条件。例如：“生产商如何使得产值最大而且消耗资源最少问题”“投资商如何使得投资收益最大而且风险最小问题”等都是多目标最优化问题。2 经典最优化方法 经典最优化方法包括无约束条件极值问题和等式约束条件极值问题两种，不等式约束条件极值问题可以化为等式约束条件极值问题。 经典的极值理论：首先，根据可微函数取极值的必要条件确定可能极值点；

11、其次，根据函数取极值的充分条件判断是否取极值？是极大值？还是极小值？这种方法已经几百年的历史了。21 无约束条件极值 设元函数，求的极值和取得极值的点。这是一个无约束条件极值问题，经典的极值理论如下。定理1（极值必要条件）：设元函数具有偏导数，则在处取得极值的必要条件为： 。 定理在此不给出证明，读者可自己参看有关资料。注1：对于一元函数上述定理当然成立，只是偏导数应为导数；注2：定理只是在偏导数存在的前提下的必要条件。如果函数在某一点偏导数不存在，那在这一点处仍然可能取得极值；注3：如果函数在某一点偏导数存在，且偏导数都等于零，那么函数在这一点处也不一定取得极值。例如，函数在点处偏导数不存在

12、，但在这一点处函数仍然取得极小值零。函数在点处偏导数存在，且偏导数都等于零，但在这一点处函数不取极值。定理1的作用在于，求出函数的可能极值点，然后，我们再研究这些点是否取得极值。对于许多实际问题来说，函数一定能够取得极大值或极小值，而函数的可能极值点（满足必要条件的点）又只有一点，则这一点当然是函数取得极大值或极小值的点。对于一般函数而言，我们怎样判定函数在某点是否取极值？是极大值？还是极小值？我们有下面的极值的充分条件定理。定理2（极值充分条件）：设元函数具有二阶偏导数，则在处取得极值的充分条件为： （1）； （2）黑塞矩阵在处正定或负定；（3）黑塞矩阵在处正定时，函数取极小值；负定时，函数

13、取极大值。 本章内容简要讲解理论，注重实际应用，对于许多经典的定理都不进行证明，读者可自己参看有关资料。例1：求函数的极值。解：（1）根据极值存在的必要条件，确定可能取得极值的点： ，令，解得 。（2) 根据极值存在的充分条件，确定是否是极值点：计算 ，； ，；函数的黑塞矩阵为 因为 ，；所以黑塞矩阵负定，故函数在处取得极大值。22 等式约束条件极值下面我们研究的是有若干个等式约束条件下，一个目标函数的极值问题，其数学模型为： 目标函数 约束条件拉格朗日（Lagrange)乘数法：（1）令 称为上述问题的拉格朗日乘数函数，称为拉格朗日乘数。（2）设和均可微，则得到方程组（3）若是上述方程组的解

14、，则点可能为该问题的最优点。 拉格朗日（Lagrange)乘数法的本质是：将求有约束条件极值问题转化为求无条件极值问题；所求得的点，即是取得极值的必要条件点。 拉格朗日乘数法没有解决极值的存在性问题，但是，如果拉格朗日乘数函数具有二阶连续偏导数，我们也可以应用黑塞矩阵来判定函数是否取得极值。在具体问题中，点是否为最优点通常可由问题的实际意义决定。例2：求表面积为定值，而体积为最大的长方体的体积。解：设长方体的三棱长为，体积为；建立数学模型如下： 构造拉格朗日乘数函数，则有解得 ， 为所求。23 不等式约束条件极值 对于不等式约束条件极值问题： 目标函数 约束条件我们有与拉格朗日乘数法密切相关的

15、方法库恩图克定理。定理3（库恩图克定理）：对于上述不等式约束条件极值问题，设和均可微，令 假设存在，则在最优点处，必满足下述条件：（1）；（2）；（3）；（4）。 根据库恩图克定理我们可以求解许多不等式约束条件极值问题，值得注意的是应用库恩图克定理求解不等式约束条件极值问题，定理并没有解决最优解的存在性问题，因此，我们必须另行判断。例3：求解最优化问题（最优解存在） 解：构造函数 ，根据库恩图克定理则有 解得： ；所求最优解为，最优值为。3 线性规划31 线性规划设线性规划标准数学模型为： 目标函数 约束条件矩阵形式： 目标函数 约束条件其中 ，线性规划问题的求解有一整套理论体系，一般来说，应

16、用单纯形法求解。此方法尽管比较复杂，然而在计算机上实现并不困难。解线性规划问题的单纯形法已在许多数学计算软件中实现，我们求解线性规划问题可根据需要，应用数学计算软件求解即可。在此，我们不系统研究其理论，只是简单介绍线性规划的穷举法和单纯形法的基本思想。3.2 线性规划的穷举法 （1）穷举法基本原理和步骤步骤1：将线性规划问题化成矩阵的标准形式，设系数矩阵的秩，则对应线性方程组的基础解系自由变量的个数为个。步骤2：穷举法求解：令，解得对应线性方程组一组解为 ；对应目标函数值为。 从个变量中选个作为自由变量，令它们的值为0，可得到组解。步骤3：确定最优解：如果最优解存在，则上述求解得到的对应个目标

17、函数值中，最小者（或最大者）即为所求最小（或最大）最优值，对应的解为最优解。步骤4：证明解为最优解：将最优解对应的自由变量看成参数；解对应线性方程组得 。将对应线性方程组解代入目标函数得：。 如果，则所求为最小值最优解；否则，线性规划问题无最小值最优解。 如果，则所求为最大值最优解；否则，线性规划问题无最大值最优解。 例1：目标函数：解：约束条件的增广矩阵为： ，；令，解得；令，无解；令，解得，不满足非负条件，舍去；令，解得；令，解得；令，解得，不满足非负条件，舍去；令，无解；令，解得；令，解得，不满足非负条件，舍去；令，解得；所以，最优解为。证明：令解得 目标函数；因为非负，所以，故最优解存

18、在。（2）单纯形法基本原理和步骤将线性规划问题化成矩阵的标准形式，设系数矩阵的秩，则对应线性方程组的基础解系的个数为个，即有个自由参数变量。选取个非基变量（自由参数变量）,不妨假设为；解得线性规划问题的典式 定理1：如果线性规划问题的上述典式中所有；则为最优解。定理2：如果线性规划问题的上述典式中存在某个，且对应；则线性规划问题无最优解。由定理1和定理2知，如果我们选择适当的个非基变量，就可以根据所求得的典式判断最优解的存在与否，从而求解该线性规划问题。单纯形法的思想是：选择适当的基变换（进基和退基），不断地变换典式，使得典式中目标函数值不断下降，从而求得最优解。其核心为如何选择进基和退基。进

19、基规则和退基规则进基规则正检验数最小下标规则，即选取，由此确定为进基。退基规则：选取这样的下标（表示第个基变量的下标） 由此确定离基。单纯形法的基本步骤：步骤1：化线性规划问题为标准形式。步骤2：确定基变量，求得基本可行解和典式；是否满足最优解定理或最优解不存在定理的条件？判断最优解的情况。步骤3：根据进基规则和退基规则，选择进基和退基，进行基变换，求得对应典式。重复进行基变换，直到求出最优解或判断出无最优解为止。例2：解线性规划问题 解：（1）约束条件的增广矩阵为： ，；所以非基变量个数为两个。（2）选取作为非基变量，作为基变量，解得典式为 不满足最优解定理和最优解不存在定理的条件，故必须进

20、行基变换。（3）进行基变换选取进基： ，根据得为进基。选取退基：，根据，得为离基。进行基变换，求新基的典式： 判断：不满足最优解定理和最优解不存在定理的条件，故继续进行基变换。（4）继续进行基变换选取进基： ，根据得为进基。选取退基：，根据，得为离基。进行基变换，求新基的典式： 满足最优解定理的条件，根据定理最优解为 。32 整数规划设纯整数线性规划数学模型为： 目标函数 约束条件 这一类问题与一般线性规划比较起来，似乎是变简单了，但实际上恰恰相反，由于解集是一些离散的整数点集，使得单纯形法失去了应用的基础，求解变得困难而复杂。整数线性规划目前还缺乏统一的解法，这里只介绍分枝定界法，它是目前求

21、解纯整数线性规划和混合整数线性规划最常用的方法，计算机求解整数线性规划的大多数程序也是以它为基础的。分枝定界法：考虑上述纯整数线性规划问题，（1）解对应线性规划问题 目标函数 约束条件若无最优解，则原纯整数线性规划问题无最优解；若有最优解，最优点，目标函数最优值。若最优点全为整数，则为原纯整数线性规划问题的最优解；若最优点不全为整数，则进行下一步。（2）定界和分枝定界：其中取原纯整数线性规划问题中，满足约束条件的某一整数可行解所对应的目标函数值。原纯整数线性规划问题的最优解必须满足定界条件。分枝：选取中一个不为整数所对应的分枝， 和称为对应线性规划问题的两枝，也是两个新线性规划问题的约束条件。

22、显然，原纯整数线性规划问题的最优解满足或。（3）对和进行剪枝和分枝解对应的线性规划问题，对其进行剪枝和分枝：若无最优解，则原纯整数线性规划问题在内无最优解。不需要对该区域继续讨论剪枝。若有最优解，最优点，目标函数的最优值。若，则原纯整数线性规划问题在内无最优解。不需要对该区域继续讨论剪枝。若最优点全为整数，则可能为原纯整数线性规划问题的最优解，定界：记，则，本分枝求解结束。若最优点不全为整数，对继续进行分枝。完全类似，解对应线性规划问题，对其进行剪枝和分枝。依此类推，对所有分枝进行求解，剪枝，分枝，定界；直至求得最优解。（4）最优解的确定若某，则为最优解，求解结束。若所有分枝求解结束，则最后的

23、上界即为最优解。例3：应用分枝定界法，求解整数线性规划问题 解：设原整数线性规划问题目标函数的最优值为，（1）求解线性规划问题： 得最优解为 ；。记约束区域为。（2）对进行分枝：选取最优解中不是整数的变量，例如，将分成两个子区域。， （3）定界：确定最优值的上下界。由（1）中求得的最优值知；而的上界可由内的任意一个可行解确定，例如，即为一个可行解。故。从而，。（4）在内求最优解，得 ；。（5）在内求最优解，得 ；。（6）因为内最优解不全是整数，因而必须继续对分枝： （7）显然内无解，剪枝。在内求最优解，得 ；为整数可行解。但因，而，故剪枝。（8）因为内最优解不全是整数，因而必须继续对分枝： （

24、9）显然内无解，剪枝。在内求最优解，得 ；。（10）因为内最优解不全是整数，因而必须继续对分枝： （11）在内求最优解，得 ；。因大于的上界，故剪枝。（12）在内求最优解，得 ；。所求原整数规划问题的最优解为：；。4 最优化问题数值算法 最优化问题的数值算法很多，常用的算法多为搜索法，本节只介绍搜索法的基本思想、无约束最优化问题的最速下降法（梯度法）和有约束最优化问题的罚函数法。41 搜索算法考虑无约束最优化问题： 我们已经讨论了这类问题的最优解条件，这必须用到函数的解析性质。我们的方法是，先利用必要条件求出平稳点，再应用充分条件判断是否是极值点。但是，我们必须求解一个个变量个方程的方程组，并

25、且常常是非线性的。这只有在特殊的情况下，才能求出它的精确解。在一般情况下，都不能用解析法求得精确解。更何况许多实际问题中，函数的解析表达式很难得到。因此，我们必须寻求一些切合实际问题的行之有效的数值解法。搜索算法就是我们常用的方法。（1）搜索算法的基本思想：假定目标函数极小值问题。首先，确定目标函数的初始点；然后，按照一定规则产生一个点列，这种规则称为算法；规则必须满足（1）点列收敛；（2）点列收敛到目标函数的极小值点。（2）搜索算法的基本步骤：选定初始点（越接近最优点越好），允许误差，令。假定已得非最优点，则选取一个搜索方向，满足： 目标函数下降，或。选定搜索步长，满足：。判断是否是最优点或

26、是满足要求的近似解。假定给定精度要求为，常用确定求近似解搜索结束的方法有： 梯度模确定法； 目标函数差值绝对误差法； 相邻搜索点绝对误差法。如果满足给定精度要求，则搜索完成，近似最优点为；如果不满足给定精度要求，令返回（2）继续搜索。注意1：我们的搜索算法一般得到的都是局部最优解。注意2：确定求近似解搜索结束的方法还有 目标函数差值相对误差法； 相邻搜索点相对误差法。（3）搜索算法的关键因素：从搜索算法的基本步骤中，我们知道，搜索算法的关键因素为：一是搜索方向，二是搜索步长。搜索方向的选择，一般考虑既要使它尽可能的指向极小值点，又要不至于花费太多的计算量。搜索步长的选择，既要确保目标函数的下降

27、性质，又要考虑近似解的精度要求，还要考虑算法的计算量，问题十分复杂。常用方法有，固定步长法，最优步长法和变步长法。固定步长法（简单算法）是选取为固定值。方法简单，但是有时不能保证目标函数的下降性质。最优步长法（一维搜索算法）是选取使得， 这是一个关于单变量的函数求极小值问题，这样确定的步长称为最优步长。变步长法（可接受点算法）是任意选取，只要使得即可。这种选取步长的方法，确保了目标函数的下降性质，尽管每次选取的步长不是最优的，但实践证明，方法能达到更好的数值效果。总之，当搜索方向确定以后，步长就是决定最优化算法好坏的重要因素，因此，我们必须特别注重步长的选取问题。（4）搜索算法的收敛性：搜索算

28、法的收敛性是指，由某算法得到的点列能够在有限步骤内收敛到目标函数的最优点或能够在有限步骤内达到满足精度要求的目标函数的最优点的近似值。显然，只有具有收敛性质的算法才有意义。搜索算法的收敛速度：作为一个好的算法，还必须要求它以较快的速度收敛于最优解。阶收敛定义：对于收敛于最优解的序列，若存在与无关的数和，当从某个开始时，有 成立，则称序列收敛的阶为，或称阶收敛。当时，称迭代序列为线性收敛；当时，称迭代序列为超线性收敛；当时，称迭代序列为二阶收敛。一般来说，线性收敛是比较慢的，而二阶收敛则是很快的，超线性收敛介于二者之间。如果一个算法具有超线性以上的收敛速度，我们就认为是一个好的算法了。42 无约

29、束最优化问题的梯度法无约束最优化问题 的计算方法很多。无约束最优化问题的计算方法分为两大类：一类是解析法，包括经典最优化方法，最速下降法（梯度法），共轭梯度法，牛顿法和变尺度法等。另一类是直接法，包括坐标轮换法，步长加速法，方向加速法和单纯形法等。 所谓解析法就是在方法的计算过程中，应用到了函数的解析性质（可导性质等）；所谓直接法就是在方法的计算过程中，仅仅涉及目标函数值的计算，而不涉及函数导数等解析性质。我们在这里只介绍最速下降法（梯度法）。 最速下降法理论根据：早在1847年，法国著名数学家Cauchy就曾提出，从任意给定点出发，函数沿哪个方向下降最快的问题。这个问题已从理论上解决了，即沿

30、着函数在该点的负梯度方向前进时，函数下降最快。这就是最速下降法的理论根据。 最速下降法的搜索步骤：步骤1：选定初始点（越接近最优点越好），允许误差，令。步骤2：假定已得非最优点，计算梯度，选取搜索方向 步骤3：选定搜索步长，满足：。步骤4：判断是否是最优点或是满足要求的近似解。根据精度要求，检验是否满足收敛性判断准则：或或 如果满足给定精度要求，则搜索完成，近似最优点为；如果不满足给定精度要求，令返回（2）继续搜索。例1：应用最速下降法求解。解：（1）选定初始点，允许误差，置收敛判断准则 。（2）计算梯度，选取搜索方向 ， 第一点搜索计算：，（3）选定搜索步长，满足： 第一点搜索计算：求最优步

31、长解得。（4）判断是否是最优点或是满足要求的近似解。第一点搜索计算：验证收敛判断准则 ，不满足，继续搜索。依次类推，直到搜索到最优解或满足精度要求为止。搜索计算列表如下：搜索步长搜索方向 搜索点函数值为最优解43 罚函数法对于约束最优化问题也有许多种方法，本段只介绍把约束最优化问题转化为无约束最优化问题的一种求解方法罚函数法。分为等式约束最优化问题和不等式约束最优化问题两种情况讨论。（1） 等式约束最优化问题的罚函数法首先，考虑等式约束最优化问题 假定上述等式约束最优化问题的最优解存在。若记 ，构造辅助函数 罚函数其中（罚因子）是一个充分大的正数。定理1：若对于某确定数，无约束最优化问题 的最

32、优解，则必为原等式约束最优化问题的最优解。证明：设无约束最优化问题 的最优解，则有： 而当时，所以即为原等式约束最优化问题的最优解。定理2：设和均为连续函数，若对于任意正数，无约束最优化问题 的最优解，且，则为原等式约束最优化问题的最优解。定理2的证明请参看有关参考资料。 根据定理1和定理2，我们就可以将通过构造罚函数的方法化为无约束最优化问题求解，这种方法称为罚函数法。罚函数法的步骤：（等式约束最优化问题罚函数法）步骤1：构造罚函数 ， 选定，允许误差，令；步骤2：求无约束问题 的最优解；步骤3：判断是否是最优点或是满足要求的近似解。根据精度要求，检验是否满足收敛性判断准则： 或 如果满足收

33、敛性判断准则，则，结束搜索；否则，令，取，返回（2），继续搜索。下面我们通过一个简单的例子来说明等式约束最优化问题的罚函数法。例2：应用罚函数法求解非线性规划问题 解：构造罚函数：求罚函数的最优解：应用解析法， 令上述两式等于零，解得 令得 为所求最优解。（2） 不等式约束最优化问题的罚函数法 对于，不等式约束最优化问题 假定上述不等式约束最优化问题的最优解存在。 由于不等式约束条件等价于等式约束条件因而，上述不等式约束最优化问题可以转化为问题 类似问题（1）构造罚函数 则将上述等式约束最优化问题的求解转化为下面无约束最优化问题的求解： 定理3：若对于某确定数，无约束最优化问题 的最优解，则必

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

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

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

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

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

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

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

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

42、多目标优化问题的最优解集或条件最优解集为。值得特别注意的是，我们不一定对所有目标函数进行多重优化，也可以根据需要只选取某几个目标函数进行多重优化，甚至只选取某一个目标函数进行优化。（2）多重优化问题最优解的性质 多重优化问题的最优解与原多目标最优化问题的最优解也有着密切的内在关系。下面的定理揭示了两者之间的相互关系。定理2：设原多目标最优化问题的最优解存在，则多重优化问题第一重优化： 其中为中的某一函数 解集为第二重优化： 其中为中的某一函数 解集为依次类推第重优化： 其中为中的某一函数 解集为的最优解必存在，且为原多目标最优化问题的最优解。定理的证明留给读者自己练习。例3：求解多目标优化问题

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

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

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

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

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

48、目标关联函数；然后通过分析目标关联函数的性质或图形，选取条件最优解。55 投资风险问题某投资公司有一定数量的资金进行投资，现有投资方向可供选择。投资选择和资金分配的原则为：总体收益尽可能大，总体风险尽可能小。已知：投资收益率，其中为投资的收益，为投资资金；投资风险率，其中为投资的风险；定义投资总体风险。投资方向收 益 率0.20.30.30.40.60.6风 险 率0.30.30.40.50.50.6试建立投资风险问题的数学模型，并根据上列数据计算选择投资方向。 投资效益与风险问题建模一、问题分析（）问题的性质本问题是一个投资“关于效益与风险的双目标”最优化决策问题。必须在“总体收益尽可能大，总体风险尽可能小”的原则下确定投资方向，即确定每个投资方向的投资资金。（二）问题的主要因素 （1）每个投资方向的投资资金；（2）每个投资方向投资的收益率与收益； （3）每个投资方向投资的风险率与风险； （4）投资总收益； （5）投资总体风险。关键因素为投资总收益与投资总体风险。（三）解决问题的难点 从本实际问题出发，投资的收益与风险是一对矛盾。一般来说，投资的收益越大，风险就会越大。因此，根本不存在投资的收益最大，同时风险又最小的投资方案。怎样协调收益与