运筹学–一门建模、优化、决策的科学

本硕博横跨三个专业,从应用数学到运筹学(Operations Research)再到人工智能(计算机视觉)。目前在海德堡大学计算机系任助教,师从旅行商问题(Traveling salesman problem)开源数据集TSPLIB创作者全球著名组合优化学者Gerhard Reinelt教授。虽然目前研究课题更偏向人工智能、数据科学以及计算机视觉,但内心深处一直坚定的认为 “I am an OR-er”。

可能很多读者朋友今天是第一次听到运筹学这个术语,但其实高中代数的课堂你早已与她幽会过(见4)。

由于运筹学在国内的欠普及(比起统计等),一直想提笔给自己的专业写个专栏,也算是为自己深爱的领域做一点普及的工作。但由于种种原因,迟迟没能动笔。今天上网搜各中科院与运筹相关的教授和研究员,偶然发现这么一篇运筹学的科普论文,读了挺有感触,因此决定动笔写下本专栏的第一文。

本文小部分内容参考了以下链接:

运筹学–中国科学院院刊

本文提纲: 1,什么是运筹学 2,运筹学有哪些应用 3,运筹学学科、专业 4,运筹学的分支 5,运筹学的就业 6,运筹学与人工智能、大数据的关联

注:以下文中黑体字代表其在学术界的术语

1,什么是运筹学

运筹学是20世纪三四十年代发展起来的一门新兴交叉学科。它主要研究人类对各种资源的运用及筹划,在满足一定约束的条件下,以期发挥有限资源的最大效益,达到总体最优的目标--所谓运筹帷幄。最初由钱学森老先生引入中国,据说最开始的用途是优化航空/军工等领域。

例如:我们用的导航软件,从一地到另一地的最短路径问题,就是一个典型的运筹学问题。该问题目标是找到最短的驾驶路径 (或驾驶时间最短的路径),约束条件往往有单行路段以及每条路段的限速等等(都可以写成严格的数学表达式)。

它的几个“别名”: 数学规划 (math programming)、 优化 (optimization)、 最优化理论 等。

2,运筹学有哪些应用

运筹学传统或最流行的应用领域,包括:

之前说的 路径优化问题 (Routing Problem)–交通领域(GPS导航);

仓储、运输等 物流 (Logistics)以及供应链(Supply chain)领域;

制造业里的 生产流程优化 (Process Optimization);

电力领域的电网的布局以及分配( Power Grid );

电子工程里的设施 部件分配 问题( Facility Layout Problem);

能源领域的优化,如:如何铺设输油管道;

火车、课程、飞机时刻表安排问题等 调度问题 (Scheduling Problem);

资产配置 (Asset Allocation)、 风险控制 (risk management)等经济金融领域的应用;

作为优化或运筹学模型,在其他各个学科的应用,如统计、生物、博弈论、压缩感知(近十年很火)、稀疏问题、人工智能(能量函数能量最小化)等等;

综上所述,运筹学里的优化模型作为数学建模里的一种模型,在各个领域被广泛应用(没错,学好运筹学 数学建模竞赛 可以玩得很溜);运筹学里的优化算法作为数值解决各类优化问题的关键,应用更为广泛,例如统计模型最后基本归结为求解一个优化问题(如最大似然估计)。

简单地说:凡是有“最”字,如:利润最大化、成本最小化,基本就和运筹学息息相关。

3,运筹学学科、专业

运筹学在国内属于“ 运筹学与控制论 ”学科。常见的设置运筹学相关课程或专业的院系如下:

数学系 运筹学 专业–(非)线性规划,整数规划,多目标优化,最优化理论等;

工商管理学院(School of Management) 管理科学 (Management Science)与工程专业–管理决策、供应链等;

工程学院 工业工程 (Industrial Engineering)、 物流工程 专业–生产流程优化、物流、运输等;

计算机学院 理论计算机 专业–偏算法方向,近似算法、遗传算法等;

另外电子工程,通信,化工,自动化等专业往往也会开 凸优化数值优化( Numerical Optimization)等课程。

4,运筹学的分支


线性规划 (Linear Programming)– 最简单和基础的优化问题,如上图, 目标函数 (max)和 约束条件 (s.t.)都是线性的,自变量x是实数变量,P问题(多项式时间可解);或许有些读者没有学过线性代数,更简单的例子: min x1+x2 s.t. 3×1-4×2> 5, x1,x2>=0。

