Аннотация:
В данной работе рассматривается задача размещения предприятий без ограничения на объемы производства. Эта задача является NP-трудной в сильном смысле. Для ее решения предлагается прямо-двойственный полиномиальный приближенный алгоритм с апостериорной оценкой точности. Он состоит из двух полиномиальных приближенных алгоритмов: алгоритма $\mathcal A_1$, основанного на жадной эвристике, и алгоритма $\mathcal A_2$, основанного на отыскании некоторого решения задачи, двойственной к релаксированной исходной постановке. Трудоемкость объединенного алгоритма $\mathcal A$ равна $\mathcal O(mn(m + \log n))$, где $m$ — количество возможных мест размещения предприятий, $n$ — количество клиентов. В двойственном алгоритме используется бинарная куча, что позволило существенно уменьшить реальное время работы алгоритма. Уменьшение времени работы особенно проявилось на многоразмерных примерах. Результаты численных экспериментов со случайно сгенерированными данными подтверждают эффективность предлагаемого алгоритма.
Ключевые слова:
задача размещения предприятий, NP-трудная задача, приближенный алгоритм, алгоритм с апостериорной оценкой точности, прямо-двойственный алгоритм, бинарная куча.
Полный текст:
PDF файл (301 kB)
Первая страница:
PDF файл