Из свойств и 2 следует, что решение задачи (1.2), (1.4) сводится к решению т — 1 задачи поиска минимального разреза в и-локальных сетях. Причем вершины И можно выбирать в произвольном порядке. Указанные локальные сети строятся последовательно для е V'. Если на каком-то шаге найдется ј,ј е Ј,ј е R о (пi:(v L ) i ' тој размещается в вершину vj•. При дальнейшем построении Ч-ЛОКиЬНЫХ сетей в них отсутствует вершина с номером ј.
Предлагаемый ниже алгоритм работает в предположении, что существует размещение, удовлетворяющее (1.4). Для проверки этого можно использовать дискретный вариант алгоритма SLP из [1], причем максимальным расстояниям Ьјк необходимо присвоить достаточно большие значения, например равные диаметру сети Т.
Опишем алгоритм по шагам.
Шаг 1. Rl ф, Ь := ф, V'. Переход на шаг 2.
Шаг 2. Для каждой е V' строим множества Rl и Ll,j е Ј, Rl := Rl и {ј}, если существует vt•e Е V/ : ск = d(Vl, vt) и не существует v/} : d(Vl, Vf); Ь := Ll {ј}, Vj,j е .I, если Зу е е (V\V/) : с < d(Vf, Ч). Переход на шаг З.
Шаг З. Если V' = ф то переход на шаг 7. Иначе выбираем
произвольную v/ е 
Переход на шаг 4.
Шаг 4. Строим ч-локальную сеть. L := пh : 
— множество ј, ј е .I ”левее” Ч. R
: Rh — множествој,ј е Јв И или
”правее”. Вершины сети s, т, R). Пропускная способность дуги (s, ј): Еh : 
+ Еке LLlkj, а дуги (Л t) : Еh V'l Whj + R 
К) R). Переход на шаг 5.
Шаг 5. Находим минимальный разрез (С, С) локальной сети Ч.
Шаг 6.
Полагаем Ц Ь С, Щ 
С. Переход на шаг З.
Шаг 7. Дляј е .I, е V' полагаем л(ј) :=f, еслиј е Rf0l (пi
: (Ч, гц) и тс(ј) := r, если Зј е 
L . Стоп.
На шаге 2 обеспечивается соблюдение ограничений (1 А). На шаге 4 в углокальную сеть включаются вершиныј е .JML R), так как новые объекты, попавшие в множество L, должны быть размещены ”левее” Ч, а попавшие в множество R — соответственно, в И или ”правее”. На последнем шаге работы алгоритма по множествам Rl и Ь, И е V', однозначно строится оптимальное решение задачи (1.2), (1.4).
Отметим, что трудоемкость предложенного алгоритма решения задачи (1.2), (1.4) равна О(тах(т2п, тп3)). Действительно, трудоемкость шага 2, который выполняется только один раз, равна О(т2п). Далее на каждой итерации алгоритма (шаг З) из множества V' исключается ровно одна вершина, т.е. количество повторений равно т — 1. Если искать на шаге 5 минимальный разрез с помощью максимального потока в сети с п + 2 вершинами, то это можно сделать с трудоемкостью О(п3) (см. [5]). Следовательно, трудоемкость выполнения шагов 3—6 равна О(тп3). Таким образом, алгоритм решения задачи (12), (1.4) имеет трудоемкость О(тах(т2п, тп3)).
Решение приведенным алгоритмом возможно в следующих случаях.
1. Все дуги дерева имеют единичную длину и все сг — целые числа. Тогда существует оптимальное решение такое, что х. е е (см. [6]).
2. На сети Т вводятся фиктивные вершины, каждая из которых разбивает дугу на две в том месте, где новый объект ј,ј е Ј, находится на максимальном расстоянии сг от некоторого объекта i, i е 1. Фиктивных вершин не более О(т2п).
СПИСОК ЛИТЕРАТУРЫ
1. ЗабуДский ГГ., Филимонов Д.В. Решение дискретной минимаксной задачи размещения на сети // Изв. вузов. Математика. 2004. № 5. С. 33—36.
2. Francis R.L., Lowe Т.Ј., RatliffD.H. Distance constraints for tree network multifacility location problems // Орerat. Res. 1978. V. 26. № З. Р. 570-595.
З. Erkut Е., Francis R.L., Tamir А. Distance-constrained multifacility minimax location problems оп tree network // Networks. 1992. № 22. Р. 37-54.
4. Erkut Е., Francis R.L., Lowe Т.Ј., Tamir А. Equivalent mathematical programming formulations of monotonic tree network location problems // 0perat. Res. 1989. V. 37. № З. Р. 447—461.
5. ПапаДимитриу Х., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. М.: Мир, 1985.
6. Picard Ј.С., RatliffD.H. А cut approach to the rectilinear distance facility location problem // 0perat. Res. 1978.
V. 26. М З. Р. 422-433.
46 М З
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.