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

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

Dates:

Submitted:	Apr 23, 2025
Accepted:	Jul 21, 2025
Published print:	Aug 26, 2025
Published online:	Aug 26, 2025

Identifiers:

Elibrary:	82832051
OpenAlex:	W4413834697

Citing: Пока нет цитирований

Altmetrics: