Сетевые модели в задачах принятия решения

анализа, можно представить в виде сетевых моделей.

1.1 Построение минимального остовного
дерева в задачах принятия решения

связанных дугами (или ребрами), и описывается парой множеств (N, А), где N - множество узлов, а А - множество ребер. Например, сеть, показанная на рисунке, описывается следующим образом:

N = {1, 2, 3, 4, 5},
А = {(1, 2), (1, 3), (2, 3), (2, 5), (3, 4),
(3, 5), (4, 2), (4, 5)}.

С каждым типом сети связан определенный тип потоков (например, транспортный поток нефти в нефтепроводах или автомобильные потоки в сети городских дорог). В общем случае потоки в сети ограничены пропускной способностью ее ребер, которая может быть как конечной, так и бесконечной.
Ребро называется направленным, или ориентированным (и в этом случае ребро будем называть дугой), если в одном направлении возможен только положительный поток, а в противоположном - только нулевой.
В ориентированной сети все ребра ориентированы.

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

определенном направлении.
Остовное дерево - это дерево, содержащее все узлы сети. В сети из n узлов остовное дерево содержит n-1 ребер и возможно построить nn-2 таких деревьев.

Исходная сеть

Остовное дерево

соединение всех узлов сети с помощью путей наименьшей длины.

новых районов. На рисунке показана структура планируемой сети и расстояния (в км) между районами и телецентром – узел 1. Необходимо спланировать наиболее экономичную кабельную сеть – сеть минимальной длины.

Этап 0. и
Этап 1. Выбираем i=1, тогда ,

Итерация 1

с другими
узлами: min(1, 9, 5, 7) = 1. Тогда j*=2

или узел 2 с другими узлами:
min1(9, 5, 7) = 5, min2(3, 6, 4) = 3, min (min1, min2) = min(5, 3) = 3.
Тогда j*=5

2 или узел 5 с другими узлами:
min1(5, 7) = 5, min2(6, 4) = 4, min5(8) = 8, min (min1, min2, min5) = min(5, 4,8) = 4.
Тогда j*=4

2, 4 или узел 5 с другими узлами:
min1( 5) = 5, min2(6) = 6, min4(5,3)=3, min (min1, min2, min4 ) = min(5,6,3) = 3.
Тогда j*=6

для построения сети L = 1+3+4+3+5=16.

условиях:
а) узлы 1 и 2 связаны кабелем длиной 8 км;
б) узлы 3 и 5 связаны кабелем длиной 2 км;
в) узлы 2 и 6 связаны кабелем длиной 4 км;
г) узлы 5 и 6 связаны кабелем длиной 2 км;
д) узлы 2 и 5 не связаны.

кратчайшего пути справедливы как для
сетей, имеющих циклы, так и для сетей, не имеющих циклов. Наиболее распространены следующие алгоритмы:
1. Алгоритм Дейкстры.
2. Алгоритм Флойда.
Алгоритм Дейкстры разработан для поиска кратчайшего пути между заданным исходным узлом и любым другим узлом сети.
Алгоритм Флойда более универсален, поскольку он в итоге дает результат, который позволяет одновременно найти минимальные пути между любыми двумя узлами сети.

квадратной матрицы с n строками и n столбцами. Элемент (i, j) этой матрицы равен расстоянию dij от узла i к узлу j, которое имеет конечное значение, если существует дуга (i, j), и равен бесконечности в противном случае.
Покажем сначала основную идею метода Флойда. Пусть есть три узла i, j ,k и заданы расстояния между ними

Если выполняется неравенство dik + dkj

узлов S0. Диагональные элементы обеих матриц помечаются знаком "—", показывающим, что эти элементы в вычислениях не участвуют. Полагаем k=1.

D0 =

S0 =

