2023-07-22 16:31

关注

运筹优化：一门决策的科学

引子

作为算法工程师中的小众路线，运筹优化还没有像搜、广、推、ML、CV、NLP那般广为人知。22年秋招，一众互联网大厂中仅有阿里、美团、京东大量设立了专门面向运筹优化工程师的算法岗位。所以呢，常常有其他方向的同学问我：“运筹优化是什么？运筹优化工程师都做些什么？”

简单来说，运筹优化是一门研究“决策（decision making）”的科学，运筹优化工程师要做的事情就是通过各种数学工具帮助业务在所有可能的方案中做出最佳的决策。

无论决策的对象是今天的晚餐吃什么、下班走什么路线回家，还是这个月的工资买哪些理财产品，又或者今年的采购预算如何分配给各种服务器机型，这些都属于运筹优化的范畴。那么，运筹优化工程师们是如何研究这些问题并做出决策的呢？以“晚上吃什么”的决策为例，接下来让我们更深入地去了解运筹优化。

“字节食堂的轻食窗口提供了酱牛肉、香熏鸡肉、土豆泥、圣女果、胡萝卜、玉米粒、水煮蛋 🤤，我该怎么吃才能既营养又健康呢？”

运筹优化如何研究决策

“运筹优化”是由两个词组合而成的术语：“运筹”和“优化”（废话😅）。其中，前者是决策研究的核心方法论，后者是决策研究的主要技术手段，具体说明如下。

运筹

“运筹”，取自运筹学（Operations Research，简称OR），指“在满足限制条件的情况下找到最佳化给定目标的决策方案”，涉及统计、仿真、数学建模、数学规划、动态规划、博弈论、排队论等理论，是一门广义的学科。

一般而言，通过运筹进行决策的方法论包含统计、建模、求解等关键步骤。其中，“统计”为决策提供数据支持，“建模”将自然语言描述的决策需求转换为数学语言描述的数学问题，“求解”是通过合适的算法找到数值量化描述的最佳决策方案。上述作用关系如下图所示。

WX20230722-140726@2x.png

对于“晚上怎么吃才能健康又营养”的决策需求，这些关键步骤的具体实施方案如下。

统计

为了满足决策需求中对“健康”和“营养”的考量，我们需要获取各种食物的热量和营养物质数据。这些数据已经由专家进行了专业的测量与统计，并且可以在网上直接查询得到。除此之外，如果食物限量供应，那么最大供应量数据在决策中同样不可或缺；如果我们还是价格敏感型消费者😭，那么食物的价格数据也需要被纳入到统计范围内。这些数据被罗列在下面的表中。

酱牛肉香熏鸡肉土豆泥圣女果胡萝卜玉米粒水煮蛋

卡路里	246	118	81	25	32	112	139
蛋白质	31	24	3	1	1	4	13
维生素	3	2	5	10	12	5	2
供应量	1	1	2	2	3	3	3
价格	30	10	5	8	3	5	2

需要注意的是，决策所需数据的统计工作并不总是这样一件简单的事情，甚至有时候会是运筹链路中最困难的一个环节。比方说，在“资金如何分配给不同理财产品以在给定风险承受能力的情况下最大化收益期望”的投资组合决策中，我们就要对不同理财产品的历史收益数据进行全面、准确的期望与方差统计；在“仓库容量如何分配给不同SKU以在满足消费需求的情况下最大化周转率”的库存管理决策中，我们就要基于时序预测算法来对未来销量做出准确估计；在“预算如何分配给不同广告平台以在有限投入下获得最大曝光量”的广告投放决策中，我们就要基于历史数据拟合曝光量关于广告投入的回归函数。

建模

建模是把实际问题转换为数学问题。实际问题中通常有三个要素：(1) 决策方案，也就是要决策的对象是什么；(2) 决策目标；(3) 决策条件，也就是决策方案要满足什么限制；这在数学问题中分别对应了决策变量、目标函数和约束条件。

决策方案 → 决策变量

在“晚上吃什么”的决策中，待确定的决策方案是“酱牛肉、香熏鸡肉、土豆泥、圣女果、胡萝卜、玉米粒、水煮蛋的食用量”，这可以用7个决策变量 $x_1$ 、 $x_2$ 、 $x_3$ 、 $x_4$ 、 $x_5$ 、 $x_6$ 、 $x_7$ 来依次表示。因为食物的提供方式是自助抓取，所以这些决策变量可以取非整数值，如 $x_1=0.5$ 表示取半份酱牛肉。

