Турунтаев Л.П. Теория принятия решений. Учебное пособие томск 2007 Томский межвузовский центр
![]()
|
5.2.5 Модальный критерий выбора альтернатив Сущность модального критерия выбора альтернатив состо- ит в том, что ЛПР при выборе альтернативы ориентируется на наиболее вероятное состояние среды. 96 Пусть максимум распределения вероятности приходится на состояние среды l e , т.е. max l j j p p = Тогда оптимальное реше- ние k x ∗ находится из условия ( , ) max k l il i F x e y ∗ = Если имеется несколько состояний среды, которым соответст- вуют одинаковые максимальные вероятности { } 1 2 , , ..., j j jr l l l , то альтернатива выбирается таким образом, чтобы обеспечить максимум среднего значения оценочного функционала по всему множеству наиболее вероятных состояний: 1 1 1 1 ( , ) max r r k jl ijl i l l F x e y r r ∗ = = = ∑ ∑ Достоинство модального критерия состоит в значительном сокращении объема расчетов. 5.3 Принятие решений в условиях неопределенности 5.3.1 Принятие решений при линейной упорядоченности состояний внешней среды ЛПР не знает закона распределения вероятностей состояний внешней среды, но располагает информацией, позволяющей упорядочить эти состояния по вероятности их появления. Последовательность принятия решения в рассматриваемой ситуации описывается следующим алгоритмом. Шаг 1. Установить отношение порядка 1 E на множестве Е состояний внешней среды. Шаг 2. Найти точечную оценку распределения вероятно- стей состояния внешней среды, т.е. некоторое конкретное рас- пределение 0 1 ( , ..., ) n p p p = , удовлетворяющее введенному на первом шаге отношению порядка 1 E . Шаг 3. Для найденной точечной оценки найти оптималь- ную альтернативу по одному из критериев (или их группе), ис- пользуемых для ПР в условиях риска. 97 Шаг 4 . Проверить, является ли найденное решение опти- мальным для всех других распределений 0 p p ≠ , но удовлетво- ряющих данной системе отношений порядка 1 E . Если «да», то решение принимается, иначе — перейти к следующему шагу. Шаг 5 . Наложить на распределение 0 p дополнительные ус- ловия (их характер рассмотрен ниже) и проверить их выполне- ние. Если эти условия выполнены, то решение принимается, иначе — ввести дополнительные отношения порядка в 1 E и вер- нуться к шагу 2. Рассмотрим алгоритм более подробно. На шаге 1 ЛПР устанавливает отношение порядка на мно- жестве Е. Простейший способ упорядочения — введение на множестве Е отношения предпочтения следующим образом: ; , ; , j k j k j k j e e p p e e E p ⇔ ≥ ∈ f где k p p ∈ — вектор распределения вероятностей внешней сре- ды; j p — вероятность появления состояния j e . Если такое упо- рядочение выполнено для всех пар ( , ) j k e e , то получаем линей- ное отношение частичного порядка и будем считать, что состоя- ния внешней среды перенумерованы таким образом, что 1 2 n p p p ≥ ≥ ≥ Шаг 2 . Вычисление точечных оценок распределений веро- ятностей, удовлетворяющих введенным отношениям порядка, может быть выполнено различными способами. Один из них предложен П. Фишберном. Оценки Фишберна j p образуют убывающую арифметическую прогрессию вида 2( 1) , 1, . ( 1) j n j p j n n n − + = = + Другие способы можно найти в работе [30]. 98 Шаг 3 . Находим оптимальную альтернативу, например, по критерию Байеса: 1 max ( , ) n i j ij i j B p x p y = = ∑ . Пусть это критерий k x x ∗ = при альтернативе . k 1 ( , ) max n k j ij i j B p x p y = = ∑ Шаг 4 . Необходимо проверить, будет ли k x оптимальным решением не только для найденного распределения j p , но и для любого другого распределения, удовлетворяющего введенному на шаге 1 отношению порядка 1 E . При использовании критерия Байеса , k i x x i ∀ f можно га- рантировать тогда и только тогда, когда ( ( , ) ( , ) 0 k i B p x B p x − ≥ или 1 ( ) 0 n j kj ij j p y y = − ≥ ∑ для всех i, , p P ∈ (5.1) где Р — множество распределений, удовлетворяющих заданно- му отношению порядка 1 E . Очевидно, что для выполнения (5.1) необходимо и доста- точно, чтобы 1 min ( ) 0, 1, n j kj ij p j p y y i m ∈Ρ = − ≥ = ∑ . (5.2) Поскольку выражение p P ∈ представляет собой в рассмат- риваемом случае не что иное, как систему линейных ограниче- ний, накладываемых на компоненты вектора Р,то выражение (5.2) определяет множество задач, состоящее из ( 1) m − задач линейного программирования (при i k = условие 5.2 выполня- ется). Шаг 5 . Этот шаг и последующие удобнее рассмотреть на примере. 99 Пример Пусть таблица значений оценочного функционала задана (табл. 5.2). Предположим, что на первом шаге алгоритма на множестве состояний среды 1 2 3 { , , } E e e e = введено отношение частичного порядка с помощью неравенств 1 2 3 , p p p ≥ ≥ 1 2 3 1. p p p + + = Таблица 5.2 — Исходные данные Вычислим по формуле Фишберна точечные оценки: 1 2 3 1 1 1 ; ; . 2 3 6 p p p = = = Для выбора оптимальной стратегии воспользуемся крите- рием Байеса. Математическое ожидание полезностей 1 2 3 4 1 1 1 1 1 ( , ) 8 2 4 5 ; ( , ) 6; ( , ) 5 ; 2 3 6 3 6 5 ( , ) 3 . 4 B p x B p x B p x B p x = ⋅ + ⋅ + ⋅ = = = = Наилучшей стратегией по Байесу является стратегия 2 x . Проверим, для любого ли распределения вероятностей, удовлетворяющего заданному отношению порядка, эта страте- гия оптимальна. 2 i x x f для всех альтернатив i,кроме второй, на любых до- пустимых распределениях вероятностей, если 1 21 1 2 22 2 23 3 min[ ( ) ( ) ( )] 0, {1,3,4}; i i i i L p y y p y y y y i = − + − + + − ≥ ∈ (5.3) Стратегии Состояния среды 1 e 2 e 3 e 1 x 8 2 4 2 x 6 7 4 3 x 4 7 5 4 x 3 4 6 100 1 2 3 1 2 3 ; 1. p p p p p p ≥ ≥ + + = Таким образом, мы имеем 3 задачи линейного программи- рования (табл.5.3). Таблица 5.3 — Задачи линейного программирования Условие задачи Решение 0 , , 1 0 0 min 0 5 2 3 2 1 3 2 1 3 2 2 1 3 2 1 1 ≥ = + + ≥ − ≥ − → ⋅ + + − = p p p p p p p p p p p p p L 0 1 2 3 2 1 min 1 = = = − = p p p L min 2 3 1 3 → − = p p L ограничения те же 3 1 3 1 3 2 1 min 3 = = = = p p p L min 2 3 3 3 2 1 4 → − + = p p p L ограничения те же 3 1 3 4 3 2 1 min 4 = = = = p p p L Как видно из табл. 5.3, условие 5.3 0 i L ≥ выполняется только для стратегий 3 x и 4 x , но не для 1 x . Следовательно, ре- шение 2 x , полученное на основе точечных оценок Фишберна, лучше, чем 3 x и 4 x , 2 3 2 4 ï ðè ( , ) x x x x p ∈Ρ f f , но 2 1 1 2 åñëè , 2 5 0 x x p p − + ≥ f — это дополнительное ограниче- ние. Оно не противоречит ранее введенной системе ограничений (есть общая область допустимых решений и при этом условии). Если ЛПР считает, что последнее ограничение выполняется (а это так), то 2 x оптимальна для любого распределения вероят- ностей, которое может иметь место. Если бы ограничение не выполнялось (т.е. не было общей области допустимых реше- 101 ний), то в рассмотрение вводится дополнительное отношение — 2 1 5 2 p p ≤ (но не 2 1 5 2 p p ≥ , а) и переходим на шаг 2. 5.3.2 Принятие решений при отсутствии информации о состоянии внешней среды ЛПР не располагает никакой информацией о вероятностях появления различных состояний внешней среды j e , в том числе и об их соотношении. Простейший способ решения задачи состоит в использовании точечных оценок неизвестного апри- орного распределения, причем критерии выбора в таких услови- ях принимают известный «принцип недостаточного основания», предложенный Даниилом Бернулли, и означают, что если нет данных, позволяющих считать одно состояние среды j e ∈Ε бо- лее вероятным, чем любое другое, то априорные вероятности всех этих состояний следует считать равными 1 j p n = Оптимальной по критерию Бернулли—Лапласса считается альтернатива, максимизирующая математическое ожидание по- лезности, т.е. 1 1 ( , ) max ( , ) max( ) n i ij i i j B p x B p x y n ∗ = = = ∑ Способ, использующий понятие Байесова множества Рассмотрим множество всевозможных распределений веро- ятностей состояний внешней среды. Так как 1 1 n j j p = = ∑ , то в каж- дом распределении достаточно задать лишь ( 1) n − вероятность, например, 1 1 , ..., n p p − Обозначим 1 1 ( , ..., ) n p p p − = . Очевидно, что каждому кон- кретному распределению вероятностей соответствует точка ( 1) n − -мерного пространства с координатами 1 1 , ..., n p p − , ле- жащая в замкнутой области, определяемой соотношениями: 102 1 1 0, 1, 1 , 1 n j j j p j n p − = ≥ = − ≤ ∑ Область, определяемая таким образом, называется ( 1) n − - мерным симплексом 1 n p − . Если n = 2, то одномерный симплекс 1 p — это отрезок [0,1], если m = 3, то двумерный симплекс 2 p — треугольник. Если в распоряжении ЛПР имеется m альтернатив, то этот симплекс можно разбить на m непересекающихся подмножеств, таких, что в любой точке этого подмножества оптимальной по критерию Байеса является одна и та же альтернатива. Такое подмножество (из p ), соответствующее стратегии i x , называется байесовым множеством этой стратегии. Будем обозначать его ( ) i p x или i p . Понятию байесова множества можно дать простую геомет- рическую интерпретацию. Если среда может находиться всего в двух состояниях n = 2 с вероятностями 1 p и 2 1 1 p p = − , то симплекс 1 1 1 ( 0, 1) p p p ≥ ≤ — есть отрезок. Математическое ожидание полезности при использовании альтернативы i x 1 1 1 2 1 1 2 2 ( , ) (1 ) ( ) i i i i i i B p x p y p y p y y y = ⋅ + − = − + Таким образом, каждой альтернативе i x соответствует пря- мая на плоскости с системой координат ( , ) p B . Приведем пример построения байесовых множеств ( ) i p x в одномерном симплексе при наличии трех альтернатив (рис. 5.2). Множеству ( ) i p x соответствует отрезок симплекса, на котором альтернатива i x обеспечивает максимум математического ожи- дания полезности. Можно доказать, что каждое байесово множество образует в ( 1) n − -мерном пространстве замкнутый выпуклый многогран- ник (в нашем случае при n = 2 — отрезок, а при n = 3 — много- гранник). 103 Объем этого многогранника будем рассматривать как меру байесова множества ( ) i p x и обозначим ее ( ) i p µ . Назовем инте- гральным потенциалом альтернативы i x величину 1 ( , ) ( ) , 1 ( ) / ( ) i i p i i m B p x dp x p p − π = − µ µ ∫ где числитель характеризует интегральное (средневзвешенное по всем априорным распределениям) байесово значение оце- ночного функционала; 1 ( ) m p − µ — мера (объем) симплекса, и, следовательно, зна- менатель определяет геометрическую вероятность непопадания вектора p в байесово множество альтернативы i x . Естественно предположить, что ЛПР стремится к увеличе- нию числителя при возможно меньшем знаменателе. Отсюда получаем критерий наибольшего интегрального потенциала: ( ) max ( ) i i x x ∗ π = π 1 0 1 p ) ( 2 x p ) ( 3 x p ) ( 1 x p ) , ( i x p B 2 x 3 x 1 x max полезности на множестве ) ( 1 x p Рис. 5.2 — Пример построения байесовых множеств ) ( i x p в одномерном симплексе при наличии трех альтернатив 104 Пример Задана матрица значений оценочного функционала (табл. 5.4). Найдем зависимость 1 ( , ) i B p x математического ожидания по- лезности от вероятности появления состояния 1 e и изобразим ее на рис. 5.3. Таблица 5.4 — Исходные данные Стра- тегия Е 1 e 2 e 1 x 2 11 2 x 6 7 3 x 11 3 Вычислим значения интегрального потенциала для всех стратегий: 1 47 1 1 1 1 0 1 1 1 1 ( , ) (11 9 ) ( ) 8; 1 ( ) / ( ) 1 ( ) p B p x dp p dp x p p p − π = = = − µ µ − µ ∫ ∫ 1 1 1 1 1 ( , ) 2 11(1 ) 11 9 B p x p p p = + − = − ; 1 2 1 1 3 1 ( , ) 7 ; ( , ) 3 8 B p x p B p x p = − = + 1 2 3 ( ) [0;0,47]; ( ) 0; ( ) [0,47;1] p x p x p x = = = Длины соответствующих отрезков: 53 , 0 47 , 0 1 ) ( ; 0 ) ( ; 47 , 0 ) ( 3 2 1 = − = µ = µ = µ p p p Мера симплекса: 1 1 : ( ) 1 p p µ = . 1 p 1 11 В 0,47 6 3 11 7 3 3 x 2 x 1 x 0 Рис. 5.3 — Иллюстрация оценки альтернатив 0,44 0,5 105 1 1 1 0,47 2 3 3 (3 8 ) ( ) 0. ( ) 7. 1 ( ) p dp x x p + π = π = = − µ ∫ Оптимальной альтернативой следует считать 1 x . 5.3.3 Принятие решений в условиях противодействия Имеется активная внешняя среда, которая стремится при- нять такие состояния, сводящие к минимуму эффективность процесса управления. ПР в таких условиях рассматривается в теории игр. Основными критериями ПР в этой ситуации явля- ются: 1) максиминный критерий |