Методы анализа и синтеза некоторых сетей с заданной структурой

• Автор: Батурина, Л.Н.
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 1984
• Место защиты: Минск
• Количество страниц: 105 c. : ил

ГЛАВА I. ЭФФЕКТИВНО РАЗРЕШИМЫЕ КЛАССЫ ЗАДАЧ О МАКСИМАЛЬНЫХ

ПОТОКАХ В МНОГОПОЛЮСНЫХ СЕТЯХ

§ 1.1. Параметрические задачи о максимальном

потоке

§ 1.2. Максимальные потоки в однородных неориентированных сетях

§ 1.3. Максимальные потоки в полных псевдосимметрических сетях

ГЛАВА 2. СВОЙСТВА МАТРИЦЫ МАКСИМАЛЬНЫХ ПОТОКОВ В ПОЛНОЙ

НЕОРИЕНТИРОВАЖОЙ. СЕТИ ’

§ 2.1. Характеристическая пропускная способность

вершин неориентированной сети

§ 2.2. Оптимальное распределение пропускных способностей по ребрам полной сети

§ 2.3. Определение матрицы максимальных потоков полной сети при ограничениях на пропускные способности ребер
ГЛАВА 3. СИНТЕЗ СЕТЕЙ С ЗАДАННОЙ СТРУКТУРОЙ
§ 3.1. Синтез полной сети по заданной матрице
требований
§ 3.2. Синтез двухполюсной сети с заданным уровнем функциональной надежности
§ 3.3. Приближенный метод решения задачи синтеза
двухполюсной сети (ЗСДС)
§ 3.4. Вопросы практического использования ЗСДС
ПРИЛОЖЕНИЕ
ЛИТЕ РАТУРА
В настоящее время исследование задач теории сетей, моделирующих многочисленные практические проблемы построения связывающих сетей самого разнообразного назначения (сетей связи, электрических сетей, сетей вычислительных центров ит. д.) относится к одному из актуальных разделов математической кибернетики.
Основными математическими задачами, возникающими при проектировании оптимальных по различным критериям связывающих сетей являются [14, 27, 32] :
- структурный анализ проектируемой сети;
- аналитическое описание системы относительно выбранного критерия эффективности;
- синтез топологической структуры с заданными стоимостными и надежностными ограничениями;
- определение оптимальных по заданному критерию пропускных способностей линий связи.
Для анализа и решения этих задач широко используются [36, 40, 44] комбинаторные и теоретико-графовые подходы.
Особый как теоретический, так и практический интерес представляют задачи синтеза оптимальных по каким-либо критериям сетей. Изучению таких задач последние десять-пятнадцать лет уделяется большое внимание, о чем свидетельствует рост публикаций, посвященных как теоретическим (например, работы [13, 40, 43,
53, 76, 99 Л ), так и прикладным аспектам [2, 21, 35, 36, 44,
50, 87, 10?] исследования задач синтеза оптимальных сетей.

Анализ этих работ позволяет выделить два основных подхода к решению задач синтеза сетей. При первом подходе (например, в работах [7, 19, 37, 38, 58, 60, 69, 93, 94, 100, 104] ) сразу определяются структура сети и пропускные способности, обеспечивающие требуемые потоки. При этом, многие методы [71, 78, 83, 91] строят сеть древовидной структуры (возможно [91] с дополнительным ограничением на структуру дерева). Основным критерием оптимальности при первом подходе является [?,19, 37, 38, 60, 100, 107] стоимость синтезируемой сети. Отметим, что при этом подходе обычно не учитываются надежностные характеристики сети. Практические проблемы построения надежных сетей обуславливают необходимость развития методов анализа и синтеза сетей с заданным уровнем надежности. При разработке математических методов решения этих задач надежность трактуется как устойчивость функционирования сети при изменении ее параметров. Второй подход к исследованию задач синтеза сетей состоит [8,36,82] в решении задачи в два этапа: сначала находится структура, отвечающая заданным надежностным и стоимостным характеристикам, и затем определяются оптимальные по выбранному критерию пропускные способности. На первом этапе широко используются строгие математические методы (см., например, [б, 40, 53, 55, 56, 74] ). Задачи нахождения пропускных способностей в основном [ТО, 29, 32, 35, Зб] решаются на содержательном уровне. Шесте с тем разработка математически обоснованных методов выбора оптимальных пропускных способностей сетей с заданной структурой представляет [77] значительный как теоретический, так и практический интерес. Построение таких методов во многом обосновывается результатами исследования параметрических потоковых задач, связанных с понятием устойчивости сети.
Также как и в других разделах дискретной математики [23, 24] , в теории сетей исследование устойчивости является одной из важ-

из списка Я. и заносим в список
то полагаем
3. Определение матрицы V
3.1. Полагаем
Щ = ьЫк [ с(XI) , С(Х^)} для всех ). Если Я * =0 ,
1^1 ~ ^ и задача решена. В противном случае переходим к следующей операции.
3.2. Для каждого & находим значение ( С*-) ) по правилу:
Если 1ФЬ) , то для величины Щ справедлива формула (2.10). Если /у , то в случае Я и X (х) ^С(х^) для величины справедлива формула (1.5)
Х(Х^) С(Хр , то определяем для вершины Х-с значение Х'(х) с помощью МВХВ и полагаем
Щ = Шп. [ Х‘(Х) , С (Х-) )
Л X"
В случае у с /ь вычисляем с помощью МВХВ значения X (X)
и Х’(х^) . Находим значение по формуле (2.11).
Если просмотрены все элементы Ь ^ Я* , то полагаем 1^1 Для £, Рассмотрим пример нахождения матрицы V полной сети £*,
функция пропускных способностей которой удовлетворяет условиям
(2.1) и (2.2), с помощью МОУ
Пусть задана полная неориентированная сеть £ с П= 9 . Предположим, что вершины сети Сг пронумерованы по невозрастанию величин С(Х) . Матрица С пропускных способностей ребер сети (г* имеет вид