Некоторые задачи терии синтеза многопродуктовых сетей тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

од

- * СЕН 1997

РОССИЙСКАЯ АКАДЕМИЯ НАУК ИНСТИТУТ ВЫСОКОПРОИЗВОДИТЕЛЬНЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ

На правах рукописи

МИХАЙЛОВА Ирина Александровна

УДК 519.85

НЕКОТОРЫЕ ЗАДАЧИ ТЕОРИИ СИНТЕЗА МНОГОПРОДУКТОВЫХ СЕТЕЙ

(01.01.09 - Математическая кибернетика)

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

Москва 1997

Работа выполнена на факультете вычислительной математики и кибернетики Московского государственного университета им. М.ВЛомоносова

Научный руководитель:

кандидат физико-математических наук, доцент Э.ГДавыдов

Официальные оппоненты:

доктор физико-математических наук, доцент Н.М.Новикова кандидат физико-математических наук Н.С.Васильев

Ведущая организация:

Институт математики им. СЛ.Соболева СО РАН.

Защита диссертации состоится "."997 г. ъ^/.... ч. на заседании диссертационного совета К200.45.01 Института высокопроизводительных вычислительных систем РАН по адресу: 117312, Москва, ул. Вавилова, 37, к. 6.

С диссертацией можно ознакомиться в библиотеке ИВВС РАН.

Автореферат разослан "¿..".^^^7.^1997 г.

Ученый секретарь

Диссертационного совета

кандидат физико-математических наук

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. Потоковые задачи на сетях вызывают неизменно большой интерес в течение нескольких последних десятилетий. Это связано с возможностью широкого их применения в области оптимизации работы реально существующих сетевых систем (транспортных структур, коммуникационных систем и др.). За это время достигнуты определенные успехи в решении одпопродуктовых потоковых задач. Для многих задач этого класса были разработаны специальные эффективные потоковые алгоритмы их решети. Однако наибольший практический интерес представляют многопродуктовые потоковые задачи. В таких задачах необходимо передать по одной сети одновременно несколько независимых потоков, относящихся к различным видам продуктов, соблюдая ограничения на суммарный поток продуктов, передаваемый по любой отдельно взятой дуге. Наличие таких связывающих ограничений не позволяет в общем случае решать эти задачи с помощью известных потоковых алгоритмов, применяемых для решения одпопродуктовых задач. В то же время большая размерность многопродуктовых задач создает серьезные трудности в использовании аппарата линейного программирования. Таким образом актуальным является поиск классов многопродуктовых задач, для которых применимы потоковые алгоритмы, а также поиск различных путей использования сетевой структуры многопродуктовых задач при решении их методами линейного программирования.

Целыо работы является исследование линейной задачи синтеза многопродуктовой коммуникационной сети - шюгопродуктОЕой задачи минимизации стоимости распределения ресурса при условии удовлетворения заданного спроса, в которой пропускные способности дуг, объем предложения и потребления каждого продукта являются линейиыми

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

Научная новизна. Для рассматриваемых задач синтеза многопродуктовой сети предложена обобщенная методика сведения однородной многопродуктовой задачи к набору однопродуктовых задач. Неоднородная задача формализована как задача линейного программирования со специальной структурой. Это позволило применить к ней метод разбиения и использовать ее сетевую структуру.

Практическая значимость. В связи с развитием информационно-вычислительных и коммушпеационных сетей в последнее время все более насущными становятся задачи оптимизации синтеза многопродуктовых сетей. Дшшая диссертациоиная работа посвящена решению линейной задачи развития многопродуктовой сети. Такая задача может быть использована как подзадача для решения задачи синтеза реальной сети связи после соответствующей линеаризации вогнутой функции цели. Методы исследования базируются на основных положениях исследования операций, используются методы линейного программирования, теории потокового программирования и методы оптимизации больших систем. Апробация. Основные результаты докладывались на научно-исследовательских семинарах Института математики СО РАН, ИВВС РАН и кафедры Исследования операций ВМК МГУ.

Структура и объем работы. Диссертация состоит из введения, четырех глав, закшочеш1я, списка литературы и приложения. Содержит 95 страниц текста, включая приложение и список литературы из 52 наименований.

