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

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

⇐ Назад
123
Далее ⇒