Приближенные алгоритмы. Полиномиальные алгоритмы построения приближенных решений с оценками точности. Асимптотически точные алгоритмы на детерминированных и случайных входах. Полиномиальные вполне и полиномиальные аппроксимационные схемы. Примеры аппроксимационных схем.
Задачи маршрутизации. Сложность построения приближенных решений с гарантированной оценкой точности для задачи коммивояжера. Алгоритмы локального поиска и их свойства. Алгоритм локального поиска с чередующимися окрестностями. Нижние оценки для задачи коммивояжера. Задача о назначениях и алгоритм ее решения. Задача коммивояжера с временными окнами.
Модели календарного планирования. Алгоритмы вычисления параметров сетевой модели. Задачи с директивными сроками и ресурсными ограничениями. Т-поздние расписания. Полиномиальный алгоритм задачи со складируемыми ресурсами. Стохастическая постановка задачи и вероятность завершения проекта к заданному сроку.
Задачи о покрытии и метод Лагранжевых релаксаций. Дискретные задачи размещения. Алгоритм Хватала и его погрешность. Алгоритм Хошбаум. Генетический алгоритм для дискретных задач размещения.
Задачи раскроя и упаковки. Приближенные алгоритмы с оценками и аппроксимационные схемы для задачи упаковки в контейнеры..Алгоритм имитации отжига на примере задачи двумерной упаковки прямоугольников. Математические модели гильотинного раскроя, раскроя кругов и прямоугольников в угол и полосу минимальной длины.
Игровые задачи размещения. Равновесия по Нэшу. Сложность нахождения равновесных решений. Трудоемкость алгоритмов локального улучшения. Цена анархии и цена стабильности.
Задачи двухуровневого программирования и равновесия Штаккельберга. Задача о центроиде. NP-трудность частных случаев. Задачи на цепи и деревьях. Метод генерации столбцов. Вероятностные алгоритмы поиска с запретами.
ЛИТЕРАТУРА
Гимади Э.Х., Глебов. Н.И. Математические модели и методы принятия решений. Учебное пособие, НГУ, 2008 .
Гимади Э.Х., Глебов Н.И., Перепелица В.А. Алгоритмы с оценками для задач дискретной оптимизации. Сб."Проблемы кибернетики", вып.31. --- М.: Наука, 1975
Гимади Э.Х.. О некоторых математических моделях и методах планирования крупномасштабных проектов //Модели и методы оптимизации. Труды Института математики. Новосибирск. Наука. Сиб. Отд–ние. 1988. с. 89–115.
Гэри М., Джонсон Д.. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982. с. 154–191.
Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы. Построение и анализ. М.: МЦНМО, 1999.
Косточка А. В. Дискретная математика. Часть 2 // Новосибирск: НГУ, 2001.
Пападимитриу Х, Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. --- М.: Мир, 1985.
Coffman E.G., Garey M.R., Johnson. D.S. Approximation algorithms for bin packing: A survey. (pdf-file 503 Кb)
Matello S.,.Toth P. Knapsack Problems. Algorithms and Computer Implementations.-John Wiley & Sons. 1990. 296 p. (pdf-file 23 Mb)
Составили
д.ф.-м.н., профессор Э.Х.Гимади к.ф.-м.н., профессор Ю.А. Кочетов
А. И. Орлов Теория принятия решений Моделирование как метод теории принятия решений и анализ ряда конкретных моделей предмет четвертой части. Приводятся методы принятия...
4. Теория принятия решений Издавна, в теории управления принятие решений (ПР) было важным разделом. Но по мере становления теория принятия решений тпр постепенно...
Программа «Повестка дня на XXI век» «Информация для принятия решений» отмечено: «В целях создания надежной основы для процесса принятия решений на всех уровнях и содействия...
Арутюнян Карен Целью данной работы является разработка программного комплекса принятия решений на основе трех наиболее мощных и наглядно обосновывающих...
