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

Введение 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)

/>

/> <td/> Рис 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, где

 />(4)

Тогда для любой стратегии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—любое скольугодно малое положительное число. Тогда при d<e функция 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 на