Найти фракцию используя 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 в ГП, какое максимальное значение 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)). Поэтому я думаю, что это должно go с чем-то вроде, учитывая B = x_1 + x_2

максимизировать лямбда

с учетом M_BP * L_BP <= C_B </p>

и B_BP> = 0

Где я предполагаю (это все мои попытки, может быть, все очень неправильно), что L_BP = (x,y) vector и lambda = (x+y)/normalization, а также что C_B каким-то образом относится к вектору B.

Извините, если мой первый вопрос слишком запутанный, я начинаю здесь.

Answer 1

Если я правильно понимаю вашу проблему, я думаю, что это возможно решить в математическом смысле. Позволь мне объяснить. Поскольку целевая функция является линейной в лямбде (как указывает Superkogito), максимум (или минимум) всегда достигается в одной из угловых точек. Используя это, вы можете вычислить лямбду.

Позвольте мне начать с нескольких простых примеров. Для любой точки в пределах черного многоугольника ясно, что лямбда равен 1: вы можете просто поставить B = B_BP. Теперь давайте возьмем B = (-1, 3). Если вы возьмете любую черную точку, отличную от B_BP = (-1, 0), и у вас лямбда> 0, то с любой зеленой точкой в ​​квадрате ваша x-координата будет выше -1. Поэтому лучшее, что вы можете сделать, это поставить B_BP = (-1, 0). Тогда зеленая точка должна быть B_GP = (-1, 3), поэтому lambda = 0.

Следуя той же логике c, вы можете видеть, что на ребре, определяемом конечными точками (-1, 0 ) и (-1, 3) вы всегда будете использовать B_BP = (-1, 0) и B_GP = (-1, 3). Поднимаясь по этому краю, лямбда будет уменьшаться с 1 до 0. В (-1, 1) лямбда = 2/3, в (-1, 2) лямбда = 1/3. То же самое для верхнего края между (-1, 3) и (2, 3): в (0, 3) лямбда = 1/3 и так далее. Для зеленого треугольника с углом (4, 3) вы должны использовать (4, 3) в качестве конечной точки. Тогда в (3, 3), например, лямбда = 1 / 2.

Интересная проблема, очевидно, заключается во внутренних частях треугольников. Здесь также B_GP является одним из углов, а B_BP находится на черной линии, которая является стороной треугольника. Вы можете показать это, предполагая, что есть другое решение, где это не так, а затем доказав, что можно увеличить лямбду, сместив B_GP или B_BP немного влево или вправо. Полное математическое доказательство было бы слишком длинным, я думаю. Теперь давайте возьмем треугольник слева, с зеленым углом (-1, 3) и черной стороной между (-1, 0) и (2, 3). Тогда для максимальной лямбды B_GP = (-1, 3) и B_BP на черной стороне. Поскольку B = лямбда * B_BP + (1 - лямбда) * B_GP, это дает вам два уравнения. А поскольку B_BP находится на линии y = x + 1, это дает вам третье уравнение. Из них вы можете решить x- и y-координаты B_BP и лямбды (с учетом точки B).

Я сделал это и пришел к лямбде = (Bx - By + 4) / 3. Координаты тогда B_BP - это B_BPx = (Bx + 1 + лямбда) / лямбда и B_BPy = (By - 3 + 3 * лямбда) / лямбда (просто заполните лямбду). Например, для точки (0, 2) у вас будет лямбда = 2/3. Вы можете сделать то же самое для двух других треугольников, я тоже это сделал.

Подведу итог:

Для левого треугольника: lambda = (Bx - By + 4) / 3

Для верхнего правого треугольника: лямбда = (-By - Bx + 7) / 2

Для нижнего правого треугольника: лямбда = By - Bx + 4

Программирование это теперь тривиально. Если вы хотите, я могу дать вам соответствующие координаты B_BP для двух других треугольников, пожалуйста, дайте мне знать. Кстати, вы можете прийти к ним, проведя прямую линию через угол треугольника и B.

Конечно, это работает только тогда, когда целевая функция линейна. В других случаях вам придется использовать подход, предложенный Superkogito. Я надеюсь, что я правильно понял ваш вопрос, пожалуйста, простите меня, если нет! По крайней мере, я нашел это хорошим математическим испытанием.

Answer 2

На мой взгляд, проблема нуждается в лучшей формулировке. Я не уверен, решит ли это вашу проблему, но, надеюсь, это поможет. Поэтому я предлагаю использовать scipy.optimize.minimize , чтобы решить эту проблему оптимизации, и просто инвертировав знак или используя инверсию, вы можете преобразовать максимизацию в минимизацию.

Кроме того, поскольку вы Основывая свой код на случайных точках из BP, GP и случайной точки B, вы должны также ввести их в свой входной вектор. Из входного вектора вы можете вычислить лямбда-коэффициенты (я назвал эту переменную 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. ]