正文:摘 要:随着计算机等各项技术的发展,用数学思维解决实际问题显得越来越重要。结合
2006 年全国大学生数学建模竞赛A 题,本文给出了整数线性规划模型的建模过程,体现了
最优化方法在数学建模中的重要作用。并通过介绍几个简单的数学模型,加深了对最优化方
法与数学建模的认识,阐述了数学建模与最优化方法之间的紧密关系,最优化方法是数学建
模的本质,数学模型是最优化方法的实现方式。
关键词:最优化;数学建模;数学规划
1.引言
最优化理论与算法是一个重要的数学分支,它所研究的问题是讨论在众多的方案中什么
样的方案最优以及怎样找出最优方案,研究这些计算方法的理论性质及实际表现。这类问题
在工程设计、资源分配、生产计划安排、原料配比问题、城建规划、农田规划、军事指挥等
人类活动的各个领域中普遍存在。
数学建模是从实际课题中抽象、提炼出数学模型的过程。人们常对实际事物建立种种数
学模型以期通过对该模型的考察来描述、解释、预计或分析出实际事物相关的规律。数学模
型(Mathematical Model)也是一种模拟,是用数学符号、数学式子、程序、图形等对实际
课题本质属性的抽象而又简洁的刻画,它或能解释某些客观现象,或能预测未来的发展规律,
或能为控制某一现象的发展提供某种意义下的最优策略或较好策略。
数学建模与最优化方法之间的关系蕴含在用最优化方法解决问题的一般过程中:一是提
出最优化问题,收集有关数据和资料;二是建立最优化问题的数学模型,确定变量,列出目
标函数和约束条件;三是分析模型,选择合适的最优化方法;四是求解,一般通过编制程序,
用计算机求最优解;五是最优解的检验和实施。
2.最优化模型
典型的最优化模型可以描述成如下形式:
Min{
f (
X ) |
X ∈
D}
其中,
X= (
x1 ,
x2 , …
xn )
T表示一组决策变量,
xi (
i= 1, …,
n) 通常在实数域
R内取值,
称决策变量的函数
f (
X )为该最优化模型的目标函数。
D为
n维欧式空间
Rn的某个子集,
通常由一组关于决策变量的等式或不等式刻画,形如:
Min f( X)s. t. Ci( X)≥0 ( i=1,2,… m1) Ci( X)=0 ( I= m1+1,… m)这 时 , 称 模 型 中 关 于 决 策变量的等式或不等式
Ci( X)≥0 ( i=1,2,… m1)、
Ci( X)=0 ( I= m1+1,… m)为约束条件,而称满足全部约束条件的空间
Rn中的点
X 为该
模型的可行解,称
即由所有可行解构成的集合为该模型的可行域。
称
X * ∈
D为最优化模型
Min{
f (
X ) |
X ∈
D}的(全局)最优解,若满足:对∀
X ∈
D均有
f (
X * ) ≤
f (
X ) , 这时称
X * ∈
D 处的目标函数值
f (
X * ) 为最优化模型
Min{
f (
X ) |
X ∈
D}的(全局)最优值;称
X * ∈
D为最优化模型
Min{
f (
X ) |
X ∈
D}的局部最优解, 若存在δ > 0 , 对∀
X ∈
D ∩{
X ∈
Rn|
}
均有
f (
X * ) ≤
f (
X )。(全局)最优解一定是局部最优解,但反之不然。
优化方法涉及的应用领域很广,问题种类与性质繁多,根据不同的原则可以给出不同的分类。一方面,根据决策变量的取值类型,可分为函数优化问题与组合优化问题。称决策变
量均为连续变量的最优化问题为函数优化问题;若最优化问题的全部决策变量均离散取值,
则称之为组合优化问题。例如,一些最优化问题的决策变量被限定只能取整数值,即为组合
最优化问题,这类优化问题通常被称为整数规划问题,大多网络规划问题都属于组合最优化
问题当然,也有许多应用问题的数学模型表现为混合类型时,即模型的部分决策变量为连续
型的,部分决策变量为离散型的。当谈论一个最优化问题是函数优化问题还是组合优化问题
时,还需结合对这一问题的思考方式来确定,比如对线性规划问题的求解,既有将其作为组
合优化问题而开发的算法,也有将其作为函数优化问题而开发的算法。
另一方面,根据问题中目标、约束条件函数的形式或性质,可分为线性规划问题和非线
性规划问题。若一个最优化问题的目标、约束条件函数均为决策变量的线性函数,则称之为
线性规划问题,否则称之为非线性最优化问题。线性规划问题的研究、理论和方法都已发展的相当成熟,方法被广泛应用于生产和管理等领域;而对非线性最优化问题,根据建模
和算法设计的需要还有更进一步的分类。
另外,在生产、经济与管理等领域中遇到的大量最优决策问题,对一个方案的评价是多
角度多指标的,反映在数学模型中,优化的目标是关于决策变量的一个函数组,称之为多目
标规划问题。比如导弹的设计,既要其射程远,又要消耗燃料少,还要命中率高等;又如选
择新厂的厂址,除了要考虑低价、原料采购的运费等经济指标外,还需考虑对环境的污染等
社会因素。
3.从数学建模到最优化理论
数学建模的关键在于一个“建”字,但一旦数学模型建立起来之后,对于它的求解就显
得很重要了,如果仅仅列出模型,没有得到一个优化的结果,更不要说总结性的归纳、拓展、
应用,那建出的模型是没有什么实际意义的。
一般的数学模型所涉及的问题都是一个最优化问题,即在一些约束条件下,如何使模型
的解达到最优。一般的数学模型中抽象出来的最优化问题具有如下形式:
Min f( x)s. .t Ax≥ b这种问题根据目标函数和约束函数的特点可分为很多类,都是运筹学的分支,如线性规
划、非线性规划、图论、目标规划、动态规划问题等。无论怎样,如果一个数学模型不能
用初等的数学理论解决,也不能用常微分方程理论解决的话,那它一定就是用最优化的理论
来解决。
针对不同的优化问题,有诸多不同的求解方法,求解线性优化问题可以用单纯形法;求
解非线性优化问题可以用最速下降法、共轭方向法、牛顿法、拟牛顿法等;网络规划中有
1/4 1 2 3 4 下一页 尾页