34 Максимінне згортання критеріїв. Приклад.

Максимінна згортка - це найпростіший спосіб побудови узагальненого критерію (суперкрітерія), заснований на застосуванні вже добре нам відомого принципу максимина. Нехай ми маємо оцінки деяких об'єктів (альтернатив) по n критеріям. Кожен з критеріїв має свою розмірність, і ці розмірності зазвичай не збігаються. Тому для початку потрібно унормувати всі наявні оцінки. Робиться це за допомогою нормують множників - на основі вихідної матриці оцінок будується нова матриця з такими елементами: cij = де aj = - нормуючі множники. Далі до отриманого матриці застосовуємо принцип максимина. Подивимося, як це робиться на нашому прикладі: Вихідну матрицю ми, так само як і раніше, доповнили справа ще одним стовпцем, в який внесли значення мінімальних елементів кожної перерахованої рядка. З елементів доданого стовпця вибираємо найбільший. Рядок, в якій він стоїть і буде оптимальною альтернативою. В даному випадку оптимальною буде альтернатива А1. Недолік максимина згортки - це те, що вона враховує лише ті критерії, які дають найгірші оцінки, всі інші критерії ігноруються. Через це максимина згортку використовують не надто часто, частіше використовують лінійні і мультиплікативні згортки. Зате такий підхід завжди дає гарантований результат, нижче якого результату не буде. А що робити, якщо максимина згортка дасть кілька однакових результатів (таке теж буває!), А ЛПР необхідно вибрати одне рішення? Для такого цікавого випадку А. Джоффріон запропонував використовувати так звану лексикографічну згортку. Робиться це так. Беруться дві (або декілька) оптимальні альтернативи, отримані методом максимина згортки, і з них вибирається найкраща методом лінійної згортки. Як бачимо, з такими числовими даними максимина згортка оптимальними вважає альтернативи А1 і А2. Тепер після максимина згортки застосуємо до альтернатив А1 і А2 лінійну згортку: В результаті отримали однозначну відповідь: оптимальною є альтернатива А1.

36 Метод ідеальної точки. Приклад.

тод ідеальної точки базується на тому, що постулюється існування “ідеальної точки” для розв’язку задачі, у якій досягається екстремум усіх критеріїв (принцип Джофріона). Так, на рис. 1 ідеальною є точка D в просторі критеріїв, якій не відповідає жоден припустимий розв’язок простору змінних. Оскільки ідеальна точка в абсолютній кількості випадків не знаходиться серед припустимих, виникає проблема знаходження точки, що “найближча” до ідеальної і належить до множини припустимих. Все було би добре, якщо б існувало єдине об’єктивне поняття “віддалі”, однак це не так - якщо на площині ми можемо з тим чи іншим обгрунтуванням застосовувати Евклідову метрику, то, наприклад, на поверхні кулі (земної також!) найкоротшою віддаллю буде дуга, а не пряма.

Таким чином, для розв’язання задачі за допомогою методу “ідеальної точки” необхідно насамперед визначити її координати, і надалі визначити метрику, за допомогою якої можна було б виміряти віддаль до оптимальної точки. Для визначення координат “ідеальної точки” розв’язуємо п однокритерійних задач за кожним з критеріїв оптимізації

Сукупність оптимальних значень критеріїв кожної з однокритерійних задач

і визначить координати ідеальної точки

в просторі критеріїв. Якщо “ідеальна точка” належить до множини припустимих (що зустрічається вкрай рідко), то розв’язок отриманий.

В іншому випадку визначаємо “віддаль” до ідеальної точки, вводячи метрику, і розв’язуємо однокритерійну задачу знаходження точки з числа припустимих, яка найменш віддалена від ідеальної. Таким чином задача матиме вигляд

«Идеальная точка» - идеальный объект в многомерном пространстве критериев, имеющий экстремальные значения всех критериев.

, где  - векторная оценка идеальной точки   в критериальном пространстве.

 – расстояние между альтернативой и идеальной точкой.

Нахождение оптимального решения сводится к отысканию альтернативы  , наиболее близкой к идеальной точке: 

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

Пример.

Пусть на множестве ω плоскости (x,y), определяемой системой неравенств

заданы две линейные функции:

U = x + y + 2 V = x - y + 6

(1)

Требуется найти решение задачи

U → max, V → max

Рассмотрим решение данной задачи методом идеальной точки.Множество ω представляет собой пятиугольник (рис. 7), вершины которого имеют следующие координаты:

A(0;0), B(0;2), C(2;2), D(4;1), E(4;0).

Рис. 7.

В силу линейности критериев U и V пятиугольник ABCDE переходит в пятиугольник A*B*C*D*E* (рис. 8), координаты вершин которого вычисляются по формулам (1):

A*(2;6), B*(4;4), C*(6;6), D*(7;9), E*(6;10).

Рис. 8.

Находим границу Парето. Это отрезок D*E*. Точка утопии M*(7;10) считается заданной (ее координаты суть наибольшее значение U и V).

Требуется найти на множестве Парето точку, ближайшую к точке утопии M*. Из рисунка видно, что искомая точка должна лежать на отрезке D*E*. Проведем через точки D* и E* прямую. Пусть

αU+βV=γ

− ее уравнение. Чтобы отыскать конкретные значения параметров α,β и γ, подставим в него координаты обеих точек D* и E*. Получим

6α+10β=γ,

7α+9β=γ.

Вычитая из первого равенства второе, после простых преобразований придем к соотношению

− α + β = 0,

откуда

α = β.

Положим α = β = 1. Тогда γ = 16 и

U + V = 16

− искомое уравнение прямой.

По условию задачи нам нужно определить на прямой

U + V = 16

точку M₀(U₀,V₀), расстояние которой от точки M*(7;10) минимально, т.е. решить экстремальную задачу:

z = (U − 7)² + (V − 10)² → min.

Так как U = 16 − V, то последнее соотношение можно переписать в виде

z = (9 − V)² + (V − 10)² → min..

Возведя в квадрат и приводя подобные, получаем, что

z = 2V² − 38V + 181→ min..

Это уравнение описывает параболу с вершиной

Тогда

U₀=16−V₀=16−9,5=6,5.

Идеальная точка

M₀(6,5;9,5)

Соответствующие значения x и y легко находятся из системы линейных уравнений

6,5 = x + y + 2

9,5 = x − y + 6

Имеем

x = 4, y = 0,5.