Методы последовательной оптимизации - документ.

Введение

Суть метода последовательных уступок

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

Исследование метода последовательных уступок

Список использованной литературы.

ВВЕДЕНИЕ

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

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

СУТЬ МЕТОД А ПОСЛЕДОВАТЕЛЬНЫХ УСТУПОК

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

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

ПОРЯДОК РЕШЕНИЯ ДЕТЕРМИНИРОВАННЫХ МНОГОКРИТЕРИАЛЬНЫХ ЗАДАЧ МЕТОДОМ ПОСЛЕДОВАТЕЛЬНЫХ УСТУПОК

При решении многокритериальной задачи мето­дом последовательных уступок вначале производит­ся качественный анализ относительной важности частных критериев; на основании такого анализа критерии располагаются и нумеруются в порядке убывания важности, так что главным является критерий K 1 , менее важен. K 2 , затем следуют остальные частные критерии К 3 , К 4 ..., K S . Максимизируется первый по важности критерий K 1 и определяется его наибольшее значение Q 1 . Затем назначается величина «допустимого» снижения (уступки) D 1 >0 критерия K 1 и ищется наибольшее значение Q 2 второго критерия K 2 при условии, что значение первого критерия должно быть не меньше, чем Q 1 -D 1 . Снова назначается величина уступки D 2 >0, но уже по второму критерию, которая вместе с пер­вой используется при нахождении условного макси­мума третьего критерия, и т. д. Наконец, максими­зируется последний по важности критерий Ks при условии, что значение каждого критерия К r из S-1 предыдущих должно быть не меньше соответствую­щей величины Q r -D r ; получаемые в итоге страте­гии считаются оптимальными.

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

1) найти Q 1 =

2) найти Q 2 =

………………………………..

3) найти Q S =

Если критерий K S на множестве стратегий, удов­летворяющих ограничениям задачи S), не достигает своего наибольшего значения Q s , то решением мно­гокритериальной задачи считают максимизирую­щую последовательность стратегий {u k } из указан­ного множества (lim K S (u k) = Q S).

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

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

Величины уступок D r последовательно назнача­ются в результате изучения взаимосвязи частных критериев.

Вначале решается вопрос о назначении величи­ны допустимого снижения D r первого критерия от его наибольшего значения Q 1 . Практически для это­го задают несколько величин уступок D 1 1 , D 2 1 , D 3 1 … и путем решения 2) в задаче (1) определяют соответствующие макс. значения Q 2 (D 1 1), Q 2 (D 2 1), Q 2 (D 3 1), и второго критерия. Иногда, если это не слишком сложно, отыскивается функция Q 2 (D 1). Результаты расчетов для наглядности Представляем графически (Рис 1)

	Рис 1

Он показывает, что вначале даже небольшие величины уступок позволяют получить существенный выигрыш по вто­рому критерию; с дальнейшим увеличением уступки выигрыш растет все медленнее. На основе анализа полученных данных и решают вопрос о назначении величины уступки D 1 , а затем находят Q 2 (D 1).

Далее рассматривают пару критериев K 2 и K 3 вновь назначают «пробные» величины уступок Q 2 (D 2 2), ... и, решая 3) в задаче (1), отыскивают наибольшие значения третьего критерия Q 3 (D 1 2), Q 3 (D 2 2),... Полученные данные анализируют, назначают D 2 , переходят к следующей паре критери­ев К 3 , K 4 и т. д.

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

Таким образом, хотя формально при использо­вании метода последовательных уступок достаточно решить лишь S задач (1), однако для назначе­ния величин уступок с целью выяснения взаимосвя­зи частных критериев фактически приходится ре­шать существенно большее число подобных задач.

ИССЛЕДОВАНИЕ МЕТОДА ПОСЛЕДОВАТЕЛЬНЫХ УСТУПОК

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

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

Пример 1. Пусть множество U Ì R 3 - многогранник, изображенный на рис.2 , K 1 (u)=u1, K 2 (u)=u 2, K 3 (u)=u 3 . Здесь решением 3 из задачи (1) является любая точка треугольника ABC (на рисунке он заштрихован), но эффек­тивны лишь точки отрезка АС.

