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

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

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

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

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

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

Выполнил:

Студент группы 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% от наибольшей величины критерия). 

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

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

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

Вектор х1єХ называется слабо оптимальным по Парето решением (оптимальным по Слейтеру), если не существует вектора х1єХ, такого, что  
 
 
 
Пусть xoj (i=1,m) есть оптимальные решения для обычных скалярных оптимизационных задач, каждая из которых максимизирует компоненту Fi(х) вектора F (х): 
 
 (3.4) 
 
Если они являются максимальными решениями для каждой i, то считаем, что Fj(xoj) >Fi(xj) (i=1,m), где xoj — оптимальное решение задачи (3.4). 
 
Положим, что Soj изображает множество решений, каждое из которых соответствует компоненту Fj, и 
Soj = {x|Fj(x)?<=Fj(xoj)+aj} (3.5) 
 
где aj представляет допустимое количество ограничений соответствующей области по отношению к Fj. Тогда оптимальное достаточное решение это такое решение, при котором минимальный компонент (наихудший компонент) максимизируется на множестве, удовлетворяющем достаточному условию хєХ и хєSo1nSo2n…,Som. Оно может быть сформулировано как 
 
max z (3.6) 
х, z при 
Fj(x)>=z; (3.7) 
Fi(x)>=Fj(x)oj—aj, i=1,m; (3.8) 
хєХ. (3.9) 
 
Здесь задача (3.6) – (3.9) неразрешима, если аj не настолько велико, что пересечение {S°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. 
 
Если Sl , тогда эта задача считается неразрешимой, а если Sl  , то х1 — оптимальное, отвечающее требованиям решение. Если  <>   и Sl<>  , то для jєSl определяется аlj>0, допустимое по отношению к Fj(xl) [аlj=0 означает, что j-я целевая функция fj(x) не может принимать значение, отличное от fj (xl)]. 
 
Ш а г 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. 
 
При этом алгоритм заканчивается. 
 
 
 

Заключение

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

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

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

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

1. Г. М. Уланов и др. Методы разработки интегрированных АСУ промышленными предприятиями. М.: Энергоатомиздат – 1983.  
2. А. М. Анохин, В. А. Глотов, В.В. Павельев, А.М. Черкашин. Методы определения коэффициентов важности критериев “Автоматика и телемеханика”, №8, 1997, с3-35. 
3. Таха, Хэмди А. Введение в исследование операций – М.:Мир,2001, с354-370. 
4. Р. Штойер. Многокритериальная оптимизация: теория, вычисления, приложения. М.:Наука, 1982, с14-29, 146-258. 
5. Многокритериальная оптимизация. Математические аспекты. М.:Наука, 1989, с116-123. 
6. В.В. Подиновский, В.Д. Ногин. Парето-оптимальные решения многокритериальных задач. М.: Наука, 1982, с9-64. 
7. В. В. Хоменюк. Элементы теории многокритериальной оптимизации. М.: Наука, 1983, с8-25.