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

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

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

Необходимо отметить, что необоснованность сужения множества Парето является существенным недостатком многих методов многокритериальной оптимизации. Многокритериальная оптимизация: Математические аспекты /Б.А Березовский, Ю.М. Барышников и др. - М.: Наука, 1989. - 128 с.

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

Первый подход. Для заданной многокритериальной задачи оптимизации находится множество её Парето-оптимальных решений, а выбор конкретного оптимального варианта из множества Парето-оптимальных предоставляется ЛПР.

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

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

Указание верхних границ критериев. Дополнительная информация об оптимальном исходе XoptD в этом случае имеет вид

Число Ci рассматривается здесь как верхняя граница по i - му критерию.

Отметим, что указание верхних границ по критериям не может быть "извлечено" из математической модели задачи принятия решения; набор ограничений (C1, C2, , Cm) представляет собой дополнительную информацию, полученную от ЛПР.

Задача. Выбор места работы.

Предположим, что Вам предстоит выбрать место работы из девяти вариантов, представленных в табл.1. В качестве основных критериев взяты: зарплата З, длительность отпуска Д, время поездки на работу В. Из смысла задачи следует, что критерии З и Д следует максимизировать, а критерий В - минимизировать. Какой вариант является оптимальным?

Таблица 1

Решение. Выделим вначале Парето-оптимальные варианты. Отбрасывая доминируемые по Парето варианты {1, 2, 8, 9}, получаем Парето-оптимальное множество {3, 4, 5, 6, 7}. При отсутствии информации об относительной важности рассматриваемых критериев, а также о каких-либо дополнительных свойствах оптимального решения дальнейшее сужение Парето-оптимального множества произвести нельзя. Тогда формальный анализ заканчивается указанием Парето-оптимального множества, и окончательный выбор оптимального варианта производится ЛПР из этих пяти вариантов на основе каких-то дополнительных соображений.

Рассмотрим теперь второй подход, который приводит к сужению Парето-оптимального множества на основе дополнительной информации, получаемой от ЛПР.

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

зарплата -- не менее 600 рублей;

длительность отпуска -- не менее 30 дней;

время поездки -- не более 40 минут.

Варианты, удовлетворяющие этим дополнительным ограничения: {3, 6, 9}; из них оптимальными по Парето являются варианты 3 и 6. Остаётся сделать окончательный выбор между вариантами 3 и 6.

б) Субоптимизация. Пусть в качестве выделенного (главного, важнейшего) критерия выступает критерий зарплата; ограничения длительность отпуска -- не менее 30 дней, время поездки -- не более 40 минут. Отбросим варианты, которые не удовлетворяют данным ограничениям; остаются варианты: {2, 3, 5, 6, 9}. Из них максимальную зарплату имеет вариант 3. Этот вариант и будет оптимальным.

в) Лексикографическая оптимизация. Упорядочим критерии по относительной важности. Например, следующим образом: (т.е. важнейший критерий -- зарплата, следующий за ним по важности время поездки, наименее важный критерий длительность отпуска). Максимальное значение по критерию З имеют варианты 1 и 7. Далее сравниваем эти варианты по второму по важности критерию В. Так как время поездки для этих вариантов одинакова, переходим к третьему критерию Д; по критерию длительность отпуска лучшим является вариант 7, который и является здесь оптимальным.

Задание. Проверьте, что при упорядочении оптимальным является вариант 6, а при упорядочении - оптимальным становится вариант 5.

Методы ЭЛЕКТРА [1]

Группа методов (ЭЛЕКТРА 1, ЭЛЕКТРА 2, ЭЛЕКТРА 3) предложена профессором Б. Руа (Франция). В этих методах бинарное отношение предпочтения (более сильное, чем отношение Парето) строятся следующим образом.

Для каждого из m критериев (предполагаются, что критерии числовые) определяется вес - число, характеризующее важность соответствующего критерия. Для того чтобы определить, превосходит ли вариант X1 вариант X2, производятся следующие действия.

Множество критериев разбивается на три подмножества:

· критерии, по которым X1 превосходит X2;

· критерии, по которым X1 и X2 имеют одинаковые оценки;