Справедливо, однако, утверждение: если u* - единственная (с точностью до эквивалентности) стратегия, являющаяся решением S) из задачи (1), то она эффективна.

Действительно, предположим, что стратегия u* неэффективна, так что существует стратегия u">u*. Но стратегия u" также удовлетворяет всем огра­ничениям S) задачи (1) и доставляет кри­терию K S значение Q s ; иначе говоря, u" оказыва­ется решением этой зада­чи, что противоречит ус­ловию единственности u*. Утверждение доказано.

Можно доказать так­ же, что если UÌR n за­мкнуто и ограничено, К r непрерывны на U, а стратегия, являющаяся реше­нием S) задачи (1), единственна с точностью до эквивалентности, то любая максимизирующая последовательность, служащая решением S), эффективна.

Пример 2. Пусть U Ì R n - выпуклое множество,

а все К r квазивогнуты. При этих условиях множество стратегий, удовлетворяющих ограничениям r) задачи (1), также выпукло (r=1,2, ..., S), так что каждая из задач 1), 2),..., S) является задачей квазивогнутого программирования. Если Ks строго квазивогнут, то решением задачи S) может служить лишь единственная и потому эффективная стратегия; если же |при этом U замкнуто и ограничено, а все К r непрерывны на U, то любая максимизирующая последовательность, являющаяся решением S), эффективна.

Пример 3. Предположим, что из многогранника U задачи, описанной в примере 1, удалена вся грань А"В"С", но оставлена точка В. Теперь эта точка оказывается единственным решением 3) задачи (1). Здесь точка В, конечно, эффективна. Любая сходящаяся к ней последовательность внутренних точек многогранника, удовлетворяющих ограниче­ниям задачи 3), будет максимизирую щей для Ks, но не будет эффективной. Указанное положение - следствие не замкнутости рассматриваемого в данном примере множества U.

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

В общем случае на этот вопрос положительный ответ дать нельзя, однако имеет место такое утверждение: если UÌR n - множество замкнутое и ограниченное, а все К r непрерывны, то решением S) задачи (1) служит по крайней мере одна эффективная стратегия.

Действительно, при выполнении условий этого утверждения множество U s стратегий-решений S) оказывается непустым, замкнутым и огра­ниченным. Следовательно, существует точка u*ÎU S , в которой функция достигает наибольшего на U s значения. Нетрудно убедиться в том, что u* эффективна.

Таким образом, при решении почти всякой при­кладной многокритериальной задачи метод последо­вательных уступок выделяет в качестве оптималь­ных и эффективные стратегии. Однако необходимо отметить, что выделенные эффективные стратегии не обязаны быть эквивалентными (см. пример 1); но нетрудно проверить, что это возможно лишь при S³3.

Если нельзя гарантировать, что при решении рассматриваемой многокритериальной задачи метод последовательных уступок приводит к получению лишь эффективных стратегий (в частности, если по выполняется вышеприведенное условие единст­венности), то для выделения эффективной страте­гии среди решений задачи S) достаточно, как пока­зывает только что проведенное доказательство,

Однако практически более удобно применять такой прием: заменить в S) критерий K s на,

где À - положительное число;

в результате получится задача:

Нетрудно доказать, что любая стратегия, являющаяся решением задачи (3), эффективна; более того, всякая максимизирующая последовательность, служащая решением этой задачи, также эффективна.

Смысл указанного приема заключается в том, что при достаточно малом числе À>0 для любой полученной в результате решения задачи (3) стратегии w значение критерия K S (w) будет весьма близким к Q s *) и эта стратегия эффективна, в то время как при решении S) задачи (1) может быть получена стратегия и, которую выгодно заме­нить некоторой эффективной стратегией v>u, су­щественно лучшей, чем и, но одному или даже не­скольким частным критериям. А поскольку величи­ны уступок А, на практике устанавливаются при­ближенно, то замена Ks на K* s при малых À>0 в силу указанной причины оказывается допустимой и оправданной.

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

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

