线性规划问题、解决方案和应用 [附示例]

数据科学有很多应用，其中最突出的应用之一就是优化。 我们都倾向于专注于优化东西。 优化的重点是使用您拥有的有限资源获得最理想的结果。

有各种各样的优化问题可用，有些很小，有些非常复杂。 在浏览它们时，您会发现一个称为线性规划问题的特定类别。 在本文中，我们讨论了它们是什么以及如何处理它们。

假设您是一个水果卖家，可以购买橙子或苹果或两者的某种组合。 但是，您只有 5,000 卢比的预算，并且只能存放 30 袋。 现在，您必须以能够为您带来最高利润的方式购买它们。

现在，一袋橙子的价格为 500 卢比，而一袋苹果的价格为 750 卢比。您可以从销售一袋橙子中赚取 100 卢比，从销售一袋苹果中赚取 200 卢比。

这个问题有多种可能性。 您可能选择只购买橙子，但您的仓库中只有 10 个袋子，您的利润将是 1000 卢比。同样，您可能选择只购买苹果并赚取 1500 卢比作为利润。 您也可以购买两者的组合。

此类问题称为线性规划问题，我们将详细讨论它们。 让我们开始吧：

什么是线性规划？

线性规划是一种使用线性函数来描述复杂关系的方法。 我们线性规划的目标是为这些函数找到最合适的解决方案。 两点之间的真实关系可能非常复杂，但我们可以使用线性规划来简单地描述它们。 线性规划在许多行业中都有应用。

线性规划基础

以下是线性规划的一些基本术语：

约束

决策变量的限制（或约束）称为约束。 大多数时间限制是您解决问题的资源的限制。

决策变量

这些变量定义了您的输出。 您的结果取决于这些变量，这就是我们称它们为“决策变量”的原因。

非消极性限制

线性规划问题的决策变量只能具有非负值。 这意味着您的决策变量的值只能等于或大于零。

目标函数

目标函数是做出决定的目标。 简单来说，它是线性规划问题的最终结果。 例如，当您找到使用给定资源集可以获得的最大利润时，最大利润就是目标函数。

制定线性规划问题

您应该知道如何制定线性规划以将其应用到现实生活中。 假设您是一家玩具制造商，您只生产两种玩具：A 和 B。粗略地说，您的玩具需要 X 和 Y 两种资源来制造。 以下是您对玩具的要求：

• 一单位玩具 A 需要一单位资源 X 和三单位资源 Y

• 一单位玩具 B 需要一单位资源 X 和两单位资源 Y

您有 5 个单位的资源 X 和 12 个单位的资源 Y。您销售这些玩具的利润率为：

• 每售出一件玩具 A 6 印度卢比
• 每售出一件玩具 B 5 卢比

你会生产多少个玩具以获得最大的利润？

解决方案

让我们用一个方程来表示我们的线性规划问题：

Z = 6a + 5b

这里，z 代表总利润，a 代表玩具 A 单位的总数，b 代表玩具 B 单位的总数。 我们的目标是最大化 Z（利润）的价值。

现在，您的公司希望尽可能多地生产这些玩具，但您的资源有限。 我们资源的限制是这个问题的制约因素。 我们总共只有

a + b 5

现在每个玩具 A 和 B 的单位分别需要 3 和 2 单位的资源 Y。 而且我们总共只有 12 个单位的资源 Y，所以在数学上，它看起来像这样：

3a + 2b 12

请记住，玩具 A 的单位值只能是整数。 这意味着我们也有 a->0 和 b<-0 的约束。

所以，现在你有一个适当的线性规划问题。 您可以按照此示例制定其他线性规划问题。 虽然这个例子非常简单，但 LP 问题可能会变得非常复杂。

阅读：线性规划项目的想法和主题

制定线性规划问题的步骤

要制定线性规划问题，请执行以下步骤：

• 找到决策变量
• 找到目标函数
• 识别约束
• 记住非负性限制

如果一个问题满足上述标准，那么它就是一个线性规划问题。 当您在确定问题的类型时，最好记住这个标准。

用 R 解决线性规划问题

如果您使用 R，解决线性规划问题会变得更加简单。 那是因为 R 有 lpsolve 包，它带有专门为解决此类问题而设计的各种功能。 作为数据科学家，您很可能会非常频繁地使用 R 来解决 LP 问题。 这就是为什么我们分享了两个不同的示例来帮助您更好地理解它的实现：

例子

让我们从一个基本问题开始。 一个组织有两种产品，售价分别为 25 卢比和 20 卢比，分别称为产品 A 和 B。 每天，他们有 1800 单位的资源来生产这些产品。 产品 A 需要 20 个资源单元，而 B 需要 12 个资源单元。 这两种产品的生产时间均为 4 分钟，该组织每天总共有 8 个工作小时。 问题是，这些产品的生产数量应该是多少才能使公司的利润最大化？

解决方案：

我们将通过定义其目标函数来开始解决这个问题：

最大（销售额）= 最大（25 y 1 + 20 y 2 ）

这里，25 和 20 分别是产品 A 和 B 的价格，y1 是生产的产品 A 的总单位数，y2 是生产的产品 B 的总单位数。 我们的决策变量是 y1 和 y2。

