Том 14, серия 2, номер 1, 2007 г., Стр. 43–58
УДК 519.854.2
И. Л. Васильев
Метод декомпозиции для задачи о $p$-медиане на несвязном графе
Аннотация:
Рассматривается задача оптимального замещения, которая формулируется как задача о $p$-медиане. Практическое приложение данной задачи возникает в автомобильной промышленности, где существуют примеры, которые определяются на графах, состоящих из нескольких десятков тысяч вершин и нескольких миллионов дуг. Отличительной особенностью любой такой задачи является то, что граф состоит из нескольких компонент связности. Эта структура графа используется для декомпозиции исходной задачи в серию подзадач о $p$-медиане меньшей размерности. Предложенная декомпозиция естественным образом позволяет использовать параллельные вычисления при программной реализации метода. Эффективность предложенного подхода иллюстрируется численными экспериментами на практических примерах.
Васильев И. Л. 1
1. Институт динамики систем и теории управления СО РАН,
ул. Лермонтова, 134, 664033 Иркутск, Россия
е-mail: vil@icc.ru
Статья поступила 13 сентября 2006 г.
Исправленный вариант — 22 января 2007 г.