СОДЕРЖАНИЕ РАБОТЫ

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

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

В п.1.1 рассматривается модель традиционной оптимизационной задачи на многопродукговой сети - задача о многопродуктовом потоке минимальной стоимости. Наряду с этой моделью рассматривается модель, к которой сводится поставленная в работе задача оптимального распределения ресурсов на многопродуктовой сети.

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

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

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

Многопродуктовая сеть задается на ориентированном графе С(А,М) с И вершинами А={аь...,аь}, и т направленными дугами, образующими множество М упорядоченных пар (а„а])3 где аь А (которые обозначим соответствующим множеством пар целых чисел {(у)}=.1). По сети необходимо передать К продуктов, каждый из которых может как производиться, так и не производиться в каждой го вершин графа. Каждой вершине а, (¡^13...,Ь) для каждого продукта к (к=1,...,К) поставлены в соответствие функции предложения и потребления к-го продукта в ¡-й вершине, линейно зависящие от вложенных в инфраструктуру производства и потребления средств.

Кроме того заданы пропускные способности дуг сети: %(^У))=с(чЖУ)+11<ч)> с(уМ Х(У)й0. (У)^ - функции, линейно

зависящие от затраченных на развитие дуги (У) средств - Х(у>.

Требуется произвести, передать и потребить некоторое задаЕшое количество к-го продукта - к=1,...,К, так, чтобы стоимость

распределенного ресурса была минимальной.

Доказана возможность сведения поставленной задачи к задаче с одним источником и одним стоком для каждого продукта. Для этого вводится К фиктивных вершин производства 15 К фиктивных вершин потребления. Всего в сети будет Ь+2К вершин. По дугам, исходящим из источника некоторого продукта (а также дугам, входящим в сток некоторого продукта), проходит только этот продукт, причем величина пропускной способности этих дуг равна предложению продукта в вершине, в которую эта дуга впадает (или потребности в продукте в вершине, из которой эта дуга исходит).

Пусть А - множество вершин в полученной сети. Исходя га всего вышесказанного, ясно, что мы имеем сеть с тремя видами вершин: 1) аь...,ак, где ^-источник, производящий ¡-йпродукт;

2) ак+ь -.ак+ь- промежуточные вершины, принадлежащие исходному графу;

3) ак+ь+1,...,а2юь - стоки, причем сток а^ пршшмает только 1-й продукт.

Соответственно имеется три вида дуг:

1) (У) при г=1,...,К; ]=К+1,...,К+Ь, исходящие из источника 1-го продукта;

2) промежуточные дуги (У)е.Г, где соответствующие дугам исходного графа;

3) дуги (У) при г=К+1,...,К+Ь; ]=К+Ы-1,...,2К+Ь, идущие в сток к-го продукта, к=]-К-Ь.

Показано, что на модифицированной сети задача может быть формализована следующим образом:

пипЕхяп (2.1)

к V ..к I ' . „., п

{Ук,! = к; О , ¡ = К+1,...К+Ь; М

-Ук, 1 =К+Ь+к; к=1,...,К

О < /(к,з> < (1(^)5 к=1,...,К; ]=К+1,...,К+Ь; (2.3)

о < Еу ¡^ < С(и) Хр Л + с1(У); - а,})е .1; (2.4) к=1

О ^ к)^ С(цК+Ь+к) Х(цК+Ь+к) + ¿(¡.К+Ь+к)

¡=К+1,...,К+Ь;к=1,...,К; (2.5) Для решения задачи необходимо найти векторы:

%={х(ц) | по всем дугам (У)};

<И/(Ч> I (¡=М=К+1,..,К+Ь;

¡=К+1„„К+Ь, ]=К+Ь+к) , к=1,..,К}.

Где П(1), С(1) - множество всех дуг, соответственно входящих и выходящих из вершины а^ - дуговой поток по дуге (у) к-го продукта (по дугам, исходящим из источшпса ак, проходят потоки Уд^) только к-го продукта, к=1,..,К; .¡-К+1,..,К+1]; по дугам, входящим в сток ак+ьа ироходяг потоки У&к^к) только к-го продукта, МО-1,..,К+Ь; к=1,..,К).

