Модели многокритериальной оптимизации. Оптимальное и арбитражные решения

Тема 4. Модели многокритериальной оптимизации Лекция 10 2 Формальная постановка задачи многокритериальной оптимизации H k ( x)  max, k  1,..., r , x  ( x1 , x2 ,..., xn )  Dx 𝐷𝑥 – множество (область) допустимых решений 𝐻𝑘 (𝑥) – критерии (цели), 𝑟≥2 H1 ( x)  max, H 2 ( x)  max, H r ( x)  max, x  ( x1 , x2 ,..., xn )  Dx H ( x)   H1 ( x),..., H r ( x)   max, 3 x  ( x1 , x2 ,..., xn )  Dx Определение оптимальности по Парето. Решение 𝑥 ∗ называется парето-оптимальным (оптимальным по Парето, эффективным), если не существует другого решения 𝑥, для которого H i ( x)  H i ( x* ), i  1,..., r , i0 : H i0 ( x)  H i0 ( x ) * 4 Оптимальное решение  Определение. Оптимальным решением в задаче многокритериальной оптимизации называется то Парето-оптимальное решение, которое выбрало лицо, принимающее решение (ЛПР).  Проблема многокритериального выбора ОБЪЕКТИВНО НЕРАЗРЕШИМА. 5 Арбитражные решения Рассмотрим задачу МКО: H k ( x)  max, k  1,..., r , x  Dx Пусть 𝑥0 ∈ 𝐷𝑥 – некоторое «подходящее» решение. Тогда H ( x0 )  H1 ( x0 ),..., H r ( x0 ) – векторная оценка этого «подходящего» решения – называется точкой статус-кво. 6 Арбитражные решения Арбитражной схемой в задаче МКО называется правило 𝜑, которое каждому множеству возможных оценок 𝐻𝑥 и каждой точке «статус-кво» 𝐻 𝑥0 ставит в соответствие единственное парето-оптимальное решение. 7 Решение, полученное в задаче МКО в соответствии с выбранной арбитражной схемой, называется арбитражным решением этой задачи. Арбитражные схемы  Метод главного критерия  Арбитражная схема Нэша  … (известно порядка 40 арбитражных схем) 8 Метод главного критерия Рассмотрим ЗМКО в общем виде: H ( x)  ( H 1 ( x),..., H r ( x)), H i  max, i  1,..., r , x  Dx 1. Фиксируем точку «статус-кво» H ( x0 ) 2. Выберем главный критерий. (Н1) 9 Метод главного критерия 3. Решаем оптимизационную задачу: H1 ( x)  max, x  Dx ,  x *  ( x1* ,..., xn* ) H i  H i ( x0 ), i  2,..., r , х* – оптимальное решение по методу главного критерия (главный критерий – первый) при заданной точке «статус-кво» 𝐻 𝑥0 . 10 Метод главного критерия для двух критериев H1 ( x)  max, H 2 ( x)  max, x  Dx  R n H2 А H 20 H x  OAB O H10 Парето-оптимальная граница? Точка статус-кво: H ( x0 )   Н1  x0  , H 2  x0     H10 , H 20  11 В H1 Метод главного критерия для двух критериев. Главный критерий – H первый. 2 H1 ( x)  max, H 2 ( x)  max, С* H 20 x  Dx  R n O H1 ( x)  max, x  Dx H 2 ( x)  H 20 12 С *   H1* , H 20  H10 H1* H1  H1 ( x)  H1*   H1 ( x)  H 2 xС  Dx Метод главного критерия для двух критериев. Главный критерий – H * Е второй. H 2 * 2 H1 ( x)  max, H 2 ( x)  max, С* H 20 x  Dx  R n O H 2 ( x)  max, x  Dx H1 ( x)  H10 13 Е *   H10 , H 2*  H10 H1* H1  H1 ( x)  H10  *  H1 ( x)  H 2 xЕ  Dx Построение эффективной кривой с помощью метода главного критерия. H1 ( x)  max, H2 H 2 ( x)  max, А x  Dx  R n 1. H ( x0 )  (0, 0) 3 2  В3 В2 В1 H1 ( x)  max, O В Пусть главный критерий - первый x  Dx H 2 ( x)  0 В 2. H ( x0 )  (0, ) H1 ( x)  max, x  Dx 14 Вn 1 H 2 ( x)   В1 H1 Арбитражная схема Нэша H ( x)  ( H 1 ( x),..., H r ( x)), H i  max, i  1,..., r , x  Dx 1. Фиксируем точку «статус-кво» H ( x)  ( H 1 ( x0 ),...,H r ( x0 )) 2. Введем в рассмотрение функцию Нэша: r H ( x)   ( H i ( x)  H i ( x0 )). N i 1 15 Арбитражная схема Нэша Рассматривается следующая ЗНЛП: N max H ( x) xDx H i ( x)  H i ( x0 ), i  1,...,r 16 Арбитражное решение Нэша * x , которое решает эту ЗНЛП, называется арбитражным решением Нэша при точке статус-кво H ( x0 ) Замечание. Арбитражное решение Нэша оптимально по Парето. 17 Теорема (о существовании арбитражного решения Нэша) Если множество допустимых решений в задаче многокритериальной оптимизации является выпуклым и замкнутым, то существует единственное арбитражное решение Нэша 18 Арбитражное решение Нэша для двух критериев H ( x)  max, 1 H 2 ( x)  max, H2 x  Dx  R n Точка статус-кво: H ( x0 )   Н1  x0  , H 2  x0     H10 , H 20  H 20 Функция Нэша H N ( x)   H1 ( x)  H10  H 2 ( x)  H 20  O H10 H N ( x)   H1 ( x)  H10  H 2 ( x)  H 20   max x  Dx H1 ( x)  H10 19 H 2 ( x)  H 20 H1 Арбитражное решение Нэша для двух критериев H N ( x)   H1 ( x)  H10  H 2 ( x)  H 20   max x  Dx H1 ( x)  H10 H 2 ( x)  H 2 H2 Е * С* H 20 O 20   H N x* H10 H1 Минимизация расстояния до «утопической точки» «Утопическая точка» - это точка 𝐻1𝑚𝑎𝑥 , 𝐻2𝑚𝑎𝑥 , … , 𝐻𝑟𝑚𝑎𝑥 , где все критерии одновременно достигают своего максимума. H2 Расстояние от векторной оценки произвольной допустимой точки до «утопической»:    H1 ( x )  H 2  H 2max H2 А*    H ( x)  H  max 2 1 max 2 2 2 H1 O    H1 ( x )  H 2 21 x  Dx   H max 2 1 2 ( x)  H  max 2 2  min H1max H1 Теорема (о существовании решения через утопическую точку) Если множество допустимых решений в задаче многокритериальной оптимизации является выпуклым и замкнутым, то существует единственное решение, минимизирующее расстояние до утопической точки. 22 Пример. Фирма Chemco Химическая компания «Chemco» планирует выпуск трёх видов продукции. Продукт 1 Продукт 2 Продукт 3 Прибыль $10 $9 $8 ЗАПАС ресурсов - Временные затраты Затраты ресурса Загрязнение 4ч 3ч 2ч 1 300 ч 3 ед. 10 ед. 2 ед. 6 ед. 3 ед. 3 ед. 1 000 ед. - Фирма «Chemco» ставит две цели: Максимизировать прибыль. 2. Минимизировать загрязнение окружающей среды. 1. 23 Математическая модель Chemco max H1 ( x)  max 10 x1  9 x2  8 x3  max H 2 ( x)  max   10 x1  6 x2  3 x3   4 x1  3 x2  2 x3  1300 3 x1  2 x2  3 x3  1000 x1  0, x2  0, x3  0 Оптимальное решение в задаче МКО – это то парето-оптимальное решение, которое выбрал ЛПР. Множество допустимых решений является выпуклым, т.к. задано линейными ограничениями, и замкнутым. Значит арбитражное решение Нэша и решение с помощью утопической точки существуют. 24 Оптимизация по первой цели 25 Оптимизация по второй цели 26 Chemco. Выбор точки SQ Точка SQ: 2390; −1915 27 Chemco. Метод главного критерия. Главный критерий - первый max H1 ( x)  max 10 x1  9 x2  8 x3  max H 2 ( x)  max   10 x1  6 x2  3 x3   Точка SQ: 2390; −1915 4 x1  3 x2  2 x3  1300 3 x1  2 x2  3 x3  1000 x1  0, x2  0, x3  0 max H1 ( x)  max 10 x1  9 x2  8 x3  4 x1  3 x2  2 x3  1300 3 x1  2 x2  3 x3  1000  10 x1  6 x2  3 x3   1915 x1  0, x2  0, x3  0 28 max H1 ( x)  max 10 x1  9 x2  8 x3  4 x1  3 x2  2 x3  1300 3 x1  2 x2  3 x3  1000 10 x1  6 x2  3 x3  1915 x1  0, x2  0, x3  0 29 «Chemco». Эффективная граница max H1 4060 min H2 -2520 min H1 max H2 max H 2  min H 2 2520    252 10 10 max H1 ( x)  max 10 x1  9 x2  8 x3  4 x1  3 x2  2 x3  1300 3 x1  2 x2  3 x3  1000 10 x1  6 x2  3 x3  k  (), k  0,...,10 x1  0, x2  0, x3  0 30 «Chemco». Эффективная граница 31 «Chemco». Эффективная граница 32 Chemco. Арбитражное решение Нэша max H1 ( x)  max 10 x1  9 x2  8 x3  max H 2 ( x)  max   10 x1  6 x2  3 x3   4 x1  3 x2  2 x3  1300 Точка SQ: 2390; −1915 3 x1  2 x2  3 x3  1000 x1  0, x2  0, x3  0 max H N ( x)  max 10 x1  9 x2  8 x3  2390  10 x1  6 x2  3 x3  1915  4 x1  3x2  2 x3  1300 3x1  2 x2  3x3  1000 10 x1  9 x2  8 x3  2390 10 x1  6 x2  3x3  1915 x1  0, x2  0, x3  0 33 «Chemco». Арбитражное решение Нэша 34 max H N ( x)  max 10 x1  9 x2  8 x3  2390  10 x1  6 x2  3 x3  1915  4 x1  3x2  2 x3  1300 3x1  2 x2  3x3  1000 10 x1  9 x2  8 x3  2390 10 x1  6 x2  3x3  1915 x1  0, x2  0, x3  0 Минимизация расстояния до «утопической точки» 35 Chemco. Сравнение решений 36 Решение 𝒙𝟏∗ 𝒙∗𝟐 𝒙𝟑∗ Максим. прибыль (ЦФ1) Сумм. загрязнение (ЦФ2) Оптим. для ЦФ1 380 80 4060 2520 Оптим. для ЦФ2 Точка SQ – – – 2390 1915 Метода главного критерия (главный – первый) 228,75 180,83 3505,42 1915 Арбитражное решение Нэша 116,87 266,42 3095,20 1467,49 Минимизация расстояния до утопической точки 37,66 308,23 2804,75 1150,64 Лабораторная работа 4  СРОК СДАЧИ без потери баллов: 12.05.2020 для ВСЕХ групп.  Задачи к ЛР № 4 – задачи к ЛР № 1, в которых добавлены новые цели.  Критериев три, но решения аналогичны рассмотренным. 37 Лабораторная работа 4  Поиск каждого решения – на отдельном Excel листе. К каждой решаемой оптимизационной задаче – обязательно математическая модель!  Необходимо решить всеми известными способами, сравнить решения, выбрать оптимальное с Вашей точки зрения и построить эффективную кривую. Краткая инструкция загружена в личный кабинет.  Выбор точки статус-кво: убедитесь в допустимости!!! 38