跳至主要内容

用电子表格进行线性规划

学习如何使用电子表格以图形方式求解线性规划问题。
· 10分钟 阅读

使用 AI 探索

作为一家公司的管理者，您总是面对有限的资源，而高层管理的期望是让您最大化地利用这些资源。从时间效率到资本使用，从土地到劳动力，从供应链到生产——几乎您所做的一切，都是为了优化产出。

大多数航空公司都会优化航班时刻表，以获得最高收入和最低成本。这些时刻表涉及大量情境和限制，如特定地点的飞机数量、燃料、机组人员，以及航线类型（热门且盈利的航线）。这些情境和限制被称为在最受欢迎且最盈利航线上执飞的约束。线性规划用于为给定的受限问题寻找解。

在本教程中，您将了解线性规划，将涵盖以下主题：

线性规划简介

从数学上讲，线性规划是在给定条件/约束下，对多个变量的线性目标进行优化（最小化或最大化），要求满足一组线性不等式。线性规划可用于规划各类经济活动，如货物与服务运输、产品制造、电力系统优化以及网络流。LP 问题可用多种技术求解，例如图解法、单纯形法和 Karmakar 方法。

LPP 基本概念

下面来看一些线性规划的基本术语：

  • 决策变量是在目标函数中使用的变量，这些变量决定您的输出。决策者可以通过决策变量来控制目标函数的取值。求解任何线性规划问题时，首先需要识别决策变量。

  • 约束是一组限制或情境条件。约束可以是等式或不等式形式。约束会限制决策变量的取值。

  • 目标函数是需要最大化或最小化的利润或成本函数。它是进行决策的主要目标。

  • 最优解是在所有可行解中使目标函数达到最大或最小的解，例如最大利润或最小成本。它是目标函数的最佳取值。

可行域图

  • 可行解是满足所有约束的决策变量取值集合。若至少存在一个可行解，则 LP 问题为可行。

  • 不可行解是指决策变量的取值集合不满足所有约束，即不存在最优解。若不存在满足全部约束的解，则 LP 问题为不可行。

  • 可行域是满足约束的所有可能取值的区域，或所有约束的交集。它包含所有不等式、等式以及整数约束。

  • 非负性约束指决策变量只能取非负值。此类约束为大于或等于零。

LPP 问题的构建（含示例）

构建线性规划模型包括以下步骤：

  • 识别决策变量
  • 确定目标函数
  • 识别约束条件
  • 定义非负性约束

在线性规划问题中，决策变量、目标函数和约束都必须是线性的。

问题描述：某家具经销商只经营两种商品——桌子和椅子。他有 50,000 卢比可用于投资，且最多只能存放 60 件货物。一张桌子成本为 2,500 卢比，一把椅子成本为 500 卢比。他估计每售出一张桌子可获利 250 卢比，每售出一把椅子可获利 75 卢比。他想知道在可用资金下应购买多少张桌子和多少把椅子，才能使总利润最大化，且假设他买来的商品都能卖出。（来源）

在这个示例中，您会注意到——

  1. 经销商可以将资金投资于购买桌子、椅子，或两者的组合。不同的投资策略会带来不同的利润。（来源）
  2. 他的投资最多为 50,000 卢比，存储空间也最多为 60 件。（来源）

数学建模：

假设他只购买桌子，不买椅子，那么他可以购买 50000/2500 = 20 张桌子。在这种情况下，他将获得 250 x 20 = 5,000 卢比的利润。或者他只购买椅子，不买桌子，则可以购买 50000/500 = 100 把椅子。

在这种情况下，他将获得 75 x 60 = 4,500 卢比的利润。

他可以购买的桌椅组合可能有很多种。

假设他购买 X 张桌子和 Y 把椅子，则 X 和 Y 必须为非负数。

  1. 经销商用于购买桌椅的金额最多为 50,000 卢比，因此——

    2500 X + 500 Y <= 50000（投资约束），或 5 * X + Y <= 100 ………………………………………… 方程 1

  1. 他最多可存放的数量为 60。

    X + Y <= 60 ………………………………………… 方程 2

  1. 经销商希望以能使其利润 Z 最大化的数量购买，因此方程为——

    Max Z : 250 X + 75 Y

目标函数： Max Z: 250 X + 75 Y

满足以下约束：

5 * X + Y <= 100,
X + Y <= 60 and
X,Y >= 0

