数据科学家线性规划入门指南

欢迎关注AI科技大本营微信公众号：rgznai100，获取更多精彩内容

前言

生活之道在于优化。每个人拥有的资源和时间都是有限的，我们都想充分利用它们。从有效地利用个人时间到解决公司的供应链问题——处处都有用到优化。

优化还是一个有趣的课题——它解决的问题初看十分简单，但是解决起来却十分复杂。例如，兄弟姐妹分享一块巧克力就是一个简单的优化问题。我们在解决这个问题时不会想到使用数学。另一方面，为电商制定库存和仓储策略可能会十分复杂。数百万个库存单位在不同地区有不同的需求量，而且配送所需的的时间和资源有限——你明白我意思吧！

线性规划（LP）是实现优化的最简途径之一。它通过作出几个简化假设，就能帮你解决一些非常复杂的优化问题。作为一名分析师，你必定会遇到需要使用线性规划解决的应用程式和问题。

由于某种原因，在学习数据科学的过程中，线性规划并未得到应有的重视。因此，我想对这个了不起的技巧作出公平评价。我决定写篇论文，用简单的语言解释线性规划。这篇文章的内容力求简单易懂。目的是让你开始了解并热爱线性规划。

目录

1. 线性规划是什么？

   a. 基本术语

   b. 定义线性规划问题的程序

2. 用图解法解决线性规划问题

3. 用 OpenSolver 解决线性规划问题

4. 单纯形法

5. 西北角法和最小费用法

6. 线性规划的应用

1. 什么是线性规划？

首先，什么是线性规划？线性规划是一个简单的技巧，我们借助线性函数描述复杂的关系，然后找出最优点。上句中的重点是“描述”。实际关系可能要复杂的多——但是我们能将它们简化为线性关系。

线性规划的应用无处不在。你在人际交往和职场中使用线性规划。你在开车上班途中抄近路时使用线性规划。或者当有项目需要交付时，你通过决策使你的团队高效工作并及时交付。

线性规划问题实例

例如，一位联邦快递公司的快递员一天要递送6个包裹。仓库位于点 A。6 个递送目的地分别为 U、V、W、X、Y 和 Z。线上的数字表示城市间的距离。为节省燃料和时间，快递员想选择最短路线。

这样，他将对到达 6 个目的地的不同路线进行计算，然后得出最短路线。选择最短路线的方法就称为线性规划。

在此情况下，快递员的目标是按时将包裹分别送到 6 个目的地。选择最佳路线的过程成为运筹学。运筹学是一种制定决策的方法，它包含一系列系统运作方法。在上例中，我的系统就是递送模型。

线性规划用于在解决特定限制条件下获得最佳解决方法。在线性规划中，我们将实际生活问题转化为数学模型。这个模型包含目标函数以及带约束条件的线性不等式组。

上面 6 点的线性表示能否代表实际情况。能又不能。它只是将实际情况过分简化，因为实际路线不会是直线。实际路线可能有许多转弯、U型弯和交通堵塞。但是借助简单的假设，我们大幅降低了问题的复杂度，得出在大多数情况下可行的解决方案。

构想一个问题——生产巧克力

举例：一家巧克力制造公司只生产两种巧克力—— A 和 B。两种都需要牛奶和巧克力原料。生产每单位 A 和 B，需满足下列数量要求：

• 生产每单位 A 需要 1 单位牛奶和 3 单位巧克力原料

• 生产每单位 B 需要 1 单位牛奶和 2 单位巧克力原料

该公司工厂总共有 5 单位牛奶和12 单位巧克力原料。该公司

• 每销售 1 单元，A 获利 6 卢比

• 每销售 1 单元，B 获利 5 卢比

现在，该公司计划将利润最大化。它应分别生产多少单元的 A 和多少单元的 B？

解决方案：首先为了便于理解，我会用表格的形式来表示问题。

A 的总生产单元数 = X

B 的总生产单元数 = Y

现在，Z 代表总利润。

该公司获得的总利润等于 A 和 B 的总生产单元数分别乘各自的每单元利润 6 卢比和 5 卢比，然后再相加。

利润：Max Z = 6X+5Y

这表示我们必须将 Z 最大化。

