НАУКА и ОБРАЗОВАНИЕ

Файл статьи: SE-BMSTU...o304.pdf (703.33Кб)

УДК 004.02+519.1

Россия,  МГТУ им. Н.Э. Баумана

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

1. Нечепуренко М.И., Попков В.К., Майнагашев С.М., Кауль С.Б., Проскуряков В.А., Кохов В.А., Грызунов А.Б. Алгоритмы и программы решения задач на графах и сетях. Новосибирск: Наука. Сиб. отд-ние , 1990. 515 с.
2. Асанов М.О., Баранский В.А., Расин В.В. Дискретная математика: графы, матроиды, алгоритмы. Ижевск: НИЦ «Регулярная и хаотическая динамика», 2001. 288 с.
3. Ахо А.В., Хопкрофт Д.Э., Ульман Д.Д. Структуры данных и алгоритмы: пер. с англ. М.: Издат. дом Вильямс, 2001. 384 с.
4. Галкина В.А. Дискретная математика: комбинаторная оптимизация на графах: учеб. пособие по специальностям "Компьютер. безопасность", "Комплекс. обеспечение информ. безопасности автоматизир. систем" и "Информ. безопасность телекоммуникац. систем". М.: Гелиос АРВ, 2003. 232 с.
5. Гудман С., Хидетниеми С. Введение в разработку и анализ алгоритмов: пер. с англ. М.: Мир, 1981. 368 с.
6. Дивеев А.И., Северцев Н.А. Метод выбора оптимального варианта технической системы. М.: ВЦ РАН, 2003. 106 с.
7. Кормен Т., Лейзерсон Ч., Риверст Р. Алгоритмы: построение и анализ: пер. с англ. М.: МЦНМО, 2000. 960 с.
8. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера. М.: Энергоатомиздат, 1988. 480 с.
9. Новиков Ф.А. Дискретная математика для программистов. СПб.: Питер, 2001. 304 с.
10. Овчинников В.А. Алгоритмизация комбинаторно-оптимизационных задач при проектировании ЭВМ и систем: учеб. для вузов. М.: Изд-во МГТУ им. Н.Э. Баумана, 2001. 288 с.
11. Овчинников В.А. Графы в задачах анализа и синтеза структур сложных систем. М.: Изд-во МГТУ им. Н.Э. Баумана, 2014. 423 с.
12. Сигал И.Х., Иванова А.П. Введение в прикладное дискретное программирование: модели и вычислительные алгоритмы: учеб. пособие. М.: ФИЗМАТЛИТ, 2002. 240 с.
13. Артюхин В.В. Прогнозирование чрезвычайных ситуаций с помощью дискретной оптимизации и современных программных средств // Технологии гражданской безопасности. 2014. Т. 11, № 1 (39). С. 86-91.
14. Ведерников Ю.В., Гарькушев А.Ю., Сазыкин А.М. Математическая формализация задачи оптимального построения информационно-управляющего комплекса мониторинга критически важных объектов // Вопросы оборонной техники. Сер. 16: Технические средства противодействия терроризму. 2014. № 1-2. С. 26-31.
15. Джамрад М., Романченко О.А., Толстикова О.Н. Размещение объекта обслуживания населения на основе метода дискретной оптимизации // Управление большими системами: сб. тр. 2006. № 14. С. 123-134.
16. Домке Э.Р., Жесткова С.А., Акимова В.Ю. Особенности решения задачи маршрутизации транспорта методом «ветвей и границ» // Вестник Московского автомобильно-дорожного государственного технического университета (МАДИ). 2012. № 2. С. 76-79.
17. Дюбин Г.Н., Корбут А.А. Асимптотика жадных методов для задач о ранце: обзор и новые результаты // Обозрение прикладной и промышленной математики. 2008. Т. 15, № 4. С. 744a-746.
18. Забиняко Г.И., Котельников Е.А. Параллельные вычисления в некоторых задачах дискретной оптимизации // Математическое моделирование. 2009. Т. 21, № 9. С. 99-107.
19. Иванко Е.Е. Метод динамического программирования в минимаксной задаче распределения заданий с равноценными исполнителями // Вестник Южно-Уральского государственного университета. Сер. Математическое моделирование и программирование. 2013. Т. 6, № 1. С. 124-133.
20. Колпаков Р.М., Посыпкин М.А. Верхняя и нижняя оценки трудоемкости метода ветвей и границ для задачи о ранце // Дискретная математика. 2010. Т. 22, № 1. С. 58-73.
21. Мещеряков Г., Дроженко В. Применение методов дискретной оптимизации для синтеза структур систем менеджмента // РИСК: Ресурсы, информация, снабжение, конкуренция. 2012. № 1. С. 39-41.
22. Посыпкин М.А., Си Ту Тант Син. Сравнительный анализ эффективности различных вариантов метода динамического программирования для решения оптимизационных задач на этапе размещения элементов микросхем // Всероссийская научно-техническая конференция «Проблемы разработки перспективных микро- и наноэлектронных систем (МЭС)»: сб. тр. Ч. 2. 2014. С. 97-100.
23. Салий Я.В. Влияние условий предшествования на вычислительную сложность решения маршрутных задач методом динамического программирования // Вестник Удмуртского университета. Математика. Механика. Компьютерные науки. 2014. № 1. С. 76-86.
24. Табуров Д.Ю. Решение задач оптимизации вычислительного процесса в локальных сетях информационно-измерительных и управляющих систем с использованием метода ветвей и границ // Приборы. 2010. № 7. С. 50-56 .
25. Dzieli´nski A., Przemysław M. Computer algorithms for solving optimization problems for discrete-time fractional systems // Proc. of the 2013 European Control Conference (ECC), July 17-19, 2013, Zürich, Switzerland. P. 4009-4014.
26. Pardalos P.M., Rodgers G.P. Computational aspects of a branch and bound algorithm for quadratic zero-one programming // Computing. 1990. Vol. 45, iss. 2. P. 131-144. DOI: 10.1007/BF02247879