· критерии, по которым X2 превосходит X1.

Далее определяется относительная важность каждого из этих подмножеств. Устанавливается некоторый порог c и считается, что вариант X1 превосходит X2 только в том случае, когда некоторая функция (называемая индексом согласия) удовлетворяет условию

f()?c

Условие (1) является необходимым, но не достаточным условием превосходства X1 над X2. В некоторых методах ЭЛЕКТРА формулируется дополнительные условия, которые предназначены учитывать не только порядок следования оценок X1 над X2 по критериям, но и значения их разностей.

Проведём анализ описанного метода.

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

Существую ситуации, когда ЛПР сообщает информацию о критериях качественного типа.

Например, при назначении весов критериям, по которым следует выбрать автомобиль: цена (критерий 1), важнее комфортности (критерий 2), а та, в свою очередь, важнее, чем скоростные качества (критерий 3) и внешний вид автомобиля (критерий 4). Кроме того, критерии 3 и 4 имеют одинаковую важность, а, рассматриваемые совместно, имею большую важность, чем критерий 1 (цена).

p1> p2>p3= p4, p3+ p4> p1.

Один из вариантов назначения весовых коэффициентов: p1=5; p2=4; p3=p4=3.

Множество критериев разбивается на три подмножества;

Далее определяется относительная важность , как сумма весов, входящих в них критериев.

В качестве условия (1) предлагается (ЭЛЕКТРА 1) взять выражение

Зам. Если мы выбрали нормированные весовые коэффициенты, то ?i=pi и

Рассмотрим пример. Пусть у нас имеются два решения X1 и X2, которые оцениваются по 5 критериям (F1, F2, F3, F4, F5):

F(X1)=(5,3,2,7,2); F(X2)=(4,2,3,5,1).

Численные методы получения множеств Парето

Часто используют следующий подход.

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

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

Рис.11. Левый рисунок - область D и P (красная линия), правый рисунок - область векторных оценок YD и КК (красная линия)

Тема Методы определения весовых коэффициентов

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

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

f(X)= ifi(X) - аддитивный критерий;

f(X)= - мультипликативный критерий;

ifi(X)=K, - равенство частных критериев,

где fi(X)= Fi(X)/ Fi0(X), Fi0(X) - нормирующий множитель.

Для рассматриваемых методов многокритериальной оптимизации существенным является исходное упорядочивание критериев. Иногда их порядок очевиден ("кошелёк или жизнь") или общепризнан (как порядок букв в алфавите), но бывает, что этот вопрос не тривиален, а привлекаемые для его решения эксперты дают несовпадающие упорядочения критериев. Выход состоит в том, чтобы установить, какое из предложенных экспертами упорядочений является "средним", “типичным” для данной группы. Это опять-таки можно делать по-разному. Среди специалистов пользуется признанием упорядочение, называемое медианой Кемени.

Весовые коэффициенты должны качественно отражать важность соответствующих частных критериев. Значения i выбираются исходя из анализа мирового уровня развития данной отрасли, из требований к проектируемому объекту и из существующих возможностей реализации этих требований. Открытие новых физических принципов и разработка новых методов проектирования могут существенно влиять на значения весовых коэффициентов. Величина i определяет важность го критерия оптимальности и задает в количественном измерении предпочтение го критерия над другими критериями оптимальности. Весовые коэффициенты i должны удовлетворять условию . В связи с этим возникает вопрос: "Как выбирать численные значения весовых коэффициентов i?". Получить ответ на этот вопрос, в какойто степени можно, если имеется дополнительная информация о важности частных критериев оптимальности.

Экспертные оценки.

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

Метод ранжирования.

Метод ранжирования заключается в следующем. Пусть экспертиза проводится группой из L экспертов, которые являются квалифицированными специалистами в той области, где принимается решение. Метод ранжирования основан на том, что каждого эксперта просят расставить частные критерии проектируемого объекта в порядке их важности. Цифрой 1 обозначают наиболее важный частный критерий, цифрой 2 - следующий по важности частный критерий и т.д. Эти ранги преобразовываются таким образом, что ранг 1 - получает оценку m, ранг 2 - оценку m-1 и т.д. до ранга m, которому присваивается оценка 1. Обозначим полученные оценки rik - где i - i - й эксперт, k - k - й критерий. Тогда результаты опроса экспертов можно свести в таблицу

