Оптимизация структуры сетей связи
1.4 Вывод
С увеличением количества ветвей суммарная протяженность ветвей увеличивается. В нашем случае сеть с МПВ состоит при n=nmin = 7 из ветвей: 1-3; 2-3; 3-5; 5-4; 5-7; 5-8; 6-7.имеем сеть с наименьшей протяженностью ветвей. Протяженность ветвей 167 км. При n = nmax = 28 протяженность ветвей максимальна и составляет 1708 км. График зависимости суммарной протяженности ветвей от числа ветвей представлен приложении 4
2. Расчет сетей связи с минимальной протяженностью связей
При построении различных вариантов схем сети, отличающихся числом n и расположением ветвей связи, будут возникать различия в емкостях, так как при отсутствии непосредственной связи между двумя пунктами, каналы между ними необходимо направлять в обход, укрупняя другие ветви.
Требование обеспечения заданного числа каналов между каждой парой пунктов остается обязательным, поэтому задача сводится к оптимальному распределению каналов по ветвям сети, обеспечивающим минимальную протяженность связей (МПС).
Суммарная протяженность связей каждого варианта построения сети определяется по формуле:
сеть ветвь канал станция
где lij нij - протяженность пути между пунктами i и j, состоящий из p ветвей
нij - требуемое число каналов между пунктами i и j,
n - число ветвей связи для данного варианта построения сети.
Алгоритм построения сети с МПС:
· Ввод исходных данных: N, L, V;
· Расчет значений:
· Расчет
· Расчет ?Lсвij при изъятии произвольной ветви i-j;
· Выбор минимального значения ?Lсвij и фиксация обходного пути для каналов изъятой ветви i-j;
· Перераспределение элементов в матрицах L и V, связанное с отсутствием изъятой ветви i-j и появлением дополнительного числа каналов Vij в ветвях обхода.
· Расчет
· Присвоение индексу n значения n ?1.
· Проверка значения n : при n = nmin - окончание расчетов.
Таким образом, сеть, имеющая наименьшую протяженность связей, будет образована путем соединения всех пунктов по принципу «каждый с каждым»(см. Приложение 5). Для такой сети потребуется nmax ветвей. При всех других схемах суммарная протяженность связей будет возрастать.
Максимальную протяженность связей будет иметь схема сети с МПВ -- «дерево».
2.1 Исходные данные
N = 8;
0 |
114 |
24 |
34 |
44 |
54 |
64 |
74 |
||
0 |
0 |
15 |
125 |
35 |
45 |
55 |
65 |
||
0 |
0 |
0 |
116 |
26 |
36 |
46 |
56 |
||
L = |
0 |
0 |
0 |
0 |
17 |
127 |
37 |
47 |
|
0 |
0 |
0 |
0 |
0 |
118 |
28 |
38 |
||
0 |
0 |
0 |
0 |
0 |
0 |
19 |
129 |
||
0 |
0 |
0 |
0 |
0 |
0 |
0 |
120 |
||
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
280 |
240 |
580 |
160 |
170 |
280 |
1420 |
||
0 |
0 |
360 |
240 |
500 |
600 |
460 |
220 |
||
0 |
0 |
0 |
330 |
360 |
290 |
230 |
650 |
||
V= |
0 |
0 |
0 |
0 |
900 |
210 |
420 |
640 |
|
0 |
0 |
0 |
0 |
0 |
310 |
620 |
620 |
||
0 |
0 |
0 |
0 |
0 |
0 |
610 |
1040 |
||
0 |
0 |
0 |
0 |
0 |
0 |
0 |
80 |
||
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
;
2.2 Расчет суммарной протяженности связей при n=nmax=28
2.3 Расчет суммарной протяженности связей при
n=nmax-1=27:
Возможны следующие обходы:
без ветви |
1-2 |
кратчайший обходной путь |
(1-7; 7-2) |
?Lсв = |
1400 |
кан.-км |
|
без ветви |
1-3 |
кратчайший обходной путь |
(1-5; 5-3) |
?Lсв = |
11040 |
кан.-км |
|
без ветви |
1-4 |
кратчайший обходной путь |
(1-5; 5-4) |
?Lсв = |
15660 |
кан.-км |
|
без ветви |
1-5 |
кратчайший обходной путь |
(1-3; 3-5) |
?Lсв = |
960 |
кан.-км |
|
без ветви |
1-6 |
кратчайший обходной путь |
(1-3; 3-6) |
?Lсв = |
1020 |
кан.-км |
|
без ветви |
1-7 |
кратчайший обходной путь |
(1-3; 3-7) |
?Lсв = |
1680 |
кан.-км |
|
без ветви |
1-8 |
кратчайший обходной путь |
(1-3; 3-8) |
?Lсв = |
8520 |
кан.-км |
|
без ветви |
2-3 |
кратчайший обходной путь |
(2-5; 5-3) |
?Lсв = |
16560 |
кан.-км |
|
без ветви |
2-4 |
кратчайший обходной путь |
(2-3;3-5; 5-8;8-4) |
?Lсв = |
240 |
кан.-км |
|
без ветви |
2-5 |
кратчайший обходной путь |
(2-3; 3-5) |
?Lсв = |
3000 |
кан.-км |
|
без ветви |
2-6 |
кратчайший обходной путь |
(2-3; 3-6) |
?Lсв = |
3600 |
кан.-км |
|
без ветви |
2-7 |
кратчайший обходной путь |
(2-3; 3-7) |
?Lсв = |
2760 |
кан.-км |
|
без ветви |
2-8 |
кратчайший обходной путь |
(2-3; 3-8) |
?Lсв = |
1320 |
кан.-км |
|
без ветви |
3-4 |
кратчайший обходной путь |
(3-2;2-6; 6-7;7-4) |
?Lсв = |
0 |
кан.-км |
|
без ветви |
3-5 |
кратчайший обходной путь |
(3-2; 2-5) |
?Lсв = |
8640 |
кан.-км |
|
без ветви |
3-6 |
кратчайший обходной путь |
(3-2; 2-6) |
?Lсв = |
6960 |
кан.-км |
|
без ветви |
3-7 |
кратчайший обходной путь |
(3-5; 5-7) |
?Lсв = |
1840 |
кан.-км |
|
без ветви |
3-8 |
кратчайший обходной путь |
(3-5; 5-8) |
?Lсв = |
5200 |
кан.-км |
|
без ветви |
4-5 |
кратчайший обходной путь |
(4-7; 7-5) |
?Lсв = |
43200 |
кан.-км |
|
без ветви |
4-6 |
кратчайший обходной путь |
(4-5; 5-7; 7-3;3-6) |
?Lсв = |
0 |
кан.-км |
|
без ветви |
4-7 |
кратчайший обходной путь |
(4-5; 5-7) |
?Lсв = |
3360 |
кан.-км |
|
без ветви |
4-8 |
кратчайший обходной путь |
(4-5; 5-8) |
?Lсв = |
5120 |
кан.-км |
|
без ветви |
5-6 |
кратчайший обходной путь |
(5-2;2-3; 3-7;7-6) |
?Lсв = |
930 |
кан.-км |
|
без ветви |
5-7 |
кратчайший обходной путь |
(5-4; 4-7) |
?Lсв = |
16120 |
кан.-км |
|
без ветви |
5-8 |
кратчайший обходной путь |
(5-4; 4-8) |
?Lсв = |
16120 |
кан.-км |
|
без ветви |
6-7 |
кратчайший обходной путь |
(6-3; 3-7) |
?Lсв = |
38430 |
кан.-км |
|
без ветви |
6-8 |
кратчайший обходной путь |
(6-7; 7-3; 3-5;5-8) |
?Lсв = |
0 |
кан.-км |
|
без ветви |
7-8 |
кратчайший обходной путь |
(7-2; 2-8) |
?Lсв = |
0 |
кан.-км |
Кратчайший обходной путь (3-2;2-6;6-7;7-4)без ветви 3-4 дает
?Lсв min = 330 * (116 - ( 15 +45+19+ 37 ) = 0 кан.-км
Произведем перераспределение каналов в матрицах V и L(? - изъятая ветвь, соединение между парой узлов отсутствует.):
0 |
114 |
24 |
34 |
44 |
54 |
64 |
74 |
||
0 |
0 |
15 |
125 |
35 |
45 |
55 |
65 |
||
0 |
0 |
0 |
? |
26 |
36 |
46 |
56 |
||
L ` = |
0 |
0 |
0 |
0 |
17 |
127 |
37 |
47 |
|
0 |
0 |
0 |
0 |
0 |
118 |
28 |
38 |
||
0 |
0 |
0 |
0 |
0 |
0 |
19 |
129 |
||
0 |
0 |
0 |
0 |
0 |
0 |
0 |
120 |
||
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
280 |
240 |
580 |
160 |
170 |
280 |
1420 |
||
0 |
0 |
360+330 |
240 |
500 |
600+330 |
460 |
220 |
||
0 |
0 |
0 |
? |
360 |
290 |
230 |
650 |
||
V= |
0 |
0 |
0 |
0 |
900 |
210 |
420+330 |
640 |
|
0 |
0 |
0 |
0 |
0 |
310 |
620 |
620 |
||
0 |
0 |
0 |
0 |
0 |
0 |
610+330 |
1040 |
||
0 |
0 |
0 |
0 |
0 |
0 |
0 |
80 |
||
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
Рассчитаем суммарную протяженность связей при n=nmax=28-1=27
2.4 Расчет суммарной протяженности связей при остальных n
Аналогично рассчитываем протяженность связей для n = nmax ?2=26, n = nmax ?3=25 и т.д. до тех пор, пока n не станет равным n = nmin =7. Результаты представлены ниже в таблице 1.
Таблица 1
Зависимость суммарной протяженности связей от числа ветвей.
№ |
n |
исключаемая ветвь |
кратчайший обходной путь |
?Lсв min |
? ПС |
||||
0 |
28 |
- |
- |
- |
741620 |
||||
1 |
27 |
(3-4) |
(3-2;2-6;6-7;7-4) |
0 |
741620 |
||||
2 |
26 |
(4-6) |
(4-5;5-7;7-3;3-6) |
0 |
741620 |
||||
3 |
25 |
(6-8) |
(6-7;7-3; 3-5;5-8) |
0 |
741620 |
||||
4 |
24 |
(7-8) |
(7-2; 2-8) |
0 |
741620 |
||||
5 |
23 |
(2-4) |
(2-3; 3-5;5-8;8-4) |
240 |
741860 |
||||
6 |
22 |
(5-6) |
(5-2;2-3;3-7;7-6) |
930 |
742790 |
||||
7 |
21 |
(1-5) |
(1-3; 3-5) |
960 |
743750 |
||||
8 |
20 |
(1-6) |
(1-3; 3-6) |
1020 |
744770 |
||||
9 |
19 |
(1-2) |
(1-7; 7-2) |
1400 |
746170 |
||||
10 |
18 |
(2-8) |
(2-3; 3-8) |
1800 |
747970 |
||||
11 |
17 |
(1-7) |
(1-3;3-7) |
3360 |
751330 |
||||
12 |
16 |
(2-5) |
(2-3; 3-5) |
4860 |
756190 |
||||
13 |
15 |
(2-7) |
(2-3; 3-7) |
4920 |
761110 |
||||
14 |
14 |
(2-6) |
(2-3;3-6) |
5580 |
766690 |
||||
15 |
13 |
(4-7) |
(4-5; 5-7) |
6000 |
772690 |
||||
16 |
12 |
(4-8) |
(4-5; 5-8) |
7040 |
779730 |
||||
17 |
11 |
(3-8) |
(3-5; 5-8) |
7600 |
787330 |
||||
18 |
10 |
(1-4) |
(1-3;3-5; 5-4) |
19140 |
806470 |
||||
19 |
9 |
(1-8) |
(1-3;3-5;5-8) |
19880 |
826350 |
||||
20 |
8 |
(3-7) |
(3-5; 5-7) |
25360 |
851710 |
||||
21 |
7 |
(3-6) |
(3-5; 5-7;7-6) |
59200 |
910910 |
||||
0 |
? |
24 |
? |
? |
? |
? |
? |
||
0 |
0 |
15 |
? |
? |
? |
? |
? |
||
0 |
0 |
0 |
? |
26 |
? |
? |
? |
||
L = |
0 |
0 |
0 |
0 |
17 |
? |
? |
? |
|
0 |
0 |
0 |
0 |
0 |
? |
28 |
38 |
||
0 |
0 |
0 |
0 |
0 |
0 |
19 |
? |
||
0 |
0 |
0 |
0 |
0 |
0 |
0 |
? |
||
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
||
0 |
? |
3130 |
? |
? |
? |
? |
? |
||
0 |
0 |
4100 |
? |
? |
? |
? |
? |
||
0 |
0 |
0 |
? |
10330 |
? |
? |
? |
||
V = |
0 |
0 |
0 |
0 |
3320 |
? |
? |
? |
|
0 |
0 |
0 |
0 |
0 |
? |
6350 |
5150 |
||
0 |
0 |
0 |
0 |
0 |
0 |
3890 |
? |
||
0 |
0 |
0 |
0 |
0 |
0 |
0 |
? |
||
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
2.5 Построение модели структуры сети с МПС при
n=nmin =7
Соединяем те пары узлов, ветви которых не равны бесконечности в окончательной матрице L?.
Рис. 2
Модель структуры сети с МПС при n=nmin =7
2.6 Вывод
Сеть с МПС состоит при n=nmin = 7 из ветвей: 1-3, 2-3, 3-5, 4-5, 5-8, 5-7, 6-7 имеем сеть с наибольшей протяженностью связей. Суммарная протяженность связи при n=nmin = 7 максимальна и составляет 910910 кан.-км. При n = nmax = 24 суммарная протяженность связи минимальна и составляет 741620 кан.-км. Наименьшая протяженность связей не соответствует сети «каждый с каждым», так как обходной путь может быть таким же, как прямой путь, поэтому суммарная протяженность не изменяется. График зависмости суммарной протяженности связи от числа ветвей представлен в приложении 4
3. Расчет сети с МКЗ
Сеть, имеющая минимальное значение капитальных затрат будет занимать некоторое промежуточное положение в ряду вариантов структур сети, ограниченном с одной стороны структурой сети с МПВ, а с другой - с МПС.
Алгоритм построения сети с МКЗ:
· Ввод исходных данных: N, L, V, КЗ;
· Расчет значений:
· Расчет
?
· Изъятие произвольной ветви i-j и поиск для нее такого обходного пути, который дает минимум капитальных затрат на построение всей сети.
· Выбор минимального значения среди всех вариантов структур полученных в результате изъятия ветвей в предыдущем пункте и фиксация обходного пути для каналов изъятой ветви i-j;
· Перераспределение элементов в матрицах L и V, связанное с отсутствием изъятой ветви i-j и появлением дополнительного числа каналов Vij в ветвях обхода.
· Расчет
· Присвоение индексу n значения n ?1.
· Проверка значения n : при min n = n - окончание расчетов.
3.1 Исходные данные
0 |
114 |
24 |
34 |
44 |
54 |
64 |
74 |
||
0 |
0 |
15 |
125 |
35 |
45 |
55 |
65 |
||
0 |
0 |
0 |
116 |
26 |
36 |
46 |
56 |
||
L = |
0 |
0 |
0 |
0 |
17 |
127 |
37 |
47 |
|
0 |
0 |
0 |
0 |
0 |
118 |
28 |
38 |
||
0 |
0 |
0 |
0 |
0 |
0 |
19 |
129 |
||
0 |
0 |
0 |
0 |
0 |
0 |
0 |
120 |
||
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
280 |
240 |
580 |
160 |
170 |
280 |
1420 |
||
0 |
0 |
360 |
240 |
500 |
600 |
460 |
220 |
||
0 |
0 |
0 |
330 |
360 |
290 |
230 |
650 |
||
V= |
0 |
0 |
0 |
0 |
900 |
210 |
420 |
640 |
|
0 |
0 |
0 |
0 |
0 |
310 |
620 |
620 |
||
0 |
0 |
0 |
0 |
0 |
0 |
610 |
1040 |
||
0 |
0 |
0 |
0 |
0 |
0 |
0 |
80 |
||
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
Из таблицы приложения 3 и на основании матрицы V получаем матрицу капитальных затрат в соответствии с зависимостью kз кан.-кмij = f(vij):
0 |
20 |
25 |
20 |
25 |
25 |
20 |
15 |
||
0 |
0 |
20 |
25 |
20 |
20 |
20 |
25 |
||
0 |
0 |
0 |
20 |
20 |
20 |
25 |
18 |
||
Кз = |
0 |
0 |
0 |
0 |
18 |
25 |
20 |
18 |
|
0 |
0 |
0 |
0 |
0 |
20 |
18 |
20 |
||
0 |
0 |
0 |
0 |
0 |
0 |
18 |
15 |
||
0 |
0 |
0 |
0 |
0 |
0 |
0 |
30 |
||
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
3.2 Расчет суммарных капитальных затрат
Распишем подробно первую итерацию при n = nmax - 1 = 27:
Возможны следующие обходы:
без ветви |
1-2 |
кратчайший обходной путь |
(1-3; 3-2) |
КЗ = |
13513270 |
|
без ветви |
1-3 |
кратчайший обходной путь |
(1-8; 8-3) |
КЗ = |
13977070 |
|
без ветви |
1-4 |
кратчайший обходной путь |
(1-5; 5-4) |
КЗ = |
14098950 |
|
без ветви |
1-5 |
кратчайший обходной путь |
(1-8; 8-5) |
КЗ = |
13741550 |
|
без ветви |
1-6 |
кратчайший обходной путь |
(1-8; 8-2; 2-6) |
КЗ = |
13820690 |
|
без ветви |
1-7 |
кратчайший обходной путь |
(1-8; 8-5; 5-7) |
КЗ = |
13888910 |
|
без ветви |
1-8 |
кратчайший обходной путь |
(1-4; 4-8) |
КЗ = |
13447070 |
|
без ветви |
2-3 |
кратчайший обходной путь |
(2-5; 5-3) |
КЗ = |
14214830 |
|
без ветви |
2-4 |
кратчайший обходной путь |
(2-5;5-4) |
КЗ = |
13362770 |
|
без ветви |
2-5 |
кратчайший обходной путь |
(2-3; 3-5) |
КЗ = |
13970750 |
|
без ветви |
2-6 |
кратчайший обходной путь |
(2-7; 7-6) |
КЗ = |
13946000 |
|
без ветви |
2-7 |
кратчайший обходной путь |
(2-6; 6-7) |
КЗ = |
13747100 |
|
без ветви |
2-8 |
кратчайший обходной путь |
(2-3; 3-1; 1-8) |
КЗ = |
13646690 |
|
без ветви |
3-4 |
кратчайший обходной путь |
(3-5;5-4) |
КЗ = |
13389640 |
|
без ветви |
3-5 |
кратчайший обходной путь |
(3-2; 2-5) |
КЗ = |
14072270 |
|
без ветви |
3-6 |
кратчайший обходной путь |
(3-2; 2-6) |
КЗ = |
14020870 |
|
без ветви |
3-7 |
кратчайший обходной путь |
(3-5; 5-7) |
КЗ = |
13952290 |
|
без ветви |
3-8 |
кратчайший обходной путь |
(3-1; 1-8) |
КЗ = |
13828510 |
|
без ветви |
4-5 |
кратчайший обходной путь |
(4-8; 8-5) |
КЗ = |
14302030 |
|
без ветви |
4-6 |
кратчайший обходной путь |
(4-7;7-6) |
КЗ = |
13495120 |
|
без ветви |
4-7 |
кратчайший обходной путь |
(4-5; 5-7) |
КЗ = |
13855990 |
|
без ветви |
4-8 |
кратчайший обходной путь |
(4-5; 5-8) |
КЗ = |
13772710 |
|
без ветви |
5-6 |
кратчайший обходной путь |
(5-7;7-6) |
КЗ = |
13511930 |
|
без ветви |
5-7 |
кратчайший обходной путь |
(5-4; 4-7) |
КЗ = |
13969870 |
|
без ветви |
5-8 |
кратчайший обходной путь |
(5-4; 4-8) |
КЗ = |
13938730 |
|
без ветви |
6-7 |
кратчайший обходной путь |
(6-2; 2-7) |
КЗ = |
14426150 |
|
без ветви |
6-8 |
кратчайший обходной путь |
(6-7; 7-5; 5-8) |
КЗ = |
12714610 |
|
без ветви |
7-8 |
кратчайший обходной путь |
(7-6; 6-2; 2-8) |
КЗ = |
13763930 |
Таким образом, после первой итерации изымается ветвь 6-8, так как именно ее изъятие дает минимальные КЗ = 12714610 руб.с обходом (6-7; 7-5; 5-8),из сети с 27 ветвями.
Произведем перераспределение каналов в матрицах V, L,Кз(? - изъятая ветвь, соединение между парой узлов отсутствует
0 |
114 |
24 |
34 |
44 |
54 |
64 |
74 |
||
0 |
0 |
15 |
125 |
35 |
45 |
55 |
65 |
||
0 |
0 |
0 |
116 |
26 |
36 |
46 |
56 |
||
L = |
0 |
0 |
0 |
0 |
17 |
127 |
37 |
47 |
|
0 |
0 |
0 |
0 |
0 |
118 |
28 |
38 |
||
0 |
0 |
0 |
0 |
0 |
0 |
19 |
? |
||
0 |
0 |
0 |
0 |
0 |
0 |
0 |
120 |
||
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
280 |
240 |
580 |
160 |
170 |
280 |
1420 |
||
0 |
0 |
360 |
240 |
500 |
600 |
460 |
220 |
||
0 |
0 |
0 |
330 |
360 |
290 |
230 |
650 |
||
V= |
0 |
0 |
0 |
0 |
900 |
210 |
420 |
640 |
|
0 |
0 |
0 |
0 |
0 |
310 |
1660 |
1660 |
||
0 |
0 |
0 |
0 |
0 |
0 |
1650 |
? |
||
0 |
0 |
0 |
0 |
0 |
0 |
0 |
80 |
||
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
20 |
25 |
20 |
25 |
25 |
20 |
15 |
||
0 |
0 |
20 |
25 |
20 |
20 |
20 |
25 |
||
0 |
0 |
0 |
20 |
20 |
20 |
25 |
18 |
||
Кз = |
0 |
0 |
0 |
0 |
18 |
25 |
20 |
18 |
|
0 |
0 |
0 |
0 |
0 |
20 |
12 |
12 |
||
0 |
0 |
0 |
0 |
0 |
0 |
12 |
? |
||
0 |
0 |
0 |
0 |
0 |
0 |
0 |
30 |
||
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
Дальнейшие итерации в соответствии с алгоритмом представим в таблице 2:
Таблица 2
Зависимость капитальных затрат от числа ветвей
№ |
n |
исключаемая ветвь |
кратчайший обходной путь |
? КЗ |
|
0 |
28 |
- |
- |
13981270 |
|
1 |
27 |
(6-8) |
(6-7; 7-5; 5-8) |
12714610 |
|
2 |
26 |
(2-4) |
(2-5;5-4) |
12096110 |
|
3 |
25 |
(1-8) |
(1-4;4-5;5-8) |
11499450 |
|
4 |
24 |
(3-4) |
(3-5;5-4) |
10925670 |
|
5 |
23 |
(5-6) |
(5-7;7-6) |
10368910 |
|
6 |
22 |
(4-6) |
(4-5;5-7;7-6) |
9856300 |
|
7 |
21 |
(1-2) |
(1-3; 3-2) |
9388300 |
|
8 |
20 |
(2-7) |
(2-5;5-7) |
9052820 |
|
9 |
19 |
(7-8) |
(7-5;5-8) |
8817620 |
|
10 |
18 |
(2-6) |
(2-5; 5-7;7-6) |
8603160 |
|
11 |
17 |
(3-8) |
(3-5;5-8) |
8394640 |
|
12 |
16 |
(2-8) |
(2-3; 3-5;5-8) |
7837980 |
|
13 |
15 |
(4-8) |
(4-5;5-8) |
7599900 |
|
14 |
14 |
(4-7) |
(4-5;5-7) |
7336660 |
|
15 |
13 |
(1-7) |
(1-4;4-5;5-7) |
6983860 |
|
16 |
12 |
(2-5) |
(2-3;3-5) |
6781540 |
|
17 |
11 |
(3-7) |
(3-1;1-4;4-5;5-7) |
6597400 |
|
18 |
10 |
(1-5) |
(1-4;4-5) |
6497560 |
|
19 |
9 |
(1-6) |
(1-4;4-5;5-7;7-6) |
6419360 |
|
20 |
8 |
(3-6) |
(3-5; 5-7;7-6) |
6406020 |
|
21 |
7 |
(1-3) |
(1-4;4-5;5-3) |
6405220 |
Окончательный вид матриц L и V после последней итерации:
0 |
? |
? |
34 |
? |
? |
? |
? |
||
0 |
0 |
15 |
? |
? |
? |
? |
? |
||
0 |
0 |
0 |
? |
26 |
? |
? |
? |
||
L = |
0 |
0 |
0 |
0 |
17 |
? |
? |
? |
|
0 |
0 |
0 |
0 |
0 |
? |
28 |
38 |
||
0 |
0 |
0 |
0 |
0 |
0 |
19 |
? |
||
0 |
0 |
0 |
0 |
0 |
0 |
0 |
? |
||
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
? |
? |
3590 |
? |
? |
? |
? |
||
0 |
0 |
2660 |
? |
? |
? |
? |
? |
||
0 |
0 |
0 |
? |
4400 |
? |
? |
? |
||
V= |
0 |
0 |
0 |
0 |
5750 |
? |
? |
? |
|
0 |
0 |
0 |
0 |
0 |
? |
4710 |
4670 |
||
0 |
0 |
0 |
0 |
0 |
0 |
3230 |
? |
||
0 |
0 |
0 |
0 |
0 |
0 |
0 |
? |
||
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
3.3 Построение модели структуры сети с МКЗ
Соединяем те пары узлов, ветви которых не равны бесконечности в окончательной матрице L?.
Рис. 3
Модель структуры сети с Кз при n=nmin =7
3.4 Вывод
Сеть с МКЗ состоит при n=nmin = 7 из ветвей: 1-4, 2-3, 3-5, 4-5, 5-8, 5-7, 6-7 имеем сеть с минимальными капитальными затратами. Суммарные капитальные затраты при n=nmin = 7 минимальны и составляют 6405220 руб. При n = nmax = 28 суммарная капитальные затраты максимальны и составляет 13981270 руб. График зависимости суммарной протяженности связи от числа ветвей представлен в приложении 4
4. Заключение
Освоив методики и алгоритмы построения сетей связи с минимальной протяженностью ветвей (МПВ), с минимальной протяженностью связей (МПС); с минимальными капитальными затратами (МКЗ)пришли к следующим выводам:
· Структура сети с минимальной протяженностью ветвей (МПВ) соответствует такой сети, в которой сумма длин ветвей минимальна. С точки зрения теории сетей связи сеть с МПВ - это экстремальное полное
собственное дерево, для построения которого используется метод Прима. С увеличением количества ветвей суммарная протяженность ветвей увеличивается. Топология «каждый с каждым» будет иметь максимальную протяженность ветвей
· При построении различных вариантов схем сети, отличающихся числом и расположением ветвей связи, будут возникать различия в емкостях, так как при отсутствии непосредственной связи между двумя пунктами, каналы между ними необходимо направлять в обход, укрупняя другие ветви. Требование обеспечения заданного числа каналов между каждой парой пунктов остается обязательным, поэтому задача сводится к оптимальному распределению каналов по ветвям сети, обеспечивающим минимальную протяженность связей. Сеть, имеющая наименьшую протяженность связей, будет образована путем соединения всех пунктов по принципу «каждый с каждым». Для такой сети потребуется максимальное количество ветвей. При всех других схемах суммарная протяженность связей будет возрастать. Максимальную протяженность связей будет иметь схема сети с минимальным числом ветвей - «дерево».
· ,На сети используются системы передачи, из которых капитальные затраты, приходящиеся на 1 кан.-км обратно пропорциональны числу каналов. Это возможно тогда, когда на всех магистралях сети используются одинаковые кабели и системы передачи. Причем, максимальная емкость каждой из них соответствует наибольшей по числу каналов магистрали сети. Поэтому, для получения минимума суммы капитальных затрат на сеть, мы стремились бы иметь по возможности более мощные магистрали. Это достигается, при структуре сети, использующей минимальное число ветвей, т.е. в сети с МПВ.
5. Список используемой литературы
1. Рогинский В.Н., Харкевич А.Д., Шнепо М.А., Давыдов Г.Б., Толчан А.Я. Теория сетей связи. - М.:Радио и связь, 1981.
2. Демина Е.В., Траубенберг И.А., Иодко Е.К., Майофис Л.И. Организация, планирование и управление предприятиями электрической связи. - М.: Связь, 1979.
3. Аджемов С.А. Метод анализа схем построения сети междугородных связей. - Сб. научных трудов ЦНИИС, вып. I, 1961.
4. Аджемов С.А. Об оценке схем построения сети по надежности и стоимости. - Сб. научных трудов ЦНИИС, вып. I, 1962.
Приложение 1
Расстояние между пунктами сети Lij
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
16 |
17 |
18 |
19 |
20 |
21 |
22 |
23 |
24 |
25 |
26 |
27 |
28 |
29 |
30 |
31 |
32 |
33 |
||
1 |
0 |
11 |
21 |
31 |
41 |
51 |
61 |
71 |
81 |
91 |
12 |
22 |
32 |
21 |
31 |
|||||||||||||||||||
2 |
0 |
32 |
42 |
132 |
45 |
52 |
62 |
72 |
82 |
92 |
40 |
50 |
60 |
40 |
50 |
|||||||||||||||||||
3 |
0 |
113 |
123 |
33 |
43 |
53 |
63 |
73 |
83 |
93 |
45 |
55 |
65 |
16 |
26 |
|||||||||||||||||||
4 |
0 |
114 |
24 |
34 |
44 |
54 |
64 |
74 |
84 |
94 |
17 |
27 |
37 |
2 |
87 |
|||||||||||||||||||
5 |
0 |
15 |
125 |
35 |
45 |
55 |
65 |
75 |
85 |
95 |
48 |
59 |
68 |
3 |
76 |
|||||||||||||||||||
6 |
0 |
116 |
26 |
36 |
46 |
56 |
66 |
76 |
86 |
96 |
18 |
28 |
38 |
5 |
65 |
|||||||||||||||||||
7 |
0 |
17 |
127 |
37 |
47 |
57 |
67 |
77 |
87 |
97 |
20 |
30 |
40 |
31 |
8 |
|||||||||||||||||||
8 |
0 |
118 |
28 |
38 |
48 |
58 |
68 |
78 |
88 |
98 |
64 |
74 |
84 |
104 |
56 |
|||||||||||||||||||
9 |
0 |
19 |
129 |
39 |
49 |
59 |
69 |
79 |
89 |
99 |
90 |
99 |
75 |
180 |
67 |
|||||||||||||||||||
10 |
0 |
120 |
30 |
40 |
50 |
60 |
70 |
80 |
90 |
99 |
38 |
48 |
59 |
74 |
85 |
|||||||||||||||||||
11 |
0 |
11 |
121 |
31 |
41 |
51 |
61 |
71 |
81 |
91 |
97 |
20 |
30 |
34 |
67 |
|||||||||||||||||||
12 |
0 |
112 |
22 |
32 |
42 |
52 |
62 |
72 |
82 |
92 |
62 |
72 |
82 |
89 |
70 |
|||||||||||||||||||
13 |
0 |
113 |
23 |
33 |
43 |
53 |
63 |
73 |
83 |
93 |
36 |
46 |
57 |
123 |
13 |
|||||||||||||||||||
14 |
0 |
14 |
124 |
34 |
44 |
54 |
64 |
74 |
84 |
94 |
19 |
29 |
39 |
115 |
84 |
|||||||||||||||||||
15 |
0 |
115 |
25 |
35 |
45 |
56 |
65 |
75 |
85 |
95 |
60 |
69 |
79 |
109 |
89 |
|||||||||||||||||||
16 |
0 |
66 |
26 |
36 |
46 |
57 |
66 |
76 |
86 |
96 |
41 |
51 |
61 |
91 |
19 |
|||||||||||||||||||
17 |
0 |
77 |
27 |
37 |
47 |
58 |
67 |
77 |
87 |
97 |
90 |
99 |
38 |
92 |
18 |
|||||||||||||||||||
18 |
0 |
88 |
28 |
38 |
48 |
59 |
68 |
78 |
88 |
98 |
85 |
95 |
60 |
84 |
56 |
|||||||||||||||||||
19 |
0 |
99 |
29 |
39 |
49 |
60 |
69 |
79 |
89 |
99 |
90 |
99 |
75 |
23 |
54 |
|||||||||||||||||||
20 |
0 |
210 |
30 |
40 |
50 |
51 |
70 |
80 |
90 |
99 |
34 |
23 |
101 |
46 |
||||||||||||||||||||
21 |
0 |
110 |
21 |
31 |
41 |
52 |
61 |
71 |
81 |
91 |
9 |
12 |
23 |
|||||||||||||||||||||
22 |
0 |
78 |
52 |
32 |
42 |
53 |
62 |
72 |
82 |
92 |
43 |
56 |
||||||||||||||||||||||
23 |
0 |
89 |
23 |
33 |
43 |
54 |
63 |
73 |
83 |
93 |
12 |
|||||||||||||||||||||||
24 |
0 |
114 |
24 |
34 |
44 |
55 |
64 |
74 |
84 |
94 |
||||||||||||||||||||||||
25 |
0 |
65 |
125 |
35 |
45 |
56 |
65 |
75 |
85 |
|||||||||||||||||||||||||
26 |
0 |
89 |
26 |
36 |
46 |
57 |
66 |
76 |
||||||||||||||||||||||||||
27 |
0 |
117 |
27 |
37 |
47 |
58 |
67 |
|||||||||||||||||||||||||||
28 |
0 |
38 |
28 |
38 |
48 |
59 |
||||||||||||||||||||||||||||
29 |
0 |
49 |
29 |
39 |
49 |
|||||||||||||||||||||||||||||
30 |
0 |
60 |
30 |
40 |
||||||||||||||||||||||||||||||
31 |
0 |
101 |
71 |
|||||||||||||||||||||||||||||||
32 |
0 |
162 |
||||||||||||||||||||||||||||||||
33 |
0 |
1 Приложение 2
Требуемое число каналов между пунктами сети Vij
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
||
1 |
60 |
80 |
100 |
220 |
180 |
320 |
900 |
800 |
100 |
60 |
|
2 |
200 |
600 |
60 |
180 |
200 |
440 |
120 |
60 |
300 |
200 |
|
3 |
870 |
70 |
330 |
960 |
360 |
500 |
610 |
150 |
40 |
100 |
|
4 |
80 |
110 |
210 |
180 |
60 |
130 |
200 |
810 |
70 |
700 |
|
5 |
170 |
890 |
280 |
120 |
420 |
450 |
360 |
190 |
840 |
80 |
|
6 |
30 |
80 |
150 |
90 |
140 |
80 |
50 |
130 |
60 |
40 |
|
7 |
400 |
120 |
240 |
800 |
70 |
130 |
100 |
440 |
380 |
450 |
|
8 |
100 |
80 |
220 |
830 |
60 |
180 |
120 |
480 |
110 |
80 |
|
9 |
40 |
150 |
210 |
80 |
130 |
820 |
480 |
500 |
120 |
60 |
|
10 |
80 |
100 |
180 |
320 |
500 |
130 |
420 |
40 |
80 |
110 |
|
11 |
610 |
30 |
520 |
200 |
140 |
540 |
40 |
380 |
50 |
80 |
|
12 |
160 |
420 |
170 |
330 |
270 |
400 |
380 |
590 |
800 |
900 |
|
13 |
60 |
480 |
150 |
130 |
200 |
500 |
400 |
80 |
330 |
200 |
|
14 |
40 |
120 |
230 |
60 |
320 |
260 |
290 |
480 |
40 |
120 |
|
15 |
30 |
820 |
390 |
180 |
480 |
60 |
120 |
180 |
150 |
200 |
|
16 |
60 |
50 |
120 |
40 |
240 |
600 |
320 |
400 |
80 |
500 |
|
17 |
130 |
190 |
160 |
620 |
270 |
540 |
50 |
560 |
120 |
260 |
|
18 |
30 |
270 |
140 |
80 |
480 |
300 |
400 |
180 |
560 |
140 |
|
19 |
40 |
70 |
180 |
200 |
230 |
420 |
30 |
340 |
60 |
120 |
|
20 |
440 |
80 |
120 |
200 |
100 |
390 |
320 |
250 |
160 |
400 |
|
21 |
140 |
340 |
270 |
60 |
340 |
250 |
100 |
60 |
220 |
50 |
|
22 |
40 |
340 |
160 |
530 |
360 |
50 |
410 |
240 |
480 |
390 |
|
23 |
290 |
120 |
160 |
60 |
240 |
510 |
70 |
320 |
90 |
110 |
|
24 |
200 |
140 |
230 |
510 |
260 |
190 |
250 |
140 |
560 |
80 |
|
25 |
140 |
80 |
260 |
340 |
180 |
360 |
120 |
240 |
160 |
70 |
|
26 |
80 |
110 |
210 |
180 |
60 |
130 |
100 |
810 |
70 |
300 |
|
27 |
30 |
320 |
200 |
140 |
540 |
610 |
880 |
50 |
80 |
120 |
|
28 |
50 |
130 |
40 |
270 |
120 |
50 |
130 |
80 |
70 |
40 |
|
29 |
60 |
50 |
120 |
40 |
240 |
600 |
320 |
400 |
30 |
500 |
|
30 |
100 |
420 |
170 |
330 |
270 |
400 |
380 |
530 |
800 |
260 |
|
31 |
30 |
330 |
390 |
180 |
480 |
50 |
120 |
180 |
150 |
200 |
|
32 |
160 |
420 |
170 |
330 |
270 |
400 |
380 |
530 |
800 |
900 |
|
33 |
100 |
80 |
220 |
830 |
60 |
180 |
120 |
430 |
110 |
80 |
Приложение 3
Значения КЗ кан.-км кабельной линии связи при различном числе каналов
Количество каналов |
?60 |
61-120 |
121-240 |
241-600 |
601-1000 |
1001-1500 |
1501-2500 |
2501-4000 |
4001-10000 |
>10000 |
|
р./кан.-км |
40 |
30 |
25 |
20 |
18 |
15 |
12 |
10 |
8 |
6 |
Приложение 4
Графики зависимостей
График 1
Зависимость суммарной протяженности ветвей от числа ветвей
График 2
Зависимость суммарной протяженности связей от числа ветвей
График 3
Зависимость капитальных затрат от числа ветвей
Приложение 5
Модель структуры сети соединении станций по принципу "каждая с каждой".