Другие журналы

научное издание МГТУ им. Н.Э. Баумана

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

Издатель ФГБОУ ВПО "МГТУ им. Н.Э. Баумана". Эл № ФС 77 - 48211.  ISSN 1994-0408

Систематизация точных методов дискретной оптимизации

# 06, июнь 2015
DOI: 10.7463/0615.0778982
Файл статьи: 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
Поделиться:
 
ПОИСК
 
elibrary crossref ulrichsweb neicon rusycon
 
ЮБИЛЕИ
ФОТОРЕПОРТАЖИ
 
СОБЫТИЯ
 
НОВОСТНАЯ ЛЕНТА
18.12.2017
С 21 по 24 ноября 2017г. в МГТУ им. Н.Э. Баумана прошла XII Всероссийская инновационная молодежная научно-инженерная выставка «Политехника», посвященная 170-летию со дня рождения Н.Е. Жуковского в рамках Всероссийского инновационного молодежного научно-инженерного форума «Политехника».

11.10.2017
XII Всероссийская инновационная молодежная научно-инженерная выставка «ПОЛИТЕХНИКА», посвященная 170-летию со дня рождения Н.Е. Жуковского 21–24 ноября 2017 года г. Москва

25.05.2017
C 15 по 17 мая 2017г. в МГТУ им. Н.Э. Баумана прошел III этап (Всероссийский) Всероссийской студенческой олимпиады по физике (в технических вузах).

25.04.2017
С 12 по 14 апреля в МГТУ им. Н.Э. Баумана прошел Всероссийский этап Всероссийской олимпиады по безопасности жизнедеятельности.

4.04.2017
С 14 по 16 марта 2017г. в МГТУ им. Н.Э. Баумана прошел III (Всероссийский) тур Всероссийской студенческой олимпиады по иностранному языку (английский в технических вузах).




Авторы
Пресс-релизы
Библиотека
Конференции
Выставки
О проекте
Rambler's Top100
Телефон: +7 (915) 336-07-65 (строго: среда; пятница c 11-00 до 17-00)
  RSS
© 2003-2018 «Наука и образование»
Перепечатка материалов журнала без согласования с редакцией запрещена
 Тел.: +7 (915) 336-07-65 (строго: среда; пятница c 11-00 до 17-00)