决策目标 → 目标函数

在“晚上吃什么”的决策中，我们的决策目标是尽可能吃得健康，也就是“食物的总卡路里尽可能低”。根据食物的卡路里数据和决策变量，这个决策目标可以表示成下列目标函数：

246x_1 + 118x_2 + 81x_3 + 25x_4 + 32x_5 + 112x_6 + 139x_7

我们需要最小化这个目标函数。

决策条件 → 约束条件

在“晚上吃什么”的决策中，我们制定的决策方案需要满足以下限制条件：

（1）食物的总蛋白质、总维生素满足每餐所需。假设我们每顿需要的蛋白质和维生素分别是100和50，那么这一限制可以表示为下列约束条件：

10031x_1+24x_2+3x_3+x_4+x_5+4x_6+13x_7 \ge 100

503x_1+2x_2+5x_3+10x_4+12x_5+5x_6+2x_7 \ge 50

（2）每种食物的食用量不超过其最大供应量。这一限制可以表示为下列约束条件：

1x_1, x_2 \le 1

2x_3, x_4 \le 2

3x_5, \ x_6, x_7 \le 3

（3）现实中，每种食物的食用量不可能为负值。这一限制可以表示为下列约束条件：

0x_1,x_2,x_3,x_4,x_5,x_6,x_7 \ge 0

综上所述，“晚上吃什么”的实际问题就写成了下列数学问题。其中，min是minimize（最小化）的缩写，s.t.是subject to（受限于）的缩写。

$31x1+24x2+3x3+x4+x5+4x6+13x7≥1003x1+2x2+5x3+10x4+12x5+5x6+2x7≥500≤x1≤10≤x2≤10≤x3≤20≤x4≤20≤x5≤30≤x6≤30≤x7≤3\begin{aligned} \min\text{ } & 246x_1 + 118x_2 + 81x_3 + 25x_4 + 32x_5 + 112x_6 + 139x_7\\ \text{s.t.\ \ } & 31x_1+24x_2+3x_3+x_4+x_5+4x_6+13x_7 \ge 100\\ & 3x_1+2x_2+5x_3+10x_4+12x_5+5x_6+2x_7 \ge 50\\ & 0 \le x_1 \le 1 \\ & 0 \le x_2 \le 1 \\ & 0 \le x_3 \le 2 \\ & 0 \le x_4 \le 2 \\ & 0 \le x_5 \le 3 \\ & 0 \le x_6 \le 3 \\ & 0 \le x_7 \le 3 \\ \end{aligned}$

求解

约束条件定义的决策变量集合被称为可行域，求解就是要在可行域内找到使得目标函数最大化或最小化的决策变量值。

上面建模得到的问题是一个线性规划问题，可以通过单纯形法、内点法等最优化算法（在下一节中详细介绍）进行求解。找到的最优解是 $x_1=1$ ， $x_2=1$ ， $x_3=0.94$ ， $x_4=2$ ， $x_5=1.19$ ， $x_6=0$ ， $x_7=3$ ，对应的目标函数值是945。也就是说，晚餐吃1份酱牛肉、1份香熏鸡肉、0.94份土豆泥、2份圣女果、1.19份胡萝卜、3份水煮蛋、不吃玉米粒，可以在满足蛋白质和维生素需求的情况下，摄入最少的945卡路里热量。

至此，我们完成了“晚上吃什么”的最优决策。

优化

“优化”，取自最优化（Optimization），或称数学规划（Mathematical Programming），指“在满足约束条件的情况下找到最大化或最小化目标函数的决策变量”，是上述运筹学定义在数学语言下的表达，是一门狭义的技术。严格来讲，“优化”只是“运筹”的一个子集。然而，架不住优化技术在运筹学中的重要地位和广泛应用，加之“运筹”和“优化”这两个词连读起来琅琅上口，“运筹优化”这个说法就在实践中逐渐流传开来。

注：在数学规划语境下，“优化/optimization”和“规划/programming”两个词几乎同义，下文中根据术语习惯进行用词选择，并非随意混用。

根据决策变量、目标函数、约束条件的特点，最优化问题可以被划分为不同的类型，并且每种类型都有特定的求解算法。下面对几种重要的最优化问题稍作介绍。

