Многокритериальная оптимизация

Кафедра информатики и автоматизации научных исследований

Специальность: Прикладная информатика в области принятия решений

Преподаватель: Коротченко А.Г.

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

В результате изучения дисциплины студенты должны:

Знать определение эффективных и слабо-эффективных стратегий (точек), теорему их существования, способы скаляризации векторного критерия, специальные свойства бинарных отношений, принципы оптимальности, используемые в задачах принятия решений, когда цели задаются с помощью связанных с ними отношений предпочтений, определение бескоалиционной, антагонистической и матричной игры, теоремы о седловых точках, основную теорему теории матричных игр, достаточные признаки значения игры и оптимальных стратегий игроков.

Уметь находить множество эффективных стратегий для классов бикритериальных задач оптимизации, использовать алгоритмы, основанные на принципах оптимальности, для отыскания эффективных решений в задачах, когда цели задаются с помощью связанных с ними отношений предпочтений, решать частные классы матричных игр: 2*2 игры, 2*n и m*2 игры, 3*3 игры.

Иметь представление об алгоритмах выделения приближенно-эффективных точек при решении конкретных многокритериальных задач, о связи между разрешимостью пар двойственных задач линейного программирования и решениями матричных игр.

Содержание

1. Задачи оптимизации со многими критериями оптимальности. Эффективные и слабо эффективные стратегии (точки). Теорема существования эффективных точек. Множество Парето. Способы отыскания эффективных точек. Обобщенная функция цели. Скаляризация векторного критерия оптимальности при наличии дополнительной информации о важности частных критериев.

2. Линейные многокритериальные задачи. Методы отыскания эффективных точек в линейных многокритериальных задачах. Бикритериальная задача о ранце, бикритериальная задача на сети.

3. Приближенно-эффективные точки и алгоритмы их выделения.  Понятие e-оптимального решения в задаче многокритериальной оптимизации и алгоритмы его отыскания. Вопросы сходимости множества приближенно-эффективных точек к множеству эффективных точек.

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

5. Принципы оптимальности, используемые в задачах принятия решений, когда цели задаются с помощью связанных с ними отношений предпочтений.  Принцип недоминируемости. Задача ранжирования при заданном транзитивном отношении предпочтения. Принцип Неймана-Моргенштерна. Понятие ядра отношения. Алгоритм выделения ядра. Принцип «грубого» ранжирования. Алгоритм выделения контуров графа бинарного отношения. Принцип «тонкого» ранжирования. Понятие предельного вектора, связь с числом Перрона-Фробениуса матрицы бинарного отношения.

6. Игровые задачи принятия решений. Определение бескоалиционной игры. Приемлемые ситуации и ситуации равновесия. Стратегическая эквивалентность игр. Антагонистические игры. Седловые точки. Равенство минимаксов.

7. Матричные игры.  Смешанные стратегии. Смешанное расширение игры. Существование минимаксов в смешанных стратегиях.

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

9. Частные классы матричных игр. 2х2 игры. Метод решения 2хn и mх2 игр. 3х3 игры.

10. Матричные игры и линейное программирование. Прямая и двойственная задача задачи линейного программирования. Связь между разрешимостью пар двойственных задач линейного программирования и решениями матричных игр.

Лабораторный практикум

  1. Линейные многокритериальные задачи. Реализация метода построения эффективных векторов и эффективных стратегий бикритериальной задачи, основанного на минимальном свойстве эффективных точек. Реализация метода динамического программирования решения бикритериальной задачи о ранце и бикритериальной задачи на сети.
  2. Реализация метода помеченных точек при приближенном решении многокритериальной задачи оптимизации. Демонстрация сходимости множества приближенных эффективных точек к множеству эффективных стратегий при различном задании аппроксимирующего множества. Решение контрольных примеров.
  3. Реализация принципов выбора (недоминируемости, Неймана – Моргенштерна, ранжирования) в задачах принятия решений, когда цели задаются с помощью связанных с ними отношений предпочтений. Решение контрольных примеров.

Литература

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

 

  1. Батищев Д.И. Задачи и методы векторной оптимизации. – Изд. ГГУ, Горький, 1979
  2. Розен В.В. Цель- оптимальность- решение: Математические модели принятия оптимальных решений. – М.: Радио и связь, 1982
  3. Батищев Д.И. Методы оптимального проектирования. – М.: Радио и связь, 1984
  4. Воробьев Н.Н. Теория игр. Лекции для экономистов-кибернетиков. Изд. ЛГУ, Ленинград, 1974
  5. Воробьев Н.Н. Теория игр для экономистов-кибернетиков. М.: Наука, 1985

б) дополнительная литература:

  1. Никайдо Х. Выпуклые структуры и математическая экономика.– М.: Мир, 1972
  2. Кини Р.Л., Райфа Х. Принятие решений при многих критериях: предпочтения и замещения.- М.: Радио и связь, 1981
  3. Соболь И.М., Статников Р.Б. Выбор оптимальных параметров в задачах со многими критериями. – М.: Наука, 1981
  4. Подиновский В.В., Ногин В.Д. Парето-оптимальные решения многокритериальных задач. – М.: Наука, 1982
  5. Морозов В.В., Сухарев А.Г., Федоров В.В. Исследование операций в задачах и упражнениях. – М.: Высшая школа, 1986
  6. Юдин Д.Б. Вычислительные методы теории принятия решений. – М.: Наука, 1989
  7. Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. – М.: Наука, 1990
  8. Штойер Р. Многокритериальная оптимизация. – М.: Радио и связь, 1992
  9. Батищев Д.И., Коган Д.И. Вычислительная сложность экстремальных задач переборного типа. – Изд. ННГУ, Н.Новгород, 1994
  10. Ашманов С.А. Линейное программирование. М.: Наука, 1981
  11. Воробьев Н.Н. Основы теории игр. Бескоалиционные игры. М.: Наука, 1984
  12. Коротченко А.Г., Тихонов В.А. Методические указания (сборник задач) по курсу «Модели и методы принятия решений» - Изд. ННГУ, Н.Новгород, 2000
  13. Коротченко А.Г., Бобков А.Н. Принципы оптимальности в задачах принятия решений (методическая разработка) – Изд. ННГУ, Н.Новгород, 2002

Отчетность

  • Семестр 2: Зач