EN|RU

Том 19, номер 6, 2012 г., Стр. 9-22

УДК 519.7
Гимади Э. Х., Курочкин А. А.
Эффективный алгоритм решения двухэтапной задачи размещения на древовидной сети

Аннотация:
Рассматривается двухэтапная задача размещения производства на древовидной сети при условии, что затраты на транспортировку единицы продукции из пункта в пункт равны сумме длин рёбер в цепи, соединяющей эти пункты. Предложен алгоритм для точного решения данной задачи с трудоёмкостью $O(nm^3)$, где $n$ – число пунктов спроса конечного продукта, $m$ – ограничение сверху на число возможных пунктов размещения производства каждого этапа.
Ил. 3, библиогр. 7.

Ключевые слова: двухэтапная задача размещения производства, полиномиальный алгоритм, древовидная сеть.

Гимади Эдуард Хайрутдинович 1,2
Курочкин Александр Александрович 1

1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
2. Новосибирский гос. университет,
ул. Пирогова, 2, 630090 Новосибирск, Россия
е-mail: gimadi@math.nsc.ru, alkurochkin@ngs.ru

Статья поступила 8 декабря 2011 г.
Исправленный вариант — 22 апреля 2012 г.

 © Институт математики им. С. Л. Соболева, 2015