无约束优化

没有约束条件的最优化问题，形如 $f(x)\min f(x)$ ，被称为无约束优化。这类问题的最优解在目标函数的零梯度点处取得，可以用梯度下降法、拟牛顿法（比如BFGS算法）、牛顿法等算法进行求解。

现实生活中的决策问题通常都是有约束的，这类问题与算法更多出现在机器学习相关的任务中。

线性规划（Linear Programming，LP）

约束条件和目标函数都是线性函数，形如 $A x + b$ ，的最优化问题，被称为线性规划。这类问题的最优解在可行域极点处取得，可以用单纯形法、内点法等算法进行求解。

上文中提到的“晚上吃什么”问题就是典型的线性规划问题。

非线性规划（Nonlinear Programming，NLP）

约束条件或目标函数中有任意一项为非线性函数的最优化问题，被称为非线性规划。这类问题的最优解在增广拉格朗日函数的零梯度点处取得，可以用内点法进行求解，也可以通过分段线性化转换为混合整数线性规划问题（在下文中介绍）进行求解。

对于上文中提到的“晚上吃什么”问题，如果我们追求雨露均沾，每种食物都要吃一点，那么可以在目标函数中加入关于食用量的L2正则项，比如：

xi2\min 246x_1 + 118x_2 + 81x_3 + 25x_4 + 32x_5 + 112x_6 + 139x_7 + 10 \times \sum_{i=1}^7 x_i^2

此时，这个问题就变成了一个非线性规划问题（特别地，凸二次规划）。新问题的最优解是 $x_1=1$ ， $x_2=1$ ， $x_3=0.56$ ， $x_4=1.6$ ， $x_5=1.56$ ， $x_6=0.29$ ， $x_7=3$ ，可以看到确实每种食物都吃了一点。

混合整数规划（Mixed Integer Programming，MIP）

决策变量中存在整数变量（即只能取整数值的决策变量）的最优化问题，被称为混合整数规划。特别地，当所有决策变量都是整数变量时，这类问题称为整数规划。根据约束条件与目标函数是否线性，混合整数规划又可以进一步分为混合整数线性规划（MILP）和混合整数非线性规划（MINLP）。混合整数规划可以通过分支定界法、割平面等算法进行求解。

对于上文中提到的“晚上吃什么”问题，如果我们要求胡萝卜和水煮蛋必须成份拿取，也就是加入相应变量的整数约束：

Zx_5,x_7 \in Z

此时，这个问题就变成了一个混合整数线性规划问题。新问题的最优解是 $x_1=1$ ， $x_2=1$ ， $x_3=0.67$ ， $x_4=2$ ， $x_5=2$ ， $x_6=0$ ， $x_7=3$ ，可以看到胡萝卜和水煮蛋确实被成份拿取了。

不确定性规划

约束条件和目标函数中的参数不是确定的常数，而是表征不确定性的分布或区间，这样的最优化问题被称为不确定性规划。不确定性规划都是要转换为确定性规划进行求解的，根据转换的手段不同，不确定性规划进一步分为随机优化、鲁棒优化、分布鲁棒优化。

除了上面提到的概念之外，凸优化、二次规划、二阶锥规划、半正定规划等类型也是最优化问题中的重要子集。上面提到的算法都是精确算法，主打一个“the best or not”，此外还有贯彻“good enough is enough”的非精确算法（或称近似算法），包括k-opt、best fit、first fit等针对特定问题的启发式方法，以及遗传算法、模拟退火、禁忌搜索、粒子群优化等元启发算法。鉴于最优化的内容极度丰富，同时具体的分类与算法并非本文的重点关注内容，因此这篇博客对其的介绍到此为止，不再展开。感兴趣的同学可以关注我们的技术专栏，后续会有专门的博客对此进行详细介绍。

值得指出的是，最优化算法并非是求解运筹学问题的唯一技术。比方说，铁路运输调度的相关决策可以建模为网络的最大流问题，这既可以用最优化中的线性规划算法求解，也可以通过专用的Ford-Fulkerson算法求解；再比方说，给定最大总价且要求食物整份拿取来最大化蛋白质摄入的“晚上吃什么”决策可以建模为背包问题，这既可以用最优化中的整数规划算法求解，也可以用经典的动态规划算法求解。

