На первичной сети, структура которой определена графом (Рис. 5.), заданы:
1. Матрица требований Ф = || φij || , где φij - требуемое число каналов в путях передачи от УКi к УКj . Ненулевые элементы матрицы Ф: φ16 = 33; φ13 = 20; φ24 = 12.
2. Емкости ребер ukl в числе каналов первичной сети, заданные весами ребер на графе.
279082512890500 2
28333702794000146177017145002865755635000
20 20
139827013017500411988013017500 1 20 3
147256517780003439795285750014617702857500
279082511493500 20 6
2344420133350028657553492500
20 20 20
20
228028513144500338645513144500
5 4
Рис. 5.
Требуется найти план распределения каналов (ПРК), удовлетворяющий матрицы требований Ф, при условии использования только кратчайших путей
Решение
Из рис. 5 определяем кратчайшие пути.
Для φ16 = 33 их три (k=3): μ11,2,6 ; μ21,4,6 ; μ31,5,6 .
Для φ13 = 20 их три (k=2): μ11,2,3 ; μ21,4,3 .
Для φ24 = 12 их три (k=3): μ12,1,4 ; μ22,3,4 ; μ32,6,4 .
Определим число каналов, необходимое для обслуживанияданного потока, распределяя общее число каналов равномерно на k путей, обозначая их через x.
x11,2,6 = x21,4,6 = x31,5,6 = φ16 / k = 33 / 3 = 11.
x11,2,3 = x21,4,3 = φ13 / k = 20 / 2 = 10.
x12,1,4 = x22,3,4 = x32,6,4 = φ24 / k = 12 / 3 = 4.
Составляем матрицу C емкостей кратчайших путей и ребер для сделанного идеального ПРК, представленную в таблице 1.
Подсчитываем для каждого ребра его емкость, полученную в результате загрузки в соответствии с идеальным ПРК, и в графе ставим со знаком "+" то число каналов, которое осталось незагруженным (ненасыщенные ребра) и со знаком "-" число каналов, на которое загрузки ребра превышают заданное число каналов в ребре.
Таблица 1
805180-5080004545330-508000-5080-508000271145-508000 φij Емкость Р е б р а Приме-
126873010795008013701143000 пути 1-2 1-4 1-5 2-3 2-6 3-4 4-6 5-6 чания
-5080571500 x11,2,6 11 11
2711453169285002711451584960002711451143000 φ16 x21,4,6 11 11
x31,5,6 11 11
-50801143000 φ13 x11,2,3 10 10
x21,4,3 10 10
-50801143000 x12,1,4 4 4
φ24 x22,3,4 4 4
x32,6,4 4 4
1397635698500919480698500-5080698500 ∆x1ij -5 -5 +9 +6 +5 +6 +5 +9 ПРК не допустим
271145157480000271145127000-5080571500 x11,2,6 8 8
φ16 x21,4,6 8 8
x31,5,6 17 17
-50801143000 φ13 x11,2,3 10 10
x21,4,3 10 10
-50801143000 x12,1,4 4 4
φ24 x22,3,4 4 4
x32,6,4 4 4
-508015855950014300201333500951865254000-508018224500-50801206500 ∆x2ij -2 -2 +3 +6 +8 +6 +8 +3 ПРК не допустим
-5080571500 x11,2,6 8 8
φ16 x21,4,6 8 8
x31,5,6 17 17
-50801143000 φ13 x11,2,3 10 10
x21,4,3 10 10
-50801143000 x12,1,4 2 2
φ24 x22,3,4 5 5
x32,6,4 5 5
∆x3ij 0 0 +3 +5 +7 +5 +7 +3 ПРК допустим
После первого этапа оказались перегруженными ребра: 1-2, 1-4, 2-6, 4-6.
На втором этапе перебрасываем нагрузку (по 3 канала) с путей x11,2,6 (ребра 1-2, 1-4) и x21,4,6 (ребра 2-6, 4-6) на путь x31,5,6 (ребра 1-5, 5-6)
Задать вопрос
на новый заказ в Автор24.
