«Национальный исследовательский  университет 

  «Высшая школа  экономики» 

Факультет менеджмента

Отделение логистики 
 
 
 
 
 
 
 
 
 

Реферат на тему:

«Методы многокритериальной оптимизации. Оптимальность по Парето» 
 
 

Выполнил:

Студент группы 720л,

Елецкий А.А.  
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Москва, 2011

Оглавление

Введение 3

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

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

Принцип справедливого компромисса 4

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

Метод квазиоптимизации локальных критериев (метод последовательных уступок) 8

Метод свертывания векторного критерия в суперкритерий 11

Принцип оптимальности по Парето 12

Заключение 14

Список литературы 15 

Введение

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

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

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

• Отбор допустимых объектов,
• Упорядочение всех объектов относительно общей цели,
• Упорядочение допустимых объектов относительно общей цели (условная оптимизация),
• Упорядочение объектов относительно индивидуальных целей
• Упорядочение объектов по образцу,
• Нахождение наилучшего (среднего, наихудшего) объекта.

Различают 2 группы методов многокритериальной оптимизации на конечном множестве альтернатив: векторные и скалярные. Под векторной оптимизацией на конечном множестве объектов понимается нахождение варианта (альтернативы) с наилучшим значением векторного критерия. Наибольшее распространение получили следующие методы векторной оптимизации:

1. Оптимизация по Парето;
2. Лексиминная оптимизация;
3. Оптимизация по приоритету критериев (лексикографическая оптимизация).

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

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

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

max{f1(x)=F1}, 
max{f2(x)=F2}, 
... 
max{fk(x)=Fk}, при xєX, где

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

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

Принцип справедливого компромисса

Пусть все локальные  критерии, образующие вектор эффективности, имеют одинаковую важность. 
 
Справедливым будем считать такой компромисс, при котором относительный уровень снижения качества по одному или нескольким критериям не превосходит относительного уровня повышения качества по остальным критериям (меньше или равен). 
 
Этому принципу можно дать следующую математическую интерпретацию. Пусть в области компромиссов Гх даны два решения х’ и х’’, качество которых оценивается критериями F1(х) и F2(х). Решение х' превосходит решение х’’ по критерию F1, но уступает ему по критерию F2. Необходимо сравнить эти решения и выбрать наилучшие на основе принципа справедливого компромисса. 
Для сравнения этих решений на основе принципа справедливого компромисса введем меру относительного снижения качества решения по каждому из критериев – цену уступки x: 
 
 (3.1) 
 
где   и   — абсолютные снижения уровня критериев при переходе от решения х' к решению х'' (для критерия F1) и при обратном переходе (для критерия F2). 
 
Если относительное снижение критерия F1 больше, чем критерия F2, то следует отдать предпочтение решению х'. Это следует из сравнения цены уступки по каждому критерию. 
 
Алгоритм решения задачи векторной оптимизации, основанный на принципе справедливого компромисса, включает следующие шаги. 
 
Шаг 0. Выбираем х' и х’’є Dx. 
Шаг 1. Вычисляем по формулам (3.1) х1 и х2. 
Шаг 2. Если х1>х2, то выбираем х', если х1<х2. то выбираем х2. 
Шаг 3. Если не существует вектора хєX предпочтительнее xI или xII, то решение останавливается, иначе выбираем новый вектор xIII и переходим к шагу 1. 
 
Модель определения области компромиссов, а также модель справедливого компромисса инвариантны к масштабу измерения критериев. Однако первая из них является вспомогательной при выборе решения, а другая может быть использована только в тех ситуациях выбора решения, для которых идея справедливого компромисса может быть оправдана. Поэтому в большинстве случаев приходится прибегать к иным принципам оптимальности, имеющим смысл только в случае нормализованного пространства критериев, когда все локальные критерии имеют единый масштаб измерения. Однако в большинстве случаев масштабы измерения критериев неодинаковы, и возникает необходимость проводить нормализацию критериев, т. е. искусственно приводить их к единой мере. 
 