Теорема 1.

Для любой эффективной стратегии u* существуют такие числа D * r , что эту стратегию можно выделить методом последовательных уступок, т. е.
при D r= D * r , r=1, 2,...,S-1, стратегия u* являет­ся единственным (с точностью до эквивалентности) решением S) задачи (1).

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

Более того, теорема 1 позволяет исследовать и сам метод последовательных уступок. Действи­тельно, она показывает, что при любом фиксирован­ном расположении частных критериев, по степени относительной важности одним лишь выбором ве­личин уступок можно обеспечить выделение любой эффективной стратегии в качестве оптимальной (так что проблема отыскания оптимальной страте­гии, т. е. проблема выбора эффективной стратегии из всего множества U°, формально эквивалентна проблеме назначения надлежащих величин уступок при произвольном фиксированном упорядочении критериев).

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

Особенно удобным является случай, когда уже в результате предварительного анализа многокритериальной задачи выясняется, что можно допустить уступки лишь в пределах «инженерной» точности (6-10% от наибольшей величины критерия).

Решение многокритериальной задачи методом последовательных уступок - процедура довольно трудоемкая, даже если заранее выбраны величины всех уступок. Поэтому большой интерес представляет вопрос: можно ли при заданных D i получить оптимальную стратегию за один этап, сведя после­довательность задач (1) к одной экстремальной задаче?

Мы можем указать лишь приближенный способ одноэтапного решения для S=2. Он основан на следующем утверждении:

Лемма 1.

Пусть множество UÌR p замкнуто и ограничено, K 1 и К 2 непрерывны на U, D 1 ³0 и À£ D 1 /M 1 2 , где

Тогда для любой стратегии u*, доставляющей функции L=K 1 +ÀК 2 наибольшее на U значение, справедливо неравенство Q 1 -K 1 (u*)£ D 1 причем если K 1 (u*)£ Q 1 , то

Эта лемма, показывает, что если решить задачу максимизации на U функции L=K 1 +ÀК 2 , в кото­рой число À назначено указанным образом, то для полученной стратегии u* (она обязательно эффек­тивна) значение K 1 (u*) будет отличаться от максимального Q 1 не более, чем на D 1 , a K 2 (u*) будет тем ближе к Q 2 , чем точнее назначена оценка М 1 2 .

Однако даже если взять число М 1 2 , удовлетворяю­щее (4) как равенству, и положить À = D 1 /M 1 2 , то все равно нельзя гарантировать, что K 2 (u*)=Q 2 , так что рассматриваемый способ действительно является приближенным.

Пример 4. Пусть U - четверть единичного круга, ле­жащая в положительном квадранте: U={u: uÎR 2 , u 2 1 +u 2 2 £1, u 1 ³0, u 2 ³0} K 1 (u)=u 1 , K 2 (u)=u 2 . Здесь Q 1 = l и М 1 2 =1, если исходить из (4) как равенства. Примем D 1 =0,2; À=0,2.

Функция u 1 + 0,2u 2 достигает максимума на U в единственной точке так что, однако

Пример 5. U={u: uÎR 2 , 0£u 2 £1, (1+d)u 2 £1-u 1 } где d - положительное число, K 1 (u)=u 1 , K 2 (u)=u 2 . Исполь­зуя (4) как равенство, находим: М 1 2 = 1. Положим D 1 =1; À=1. Функция u 1 +u 2 достигает на U максимума в един­ственной точке (1, 0). Возьмем теперь; À=1 + e. где e- любое сколь угодно малое положительное число. Тогда при d точ­ке (-d, 1), так

что Q 1 -K 1 (-d, 1) = 1+d >D 1 =1.

Примечание. Для решения многокритериальных задач иногда применяют метод выделения основного частного кри­терия. Этот метод состоит в том, что исходная многокритери­альная задача сводится к задаче оптимизации по одному частному критерию К L , который объявляется основным, или главным, при условии, что значения остальных частных кри­териев К r должны быть не меньше некоторых установленных величин («требуемых» значений) b r , т. е. к задаче

