Задачи размещения

Задачи размещения связаны с решением проблем наилучшего расположения в определенных регионах таких систем обслуживания, как торговые центры, посты пожарной охраны, фабрики, аэропорты, склады и т. д. Математическая структура задачи размещения определяется конфигурацией области допустимых точек и способом оценки качества размещения. Вследствие этого существует много разнообразных задач размещения, и техническая литература изобилует методами их решения. В этом разделе мы ограничимся рассмотрением только таких задач размещения, для которых областью допустимых точек размещения центров обслуживания является некоторый граф, т. е. эти центры могут располагаться в какой-либо вершине или на какой-либо дуге графа.
В задачах размещения есть два основных критерия оценки качества размещения: минимизация максимального расстояния и минимизация суммы расстояний. Соответственно имеем и две основные задачи. Задача поиска точки размещения, выбранной в соответствии с критерием минимизации максимального расстояния, называется задачей поиска центра графа, точки выбранной по критерию минимизации суммы расстояний – задачей поиска медианы.
Прежде чем ввести более строгие определения подлежащих рассмотрению различных типов размещений, следует ввести некоторые определения, необходимые для описания точек на дугах и различных расстояний в графе.
Множество рассматриваемых вершин в графе содержит вершины с номерами от 1 до n. Рассмотрпм произвольную дугу (i, j), длина которой равна a_i,j>0. Пусть f обозначает точку на дуге (i, j), которая для всех 0≤f≤1 отстоит на f×a_i,j единиц от вершины i и на (1 — f)×a_i,j единиц от вершины j. Назовем ее f-точкой. Таким образом, четверть-точкой дуги (i, j) является точка, отстоящая от вершины i на 1/4 длины дуги (i, j)
Нуль-точка дуги (i, j) является вершиной i, а единичная точка дуги (i, j) — вершиной j. Следоватльно, вершины графа также могут рассматриваться как точки дуг. Точки дуг, которые не являются вершинами, называются внутренними точками. Любая точка дуги должна быть либо внутренней точкой, либо вершиной. Как и ранее, обозначим через Х множество всех вершин графа. Пусть через Р обозначается множество всех точек. Таким образом, Р — Х является множеством всех внутренних точек.
Пусть d_i,j обозначает длину кратчайшего пути из вершины i в вершину j. Тогда через D обозначается матркца n×n, в которой элементом (i, j) является d_i,j. Элементы в матрице называются расстоянимми вершина — вершина. Напомним, что для вычисления элементов матрицы 1 может быть использован любой из двух рассмотренных ранее алгоритмов: алгоритм Флойда или алгоритм Данцига. Пусть через d(f -(r,s ), j) обозначена длина кратчайшего пути от f-точки на дуге (r,s) до вершины j. Эта величина называется расстоянием точка — вершина. Если дуга (r,s) неориентированная, т. е. допустим ее обход в обоих направлениях, то в качестве d(f -(r,s ), j) должно быть выбрано паименьшее из следующих двух расстояний:
(а) расстояние от точки до вершины r плюс расстояние от вершины f до вершины j,
(б) расстояние от f-точки до вершины s плюс расстояние от вершины s до вершины j.
Таким образом,

d(f—(r,s ),j)=min{f×а_r,s+d_r,j), (1—f)×а_r,s+d_s,j}. (1a)

Если дуга (r,s) ориентированная, т. е. ее обход допустим только из r в s, то первый член в (1а) может быть исключен и

d(f—(r,s ),j) =(1—f)×а_r,s+d_s,j . (1б)

Заметим, что для вычисления всех расстояний точка — вершина необходимо знать только значения длин всех дуг и значения всех элементов матрицы D.
Для заданной дуги (r,s) и вершины j расстояние точка — вершина как функция от f на графике должна иметь один из трех типов зависимостей, показанных на рисунке Заметим, что угол наклона этой кусочно-лпнейной кривой равен +а_r,s или -а_r,s и его величина может не более одного раза измениться от +а_r,s до -а_r,s.

