Задача многокритериальной оптимизации

Лекция №2 Задача многокритериальной оптимизации Задача многокритериальной оптимизации возникает в тех случаях, когда при принятии решений приходиться руководствоваться несколькими целями, которые не могут быть отражены единым критерием. Имеет место т.н. неопределенность цели. Постановку задачи многокритериальной оптимизации будем формулировать в следующем виде: Определить (1) В (1) - n-мерный вектор взвируемых параметров; - область допустимых значений вектора Х (альтернатив); - векторная целевая функция. Множество (2) называется множеством достижимых векторных оценок (аналогично области значений функций). Таким образом выбор оптимального решения из допустимого множества D сводится к выбору оптимальной векторной оценки из множества допустимых векторных оценок , которая доставляет всем компонентам векторной целевой функции минимальные (максимальные) значения. Обычно множество D задается системой неравенств: (3) Задача (1), (3) называют конечномерной задачей многокритериальной оптимизации (М0). Основное отличие рассматриваемой задачи М0 от классической задачи нелинейного программирования (НГ) состоит в следующем. В задаче нелинейного программирования область значений функции является отрезком (т.к. - скаляр). Поэтому решение задачи нелинейного программирования состоит в В задаче М0 множество является m-мерным. Поэтому элемента , доставляющего минимальные значения всем компонентам векторной целевой функции , как правило, не существует. , где . Поэтому в задаче (1), (2) понятие оптимальности требует определения. С этой целью введем понятие бинарного отношения строго предпочтения (Для определенности будем рассматривать задачу на . Определение 1 Бинарным отношением на множество достижимых векторных оценок называется совокупность упорядоченных где Если , то говорят, что находятся в отношении , и этот факт записывают так: Для описания предпочтений ЛПР широко используются следующие бинарные отношения строгого предпочтения. Определение 2. Отношение строгого предпочтения означает, что объект строго предпочтительнее, чем определяется следующим образом: (3) Геометрическая интерпретация () определения 2 Точка должна находиться внутри конуса или на его гранях, исключая величину . Определение 3. Элемент называется минимальным (недоминируемым) по на множестве , если в не существует элемента , строго более предпочтительного, чем , т.е. если не имеет места ни при каких Геометрическая интерпретация определения 3 () Определение 4. Векторная оценка минимальная по вида (3), называется оптимальной по Парето (эффективной). Множество векторных оценок, минимальных по на множестве , называется множеством Парето (эффективным множеством) и обозначается . Геометрическая интерпретация множества Парето () - множество Парето. Множество Парето может иметь более сложные конфигурации в зависимости от конфигурации множества допустимых векторных оценок. Пример 1. Множество Парето: Замечание Если задача решается на максимум: Определить , то отношение строгого предпочтения имеет вид , и множество Парето имеет следующую геометрическую интерпретацию - множество Парето Пример 2 (Задача многокритериального ЛП) Построить множество Парето для случаев: А) б) А) Пространство параметров: Пространство критериев: А) Множество Парето: отрезок C’D’в пространстве критериев Б) Множество Парето: отрезок А’В’в пространстве критериев Дискретное множество F(D) В этом случае можно использовать алгоритм многокритериаяльного ранжирования по Парето. Алгоритм включает в себя следующие основные шаги. Пусть N – количество точек в F(D). Шаг 1. Полагаем . Шаг2. Вычисляем параметр в к-количество точек, для которых выполняется условие: (4) Шаг3. Вычисляем функцию: (5) Шаг 4. Если , то переходим к шагу 5, иначе – к шагу 6. Шаг 5. Шаг6. Из точек множества F(D) формируем подмножество обладающее следующим свойством Это подмножество будет множеством Парето Замечание Функция обладает следующими свойствами: 1) , при ; 2) , при ; 3) 4) Пример. Рассмотрим множество F(D) в виде таблицы (задача на ) № Парето 1 3 8,5 1 + 2 9 6 3 3 7,5 9,5 3 0,75 4 4,5 5,5 1 + 5 11 9 6 6 7 3 1 + 7 12 6 6 0,6 8 11,5 4 3 0,75 9 8 1 10 1 + 10 10,5 1,5 1