причем оптимальной считается обычно всякая стратегия, яв­ляющаяся решением задачи (5).

Выделение критерия K t в качестве основного и назна­чение пороговых величин b r , для остальных частных критериев фактически означает, что все стратегии разбиваются на два класса. К одному относятся стратегии, которые удовлетворяют всем S-1 ограничениям K r (u)³b r ; такие стратегии можно назвать допустимыми. К другому классу относятся такие стратегии, которые не удовлетворяют хотя бы одному из указаных S-1 неравенств. Наконец, среди допустимых стратегий предпочтительнее считается та, для которой значение Критерия K l больше.

Необходимо отметить, что установившееся название - «ос­новной», или «главный» критерий - по существу весьма условно. Действительно, критерий K l максимизируется на множестве лишь допустимых стратегий; иначе говоря, если для стратегии u значение некоторого «второстепенного» частного критерия K r оказывается хоть немного меньше, чем b r , то она уже не может «претендовать» на роль оптимальной, сколь бы большим ни было для нее значение основного критерия. Сравнение (5) и (1) показывает, что метод после­довательных уступок формально можно рассматривать как особую разновидность метода выделения основного частного критерия, отличающуюся наличием специфической процедуры назначения величин ограничений для задачи максимизации K S (это обстоятельство фактически уже использовалось при доказательстве теоремы 1).

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

Где À>0 – достаточно малое число.

Выбор конкретной эффективной стратегии из множества U 0 формаль­но эквивалентен назначению надлежащих величин b r , причем в качестве основного можно выбрать любой частный крите­рий.

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

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

Таким образом, предварительное выделение одного из ча­стных критериев основным еще никак не уменьшает свободы выбора эффективной стратегии (так что название «основной», или «главный» критерий действительно весьма условно). Сле­довательно, при качественном анализе конкретной многокри­териальной задачи вопрос о выделении одного из частных критериев в качестве основного следует решить так, чтобы облегчить назначение величин ограничений на остальные частные критерии.

Практически назначается серия «наборов» {b r } пороговых значений и для каждого «набора» отыскивается соответствую­щее наибольшее значение основного критерия (при этом сле­дует учитывать данные выше рекомендации, относящиеся к обеспечению (получения лишь эффективных стратегий, а так­же иметь в виду, что при произвольно назначенных числах b r может случиться, что задача (5) вообще не имеет смыс­ла, так как ни одна стратегия не удовлетворяет входящим в нее ограничениям).

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

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

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

Список использованной литературы.

1) Подиновский В.В. , Гаврилов В. М. Оптимизация по последовательно применяемым критериям. М., «Сов. радио», 1975, 192 стр.

Интерактивные методы ориентированы на решение МКЗ, в которых требуется выделить наиболее предпочтительный объект (решение). В некоторых методах удается упорядочить объекты по предпочтению.

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

В данном разделе рассмотрены различные по своим подходам методы. Первые два метода: метод уступок иметод смещенного идеала относятся к разным группам методов. Последующие три метода относятся к группе методов, позволяющих устанавливать бинарные отношения между объектами (outranking). В этих методах между объектами устанавливаются отношения: предпочтения (),безразличия (~)или несравнимости (N). Одним из первых методов этой группы былметод ELECTRE ,получивший свое развитие вметоде PROMETHEE . К этой же группе относится иметод ORESTE , но он существенно отличается от вышеперечисленных методов. Изложенные в данном разделе методы дают представление о многообразии интерактивных методов решения МКЗ.

Метод уступок

Данный метод позволяет выделить наиболее предпочти­тельный объект из конечного исходного множества.

Основная идея метода заключается в поэтапном исключе­нии доминируемых объектов. Для установления доминирования между конкурирующими по двум критериям объектами используются коэффициенты замещения критериев. Блок-схема метода приведена на рис.2.1. Рассмотрим метод на примере.

