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

07.12.202322.04.2022 admin 0 Comments

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

Тема магистерской работы: «Разработка моделей и программных средств для многокритериальной оптимизации сложных объектов в компьютерных информационных системах»

Руководитель: доцент кафедры АСУ Лаздынь Сергей Владимирович

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

Результаты исследования задач планирования и управления показывают, что в реальной постановке эти задачи являются многокритериальными. Так, часто встречающееся выражение «достичь максимального эффекта при наименьших затратах» уже означает принятие решения при двух критериях. Оценка деятельности предприятий и планирования как системы принятия решений производится на основе более десятка критериев: выполнение плана производства по объему, по номенклатуре, плана реализации, прибыли по показателям рентабельности, производительности труда и т. д.

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

Впервые проблема оптимизации векторного критерия была сформулирована экономистом Парето в 1896 г.

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

Покажем, насколько широк диапазон проблем, которые могут быть адекватно сформулированы как многокритериальные, и какие характеристики следует использовать в качестве критериев.

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

Задача многокритериального математического программирования имеет вид:

X – множество допустимых значений переменных х;
k – число целевых функций (критериев);
Fi – значение i-го критерия (целевой функции),
“max” – означает, что данный критерий нужно максимизировать.

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

При наличии в многокритериальной задаче критериев с разной размерностью с целью устранения данной проблемы используют нормализацию критериев. Способы нормализации представлены в таблице 2.1.

Таблица 2.1. Способы нормализации.

Нормализация	Математическое выражение
Сведение к безразмерным величинам
Приведение к одной размерности
Смена ингридиента
Естественная нормализация
Нормализация сравнения
Нормализация Савиджа
Нормализация осреднения

В данной таблице y – элемент пространства G. G – пространство элементов произвольной природы, называемых целевыми термами (в конкретных интерпретациях это совокупность, перечень или нумерация качественных свойств) элементов xєX.

