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

Введение

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

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

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

ВВЕДЕНИЕ

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

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

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

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

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

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

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

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

1) найти Q 1 =

2) найти Q 2 =

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

3) найти Q S =

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

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

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

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

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

Рис 1

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

Далее рассматривают пару критериев K 2 и K 3 вновь назначают «пробные» величины уступок Q 2 (D 2 2), ... и, решая 3) в задаче (1), отыскивают наибольшие значения третьего критерия Q 3 (D 1 2), Q 3 (D 2 2),... Полученные данные анализируют, назначают D 2 , переходят к следующей паре критериев К 3 , K 4 и т. д.

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

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

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

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

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

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

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

Пример 2. Пусть U Ì R n - выпуклое множество,

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

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

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

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

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

где À - положительное число;

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

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

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

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

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

Теорема 1.

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

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

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

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

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

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

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

Лемма 1.

Пусть множество UÌR p замкнуто и ограничено, K 1 и К 2 непрерывны на U, D 1 ³0 и À£ D 1 /M 1 2 , где

Тогда для любой стратегии u*, доставляющей функции L=K 1 +ÀК 2 наибольшее на U значение, справедливо неравенство Q 1 -K 1 (u*)£ D 1 причем если K 1 (u*)£ Q 1 , то

Эта лемма, показывает, что если решить задачу максимизации на U функции L=K 1 +ÀК 2 , в которой число À назначено указанным образом, то для полученной стратегии u* (она обязательно эффективна) значение K 1 (u*) будет отличаться от максимального Q 1 не более, чем на D 1 , a K 2 (u*) будет тем ближе к Q 2 , чем точнее назначена оценка М 1 2 .

Однако даже если взять число М 1 2 , удовлетворяющее (4) как равенству, и положить À = D 1 /M 1 2 , то все равно нельзя гарантировать, что K 2 (u*)=Q 2 , так что рассматриваемый способ действительно является приближенным.

Пример 4. Пусть U - четверть единичного круга, лежащая в положительном квадранте: U={u: uÎR 2 , u 2 1 +u 2 2 £1, u 1 ³0, u 2 ³0} K 1 (u)=u 1 , K 2 (u)=u 2 . Здесь Q 1 = l и М 1 2 =1, если исходить из (4) как равенства. Примем D 1 =0,2; À=0,2.

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

Пример 5. U={u: uÎR 2 , 0£u 2 £1, (1+d)u 2 £1-u 1 } где d - положительное число, K 1 (u)=u 1 , K 2 (u)=u 2 . Используя (4) как равенство, находим: М 1 2 = 1. Положим D 1 =1; À=1. Функция u 1 +u 2 достигает на U максимума в единственной точке (1, 0). Возьмем теперь; À=1 + e. где e- любое сколь угодно малое положительное число. Тогда при d точке (-d, 1), так

что Q 1 -K 1 (-d, 1) = 1+d >D 1 =1.

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

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

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

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

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

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

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

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

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

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

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

В начале показатели ранжируются по важности. Но их упорядочение носит чисто качественный характер, т.е. никаких количественных оценок важностей не производится. Затем выбирается первый, самый важный, показатель и находится оптимальная по нему альтернатива. После этого назначается уступка, т.е. интервал, в котором могут варьироваться значения первого показателя. Другими словами, определяется насколько первый показатель может отличатся от своего оптимального значения.

Потом производится оптимизация по второму показателю. При этом оптимальное значение второго показателя ищется при допустимой уступке первого. Далее определяется уступка по второму показателю и т.д. В качестве оптимальной по векторному критерию принимается альтернатива вычисленная в конце многоэтапной оптимизации.

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

Оптимальность по Парето.

Прежде чем рассматривать данный метод, определим понятие доминирования

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

Данный метод, рассматривая все множество альтернатив, отбрасывает те из них, которые доминируются хотя бы одной альтернативой. Таким образом, создается множество недоминируемых альтернатив . Оно называется Парето оптимальным , и именно из него следует выбирать решение. Итак, поиск решений по принципу Парето-оптимальности дает множество допустимых решений, а не одно единственное..