Многопродуктовая задача (2.1)-(2.5) является задачей линейного программирования особой природы. Она имеет блочно-диагональную структуру со связывающими ограничениями. Блочно-диагональную структуру образуют матрицы инцидентности дуг-вершин в уравнениях (2.2к), а неравенства (2.4), которые ограничивают суммарный поток через каждую дугу в сети, являются связывающими. В общем случае для решения такой линейной задачи применимы алгоритмы, использующие методы декомпозиции или методы прямого разбиения, но учет сетевой специфики поставленной задачи позволяет их улучшить.

В п.2.2 выделен и рассмотрен класс задач однородного линейного синтеза многопродуктовой сети. В этом случае задача сведена к набору однопродуктовых задач. Каждая однопродуктовая задача решена эффективным методом потокового программирования.

Рассматривается случай, когда функции

^^(чЯЧУЬ (*1<ч)=0). 1=1,..,К; ¿=К+1,..,К+Ь; (У)е Л;

*СчГ Ьы>; (С(ч)=0, с1(У)= Ь(Ц)), 1=К+1,..,К+Ь; ]=К+Ь+1,..,2К+Ь. Этот случай является более интересным, чем полностью однородный, и соответствует тому, что спрос па к-й продукт в ¿-ой вернише исходного графа фиксировал и равен (Случай нефиксированного спроса

решается аналогично).

Для того, чтобы потребности на все продукты удовлетворялись, накладывается ограничение:

К+Ь j к+п

К+Ь

I

1=К+1

(2.6)

Показано, что решение исходной К-продуктовой задачи (2.1)-(2.6) может быть получено из решашя К одпопродуктовых задач линейного программирования:

К+Ь

тт Г Е хк + Е хк 1

?,Г ]=К+1 0ч> (у)Е .7 о^

(2.12)

ЕК V К

У(Г}) - 2

к Г ^

= 4 0,1

^к, • = к; О , ¡ = К+1,...К+Ь; = К+Ь+к;

О </(у) < с(и)хк(и);

]=К+1,..,К+Ь;

(У)е ^

о < у (!,к+ь+к) ^ Ь|>К+ь+к = Ь|; ¡=К+1,...,К+Ь; К+Ь

где Ук > Е Ь; ;

¡=К+1

Требуется найти векторы

2к= { х(% | ¡=к; ]=К+1,..,К+Ь; (¡,])еЛ);

(У)е^

¡=К+1 ,..,К+Ь, ¿=К+Ь+к }.

(2.13)

(2.14)

(2.15)

(2.16) (2.17)

Доказана теорема:

Теорема 2.1. Векторы решения задачи (2.1)-(2.6) % , "Ц тождественны

л л

векторам "X , получаемым из векторов решений соответствующих

Л л л

однопродуктовых задач (2.12) - (2.17) % , Ц , где % является

л ,

совокупностью векторов % , а

хк(М), ^и1=к=1,..,К;]=К+1,..,К+Ь; (2.18)

л К л

*(Ц) =Е Ал)? при (Ц)еЛ (2.19)

к=1

Каждая однонродуктовая задача (2.12)-(2.17) может быть решена нахождением кратчайшего пути из источника в каждую вершину исходного графа, если считать 1/С(^) длиной дуги (у). Необходимый поток Ь ^ к-го продукта в К+Ь+к стоке нужно пропустить но кратчайшему пути, соединяющему к-й источник и вершину ¡; к=1,...,К; ¡=К+1,...,К+1т. Сложность алгоритма равна ЗКЬ2.

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

В п.3.1 исходная задача (2.1)-(2.6) зшшсывается в матричном виде:

