автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Распределение ограниченных ресурсов в иерархических системах транспортного типа

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

Афраймович Лев Григорьевич

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

Специальность 05.13.18 Математическое моделирование, численные методы и комплексы программ (физико-математические науки)

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

Нижний Новгород 2006

Работа выполнена на кафедре информатики и автоматизации научных исследований Нижегородского государственного университета им. Н.И. Лобачевского

Научный руководитель: доктор технических наук, профессор

Прилуцкий Михаил Хаимович

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

доктор физико-математических наук, профессор Иорданский Михаил Анатольевич

кандидат физико-математических наук, доцент Баркалов Александр Валентинович

Ведущая организация: Институт проблем управления РАН (Москва) Защита диссертации состоится « » 1С03а)ри5ч_2006г.

в аудитории корпуса Нижегородского государственного

ас

университета им. Н.И. Лобачевского в /Ч— часов на заседании Диссертационного совета Д 212.166.13.

Заверенные отзывы просим направлять по адресу: 603600, Н. Новгород, проспект Гагарина, 23, Нижегородский государственный университет им. Н.И. Лобачевского, Диссертационный совет Д 212.166.13.

С диссертацией можно ознакомиться в фундаментальной библиотеке университета.

Автореферат разослан «IX » ОьСГП 2006г.

Ученый секретарь диссертационного совета, кандидат физико-математических наук, доцент

Савельев В.П.

Актуальность темы исследования

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

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

Рассматриваемые в диссертационной работе задачи возникают, например, при распределении энергоресурсов между поставщиками и потребителями, базового сырья при производстве строительных материалов, мощностей каналов передачи данных провайдерами сети ИНТЕРНЕТ, нагрузки распределенной вычислительной сети, объема работ производства и так далее.

Из отечественных ученых существенный вклад в развитие рассматриваемого в диссертационной работе класса задач внесли Гольштейн Е.Г., Канторович Л.В., Карзанов A.B., Подчасова Т.П., Юдин Д.Б., Шкурба В.В. и другие. Среди зарубежных ученых развитием этой области занимались Danzig G.L., Hitchcock F.L., Hu Т.С., Koopmans T.C. и другие. Следует также отметить школу Нижегородского университета и учёных Батищева Д.И., Прилуцкого М.Х., Когана Д.И., Федосенко Ю.С., которые рассматривали подобные проблемы.

Цель работы

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

Методы исследования

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

Научная новизна

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

2. Проведено исследование построенных математических моделей распределения ресурсов в иерархических системах транспортного типа, построены алгоритмы проверки совместности и поиска допустимого варианта распределения ресурсов.

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

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

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

Теоретическая и практическая значимость

В рамках построенных математических моделей описываются многие реальные прикладные задачи, связанные с проблемой распределения ресурсов. В качестве примеров можно отметить задачу распределения мощностей каналов передачи данных провайдерами сети ИНТЕРНЕТ, транспортную задачу с промежуточными пунктами, задачу объемно-календарного планирования и другие. Для решения данных задач могут применяться разработанные и программно реализованные в ходе выполнения исследования алгоритмы, позволяющие сократить объем вычислений, обеспечивая возможность решения прикладных задач достаточно большой размерности.

Апробация полученных результатов

Полученные в диссертационной работе результаты обсуждались на

Всероссийской конференции «КоГраф 2002» (Нижний Новгород, 2002 г.),

4

Международных научно-практических семинарах «Высокопроизводительные параллельные вычисления на кластерных системах» (Нижний Новгород, 2002 и 2003 г.), Нижегородских сессиях молодых ученых (Саров, 2003 и 2004 г., Нижний Новгород, 2004 г.), Научно-технической конференции ООО ТЕКОМ «Технические, программные и математические аспекты управления сложными распределенными системами» (Нижний Новгород, 2003 г.), Юбилейной научно-технической конференции ВМК ННГУ и НИИ ПМК, «Математика и кибернетика 2003» (Нижний Новгород, 2003 г.), VI международном конгрессе по математическому моделированию (Нижний Новгород, 2004 г.), Конференциях «Технологии Microsoft в теории и практике программирования» (Москва, 2005 г., Нижний Новгород, 2006 г.), Международной научной конференции, приуроченной к 200-летию со дня рождения Карла Густава Якоби (Калининград, 2005 г.), XIV международной конференции «Проблемы теоретической кибернетики» (Пенза, 2005 г.), научном семинаре отделения информатики университета г. Падерборна (Германия, г. Падерборн, 2005 г.), а также на научном семинаре кафедры информатики и автоматизации научных исследований факультета ВМК ННГУ (2006 г.).

Результаты диссертационной работы используются в учебном процессе Нижегородского государственного университета им. Н.И. Лобачевского на факультете ВМК при преподавании курса «Моделирование сложных систем»

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

Структура и объем работы

Работа состоит из введения, трех глав, заключения, списка литературы и приложения. Общий объем работы составляет 132 страницы. Список литературы включает 118 наименований.

Прилуцкий М.Х., Афраймович Л.Г. Учебно-методическая разработка по курсу "Моделирование сложных систем" при изучении темы "Распределение ресурсов в многоиндексных иерархических системах"

Публикации

Основные полученные в диссертации результаты отражены в 19 публикациях (в том числе 7 статьях, 2 из которых опубликованы в ведущих рецензируемых научных журналах). Список публикаций приведен в конце автореферата.

Краткое содержание работы

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

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

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

С иерархической системой связаны ограничения трех типов: ресурсные ограничения элементов системы, ресурсные ограничения связей между элементами системы, ограничения суммарных объемов ресурсов.

Среди множества элементов системы выделяется подмножество контролируемых элементов, с которыми связаны функции предпочтения, определяющие условия эффективного функционирования системы.

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

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

Одним из примеров задачи распределения ресурсов в одноресурсной иерархической системе является задача распределения мощностей каналов передачи

6

данных провайдерами сети ИНТЕРНЕТ; в многоресурсной иерархической системе -транспортная задача с промежуточными пунктами; в многоиндексной иерархической системе - задача объемно-календарного планирования.

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

