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

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

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

- Считается, что заданно множество альтернатив, и выбор на нем осуществляется путем пошагового диалога с ЛПР и построение последовательности слабых бинарных отношений с целью сужения первичного множества альтернатив

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

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

Метод сворачивания критериев приводит первичную задачу к однокритериальной задаче такого вида:

.

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

где Q_i(x) – i-й компонент векторного критерия, - весовой коэффициент, который отображает относительную важность i-ого критерия.

Линейное сворачивание нормированных критериев основывается на идее построения частичных критериев до безразмерных величин с интервалом возможных значений каждого из них [0,1]. Для того чтобы выполнить такое превращение, ЛПР должен указать для каждого из критериев границы его изменения от минимального до максимального значения, и коэффициенты относительной важности нормированных критериев:

.

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

Аддитивные сворачивания имеют еще один изъян - значение глобального критерия может обеспечиваться очень большим значением одного из составляющих критериев за счет минимальных значений других.

Для того чтобы избежать такие ситуации, подобно аддитивному сворачиванию были предложены варианты мультипликативного сворачивания в обычном и нормированном виде:

Максиминное сворачивание. Глобальный критерий определяется как:

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

В проектировании используется разновидность критерия максиминного сворачивания, если существуют и заданны нормативные значения параметров Q*, которых желательно придерживаться:

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

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

Задача имеет вид:

.

В случае если выбрана метрика Эвклида то критерий будет иметь вид:

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

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

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

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

Метод последовательных уступок. Является одним из обоснованейших содержательно и при условии отсутствия противоречий в преимуществах ЛПР может дать хороший результат. Первым делом критерии упорядочиваются ЛПР по мере их уменьшения важности. После этого на каждом шаге решается задача оптимизации по критерию Qi и назначается погрешность на которую мы готовы уменьшить полученное оптимальное значение , чтобы улучшить значение других критериев, менее важных. Значения этих критериев рассчитываются по известным координатам оптимума х*. Получаем что на шаге решается задача:

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

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

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

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

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

Методы, которые используют бинарные отношения. «Сильным» бинарным отношениям соответствуют большие требования к преимуществу одной альтернативы над другой. Сильнейшим требованием является требование полного доминирования – множество альтернатив, оптимальных по Слейтеру.

В этих методах происходит по парное сравнение альтернатив и те альтернативы которые имеют преимущество становятся несравнимыми и формируют «ядро». После сравнения всех альтернатив для полученного ядра ставится новое условие и все альтернативы из этого ядра вновь по парно сравниваются.

Методы ELECTRE(1 2 3). В этих методах, в этих методах бинарное отношение преимущества, сильнее чем отношение Парето, строится следующим образом: Для каждого из n критериев определяется вес – число. Которое характеризует важность соответствующего критерия, которое тем больше чем этот критерий важнее для ЛПР. Веса могут быть определенны или ранжированием или методом Саати к примеру.

Для определения преимуществ между альтернативами выполняются следующие действия.

Множнство Q разбивается на 3 подмножества:

-Q⁺(x,y) – критерии по которым х лучше у;

- Q⁼(x,y) – критерии по которым х и у получили одинаковые значения;

- Q^-(x,y) – критерии по которым у лучше х.

Далее определяется относительная важность каждого из этих подмножеств.

Устанавливается порог и считается, что вариант х лучше у лишь в том случае, когда для определенной функции (индекс согласия) выполняется условие

Вид функции f зависит от модификации метода ELECTRE. В методах ELECTRE еще используются и индексы несогласия которые можно записать в следующем виде:

- пороговое значение индекса несогласия .

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

В ELECTRE 1 –

где pi – вес i-го критерия. Индекс несогласия рассчитывается на множестве критериев Q^-(x,y) . В последующих расчетах индексы согласия и несогласия нормируются.

В ELECTRE 2 гипотеза о преимуществе х над у принимается когда значения индексов

является достаточно большим, а

достаточно маленьким.

В ELECTRE 3 используется нечеткие отношения преимуществ.

Методы принятия решений в условиях неопределенности. Задача принятия решений в условиях неопределенности. В случае полной неопределенности – «совершенной неизвестности» - принятие любого решения является достаточным (включая вариант «ничего не делать»).

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

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

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

рис.10.4

Выбрав произвольную точку – альтернативу А. С помощью прямых параллельных осям координат разбиваем плоскость на 4 квадрата (конуса) и обозначим их I, II, III, IV.

Все точки конуса I лучше чем А, поэтому I называется конусом преимуществ. Все точки конуса III хуже – антиконус. II и IV – области неопределенности.

В случае m вариантов стратегий ЛПР и n вариантов стратегий «природы» задача принятия решений в условиях неопределенности будет иметь вид

.

Рассмотрим произвольную альтернативу D. Если ЛПР не отдает преимущества ни одной из двух стратегий природы П1 или П2, то он выходит из позиции нейтралитета, и можно считать, что природа будет использовать эти стратегии с равной вероятностью, в следствии чего критерий выбора будет иметь вид , то есть будет функцией двух переменных . Для линии уровня, которая проходит через точку D(х1,у1), , то есть в этом случае получаем у=-х+(х1+у1) и линия уровня будет прямой. Если перенести начало координат в точку D(х1,у1), то получаем зависимость у’=-х’, то есть биссектрису II и IV квадратов.