Пусть стоит задача выбора варианта квартиры по трём критериям: k 1 – цена (тыс.$),k 2 – площадь (м 2),k 3 – расположение дома от метро (мин ходьбы до метро). Опреде­лим характер изменения критериев: предпочтение вариантов возрастает при уменьшенииk 1 ,k 3 и при увеличенииk 2 . Альтернативные варианты приведены в табл.2.1.

Таблица 2.1

Пример выбора варианта квартиры

Варианты квартир	k 1 , тыс.$	k 2 , м 2	k 3 , мин
В 1
В 2
В 3
В 4
В 5

На первом этапе выделим доминируемые варианты. Среди пяти исходных В 4 доминируетВ 3 , поэтому вариант 3исключа­ем. Оставшиеся варианты конкурируют между собой (оптималь­ны по Парето).

На втором этапе зададим коэффициент замещения второго критерия первым. В данном примере ЛПР должно ответить на вопрос: сколько тыс.$ оно готово заплатить за каждый дополни­тельный квадратный метр площади. Пусть

т.е. на столько по критерию k 1 он уступает при сравнении вариантов по критериюk 2 .

С учетом заданного коэффициента замещения Z 2,1 сравним вариантыВ 1 иВ 2 .

По критерию k 1 вариант 1предпочтительнее на б тыс.$, а по критериюk 2 , вариант 2предпочтительнее на .

Таким образом с учетом Z 2,1 = 1тыс.$по критериям k 1 иk 2 вариант 1 предпочтительнееВ 2 , так как. Поскольку по критериюk 3 вариант 1также предпочтительнееВ 2 , тоВ 1 доминируетВ 2 и значитВ 2 должен быть исключен.

З
десь и далее во всех блок-схемах интерактивных методов двойными контурными линиями выделены блоки, выполняе­мые с участием ЛПР. При сравненииВ 1 иВ 4 получим:

С учетом значенийk 3 вариант 1 доминируетВ 4 .

Сравнивая В 1 иВ 5 , определим

Значит, В 5 предпочтительнееВ 1 по критериямk 1 иk 2 , а с учётомk 3 получим,что эти два варианта конкурируют между собой.

После исключения доминируемых вариантовна основе коэффициента замещенияZ 2,1 остались два вариантаВ 1 иВ 5 .

Зададим коэффициент замещения третьего критерия первым. Пусть ЛПР готово уступить за каждую минуту (расстояние до метро) 100 $,т.е.

Сравнивая варианты В 1 иВ 5 , получим

Значит В 5 предпочтительнееВ 1 . Однако, надо иметь в виду, что вывод о предпочтительностиВ 5 неустойчив. Действи­тельно, если коэффициент замещенияZ 2,1 принять равным0,15тыс.$, получим, чтоВ 1 предпочтительнееВ 5 .

Поэтому для большей уверенности при выборе вариантов следует ввести дополнительныекритерии.

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

Порядок, в котором вводятся в алгоритм коэффициенты замещения, не влияет на итоговый результат выделения наиболее предпочтительного варианта, т.е., если бы в примере ввести сначала Z 3,1 , а потомZ 2,1 , всё равноВ 5 будет наилуч­шим.

В заключение отметим особенности метода уступок:

метод позволяет выделять наиболее предпочтительные варианты;

отсутствуют процедуры перехода к относительным единицам (они не требуются);

агрегирование критериев осуществляется через коэффици­енты замещения критериев;

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

Метод условной оптимизации.

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

Пример . Как и в предыдущем примере будем выбирать лучший подарок по двум критериям: q 1 - цена подарка, главный критерий; q 2 - время, затрачиваемое на его приобретение. Допустим, что цена первого, второго и третьего соответственно 300 руб., 350 руб. и 400 руб.; время, затрачиваемое на их приобретение, 2 часа, 1 час и 30 мин.

Рассмотрим случай ограничений типа равенств . Зададим ограничение по времени (так как это не главный для нас критерий): время, затрачиваемое на приобретение подарка q 2 = 1 час. 20 мин. Выберем теперь из всех подарков такие, у которых q 2 = 1 час. 20 мин. Видим, что таких подарков в нашем списке нет. Таким образом, далее мы осуществляем выбор на пустом множестве альтернатив. Это значит, что мы отвергли все предложенные альтернативы.

