О ГЛАВЛЕНИЕ
Стр.
ВВЕДЕНИЕ........................................................ 3
ГЛАВА I. ЭФФЕКТИВНО РАЗРЕШИМЫЕ КЛАССЫ ЗАДАЧ О МАКСИМАЛЬНЫХ
ПОТОКАХ В МНОГОПОЛЮСНЫХ СЕТЯХ......................... II
§ 1.1. Параметрические задачи о максимальном
потоке ........................................ II
§ 1.2. Максимальные потоки в однородных неориентированных сетях ....................................... 17
§ 1.3. Максимальные потоки в полных псевдосиммет-
рических сетях ................................ 25
ГЛАВА 2. СВОЙСТВА МАТРИЦЫ МАКСИМАЛЬНЫХ ПОТОКОВ В ПОЛНОЙ
НЕОРИЕНТИРОВАННОЙ • СЕТИ '............................ 30
Г:,--
§ 2.1. Характеристическая пропускная способность
вершин неориентированной сети ................. 30
§ 2.2. Оптимальное распределение пропускных способностей по ребрам полной сети....................... 41
§ 2.3. Определение матрицы максимальных потоков полной сети при ограничениях на пропускные способности ребер ................................ 49
ГЛАВА 3. СИНТЕЗ СЕТЕЙ С ЗАДАННОЙ СТРУКТУРОЙ.............. 55
§ 3.1. Синтез полной сети по заданной матрице
требований .................................... 55
§ 3.2. Синтез двухполюсной сети с заданным уровнем функциональной надежности ........................ 71
§ 3.3. Приближенный метод решения задачи синтеза
двухполюсной сети (ЗСДС) ...................... 81
§ 3.4. Вопросы практического использования ЗСДС ... 87
ПРИЛОЖЕНИЕ..................................................... 92
ЛИТЕ РАТУРА.................................................... 93
ВВЕДЕНИЕ
В настоящее время исследование задач теории сетей, моделирующих многочисленные практические проблемы построения связывающих сетей самого разнообразного назначения (сетей связи, электрических сетей, сетей вычислительных центров ИТ. д.) относится к одному из актуальных разделов математической кибернетики.
Основными математическими задачами, возникающими при проектировании оптимальных по различным критериям связывающих сетей являются [14, 27, 32] :
- структурный анализ проектируемой сети;
- аналитическое описание системы относительно выбранного критерия эффективности;
- синтез топологической структуры с заданными стоимостными и надежностными ограничениями;
- определение оптимальных по заданному критерию пропускных способностей линий связи.
Для анализа и решения этих задач широко используются [36, 40, 44} комбинаторные и теоретико-графовые подходы.
Особый как теоретический, так и практический интерес представляют задачи синтеза оптимальных по каким-либо критериям сетей. Изучению таких задач последние десять-пятнадцать лет уделяется большое внимание, о чем свидетельствует рост публикаций, посвященных как теоретическим (например, работы [13, 40, 43,
53, 76, 993 )* так и прикладным аспектам [2, 21, 35, 36, 44,
50, 87, 107] исследования задач синтеза оптимальных сетей.
- 4 -
Анализ этих работ позволяет выделить два основных подхода к решению задач синтеза сетей. При первом подходе (например, в рабо-тах [7, 19, 37, 38, 58, 60, 69, 93, 94, 100, 104] ) сразу определяются структура сети и пропускные способности, обеспечивающие требуемые потоки. При этом, многие методы [71, 78, 83, 91] строят сеть древовидной структуры (возможно [91] с дополнительным ограничением на структуру дерева). Основным критерием оптимальности при первом подходе является [7,19, 37, 38, 60, 100, 107] стоимость синтезируемой сети. Отметим, что при этом подходе обычно не учитываются надежностные характеристики сети. Практические проблемы построения надежных сетей обуславливают необходимость развития методов анализа и синтеза сетей с заданным уровнем надежности. При разработке математических методов решения этих задач надежность трактуется как устойчивость функционирования сети при изменении ее параметров. Второй подход к исследованию задач синтеза сетей состоит [8,36,82] в решении задачи в два этапа: сначала находится структура, отвечающая заданным надежностным и стоимостным характеристикам, и затем определяются оптимальные по выбранному критерию пропускные способности. На первом этапе широко используются строгие математические методы (см., например, [б, 40, 53, 55, 56, 74] ). Задачи нахождения пропускных способностей в основном [10, 29, 32, 35, Зб] решаются на содержательном уровне. Вместе с тем разработка математически обоснованных методов выбора оптимальных пропускных способностей сетей с заданной структурой представляет [77] значительный как теоретический, так и практический интерес. Построение таких методов во многом обосновывается результатами исследования параметрических потоковых задач, связанных с понятием устойчивости сети. Также как и в других разделах дискретной математики [23, 24] , в теории сетей исследование устойчивости является одной из важ-
- 5 -
нейших задач анализа. В работе [24] подчеркивается, что в настоящее время существует достаточно много различных понятий устойчивости, выбор каждого из которых обуславливается характером решаемой задачи. Для решения задач выбора оптимальных пропускных способностей представляют интерес параметрические потоковые задачи, заключающиеся в изучении поведения величины максимального потока как функции пропускных способностей дуг (или ребер), а также задачи нахождения множеств дуг (или вершин) наибольшим образом "влияющих" на величину потока в сети. Отметим, что в основном исследование перечисленных задач проводилось [5, II, 57, 61, 92, 95, 98] для двухполюсных сетей (то есть сетей с вьщеленными источником и стоком). Для многополюсных сетей параметрические задачи о максимальном потоке еще сравнительно мало исследованы, хотя именно такие сети чаще всего являются моделями реальных связывающих сетей.
Диссертационная работа посвящена исследованию свойств матрицы максимальных потоков многополюсной сети в зависимости от характеристик функции пропускных способностей и решению на этой основе задач анализа и синтеза многополюсных сетей с заданной структурой, а также исследованию задачи синтеза двухполюсной сети с заданным уровнем надежности.
Работа состоит из введения, трех глав, приложения и списка цитированной литературы.
В первой главе для неориентированных однородных (в частности, полных) сетей и полных псевдосимметрических сетей определены свойства функции пропускных способностей, при которой матрица максимальных потоков находится с помощью простых вычислительных операций.
В § 1.1 проведен обзор постановок параметрических задач о максимальном потоке, в которых исследуется зависимость величины
- 6 -
максимального потока от изменения пропускных способностей дуг (или ребер) сети.
В § 1.2 для полных неориентированных, а в § 1.3 для полных псевдосимметрических сетей определены замкнутые интервалы значений пропускных способностей, при которых любая функция пропускных способностей на ребрах (или дугах) приводит к матрице V = ||^Ы1цхп максимальных потоков, которая является так называемой матрицей максимальной пропускной способности (ММПС), то есть матрицей, в которой для любого ее значения 1/ц ( )
максимального потока из Х^ в справедливо равенство
Щ ~ тс/г [с(х1) , С(х>)] , где С (Х1) - пропускная способность вершины Х-с , равная сум-марной пропускной способности инцидентных ей ребер (или суммарной пропускной способности входящих в нее дуг, если сеть псевдо-симметрическая). Псевдосимметрической называется ориентированная сеть, для любой вершины которой сумма пропускных способностей входящих в нее дуг равна сумме пропускных способностей выходящих из нее дуг. В результате исследования выделены классы эффективно разрешимых задач о максимальных потоках в многополюсных сетях.
В главе 2 исследуются свойства матрицы максимальных потоков в полных неориентированных сетях в зависимости от характеристик функции пропускных способностей, принимающей значения из заданного замкнутого интервала. Целью исследования является определение характеристик функции пропускных способностей, при которых матрица V" является ММПС.
В § 2.1 вводится понятие характеристической пропускной способности Х(хй вершины, значение которой позволяет оценить величины возможных максимальных потоков из заданной вершины в любую другую вершину сети. Для значения ЗС(х£) показана
- 7 -
справедливость формулы
Х(*С)- У аР + У сиг + У ,
Уы г^хуилу г^лУ
где Л-1 - [ Ъ / •£- (в. + ()С *, Ъ^С) 2=/,... ,/г-^ - специаль-
ные множества, связанные с каждой вершиной Хс , и X* , ЖУ , XУ - подмножества множества У^1 , построенные по определен-ным правилам. Значение £ находится по формуле
* - * - т\
где С** = тях _[су] , С* = £ Су] ?
(хс,*У)€А (хс.хр^Х
р * 2
И /2. - число вершин сети. Величины С 1% ДЛЯ 2 €Г ^
определяются с помощью разработанного алгоритма вычисления характеристической пропускной способности (МВХВ) с оценкой трудоемкости 0(пъ). Показано, что величина 2^; максимального потока из в ^ зависит от типа отношений (в теоретико-множественном смысле) между множествами и Ж} . В частности, дока-
зано, что в полной неориентированной сети при Д - £ *■ ]%[ для любого значения 1^и матрицы V справедливо равенство
_ Г пЫп [Х(хс) , ЛЦ)} при С 4- Х] ,
V ” I тсп [Х'(х£) ■) х'(х-) ] при I <=
Для нахождения значений Х'/Х^) >,Х(*У) также используется МВХВ.
В § 2.2 определяются типы отношений между множествами Л[ , при которых соответствующая матрица V" является ММПС. В частности, доказано, что если для любой вершины сети с заданным ограничением на функцию пропускных способностей справедливо условие
I /,, \LjHV и \ * г,
^ символ ]а.[~ наименьшее целое, не меньшее а- .
- 8 -
то матрица V является ММПС. Здесь I»; - подмножества множеств щ , построенные с помощью специальной процедуры и
— £ I /у Ф ? с м]. На основе проведенных в
главе исследований построен (§ 2.3) метод определения матрицы V (М01/-) полной сети с заданным ограничением на пропускные способности. Эффективность метода обеспечивается тем, что для многих
классов задач все значения матрицы V находятся путем построения множеств и у и анализа отношений между ними, что требует не более 0(п*~) действий. При необходимости дополнительного нахождения значений X (х£\ и (или) Х'(х^) общее число дейст-
вий МОУ не превосходит 0(п *).
В главе 3 исследуются задачи синтеза оптимальных сетей с заданной структурой при условии минимизации суммарной пропускной способности ребер (или дуг) сети, а также при дополнительном требовании обеспечения заданного уровня надежности.
В § 3.I исследуется задача синтеза полной неориентированной сети (ЗСПС) в следующей постановке. Пусть заданы положительные целые значения С* и С** и симметричная матрица V Для полной неориентированной сети требуется найти целочисленную функцию пропускных способностей, значения которой на ребрах удовлетворяют условию
с* * Су ± с** V (х1ё X,) ,
и при которой матрица V* является ММПС построенной сети.
Отметим, что требование нахождения функции пропускных способностей, при которой матрица V является ММПС, равносильно требованию минимизации суммы пропускных способностей ребер. Задачи синтеза по симметричной матрице требований при условии минимизации суммарной пропускной способности ребер сети рассмотрены в работах [78, 88, 104] . Основные отличия ЗСПС от указанных задач состоят в том, что, во-первых, в ЗСПС определено требование на структуру синтезируемой сети, во-вторых, в отличие
- Київ+380960830922