该公司将尽量多地生产 A 和 B 以实现利润最大化。但是牛奶和巧克力原料的供应是有限的。

按照上表，生产每单位 A 和 B 分别需要1 单元牛奶。现共有 5 单元牛奶。以数学公式表达：

X+Y ≤ 5

同时，生产每单位 A 和 B 分别需要3 单元和 2 单元巧克力原料。现共有 12 单元巧克力原料。以数学公式表达：

3X+2Y ≤ 12

而且，A 的生产单元数只能是整数。

因此我们还有另外两个约束条件，X ≥ 0 & Y ≥ 0

为使该公司实现利润最大化，必须满足上述条件。

这就称为将现实问题转化为数学模型。

线性规划中使用的常见术语

让我们用上述例子定义一些线性规划中使用的术语。

• 决策变量：决策变量是指决定结果的变量。它们代表最终解决方案。在解决任何问题前，我们首先要确定决策变量。在上例中， X 和 Y 分别代表 A 和 B 总生产单元数，它们作为决策变量。

• 目标函数：定义为决策目标。在上例中，该公司希望增加总利润 Z。因此，利润作为目标函数。

• 约束条件：约束条件是指对决策变量的约束或限制。它们通常限制决策变量的值。在上例中，牛奶和巧克力原料的供应限制就是约束条件。

• 非负值限制：对于所有线性规划，决策变量应始终为非负值。这表示决策变量的值应大于或等于 0。

如何用公式表示线性规划问题

概括定义线性规划问题的步骤：

• 确定决策变量

• 写目标函数

• 标出现在条件

• 清楚表明非负值限制

属于线性规划问题的前提是：决策变量、目标函数和限制条件都必须为线性函数。

如果某一问题都满足这三个条件，那么它可称为线性规划问题。

2. 用图解法解决线性规划问题

线性规划问题的解决方法有多种。在本节，我们将探讨用图解法解决线性规划问题。该方法用于解决双变量线性规划问题。如果决策变量有两个，则应使用图解法找到最佳方案。

图解法就是先表示出一组带约束条件线性不等式。平面直角坐标系上点的坐标代表决策变量的一组值。当我们把所有不等式都表示在图中时，得出的交叉部分就是可行解域。可行解域就是模型可以取值的范围。它会给出最优解。

让我们通过举例来理解该方法。

举例：一位农民最近获得了一片 110 公顷的土地。他决定在这片地上种植小麦和大麦。由于该地区绝好的日照和气候条件，产出的小麦和大麦都可以出售。他想要知道如何分配每种作物的种植面积，现已知成本、毛利润和劳动力要求，如下所示：

该农民的预算为 10000 美元，在计划周期内有1200 个工日。找到最佳解决方案和最优解。

解决方案：要解决这个问题，我们先要用公式表示该线性规划问题。

作出线性规划问题的公式

• 步骤 1：确定决策变量

种植小麦的总面积 = X（单位为公顷）

种植大麦的总面积 = Y（单位为公顷）

X 和 Y 为决策变量。

• 步骤 2：写目标函数

由于整片土地的产出都可以在市场上销售。该农民想要将总产出所获的利润最大化。我们已知小麦和大麦的净利润。农民每公顷小麦和大麦可分别获得50 美元和 120 美元的净利润。

我们的目标函数（由 Z 表示）为：Max Z = 50X + 120Y

• 步骤 3：写限制条件

1. 现已知该农民的总预算为10000 美元。还已知每公顷土地种植小麦和大麦的成本。已知该农民总成本的上限。方程式表示为：

   100X + 200Y ≤10,000

2. 下个限制条件为规划周期内总工日的上限。可提供的总工日数为1200。按照上表，我们已知每公顷种植小麦和大麦所需的工日。

   10X + 30Y ≤1200

3. 第三个限制条件是种植总面积。种植总面积为110 公顷。因此方程式表示为：

   X + Y ≤ 110

• 步骤 4：非负值限制

X 和 Y 的值须大于或等于 0。表示为：

X ≥ 0,Y ≥ 0

我们用公式表示出了这个线性规划问题。现在要解决这个问题。

用图解法解决线性规划问题

我们已知 X, Y ≥ 0。我们将只考虑第一象限。

要在图上表示出上述方程式，首先要简化所有方程式。