反过来说，最优化也并非只用于求解运筹学问题。比方说，深度学习中的神经网络训练其实是一个大规模的无约束优化问题，广泛使用的反向传播算法本质上是梯度下降法的一种表现形式，深度学习的发展反过来又促进了梯度下降法的发展，衍生出Momentum、AdaGrad、RMSProp、Adam等SGD家族；再比方说，机器学习中的支持向量机（SVM）训练其实是一个大规模的二次规划问题，广泛使用的SMO算法本质上就是一种寻找增广拉格朗日函数的零梯度点的启发式方法，在样本量不大的情况下，现成的内点法也是适用的，而且可以保证找到SVM的最优参数。

运筹优化可以做哪些决策

用运筹优化来决策“晚上吃什么”多少有些杀鸡用牛刀，而且也不会真有人这么干，毕竟，理性者正确，感性者快乐，吃饭这么快乐的事情当然要感性一点啦。运筹优化真正的用武之地还是在生产制造、仓储物流、电商零售、资源调度、供应链管理等工业领域，可以达到降低成本、提高效率、优化资源利用的效果。本文的引子中提到，阿里是有运筹优化需求的。正好我曾经在阿里达摩院的决策智能Lab实习过，这个Lab的拳头产品是MindOpt求解器（一种集成数学规划算法的软件包）。这个产品发布的时候，Lab负责人介绍说“MindOpt已经应用于阿里集团的多项业务，包括云计算资源调度、金融资金分配、新零售智能营销等，每年可产生数亿元效益”。由此可以管窥，运筹优化的价值确实不容小觑。下面是一些典型的应用场景。

军事

二战期间，军事上的决策需求是运筹优化的起源之一。在这个时期，军事上面临许多复杂的决策问题，例如怎样在满足供应总量、运输能力和兵力需求的前提下，对军队、武器和物资进行有效的部署和配置，以达到最小化调动成本或转移时间的目标。随着计算机硬件和优化算法理论的快速发展，运筹优化已经很好地解决了这些问题，为军队提供了精确而且快速的决策支持。

制造

生产制造是最早应用运筹优化的民用领域之一，其应用场景非常广泛。以下是几个常见的例子：（1）生产排程问题：研究在给定订单需求和生产能力的情况下，如何安排生产计划以最大化交付能力；（2）流水线调度问题：研究在给定作业工序的资源要求和依赖关系的情况下，如何安排所有工序的顺序及对应机器以最小化生产时间；（3）板材下料问题：研究在给定原材料尺寸和所需零件尺寸、数量要求的情况下，如何制定切割方案以最小化原材料使用，提高资源利用率，该问题主要来源于服装纺织、钣金加工和家具制造行业。使用运筹优化技术来解决这些问题，相较于人工制定，可以显著提升决策质量，降低生产成本。

能源

能源领域是运筹优化的重要落地场景。以电力调度为例，如何确定电网中各台发电机的启停状态和发电功率是一项事关安全和经济的关键决策：安全是指调度方案要保证发电机、变压器、传输线的负载不超过其额定容量，而且所有用户的电力需求都要被满足，否则会发生安全事故；经济是指调度方案要最小化总的发电成本。这项决策被称为电网的机组组合（Unit Commitment）问题，通常建模为混合整数线性规划进行求解。这个问题还衍生出一种定价思想：实时电价 = 当前电网增加一单位电负荷带来的最优成本增量，并被欧美等电力市场广泛采用。这就是为什么我们时常听到美国电价飙升几十甚至上百倍的新闻，比如21年美国德州大停电的时候，部分未失电地区的一度电价格曾达到10美元以上，是正常价格的200倍。我国目前的电价是由国家发改委制定的固定价格（计划制经济），但未来也会向这种市场机制靠拢，由运筹优化算法实时定价。

金融

运筹优化在金融领域的投资决策中同样被广泛应用。美国经济学家Markowitz在1952年提出了投资组合理论，并因此获得了诺贝尔经济学奖。该理论的一个核心内容是根据不同资产收益的期望和方差，研究在达成预期收益水平的情况下，如何最小化投资风险的资金配置方案，从而实现更稳定的投资回报。大体上，这个问题被建模为二次规划，可以用内点法等优化算法进行求解。

交通