Большинство принципов нормализации основывается на введении идеального решения, т. е. решения, обладающего идеальным вектором эффективности Fи. Это идеальное решение можно априорно предположить исходя из информации об объекте, а можно решить задачу оптимизации для каждого локального критерия и соответствующее этим решениям значение вектора эффективности принять за идеальный вектор эффективности Fи. Тогда выбор оптимального решения становится равнозначным наилучшему приближению к этому идеальному вектору Fи = (Fи , … , Fиn) В этом случае вместо действительного значения критериев рассматриваются или их отклонение от идеального значения 
 
dFj=Fиj - Fj (3.2) 
 
или их безразмерное относительное значение 
 
 (3.3) 
 
При решении данной проблемы используются оба способа нормализации. Таким образом, успешное решение проблемы нормализации во многом зависит от того, насколько точно и объективно удается определить идеальное качество решения. 
 
После нормализации критериев эффективности задача выбора решения приобретает ясный математический смысл. В теоретико-множественном отношении она становится задачей упорядочивания ограниченных векторных множеств, а с точки зрения теории приближений – задачей приближения в метрическом конечномерном пространстве. Это дает возможность проводить обоснованный выбор принципов оптимальности и выявлять их логический смысл. 
 
Итак, для данного случая принцип оптимальности идентичен принципу приближения, а обобщенный скалярный критерий оптимизации – критерию приближения, являющемуся некоторой функцией отклонения от идеальной функции. 

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

В основу данного  подхода положена идея приближения  по всем критериям. 
 
Пусть дана задача многокритериального программирования 
 
max{f1(x)=F1}, 
max{f2(x)=F2}, (3.11)  
 
max{fk(x)=Fk}, xєX,  
 
и заданы граничные условия 
(3.12) 
(3.13) 
x1>=0, x2>=0, …, xn>=0. (3.14) 
 
Среди решений системы (3.11) – (3.14) требуется отыскать такое значение вектора х*(х*1, … , х*n), при котором локальные критерии примут по возможности максимальное (минимальное) значение одновременно. 
 
Рассмотрим каждую отдельную функцию fi(x) и допустим, что для каждого фиксированного i (i=1,m) решена задача максимизации. Пусть соответствующие оптимальные планы характеризуются векторами 
 
xoi(xo1, xo2,…, xon), i=1,m (3.15) 
 
На этих оптимальных планах определим значения критериев соответственно 
 
Foi=(Fi(xo1), Fi(xo2),…, Fi(xon)) (3.16) 
 
Естественно, что векторы (3.15), определяющие векторы точки в пространстве переменных (x1, x2,…, xn)є  , будут разными: некоторые из них могут совпадать друг с другом. 
 
Рассмотрим вектор F(х) с компонентами F(x)|Foi из (3.15) и составим квадрат евклидовой нормы 
 
(3.17) 
 
вектора F(x) - Fo, определенного для всех xє  . 
 
Заметим, что Fo будет представлять собой единичный вектор в пространстве вектора F(x). Назовем его идеальным значением вектора F(x). Поставленная задача теперь сформулируется так: дана система целевых функций (3.11) и даны условия задачи (3.12) – (3.14). Требуется определить точку xє  , в которой функция R(x) достигает минимума. 
 
Таким образом, отыскание векторно-оптимального плана xє  в данной задаче сведено к оптимизации выражения (3.17) на решениях системы линейных неравенств (3.12) – (3.14). Поскольку выражение (3.17) представляет собой квадратичную функцию переменных х1, …, хп, то задача отыскания векторно-оптимального плана свелась к задаче выпуклого программирования: 
 
Задана выпуклая функция R(x), определенная на множестве xє  . Требуется отыскать точку xє , обеспечивающую выполнение условия R(x*) = minR(x), xє . 
 
Таким образом, алгоритм решения задачи (3.11) – (3.14) состоит из двух основных этапов: 
этап 1: maxFi(x), i=1, m; 
этап 2: min R(x). 
 

Метод квазиоптимизации локальных критериев (метод последовательных уступок)

В этом случае осуществляется поиск не единственного точного  оптимума, а некоторой области  решений, близких к оптимальному, – квазиоптимального множества. При этом уровень допустимого отклонения от точного оптимума определяется с учетом точности постановки задачи (например, в зависимости от точности вычисления величины критериев), а также некоторых практических соображений (например, требований точности решения задачи). 
 
