Лекции 5-6. Расчет иерархической древовидной конфигурации сети (1153084), страница 3

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 3)

4.15 Матрица МК(2Рис. 4.16 Матрица МС(2)Минимальный элемент m95=120. Центр группы при 5-м узле, состав группыГ3=5,3,9.7) Улучшение группы Г3Центр улучшаемой группы Гу = Г3 расположен при узле 5. Узлы 3,9 могуткорректироваться, если расстояние m35 > m32 либо m95 > m97 .По матриценомеров МК, представленной на рис. 4.6, анализируем соответственно столбцы3 и 9, которые приведены на рис. 4.17В 3-м столбце узел 2 находятся выше узла5. Это означает, что центр Г1 при узле 2 расположен к улучшаемому узлу 3ближе, чем центр Г3, расположенный при узле 5.

Поэтому корректировку узла 3следует производить.3 913 922 731 644 855 468 576 287 199 3Рис. 4.17 Столбцы матрицы МК номеровВ 9-м столбце узел 7 находятся выше узла 5. Это означает, что центр Г 2 приузле 7 расположен к улучшаемому узлу 9 ближе, чем центр Г 3, расположенныйпри узле 5. Поэтому корректировку узла 9 также следует производить.В процессе корректировки узел 3 из группы Г3 необходимо передать в группуГ1 (с центром в узле 2), а из группы Г1 необходимо узел, ближайший к группеГ3 (с центром в узле 5), включить в состав группы Г3.Группа Г1 имеет для корректировки два узла –1 и 4.

Чтобы найти, который изэтих узлов расположен ближе к центру 5 группы Г 3, рассмотрим матрицуномеров МК, представленную на рис. 5, точнее ее 5-й столбец, приведенный нарис. 4.18. В этом столбце узел 4 расположен выше узла 2, следовательно,необходимо узел 3 включить в состав Г1, а узел 4 – в состав Г3.5152438475266718399Рис. 4.18Столбец матрицы МК номеровКроме того, в процессе корректировки узел 9 из группы Г3 необходимопередать в группу Г2 (с центром в узле 7), а из группы Г2 необходимо узел,ближайший к группе Г3 (с центром в узле 5), включить в состав группы Г3.Группа Г2 имеет для корректировки два узла –6 и 8.

Чтобы найти, который изэтих узлов расположен ближе к центру 5 группы Г 3, рассмотрим 5-й столбецматрицы номеров МК, приведенный на рис. 4.18. В этом столбце узел 8расположен выше узла 7, следовательно, необходимо узел 8 включить в составГ3, а узел 4 – в состав Г3.Таким образом, получаем скорректированные группы первого уровня:Г1 = 2,1,3; Г2 = 7,6,9; Г3 = 5,4,8.8) В рассматриваемом примере вес каждого узла равен 1, а пропускныеспособности центров групп Пh=1=3. Для каждой из полученных группвыполняется условие равенства пропускных способностей, поэтомукорректировка завершена.Определение групп следующего уровня9) Все узлы уровня h =1 сгруппированы, переходим к определению группуровня h = 2.Исходными узлами для уровня h = 2 являются центры групп уровня h =1,которые расположены при узлах 2,7,5.10) Корректируем исходную матрицу М так, что в ней остаютсятолько центры групп (рис.

4.19)2 5 720 35 50М(4) 535 0 30750 30 0Рис. 4.19 Скорректированная матрица М(4)11) Аналогично п.1 формируются три матрицы:упорядоченная матрица М(4) (рис. 4.20); матрица М(4) номеров (рис. 4.21);суммарная матрица М(4) (рис. 4.22).2 5 72 5 72 5 720 0 02 2 5 72 0 0 0535 30 305 5 7 55 35 30 30750 35 507 7 2 27 85 65 80Рис. 4.20МатрицаM ( 2)Рис. 4.21 МатрицаМК(4)Рис. 4.22 МатрицаМС(4)Минимальный элемент m75=65, тогда центр группы распложен при 5-м узле,состав группы Г1=5,7,2.Так каксформирована только одна группа, то процедура расчётазаканчивается.Результат расчета структуры представлен на рис. 4.23.Рис.

4.23 Схема рассчитанной структуры.Рассмотренный пример носит иллюстративный характер и предназначен дляпояснения процедуры расчета. Однако, как указывалось ранее, даннаяпроцедура может быть использована для сетей, имеющих размерность 100—400 исходных элементов.Самоконтроль знанийКонтрольные вопросы1. Какие примеры реальных ВС имеют иерархическую древовиднуюконфигурацию (ИДК).

Какие технические реализации соответствуют узлам идугам ИДК ?2. Обоснуйте, что сформированные матрицы: ‖‖ℎ , ‖‖ℎ полно и однозначноописывают ИДК ВС.3. Почему отсутствие одной из групп ограничений 4.4 – 4.7 может привести кнеправильному решению поставленной задачи?4. Почему сформулированная математическая постановка задачи определенияИДК относится к классу нелинейных задач с булевскими переменными?5. Почему в предложном алгоритме определения ИДК необходим этапкорректировки матрицы?6.

Почему предложенная эвристическая процедура решения не гарантируетглобального оптимума целевой функции.Контрольные задания1. Поясните, как выбраны номера в 4-м столбце матрицы MK , учитывая, чтов 4-м столбце матрицы M 4-й и 5-й элементы имеют одинаковые значения.2. Поясните, почему этап корректировки начинается только послеопределения второй группы?3. Как объяснить, почему при выполнении любого этапа корректировкииспользуется матрица MK, сформированная на первом этапе выполнениярасчетов.4. Подтвердите расчетом возникновение ошибки по п. 5 примера, если вместоматрицы МК, (рис.

4.6), использовать матрицу МК(1) (рис. 4.11).

Характеристики

Список файлов лекций