100X + 200Y ≤ 10,000 可通过除以 100 简化为 X + 2Y ≤ 100。

10X + 30Y ≤ 1200 可通过除以 10 简化为 X + 3Y ≤ 120。

第三个方程式无需简化，X +Y ≤ 110。

在图中第一象限画出前两条线（如下所示）。

交叉点代表最佳的可行方案，同时满足预算和工日的限制条件。这表示X + 2Y ≤ 100 和 X + 3Y ≤ 120 的交叉点给出最佳解决方案。

该点的坐标为（60，20）。

要实现利润最大化，该农民应分别种植60 公顷的小麦和 20 公顷的大麦。

该公司将获得的最大利润为：

Max Z = 50 * (60) + 120 * (20)

= US$5400

3. 用 OpenSolver 解决线性规划问题

事实上，使用图表法或代数的方法解决包含30 至 100 个变量的线性规划问题是几乎不可能的。公司一般使用 OpenSolver 解决这些现实问题。现在我将为你介绍用 OpenSolver 解决线性规划问题的步骤。

OpenSolver 是微软Excel 的开源线性和优化软件。它是内置 excel Solver 的改进版。您可以在此下载 OpenSolver

https://sourceforge.net/projects/opensolver/files/latest/download

并按照安装手册完成安装（http://opensolver.org/installing-opensolver/）。

我希望你能亲手操作和使用 OpenSolver。为了便于理解，我将举例说明该软件的使用方法。

举例：下方的食谱表给出 4 中食物的卡路里数以及蛋白质、碳水化合物和脂肪含量。Sara 想要一个最低成本的饮食。饮食表如下：

该表给出了营养含量以及每种食物的每单元成本。该食谱必须至少包含 500 卡热量、6 克蛋白质、10 克碳水化合物和 8 克脂肪。

解决方案：首先，我将在电子表格上用公式表示出这个线性规划问题。

• 步骤 1：找出决策变量。决策变量为食物种类。添加表头。为试验目的，输入任意值。利润，Sara 消耗 3 单位食物 1、0 单位食物 2、1 单位食物 3 和 0 单位食物 4。这些为可变单元格。

• 步骤 2：现在我们将写出目标函数。为使优化该食谱，我们必须以最低的成本满足热量、蛋白质、碳水化合物和脂肪要求。

在单元格 B7:E7，我们参考单位数。在单元格 B8:E8 中输入每种食物的每单元成本。

在单元格 B10 中，我们得出该食谱的总成本。总成本为单位数与每单元成本的乘积之和。总成本= B7*B8+C7*C8+D7*D8+E7*E8。让我们在电子表格中查看结果。

• 步骤 3：现在，我们输入限制条件。第 F 栏包含热量、蛋白质、碳水化合物和脂肪的总量。摄取的热量等于这几种食物的食用量与每种食物的热量的乘积之和。F13 = 乘积之和（$B$7:$F$7，B13:F13）。其它类似。第 G 栏给出方程式，由于此问题要求摄入的热量、蛋白质、碳水化合物和脂肪分别至少达到 500 卡、6 克、10 克 和 8 克。第 H 栏给出要求的营养含量。

• 步骤 4：现在，我们将该线性规划输入求解器。现在，当您已安装 OpenSolver。当您点击数据表，您将在右侧看见此模型。点击模型，然后依次输入数值。首先，我们将在目标单元格中输入目标函数，即 B10。选择最小化，因为我们要将成本将至最低。

• 步骤 5：现在在可变单元格内输入决策变量。

• 步骤 6：现在，我们将添加限制条件。 第一个限制条件是 F13 ≥ H13。依次添加限制条件。

• 步骤 7：现在，您须输入一个重要的限制条件。非负值限制。所有的决策变量都必须大于 0。

• 步骤 8：现在，点击保存模型以完成建模程序。在您保存此模型后，将显示如下。

• 步骤 9：在保存模型后，点击数据表，然后点击求解。最佳解决方案和最优解将显示在以下单元格内。优化的最低成本为US$0.90。要以最低成本满足所要求的营养量，Sara 应食用3单位的食品2和1单位的食品3。这就解决了这个线性规划问题。

4. 单纯形法

