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

前言

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

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

线性规划(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 学习数据科学。

原文发布于微信公众号 - AI科技大本营(rgznai100)

原文发表时间:2017-10-03

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏PPV课数据科学社区

【笔记】CDA LEVEL II 数据建模师培训学习笔记(一)软件安装

? 写在前面:此笔记是PPV课学员张梦根据李玉玺老师在CDA LEVEL II 数据建模师培训的上课内容整理而成的。 ———————————–作者说明——...

360100
来自专栏嵌入式程序猿

看图快速学变频器

在嵌入式开发中,经常会涉及到对电机的控制,目前交流电动机的变频控制应用非常广泛,所以我们来简单看图介绍下变频器 (variable-frequency driv...

33050
来自专栏Albert陈凯

算法与数据结构algorithm

算法与数据结构 《Data structures》 介绍:高级数据结构大全,基本算法:二叉树等 《基于用户投票的排名算法(一):Delicious和Hacker...

38050
来自专栏顶级程序员

用Python模拟弹道轨迹

转自:中国统计网(小编微信:itongjilove) ‍作者:Toby:python数据科学爱好者。国内最大药品数据中心任职,二十多个数据库负责人。 最近美国...

60050
来自专栏BestSDK

如何用深度学习来识别恶意软件

这是一个悲伤的故事,你可能经历过。 你又热又渴,看到桌子上有一瓶看起来像水的东西,来不及思考,揭开瓶盖喝了一大口。哦!漏!是油! 时间回到10秒前,我们重来一次...

34590
来自专栏美团技术团队

美团点评旅游搜索召回策略的演进

背景 美团点评作为最大的生活服务平台,有丰富的品类可供用户选择,因此搜索这个入口对各业务的重要性不言而喻,除了平台搜索外,业务搜索系统的质量和效果对用户体验、商...

789110
来自专栏量子位

AI说:你的书法有咖喱味丨看字识国别

15420
来自专栏专知

【2018元旦】好玩的人工智能“李白”为您作诗,输入您的2018心愿词就行!

2018开启!祝各位专知用户元旦快乐!感谢对专知的支持!在此之际,专知小组为大家准备一个好玩的元旦作品 - 人工智能“李白”作诗,祝大家开心快乐! ▌AI“李白...

45490
来自专栏新智元

邓侃解读:医疗关键数据时间序列敏感度分析的通用方法

---- 新智元专栏 作者:邓侃 【新智元导读】密歇根州立大学、康奈尔大学腾讯研究院的几位学者,联名发表了一篇题为 “Identify Suscept...

40160
来自专栏AI科技大本营的专栏

AI 技术讲座精选:数据科学家线性规划入门指南

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

39930

扫码关注云+社区

领取腾讯云代金券