Глава 6. РАЗМЕЩЕНИЕ МЕДИАН В ГРАФЕ

1. Введение

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

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