#math #mathematical-optimization #linear-programming
#математика #математическая оптимизация #линейное программирование
Вопрос:
У меня есть проблема оптимизации следующим образом.
Учитывая массив положительных целых чисел, например, (y1 = 2, y2 = 3, y3 = 1, y4 = 4, y5 = 3) , я стремлюсь максимизировать сумму значений функций f(x) , где f(x) = x if x y <= m и f(x) = 0 в противном случае. ( m является положительным целым числом)
Например, в этом конкретном примере выше (с m = 5 ) оптимальным x значением является 2 , поскольку сумма была бы 2 2 2 0 2 = 8 , которая является наибольшей среди других возможных значений для x (неявно, возможные x будут варьироваться от 0 и 5 )
Я, конечно, могу исчерпывающе рассчитать и сравнить суммы, полученные по всем возможным значениям x, и выбрать x, который дает наибольшую сумму, при условии, что диапазон значений x достаточно мал. Однако, если диапазон становится большим, этот метод может стать чрезмерно дорогим.
Интересно, есть ли что-нибудь, что я мог бы использовать из таких вещей, как линейное программирование, для более общего и правильного решения этой проблемы.
Комментарии:
1. Вы ответили на вопрос: en.wikipedia.org/wiki/Linear_programming#Standard_form . Не могли бы вы указать конкретную проблему, могу я не видеть?
2. Я не понимаю вашу постановку задачи. Откуда вы берете значение для y?
3. Вы задали 10 вопросов и НИ РАЗУ не проголосовали. Все ли ответы, которые вы получили, заслуживают одобрения?
4. @Igor: приведенный выше пример может быть конкретной проблемой, хотя конкретные значения массива и m могут различаться. Вот почему я попросил более надежное и общее решение. Спасибо за вики-страницу, и я изучу ее…
5. @ThomasMcLeod: y можно рассматривать как массив y = (y1, y2, y3, …,yn). В приведенном выше примере n = 5. Другая переменная m определяет «верхнюю границу» суммы между x и yi (i от 1 до n), за которой значение функции f (x) = 0
Ответ №1:
Здесь нет необходимости в линейном программировании, просто сортировка и один проход для определения оптимального x.
Псевдокод является:
getBestX(m, Y) {
Y = sort(Y);
bestSum = 0;
bestX = 0;
for (i from 0 to length(Y)) {
x = m - Y[i];
currSum = x * (i 1);
if (currSum > bestSum) {
bestSum = currSum;
bestX = x;
}
}
return bestX;
}
Обратите внимание, что для каждого i мы знаем, что если x = m - Y[i] , то f(x) = x для каждого элемента до i включительно и f(x) = 0 для каждого элемента после, поскольку Y находится в порядке возрастания.
Комментарии:
1. Это хорошее решение, поскольку сортировка обеспечивает приятное свойство, которое вередесмаралд описал выше. Хотя ответ решает вопрос программно, мне интересно, как мы можем решить это численно как математическую задачу.