, i=1,2, …,m.

В (L+1) - строке стоят суммы оценок, полученных критериями от экспертов. Тогда весовые коэффициенты определяются следующим образом

- (i=1,2, . . . , m)

формула для вычисления весовых коэффициентов i по методу ранжирования.

Рассмотрим пример. Пусть имеются группа из трёх экспертов и два критерия F1 и F2. Эксперты их расставили в следующем порядке.

Определим элементы матрицы согласно алгоритму (первому месту - два балла, а второму - один балл): r11=2, r12=1, r21=1, r32=1.

=5+4=9; 1=r1/9=5/9; 2=r2/9=4/9.

Таким образом, 1>2 и 1 - й критерий важнее 2 - го.

Метод приписывания баллов.

Этот метод основан на том, что эксперты оценивают важность частного критерия по шкале [0-10]. При этом разрешается оценивать важность дробными величинами или приписывать одну и ту же величину из выбранной шкалы нескольким критериям. Обозначим через hik - балл i - го эксперта для k- критерия, тогда

где - сумма i - ой строки.

rik - называют весом, подсчитанным для k - критерия i - м экспертом. Отсюда, учитывая, что

, получим

Пример. Пусть имеются два критерия F1 и F2. Эксперты поставили им следующие баллы.

F1 F2

1 9 6 h11=9, h12=6; 1=15

2 10 6 h21=10, h22=6; 2=16

3 10 5 h31=10, h32=5; 3=15

Построим матрицу оценок

Находим сумму значений каждой строки

Вычислим веса rik

r11=h11/15=9/15, r12=h12/15=6/15, r21=h21/16=10/15, r22=h22/16=6/16, r31=h31/15=10/15, r32=h32/15=5/15.

Построим матрицу весов и найдём сумму значений каждого столбца

ri=1.892+1.108=3.

Вычисляем весовые коэффициенты

1=1.892/3=0.631, 2=1.108/3=0.369.

Таким образом, 1>2 и 1 - й критерий важнее 2 - го критерия.

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

Тогда для метода ранжирования ri будем рассчитывать по формулам

Аналогично получаем для метода приписывания баллов

Замечание. Иногда значения j выбирают из интервала (0 1).

Обработка результатов экспертных оценок.

Если рассматривать результаты оценок каждого из экспертов как реализации некоторой случайной величины, то к ним можно применять методы математической статистики. Среднее значение оценки для i - го критерия

Среднее значение выражает коллективное мнение группы экспертов.

Степень согласованности мнений экспертов характеризуется величиной

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

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

Индивидуальные экспертные оценки также носят на себе печать случайности: настроение, самочувствие, обстановка, а также знание и опыт.

Формальные методы определения весовых коэффициентов.

Рассмотрим некоторые способы и числовые приемы, позволяющие по информации о качестве значений частных критериев оптимальности определять значения весовых коэффициентов ?i.

Способ 1. Для каждого частного критерия оптимальности Fi(X)>0, вычисляется коэффициент относительного разброса по формуле:

,

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

Пример 1. В качестве примера рассмотрим конкретную числовую задачу в следующей постановке:

При этом имеем следующие значения промежуточных вычислений:

Тогда весовые коэффициенты будут иметь следующие значения:

,

т.к. ?2>?1, то локальный критерий F2 важнее локального критерия F1.

Способ 2. Пусть все , тогда рассматриваются коэффициенты

которые характеризуют отклонение частного критерия оптимальности от его наименьшего значения.

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

Здесь величины задаются ЛПР из условия, что чем важнее критерий, тем меньше выбирается значение .

Пусть - наибольший радиус шара, построенного около точки минимума - -го критерия оптимальности, внутри которого точки (шар радиуса с центром в ) удовлетворяют условию (1).

Тогда

при условии

.