В разделе 2.1 рассматривается случай одноресурсной иерархической системы. Иерархическую систему будем моделировать ориентированным графом <7=(Г,Л) без петель и контуров, АаУ2, множество V, \V\-n, вершин которого соответствует элементам системы, а множество А, \А\=т, дуг — связям между элементами системы. Введем вспомогательные обозначения: (),=№0У)е/*}> {/!(/,') ¿е V. Пусть Х=\\ Ху ||лхл — матрица, элемент Ху которой определяет количество

ресурсов, переданных по связи (/,/"), (//)еЛ. Ограничения на суммарные объемы

ресурсов будем задавать с использованием множества и, и с: 2А.

Общая математическая модель распределения ресурсов в одноресурсной иерархической системе транспортного типа при заданном множестве и имеет следующий вид:

где [2?*С,] - сегмент, соответствующий балансным ограничениям элемента /, ¡¡¡<СЬ ВгС,>0, /е V; - сегмент, соответствующий пропускной способности связи (/,/),

0<Оу<Еу, [Ни.,1и.] - сегмент, соответствующий ограничениям суммарного

объема ресурсов, определяемого множеством и', 0 < Ни- < 1и-, V е II.

Будем обозначать через V*, Vе и Vй множество производителей ресурсов, передающих элементов и потребителей ресурсов, соответственно.

(2.1)2

А/ ^ хи ^ Еа»

(2.2)

(2.3)

2 Нумерация формул, определений, теорем и следствий в автореферате соответствует принятой в диссертации.

Под допустимым вариантом распределения ресурсов будем понимать матрицу Х=\\ Ху ||ихл, удовлетворяющую условиям (2.1)-(2.3). В дальнейшем иерархическую

систему будем называть совместной, если для нее существует допустимый вариант распределения ресурсов.

Для исследования системы (2.1)-(2.3) могут быть использованы общие методы решения систем линейных неравенств. Однако специфика построенной математической модели позволила в некоторых частных случаях предложить более эффективные алгоритмы, основанные на сводимости к потоковым моделям.

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

Определение 3. Матрица АА' -\\ а'у ||т.хп., сводится, сохраняя соответствие

допустимости, к матрице А", А" =|| а," ||т»хл«, если существует отображение

а: {1,2,.., л'} —> {1,2,..,«"} такое, что для системы линейных неравенств вида

А'х' йЬ', обозначаемой через 5', можно построить систему линейных неравенств

вида А"х" й Ь", обозначаемую через 5", такую, что

- если х" = (х",хг>...>х"») является допустимым решением системы 5", то х' = (ха(1),хё(2)>—>ха(„')) является допустимым решением системы 5";

- система 5' не совместна, если не совместна система 5";

- все компоненты вектора Ь" целочисленны, если целочисленны все компоненты вектора Ь'.

Определение 4. Система линейных неравенств Я' сводится, сохраняя соответствие между переменными, к системе линейных неравенств Б", если матрица ограничений системы Я' сводится, сохраняя соответствие допустимости, к матрице ограничений системы 5".

Под объемом ресурсов, соответствующих элементу /, обозначаемым через у^

будем понимать следующее выражение: у{= если ¿еУ; у1 = если

¡еУсиУ". В случае, когда ограничения суммарных объемов ресурсов

представляют собой ограничения объемов ресурсов, соответствующих элементам системы, условия (2.3) имеют следующий вид:

(2.9)

где для удобства через [//»/,•] обозначается сегмент, связанный с ограничением объема ресурсов, соответствующих элементу /, 0<//,</„ /е V.

Математическая модель распределения ресурсов в одноресурсной иерархической системе с ограничениями объемов ресурсов, соответствующих элементам системы, представляет собой систему ограничений (2.1),(2.2),(2.9), исследование которой сводится к поиску допустимой циркуляции транспортной сети. Обоснование сводимости требует некоторых вспомогательных результатов. Пусть 7] = а,- каноническая транспортная сеть, в основе

которой лежит ориентированный граф С^У^О, Ух с Л,2; 5 - исток, / - сток, V; ау — пропускная способность дуги (/V)» ОУ) еЛ 1. С канонической транспортной сетью Т\ будем связывать задачу поиска максимального потока /у, (ц)еА\.

Пусть Т2 =(У2,А2>\\Ъу 11|к2|х|кг|>Ис0 Н|и2ми2|) " транспортная сеть, в основе

которой лежит ориентированный граф СгК^г^г), У2С2А%; Ьу и с у - нижняя и верхняя пропускные способность дуги (/,/'), соответственно, 0 < Ьу < с у, (¡¿)еА2. С

транспортной сетью Т2 будем связывать задачу поиска допустимой циркуляции, которая заключается в определении циркуляции gy, (¡¿)еА2, удовлетворяющей следующей системе ограничений:

(213)

а.ЛеМ2 и, У '

Ъу<,Еу^Су,(и)еА2. (2.14)

В диссертационной работе вводится понятие канонической транспортной сети Т\(Тг), соответствующей транспортной сети Т2.

Теорема 1. Для существования допустимой циркуляции транспортной сети Т2 необходимо и достаточно равенство величины максимального потока соответствующей канонической транспортной сети Т](Т2) величине Уд¿>„ .

В работе вводится понятие транспортной сети Т2(Ц), соответствующей одноресурсной иерархической системе, определимой ограничениями (2.1),(2.2),(2.9).

Теорема 2. Для совместности системы (2.1),(2.2),(2.9), необходимо и достаточно существование допустимой циркуляции в транспортной сети Т2{С).

Следствие 3. Система линейных неравенств (2.1),(2.2),(2.9) сводится, сохраняя соответствие между переменными, к системе (2.13),(2.14), связанной с транспортной сетью T2(G).

Таким образом, можно предложить метод исследования совместности одноресурсной иерархической системы с ограничениями объемов ресурсов, соответствующих элементам системы, основанный на ее сводимости к сети 7г(Сг), исследование которой связано с поиском максимального потока в сети T\{Ti(G)). Для поиска максимального потока можно воспользоваться известными алгоритмами, например, алгоритмом Карзанова3, вычислительная сложность которого 0(|Fj|3). При этом количество вершин сети T\(Ti(G)) по порядку совпадает с величиной и. Вычислительная сложность предлагаемого метода 0(п3).

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

Теорема 4. Если совместная система линейных неравенств А'х' < Ь', обозначаемая через S', сводится, сохраняя соответствие между переменными, к системе вида (2.13),(2.14), то в случае целочисленности всех компонент вектора Ь', система S" имеет целочисленное решение.

В разделе 2.2 рассматривается случай многоресурсной иерархической системы. Как и в одноресурсном случае многоресурсную иерархическую систему будем моделировать ориентированным графом G=(M), AcV2, \V\ Обозначим через К, г ^ 2, множество различных типов ресурсов. Пусть

Л^Ц xijk ||ихлхг - 3-х индексная матрица, элемент Xyk которой определяет количество

ресурсов к, переданных по связи (ij), (iJ)eA, кеК. Ограничения на суммарные

объемы ресурсов будем задавать с использованием множества U, U с 2АхК.

Общая математическая модель распределения ресурсов в многоресурсной иерархической системе при заданном множестве U имеет следующий вид:

3 См. Карзанов A.B. Нахождение максимального потока в сети методом предпотоков // ДАН СССР, 1974. Т. 215, №1. с. 49-52.

Bik ^ 2X* - Y.xjik * cik>»e кек, (2 J9)

Уе0 J6 Я/

Ад ^ ^ ^ ^» (V')e^, ¿eK, (2.20)

Fij ^ z% * Gu• ('V)Р2П

VJ.W >

где [5,fcC(*] - сегмент, соответствующий балансным ограничениям элемента /', связанным с ресурсом к, Bik<Cik, Вц-Сц^.0, /еК, ¿еЛТ; - сегмент,

соответствующий пропускной способности связи (/,/), связанной с ресурсом 0<DyiSEijk, кеК; [F^Gy] - сегмент, соответствующий суммарной пропускной

способности связи (ij), 0<Fy<Gij, (Uj)e.A; [Яу.,/^.] - сегмент, соответствующий

ограничениям суммарного объема ресурсов, определяемого множеством U', 0<Ни.<1и., U'eU.

Под допустимым вариантом распределения ресурсов будем понимать 3-х индексную матрицу Х=\\Хук ||Л)<ИХГ, удовлетворяющую условиям (2.19)-(2.22). Через

Vk , Vk и Vk будем обозначать множества производителей, передающих элементов и потребителей ресурсов к, соответственно, кеК.

Под объемом ресурсов к, соответствующих элементу /, обозначаемым через yjk,

будем понимать следующее выражение:^ = ^Хук, если, iеVk, yik = ^xjik, если

jeß jeR,

i e Vk kj Vk , ke.K. ■ В случае иерархической системы с ограничениями объемов ресурсов, соответствующих элементам системы, ограничения (2.22) имеют следующий вид:

Hik<ylk<Iik,ieV,keK, (2.23)

где через [Hik,Iik] обозначается сегмент, связанный с ограничением объема ресурсов

к, соответствующих элементу /, 0<Hik<Iik, ie V, кеК.

В частном случае многоресурсной иерархической системы с ограничениями

объемов ресурсов, соответствующих элементам системы, при отсутствии суммарных

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

имеет вид (2.19),(2.20),(2.23). В работе показано, что система линейных неравенств

(2.19),(2.20),(2.23) сводится, сохраняя соответствие между переменными, к системе

11

вида (2.13),(2.14). При этом предлагаемый алгоритм исследования совместности рассматриваемой иерархической ' системы, основанный на сводимости к транспортной сети, имеет вычислительную сложность 0(г«3).

Особый интерес представляют многоресурсные древовидные иерархические системы. Здесь предполагается, что граф G=(V^4) является ориентированным деревом, корень которого соответствует единственному в системе источнику ресурсов, листья — потребителям ресурсов, остальные вершины — передающим элементам.

В работе вводится понятие транспортной сети 7г(г), соответствующей многоресурсной древовидной иерархической системе с ограничениями объемов ресурсов, соответствующих элементам системы.

Теорема 5. Система ограничений (2.19)-(2.21),(2.23) в случае древовидной иерархической системы сводится, сохраняя соответствие между переменными, к системе (2.13),(2.14), связанной с транспортной сетью Т2(г).

Таким образом можно предложить метод исследования совместности рассматриваемой иерархической системы, основанный на ее сводимости к сети Гг(г), исследование которой связано с поиском максимального потока в сети Г1(Г2(г)). Для поиска максимального потока можно воспользоваться известными алгоритмами, например, алгоритмом Слейтора и Тарьяна4, вычислительная сложность которого 0(| У, || Ах | log | Vx I). При этом количество вершин и количество дуг сети Т\(Т2{г)) по порядку совпадают с величиной nr. Вычислительная сложность предлагаемого метода 0(n2r2 log(wr)).

В разделе 2.3 рассматривается случай многоиндексной иерархической системы. Для построения математической модели воспользуемся следующей формализацией. Пусть N(s) = {l,2,...,s}. Каждому числу / поставим в соответствие параметр j¡, называемый индексом, j¡ eJ¡ = {1,2,...,/:,}, и, £2, I e N(s). Пусть / = {Aj,&2 ♦—»*,}> f сN(s). Набор значений индексов Ff=(Jki,jkl,...,jkl) будем называть /-индексом, а множество всех /-индексов будем обозначать через Er = Jkx xJk:¡ x...xJki, / = l,s. Пусть каждому набору поставлено в соответствие действительное число zF , Fy еЕ,. Совокупность таких чисел для всех возможных

4 Cm. Sleator D.D., Tarjan R.E. A data structure for dynamic trees U J. Comput. Syst. Sci., 26, 1983. pp. 362-391.

значений индексов Л,»Л2»—»Л, назовем /-индексной матрицей и обозначим через

{zjkyjk2.....jki } = {z/r/}. Пусть f — N(s)\ f, тогда через F=Fy Fj будем обозначать s-

индексный набор (Л, >Л2 '—.У*, .—»Л,)• Введем следующие обозначения:

Z Z X - Z

Общая математическая модель распределения ресурсов в многоиндексной иерархической системе имеет следующий вид:

X xF/F_*b^,F7eEj,feM, (2.31)

FfeEf

где М — заданное множество, A/c2JV(,); а p., bF_ - заданные параметры,

О £ а ¡у ^ , Fy eEj, f еМ; {дс/г} - j-индексная матрица действительных

неотрицательных неизвестных. Систему (2.31) будем обозначать через D(M).

Под допустимым вариантом распределения ресурсов будем понимать s-индексную матрицу {х/г}, удовлетворяющую системе ограничений D(M).

Теорема 6. Для того, чтобы система ограничений £>{М) сводилась, сохраняя соответствие между переменными, к системе вида (2.13),(2.14), достаточно, чтобы существовало такое разбиение Л/, = {/,(1),/2(1).....М2 = {^(2),/2<2),-,Д2)}

множества М, для которого /,(|) с /¡Ц, / = 1, т1 -1 и //2) с , i = l,m2 -1.

Доказательство теоремы 6 основано на конструктивном построении транспортной сети Т2{М), к исследованию которой сводится система D(M).

При выполнении условий теоремы 6 можно предложить метод исследования совместности многоиндексной иерархической системы, основанный на ее сводимости к сети Т2(М), исследование которой связано с поиском максимального потока в сети 7|(Гг(Л0), для чего можно воспользоваться, например, алгоритмом Слейтора и Тарьяна. При этом количество вершин и количество дуг сети Т\(Т2(М)) по порядку совпадают с величиной | EN^ |. Вычислительная сложность предлагаемого

метода 0(| EN(i) |2 log | EN{s) |).

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

Будем рассматривать задачу распределения ресурсов на примере одноресурсной иерархической системы.

Среди множества элементов системы выделим подмножество контролируемых элементов Р, РсУ, \P\~d. Тогда будем считать, что каждый из контролируемых элементов / задает на соответствующем ему сегменте [//,,/, ] бинарное отношение, отражающее его предпочтение относительно соответствующего ему объема ресурсов, /еР. Зададим бинарное отношение в виде функции предпочтения Х( (У() > определенной на сегменте [//,, /, ], /еР.

Задача заключается в определении такого допустимого варианта распределения ресурсов, для которого принимают экстремальные значения функции предпочтения контролируемых элементов:

*еА (3.1)

Заметим, что в случае многоресурсной иерархической системы предполагается, что Рс:УхК, и функция предпочтения задается на сегменте [Нл, 1Л], (1,к)еР. В случае многоиндексной иерархической системы для заданного множества /р, /р^М, предполагается, что Р сг Еу-, и функция предпочтения Хг—

задается на сегменте \ар__, Ър_ ], .Р-^- е Р.

В разделе 3.1 рассматривается случай аддитивной схемы компромисса и линейных функций предпочтения. При этом задача распределения ресурсов обозначается через Щ (№\(М) в случае многоиндексной иерархической системы).

При заданном параметре г/,- в качестве функции предпочтения будем рассматривать следующую линейную функцию %({у{) — сI,>>,, / е Р.

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

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

Будем обозначать через L\ задачу поиска потока заданной величины минимальной стоимости в канонической транспортной сети Т\\ через Lz - задачу поиска циркуляции минимальной стоимости в транспортной сети Т2.

Теорема 7. Задача W\ в случае одноресурсной иерархической системы с ограничениями объемов ресурсов, соответствующих элементам системы, сводится, сохраняя соответствие между переменными, к задаче Ь2.

Следствие 5. Задача W\ в случае многоресурсной иерархической системы с ограничениями объемов ресурсов, соответствующих элементам системы, при отсутствии суммарных пропускных способностей связей сводится, сохраняя соответствие между переменными, к задаче L2.

Теорема 8. Задача W\ в случае многоресурсной древовидной иерархической системы с ограничениями объемов ресурсов, соответствующих элементам системы, сводится, сохраняя соответствие между переменными, к задаче Ь2.

Теорема 9. Для того, чтобы задача W\(M) сводилась, сохраняя соответствие между переменными, к задаче Ь2, достаточно, чтобы существовало такое разбиение

множества М на подмножества М, = {fxl\f2\-.,f^} и М2 = {/|(2),/2<2\->/„(,2>},

для которого //" с /¿у, i = l,ml -1 и //2) с f™, i = \,m2 -1.

В работе вводится понятие задачи L\(L2), соответствующей задаче Ь2 и определенной на сети ^(Jj).

Теорема 10. Пусть поток/является решением задачи L](L2), тогда циркуляция g, gy =/у + by, (iJ)eA2, будет являться решением задачи L2.

Для решения задачи L\(L2) можно воспользоваться известными алгоритмами, например, алгоритмом Галиля и Тардоша5, вычислительная сложность которого

0(| Fj |2 log | Vx | (| Л, | +1 Vx | log | I)). Тогда в случае сводимости задачи W\ к задаче

Ь2, мы получаем эффективные алгоритмы решения задачи JV,.

Более того, в случае сводимости задачи W\ к задаче L2 целочисленное решение задачи W\ может быть найдено за полиномиальное время, обоснованием чего является следующая теорема:

5 Cm. Galil Z., Tardos E. An 0(n2 log n(m + n log n)) min-cost flow algorithm // In Proc. 27th IEEE

Symp. of Foundations of Computer Science, 1986. pp. 1-9.

15

Теорема 11. Если задача линейного программирования Р сводится, сохраняя соответствие между переменными, к задаче ¿2, то матрица ограничений задачи Р абсолютно унимодулярна.

В разделе 3.2 в качестве схемы компромисса рассматривается лексикографическое упорядочивание, в качестве функций предпочтения — кусочно-постоянные функции. При этом задача распределения ресурсов обозначается через 1¥2. Введем для каждого из контролируемых элементов / совокупность из /Я-1

вложенных друг в друга сегментов Я}0, t = 0,p. При этом Я}'* ст / = 0, р -1,

= [#,,/,], ¡еР. В качестве функции предпочтения рассмотрим кусочно-постоянную функцию х*(У*»5/0)у,...,), принимающую значение если

Рассмотрим (р+1)-ичный ¿/-мерный куб, на котором определим порядок П. Каждой вершине куба г поставим в соответствие систему С (г), содержащую не зависящие от вершины куба ограничения математической модели распределения ресурсов и ограничения, зависящие от' вершины 2 следующим образом: для

Р = »2.»•»*'</}> если то ^ у = 1,с/. На множестве вершин куба

зададим двузначную функцию g(z), принимающую значение 1, если система С (г) совместна и 0 в противном случае. В качестве порядка П рассмотрим лексикографическое отношение порядка: IхПг2 тогда и только тогда, когда для некоторого /, /= 1, (I, г) < г} и одновременно — г2 дляу = 1, / -1.

Задача РГ2 заключается в поиске оптимальной вершины куба 2° такой, что 5(2°) = 1, и выполняются условия: г0Пг для всех вершин куба, для которых g{z)= 1. Предлагаемый алгоритм решения задачи включает в себя

0(d\og2(p + \)) проверок совместности системы вида С(£). Для проверки совместности системы С(£) могут быть применены методы, предложенные в главе 2.

В разделе 3.3 в качестве схемы компромисса рассматривается максиминная (минимаксная) схема, в качестве функций предпочтения — кусочно-постоянные и линейные функции предпочтения. При этом задача распределения ресурсов

обозначается через Цг3тттт (Ж3т1птах ).

В случае кусочно-постоянных функций предпочтения предлагается алгоритм решения задачи {у3тахт,п> который включает в себя <9(1о§2(р +1)) проверок совместности системы С (г).

В случае линейных функций предпочтения при решении задачи щтахтш

вводится вспомогательная система Стахтт(с1'), содержащая ограничения математической модели распределения ресурсов и ограничения, зависящие от параметра Ы' следующим образом:

у,<,аЧс1пЫР. (3.4)

В работе предлагается алгоритм поиска решения, значение критерия на котором отклоняется от оптимального значения критерия задачи }У3тах тш не более чем на е. Данный алгоритм требует 0(1о§2(шах£/4/</£)) проверок совместности системы

¡еР

Стахт,п(^'), для чего могут быть применены методы, предложенные в главе 2.

При этом общая схема решения задачи IV™'"тах аналогична схеме решения задачи ^3тахгЫп.

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

Основные результаты

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

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

17

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

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

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

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

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

Публикации по теме диссертации

1. Афраймович Л.Г. Минимизация затрат при распределении однородного ресурса в иерархических системах с двусторонними ограничениями // КоГраф 2002. Материалы докладов всероссийской конференции.-Нижний Новгород, 2002. с. 81-83.

2. Прилуцкий М.Х., Афраймович Л.Г. Параллельные алгоритмы распределения ресурсов в иерархических системах с лексикографическим упорядочиванием элементов // Материалы второго Международного научно-практического семинара «Высокопроизводительные параллельные вычисления на кластерных системах». — Нижний Новгород: Издательство Нижегородского госуниверситета, 2002. с. 243-248.

18

3. Афраймович JI.Г. Задачи распределения однородного ресурса в иерархических системах // VIII Нижегородская сессия молодых ученых. Математические науки. Тезисы докладов. Саров, 2003. с 41-42.

4. Афраймович Л.Г. Модифицированные потоковые алгоритмы распределения однородного ресурса в иерархических системах // Математика и кибернетика 2003. Сборник научных статей юбилейной научно-технической конференции факультета ВМК ННГУ и НИИ ПМК. Нижний Новгород, 2003. с. 23-25.

5. Афраймович Л.Г. Потоковые алгоритмы распределения ресурсов в иерархических системах // Тезисы докладов НТК «Технические, программные и математические аспекты управления сложными распределенными системами». Нижний Новгород, 2003. с. 6.

6. Прилуцкий М.Х., Афраймович Л.Г. Параллельные структуры потоковых и итерационных алгоритмов распределения ресурса в иерархических системах // Материалы третьего Международного научно-практического семинара «Высокопроизводительные параллельные вычисления на кластерных системах». -Нижний Новгород: Издательство Нижегородского госуниверситета, 2003. с. 140-145.

7. Афраймович Л.Г. Оптимальные преобразования перестраиваемых иерархических систем распределения однородного ресурса // IX Нижегородская сессия молодых ученых. Математические науки. Тезисы докладов. Саров, 2004. с 6-7.

8. Афраймович Л.Г. Задачи распределения однородного ресурса в многоуровневых иерархических системах // IX Нижегородская сессия молодых ученых. Технические науки. Тезисы докладов. Нижний Новгород, 2004. с. 5-6.

9. Прилуцкий М.Х., Афраймович Л.Г. Оптимальное распределение однородного ресурса в иерархических системах с доходами // Вестник ВГАВТ. Межвузовская серия Моделирование и оптимизация сложных систем, 2004. Вып. 9. с. 56-63.

10. Afraimovich L.G. Generalized model of homogeneous resource distribution in hierarchy systems // VI International congress on mathematical modeling. Book of abstracts. Nizhny Novgorod, 2004. p. 65.

11. Афраймович Л.Г. Оптимальное распределение однородного ресурса в задачах управления производством // Технологии Microsoft в теории и практике программирования. Труды Всероссийской конференции студентов, аспирантов и молодых ученых. Центральный регион. - М.: Издательство МГТУ им Н.Э. Баумана, 2005. с. 31-32.

12. Афраймович Л.Г. Проблема существования решения в многоресурсных иерархических системах // Вестник ВГАВТ. Межвузовская серия Моделирование и оптимизация сложных систем, 2005. Вып. 14. с. 122-127.

13. Afraimovich L.G. Reconstructing hierarchy systems of homogeneous resource distribution // Избранные вопросы современной математики: Тез. Междунар. науч. конф., приуроченной к 200-летию со дня рождения Карла Густава Якоби -Калининград: Изд-во КГУ, 2005. с 64-66.

14. Афраймович Л.Г. Сведение системы линейных неравенств транспортного типа к задаче поиска максимального потока в сети при дополнительных ограничениях // Проблемы теоретической кибернетики. Тезисы докладов XIV Международной конференции.— М.: Изд-во механико-математического факультета МГУ, 2005. с. 13.

15. Прилуцкий М.Х., Афраймович Л.Г. Условия совместности многоиндексных систем транспортного типа // Электронный журнал "Исследовано в России", 70, 2005. с. 762-767. http://zhurnal.ape.relarn.ru/articles/2005/070.pdf

16. Афраймович Л.Г. Распределение ресурсов в иерархических системах транспортного типа с ограничениями. Построение математических моделей и их исследование // Труды НГТУ. Системы обработки информации и управления, 2005. Т. 45, Вып. 23. с. 27-34.

17. Афраймович Л.Г., Прилуцкий М.Х. Сводимость задачи распределения ресурсов в иерархических системах древовидной структуры к потоковым задачам // Технологии Microsoft в теории и практике программирования. Материалы конференции. -Нижний Новгород: Изд-во Нижегородского госуниверситета, 2006. с. 25-26.

18. Афраймович Л.Г. Потоковые алгоритмы исследования совместности иерархических систем распределения ресурсов с ограничениями // Вестник Нижегородского государственного университета. Математическое моделирование и оптимальное управление, 2006.2(31). с. 129-138.

19. Афраймович Л.Г., Прилуцкий М.Х. Многоиндексные задачи распределения ресурсов в иерархических системах // Автоматика и телемеханика, 2006. №6. с. 194-205.

\

Подписано в печать 09.10.2006. Формат 60x84 1/16. Бумага офсетная. Печать офсетная. Усл. печ. л. 1. Зак. 1434. Тир. 100.

Типография Нижегородского госуниверситета. Лиц. ПД № 18-0099 от 04.05.2001. 603000, Н. Новгород, ул. Б. Покровская, 37.

ВВЕДЕНИЕ.

ГЛАВА 1. ОПТИМИЗАЦИОННЫЕ ЗАДАЧИ РАСПРЕДЕЛЕНИЯ РЕСУРСОВ В ИЕРАРХИЧЕСКИХ СИСТЕМАХ.И

1.1. МЕСТО ЗАДАЧ РАСПРЕДЕЛЕНИЯ РЕСУРСОВ В КЛАССЕ ЗАДАЧ МАТЕМАТИЧЕСКОГО ПРОГРАММИРОВАНИЯ.

1.1.1. Задачи распределения ресурсов как задачи математического программирования.

1.1.2. Задачи распределения ресурсов как задачи выпуклого программирования.

1.1.3. Задачи распределения ресурсов как задачи линейного программирования транспортного типа.

1.2. ЗАДАЧИ РАСПРЕДЕЛЕНИЯ РЕСУРСОВ В ИЕРАРХИЧЕСКИХ СИСТЕМАХ.

1.2.1. Иерархические системы транспортного типа.

1.2.2. Распределение ресурсов в иерархических системах.

1.2.3. Эффективность функционирования иерархических систем.

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

1.3.1. Одноресурсные задачи распределения в иерархических ситсемах транспортного типа.

1.3.2. Многоресурсные задачи распределения в иерархических системах транспортного типа.

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

ВЫВОДЫ.

ГЛАВА 2. МАТЕМАТИЧЕСКИЕ МОДЕЛИ РАСПРЕДЕЛЕНИЯ ОГРАНИЧЕННЫХ РЕСУРСОВ В ИЕРАРХИЧЕСКИХ СИСТЕМАХ ТРАНСПОРТНОГО ТИПА.

2.1. ОДНОРЕСУРСНЫЕ ИЕРАРХИЧЕСКИЕ СИСТЕМЫ.

2.1.1. Общая математическая модель распределения ресурсов в одноресурсных иерархических системах транспортного типа.

2.1.2. Исследование общей математической модели распределения ресурсов в одноресурсных иерархических системах транспортного типа.

2.1.3. Исследование математической модели распределения ресурсов в одноресурсных иерархических системах древовидной структуры.

2.2. МНОГОРЕСУРСНЫЕ ИЕРАРХИЧЕСКИЕ СИСТЕМЫ.

2.2.1. Общая математическая модель распределения ресурсов в многоресурсных иерархических системах транспортного типа.

2.2.2. Исследование общей математической модели распределения ресурсов в многоресурсных иерархических системах транспортного типа.

2.2.3. Исследование математической модели распределения ресурсов в многоресурсных иерархических системах древовидной структуры.

2.3. МНОГОИНДЕКСНЫЕ ИЕРАРХИЧЕСКИЕ СИСТЕМЫ.

2.3.1. Общая математическая модель распределения ресурсов в многоиндексных иерархических системах транспортного типа.

2.3.2. Исследование общей математической модели распределения ресурсов в многоиндексных иерархических системах транспортного типа.

2.3.3. Сводимость математической модели распределения ресурсов в многоиндексных иерархических системах транспортного типа к потоковым моделям.

Выводы.

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

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

3.1.1. Сводимость задачи распределения ресурсов в иерархических системах транспортного типа с аддитивными схемами компромисса к потоковым задачам.

3.1.2. Применение сводимости для построения алгоритмов решения задачи распределения ресурсов в иерархических системах транспортного типа с аддитивными схемами компромисса.

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

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

3.2.1. Формализация лексикографического упорядочивания частных критериев оптимальности как схемы компромисса при решении задачи распределения ресурсов в иерархических системах транспортного типа.

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

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

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

3.3.1. Алгоритмы решения задачи распределения ресурсов в иерархических системах транспортного типа с максиминными схемами компромисса в случае кусочно-постоянных частных критериев оптимальности.

3.3.2. Алгоритмы решения задачи распределения ресурсов в иерархических системах транспортного типа с максиминными (минимаксными) схемами компромисса в случае линейных функций предпочтения.

3.3.3. Алгоритмы решения задачи целочисленного распределения ресурсов в иерархических системах транспортного типа с максиминными (минимаксными) схемами компромисса в случае линейных частных критериев оптимальности.

Выводы.Ill

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

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

Подобного рода задачи возникают, например, при распределении энергоресурсов между поставщиками и потребителями, базового сырья при производстве строительных материалов, мощностей каналов передачи данных провайдерами сети ИНТЕРНЕТ, нагрузки распределенной вычислительной сети, объема работ производства и так далее.

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

Из отечественных ученых существенный вклад в развитие рассматриваемого в диссертационной работе класса задач внесли Голынтейн Е.Г., Канторович JI.B., Карзанов A.B., Подчасова Т.П., Юдин Д.Б., Шкурба В.В. и другие. Среди зарубежных ученых развитием этой области занимались Danzig G.L., Hitchcock F.L., Hu T.C., Koopmans T.C. и другие. Следует также отметить школу Нижегородского университета и ученых Батищева Д.И., Прилуцкого М.Х., Когана Д.И., Федосенко Ю.С., которые рассматривали подобные проблемы.

Цель работы

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

7 Научная новизна

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

2. Проведено исследование построенных математических моделей распределения ресурсов в иерархических системах транспортного типа, построены алгоритмы проверки совместности и поиска допустимого варианта распределения ресурсов.

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

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

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

Теоретическая и практическая ценности работы

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

Проведенные исследования выполнены в рамках Задания Минобразования РФ, номер госрегистрации 0120.0 506816 (2003-2006 гг.) -Тема НИР "Математическое моделирование и создание новых методов анализа динамических систем и систем оптимизации ".

Результаты диссертационной работы используются в учебном процессе

Нижегородского государственного университета им. Н.И. Лобачевского на факультете ВМК при преподавании курса «Моделирование сложных систем».

Апробаций результатов

Полученные в диссертационной работе результаты обсуждались на Всероссийской конференции «КоГраф 2002» (Н.Новгород, 2002 г.), Международных научно-практических семинарах «Высокопроизводительные параллельные вычисления на кластерных системах» (Н.Новгород, 2002 и 2003 г.), Нижегородских сессиях молодых ученых (Саров, 2003 и 2004 г.,

Нижний Новгород, 2004 г.), Научно-технической конференции ООО ТЕКОМ «Технические, программные и математические аспекты управления сложными распределенными системами» (Н.Новгород, 2003 г.), Юбилейной научно-технической конференции ВМК ННГУ и НИИ ПМК, «Математика и кибернетика 2003» (Н.Новгород, 2003 г.), VI международном конгрессе по математическому моделированию (Н.Новгород, 2004 г.), Конференциях «Технологии Microsoft в теории и практике программирования» (Москва, 2005 г., Н.Новгород, 2006 г.), Международной научной конференции, приуроченной к 200-летию со дня рождения Карла Густава Якоби (Калининград, 2005 г.), XIV международной конференции «Проблемы теоретической кибернетики» (Пенза, 2005 г.), научном семинаре отделения информатики университета г. Падерборна (Германия, г. Падерборн, 2005 г.), а также на научном семинаре кафедры информатики и автоматизации научных исследований факультета ВМК ННГУ (2006 г.).

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

Основные результаты, полученные в ходе выполнения диссертационной работы, отражены в 19 научных работах [3-15,56-59,81,82].

Структура и содержание работы

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

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

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

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

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

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

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

Основные результаты диссертационной работы заключаются в следующем.

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

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

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

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

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

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

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

Заключение

1. Адельсон-Вельский Г.М., Диниц Е.А., Карзанов А.В. Потоковые алгоритмы. - М.: Наука, 1975. - 120 с.

2. Акоф Р., Сасиени М. Основы исследования операций. М.: Наука, 1971, 534 с.

3. Афраймович Л.Г. Задачи распределения однородного ресурса в иерархических системах // VIII Нижегородская сессия молодых ученых. Математические науки. Тезисы докладов. Саров, 2003. с 41-42.

4. Афраймович Л.Г. Задачи распределения однородного ресурса в многоуровневых иерархических системах // IX Нижегородская сессия молодых ученых. Технические науки. Тезисы докладов. Нижний Новгород, 2004. с. 5-6.

5. Афраймович Л.Г. Минимизация затрат при распределении однородного ресурса в иерархических системах с двусторонними ограничениями // КоГраф 2002. Материалы докладов всероссийской конференции. -Нижний Новгород, 2002. с. 81-83.

6. Афраймович Л.Г. Оптимальные преобразования перестраиваемых иерархических систем распределения однородного ресурса // IX

7. Нижегородская сессия молодых ученых. Математические науки. Тезисы докладов. Саров, 2004. с 6-7.

8. Афраймович Л.Г. Потоковые алгоритмы распределения ресурсов в иерархических системах // Тезисы докладов НТК «Технические, программные и математические аспекты управления сложными распределенными системами». Нижний Новгород, 2003. с. 6.

9. Афраймович Л.Г. Проблема существования решения в многоресурсных иерархических системах // Вестник ВГАВТ. Межвузовская серия Моделирование и оптимизация сложных систем, 2005. Вып. 14. с. 122127.

10. Афраймович Л.Г. Распределение ресурсов в иерархических системах транспортного типа с ограничениями. Построение математических моделей и их исследование // Труды НГТУ. Системы обработки информации и управления, 2005. Т. 45, Вып. 23. с. 27-34.

11. Афраймович Л.Г., Прилуцкий М.Х. Многоиндексные задачи распределения ресурсов в иерархических системах // Автоматика и телемеханика, 2006. №6. с. 194-205.

12. Афраймович Л.Г., Прилуцкий М.Х. Сводимость задачи распределения ресурсов в иерархических системах древовидной структуры к потоковым задачам // Технологии Microsoft в теории и практике программирования.

13. Материалы конференции. Нижний Новгород: Изд-во Нижегородского госуниверситета, 2006. с. 25-26.

14. Ашманов С.А. Линейное программирование. М.: Наука, 1981. - 304 с.

15. Баркалов П. С., Буркова И.В., Глаголев A.B., Колпачев В.Н. Задачи распределения ресурсов в управлении проектами.-М.:ИПУ РАН, 2002-65с.

16. Берзин Е. А. Оптимальное распределение ресурсов и теория игр. -М.: Радио и связь, 1983. 216 с.

17. Берзин Е. А. Оптимальное распределение ресурсов и элементы синтеза систем. -М.: Советское радио, 1974. 302 с.

18. Букан Д.Ф., Кенигсберг Э. Научное управление запасами. М.: Наука, 1967.-423 с.

19. Васильев В.П. Методы решения экстремальных задач. Учебное пособие. М.: Наука. Главная редакция физико-математической литературы, 1981.-400 с.

20. Воронин A.A., Мишин С.П. Оптимальные иерархические структуры. -М.: ИЛУ РАН, 2003.-214 с.

21. Габасов Р., Кириллова Ф.М. Методы линейного программирования. Ч. 2. Транспортные задачи. Мн.: БГУ, 1977. - 237 с.

22. Габасов Р., Кириллова Ф.М. Методы линейного программирования. Ч. 3. Специальные задачи. Мн.: БГУ, 1980. - 368 с.

23. Гейл Д. Теория линейных экономических моделей.-М.:Мир, 1969.-342 с.

24. Голынтейн Е.Г., Соколов H.A. Новый метод решения многопродуктовой транспортной задачи // Экономика и математические методы, 1995. Т. 31. Вып. 2. с. 128-136.

25. Голыптейн Е.Г., Юдин Д.Б. Задачи линейного программирования транспортного типа. М.: Наука, 1969. - 382 с.

26. Голыптейн Е.Г., Юдин Д.Б. Новые направления в линейном программирование. М.: Советское радио, 1966. - 524 с.

27. Гофман А.Д., Краскал Д.Б. Целочисленные граничные точки выпуклых многогранников // Линейные неравенства и смежные вопросы. М.: ИЛ, 1959. с. 325-347.

28. ГуринЛ.С., Дымарский Я.С., Меркулов А.Д. Задачи и методы оптимального распределения ресурсов. М.: Советское радио, 1968. -463 с.

29. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982. - 416 с.

30. Давыдов Э.Г. Исследование операций. М.: Высшая школа, 1990. -383 с.

31. Дементьев В. Т., Ерзин А. И., Ларин Р. М., Шамардин Ю. В. Задачи оптимизации иерархических структур. Новосибирск: Изд-во Новосибирского университета, 1996. - 168 с.

32. Емеличев В.А., Ковалев М.М., Кравцов М.К. Многогранники, графы, оптимизация. М.: Наука. 1981. - 344 с.

33. Жиров B.C. Решение игровой задачи распределения дискретных ресурсов // Автоматика и телемеханика, 1981. №6. с. 109-114.

34. Зуховицкий С.И., Авдеева Л.И. Линейное и выпуклое программирование. М.: Наука, 1964. - 460 с.

35. Канторович Л.В. Математические методы организации и планирования производства // Применение математики в экономических исследованиях, Т. 2, М., Соцэкгиз, 1961. с. 251-309.

36. Канторович Л.В. Экономический расчет наилучшего использования ресурсов. М.: Из-во АН ССР, 1960. - 347 с.

37. Карзанов A.B. Нахождение максимального потока в сети методом предпотоков // ДАН СССР, 1974. Т. 215. №1. с. 49-52.

38. Ковалев М.М. Матроиды в дискретной оптимизации. М.: Едиториал УРСС, 2003.-224 с.

39. Козырев А.Н. Оптимизация распределения ресурсов в системе линейных моделей производства // Оптимизация. Сборник трудов. Новосибирск. 1975. Вып. 16(33), с. 62-72.

40. Корбут A.A., Финкелыптейн Ю.Ю. Дискретное программирование. М.: Наука, 1969.-368 с.

41. Кузнецов Ю.Н., Кузубов В.И., Волощенко А.Б., Математическое программирование. М.: Высшая школа, 1980. - 302 с.

42. Кузнецов A.B., Холод H.H. Математическое программирование. Мн.: Высшая школа, 1984.-221 с.

43. Литвак Б.Г., Раппопорт A.M. Задачи линейного программирования, допускающие сетевую постановку // Экономика и математические методы, 1970. Т. 6. Вып. 4. с. 594-604.

44. Макеев С.П., Серов Г.П., Шахнов И.Ф. Модель процесса координации в линейной задаче распределения ресурсов. М.:ВЦ АН СССР, 1984. - 47с.

45. Маршак В.Д. Алгоритм решения задачи распределения ресурсов в отрасли// Оптимизация. Сборник трудов. Новосибирск, 1973. Вып. 10(27). с.128-143.

46. Майника Э. Алгоритмы оптимизации на сетях и графах. М.: Мир, 1981. -323 с.

47. Месарович М., Мако Д., Такахара И. Теория иерархических многоуровневых систем. М.: Мир, 1973. - 342 с.

48. Многокритериальная оптимизация: Математические аспекты / Березовский Б.А., Барышников Ю.М., Борзенко В.И., Кемпнер JIM. -М.: Наука, 1989.- 128 с.

49. Нейман Д., Моргенштерн О. Теория игр и экономическое поведение. -М.: Наука, 1970.-707 с.

50. Пападимитриу X., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. М.: Мир, 1985. - 510 с.

51. Прилуцкий М.Х. Математическая модель многокритериального распределения ресурсов на сетях и условие ее разрешимости // Принятиеоптимальных решений в экономических системах. Горький, 1985. с. 62-65.

52. Прилуцкий М.Х. Многокритериальное распределение однородного ресурса в иерархических системах // Автоматика и телемеханика, 1996. №2. с.24-29.

53. Прилуцкий М.Х., Афраймович Л.Г. Оптимальное распределение однородного ресурса в иерархических системах с доходами // Вестник ВГАВТ. Межвузовская серия Моделирование и оптимизация сложных систем, 2004. Вып. 9. с. 56-63.

54. Прилуцкий М.Х., Афраймович Л.Г. Условия совместности многоиндексных систем транспортного типа // Электронный журнал "Исследовано в России", 70, 2005. с. 762-767.http://zhurnal.ape.relarn.ru/articles/2005/070.pdf

55. Прилуцкий М.Х., Батищев Д.И., Гудман Э.Д., Норенков И.П. Метод декомпозиций для решения комбинаторных задач упорядочения и распределения ресурсов // Информационные технологии, №2. Москва, 1999, с. 29-32.

56. Прилуцкий М.Х., Картомин А.Г. Потоковые алгоритмы распределения ресурсов в иерархических системах // Электронный журнал "Исследовано в России", 39, 2003 г. с. 444-452. http://zhurnal.ape.relarn.ru/articles/2003/039.pdf

57. Прилуцкий М.Х., Нефедов Д.С., Попов Д.В. Распределение ресурсов в дискретно управляемых системах // Электронный журнал "Исследовано в России", 032/020228, 2002. с. 322-337. http://zhurnal.ape.relarn.ru/articles/2002/032.pdf

58. Прилуцкий М.Х., Рапопорт И.А. Распределение ограниченных ресурсов в иерархических компьютерных системах // Сборник трудов ВятГТУ. -Киров: ВятГТУ, 2000. с. 67-72.

59. Прилуцкий М.Х., Фомина И.А. Распределение однородного ресурса в многоуровневых иерархических системах // Анализ и проектирование систем управления производством. Н.Новгород: Нижегородский университет, 1992. с. 23-30.

60. Пшеничный Б.Н. Выпуклый анализ и экстремальные задачи. М.: Наука, 1980.-319 с.

61. Раскин Л.Г., Кириченко И.О. Многоиндексные задачи линейного программирования. М.: Радио и связь, 1982. - 240 с.

62. Строцев А.А., Долотина Ю.И. Распределение ресурсов в условиях конфликта // Электронный журнал "Исследовано в России", 77, 2005. с. 839-847. http://zhurnal.ape.relarn.ru/articles/2004/077.pdf

63. Схрейвер А. Теория линейного и целочисленного программирования: в 2 т. Т. 1.-М.: Мир, 1991.-360 с.

64. Схрейвер А. Теория линейного и целочисленного программирования: в 2 т. Т. 2.-М.: Мир, 1991.-702 с.

65. Фань Ц. О системе линейных неравенств // Линейные неравенства и смежные вопросы. -М.: ИЛ, 1959. с. 214-262.

66. Филлипс Д., Гарсиа-Диас А. Методы анализа сетей. М.: Мир, 1984. -496 с.

67. Форд Л., Фалкерсон Д. Потоки в сетях. М.: МИР, 1966. - 276 с.

68. Хачиян, Л.Г. Полиномиальные алгоритмы в линейном программировании // ДАН СССР, том 244, вып. 5. 1979. с. 1033-1096.

69. Хедли Дж., Уайтин Т. Анализ систем управления запасами. М.: Наука, 1969.-511 с.

70. Ху Т. Целочисленное программирование и потоки в сетях. М.: Мир, 1974.-519 с.

71. Черников С.Н. Линейные неравенства. М.: Наука, 1968. - 488 с.

72. Юдин Д.Б. Методы количественного анализа сложных систем //1. ИАН СССР, техн. киберн., 1965, №1, с. 3-13.

73. Юдин Д.Б., Голынтейн Е.Г. Линейное программирование (теория, методы и приложения). М.: Наука, 1968. - 424 с.

74. Afraimovich L.G. Generalized model of homogeneous resource distribution in hierarchy systems // VI International congress on mathematical modeling. Book of Abstracts. Nizhny Novgorod, 2004. p. 65.

75. Agmon S. The relaxation method for linear inequalities // Caned. J.Moth. 1954. V. 6. №3. P. 382-392.

76. Ahuja R.K., Magnati T.L., Orlin J.B. Network flows: theory, algorithms, and applications. Prentice Hall. 1993.

77. Assad A.A. Multicommodity network flows a survey // Networks, Vol. 8, 1978. pp. 37-91.

78. Cherkassky В. V., Goldberg A. V. Negative-cycle detection algorithms // In Proc. 4th European Symp. on Algorithms, 1996, pp. 349-363.

79. Dantzig G.B. Application of the simplex method to a transportation problem // Activity analysis of production and allocation. New York. Wiley, 1951, pp. 359-373.

80. Deikmann R., Frommer A., Monien B. Efficient schemes for nearest neighbor load balancing // Parallel Computing, 25, 1999. pp. 789-812.

81. Fleischer L.K. Faster algorithms for the quickest transshipment problem // SIAM Journal on Optimization, 2001, Vol.12, No.l, pp.18 -35.

82. Ford L.R., Fulkerson D.R. A Simple Algorithm for Finding Maximal Network Flows and an Application to the Hitchcock Problem // Canadian Journal of Mathematics 9, 1957. pp. 210-218.

83. Ford L. R., Fulkerson D. R. Constructing maximal dynamic flows from static flows // Operations Research, 1958, Vol. 6, pp. 419-433.

84. Gairing M., Lucking Т., Mavronicolas M., Monien B. Computing Nash Equilibria for Scheduling on Restricted Parallel Links // Proc. 36th Annual ACM Sympos. Theory Comput. 2004. P. 613-622.

85. Galil Z., Tardos E. An 0(n log n(m + nlogn)) min-cost flow algorithm // In

86. Proc. 27th IEEE Symp. of Foundations of Computer Science, 1986, pp. 1-9.

87. Gleyzal A. An algorithm for solving the transportation problem // Journal of Research National Bureau of Standards, 54, 1955. pp. 213-216.

88. Goldberg A.V., Rao S. Beyond the flow decomposition barrier // Journal of the ACM, Vol. 45, N. 5, 1998, pp. 783-797.

89. Goldberg A. V., Tarjan R. E. Solving minimum-cost flow problems by successive approximation // Mathematics of Operations Research, 1990, Vol. 15, No. 3, pp. 430-466.

90. Gomory R.E., Hu T.C. Multi-terminal network flows // SIAM Journal of Applied Mathematics, Vol. 9, 1971, pp. 551-571.

91. Grinold R.C. Calculating maximal flows in a network with positive gains // Operations Research, Vol. 21, 1973, pp. 528-451.

92. Hitchcock F.L. The distribution of a product from several sources to numerous locations // Journal of Mathematics and Physics, Vol. 20, 1941, pp. 224-230.

93. Itai A. Two-Commodity Flow // Journal of the ACM, Vol. 25, N. 4, 1978, pp. 596-611.

94. Jewell W.J. Optimal flows through networks with gains // Operations Research, Vol. 10,1962, pp. 476-499.

95. Kamath A., Palmon O. Improved interior point algorithms for exact and approximate solution of multicommodity flow problems // Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, 1995, pp. 502511.

96. Kampke T. The geometry of linear infeasibility // Applied Mathematics and Computation, vol. 29, no. 2-3, 2002, pp. 317-337.

97. Karmarkar N. A new polynomial-time algorithm for linear programming // Combinatorica, Vol. 4, 1984, pp. 373-395.

98. Kennington J.L. A survey of linear cost multicommodity network flows // Operations Research, Vol. 26, 1978, pp. 206-236.

99. Koopmans T.C. Optimum utilization of the transportation systems. Econometrica 17,1949. pp. 136-146.

100. Koopmans T.C., Reiter S. A model of transportation // Activity Analysis of Production and Allocation, Wiley, New York, 1951, pp. 222-259.

101. Koutsoupias E., Papadimitrou C. Worst-case equilibria // In Proc. Of the 16th Int. Symposium on Theoretical Aspects of Computer Science, 1999, pp. 404413.

102. Luss H. Minimax resource allocation problem: optimization and parametric analysis // European Journal of Operational Research, V. 60, 1992, pp. 76-86.

103. Land A.H. A problem in transportation // Conference on Linear Programming, Ferranti Ltd., London, 1954, pp. 20-31.

104. Motzkin T.S., Schoenberg I.J. The relaxation method for linear inequalities // Caned. J. Moth. 1954. V. 6. №3. P.393-404.

105. Munkres J. Algorithms for the assignment and transportation problems // Journal of the Society for Industrial and Applied Mathematics, 5, 1957. pp. 32-38.113.0rden A. The transshipment problem // Manag. Sci. 2, N. 3, 1956, pp. 276285.

106. Santos C., Zhu X., Crowder H. A Mathematical Optimization Approach for Resource Allocation in Large Scale Data Centers // Tech. Rep. HP-2002-64, Hewlett Packard Laboratories, Palo Alto, USA, 2002.

107. Sleator D.D., Tarjan R.E. A data structure for dynamic trees // J. Comput. Syst. Sci., 26, 1983. pp. 362-391.

108. Tucker A.W. Linear and nonlinear programming // Operation Research, V. 5, N. 2, 1957. pp. 244-257.

109. Xue G., Sun S., Rosen B. Fast data transmission and maximal dynamic flow // Information Processing Letters, 1998, Vol.66, pp. 127-132.

110. Zadeh N. A bad network problem for the simplex method and other minimum cost flow algorithms // Mathematical Programming, 5, 1973, 255-266.