Сверткой компонент многоцелевого показателя fєF называется отображение gєR1>, которое преобразует совокупность компонент многоцелевого показателя f, соответствующих целевым термам yєY, в скалярный целевой показатель g(f(x|y)= g[yєY]єR1. Основными видами сверток являются линейные, минимизационные, максимизационные, произведения и функции Кобба-Дугласа вида:

Проблемы получения и обоснования выбора сверток составляют основное направление теории полезности.

К настоящему времени сформулированы основные принципы выбора, приведенные в таблице 2.2.

Таблица 2.2. Принципы выбора.

Принцип выбора	Условие оптимальности
Доминантности
Частичной доминантности
Парето
Слейтера
Собственно эффективности Джерри
Несобственно эффективности Джерри
Равенства
Суммарной эффективности
Нэша
Компромисса
Доминирующего результата
Гарантированного результата
Наименьшего уклонения
ламбда-критерия
альфа-критерия Гурвица
Максимума функции неопределенности

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

Вектор называется оптимальным по Парето решением, если не существует хєХ такого, что выполнены неравенства
и

Областью компромиссов Гх называется подмножество допустимого множества решений Х, обладающего тем свойством, что все принадлежащие ему решения не могут быть улучшены одновременно по всем локальным критериям — компонентам вектора эффективности. Следовательно, для любых двух решений, принадлежащих области Гх(х’, x»єГх ), обязательно имеет место противоречие хотя бы с одним из локальных критериев. Это автоматически приводит к необходимости проводить выбор решения в Гх на основе некоторой схемы компромисса, что и послужило причиной для названия этого подмножества областью компромиссов.

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

Пусть все локальные критерии, образующие вектор эффективности, имеют одинаковую важность.

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

Этому принципу можно дать следующую математическую интерпретацию. Пусть в области компромиссов Гх даны два решения х’ и х’’, качество которых оценивается критериями F1(х) и F2(х). Решение х’ превосходит решение х’’ по критерию F1, но уступает ему по критерию F2. Необходимо сравнить эти решения и выбрать наилучшие на основе принципа справедливого компромисса.
Для сравнения этих решений на основе принципа справедливого компромисса введем меру относительного снижения качества решения по каждому из критериев – цену уступки x:

где и — абсолютные снижения уровня критериев при переходе от решения х’ к решению х» (для критерия F1) и при обратном переходе (для критерия F2).

Если относительное снижение критерия F1 больше, чем критерия F2, то следует отдать предпочтение решению х’. Это следует из сравнения цены уступки по каждому критерию.

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

Шаг 0. Выбираем х’ и х’’є Dx.
Шаг 1. Вычисляем по формулам (3.1) х1 и х2.
Шаг 2. Если х1>х2, то выбираем х’, если х1 (3.3)

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

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

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

Вектор х1єХ называется слабо оптимальным по Парето решением (оптимальным по Слейтеру), если не существует вектора х1єХ, такого, что

Пусть xoj (i=1,m) есть оптимальные решения для обычных скалярных оптимизационных задач, каждая из которых максимизирует компоненту Fi(х) вектора F (х):

Если они являются максимальными решениями для каждой i, то считаем, что Fj(xoj) >Fi(xj) (i=1,m), где xoj — оптимальное решение задачи (3.4).

Положим, что Soj изображает множество решений, каждое из которых соответствует компоненту Fj, и
Soj = Fi(x)>=Fj(x)oj—aj, i=1,m; (3.8)
хєХ. (3.9)

Здесь задача (3.6) – (3.9) неразрешима, если аj не настолько велико, что пересечение непусто. Величины аj должны быть определены на основе значений Fj(xoj) или анализа точности. Можно доказать, что оптимальное решение задачи (3.6) – (3.9) есть оптимальное решение по Парето.

Алгоритм решения задачи имеет следующие этапы.

Шаг 1. Полагаем l=1 и решаем задачу

max z (3.10)
х, z при
Fj(x)>=z;
Fi(x)>=Fj(x)oj—aj, i=1,m; хєХ.

Вызываем исходное решение x1 и оцениваем целевую функцию F(x1).

Шаг 2. Когда хl задано, разлагаем F(хl) на удовлетворительные и неудовлетворительные
компоненты. Обозначим их соответственно через Sl и l.

Ш а г 3. Решаем задачу
max z
х, z
при условии
Fj(x)єz, jє l ;
Fi(x)>=Fj(x)oj—aj, jєSl; хєХ.

Вызываем исходное решение xl+l. Если xl+1=xl, то задача будет неразрешимой; если xl+1<>xl, то полагаем 1 = 1+1 и возвращаемся к шагу 2.

При этом алгоритм заканчивается.

В основу данного подхода положена идея приближения по всем критериям.

Пусть дана задача многокритериального программирования

и заданы граничные условия
(3.12)
(3.13)
x1>=0, x2>=0, …, xn>=0. (3.14)

Рассмотрим каждую отдельную функцию fi(x) и допустим, что для каждого фиксированного i (i=1,m) решена задача максимизации. Пусть соответствующие оптимальные планы характеризуются векторами

xoi(xo1, xo2,…, xon), i=1,m (3.15)

На этих оптимальных планах определим значения критериев соответственно

Foi=(Fi(xo1), Fi(xo2),…, Fi(xon)) (3.16)

Рассмотрим вектор F(х) с компонентами F(x)|Foi из (3.15) и составим квадрат евклидовой нормы

Таким образом, отыскание векторно-оптимального плана xє в данной задаче сведено к оптимизации выражения (3.17) на решениях системы линейных неравенств (3.12) – (3.14). Поскольку выражение (3.17) представляет собой квадратичную функцию переменных х1, …, хп, то задача отыскания векторно-оптимального плана свелась к задаче выпуклого программирования:

Таким образом, алгоритм решения задачи (3.11) – (3.14) состоит из двух основных этапов:
этап 1: maxFi(x), i=1, m;
этап 2: min R(x).

В этом случае осуществляется поиск не единственного точного оптимума, а некоторой области решений, близких к оптимальному, – квазиоптимального множества. При этом уровень допустимого отклонения от точного оптимума определяется с учетом точности постановки задачи (например, в зависимости от точности вычисления величины критериев), а также некоторых практических соображений (например, требований точности решения задачи).

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

Таким образом, оптимальной считается всякая стратегия, являющаяся решением последней задачи из следующей последовательности задач:

1) найти M1= supF1(x), xєX;
2) найти M2= supF2(x), xєX; (3.19)
…
m) найти Mm= supFm(x), xєX;

