Реализация алгоритма добавления

Инициализация алгоритма добавления начинается со структуры сети, в которой все абоненты соединяются выделенными каналами (без использования концентраторов). Такая структура показана на рисунке 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 Изменение стоимости сети за счет установки концентраторов.

Наши рекомендации