飞机、火车、地铁等公共交通遵守严格的班表计划。这些计划的制定需要考虑航班或列车之间的换乘时间、服务人员与设备的可用性、乘客流量等因素，通过运筹优化进行班表制定可以提升航空和铁路公司的运力利用率并优化乘客体验，比如减少延误和拥堵、提高航班廊桥率等。除此之外，运筹优化在城市的道路交通中也有很多应用，诸如道路网络布局、信号灯时间优化、公交路线规划、网约车/出租车调度，甚至是共享单车调度（用大货车把大量共享单车从下车热点转移到上车热点），都可以通过建模和优化得到更经济、更高效、更舒适的解决方案。

科技

自从美国封杀我国芯片制造行业以来，光刻机俨然以顶级科技的象征进入公众视野。光刻机和运筹优化看似八竿子打不着，但实际上两者之间也有密切的联系。比方说，光刻机的激光头需要在硅片上移动，并在若干位置上进行曝光。这里激光头的移动路径决策就是一个非常典型的运筹优化问题：旅行商问题（Traveling Salesman Problem， TSP），即寻找一条最短的轨迹来遍历空间中的指定位置并最终回到起点。通过优化激光头的移动路径，可以提高光刻机的工作效率，从而在相同的机器和时间条件下完成更多芯片的生产。

云计算资源调度

在云计算资源调度领域同样有大量运筹优化场景。在计算资源层面，可以用运筹优化技术解决虚拟机重调度问题和微服务合并部署问题：前者通过少量虚拟机在宿主物理机之间的迁移（决策虚拟机如何在物理机集群上部署）来减少集群的CPU碎片、释放空闲物理机、增加大规格虚拟机的库存数量；后者通过识别具有上下游调用关系的微服务并将其计算节点合并部署于同一台物理机（决策微服务容器如何在物理机集群上部署），在物理机容量限制下最大化本地化通信，减少RPC调用与序列化/反序列化操作，从而减少微服务之间的通信时延并提高集群的CPU利用率。在存储资源层面，可以用运筹优化技术解决多机房场景下的数据排布问题：通过将强关联的业务数据存放在相同机房（决策数据如何在多个核心机房上部署）、分散访问的数据进行多机房缓存（决策哪些数据缓存到哪些机房）来减少离线作业的跨机房流量，从而减少作业的等待时间、缓解公网带宽的性能瓶颈、提高机房资源利用率。在网络资源层面，可以用运筹优化技术解决云边端流量调度问题：通过打平业务流量在通信链路各项资源上的水位（决策流量如何在线路与机房上分配）来缓解资源过载问题、提升用户的访问体验、增强网络系统的稳定性。

电商物流

运筹优化还可以服务于电商物流业务。在仓库建设环节，通过优化仓库选址可以在满足地区需求的前提下最小化建设成本与日常运输成本；在仓储管理环节，通过优化仓库布局可以在满足商品存储要求的前提下最大化仓库利用率，通过优化分拣策略可以在满足出库需求的前提下最小化拣货时间，提高订单处理效率；在商品售卖环节，通过优化SKU选品可以在满足消费者需要的前提下提升销售额并缓解库存压力；在商品配送环节，通过优化配送路径和顺序可以在满足物流时效的前提下最小化配送成本……可以说，电商物流是运筹优化落地场景最为丰富的业务之一。

广告投放

广告是运筹优化技术的又一个广阔舞台。无论是将有限的广告预算分配给不同渠道来最大化广告效果和用户增长，还是在实时竞价广告中制定专门的出价策略来最大化广告的产出投入比（ROI），又或者在保障用户体验的前提下通过针对性推荐来最大化用户点击率从而提升广告变现，都可以建立相应的优化模型并求解以实现量化决策。不过需要说明的是，运筹优化只是广告算法链路中的一个环节，后者的闭环更多依赖机器学习、强化学习等算法。

……

结语

尽管运筹优化的应用场景无处不在，但从上面的介绍中不难看出，比起前/后端开发工程师、CV/NLP算法工程师解决“从无到有”的问题，运筹优化工程师更多关注“从有到精”的问题。在很多决策的问题中，用一些简单的策略，比如贪心、比如规则，同样可以让代码跑起来、让业务转起来，这也正是运筹优化工程师未被广为人知的原因之一。但是，“又不是不能用”的野蛮生长方式无法满足业务精细化发展的要求，在“降本增效”的大趋势下，相信越来越多的业务决策会用到运筹优化、用好运筹优化。