Программа курса «Исследование операций» на 2013/14 уч г. (4 курс ммф нгу, 2 семестр) Темы лекций

ПРОГРАММА курса «Исследование операций» на 2013/14 уч. г. (4 курс ММФ НГУ, 2 семестр) Темы лекций: Математическое моделирование Задачи исследования операций. Массовая и индивидуальная задачи Построение математических моделей, их особенности и характеристики. Примеры Введение в теорию NP-полноты Задачи распознавания свойств. Трудоемкость алгоритмов Классы P и NP и их взаимоотношения Теорема Кука о NP-полноте задачи ВЫПОЛНИМОСТЬ Лемма о сводимости. Схема доказательства принадлежности задачи классу NP-полных проблем Применение теории NP-полноты для анализа задач Задачи с числовыми параметрами. Сильная NP-полнота и псевдополиномиальные алгоритмы NP-трудные проблемы Динамическое программирование Принцип оптимальности Беллмана. Примеры Задача производства и хранения продукции Булева задача о ранце. Линейная задача о ранце и обратная задача о ранце. Связь решений прямой и обратной задач Задача о ближайшем соседе. Свойство Глебова для задачи о ближайшем соседе Релаксационные алгоритмы динамического программирования Сетевые модели планирования и управления Построение сетевых графиков Упрощение сетевых графиков путем склейки вершин Параметры сетевой модели. Алгоритм Форда для вычисления рангов событий, ранних и поздних моментов наступления событий Критические события, работы и пути. Правильная нумерация событий и правильное упорядочивание работ Особенности вычисления характеристик сети в этом случае Методы неявного перебора Метод ветвей и границ. Пример применения метода для задачи КОММИВОЯЖЕР. Способы построения нижней границы Аддитивный метод Балаша Построение паросочетания максимальной мощности в двудольном графе и решение задачи о назначениях Паросоченание и вершинное покрытие графа. Увеличивающие пути Алгоритм построения максимального паросочетания в двудольном графе Метод решения задачи о назначениях и его сложность Сведение задачи о паросочетании максимального веса к задаче о назначениях Введение в теорию матричных игр Решение игры в чистых стратегиях Смешанные стратегии. Теорема Фон-Неймана Теорема об активных стратегиях. Игры 22 и 2n Итеративный метод Брауна – Робинсон Потоки в сетях Потоки в сетях. Теорема о максимальном потоке и минимальном разреза Метод расстановки пометок Форда-Фалкерсона для нахождения максимального потока Потоки минимальной стоимости. Алгоритмы Басакера-Гоуэна. Алгоритмы Клейна Приближенные алгоритмы Примеры приближенных алгоритмов. Жадный алгоритм. Локальный поиск Метаэвристики. Поиск с запретами. Имитация отжига. Генетический алгоритм. Примеры Способы оценки точности приближенных алгоритмов. Аппроксимационные схемы. Субоптимальные алгоритмы. Примеры Темы семинаров: Математическое моделирование (переход от содержательной постановки к математической). Динамическое программирование. Задача о ближайшем соседе. Распределительная задача. Прямая и обратная задачи о ранце. Сетевые модели планирования и управления. Алгоритм Форда. Метод ветвей и границ. Применение метода для решения задачи коммивояжера. Матричные игры. Чистые и смешанные стратегии. Игры 22, 2n и 33. Метод Брауна-Робинсон. Потоки в сетях. Потоки максимальной мощности и минимальной стоимости. Контрольные работы по решению задач о ранце, ближайшем соседе, нахождения характеристик сетевых моделей и коммивояжера. Основная литература: Ерзин А.И. Введение в исследование операций. Уч. пособие. Новосибирск: НГУ, 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 Профессор кафедры теор. кибернетики, д.ф.-м.н. А.И. Ерзин

Похожие:

	Программа на 2013/2014 уч год по курсу «Методы оптимизации» для студентов... Введение. Постановка и общие методы решения задач оптимизации (1 лекция): Предмет изучения, основные термины и обозначения, связь...		Программа на 2013/14 уч год по курсу «Дискретная математика» для... Основные правила комбинаторики. Выборки. Комбинаторные правила произведения и суммы. Формула включений исключений. Примеры применения...
	Программа курса лекций (2 курс, 3 сем., 36 ч., экзамен) 4 Литература... Булева Алгебра. Основные аксиомы и теоремы. Диаграммы Вейча. Карты Карно. Применение при проектировании и анализе работы ЭВМ		Расписание лекций для VI курса педиатрического факультета 2012-2013 уч г. Весенний семестр
	Весенний семестр Расписание лекций для V курса мимос стоматологического факультета 2013-2014 уч г		Экзаменационные вопросы по курсу теория игр и исследование операций... Доказать, что если функция K(X,y) непрерывна на X? Y (X, y компакты), то функция непрерывна на X
	Расписание спецкурсов на 1 семестр 2013/2014 уч года кафедры физико-технической... Вниманию студентов 2-го курса! Для проведения инструктажа всем подойти 9 сентября к 14-00 на проходную главного корпуса ияф		Расписание спецкурсов на 1 семестр 2012/2013 уч года кафедры физико-технической... Вниманию студентов 2-го курса! Для проведения инструктажа всем подойти 6 сентября к 14-00 на проходную главного корпуса ияф
	Курс «Базы данных» Разработчики курса: Иваньчева Татьяна Александровна,... Порядок построения er-модели и построение реляционной схемы базы данных из er-модели 27		Расписание спецкурсов на 2 семестр 2007/2008 уч года кафедры физико-технической... Кондауров М. Н., Суханов Д. П. Тсани нгу возможны изменения в первые две недели февраля!!!