建模典型实例详解讲义

《建模典型实例详解讲义》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第三章一.基本概念：因为人类所从事的一切生产或社会活动均是有目的的，其行为总是在特定的价值观念或审美取向的支配下进行的，经常面临求解一个可行的甚至是最优的方案的决策问题。可以说，最优化思想是数学建模的灵魂。而最优化方法作为一门特殊的数学学科分支有着广泛的实际应用背景。典型的最优化模型可以被描述为如下形式：其中表示一组决策变量，通常在实数域内取值，称决策变量的函数为该最优化模型的目标函数；为维欧氏空间的某个子集，通常由一组关于决策变量的等式或不等式刻画，形如：这时，称模型中关于决策变量的等式或不等式、为约束条件，而称满足全部约束条件的空间中的点为该模型的可行解，称，即由所有可行解构成的

2、集合为该模型的可行域。称为最优化模型的（全局）最优解，若满足：对均有，这时称处的目标函数值的为最优化模型的（全局）最优值；称为最优化模型的局部最优解，若存在，对，均有。（全局）最优解一定是局部最优解，但反之不然，其关系可由下图得到反映：上图为函数在区间上的一段函数曲线（由Mathematica绘制），如果考察最优化问题，从图中发现它有三个局部最优解、、，其中是全局最优解，最优值为“”。二.最优化问题的一些典型的分类：优化方法涉及的应用领域很广，问题种类与性质繁多，根据不同的原则可以给出不同的分类。从数学建模的角度，对最优化问题的一些典型分类及相关概念的了解是有益的。根据决策变量的取值

3、类型，可分为函数优化问题与组合优化问题，称决策变量均为连续变量的最优化问题为函数优化问题；若一个最优化问题的全部决策变量均离散取值，则称之为组合优化问题。比方一些最优化问题的决策变量被限定只能取整数值，即为组合最优化问题，这类优化问题通常被称为整数规划问题，另外大多网络规划问题属于组合最优化问题。当然，也有许多应用问题的数学模型表现为混合类型的，即模型的部分决策变量为连续型的，部分决策变量为离散型的；另外当谈论一个最优化问题是函数优化问题还是组合优化问题时，还需结合我们对这一问题的思考方式来进行确定，比方后面介绍的线性规划问题的求解，既有将其作为一个组合优化问题而开发的算法，也有将其

4、作为一个函数优化问题而开发的算法；另外的一种分类方式是根据问题中目标、约束条件函数的形式或性质来加以划分的：若一个最优化问题的目标、约束条件函数均为决策变量的线性函数，则称之为线性规划问题，否则称之为非线性最优化问题。线性规划问题的研究，理论和方法都已发展的相当成熟，方法被广泛应用于生产和管理等领域；而对非线性最优化问题，根据建模和算法设计的需要还有更进一步的分类；在生产、经济与管理等领域中遇到的大量最优决策问题，对一个方案的评价是多角度多指标的，反映在数学模型中，优化的目标是关于决策变量的一个函数组，我们称之为多目标规划问题。比如导弹的设计，既要其射程远，又要消耗燃料少，还要命中率

5、高等；又如选择新厂的厂址，除了要考虑地价、原料采购的运费等经济指标外，还需考虑对环境的污染等社会因素。三.最优化问题最优解的一阶必要条件：这里对形如的最优化问题的一阶必要性条件作简单介绍，它一方面可以将最优化问题和方程组问题做某种形式的联系，另一方面它在最优化问题数值求解算法的设计有重要的意义。定理：设为最优化问题的（局部）最优解，若满足：1）、在均可微；2）、分别表示、在的梯度向量，向量组线性无关；则，满足：1）；2）对于，均有且。例、求解如下非线性规划:。解：目标函数的梯度向量（函数）为，而约束条件相当于有三个：、、，它们分别对应梯度向量（函数）、、；令、、、并要求。解之得四组解

6、：1）；；2）；；3）；；4）；；计算每个点的目标函数值，发现为（全局）最优解，最优目标函数值为。特别，对于无约束最优化问题，其一阶最优化条件如下：定理：设为最优化问题的（局部）最优解，若在均可微，则在的梯度向量为零向量，即。§3.2无约束最优化方法在这里我们只是对一些典型的最优化算法作简单介绍，以期那些初次接触数值计算方法的学习者能对最优化算法的设计思想有概貌性了解，能编写一些简单的最优化算法以处理学习中遇到的问题。而希望对最优化方法有更深入的学习或者欲处理相对复杂的最优化问题，需要参考更为专门的书籍或借助有关数学软件。一．一维搜索：1．0.618法（黄金分割法）：设单变量函数在区

7、间上有定义，若存在一点，使得在区间上严格单调减，在区间上严格单调增，则称是区间上的（下）单峰函数。显然是在区间上的唯一的极小值点。对（下）单峰函数，有如下基本性质：性质1：设是区间上的（下）单峰函数，是在区间上的唯一的极小值点，对任意，若，则必有；性质2：设是区间上的（下）单峰函数，是在区间上的唯一的极小值点，对任意，若，则必有；若，则必有。根据（下）单峰函数所具有的性质，对在某区间上的（下）单峰函数可采用法（黄金分割法）进行搜索其在区间内的极小值点。方法