Если критерий Fm на множестве стратегий, удовлетворяющих ограничениям задачи m) из (3.19) не достигает своего наибольшего значения Мm, то решением многокритериальной задачи считают максимизирующую последовательность из последовательности множеств

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

Алгоритм решения задачи векторной оптимизации включает следующие шаги.

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

При этом возникают трудности с правильным подбором весовых коэффициентов аi.

Существуют различные способы выбора коэффициентов аi. Одним из них является назначение аi в зависимости от относительной важности критериев. Такой подбор указанных коэффициентов можно выполнять согласно таблице:

Общие сведения о генетических алгоритмах.

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

Простой ГА случайным образом генерирует начальную популяцию структур. Работа ГА представляет собой итерационный процесс, который продолжается до тех пор, пока не выполнятся заданное число поколений или какой-либо иной критерий остановки. На каждом поколении ГА реализуется отбор пропорционально приспособленности, одноточечный кроссовер и мутация. Сначала, пропорциональный отбор назначает каждой структуре вероятность Ps(i) равную отношению ее приспособленности к суммарной приспособленности популяции. Затем происходит отбор (с замещением) всех n особей для дальнейшей генетической обработки, согласно величине Ps(i). Простейший пропорциональный отбор – рулетка – отбирает особей с помощью n «запусков» рулетки. Колесо рулетки содержит по одному сектору для каждого члена популяции. Размер i-ого сектора пропорционален соответствующей величине Ps(i). При таком отборе члены популяции с более высокой приспособленностью с большей вероятность будут чаще выбираться, чем особи с низкой приспособленностью.

После отбора, n выбранных особей подвергаются кроссоверу (иногда называемому рекомбинацией) с заданной вероятностью Pc. – n строк случайным образом разбиваются на n/2 пары. Для каждой пары с вероятностью Pc может применяться кроссовер. Соответственно с вероятностью 1-Pc кроссовер не происходит и неизмененные особи переходят на стадию мутации. Если кроссовер происходит, полученные потомки заменяют собой родителей и переходят к мутации.

Одноточечный кроссовер работает следующим образом. Сначала, случайным образом выбирается одна из l-1 точек разрыва. (Точка разрыва – участок между соседними битами в строке.) Обе родительские структуры разрываются на два сегмента по этой точке. Затем, соответствующие сегменты различных родителей склеиваются и получаются два генотипа потомков.

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

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

Обобщенная блок-схема генетического алгоритма.

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

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

Первая проблема связана с выбором принципа оптимальности, который строго определяет свойства оптимального решения и отвечает на вопрос, в каком смысле оптимальное решение превосходит все остальные допустимые решения. В отличие от задач однокритериальной оптимизации, у которых только один принцип оптимальности f(xо)>=f(x), в данном случае имеется большое количество различных принципов, и каждый принцип может приводить к выбору различных оптимальных решений. Это объясняется тем, что приходится сравнивать векторы эффективности на основе некоторой схемы компромисса.

В математическом отношении эта проблема эквивалентна задаче упорядочения векторных множеств, а выбор принципа оптимальности – выбору отношения порядка.

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

Третья проблема связана с учетом приоритета (или различной степени важности) локальных критериев. Хотя при выборе решения и следует добиваться наивысшего качества по всем критериям, однако степень совершенства по каждому из них, как правило, имеет различную значимость. Поэтому обычно для учета приоритета вводится вектор распределения важности критериев L=(l1, l2. ln), с помощью которого корректируется принцип оптимальности или проводится дифференциация масштабов измерения критериев.

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

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

Возможными путями решения рассмотренных выше проблем многокритериальной оптимизации может быть применение рассмотренных в пункте 2 сверток и способов нормализации.

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

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