非线性规划 (Nonlinear Programming)–目标函数或约束条件为非线性,例如2次函数;

凸优化 (Convex Optimization)–约束条件形成的可行域(feasible region)是凸的;

(混合)整数规划 (Mixed Integer Programming)–自变量有整数变量,NP难问题(指数级算法复杂度)。目前据作者所知,这个专业出身的在大陆的学者非常稀少,如果读者有知道中国国内有研究这个方向的教授,请在评论区留下姓名和机构,万分感谢;

半正定规划 (Semi-definite Programming)–每一个自变量x代表一个矩阵;

网络流问题 (Network Flow Problems)–一个特殊的混合整数规划问题,满足一个节点流出流量=流入流(或许你听说过最大流最小割定理);

动态规划 (Dynamic Programming)、 近似算法 (Approximation Algorithms) 启发式算法 (Heuristic Algorithms)、 遗传算法 (Generic Algorithms)–用来解例如整数规划等NP难优化问题的算法,后俩个通常只能得到局部最优解,最经典的当属最大流最小割定理衍生出来的一些最大流算法(全局最优)。被广泛得用在各个学科和领域,如人工智能;

有哪些数学定理或者数学知识惊呆了你? – Ruobing Shen 的回答 – 知乎

鲁棒优化 (Robust Optimization)–目标函数或约束条件有扰动的情况下,求解其最坏情况下的最优解;

多目标优化 (Muti-objective Optimization)–优化的目标函数是一个向量,通常通过引入权重权衡个目标函数,转化成单目标优化,或者寻找 帕累托最优 (Pareto Optimality) ;

双层优化 (Bilevel Optimization)–和复合函数的概念类似,比如Max-Min Problem,在一个优化问题外嵌套另一个优化问题,通常用迭代法;

随机优化 (Stochastic Programming)–加入了不确定的因素(通常以概率形式表现,目标函数变成求期望最大化);

最优控制

(Optimal Control)–,目标函数是最优一个带时间变量t的函数,约束条件有偏微分方程。

最优控制 (Optimal Control):严格说属于控制论的范畴,可以简单地把它理解为,优化问题中的变量由x变为f(x),并且通常f是时间t的函数,约束条件常有偏微分方程。也就是说,控制论期望通过解一个优化问题,得到一个最优的函数f(t),使得这个函数在全局(空间+时间)上是最优的。而运筹学通过解一个优化问题,得到的是最优解x,使得目标函数在一个确定性(deterministic,通常与t无关,或者可以理解为在t的某一时刻)的环境下是最优的。

说了这么多运筹学术语,是不是觉得很玄乎?其实大家早在高中代数课堂就已接触过运筹学,只是大家不知道罢了。下图是不是很熟悉?三条实现代表三个不等式,虚线代表目标函数,然后我们在三角形阴影区域的三个顶点衡量,比划出最优解。


5,运筹学的就业

根据2所述的应用领域,这里简单举几个例子:

滴滴算法工程师(高精尖高薪)–车辆路径规划及叫车资源匹配和调度;

顺丰、京东物流工程师(高精尖高薪)–仓储问题、快递寄送问题;

投资银行、大型企业工程师–资产配置、成本优化、利润最大化;

国家电网、中石油技术工程师–电力调度、石油管道最优化铺设;

铁路、航空公司–时刻表安排、定价策略、航班安排;

国家铁路局、交通局等公务员–如上;

以上这些,本质上都在最小化成本和支出,例如铺设输油管道,选择好的铺设路线和策略,可以节省几个百分点的成本,那是巨额的资金。

大学教授、研究所研究员–运筹学出身的学者,中国紧缺;

人工智能相关领域–数据科学家、算法工程师、定量分析师、google等IT企业的研究科学家等。

国内(全球)TOP互联网公司、学术界超高薪的揽才计划有哪些? – Ruobing Shen 的回答 – 知乎

6,运筹学与大数据、 人工智能 的关联

大数据:不妨简单地把大数据理解为变量个数非常大的应用题。那么统计和优化问题,自然而然地属于大数据问题。

想学数据分析(人工智能)需要学哪些课程? – Ruobing Shen 的回答 – 知乎

