数模干货|优化问题的常见算法总结

标签: 建模 算法 数模竞赛

社区小助手 2023-05-06 17:08:02

      “优化”是生活中经常使用的词:开车时希望能在安全的前提下以最短时间到达目的地;双11做功课考虑各种优惠活动,希望获得最大优惠;超市进货时需要考虑动销存,最大化提高物品周转效率。 这些问题都是“最优化问题”,也是数学建模中的典型问题,是各大数学建模比赛里的常客。


      优化题型有三要素:决策变量、目标函数、约束条件。

      (1)决策变量:是决策者可以控制的因素,例如根据不同的实际问题,决策变量可以选为产品的产量、物资的运量及工作的天数等。

      (2) 目标函数:是以函数形式来表示决策者追求的目标。例如目标可以是利润最大或成本最小等。

      (3) 约束条件:是决策变量需要满足的限定条件。


      历年国赛优化问题:

国赛.png


      优化问题的出发点是系统思维,其基本思路是在一定的约束条件下,保证各方面资源的合理分配, 最大限度地提升系统某一性能或系统整体性能,最终实现最理想结果。对于这类问题,想要建立并求解数学模型,可以参考以下思路:

      (1)明确目标,分析问题背景,确定约束条件,搜集全面的客观数据和信息。

      (2)建立数学模型,构建变量之间的数学关系,设立目标函数。

      (3)分析数学模型,综合选择最适合该模型的优化方法。

      (4)求解模型,通常借助计算机和数学分析软件完成。

      (5)对最优解进行检验和实施。


      PS.北太天元内已有优化工具箱optimization,可以调用工具箱解决优化类问题。

工具箱.PNG


      下面给大家分享几种数学建模中常用优化算法:


      1、线性规划

      在人们的生产实践中,经常会遇到如何利用现有资源来安排生产,以取得最大经济效益的问题。此类问题构成了运筹学的一个重要分支—数学规划,而线性规划(Linear Programming 简记 LP)则是数学规划的一个重要分支。

      1.1 用北太天元求解线性规划问题

      北太天元内已有优化工具箱optimization,其中的linprog等相关函数可用于求解线性规划问题。

linprog.png

      1.2 线性规划特点

      优点:

      (1)作为经营管理决策中的数学手段,在现代决策中的应用非常广泛。

      (2)有统一算法,任何线性规划问题都能求解,解决多变量最优决策的方法。

      (3)训练速度快。

      (4)预测速度快,可以推广到非常大的数据集,对稀疏数据也很有效。

      缺点:

      (1)对于数据的准确性要求高,只能对线性的问题进行规划约束,而且计算量大。

      1.3 相关问题

      运输问题(产销平衡)、指派问题(匈牙利算法)、对偶理论与灵敏度分析、投资的收益和风险。


      2、整数规划

      规划中的变量(部分或全部)限制为整数时,称为整数规划。若在线性规划模型中,变量限制为整数,则称为整数线性规划。目前所流行的求解整数规划的方法,往往只适用于整数线性规划。目前还没有一种方法能有效地求解一切整数规划。

      2.1 用北太天元求解线性混合整数规划问题

      可在北太天元内调用优化工具箱optimization,使用intlinprog等相关函数求解线性混合整数规划问题。

image.png

      2.2 整数规划的分类

      如不加特殊说明,一般指整数线性规划。对于整数线性规划模型大致可分为两类:

      (1)变量全限制为整数时,称纯(完全)整数规划。

      (2)变量部分限制为整数的,称混合整数规划。

      2.3 整数规划特点

      原线性规划有最优解,当自变量限制为整数后,其整数规划解出现下述情况:

      (1)原线性规划最优解全是整数,则整数规划最优解与线性规划最优解一致。

      (2)整数规划无可行解。

      (3)有可行解(当然就存在最优解),但最优解值变差。

      整数规划最优解不能按照实数最优解简单取整而获得。

      2.4 求解方法分类

      (1)分枝定界法—可求纯或混合整数线性规划。

      (2)割平面法—可求纯或混合整数线性规划。

      (3)隐枚举法—求解“0-1”整数规划:过滤隐枚举法;分枝隐枚举法。

      (4)匈牙利法—解决指派问题(“0-1”规划特殊情形)。

      (5)蒙特卡洛法—求解各种类型规划。


      3、非线性规划

      如果目标函数或约束条件中包含非线性函数,就称这种规划问题为非线性规划问题。一般说来,解非线性规划要比解线性规划问题困难得多。而且,也不象线性规划有单纯形法这一通用方法,非线性规划目前还没有适于各种问题的一般算法,各个方法都有自己特定的适用范围。

      3.1 线性规划与非线性规划的区别

      如果线性规划的最优解存在,其最优解只能在其可行域的边界上达到(特别是可行域的顶点上达到);而非线性规划的最优解(如果最优解存在)则可能在其可行域的任意一点达到。

      3.2 相关问题

      无约束问题(一维搜索方法、二次插值法、无约束极值问题的解法)、约束极值问题(二次规划、罚函数法)、飞行管理问题


      4、动态规划

      动态规划(dynamic programming)是运筹学的一个分支,是求解决策过程(decisionprocess)最优化的数学方法。例如最短路线、库存管理、资源分配、设备更新、排序、装载等问题,用动态规划方法比用其它方法求解更为方便。

      虽然动态规划主要用于求解以时间划分阶段的动态过程的优化问题,但是一些与时间无关的静态规划(如线性规划、非线性规划),只要人为地引进时间因素,把它视为多阶段决策过程,也可以用动态规划方法方便地求解。应指出,动态规划是求解某类问题的一种方法,是考察问题的一种途径,而不是一种特殊算法(如线性规划是一种算法)。因而,它不象线性规划那样有一个标准的数学表达式和明确定义的一组规则,而必须对具体问题进行具体分析处理。因此,在学习时,除了要对基本概念和方法正确理解外,应以丰富的想象力去建立模型,用创造性的技巧去求解。


      5、多目标规划

      多目标规划已经应用到科学的许多领域,包括工程、经济和物流,在两个或更多冲突的目标之间存在取舍时,需要采取最优决策。

      解决多目标规划问题的方法:

      (1)将多目标化为单目标 (给多个目标赋予权重)

      (2)保持多目标不变,根据自己的偏好选择解

      实际问题中,目标函数相互冲突是很常见的,例如购买汽车时,要求花费少且舒适度高或者要求性能好油耗低,这种问题并没有绝对最优解(因为并没有确定多个目标的权值),但是我们可以根据自己的需要选择一个相对好的(达到我们想要的最佳平衡)。为了寻求这种“最佳平衡”,可以采用算法帕累托最优(Pareto optimal)。


      以上部分内容引用公众号“科研交流”,希望对大家有帮助,觉得有用就点个赞吧。小助手会不定期更新数学建模干货,可以多多关注哟。

3456 0 1 收藏 回复

回复

回复

重置 提交