单纯形法是最解决线性规划问题的最高效、最普遍的方法之一。单纯形法是用迭代法获得最可行的解决方案。在这种方法中，我一直转变基变量以得出目标函数的最大值。

如果要将目标函数最大化，必须将线性规划函数转化为标准形式。

限制条件，

…………

…………

其中，

和

。在输入这些松弛变量后，约束方程式的对应系统为，

…………

其中，

变量， S1，S2……Sm 成为松弛变量。它们是用来从方程式中移除不等式的非负值。

上述解释为单纯形法的理论解释。现在，我将将解释如何在 Excel 中使用单纯形法。

举例：一家公司可选的广告媒介包括电视、报纸和广播广告每种媒介的成本以及受众人数如下所示。

当地报纸限制每家公司的广告数不得超过 10 支。而且，为了平衡三种媒介的广告，广播广告的数量不得超过广告总数的一半。电视广告的数量至少占 10%。广告的周预算为 18,200 美元。该如何在三种媒介中分配广告才能使受众人数最大化？

解决方案：首先为了便于理解，我将用公式表示这个问题。

• 步骤 1：找出决策变量。

用 X1，X2，X3 分别代表电视广告、报纸广告和广播广告的总数。

• 步骤 2：目标函数。

该公司的目标是使受众人数最大化。目标函数为：

• 步骤 3：写限制条件。

现在，我将依次标出每个限制条件。

显然，我们已知预算限制。总预算总计为 18200 美元。电视广告、报纸广告和广播广告的成本分别为 2000 美元、600 美元和 300 美元。这可通过方程式表示出来，

对于报纸广告，广告数量不得超过 10支。第一个限制条件是，

下一个限制条件是电视广告的数量。该公司要求电视广告的数量至少占10%。因此，可表示为：

最后一个限制条件为广播广告的数量不得超过广告总数的一半。可表示为，

现在，我已将这个线性规划问题用公式表示出来。我们使用单纯形法解决这个问题。我将向您依次介绍单纯形法。

所有限制条件如下。我已将最后两个方程式转化为标准形式。

我们现有 4 个方程式。为抵消每个不等式，我将引入 4 个松弛变量 , S1，S2，S3，S4。

因此我们的方程式如下所示：

我希望您现在可以理解整个广告问题。上面的所有方程式仅为了帮您更好地理解这个问题。现在如果您要解出这些方程式，您会得出：X1=4, X2=10 和 X3= 14。

在解出目标函数时，您将得出每周受众人数的最大值为1052000。您可以按照该 教程 来解该方程式。欲在 excel 中解决该线性规划问题，请参考此 教程。

5. 西北角法和最小费用法

5.1 西北角法

西北角法用于解决线性规划问题中的运输问题。它被用来计算计算出将商品从某地运至另一地的可行方案。当您遇到涉及供求的实际问题，这个问题涉及不同供货处中的一个。数据模型包含：

• 每个供货地的供求水平已知

• 将货物从任一供货处运至每一目的地的单位运输

该模型假设仅有一种货物。该货物的需求可能来自不同供货处。目标是以最低的运输成本满足总需求。该模型基于总需求等于总供给的假设，即该模型是平衡的。让我们通过举例来理解该方法。

举例：现有 3 个贮仓用来满足 4 个磨坊的需求。（贮仓是用来储存粮食的贮存区域，磨坊是粮食的研磨加工厂。

解决方案：让我们先了解上表的内容。

从贮仓 i 到 磨坊 j 的运输成本为对应每个贮仓 1 供应贮仓和每个磨坊需求的每单位运输成本。例如：从贮仓 1 到磨坊 1 的运输成本为 10 美元，从贮仓 3 到磨坊 8 的运输成本为 18 美元。先已知贮仓和磨坊的总需求和总供给。目标是以最低成本满足所有磨坊的需求。

顾名思义，西北角法是自左上角单位起分配所有单位的方法。磨坊1 的需求为 5，贮仓 1 的总供给为 15。因此，可以每单位 10 美元的成本向磨坊 1 分配 5 单位。磨坊 1 的需求得到满足。然后，我们再处理磨坊 2的左上角。磨坊 2 的需求为 15 单位， 可以每单位 2 美元的成本从贮仓 1 向磨坊 2 运输 10 单位，以每单位 2 美元的成本从贮仓 2 向磨坊 2运输 7 单位。然后我们再安排磨坊 3，西北角单元为 S2M3。磨坊 3 的需求为 15 单位， 可以每单位 9 美元的成本从贮仓 2 向磨坊 3 运输 15单位。再安排最后一家磨坊，磨坊 4 的需求为 15 单位。将以每单位 20 美元的成本从贮仓 2 向它运 5 单元，以 每单位 18 美元的价格从贮仓 3 向它运10 单元。