来源： http://ncert.nic.in/ncerts/l/lemh206.pdf

在电子表格中用图解法求解 LPP

线性规划示例

目标函数： Max Z: 250 X + 75 Y

满足以下约束：

5 * X + Y <= 100,

X + Y <= 60 and

Where X,Y >= 0

步骤 1： 按下图所示在 Excel 中写出函数。

excel 示例 1

步骤 2： 在电子表格中写好目标函数和约束后，计算约束 C1 和 C2 的取值。可以将另一个变量的值设为 0 来计算。如对 C1，当 X = 0 时，Y 的值为 Y = 100；当 Y = 0 时，X 的值为 X = 20。C2 的计算同理。

excel 示例 2

步骤 3： 现在计算出数值后，开始绘制图表。选择 C1 约束的数值，转到“插入”，绘制带平滑线的散点图。您可能会看到如下图表。

excel 示例 3

如果看起来像这样，不用担心，按以下步骤更改。右键单击图表，转到“选择数据”，您会看到两个系列，删除系列 2，并编辑系列 1。

excel 示例 4

将系列命名为 C1，并将其 X 值改为 C1 的 A 列值、Y 值改为 C1 的 B 列值。然后单击“确定”。您会看到如下图表：

excel 示例 5

步骤 4： 再次右键单击图表进入“选择数据”，并添加另一个系列。将其命名为 C2，在 X 值中选择约束 C2 的 X 列值，在 Y 值中选择约束 C2 的 Y 列值。您的图表将如下所示：

excel 示例 6

步骤 5： 现在图已经绘制出来，您需要找出可行域：

excel 示例 7
excel 示例 8

现在在可行域内有 4 个点（O、A、B、C），您需要在这些点上计算目标函数值，以确定哪个点能给出目标的最大值。

步骤 6： 要计算目标函数值，请按以下步骤操作：

分别计算每个点的目标函数：

  • 在点 O，(X, Y) 的坐标为 (0, 0)，因此目标函数值为 = (2500+750) = 0
  • 在点 A，(X, Y) 的坐标为 (0, 60)，因此目标函数值为 = (2500+753) = 4500
  • 在点 B，(X, Y) 的坐标为 (20, 0)，因此目标函数值为 = (2503+750) = 5000

  • 在点 C 要找到点 Z 的坐标值，需求出约束直线 C1 与 C2 的交点。您将使用 MMULT() 和 MINVERSE() 函数来计算两条方程的交点。

  • MMULT(MINVERSE(array),array) # 这将给出二元方程组的解值。或，=MMULT(MINVERSE(AB17:AC18), AE17:AE18)，在使用该公式前，选中 X 和 Y 的单元格（黄色高亮的单元格），使用该函数计算两个方程的交点，并按 CTRL+SHIFT+ENTER

excel 示例 9

Z 的最终取值：

excel 示例 10

如您所见，在这个线性最大化问题中，Z 的最大值出现在点 B，最大值为 6,250 卢比。因此，为了使利润最大化，经销商应购买 10 张桌子和 50 把椅子。

LPP 的应用场景

线性规划用于求解运筹学中的最优解。LP 能在给定的约束与限制下找到最优方案。LP 适用于各类问题，如农业、工程、制造、能源、物流与供应链等领域的经济活动。

  • 工程师在制造与生产行业中应用线性规划来优化可用资源，从而获得最大利润。

  • 物流与运输行业使用线性规划来寻找最短路径/路线、行程时间以及定价策略。

  • 工程师在能源领域应用线性规划。他们优化电力负荷、最短配电线路，并优化电网设计。

  • 在农业领域，工程师可借助线性规划来确定应种植的作物类型和数量，以高效提升收入。

  • 在食品行业，线性规划可帮助健康管理人员和营养师规划膳食需求，并以低成本组合食材，从而预防非传染性疾病。

结语

恭喜您读完本教程！

您已经了解了许多有关线性规划的细节。您学习了什么是线性规划、LP 中的基本概念与术语、LP 问题的建模、使用图解法求解 LP 问题，以及 LP 的应用案例。

希望您现在能够运用线性规划的概念，在您的组织中做出决策，或为决策者优化结果。感谢阅读本教程！

欢迎查看我们的电子表格中的图表教程。

如果您想进一步学习电子表格，可参加以下 DataCamp 课程：

主题

数据可视化