线性规划中的图形法

线性规划（LP）是一种数学技术，用于优化线性目标函数，受线性等式和线性不等式约束。目标函数是需要最大化或最小化的公式。图形法是解决线性规划问题最简单的方法之一，有助于理解基本概念。这是一种通过视觉表示解决两个变量线性规划问题的方法。让我们通过例子详细了解图形法。

理解问题

在线性规划中，一个常见的问题是选择最佳的两个活动组合，以最大化或最小化某种结果。这些活动可以是您想要管理的任何东西，例如生产量、工作时间，甚至投资量。

目标函数

线性规划问题中的目标函数是我们想要优化以实现最大利润或最小成本的函数。通常写为：

Z = ax + by

其中，Z是您试图实现的目标，x和y是决策变量，a和b是赋予每个变量实现目标的权重的常数。

限制

线性规划问题中的约束是对决策变量的限制或限制。这些可以是不等式，限制x和y可以采用的值。例如：

2x + 3y ≤ 12

x + y ≥ 3

x ≥ 0

y ≥ 0

不等式表示必须满足的条件，以便解决方案被视为可行。

图形法

图形法涉及在图上绘制每个约束，得到一个可行区域。最佳解决方案位于此可行区域的边界上。以下是使用图形法解决LP问题的一步步方法：

步骤1：绘制约束

每个约束都是一个不等式，可以被绘制为二维图上的直线（如果您有两个决策变量）。例如，考虑以下约束：

• 2x + 3y ≤ 12
• x + y ≥ 3
• x ≥ 0
• y ≥ 0

我们可以通过将不等式变为等式来找到直线：

2x + 3y = 12

x + y = 3

现在找到这些线的截距。例如，让我们找到第一个条件的截距：

• Y截距：设x = 0：3y = 12，所以y = 4。
• X截距：设y = 0：2x = 12，所以x = 6。

这些中间步骤将对两个约束进行，然后进行绘图。

图上的线将如下所示：

  
  
  
  2x + 3y = 12
  
  x + y = 3

步骤2：确定可行区域

一旦所有的线都绘制出来，可行区域就是所有约束重叠的共同区域。这个区域代表了满足所有约束的所有可能解。通常是由不等式所创造的半平面相交形成的多边形或相交区域。

在您的图中阴影或突出显示此区域，因为它对于找到最佳点很重要。

步骤3：找到顶点

可行区域由其顶点或多边形的角点定义。通过求解相交点的线性方程可以识别每个顶点。这些顶点是潜在的解候选点。

例如，如果两条线交叉，求两个匹配方程：

2x + 3y = 12

x + y = 3

通过同时求解这些方程，您可以找到交点。重复此过程以找到可行区域的所有顶点。

步骤4：在每个顶点处评估目标函数

下一步是在可行区域的每个顶点评估目标函数。将每个顶点的(x, y)值代入目标函数：

Z = ax + by

计算每个顶点的Z值，以找出哪个点最大化或最小化目标函数。

例如，如果您的顶点是(x1, y1)，(x2, y2)，(x3, y3)，等等，计算：

• Z1 = ax1 + by1
• Z2 = ax2 + by2
• Z3 = ax3 + by3

最佳解是提供目标函数最大或最小值的顶点，具体取决于问题。

步骤5：解释解决方案

最后一步是在原始问题的背景下解释解决方案，将数学解转回现实世界的术语。例如，如果您正在求解最佳生产量，解决方案给出了 achieve desired objective.

示例问题

让我们通过一个示例问题使用图形法来说明这些步骤。

问题描述：

一家公司生产两种产品，P1和P2，每单位分别产生$3和$5的利润。公司希望最大化利润。这些产品的生产受到以下约束：

• P1每单位需要1小时加工时间，P2每单位需要2小时。总可用加工时间为10小时。
• P1每单位需要4小时机器时间，P2每单位需要3小时。总可用机器时间为12小时。
• 非负约束：P1 ≥ 0，P2 ≥ 0。

正式的线性规划模型如下：

• 目标函数：Z = 3P1 + 5P2（最大化利润）
• 限制条件：
  • P1 + 2P2 ≤ 10
  • 4P1 + 3P2 ≤ 12
  • P1 ≥ 0
  • P2 ≥ 0

设计障碍

将不等式转换为等式并找到截距以在图上绘制：

P1 + 2P2 = 10

• 截距：(10, 0), (0, 5)

4P1 + 3P2 = 12

• 截距：(3, 0), (0, 4)

绘制这些线并识别可行区域。

  
  
  
  p1 + 2p2 = 10
  
  4p1 + 3p2 = 12

找到可行区域

识别满足所有条件以及非负条件的可行区域。此区域是图上这些条件交叉形成的多边形。

顶点

通过同时解决约束来计算交点：

P1 + 2P2 = 10

4P1 + 3P2 = 12

解法：

为了消去P2，将第一个方程乘以3，第二个乘以2：

3P1 + 6P2 = 30

8P1 + 6P2 = 24

减去其中一个方程：

-5P1 = 6

P1 = 1.2

代入P1到一个原方程以确定P2：

1.2 + 2P2 = 10

2P2 = 8.8

P2 = 4.4

因此有一个点(1.2, 4.4)，通过类似的计算找到所有可能的顶点。

评估目标函数

在每个顶点计算目标函数Z = 3P1 + 5P2。

• 在 (0, 0)：Z = 3(0) + 5(0) = 0
• 在 (10, 0)：Z = 3(10) + 5(0) = 30
• 在 (0, 4)：Z = 3(0) + 5(4) = 20
• 在 (1.2, 4.4)：Z = 3(1.2) + 5(4.4) = 3.6 + 22 = 25.6

结论

在 (10, 0) 达到Z的最大值。因此，最佳利润最大化方案是生产10单位P1和0单位P2。

总之，图形法提供了一种清晰的视觉方法来了解变化如何影响系统，是引入可行性和优化概念的优秀方式。由于超过两个维度的可视化变得不切实际，它限于具有两个决策变量的问题。

评论