解析什么是优化(什么是优化问题和优化方法)

本文约4400字,建议阅读10分钟

本文介绍了什么是优化问题,常见的优化问题分类,优化问题的核心要素以及如何构建简单的优化模型。本文不涉及复杂的数学公式,堪称入门优化问题的保姆级教程。

标签:优化、约束条件、Optimization

什么是优化问题,它的背后的原理是什么?

图片来源Unsplash,由 Ricardo Gomez Angel上传

通过本文,您将了解一些优化问题的基础知识,以及优化是如何在幕后真正发挥作用的。我会通过两个例子来说明如何构建一个简单的优化问题,并且展示优化问题中要素的更改如何影响我们的解决方案的。

本文将涵盖如下主题:

  • 什么是优化?
  • 优化为什么如此重要?
  • 优化用在哪些地方?
  • 约束性优化与无约束优化有什么区别?
  • 优化模型的三个核心要素是什么?
  • 如何构建一个简单的优化问题(两个示例)。

本文不会涉及复杂的数学推导、算法、优化软件,也不会讨论其他不同类型的优化问题。

什么是优化?

简而言之,优化就是在所有可行的解决方案中选择最优方案。

但是,什么是最优呢?所谓最优,取决于你手头上的问题是什么。对于你正在解决的问题来说,最优意味着最大的利润吗,还是最低的成本?是否意味着节省的时间最多,还是使用的资源最少?所以说,“最优”的定义取决于你要解决的问题。

什么时候需要优化?当某个问题有一个以上解决方案的时候,就可以利用优化了。

优化为什么如此重要?

那么我们为什么要关心优化?它为什么如此重要?

要了解它的重要性,让我们先来看一下分析的四个不同阶段。下图是 Gartner 分析优势模型,这是用来衡量一个组织的数据成熟度的有用工具。

图片来源: Cartner (2012年3月)

x 轴表示难度或复杂程度,y 轴表示价值或影响。四种不同阶段的分析从事后分析到先见分析,其中先见分析最为复杂。

第一阶分析是描述性分析(descriptive analytics)。它告诉你发生了什么。例如,浏览网站的平均时间或同比销售额增长。

第二阶分析是诊断性分析(diagnostic analytics)。为什么会这样?其特点是深入研究数据以确保在数据中能够发现潜在的原因。

接下来,是预测性分析(predictive analytics)。将要发生什么?为了做出预测,我们可能会使用机器学习模型。也许你可能听说过聚类模型或回归模型。你猜怎么着,这些机器学习模型也是依靠优化来找到答案的。

优化也是规范性分析(prescriptive analytics)的范畴。我们会做出哪些决定来让事情发生?例如,我们如何分配零售货架以实现利润最大化?将多少产品运送到美国各地的仓库在最大限度地降低总体成本的情况下仍能满足需求?

这些决定将具有巨大的商业价值,不是吗?这将帮助我们提高效率,或者提供竞争优势。优化非常强大,因为你能够在战略、运营和战术层面为组织提供指导。

从图表中可以看出,优化是最复杂的分析阶段,但同时也提供了最大的商业价值。我们将在接下来的几个示例中看到这一点。

优化用在哪些地方?

图片来源Unsplash,由Ravi Palwe上传

你可能没特别留意,但优化其实无处不在。当你使用 GPS 时,无论是谷歌地图还是苹果地图,它都会帮你计算到目的地的最短行驶距离。这就是优化。

优化不仅在日常问题中发挥作用,而且已被应用于各个行业的各种类型的问题当中。以下就是两个著名的优化案例。

案例 1: UPS

首先讨论运输中的优化问题。一个著名案例来自 UPS(United Parcel Service, Inc. 美国联合包裹运送服务公司)。UPS 希望为其司机找到最有效的包裹递送路线,以节省时间并降低油耗。为了节省时间,该公司决定司机应尽可能地避免左转。在美国,你需要等待绿灯以及前方直行无车时才能左转。因此,取消左转意味着更少的时间浪费和更少的燃料消耗。UPS 创建了一个名为 ORION 的专有优化软件,以帮助司机最大限度地减少运输路线的左转。

图片引自: Holland et al.: UPS Optimizes Delivery Routes、

在上图中,左侧是驾驶员原本的路线方案,右侧是 ORION 给出的解决方案。正如您在地图上看到的,ORION 的解决方案比司机的方案要高效得多。使用 ORION 软件可以节省 30 英里的路途。

