Программа курса «дискретные задачи принятия решений»

ПРОГРАММА

КУРСА «ДИСКРЕТНЫЕ ЗАДАЧИ ПРИНЯТИЯ РЕШЕНИЙ»
ММФ, НГУ, 4 курс

  1. Математические модели. Дискретные экстремальные задачи. Системы поддержки принятия решений.

  2. Алгоритмы и оценки временной сложности. Классы P и NP. Полиномиальная сводимость. NP-полные и NP-трудные задачи. Теорема Кука.

  3. NP-полнота задач: 3-ВЫПОЛНИМОСТЬ, 3-СОЧЕТАНИЕ, ВЕРШИННОЕ ПОКРЫТИЕ, КЛИКА, НЕЗАВИСИМОЕ МНОЖЕСТВО, ГАМИЛЬТОНОВ ЦИКЛ, 0-1 РЮКЗАК, РАЗБИЕНИЕ, МНОГОПРОЦЕССОРНОЕ РАСПИСАНИЕ.

  4. Приближенные алгоритмы. Полиномиальные алгоритмы построения приближенных решений с оценками точности. Асимптотически точные алгоритмы на детерминированных и случайных входах. Полиномиальные вполне и полиномиальные аппроксимационные схемы. Примеры аппроксимационных схем.

  5. Задачи маршрутизации. Сложность построения приближенных решений с гарантированной оценкой точности для задачи коммивояжера. Алгоритмы локального
    поиска и их свойства. Алгоритм локального поиска с чередующимися окрестностями. Нижние оценки для задачи коммивояжера. Задача о назначениях и алгоритм ее решения. Задача коммивояжера с временными окнами.

  6. Модели календарного планирования. Алгоритмы вычисления параметров сетевой модели. Задачи с директивными сроками и ресурсными ограничениями. Т-поздние расписания. Полиномиальный алгоритм задачи со складируемыми ресурсами. Стохастическая постановка задачи и вероятность завершения проекта к заданному сроку.

  7. Задачи о покрытии и метод Лагранжевых релаксаций. Дискретные задачи
    размещения. Алгоритм Хватала и его погрешность. Алгоритм Хошбаум. Генетический алгоритм для дискретных задач размещения.

  8. Задачи раскроя и упаковки. Приближенные алгоритмы с оценками и аппроксимационные схемы для задачи упаковки в контейнеры..Алгоритм имитации отжига на примере задачи двумерной упаковки прямоугольников. Математические модели гильотинного раскроя, раскроя кругов и прямоугольников в угол и полосу минимальной длины.

  9. Игровые задачи размещения. Равновесия по Нэшу. Сложность нахождения равновесных решений. Трудоемкость алгоритмов локального улучшения. Цена анархии и цена стабильности.

  10. Задачи двухуровневого программирования и равновесия Штаккельберга. Задача о центроиде. NP-трудность частных случаев. Задачи на цепи и деревьях. Метод генерации столбцов. Вероятностные алгоритмы поиска с запретами.

ЛИТЕРАТУРА

  1. Гимади Э.Х., Глебов. Н.И. Математические модели и методы принятия решений. Учебное пособие, НГУ, 2008 .

  2. Гимади Э.Х., Глебов Н.И., Перепелица В.А. Алгоритмы с оценками для задач дискретной оптимизации. Сб."Проблемы кибернетики", вып.31. --- М.: Наука, 1975

  3. Гимади Э.Х.. О некоторых математических моделях и методах планирования крупномасштабных проектов //Модели и методы оптимизации. Труды Института математики. Новосибирск. Наука. Сиб. Отд–ние. 1988. с. 89–115. 

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

  5. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы. Построение и анализ. М.: МЦНМО, 1999.

  6. Косточка А. В. Дискретная математика. Часть 2 // Новосибирск: НГУ, 2001.

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

  8. Coffman E.G., Garey M.R., Johnson. D.S. Approximation algorithms for bin packing: A survey. (pdf-file  503 Кb)

  9. Matello S.,.Toth P. Knapsack Problems.  Algorithms and Computer Implementations.-John Wiley & Sons. 1990. 296 p. (pdf-file   23 Mb)

Составили

д.ф.-м.н., профессор Э.Х.Гимади
к.ф.-м.н., профессор Ю.А. Кочетов

19.03.2009

  1. Рабочая программа дисциплины Дискретные задачи принятия решений Направление подготовки

    Рабочая программа
    Дисциплина «Дискретные задачи принятия решений» является частью математического цикла ООП по направлению подготовки «Error: Reference source not found», профиль «Error: Reference source not found».
  2. Основная образовательная программа высшего профессионального образования Направление подготовки (210)

    Основная образовательная программа
    4. Документы, регламентирующие содержание и организацию образовательного процесса при реализации магистерской программы по профилю «Исследование операций и оптимизация» 7
  3. Программа по дисциплине «разработка управленческого решения» для специальности 061000 «Государственное и муниципальное управление» очная форма обучения

    Программа
    Курс адресован как студентам специальности «Государственное и муниципальное управление» любой формы обучения, так и студентам родственных специальностей – «Административный менеджмент», «Менеджмент организации».
  4. Программа дисциплины ен. В. 01 «теория принятия решений» Рекомендуется умц кгту им. А. Н. Туполева для направлений

    Программа дисциплины
    Целью дисциплины является формирование фундаментальных знаний у студентов о принципах применения математических моделей, методов и алгоритмов для выбора эффективных решений при решении различных организационно-технических задач с применением
  5. Программа дисциплины Оптимизация и математические методы принятия решений для направления 080700. 62 подготовки бакалавра Автор д т. н., профессор В. В. Подиновский

    Программа дисциплины
    Процесс принятия решений, его участники и этапы. Классификация задач принятия решений по Саймону. Исследование операций как комплексное научно-прикладное направление.
  6. Программа дисциплины Оптимизация и математические методы принятия решений для специальности 351400 Прикладная информатика (в экономике) 1-я ступень высшего профессионального образования

    Программа дисциплины
    Элементы математической теории измерений. Измерение как построение числовой модели признака. Шкала; основные типы шкал. Количественные и качественные признаки (критерии).
  7. Программа дисциплины сд. Ф. 2, Ен. Ф. 8 Теория принятия решений для студентов специальности 230102 Автоматизированные системы обработки информации и управления

    Программа дисциплины
    Лекционная часть курса должна обеспечить получение теоретических знаний в области системного анализа и исследования операций с точки зрения постановки задачи принятия решений,
  8. Программа дисциплины Вероятностно-статистические методы в теории принятия решений для направления 010500. 68 «Прикладная математика и информатика» подготовки магистров Автор: Михальский А. И

    Программа дисциплины
    Курс «Вероятностно-статистические методы в теории принятия решений» предназначен для изучения магистрами 1-го года обучения. Включает в себя введение в теорию принятия решений, разбор задач в условиях определенности, неопределенности
  9. 1. Структура систем многокритериального принятия решений

    Документ
    Математическое ядро – математические методы принятия решений. Оно используется для обработки входной информации, формирования векторов приоритетов и т.

Другие похожие документы..