数 学 建 模
最 优 化 问 题
最优化问题
摘 要：自从1946年世界上第一台电子数字计算机诞生以来，计算机技术便以一种势不可挡的速度开始发展，与之伴随的是数学的广泛应用，不仅在工程技术、自然科学等等领域，数学的应用发挥着无与伦比的重要作用，并且在广度和深度上还渗透到了新的领域中，如医学、地质、交通灯、经济、生物、环境、人口、金融等等。因而说，在当代高新技术中，数学技术已经成为一个不可替代的重要组成部分。在本文中，笔者对最优化的问题在求解数学模型中的应用做了简要的探讨。
关键词：最优化问题；数学；建模
一、
在体现数学应用的方式中，数学建模是不可忽视的一种
所谓数学建模，指的是以数学语言为工具，对实际现象进行描述的过程。在这一过程中，要以“建”为中心，使学生的创造性思维在“建”的过程中被激发出来。可以建立不同的实际模型来对同一个问题进行解决，从而可以得到不同的“最优解”，所以说，模型的独特之处是建立模型的关键，在数学模型中没有最好，只有更好。 以下是数学模型建立的大致步骤：
第一、模型准备。对问题的实际背景进行了解，使建模的目的得到明确，从而使必要的数据资料被收集、掌握到。
第二、模型假设。提出假设，这些假设必须与客观实际相符合。
第三、模型建立。进行相应的数学模型的建立，以实际问题的特征为依据，决定使用的数学结构、数学工具的类型。通常，以能够达到预期的目的为前提，选择的越简单的数学工具进行建模越好。
第四、模型求解。模型建立者需要对上述过程中获取的数据资料进行利用，计算模型中的参数，对模型进行求解。在必要时，可以使用计算机为辅助工具。
第五、模型分析、检验。对模型的结果在数学分析的基础上与实际情形进行比较，从而对模型的合理性、准确性、适用性进行验证。如果吻合，则进行解释、应用，如果不吻合，则修改、重建。
现实中的问题是错综复杂的，必然的因果关系与偶然的因果关系都存在其中，所以，我们必须将主要原因从杂乱无章的现象中寻找出来，对变量进行确定，并使变量之间的内在联系显现出来。
二、以最优化看待数学建模
数学建模的关键在于一个“建”字，但一旦数学模型建立起来之后，对于它的求解就显得很重要了。一般的数学模型所涉及的问题都是一个最优化问题，即在一些约束的条件下，如何使得模型的解达到最优？一般的数学模型中抽象出来的最优化问题具有如下的形式：
min f （X ） s. t. AX ≥b.
这种问题根据目标函数和约束函数的特点可分为很多类，都是运筹学的分支，如线性规划、非线性规划、图论、目标规划、动态规划问题等等。无论怎样，如果一个数学模型不能用初等的数学理论解决，也不能用常微分方程理论解决的话，那它一定就是用最优化的理论来解决。
最优化理论广泛地应用于管理科学、科学技术和生活实践中，而线性规划问题因为有普遍适用的单纯形法，故而其理论和应用都非常完善。所以目前研究较多的当属非线性规划理论和其它的优化问题。类似于高等数学中一切非线性的函数都尽量对它进行局部线性化的思想使问题简单化，非线性规划问题求解的总体思想也是如此。尽量将非线性规划问题局部线性化来解决。
下面我们再看一个用匈牙利算法求解指派问题的例子。
例：有甲、乙、丙、丁四人完成A 、B 、C 、D 四项任务，他们完成各项任务的时间见右表，问应如何安排，使所需总时间最少？
这类问题一建立模型后，我们应清楚地知道我们遇到了一个指派问题，而求解指派问题的最简单的方法就是匈牙利算法。否则，若不能认识到这一点，用一般的方法建立模型求解，可能会用到求解整数规划的分枝定界法或是求解0-1规划的隐枚举法，那都将是很复杂的。下面我们用匈牙利算法求解：
这样很快得到最优的安排是甲→D 、乙→B 、丙→A 、丁→C 。
以上通过两个简单的例子，我们讨论了求解数学模型的简单方法。数学建模的“建”完成之后，关键一步就是模型的求解，而最优化理论的掌握程度，是否具有厚、博、精的优化理论知识对能否完整地求解，，为实际问题的发展带来突破性。
综上所述，在数学建模和最优化理论之间，二者是相辅相成的关系。生活和实践是数学模型的源泉，在实际生活中，模型将会随着层见叠出的问题而越来越庞大、越来越复杂，因而，最优化理论的发展会不断地在模型的建立过程中挑战、发展。从另外一个角度看，在这个不断得到丰富、完善的最优化理论的影响下，数学模型的求解也会得到不断地促进而越来越优化解决最优化问题已经有很多比较成熟的算法，如遗传算法、神经网络、模拟退
火法等，各有其优劣。模式搜索法作为一种解决最优化问题的直接搜索方法，因为在计算时不需要目标函数的导数，所以在解决不可导或者求导异常麻烦时比较有效。随着模式搜索法的发展，人们在Hooke-Jeeves 模式搜索法 的基础上设计了变步长搜索策略，使得模式搜索方向更接近于 最优下降方向，并且同时采用了插值技术和非单调技术，不仅改善了方法的局部寻优能力，而且改善了方法的收敛性。现在已有很多软件将这一算法集成到程序中， 如Matlab 已经将它 添加到工具箱中，使用时只要调用相应的函数就可以用模式搜 索法解决问题，大大提高了工作效率，降低了编程工作量。
引言
水利工程大部分在山区 位置偏僻, 交通不便, 水、电设施需要在施工前备齐。工程建设过程中需要 的宿舍、办公楼、材料仓库、成品半成品加工场地等 临时工程和辅助设施需要修建。临时工程、辅助设施 科学合理的选址不仅能够减少费用和运行期间材料 运输费用, 大幅度降低运行成本, 而且能为施工生产 部门带来方便、快捷的服务。在考虑施工辅助设施位置布置时, 若地址位置 平面坐( x1,x2) 是以建造费用和运行费用为目标函数的变量, 该函数的导数很难求得, 或者根本不存 在, 利用传统的解析法不能得出解答。模式搜索法的 迭代步骤简单, 收敛速度较快, 可以很方便地得出满 意解。
1 模式搜索法求极值的优化理论
模式搜索法是一种最优化算法当目标函数 f(x1,x2,⋯,xn) 的解析表达式十分复杂甚至写不出具体 表达式、用解析法无法解答时, 它可以方便地求出极 值。求解目标函数极值问题的计算步骤为:
( 1) 任选初始近似点B1, 以它为初始基点进行 探索。
( 2) 为每一独立变量xi( i=1, 2, ⋯, n) 选定步长 缩小到要求的精度时, 即可停止迭代, 确定已找到最优点。
2 模式搜索法优化施工方案
施工某场址平面图和剖面图见图1、图2。现要确定其混凝土生产系统合适的位置, 使修建费用最 少。在场址范围的西南角设置坐标原点, 建立坐标 系统。由于各种线路的长短不同, 以及桩的长短不 同( 桩的最小长度为20m, 差别在于超过20m 以上 的部分) 。因工厂位置不同, 其修建费用就有差别。 2.1 目标函数 列出目标函数即修建总费用C : C( x1,x2) =45x2+9[(5000- x1)2+x2 2]1/2+15[x2 1+(x2- 2000)2]1/2+12[(x1- 200)2+(5600- x2)2]1/2+ 36[(3000- x1)2+(4800- x2)2] 1/2+45×15(x2/100) 地理范围的约束条件为: 0≤x1≤5000; 0≤x2≤6000- (2/5)x1。 2.2 以探索法解算
起点坐标（x1, x2), 采用模式探索法进行解 算。搜索步长定为100m, 即!1=(0,100)。搜索过程及 结果见表1。
从表1 的计算结果可以看到：
无论初始点在最 终结果附( 见表1 中的1 点) , 还是在最终结果的 上、下、左、右见表1 中
的3, 4, 5 点) , 均可以找到最 从表1 的计算结果可以看到, 无论初始点在最 终结果附见表1 中的1 点) , 还是在最终结果的 上、下、左、右( 见表1 中的3, 4, 5 点) , 均可以找到最
表1搜索过程及结果 起点坐标/m x1 x2 1 2 3 5
佳的结果。
即使给出的初始点离最佳点较远, 是一些 极不合理的点( 见表1 中的2 点) , 用模式搜索法同 样可以找出最优位置点。
从以上的计算结果, 可以看 到该方法的合理性和优越性。这说明 用模式搜索法 确定施工场址, 只需给定场址范围, 在简化后的平面 图或剖面图中建立相应坐标系, 找出目标函数( 总费 用) 与纵、横坐标变量的关系, 编制相应程序, 然后给 定一个初始点, 经过一系列的迭代过程, 就能确定出 满足目标函数f(x1,x2)的最优位置。
对于比较复杂的目标函数, 为了防止把局部极 值误认为全局最优值, 应分区域进行探查, 或者从任 意选取的不同点开始, 至少引入两个独立的搜索。如 果它们都收敛于同一点, 则这个点作为最优点的把 握就大大增加了。
3. 结语
施工企业主要建筑物的选址是一个复杂的多目标决策问题, 由于目标间存在矛盾性和不可公开性, 因此, 如何确定主要建筑物的最佳地址是施工总布 置需要认真研究的课题。而通过一定的简化, 建立数 模型, 利用模式搜索法求出最优解是可行的。
数 学 建 模
最 优 化 问 题
最优化问题
摘 要：自从1946年世界上第一台电子数字计算机诞生以来，计算机技术便以一种势不可挡的速度开始发展，与之伴随的是数学的广泛应用，不仅在工程技术、自然科学等等领域，数学的应用发挥着无与伦比的重要作用，并且在广度和深度上还渗透到了新的领域中，如医学、地质、交通灯、经济、生物、环境、人口、金融等等。因而说，在当代高新技术中，数学技术已经成为一个不可替代的重要组成部分。在本文中，笔者对最优化的问题在求解数学模型中的应用做了简要的探讨。
关键词：最优化问题；数学；建模
一、
在体现数学应用的方式中，数学建模是不可忽视的一种
所谓数学建模，指的是以数学语言为工具，对实际现象进行描述的过程。在这一过程中，要以“建”为中心，使学生的创造性思维在“建”的过程中被激发出来。可以建立不同的实际模型来对同一个问题进行解决，从而可以得到不同的“最优解”，所以说，模型的独特之处是建立模型的关键，在数学模型中没有最好，只有更好。 以下是数学模型建立的大致步骤：
第一、模型准备。对问题的实际背景进行了解，使建模的目的得到明确，从而使必要的数据资料被收集、掌握到。
第二、模型假设。提出假设，这些假设必须与客观实际相符合。
第三、模型建立。进行相应的数学模型的建立，以实际问题的特征为依据，决定使用的数学结构、数学工具的类型。通常，以能够达到预期的目的为前提，选择的越简单的数学工具进行建模越好。
第四、模型求解。模型建立者需要对上述过程中获取的数据资料进行利用，计算模型中的参数，对模型进行求解。在必要时，可以使用计算机为辅助工具。
第五、模型分析、检验。对模型的结果在数学分析的基础上与实际情形进行比较，从而对模型的合理性、准确性、适用性进行验证。如果吻合，则进行解释、应用，如果不吻合，则修改、重建。
现实中的问题是错综复杂的，必然的因果关系与偶然的因果关系都存在其中，所以，我们必须将主要原因从杂乱无章的现象中寻找出来，对变量进行确定，并使变量之间的内在联系显现出来。
二、以最优化看待数学建模
数学建模的关键在于一个“建”字，但一旦数学模型建立起来之后，对于它的求解就显得很重要了。一般的数学模型所涉及的问题都是一个最优化问题，即在一些约束的条件下，如何使得模型的解达到最优？一般的数学模型中抽象出来的最优化问题具有如下的形式：
min f （X ） s. t. AX ≥b.
这种问题根据目标函数和约束函数的特点可分为很多类，都是运筹学的分支，如线性规划、非线性规划、图论、目标规划、动态规划问题等等。无论怎样，如果一个数学模型不能用初等的数学理论解决，也不能用常微分方程理论解决的话，那它一定就是用最优化的理论来解决。
最优化理论广泛地应用于管理科学、科学技术和生活实践中，而线性规划问题因为有普遍适用的单纯形法，故而其理论和应用都非常完善。所以目前研究较多的当属非线性规划理论和其它的优化问题。类似于高等数学中一切非线性的函数都尽量对它进行局部线性化的思想使问题简单化，非线性规划问题求解的总体思想也是如此。尽量将非线性规划问题局部线性化来解决。
下面我们再看一个用匈牙利算法求解指派问题的例子。
例：有甲、乙、丙、丁四人完成A 、B 、C 、D 四项任务，他们完成各项任务的时间见右表，问应如何安排，使所需总时间最少？
这类问题一建立模型后，我们应清楚地知道我们遇到了一个指派问题，而求解指派问题的最简单的方法就是匈牙利算法。否则，若不能认识到这一点，用一般的方法建立模型求解，可能会用到求解整数规划的分枝定界法或是求解0-1规划的隐枚举法，那都将是很复杂的。下面我们用匈牙利算法求解：
这样很快得到最优的安排是甲→D 、乙→B 、丙→A 、丁→C 。
以上通过两个简单的例子，我们讨论了求解数学模型的简单方法。数学建模的“建”完成之后，关键一步就是模型的求解，而最优化理论的掌握程度，是否具有厚、博、精的优化理论知识对能否完整地求解，，为实际问题的发展带来突破性。
综上所述，在数学建模和最优化理论之间，二者是相辅相成的关系。生活和实践是数学模型的源泉，在实际生活中，模型将会随着层见叠出的问题而越来越庞大、越来越复杂，因而，最优化理论的发展会不断地在模型的建立过程中挑战、发展。从另外一个角度看，在这个不断得到丰富、完善的最优化理论的影响下，数学模型的求解也会得到不断地促进而越来越优化解决最优化问题已经有很多比较成熟的算法，如遗传算法、神经网络、模拟退
火法等，各有其优劣。模式搜索法作为一种解决最优化问题的直接搜索方法，因为在计算时不需要目标函数的导数，所以在解决不可导或者求导异常麻烦时比较有效。随着模式搜索法的发展，人们在Hooke-Jeeves 模式搜索法 的基础上设计了变步长搜索策略，使得模式搜索方向更接近于 最优下降方向，并且同时采用了插值技术和非单调技术，不仅改善了方法的局部寻优能力，而且改善了方法的收敛性。现在已有很多软件将这一算法集成到程序中， 如Matlab 已经将它 添加到工具箱中，使用时只要调用相应的函数就可以用模式搜 索法解决问题，大大提高了工作效率，降低了编程工作量。
引言
水利工程大部分在山区 位置偏僻, 交通不便, 水、电设施需要在施工前备齐。工程建设过程中需要 的宿舍、办公楼、材料仓库、成品半成品加工场地等 临时工程和辅助设施需要修建。临时工程、辅助设施 科学合理的选址不仅能够减少费用和运行期间材料 运输费用, 大幅度降低运行成本, 而且能为施工生产 部门带来方便、快捷的服务。在考虑施工辅助设施位置布置时, 若地址位置 平面坐( x1,x2) 是以建造费用和运行费用为目标函数的变量, 该函数的导数很难求得, 或者根本不存 在, 利用传统的解析法不能得出解答。模式搜索法的 迭代步骤简单, 收敛速度较快, 可以很方便地得出满 意解。
1 模式搜索法求极值的优化理论
模式搜索法是一种最优化算法当目标函数 f(x1,x2,⋯,xn) 的解析表达式十分复杂甚至写不出具体 表达式、用解析法无法解答时, 它可以方便地求出极 值。求解目标函数极值问题的计算步骤为:
( 1) 任选初始近似点B1, 以它为初始基点进行 探索。
( 2) 为每一独立变量xi( i=1, 2, ⋯, n) 选定步长 缩小到要求的精度时, 即可停止迭代, 确定已找到最优点。
2 模式搜索法优化施工方案
施工某场址平面图和剖面图见图1、图2。现要确定其混凝土生产系统合适的位置, 使修建费用最 少。在场址范围的西南角设置坐标原点, 建立坐标 系统。由于各种线路的长短不同, 以及桩的长短不 同( 桩的最小长度为20m, 差别在于超过20m 以上 的部分) 。因工厂位置不同, 其修建费用就有差别。 2.1 目标函数 列出目标函数即修建总费用C : C( x1,x2) =45x2+9[(5000- x1)2+x2 2]1/2+15[x2 1+(x2- 2000)2]1/2+12[(x1- 200)2+(5600- x2)2]1/2+ 36[(3000- x1)2+(4800- x2)2] 1/2+45×15(x2/100) 地理范围的约束条件为: 0≤x1≤5000; 0≤x2≤6000- (2/5)x1。 2.2 以探索法解算
起点坐标（x1, x2), 采用模式探索法进行解 算。搜索步长定为100m, 即!1=(0,100)。搜索过程及 结果见表1。
从表1 的计算结果可以看到：
无论初始点在最 终结果附( 见表1 中的1 点) , 还是在最终结果的 上、下、左、右见表1 中
的3, 4, 5 点) , 均可以找到最 从表1 的计算结果可以看到, 无论初始点在最 终结果附见表1 中的1 点) , 还是在最终结果的 上、下、左、右( 见表1 中的3, 4, 5 点) , 均可以找到最
表1搜索过程及结果 起点坐标/m x1 x2 1 2 3 5
佳的结果。
即使给出的初始点离最佳点较远, 是一些 极不合理的点( 见表1 中的2 点) , 用模式搜索法同 样可以找出最优位置点。
从以上的计算结果, 可以看 到该方法的合理性和优越性。这说明 用模式搜索法 确定施工场址, 只需给定场址范围, 在简化后的平面 图或剖面图中建立相应坐标系, 找出目标函数( 总费 用) 与纵、横坐标变量的关系, 编制相应程序, 然后给 定一个初始点, 经过一系列的迭代过程, 就能确定出 满足目标函数f(x1,x2)的最优位置。
对于比较复杂的目标函数, 为了防止把局部极 值误认为全局最优值, 应分区域进行探查, 或者从任 意选取的不同点开始, 至少引入两个独立的搜索。如 果它们都收敛于同一点, 则这个点作为最优点的把 握就大大增加了。
3. 结语
施工企业主要建筑物的选址是一个复杂的多目标决策问题, 由于目标间存在矛盾性和不可公开性, 因此, 如何确定主要建筑物的最佳地址是施工总布 置需要认真研究的课题。而通过一定的简化, 建立数 模型, 利用模式搜索法求出最优解是可行的。