谈到商业价值,UPS称:“自 ORION 最初部署以来,每年为 UPS 节省了大约 1 亿英里和 1000 万加仑的燃料。”

这当然可以使他们比竞争对手更具竞争优势。正如在此处看到的,优化为 UPS 带来了重大的商业价值。

案例 2: 美国陆军

接下来是一个经典案例。最早的优化问题之一可以追溯到 1930 年代。在第二次世界大战期间,美国陆军想搞清楚如何在满足饮食的必需的营养的同时,最大限度地降低在战场上饮食供给的成本。

图片来源Unsplash,由Martijn Hendrikx上传

研究这个问题的经济学家乔治·斯蒂格勒发现,最佳饮食组合包括以下 5 种食物:370 磅小麦粉、57 罐炼乳、111 磅卷心菜、23 磅菠菜和285 磅海军豆。

这听起来当然不是最美味的饮食,但一年只需 39.93 美元。有趣的是,按照今天的价格,它大约是 831 美元。

图片引自: Wikipedia

这种饮食组合最大限度地降低了成本,还满足了以下营养要求。

图片引自: Wikipedia

在战争时期,最小化成本至关重要,因此,这个优化问题对陆军来说具有巨大价值。

无约束优化vs约束性优化

如果从图形上看优化是什么,它只是找到最大点或最小点。

图片来源: 作者

上图中,我们看到的是一个无约束优化的示例,其中最高峰是最大点,最低谷是最小点。

然而,实际上我们是有约束条件的,所以图表看起来更像这样。

图片来源: 作者

我们将受到限制,因为我们身处一个资源有限的世界。例如,一天只有 24 小时。我的银行账户里只有有限的美元。我们可以利用的东西是有限的。

红线代表约束,由于存在约束,我们的最大点将不再是最高峰,而是在峰的一半左右。上图即说明了约束性优化,也就是我们在讨论优化问题时通常需要处理的优化类型。

优化问题的三个核心要素

现在我们来介绍优化问题都需要面对的三个核心要素。我将使用前面提到的斯蒂格勒饮食问题作为这些核心要素的示例。

1. 目标函数

2. 决策变量

3. 约束

目标函数

之前我们讨论过“最优”这个词。在优化方面,我们正在努力寻找最佳解决方案。目标函数将帮助我们衡量什么是最优的。

在饮食问题中,“最优”意味着最小化年度总成本。因此,年度总成本是我们衡量解决方案质量的方式。也就是说,年度总成本越小,解决方案越好。

决策变量

决策变量是你必须做出决定的事情。这些是可以调整的东西,或者换句话说,是在你可控范围之内的东西。

在饮食问题上,斯蒂格勒必须弄清楚要供给士兵什么食物以及每种食物的量。食物的种类和数量是这个问题的决策变量。

约束

约束是对这些决定的限制。在饮食问题上,斯蒂格勒有以下营养限制。

一个成年人每天需要摄入 3000 卡路里热量,70 克蛋白质,等等。饮食组合的选项需要满足这些要求。约束这个元素非常重要,因为软件可以为您计算并找到最佳解决方案,但软件并不理解现实世界。你必须为机器翻译现实生活中的约束,否则,你最终可能会得到一个无法实际操作的解决方案。

解决方案

我们经常使用解决方案这个词,所以让我们清晰地定义一些处理解决方案的术语。

  • 解决方案是每个决策变量的一组值。例如,5磅菠菜。这可以是一个解决方案。20磅菠菜。这可能是另一种解决方案。
  • 可行方案是实际可行的解决方案。也就是说,一个满足我们约束的解决方案。如果 20 磅菠菜足以满足营养需求,那么这是一个可行方案。
  • 为我们提供最佳价值的一种可行解决方案是我们的最佳方案。在饮食问题上,就是23磅菠菜。

优化问题1

现在我们已经掌握了所有术语,让我们看一个超级简单的玩具优化问题。这个问题非常简单,以帮助你轻松进入解决优化问题的状态。这里只是学习使用我们学习过的术语来构建优化问题,并理解优化是如何工作的,所以不要太担心解决方案。