我们现在将为我们的问题设置约束：

资源限制：

20 岁1 + 12岁2 1800

时间限制：

4年1 + 4年2 8*60

我们的目标是找到我们必须生产的正确数量的产品，以获得最大的利润。

使用 R 解决问题：

我们将使用 lpsolve 来解决这个 LP 问题，并从设置目标函数开始：

> 要求（lp解决）

加载所需的包：lpSolve

> 目标.in <- c(25, 20)

> 目标.in

[1] 25 20

然后我们将为约束构建一个矩阵：

> const <- 矩阵(c(20, 12, 4, 4), nrow=2, byrow=TRUE)

> 常量

[,1] [,2]

[1,] 20 12

[2,] 4 4

> time_constraints <- (8*60)

> 资源约束 <- 1800

> 时间约束

[1] 480

> 资源约束

[1] 1800

现在让我们创建已经定义的方程：

> rhs <- c(resource_constraints, time_constraints)

> 右声道

[1] 1800 480

> 方向 <- c(“<=”, “<=”)

> 方向

[1] “<=” “<=”

一旦添加了所有必要的信息，我们就可以开始寻找最佳答案。 我们的包的语法是：

lp（方向，目标，const.mat，const.dir，const.rhs）

> 最佳 <- lp(direction=”max”, objective.in, const, direction, rhs)

> 最佳

成功：目标函数为 2625

> 摘要（最佳）

长度类模式

方向 1 - 无 - 数字

x.count 1 -none- 数字

目标 2 - 非数字

const.count 1 -none- 数字

约束 8 -none- 数字

int.count 1 -none- 数字

int.vec 1 -none- 数字

bin.count 1 -none- 数字

binary.vec 1 -none- 数字

num.bin.solns 1 -none- 数字

objval 1 -none- 数字

解决方案 2 - 无 - 数字

presolve 1 -none- numeric

compute.sens 1 -none- 数字

sens.coef.from 1 -none- numeric

sens.coef.to 1 -none- 数字

对偶 1 -none- 数字

duals.from 1 -none- numeric

duals.to 1 -none- 数字

比例 1 -none- 数字

use.dense 1 -none- numeric

dense.col 1 -none- 数字

dense.val 1 -none- 数字

dense.const.nrow 1 -none- 数字

dense.ctr 1 -none- 数字

use.rw 1 -none- 数字

tmp 1 -none- 字符

状态 1 -none- 数字

运行上面的代码后，您可以获得我们问题的所需解决方案。

y1 和 y2 的最佳值：

请记住，y1 和 y2 是我们必须生产的产品 A 和产品 B 的单位：

> 最优$解决方案

[1] 45 75

最佳销售数字：

我们可以用获得的 y1 和 y2 的值​​产生的最大利润是：

> 最佳$objval

[1] 2625

另请阅读：机器学习的线性代数

线性规划的用途

正如我们之前提到的，线性规划在许多行业中都有应用。 以下是我们使用它的一些领域：

• 随着送货服务的日益普及，线性规划已成为寻找最佳路线的最受青睐的方法之一。 当你乘坐 Ola 或 Uber 时，该软件会使用线性规划来找到最佳路线。 亚马逊和联邦快递等快递公司也使用它来为他们的快递员确定最佳路线。 他们专注于减少交付时间和成本。
• 机器学习的监督学习基于线性规划的基本概念。 在监督学习中，你必须根据提供的输入数据找到最优的数学模型来预测输出。
• 零售业使用线性规划来优化货架空间。 有这么多品牌和产品可供选择，确定将它们放在商店的哪个位置是一项非常艰巨的任务。 产品在商店中的放置会极大地影响其销售。 Big Bazaar、Reliance、Walmart 等主要零售连锁店使用线性规划来确定产品放置。 他们必须牢记消费者的利益，同时确保最佳的产品放置以产生最大的利润。
• 公司使用线性规划来改善他们的供应链。 供应链的效率取决于许多因素，例如选择的路线、时间等。通过使用线性规划，他们可以找到最佳的路线、时间和其他资源分配来优化效率。

了解有关线性规划和数据科学的更多信息

线性规划是数据科学中最重要的概念之一。 这也是成为一名熟练的数据科学家应该了解的基本主题。 正如我们所讨论的，这个概念有很多应用，你可以在日常生活中找到它的用例。

您可以访问我们的博客，了解有关数据科学及其相关概念的更多信息。 我们有许多宝贵的资源可以帮助您了解更多信息。 以下是一些供您进一步阅读的内容：

• 成为数据科学家的主要原因
• 每个数据科学家都应该知道的算法
• 如何成为一名数据科学家

另一方面，您可以获得数据科学课程，向行业专家学习。 您将通过视频、测验和项目进行交互式学习。 参加课程将帮助您学习成为专业数据科学家的必要技能。 查看 IIIT-B 和 upGrad 的数据科学 PG 文凭，该文凭专为在职专业人士而设，提供 10 多个案例研究和项目、实用的实践研讨会、与行业专家的指导、与行业导师的 1 对 1、400 多个小时与顶级公司的学习和工作援助。