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

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

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

СУТЬ МЕТОДАПОСЛЕДОВАТЕЛЬНЫХУСТУПОК
Процедура решениямногокритериальной задачи методомпоследовательных уступок заключается в том, что всечастные критерии располагают и нумеруют впорядке их относительной важности; максимизируютпервый, наиболее важный критерий; затем назначают величину допустимогоснижения значения этого критерия и максимизируют второй по важности частный критерий при условии, что значение первогокритерия не должно отличаться от максимального более чем на величину установленного снижения (уступки); снова назначаютвеличину уступки, но уже по второму критерию и находят максимум третьегопо важности критерия при условии, чтобызначения первых двух критериев не отличались от ранее найденныхмаксимальных значений больше чем на величины соответствующихуступок; далее подобным же образомпоочередно используются все остальные частные критерии; оптимальной обычносчитают любую стратегию, которая получена при решении задачи отысканияусловного максимума последнего по важностикритерия.
Таким образом, при использовании методапоследовательных уступок многокритериальная задача сводится к поочередноймаксимизации частных критериев и выборувеличин уступок. Величины уступок характеризуют отклонение приоритета одних частных критериев перед другимиот лексикографического: чем уступки меньше, тем приоритет жестче.

ПОРЯДОК РЕШЕНИЯ ДЕТЕРМИНИРОВАННЫХМНОГОКРИТЕРИАЛЬНЫХ  ЗАДАЧ МЕТОДОМПОСЛЕДОВАТЕЛЬНЫХ УСТУПОК
При решении многокритериальной задачи мето­дом последовательныхуступок вначале производит­ся качественный анализ относительной важностичастных критериев; на основании такого анализа критерии располагаются инумеруются в порядке убывания важности, так что главным является критерийK1, менее важен. K2, затем следуют остальные частныекритерии К3, К4 ..., KS. Максимизируетсяпервый по важности критерий K1 и определяется его наибольшеезначение Q1. Затем назначается величина «допустимого» снижения(уступки) D1>0 критерия K1и ищется наибольшее значение Q2 второго критерия K2 приусловии, что значение первого критерия должно быть не меньше, чем Q1—D1.Снова назначается величина уступки D2>0,но уже по второму критерию, которая вместе с пер­вой используется принахождении условного макси­мума третьего критерия, и т. д. Наконец, максими­зируетсяпоследний по важности критерий Ks при условии, чтозначение каждого критерия Кr из S—1предыдущих должно быть не меньше соответствую­щей величины Qr—Dr;получаемые в итоге страте­гии считаются оптимальными.
Такимобразом, оптимальной считается всякая стратегия, являющаяся решением последнейзадачи из следующей последовательности задач:
1) найти Q1= 

(1) 2) найти Q2= 
………………………………..
3) найти QS= 
Если критерий KS на множествестратегий, удов­летворяющих ограничениям задачи S), не достигает своего наибольшего значения Qs,то решением мно­гокритериальной задачи считают максимизирую­щуюпоследовательность стратегий {uk} из указан­ного множества (lim KS(uk)= QS).
k->¥
Практически подобные максимизирующие после­довательностиимеет смысл рассматривать и для то­го случая, когда верхняя грань в задаче S)дости­гается, так как для решения экстремальных задач широко применяютсяитеративные методы.
Величиныуступок, назначенные для много­критериальной задачи, можно рассматривать каксвоеобразную меру отклонения приоритета (степени относительной важности)частных критериев от жесткого, лексикографического.
Величины уступок Drпоследовательноназнача­ются в результате изучения взаимосвязи частных критериев.
Вначалерешается вопрос о назначении величи­ны допустимого снижения Drпервогокритерия от его наибольшего значения Q1. Практически для это­гозадают несколько величин уступок D11, D21, D31… и путемрешения 2) в задаче (1) определяют соответствующие макс. значения Q2(D11), Q2(D21), Q2(D31), ивторого критерия. Иногда, если это не слишком сложно, отыскивается функция Q2(D1).Результаты расчетов для наглядности Представляем графически (Рис 1)

Рис 1

Он показывает, что вначале даже небольшиевеличины уступок позволяют получить существенный выигрыш по вто­рому критерию;с дальнейшим увеличением уступки выигрыш растет все медленнее. На основеанализа полученных данных и решают вопрос о назначении величины уступки D1, азатем находят Q2(D1).
Далее рассматривают пару критериев K2и K3 вновь назначают «пробные» величины уступок Q2(D22), ,… и, решая  3)в задаче(1), отыскивают наибольшие значения третьего критерия Q3(D12), Q3(D22),...  Полученные данные анализируют, назначают D2,переходят к следующей паре критери­ев К3, K4 и т. д.
Наконец, в результатеанализа взаимного влия­ниякритериев KS-1 и  KSвыбирают величину по­следней уступки DS-1и отыскивают оптимальные стратегии, решая  S) в задаче1(обычно ограничива­ются нахождением одной такой стратегии).
Таким образом, хотяформально при использо­вании методапоследовательных уступок достаточно решитьлишь S задач (1),однако для назначе­ния величин уступок с целью выяснения взаимосвя­зи частных критериев фактически приходится ре­шать существенно большее число подобных задач.

