Глава 5. РАЗМЕЩЕНИЕ ЦЕНТРОВ

1. Введение

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

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

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

Минисуммная задача размещения рассматривается отдельно в следующей главе. Хотя эти две задачи, очевидно, связаны между собой, но, поскольку методы их решения различны, гл. 5 и 6 можно читать независимо друг от друга.