Естественно, что в реальных ситуациях принятия решений ограничения типа равенств встречаются не часто. Более адекватный случай – ограничения типа неравенств . Зададим в нашем примере ограничения типа неравенств. Будем считать, что нам надо купить подарок не ровно за 1 час. 20 мин. (как это было в ограничении типа равенств), а не более, чем за 1 час 20 мин., т.е. 0 мин. #q 2 #1 час 20 мин. Выбираем из всего множества подарков те, которые покупаются не более, чем за 1 час 20 мин. В это множество вошли второй и третий подарок. Теперь мы выбираем из них наилучший на основании только главного критерия – цены. Наилучшим будет второй подарок, т.к. у него меньшая цена (350 руб.)

Достоинства метода:

Не вводится никаких новых критериев;

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

Недостатки метода:

Ограничения типа равенств часто являются неадекватными реальным ситуациям принятия решений;

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

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

Поясним суть этого метода на рисунке. Пусть q 1 (x) - главный критерий. Зафиксируем значение второстепенного критерия q 2 (x) = C 2 1 . При данном фиксированном значении этого критерия (на рисунке это нижняя из горизонтальных прямых) найдем альтернативу с минимальным значением критерия q 1 (x). Это точка x 1 *1 . Предположим, что значение главного критерия q 1 (x 1 *1) нас не удовлетворяет.

Мы делаем уступку в значении второстепенного критерия q 2 (x), полагая его значение q 2 (x) = C 2 2 > C 2 1 . Далее при этом значении критерия q 2 (x) (на рисунке это средняя из горизонтальных прямых) найдем альтернативу с минимальным значением критерия q 1 (x). Это точка x 1 *2 . Предположим, что значение главного критерия q 1 (x 1 *1) нас не удовлетворяет.

Мы готовы сделать еще уступку в значении второстепенного критерия q 2 (x), полагая его значение q 2 (x) = C 2 3 > C 2 2 . Далее при этом значении критерия q 2 (x) (на рисунке это верхняя из горизонтальных прямых) найдем альтернативу с минимальным значением критерия q 1 (x). Это точка x 1 *3 . Значение главного критерия q 1 (x 1 *3) = Q нас теперь удовлетворяет. На этом процесс поиска решения прекращается. Найденная альтернатива x 1 *3 считается принятой.

Пример . Выбираем лучший подарок по двум критериям: q 1 - цена подарка, главный критерий; q 2 - время, затрачиваемое на его приобретение. Допустим, что цена первого, второго и третьего подарков соответственно 300 руб., 350 руб. и 400 руб.; время, затрачиваемое на их приобретение 2 часа, 1 час и 30 мин.

Зафиксируем значение второстепенного критерия q 2 (x) = 20 мин. При этом значении второго критерия выберем подарок с наименьшей ценой. Это множество пусто. Такое положение нас не удовлетворяет. Сделаем уступку по времени. Положим q 2 (x) = 30 мин. При этом значении второго критерия выберем подарок с наименьшей ценой. Это подарок третий. Посмотрим значение главного критерия – цену. Допустим, что его цена 400 руб. нас не устраивает. Вновь делаем уступку по времени. Положим q 2 (x) = 1 час. При этом значении второго критерия выберем подарок с наименьшей ценой. Это подарок второй. Посмотрим значение главного критерия – цену. Допустим, что его цена 350 руб. нас устраивает, т.е. мы считаем цену нашей уступки по времени (30 мин.) адекватной цене нашего выигрыша в главном критерии (50 руб.). Тогда процесс выбора окончен. Мы выбираем второй подарок.

Достоинства метода:

Идея метода уступок крайне проста;

Метод прост в реализации.

Недостатки метода:

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

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

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

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

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

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