ИССЛЕДОВАНИЕМЕТОДА ПОСЛЕДОВАТЕЛЬНЫХ УСТУПОК
Во введении при изученииотношения предпоч­тения ³,порождаемого векторным критерием, бы­ло выяснено, что в качестве оптимальныхвообще могут выступать лишь эффективные стратегии. По­этому возникаютестественные вопросы: всегда ли использование метода последовательных уступокприводит к получению эффективных стратегий, а если не всегда — то в какихслучаях (при выпол­нении каких условий) можно гарантировать полу­чение лишь эффективныхстратегий?
Оказывается, что метод последовательных усту­покне всегда приводит к выделению лишь эффек­тивных стратегий, т. е. решениями S)из задачи (1) могут быть и неэффективные стратегии. Это легко подтвердитьпростым примером.
Пример1. Пусть множество UÌR3 —многогранник,изображенный на рис.2, K1(u)=u1, K2(u)=u2, K3(u)=u3.Здесь решением 3 из задачи (1) является любая точка треугольника ABC (на рисунке он заштрихован), ноэффек­тивны лишь точки отрезка АС.
Справедливо, однако, утверждение: если u* — единственная (с точностью доэквивалентности) стратегия, являющаяся решением S) из задачи (1), тоона эффективна.
Действительно, предположим, что стратегия u* неэффективна, так что существуетстратегия u'>u*. Ностратегия u'также удовлетворяет всем огра­ничениям S) задачи (1) и доставляет кри­терию KSзначение Qs; иначе говоря, u' оказыва­ется решением этой зада­чи,что противоречит ус­ловию единственности u*. Утверждение доказано.

Рис 2
Можно доказать так­  же, что если UÌRnза­мкнуто и ограничено, Кrнепрерывны на U, а стратегия, являющаяся реше­нием  S) задачи (1), единственна с точностью доэквивалентности, то любая максимизирующая последовательность, служащая решениемS), эффективна.
Пример2. Пусть UÌRn—выпуклое множество,
а все К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ÌRn— множествозамкнутое и ограниченное, а все Кrнепрерывны, то решением  S) задачи (1)служит по крайней мере одна эффективная стратегия.
Действительно, при выполнении условий этогоутверждения множество Usстратегий-решений S) оказываетсянепустым, замкнутым и огра­ниченным. Следовательно, существует точка u*ÎUS,в которой   функция    достигаетнаибольшего на Usзначения.    Нетрудно   убедиться в том, что u* эффективна.
Таким образом, при решении почти всякой при­кладноймногокритериальной задачи метод последо­вательных уступок выделяет в качествеоптималь­ных и эффективные стратегии. Однако необходимо отметить, чтовыделенные эффективные стратегии не обязаны быть эквивалентными (см. пример 1);но нетрудно проверить, что это возможно лишь при S³3.
Если нельзя гарантировать, что при решениирассматриваемой многокритериальной задачи метод последовательных уступокприводит к получению лишь эффективных стратегий (в частности, если повыполняется вышеприведенное условие единст­венности), то для выделенияэффективной страте­гии среди решений задачи S) достаточно, как пока­зываеттолько что проведенное доказательство,
найти         (2)
Однако   практически  более   удобно   применять такой прием: заменить в  S) критерий Ksна  ,
где À— положительное число;
в результате получится задача:
   (3)
Нетрудно доказать, что любая стратегия,являющаяся решением задачи (3), эффективна; более того, всякая максимизирующаяпоследовательность, служащая    решениемэтой задачи, также эффективна.
Смысл указанного приема заключается в том, чтопри достаточно малом числе À>0 для любой полученной    в результате решения задачи  (3) стратегии wзначение критерия KS(w)будет весьма близким к Qs*) иэта стратегия эффективна, в то время как при решении  S) задачи (1) может быть получена стратегия и, которую выгодно заме­нитьнекоторой эффективной стратегией v>u, су­щественно лучшей, чем и, но одному или даже не­скольким частным критериям. А посколькувеличи­ны уступок А, на практике устанавливаются при­ближенно, то замена Ksна K*sпри малых À>0в силу указанной причины оказывается допустимой и оправданной.
Таким образом, понятие эффективной стратегиипозволило уточнить вычислительную процедуру отыскания оптимальных стратегийметодом после­довательных уступок.
Сдругой стороны, метод последовательных уступок позволяет указатьхарактеристическое свойство эффективных стратегий.


