Инициализация алгоритма добавления начинается со структуры сети, в которой все абоненты соединяются выделенными каналами (без использования концентраторов). Такая структура показана на рисунке 5.
|
|
|
|
Рис.5
В этом случае общая стоимость СПД составит
.
Далее последовательно предусматриваем установку концентраторов в возможных пунктах установки Wj (j = 1-3) и для каждого абонента вычисляем разность
Cij(нов)-Cij(пред.), i=1-7, j=0-3. (1)
где Cij(нов) — стоимость подключения абонента Ai в новой структуре сети;
Cij(пред.) — стоимость подключения абонента Аj в предыдущей структуре сети.
Если для некоторого абонента Ai разность (1-1) оказывается отрицательной, это означает, что вариант подключения для данного абонента является более дешевым и потенциально может быть достигнуто снижение общей стоимости сети Z (при условии, что стоимость установки концентратора не превысит общего снижения стоимости за счет отрицательных значений разностей (1).
Итерация 1.
Устанавливаем концентратор в пункте W1 и проверяем возможность снижения общей стоимости сети путем подключения к нему всех абонентов сети. Для этого вычисляем разности
Ci1-Ci0, i = 1,7.
Получаем
C11 - C10 = 2 – 9 = - 7,
C21 – C20 = 0 – 7 = - 7,
C31 – C30 = 4 – 6 = - 2,
C41 – C40 = 9 – 9 = 0,
C51 – C50 = 7 – 3 = 4,
C61 – C60 = 13 –11 = 2,
C71 – C70 = 10 – 8 = 2.
Отсюда видно, что подключение к концентратору в пункте W1 абонентов A1, А2, и А3 может привести к снижению общей стоимости сети Z.
Структура сети в этом случае показана на рис. 6а.
Рис.6
|
Общая стоимость сети
.
Или
.
Далее устанавливаем концентратор в пункте W2 и проверяем возможность снижения общей стоимости сети путем подключения к нему всех абонентов сети. Для этого вычисляем разности
Ci2-Ci0, i = 1,7.
Получаем
C12 - C10 = 7 – 9 = -2,
C22 – C20 = 6 – 7 = -1,
C32 – C30 = 2 – 6 = -4,
C42 – C40 = 6 – 9 = -3,
C52 – C50 = 0 – 3 = -3,
C62 – C60 = 8 –11 = -3,
C72 – C70 = 5 – 8 = -3.
Отсюда видно, что подключение к концентратору в пункте W2 всех абонентов может привести к снижению общей величины Z.
Однако с учетом ограничения по числу подключаемых абонентов (d = 6) подключение их производится с учетом максимальных (по модулю) отрицательных значений вычисленных разностей. Поэтому абонент А2 в этой структуре подключается непосредственно к W0.
Структура сети в этом случае показана на рис. 6б.
Общая стоимость сети будет равна
Z = 6 + 7 + 7 + 2 + 6 + 0 + 8 + 5 = 41, или
Z12 = 53-(2+ 4 + 3 + 3 + 3 + 3-6) = 41.
Далее устанавливаем концентратор в пункте W3 и проверяем возможность снижения общей стоимости сети путем подключения к нему всех абонентов сети. Для этого вычисляем разности
Ci3-Ci0, i = 1,7.
Получаем
C13 - C10 = 10 – 9 = 1,
C23 – C20 = 11 – 7 = 4,
C33 – C30 = 7 – 6 = 1,
C43 – C40 = 2 – 9 = -7,
C53 – C50 = 6 – 3 = 3,
C63 – C60 = 2 –11 = -9,
C73 – C70 = 0 – 8 = -8.
Отсюда видно, что подключение к концентратору в пункте W3 абонентов А4, А6 и А7 может привести к снижению общей величины Z.
Структура сети в этом случае показана на рис. 6в.
Общая стоимость сети будет равна
Z=10 + 9 + 7 + 6 + 3 + 2 + 2 + 0 = 39, или
Z = 53 - (7 + 9 + 8 - 10) = 39.
После первой итерации получена оптимальная по стоимости структура сети с одним концентратором, установленным в пункте W3, (см. рис. 6в).
Итерация 2.
Для структуры сети, имеющей минимальную стоимость после первой итерации (концентратор установлен в пункте W3 см. рис. 6в), определим возможность снижения стоимости сети за счет установки других концентраторов.
Размещаем концентратор в пункте W1 и вычисляем разности стоимости подключения абонентов к этому концентратору и стоимости их подключения в предыдущей структуре.
Получаем
C11 - C10 = 2 – 9 = - 7,
C21 – C20 = 0 – 7 = - 7,
C31 – C30 = 4 – 6 = - 2,
C41 – C43 = 9 –6 = 3,
C51 – C50 = 7 – 3 = 4,
C61 – C63 = 13 –2 = 11,
C71 – C73 = 10 – 0 = 10.
Отсюда видно, что к снижению стоимости сети может привести подключение абонентов А1, А2 и А3 к концентратору в пункте W1. Абоненты
A4, A6 и A7 целесообразно оставить подключенными к концентратору W3, а абонента А5 подключить по выделенному каналу к серверу АСУ ЛР.
Структура сети показана на рис. 7а.
Общая стоимость сети
или
Z = 39 -(7 + 7 + 2 - 9) = 32.
Таким образом, установка концентратора в пункте W1 приводит к снижению стоимости сети.
Далее проверим, приведет ли к снижению стоимости сети с концентраторами в пунктах W1 и W3 установка концентратора в пункте W2.
Вычислим соответствующие разности:
C12 - C11 = 7 – 2 = 5,
C22 – C21 = 6 – 0 = 6,
C32 – C31 = 2 – 4 = - 2,
C42 – C43 = 6 – 2 = 4,
C52 – C50 = 0 – 3 = -3,
C62 – C63 = 8 – 2 = 6,
C72 – C73 = 5 – 0 = 5,
Отсюда видно, что к снижению стоимости может привести подключение абонентов А3 и А5 к концентратору в пункте W2.
Структура сети показана на рис. 7б.
|
Рис.7
Общая стоимость такой сети
Z = C1 + C2 + C3 + C11 + C21 + C32 + C43 + C52 + C63 + C73 =
= 9 + 6 + 10 + 2 + 0 + 2 + 2 + 0 + 2 + 0 = 33,
или
Z = 32 - (2 + 3 - 6) = 33.
Следовательно, установка третьего концентратора в пункте W2 не приводит к уменьшению стоимости сети. Оптимальная по стоимости структура сети, полученная с помощью алгоритма добавления, приведена на рис. а.
На рис.8 показано последовательное изменение стоимости сети в процессе применения алгоритма добавления.
Рис.8 Изменение стоимости сети за счет установки концентраторов.
