第六章 最优化数学模型
§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)变量
变量就是指最优化问题中所涉及的与约束条件与目标函数有关的待确定的量。一般来说,它们都有一些限制条件(约束条件),与目标函数紧密关联。
设问题中涉及的变量为n x x x ,,,21 ;我们常常也用),,,(21n x x x X 表示。 (3)约束条件
在最优化问题中,求目标函数的极值时,变量必须满足的限制称为约束条件。 例如,许多实际问题变量要求必须非负,这就是一种限制;在研究电路优化设计
问题时,变量必须服从电路基本定律,这也就是一种限制等等。在研究问题时,这些限制我们必须用数学表达式准确地描述它们。 用数学语言描述约束条件一般来说有两种: 等式约束条件 m i X g i ,,2,1,0)( 不等式约束条件 r i X h i ,,2,1,
0)( 或 r i X h i ,,2,1,
0)(
注:在最优化问题研究中,由于解的存在性十分复杂,一般来说,我们不考虑不等式约束条件0)( X h 或0)( X h 。这两种约束条件最优化问题最优解的存在性较复杂。
(4)目标函数
在最优化问题中,与变量有关的待求其极值(或最大值最小值)的函数称为目标函数。
目标函数常用),,,()(21n x x x f X f 表示。当目标函数为某问题的效益函数时,问题即为求极大值;当目标函数为某问题的费用函数时,问题即为求极小值等等。
求极大值与极小值问题实际上没有原则上的区别,因为求)(X f 的极小值,也就就是要求)(X f 的极大值,两者的最优值在同一点取到。
1.2 最优化问题分类
最优化问题种类繁多,因而分类的方法也有许多。可以按变量的性质分类,按有无约束条件分类,按目标函数的个数分类等等。
一般来说,变量可以分为确定性变量,随机变量与系统变量等等,相对应的最优化问题分别称为:普通最优化问题,统计最优化问题与系统最优化问题。 按有无约束条件分类:无约束最优化问题,有约束最优化问题。
按目标函数的个数分类:单目标最优化问题,多目标最优化问题。
按约束条件与目标函数就是否就是线性函数分类:线性最优化问题(线性规划),非线性最优化问题(非线性规划)。
按约束条件与目标函数就是否就是时间的函数分类:静态最优化问题与动态最优化问题(动态规划)。
按最优化问题求解方法分类:
①解析法(间接法)
图克定理库恩极大值原理有约束古典变分法古典微分法无约束
②数值算法(直接法)
随机搜索法单纯形法方向加速法
步长加速法坐标轮换法
多维搜索法插值法黄金分割法斐波那西法一维搜索法 ③数值算法(梯度法)
复形法法法化有约束为无约束梯度投影法可行方向法有约束梯度法变尺度法
共轭梯度法拟牛顿法
最速下降法无约束梯度法SWIFT SUMT
④多目标优化方法
目标关联函数法多重目标化方法单目标化方法
⑤网络优化方法
1.3 最优化问题的求解步骤与数学模型 (1)最优化问题的求解步骤
最优化问题的求解涉及到应用数学,计算机科学以及各专业领域等等,就是一个十分复杂的问题,然而它却就是需要我们重点关心的问题之一。怎样研究分析求解这类问题呢？其中最关键的就是建立数学模型与求解数学模型。一般来说,应用最优化方法解决实际问题可分为四个步骤进行: 步骤1:建立模型
提出最优化问题,变量就是什么？约束条件有那些？目标函数就是什么？建立最优化问题数学模型:确定变量,建立目标函数,列出约束条件——建立模型。 步骤2:确定求解方法
分析模型,根据数学模型的性质,选择优化求解方法——确定求解方法。 步骤3:计算机求解
编程序(或使用数学计算软件),应用计算机求最优解——计算机求解。 步骤4:结果分析
对算法的可行性、收敛性、通用性、时效性、稳定性、灵敏性与误差等等作出评价——结果分析。
(2)最优化问题数学模型
最优化问题的求解与其数学模型的类型密切相关,因而我们有必要对最优化问题的数学模型有所掌握。一般来说,最优化问题的常见数学模型有以下几种: ①无约束最优化问题数学模型
由某实际问题设立变量,建立一个目标函数且无约束条件,这样的求函数极值或最大值最小值问题,我们称为无约束最优化问题。其数学模型为: ),,,(min 21n x x x f ——目标函数
例如:求一元函数)(x f y 与二元函数),(y x f z 的极值。
又例如:求函数3231212322
21321242643),,(x x x x x x x x x x x x f 的极值与取得极值的点。
②有约束最优化问题数学模型
由某实际问题设立变量,建立一个目标函数与若干个约束条件(等式或不等式),这样的求函数极值或最大值最小值问题,我们称为有约束最优化问题。其数学模型为:
),,,(min 21n x x x f ——目标函数 m i x x x g n i ,,2,10
),,,(21 ——约束条件
有约束最优化问题的例子:求函数n x x x x x x f 31321),,( 在约束条件条件
n i x x x x i n ,,2,1,0,
200831 下的最大值与取得最大值的点。
③线性规划问题数学模型
由某实际问题设立变量,建立一个目标函数与若干个约束条件,目标函数 与约束条件都就是变量的线性函数,而且变量就是非负的,这样的求函数最大值最小值问题,我们称为线性最优化问题,简称为线性规划问题。其标准数学模型为: n n n x c x c x c x x x f 221121),,,(m in ——目标函数
,,2,12211 i i
n im i i x m
i b x a x a x a ——约束条件
矩阵形式: X C X f T )(m in ——目标函数
X B
AX ——约束条件
其中 T n x x x X ),,,(21 ,T n c c c C ),,,(21 ,T m b b b B ),,,(21
