2022年多目标最优化模型 2.pdf

第六章最优化数学模型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）变量变量是指最优化问题中所涉及的与约束条件和目标函数有关的待确定的量。一般来说，它们都有一些限制条件（约束条件），与目标函数紧密关联。设问题中涉及的变量为nxxx,21；我们常常也用),(21nxxxX表示。（3）约束条件在最优化问题中， 求目标函数的极值时， 变量必须满足的限制称为约束条件 。例如，许多实际问题变量要求必须非负，这是一种限制；在研究电路优化设名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 34 页 - - - - - - - - - 计问题时，变量必须服从电路基本定律，这也是一种限制等等。在研究问题时，这些限制我们必须用数学表达式准确地描述它们。用数学语言描述约束条件一般来说有两种：等式约束条件miXgi,2, 1,0)(不等式约束条件riXhi,2, 1,0)(或riXhi,2, 1,0)(注：在最优化问题研究中，由于解的存在性十分复杂，一般来说，我们不考虑不等式约束条件0)(Xh或0)(Xh。这两种约束条件最优化问题最优解的存在性较复杂。（4）目标函数在最优化问题中，与变量有关的待求其极值（或最大值最小值）的函数称为目标函数。目标函数常用),()(21nxxxfXf表示。当目标函数为某问题的效益函数时，问题即为求极大值； 当目标函数为某问题的费用函数时，问题即为求极小值等等。求极大值和极小值问题实际上没有原则上的区别，因为求)(Xf的极小值，也就是要求)(Xf的极大值，两者的最优值在同一点取到。12 最优化问题分类最优化问题种类繁多，因而分类的方法也有许多。可以按变量的性质分类，按有无约束条件分类，按目标函数的个数分类等等。一般来说， 变量可以分为确定性变量，随机变量和系统变量等等，相对应的最优化问题分别称为：普通最优化问题，统计最优化问题和系统最优化问题。按有无约束条件分类：无约束最优化问题，有约束最优化问题。按目标函数的个数分类：单目标最优化问题，多目标最优化问题。按约束条件和目标函数是否是线性函数分类：线性最优化问题 （线性规划），非线性最优化问题（非线性规划） 。按约束条件和目标函数是否是时间的函数分类：静态最优化问题和动态最优化问题（动态规划）。按最优化问题求解方法分类：解析法（间接法）图克定理库恩极大值原理有约束古典变分法古典微分法无约束名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 34 页 - - - - - - - - - 数值算法（直接法）随机搜索法单纯形法方向加速法步长加速法坐标轮换法多维搜索法插值法黄金分割法斐波那西法一维搜索法数值算法（梯度法）复形法法法化有约束为无约束梯度投影法可行方向法有约束梯度法变尺度法共轭梯度法拟牛顿法最速下降法无约束梯度法SWIFTSUMT多目标优化方法目标关联函数法多重目标化方法单目标化方法网络优化方法13 最优化问题的求解步骤和数学模型（1）最优化问题的求解步骤最优化问题的求解涉及到应用数学，计算机科学以及各专业领域等等，是一个十分复杂的问题， 然而它却是需要我们重点关心的问题之一。怎样研究分析求解这类问题呢？其中最关键的是建立数学模型和求解数学模型。一般来说，应用最优化方法解决实际问题可分为四个步骤进行：步骤 1：建立模型提出最优化问题，变量是什么？约束条件有那些？目标函数是什么？建立最优化问题数学模型：确定变量，建立目标函数，列出约束条件建立模型 。步骤 2：确定求解方法分析模型，根据数学模型的性质，选择优化求解方法确定求解方法 。步骤 3：计算机求解编程序（或使用数学计算软件） ，应用计算机求最优解计算机求解 。步骤 4：结果分析对算法的可行性、收敛性、通用性、时效性、稳定性、灵敏性和误差等等作出评价 结果分析 。（2）最优化问题数学模型名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 34 页 - - - - - - - - - 最优化问题的求解与其数学模型的类型密切相关，因而我们有必要对最优化问题的数学模型有所掌握。一般来说，最优化问题的常见数学模型有以下几种：无约束最优化问题数学模型由某实际问题设立变量， 建立一个目标函数且无约束条件，这样的求函数极值或最大值最小值问题，我们称为无约束最优化问题 。其数学模型为：),(m i n21nxxxf目标函数例如：求一元函数)(xfy和二元函数),(yxfz的极值。又例如：求函数323121232221321242643),(xxxxxxxxxxxxf的极值和取得极值的点。有约束最优化问题数学模型由某实际问题设立变量， 建立一个目标函数和若干个约束条件（等式或不等式） ，这样的求函数极值或最大值最小值问题，我们称为有约束最优化问题 。其数学模型为：),(m i n21nxxxf目标函数mixxxgni,2, 10),(21约束条件有约束最优化问题的例子：求函数nxxxxxxf31321),(在约束条件条件nixxxxin,2, 1,0,200831下的最大值和取得最大值的点。线性规划问题数学模型由某实际问题设立变量，建立一个目标函数和若干个约束条件，目标函数和约束条件都是变量的线性函数，而且变量是非负的， 这样的求函数最大值最小值问题，我们称为线性最优化问题，简称为线性规划问题 。其标准数学模型为：nnnxcxcxcxxxf221121),(m i n目标函数0, 2, 12211iinimiixmibxaxaxa约束条件矩阵形式：XCXfT)(m i n目标函数0XBAX约束条件其中TnxxxX),(21，TncccC),(21，TmbbbB),(21在线性规划问题中，关于约束条件我们必须注意以下几个问题。注 1：非负约束条件),2,1(0nixi，一般来说这是实际问题要求的需要。如果约束条件为iidx，我们作变量替换0iiidxz；如果约束条件为名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 34 页 - - - - - - - - - iidx，我们作变量替换0iiixdz。注 2：在线性规划的标准数学模型中，约束条件为等式。如果约束条件不是等式， 我们引入松驰变量， 化不等式约束条件为等式约束条件。情况 1：若约束条件为inimiibxaxaxa2211，引入松驰变量原约束条件变为iinimiibzxaxaxa2211。情况 2：若约束条件为inimiibxaxaxa2211，引入松驰变量原约束条件变为iinimiibzxaxaxa2211在其它最优化问题中， 我们也常常采取上述方法化不等式约束条件为等式约束条件。实际问题中， 我们经常遇到两类特殊的线性规划问题。一类是：所求变量要求是非负整数， 称为整数规划问题 ；另一类是所求变量要求只取0或1，称为 0-1规划问题 。例如：整数规划问题且 为 整 数0,02 8 5342213.3.21212xxxxxts。又例如： 0-1 规划问题321523ma xxxxz10,6434422. .3213221321321或xxxxxxxxxxxxxts。非线性规划问题数学模型由某实际问题设立变量， 建立一个目标函数和若干个约束条件，如果目标函数或约束条件表达式中有变量的非线性函数，那么，这样的求函数最大值最小值问题，我们称为非线性规划最优化问题， 简称为 非线性规划问题 。 其数学模型为：),(m i n21nxxxf目标函数mixxxgni,2, 10),(21约束条件其中目标函数或约束条件中有变量的非线性函数。例如：非线性规划问题yxyxf2) 1(),(m i n0),(02),(21yyxgyxyxg。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 34 页 - - - - - - - - - 上述最优化问题中，目标函数是非线性函数，故称为非线性规划问题。前面介绍的四种最优化数学模型都只有一个目标函数，称为单目标最优化问题，简称为最优化问题。多目标最优化问题数学模型由某实际问题设立变量， 建立两个或多个目标函数和若干个约束条件，且目标函数或约束条件是变量的函数，这样的求函数最大值最小值问题，我们称为 多目标最优化问题 。其数学模型为：sixxxfni, 2, 1),(m i n21目标函数mixxxgni,2, 10),(21约束条件上述模型中有s个目标函数，m个等式约束条件。例如： “生产商如何使得产值最大而且消耗资源最少问题”“投资商如何使得投资收益最大而且风险最小问题”等都是多目标最优化问题。2 经典最优化方法经典最优化方法包括无约束条件极值问题和等式约束条件极值问题两种，不等式约束条件极值问题可以化为等式约束条件极值问题。经典的极值理论：首先，根据可微函数取极值的必要条件确定可能极值点；其次，根据函数取极值的充分条件判断是否取极值？是极大值？还是极小值？这种方法已经几百年的历史了。21 无约束条件极值设n元函数),()(21nxxxfXf，求)(Xf的极值和取得极值的点。这是一个无约束条件极值问题，经典的极值理论如下。定理 1 （极值必要条件）： 设n元函数),()(21nxxxfXf具有偏导数，则)(Xf在*XX处取得极值的必要条件为：nixfXXi,2, 10|*。定理在此不给出证明，读者可自己参看有关资料。注 1：对于一元函数上述定理当然成立，只是偏导数应为导数；注 2：定理只是在偏导数存在的前提下的必要条件。如果函数在某一点偏导数不存在，那在这一点处仍然可能取得极值；注 3：如果函数在某一点偏导数存在，且偏导数都等于零，那么函数在这一点处也不一定取得极值。例如，函数232),(yxyxf在点)0 ,0(处偏导数不存在，但在这一点处函数仍然取得极小值零。函数53),(yxyxf在点)0, 0(处偏导数存在，且偏导数都等于零，但在这一点处函数不取极值。定理 1 的作用在于， 求出函数的可能极值点，然后，我们再研究这些点是否取得极值。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 34 页 - - - - - - - - - 对于许多实际问题来说， 函数一定能够取得极大值或极小值，而函数的可能极值点（满足必要条件的点） 又只有一点， 则这一点当然是函数取得极大值或极小值的点。对于一般函数而言， 我们怎样判定函数在某点是否取极值？是极大值？还是极小值？我们有下面的极值的充分条件定理。定理 2（极值充分条件）：设n元函数),()(21nxxxfXf具有二阶偏导数，则)(Xf在*XX处取得极值的充分条件为：（1）nixfXXi,3,20|*；（2）黑塞矩阵2222122222212212212212nxnnnxfxxfxxfxxfxfxxfxxfxxfxf在*XX处正定或负定；（3）黑塞矩阵在*XX处正定时，函数取极小值； 负定时，函数取极大值。本章内容简要讲解理论， 注重实际应用，对于许多经典的定理都不进行证明，读者可自己参看有关资料。例 1：求函数322123222132122462),(xxxxxxxxxxf的极值。解： （1）根据极值存在的必要条件，确定可能取得极值的点：21124xxxf，31222212xxxxf，23328xxxf令0321xfxfxf，解得)0 ,0 ,0(),(321xxx。（2) 根据极值存在的充分条件，确定)0,0 ,0(),(321xxx是否是极值点：计算4212xf，12222xf，8232xf；2212xxf，0312xxf，2322xxf；名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 34 页 - - - - - - - - - 函数的黑塞矩阵为8202122024)0,0 ,0(2f因为04，04412224，03208202122024；所以黑塞矩阵负定，故函数在)0,0 ,0(),(321xxx处取得极大值0)0,0,0(f。22 等式约束条件极值下面我们研究的是有若干个等式约束条件下，一个目标函数的极值问题， 其数学模型为：),(m i n21nxxxf目标函数mixxxgtsni,2, 10),(.21约束条件拉格朗日（ Lagrange)乘数法 ：（1）令),(),(21121nimiinxxxgxxxfL称为上述问题的拉格朗日乘数函数，称i为拉格朗日乘数。（2）设),(21nxxxf和),(21nixxxg均可微，则得到方程组（3）若),(2121mnxxx是上述方程组的解， 则点),(21nxxx可能为该问题的最优点。拉格朗日（Lagrange)乘数法的本质是： 将求有约束条件极值问题转化为求无条件极值问题；所求得的点，即是取得极值的必要条件点。拉格朗日乘数法没有解决极值的存在性问题，但是，如果拉格朗日乘数函数具有二阶连续偏导数，我们也可以应用黑塞矩阵来判定函数是否取得极值。在具体问题中， 点),(21nxxx是否为最优点通常可由问题的实际意义决定。例 2：求表面积为定值2a，而体积为最大的长方体的体积。解：设长方体的三棱长为zyx,，体积为 V ；建立数学模型如下：xyzVmax构造拉格朗日乘数函数)222(),(2axzyzxyxyzzyxL，则有名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 34 页 - - - - - - - - - 解得azyx66，3366maxaV为所求。23 不等式约束条件极值对于不等式约束条件极值问题：),(m i n21nxxxf目标函数mixxxgtsni,2, 10),(.21约束条件我们有与拉格朗日乘数法密切相关的方法库恩图克定理。定理 3 （库恩图克定理）： 对于上述不等式约束条件极值问题， 设),(21nxxxf和),(21nixxxg均可微，令),(),(21121nimiinxxxgxxxfL假设i存在，则在最优点*XX),(21nxxx处，必满足下述条件：（1）mijiijjnjxgxfxL1, 2, 10；（2）mixxxgni, 2, 10),(21；（3）mixxxgnii,2, 10),(21；（4）0i。根据库恩图克定理我们可以求解许多不等式约束条件极值问题，值得注意的是应用库恩图克定理求解不等式约束条件极值问题，定理并没有解决最优解的存在性问题，因此，我们必须另行判断。例 3：求解最优化问题（最优解存在）解：构造函数)()2() 1(),(212yyxyxzyxL，根据库恩图克定理则有0,000)2(010) 1(22121211yyxyLxxL解得：1,0,0, 121yx；所求最优解为)0, 1(),(yx，最优值为 0。3 线性规划31 线性规划名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 34 页 - - - - - - - - - 设线性规划标准数学模型为：nnnxcxcxcxxxf221121),(m i n目标函数nixmibxaxaxatsiinimii, 2, 10, 2, 1.2211约束条件矩阵形式：XCXfT)(m i n目标函数0XBAX约束条件其中TnxxxX),(21，TncccC),(21，TmbbbB),(21线性规划问题的求解有一整套理论体系，一般来说，应用单纯形法求解。此方法尽管比较复杂， 然而在计算机上实现并不困难。解线性规划问题的单纯形法已在许多数学计算软件中实现，我们求解线性规划问题可根据需要，应用数学计算软件求解即可。在此， 我们不系统研究其理论， 只是简单介绍线性规划的穷举法和单纯形法的基本思想。3.2 线性规划的穷举法（1）穷举法基本原理和步骤步骤 1：将线性规划问题化成矩阵的标准形式，设系数矩阵的秩mAR)(，则对应线性方程组的基础解系自由变量的个数为mn个。步骤 2：穷举法求解：令0)(21mniiixxx，解得对应线性方程组一组解为),(21nxxx；对应目标函数值为infxxxf),(21。从n个变量x中选mn个作为自由变量， 令它们的值为 0，可得到mnnmnCC组解。步骤 3：确定最优解：如果最优解存在，则上述求解得到的对应mnnmnCC个目标函数值中，最小者（或最大者）即为所求最小（或最大）最优值，对应的解为最优解。步骤 4：证明解为最优解：将最优解对应的自由变量看成参数)(21,mnttt；解对应线性方程组得nitbtbtbbxmnmniiiii,2, 1,)()(22110。将对应线性方程组解nitbtbtbbxmnmniiiii,2, 1,)()(22110代入目标函数得：)()(22110mnmntdtdtdff。如果nidi,2 ,1,0，则所求为最小值最优解；否则，线性规划问题无最名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 34 页 - - - - - - - - - 小值最优解。如果nidi,2 ,1,0，则所求为最大值最优解；否则，线性规划问题无最大值最优解。例 1：目标函数：32132)(maxxxxXf解：约束条件的增广矩阵为：100100102100101A，3)(AR；令021xx，解得5)(),4,10,5 ,0 ,0(XfX；令031xx，无解；令041xx，解得)1,0,5 ,5, 0(X，不满足非负条件，舍去；令051xx，解得17)(),0 ,2,5 ,4,0(XfX；令032xx，解得10)(),4 ,5 ,0 ,0,5(XfX；令042xx，解得)4,0, 5,0,10(X，不满足非负条件，舍去；令052xx，无解；令043xx，解得235)(),23,0, 0,25, 5(XfX；令053xx，解得)0 ,3,0 ,4, 5(X，不满足非负条件，舍去；令054xx，解得19)(),0, 0, 3,4, 2(XfX；所以19)(maxXf，最优解为)0,0, 3, 4,2(X。证明：令sxtx54,解得5 , 1,023422321ixstxsxstxi目标函数stXf19)(；因为sxtx54,非负，所以19)(maxXf，故最优解存在。（2）单纯形法基本原理和步骤将线性规划问题化成矩阵的标准形式，设系数矩阵的秩mAR)(，则对应线名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 34 页 - - - - - - - - - 性方程组的基础解系的个数为mn个，即有mn个自由参数变量。选取mn个非基变量 （自由参数变量） , 不妨假设为nmjxj, 1,；解得线性规划问题的 典式定理 1：如果线性规划问题的上述典式中所有nmjj, 1,0；则)0,0 ,(21mX为最优解。定理 2：如果线性规划问题的上述典式中存在某个0km，且对应mikmi,2, 1,0)(；则线性规划问题无最优解。由定理 1 和定理 2 知，如果我们选择适当的mn个非基变量，就可以根据所求得的典式判断最优解的存在与否，从而求解该线性规划问题。单纯形法的思想是：选择适当的基变换（进基和退基），不断地变换典式，使得典式中目标函数值不断下降，从而求得最优解。 其核心为如何选择进基和退基。进基规则和退基规则进基规则 正检验数最小下标规则，即选取0|minjjs，由此确定sx为进基。退基规则 ：选取这样的下标rJ（iJ表示第 i 个基变量的下标）由此确定rJx离基。单纯形法的基本步骤：步骤 1：化线性规划问题为标准形式。步骤 2：确定基变量，求得基本可行解和典式；是否满足最优解定理或最优解不存在定理的条件？判断最优解的情况。步骤 3：根据进基规则和退基规则，选择进基和退基，进行基变换，求得对应典式。重复进行基变换，直到求出最优解或判断出无最优解为止。例 2：解线性规划问题解： （1）约束条件的增广矩阵为：100260101100111A，3)(AR；所以非基变量个数为两个。（2）选取21,xx作为非基变量，543,xxx作为基变量，解得典式为不满足最优解定理和最优解不存在定理的条件，故必须进行基变换。（3）进行基变换选取进基：01,0221，名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 12 页，共 34 页 - - - - - - - - - 根据0|minjjs得1x为进基。选取退基：621621,15min，根据0|minisisi，0,|minisisiirJJ得5x为离基。进行基变换，求新基的典式：判断：不满足最优解定理和最优解不存在定理的条件，故继续进行基变换。（4）继续进行基变换选取进基：0312，根据0|minjjs得2x为进基。选取退基：49221,821,49min，根据0|minisisi，0,|minisisiirJJ得3x为离基。进行基变换，求新基的典式：满足最优解定理的条件，根据定理最优解为431min),0,21,0 ,49,411(fX。32 整数规划设纯整数线性规划数学模型为：nnnxcxcxcxxxf221121),(m i n目标函数nixxmibxaxaxatsiiinimii,2, 1,0, 2, 1.2211为整数约束条件这一类问题与一般线性规划比较起来，似乎是变简单了， 但实际上恰恰相反，由于解集是一些离散的整数点集，使得单纯形法失去了应用的基础，求解变得困难而复杂。 整数线性规划目前还缺乏统一的解法，这里只介绍分枝定界法，它是目前求解纯整数线性规划和混合整数线性规划最常用的方法，计算机求解整数线性规划的大多数程序也是以它为基础的。分枝定界法：考虑上述纯整数线性规划问题，（1）解对应线性规划问题nnnxcxcxcxxxf221121),(m i n目标函数nixmibxaxaxatsiinimii, 2, 10, 2, 1.2211约束条件若无最优解，则原纯整数线性规划问题无最优解；若有最优解，最优点),(21nxxx，目标函数最优值),(210nxxxfz。若最优点),(21nxxx全为整数，则为原纯整数线性规划问题的最优解；名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 13 页，共 34 页 - - - - - - - - - 若最优点),(21nxxx不全为整数，则进行下一步。（2）定界和分枝定界：00210),(minmzxxxfMn其中0M取原纯整数线性规划问题中，满足约束条件的某一整数可行解所对应的目标函数值。原纯整数线性规划问题的最优解必须满足定界条件。分枝： 选取),(21nxxx中一个不为整数所对应的kx 分枝，1R和2R称为对应线性规划问题的两枝，也是两个新线性规划问题的约束条件。显然，原纯整数线性规划问题的最优解满足1R或2R。（3）对1R和2R进行剪枝和分枝解1R对应的线性规划问题，对其进行剪枝和分枝：若无最优解，则原纯整数线性规划问题在1R内无最优解。不需要对该区域继续讨论 剪枝 。若有最优解，最优点),(21nxxx，目标函数的最优值),(211nxxxfz。若0211),(Mxxxfzn，则原纯整数线性规划问题在1R内无最优解。 不需要对该区域继续讨论剪枝 。若最优点),(21nxxx全为整数，则可能为原纯整数线性规划问题的最优解，定界：记0211),(MxxxfMn，则0211),(m inmxxxfMn，本分枝求解结束。若最优点),(21nxxx不全为整数，对1R继续进行分枝。完全类似，解2R对应线性规划问题，对其进行剪枝和分枝。依此类推，对所有分枝进行求解，剪枝，分枝，定界；直至求得最优解。（4）最优解的确定若某0mMk，则为最优解，求解结束。若所有分枝求解结束，则最后的上界kM即为最优解。例 3：应用分枝定界法，求解整数线性规划问题解：设原整数线性规划问题目标函数的最优值为*z ，（1）求解线性规划问题：213minxxz名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 14 页，共 34 页 - - - - - - - - - 得最优解为13.3,12.821xx；51.17min z。记约束区域0,0285342213.321212xxxxx为 R。（2）对 R进行分枝：选取最优解中不是整数的变量，例如1x，将 R分成两个子区域21,RR。0,0285342213.39:2121211xxxxxxR，0,0285342213.38:2121212xxxxxxR（3）定界：确定最优值*z 的上下界。由（1）中求得的最优值知51.17*z；而*z的上界可由 R内的任意一个可行解确定，例如，4,721xx即为一个可行解。故19* z。从而，19*51.17z。（4）在1R内求最优解，得13.3,921xx；39.18min z。（5）在2R内求最优解，得21.3,821xx；62.17min z。（6）因为1R内最优解不全是整数，因而必须继续对1R分枝：（7）显然12R内无解，剪枝。在11R内求最优解，得4,921xx；21min z；为整数可行解。但因19*51.17z，而1921，故剪枝。（8）因为2R内最优解不全是整数，因而必须继续对2R分枝：（9）显然22R内无解，剪枝。在21R内求最优解，得4,77.621xx；77.18min z。（10）因为21R内最优解不全是整数，因而必须继续对21R分枝：（11）在212R内求最优解，得5 .4,621xx；5.19min z。因5 .19min z大于*z 的上界，故剪枝。（12）在211R内求最优解，得4,721xx；19min z。所求原整数规划问题的最优解为：4,721xx；19min z。4 最优化问题数值算法名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 15 页，共 34 页 - - - - - - - - - 最优化问题的数值算法很多，常用的算法多为搜索法，本节只介绍搜索法的基本思想、无约束最优化问题的最速下降法（梯度法）和有约束最优化问题的罚函数法。41 搜索算法考虑无约束最优化问题：),(min21nxxxf我们已经讨论了这类问题的最优解条件，这必须用到函数的解析性质。 我们的方法是，先利用必要条件求出平稳点，再应用充分条件判断是否是极值点。但是，我们必须求解一个n个变量n个方程的方程组，并且常常是非线性的。这只有在特殊的情况下，才能求出它的精确解。在一般情况下， 都不能用解析法求得精确解。更何况许多实际问题中，函数的解析表达式很难得到。因此，我们必须寻求一些切合实际问题的行之有效的数值解法。搜索算法 就是我们常用的方法。（1）搜索算法的基本思想：假定目标函数)(Xf极小值问题。首先，确定目标函数)(Xf的初始点0X；然后，按照一定规则产生一个点列kX，这种规则称为算法；规则必须满足（1）点列kX收敛； （2）点列kX收敛到目标函数)(Xf的极小值点。（2）搜索算法的基本步骤：选定初始点0X（越接近最优点越好），允许误差0 ，令0k。假定已得非最优点kX，则选取一个搜索方向kS，满足：目标函数)(Xf下降，或0)(kkSXgradf。选定搜索步长0k，kkkkSXX1，满足：)()()(1kkkkkXfSXfXf。判断1kX是否是最优点或是满足要求的近似解。假定给定精度要求为0，常用确定求近似解搜索结束的方法有：|)(|1kXgradf梯度模确定法；|)()(|1kkXfXf目标函数差值绝对误差法；|1kkXX相邻搜索点绝对误差法。如果1kX满足给定精度要求，则搜索完成，近似最优点为1*kXX；如果1kX不满足给定精度要求，令1kk返回（ 2）继续搜索。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 16 页，共 34 页 - - - - - - - - - 注意 1：我们的搜索算法一般得到的都是局部最优解。注意 2：确定求近似解搜索结束的方法还有|)(|)()(|1kkkXfXfXf目标函数差值相对误差法；|1kkkXXX相邻搜索点相对误差法。（3）搜索算法的关键因素：从搜索算法的基本步骤中，我们知道，搜索算法的关键因素为：一是搜索方向，二是搜索步长。搜索方向的选择， 一般考虑既要使它尽可能的指向极小值点，又要不至于花费太多的计算量。搜索步长的选择， 既要确保目标函数的下降性质，又要考虑近似解的精度要求，还要考虑算法的计算量，问题十分复杂。常用方法有，固定步长法，最优步长法和变步长法。固定步长法（简单算法）是选取0k为固定值。方法简单，但是有时不能保证目标函数的下降性质。最优步长法（一维搜索算法）是选取k使得，这是一个关于单变量的函数求极小值问题，这样确定的步长称为最优步长。变步长法（可接受点算法）是任意选取k，只要使得)()(1kkXfXf即可。这种选取步长的方法， 确保了目标函数的下降性质， 尽管每次选取的步长不是最优的，但实践证明，方法能达到更好的数值效果。总之，当搜索方向确定以后，步长就是决定最优化算法好坏的重要因素，因此，我们必须特别注重步长的选取问题。（4） 搜索算法的收敛性： 搜索算法的收敛性是指， 由某算法得到的点列kX能够在有限步骤内收敛到目标函数)(Xf的最优点或能够在有限步骤内达到满足精度要求的目标函数)(Xf的最优点的近似值。显然，只有具有收敛性质的算法才有意义。搜索算法的收敛速度： 作为一个好的算法， 还必须要求它以较快的速度收敛于最优解。阶收敛定义 ：对于收敛于最优解*X的序列kX，若存在与 k 无关的数0和1，当 k 从某个0k开始时，有|*|*|1XXXXkk成立，则称序列kX收敛的阶为，或称阶收敛。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 17 页，共 34 页 - - - - - - - - - 当1时，称迭代序列kX为线性收敛；当21时，称迭代序列kX为超线性收敛；当2 时，称迭代序列kX为二阶收敛。一般来说， 线性收敛是比较慢的，而二阶收敛则是很快的，超线性收敛介于二者之间。 如果一个算法具有超线性以上的收敛速度，我们就认为是一个好的算法了。42 无约束最优化问题的梯度法无约束最优化问题的计算方法很多。无约束最优化问题的计算方法分为两大类：一类是解析法，包括经典最优化方法，最速下降法（梯度法） ，共轭梯度法，牛顿法和变尺度法等。另一类是直接法，包括坐标轮换法，步长加速法，方向加速法和单纯形法等。所谓解析法就是在方法的计算过程中，应用到了函数的解析性质 （可导性质等） ；所谓直接法就是在方法的计算过程中，仅仅涉及目标函数值的计算，而不涉及函数导数等解析性质。我们在这里只介绍最速下降法（梯度法）。最速下降法理论根据：早在1847 年，法国着名数学家Cauchy 就曾提出，从任意给定点出发，函数沿哪个方向下降最快的问题。 这个问题已从理论上解决了，即沿着函数在该点的负梯度方向前进时，函数下降最快。 这就是最速下降法的理论根据。最速下降法的 搜索步骤：步骤 1：选定初始点0X（越接近最优点越好） ，允许误差0，令0k。步骤 2：假定已得非最优点kX，计算梯度)(kXgradf，选取搜索方向)(kkXg r a d fS步骤 3：选定搜索步长0k，kkkkSXX1，满足：)(min)(0kkkkkSXfSXf。步骤 4：判断1kX是否是最优点或是满足要求的近似解。根据精度要求，检验是否满足收敛性判断准则：|)(|1kXgradf或|)()(|1kkXfXf或|1kkXX如果1kX满足给定精度要求，则搜索完成，近似最优点为1*kXX；如果1kX不满足给定精度要求，令1kk返回（ 2）继续搜索。例 1：应用最速下降法求解222125)(minxxXf。解： （1）选定初始点)2,2(0X，允许误差2.0，置0:k收敛判断准则|)()(|1kkXfXf。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 18 页，共 34 页 - - - - - - - - - （2）计算梯度)(kXgradf，选取搜索方向)(kkXgradfSkXXkxxXg r a d f|50,2)(21，kXXkxxS|50,221第一点搜索计算：100,4)(0Xgradf，100, 40S（3）选定搜索步长0k，kkkkSXX1，满足：第一点搜索计算：求最优步长解得02.00。（4）判断1kX是否是最优点或是满足要求的近似解。第一点搜索计算：)0 ,92.1(1X验证收敛判断准则02.031.100|)()(|01XfXf，不满足，继续搜索。依次类推，直到搜索到最优解或满足精度要求为止。搜索计算列表如下：搜索步长k搜索方向kS搜索点kX函数值)(kXf)0,0(2X为最优解43 罚函数法对于约束最优化问题也有许多种方法，本段只介绍把约束最优化问题转化为无约束最优化问题的一种求解方法罚函数法。分为等式约束最优化问题和不等式约束最优化问题两种情况讨论。（1）等式约束最优化问题的罚函数法首先，考虑等式约束最优化问题假定上述等式约束最优化问题的最优解存在。若记,2, 1,0)(|niRXmiXgXD，构造辅助函数miiXgMXfMXT12)()(),(罚函数其中0M（罚因子 ）是一个充分大的正数。定理 1