Реферат: Метод последовательных уступок (Теория принятия решений)
Введение 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 на