В том случае, если на этапе 2 решалась задача на поиск максимума критерия , то дополнительное ограничение имеет следующий вид: . Уступка здесь в меньшую сторону, т.к. максимум функции уже найден.

В случае, если на этапе 2 решалась задача на поиск минимума критерия , то дополнительное ограничение имеет следующий вид: . Уступка здесь в большую сторону, т.к. найден минимум функции.

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

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

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

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

Пример. Решить задачу

методом последовательных уступок, если уступка по первому критерию составляет 10 % от его оптимального значения.

Решение

1. Поскольку в задаче указано, по какому критерию назначена уступка 10 %, то данный (первый) критерий считается самым важным.

Метод главного критерия

Методы последовательной оптимизации

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

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

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

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

Метод последовательных уступок. Согласно этому методу локальные критерии предварительно ранжируются по важности. Затем ищется наилучшее решение по наиболее важному критерию. На следующем шаге ищется решение наилучшее по следующему по важности критерию, причем допускается потеря в значении первого критерия не более чем на некоторую обусловленную величину, т.е. делается уступка по первому критерию. На третьем шаге оптимизируется решение по третьему критерию, при заданных уступках по первому и второму и т.д., пока не будет рассмотрен последний по важности критерий. При решении многокритериальных задач методом последовательных уступок вначале нужно определить важность частных критериев, т.е. расположить частные критерии в порядке убывания важности. Таким образом, главным считается критерий F 1 , менее важным F 2 , . . . , F m . Минимизируется первый по важности критерий и определяется его наименьшее значение F 1 min . Затем назначается величина допустимого снижения уступки D 1 ³0 критерия F 1 и ищется наименьшее значение критерия F 2 при условии, что значение F 1 должно быть не больше, чем F 1 min +D 1 . Снова назначается уступка D 2 ³0, но уже по второму критерию, которая вместе с первой используется при нахождении условного минимума F 3 и т.д. Наконец, минимизируется последний по важности критерий F m при условии, что значения каждого критерия F i из m-1 предыдущих должны быть не больше соответствующей величины F i min +D i .Получаемое в итоге решение считается оптимальным.

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

1) Найти F 1 min =min F 1 (X)

2) Найти F 2 min .=min F 2 (X) (1)

F 1 £ F 1 min +D 1

m) Найти F m min .=min F m (X)

F i £ F imin +D i

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

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

Пример. Пусть в области D={0;4} заданы два критерия F 1 (x)=(x-1) 2 +1 F 2 (x)=(x-2) 2 +2, которые нужно минимизировать (рис.1). Критерий F 1 важнее критерия F 2 (F 1 предпочтительнее F 2).

Рис.1. Графики функций F 1 и F 2

1. Согласно алгоритму минимизируем первый по важности критерий, и определяется его наименьшее значение F 1 min .Формулируем задачу оптимизации

найти min F 1 (x)= min[(x-1) 2 +1]

при ограничениях

Минимум для первого критерия достигается в точке x 1 opt =1 и равен F 1 (x 1 opt)=1

2. Затем назначается величина уступки D 1 =0.1 критерия F 1 и ищется наименьшее значение критерия F 2 при условии, что значение F 1 должно быть не больше, чем F 1 min +D 1 . Таким образом, мы получили следующую задачу оптимизации

minF 2 (x)=min[(x-2) 2 +2]

при ограничениях

(x-1) 2 +1£1+0.1

Для решения воспользуемся методом множителей Лагранжа. В результате получим безусловную задачу оптимизации

Ф(x, λ)= (x-2) 2 +2+ λ((x-1) 2 -0.1).

Находим частные производные и приравниваем их к нулю. В результате получим систему уравнений

Решая эту систему, получим x 2 opt =1.32.

Согласно алгоритму, решение, полученное на последнем этапе, и будет считаться оптимальным, т.е. x opt =1.32.

Решим данную задачу, используя систему MathCad.

f(x):=(x-2) 2 +2 целевая функция

x:=1 начальное приближение

ограничения

0≤x≤4

p:=Minimize(f,x) p=1.316.

Ответ: x opt =1.32.

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

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

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