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

Инициализация алгоритма добавления начинается со структуры сети, в которой все абоненты соединяются выделенными каналами (без использования концентраторов). Такая структура показана на рисунке 5.

Рис.5

В этом случае общая стоимость СПД составит

.

Далее последовательно предусматриваем установку концентраторов в возможных пунктах установки W_j (j = 1-3 ) и для каждого абонента вычисляем разность

C_ij(нов)-C_ij(пред.), i=1-7, j=0-3. (1)

где C_ij(нов) — стоимость подключения абонента A_i в новой структуре сети;

C_ij(пред.) — стоимость подключения абонента А_j в предыдущей структуре сети.

Если для некоторого абонента A_i разность (1-1) оказывается отрицательной, это означает, что вариант подключения для данного абонента является более дешевым и потенциально может быть достигнуто снижение общей стоимости сети Z (при условии, что стоимость установки концентратора не превысит общего снижения стоимости за счет отрицательных значений разностей (1).

Итерация 1.

Устанавливаем концентратор в пункте W₁ и проверяем возможность снижения общей стоимости сети путем подключения к нему всех абонентов сети. Для этого вычисляем разности

C_i1-C_i0, i = 1,7.

Получаем

C₁₁ - C₁₀ = 2 – 9 = - 7,

C₂₁ – C₂₀ = 0 – 7 = - 7,

C₃₁ – C₃₀ = 4 – 6 = - 2,

C₄₁ – C₄₀ = 9 – 9 = 0,

C₅₁ – C₅₀ = 7 – 3 = 4,

C₆₁ – C₆₀ = 13 –11 = 2,

C₇₁ – C₇₀ = 10 – 8 = 2.

Отсюда видно, что подключение к концентратору в пункте W₁ абонентов A₁, А₂, и А₃ может привести к снижению общей стоимости сети Z.

Структура сети в этом случае показана на рис. 6а.

Рис.6

Общая стоимость сети

.

Или

.

Далее устанавливаем концентратор в пункте W₂ и проверяем возможность снижения общей стоимости сети путем подключения к нему всех абонентов сети. Для этого вычисляем разности

C_i2-C_i0, i = 1,7.

Получаем

C₁₂ - C₁₀ = 7 – 9 = -2,

C₂₂ – C₂₀ = 6 – 7 = -1,

C₃₂ – C₃₀ = 2 – 6 = -4,

C₄₂ – C₄₀ = 6 – 9 = -3,

C₅₂ – C₅₀ = 0 – 3 = -3,

C₆₂ – C₆₀ = 8 –11 = -3,

C₇₂ – C₇₀ = 5 – 8 = -3.

Отсюда видно, что подключение к концентратору в пункте W₂ всех абонентов может привести к снижению общей величины Z.

Однако с учетом ограничения по числу подключаемых абонентов (d = 6) подключение их производится с учетом максимальных (по модулю) отрицательных значений вычисленных разностей. Поэтому абонент А₂ в этой структуре подключается непосредственно к W₀.

Структура сети в этом случае показана на рис. 6б.

Общая стоимость сети будет равна

Z = 6 + 7 + 7 + 2 + 6 + 0 + 8 + 5 = 41, или

Z₁₂ = 53-(2+ 4 + 3 + 3 + 3 + 3-6) = 41.

Далее устанавливаем концентратор в пункте W₃ и проверяем возможность снижения общей стоимости сети путем подключения к нему всех абонентов сети. Для этого вычисляем разности

C_i3-C_i0, i = 1,7.

Получаем

C₁₃ - C₁₀ = 10 – 9 = 1,

C₂₃ – C₂₀ = 11 – 7 = 4,

C₃₃ – C₃₀ = 7 – 6 = 1,

C₄₃ – C₄₀ = 2 – 9 = -7,

C₅₃ – C₅₀ = 6 – 3 = 3,

C₆₃ – C₆₀ = 2 –11 = -9,

C₇₃ – C₇₀ = 0 – 8 = -8.

Отсюда видно, что подключение к концентратору в пункте W₃ абонентов А₄, А₆ и А₇ может привести к снижению общей величины Z.

Структура сети в этом случае показана на рис. 6в.

Общая стоимость сети будет равна

Z=10 + 9 + 7 + 6 + 3 + 2 + 2 + 0 = 39, или

Z = 53 - (7 + 9 + 8 - 10) = 39.

После первой итерации получена оптимальная по стоимости структура сети с одним концентратором, установленным в пункте W₃ , (см. рис. 6в).

Итерация 2.

Для структуры сети, имеющей минимальную стоимость после первой итерации (концентратор установлен в пункте W₃ см. рис. 6в), определим возможность снижения стоимости сети за счет установки других концентраторов.

Размещаем концентратор в пункте W₁ и вычисляем разности стоимости подключения абонентов к этому концентратору и стоимости их подключения в предыдущей структуре.

Получаем

C₁₁ - C₁₀ = 2 – 9 = - 7,

C₂₁ – C₂₀ = 0 – 7 = - 7,

C₃₁ – C₃₀ = 4 – 6 = - 2,

C₄₁ – C₄₃ = 9 –6 = 3,

C₅₁ – C₅₀ = 7 – 3 = 4,

C₆₁ – C₆₃ = 13 –2 = 11,

C₇₁ – C₇₃ = 10 – 0 = 10.

Отсюда видно, что к снижению стоимости сети может привести подключение абонентов А₁, А₂ и А₃ к концентратору в пункте W₁. Абоненты

A₄, A₆ и A₇ целесообразно оставить подключенными к концентратору W₃, а абонента А₅ подключить по выделенному каналу к серверу АСУ ЛР.

Структура сети показана на рис. 7а.

Общая стоимость сети

или

Z = 39 -(7 + 7 + 2 - 9) = 32.

Таким образом, установка концентратора в пункте W₁ приводит к снижению стоимости сети.

Далее проверим, приведет ли к снижению стоимости сети с концентраторами в пунктах W₁ и W₃ установка концентратора в пункте W₂.

Вычислим соответствующие разности:

C₁₂ - C₁₁ = 7 – 2 = 5,

C₂₂ – C₂₁ = 6 – 0 = 6,

C₃₂ – C₃₁ = 2 – 4 = - 2,

C₄₂ – C₄₃ = 6 – 2 = 4,

C₅₂ – C₅₀ = 0 – 3 = -3,

C₆₂ – C₆₃ = 8 – 2 = 6,

C₇₂ – C₇₃ = 5 – 0 = 5,

Отсюда видно, что к снижению стоимости может привести подключение абонентов А₃ и А₅ к концентратору в пункте W₂.

Структура сети показана на рис. 7б.

Рис.7

Общая стоимость такой сети

Z = C₁ + C₂ + C₃ + C₁₁ + C₂₁ + C₃₂ + C₄₃ + C₅₂ + C₆₃ + C₇₃ =

= 9 + 6 + 10 + 2 + 0 + 2 + 2 + 0 + 2 + 0 = 33,

или

Z = 32 - (2 + 3 - 6) = 33.

Следовательно, установка третьего концентратора в пункте W₂ не приводит к уменьшению стоимости сети. Оптимальная по стоимости структура сети, полученная с помощью алгоритма добавления, приведена на рис. а.

На рис.8 показано последовательное изменение стоимости сети в процессе применения алгоритма добавления.

Рис.8 Изменение стоимости сети за счет установки концентраторов.