Распределение ограниченных ресурсов в иерархических системах транспортного типа тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат физико-математических наук Афраймович, Лев Григорьевич

• Афраймович, Лев Григорьевич
• кандидат физико-математических наук
• 2006

Оглавление диссертации кандидат физико-математических наук Афраймович, Лев Григорьевич

ВВЕДЕНИЕ.

ГЛАВА 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 рассматривается общая многокритериальная задача распределения ресурсов в иерархических системах транспортного типа. В качестве схем компромисса при решении многокритериальной задачи распределения ресурсов рассматриваются аддитивные свертки в случае линейных функций предпочтения; лексикографическое упорядочивание в случае кусочно-постоянных функций предпочтения; а также максиминные (минимаксные) свертки в случае линейных или кусочно-постоянных функций предпочтения. Строятся алгоритмы решения рассматриваемых задач. Определяются классы задач, для которых построенные алгоритмы позволяют находить целочисленное решение.

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

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

Заключение диссертации по теме «Математическое моделирование, численные методы и комплексы программ», Афраймович, Лев Григорьевич

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

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

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

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

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

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

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

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

Заключение

Список литературы диссертационного исследования кандидат физико-математических наук Афраймович, Лев Григорьевич, 2006 год

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.