Для выбора наилучшей альтернативы можно использовать один из рассмотренных выше методов скаляризации, или привлечь дополнительную неформальную информацию о ценности вариантов решений, составляющих Парето-оптимальное множество. Держателем такой информации обычно является лицо, принимающее решения (ЛПР). Именно ЛПР, рассматривая и анализируя недоминируемые альтернативы, выбирает ту из них, которая с его точки зрения является оптимальной (точнее рациональной). Если число элементов Парето-оптимального множества сравнительно невелико, то такой выбор ЛПР может и должен произвести. В противном случае вновь в полной мере возникают все трудности оптимизации и ранжирования по векторному критерию. Однако тот факт, что ЛПР подключен к решению задачи в качестве носителя неформальной информации, позволяет поставить вопрос о ее формализации с тем, чтобы, с одной стороны, помочь ЛПР разобраться в своих оценках и,с другой стороны, использовать ее в формализованной процедуре принятия решений. Это можно сделать на основе понятий полезности альтернатив или их относительной предпочтительности.

Полезность

Полезность является индивидуальной оценкой качества альтернатив определяемой ЛПР. Она отображает его систему ценностей на полном множестве альтернатив (можно на реализуемом). Полезность принято измерять в числовой шкале. Обычно в 0-1 или в 0-100. Это дает возможность количественно оценить во сколько или на сколько одно решение полезнее другого с точки зрения ЛПР. Таким образом, назначение полезностей альтернатив можно рассматривать как еще один способ скаляризации векторного критерия.

Содержание понятия полезности легко проиллюстрировать на следующем примере (см. рис.1). Пусть некоторому лицу (по нашей терминологии это ЛПР) предлагается купить билет для участия в лотерее с выигрышем в 100 у.е. Билеты четырех типов. По билету первого типа вероятность выигрыша равна 0,25, второго - 0,5, третьего - 0,75 и четвертого -1. Нетрудно убедиться, что математические ожидания выигрышей по каждому типу билетов соответственны равны: 25, 50, 75 и 100 у.е. Согласно общепринятой логике справедливая цена лотерейного билета равна математическому ожиданию выигрыша по нему (прямая 1). Поэтому названные суммы можно рассматривать как объективные полезности билетов. Однако индивидуальные особенности ЛПР могут вносить свои коррективы. Если оно склонно к риску, то вполне может заплатить за билет больше его объективной стоимости в надежде выиграть 100 у.е. Причем, если риск связан с небольшими затратами, то его можно увеличивать. Эта ситуация отражена на рис.1 кривой 2. Если же ЛПР склонно к осторожности и ему даже объективная цена билета кажется чрезмерной, то его оценка полезности участия в лотерее будет соответствовать кривой 3. Наконец, если ЛПР готов рисковать, когда затраты невелики, и проявляет осторожность, когда возрастают, его функция полезности выражается кривой 4.

Вопросы организации процедур назначения полезностей, их свойства и операции над ними рассматриваются в специальном разделе исследования операций «теории полезности».

Предпочтения

Предпочтения определяются в шкале отношений, Обычно используется бинарная шкала. ЛПР сопоставляет попарно совокупности значений показателей (альтернативы) и определяет какая из них предпочтительней или же они равноценны. Таким образом, на множестве альтернатив вводится отношение не строгого порядка, что отвечает их не строгому ранжированию. Многомерная скалярная функция, формализующая это ранжирование, называется функцией предпочтений (ФП) и на ее основе возможно проводить оптимизацию и ранжирование модельно реализуемых альтернатив. Процедуру вычисления ФП можно также рассматривать как способ скаляризации векторного критерия. Более подробно формализация предпочтений в форме ФП будет рассмотрена ниже при описании системы поддержки решений DSS/UTES.

Резюме

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

Во-вторых, общим свойством всех рассмотренных подходов, как, впрочем, и не рассмотренных, является их зависимость от субъективизма ЛПР. Это проявляется в том, что выбор метода и назначение его необходимых внутренних параметров осуществляется (или, по крайне мере, должно осуществляться) либо непосредственно ЛПР, либо с его участием. Это положение приобретает принципиальный характер, когда речь идет о принятии решений с помощью СППР (системы поддержки принятия решений). Метод скаляризации в СППР может быть «прописан», и если система для ЛПР не прозрачна, то нет никакой уверенности в том, что он отвечает подходу ЛПР. Поэтому ЛПР необходимо понимать основные достоинства и недостатки различных методов скаляризации векторного критерия. Кратко рассмотрим их.

