Москвин Б.В. Теория принятия решений

Подождите немного. Документ загружается.

271

Такая задача выбора является задачей стохастического матема-

тического программирования, и ее можно представить в виде.

f(x,ω) → max,

(x,ω) ≤ 0, i = 1,...,n.

Далее будем иметь в виду обозначение g

(x,ω) = f(x,ω).

Функции g

(x,ω), i = 0,...,n представляют собой случайные

функции, и при каждом фиксированном x являются случайными

величинами с заданным законом распределения. Сущность ме-

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

занными случайными функциями к моделям, зависящим лишь от

числовых характеристик, соответствующих законов распределе-

ния (например, математического ожидания, дисперсии и т.д.), ко-

торые

являются уже детерминированными величинами.

Как правило, вводятся следующие числовые характеристи-

ки законов распределения случайной функции g

(x,ω), i=0,...,n.

1). Математическое ожидание (М - преобразование)

(x) = М (g(x, ω)). (13.2)

2). Дисперсия (V - преобразование)

(x) = М( g(x, ω) - М g(x,ω))

. (13.3)

3). Вероятность превышения значений случайной функции

некоторого заданного порогового значения b (Р - преобразование)

(x) = Р{ g(x, ω) ≥ b }. (13.4)

4). Максимальное значение b, которое превышается значе-

ниями случайной функции с заданной вероятностью q (В - преоб-

разование)

(x) = max {b ⏐ Р{g(x, ω) ≥ b} ≥ q }. (13.5)

Ограничения задачи стохастического программирования

подвергаются, как правило, однотипным преобразованиям. По-

этому в целом такие задачи характеризуются парой символов

<G,C>, где первый символ характеризует вид преобразования

целевой функции, а второй характеризует вид преобразований

ограничений. Например, различают <М,М> задачи, в которых це-

левая функция и ограничения подвергаются

М-преобразованию;

<М,Р> задачи, в которых ограничения подвержены Р-

преобразованию и т.д. Наиболее широко в задачах стохастиче-

272

ского программирования используются преобразования типа М,

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

Довольно часто при поиске наилучших альтернатив функ-

ции g

(x, ω), i=0,...,n представляются в виде полиномов. Тогда эти

функции можно задать как g

(x,h

(ω)), i=0,...,n, где h

(ω) - вектор

коэффициентов полинома, т.е.

(x, h(ω)) =

∑

(ω) x

В результате проведения детерминизации задач стохасти-

ческого программирования их окончательное решение может

быть получено уже с использованием известных методов мате-

матического программирования (см. раздел 2).

13.2.2. Методы имитационной оптимизации.

В методах имитационной оптимизации (прямых методах

стохастического выбора) не производится преобразование зада-

чи к ее детерминированному эквиваленту. Суть данных методов

заключается в том, что генерируются случайные значения ω в

соответствии с известным законом распределения, далее для

заданного ω вычисляются функции g

(x, ω), i = 0,...,n, и решает-

ся оптимизационная задача вида x = arg max f(x, ω), где x ∈ {x⏐

(x,ω) ≤ 0}, i=1,...,n при фиксированном ω. Особенностью реали-

зации данных методов является то, что, во-первых, при произ-

вольном выборе ω допустимое множество альтернатив может

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

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

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

Преодоление указанных трудностей достигается на

основе

применения методов и м и т а ц и о н н о г о у с р е д н е н и я

и методов с т о х а с т и ч е с к о й а п п р о к c и м а

ц и и.

При имитационном усреднении произвольно (случайно) вы-

бирается некоторое подмножество точек из допустимой области

при некотором значении параметров среды. Далее на каждом ша-

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

ного программирования и производится усреднение значений

функций, ограничивающих выбор, и значений градиентов, вычис-

ленных на множестве избранных точек.

273

Метод стохастической аппроксимации, как и метод имита-

ционного усреднения, представляет собой итерационную проце-

дуру градиентного типа. При реализации данного метода на каж-

дом шаге процесса происходит движение к оптимуму в некотором

случайном направлении в пространстве альтернатив. При этом

сам итерационный процесс сходится при определенных условиях.

Использование классических методов стохастической аппрокси-

мации

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

ет их соответствующей модификации для задач условной опти-

мизации.

13.2.3. Модель двухэтапного стохастического выбора.

Как уже отмечалось в 13.1, реализация плана (программы

управления) производится в условиях изменяющейся внешней

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

гошаговые методы принятия решений и, в частности, принятие

решений по схеме ... → (сбор информации, анализ, прогноз) →

(принятие решения) → (коррекция решения) → (реализация пла-

на)...

Коррекция решения производится либо

на этапе непосред-

ственно предшествующем реализации плана, либо на этапе реа-