总运输成本 =5*10+(2*10+7*5)+9*15+(20*5+18*10) = $520

5.2 最小费用法

最小费用法是一种计算线性问题最可行方案的方法。该方法得出的结果比西北角方法更准确。它被用于解决运输和生产问题。我将用最简单的方法解释上述运输问题。

按照最小费用法，您先从运输成本最低的单元开始安排。因此，同意是上述问题，以每单元4 美元的成本从贮仓 3 供应 5 单位。磨坊 1 的需求得到满足。我们以每单元 2 美元的成本从贮仓 1 向磨坊 2 供应 15 单位。然后我们以每单元 9美元的成本从贮仓 2 向磨坊 3 供应 15 单位。再然后我们以每单元 20 美元的成本从贮仓 2 向磨坊 4 供应 15 单位，以每单元 18 美元的成本从贮仓3 向磨坊 4 供应 5 单位。总运输成本为 475 美元。

上述方法说明，我们可以以最佳方法进一步优化成本。让我们使用Excel Solver 检查。Solver 是 Microsoft Excel 的内置附加物。它是 Excel 的内置插件。按途径文件->选项->插件->选择solver->选择管理->选择 solver->点击 Ok 进行操作。您的 solver 已安装在 excel 上。您可在数据表中检查。

现在 excel 中输入您的数据。在excel 中输入数据后，我计算了 C3:F3 的总和。其它类似。这步是计算从贮仓1 和其他贮仓的总需求。

在这步之后，我将把该模型一分为二。第一个表格给出供应的单位，第二个表格给出每单位成本。

现在，计算总成本，即各单位成本和供应的单位的乘积之和。

现在我要使用 Solver 计算我的模型。与上述方法类似。添加目标函数，变量单元格和限制条件。

现在您的模型已可以计算。点击计算，您将得到优化成本。最低运输成本为435 美元。

6. 线性规划的应用

许多行业都用到线性规划和优化。制造业和服务业经常使用线性规划。在本节中，我们将探讨线性规划的各种应用。

1. 制造业使用线性规划分析他们的供应链运营。他们的目的是以最低的成本将效率最大化。按照线性规划模型的建议，制造商可以重新配置他们的仓库布局，调整人力资源并减少交通堵塞。这是美国公司 Cequent 的一个小型案例分析，观看此视频（https://www.youtube.com/watch?v=gIXNTebJOe8）以加深了解。

2. 有组织的零售业使用线性规划优化货架空间。由于市场上商品数量大幅增加，理解顾客需求显得格外重要。诸如沃尔玛、Hypercity、Reliance 和 Big Bazaar 等商店越来越应用优化。商店安装顾客的购物习惯，有策略地放置商品。目的是为了帮助顾客轻松找到并选择合适的商品。这受限于有限的货架空间、产品的种类等。

3. 优化方法还用于优化递送路线。这是常见旅行销售员问题的延伸。服务业使用优化方法为前往多个城市的多名销售员找出最佳路线。通过集群和贪婪算法，诸如联邦快递公司和亚马逊等公司决定递送路线。目的是将运营成本和时间降至最低。

4. 机器学习也用到优化方法。对线性规划基本要素的监督学习。系统在经过训练后安装函数的数学模型，函数来自标记的输入数据，该模型能够从未知的测试数据中预测结果。

线性规划的应用除此之外还有很多。在现实中，许多领域都用到线性规划，例如股东、体育、股票市场等。继续探索更多应用。

尾注

我希望你喜欢这篇文章。我已尽力解释了线性规划的所有基本概念。我用实际生活中的例子解释了每个概念。我希望你亲自操作，获得亲身体验。告诉我你的想法！

本文作者 Swati Kashyap 是一名数据科学与分析爱好者。 目前，在 Google Analytics Vidhya 学习数据科学。