这是我们手头的问题:

  • 非常毛绒玩具公司(It's So Fluffy LLC) 想要最大化利润。
  • 他们有两种产品:可爱的独角兽抱枕和肥猫玩偶。
  • 非常毛绒玩具公司有足够的雪尼尔材料来生产最多 2 个可爱的独角兽抱枕。
  • 非常毛绒玩具公司有足够的面料生产最多 3 个肥猫玩偶。
  • 独角兽抱枕有 15 美元的利润,肥猫玩偶有 10 美元的利润。

花点时间来想一想这个优化问题的三个核心要素是什么。如果忘记了核心要素,这里有一个提醒。

  1. 目标函数
  2. 决策变量
  3. 约束

目标函数是什么?我们希望为公司带来最大的利润。利润是独角兽抱枕的价格乘以卖出的独角兽抱枕的个数加上肥猫玩偶的价格乘以卖出的肥猫玩偶的个数。

什么是决策变量?公司可以决定哪些事情?要制作的独角兽抱枕的数量和要制作的肥猫玩偶的数量。

有哪些约束条件?由于材料限制,最多只能生产2个独角兽抱枕和3个肥猫玩偶。

另一件值得注意的事情是,不可能生产少于 0 个独角兽抱枕或 0 个肥猫玩偶。尽管这对我们来说是直观和合乎逻辑的,但将这些约束构建到问题中是一种很好的做法。你希望避免计算机可能输出不合逻辑的解决方案的情况,例如在这种情况下的负数。

现在让我们将刚刚提出的组件转换为图形形式,以便将问题可视化。

下图中的 X 和 Y 轴是我们的决策变量。现在让我们画出我们的约束。在向下滚动之前,请花点时间考虑一下如何在此图上绘制约束。

它应该如下所示。图表上的红线代表我们针对此优化问题应用的约束。分别有一条垂直线在x轴0 和 2 处,分别有一条水平线在y轴 0 和 3 处。其中绿色部分我们称之为可行解决方案空间,粉色部分称为不可行解空间。

在绿色的可行解决方案空间内,我们现在想要找到要制作的最佳独角兽抱枕和肥猫玩偶的数量。请记住,独角兽抱枕的利润为 15 美元,肥猫玩偶的利润为 10 美元。如果该公司生产 1 个独角兽抱枕和 0 个肥猫玩偶,它将赚 15 美元。如果该公司生产 2 个独角兽抱枕和 1 个肥猫玩偶,它将赚 40 美元。等等。

我已经计算了下图中每个可行解决方案的利润。那么哪一个是最优解呢?也就是说,哪一个会帮助我们实现利润最大化?

最高利润为60美元,即制作了2个独角兽抱枕和3个肥猫玩偶。

最优解: 独角兽抱枕 = 2, 肥猫玩偶 = 3

该解决方案是合理的,其实并不需要经过这么些步骤,但这里只是想帮你理解如何构建优化问题,就像我们刚刚所做的那样。这很重要,因为计算机会执行运算来帮你找到解决方案,但你必须正确地为计算机构建问题。

优化问题2

在问题 1 的基础上,现在让我们为问题添加一个额外的约束条件。

  • 这家小型有限责任公司的人力只够一天生产最多 4 件产品。

这对现在的问题有什么影响?我们有一个额外的约束条件需要添加到问题中,但其他一切都保持不变。

现在,让我们也将此约束条件添加到图表中。下面的对角红线是我们刚刚添加的新约束。由于增加了此约束,绿色矩形右上角的三角形区域将不再是绿色。

因此,在我们可行的解决方案空间内,以下是每个解决方案的利润。

最大利润是50美元, 即制作了2个独角兽抱枕和2个肥猫玩偶。

最优解: 独角兽抱枕 = 2, 肥猫玩偶 = 2

问题 1 与问题 2的比较

如果我们将问题 1 的解决方案与问题 2 的解决方案进行比较,您会注意到什么?

问题 2 的可行解空间要比问题1的小。问题 2 的解决方案得到的利润较低。

发生了什么?

额外的约束条件会缩小可行解空间,因而会使得我们的解决方案变差。在问题设定时意识到这一点非常重要。你要添加的约束条件是必需的吗?因为约束越少,优化软件找到最优解决方案的空间就会越大。

原文标题:

A Gentle Introduction to Optimization

原文链接:

https://towardsdatascience.com/a-gentle-introduction-to-optimization-f95938ce475e

文章来源于网络,如若侵权,请联系站长删除。

本站承接各类商务合作,如有合作需求,请联系我们。