лизации плана по результатам наблюдения и оценки состояния

среды. Причем под коррекцией понимают, как правило, компен-

сацию возмущений среды за счет заранее выделенных ресурсов

(иначе такую коррекцию называют коррекцией по программе

управления - плану, в отличие от коррекции по конечному

состоя-

нию).

В этой связи основным содержанием задачи двухэтапного

стохастического выбора является поиск такого плана (нахожде-

ние такого решения), который с учетом последующей его коррек-

ции позволил бы минимизировать затраты на эту коррекцию. То-

гда содержание первого этапа разработки программы управления

состоит в поиске указанного плана, а содержание второго этапа

состоит

в коррекции плана по результатам наблюдений за со-

стоянием среды.

Формальная постановка задачи двухэтапного стохастиче-

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

x - M( d

(ω) y ) → max, (13.6)

A(ω) x + B(ω) y = b(ω) , ω ∈ Ω, (13.7)

x, y ≥ 0. (13.8)

274

Здесь

x - решение, принимаемое на первом этапе до наблюдения ω;

y - коррекция решения x по результатам наблюдения за со-

стоянием среды;

ω - наблюдаемое состояние среды, которое на этапе выбора x

неизвестно;

с - коэффициенты целевой функции исходной задачи выбора,

которые позволяют оценить качество принятого решения;

d(ω) - вектор стоимости затрат на проведение коррекции в том

случае, если среда приняла состояние ω;

A(ω) - матрица условий, ограничивающих выбор x, соответст-

вующих состоянию среды ω;

B(ω) - матрица условий проведения коррекции;

b(ω) - реализация вектора ограничений в том случае, если

среда находится в состоянии ω.

M(d

(ω) y) представляет собой среднее значение (математиче-

ское ожидание) затрат на проведение коррекции в условиях ω.

Величина (b(ω) - A(ω)x) характеризует величину возмуще-

ний (невязки), обусловленных состоянием среды ω, которые не-

обходимо компенсировать в результате проведения коррекции.

В общем случае решение задачи при известном законе

распределения ω является достаточно трудоемким, т.к.

произ-

водится на основе использования методов имитационной стохас-

тической оптимизации.

Рассмотрим случай, когда множество Ω конечно. Тогда ве-

роятностное пространство задается множеством пар (ω

), (ω

),...,(ω

), где ω

∈Ω - i-е состояние среды, p

- вероятность i-го

состояния. В этом случае число решений (число возможных кор-

рекций) второго этапа конечно и равно n, соответствующее мно-

жество имеет вид {y

,...,y

}. Решение первого этапа (план) и

множество решений второго этапа (множество возможных кор-

рекций) находятся в результате решения поставленной задачи

(13.6)-(13.8), которая примет вид:

x -

∑

) → max, (13.9)

x + B

= b

, i = 1,...,n , (13.10)

x, y

≥ 0. i = 1,...,n. (13.11)

275

Здесь