Теорема 1.
Для любой эффективнойстратегии u* существуют такие числа D*r, что эту стратегию можно выделить методомпоследовательных уступок, т. е.
при Dr=D*r, r=1,2,...,S—1, стратегия u* являет­ся единственным (с точностью до эквивалентности)решением  S) задачи (1).
Теорема 1 характеризует эффективные стра­тегии спомощью последовательности задач (1). В частности, она показывает, что методпоследова­тельных уступок можно использовать для построе­ния множестваэффективных стратегий.
Более того, теорема 1 позволяет исследовать и самметод последовательных уступок. Действи­тельно, она показывает, что при любомфиксирован­ном расположении частных критериев, по степени относительнойважности одним лишь выбором ве­личин уступок можно обеспечить выделение любойэффективной стратегии в качестве оптимальной (так что проблема отысканияоптимальной страте­гии, т. е. проблема выбора эффективной стратегии из всегомножества U°, формально эквивалентнапроблеме назначения надлежащих величин уступок при произвольном фиксированномупорядочении критериев).
Следовательно, для решения многокритериаль­нойзадачи нужно так ранжировать критерии, чтобы потом удобнее было выбиратьвеличины уступок. Учитывая вышеизложенное и внимательно рассмо­трев порядокназначения величин уступок, можно сделать следующий вывод: методпоследовательных уступок целесообразно применять для решения техмногокритериальных задач, в которых все частные критерии естествен­ным образомупорядочены по степени важности, причем каждый критерий настолько существенноболее важен, чем последующий, что можно ограни­читься учетом только попарнойсвязи критериев и выбирать величину допустимого снижения очеред­ного критерия сучетом поведения лишь одного сле­дующего критерия.
Особенноудобным является случай, когда уже в результате предварительного анализамногокритериальной задачи выясняется, что можно допустить уступки лишь впределах «инженерной» точности (6—10% от наибольшей величины критерия).
Решение многокритериальной задачи методомпоследовательных уступок — процедура довольно трудоемкая, даже если заранеевыбраны величины всех уступок. Поэтому большой интерес представляет вопрос:можно ли при заданных Diполучить оптимальную стратегию за одинэтап, сведя после­довательность задач (1) к одной экстремальной задаче?
Мы можем указать лишь приближенный способодноэтапного решения для S=2. Он основан на следующем утверждении:
Лемма 1.
Пусть множество UÌRpзамкнуто и ограничено, K1и К2 непрерывны на U, D1³0иÀ£D1/M12, где
 
Тогда для любой стратегии u*,доставляющей функции L=K1+ÀК2 наибольшее на U значение, справедливонеравенство Q1-K1(u*)£D1причем если K1(u*)£Q1, то