рис 10.5

Критерии принятия решений в условиях неопределенности. Классические критерии принятия решений в условиях неопределенности.

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

и выбирается стратегия с индексом k для которой

Это является позиция крайнего пессимизма и в отношении к природе является перестраховывающейся. Выбранная таким образом стратегия полностью исключает риск.

Использование критерия Вальда является обоснованным, если ситуация, в котрой принимается решение, характеризуется следующими обстоятельствами:

- о реализации природой своих стратегий ничего не известно;

- приходится учитывать разные стратегии природы;

- принимается уникальное решение, которое может быть реализовано лишь один раз;

- необходимо исключить любые риски.

Критерий Байеса-Лапласа. Простейший неопределенностью является «доброкачественная» стохастическая неопределенность. В этом случае состояние природы характеризуется вероятностью возникновения состояния (р) и оптимальной стратегией Аk будет та для которой критерий Байеса достигает максимума

то есть выбирается стратегия Аk с индексом k, для которой

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

то есть выбирается стратегия Аk с индексом k, для которой

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

- вероятности использования стратегий природой известны и не зависят от времени;

- принятие решений реализуется (теоретически) бесконечно много раз;

- для небольшого числа реализаций решения допускает некоторый риск.

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

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

С этой целью вводится понятия риска, как разницей между выигрышем, который можно было бы получить, если бы были известны условия природы – ее стратегию, и выигрышем, который получаем, не зная их и выбирая стратегию Аi,

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

Для среднего риска в случае стохастической неопределенности:

и выбирается стратегия Аk, для которой

Критерий Севиджа. Этот критерий также очень писимистичный, как и критерий максимина, но при выборе оптимальной стратегии ориентирует на минимальный гарантированный риск:

и выбирается стратегия Аk, для которой

.

Производные (комбинированные) критерии.

Критерий пессимизма - оптимизма Гурвица. Этот критерий рекомендует при выборе решения не ориентироваться ни на пессимизм, ни на оптимизм, а на их определенную комбинацию путем ввода коэффициента пессимизма , и если =1 то получаем критерий максимина, а когда =0 – крайний оптимизм (азартный игрок).

В этом случае проблема не решается – ее решение переносится в другую плоскость – определение «правильного» значения коэффициента оптимизма.

Критерий Ходжа - Лемана. Критерий Ходжа-Лемана строится с использованием максиминного критерия одновременно с критерием Байеса. С помощью параметра v отображается степень доверия к распределению вероятностей, которая используется. Если степень доверия большая, то акцентируется критерий Байеса, в другом случае преобладает составляющая, которая отвечает максиминному критерию.

При значении v=1 получаем критерий Байеса, а при v=0 – критерий максимина.

Этот критерий чаще применяется при следующих условиях:

- вероятности использования природой своих стратегий неизвестны, но некоторые гипотезы про распределение вероятности возможны;

- принятие решения теоретически допускает бесконечное количество реализаций;

- при малых числа реализации допускается определенный риск.

Метод дерева решений. Метод дерева решений заключается в графическом построении различных вариантов действий, которые могут быть использованы для решения первичной проблемы. Дерево решений- это граф, вершины его являются ключевыми состояниями, в которых возникает необходимость выбора, а дуги – разные события, которые могут возникать в ситуации, оговариваемой вершины. Каждой дуге дерева могут быть присвоены числовые характеристики. Главным преимуществом метода дерева решений является его наглядность. Чтобы построить дерево решений, необходимо в первую очередь получить первичную информацию, последовательность сбора которой включает следующие шаги:

- определение состава и продолжительности фаз циклов жизни проблемы, которую необходимо решить;

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

- определение времени наступления ключевых событий;

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

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

- определение вероятности принятия каждого составляющего решения.

На основании полученных данных строится дерево решений.

Дерево решений состоит из трех полей, которые могут повторятся в зависимости от сложности проблемы:

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

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

Основными компонентами дерева решений является:

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

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

- точки возможностей – изображаются в виде колец и характеризуют ожидаемые результаты возможных событий;

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

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

Процесс принятия решений с помощью дерева решений в общем случае предусматривает выполнение следующих пяти этапов.

- Формулирование задачи.

- Построение дерева решений согласно алгоритма, приведенного раньше.

- Оценивание вероятностей состояния окружения. (обычно на основании статистики или экспертным путем)

- Установление выигрышей.

- Решение задачи.

Тот факт, что анализ дерева решений происходит от листвы до корня, означает, что первыми рассматриваются те события, которые произошли последними. А то, которое произошло первым, проанализировано последним.

В зависимости от отношения к рискам решение задачи может выполнятся с позиций объективистов или субъективистов.

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

Безусловным денежным эквивалентом (БДЭ) называется максимальная сумма денег, которую ЛПР готов заплатить за участие в игре, или минимальная сумма денег за которую ЛПР готов отказаться от игры.

Объективист – это индивид, у которого ожидаемый денежный выигрыш совпадает с безусловным денежным эквивалентом, то есть со средним выигрышем в игре. У субъективиста ОДВ и БДЭ не равны.

Дата добавления: 2015-09-29