Критерий среднего взвешенного. Достоинства

1. Простота формализации

2. Ясный физический смысл

3. Учет индивидуальных представлений ЛПР о задаче при назначении весовых коэффициентов (важностей)

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

Недостатки:

Не учет нелинейной зависимости весовых коэффициентов от значений показателей: важности вводятся один раз и остаются постоянными величинами.

Метод идеальной точки. Достоинства:

1. Компоненты векторного критерия рассматриваются в совокупности (без применения сверток)

2. Четкая формальная постановка

Недостатки:

1. Неявная взаимная компенсация показателей, которая становится неконтролируемой при большом их числе.

2. Произвольный выбор метрики

3. Непредставимость расстояния между двумя точками n-мерного пространства (при n>3).

Метод последовательных уступок. Достоинства:

2. Учет всех компонент векторного критерия

Недостатки:

1. Необходимость предварительного ранжирования показателей по важности

2 Трудность определения величин уступок

3. Практическая не реализуемость при большом числе показателей

Оптимальность по Парето. Достоинства:

1. Метод математически строг и понятен пользователю.

2. Выделяет множество допустимых решений.,

3. Дает возможность ЛПР сосредоточить анализ решений на более узком множестве и выбрать субъективно оптимальное решение.

Недостатки:

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

Свертка по полезности, свертка по предпочтениям. Хотя оба метода можно рассматривать как способ скаляризации векторного критерия, по существу это способы выявления неформальной информации, которой обладает ЛПР. Информации основанной на знаниях, опыте, интуиции и сложившейся на этой основе системе ценностей ЛПР. Внешне они просты для пользователя, однако это далеко не так. Выявление и формализация системы ценностей ЛПР, выражаемой в виде предпочтений или полезностей требует организации достаточно сложных процедур Одна из таких процедур будет показана ниже на примере СППР DSS/UTES.

Похожая информация.

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

1. Вначале устанавливается предпочтительность всех критериев, т.е на первое место ставится самый важный критерий.

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

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

4. Решается задача по следующему критерию с дополнительным ограничением.

В том случае, если на этапе 2 решалась задача на поиск максимума критерия , то дополнительное ограничение имеет следующий вид: . Уступка здесь в меньшую сторону, т.к. максимум функции уже найден.

В случае, если на этапе 2 решалась задача на поиск минимума критерия , то дополнительное ограничение имеет следующий вид: . Уступка здесь в большую сторону, т.к. найден минимум функции.

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

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

Метод хорош тем, что сразу видно, ценой какой уступки в одном показателе приобретается выигрыш в другом показателе и какова величина этого выигрыша.

Если лицо, принимающее решение, устраивают значения полученных критериев, то задача считается решенной. В противном случае изменяются величины уступок, и задача решается заново.

Пример. Решить задачу

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

Решение

1. Поскольку в задаче указано, по какому критерию назначена уступка 10 %, то данный (первый) критерий считается самым важным.

ВВЕДЕНИЕ

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

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

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

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

1) найти Q 1 =

(1)

2) найти Q 2 =

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

3) найти Q S =

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

Рис 1

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

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

Рис 2

Пример 2. Пусть U Ì R n - выпуклое множество,

найти (2)

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

где À - положительное число;

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

(3)

Теорема 1.

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

Лемма 1.

Пусть множество UÌR p замкнуто и ограничено, K 1 и К 2 непрерывны на U, D 1 ³0 и À£D 1 /M 1 2 , где

(4)

Однако даже если взять число М 1 2 , удовлетворяющее (4) как равенству, и положить À = D 1 /M 1 2 , то все равно нельзя гарантировать, что K 2 (u*)=Q 2 ,так что рассматриваемый способ действительно является приближенным.

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

Пример 5. U={u: uÎR 2 , 0£u 2 £1, (1+d)u 2 £1-u 1 } где d - положительное число, K 1 (u)=u 1 , K 2 (u)=u 2 . Используя (4) как равенство, находим: М 1 2 = 1. Положим D 1 =1; À=1. Функция u 1 +u 2 достигает на Uмаксимума в единственной точке (1, 0). Возьмем теперь; À=1 + e. где e- любое сколь угодно малое положительное число. Тогда при d

что Q 1 -K 1 (-d,1) = 1+d >D 1 =1.

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

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

Выделение критерия K t в качестве основного и назначение пороговых величин b r , для остальных частных критериев фактически означает, что все стратегии разбиваются на два класса. К одному относятся стратегии, которые удовлетворяют всем S-1 ограничениям K r (u)³b r ;такие стратегии можно назвать допустимыми. К другому классу относятся такие стратегии, которые не удовлетворяют хотя бы одному из указаных S-1 неравенств. Наконец, среди допустимых стратегий предпочтительнее считается та, для которой значение Критерия K l больше.

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

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

Метод (последовательных) уступок заключается в анализе точек на границе Парето и выбора одной из них - компромиссной.

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

Инструкция . Выберите количество переменных и количество строк (количество ограничений). Полученное решение сохраняется в файле Word и Excel .

При этом ограничения типа x i ≥ 0 не учитывайте. Если в задании для некоторых x i отсутствуют ограничения, то ЗЛП необходимо привести к КЗЛП, или воспользоваться этим сервисом .

Вместе с этим калькулятором также используют следующие:
Графический метод решения ЗЛП

Решение транспортной задачи

Решение матричной игры
С помощью сервиса в онлайн режиме можно определить цену матричной игры (нижнюю и верхнюю границы), проверить наличие седловой точки, найти решение смешанной стратегии методами: минимакс, симплекс-метод, графический (геометрический) метод, методом Брауна.

Экстремум функции двух переменных

Задачи динамического программирования
Распределить 5 однородных партий товара между тремя рынками так, чтобы получить максимальный доход от их продажи. Доход от продажи на каждом рынке G(X) зависит от количества реализованных партий товара Х и представлен в таблице.

Объем товара Х (в партиях)	Доход G(X)
Объем товара Х (в партиях)	1	2	3
0	0	0	0
1	28	30	32
2	41	42	45
3	50	55	48
4	62	64	60
5	76	76	72

Алгоритм метода последовательных уступок (компромиссов)

Вначале производится качественный анализ относительной важности критериев. На основании такого анализа критерии нумеруются в порядке убывания важности.
Ищем максимальное значение f 1 * первого критерия f=f 1 (x) на всем множестве допустимых решений. Затем назначаем величину «допустимого» снижения (уступки ) Δ 1 критерия f 1 (x) и определяем наибольшее значение f 2 * второго критерия f=f 2 (x) при условии, что значение первого критерия должно быть не меньше, чем f 1 (x)-Δ 1 . Затем назначаем величину «допустимого» снижения (уступки ) Δ 2 критерия f 2 (x) и определяем наибольшее значение f 3 * третьего критерия f=f 3 (x) при условии, что значение второго критерия должно быть не меньше, чем f 2 * - Δ 2 и т. д. Таким образом, оптимальным решением многокритериальной задачи считается всякое решение последней из задач последовательности:
1) найти max f 1 (x)=f 1 * в области x ∈ X;
2) найти max f 2 (x)=f 2 * в области, задаваемой условиями x ∈ X; f 1 (x) ≥ f 1 * -Δ 1 (6)
……………………………………………………………….
m) найти max f m (x)=f m * в области, задаваемой условиями
x ∈ X; f i (x) ≥ f i * -Δ i , i=1,...,m-1
Очевидно, что если все Δ i =0, то метод уступок находит только лексикографически оптимальные решения, которые доставляют первому по важности критерию наибольшее на Х значение. В другом крайнем случае, когда величины уступок очень велики, решения, получаемые по этому методу, доставляют последнему по важности критерию наибольшее на Х значение. Поэтому величины уступок можно рассматривать как своеобразную меру отклонения приоритета частных критериев от жесткого лексикографического.
Метод последовательных уступок не всегда приводит к получению только эффективных точек, но среди этих точек всегда существует хотя бы одна эффективная. Это следует из следующих утверждений.
Утверждение 3 . Если X ⊂ R n - множество замкнутое и ограниченное, а функции f i (x) непрерывны, то решением m-й задачи из (6) является, по крайней мере, одна эффективная точка.
Утверждение 4 . Если x * - единственная (с точностью до эквивалентности) точка, являющаяся решением m-й задачи из (6), то она эффективна.

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

Пример №1 . Решить методом последовательных уступок многокритериальную задачу.
f 1 (x)=7x 1 +2x 3 -x 4 +x 5 → max ,

при ограничениях
-x 1 +x 2 +x 3 =2 ;
3x 1 -x 2 +x 4 =3 ;
5x 1 +2x 2 +x 3 +x 4 +x 5 =11;
x i ≥ 0 для i=1,2,...,5.
Упорядочим критерии согласно их нумерации, то есть будем в начале работать с критерием f 1 (x), а затем с критерием f 2 (x).
При решении примера методом искусственного базиса была получена симплекс-таблица (табл.). Возьмем ее в качестве начальной, вычислив относительные оценки для функции f=f 1 (x). Получим таблицу 10. Таблица 11 определяет точку, доставляющую функции f1(x) наибольшее значение f 1 * , равное 16.
Таблица 10. Таблица 11.

		7	0
c в		X 1	x 2			x 4	x 2
2	x 3	-1	1	2	x 3	1/3	2/3	3
-1	x 4	3	-1	3	x 1	1/3	-1/3	1
1	x 5	3	2	6	x 5	-1	3	3
	f 1	-9	5	7	f 1	3	2	16

Далее переходим к решению задачи
f 2 (x)=x 1 -5x 2 -4x 3 +x 4 → max
при ограничениях задачи, к которым добавлено новое ограничение f 1 (x)≥f 1 * -Δ:
-x 1 +x 2 +x 3 =2,
3x 1 -x 2 +x 4 =3 , (7)
5x 1 +2x 2 +x 3 +x 4 +x 5 =11,
7x 1 +2x 3 - x 4 +x 5 ³16-Δ,
x i ≥ 0 для i=1,2,...,5.
Новое ограничение преобразуем в равенство и заменим переменные x 1 , x 3, x 5 , используя таблицу 11, выражениями
x 1 =1/3x 2 -1/3x 4 +1, x 3 =-2/3x 2 -1/3x 4 +3, x 5 =-3x 2 +x 4 +3.
В результате этих преобразований дополнительно введенное ограничение примет вид -2x 2 -x 4 +x 6 =-16+Δ. Итак, получили задачу параметрического программирования с параметром в правой части ограничений.
В качестве начальной таблицы для задачи (7) можно использовать таблицу 12, которая получена из таблицы 11 в результате пополнения ее еще одной строкой и пересчета строки относительных оценок. Решим задачу (7) для произвольного параметра Δ≥0. Для этого столбец правых частей ограничений в таблице 12 представим в виде двух столбцов z′, z″: z i 0 =z i ′+z i ″Δ. При выборе главной строки в таблице 12 следует использовать значения из столбца z′. Полученная далее таблица 13 является оптимальной при Δ=0 и при всех значениях Δ, удовлетворяющих условиям
3+(-1/9) Δ ≥ 0, 1+(-1/9) Δ ≥ 0, 3+1/3 Δ ≥ 0, 0+1/3 Δ ≥ 0.
Из этой системы неравенств получаем 0 ≤ Δ ≤ 9. При этих значениях параметра решением задачи является точка x*=(1+(-1/9)Δ, 0, 3+(-1/9)Δ, 0+1/3Δ, 3+1/3Δ).
Таблица 12. Таблица 13.

		1	-5
с в		x 4	x 2	z′	z″		x 6	x 2	z′	z″
-4	x 3	1/3	2/3	3	0	x 3	-1/9	4/9	3	-1/9
1	x 1	1/3	-1/3	1	0	x 1	-1/9	-5/9	1	-1/9
0	x 5	-1	3	3	0	x 5	1/3	11/3	3	1/3
0	x 6	3	2	0	1	x 4	1/3	2/3	0	1/3
	f 2	-2	2	-11	0	f 2	2/3	10/3	-11	2/3

При Δ > 9 таблица 13 не является оптимальной, и нужно выполнить шаг двойственного симплекс-метода с главным элементом, стоящим на пересечение второй строки и первого или второго столбцов. Получим таблицу 14, из которой видно, что при Δ > 9 решениями являются точки, доставляющие функции f 2 (x) значение –5. Таблица 14 определяет опорное решение x ** =(0,0,2,3,6).
Таблица 14.

	x 1	x 2	z′	z″
x 3	-1	1	2	0
x 6	-9	5	-9	1
x 5	3	2	6	0
x 4	3	-1	3	0
f 2	6	0	-5	0

Найдем эти решения. Выберем главным столбец с 0-оценкой. В зависимости от Δ главной строкой будет первая или вторая строка. Если
(-9+Δ)/5 > 2, то главной строкой будет выбрана 1-я. А значит, следующей будет таблица 15. Она определяет опорное решение X=(0,2,0,5,2) , если
–19+Δ≥0. Итак, если D≥19, оптимальными решениями будут все точки выпуклой комбинации
ax ** +(1-a)x * =(0, 2-2a, 2a,5-2a,2+4a), где a∈.
Таблица 15.

	x 1	x 3	z′	z″
x 2	-1	1	2	0
x 6	-4	-5	-19	1
x 5	5	-2	2	0
x 4	2	1	5	0
f 2	6	0	-5	0

Если (-9+Δ)/5 > 2, то главной строкой будет выбрана 2-я. А значит, следующей после таблицы 14 будет таблица 16. Таблица 16 определяет решение X=(0, (-9+Δ)/5, (19-Δ)/5, (6+Δ)/5, (48-2Δ)/5), если –19+Δ≤0. Итак, если Δ≤19, оптимальными решениями будут все точки выпуклой комбинации
ax**+(1-a)x*=(0, (1-a)(-9+Δ)/5, (19-Δ)/5+a(-9+Δ)/5, (6+Δ)/5+a(9-Δ)/5, (48-2Δ)/5+a(-18+2Δ)/5), где a∈.
Таблица 16.

	x 1	x 6	z′	z″
x 3	4/5	-1/5	19/5	-1/5
x 2	-9/5	1/5	-9/5	1/5
x 5	33/5	-2/5	48/5	-2/5
x 4	6/5	1/5	6/5	1/5
f 2	6	0	-5	0

Окончательный результат формулируется следующим образом: решением многокритериальной задачи являются:
точки x*=(1+(-1/9)Δ, 0, 3+(-1/9)Δ, 0+1/3Δ, 3+1/3Δ), если 0 ≤ Δ ≤ 9,
точки x**=(0, (1-a)(-9+Δ)/5, (19-Δ)/5+a(-9+Δ)/5,
(6+Δ)/5+a(9-Δ)/5,(48-2Δ)/5+a(-18+2Δ)/5), если 9 < Δ ≤ 19,
точки x *** =(0, 2-2a, 2a,5-2a,2+4a), если Δ ≥ 19,
где a∈.

Пример №2 . Методом последовательных уступок найти решение задачи, считая, что критерии упорядочены по важности в последовательности {f 2 ,f 1 }, и Δ 2 =1.
f 1 =-x 1 +3x 2 → max,
f 2 (x)=4x 1 -x 2 → max ,
Первая задача из последовательности (6) в данном случае имеет вид:
f 2 (x)=4x 1 -x 2 → max ,
при ограничениях
-x 1 +x 2 ≤1, x 1 +x 2 ≥3, x 1 -2x 2 ≤0 , x 1 ≤4 , x 2 ≤3.
Решение этой задачи можно найти графически. Из рисунка 14 видно, что максимум критерия f 2 (x) на множестве X достигается в вершине x 5 =(4,2) и f 2 * =f 2 (x 5)=14.
Графическое решение примера №2.

Рис.
Добавим к ограничениям задачи условие f 2 ≥f 2 * -Δ и сформулируем вторую задачу последовательности (6):
f 1 =-x 1 +3x 2 → max,
-x 1 +x 2 1 , x 1 +x 2 3, x 1 -2x 2 0 , x 1 4 , x 2 3,
4x 1 -x 2 13
Ее решением (рис.) будет вершина x 4 =(4,3) и f 1 * =f 1 (x 4)=5. Так как, оптимальное решение последней задачи единственно, то в силу утверждения 5, x 4 принадлежит множеству Парето.
Отметим, что при Δ∈ методом последовательных уступок будет найдена одна из точек отрезка , а при Δ>1, одна из точек отрезка . Все эти точки и только они принадлежит множеству Парето.