шах - (х,е) ЕкЕк/-Сл:+н = {!

ОЛ

(3.8к) к=1,..,К

(3.7)

(3.6)

/> О, к=1,..,к л:> 0 , «> О .

(3.10)

(3.9)

где >,к - вектор дуговых потоков к-го продукт;!, к=1,..,К; л: - вектор стоимости размерности то, соответствующий дугам всего графа С; с =

продукта; ук - вектор (Ук,0,..,0,-Ук) размерности Ь+2, Ек - матрица идентичности, определяющая соответствие между дугами исходного графа и дугами его подграфа, в котором передается к-й продукт, к=1,..,К; (1 -вектор размерности ш0, соответствующий всем дугам графа; С -диагональная матрица [тохто], с диагональными элементами равными коэффициентам с^) из функции пропускной способности соответствующей дуги (у); и - вектор несущественных переменных размерности Шо; Н'*=(и>0,и>1,..,и>к) - вектор двойственных переменных для задачи двойственной к задаче (З.б)-(З.Ю), где IV0 - вектор, соответствующий строкам огршшчений (3.7), и»"4 - вектор, соответствующий строкам офаничешш (3.8к), к=1,..,К.

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

(1,..,1) размерности тпо; Вк- матрица инцидентности дуг-вершш! для к-го

ч

Перед тем, как начать алгоритм, необходимо найти допустимый вектор для двойствегаюй задачи и>°. Очевидно, что в качестве такого допустимого вектора можно взять >у°=(0,..,0).

Шаг 0.

Пусть начальное допустимое и»0 задано. Поставим К подзадач (3.153.17), которые в дальнейшем будем обозначать 1к, к=1,..,К.

шах (- м>° Ек)^к (3.15)

ВУ'=ук, (3.16)

/>0, (3.17)

Если для некоторого к подзадача 1к не имеет допустимого решеиия,

то исходная задача (3.1)-(3.5) также не имеет допустимого решения - копей алгоритма.

Иначе - решим эти подзадачи и найдем базисные дуговые потоки _укв:

/в= (В'в)1 Ук - (В^У1 В\Л, (3.18)

где = 0 - множество небазисных дуг для каждого к=1,..,К, Вкв - базис матрицы Вк, ВкК - соответствующие небазиспые столбцы матрицы Вк (считаем, что в матрице Вк все строки линейно независимы).

(Если м>° - нулевой вектор, то необходимо найти любой допустимый вектор дуговых потоков >'к. Это может быть сделано обычной процедурой прямого симплекс метода или с помощью алгоригма построения покрывающего дерева базисных дуг, содержащего произвольный путь из источника в сток к-го продукта.)

Шаг 1.

Итак, пусть ^в - базисное решение задачи 1к, соответствующее базису Вкв матрицы Вк; >,кы - вектор небазисных элементов вектора

Кроме того введем два множества индексов Фк= {ф | (ук)ф- базисный элемент) и Ч/к= {у | (У% - небазисный элемент}

к к

и договоримся сохранять нумерацию индексов вектора у для векторов у „ и /ы(элемент (Д = (Л)*, если БеФк; и (ук)5 = (Д)5, если яеЧ'к).

Используем выражение (3.18) для исключения переменных у д го связывающих ограничений (3.7) исходной задачи. Получим задачу П

(3.19М3.24):

шт(х,е) (3.19)

ЕкК\Д-Сх + 1* = <Г,к=1,..,К (3.20) где 1*к = Е\ - Екв(Вкв)4 Вки

<Г=<1- 2кЕкв(Вкв)"1ук (3.21)

Л>0, к=1,..,К ... (3.23)

л: > 0, и > 0 (3.24)

(Екв - столбцы матрицы Ек, соответствующие базисным координатам вектора >'к, Ек» - столбцы, соответствующие небазисш>1м координатам вектора У1).

Шаг 2.

Решим задачу П (3.19)-(3.24) и соответствующую ей двойственную. В результате получаем решение: (к=1,..,К), х', и'} (/ - номер итеращш), и соответствующий этому решению вектор двойственных переменных м"'.

Обозначим через Ь1" множество индексов положительных дуговых потоков Ь1" = {11 (Д), >0} с Ч'1".

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

тогда исходная задача не имеет допустимых решений - решения нет. Конец алгоритма. Иначе - шаг 3.

Шаг 3.

Для каждого к=1,..,К в соответствии с (3.18) вычислим пересмотренные базисные потоки ^'"в- Если з7^ ■ нулевой вектор, то очевидно, что для этого к базисные потоки изменять не нужно.

Пусть =01 (У"в)] <0} с Фи.

Если .1к1 = 0 д ля к=1,..,К, то шаг 5. Иначе шаг 4.

Шаг 4.

Для любого к, для которого необходимо произвести изменение базиса задачи 1ь:

Столбец йг, матрицы Вк, где г={] | тюДО^ДОЛОг (У"в^)}, ^-Г1"} выводится ш базиса. Вводится столбец где БеЬ1".

Это изменение переопределит базис Вкв задачи 1к и вектор базисных дуговых потоков >'кв = (В1^)'1^. Такое изменение правомерно, так как справедлива Теорема 3.1:

Если Л имеет одну или более отрицательных компонент, то существует альтернативное оптимальное решение подзадачи 1к такое, что соответствующий ему базис может быть получеп из Вкв процедурой (*).

Шаг 5.

а) Справедлива Теорема 3.2:

Вектор уи является оптимальным решением задачи (З.б)-(ЗЛО) тогда и только тогда, когда У"в> 0.

То есть, если Iй = 0 (то есть уив > 0) для к=1,..,К, то тогда задача (З.б)-(З.Ю) решена и вектор (у1^, Л, к=1,..,К, х!) является ее решением. Решение получено. Коней алгоритма.

Ь) Если хотя бы для одного к=1,..,К изменение базиса подзадачи]* было сделано, вернуться к шагу 1.

Вышеприведенный алгоритм позволяет получать решешге задачи (З.б)-(ЗЛО), причем справедлива Теорема 3.3:

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

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

В п.3.4 рассматривается, как применение метода разбиения к поставленной многопродуктовой задаче позволяет сохранять и использовать ее сетевую структуру. На каждой итерации алгоритма решается последовательность отдельных подзадач для каждого продукта. Каждая подзадача является однонродуктовой потоковой задачей на минимум стоимости, и к ней применимы извесгные эффективные потоковые алгоритмы. Кроме того базисное множество дут для каждой подзадачи образует дерево, и рассмотришь^ базисные потоки могут быгь вычислены с помощью увеличения потока через небазисные дуги и восстановления потоков на базисных дугах; для этого достаточно знать дерево базисных дут, поток на этих базисных дугах и множество меток вершин, входящих в дерево.

В п.3.5 разобран случай заданного фиксированного производства и потребления каждого продукта.

п

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

Рассмотренные алгоритмы решения многопродукговых однородной и неоднородной задач были реализованы в виде комплекса программ в среде языка программирования Borland Pascal 7.0 на персональном компьютере ЮМ РС-АТ 486. Тексты программ приведены в приложении. На базе реализованных алгоритмов проводились численные эксперименты. Их результаты приведены в трех таблицах. Они свидетельствуют об принципиальной применимости предложенных методов решения поставленных задач.

ОСПОВНЫЕ РЕЗУЛЬ ТАТЫ

К основным результатам, полученным в диссертации, относятся следующие:

1. В работе поставлена задача оптимального распределения ресурсов на многопродукговой сети. Выделен класс задач линейно-однородного синтеза многопродуктовых сетей, для которых удалось разработать эффективный метод решения. Решение К-продуктовой задачи линейно-однородного синтеза сведено к задачам поиска дерева кратчайших путей для однопродуктовых сетей.

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

Основные результаты диссертантги опубликованы в работах:

1. Михайлова И. А. Обобщение теоремы Форда-Фалкерсона на мультиграф. Вести. Моск. Ун-та. Сер. 15, Вычисл. матем. и киберн., 1994, №4, с. 2831.

2. Михайлова И.А. Некоторые частные задачи сшггеза многопродуктовых сетей. Вестн. Моск. Ун-та. Сер. 15, Вычисл. матем. и киберн., 1995, №2, с. 48-53.

3. Давыдов Э.Г., Михайлова И.А. Задача линейно-неоднородного сшггеза многопродуктовых сетей. - Вестн. Моск. Ун-та. Сер. 15, Вычисл. матем. и киберн., 1997, №2, с.40-42.