Управление коммутируемой сетью передачи информации (СПИ)

 

Матрица емкостей

 

	0	30	40	20	0	0	0
	30	0	0	0	30	0	45
	40	0	0	20	40	0	0
В=	20	0	0	0	30	0	0
	0	30	40	30	0	0	45
	0	0	0	0	0	0	0
	0	45	0	0	45	0	0

Так как b₄₆= b₅₆= b₆₇=0, то граф имеет вид:

Рис. 4.1.2 - Перестроенный граф СПИ

 

Тогда матрица смежности  имеет вид:

	0	1	1	1	0	0
	1	0	0	0	1	1
	1	0	0	1	1	0
С=	1	0	0	0	1	0
	0	1	1	1	0	1
	0	1	0	0	1	0

 

Составим матрицу потоков  сообщения:

φ₁₅=40; φ₂₃=60; φ₄₂=35

 

	0	0	0	0	40	0
	0	0	60	0	0	0
	0	0	0	0	0	0
Ф=	0	35	0	0	0	0
	0	0	0	0	0	0
	0	0	0	0	0	0

 

По матрице смежности  составим деревья путей.

 

Рис. 4.1.3 - Дерево путей из узла 2 в узел 3

М₂₃{ 213,21453,253,25413,2753,275413}

 

Рис. 4.1.4 -  Дерево путей из узла 1 в узел 5

М₁₅{125,1275,1345,135,145}

 

Рис. 4.1.5 -  Дерево путей из узла 4 в узел 2

 

М₄₂{412,41352,413572,452,45312,4572}

 

4.2 Построение симплекс-таблицы

 

Составим целевую функцию:

F=x1+ x2+ x3+ x4+ x5+ x6+ x7+ x8+ x9+ x10+ x11+ x12+ x13+ x14+ x15+ x16+ x17;

Ограничения на поток  сообщения:

Ограничения по пропускным способностям линий связи:

x1+x2+x7+x8+x12+x16≤30

x1+x4+x6+x9+x10+x13+x14+x16≤40

x2+x4+x6+x11+x12+x13+x14≤20

x3+x4+x7+x13+x15≤30

x5+x6+x8+x17≤45

x9≤20

x2+x3+x5+x10+x13+x14+x16≤40

x2+x4+x6+x9+x11+x15+x16+x17≤30

x5+x6+x8+x14+x17≤45

 

Для того, чтобы построить симплекс-таблицу, необходимо перейти к основной задаче линейного программирования.

Целевая функция будет  иметь вид:

Ограничения вида неравенств, заменяем на ограничения вида равенств:

где х1,…х17-свободные переменные;      y1,..,y12- базисные переменные.

Таблица 4.2 -Симплекс-таблица

	CК	X1	X2	X3	X4	X5	X6	X7	X8	X9	X10	X11	X12	X13	X14	X15	X16	X17
F	0	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1
Y1	60	1	1	1	1	1	1	0	0	0	0	0	0	0	0	0	0	0
Y2	40	0	0	0	0	0	0	1	1	1	1	1	0	0	0	0	0	0
Y3	35	0	0	0	0	0	0	0	0	0	0	0	1	1	1	1	1	1
Y4	30	1	1	0	0	0	0	1	1	0	0	0	1	0	0	0	1	0
Y5	40	1	0	0	1	0	1	0	0	1	1	0	0	1	1	0	1	0
Y6	20	0	1	0	1	0	1	0	0	0	0	1	1	1	1	0	0	0
Y7	30	0	0	1	1	0	0	1	0	0	0	0	0	1	0	1	0	0
Y8	45	0	0	0	0	1	1	0	1	0	0	0	0	0	0	0	0	1
Y9	20	0	0	0	0	0	0	0	0	1	0	0	0	0	0	0	0	0
Y10	40	0	1	1	0	1	0	0	0	0	1	0	0	1	1	0	1	0
Y11	30	0	1	0	1	0	1	0	0	1	0	1	0	0	0	1	1	1
Y12	45	0	0	0	0	1	1	0	1	0	0	0	0	0	1	0	0	1

 

4.3 Расчет на ЭВМ  потоков сообщения

Решим данную задачу с  помощью симплекс метода на ЭВМ.

Получим решение :

Раскрывая скобки, видим, что при увеличении любой из переменных функция F возрастает, что недопустимо.

Следовательно, решение  найдено:

F=- =100

Принимаем все свободные  переменные равные нулю:

Х15= х7=х4= х8= х13=x9=х11=у1=у7=у3=у5=y6=0,

тогда, по таблице симплекс-метода:

y8=15; x17=22.5; x1=22.5;x6=7.5; x14=5; y2=35; y12=10; y9=20; x3=30; x12=7.5;x10=5

 

 

 

 

 

 

 

 

4. Построение вторичного графа СПИ

    Построим вторичный  граф СПИ при  оптимальном   распределении  каналов. Сначала  cоставим  массив  всех  путей,  по  которым  передается  количество  сообщений,  больше  нуля:

Таблица 4.4.1 – Таблица  для построения вторичного графи СПИ

Путь	Обозначение	Количество сообщений, Х
4-5-7-2	1	22.5
2-1-3	2	22.5
2-7-5-4-1-3	3	7.5
4-1-3-5-7-2	4	5
2-5-3	5	30
4-1-2	6	7.5
1-3-5	7	5

 

Построим вторичный  граф СПИ.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Рис. 4.4.1 - Вторичный граф СПИ

 

5 Разработка алгоритма управления  СПИ по критерию максимальной  надежности

5.1 Построение матрицы  надежных маршрутов (дистанционной  таблицы)

По исходным данным построим матрицу надежности:

	1	0.997	0.995	0.994	0	0	0
	0.997	1	0	0	0.994	0	0.999
	0.995	0	1	0.994	0.999	0	0
W=	0.994	0	0.994	1	0.995	0.999	0
	0	0.994	0.999	0.995	1	0.999	0.997
	0	0	0	0.999	0.999	1	0.999
	0	0.999	0	0	0.997	0.999	1

Перейдем к матрице  ненадежности по формуле:

	0	3	5	6
	3	0			6		1
	5		0	6	1
	6		6	0	5	1
		6	1	5	0	1	3
				1	1	0	1
		1			3	1	0

Определим матрицу минимальной ненадежности с помощью операций Шимбела – Оттермана:

	0	3	5	6	6	5	4
	3	0	7	9	4	2	1
	5	7	0	6	1	2	4
	6	9	6	0	2	1	2
	6	4	1	2	0	1	2
	7	2	2	1	1	0	1
	4	1	4	2	2	1	0