Теперь очевидно, что чем больше радиус шара , в котором относительное отклонение -го критерия от его минимального значения не превосходит , тем меньше надо выбирать значение весового коэффициента ?i:

Пример 2. Рассмотрим задачу из примера 1 и положим, что ЛПР задал , . Тогда будем иметь

при ,

при .

Откуда

т.к. ?1>?2, то локальный критерий F1 важнее локального критерия F2.

Методы замены векторного критерия скалярным.

Одним из подходов к поиску компромиссного решения задач векторной оптимизации является сведение её к задаче параметрической оптимизации, т.е. сведение её к однокритериальной (скалярной) оптимизации. Иначе говоря, частные критерии Fi(X), тем или иным способом объединяются в составной (обобщенный, интегральный) критерий f(X)=Ф[F1(X), F2(X), . . . , Fm(X)], который затем оптимизируется. Под построением обобщённого критерия в МЗО понимается процедура, которая "синтезирует" набор оценок по заданным частным критериям, в единую численную оценку, выражающую итоговую полезность этого набора оценок для ЛПР. Формально обобщённый критерий для МЗО, представляет собой функцию Ф: , где Yj - множество оценок по j - критерию. Если обобщённый критерий Ф построен, то для каждого допустимого исхода XD может быть найдена численная оценка его полезности (ценности, эффективности): f(X)= Ф[F1(X), F2(X), . . . , Fm(X)]. Таким образом, задание обобщённого критерия сводит задачу многокритериальной оптимизации к задаче однокритериальной оптимизации с целевой функцией f(X). Наиболее распространённым обобщённым критерием является "взвешенная сумма частных критериев", которая превращает векторную оценку в скалярную оценку.

Метод взвешенных сумм (Метод линейной свертки)

Идея этого метода заключается в том, что обобщённый критерий записывается в следующем виде:

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

XD XD

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

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

q в качестве нормирующих делителей берут максимальные значения критериев, достигаемых в области существования проектных решений (область D);

q берут лучшие мировые достижения в данной области;

q в качестве нормирующего берут разность между max и min значениями критерия в области D

или

Нормированные критерии будем обозначать через fi(X), т.е. аддитивный критерий примет вид

Какой определён принцип оптимальности?

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

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

В случае f<0 решение X2 признаётся лучшим, чем X1, если f>0, то лучше X1. Тогда оптимальным решением будет такое, для которого f0 при переходе от него к любому другому решению, т.е.

где Xopt - точка min, X любая точка из D.

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

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

где m1+m2=m. Обобщённый критерий f(X) - максимизируется.

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

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

Рассмотрим пример. Пример взят из книги [В.П. Корячко, В.М. Курейчик, И.П. Норенков. Теоретические основы САПР]. Переносной автомат для забивания стальных дюбелей в бетонные стены состоит из корпуса с магазином, содержащим запас дюбелей; подающего-спускового механизма с зарядами и ствола. Требуется определить основные конструктивные параметры автомата - длину ствола L и число дюбелей -N при следующих исходных данных:

число дюбелей , N12;

масса одного дюбеля с зарядом равна m=50 г;

масса ствола 1.6 кг/м;

масса корпуса 2 кг.

При фиксированной величине заряда и заданной массе дюбеля скорость V выбрасывания связана с длиной ствола L соотношением V=k; где k=. Минимально допустимая скорость Vmin=100 м/cек. Масса автомата не должна превышать 6 кг. Частными критериями являются скорость выбрасывания и число дюбелей, помещающихся в магазине. Выбор этих критериев объясняется тем, что чем выше V, тем надёжнее дюбеля проникают в бетонные стены любой марки, а чем больше N, тем удобнее работать. По мнению экспертов оба критерия V и N имеют одинаковую важность.

Введём обозначения: F1(N,L)= k - первый критерий (скорость);

F2(N,L)=N - второй критерий (число дюбелей).

Сформулируем задачу многокритериальной оптимизации:

maxF=max(F1, F2)

при следующих ограничениях

N12;

V100;

1.6L+ 0.05N+26.

Построим область D (см. рис.1) и критериальное пространство и определим компромиссную кривую (КК) (см. рис.2).

Рис.1. Область D

