Состоялось очередное заседание общемосковского научного семинара "МАТЕМАТИЧЕСКИЕ МЕТОДЫ АНАЛИЗА РЕШЕНИЙ В ЭКОНОМИКЕ, БИЗНЕСЕ И ПОЛИТИКЕ"

Автор доклада: Гафаров Евгений Рашидович (к.ф.-м.н., с.н.с. лаборатории №68 "Теории расписаний и дискретной оптимизации", ФГБУН Институт проблем управления РАН)
Тема: Графический метод решения задач комбинаторной оптимизации

18 декабря 2013 года в рамках очередного заседания общемосковского научного семинара "МАТЕМАТИЧЕСКИЕ МЕТОДЫ АНАЛИЗА РЕШЕНИЙ В ЭКОНОМИКЕ, БИЗНЕСЕ И ПОЛИТИКЕ" был заслушан доклад на тему "Графический метод решения задач комбинаторной оптимизации".
         Автор доклада: Гафаров Евгений Рашидович (к.ф.-м.н., с.н.с. лаборатории №68 "Теории расписаний и дискретной оптимизации", ФГБУН Институт проблем управления РАН)

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

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

Дополнительные материалы:

• Презентация доклада
• Лекция (видеозапись)

Видеозапись лекции: