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

ПЛАН

Введение

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

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

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

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

ВВЕДЕНИЕ

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

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

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

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

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

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

При решении многокритериальной задачи методом последовательныхуступок вначале производится качественный анализ относительной важностичастных критериев; на основании такого анализа критерии располагаются инумеруются в порядке убывания важности, так что главным является критерийK1, менее важен. K2, затем следуют остальные частныекритерии К3, К4 ..., KS. Максимизируетсяпервый по важности критерий K1 и определяется его наибольшеезначение Q1. Затем назначается величина «допустимого» снижения(уступки) D

1>0 критерия K1и ищется наибольшее значение Q2 второго критерия K2 приусловии, что значение первого критерия должно быть не меньше, чем Q1—D1.Снова назначается величина уступки D2>0,но уже по второму критерию, которая вместе с первой используется принахождении условного максимума третьего критерия, и т. д. Наконец, максимизируетсяпоследний по важности критерий Ks при условии, чтозначение каждого критерия Кr из S—1предыдущих должно быть не меньше соответствующей величины Qr—Dr;получаемые в итоге стратегии считаются оптимальными.

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

1) найти Q1=<img src="/cache/referats/8228/image002.gif" v:shapes="_x0000_i1025">

(1)

2) найти Q2=<img src="/cache/referats/8228/image004.gif" v:shapes="_x0000_i1026">

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

3) найти QS=<img src="/cache/referats/8228/image006.gif" v:shapes="_x0000_i1027">

Если критерий KS на множествестратегий, удовлетворяющих ограничениям задачи S), не достигает своего наибольшего значения Qs,то решением многокритериальной задачи считают максимизирующуюпоследовательность стратегий {uk} из указанного множества (lim KS(uk)= QS).

k->¥

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

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

Величины уступок D

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

Вначалерешается вопрос о назначении величины допустимого снижения D

rпервогокритерия от его наибольшего значения Q1. Практически для этогозадают несколько величин уступок D11, D21, D31… и путемрешения 2) в задаче (1) определяют соответствующие макс. значения Q2(D11), Q2(D21), Q2(D31), ивторого критерия. Иногда, если это не слишком сложно, отыскивается функция Q2(D1).Результаты расчетов для наглядности Представляем графически (Рис 1)

<div v:shape="_x0000_s1027"> Рис 1

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

1, азатем находят Q2(D1).

Далее рассматривают пару критериев K2и K3 вновь назначают «пробные» величины уступок Q2(D

22), ,… и, решая 3)в задаче(1), отыскивают наибольшие значения третьего критерия Q3(D12), Q3(D22),... Полученные данные анализируют, назначают D2,переходят к следующей паре критериев К3, K4 и т. д.

Наконец, в результатеанализа взаимного влияниякритериев KS-1 и KSвыбирают величину последней уступки D

S-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,в которой функция <img src="/cache/referats/8228/image012.gif" v:shapes="_x0000_i1030"> достигаетнаибольшего на Usзначения. Нетрудно убедиться в том, что u* эффективна.

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

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

найти <img src="/cache/referats/8228/image014.gif" v:shapes="_x0000_i1031"> (2)

Однако практически более удобно применять такой прием: заменить в S) критерий Ksна <img src="/cache/referats/8228/image016.gif" v:shapes="_x0000_i1032"> ,

где À

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

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

<img src="/cache/referats/8228/image018.gif" v:shapes="_x0000_i1033"> (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% от наибольшей величины критерия).

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

iполучить оптимальную стратегию за одинэтап, сведя последовательность задач (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 в единственной точке <img src="/cache/referats/8228/image024.gif" v:shapes="_x0000_i1036"><img src="/cache/referats/8228/image026.gif" v:shapes="_x0000_i1037"> , однако <img src="/cache/referats/8228/image028.gif" v:shapes="_x0000_i1038">

Пример 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, т. е. к задаче

найти <img src="/cache/referats/8228/image030.gif" v:shapes="_x0000_i1039"> (5)

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

Выделение критерия Ktв качестве основного и назначение пороговых величин br,для остальных частных критериев фактически означает, что все стратегииразбиваются на два класса. К одному относятся стратегии, которые удовлетворяютвсем S—1 ограничениям Kr(u)³

br;такие стратегии можно назвать допустимыми. К другому классу относятся такие стратегии, которые не удовлетворяютхотя бы одному из указаных S—1 неравенств. Наконец, среди допустимыхстратегий предпочтительнее считается та, для которой значение Критерия Kl больше.

Необходимо отметить, что установившееся название— «основной», или «главный» критерий — по существу весьма условно.Действительно, критерий Kl максимизируетсяна множестве лишь допустимых стратегий; иначе говоря, если для стратегии uзначение некоторого «второстепенного» частного критерия Krоказываетсяхоть немного меньше, чем br, то она уже не может «претендовать» на роль оптимальной, сколь быбольшим ни было для нее значение основного критерия. Сравнение (5) и (1) показывает, что методпоследовательных уступок формально можно рассматривать как особую разновидность метода выделения основного частного критерия,отличающуюся наличием специфическойпроцедуры назначения величин ограничений для задачи максимизации KS (этообстоятельство фактически ужеиспользовалось при доказательстве теоремы 1).

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

<img src="/cache/referats/8228/image032.gif" v:shapes="_x0000_i1040">À

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

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

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

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

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

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

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

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

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

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

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

еще рефераты

Еще работы по математике

Реферат по математике

Правильные и полуправильные многогранники

20 Июня 2015

Реферат по математике

Иррациональные уравнения

20 Июня 2015

Реферат по математике

Интегральное исчисление. Исторический очерк

20 Июня 2015

Реферат по математике

Методы и приемы решения задач

20 Июня 2015