5. Методы решения задачи о p-медиане

5.1. Формулировка задачи в терминах целочисленного программирования

Пусть матрица распределения, в которой

Далее примем если вершина является медианной вершиной и в противном случае. Задача -медиане может быть сформулирована тогда следующим образом.

Минимизировать функцию

при ограничениях

и

где матрица взвешенных расстояний графа (она получается из матрицы расстояний после умножения каждого столбца на соответствующий вес Соотношения (6.15) гарантируют выполнимость следующего условия: любая заданная вершина прикреплена к одной и только к одной медианной вершине Выражение (6.16) гарантирует существование в точности медианных вершин. Из ограничений (6.17) следует, что только тогда, когда т. е. прикрепления осуществляются только к вершинам медианного множества. Если является оптимальным решением задачи, определяемой соотношениями (6.14)-(6.18), то -медиана имеет вид

Если ограничения (6.18) вышеприведенной задачи заменить на

то возникает задача линейного программирования Ее решение получить нетрудно. (Отметим, что для величины указывать верхнюю границу не нужно, поскольку из соотношений (6.15) следует, что

Решение задачи не обязательно будет целочисленным, может принимать и дробные значения. Ревель и Свэйн [26] показали, что дробные значения встречаются крайне редко, и поэтому в большинстве случаев для получения -медиан можно использовать язык и методы линейного программирования. В том случае, когда некоторые являются дробными, решение можно получить с помощью древовидного поиска [11], причем одной ветви, соответствующей какой-либо дробной величине (переменной) придается значение 0, а другой ветви — значение 1. Затем для каждой из полученных ветвей (подзадач) можно продолжить поиск решения (как задачи и действовать подобным образом до тех пор, пока все примут значения из множества

Другой подход, отличный от метода линейного программирования, предложен Марстеном [23], который показал, что решение задачи (6.14) — (6.18), соответствующее -медиане графа» является экстремальной точкой некоторого многогранника причем многогранник будет одним и тем же для всех удовлетворяющих условию Используя множители Лагранжа и параметрическое линейное программирование, Марстен

предложил метод «прокладки пути» между несколькими экстремальными точками многогранника При «прокладке» этого пути последовательно, в порядке убывания порождаются некоторые -медианы графа. Кое-какие -медианы (для отдельных значений могут быть не построены, и, наоборот, могут быть «порождены» такие экстремальные точки многогранника которые не соответствуют -медианам графа так как содержат дробные значения величин Хотя этот метод привлекателен как с теоретической, так и с вычислительной точек зрения, но все же он не всегда приводит к построению -медианы графа для требуемого значения . В работе [23] дан пример полного графа с 33 вершинами, для которого указанным методом последовательно порождаются -медианы с но построить таким способом -медиану и -медиану уже нельзя.