Добавлен: 21.10.2018
Просмотров: 1316
Скачиваний: 11
Алгоритм решения состоит из двух этапов:
определение группы (центр, состав, число элементов),
улучшение группы путём обмена наиболее удалённых её элементов
с элементами соседних групп.
Решение:
Определение группы
1) Производим преобразование исходной матрицы М и из исходной
матрицы получаем три:
M
, M
K
, M
C
.
Упорядоченная
матрица
M
(каждый
столбец
исходной
матрицы
упорядочивается по возрастанию) представлена на рис. 4.5
M
1
2
3
4
5
6
7
8
9
Рис. 4.5
Упорядоченная
матрица
M
1
0
0
0
0
0
0
0
0
0
2
10 10 15 11 25 12 12 18 28
3
21 11 24 21 26 30 18 26 40
4
24 15 25 25 30 40 28 30 40
5
45 35 50 25 35 40 30 35 60
6
55 48 60 35 40 45 40 40 70
7
60 50 70 40 45 55 50 48 90
8
65 55 75 45 50 65 60 55 100
9
100 90 100 60 70 70 75 60 100
Рис. 4.5 Упорядоченная матрица
M
При равенстве взвешенных расстояний элементов, меньшим принимается
элемент с меньшим номером по строке.
В матрицу M
K
номеров записываются порядковые номера элементов,
переставленных при формировании упорядоченной матрицы
M
упорядочении
элементов, как представлено на рис. 4.6.
М
К
1 2 3 4 5 6 7 8 9
1 1 2 3 4 5 6 7 8 9
2 2 1 2 2 4 7 6 7 7
3 4 4 1 1 8 8 8 5 6
4 3 3 4 3 7 5 9 6 8
5 5 5 5 5 2 9 5 4 4
6 8 8 8 8 6 4 4 9 5
7 7 7 6 7 1 2 2 2 2
8 6 6 7 6 3 1 1 1 1
9 9 9 9 9 9 3 3 3 3
Рис. 4.6 Матрица M
K
номеров
Суммарная матрица M
C
, получается путем последовательного суммирования
элементов столбца упорядоченной матрицы, представлена на рис. 4.7.
М
С
1
2
3
4
5
6
7
8
9
1
0
0
0
0
0
0
0
0
0
2
10 10 15 11 25 12 12 18 28
3
31 21 39 32 51 42 30 44 68
4
55 36 64 57 81 82 58 74 108
5
100 71 114 82 116 122 88 109 168
6
155 119 174 117 156 167 128 149 238
7
215 169 244 157 201 222 178 197 328
8
280 224 319 202 251 287 238 252 428
9
380 314 419 262 321 357 313 312 528
Рис.4.7 Суммарная матрица M
C
2) Находим состав группы.
Просматриваем очередную строку i суммарной матрицы М
С
и ищем
минимальный элемент j. Принимаем, что при этом элементе j располагается
центр группы, состоящей (разумеется) из i узлов.
Проверяем ограничение по пропускной способности:
z
i
П
h=1 или 2
(для
соответствующего уровня h). Если ограничение выполняется, то увеличиваем
номер строки i=i+1 и всё повторяем сначала. В противном случае оставляем
состав группы с предыдущего шага(i-1).
В нашем примере задано найти три узла, входящие в группу. Поэтому
дойдем до 3-й строки матрицы М
С
(z
i
=1, а П
h=1
=3), в этой строке минимальным
является элемент m
32
=21.
Центр группы располагается при 2-м узле (j=2). Всего в группе три узла (i=3).
По столбцу 2 матрицы номеров М
К
определяем номера узлов, входящих в
группу Г
1
=2,1,4.
Корректировка для первой группы не производится.
3) Вычёркиваем строки и столбцы из исходной матрицы М с номерами
элементов, входящих в группу. В данном случае это строки 1,2,4 и столбцы
1,2,4. Получаем матрицу М
(1)
, представленную на рис. 4.8.
3
5
6
7
8
9
3
0
50 70 75 60 100
5
50 0
40 30 26 70
М
(1)
6
70 40 0
12 30 40
7
75 30 12 0
18 28
8
60 26 30 18 0
40
9
100 70 40 28 40 0
Рис. 4.8 Скорректированная матрица М
(1)
,
4) Если число групп > 1, переходим к следующему этапу (улучшение
группы), иначе к шагу 1.
В рассматриваемом примере имеем одну группу и опять из исходной
матрицы М
(1)
формируем три матрицы: упорядоченная
)
1
(
M
матрица, матрица
М
К(1)
и суммарная матрица М
С(1)
3
5
6
7
8
9
3
5
6
7
8
9
3 0
0
0
0
0
0
3 0
0
0
0
0
0
5 50 26 12 12 18 28
5 50 26 12 12 18 28
)
1
(
M
6 60 30 30 18 26 40
М
С(1)
6 110 56 42 30 44 68
7 70 40 40 28 30 40
7 180 96 82 58 74 108
8 75 50 40 30 40 70
8 255 146 122 88 114 178
9 100 70 70 75 60 100
9 355 216 192 163 174 278
Рис. 4.9 Матрица
)
1
(
M
Рис. 4.10 Матрица М
С(1)
3 5 6 7 8 9
3 3 5 6 7 8 9
5 5 8 7 6 7 7
6 8 7 8 8 5 6
7 6 6 5 9 6 8
8 7 3 9 5 9 5
9 9 9 3 3 3 3
Рис. 4.11 Матрица М
К(1)
Далее согласно п. 2 определяем группу. Минимальный элемент m
67
=30.
Следовательно, центр группы при 7-м узле, а состав группы Г
2
=7,6,8.
5) Проверяем необходимость корректировки группы Г
2
=7,6,8
Центр улучшаемой группы Г
у
= Г
2
расположен при узле 7. Узлы 6,8 должны
корректироваться, если расстояние от корректируемого узла до центра
улучшаемой группы Г
у
больше расстояния от корректируемого узла до центра
группы Г
1
при узле 2, из которой может выделяться узел, который участвует в
корректировке, т.е. в рассматриваемом примере для корректируемых узлов 6 и
8 должны соответственно выполняться условия: m
87
> m
82
либо m
67
> m
62
По матрице номеров М
К
, представленной на рис. 4.6, анализируем
соответственно столбцы 8 и 6, как представлено на рис. 4.12.
6 8
1 6 8
2 7 7
3 8 5
4 5 6
5 9 4
6 4 9
7 2 2
8 1 1
9 3 3
Рис. 4.12. Столбцы матрицы М
К
номеров
В каждом из этих столбцов узлы 6 и 8находятся выше узла 2. Это означает,
что центр Г
2
при узле 7 расположен к рассматриваемым узлам 6 и 8 ближе, чем
центр Г
1
, расположенный при узле 2. Поэтому корректировку Г
2
производить
не следует.
6) Находим следующую группу. После вычёркивания из матрицы М
(1)
строк
и столбцов, номера которых соответствуют номерам узлов, входящих в Г
2
,
получаем матрицу М
(2)
, представленную на рис.4.13.
3
5
9
3 0
50 100
М
(2)
5 50
0
70
9 100 70
0
Рис. 4.13 Скорректированная матрица М
(2)