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

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

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

Это легко подтвердить простым примером. Пример 1. Пусть множество UR3 многогранник, изображенный на рис.2 , K1uu1, K2uu2, K3uu3. Здесь решением 3 из задачи 1 является любая точка треугольника ABC на рисунке он заштрихован, но эффективны лишь точки отрезка АС. Справедливо, однако, утверждение если u единственная с точностью до эквивалентности стратегия, являющаяся решением S из задачи 1, то она эффективна.

Действительно, предположим, что стратегия u неэффективна, так что существует стратегия u u. Но стратегия u также удовлетворяет всем ограничениям S задачи 1 и доставляет критерию KS значение Qs иначе говоря, u оказывается решением этой задачи, что противоречит условию единственности u. Утверждение доказано. Можно доказать так же, что если URn замкнуто и ограничено, Кr непрерывны на U, а стратегия, являющаяся решением S задачи 1, единственна с точностью до эквивалентности, то любая максимизирующая последовательность, служащая решением S, эффективна.

Пример 2. Пусть URn выпуклое множество, а все Кr квазивогнуты. При этих условиях множество стратегий, удовлетворяющих ограничениям r задачи 1, также выпукло r1,2, S, так что каждая из задач 1, 2 S является задачей квазивогнутого программирования. Если Ks строго квазивогнут, то решением задачи S может служить лишь единственная и потому эффективная стратегия если же при этом U замкнуто и ограничено, а все Кr непрерывны на U, то любая максимизирующая последовательность, являющаяся решением S, эффективна.

Пример 3. Предположим, что из многогранника U задачи, описанной в примере 1, удалена вся грань АВС, но оставлена точка В. Теперь эта точка оказывается единственным решением 3 задачи 1. Здесь точка В, конечно, эффективна. Любая сходящаяся к ней последовательность внутренних точек многогранника, удовлетворяющих ограничениям задачи 3, будет максимизирую щей для Ks, но не будет эффективной. Указанное положение следствие не замкнутости рассматриваемого в данном примере множества U. В связи с тем, что не всегда стратегия, полученная с помощью метода последовательных уступок, является эффективной, возникает и такой вопрос обязательно ли среди множества стратегий, выделяемых этим методом, существует хотя бы одна эффективная В общем случае на этот вопрос положительный ответ дать нельзя, однако имеет место такое утверждение если URn множество замкнутое и ограниченное, а все Кr непрерывны, то решением S задачи 1 служит по крайней мере одна эффективная стратегия.

Действительно, при выполнении условий этого утверждения множество Us стратегий-решений S оказывается непустым, замкнутым и ограниченным.

Следовательно, существует точка uUS , в которой функция достигает наибольшего на Us значения. Нетрудно убедиться в том, что u эффективна. Таким образом, при решении почти всякой прикладной многокритериальной задачи метод последовательных уступок выделяет в качестве оптимальных и эффективные стратегии.

Однако необходимо отметить, что выделенные эффективные стратегии не обязаны быть эквивалентными см. пример 1 но нетрудно проверить, что это возможно лишь при S3. Если нельзя гарантировать, что при решении рассматриваемой многокритериальной задачи метод последовательных уступок приводит к получению лишь эффективных стратегий в частности, если по выполняется вышеприведенное условие единственности, то для выделения эффективной стратегии среди решений задачи S достаточно, как показывает только что проведенное доказательство, найти 2 Однако практически более удобно применять такой прием заменить в S критерий Ks на, где положительное число в результате получится задача 3 Нетрудно доказать, что любая стратегия, являющаяся решением задачи 3, эффективна более того, всякая максимизирующая последовательность, служащая решением этой задачи, также эффективна.

Смысл указанного приема заключается в том, что при достаточно малом числе 0 для любой полученной в результате решения задачи 3 стратегии w значение критерия KSw будет весьма близким к Qs и эта стратегия эффективна, в то время как при решении S задачи 1 может быть получена стратегия и, которую выгодно заменить некоторой эффективной стратегией v u, существенно лучшей, чем и, но одному или даже нескольким частным критериям.

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

