8.4 Оптимизация топологической структуры по критериям стоимости и надежности

В ряде случаев представляет интерес более простая задача топологической оптимизации в постановке которой не учитывается требование к информационным потокам, проходящим по сети. Такая задача решается на предпроектной стадии создания сети в условиях отсутствия подробной информации о сетевых протоколах, матрице интенсивности входных потоков и т.д.

Пусть сеть описывается графом где — число вершин и — число ребер графа

Рассмотрим остовной подграф графа в котором Обозначим: диаметр графа — диаметры графа G — , полученного из графа G удалением произвольного ребра, и графа G — v полученного из графа G удалением произвольной вершины. Всем ребрам графа G приписаны неотрицательные веса, равные стоимости аренды каналов между парой узлов коммутации. Под стоимостью графа G понимается сумма весов, входящих в G ребер (обозначается ). Обозначим через X — множество всех остовных подграфов графа

Тогда постановка задачи синтеза топологической структуры СПД имеет следующий вид:

Найти такой подграф G, что:

при следующих условиях:

Условие (8.5) по определению диаметра графа эквивалентно ограничению на длину кратчайшего пути между каждой парой вершин. Условия (8.6) и (8.7) ограничивают длины кратчайших путей между каждой парой вершин при удалении ребра или вершины в графе G.

Задача (8.4)-(8.7) является сложной -полной задачей дискретного программирования. Прежде чем описать алгоритм решения задачи (8.4)-(8.7), остановимся на способе получения нижней оценки стоимости сети. С одной стороны, она позволяет оценить предварительные расходы на создание сети (что очень важно на предпроектной стадии создания сети), с другой стороны, нижняя оценка стоимости будет использована как важный этап в комбинаторном алгоритме решения задачи.

Обозначим М число ребер сети и определим нижнюю оценку стоимости сети с М ребрами. Для определения нижней оценки используется следующий прием: условия (8.5)-(8.7) не учитываются, а условие двусвязности графа заменяется на необходимое условие

Кроме того, вводится новое условие, состоящие в том, что сеть содержит М ребер:

Таким образом необходимо решить следующую задачу:

Найти

если

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

Шаг 1. Сортировка строк матрицы Строки матрицы сортируются в порядке возрастания стоимостей. Таким образом, для каждого узла i в строке матрицы содержатся стоимости соединения узла со всеми остальными узлами в порядке возрастания (предполагается ).

Шаг 2. Для каждой строки матрицы выбрать первые два элемента, то есть положить

Шаг 3. Остальные элементов матрицы расположить в порядке возрастания их стоимостей, то есть из оставшихся ее элементов сформировать вектор при

Шаг 4. Выбрать первые элементов вектора С, то есть положить

Шаг 5. Вычислить нижнюю оценку стоимости сети с М ребрами: (оценка делится пополам, так как полученное алгоритмом решение содержит ребер, а в решении должно быть М ребер).

Шаг 6. Конец работы алгоритма.

Легко видеть, что трудоемкость алгоритма определяется шагом 1 (или 3) и равна Число ребер М обычно неизвестно. Поэтому для получения нижней оценки стоимости сети необходимо определить границу числа ребер, при которой выполняются условия (8.5)-(8.7).

Таким образом, для просмотра множества допустимых решений можно предложить алгоритм, который заключается в следующем. Вначале определяется нижняя граница числа ребер Для заданного числа узлов N и ребер исследуются все графы, которые являются двусвязными и удовлетворяют, ограничениям (8.5)-(8.7). Среди этих графов выбирается граф сумма весов которого минимальна. Если в процессе анализа установлено, что на некотором графе достигнуто значение, равное нижней оценки стоимости для Мребер, то поиск оптимального решения прекращается. Если все графы с Мребрами проанализированы, то число ребер М увеличивается на единицу; определяется нижняя оценка стоимости сети, и если она не лучше оптимального решения с меньшим числом ребер, то работа алгоритма завершается. В противном случае исследуются все графы с ребрами и т.д.

Машинные эксперименты синтеза топологической структуры сетей с числом узлов коммутации, не превосходящим десяти, показали одно важное свойство предлагаемого комбинаторного алгоритма: для отыскания оптимального решения требуется не более 5% от общего числа итераций.

Остальные итерации тратятся на доказательство оптимальности решения. С учетом указанного свойства на базе комбинаторного подхода разработаны эффективные эвристические алгоритмы для синтеза топологии сетей средней и большой размерности.