WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!

Pages:     ||
|

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

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

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

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

, iP.

(3.4)

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

При этом общая схема решения задачи аналогична схеме решения задачи.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

8. Афраймович Л.Г. Задачи распределения однородного ресурса в многоуровневых иерархических системах // IX Нижегородская сессия молодых ученых. Технические науки. Тезисы докладов. Нижний Новгород, 2004. c. 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.


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

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

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

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

5 См. Galil Z., Tardos E. An min-cost flow algorithm // In Proc. 27th IEEE Symp. of Foundations of Computer Science, 1986. pp. 1-9.

Pages:     ||
|



© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.