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

ПЛАН

Введение	3
Суть метода последовательных уступок	4
Порядок решения детерминированных многокритериальных задач методом последовательных уступок	5
Исследование метода последовательных уступок	9
Список использованной литературы.	19

ВВЕДЕНИЕ

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

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

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

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

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

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

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

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

1) найти Q_>1>=

2

(1)

) найти Q_>2>=

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

3) найти Q_>S>=

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

k->

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

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

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

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

Рис 1

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

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

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

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

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

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

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

Пример 1. Пусть множество UR³ — многогранник, изображенный на рис.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*. Утверждение доказано.

Рис 2

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

Пример 2. Пусть URⁿ — выпуклое множество,

а все К_>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ⁿ — множество замкнутое и ограниченное, а все К_>r> непрерывны, то решением S) задачи (1) служит по крайней мере одна эффективная стратегия.

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

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

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

найти (2)

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

где  — положительное число;

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

(3)

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

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

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

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

Теорема 1.

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

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

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

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

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

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

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

Лемма 1.

Пусть множество UR^p замкнуто и ограничено, K_>1>и К_>2> непрерывны на U, _>1>0 и  _>1>/M¹_>2>, где

(4)

Тогда для любой стратегии u*, доставляющей функции L=K_>1>+К_>2> наибольшее на U значение, справедливо неравенство Q_>1>-K_>1>(u*) _>1> причем если K_>1>(u*) Q_>1>, то

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

Однако даже если взять число М¹_>2>, удовлетворяю­щее (4) как равенству, и положить  = _>1>/M¹_>2>, то все равно нельзя гарантировать, что K_>2>(u*)=Q_>2>, так что рассматриваемый способ действительно является приближенным.

Пример 4. Пусть U — четверть единичного круга, ле­жащая в положительном квадранте: U={u: uR_>2>, u²_>1>+u²_>2>1, u_>1>0, u_>2>0} K_>1>(u)=u_>1>, K_>2>(u)=u_>2>. Здесь Q_>1> = l и М¹_>2>=1, если исходить из (4) как равенства. Примем _>1>=0,2; =0,2.

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

Пример 5. U={u: uR_{>2 ,} >0u_>2>1, (1+)u_>2>1-u_>1>} где  — положительное число, K_>1>(u)=u_>1>, K_>2>(u)=u_>2 >. Исполь­зуя (4) как равенство, находим: М¹_>2> = 1. Положим _>1>=1; =1. Функция u_>1>+u_>2> достигает на U максимума в един­ственной точке (1, 0). Возьмем теперь ; =1 + . где — любое сколь угодно малое положительное число. Тогда при < функция u_>1>+(1+)u_>2> будет достигать максимума на U в точ­ке (-, 1), так

что Q_>1>-K_>1>(-, 1) = 1+ >_>1>=1.

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

найти (5)

причем оптимальной считается обычно всякая стратегия, яв­ляющаяся решением задачи (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⁰ формаль­но эквивалентен назначению надлежащих величин b_>r>, причем в качестве основного можно выбрать любой частный крите­рий.

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

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

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

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

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

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

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

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

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