(6.5)

так же, как и для одиночной вершины:

а,(Хр)= S vjd{xj,Xp),

где Од {Хр) и Ot {Хр) - соответственно внешнее и внутреннее передаточные числа множества вершин Хр. Множество Хро, для которого

а„(Хр,)= min [аЛХр)], (6.6)

называют внешней р-медианой графа G; аналогично определяется внутренняя р-медиана.

Как и в слзАчае р-центров, рассмотренных в предыдущей главе, даже для графов средних размеров с вычислительной точки зрения нецелесообразно использовать при нахождении р-медиан непосредственно выражения (6.4), (6.5) и (6.6). Алгоритмы построения р-медиан будут даны в разд. 5.

3.1. Абсолютные медианы

С целью упрощения изложения рассмотрим неориентированный граф G. Индексы out будут отсутствовать. Разберем сначала случай медианы (1-медианы). Спрашивается, существует ли такая точка у на некотором ребре (не обязательно совпадающая с вершиной графа G), для которой передаточное число

о(У)= S Vjd{y,Xj)

Xj£X

меньше, чем для медианы графа G. Точку у, на которой достигается минимум величины а (у), будем называть абсолютной медианой графа G.

Сейчас мы докажем [5,6], что не существует точки у, для которой о {у) <.а (х), т. е. здесь ситуация противоположна той, которая имела MdCTO при рассмотрении центров.

Теорема 1. Какова бы ни была точка у графа G = {X, А), в нем найдется по крайней мере одна вершина х, для которой а (ж) < о {у).

Доказательство. Пусть у - точка ребра (жа, х^, расположенная на расстоянии от Ха. Тогда

d{y, x) = min[?4-d(x , Xj), с„ь-? + й(хь, Xj)\, (G.7) где Cab - длина ребра (Хд, Хь).

3. КРАТНЫЕ МЕДИАНЫ (р-МБДИАНЫ) ГРАФА 131

Пусть Ха - множество тех вершин Xj, для которых первый член в (6.7) не больше второго, а Z;, - множество вершин, для которых второй член меньше первого. Мы можем тогда написать

о{у)= S Vjd (у, Xj) = S vj[l + d {Ха, Xj)] +

+ S v,[e,b-l + dixb,xj)]. (6.8) Поскольку из неравенства треугольника следует, что

d (а, j)<Cab + d (Хь, Xj), (6.9)

то, заменяя Саь + d (xj xj) на d {Ха, xj) в выражении (6.8), получаем

0{У)> S Vj[l+d{x Xj)]- S Vj[d{x Xj)-l]. (6.10)

Так как Ха {] Х^ = X, то, сделав перегруппировку в (6.10), имеем:

0(У)> S Vjd(x Xj)+l[ S I;- S Vj]. (6.11)

Поскольку для каждого ребра (Ха, Xf,) мы вправе сами решать, какую вершину называть Ха и какую Xf то всегда можно добиться выполнения неравенства

S Vj> S Vj. XjiX XjXf,

Заметив, что первый член в правой части неравенства (6.11) равен о (Ха), получаем из (6.11) такое соотношение:

о (У)>( М-

Таким образом, для вершины Ха величина о (ха) не превышает о (у) и, следовательно, теорема доказана.

Теорема 1 довольно просто обобщается на случай р-медиан.

Теорема 2. Каково бы ни было множество Yp, состоящее из р точек график = (X, А), т. е. из р точек ребер и рвршин, найдется по крайней мере одно подмножество Хр с: X, содержащее р вершин, для которого о (Хр) о (Yp).

В теоремах 1 и 2 предполагалось, что передаточные числа а (х) и о (Хр) определены с помощью выражений (6.1) и (6.5). В работах Леви [20], Голдмана [12] и Голдмана и Мейерса [141 было показано, что эти теоремы остаюгся в силе и в тех случаях, когда передаточные числа определяются как суммы произвольных, вогнутых функций от взвешенных расстояний.

Из теорем 1 и 2 следует, что понятие абсолютной медианы не представляет особого интереса (в иротивоположность ситуации с абсолютными центрами, рассмотренными в гл. 5). Поэтому в остальной части этой главы основное внимание уделяется задаче о /?-медиане.

4. Обобщенная р медиана графа

Задача нахождения /?-медианы графа является центральной в общем классе задач, встречающихся в литературе иод названием распределение и размещение центров обслуживания [5, 6, 9] или размещение складов [8, 29, 30, 10, 15, 7, 28]. Эти задачи являются до некоторой степени более общими, чем задача о р-медиане, в которой вершинам сопоставлены фиксированные стоимости /,. Обобщенная задача о р-медиане может быть сформулирована следующим образом.

Для заданного графа G = {X, А) с матрицей кратчайших расстояний [d (Xi, Xj)], с весами вершин у,- и с фиксированными стоимостями вершин fi задача состоит в нахождении такого подмножества Хр из р вершин, для которого величина

г= S fi+o(Xj,) (6.12)

принимает минимально возможное значение.

Таким образом, в этом случае минимизации подлежит не просто передаточное число а (Хр) множества Хр, а полная функция цели, содержащая фиксированные стоимости /; вершин Xj подмножества Хр. На практике fi представляет, например, фиксированную стоимость строительства пункта обслуживания (склада, фабрики, иод-станции) при размещении его в вершине х,. Задача о р-медиане соответствует такому случаю, когда все fi одинаковы (например, равны /), так что первый член в (6.12) равен постоянной величине pf независимо от выбора подмножества Хр

Очень близкой к сформулированной выше задаче об обобщенной р-медиане является такая задача, в которой число вершин \ Хр I не обязательно равно р, а может быть некоторым числом, не превосходящим р. Задача минимизации выражения (6.12) ири условии \ Хр I р является разновидностью задачи об обобщенной р-медиане и часто встречается на практике.

В задачах размещения складов неизменно приходится сталкиваться с ограничениями, которых нет в чистой задаче о р-медиане. Чаще всего встречаются ограничения на наибольшее и наименьшее значения, которые может принять выражение

S Vj (6.13)

Ш], прМфеплеиные каС|