统计推断里最经典的线性回归问题(如下图,给定一堆蓝点(x,y)“大数据”,加上线性假设,要求预测下一个给定点x的坐标值y--典型的大数据和人工智能问题),不妨把它看作一个无约束的二次规划问题,min: sum_(ax_i+b-y_i)^2, 由于无约束,因此可以算得其解析解(a,b);


统计里的最大似然估计,根据2里的“最”字原则,自然是一个运筹(优化)问题。从这点上,运筹模型比起统计的模型更加灵活,因为可以根据需要加上约束条件,目标函数也可以随意调整。

关于人工智能,大家可能不知道,当下最热的神经网络、深度学习,其最终的问题,还是落到了解决一个优化问题。神经网络最基础的优化算法-- 反向传播 (BP)算法,可以纳入启发式算法或贪婪算法的行列。而搭建起神经网络的一个个神经元和他们的连线,则是数学建模的过程,用的正是图模型。

机器学习中最经典的支持向量机模型,本质是一个非线性(二次、凸)规划的问题;网络流设计问题(整数规划)被广泛应用在视频追踪领域。

详细说一个计算机视觉领域我博士论文相关的–图像分割问题。由于涉及到太多理论知识和背景,这里简单论述,后续专栏会为此专门写一篇。

这里我把一张m*n(这里3*3=9)像素的图像看作m*n个node的图(图论术语里的图),并且把上下左右相邻的点用边连接起来,组成edge(图论里的边)。这么一来,图像分割问题就完美地转换成了一个基于图论(或者network flow)的优化问题。如下图,九个像素的图被最大流最小割算法用绿线分割成了俩个部分(segment),这里s点和t点是为了构建网络流模型额外增加的俩个点。


7, 运筹学在中国–展望

很多人看这篇专栏前听说过统计,微分方程,但是没有听说过运筹,或者不知道运筹学是干啥的。确实,这是运筹学在中国的现状。老实说我本科所在学校运筹学(数学系下)全国前三,但我本科一门运筹学相关的课都没有学过(那时候有同学选修线性规划,完全不知道它属于运筹学)。第一次听说运筹学还是到了美国。

运筹学由于其分支的庞大(很少有运筹学专业或运筹系,更多地被作为工具或模型应用在其他领域),运筹学博士毕业的学者大量地分散在商学院、工程学院、计算机学院、数学院,因此各学院下的学生接触到的运筹学很有可能只是其中的一瞥。这里给大家推荐几个全球运筹中心(其实只要搜索运筹学排名,排名较高通常体量较大,20+运筹出身的教授):佐治亚理工工程学院、CMU商学院、斯坦福工程学院、MIT ORC系、哈佛商学院、加州伯克利、哥大、康奈尔大学、明尼苏达大学、弗罗里达大学、威斯康星曼迪逊、密歇根大学、KU鲁汶、ZIB柏林、加拿大蒙特利尔HEC等等。中国的中心:中国科学院数学与系统科学研究院、北京大学、清华数学系与工业工程系、南开大学计算机与控制工程学院、复旦数学院、上交、上海交大、浙大管院、南大数学系管院、山东大学数学院、川大管院、吉大数学院运筹系、上海大学数学系、中科大管院、西安交大商学院、上海财大。

希望这个系列的专栏,可以为运筹学在中国的普及,起到一点推动的作用。后续将更多地和大家聊聊运筹学在当下最热地人工智能、大数据等领域扮演着何等重要的角色。

如果你的想法和我一样,或者这篇专栏给你带来了普及效果,请不要吝惜您的“赞”。

注:记忆常有偏差,如细心的读者发现文中任何信息上的偏差或遗漏,敬请指出。

最后按照惯例广告一波:

欧洲、北美、全球留学及人工智能、数据科学深度私人咨询,从此DIY – 知乎专栏

运筹帷幄稿源:运筹帷幄 (源链) | 关于 | 阅读提示

本站遵循[CC BY-NC-SA 4.0]。如您有版权、意见投诉等问题,请通过eMail联系我们处理。
酷辣虫 » 综合技术 » 运筹学–一门建模、优化、决策的科学

喜欢 (0)or分享给?

专业 x 专注 x 聚合 x 分享 CC BY-NC-SA 4.0

使用声明 | 英豪名录