Вначале производится качественный анализ относительной важности критериев; на основании такого анализа критерии располагаются и нумеруются в порядке убывания важности, так что главным считается критерий F1, менее важен F2, затем следуют остальные локальные критерии F3, F4,.. ., Fm. Максимизируется первый по важности критерий F1 и определяется его наибольшее значение M1. Затем назначается допустимое снижение (уступка) d1>=0 критерия F1. Определим новую допустимую область X(1), как подобласть X вида 
 
X(1) = Xn{x|F1(x)>=M1-d1} (3.18) 
 
Такой подход позволяет значительно сузить первоначальную допустимую область X, когда переходим к следующему по важности критерию. 
 
После этого находим наибольшее значение М2 второго критерия F2 на множестве X(1) , т. е. при условии, что значение первого критерия должно быть не меньше, чем M1-d1. Снова назначается значение уступки d2>=0, но уже по второму критерию, которое вместе с первым используется при нахождении условного максимума третьего критерия, и т. д. Наконец, максимизируется последний по важности критерий Fm при условии, что значение каждого критерия Fr из m—1 предыдущих должно быть не меньше соответствующей величины Мr - dг; получаемые стратегии считаются оптимальными: 
 
X(i) = X(i-1)n{x|Fi(x)>=Mi-di} 
 
Таким образом, оптимальной считается всякая стратегия, являющаяся решением последней задачи из следующей последовательности задач: 
 
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, то решением многокритериальной задачи считают максимизирующую последовательность {xk} из последовательности множеств 
 
Xm-1 Xm-2  …  X1  X 
 
Практически подобные максимизирующие последовательности имеет смысл рассматривать и для того случая, когда верхняя грань в задаче m достигается, так как для решения экстремальных задач широко применяются итеративные методы. 
 
Алгоритм решения задачи векторной оптимизации включает следующие шаги. 
 
Шаг 1. Пусть х01 — решение задачи (3.19) 
max Fl(x), xєX 
Шаг 2. Пусть xok - решение задачи 
max Fk(x), xєX(k-1) 
где Xk определяется из (3.19). 
Шаг 3. Если k<m, то устанавливаем k=k+1 и повторяем шаг 2. Если k = m, то хom считаем оптимальным решением. 
 
Алгоритм закончен. 
 
Значения уступок di (i=1,m) последовательно назначаются при изучении взаимосвязи частных критериев. 
 
Вначале решается вопрос о назначении допустимого снижения d1 первого критерия от наибольшего значения М1. Практически для этого задают несколько величин уступок d11 ,d21, d31 ... и путем решения задачи (3.19) определяют соответствующие максимальные значения М2(d11), М2(d21), М2(d31),... второго критерия. Далее рассматривают пару критериев F2 и F3. Вновь назначают пробные значения уступок d12 , d22 ... и, решая задачу (3.21), отыскивают наибольшие значения М3(d12), М3(d22). Полученные данные анализируют, назначают d2, переходят к следующей паре критериев F2 и F3 и т. д. Наконец, в результате анализа взаимного влияния критериев Fm-l и Fm выбирают значение последней уступки dm-1 и отыскивают оптимальные стратегии, решая задачу m из (3.19) (обычно ограничиваются нахождением одной такой стратегии). 
 
Таким образом, хотя формально при использовании метода последовательных уступок достаточно решить лишь от задач (3.19), однако для назначения значения уступок с целью выяснения взаимосвязи частных критериев фактически приходится решать существенно большее число таких задач. 
 
Для решения многокритериальной задачи нужно так ранжировать критерии, чтобы потом удобнее было выбирать значения уступок. 
 
Учитывая вышеизложенное, можно сделать следующий вывод. Метод последовательных уступок целесообразно применять для решения тех многокритериальных задач, в которых все частные критерии естественным образом упорядочены по степени важности, причем каждый критерий настолько существенно более важен, чем последующий, что можно ограничиться учетом только попарной связи критериев и выбирать допустимое снижение очередного критерия с учетом поведения лишь одного следующего критерия. 
 
Особенно удобным является случай, когда уже в результате предварительного анализа многокритериальной задачи выясняется, что можно допустить уступки лишь в пределах «инженерной» точности (5-10% от наибольшей величины критерия).