строку и ведущий столбец. Двигаясь построчно, рассматриваем возможность применения треугольного оператора Флойда ко всем элементам dij матрицы Dk-1, кроме элементов ведущей строки, ведущего столбца и диагональных элементов: если для элемента ij выполняется неравенство
то делаем следующее:
1) создаем матрицу Dk путем замены в матрице Dk-1 элемента dij суммой dik + dkj;
2) создаем матрицу Sk, меняя в матрице Sk_1 элемент sij на k.
Полагаем k = k + 1 и повторяем этап k.
В итоге осуществляется n аналогичных основных этапов. При этом возможно, что на k-й итерации не будет никаких изменений матриц Dk-1 и Sk-1 .
После реализации n этапов алгоритма определение по матрицам Dn и Sn кратчайшего пути между узлами i и j выполняется по следующим правилам:
1. Расстояние между узлами i и j равно элементу dij в матрице Dn.
2. Промежуточные узлы пути от узла i к узлу j определяем по матрице Sn. Пусть sij = k, тогда имеем путь i → k → j. Если далее sik = k и skj= j, тогда считаем, что весь путь определен, так как найдены все промежуточные узлы. В противном случае повторяем описанную процедуру для путей от узла i к узлу k и от узла k к узлу j.

Условия означают:
i ≠ k – на k-м шаге исключаем k-ю строку
j ≠ k– на k-м шаге исключаем k-й столбец,
i ≠ j – не обрабатываем диагональные элементы

dik + dkj

двумя узлами. Расстояния между узлами этой сети проставлены на рисунке возле соответствующих ребер. Ребро (3, 5) ориентированно, поэтому не допускается движение от узла 5 к узлу 3. Все остальные ребра допускают движение в обе стороны.

D0 =

S0 =

Решение: согласно Этапу 0 имеем

Полагаем k=1 и переходим к Основному этапу 1.

≠ 1, i ≠ j.

i=2, j = 3: d21 + d13 = 3+10=13i=2, j = 4: d21 + d14 = 3+ ∞ < d24=5 - не выполняется
i=2, j = 5: d21 + d15 = 3+ ∞ < d25=∞ - не выполняется

i=3, j = 2: d31 + d12 = 10+3=13i=3, j = 4: d31 + d14 = 10+ ∞ < d34=6 - не выполняется
i=3, j = 5: d31 + d15 = 10+ ∞ < d35=15 - не выполняется

i=4, j = 2: d41 + d12 = ∞ +3 < d42=5 - не выполняется
i=4, j = 3: d41 + d13 = ∞ + 10 < d43=6 - не выполняется
i=4, j = 5: d41 + d15 = ∞ + ∞ < d45=4 - не выполняется

i=5, j = 2: d51 + d12 = ∞ +3 < d52 = ∞ - не выполняется
i=5, j = 3: d51 + d13 = ∞ + 10 < d53= ∞ - не выполняется
i=5, j = 4: d51 + d14 = ∞ + ∞ < d54=4 - не выполняется

d23 = 13,
s23 = 1

d32 = 13,
s32 = 1

Соответственно
создаем матрицы
D1 и S1.

Основной этап 1

2.

D1 =

Проверяем выполнение неравенства
dik + dkjдля k=2, i≠2, j ≠ 2, i ≠ j.

i=1, j = 3: d12 + d23 = 3+13= 16 < d13=10 - не выполняется
i=1, j = 4: d12 + d24 = 3+ 5 =8 < d14= ∞ - выполняется
i=1, j = 5: d12 + d25 = 3+ ∞ < d15=∞ - не выполняется

i=3, j = 1: d32 + d21 = 13+3= 16 < d31=10 - не выполняется
i=3, j = 4: d32 + d24 = 13+ 5 =18 < d34= 6 - не выполняется
i=3, j = 5: d32 + d25 = 13+ ∞ < d35=15 - не выполняется

i=4, j = 1: d42 + d21 = 5+3= 8 < d41= ∞ - выполняется
i=4, j = 3: d42 + d23 = 5+ 13 =18 < d43= 6 - не выполняется
i=4, j = 5: d42 + d25 = 5+ ∞ < d45=4 - не выполняется

i=5, j = 1: d52 + d21 = ∞ +3 < d51= ∞ - не выполняется
i=5, j = 3: d52 + d23 = ∞ + 13 < d53= ∞ - не выполняется
i=5, j = 4: d52 + d24 = ∞ + 5 < d54=4 - не выполняется

d14 = 8,
s14 = 2

d41 = 8,
s41 = 2

Соответственно
создаем матрицы
D2 и S2.

3.

Проверяем выполнение неравенства
dik + dkjдля k=3, i≠3, j ≠ 3, i ≠ j.