=A(ω

=B(ω

=d(ω

=b(ω

), i = 1,...,n. Матрица усло-

вий задачи (13.9)-(13.11) имеет вид

0 ...… 0

0 B

...... 0

. . . . . . . . . . .

0 0 ..…. B

т.е. она имеет блочно-диагональную структуру с левым окаймле-

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

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

13.3. Принятие решений в условиях целенаправленной

среды

Принятие решений в условиях целенаправленной среды

связано с тем, что известна цель среды, в соответствии с которой

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

ствиях. Эти действия могут вступать в противоречия с нашими

действиями, т.е. формируется конфликтная ситуация.

К о н ф л и к т н

о й с и т у а ц и е й назовем ситуацию, в

которой сталкиваются интересы нескольких оперирующих сторон,

преследующих различные цели.

Конфликтная ситуация характеризуется: составом опери-

рующих сторон; целями, которые преследует каждая из сторон;

способами участия оперирующих сторон в конфликте; возможны-

ми результатами разрешения (исходами) конфликта.

Формализованную модель

некоторой конфликтной ситуа-

ции называют и г р о й .

Методы принятия рациональных решений в условиях целе-

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

стоящее время в рамках т е о р и и и г р, которая входит в ка-

честве раздела в общую теорию выбора и принятия решений.

Теория

игр является математической теорией моделей принятия

решений при целенаправленном воздействии среды. Эта теория

создает формальную основу для анализа конфликтных и проти-

воречивых ситуаций и, в конечном итоге, позволяет формулиро-

вать рекомендации о наилучшем поведении в таких ситуациях. Ее

предназначение - выработка рекомендаций по рациональному

поведению участников конфликта (оперирующих сторон - игро-

276

ков). Формальное описание игры предполагает задание множест-

ва участников конфликта, задание множеств разнообразных кон-

тролируемых ими параметров и формулирование правил, по ко-

торым производится выбор параметров и оценивается эффек-

тивность всевозможных действий участников. Цели участников

конфликта не обязательно должны быть антагонистическими.

Конкретное описание конфликтной ситуации осуществляет-

ся путем задания определенных п

р а в и л игры. В частности, в

качестве таких правил могут выступать:

- возможные действия игроков;

- состав информации о действиях других игроков и об услови-

ях, в которых происходит игра;

- оценки качества действий каждого из игроков в ходе кон-

фликта.

Игры с различными правилами можно классифицировать по

следующим

признакам.

1. Количество участников игры. По этому признаку различают

игры двух игроков и игры n лиц.

2. Мощность множеств выбора игроков (количество возможных

вариантов действий каждого участника). Различают игры конеч-

ные и бесконечные.

3. Суммарный выигрыш игроков: игры с нулевой (ненулевой)

суммой.

4. Количество розыгрышей игры. Различают одношаговые,

многошаговые и дифференциальные (непрерывные) игры.

Если

игра многошаговая, то различают фиксацию очередности ходов -

игры с фиксированной (нефиксированной) последовательностью

ходов.

5. Информированность игроков - состав имеющейся у участни-

ков игры информации о действиях противника, функциях выиг-

рыша, числе ходов и т.д. Различают игры с полной информацией

и игры с неполной информацией.

6. Математико-психологические аспекты игры:

- угрозы -

информированность противника о возможных по-

следствиях его хода;

- блеф - ложная информация, сообщаемая противнику;

- рефлексия - постановка себя на место противника.

В зависимости от значений указанных признаков рассмат-

ривают различные конкретные игры. Так, например, а н т а г о -

н и с т и ч е с к о й и

г р о й называется игра n лиц (игроков) с

нулевой суммой.

277

Игры n лиц в зависимости от характера взаимоотношений

игроков могут быть б е с к о а л и ц и о н н ы м и и к о а л и ц и -

о н н ы м и. В первых играх между игроками не допускается ни-

каких соглашений для

принятия совместных решений, во-вторых -

игроки могут составлять коалиции для принятия согласованных

решений с целью увеличения выигрыша каждого игрока.

П а р т и я и г р ы представляет из себя фиксированный

вариант реализации игры при неизменных правилах и складыва-

ется из отдельных х о д о в - решений,

принимаемых противо-

положными сторонами.

Поведение каждой из оперирующих сторон (игроков) харак-

теризуется стратегией.

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

определяющих выбор варианта действий (принятия решения) при

каждом личном ходе игрока в зависимости от ситуации, сложив-

шейся в процессе игры.

В ряде случаев в

связи с необходимостью отражения сте-

пени информированности игроков происходит расширение поня-

тия стратегии. Стратегия рассматривается как функция со значе-

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

зависят от имеющейся и ожидаемой информации о действиях

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

может быть достаточно много.

О п т

и м а л ь н о й с т р а т е г и е й игрока принято на-

зывать такую стратегию, которая при многократном повторении

партий игры обеспечивает ему максимально возможный выигрыш

(или соответственно минимально возможный проигрыш).

Таким образом, о с н о в н о й

ц е л ь ю изучения игр яв-

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

мальному выигрышу игрока. При выборе оптимальной стратегии

содержание основной гипотезы о поведении противника состоит в

предположении, что он разумен и делает все для увеличения

своего выигрыша.

13.3.1. Постановка задач игрового выбора.

Рассмотрим формализованное представление задачи при-

нятия решений в условиях целенаправленной среды. Обобщен-

ную задачу принятия решения в условиях неопределенности

можно записать в виде

(Δ × Ω, {f

, j∈G} ),

278

где в качестве среды Ω выступают противники, преследующие

свои цели f

, j ∈ {2,…,n}.

Т.к. имеется n оперирующих сторон, то множество альтер-

натив Δ × Ω

представляется в виде декартового произведения

(расчленяется)

Δ × Ω =

× Δ

× ⋅ ⋅ ⋅ × Δ

где Δ

- множество альтернатив j-ой оперирующей стороны (игро-

ка), j=1, 2,..., n (здесь Δ

=Δ). Соответственно множество целевых

функций f

,j∈G, заданных на Δ×Ω представляет собой множество

функций выигрыша игроков, f

: Δ

×Δ

×⋅⋅⋅× Δ

→ R

, j∈G={1,2,...,n}.

Неопределенность выбора заключается в том, что каждая

оперирующая сторона осуществляет выбор альтернативы x

∈Δ

, в

тоже время качество принятого решения (выигрыш) определяется

функцией f

,..,x

), то есть зависит от выбора других игроков, ко-

торый заранее неизвестен.

Таким образом, каждый j-ый игрок решает задачу

= arg max f

( x

, x

,..., x

), (13.12)

∈Δ

и целью теории игр является разрешение этой неопределенной

ситуации.

13.3.2. Матричные игры. Чистые и смешанные стра-

тегии.

Простейшим вариантом игры является антагонистическая

игра, в которой противодействуют две оперирующих стороны (2

игрока), при этом множества различных альтернатив, из которых

они выбирают свои решения, конечны. Такая игра называется

матричной.

М а т р и ч н о й и г р о й называется конечная игра двух

лиц с нулевой суммой

Тогда такая игра характеризуется конструкцией

(

× Δ

, { f

, f

}). (13.13)

Участники игры могут выбирать свои решения из конечного

множества альтернатив

= X = { x

, i = 1,..., m },

= Y = { y

, j = 1,..., n }.

279

Т.к. игра антагонистическая, то f

=0. Откуда f

= f; f

= -f. В

такой игре может быть m×n различных исходов, которые характе-

ризуются различными значениями выигрыша первого игрока f

f(x

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

матрицей выигрышей F (платежная матрица), элементы f

кото-

рой характеризуют выигрыш первого игрока и, соответственно,

проигрыш второго при выборе игроками альтернатив, номера ко-

торых соответствуют номеру строки i и столбца j этой матрицы.

Итак, совокупность пар (x

) характеризует множество ис-

ходов игры, а матрица, содержащая элементы соответствующие

значениям выигрыша, называется п л а т е ж н о й м а т р и ц е й

и имеет следующий вид

. . . . . . . . . y

. . . . . . . . . f

F = . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . .

. . . . . . . . . f

В матричных играх, под стратегией понимается ход, приво-

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

вого игрока равно X и его часто называют множеством ч и с т ы х

с т р а т е г и й первого игрока.

Проанализируем рациональное поведение одного из игро-

ков, например, первого

. На каждую i-ю стратегию (ход, максими-

зирующий выигрыш) первого игрока, второй игрок ответит j-ой

стратегией, которая минимизирует выигрыш первого игрока от

применения его стратегии. Тогда гарантированный выигрыш пер-

вого игрока от применения i-ой чистой стратегии при использова-

нии всех возможных стратегий второго игрока будет равен

(-)

= min f

, j=1,…,n

В этих условиях для первого игрока наилучшим (оптималь-

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

рующей значение гарантированного выигрыша F

(-)

, соответствен-

но наилучшей стратегией является стратегия, на которой дости-

гается

(-)

= max F

(-)

= max min f

. (13.14)

i i j

280

Это для первого игрока гарантированный выигрыш (при ра-

циональном его поведении меньше этого значения он выиграть

не может), который называется н и ж н е й ц е н о й и г р ы.

Стратегии, доставляющие первому игроку выигрыш, рав-

ный нижней цене игры называются г а р а н

т и р у ю щ и м и.

Второй игрок, поступая аналогично, путем выбора своих га-

рантирующих стратегий может свести свой проигрыш к гаранти-

рованному минимуму

(+)

= min max f

, (13.15)

j i

который называется в е р х н е й ц е н о й и г р ы. Для первого

игрока F

(+)

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

рыш при рациональном поведении второго игрока. Обычно при-

нято оба вида гарантирующих стратегий для краткости называть

минимаксными.

Итак, первый игрок имеет m чистых стратегий, а второй иг-

рок имеет n чистых стратегий. В каждой строке платежной матри-

цы F, характеризующей возможные исходы игры, первый игрок

выбирает элемент матрицы,

имеющий наименьшее значение,

далее среди этих значений ищется наибольшее, которое и соот-

ветствует нижней цене игры. В каждом столбце матрицы второй

игрок выбирает наибольшее значение, а затем среди этих значе-

ний находится наименьшее значение (наименьший проигрыш),

что соответствует верхней цене игры.

Рациональным поведением игрока в такой ситуации явля-

ется, очевидно, выбор

гарантирующей стратегии, тогда его выиг-

рыш будет находиться в диапазоне от F

(-)

до F

(+)

Пример.

3 6 7 3 3 3*

1 4 4 2 4 1

F = 9 3 1 6 8 1 гарантирующие

4 5 3 4 8 3* стратегии 1-го игрока

9 6* 7 6* 8

гарантирующие стратегии

2-го игрока

(-)

= 3; F

(+)

= 6.

Если верхняя цена игры равна нижней F

(-)

= F

(+)

= С, то игру

называют игрой, р а з р е ш и м о й в ч и с т ы х с т р а т е г и я х,