Минимизировать абсолютные значения взвешенной суммы чисел
Частью моей проблемы является минимизация абсолютной величины взвешенной суммы определенных чисел. Я должен найти вес.
Допустим, у меня есть набор чисел A, a1, a2, a3 и a4, такой что (a1, a2 > 0), (a3, a4 < 0)
Минимальный вес, скажем, 0,1 (10%), максимальный - 0,4 (40%). Я ищу веса w таким образом, чтобы взвешенная сумма была равна нулю; если ноль невозможен, то ближайший возможный ноль. Для этого можно использовать простую линейную модель:
Minimise E
E >= SUM w * a
E >= -(SUM w * a)
SUM w = 1
w >= 0.1 for all w
w <= 0.4 for all w
Простой линейной программы достаточно, чтобы найти решение очень быстро. Однако мне бы очень хотелось найти полиномиальный алгоритм или формулу для этой задачи. Есть идеи? Эта проблема хорошо известна?
Спасибо!
2 ответа
Минимизация (соответственно максимизация) SUM w * a это просто; установите все веса на минимум, а затем от наименьшего а к наибольшему (соответственно от наибольшего к наименьшему) увеличивайте вес с учетом локального максимума до достижения глобального максимума.
Если интервал [min, max] содержит 0, то оптимальное решение может быть реализовано как выпуклая комбинация этих двух решений. В противном случае, принять решение ближе к 0.
Алгоритм эллипсоида был первым алгоритмом полиномиального времени для наихудшего случая для линейного программирования.
Тем не менее, я подозреваю, что вы хотите решить вашу проблему быстро, поэтому вы заинтересованы в алгоритме полиномиального времени.
В этом случае вам будет лучше с симплекс-методом. Несмотря на то, что в худшем случае симплекс экспоненциальный, он представляется наилучшим выбором для большинства практических применений. Неудивительно, что он реализован во всех известных мне качественных решателях.