运筹学/图形线性规划解决方案

我们现在将尝试找到上一节中介绍的线性规划模型的最优解。我们将采用的方法被称为图形法，可以应用于任何具有两个决策变量的问题。它基本上包括两个步骤：找到可行域或可行空间（即平面上所有可行解所在的区域），然后在所有可行解中识别最优解。

为了开始这个过程，我们首先绘制直线

$6x_{1}+4x_{2}=24$,

$x_{1}+2x_{2}=6$,

$x_{2}-x_{1}=1$,

$x_{2}=2$,

在第一象限。请注意，出于我们的目的$x_{1}=x$ 和 $x_{2}=y$ 在图上。

我们现在将对可行域进行阴影处理。为此，请逐个考虑约束条件。第一个是$6x_{1}+4x_{2}\leq 24$。为了确定它所代表的区域，请选择任何不通过直线$6x_{1}+4x_{2}=24$ 的点，例如 (0,0)。将其代入约束条件$6x_{1}+4x_{2}\leq 24$ 以得到$0\leq 24$。由于这是正确的，我们得出结论 (0,0) 位于 $6x_{1}+4x_{2}\leq 24$ 所代表的区域中。我们得出结论，$6x_{1}+4x_{2}=24$ 这一侧包含 (0,0) 的所有点实际上代表 $6x_{1}+4x_{2}\leq 24$。这一点由直线 $6x_{1}+4x_{2}=24$ 将平面分成两个不同的半部分：一个点满足不等式，另一个点不满足不等式。

通过这种方式，可以对所有不等式进行阴影处理。在所有不等式下都进行阴影处理的区域是整个问题的可行域。(由于我们在第一象限内工作，因此非负性限制成立。)

现在我们准备找出最优解。为此，绘制直线$5x_{1}+4x_{2}=10$。由于$z=5x_{1}+4x_{2}$ 表示目标函数，因此 $5x_{1}+4x_{2}=10$ 表示目标函数值为 10 的点（即总利润为 10）。现在绘制直线 $5x_{1}+4x_{2}=15$，它表示目标函数值为 15 的点。这让我们了解了 z 增加的方向。最优解出现在点 X，该点是任何进一步增加都会导致 z 超出可行域边界的点。X 的坐标可以通过求解 $6x_{1}+4x_{2}=24$ 和 $x_{1}+2x_{2}=6$ 获得，因此 $x_{1}=3$ 和 $x_{2}=1.5$。这是问题的最优解，表明盐 X 和 Y 的数量应分别为 3 和 1.5。这将带来 21 的最大利润，即 *最优值*。

需要注意的是，LP 模型中的最优解总是出现在可行域的 *角点*。即使直线 z=c 与其中一个约束平行，这也成立。尽管这个事实的数学证明将涉及大量的线性代数，但我们可以通过注意到任何可行域中的目标函数都会在接触一个角点后立即滑出该域来满足自己。

最小化示例

让我们来看一个最小化问题。当我们不是得到盐 X 和 Y 的利润，而是得到它们的生产成本时，它就会在实际应用中出现。我们所要做的就是现在将直线 z=c 朝其减少的方向移动，并且我们在这个点（在我们示例中为 (0,0)）处获得了最优解，任何进一步的减少都会将 z 带出可行域。解决问题的另一种方法是将最小化问题转换为最大化问题。为此，只需考虑目标函数的负值。