第六章最优化数学模型§1最优化问题1．1最优化问题概念1．2最优化问题分类1．3最优化问题数学模型§2经典最优化方法2．1无约束条件极值2．2等式约束条件极值2．3不等式约束条件极值§3线性规划3．1线性规划3．2整数规划§4最优化问题数值算法4．1直接搜索法4．2梯度法4．3罚函数法§5多目标优化问题5．1多目标优化问题5．2单目标化解法5．3多重优化解法5．4目标关联函数解法5．5投资收益风险问题第六章最优化问题数学模§1最优化问题1．1最优化问题概念（1）最优化问题在工业、农业、交通运输、商业、国防、建筑、通信、政府机关等各部门各领域的实际工作中，我们经常会遇到求函数的极值或最大值最小值问题，这一类问题我们称之为最优化问题。
而求解最优化问题的数学方法被称为最优化方法。
它主要解决最优生产计划、最优分配、最佳设计、最优决策、最优管理等求函数最大值最小值问题。
最优化问题的目的有两个：①求出满足一定条件下，函数的极值或最大值最小值；②求出取得极值时变量的取值。
最优化问题所涉及的内容种类繁多，有的十分复杂，但是它们都有共同的关键因素：变量，约束条件和目标函数。
（2）变量变量是指最优化问题中所涉及的与约束条件和目标函数有关的待确定的量。
一般来说，它们都有一些限制条件（约束条件），与目标函数紧密关联。
设问题中涉及的变量为x1,x2, , x n ；我们常常也用X （x1,x2, ,x n）表示。
3）约束条件在最优化问题中，求目标函数的极值时，变量必须满足的限制称为约束条件例如，许多实际问题变量要求必须非负，这是一种限制；在研究电路优化设计问题时，变量必须服从电路基本定律，这也是一种限制等等。
在研究问题时，这些限制我们必须用数学表达式准确地描述它们。
用数学语言描述约束条件一般来说有两种：等式约束条件g i (X) 0, i 1,2, ,m不等式约束条件h i (X) 0, i 1,2, ,r或h i (X) 0, i 1,2, ,r注：在最优化问题研究中，由于解的存在性十分复杂，一般来说，我们不考虑不等式约束条件h(X) 0或h(X) 0 。
这两种约束条件最优化问题最优解的存在性较复杂。
(4)目标函数在最优化问题中，与变量有关的待求其极值(或最大值最小值)的函数称为目标函数。
目标函数常用f(X) f (x1,x2, ,x n )表示。
当目标函数为某问题的效益函数时，问题即为求极大值；当目标函数为某问题的费用函数时，问题即为求极小值等等。
求极大值和极小值问题实际上没有原则上的区别，因为求 f (X) 的极小值，也就是要求 f ( X )的极大值，两者的最优值在同一点取到1．2 最优化问题分类最优化问题种类繁多，因而分类的方法也有许多。
可以按变量的性质分类，按有无约束条件分类，按目标函数的个数分类等等。
一般来说，变量可以分为确定性变量，随机变量和系统变量等等，相对应的最优化问题分别称为：普通最优化问题，统计最优化问题和系统最优化问题。
按有无约束条件分类：无约束最优化问题，有约束最优化问题。
按目标函数的个数分类：单目标最优化问题，多目标最优化问题。
按约束条件和目标函数是否是线性函数分类：线性最优化问题 (线性规划)，非线性最优化问题(非线性规划) 。
按约束条件和目标函数是否是时间的函数分类：静态最优化问题和动态最优化问题(动态规划)。
按最优化问题求解方法分类：无约束①解析法(间接法)有约束古典微分法古典变分法极大值原理库恩图克定理斐波那西法一维搜索法 黄金分割法 插值法坐标轮换法 步长加速法多维搜索法 方向加速法 单纯形法 随机搜索法最速下降法 拟牛顿法 无约束梯度法共轭梯度法 变尺度法 可行方向法 梯度投影法SUMT 法 化有约束为无约束SWIFT 法 复形法单目标化方法④多目标优化方法 多重目标化方法目标关联函数法⑤网络优化方法1．3 最优化问题的求解步骤和数学模型（1）最优化问题的求解步骤 最优化问题的求解涉及到应用数学， 计算机科学以及各专业领域等等， 是一 个十分复杂的问题， 然而它却是需要我们重点关心的问题之一。
怎样研究分析求 解这类问题呢？其中最关键的是建立数学模型和求解数学模型。
一般来说， 应用 最优化方法解决实际问题可分为四个步骤进行：步骤 1：建立模型 提出最优化问题，变量是什么？约束条件有那些？目标函数是什么？建立最 优化问题数学模型：确定变量，建立目标函数，列出约束条件—— 建立模型 。
步骤 2：确定求解方法分析模型，根据数学模型的性质，选择优化求解方法—— 确定求解方法 。
步骤 3：计算机求解编程序（或使用数学计算软件） ，应用计算机求最优解—— 计算机求解 。
步骤 4：结果分析对算法的可行性、收敛性、通用性、时效性、稳定性、灵敏性和误差等等作出 评价——结果分析 。
（2）最优化问题数学模型②数值算法（直接法）③数值算法（梯度法）有约束梯度法最优化问题的求解与其数学模型的类型密切相关， 因而我们有必要对最优化 问题的数学模型有所掌握。
一般来说，最优化问题的常见数学模型有以下几种：① 无约束最优化问题数学模型 由某实际问题设立变量， 建立一个目标函数且无约束条件， 这样的求函数极 值或最大值最小值问题，我们称为 无约束最优化问题 。
其数学模型为：m i nf (x 1, x 2, ,x n ) ——目标函数例如：求一元函数 y f (x) 和二元函数 z f (x,y)的极值。
又例如：求函数 f (x 1, x 2, x 3) 3x 12 4x 22 6x 32 2x 1x 2 4x 1x 3 2x 2x 3 的极值和取 得极值的点。
② 有约束最优化问题数学模型 由某实际问题设立变量， 建立一个目标函数和若干个约束条件 (等式或不等 式)，这样的求函数极值或最大值最小值问题，我们称为 有约束最优化问题 。
其 数学模型为：m i nf (x 1, x 2, , x n )——目标函数g i (x 1,x 2, ,x n ) 0 i 1,2, ,m ——约束条件 有约束最优化问题的例子：求函数 f (x 1,x 2, x 3) x 1x 3 x n 在约束条件条件 x 1 x 3x n 2008, x i 0 ,i 1,2, , n 下的最大值和取得最大值的点。
③ 线性规划问题数学模型 由某实际问题设立变量，建立一个目标函数和若干个约束条件，目标函数 和约束条件都是变量的线性函数， 而且变量是非负的， 这样的求函数最大值最小 值问题，我们称为线性最优化问题，简称为 线性规划问题m i nf (x 1, x 2, ,x n ) c 1x 1 c 2x 2c n x na i1x 1 a i2x 2a im x nb i i 1,2, ,mx i 0矩阵形式： mi nf (X) C T XAX B X0其中 X (x 1,x 2, ,x n )T ， C (c 1,c 2, ,c n )T ， B (b 1,b 2, ,b m )T 在线性规划问题中，关于约束条件我们必须注意以下几个问题。
注 1：非负约束条件 x i 0 ( i 1,2, , n)，一般来说这是实际问题要求的需要。
如果约束条件为 x i d i ，我们作变量替换 z i x i d i 0 ；如果约束条件为 x i d i ，我们作变量替换 z i d i x i 0。
注 2 ：在线性规划的标准数学模型中，约束条件为等式。
如果约束条件不是等式， 我们引入松驰变量， 化不等式约束条件为等式约束 条件。
情况 1：若约束条件为 a i1x 1 a i2x 2a im x nb i ，引入松驰变量其标准数学模型为： ——目标函数——约束条件——目标函数——约束条件原约束条件变为a i1x1 a i2x2 a im x n z i b i 。
情况2：若约束条件为a i1x1 a i2x2 a im x n b i ，引入松驰变量原约束条件变为a i1x1 a i2 x2 a im x n z i b i在其它最优化问题中，我们也常常采取上述方法化不等式约束条件为等式约束条件。
实际问题中，我们经常遇到两类特殊的线性规划问题。
一类是：所求变量要求是非负整数，称为整数规划问题；另一类是所求变量要求只取0或1，称为0-1 规划问题。
例如：整数规划问题x2 3.13s.t. 22x1 34x2 2 8 5 。
x1 0, x2 0且为整数又例如：0-1 规划问题ma xz 3x1 2x2 5x3x1 2x2 x3 2x1 4x2 x3 4s.t. x1, x2, x3 0或1。
x1 x2 34x2 x3 6④非线性规划问题数学模型由某实际问题设立变量，建立一个目标函数和若干个约束条件，如果目标函数或约束条件表达式中有变量的非线性函数，那么，这样的求函数最大值最小值问题，我们称为非线性规划最优化问题，简称为非线性规划问题。
其数学模型为：m i nf (x1, x2, , x n) ——目标函数g i (x1,x2 , , x n) 0 i 1,2, ,m ——约束条件其中目标函数或约束条件中有变量的非线性函数。
例如：非线性规划问题mi nf(x,y) (x 1)2 yg1(x, y) x y 2 0 。
g2(x, y) y 0上述最优化问题中，目标函数是非线性函数，故称为非线性规划问题。
前面介绍的四种最优化数学模型都只有一个目标函数，称为单目标最优化问题，简称为最优化问题。
⑤多目标最优化问题数学模型由某实际问题设立变量，建立两个或多个目标函数和若干个约束条件，且目标函数或约束条件是变量的函数，这样的求函数最大值最小值问题，我们称为多目标最优化问题。
其数学模型为：m inf i (x1,x2, ,x n) i 1,2, ,s ——目标函数g i (x1,x2 , ,x n) 0 i 1,2, ,m ——约束条件上述模型中有s 个目标函数，m个等式约束条件。
例如：“生产商如何使得产值最大而且消耗资源最少问题” “投资商如何使得投资收益最大而且风险最小问题”等都是多目标最优化问题。
§ 2 经典最优化方法经典最优化方法包括无约束条件极值问题和等式约束条件极值问题两种，不等式约束条件极值问题可以化为等式约束条件极值问题。
经典的极值理论：首先，根据可微函数取极值的必要条件确定可能极值点；其次，根据函数取极值的充分条件判断是否取极值？是极大值？还是极小值？这种方法已经几百年的历史了。
2．1 无约束条件极值设n元函数f (X) f (x1,x2, ,x n)，求f (X )的极值和取得极值的点。
这是一个无约束条件极值问题，经典的极值理论如下。