Тема 6. Методы выбора и принятия решений

Стр 1 из 5Следующая ⇒

Тема 6. Методы выбора и принятия решений

1. Классификация задач выбора.

2. Критериальный язык описания выбора.

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

3. Описание выбора на языке бинарных отношений.

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

4. Выбор в условиях статистической неопределенности.

Общая схема принятия статистических решений.Понятие о байесовом подходе.

5. Выбор в условиях неопределенности.

Платежная матрица. Максиминный критерий. Критерии Сэвиджа, Гурвица.

6. Выбор на нечетком множестве альтернатив.

Нечеткие множества целей, ограничений, решений.

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

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

Во-вторых, были обсуждены способы построения моделей - анализ и синтез.

В-третьих, методом проб и ошибок осуществляется " достроение", модификация, коррекция моделей путем включения в нее новой информации, полученной при очередном эксперименте с системой.

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

Таким образом, было подготовлено все необходимое для выбора:

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

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

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

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

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

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

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

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

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

Классификация задач выбора

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

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

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

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

Задачи выбора чрезвычайно многообразны, различны и методы их решения. Прежде всего, введем понятия, общие для всех задач выбора.

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

Обратим внимание на то, что при таком описании выбора считают сами собой разумеющимися, уже пройденными, два чрезвычайно важных этапа:

1) порождение множества альтернатив, на котором предстоит осуществлять выбор;

2) определение целей, ради достижения которых производится выбор.

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

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

Таким образом, выбор можно определить как целевое сужение множества альтернатив.

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

множество альтернатив может быть конечным, счетным или континуальным;

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

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

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

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

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

Условная максимизация

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

(7)

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

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

(8)

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

Варианты оптимизации при разноважных критериях

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

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

Пусть частные критерии могут быть пронумерованы в порядке убывания их важности. Возьмем первый из них и найдем наилучшую по этому критерию альтернативу (на рис. 1, б это x₂*, если самым важным критерием является q₂, и x₄*, если им является q₁). Затем определим “уступку” Δ q_i, т.е. величину, на которую мы согласны уменьшить достигнутое значение самого важного критерия, чтобы в пределах этой уступки попытаться увеличить, насколько возможно, значение следующего по важности критерия (на рис. 1, б полученные таким образом альтернативы изображены точками x₃* и x₅*). Далее (если число критериев более двух) определяется уступка по только что максимизированному критерию и максимизируется следующий; процедура повторяется до тех пор, пока перечень критериев не закончится.

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

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

Выбор между упорядочениями

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

Обозначим через R_i упорядочение критериев, предложенное i-м экспертом. Введем некоторую меру расхождения между двумя (i-й и j-й) ранжировками: d(R_i, R_j). Медианой Кемени R* среди n предложенных упорядочений R₁, R₂, ..., R_n называется то из них, которое отвечает условию

т.е. то, сумма “расстояний” до которого от всех остальных минимальна. Ясно, что многое зависит от того, как определить расстояние d. Например, если R_i = q₁⁽ⁱ⁾, ..., q_p⁽ⁱ⁾, то d_p(R_i, R_j) можно определить как d(h_i, R_j₁) = = p – , где? (x⁽ⁱ⁾, x^{( j)}) – символ Кронекера.

Однако следует отметить, что с медианой Кемени связано несколько трудностей. Во-первых, оптимизационная задача по нахождению R* решается методами дискретной оптимизации (динамического программирования, ветвей и границ, и др.), трудоемкость которых экспоненциально растет с увеличением размерности задачи. Во-вторых, иногда решение задачи не единственно, и в этом случае возникают трудности: в литературе приводится пример, когда в одной из оптимальных ранжировок конкретная альтернатива стоит на первом месте, а в другой – на последнем). Поэтому используют и другие способы упорядочения, наиболее известным из которых является метод строчных сумм. Пусть критерии сравниваются попарно: a_ij= 1, если k-й эксперт считает, что q_i важнее q_j; 0, если наоборот; 1/2, если он считает их равноценными. Для каждого критерия вычисляют величины , i = I, n, и критерии упорядочивают по этой “сумме очков” – совсем как по турнирной таблице в спорте. Однако и этот метод может давать сбои, как и всякое голосование (см. § 7.5).

Функция полезности

Важно обсудить ситуацию, возникшую при описании выбора на языке бинарных отношений в результате создания теории полезности [38]. П. Фишберн строго доказал теорему, смысл которой довольно ясен: если множество X конечно и между его элементами имеется отношение строгого порядка, то можно построить такую вещественную функцию u(x) на X, для которой

(x < y) Þ [u(x) < u(y)]

(в левой части < означает отношение предпочтения, в правой – знак “меньше”).

Функция u(x) называется функцией полезности. Ясно, что такая функция не единственна: произвольное монотонное преобразование сохраняет ее упорядочивающее свойство. Этот результат затем был обобщен на счетные и континуальные множества X, на нестрогий порядок и на многокритериальный случай (аддитивные функции полезности). Определение функции u(x) позволяет перейти от языка бинарных отношений к критериальному языку, взяв u(x) в качестве критериальной функции. Были развиты методы, позволяющие сузить класс функций полезности, например, благодаря рассмотрению иерархических парных предпочтений (см. § 6.2), повышая тем самым “точность определения u(x)”.