Для определения оптимальных значений параметров будем использовать аддитивный критерий

Так как критерии имеют одинаковую важность, то весовые коэффициенты можно взять равными единице.

Рис.2. Критериальное пространство и КК

В качестве нормирующих делителей возьмём максимальные значения критериев, достигаемых в области существования проектных решений (область D). Для определения нормирующих делителей будем использовать уравнение баланса (массу автомата). Найдем Nmax из условия, что Vmin=100 м/cек. Определяем длину ствола, соответствующую минимальной скорости L=и подставляем в уравнение баланса. Получим, что Nmax=66. Аналогично находим, т.е. берём N=12 и подставляем в уравнение баланса. Получим Vmax=219 м/cек.

Таким образом, мы получили следующую задачу оптимизации:

найти максимум функции

при ограничении 1.6L+ 0.05N+26.

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

при ограничении 1.6L+0.05N+2=6.

Для определения максимального значения f(L,N) с учётом ограничения равенства мы будем использовать метод неопределённых множителей Лагранжа. Получим следующую задачу безусловной оптимизации:

найти максимум функции

Находим частные производные по L, N, и приравниваем их к нулю. Получим систему уравнений:

Решая эту систему, получим следующие значения: , , или =-4/13=0.308, Nopt=64, Lopt=0.499 м, Vopt=106 м/cек.

Аддитивный критерий имеет ряд недостатков:

q Он выступает как формальный математический приём, придающий задаче удобный для решения вид;

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

q Более того, оказывается, что сумма оценок основана на следующем неявном постулате: "низкая оценка по одному критерию может быть компенсирована высокой оценкой по другому". Однако, этот постулат верен отнюдь не всегда. Например, пусть качество оператора ввода текстов оценивается двумя критериями: 1) скорость ввода (символов в минуту) и 2) среднее количество ошибок на страницу текста. Очевидно, что ухудшение качества ввода (увеличение количества ошибок) не может быть компенсировано увеличением скорости ввода. Можно даже сказать, что в области оценки персонала такая ситуация типична. Скажем, недостаток компетентности не может быть компенсирован повышенным уровнем активности. Скорее наоборот! Вспомним шутливое изречение: "Кто может быть хуже дурака? Дурак с инициативой!"

Замечание. Хотя аддитивный критерий подвергается сильной критике, но существуют задачи, где критерий качества должен удовлетворять аддитивности. Например, в динамическом программировании эффект от управления процессом F складывается из элементарных эффектов fk, полученных на отдельных шагах процесса: F=fk.

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

Мультипликативный критерий

Аддитивный критерий основан на использования принципа справедливой компенсации значений нормированных частных критериев. Но в ряде задач проектирования более целесообразным является оперирование не с абсолютными, а с относительными изменениями значений частных критериев.

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

В математической формулировке условие оптимальности на основе принципа справедливой относительной компенсации имеет вид

где ?Fi(X) - приращение величины i - го критерия, Fi(X) - первоначальная величина i - го критерия.

Полагая , можно представить (3) как дифференциал натурального логарифма

Из выражения (4) следует, что принцип относительной компенсации приводит к мультипликативному обобщённому критерию оптимальности

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

Мультипликативный критерий иногда представляется в виде отношения произведений частных критериев (выходных параметров)

m1+m2=m

где в числителе перемножаются все выходные параметры, требующие максимизации и имеющие ограничения а в знаменателе - все выходные параметры, требующие минимизации и имеющие ограничения

где TTi - значение технического требования, предъявленного к i- му критерию. Целевая функция (7) в дальнейшем подвергается максимизации.

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

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

где Yt - выпуск продукции; L - численность рабочих; K - объём основных производственных фондов. Здесь величины и 1- следует рассматривать как весовые коэффициенты.

Пример 2. Обнаружение сигналов в "белом" шуме. На вход RC - фильтра с импульсной характеристикой поступает аддитивная смесь: прямоугольный импульс s(t) плюс "белый" шум n(t). Требуется найти такое значение , чтобы отношение сигнал/шум было максимальным, т.е. мы желаем, чтобы значение сигнала было максимальным, а уровень шума - минимальным ( - полоса пропускания RC - фильтра).

