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

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

Для заданного графа с матрицей кратчайших расстояний с весами вершин и с фиксированными стоимостями вершин задача состоит в нахождении такого подмножества из вершин, для которого величина

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

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

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

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

для любой медианной вершины Выражение (6.13) определяет количество товара, вывозимого из вершины следовательно, является мерой вместимости склада

Очевидно, что такое же обобщение, возникающее при введении ограничений на величину (6.13), возможно и в задачах о нахождении -центров и абсолютных -центров, рассмотренных в предыдущей главе. Однако для практических задач размещения энергетических объектов, именно тех задач, которые связаны с нахождением -центров, указанное обобщение имеет небольшое значение, так как всегда эти ограничения легко вводятся в алгоритм, приведенный в разд. 8 предыдущей главы.

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