使用 LP 求分数

Question

我有两个多边形BP，GP并由-x+y<=1 and x+y<= 5 and x-y<=3 and -y <= 0黑色多边形和-1<=x<=4 and 0 <= y <= 3绿色多边形的不等式约束集描述。

我的目标是使用 LP 来找到分数问题的最佳解决方案：鉴于BGP 中的最大值是多少lambda，使得

B = λ*B_BP + (1-λ)*B_GP

换句话说，我想B在上述意义上找到多边形内部的最大部分。对于我奋力写一个LP计划，我认为，如果我们写BP作为矩阵不等式条件，我们得到每一个B_BP是这样的 M_BP*B_BP <= C人C是一个载体(1,5,3,0)，并M_BP为矩阵((-1,1),(1,1),(1,-1),(0,-1))。所以我认为它应该类似于，给定 B = x_1+x_2

最大化 lambda

服从 M_BP*L_BP <= C_B

并且 B_BP >= 0

我认为（这是我的全部尝试，可能都是非常错误的）那个L_BP = (x,y)vector 以及lambda = (x+y)/normalization它C_B与 vector 有某种关系B。

对不起，如果我的第一个问题太乱，我从这里开始。

Answer 1

如果我正确理解你的问题，我认为可以从数学意义上精确地解决这个问题。让我解释。由于目标函数在 lambda 中是线性的（正如 Superkogito 指出的），因此总是在角点之一达到最大值（或最小值）。通过使用它，您可以计算 lambda。

让我从一些简单的例子开始。对于黑色多边形内的任何点，很明显 lambda 为 1：您可以直接输入 B = B_BP。现在我们取 B = (-1, 3)。如果您取 B_BP = (-1, 0) 以外的任何黑点并且 lambda > 0，那么对于正方形内的任何绿点，您的 x 坐标将高于 -1。所以你能做的最好的就是输入 B_BP = (-1, 0)。那么绿点应该是 B_GP = (-1, 3)，因此 lambda = 0。

遵循相同的逻辑，您可以看到，在端点 (-1, 0) 和 (-1, 3) 定义的边上，您将始终使用 B_BP = (-1, 0) 和 B_GP = (-1, 3) 。沿该边缘上升，lambda 将从 1 减小到 0。在 (-1, 1) 中 lambda = 2/3，在 (-1, 2) 中 lambda = 1/3。对于 (-1, 3) 和 (2, 3) 之间的上边缘也是如此：在 (0, 3) 中 lambda = 1/3 等等。对于角为 (4, 3) 的绿色三角形，您必须使用 (4, 3) 作为端点。那么在 (3, 3) 中，例如 lambda = 1/2。

有趣的问题显然是在三角形的内部。这里，B_GP 也是其中一个角，B_BP 位于三角形边的黑线上。您可以通过假设存在另一种解决方案（但情况并非如此）来证明这一点，然后证明可以通过将 B_GP 或 B_BP 向左或向右移动一点来增加 lambda。我想，完整的数学证明对于这里来说太长了。现在我们看左边的三角形，绿色角为 (-1, 3)，黑色边位于 (-1, 0) 和 (2, 3) 之间。那么对于最大 lambda，B_GP = (-1, 3) 并且 B_BP 在黑色一侧。因为 B = lambda * B_BP + (1 - lambda) * B_GP，所以这给出了两个方程。因为 B_BP 位于 y = x + 1 线上，所以得出第三个方程。由此您可以求解 B_BP 和 lambda 的 x 和 y 坐标（给定点 B）。

我已完成此操作并得出 lambda = (Bx - By + 4) / 3。B_BP 的坐标为 B_BPx = (Bx + 1 + lambda) / lambda 和 B_BPy = (By - 3 + 3 * lambda) / lambda （只需填写 lambda）。例如，对于点 (0, 2)，lambda = 2/3。你可以对另外两个三角形做同样的事情，我也这样做了。

我总结一下：

对于左三角形： lambda = (Bx - By + 4) / 3

对于右上三角形： lambda = (-By - Bx + 7) / 2

对于右下三角形： lambda = By - Bx + 4

现在对此进行编程是微不足道的。如果你愿意的话，我可以给你另外两个三角形的B_BP对应的坐标，请告诉我。顺便说一下，你可以通过画一条穿过三角形和B的角的直线来得到它们。

当然，这仅在目标函数是线性时才有效。在其他情况下，您必须使用 Superkogito 建议的方法。我希望我正确理解了你的问题，如果没有理解，请原谅！至少我发现这是一个很好的数学挑战。