Рис.3. Сигнал s(t)

Рис 4.Шум n(t)

Рис. 5.Сигнал плюс шум

Рис.6. Отфильтрованный сигнал

Рис. 7.Система обнаружения сигнала

F1()=A(1-e-T) max (уровень сигнала на выходе фильтра),

F2()= min (уровень шума на выходе фильтра).

где A,N,T - константы; F1 и F2 - имеют одинаковую размерность. Найти оптимальную полосу пропускания , если справедлив принцип относительной компенсации частных критериев. Согласно формуле (7) мультипликативный критерий будем иметь вид:

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

найти максимум функции

при ограничении 1.6L+ 0.05N+2?6.

Для определения максимального значения f(L,N) с учётом ограничения равенства мы будем использовать метод неопределённых множителей Лагранжа. Получим следующую задачу безусловной оптимизации:

найти максимум функции

Находим частные производные по L, N, и приравниваем их к нулю. Получим систему уравнений:

Решая эту систему, получим следующие значения: Nopt=53, Lopt=0.83 м, Vopt=137 м/cек.

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

Заключение. Преимущества и недостатки формальных обобщённых критериев.

Преимущества - возможность учёта в качестве fi(X) любых выходных параметров системы, а также надёжность и стоимость.

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

Метод "идеальной" точки

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

Определим обобщенный критерий следующим образом. Положим ai=maxFi(X); , т.е. ai является максимально (минимально) возможным значением по i - му критерию. Положим a=(a1, a2, . . ., am). Точка a называется идеальной. Смысл названия связан с тем, что такие точки оптимальны сразу по всем критериям - получить большее (меньшее) значение ни по одному критерию невозможно. Как правило, точка aYD. Зададим для всех точек YYD функцию, являющуюся евклидовым расстоянием между точками Y и a

За целевую функцию (обобщённый критерий) берут выражение

где i - весовые коэффициенты.

Таким образом, задача оптимизации формулируется следующим образом

min

XD

С учётом нормировки

min

XD

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

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

Какие задачи оптимального проектирования приводят к использованию метода идеальной точки?

Например, когда все или основные условия работоспособности имеют вид равенств, т.е. Fi(X)=TTi, где TTi - значение технического требования, предъявленные к i - критерию. Тогда целевая функция имеет вид:

Пример. Пусть имеются частные критерии F1(X)=-3x1+2x2; F2(X)=4x1+3x2; F3(X)=2x1-5x2, которые требуется максимизировать. Область D задаётся неравенствами -x1-3x2+180; -2x1-x2+100; x10; x20. Линейная функция F1(X) достигает максимального значения a1=12 в точке X1=(0, 6); F2(X) - максимальное значение a2=24 в точке X2=(3, 4); F3(X) - максимальное значение a3=10 в точке X3 =(5, 0). По методу идеальной точки составим функцию f(X)=[12-(-3x1+2x2)]2+[24-(4x1+3x2)]2+[10-(2x1-5x2)]2. После преобразований получим f(x1, x2)=.

Таким образом, задача оптимизации будет такая

min f(x1, x2)

g1(X)= -x1-3x2+180

g2(X)= -2x1-x2+100

g3(X)=x1?0; g4(X)=x2?0

Построим область D.

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

Находим частные производные по x1 и x2 функции f(x1, x2) и приравняем их к нулю. Получим следующую систему линейных уравнений

29x1-4x2=80

-4x1+38x2=46.

Решение этой системы: x1=2.97; x2=1.52. Эта точка находится внутри области D. Следовательно, минимум функции достигается в точке с координатами x1opt=2.97; x2opt=1.52.

В найденной точке Xopt, являющейся решением рассматриваемой многокритериальной задачи линейного программирования, F1(Xopt)=-5.87; F2(Xopt)=16.44; F3(Xopt)=-1.66.

Следовательно, x1opt=2.97; x2opt=1.52.

Вопросы:

· Сложности в построении обобщённого критерия; примеры.

· Формальное определение обобщённого критерия. Эквивалентность обобщённых критериев.

