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




Скачать 34.11 Kb.
НазваниеПрограмма курса «Исследование операций» на 2013/14 уч г. (4 курс ммф нгу, 2 семестр) Темы лекций
Дата публикации27.03.2014
Размер34.11 Kb.
ТипПрограмма курса
litcey.ru > Математика > Программа курса
ПРОГРАММА

курса «Исследование операций» на 2013/14 уч. г.

(4 курс ММФ НГУ, 2 семестр)
Темы лекций:

  1. Математическое моделирование

    1. Задачи исследования операций. Массовая и индивидуальная задачи

    2. Построение математических моделей, их особенности и характеристики. Примеры

  2. Введение в теорию NP-полноты

    1. Задачи распознавания свойств. Трудоемкость алгоритмов

    2. Классы P и NP и их взаимоотношения

    3. Теорема Кука о NP-полноте задачи ВЫПОЛНИМОСТЬ

    4. Лемма о сводимости. Схема доказательства принадлежности задачи классу NP-полных проблем

    5. Применение теории NP-полноты для анализа задач

    6. Задачи с числовыми параметрами. Сильная NP-полнота и псевдополиномиальные алгоритмы

    7. NP-трудные проблемы

  3. Динамическое программирование

    1. Принцип оптимальности Беллмана. Примеры

    2. Задача производства и хранения продукции

    3. Булева задача о ранце. Линейная задача о ранце и обратная задача о ранце. Связь решений прямой и обратной задач

    4. Задача о ближайшем соседе. Свойство Глебова для задачи о ближайшем соседе

    5. Релаксационные алгоритмы динамического программирования

  4. Сетевые модели планирования и управления

    1. Построение сетевых графиков

    2. Упрощение сетевых графиков путем склейки вершин

    3. Параметры сетевой модели. Алгоритм Форда для вычисления рангов событий, ранних и поздних моментов наступления событий

    4. Критические события, работы и пути. Правильная нумерация событий и правильное упорядочивание работ

    5. Особенности вычисления характеристик сети в этом случае

  5. Методы неявного перебора

    1. Метод ветвей и границ.

    2. Пример применения метода для задачи КОММИВОЯЖЕР.

    3. Способы построения нижней границы

    4. Аддитивный метод Балаша

  6. Построение паросочетания максимальной мощности в двудольном графе и решение задачи о назначениях

    1. Паросоченание и вершинное покрытие графа. Увеличивающие пути

    2. Алгоритм построения максимального паросочетания в двудольном графе

    3. Метод решения задачи о назначениях и его сложность

    4. Сведение задачи о паросочетании максимального веса к задаче о назначениях

  7. Введение в теорию матричных игр

    1. Решение игры в чистых стратегиях

    2. Смешанные стратегии. Теорема Фон-Неймана

    3. Теорема об активных стратегиях. Игры 22 и 2n

    4. Итеративный метод Брауна – Робинсон

  8. Потоки в сетях

    1. Потоки в сетях. Теорема о максимальном потоке и минимальном разреза

    2. Метод расстановки пометок Форда-Фалкерсона для нахождения максимального потока

    3. Потоки минимальной стоимости. Алгоритмы Басакера-Гоуэна. Алгоритмы Клейна

  9. Приближенные алгоритмы

    1. Примеры приближенных алгоритмов. Жадный алгоритм. Локальный поиск

    2. Метаэвристики. Поиск с запретами. Имитация отжига. Генетический алгоритм. Примеры

    3. Способы оценки точности приближенных алгоритмов. Аппроксимационные схемы. Субоптимальные алгоритмы. Примеры


Темы семинаров:

  1. Математическое моделирование (переход от содержательной постановки к математической).

  2. Динамическое программирование. Задача о ближайшем соседе.

  3. Распределительная задача. Прямая и обратная задачи о ранце.

  4. Сетевые модели планирования и управления. Алгоритм Форда.

  5. Метод ветвей и границ. Применение метода для решения задачи коммивояжера.

  6. Матричные игры. Чистые и смешанные стратегии. Игры 22, 2n и 33. Метод Брауна-Робинсон.

  7. Потоки в сетях. Потоки максимальной мощности и минимальной стоимости.

  8. Контрольные работы по решению задач о ранце, ближайшем соседе, нахождения характеристик сетевых моделей и коммивояжера.


Основная литература:

  1. Ерзин А.И. Введение в исследование операций. Уч. пособие. Новосибирск: НГУ, 2006.

  2. Гончаров Е.Н., Ерзин А.И., Залюбовский В.В. Исследование операций. Примеры и задачи. Уч. пособие. Новосибирск: НГУ, 2005.

  3. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи – М.: Мир, 1982.

  4. Ху Т. Целочисленное программирование и потоки в сетях – М.: Мир, 1974.


Дополнительная литература:

  1. Беллман Р., Дрейфус С. Прикладные задачи динамического программирования. – М.: Наука, 1965.

  2. Вагнер Г. Основы исследования операций. Т. 1, 2. – М: Мир, 1972.

  3. Вентцель Е.С. Исследование операций. М.: Сов. радио, 1972.

  4. Зуховицкий С.И., Радчик И.А. Математические методы сетевого планирования. – М.: Наука, 1965.

  5. Пападимитриу Х., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. – М.: Мир, 1985.


Программное обеспечение и Интернет-ресурсы:

  • Слайды лекций – math.nsc.ru/LBRT/k4/LOR

  • Учебное пособие – math.nsc.ru/LBRT/k4/LOR

  • Задачник – math.nsc.ru/LBRT/k4/or





Профессор кафедры теор.

кибернетики, д.ф.-м.н. А.И. Ерзин

Похожие:

Программа курса «Исследование операций» на 2013/14 уч г. (4 курс ммф нгу, 2 семестр) Темы лекций iconПрограмма на 2013/2014 уч год по курсу «Методы оптимизации» для студентов...
Введение. Постановка и общие методы решения задач оптимизации (1 лекция): Предмет изучения, основные термины и обозначения, связь...
Программа курса «Исследование операций» на 2013/14 уч г. (4 курс ммф нгу, 2 семестр) Темы лекций iconПрограмма на 2013/14 уч год по курсу «Дискретная математика» для...
Основные правила комбинаторики. Выборки. Комбинаторные правила произведения и суммы. Формула включений исключений. Примеры применения...
Программа курса «Исследование операций» на 2013/14 уч г. (4 курс ммф нгу, 2 семестр) Темы лекций iconПрограмма курса лекций (2 курс, 3 сем., 36 ч., экзамен) 4 Литература...
Булева Алгебра. Основные аксиомы и теоремы. Диаграммы Вейча. Карты Карно. Применение при проектировании и анализе работы ЭВМ
Программа курса «Исследование операций» на 2013/14 уч г. (4 курс ммф нгу, 2 семестр) Темы лекций iconРасписание лекций для VI курса педиатрического факультета 2012-2013 уч г. Весенний семестр

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


При копировании материала укажите ссылку © 2013
контакты
litcey.ru
Главная страница