Таким образом, будущая работа заключается в следующем. Вначале будет выбран математический аппарат для решения задачи многокритериальной оптимизации с предварительным обоснованием выбора. Затем будет разработано программное обеспечение для многокритериальной оптимизации конкретного объекта либо процесса в соответствии с выбранным методом. Примерное содержание магистерской работы выглядит следующим образом:

Введение.
1. Анализ существующих методов и моделей многокритериальной оптимизации.
2. Разработка математической модели выбранного технологического объекта.
3. Разработка метода многокритериальной оптимизации для выбранного объекта.
4. Разработка программного обеспечения ля выбранного объекта.
5. Проведение экспериментов по многокритериальной оптимизации и анализ полученных результатов.
6. Обобщение результатов исследований и разработка рекомендаций по их использованию.
Заключение.

Источник

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

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

Многокритериальная задача оптимизации – математическая модель принятия оптимального решения одновременно по нескольким критериям.

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

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

Математическая постановка многокритериальной задачи (далее МЗ) представляется следующим образом:

, (5.1)

Сущность многокритериальной задачи (5.1) (или (5.2) состоит в нахождении такого решения, принадлежащего области допустимых решений (т. е. такого x Î D), которое в том или ином смысле максимизирует (или минимизирует) значения всех целевых функций f i(x), где i = 1, …, k.

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

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

или, что то же самое:

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

Найдем субоптимальные решения для Примера 5.1. Из графика, приведенного на рис. 5.1 видно, что

Рис. 5.1. Субоптимальные решения задачи Примера 5.1.

5.2. Основные определения теории векторной оптимизации. Принцип Парето

Введем несколько определений.

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

Множество эффективных решений называется множеством Парето и обозначается P(D). Очевидно, множество Парето является подмножеством множества допустимых решений, которое, в свою очередь принадлежит n-мерному векторному пространству, т. е. P(D) D En.

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

Смысл введенного понятия эффективного решения состоит в том, что оптимальное решение следует искать только среди элементов множества P(Д)

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

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

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

Рассмотрим введенные понятия на примере.

Решение xl называется слабоэффективным решением задачи (*), если для него не существует решения xll такого, что i=1,k f(xl) > f(xll), другими словами, слабоэффективное решение – решение, которое не может быть улучшено одновременно по всем критериям.

P(Д)En.

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

Схемы построения слабоэффективных и эффективных решений основываются, как правило, на ряде теорем.

F=,т. е.

D(2,0)- субоптимальное решение по f1,

f1()=f1max=6,

B(1,4), C(0,4) – субоптимальные решения по f2 (y=b+(1-)c)

f2(Д)= f2()=f2min=0

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

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

2. быть монотонным преобразованием, т. к. должно сохранять отношение предпочтения на множестве Д, т. е. не менять множество Парето

3. учитывать необходимость минимизации отклонения от оптимальных значений по каждой целевой функции

Обыкновенно в качестве таких преобразований используют следующие:

причем , т. е. минимизируется разность между наилучшим решением и оптимальным.

Если , то

Компромиссное решение в задачах многокритериальной оптимизации

Недостаток принципа Парето в том, что он предлагает в качестве решения – множество решений, что не всегда приемлемо.

Для того, чтобы выбрать из этого множества единственное решение нужны какие-то дополнительные сведения, предположения, договоренность о том, что же считать наилучшим решением (некоторая дополнительная неформальная информация…).

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

Существует теорема: Если x0 – эффективное решение для данного вектора предпочтений , то ему соответствует наименьшее значение , при котором система равенств = выполняется для всех i=1,k.

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

Пример. 1-й критерий в 2 раза значимее по сравнению со 2-м

Т. о. — вектор предпочтений

Тогда в качестве решения задачи (*) можно принять компромиссное решение с заданным вектором предпочтений, под таким решением будем понимать эффективное решение x0, которое обеспечивает одинаковые минимальные значения параметра , при котором эта система совместна.

Это подтверждается следующей теоремой:

Компромиссное решение может быть найдено как единственное решение системы неравенств вида для минимального значения параметра , при котором эта система совместна.