Том 15, номер 3, 2008 г., Стр. 22-30
УДК 519.87+519.854
В. Т. Дементьев, А. В. Пяткин
О децентрализованной транспортной задаче
Аннотация:
Рассматривается децентрализованная транспортная задача, когда потребители действуют индивидуально, максимизируя каждый свою собственную выгоду, а производитель определяет только очерёдность их обслуживания. Показывается, что данная задача NP-трудна, и предлагается эффективный приближённый алгоритм с оценкой точности решения для случая одинаковых объёмов спроса.
Ключевые слова: транспортная задача, двухуровневое программирование, алгоритмическая сложность, NP-полнота, приближённый алгоритм.
Дементьев Владимир Тихонович 1
Пяткин Артём Валерьевич 1
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
е-mail: artem@math.nsc.ru
Статья поступила 10 октября 2007 г.
Исправленный вариант — 3 марта 2008 г.
