Глава 6

РАЗМЕЩЕНИЕ МЕДИАН В ГРАФЕ

1. Введение

В ряде задач о размещении пунктов обслуживания требуется так расположить пункт обслуживания на графе, чтобы сумма кратчайших расстояний от этого пункта до вершин графа была минимально возможной. Оптимальное в указанном смысле место расположения пункта называется медианой графа. Исходя из природы целевой функции, такие задачи называют минисуммными задачами размещения. Эти задачи в различных формах часто встречаются на практике: при выборе места расположения коммутаторов в телефонной сети, подстанций в электросетях, баз снабжения (складов) в сети дорог (где вершины представляют потребителей) или отделов сортировки в почтовой связи.

С этим типом задач контрастирует минимаксная задача размещения, возникающая при выборе места для таких пунктов обслуживания, как пожарное депо, полицейский участок или амбулатория, и рассмотренная в предыдущей главе. В настоящей главе рассматривается минисуммная задача размещения. В частности, обсуждается задача о нахождении р-медианы данного графа G; это задача об оптимальном размещении заданного числа (скажем р) пунктов обслуживания, при котором сумма кратчайших расстояний от вершин графа G до ближайших к ним пунктов ) принимает минимально возможное значение. Задача нахождения р-медианы может быть несколько обобщена, если каждой вершине Xj сопоставить некоторый вес Vj (представляющий, например, ее размеры или важность); тогда целевой функцией, подлежащей минимизации, станет сумма взвешенных расстояний.

2. Медиана графа

Пусть дан граф G = (X, Г). Для каждой вершины х,- 6 X определим два числа, которые назовем передаточными числами:

OoiXi)= Yi Vjd {Xi,Xj), Ot{Xi)= S Vjd{Xj,Xi),

(6.1)

1) Суммирование ведется по всем вершинам. Для каждой вершины берется кратчайшее расстояние от нее до ближайшего к ней пункта обслуживания.- Прим. ред.

где d (xi, Xj) - кратчайшее расстояние от вершины xt до вершины Xj. Числа Оо (xj) и Oj {xi) называются соответственно внешним и внутренним передаточными числами вершины Xf. Число а о {xi) есть сумма элементов строки Xi матрицы, полученной после умножения каждого столбца матрицы расстояний D (G) = [d (ж,-, Xj)] на вес соответствующей этому столбцу вершины, т. е. /-й столбец умножается на Vj-, число о^ (ж,) есть сумма элементов столбца ж,-матрицы, полученной в результате умножения каждой строки матрицы расстояний D (G) на соответствующий этой строке вес 0-я строка умножается на Vj). Вершина ж^, для которой

Оо{хо) = тт К {Xi)],

(6.2)

называется внешней медианой графа G, а вершина Xt, для которой at{xt) = inm[at{Xi)], (6.3)

называется внутренней медианой графа G.

Рассмотрим еще раз граф, изображенный на рис. 5.1 (для которого все Vj и С;у приняты равными единице), и вычислим внешние и внутренние передаточные числа вершин. Эти числа приведены в присоединенных к матрице расстояний строке и столбце:

По полученным передаточным числам видно, что внешней медианой является х^ с (х^) = 7 и что существуют три внутренние медианы (х^, Хд и х^), каждая с внутренним передаточным числом, равным 9.

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

2.1. Выбор места для склада

Рассмотрим задачу снабжения ряда потребителей товарами поступающими с одного склада. Потребителей можно объединить в группы таким образом, чтобы каждую группу обслуживало целое число грузовиков. Машина выезжает со склада, обслуживает некоторую группу потребителей и возвращается на склад. Группы потребителей можно представить вершинами графа, а сеть дорог - его дугами. На практике каждой группе потребителей присваивается вес Vj, представляющий ее важность (например, Vj может быть числом, пропорциональным годовому потреблению или частоте, с которой транспорт должен объезжать эту группу потребителей, чтобы удовлетворить их потребности).

В этом случае задача состоит в определении такого места для склада, чтобы общее расстояние, проходимое транспортом, было бы минимально возможным. Если матрица расстояний D (G) задает действительные расстояния в километрах, то требуемым местом расположения склада будет такая вершина х^ j, для которой сумма внешних и внутренних передаточных чисел будет наименьшей. Вершина Хд, t может быть названа внешне-внутренней медианой и найдена из соотношения, аналогичного (6.1). В следующем разделе будет показано, что для любой точки (вершины или произвольной точки дороги), выбранной для размещения склада, общий километраж, покрываемый транспортом, не может быть меньше, чем для вершины Xgf

3. Кратные медианы (/?-медианы) графа

В предыдущей главе, обобщая понятие центра, мы ввели понятие р-центра. Подобным же образом можно обобщить понятие медианы, определив р-медиану.

Пусть Хр - подмножество множества вершин X графа G = = (Х, Г), и предположим, что Хр содержит р вершин. Как и прежде, введем следующие обозначения:

d (Хр, Xj) = min [d (Xt, Xj)] (6.4 (a))

d {Xj, Xp) = min [d {Xj, X,)]. (6.4 (6))

Если xi - вершина из Хр, на которой достигается минимум в (6.4 (а)) или (6.4 (б)), то говорят, что вершина Xj прикреплена к xi. Передаточные числа множества вершин Хр определяются

9 н. Кристофидес