Введение к работе
Актуальность темы. Потоковые задачи на сетях вызывают неизмешго большой интерес в течение нескольких последних десятилетий. Это связано с возможностью широкого их применения в области оптимизации работы реально существующих сетевых систем (транспортных структур, коммуникационных систем и др.). За это время достигнуты определешпле успехи в решеїши одпопродуктовых потоковых задач. Для многих задач этого класса были разработаны специальные эффективные потоковые алгоритмы их решения. Однако наибольший практический интерес представляют многопродуктовые потоковые задачи. В таких задачах необходимо передать по одной сети одновременно несколько независимых потоков, относящихся к различным видам продуктов, соблюдая ограничения на суммарный поток продуктов, передаваемый по любой отдельно взятой дуге. Наличие таких связывающих ограничений не позволяет в общем случае решать эти задачи с помощью известных потоковых алгоритмов, применяемых для решения однопродуктовых задач. В то же время большая размерность многопродуктовых задач создает серьезные трудности в использовании аппарата линейного программирования. Таким образом актуальным является поиск классов многопродуктовых задач, для которых применимы потоковые алгоритмы, а также поиск различных путей использования сетевой структуры многопродуктовых задач при решении их методами линейного программирования.
Целью работы является исследование линейной задачи синтеза многопродуктовой коммуникационной сети - многопродуктОЕой задачи минимизации стоимости распределения ресурса при условии удовлетворения заданного спроса, в которой пропускные способности дуг, объем предложения и потребления каждого продукта являются линейными
функциями от вложенных ресурсов. В результате анализа предполагается определить частные случаи линейной задачи сгаггеза многопродуктовой коммуникационной сети, которые возможно решать при помощи потоковых алгоритмов. Для общего случая задачи целью исследования является разработка нового алгоритма ее решения, основанного на методах линейного программирования и декомпозиции и использующего сетевую структуру задачи.
Научная новизна. Для рассматриваемых задач синтеза многопродуктовой сети предложена обобщенная методика сведения однородной многопродуктовои задачи к набору однопродуктовых задач. Неоднородная задача формализована как задача линейного программирования со специальной структурой. Это позволило применить к ней метод разбиения и использовать ее сетевую структуру.
Практическая зпачнмость. В связи с развитием информационно-вычислительных и коммушпсациоїшьіх сетей в последнее время все более насущными становятся задачи огггимизации синтеза многопродуктовых сетей. Данная диссертационная работа посвящена решению линейной задачи развития многопродуктовои сети. Такая задача может быть использована как подзадача для решения задачи стггеза реальной сети связи после соответствующей линеаризации вогнутой функции цели. Методы исследования базируются на основных положениях исследования операций, используются методы линейного программирования, теории потокового программирования и методы оптимизации больших систем. Апробация. Основные результаты докладывались на научно-исследовательских семинарах Института математики СО РАН, ИВВС РАН и кафедры Исследования операций ВМК МГУ.
Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения, списка литературы и приложения. Содержит 95 страниц текста, включая приложение и список литературы ш 52 наименований.
?