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

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

 

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

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

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

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

 

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

необходимо определить такой вектор переменных x = (x₁, x₂, … , x_n) из множества допустимых решений D, при котором значение векторной функции векторного аргумента F(x₁,x₂,…,x_n)={f₁ (x₁,x₂, … , x_n), f₂(x₁,x₂, … , x_n), … , f_k (x₁,x₂, … , x_n)} (где f_i(x₁,x₂, … , x_n) – i-ая скалярная целевая функция, i=1,k) достигает своего максимума (или минимума).

 

,  

 

       ,                                                        (5.1)

где x = (x₁,x₂, … , x_n) – вектор искомых переменных, а D – множество допустимых решений, заданное с помощью тех или иных ограничений.

   (первая)                                               (5.2)

где F(x) - векторная функция векторного аргумента. Поскольку в записи модели (5.2) используется векторная функция, многокритериальную задачу часто называют задачей векторной оптимизации.

 

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

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

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

Пример

 

 

 

 

 

 

 

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

 

 

 

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

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

 

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

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

 

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

Пусть решается задача (5.1) и есть x', x'' - допустимые решения данной задачи. Говорят, что x' более предпочтительное решение по сравнению с x'', если f _i (x') ≥ f _i (x'') i=1,k), причем i₀, такой, что  f _i (x') > f _i (x''). Другими словами, будем считать, что x' более предпочтительно по сравнению с x'' , если оно не хуже x'' по всем рассматриваемым критериям, причем среди всех критериев есть  хотя бы один критерий с номером i₀, для которого  решение x' лучше, чем x''

 

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

 

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

 

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

 

 

 

Принцип Парето

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

 

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

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

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

 

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

 

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

P(Д) Eⁿ.

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

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

F= ,т.е.

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

 

f₁( )=f_1max=6,

f₂(c)=f_1min=-4

 

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

 

f₂(B)= f₂ (C)=f_2max=4

f₂(Д)= f₂( )=f_2min=0

 

N%	x	f1(x)	f2(x)	Свойство решения
1	A=(2,2)	4	2	Эффективное	0.2	0.5
2	B=(1,4)	-1	4	Эффективное	0.7	0
3	C=(0,4)	-4	4	Слабоэффективное	1	0
4	Д=(0,0)	0	0	Не эффективное	0.6	1
5	E=(2,0)	6	0	эффективное	0	1

 

 

 

Нормализация  критериев

 

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

 

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

 

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

 

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

 

Пример

 

Если  , то

 

см. рис.3

 

 

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

 

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

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

 

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

Но наименьшие значения величин  или (x) , как правило,  не достигаются одновременно ни для какого решения из Д (т.е. нельзя подобрать x , чтобы (x) max или min min  .

 

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

 

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

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

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

 

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

 

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

 

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

 

Метод, основанный на этом положении называется методом ограничений.

Этот метод можно  рассматривать как метод решения  минимаксной задачи:

Таким образом решается задача:

(**)

Для задачи ЛП:

      

Если решение задачи (**) не единственное, то окончательное  решение получится с помощью  критерия

 

Пример

 

₁(x)=0.6-0.3 +0.1

₂(x)=1-0.25

 

             

 

 

 

1	-	-	-	1
=	-3	1	-20	-6
=	0	-1	-8	-4
=	1	0	0	2
=	0	1	0	4
=	2	1	0	6
Z	0	0	1	0