原文标题:什么是优化技术?给算法小白同学的快速讲解和上手文
原文作者:阿里云开发者
冷月清谈:
-
优化问题定义: 解释优化问题和优化求解器的概念,并以鸡兔同笼问题为例进行说明。
-
快速理解优化: 将优化问题类比解方程组,并通过线性规划的例子进行解释。
-
拓展思路: 涵盖优化问题在电商广告投放、人力资源福利安排等场景的应用,以及线性、非线性、连续变量、整数变量等不同问题类型。
-
优化问题的应用: 介绍优化技术在多个领域的应用,并推荐阿里达摩院求解器的案例广场。
-
优化问题的求解: 讲解常用的求解方法 (单纯形法、内点法等),并比较国内外 (MindOpt, CPLEX, Gurobi等) 优化求解器软件的优劣。
-
优化技术使用难点: 分析优化技术应用中的难点,并推荐使用MindOpt Copilot等工具进行辅助。
怜星夜思:
2、优化问题涉及到很多数学知识,对于数学基础薄弱的人来说,该如何学习和应用优化技术呢?
3、优化技术在各个领域都有广泛的应用,你认为未来它会朝着哪些方向发展?
原文内容
阿里妹导读
背景
一、术语定义
二、快速get理解优化是什么
引用说明:下面的公式均来自 MindOpt新发布的基于大模型的“AI工程师”MindOpt Copilot 生成的内容截图,或者案例广场公开内容截图。大家也可以进去聊天生成自己需要的示例公式和代码。
2.1 方程:一个鸡兔同笼问题
有一笼兔子和鸡,兔子和鸡各有一个头,兔子有4只脚,鸡有两只脚。笼子上有 35 个头,下有94 个脚。请问兔子和鸡的数目各是多少?
这个时候算出来的结果是:
- 兔子的数量x=12
2.2 不等式方程组+目标函数:
鸡兔同笼问题的优化问题
有一笼兔子和鸡,兔子和鸡各有一个头,兔子有4只脚,鸡有两只脚。笼子上有头至少有30个,下面脚至多80个。要想兔子最多,请问最多有多少个兔子?
-
对应的数学公式的约束就是个不等式的关系:最多,最少。subject to 就是约束的意思,有时会写成 st.。
-
增加了目标,想要兔子最多。对应 maximize x,也就是优化的目标函数 f = x,优化方向是最大化。
-
如果只考虑不等式的约束,解可能就是个域(有多种解、多个可行域)。比如 x=1,y=29; x=3,y=29; x=3, y= 30……等等;
-
增加了要将x最大化这个目标,就相当于在这个域里面找最大值。这个时候可以利用优化求解器进行计算,得出最优目标时候的变量取值,如下:
- 兔子的数量 x=10,
![图片](https://xinfinite3.cedu.ac.cn/original/3X/e/9/e9be758dedbb1870d7cb613cde284d2406a47761.png)
三、拓展思路
3.1 拓展应用场景
例1. 电商互联网常见的广告资源的安排:
电商平台要为一家新兴手游公司进行广告推广,平台有两种广告类型可供选择:类型A、类型B、类型C。广告类型A的转化率为5%,每投放一次费用为10元;广告类型B的转化率为8%,每投放一次费用为15元; 广告类型B的转化率为7.7%,每投放一次费用为12元。手游公司需要至少获得1000次投放,并且总费用不能超过20000元。每种类型广告都希望至少投放5次。平台希望最大化累计转化数,要如何规划广告投放?
广告类型A投放次数=5
广告类型B投放次数=6广告类型C投放次数=1655- 目标函数值 = 128.165为了最大化累计转化数,电商平台应该投放5次类型A的广告(每次转化率为5%,每次费用为10元),6次类型B的广告(每次转化率为8%,每次费用为15元),以及1655次类型C的广告(每次转化率为7.7%,每次费用为12元)。此时,累计转化数最大,为128.165次。
假设一家公司想要给每位员工至少提供以下三种福利中的一种:健身房、健康保险和午餐补贴。给每个员工提供使用健身房需支付50元,健康保险需支付20元,午餐补贴需支付15元。公司有100名员工,每天福利投入的成本上限是4000。公司希望最小化支出,同时尽可能多地为员工提供福利,每种福利至少有30份。该如何规划福利?
提供健身房福利的员工人数=30
提供健康保险福利的员工人数=30提供午餐补贴福利的员工人数=40- 目标函数值 = 2700为了最小化福利支出,同时尽可能多地为员工提供福利,公司应该为30位员工提供健身房福利(每人每天成本50元),为30位员工提供健康保险福利(每人每天成本20元),并为40位员工提供午餐补贴福利(每人每天成本15元)。这样,每天的福利支出最低,为2700元。
3.2 拓展问题维度和类型
![图片](https://xinfinite3.cedu.ac.cn/original/3X/e/a/ea1cd981d9c478ac773ac7254b680fe2576fc8cc.png)
-
线性、非线性:优化问题里面常说的“线性”就是一次关系,y =3x就是一次的,线性关系。y = 4 *x*x 就是二次的,属于非线性关系。当前大部分优化问题是着重处理线性关系和二次关系,再高次就不好解了。
-
连续变量、整数变量:变量x的取值类型。如果有的变量只能是整数,不能是小数,或者说是“离散的”。与之相对的是“连续的”。离散的问题优化起来会方法不一样,会变困难,因此经常有问题需要松弛下,使得变为连续的。
-
问题 “凸” 和 “非凸”。凸优化是个研究生课程,比较难。普通人需要掌握凸问题更好求解,非凸不好求解。因此列数学公式描述业务问题时,尽量避免非凸的情况。比如尽量是线性的关系。多次的关系很容易出现非凸的情况。
3.3 更丰富的优化问题类型列表
-
线性规划,英文是Linear Programming,简称LP,对应的数学目标函数是线性关系;
-
如果加上变量有些是整数(integer),则组合成MILP(Mixed Integer Programming),混合整数的线性规划问题;
-
如果目标里面有二次项,则称为二次规划 QP(Quadratic Programming);
-
如果约束里面有二次项,则称为二次约束规划 QC (Quadratic Constraint),组合还有QCQP;
-
再进一步的根据目标约束的类型,还可以进一步分类描述不同类型的问题,很多种;
-
再进一步,根据问题的优化计算方式,还可以取名字,比如零阶优化、黑盒优化、梯度下降、无梯度优化等;
四、优化问题的应用
仓库选址规划
|
|
虚拟电厂的智能调度
|
|
网络流问题:交通调度、仓储运输
|
![]() |
人员排班问题
|
|
数独问题的求解
|
|
广告流量分配:曝光与转换均衡
|
五、优化问题的求解计算
5.1 计算方法
- 是否能求解
- 求解速度
- 稳定性
- 大规模问题求解能力和计算资源占用
5.2 有哪些软件可选?
国际上
-
CPLEX:美国/IBM。网址:https://www.ibm.com/cn-zh/products/ilog-cplex-optimization-studio。 IBM的老牌产品,历史悠久,企业用户多。现在研发团队维护少了,对于时效要求高的场景可能不支持。
-
Gurobi:美国/Gurobi。网址:https://www.gurobi.com。当前世界顶尖的求解器,部分成员曾任职CPLEX,MILP的性能国际第一。费用比较贵,大约几十万/1年/1并发。
-
Xpress:加拿大/FICO。网址:https://www.fico.com/en/products/fico-xpress-optimization
-
Mosek:丹麦/Mosek。网址:https://www.mosek.com
-
LocalSolver:法国/LocalSolver。网址:https://www.localsolver.com/
-
LINGO:美国/LINDO。网址:https://www.lindo.com/index.php/products/lingo-and-optimization-modeling
-
COIN-OR:开源组织,收录了很多种不同的开源求解器。网址:https://www.coin-or.org
-
SCIP:开源的求解器。网址:https://www.scipopt.org
-
GLPK:开源的求解器。网址:https://www.gnu.org/software/glpk
国产的:MindOpt,阿里的求解器
-
MindOpt:中国/阿里达摩院。
-
当前支持:
-
LP、MILP、CQP、SDP这些数学规划求解。可下载使用。网址:https://opt.aliyun.com 。根据网页指引,直接在阿里云产品平台https://help.aliyun.com/document_detail/298275.html 下载软件和获取免费License。
-
仿真优化 (零阶优化、黑盒优化,可用于调参),未公开下载,需要联系 @有悠。
-
新手推荐用MindOpt线上的平台,不需要安装直接先学会使用,Notebook中直接码代码,上手学习更快捷。还有自研的代数建模语言、以及AI技术结合开发、大模型技术结合自动建模和码代码的方案,更贴合现代的AI+运筹结合的技术趋势。
-
COPT:中国/杉数。网址:https://www.shanshu.ai/copt 。根据页面指引填写信息申请安装包和License。国内研发的早的公司,求解效果不错。
-
这个功能和阿里的求解器MindOpt差异不大,目前主要优势是数学规划的求解能力全一些。可以提需求给MindOpt研发团队做针对性调优。
-
而且,用MindOpt APL建模语言编程,是可以轻松一行代码就换调用COPT的!不用纠结一开始选谁家的。
电力能源领域,这个问题规模非常大,海外求解器已经搞不定的行业。
MindOpt通过项目合作定制调优,整体最优。友商结果并没有我们优秀。
5.3 其他求解方法
六、优化技术使用难点、推荐上手方案
方案征集
-
定价问题 (建模,在线/离线计算求解)
-
排班问题(问题、建模、求解)