С другой стороны, метод последовательных уступок позволяет указать характеристическое свойство эффективных стратегий. Теорема 1. Для любой эффективной стратегии u существуют такие числа r, что эту стратегию можно выделить методом последовательных уступок, т. е.при rr, r1, 2 S 1, стратегия u является единственным с точностью до эквивалентности решением S задачи 1. Теорема 1 характеризует эффективные стратегии с помощью последовательности задач 1. В частности, она показывает, что метод последовательных уступок можно использовать для построения множества эффективных стратегий.

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

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

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

Поэтому большой интерес представляет вопрос можно ли при заданных i получить оптимальную стратегию за один этап, сведя последовательность задач 1 к одной экстремальной задаче Мы можем указать лишь приближенный способ одноэтапного решения для S2. Он основан на следующем утверждении Лемма 1. Пусть множество URp замкнуто и ограничено, K1и К2 непрерывны на U, 10 и 1M12, где 4 Тогда для любой стратегии u, доставляющей функции LK1К2 наибольшее на U значение, справедливо неравенство Q1-K1u 1 причем если K1u Q1, то Эта лемма, показывает, что если решить задачу максимизации на U функции LK1К2, в которой число назначено указанным образом, то для полученной стратегии u она обязательно эффективна значение K1u будет отличаться от максимального Q1 не более, чем на 1, a K2u будет тем ближе к Q2, чем точнее назначена оценка М12. Однако даже если взять число М12, удовлетворяющее 4 как равенству, и положить 1M12, то все равно нельзя гарантировать, что K2uQ2, так что рассматриваемый способ действительно является приближенным.

Пример 4. Пусть U четверть единичного круга, лежащая в положительном квадранте Uu uR2, u21u221, u10, u20 K1uu1, K2uu2. Здесь Q1 l и М121, если исходить из 4 как равенства.

Примем 10,2 0,2. Функция u1 0,2u2 достигает максимума на U в единственной точке так что, однако Пример 5. Uu uR2 , 0u21, 1u21-u1 где положительное число, K1uu1, K2uu2 . Используя 4 как равенство, находим М12 1. Положим 11 1. Функция u1u2 достигает на U максимума в единственной точке 1, 0. Возьмем теперь 1 . где любое сколь угодно малое положительное число. Тогда при функция u11u2 будет достигать максимума на U в точке 1, так что Q1-K1 1 1 11. Примечание.

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

Этот метод состоит в том, что исходная многокритериальная задача сводится к задаче оптимизации по одному частному критерию КL, который объявляется основным, или главным, при условии, что значения остальных частных критериев Кr должны быть не меньше некоторых установленных величин требуемых значений br, т. е. к задаче найти 5 причем оптимальной считается обычно всякая стратегия, являющаяся решением задачи 5. Выделение критерия Kt в качестве основного и назначение пороговых величин br, для остальных частных критериев фактически означает, что все стратегии разбиваются на два класса.

К одному относятся стратегии, которые удовлетворяют всем S 1 ограничениям Krubr такие стратегии можно назвать допустимыми. К другому классу относятся такие стратегии, которые не удовлетворяют хотя бы одному из указаных S 1 неравенств.

Наконец, среди допустимых стратегий предпочтительнее считается та, для которой значение Критерия Kl больше. Необходимо отметить, что установившееся название основной, или главный критерий по существу весьма условно. Действительно, критерий Kl максимизируется на множестве лишь допустимых стратегий иначе говоря, если для стратегии u значение некоторого второстепенного частного критерия Kr оказывается хоть немного меньше, чем br, то она уже не может претендовать на роль оптимальной, сколь бы большим ни было для нее значение основного критерия.

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

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

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

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

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

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