ПРОГРАММА
курса «Исследование операций» на 2013/14 уч. г.
(4 курс ММФ НГУ, 2 семестр) Темы лекций:
Математическое моделирование
Задачи исследования операций. Массовая и индивидуальная задачи
Построение математических моделей, их особенности и характеристики. Примеры
Введение в теорию NP-полноты
Задачи распознавания свойств. Трудоемкость алгоритмов
Классы P и NP и их взаимоотношения
Теорема Кука о NP-полноте задачи ВЫПОЛНИМОСТЬ
Лемма о сводимости. Схема доказательства принадлежности задачи классу NP-полных проблем
Применение теории NP-полноты для анализа задач
Задачи с числовыми параметрами. Сильная NP-полнота и псевдополиномиальные алгоритмы
NP-трудные проблемы
Динамическое программирование
Принцип оптимальности Беллмана. Примеры
Задача производства и хранения продукции
Булева задача о ранце. Линейная задача о ранце и обратная задача о ранце. Связь решений прямой и обратной задач
Задача о ближайшем соседе. Свойство Глебова для задачи о ближайшем соседе
Релаксационные алгоритмы динамического программирования
Сетевые модели планирования и управления
Построение сетевых графиков
Упрощение сетевых графиков путем склейки вершин
Параметры сетевой модели. Алгоритм Форда для вычисления рангов событий, ранних и поздних моментов наступления событий
Критические события, работы и пути. Правильная нумерация событий и правильное упорядочивание работ
Особенности вычисления характеристик сети в этом случае
Методы неявного перебора
Метод ветвей и границ.
Пример применения метода для задачи КОММИВОЯЖЕР.
Способы построения нижней границы
Аддитивный метод Балаша
Построение паросочетания максимальной мощности в двудольном графе и решение задачи о назначениях
Паросоченание и вершинное покрытие графа. Увеличивающие пути
Алгоритм построения максимального паросочетания в двудольном графе
Метод решения задачи о назначениях и его сложность
Сведение задачи о паросочетании максимального веса к задаче о назначениях
Введение в теорию матричных игр
Решение игры в чистых стратегиях
Смешанные стратегии. Теорема Фон-Неймана
Теорема об активных стратегиях. Игры 22 и 2n
Итеративный метод Брауна – Робинсон
Потоки в сетях
Потоки в сетях. Теорема о максимальном потоке и минимальном разреза
Метод расстановки пометок Форда-Фалкерсона для нахождения максимального потока
Потоки минимальной стоимости. Алгоритмы Басакера-Гоуэна. Алгоритмы Клейна
Приближенные алгоритмы
Примеры приближенных алгоритмов. Жадный алгоритм. Локальный поиск
Метаэвристики. Поиск с запретами. Имитация отжига. Генетический алгоритм. Примеры
Способы оценки точности приближенных алгоритмов. Аппроксимационные схемы. Субоптимальные алгоритмы. Примеры
Темы семинаров:
Математическое моделирование (переход от содержательной постановки к математической).
Динамическое программирование. Задача о ближайшем соседе.
Распределительная задача. Прямая и обратная задачи о ранце.
Сетевые модели планирования и управления. Алгоритм Форда.
Метод ветвей и границ. Применение метода для решения задачи коммивояжера.
Матричные игры. Чистые и смешанные стратегии. Игры 22, 2n и 33. Метод Брауна-Робинсон.
Потоки в сетях. Потоки максимальной мощности и минимальной стоимости.
Контрольные работы по решению задач о ранце, ближайшем соседе, нахождения характеристик сетевых моделей и коммивояжера.
Основная литература:
Ерзин А.И. Введение в исследование операций. Уч. пособие. Новосибирск: НГУ, 2006.
Гончаров Е.Н., Ерзин А.И., Залюбовский В.В. Исследование операций. Примеры и задачи. Уч. пособие. Новосибирск: НГУ, 2005.
Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи – М.: Мир, 1982.
Ху Т. Целочисленное программирование и потоки в сетях – М.: Мир, 1974.
Дополнительная литература:
Беллман Р., Дрейфус С. Прикладные задачи динамического программирования. – М.: Наука, 1965.
Вагнер Г. Основы исследования операций. Т. 1, 2. – М: Мир, 1972.
Вентцель Е.С. Исследование операций. М.: Сов. радио, 1972.
Зуховицкий С.И., Радчик И.А. Математические методы сетевого планирования. – М.: Наука, 1965.
Пападимитриу Х., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. – М.: Мир, 1985.
Программное обеспечение и Интернет-ресурсы:
Слайды лекций – math.nsc.ru/LBRT/k4/LOR
Учебное пособие – math.nsc.ru/LBRT/k4/LOR
Задачник – math.nsc.ru/LBRT/k4/or

Профессор кафедры теор.
кибернетики, д.ф.-м.н. А.И. Ерзин |