Линейные целочисленные модели распределения потоков в задачах проектирования и анализа многопродуктовых коммуникационных сетей

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

Ausführliche Beschreibung

Gespeichert in:

Bibliographische Detailangaben
Datum:	2013
Hauptverfasser:	Васянин, В.А., Трофимчук, А.Н.
Format:	Artikel
Sprache:	Russian
Veröffentlicht:	Інститут телекомунікацій і глобального інформаційного простору НАН України 2013
Schriftenreihe:	Екологічна безпека та природокористування
Schlagworte:	Науково-технологічна безпека та інтелектуальні ресурси
Online Zugang:	https://nasplib.isofts.kiev.ua/handle/123456789/57585
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Zitieren:	Линейные целочисленные модели распределения потоков в задачах проектирования и анализа многопродуктовых коммуникационных сетей / В.А. Васянин, А.Н. Трофимчук // Екологічна безпека та природокористування: Зб. наук. пр. — К., 2013. — Вип. 12. — С. 147-165. — Бібліогр.: 71 назв. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	nasplib_isofts_kiev_ua-123456789-57585
record_format	dspace
spelling	nasplib_isofts_kiev_ua-123456789-575852025-02-09T09:46:17Z Линейные целочисленные модели распределения потоков в задачах проектирования и анализа многопродуктовых коммуникационных сетей Лінійні цілочисельні моделі розподілу потоків у задачах проектування й аналізу багатопродуктових комунікаційних мереж Linear integer models of distribution of flows in problems of designing and analysis of multicommodity communication networks Васянин, В.А. Трофимчук, А.Н. Науково-технологічна безпека та інтелектуальні ресурси В статье предлагаются модели распределения дискретных многопродуктовых потоков, представленные в виде задач линейного программирования. Проведен краткий обзор методов и алгоритмов, используемых в настоящее время для решения задач подобного класса. Показано, что практическое использование методов декомпозиции Данцига-Вулфа и релаксации ограничений Розена для решения сформулированных задач позволило установить границы их разумного применения для реальных сетей - от 30 до 100 узлов, и они могут быть использованы при проектировании распределения потоков на нижних уровнях иерархической сетевой структуры. Отмечается, что для решения задач распределения потоков в децентрализованных распределенных сетях, содержащих более 200 узлов и 12000 дуг, целесообразно использовать сетевые постановки задач и приближенные методы решения, существенно опирающиеся на специфику структуры данных задач и содержательные эвристические соображения. У статті пропонуються моделі розподілу дискретних багатопродуктових потоків, представлені у виді задач лінійного програмування. Проведено короткий огляд методів і алгоритмів, використовуваних у даний час для рішення задач подібного класу. Показано, що практичне використання методів декомпозиції Данцига-Вулфа і релаксації обмежень Розена для рішення сформульованих задач дозволило установити границі їхнього розумного застосування для реальних мереж - від 30 до 100 вузлів, і вони можуть бути використані при проектуванні розподілу потоків на нижніх рівнях ієрархічної мережної структури. Відзначається, що для рішення задач розподілу потоків у децентралізованих розподілених мережах, що містять більш 200 вузлів і 12000 дуг, доцільно використовувати мережні постановки задач і наближені методи рішення, що істотно спираються на специфіку структури даних задач і змістовні евристичні розуміння. The models of distribution of the discrete multicommodity flows, submitted as problems of linear programming are offered in this article. The brief review of methods and the algorithms now in use for the decision of problems of a similar class is conducted. Practical use of methods of decomposition of Dantzig - Wolfe and a relaxation of restrictions Rosen for the decision of the formulated problems is shown, that, has allowed to establish borders of their reasonable application for real networks - from 30 up to 100 vertices, and they can be used at designing distribution of flows at the bottom levels of hierarchical network structure. It is marked, that for the decision of problems of distribution of flows in the noncentralized distributed networks, containing more of 200 vertices and 12000 arches it is expedient to use network productions of problems and the approached methods of the decision, essentially basing on specificity of structure of the given problems and substantial heuristic reasons. 2013 Article Линейные целочисленные модели распределения потоков в задачах проектирования и анализа многопродуктовых коммуникационных сетей / В.А. Васянин, А.Н. Трофимчук // Екологічна безпека та природокористування: Зб. наук. пр. — К., 2013. — Вип. 12. — С. 147-165. — Бібліогр.: 71 назв. — рос. XXXX-0062 https://nasplib.isofts.kiev.ua/handle/123456789/57585 504.1: 519.05 ru Екологічна безпека та природокористування application/pdf Інститут телекомунікацій і глобального інформаційного простору НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Russian
topic	Науково-технологічна безпека та інтелектуальні ресурси Науково-технологічна безпека та інтелектуальні ресурси
spellingShingle	Науково-технологічна безпека та інтелектуальні ресурси Науково-технологічна безпека та інтелектуальні ресурси Васянин, В.А. Трофимчук, А.Н. Линейные целочисленные модели распределения потоков в задачах проектирования и анализа многопродуктовых коммуникационных сетей Екологічна безпека та природокористування
description	В статье предлагаются модели распределения дискретных многопродуктовых потоков, представленные в виде задач линейного программирования. Проведен краткий обзор методов и алгоритмов, используемых в настоящее время для решения задач подобного класса. Показано, что практическое использование методов декомпозиции Данцига-Вулфа и релаксации ограничений Розена для решения сформулированных задач позволило установить границы их разумного применения для реальных сетей - от 30 до 100 узлов, и они могут быть использованы при проектировании распределения потоков на нижних уровнях иерархической сетевой структуры. Отмечается, что для решения задач распределения потоков в децентрализованных распределенных сетях, содержащих более 200 узлов и 12000 дуг, целесообразно использовать сетевые постановки задач и приближенные методы решения, существенно опирающиеся на специфику структуры данных задач и содержательные эвристические соображения.
format	Article
author	Васянин, В.А. Трофимчук, А.Н.
author_facet	Васянин, В.А. Трофимчук, А.Н.
author_sort	Васянин, В.А.
title	Линейные целочисленные модели распределения потоков в задачах проектирования и анализа многопродуктовых коммуникационных сетей
title_short	Линейные целочисленные модели распределения потоков в задачах проектирования и анализа многопродуктовых коммуникационных сетей
title_full	Линейные целочисленные модели распределения потоков в задачах проектирования и анализа многопродуктовых коммуникационных сетей
title_fullStr	Линейные целочисленные модели распределения потоков в задачах проектирования и анализа многопродуктовых коммуникационных сетей
title_full_unstemmed	Линейные целочисленные модели распределения потоков в задачах проектирования и анализа многопродуктовых коммуникационных сетей
title_sort	линейные целочисленные модели распределения потоков в задачах проектирования и анализа многопродуктовых коммуникационных сетей
publisher	Інститут телекомунікацій і глобального інформаційного простору НАН України
publishDate	2013
topic_facet	Науково-технологічна безпека та інтелектуальні ресурси
url	https://nasplib.isofts.kiev.ua/handle/123456789/57585
citation_txt	Линейные целочисленные модели распределения потоков в задачах проектирования и анализа многопродуктовых коммуникационных сетей / В.А. Васянин, А.Н. Трофимчук // Екологічна безпека та природокористування: Зб. наук. пр. — К., 2013. — Вип. 12. — С. 147-165. — Бібліогр.: 71 назв. — рос.
series	Екологічна безпека та природокористування
work_keys_str_mv	AT vasâninva linejnyeceločislennyemodeliraspredeleniâpotokovvzadačahproektirovaniâianalizamnogoproduktovyhkommunikacionnyhsetej AT trofimčukan linejnyeceločislennyemodeliraspredeleniâpotokovvzadačahproektirovaniâianalizamnogoproduktovyhkommunikacionnyhsetej AT vasâninva líníjnícíločiselʹnímodelírozpodílupotokívuzadačahproektuvannâjanalízubagatoproduktovihkomuníkacíjnihmerež AT trofimčukan líníjnícíločiselʹnímodelírozpodílupotokívuzadačahproektuvannâjanalízubagatoproduktovihkomuníkacíjnihmerež AT vasâninva linearintegermodelsofdistributionofflowsinproblemsofdesigningandanalysisofmulticommoditycommunicationnetworks AT trofimčukan linearintegermodelsofdistributionofflowsinproblemsofdesigningandanalysisofmulticommoditycommunicationnetworks
first_indexed	2025-11-25T13:55:19Z
last_indexed	2025-11-25T13:55:19Z
_version_	1849770821136941056
fulltext	Розділ 3. Науково-технологічна безпека та інтелектуальні ресурси 147 УДК 504.1: 519.05 © В.А. Васянин, канд. техн. наук; А.Н. Трофимчук, д-р техн. наук, проф., чл.-корр. НАН Украины Институт телекоммуникаций и глобального информационного пространства НАН Украины, г. Киев ЛИНЕЙНЫЕ ЦЕЛОЧИСЛЕННЫЕ МОДЕЛИ РАСПРЕДЕЛЕНИЯ ПОТОКОВ В ЗАДАЧАХ ПРОЕКТИРОВАНИЯ И АНАЛИЗА МНОГОПРОДУКТОВЫХ КОММУНИКАЦИОННЫХ СЕТЕЙ В статье предлагаются модели распределения дискретных многопродуктовых пото- ков, представленные в виде задач линейного программирования. Проведен краткий обзор методов и алгоритмов, используемых в настоящее время для решения задач подобного клас- са. Показано, что практическое использование методов декомпозиции Данцига-Вулфа и ре- лаксации ограничений Розена для решения сформулированных задач позволило установить границы их разумного применения для реальных сетей - от 30 до 100 узлов, и они могут быть использованы при проектировании распределения потоков на нижних уровнях иерар- хической сетевой структуры. Отмечается, что для решения задач распределения потоков в децентрализованных распределенных сетях, содержащих более 200 узлов и 12000 дуг, целе- сообразно использовать сетевые постановки задач и приближенные методы решения, су- щественно опирающиеся на специфику структуры данных задач и содержательные эврис- тические соображения. Ключевые слова: линейные модели, многопродуктовые потоки, дискретность, ра- спределенные сети Для многих реальных территориально-распределенных сетей (транспортных, информа- ционно - вычислительных, топливно - энергетических, почтовых, телеграфных, телефонных и пр.) характерно использование широкого диапазона классов структур с различным коли- чеством узлов и линий связи, которые в общем случае неоднородны и имеют большое чис- ло разнообразных параметров. Существующие и проектируемые коммуникационные сети в большинстве случаев являются многоуровневыми. Как правило, такие сети состоят из децен- трализованной распределенной сети верхнего уровня (магистральной сети) и централизован- ных низовых сетей (зональных сетей) в нижнем уровне. Структура сети каждого уровня мо- жет обладать своей внутренней иерархией. Сложная структура сети может быть разделена на более простые структуры. Все многообразие данных сетевых структур может быть представлено в виде геопро- странственной модели, поддерживаемой средствами геоинформационной системы, напри- мер, платформой ArcGIS 9 компании ESRI. ArcGIS 9 построена на основе стандартов ком- Екологічна безпека та природокористування____________________________ 148 пьютерной отрасли, включая объектную архитектуру COM, .NET, Java, XML, SOAP, что обеспечивает поддержку общепринятых стандартов, гибкость предлагаемых решений, широ- кие возможности использования во многих прикладных сферах и на разных уровнях органи- зации работы: на персональных компьютерах, на серверах, через Web [1]. Инструментальные средства геоинформационных систем позволяют создать очень удобный, «дружественный» интерфейс для системных аналитиков при решении различных задач исследования сложных сетевых структур. При проектировании, анализе, планировании функционирования различных иерархиче- ских (многоуровневых) и однородных территориально-распределенных многопродуктовых коммуникационных сетей всегда приходится сталкиваться с необходимостью решения задач распределения потоков. При этом, как правило, следует рассматривать совокупность связан- ных между собой моделей распределения потоков для задач перспективного развития, теку- щего (среднесрочного) планирования и оперативного управления. Напомним, что под мно- гопродуктовой сетью понимается сеть с адресными несмешивающимися потоками (требова- ниями) между всеми парами узлов (или их подмножеством), которые одновременно переда- ются по сети. Таким образом, любой адресный поток представлен узлом-источником и уз- лом-стоком некоторого продукта. В общем случае на сети может быть задано некоторое множество видов (категорий) продуктов, отличающихся весом, габаритами и другими харак- теристиками, но имеющих общие источники и стоки. В различных математических моделях задачи распределения потоков функция цели и ограничения могут быть заданы как линей- ными, так и нелинейными уравнениями и неравенствами, а потоки продуктов и коэффициен- ты ограничений - непрерывными и дискретными величинами. Для многопродуктовых задач распределения потоков с непрерывными переменными известен целый ряд работ Ю.Е.Малашенко и Н.М.Новиковой, в которых рассматриваются задачи анализа допустимости многопродуктовых сетей при заданных, неточно заданных или неизвестных потоках требований [2-5]. При решении задач осуществляется поиск допусти- мого распределения потоков, на котором достигается уровень максиминной обеспеченности многопродуктовой сети - максимальное отношение реализованного в сети потока к заданным требованиям для "самых необеспеченных" пользователей, т.е. для пары пользователей, у ко- торых указанное отношение минимально. Такой критерий позволяет охарактеризовать структурные свойства сети и алгоритмы управления потоками. Решения соответствующих оптимизационных задач позволяют оценивать или формировать целый набор проектов сети с тем, чтобы обеспечить возможность выбора приемлемого варианта реальной сетевой систе- мы. Отмечается, что для решения задач о допустимости существует много методов: от спе- циальных сетевых вариантов симплекс-метода до метода последовательного проектирования [6-10]. Потоковые (комбинаторные) методы распределения потоков приведены в [11-17]. Эффективный приближенный алгоритм, основанный на методе экспоненциального потенци- ала [18], рассматривается в работе [19]. В случае сведения общей задачи о допустимости к задаче линейного программирования, для ее решения могут быть применены известные ме- тоды линейного программирования [15]. Задачи распределения потоков в различных поста- Розділ 3. Науково-технологічна безпека та інтелектуальні ресурси 149 новках являются весьма актуальными на уровне оперативного управления при исследовании вопросов живучести сетевых структур при их функционировании в режиме экстремальных нагрузок и воздействия неблагоприятных внешних факторов (например, стихийных бед- ствий) [20]. При этом выявляются и анализируются «узкие места» в сети - наиболее часто перегружаемые линии связи и узлы, нарушение ограничений на сроки доставки грузов на отдельных маршрутах транспортных средств или ограничений на среднее время задержки в передаче сообщений и т. д. При теоретико-графовом рассмотрении задач анализа живучести сетевых структур (процедурные модели вычисления основных графовых характеристик [21] ) не выделяется множество тяготеющих пар с потоками требований. При таком подходе критерий живучести может оказаться неэффективным - связность графа не нарушается, а многопродуктовый поток недопустим. Более действенным представляется потоковый подход [22,25,26]. При разрушении, перегрузке или отказе части сетевой структуры происходит пе- рераспределение потоков. Некоторые вопросы, связанные с перераспределением потоков после выхода из строя отдельных линий связи, рассматривались в работах [23,24], а задачи синтеза потоковой сетевой структуры с учетом живучести – в работах [25, 26]. Для распреде- ленных сетей передачи данных (РСПД) в книге Ю. П. Зайченко и Ю. В. Гонты [27] можно найти описание модифицированного алгоритма распределения потоков по критерию мини- мума среднего времени задержки в передаче сообщений, основанного на градиентном мето- де, в отличие от алгоритма отклонения потока, базирующегося на методе наискорейшего спуска, предложенного в работе Л. Клейнрока [28]. Другие алгоритмы, основанные на мето- де отклонения потока, приведены в работах [29,30]. Для неразветвленных потоков известны эвристические алгоритмы, которые позволяют получить приближенное решение задачи с небольшими вычислительными затратами [28,31,32]. Одним из основных недостатков эври- стических алгоритмов является невозможность оценки погрешности получаемых решений. Следует отметить, что при проектировании новых или анализе существующих РСПД, как правило, исследователю не известны ни число источников потоков, ни величины пото- ков, ни величины концевых задержек при передаче сообщений. Приходится довольствовать- ся вероятностной оценкой того или иного параметра. Неопределенность возникает и тогда, когда большой объем информации невозможно передать по одному каналу. В этом случае весь объем делят на пакеты, каждый из которых передается по любому свободному каналу с присущими ему случайными задержками. Реальные сетевые структуры всегда функциони- руют в условиях неопределенности и воздействия случайных факторов, но в большинстве случаев эту неопределенность можно «измерить» методами мониторинга и статистически оценить. Задержки линий связи, узлов, отказы технических элементов могут привести к бло- каде значительного участка сетевой структуры, но не разрушить ее - она остается живучей, но временно не работающей [33]. В работах [34-36] были предложены алгоритмы мультиа- гентной маршрутизации потоков, которые основываются на многоадресной маршрутизации, адаптации к факторам неопределённости и анализе возможных сетевых конфликтов. Отмеча- ется, что разработанные математические модели и оптимизационные методы динамической, адап- тивной, нейросетевой и мультиагентной (многоадресной и многопотоковой) маршрутизации ин- Екологічна безпека та природокористування____________________________ 150 формационных потоков для глобальных телекоммуникационных систем нового поколения пред- ставляются важным шагом в направлении создания теории адаптивного мультиагентного обслу- живания глобальных информационных и телекоммуникационных сетей, которая должна прийти на смену традиционной статистической теории массового обслуживания. Они могут быть полез- ны для организации адаптивного мультиагентного обслуживания GRID-инфраструктур различ- ного масштаба и назначения или для создания нового поколения научно-образовательных IP- сетей. Пусть G (N, P) – однородная многопродуктовая сеть с множеством узлов N, n = \| N \| и множеством неориентированных топологических дуг P, k = \| P \|. Под топологической дугой понимается физический отрезок линии связи: железной или автомобильной дороги, кабеля сети передачи данных, линии электропередач, телефонного кабеля и т. д.,- соединяющий два любых узла из множества N так, что между рассматриваемыми узлами на данном отрезке нет больше ни одного узла из N. Узлы сети соответствуют пунктам отправления, получения, пе- регрузки (перекоммутации) грузов или информационных потоков. На сети задано множество требований S на перевозку или передачу потоков. Под тре- бованием sij  S понимается пapa узлов ( і, j ), между которыми имеется направленный дис- кретный поток единичных элементов (например, неделимых грузов унифицированного раз- мера, бит или символов) объемом aij. Потоки требований заданы целочисленной матрицей грузов или сообщений A = \|\| a i j \|\| n x n , a i i = 0 , i = 1,n, которые подлежат единовременной передаче из источников i в стоки j , i, j = 1, n. Пусть на сети задано также множество M маршрутов транспортных средств (ТСР) или маршрутов передачи информации, содержащее прямые mij и обратные mji пути. Путь mij состоит из последовательности топологических дуг и узлов сети, соединяющей узел i с узлом j. B терминах теории графов mij представляет из себя простой путь [37]. Для сетей передачи данных (СПД) маршруты могут быть представлены простыми каналами связи, соединяющи- ми смежные узлы, или несколькими коммутируемыми каналами связи, соединяющими лю- бую последовательность узлов (выделенными каналами). В частном случае все заданные маршруты могут совпадать с топологическими дугами сети. Множество М может содержать несколько маршрутов, соединяющих любую пару узлов. C каждым маршрутом ТСР связаны его характеристики: тип и стоимость единицы пробега груженого и порожнего транспортного средства, курсирующего по маршруту; периодичность курсирования; грузоподъемность; узел приписки; место прибытия и отправления для крупных узлов; время прибытия и отправления транспортного средства для каждого узла в маршруте. Для каждого маршрута СПД заданы длина, стоимость и пропуск- ная способность. С элементами сети ассоциированы числа, характеризующие длину дуг сети, пропускные способности дуг и узлов, стоимости перевозки по дуге и обработки в узле единицы потока и т.д. Пропускные способности дуг сети определяют провозные возможности транспортных средств или объемы передаваемой информации по каналам связи, a под пропускными способностями узлов понимается допустимый объем обработки Розділ 3. Науково-технологічна безпека та інтелектуальні ресурси 151 транзитных грузовых или информационных потоков, т. к. исходящие и входящие потоки для каждого узла должны быть обработаны безусловно. Обозначим через H = \|\| hi \|\| T , i = 1,n – вектор - столбец пропускных способностей узлов, где знак “ T ” - означает транспонирование; L = \|\| lj \|\| T , j = 1,k - вектор - столбец пропускных способностей топологических дуг. Где hi , i = 1,n, lj , j = 1,k – суть целые неотрицательные числа. Кроме того, для выполнения требований могут быть заданы ограничения на сроки до- ставки грузов ti j из i в j или на среднее время задержки в передаче сообщений Tср [38] : ti j  Ti j ; (1) n n k Tср =(1/  aij)  fj /(lj - fj )  Tмакс , где fj – суммарный поток по дуге j . (2) i=1 j=1 j=1 Задача оптимизации распределения потоков заключается в определении рациональных путей перевозки или передачи вcex потоков, заданных на сети. При этом, в качестве крите- рия оптимальности распределения потоков могут выступать, например, минимум затрат (стоимости) или минимум среднего времени задержки на передачу всех потоков при задан- ных ограничениях на пропускные способности узлов и линий связи сети. Другим критерием оптимальности может быть максимум суммы распределенных потоков при ограничениях на суммы средств, выделенных на увеличение пропускных способностей узлов и линий связи сети, и ограничениях на среднее время задержки на передачу потоков. В настоящей работе рассматриваются линейные целочисленные модели задач распре- деления потоков в однородных многопродуктовых транспортных сетях (ТС) и сетях переда- чи данных, в которых в качестве функции цели принимается минимум затрат на обработку и передачу потоков, при ограничениях на пропускные способности узлов и дуг, а также приво- дятся некоторые практические соображения по использованию классических методов реше- ния таких задач. Будем считать, что дискретом времени отправления потоков в транспорт- ных сетях являются одни сутки, а в сетях передачи данных – одна секунда. Такие модели будем относить к моделям текущего планирования распределения потоков. Пусть E = \|\| ei j \|\| n x k - матрица инциденций "узлы-дуги" , описывающая сеть G. Будем считать, что каждая неориентированная дуга p  P заменена на две дуги с противоположной ориентацией и k означает число всех ориентированных дуг в G . Тогда элемент матрицы 1, если дуга j направлена к узлу і , e i j =  - 1, если дуга j направлена от узла і , 0, в противном случае . Екологічна безпека та природокористування____________________________ 152 Если через X i = ( x i 1 , x i 2 , …, x i k ) T обозначить вектор-столбец потока aij по всем дугам, то, используя матрицу инциденций, легко записать условия сохранения потока : ЕX i = V i , (3) где V i - вектор потребностей узлов в потоке aij и имеет следующий вид V i = ( v i 1 , v i 2 , …, v i n ) T , причем - a i j , если ξ = i , v i ξ =  a i j , если ξ = j , 0 , в противном случае. Очевидно, что максимальное число разных потоков (продуктов) на сети размерностью ( n x n) будет r = (n-1) x n . Условие (3) будет справедливо и в том случае, если его записать для всех потоков, исходящих из узла i . B этом случае число условий (3) сократится до числа узлов-источников потоков, a X i будет означать вектор-столбец потоков aij , j = 1,n , i  j по всем дугам. Элементы вектора V i определятся так : n -  a ij , если ξ = i , ξ =  j=1 (4) a ij , если ξ = j . Пусть C i = ( c i 1 , c i 2 , …, c i k ) - вектор-строка стоимости перевозки (передачи) единицы потока из источника i по дугам сети;  i = (  i 1 ,  i 2 , …,  i k ) - вектор-строка матрицы инци- денций, в которой элементы равные –1 заменены на нули ; H' = ( h'1 , h'2,…,h'k) - вектор допустимых транзитных потоков, проходящих узлы без дополнительной обработки. Тогда задачу распределения потоков можно сформулировать в виде : Min Z = C 1 X 1 + ... + C n X n (5) n  1 X 1 + ... +  1 X n  h1 + h'1 +  a i 1 , i=1 ... ... ... (6) n  n X 1 + ... +  n X n  hn + h' +  a i n , i=1 X 1 + ... + X n  L , (7) EX 1 = V 1 , . . . . (8) . . EX n = V n , X i  0 и целые, i = 1,n . (9) Розділ 3. Науково-технологічна безпека та інтелектуальні ресурси 153 Запись ограничений по пропускной способности узлов в виде (6) может быть неудобна, поскольку на практике трудно выделить транзит ( значения hi и h'i) и входящие потоки, а значит, указать правильную величину пропускной способности. Поэтому ограничения (6) можно переписать так, чтобы в правых частях была указана фактическая пропускная спо- собность узлов, состоящая из суммы исходящих, входящих и транзитных потоков. Для этого определим матрицы W i , i = 1,n с элементами 1, если eξ j = 1 , w i ξ j =  1, если eξ j = -1 и ξ = i , (10) 0, в противном случае , для ξ = 1, n , j = 1, k и вектор n n n n H w = ( h1 + h'1 +  a1 j +  a j 1 ,…, hi + h'i +  a i j +  a j i ,…, j=1 j=1 j=1 j=1 n n hn + h'n +  a n j +  a j n ) T . (11) j=1 j=1 Тогда условия (6) запишутся в виде W 1 X 1 + ... + W n X n  H w . (12) При обсуждении модели (5), (7) - (9), (12) очевидно, что в любом оптимальном решении Х 0 = ( X 1 ,…,X n ) не будут учтены стоимости транзитных перегрузок потоков гру- зов с одного транспорта на другой, или перекоммутацию информационных потоков в тран- зитных узлах, поскольку распределение потоков выполняется по топологическим дугам и не учитываются заданные маршруты транспортных средств или информационные маршруты (выделенные каналы связи). В левых частях векторных неравенств (12) суммируются, кроме исходящих и входящих потоков, все потоки, проходящие транзитом через рассматриваемый узел. Однако неизвестно, какие потоки будут перегружаться или перекоммутироваться в узле, а какие пройдут транзитом в транспортных средствах без перегрузки или по скоммути- рованным каналам. В этом случае, для того чтобы определить действительную стоимость транзитных перегрузок (перекоммутации), необходимо решить дополнительную задачу маршрутизации оптимальных потоков по маршрутам транспортных средств или скоммути- рованным каналам. Известно, что при перевозке грузов наиболее трудоемкими операциями, увеличивающими стоимость перевозок, являются транзитные перегрузки грузов с одного транспорта на другой. Для сетей передачи данных для уменьшения времени задержки сооб- щений также желательно использовать широкополосные скоростные скоммутированные (выделенные) каналы связи с большой пропускной способностью. Поэтому далее рассмот- рим модели задачи, в которых учитываются маршрутные дуги. Пусть GM (N, PM) - маршрутная сеть, где N - множество узлов сети, PM - множество ее ориентированных маршрутных дуг. Между любыми двумя узлами i, j сети существует маршрутная дуга, если они связаны хотя бы одним маршрутом из M, проходящим через эти Екологічна безпека та природокористування____________________________ 154 узлы. В этом случае говорят, что между i и j существует прямая связь. Ясно, что в общем случае GM является мультисетью. Учитывая сложность многопродуктовых задач и их боль- шую размерность, при распределении потоков все параллельные дуги сети GM обычно "склеивают" в одну . Сформулируем задачу распределения потоков на маршрутной сети в виде, аналогичном (5), (12), (7), (9). Прежде всего, очевидно, что при определении вектора H w нет необходимости учитывать величины h'i, так как потоки распределяются по маршрутным дугам и число транзитных перегрузок или перекоммутаций для любого потока определяется числом транзитных узлов на пути следования потока. Примем H' = 0. Сложнее обстоит дело при записи условий о непревышении пропускных способностей дуг. Рассмотрим совокупность векторов X i = ( x i 1 , x i 2 , …, x i k' ) T , i = 1,n, где k' - число дуг в сети GM . Поток по любой дуге x i j не может быть соотнесен с провозной возможностью транспортных средств или пропускной способностью канала, заданных вектором L пропускных способностей топо- логических дуг сети G. Каждой маршрутной дуге pj  PM соответствует некоторое подмножество топологических дуг j  P, поэтому поток по дуге pj, проходит по всем ду- гам из j . Пусть Y i = Ф(X i ) , i = 1,n ‚ (13) где Y i = ( y i 1 , y i 2 , …, y i k ) T - вектор-столбец потоков продукта по топологическим дугам сети G, соответствующий распределению потоков X i по маршрутным дугам; Ф - линейный оператор, отображающий множество элементов X i на множество элементов Y i . Тогда задачу распределения потоков можно записать в виде: Min Z = C 1 [k']X 1 [k'] + ... + C n [k']X n [k'] , (14) W 1 [n,k']X 1 [k'] + ... + W n [n,k']X n [k']  H w [n] , (15) Y 1 [k] + ... + Y n [k]  L[k] , (16) E[n,k']X 1 [k'] = V 1 [n] , . . . . (17) . . E[n,k']X n [k'] = V n [n] , X i [k'] ,Y i [k]  0 и целые. (18) В записи (14) - (18) квадратные скобки употреблены для подчеркивания размерности задачи. B отличие от модели распределения потоков на сети, заданной топологическими дуга- ми в модели (14) - (18) , правые части (15) определяются значительно проще, так как для каждого узла i необходимо указать только величины hi. Однако ограничения (16) усложняют Розділ 3. Науково-технологічна безпека та інтелектуальні ресурси 155 задачу из-за наличия операций преобразования (13). Отметим также, что целевая функция (14) отражает затраты только на перевозку или передачу потоков по маршрутным дугам, хотя минимизация транзита может быть обеспечена при распределении потоков использова- нием "двухступенчатого" алгоритма - минимум перегрузок, минимум длины пути [39]. Рассмотрим модель задачи распределения потоков, позволяющую учесть в целевой функции затраты на транспортировку (передачу) потоков и их обработку в узлах. Для этого введем понятие расширенной сети GM  (N  , PM  ), в которой каждый узел сети GM заменен двумя - левым и правым, причем каждая пара узлов "левый - правый" в сети GM  имеет номера i , i + n , где i - номер узла в сети GM или G. Bce дуги, входящие в данный узел сети GM , заменяются на дуги, входящие в его левый узел сети GM  ; дуги, выходящие из узла сети GM , заменяются на дуги, выходящие из его правого узла сети GM  . Каждый левый и правый узлы сети GM  , соединяются фиктивной дугой, стоимость перевозки (передачи) по которой является стоимостью обработки в узле. Ha сети GM  в качестве источников потоков выступают левые узлы, a в качестве стоков - правые. Пусть n  = n + n - число узлов расши- ренной сети, k  = k' + n – число ее дуг. Составим матрицу инциденций для расширенной сети таким образом, чтобы первые n ее строк соответствовали номерам узлов источников (левым узлам) , a первые n столбцов - фиктивным дугам. Пусть X i = ( x i 1 , …, x i n, x i n+1 ,…, x i n+k' ) T , i = 1,n , где первые n элементов определяют потоки i - го продукта по фиктивным дугам; C i = ( c i 1 , …, c i n, c i n+1 ,…, c i n+k' ) , i = 1,n , где первые n элементов c i j , j = 1,n определяют стоимость обработки единицы i - го про- дукта в j - ом узле. Разделим X i на две части следующим образом: X i = ( x i 1 , …, x i n ) T , X i  = ( x i n+1 ,…, x i n+k' ) T . Тогда можно записать X 1 [n] + … + X n [n]  H w [n] , где элементы вектора H w определяются из выражения (11) при h'i = 0. Пусть по аналогии с (13) Y i = Ф(X i ), тогда окончательно сформулированная задача примет вид: Min Z = C 1 [k  ]X 1 [k  ] + ... + C n [k  ]X n [k  ] , (19) X 1 [n] + ... + X n [n]  H w [n] , (20) Екологічна безпека та природокористування____________________________ 156 Y 1 [k] + ... + Y n [k]  L[k] , (21) E[n  ,k  ]X 1 [k  ] = V 1 [n  ] , . . . . (22) . . E[n  ,k  ]X n [k  ] = V n [n  ] , X i [k  ] , X i [n] , Y i [k]  0 и целые. (23) Bce приведенные модели задачи распределения потоков относятся к классу задач ли- нейного целочисленного программирования, имеют блочно-диагональную структуру со свя- зывающими ограничениями и являются NP-полными [40,41]. Для решения таких задач из общих точных методов известны методы отсечения, ветвей и границ, динамического про- граммирования, из специальных - метод декомпозиции Данцига - Вулфа и его модификации [42,43], метод релаксации ограничений Розена [44,45], минимаксно - двойственные методы и методы параметрической декомпозиции. Обзор методов и алгоритмов решения блочных задач можно найти в [46-49]. Поскольку матрицы ограничений рассмотренных моделей яв- ляются вполне унимодулярными, а правые части ограничений - целочисленными векторами, то получаемые решения с использованием различных модификаций симплекс-алгоритма внутри схем декомпозиции будут всегда целочисленными, так как допустимый многогран- ник решений имеет только целочисленные вершины. Не следует также забывать, что и в слу- чае не унимодулярности матриц ограничений для некоторых классов задач, в которых реше- ния представляются большими целыми числами, а неизвестные принимают значения с ма- лым (например, единичным) шагом, можно использовать симплекс-методы с последующим округлением решения до ближайших целых чисел. Как известно из практики, методы отсечения успешно применяются при решении целочисленных задач небольшой размерности (десятки и сотни переменных) [50]. Не лучше обстоит дело и при использовании методов ветвей и границ и декомпозиции, когда размерность решаемых задач определяется десятками тысяч переменных [51]. Эти методы могут использоваться лишь в качестве вспомогательного аппарата при анализе задач боль- шой размерности (сотни тысяч и более переменных и ограничений). Для методов динамического программирования характерно то, что их эффективность зависит от удачно построенных последовательностей, рекуррентно связанных между собой функций Беллмана. При этом, как правило, принципы динамического программирования оказываются полезными лишь в случае малого числа ограничений, то есть для узкого класса специальных целочисленных задач [52]. Так, например, практическое использование метода Данцига- Вулфа и модификации метода ограничений Розена для решения задач (14) - (18) и (19) - (23) позволило установить границу эффективности их применения – соответственно до 40 и 100 узлов и 300 и 500 маршрутных ориентированных дуг. Для реальных сетей, содержащих от n=200 узлов и k=12000 маршрутных ориентированных дуг (число переменных = n(n- 1)k=20019912000=4,77610 8 ) до 500 узлов и 55000 маршрутных ориентированных дуг Розділ 3. Науково-технологічна безпека та інтелектуальні ресурси 157 (число переменных = 50049955000=1,3722510 10 ) и выше, использование вышеуказанных точных методов не позволяет получить решение рассмотренных задач за приемлемое время. Численное экспериментирование с точными методами решения задач целочисленного программирования выявило ограниченность их возможностей [53,54]. Трудности, возникающие при решении практических задач большой размерности, получили не только вычислительное подтверждение, но и теоретическое обоснование [41,55,56]. Другим факто- ром, заставляющим отказаться от применения точных методов для решения рассмотренных задач, является то, что большинство практических задач характеризуются мнoгoэкстремальностью, должны решаться в условиях ограниченных и динамически изме- няющихся с течением времени ресурсов, a также при недостаточно точной исходной информации. Учитывая общую теоретическую сложность (NP - полноту) задач целочисленного линейного программирования и недостатки, присущие точному решению практических задач распределения потоков, следует сделать вывод о бесперспективности развития точных методов для решения задач подобного класса. При этом, однако, не следует забывать о возможности эффективного применения точных методов для решения частных подзадач распределения потоков на нижних уровнях сети для ее фрагментов с числом узлов до 30-40. Перечисленные обстоятельства привели к тому, что в настоящее время одним из глав- ных направлений развития дискретной оптимизации стала разработка и исследование приближенных методов. Обширный библиографический обзор по приближенным методам можно найти в [53,54,57-61]. Среди многообразия приближенных методов следует выделить два класса - методы, порожденные точными методами, и методы, сразу нацеленные на получение приближенного решения. К первому классу относятся все точные методы монотонно не увеличивающие ( или не уменьшающие) значение целевого функционала на последовательно выполняющихся итерациях. B этом случае решение, полученное на любой итерации, будет приближенным. Наиболее перспективными точными методами, используемыми для приближенного реше- ния дискретных задач, являются методы ветвей и границ. Общая схема этих методов порождает последовательность приближенных решений и дает оценку погрешности отклонения от действительного оптимума. Известны прямые методы отсечения, позволяющие на каждом шаге получать целочисленные решения и обладающие свойством монотонности [62-64]. Главным недостатком этих методов является крайне медленная сходимость, поэтому, как правило, построить эффективный приближенный алгоритм, используя прямые методы отсечения, не удается. Второй класс приближенных методов подразделяется на три подкласса: детерминированные методы, методы случайного поиска и эвристические методы. К детерминированным методам относятся: метод вектора спада, метод направляющих окрестностей и специальные методы [58]. Для сетевых постановок задач дискретной опти- мизации из группы детерминированных методов известны методы выключения узлов, прокатных оценок, последовательного улучшения плана, сокращения невязок [65,66]. Отме- Екологічна безпека та природокористування____________________________ 158 чается, что метод выключения узлов может привести к случаю несвязной сети и не гарантирует получение решения. Для метода прокатных оценок при определенных парамет- рах сети также не удается получить решение из-за возможности зацикливания алгоритма. Работы [67-69] посвящены методам случайного поиска. Наибольшей трудностью, с которой приходится сталкиваться при использовании методов случайного поиска, является сложность выбора рабочих параметров методов, неудачное определение которых может привести к нежелательному эффекту "блуждания" алгоритмов. Рассматривая приближенные методы решения дискретных задач, нельзя не выделить класс эвристических методов. Под эвристическими методами понимаются любые приемы, не имеющие формального обоснования и опирающиеся на анализ специфики структуры задачи и связанные с ней содержательные соображения. Эвристические методы используются как самостоятельные процедуры решения, так и внутри точных методов. Главным недостатком эвристических методов является то, что в подавляющем большинстве случаев нет возможности оценить отклонение полученного приближенного решения от действительного оптимума. Стремление к разработке приближенных алгоритмов с априорной оценкой точности привело к тому, что в последнее время особое внимание уделяется поиску алгоритмов малой трудоемкости, дающих "почти оптимальное" решение, и алгоритмов, дающих оптимальное решение "почти всегда" [57,70]. B работах [54,57] приведен обзор развития этих направлений, из которого следует, что для NP - трудных классов задач дискретного программирования получение приближенного решения с заданной абсолютной погрешностью так же сложно, как и получение точного решения. B частности, к этому классу задач относится и рассмотренная задача о распределении целочисленного многопро- дуктового потока в сети. Заключая обзор методов решения дискретных задач оптимизации, отметим, что для решения задач потокораспределения, возникающих при проектировании и анализе распреде- ленных коммуникационных сетевых структур с дискретными потоками, целесообразно ис- пользовать приближенные методы с максимальным учетом специфики структуры задач, a также комбинированные методы, позволяющие за приемлемое время получать решения требуемой точности. Проанализируем рассмотренные модели с точки зрения их использования при решении задач проектирования и анализа однородных и иерархических многопродуктовых коммуни- кационных сетей. Прежде всего, отметим, что целевые функции во всех моделях линейные. B модели (19)-(23) в целевой функции учитываются стоимости обработки исходящего, входящего и транзитного потоков. Как известно, для дискретных потоков грузов операции обработки в основном связаны с сортировкой и сличением грузов с сопроводительной доку- ментацией. Стоимость таких операций определяется не только обрабатываемым объемом, но и количеством направлений сортировки, по которым рассортировывается этот поток грузов. Как правило, для реальных сетей функция приведенных затрат на сортировку зависит от объема и числа направлений сортировки нелинейно. Кроме того, эта функция зависит также Розділ 3. Науково-технологічна безпека та інтелектуальні ресурси 159 от оборудования, которое применяется для сортировки, то есть от типа сортировочной ма- шины и режимов ее работы (автоматический, полуавтоматический, ручной). Для сетей пере- дачи данных также характерно использование специального оборудования (коммутаторов, маршрутизаторов, концентраторов) для уменьшения количества линий связи передачи пото- ков. Во многих случаях в реальных сетевых системах объемы (величины) большинства пото- ков требований очень малы по сравнению с провозной возможностью транспортных средств или пропускной способностью каналов связи. Тогда возникает задача формирования пото- ков, суть которой заключается в уменьшении количества направлений сортировки грузов или сообщений за счет объединения нескольких грузов или сообщений с разными конечны- ми адресами в некоторые транспортные блоки заданного размера. При этом увеличивается загрузка транспортных средств и каналов связи и уменьшается их общее количество, но воз- никает дополнительная сортировка тех потоков требований, которые в составе транспортно- го блока, адресованного в некоторый узел, являются транзитными для данного узла. Для транспортных сетей такая ситуация характерна при перевозке мелкопартионных грузов, а для сетей передачи данных - при использовании технологии виртуальных контейнеров в крупномасштабных общенациональных и интернациональных сетях на основе сверхшироко- полосных каналов и схем типа опорной сети – backbone. B приведенных моделях задача распределения потоков рассматривается в отрыве от организации процессов сортировки дискретных потоков грузов и концентрации информаци- онных потоков в узлах сети, в действительности же, именно схема сортировки и концентра- ции адресует потоки, a значит, и сильно влияет на оптимальность распределения потоков. На уровне магистральной децентрализованной распределенной сети нельзя рассматривать стоимость транспортировки или передачи потоков как линейную функцию от расстояния, поскольку она нелинейно и дискретно зависит от величины пропускаемых потоков. В мате- матической модели задачи распределения потоков для реальных магистральных распреде- ленных сетей должны учитываться не только ограничения на пропускные способности узлов и дуг сети, но и ограничения на: сроки доставки грузов (1) или среднее время задержки в передаче сообщений (2); время погрузки-выгрузки грузов во всех узлах, через которые следуют транспортные средства, или время перекоммутации сообщений в транзитных узлах. Могут быть заданы также чисто комбинаторные ограничения на допустимое число транзит- ных узлов в путях следования потоков. Кроме того, необходимо учитывать нелинейность затрат на обработку и перевозку грузов или обработку и передачу сообщений. B работе [71] приведены модели, позволяющие логически увязать процессы сортировки и концентрации дискретных потоков в узлах сети с задачами распределения и маршрутизации потоков и учи- тывающие нелинейность затрат на обработку и транспортировку (передачу) потоков и все вышеперечисленные ограничения. На основании вышеизложенного можно сделать следующие выводы и определить направления дальнейшего исследования задач распределения потоков в иерархических мно- гопродуктовых сетевых структурах. Екологічна безпека та природокористування____________________________ 160 1. Предложенные модели и декомпозиционные методы решения соответствующих за- дач могут быть использованы для распределения потоков на нижних уровнях иерархической сети - в зональных сетях, содержащих не более 30-40 узлов. 2. Существенное влияние на распределение потоков в сетевых структурах с дискрет- ными потоками требований, объемы (величины) каждого из которых много меньше объема транспортных блоков, подлежащих транспортировке или передаче по распределенной магистральной сети, оказывают процессы сортировки грузов и концентрации сообщений в узлах сети, что приводит к ярко выраженной зависимости затрат на обработку и траспорти- ровку (передачу) потоков от процессов их сортировки. В приведенных моделях не учитыва- ются зависимости распределения потоков от процессов их сортировки, поэтому они не могут с достаточной степенью адекватности отражать формирование и распределение потоков в реальных сетях и обеспечить высокую эффективность функционирования распределенной сетевой структуры. 3. B рассмотренных математических моделях распределения потоков не учитывается ряд важнейших факторов, сопутствующих обработке и перевозке (передаче) потоков в реальных сетях, таких как сроки доставки грузов или среднее время задержки в передаче сообщений, время обмена грузами в пунктах следования транспортных средств или время на перекоммутацию сообщений, нелинейность затрат на обработку и перевозку потоков. Проектирование схемы функционирования многопродуктовой сетевой структуры требует учета этих факторов, что приводит к необходимости разработки новых сетевых математиче- ских моделей, адекватно описывающих процессы сортировки и транспортировки (передачи) потоков и позволяющих взаимосвязанно решать задачи распределения потоков и загрузки транспортных средств или каналов связи. 4. Проведенный обзор методов дискретного программирования показал, что для реше- ния задач распределения потоков большой размерности (сотни миллионов и более переменных), возникающих при проектировании и анализе реальных сетевых структур (более 200 узлов и 12 тысяч дуг), целесообразна разработка специальных приближенных методов, существенно использующих специфику структуры практических задач, разумные эвристические соображения и интерактивный режим оптимизации и выбора получаемых решений. Список использованной литературы 1. Режим доступа: http://www.dataplus.ru/Soft/ESRI/ArcGIS/. 2. Малашенко Ю.Е. Нормативный подход к анализу многопродуктовых сетей // Изв. АН СССР. Техн. кибернетика, 1988.- N. 3. 3. Малашенко Ю. Е., Новикова H. М. Обобщенная задача анализа многопродуктовой сети // Изв. АН СССР. Техн. кибернетика, 1989.- N. 4. 4. Малашенко Ю. Е. Математические модели анализа потоковых сетевых систем. М.: ВЦ РАН, 1993. http://www.dataplus.ru/Soft/ESRI/ArcGIS/ Розділ 3. Науково-технологічна безпека та інтелектуальні ресурси 161 5. Малашенко Ю. Е. Модели неопределенности в многопользовательских сетях / Ю. Е. Малашенко, Н. М. Новикова. – М. : Едиториал УРСС, 1999. – 160 с. 6. Hu Т. C. On the feasibility of simultaneous flows in network // Oper. Res., 1964.- V 12. 7. Assad A. A. Multicommodity network flows: A survey // Networks.- 1978.- V.8.- N. 1.- P. 37-91. 8. Кеnnіngton J. L. A survey of linear cost multicommodity network flows // Орег. Res.- 1978.- V. 26.- N. 2.- P. 206-236. 9. Kamath A., Palmon 0. Improved interior-point algorithms for exact and approximate solutions of multicommodity flow problems // Proceeding of the 6th ACM-SIAM Symposium on Dis- crete Algorithms, 1995. 10. Давидсон М. Р. Условия устойчивости множества крайних точек полиэдра и их приме- нение для исследования многопродуктовых сетевых моделей: Автореф. дис.... канд. физ.-матем. наук. М.: ВЦ РАН,1995. 11. Matula D. W. Concurrent flow and concurrent connectivity іn graphs // Graph Theory and Its Appl. to Algorithms and Comput. Sci. N.-Y.: Wi1ey-Intersci., 1985. 12. Biswas J., Matula D. W. Two flow routing algorithms for the maximum concurrent flow problem // Fall Joint Comput. Conf., Dallas, Tex., Nov. 2-6, 1986. Proc. Washington, D .C., 1986. 13. Thompson B. J., Matula D. W. A Flow Rerouting Algorithm for Maximum Concurrent Flow Problem with Variable Capacities and Demands, and its Application to Cluster Analysis, Tech. Report 86-CSE-12, Computer Science Dept., Southern Methodist University, March, 1986. 14. Shahrokhi F., Matula D. W. The maximum concurrent flow problem // J. Assoc. Comput. Math., 1990, 37. N.2. 15. Leong T., Shor P., Stein C. Implementation of a combinatorial multicomrnodity flow algo- rithm. DIMACS Working paper, 1992. 16. Klein P., Plotkin S., Stein C., Tardos E. Faster approximation algorithms for the unіt capacity concurrent flow problem with applications to routing and finding sparse cuts // SIAM J. Comput. 1994.- V. 23, N. 3. 17. Leighton T., Makedon F., Plotkin S., Stein C., Tardos E., Tragoudas S. Fast approximation algorithms for multicommodity fiow problems // J. Computer and Syst. Sci.,1995.- V. 50. N. 1. 18. Grigoriadis M. D., Khachiyan L. G. Fast approximation schemes for convex programs with many blocks and coupling constraints // SIAM J. Optimization,1994. V.4. 19. Grіgoriadis M. D., Khachiyan L. G. Approximate minimum-cost multicommodity flows in O( -2 KNM) time. Tech. Rep. LCSR-TR-245, Department of Computer Science, Rutgers Uni- versity, New Brunswick, NJ, May 1995. 20. Громов Ю.Ю., Драчев В.О., Набатов К.А., Иванова О.Г. Синтез и анализ живучести сетевых систем.- М.: «Издательство Машиностроение-1», 2007.-152 с. Екологічна безпека та природокористування____________________________ 162 21. Алгоритмы и программы решения задач на графах и сетях / М.И. Нечепуренко, В.К. Попков, С.М. Майнагашев, С.Б. Кауль и др. – Новосибирск : Наука : Сиб. отд-ние, 1990. 22. Малашенко Ю. Е. Оперативная корректировка запасов и потоков энергоресурсов в энергетических комплексах при внешних возмущениях: справочник по общим моделям анализа и синтеза надежности систем энергетики / Ю.Е. Малашенко; под ред. Ю.Н. Ру- денко.- М.: Энергоатомиздат, 1994.- С. 435-447. 23. Multicommodity flow approach to assignment of circuits in case of failure in a communica- tion network / Y. Ishiyama, Y. Ishizaki, S. Sasabe, N. Yoshida // Survey of mathematical pro- gramming. Proceedings of the 9th international mathematical programming symposium. – 1976, 1979. – V. 3. – P. 195 – 209. 24. Chung, F.R.K. Diameters of communication networks / F.R.K. Chung // Proceedings of sym- posia in applyed mathematics. Providence, R.I. – 1986. – V. 34. – P. 1 – 18. 25. Мину. М. Математическое программирование / М. Мину. – М. : Наука, 1990. 26. Математические постановки задач восстановления и обеспечения живучести для мно- гопродуктовых сетей / М.Р. Давидсон, Ю.Е. Малашенко, Н.М. Новикова и др. – М. : ВЦ РАН, 1993. 27. Зайченко Ю.П., Гонта Ю. В. Структурная оптимизация сетей ЭВМ.-К.: Техніка, 1986.- 168 с. 28. Fratta L., Gerla M., Kleinrock L. The Flow Deviation Method: An Approach to Store-and- Forward Communication Network Design. Networks, 1973, vol. 3, no. 2, pp. 97–133. 29. Федотов Е. В. Определение оптимальных маршрутов в сети пакетной коммутации. В сборнике: Сетевая обработка информации. М.: МДНТП, 1990, стр. 95–98. 30. Gavish B., Hantler S. L. An Algorithm for Optimal Route Selection in SNA Networks. IEEE Trans. Commun., 1983, vol. COM-31, no. 10, pp. 1154–1161. 31. Courtois P.J., Semal P. An Algorithm for the Optimization of Nonbifurcated Flows in Comput- er Communication Networks. Performance Evaluation, 1981, vol. 1, pp. 139–152. 32. Вишневский В. М., Федотов Е.В. Анализ методов маршрутизации при проектировании сетей пакетной коммутации. 3rd I.S. “Teletraffic Theory and Computing Modeling,” София, 1990. 33. Вишневский, В. М. Теоретические основы проектирования компьютерных сетей / В.М. Вишневский. – М. : Техносфера, 2003. – 512 с. 34. Syrtzev A. V., Timofeev A. V. Neural and Multi-Agent Routing in Telecommunicational Networks. – International Journal “Information Theories and Their Applications”, 2003 , vol.10, № 2, pp. 167-172. 35. Timofeev A. V. Models for Multi-Agent Dialogue and Informational Control in Global Tele- communicational Networks. – International Journal “Information Theories and Their Applica- tions”, 2003, vol., №1. Розділ 3. Науково-технологічна безпека та інтелектуальні ресурси 163 36. Timofeev A. V. Multi-Agent Information Processing and Adaptive Control in Global Tele- communication and Computer Networks. – International Journal “Information Theories and Their Applications”, 2003, vol. 10, N 1, pp. 54–60. 37. Оре О. Теория графов. - М .: Наука., 1980.- 336 с. 38. Клейнрок Л. Коммуникационные сети : Стохастические потоки и задержки сообщений.- М.: Наука, 1970.- 255 с. 39. Васянин B. A. , Савенков A. И. Алгоритм построения кратчайших путей на сети по сту- пенчатому критерию // Дискретные и эргатические системы управления : Сб. науч. тр.- Киев, 1983. - C. 40 - 49.- B надзаг. : АН УССР, Научный совет по проблеме "Киберне- тика", институт кибернетики. 40. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов.- М.: Мир, 1979.- 512 с. 41. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи .- М .: Мир, 1982.- 416 с. 42. Dantzig G. B., Wolfe Ph. Decomposition prinsiple for linear programming // Oper. Res.- 1960.- v. 8, № 1.- P. 101-111. 43. Dantzig G. B., Wolfe Ph. Decomposition Algorithm for linear programming // Econometrica.- 1961.- v. 29, № 4.- P. 767-778. 44. Rosen J. B. Convex partition programming // In Recent advances in mathematical program- ming.- New York, 1963.- P. 159-176. 45. Rosen J. B. Primal partition programming for block-diagonal matrices // Numerische Mathe- matik.- 1964.- v. 6, № . 3.- P. 250-264. 46. Лэсдон Л. C. Оптимизация больших систем. - М.: Наука, 1975.- 432 с. 47. Верина Л.Ф.,Танаев B.C. Декомпозиционные подходы к решению задач математиче- ского программирования (обзор) // Экономика и математ. методы,- М., 1975.- Т. 10, вып. 6.- C. 1160 -1172. 48. Бyлaвcкий B.A., Звягинa P.A. ,Якoвлeвa М.A.Численные методы линейного программи- рования. - М.: Наука, 1977. - 367 c . 49. Цypкoв B. И. Декомпозиция в задачах большой размерности. - М .: Hayкa, 1981.- 352 c . 50. Wolsey L. A. Cutting planer methods // Oper. Res. Suppot Method.- New York-Basel, 1979.- P. 441-446. 51. Фридман A. A . О некоторых современных направлениях в дискретной оптимизации // Экономика и матем. методы. – М ., 1977 .- Т. 13, № 5.- C. 1115 - 1131. 52. Гольштейн Е. Г. , Юдин Д. Б. Новые направления в линейном программировании. - М. : Сов. радио, 1966 . - 524 с . 53. Финкельштейн Ю. Ю. Приближенные методы и прикладные задачи дискретного про- граммирования. - М.: Наука, 1976 .- 283 с. 54. Корбут A. A. , Финкельштейн Ю. Ю. Приближенные методы дискретного программи- рования // Изв. АН СССР. Техническая кибернетика. - М., 1983 . - № 1.- C. 165-176 . Екологічна безпека та природокористування____________________________ 164 55. Немировский A. C. , Юдин Д. Б. Сложность задач и эффективность методов оптимиза- ции. - М. : Наука, 1979 .- 384 с. 56. Пападимитриу Х. , Cтайглиц K. Комбинаторная оптимизация. Алгоритмы и сложность : Пер. с англ. – М . : Мир, 1985. - 512 с. 57. Генс Г. B. , Левнер Е. B. Дискретные оптимизационные задачи и эффективные прибли- женные алгоритмы // Изв. АН СССР. Техническая кибернетика. - М ., 1976.- № 6.- C. 9- 20. 58. Сергиенко И. B. , Лебедева Т. Т., Рощин B. A. Приближенные методы решения задач оптимизации. - Киев : Наукова думка, 1980. - 276 с. 59. Garey M. R. , Johnson D. S. Approximation algorithms for combinatorial problems : an anno- tated bibliography // Algorithms and complexity. New directions and recent results.- New York: Acad. Press, 1976.- P. 41-52. 60. Grigoriadis M. D., Whate W. W. A partitioning algorithm for the multi-commodity network flow problem // Math. Prog.- 1972.- v. 3.- P. 157-177. 61. Klee V. Combinatorial optimization : what is the state of the art // Math. Oper. Res.- 1980.-v. 5, № 1.- P. 1-26. 62. Юдин Д. Б. , Гoльштeйн E. Г. Линейное программирование. Теория, методы и прило- жения. - М.: Hayкa, 1969 . - 422 c . 63. Чepвaк Ю. Ю. Возвращающийся алгоритм метода отсечений и метод ветвей и границ // Экономика и мaтeм. методы. - М ., 1978.- T. 14, № 5.- C. 1002-1005. 64. Динин И. И., 3оркальцев B. И. Итеративное решение задач математического програм- мирования / Сб. под ред. A. И. Тятюшкина. – Новосибирск : Наука, 1980.- 144 с 65. Нестеров Е. П. Транспортные задачи линейного программирования. - М.: Транспорт, 1971.- 216 с. 66. Габасов P. , Кириллова P. М. Методы линейного программирования. Часть 2. Транс- портные задачи. - Минск : Изд – во Белорусск . ун - та, 1978.- 236 с. 67. Растригин Л. A. Статистические методы поиска . – М . : Наука, 1968.- 376 с. 68. Алгоритмы и программы случайного поиска. / Под peд. Л. A. Pacтpигинa.- Рига: 3инaтнe, 1969.- 374 c. 69. Вопросы повышения эффективности алгоритмов минимизации функций и математиче- ского программирования / Иванов B. B., Людвиченко B. A., Михалевич B. C. и др. - Ки- ев, 1979.- 53 с. ( Препринт ИК АН УССР ; № 79 - 59). 70. Левнер Е. B., Генс Г. B. Дискретные оптимизационные задачи и эффективные алгорит- мы. – М . : ЦЭМИ, 1978. - 55 с. 71. Васянин В.А. Обобщенная задача упаковки и распределения мелкопартионных потоков в многопродуктовых иерархических коммуникационных сетях и ее последовательная декомпозиция // Екологічна безпека та природокористування: Зб. наук. праць.- Київ, 2012.- Вип. 11.- С. 136-154. Стаття надійшла до редакції 13.11.12 російською мовою Розділ 3. Науково-технологічна безпека та інтелектуальні ресурси 165 © В.О. Васянін, О.М. Трофимчук Лінійні цілочисельні моделі розподілу потоків у задачах проектування й аналізу багатопродуктових комунікаційних мереж У статті пропонуються моделі розподілу дискретних багатопродуктових потоків, пред- ставлені у виді задач лінійного програмування. Проведено короткий огляд методів і алго- ритмів, використовуваних у даний час для рішення задач подібного класу. Показано, що практичне використання методів декомпозиції Данцига-Вулфа і релаксації обмежень Розена для рішення сформульованих задач дозволило установити границі їхнього розумного за- стосування для реальних мереж - від 30 до 100 вузлів, і вони можуть бути використані при проектуванні розподілу потоків на нижніх рівнях ієрархічної мережної структури. Відзна- чається, що для рішення задач розподілу потоків у децентралізованих розподілених мережах, що містять більш 200 вузлів і 12000 дуг, доцільно використовувати мережні постановки за- дач і наближені методи рішення, що істотно спираються на специфіку структури даних задач і змістовні евристичні розуміння. © V.A. Vasyanin, A.N. Trofimchyk Linear integer models of distribution of flows in problems of designing and analysis of multicommodity communication networks The models of distribution of the discrete multicommodity flows, submitted as problems of linear programming are offered in this article. The brief review of methods and the algorithms now in use for the decision of problems of a similar class is conducted. Practical use of methods of de- composition of Dantzig - Wolfe and a relaxation of restrictions Rosen for the decision of the formu- lated problems is shown, that, has allowed to establish borders of their reasonable application for real networks - from 30 up to 100 vertices, and they can be used at designing distribution of flows at the bottom levels of hierarchical network structure. It is marked, that for the decision of problems of distribution of flows in the noncentralized distributed networks, containing more of 200 vertices and 12000 arches it is expedient to use network productions of problems and the approached meth- ods of the decision, essentially basing on specificity of structure of the given problems and substan- tial heuristic reasons.

Линейные целочисленные модели распределения потоков в задачах проектирования и анализа многопродуктовых коммуникационных сетей

Institution

Ähnliche Einträge