D2 =

i=1, j = 2: d13 + d32 = 10+13= 23 < d12=3 - не выполняется
i=1, j = 4: d13 + d34 = 10+ 6 = 16 < d14=8 - не выполняется
i=1, j = 5: d13 + d35 = 10+ 15=25 < d15 =∞ - выполняется

i=4, j = 1: d43 + d31 = 6+10= 16 < d41=8 - не выполняется
i=4, j = 2: d43 + d32 = 6+ 13 = 19 < d42=5 - не выполняется
i=4, j = 5: d43 + d35 = 6+ 15= 21 < d45 =4 - не выполняется

i=2, j = 1: d23 + d31 = 13+10= 23 < d21=3 - не выполняется
i=2, j = 4: d23 + d34 = 13+ 6 = 19 < d24=5 - не выполняется
i=2, j = 5: d23 + d35 = 13+ 15= 28 < d25 =∞ - выполняется

i=5, j = 1: d53 + d31 = ∞+10 < d51= ∞ - не выполняется
i=5, j = 2: d53 + d32 = ∞+ 13 < d52=∞ - не выполняется
i=5, j = 4: d53 + d34 = ∞+ 6 < d54 =4 - не выполняется

d15 = 25,
s15 = 3

d25 = 28,
s25 = 3

Соответственно
создаем матрицы
D3 и S3.

4.

Проверяем выполнение неравенства
dik + dkjдля k=4, i≠4, j ≠ 4, i ≠ j.

D3 =

i=1, j = 2: d14 + d42 = 8+5 = 13 < d12=3 - не выполняется
i=1, j = 3: d14 + d43 = 8+ 6 = 14 < d13=10 - не выполняется
i=1, j = 5: d14 + d45 = 8+ 4 = 12 < d15 =25 - выполняется

i=2, j = 1: d24 + d41 = 5+ 8 = 13 < d21=3 - не выполняется
i=2, j = 3: d24 + d43 = 5+ 6 = 11 < d23 =13 - выполняется
i=2, j = 5: d24 + d45 = 5+ 4 = 9 < d25 =28 - выполняется

i=3, j = 1: d34 + d41 = 6+ 8 = 14 < d31=10 - не выполняется
i=3, j = 2: d34 + d42 = 6+ 5 = 11 < d32 =13 - выполняется
i=3, j = 5: d34 + d45 = 6+ 4 = 10 < d35 =15 - выполняется

i=5, j = 1: d54 + d41 = 4+ 8 = 12 < d51 = ∞ - выполняется
i=5, j = 2: d54 + d42 = 4+ 5 = 9 < d52 = ∞ - выполняется
i=5, j = 3: d54 + d43 = 4+ 6 = 10 < d53 = ∞ - выполняется

d15 = 12,
s15 = 4

d32 = 11,
s32 = 4

Соответственно
создаем матрицы
D4 и S4.

d35 = 10,
s35 = 4

d25 = 9,
s25 = 4

d23 = 11,
s23 = 4

d51 = 12,
s51 = 4

d52 = 9,
s52 = 4

d53 = 10,
s53 = 4

5.
На этом этапе нет изменений в матрицах: D5 =D4 ,
S5 = S4. Вычисления закончены.

Для определения соответствующих маршрутов напомним, что сегмент маршрута состоит из ребра (i, j) только тогда, когда sij=j. В противном случае узлы i и j связаны, по крайней мере, через один промежуточный узел. Например, поскольку s15 = 4 и s45 = 5, сначала кратчайший маршрут между узлами 1 и 5 будет иметь вид 1 → 4 → 5. Но так как s14≠ 4, узлы 1 и 4 в определяемом кратчайшем пути не связаны одним ребром (но в исходной сети они могут быть связаны непосредственно). Далее следует определить промежуточный узел (узлы) между первым и четвертым узлами. Имеем s14 = 2 и s24 = 4, поэтому маршрут 1 → 4 заменяем 1 → 2 → 4. Поскольку s12 = 2 и s24 = 4, других промежуточных узлов нет.
Комбинируя определенные сегменты маршрута, окончательно получаем следующий кратчайший путь от узла 1 до узла 5: 1 → 2 → 4 → 5. Длина этого пути равна 12.