Рассмотрим далее наименьшее расстояние от вершины j до каждой точки на дуге (r, s). для некоторой точки на дуге (r, s) это расстояние принимает максимальное значение. Оно обозначается через d'(j, (r, s) и называется расстоянием вершина — дуга. Если дуга (r, s) неориентированная, то имеются два маршрута движения из вершины j в f-точку на дуге (r, s): через вершину r или вершину s. Естественно, мы выбираем кратчайший из этих двух маршрутов. Еслп эти два маршрута из вершины j в f-точку на дуге (r, s) имеют различную протяженность, то некоторые точки, соседние с f-точкой на дуге (r, s), отстоят еще дальше от вершины.
Поэтому два расстояния от вершины j до некоторой точки ка дуге равны между собой, если эта точка является наиболее удаленной от вершины j.
Заметим, что сумма этих расстояний всегда равна d_j,r+f×а_r,s +d_j,s+(1—f)×а_r,s =d_j,r+d_j,s +а_r,s.
Откуда следует, что

d'(j, _r,s)= d_j,r+ d_j,s +а_r,s/2 (2a)

С другой стороны, если дуга (r, s) ориентированная, то некоторая точка на дуге (r, s) может быть достигмута только через вершину r. Следовательно, наиболее удаленной от любой вершины графа точкой на дуге (r, s) является точка, ближайшая к вершине s (т. е. f-точка на дуге (r, s), для которой f = 1). В этом случае

d'(j, (r, s))= d_j,r+ а_r,s. (2б)

Пусть в графе имеется m дуг. Обозначимчерез D’ матрицу размерности n×m, у которой элемент, стоящий на пересечении i-й строки и k-столбца, является расстоянием вершина — дуга от j-й вершины до k-й дуги. Заметим, что значения элементов матрицы D’ могут быть вычислены с помощью равенств (2а) и (26), если известны расстояния вершина —‘ вершина, задаваемые матрицей D, и длины дуг графа.
Пусть d'(f — (r, s), (t, u)) обозначает максимальное расстояние от f-точки на дуге (r, s) до точек на дуге (t, u). Это расстояние называется расстоянием точка — дуга.
Если дуга (r, s) неориентированная и если (r, s)≠(t, u), то маршрут от f-точкк на дуге (r, s) до наиболее отдаленной точки на дуге (t, u) должен проходить либо через вершину r, либо через веркiику s. Отсюда следует, что

d'(f — (r, s), (t, u)) = min {f×а_r,s + d’ (r, (t, u)), (1—f)×а_r,s+ d'(s, t, u))}. (За)

Если же дуга (r, s) ориентированная и (r, s)≠(t, u), то первый член в формуле (8.За) может быть исключен и

d'(f — (r, s), (t, u)) = (1—f)×а_r,s + d'(s, t, u)). (3б)

Если (r, s) = (t, u) и дуга (r, s) ориентированная, то наиболее удаленная точка на дуге (r, s) от f-точки на (r, s) является g-точкой, где стремится к f со стороны значений, меньших чем f. Таким образом, в этом случае

d'(f—(r, s), (r, s))= (1—f)×а_r,s+d_s,r. (Зв)

Если же (r, s)= (t, u) и дуга (r, s) неориентированная, то максимальное расстояние от f-точки на дуге (r, s) до g-точки на дуге (r, s) в случае, когда g<f, не=”” может=”” превышать=”” a=”min{f<strong”>×а_r,s, 1/2×[а_r,s+d_s,r]}.
Первый член в этом выражении равен длине маршрута от f- точки до g-точки в пределах дуггi (r, s), второй член равен длине маршрута от f-точки на дуге (r, s) до g-точки на дуге (r, s), но проходящего через вершину s.
Аналогично в случае, когда g>f, максимальное расстояние от f-точки на дуге (r, s) до g-точки (r, s) не может превышать (r, s):
В=min{(1 —f)×а_r,s, 1/2×[а_r,s + d_r,s]}.
Первый член в выражении для В равен длине маршрута от f-точки до g-точки в пределах дуги (r, s), а второй — равен длине маршрута от f-точки на дуге (r, s) до g-точки на дуге (r, s), проходящего через вершину r.
Следовательно, если дуга (r, s) неориентированная, то d'(f-(r, s), (r, s))= max {A, B}, или, что эквивалентно, </f,>

