You are here

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

Профессор А. В. Лотов. Кафедральный курс лекций. 5 курс, 9 семестр.

Программа курса

  1. Основные представления о СППР.
    1. Обработка информации на основе математического моделирования. Математическое моделирование в задачах выбора решений. Моделирование в науке как изучение систем на основе использования вспомогательных объектов. Типы моделирования. Особенности математического моделирования. Основной вопрос моделирования и методы его решения в различных областях науки. Математическое моделирование социально-экономических систем. Становление и развитие теории принятия решений. Структуризованные и неструктуризованные проблемы принятия решений. Субъективные и объективные элементы выбора решений в плохо структуризованных проблемах. Многокритериальность как пример плохой структуризации проблемы. Природа многокритериальности. Примеры многокритериальных задач принятия решений. Системный подход и его особенности. Системный анализ проблем принятия решений. «Жесткий» и «мягкий» системный анализ. Схема исследования операций и её ограниченность. Системный анализ и проблема неединственности критерия. Роль человека. «Мягкий» системный анализ и структуризация проблем. Этапы процесса принятия решений. Поиск и анализ решений.
    2. Компьютерные системы поддержки принятия решений. Понятие и определения СППР. СППР как реализация современных представлений теории принятия решений. Структура СППР. Задачи поиска и анализа решений в СППР. Роль математических моделей в СППР. Роль многокритериальной оптимизации в СППР. Современный подход к созданию СППР. Генераторы СППР и средства анализа в СППР. Концепция лица, принимающего решение (ЛПР). ЛПР, эксперты, специалисты по системному анализу и исследователи операций. Примеры ЛПР. Ограниченность понятия ЛПР. Распределённое принятие решений. Проблемы с неопределённым числом ЛПР. Переговоры и дискуссии. Принципиальные и позиционные переговоры. Роль и возможности человека с СППР. Современные представления о психологии принятии решений. Основные уровни восприятия. Роль логического и образного восприятия.
  2. Основные понятия многокритериальной оптимизации.
    1. Бинарные отношения и их использование при описании предпочтений в задачах принятия решений. Задание и типы бинарных отношений. Операции с бинарными отношениями. Бинарные отношения порядка в задачах принятия решений. Квазипорядок. Разбиение квазипорядка. Отношение эквивалентности. Теорема о разбиении на классы. Строгий порядок. Понятие доминирования. Максимальные элементы бинарного отношения строгого порядка. Понятия внутренней и внешней устойчивости множества максимальных элементов.
    2. Основные понятия многокритериальной оптимизации (МКО). Решения и показатели. Измерение показателей. Шкалы. Типы шкал. Порядковые шкалы. Показатели и критерии. Независимость критериев предпочтению. Формулировка понятия МКО. МКО как теоретическая основа выбора решений с использованием математических моделей. Множество допустимых решений. Множество достижимых значений критериев и его свойства. Использование квазипорядка и строгого порядка для построения понятия решения. Доминирование по Парето и по Слейтеру. Понятия оптимальности по Парето и по Слейтеру. Недоминируемое множество по Парето и по Слейтеру. Эффективные и слабо-эффективные решения. Оболочка Эджворта-Парето (ОЭП) множества достижимых значений критериев. Оптимальность по Джоффриону. Множество Джоффриона. Собственно эффективные решения.
    3. Достаточные условия существования и внешней устойчивости множества Парето. Теорема о замыкании собственно эффективного множества (без доказательства). Свойства недоминируемого множества по Парето и по Слейтеру. Недоминируемое множество как граница множества достижимых значений критериев.
    4. Свёртки критериев и их свойства. Свёртки, неубывающие и возрастающие по бинарному отношению строгого предпочтения. Общие достаточные условия оптимальности по Парето и Слейтеру. Наиболее распространенные свёртки: линейная свёртка; свёртка Гермейера; свёртки, основанные на идеальной точке; свёртка Вержбицкого. Свойства свёрток.
    5. Необходимые и достаточные условия эффективности. Выпуклые задачи. Понятие эффективной выпуклости. Достаточное условие эффективной выпуклости (лемма Карлина). Условия оптимальности в эффективно-выпуклых задачах. Теорема Ю. Теорема Джоффриона и её следствия. Эффективность в линейном случае. Геометрическая и алгебраическая формы леммы Фаркаша. Следствия леммы Фаркаша: лемма Фань Цзи, теоремы Моцкина и Таккера. Связь собственной эффективности и эффективности для линейного случая. Условия эффективности в общем случае.
  3. Многокритериальные методы в СППР.
    1. Классификация многокритериальных методов в соответствии с ролью ЛПР. Методы, основанные на построении решающего правила (функции выбора) с участием ЛПР. Решающее правило в виде функции ценности (полезности). Кривые безразличия и субъективное замещение. Многомерные функции полезности и поверхности безразличия. Стратегическая эквивалентность функций полезности. Предельный коэффициент замещения. Аддитивная функция полезности. Условия аддитивности и построение аддитивной функции ценности для двух критериев. Обсуждение ситуации с тремя и большим числом критериев. Эвристические подходы к построению решающих правил. Процесс анализа иерархии критериев Т. Саати. Метод Электра для выбора из конечного числа альтернатив.
    2. Итеративные многокритериальные процедуры поиска наиболее предпочтительного решения. Структура итеративных процедур. Две фазы итеративной процедуры. Прямое назначение весов, ограничений, целей и других параметров в итеративных процедурах. Структуризованные и неструктуризованные процедуры. Процедура Джоффриона-Дайера как пример структуризованной процедуры. Возможности человека в итеративных процедурах. Требования, предъявляемые к итеративным процедурам: сходимость, простота вопросов к ЛПР, малое число итераций, устойчивость к ошибкам ЛПР.
    3. Основные типы итеративных процедур. Процедуры, основанные на назначении весов. Процедура Зайонца-Валлениуса сжатия конуса весов. Процедуры, основанные на использовании ограничений. Процедура STEM. Процедуры, основанные на назначении целей. Современные графические итеративные методы. Проекции на эффективное множество. Процедура Корхонена-Лааксо. Бег по множеству Парето. Процедуры, основанные на визуализации двумерных сечений оболочки Эджворта-Парето.
    4. Традиционные методы представления эффективного множества совокупностью его точек. Построение эффективного множества для систем с конечным числом вариантов. Представление ЛПР совокупности эффективных точек. Профили альтернатив. Выбор среди эффективных точек. Трудности непосредственного выбора из большого списка альтернатив. Случай линейных систем. Нахождение всех эффективных вершин. Условия эффективности соседнего базиса. Построение эффективной грани. Представление ЛПР совокупности эффективных вершин. Методы представления эффективного множества для нелинейных систем. Использование свёрток критериев, целевых точек и критериальных ограничений. Метод идеальной точки. Методы ограничений.
    5. Методы представления недоминируемого множества на основе визуализации двумерных сечений оболочки Эджворта-Парето. Свойства двумерных сечений оболочки Эджворта-Парето. Диалоговые карты решений. Анимация карт решений. Метод достижимых целей для выпуклых систем. Построение решений. Метод достижимых целей для нелинейных систем. Визуализация системы конусов. Анализ возможностей выбора решения. Метод разумных целей для задач с конечным числом альтернатив. Визуализация выпуклой оболочки системы конечного числа вариантов. Осознанный выбор цели и наложения ограничений. Методы выбор предпочтительных решений из совокупности вариантов. Примеры применения. Метод разумных целей для задач с бесконечным числом альтернатив.
  4. Лабораторные работы.
    1. Компьютерная лабораторная работа «Компромисс». Реализация работы в виде учебной игры. Реализация работы в сети Интернет.
    2. Компьютерная лабораторная работа «Изучение метода разумных целей». Реализация работы в сети Интернет.
    3. Компьютерная лабораторная работа «Изучение метода ограничений и системы WWW-NIMBUS».

Литература

  1. Р. Л. Кини, Х. Райфа. Принятие решений при многих критериях: предпочтения и замещения. - М.: Радио и связь, 1981.
  2. П. С. Краснощеков, А. А. Петров. Принципы построения моделей. - М.: МГУ, 1983.
  3. О. И. Ларичев. Объективные модели и субъективные решения. - М.: Наука, 1987.
  4. О. И. Ларичев. Теория и методы принятия решений. - М.: Логос, 2000.
  5. А. В. Лотов. Введение в экономико-математическое моделирование. - М.: Наука, 1984.
  6. А. В. Лотов, В. А. Бушенков, Г. К. Каменев и О. Л. Черных. Компьютер и поиск компромисса. Метод достижимых целей. - М.: Наука, 1997.
  7. В. В. Подиновский, В. Д. Ногин. Парето-оптимальные решения многокритериальных задач. - М.: Наука, 1982.
  8. Р. Штойер. Многокритериальная оптимизация: теория, вычисления и приложения. - М.: Радио и связь, 1992.