Создается впечатление, что от качественных порядковых измерений можно перейти к количественным. На самом деле мы здесь вновь сталкиваемся с такой ситуацией, когда “оцифровка” порядковой шкалы не делает ее числовой шкалой. Для воспроизводства упорядочения фиксированного попарно упорядоченного множества X, конечно, можно воспользоваться числовой функцией u(x); однако стоит дополнить X альтернативами, которые не рассматривались при первом упорядочении, как функцию u(x) потребуется определять заново. Более того, если два разных эксперта дадут разные упорядочения множества X, то можно доопределить функции полезности для каждого из них, но сравнивать их численно иначе как в отношении порядка не имеет смысла (см. пример в § 6.2), хотя обе они определены на одном множестве.

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

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

Язык функций выбора

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

Язык функций выбора описывает выбор как операцию над произвольным множеством альтернатив X, которая ставит этому множеству в соответствие некоторое его подмножество C(X): C(X) Í X. (Обозначение связано с первой буквой английского слова choiсe – “выбор”.) Функция выбора как отображение совокупности множеств в совокупность множеств (поскольку для выбора могут предлагаться любые подмножества X_i Í X) без поэлементного отображения одного множества на другое и без отображения множеств на числовую ось является своеобразным и пока еще не полно изученным математическим объектом. Конечно, накладывая на функцию выбора определенные требования, мы можем на этом языке описывать и те варианты выбора, которые отражаются в предыдущих языках. Однако главное достоинство нового языка – возможность рассмотрения более сложных правил выбора. На такую возможность указывает хотя бы различие числа возможных функций выбора и числа возможных графов предпочтения на множестве n альтернатив. Число графов, отличающихся наличием или отсутствием хотя бы одной дуги, равно . Если для выбора предлагаются k из n альтернатив, то число функций выбора равно 2^k (каждая из альтернатив может либо входить в C(X_k), либо нет). Так как число возможных вариантов предъявления альтернатив равно , то общее число функций выбора равно

Как видим, разнообразие функций выбора намного превосходит разнообразие графов предпочтения. Кроме того, здесь сразу допускается отказ от выбора, т.е. пустой выбор C(X_i) = , что также расширяет множество правил выбора.

Итог. Язык функций выбора является весьма общим и потенциально может описать любой выбор. Однако его теория находится в начальной стадии развития и пока еще занимается преимущественно описанием старых ситуаций в новых терминах. Язык функций выбора (“глобальных функций множеств”) описывает результат выбора как некоторое подмножество множества альтернатив. Такое соответствие двух множеств без их поэлементного соответствия является новым понятием, расширяющим смысл термина “функция”. Оно позволяет описывать произвольные ситуации выбора, чего нельзя было сделать с помощью предыдущих двух языков.

Понятие о байесовом подходе

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

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

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

- распределение P(q), q Î Q;

- условное распределение выборочных значений F(x|q), x Î X, q Î Q;

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

Такой уровень априорной информации соответствует байесову направлению статистики (Т. Байес – известный английский статистик). Среднее значение потерь l, связанное с конкретным алгоритмом γ обработки наблюдений x, называемое байесовым риском R, принимается за меру качества этого алгоритма. Оптимальная в этом смысле процедура γ * (также называемая байесовой) и считается наилучшим решением задачи:

Наибольшее количество споров относительно байесовых задач вызывала необходимость задавать априорное распределение P(q). Постулат Лапласа – Байеса, предлагающий при неизвестности P(q) считать его равномерным в Q, приводит к противоречиям в случае деформаций пространства Q [39, § 17]. Не помогает и предположение о том, что неизвестное P(q) принадлежит некоторому классу распределений, с тем чтобы взять в этом классе “наихудшее” распределение и для него найти байесову процедуру. Такая минимаксная процедура гарантирует, что “хуже не будет”, если только P(q) действительно входит в заданный класс.

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

Следующим уровнем стал отказ от необходимости знать P(q); на этом уровне в синтезе алгоритмов участвует только информация о семействе функций F(x|q). Оказалось, что если подставить в функцию плотности f(x|q) выборочные значения x₁, ..., x_N, и рассматривать ее зависимость от q, то такая зависимость

L (q |x₁, ..., x_N) = f(x₁, ..., x_N |q)

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

В том случае, когда по выборке x₁, ..., x_N следует принять решение в пользу одной из конкурирующих гипотез H₀ и H₁, т.е. решить – это выборка из распределения с плотностью f (x|H₀) или f (x|H₁), лучшей процедурой является вычисление отношения правдоподобия f(x₁, ..., x_N|H₁) / f(x₁, ..., x_N|H₀) и выбор гипотезы H₁, если это отношение превышает заданный порог, и гипотезы H₀, если ниже его. В рамках этого уровня возможны и другие методы принятия статистических решений; обычно их использование вызвано соображениями простоты реализации, но по качеству получаемых с их помощью решений они не превосходят процедур, основанных на функции правдоподобия.