python - 使用 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以某种方式与向量有关 B .
对不起，如果我的第一个问题太乱，我从这里开始。

Answer 1

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

此外，由于您的代码基于来自 BP、GP 和随机点 B 的随机点，因此您也应该将它们输入到您的输入向量中。您可以从输入向量计算 lambda 系数(我在代码中将此变量命名为 k)。这种方法将返回满足目标函数最小输出约束条件的输入向量的值 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. ]