3. Содержательная постановка задачи
Задана топографическая схема сети электросвязи (рис.2). Для каждой линии связи между узлами сети может быть вычислена метрика (4), характеризующая стоимость использования линии.
Требуется разработать шаблон Excel для расчёта оптимального маршрута прохождения трафика заданной величины между двумя произвольными узлами сети. Критерием оптимальности является минимальная суммарная стоимость использования (сумма метрик) линий, входящих в маршрут. В качестве примера необходимо проложить оптимальный маршрут для прохождения трафика T = 190 Эрл от узла А200 до узла А400 (см. рис.1).
Оценочной функцией в данной задаче является суммарная стоимость пути, связывающего начальный и конечный узлы, а ограничениями служат наличие или отсутствие доступных линий между промежуточными узлами маршрута.
4. Исходные данные
Таблица 1. Характеристики линий связи
Узел i |
Узел j |
Предельная нагрузка Rijпред [Эрл] |
Степень загруженности Nij [%] |
Процент отказов Eij [%] |
Удельная стоимость трафика Sij [руб/Эрл] |
А100 |
А110 |
700 |
15 |
1,0 |
2,00 |
А100 |
А120 |
400 |
10 |
2,0 |
5,00 |
А100 |
А130 |
560 |
80 |
1,5 |
3,00 |
А110 |
А130 |
360 |
40 |
1,7 |
2,00 |
А110 |
А140 |
180 |
15 |
2,2 |
2,00 |
А120 |
А130 |
140 |
12 |
3,0 |
2,00 |
А120 |
А150 |
200 |
20 |
1,6 |
2,00 |
А120 |
А160 |
400 |
25 |
3,1 |
2,00 |
А130 |
А160 |
700 |
37 |
1,0 |
2,00 |
А140 |
А160 |
600 |
10 |
0,9 |
2,00 |
А140 |
А170 |
500 |
14 |
0,7 |
2,00 |
А140 |
А240 |
190 |
2 |
0,3 |
2,00 |
А150 |
А180 |
800 |
11 |
3,4 |
2,00 |
А150 |
А520 |
200 |
3 |
1,0 |
2,50 |
А160 |
А180 |
650 |
36 |
1,6 |
3,00 |
А160 |
А190 |
450 |
50 |
2,4 |
4,00 |
А170 |
А190 |
580 |
34 |
1,5 |
1,00 |
А170 |
А260 |
210 |
3 |
1,7 |
1,30 |
А180 |
А190 |
890 |
36 |
1,4 |
1,00 |
А180 |
А560 |
280 |
4 |
1,2 |
1,20 |
А190 |
ТУ101 |
720 |
62 |
4,0 |
1,00 |
ТУ101 |
ТУ201 |
1500 |
68 |
1,6 |
1,00 |
ТУ101 |
ТУ501 |
2000 |
72 |
3,1 |
1,00 |
А200 |
А210 |
630 |
10 |
1,0 |
1,00 |
А200 |
А220 |
480 |
13 |
0,9 |
1,00 |
А200 |
А240 |
650 |
18 |
0,7 |
1,00 |
А210 |
А220 |
140 |
11 |
3,4 |
1,00 |
А210 |
А230 |
270 |
26 |
1,6 |
7,00 |
А220 |
А250 |
360 |
14 |
2,0 |
2,00 |
А230 |
А250 |
330 |
31 |
1,5 |
2,00 |
А230 |
А270 |
390 |
25 |
1,7 |
2,00 |
А240 |
А250 |
420 |
18 |
2,2 |
2,00 |
А240 |
А260 |
530 |
36 |
3,0 |
2,00 |
А250 |
А290 |
180 |
2 |
1,6 |
2,00 |
А260 |
А290 |
490 |
17 |
1,0 |
3,00 |
А270 |
А280 |
510 |
19 |
0,9 |
3,00 |
А270 |
А290 |
660 |
21 |
0,7 |
3,00 |
А270 |
А360 |
310 |
5 |
0,9 |
2,00 |
А280 |
А290 |
780 |
37 |
3,4 |
3,00 |
А280 |
А390 |
290 |
4 |
0,9 |
2,70 |
А280 |
ТУ201 |
800 |
40 |
1,6 |
3,00 |
А290 |
ТУ201 |
850 |
42 |
2,2 |
3,00 |
ТУ201 |
ТУ301 |
1800 |
54 |
3,1 |
1,00 |
А300 |
А310 |
530 |
13 |
1,0 |
1,00 |
А300 |
А320 |
540 |
11 |
0,9 |
1,00 |
А310 |
А330 |
290 |
20 |
0,7 |
1,00 |
А310 |
А340 |
360 |
16 |
0,6 |
1,00 |
А320 |
А330 |
180 |
4 |
0,7 |
1,00 |
А320 |
А360 |
580 |
8 |
3,4 |
1,00 |
А330 |
А350 |
430 |
12 |
1,6 |
1,00 |
А340 |
А350 |
270 |
16 |
2,2 |
1,00 |
А340 |
А370 |
640 |
24 |
3,1 |
2,00 |
А350 |
А370 |
260 |
12 |
1,0 |
2,00 |
А360 |
А370 |
190 |
13 |
3,1 |
2,00 |
А360 |
А390 |
200 |
41 |
1,0 |
2,00 |
А370 |
А380 |
540 |
29 |
0,9 |
2,00 |
А370 |
А420 |
325 |
5 |
1,9 |
1,90 |
А380 |
А390 |
390 |
31 |
0,7 |
2,00 |
А380 |
А480 |
360 |
2 |
1,1 |
1,70 |
А380 |
ТУ301 |
940 |
36 |
3,4 |
2,00 |
А390 |
ТУ301 |
680 |
39 |
1,6 |
2,00 |
ТУ301 |
ТУ401 |
2100 |
52 |
3,0 |
2,00 |
А400 |
А410 |
190 |
7 |
1,6 |
2,00 |
А400 |
А420 |
230 |
2,5 |
3,1 |
2,00 |
А410 |
А430 |
1700 |
3 |
1,0 |
2,00 |
А420 |
А440 |
360 |
36 |
0,9 |
2,00 |
А420 |
А450 |
280 |
2 |
0,7 |
2,00 |
А430 |
А460 |
600 |
17 |
5,0 |
3,00 |
А440 |
А460 |
420 |
19 |
4,7 |
3,00 |
А450 |
А470 |
540 |
21 |
1,2 |
3,00 |
А450 |
А480 |
550 |
37 |
1,3 |
3,00 |
А460 |
А470 |
760 |
40 |
3,4 |
3,00 |
А460 |
А540 |
190 |
7 |
2,7 |
2,20 |
А470 |
А480 |
820 |
42 |
1,6 |
3,00 |
А470 |
А490 |
800 |
54 |
2,2 |
3,00 |
А480 |
ТУ401 |
960 |
64 |
3,1 |
3,00 |
А490 |
ТУ401 |
1070 |
70 |
1,0 |
1,00 |
А490 |
А570 |
600 |
8 |
3,0 |
1,50 |
ТУ401 |
ТУ501 |
1250 |
83 |
3,1 |
1,00 |
А500 |
А510 |
190 |
11 |
1,0 |
1,00 |
А500 |
А520 |
260 |
12 |
1,0 |
1,00 |
А500 |
А530 |
180 |
6 |
0,9 |
1,00 |
А510 |
А530 |
340 |
4 |
0,7 |
1,00 |
А510 |
А540 |
170 |
8 |
5,0 |
1,00 |
А520 |
А530 |
240 |
7 |
4,4 |
1,00 |
А520 |
А560 |
280 |
14 |
1,2 |
4,00 |
А530 |
А550 |
300 |
70 |
3,1 |
2,00 |
А540 |
А550 |
380 |
28 |
1,0 |
2,00 |
А540 |
А570 |
400 |
36 |
3,1 |
2,00 |
А550 |
А570 |
470 |
31 |
1,0 |
2,00 |
А560 |
ТУ501 |
870 |
66 |
1,6 |
2,00 |
А570 |
ТУ501 |
790 |
78 |
2,0 |
2,00 |