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

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

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

1, если вершина Xj прикреплена к вершине zj, О в противном случае.

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

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

z= S S do-iiy (6.14)

i=i 5=1

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

5 \ij\ для / = 1, ...,n, (6.15)

%}ii=P (6-16)

ДЛЯ всех г, 7 = 1.....п (6.17)

ДЛЯ любой медианной вершины 6 Хр. Выражение (6.13) определяет количество товара, вывозимого из вершины xt, и, следовательно, является мерой вместимости склада Xi [8, 15, 7, 28].

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

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

1) И.меется в виду поиск, использующий дерево решений (в оригинале - tree search).- Прим. ред.

И

г^ = 0 или 1, (6.18)

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

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

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

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

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

ЖИЛ метод прокладки пути между несколькими экстремальными точками многогранника Н. При прокладке этого пути последовательно, в порядке убывания р, порождаются некоторые р-медианы графа. Кое-какие р-медианы (для отдельных значений р) могут быть не построены, и, наоборот, могут быть порождены такие экстремальные точки многогранника Н, которые не соответствуют р-медианам графа G, так как содержат дробные значения величин Хотя этот метод привлекателен как с теоретической, так и с вычислительной точек зрения, но все же он не всегда приводит к построению р-медианы графа для требуемого значения р. В работе [23] дан пример полного графа с 33 вершинами, для которого указанным методом последовательно порождаются р-медианы с р = 33, 32, . . ., 10, но построить таким способом 9-медиану и 8-медиану уже нельзя.

5а2. Алгоритм направленного древовидного поиска

Вместо того чтобы задачу нахождения р-медианы толковать как задачу целочисленного программирования, можно для ее решения использовать прямое дерево поиска. Этот подход лучше всего соответствует структуре рассматриваемой задачи. В настоящем разделе будет описан один из таких методов, в котором каждая подзадача, возникающая при ветвлении в каком-либо узле дерева, определяется тем, что (при заданной вершине Xj) переменная \ij полагается равной 1 для некоторой вершины Xj. Равенство ij; = 1 означает, что вершина х/ прикреплена к вершине Xj, а также, очевидно, что Xi является медианной вершиной.

Этот поиск удобно выполнять следующим образом.

Построим матрицу М = [т^], У-й столбец которой содержит все вершины графа G, расположенные в порядке неубывания их расстояний от вершины Xj. Таким образом, если т^) = Х}, то вершина Xi будет к-ж ближайшей к Xj вершиной. Очевидно, что первой ближайшей к xj вершиной является она сама, т. е. mij = Xj.

Поиск начинается с последовательного просмотра всех вершин графа, с Xi по х^. Вершина Xj вначале прикрепляется к вершине m-ij, затем к m-ij и т. д., пока не будут перебраны vie возможности. Необходимо сделать несколько замечаний.

1. Поскольку оптимальное решение состоит из р медианных вершин, то прикрепление вершины в этом решении к какой-либо медианной вершине должно быть наилучшим из р возможных прикреплений. Иными словами, для каждой вершины должно существовать по крайней мере еще р - 1 возможностей прикрепления с неменьшей стоимостью, чем у выбранной возможности. Следовательно, из матрицы М можно удалить р - 1 последних строк, и wo не отразится на оптимальном решении задачи о р-медиане.