· Локальный коэффициент замещения (ЛКЗ). Карта безразличий. Условия постоянства ЛКЗ.

1. Как было сказано ранее, задание обобщённого критерия превращает задачу многокритериальной оптимизации в задачу однокритериальной оптимизации. Первоначально кажется, что это единственный способ. Однако на пути построения обобщённого критерия (итоговой “синтетической” оценки) имеются весьма существенные, а подчас - непреодолимые препятствия.

В качестве примера можно рассмотреть задачу построения обобщённой оценки некоторой реальной системы (объекта). Частные критерии оценки системы можно разбить на две группы: критерии, отражающие эффективность системы, и критерии, связанные со стоимостью системы. Предположим, что уже удалось построить обобщённый критерий эффективности (Э) и обобщённый критерий стоимости (С). Как теперь соединить критерий стоимости и эффективности в один критерий? Наиболее естественным представляется в качестве такой оценки рассматривать “удельную эффективность”, т.е. отношение эффективности к стоимости: f=Э/С. Так как обобщённый критерий указывает “итоговую” оценку полезности системы для принимающего решение, то по величине обобщённого критерия устанавливается предпочтение между сравниваемыми объектами.

Рассмотрим теперь показатели стоимости и эффективности для трёх систем: a0, a1, a2, представленные на рис. 9. Здесь f0 = Э0/С0, f1 = Э1/С1, f2 = Э2/С2, причём f1 > f0, f2 > f0

Рис. 9. Отношение эффективности к стоимости для трёх систем

Из рисунка можно определить, что f1 = = 1, f0 = = , f2 = = .

Таким образом, по обобщённому критерию системы a1 и a2 являются более предпочтительными, чем система a0. Однако система a1 имеет очень низкую эффективность, а система a2 - очень высокую стоимость. Ясно, с практической точки зрения ни система a1, ни система a2 не могут рассматриваться как удовлетворительные. Поэтому критерий f=Э/С не может претендовать на роль “адекватного” обобщённого критерия. Отметим, что даже на первом шаге - объединении всех частных критериев эффективности в единый обобщённый критерий (Э) можно встретиться с весьма существенными трудностями, особенно в случае наличия критериев, характеризующих объект с разных сторон (например, скорость автомобиля и его надёжность).

Обратимся теперь к проблеме построения обобщённого критерия в виде взвешенной суммы частных критериев, которая превращает векторную оценку y = (y1, . . . , ym) в скалярную оценку Ф(y) = ?1y1 + … + ?mym ,(где ?j o, j = ). Предложено множество различных способов нахождения весовых коэффициентов, однако ни один из них не может претендовать на роль универсального. Рассмотрим в качестве примера следующий способ нахождения весовых коэффициентов:

?J =

где Mj = |fj(x)|

В этом случае

f(x) =

т.е. итоговой численной оценкой исхода а, является сумма нормализованных оценок по всем критериям (нормализованная оценка по j-му критерию есть отношение fj(x)/Mj). На первый взгляд, обобщённый критерий (8) представляется вполне разумным. Однако, следующий пример выявляет один существенный недостаток критерия (8).

Предположим, требуется сравнить два альтернативных варианта мест работы А и В, векторные оценки которых приведены в табл.1

Таблица 1

Здесь M1 = 900, М2 = 30, М3 = 60, откуда

f(A) = + - = ; f(B) = + - = .

Так как f(B) > f(A), то альтернатива В более предпочтительна, чем альтернатива А.

Пусть теперь наряду с альтернативами А и В появилась ещё одна альтернатива С, которая характеризуется векторной оценкой (400, 60,-100). В этом случае = 900, = 60, = 100, откуда f(A) = + - = ;

f(B) = + - = ; f(C) = + - = .

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

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

2. Рассмотрим теперь в общем виде проблему построения обобщённого критерия для многокритериальных задач принятия решений. Ограничимся случаем двух критериев, оценки по которым будем обозначать через u и v соответственно; тогда каждая векторная оценка может быть представлена точкой на координатной плоскости (u, v). Считаем, что оба критерия являются позитивными, следовательно, целью принимающего решение будет увеличение обоих критериев.