Определение оптимального места расположения зональных узлов.
Число зон на которые необходимо разделить магистральную сеть определяются последней цифрой номера зачетки
Таблиця 2.1 - Кількість зон (визначається останньою цифрою залікової книжки)
NЗ |
Задача может быть решена следующим образом, пусть наша сеть представлена графом, где вершины – это областные центры, а ребра это расстояния между областными центрами (заданы в таблице 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.