Том 18, номер 1, 2011 г., Стр. 20-26

УДК 519.87+519.854
Дементьев В. Т., Шамардин Ю. В.
Об одном полиномиально разрешимом случае децентрализованной транспортной задачи

Аннотация:
Рассматривается частный случай децентрализованной транспортной задачи. Матрица транспортных затрат состоит из $n$ строк, $2n$ столбцов и обладает диагональной структурой. Предлагается алгоритм решения задачи на основе метода динамического программирования с временно́й сложностью $O(n^2)$.
Библиогр. 1.

Ключевые слова: децентрализованная транспортная задача, динамическое программирование.

Дементьев Владимир Тихонович ^1,2
Шамардин Юрий Владиславович ¹
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
2. Новосибирский гос. университет,
ул. Пирогова, 2, 630090 Новосибирск, Россия
е-mail: orlab@math.nsc.ru

Статья поступила 8 сентября 2010 г.

Литература

[1] Дементьев В. Т., Пяткин А. В. О децентрализованной транспортной задаче // Дискрет. анализ и исслед. операций. — 2008. — Т. 15, № 3. — С. 22–30.