Эта  лемма,   показывает, что еслирешить задачу максимизации на U функцииL=K1+ÀК2,   в кото­рой число Àназначено указанным образом, то для полученной стратегии u* (она обязательно эффек­тивна)  значение K1(u*)  будет отличаться   от максимального Q1 не более, чемна D1,a K2(u*) будет тем ближе к Q2, чем точнееназначена оценка М12.
Однако даже если взять число М12,удовлетворяю­щее (4) как равенству, и положить À= D1/M12,то все равно нельзя гарантировать, что K2(u*)=Q2,так что рассматриваемый способ действительно является приближенным.
Пример 4. ПустьU — четверть единичного круга, ле­жащая в положительном квадранте: U={u: uÎR2,u21+u22£1,u1³0, u2³0}K1(u)=u1, K2(u)=u2. Здесь Q1 = lи М12=1, если исходить из (4) как равенства. Примем D1=0,2;À=0,2.
Функция u1 + 0,2u2достигает максимума на U в единственной точке  , однако
Пример 5. U={u: uÎR2, 0£u2£1,(1+d)u2£1-u1}где d— положительное число, K1(u)=u1,K2(u)=u2 . Исполь­зуя (4) какравенство, находим: М12 = 1. Положим D1=1;À=1.Функция u1+u2достигает на U максимума ведин­ственной точке (1, 0). Возьмем теперь; À=1+ e.где e— любое сколь угодно малое положительноечисло. Тогда при deфункция u1+(1+e)u2будет достигать максимума на U в точ­ке (-d,1), так
чтоQ1-K1(-d, 1) = 1+d>D1=1.
Примечание.Для решения многокритериальных задач иногда применяют метод выделения основногочастного кри­терия. Этот метод состоит в том, что исходная многокритери­альнаязадача сводится к задаче оптимизации по одному частному критерию КL,который объявляется основным, или главным, при условии, что значенияостальных частных кри­териев Кr должныбыть не меньше некоторых установленных величин («требуемых» значений) br, т. е. к задаче
найти          (5)
причемоптимальной считается обычно всякая стратегия, яв­ляющаяся решением задачи (5).
Выделение критерия Ktв качестве основного и назна­чение пороговых величин br,для остальных частных критериев фактически означает, что все стратегииразбиваются на два класса. К одному относятся стратегии, которые удовлетворяютвсем S—1 ограничениям Kr(u)³br;такие стратегии можно назвать  допустимыми.   К   другому  классу   относятся   такие стратегии, которые не удовлетворяютхотя бы одному из указаных S—1  неравенств. Наконец, среди допустимыхстратегий   предпочтительнее   считается  та,   для   которой  значение Критерия Kl больше.
Необходимо отметить, что установившееся название— «ос­новной», или «главный» критерий — по существу весьма условно.Действительно, критерий Kl  максимизируетсяна множестве  лишь   допустимых  стратегий;   иначе   говоря, если   для стратегии uзначение некоторого  «второстепенного» частного критерия Krоказываетсяхоть немного меньше, чем br, то она уже  не может «претендовать»   на роль оптимальной,  сколь быбольшим ни было для нее значение основного критерия. Сравнение  (5) и   (1) показывает, что методпосле­довательных   уступок  формально  можно   рассматривать  как особую разновидность метода  выделения основного частного критерия,отличающуюся  наличием специфическойпроцедуры назначения   величин   ограничений  для   задачи   максимизации KS (этообстоятельство фактически  ужеиспользовалось при доказательстве теоремы 1).
Поэтому все полученные выше результаты, связанныес вопросами выделения эффективных стратегий методом последовательных уступок,переносятся и на рассматриваемый метод. В частности, этот метод выделяет лишьэффективные стратегии, когда решение задачи (5) единственно с точностью доэквивалентности; если же справедливость указанного условия единственности не установлена,то целесообразно в (5) заменить Klна

À>0 – достаточно малое число.
Выбор конкретной эффективной стратегии измножества U0формаль­ноэквивалентен назначению надлежащих величин br, причем в качестве основного можно выбратьлюбой частный крите­рий.
Это означает, с одной стороны, чторассматриваемый метод универсален в том смысле, что он позволяет для каждой ммногокритериальной задачи выделить в качестве наилучшейлюбую эффективную стратегию.
Это же означает, с другой стороны, что вопросы овыборе одного из частных критериев в качестве основного и назначении минимальнодопустимых величин brдля остальных критериев нужно решатьсовместно, ибо какой бы частный критерий ни был выбран основным, только лишьназначением величин ограничений на остальные критерии можно обеспе­читьполучение в качестве оптимальной любой (намеченной) эффективной стратегии.
Таким образом, предварительное выделение одногоиз ча­стных критериев основным еще никак не уменьшает свободы выбора эффективнойстратегии (так что название «основной», или «главный» критерий действительновесьма условно). Сле­довательно, при качественном анализе конкретной многокри­териальнойзадачи вопрос о выделении одного из частных критериев в качестве основногоследует решить так, чтобы облегчить назначение величин ограничений на остальныечастные критерии.
Практически назначается серия «наборов» {br}пороговыхзначений и для каждого «набора» отыскивается соответствую­щее наибольшеезначение основного критерия (при этом сле­дует учитывать данные вышерекомендации, относящиеся к обеспечению (получения лишь эффективных стратегий,а так­же иметь в виду, что при произвольно назначенных числах brможет случиться, что задача (5)вообще не имеет смыс­ла, так как ни одна стратегия не удовлетворяет входящим внее ограничениям).
Далее на основании анализа полученной сериизначений всех частных критериев (т. е.  серии значений векторного кри­терия)производится окончательное назначение величин огра­ничений, чем определяется ивыбор стратегии, которая и бу­дет считаться оптимальной.
Рассмотрение указанной процедуры назначениявеличин ограничений показывает, что расчет серии значений всех частныхкритериев фактически имеет целью получение представления о множествеэффективных стратегий (или некоторо­го его подмножества) с помощью рядаотдельных точек, а за­тем эта информация служит для окончательного выбора стра­тегии(производимого на основании интуиции, «здравого смыс­ла» и т. п.).
Следовательно, метод выделения основного частногокритерия стоит применять лишь в том случае, когда имеются соображения опримерных значениях величин br, (или о до­вольно узких пределахэтих значений), позволяющие огра­ничиться рассмотрением сравнительно небольшойчасти всего множества эффективных стратегий.

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