使用 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 找到分数问题的最优解：假设 B 在 GP 中，最大值 lambda 是什么

B = lambda*B_BP + (1-lambda)*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

maximize lambda

subject to M_BP*L_BP <= C_B

and B_BP >= 0

我认为（这是我所有的尝试，可能都是非常错误的）L_BP = (x,y) 向量和 lambda = (x+y)/normalization 以及 C_B 以某种方式与向量 [=14] 相关=].

抱歉，如果我的第一个问题太乱，我就从这里开始。

Answer 1

我认为这个问题需要更好的表述。我不确定这是否能解决您的问题，但希望对您有所帮助。所以我建议使用 scipy.optimize.minimize 来解决这个优化问题，只需反转符号或使用倒数，就可以将最大化转换为最小化。

此外，由于您的代码基于来自 BP、GP 和随机点 B 的随机点，因此您应该将它们也输入到您的输入向量中。您可以根据输入向量计算 lambda 系数（我在代码中将此变量命名为 k）。这种方法将 return 满足约束的输入向量的值与 objective 函数的最小输出 fun 又名最大 kx 和最大 ky .

前面解释的方法可以实现如下：

import numpy as np
import scipy.optimize


# compute k
def k(x):
    x_bp, y_bp = x[0], x[1]
    x_gp, y_gp = x[2], x[3]
    bx  , by   = x[4], x[5]

    # compute k
    kx = (bx - x_gp) / (x_bp - x_gp)
    ky = (by - y_gp) / (y_bp - y_gp)
    return kx, ky


# define objctive/cost function
def fun(x):
    kx, ky = k(x)
    return 1 / kx + 1 / ky

# define constraints (bp raandom point constraints)
cons = ({'type': 'ineq', 'fun': lambda x:  x[0] + x[1] - 5},
        {'type': 'ineq', 'fun': lambda x: -x[0] - x[1] - 3})

# init bounds 
bnds = ((None, None), (0, None), 
        (-1., 4.), (0., 3.), 
        (-1., 4.), (0., 3.))

# init vars vec
#x = [x_bp, y_bp, x_gp, y_gp, bx,   by]
x0 = [ 0.1,  0.2,  0.3,  0.5, 0.6, 0.5]

# optimize 
res = scipy.optimize.minimize(fun, 
                              x0, 
                              bounds=bnds, 
                              constraints=cons)

# print result
print("optimal x: ", np.round(res.x, 3))

# print optimal k 
print("optimal k: ", np.round(k(res.x), 3))

请注意，您可能需要稍微调整一下代码并使用初始值 x0 和边界，但这应该可以解决问题。发布的代码片段产生以下输出：

optimal x:  [0.1 0.2 0.3 0.5 0.6 0.5]
optimal k:  [-1.5 -0. ]

Answer 2

如果我正确理解你的问题，我认为可以从数学意义上准确地解决这个问题。让我解释。由于 objective 函数在 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（给定点 B）的 x 和 y 坐标。

我这样做了，得到了 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画一条直线来到达它们。

当然这只适用于objective函数是线性的。在其他情况下，您将不得不使用 Superkogito 建议的方法。我希望我已经正确理解你的问题，如果不正确请原谅我！至少我发现这是一个很好的数学挑战。

使用 LP 查找分数

Find Fraction using LP

python

linear-programming