Реферат: В данной работе рассматривается задача размещения предприятий без ограничения на объемы производства. Эта задача является NP-трудной в сильном смысле. Для ее решения предлагается прямо-двойственный полиномиальный приближенный алгоритм с апостериорной оценкой точности. Он состоит из двух полиномиальных приближенных алгоритмов: алгоритма A1, основанного на жадной эвристике, и алгоритма A2, основанного на отыскании некоторого решения задачи, двойственной к релаксированной исходной постановке. Трудоемкость объединенного алгоритма A равна O(mn(m+logn)), где m – количество возможных мест размещения предприятий, n – количество клиентов. В двойственном алгоритме используется бинарная куча, что позволило существенно уменьшить реальное время работы алгоритма. Уменьшение времени работы особенно проявилось на многоразмерных примерах. Результаты численных экспериментов со случайно сгенерированными данными подтверждают эффективность предлагаемого алгоритма.

Библиографическая ссылка: Гимади Э.Х. , Гончаров Е.Н. , Штепа А.А.
Прямо-двойственный полиномиальный приближенный алгоритм для задачи размещения предприятий
Труды Института математики и механики УрО РАН (Trudy Instituta Matematiki i Mekhaniki UrO RAN). 2025. Т.31. №3. С.77-90. DOI: 10.21538/0134-4889-2025-31-3-77-90 РИНЦ OpenAlex

Даты:

Поступила в редакцию:	23 апр. 2025 г.
Принята к публикации:	21 июл. 2025 г.
Опубликована в печати:	26 авг. 2025 г.
Опубликована online:	26 авг. 2025 г.

Идентификаторы БД:

РИНЦ:	82832051
OpenAlex:	W4413834697

Цитирование в БД: Пока нет цитирований

Альметрики: