Оптимальное размещение взаимосвязанных объектов на древовидных сетях с ограничениями на расстояния

ЖУРНАЛ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ И МАТЕМАТИЧЕСКОЙ ФИЗИКИ, 2006, том 46, № З, с. 395-400

удк 519.658

ОПТИМАЛЬНОЕ РАЗМЕЩЕНИЕ ВЗАИМОСВЯЗАННЫХ

ОБЪЕКТОВ НА ДРЕВОВИДНЫХ СЕТЯХ

С ОГРАНИЧЕНИЯМИ НА РАССТОЯНИЯ ¹)

2006 г. Г. Г. Забудский

(644099 Омск, ул. Певцова, 13, Омский фил. Ин-та матем. СО РАН) e-mail: zabudsky@iitarn.omsk.net.ru

Поступила в редакцию 13.05.2005 г.

Рассматриваются задачи оптимального размещения взаимосвязанных объектов на древовидных сетях, в узлах которых расположены фиксированные объекты. Между объектами заданы ограничения на максимальные расстояния. Предлагаются полиномиальные алгоритмы решения. Библ. 6. Табл. 1.

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

1. ПОСТАНОВКА ЗАДАЧ

В узлах У = { ^Vl' , vm} связной неориентиованной сети Т = (У, Е) расположены фиксированные объекты. Новые объекты размещаются в точках Х = (М, х ) которые могут быть распложены как в вершинах, так и на дугах. Пусть { 1, 2, т } и Ј= { 1, 2 п Расстояние d(x, у) между точками х и У в сети Т определяется как длина кратчайшего пути. Заданы vvr > 0 (wr = wji) и ијк > 0 (ијк = икј) — удельные стоимости связей между фиксированным объектом i и размещаемым ј, i е I,j е Ј, а также стоимости размещаемых объектовј и К соответственно,ј, К е Ј,ј К и максимальные расстояния сг (с = CJi), Е Е ], (bjk — К е .Ј,ј К. Необходимо найти такое размещение новых объектов на сети Т, удовлетворяющее ограничениям на максимально допустимые расстояния, чтобы либо максимальное взвешенное расстояние, либо суммарная стоимость связей между всеми объектами были минимальными:

d(Vi, Х.) СИ,

Задачу (1.1), (1 . З), (1.4) будем называть задачей минимизации максимальной связи (ММС), а ( 1.2), (1.3), (1.4) — задачей минимизации суммарной связи (МСС). В [1] для решения задачи ММС на общей сети предложен алгоритм ветвей и границ. Для древовидных сетей в [2] решена задача ( 1.1), а в [З] предложены полиномиальные алгоритмы для задачи ММС. В работе [4] приведено сведение задач ММС и МСС на деревьях к задачам линейного программирования (ЛП).

В данной работе рассматривается древовидная сеть Т. Для проверки совместности ограничений (1.3) и (1.4) строится вспомогательная сеть Л/ следующим образом (см. [2]). Каждому фиксированному объекту i ставится в соответствие узел Ер i е I, а каждому новому объектуј — узел л^к, м; Е .Ј. Узлы Ei и л^ь соединяются дугой длины се а узлы и Nk — дугой длины Ьјк. Длина кратчаишего пути в сети между узлами Es и Е, обозначается через L(Es, Et), s, t 1, s < t. В [2] доказано, что ограничения (1.3), ( I .4) эквивалентны следующим неравенствам:

                                                                    L(Es, Е,) d(vs, vt), s, te 1, s<t.                                                  (1.5)

Работа выполнена при финансовой поддержке Р ГНФ (грант 04-02-00238а).

395

Прямым путем в сети л^ь между узлами Es и Ет называется путь, не содержащий узлов Ц, i t. Условия (1.5) справедливы и в том случае, когда L(Es, Et) — длина кратчайшего прямого пути между узлами Es и Ет (см. [4]). Для общей сети эти условия лишь необходимые (см. [2]).

Найти допустимое размещение на дереве можно с помощью процедуры SLP (Sequential Location Procedure, см. [2]).

2. РЕШЕНИЕ ЗАДАЧИ ММС

Задачу (1.1), (1.3), (1.4) перепишем в эквивалентном виде с помощью введения переменной z:

                                                                                                                       (2.1)

Отметим, что для данной задачи длины дуг во вспомогательной сети N зависят от параметра z и являются кусочно-линейными вогнутыми функциями. Обозначим указанную сеть через N(z), а длину кратчайшего пути в ней — через L(Es, Et : z). Условия, аналогичные (1.5), имеют вид

                                                    L(Es, : z) d(vs, И), s, t e I, s < t.                                    (2.4)

Для решения задачи в [З] предлагается следующий алгоритм. На первом этапе находится верхняя оценка оптимального значения z

                                             ZUB              тах         {(ијкЬјк); (WilCiD}.

                                                                       j,ke                 I,leJ

На отрезке [0, ZUB] производится бинарный поиск по тп + п(п — 1)/2 упорядоченным значениям:

 I,je Л.

После первого этапа для значения z* определяется интервал [z.L, zU], z* S zU. Для значения не существует допустимого размещения, а для zU — существует. Все функции в правых частях ограничений (2.2), (2.3) на [4, zU] линейные.