Определение оптимального места расположения зональных узлов.

Число зон на которые необходимо разделить магистральную сеть определяются последней цифрой номера зачетки

Таблиця 2.1 - Кількість зон (визначається останньою цифрою залікової книжки)

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

Таблица 5. - Матрица расстояний между областными центрами Украины (в км.)

Для решения задачи используется эвристический алгоритм:

1. Определяем некоторое множество S вершин мощностью р, в качестве первого приближения, все остальные вершины будут «неопробованными».

2. Выбираем произвольную «неопробованную» вершину и для каждой вершины рассчитываем приращение передаточных чисел для множества S и множества :

,	(10)
	(11)
	(12)

где – передаточное число для исходного множества S; – передаточное число для множества ; – значение смежности j вершины, ; – весовая характеристика ребра между вершинами и ; – весовая характеристика ребра между вершиной и ;

3. Если ≤ 0, то вершину помечаем как «опробованную» и переходим к шагу 5. Если ≥ 0, то вершину помечаем как «опробованную», заменяем множество S на множество (S ← ) и переходим к шагу 4.

4. Проверяем есть ли в множестве неопробованные вершины. Если , то переходим к шагу 2. Если то стоп, текущее множество S является решением задачи.

Рассмотрим пример:

Пусть задан граф (рис.2.2) и нам необходимо найти две медианы графа – р=2.

Пусть начальное множество S включает вершины Х6 и Х3, все остальные вершины являются неопробованными (Х1, Х2, Х4, Х5).

Определим передаточное число исходного множества S

σ(S) = 2*1+2*1+2*1+2*1 = 8 (с вершиной 6 смежные две вершины и с вершиной 3 смежные 2 вершины).

Сформируем новое множество , которое будет включать вершины Х6 и Х4, рассчитываем , =2*1+2*1+2*1+2*1=8.

Проверяем условие

=8-8=0. Так как =0, то множество S остается прежним.

И так далее перебираем все неопробованные вершины и формируем множества .

В результате получим два множества (Х4 и Х1) и (Х2 и Х5), для которых передаточное число равно 7. В этом случае =8-7=1.А значить одно из этих множеств может быть использовано в качестве решения нашей задачи – центры зон можно разместить в узлах 1 и 4 или в узлах 2 и 5.