d'(f-(r, s), (r, s))=max {min{f×a_r,s, 1/2×[а_r,s+d_s,r]}, min{(1 —f)×а_r,s, 1/2×[а_r,s+d_r,s]}}. (3 г)

Если изобразить расстояние d'(f—(r, s), (t, u)) точка — дуга как функцию f для всех (r, s)≠(t, u), то соответствующая кривая на графике будет иметь тот же вид, что и кривая расстояний точка — вершина, представленная на предыдущем рисунке, так как уравнения (За) и (36) имеют соответственно тот же вид, что и уравнения (1а) и (1б). Отличаются они только на постоянные величины. С другой стороны, если d'(f—(r, s), (r, s)) для любой неориентированной дуги (r, s) представить как функцию от f, то кривая функции будет иметь вид, показанный на рисунке 2. Это следует из уравнения (3г).

Рисунок 2 – расстояние точка-дуга как функция от f

Такии образом, введенные нами определения могут быть систематизированы в форме следующей таблицы:

Пусть МВВ(i)=max {d(i, j)}— максимальное расстояние от вершины i до вершин графа, т. е. расстояние от вершины i до наиболее отдаленной вершины графа, и СВВ(i)=Σd(i, j) — суммарное расстояние от вершины i до всех вершин графа.
Пусть аналогично МТВ(f—(r, s))=max{d(f—(r, s), j}— максимальное расстояние от f-точки на дуге (r, s) до вершин графа, т. е. расстояние от f-точки на дуге (r, s) до наиболее отдалеяной вершивы графа, и СТВ(f—(r, s))=Σd(f—(r, s), f) — сумма расстояний от f-точки на дуге (r, s) до всех вершин графа. Аналогично мы можем определить МВД(i), СВД(i), МТД(f—(r, s)), СТД(f—(r, s)), взяв максимум или сумму по всем дугам, а не по всем вершинам.
Введя определения всех этих расстояний, их максимумов и сумм, мы теперь готовы к тому, чтобы дать строгие определения для рассматриваемых далее различных типов размещений.

1. 1. Центром графа G является любая вершина х этого графа, такая, что МВВ (х) = min{МВВ(i)}. Таким образом центр — это любая вершина, расстояние от которой до наиболее отдаленной от нее вершины минимально.
   2. Главным центром графа G является любая вершина х этогс графа, такая, что МВД (х) = min {МВД (i)}, т. е. главный центр — это любая вершина, расстояние от которой до наиболее удаленной точки на дугах графа минимально.
   3. Абсолютным центром графа G является любая f-точка на произвольной дуге (r, s) этого графа, такая, что МТВ (f— (r, s)) = min{МТВ (f — (t, u))}, f-(t, u)ЕP т. е. абсолютный центр — это любая точка на дуге, расстояние от которой до наиболее отдаленной вершины графа минимально.
   4. Главным абсолютным центром графа G является f-точка на произвольной дуге (r, s) этого графа, такая, что МТД (f (r, s)) = min {МТД (f — (t, u))}, f—(t, u)ЕР. Таким образом, главный абсолютный центр — это любая точка, расстояние от которой до наиболее удаленной точки минимально,

По аналогии с каждым из четырех типов определенных здесь размещений мы можем определить медиану, главную медиану, абсолютную медиану и главную абсолютную медиану.
Определения этих типов размещений совершенно аналогичны определениям соответствующих предыдущих типов раз мещений, за исключением того, что везде оператор максимизации (т. е. МВВ(i), МВД(i), МТВ(f—(t, u)), МТД(f—(t u)))заменяется оператором суммирования (т. е. СВВ(i), СВД(i), СТВ(f—(t, u)) СТД(f—(t, u))).