Теория принятия решений, страница 5

Стратегия x̃a ∈ M называется абсолютно оптимальной,еслиF (x̃a , y, θ) = max F (x̃, y, θ) ∀ y ∈ N.x̃∈MТеорема 3.4. Пусть существует абсолютно оптимальная стратегия x̃a ∈M. Тогда x̃a − оптимальная стратегия иFг (M ) = inf max F (x̃, y, θ).y∈N x̃∈MДоказательство. Для любой стратегии x̃ ∈ M имеемW (x̃) = inf F (x̃, y, θ) ≤ inf max F (x̃, y, θ) =y∈Ny∈N x̃∈M21= inf F (x̃a , y, θ) = W (x̃a ).y∈NСледствие. 1) Пусть для любых y ∈ N достигается max F (x, y, θ). Тогдаx∈M0defFи = Fг (Mи ) = inf max F (x, y, θ).y∈N x∈M02) Пусть для любых y ∈ N, z ∈ Z достигается max F (x, y, z). Тогдаx∈M0ZdefF̃ = Fг (M̃ ) = infmax F (x, y, z)dθ(z).y∈Nx∈M0ZЗамечание. Формулы для Fи и F̃ не содержат символов оптимизации помножеству функций.Доказательство. 1). Определим стратегию x̃a из следующего условия:x̃a (y) ∈ Arg max F (x, y, θ) при любом y ∈ N.

Стратегия x̃a содержится воx∈M0множестве стратегий Mи . Покажем, что она абсолютно оптимальна. Действительно, для любой стратегии x̃ ∈ Mи и любом y ∈ NF (x̃, y, θ) = F (x̃(y), y, θ) ≤ max F (x, y, θ)x∈M0и равенство здесь достигается на стратегии x̃a . По теореме 3.4Fи = inf max F (x̃, y, θ) = inf max F (x, y, θ).y∈N x̃∈My∈N x∈M02) Определим стратегию x̃a из следующего условия:x̃a (y, z) ∈ Arg max F (x, y, z)x∈M0при любых y ∈ N, z ∈ Z. Стратегия x̃a содержится во множестве стратегийM̃ . Покажем, что она абсолютно оптимальна. Действительно, для любыхx̃ ∈ M̃ и y ∈ NZZF (x̃, y, θ) = F (x̃(y, z), y, z)dθ(z) ≤max F (x, y, z)dθ(z) =x∈M0ZZZF (x̃a (y, z), y, z)dθ(z) = F (x̃a , y, θ).=ZПо теореме 3.4ZF̃ = inf max F (x̃, y, θ) = infy∈N x̃∈M̃max F (x, y, z)dθ(z).y∈Nx∈M0Z22Пусть для множества стратегий M при некотором y ∈ N max F (x̃, y, θ)x̃∈Mне достигается, но sup F (x̃, y, θ) < +∞.

Тогда можно ввести понятие εx̃∈Mабсолютно оптимальной стратегии.Определение. Пусть задано ε > 0. Стратегия x̃εa ∈ M называется εабсолютно оптимальной, еслиF (x̃εa (y, z), y, θ) ≥ sup F (x̃, y, θ) − ε, ∀ y ∈ N.x̃∈MРассмотрим пример множества стратегий, не содержащих ε-абсолютно оптимальные стратегии.Пример. Пусть M = M0 = {1, 2}, N = {1, 2}, а z отсутствует.

Критерийэффективности зададим матрицей−11(F (i, j))2×2 =, i ∈ M0 , j ∈ N.1 −1Докажем, что при 0 ≤ ε < 2 в M0 не существует ε-абсолютно оптимальнойстратегии. Возьмем i = 1. Тогда F (1, 1) = −1 < 1 − ε = F (2, 1) − ε, т.е. приj = 2 нарушается неравенство из определения ε-абсолютно оптимальнойстратегии. Итак, доказано, что стратегия i = 1 не является ε-абсолютнооптимальной. Аналогично доказывается, что стратегия i = 2 также не εабсолютно оптимальна.Теорема 3.40 .

Пусть для всякого ε > 0 существует ε-абсолютно оптимальная стратегия x̃εa ∈ M. Тогда стратегия x̃εa ε-оптимальна иFг (M ) = inf sup F (x̃, y, θ).y∈Nx̃∈MДокажите самостоятельно.Следствие. 1) Пусть для любых y ∈ N величина sup F (x, y, θ) конечx∈M0ная. ТогдаdefFи = Fг (Mи ) = inf sup F (x, y, θ).y∈N x∈M02) Пусть для любых y ∈ N, z ∈ Z величина max F (x, y, z) конечная.x∈M0ТогдаdefZF̃ = Fг (M̃ ) = infy∈Nsup F (x, y, z)dθ(z).Zx∈M0Докажите самостоятельно.Закончим параграф сравнением наилучших гарантированных результатов для четырех множеств стратегий : M0 , {ϕ}, Mи и M̃ . Положим Fг0 =Fг (M0 ).

Ранее ввели величиныFc = sup W (ϕ), Fи = Fг (Mи ), F̃ = Fг (M̃ ).ϕ∈{ϕ}23Теорема 3.5. Справедливы неравенстваFг0 ≤ Fc ≤ Fи ≤ F̃ .Предположим, что случайный фактор z отсутствует, M0 и N − параллелепипеды евклидовых пространств, а критерий F (x, y) непрерывен на M0 ×N.Тогда, если F вогнут по x, то Fг0 = Fc , а если F является выпуклым по y,то Fc = Fи .Доказательство.

Напомним, что закон распределения случайных факторов θ предполагается известным. ИмеемZ0F (x, y, θ)dϕ(x) = Fc ,Fг = sup inf F (x, y, θ) ≤ sup infϕ∈{ϕ} y∈Nx∈M0 y∈NM0поскольку M0 ⊂ {ϕ}. Далее, для любой смешанной стратегии ϕ ∈ {ϕ}ZW (ϕ) = infF (x, y, θ)dϕ(x) ≤ inf sup F (x, y, θ) = Fи .y∈Ny∈N x∈M0M0Отсюда Fc ≤ Fи . Неравенство Fи ≤ F̃ вытекает из включения множествстратегий: Mи ⊂ M̃ .ПустьслучайныйDE фактор z отсутствует. Рассмотрим непрерывную игруΓ = M0 , N, F (x, y) , в которойFг0 = v = max min F (x, y), Fc = max minx∈M0 y∈NZϕ∈{ϕ} y∈NF (x, y)dϕ(x) = vM0− значение игры, Fи = v = min max F (x, y). Теперь все утверждения вытеy∈N x∈M0кают из теорем 1.14, 1.15.Результатам доказанной теоремы можно придать информационный смысл.Величину Цп = Fc − Fг0 можно рассматривать как ценность информациипротивника о значении x.

Покажем, что если противник знает x, то оперирующая сторона обеспечивает себе результат Fг0 . Оценка эффективностилюбой смешанной стратегии ϕZW (ϕ) =min F (x, y)dϕ(x)y∈NM0не превосходитmax min F (x, y) = Fг0 .x∈M0 y∈NПоэтому в этом случае применение смешанных стратегий не имеет смысла,а использование чистых стратегий позволяет получить Fг0 . Если, наоборот,реализация значения x противнику неизвестна, то оперирующая сторонаможет получить результат Fc . Если критерий F (x, y) вогнут по x, то Цп = 0и противнику не имеет смысла добиваться информации о x.24Аналогично величину Цo = Fи − Fc можно рассматривать как ценностьинформации оперирующей стороны о значении y. Действительно, если информация о неопределенном факторе y ожидается, то оперирующая сторона получает результат Fи , а в противном случае − Fc . Если критерийF (x, y) является выпуклым по y, то Цo = 0 и оперирующей стороне неимеет смысла добиваться информации об y.Рассмотрим пример поиска оптимальных и абсолютно-оптимальных стратегий.

Пусть i ∈ M0 = {1, 2, 3}, j ∈ N = {1, 2, 3, 4}, случайный фактор zотсутствует. Критерий эффективности задается матрицей−1 25 2(F (i, j))3×4 =  3 2 −1 2 .4 23 1a) M = Mи − множество всех функций вида ĩ : N → M0 . Всего 81стратегия. Здесь по следствию теоремы 3.4Fи = Fг (Mи ) = min max F (i, j) = 2.1≤j≤4 1≤i≤3Стратегия ĩ0 оптимальна, если min F (ĩ0 (j), j) = 2 или F (ĩ0 (j), j) ≥ 2, ∀ j ∈1≤i≤3N. Перечислим возможные значения оптимальной стратегии: ĩ0 (1) = 2, 3, ĩ0 (2) =1, 2, 3, ĩ0 (3) = 1, 3, ĩ0 (4) = 1, 2.

Подчеркнутые значения отвечают однойконкретной оптимальной стратегии. Всего 2 · 3 · 2 · 2 = 24 оптимальныестратегии.Найдем все абсолютно-оптимальные стратегииĩa : F (ĩa (j), j) = max F (i, j).i∈M0Перечислим возможные значения абсолютно-оптимальной стратегии: ĩa (1) =3, ĩa (2) = 1, 2, 3, ĩa (3) = 1, ĩa (4) = 1, 2. Всего 6 абсолютно-оптимальныхстратегий.б) Пусть в начале операции оперирующей стороне будет известно, какому из множеств N1 = {1, 2} или N2 = {3, 4} принадлежит значение неопределенного фактора j. Здесь стратегия имеет вид(i1 , j ∈ N1 ,ĩ(j) =i2 , j ∈ N2 .Множество M состоит из 9 стратегий. В нем содержится абсолютно-оптимальная стратегия ĩa : ia1 = 3, ia2 = 1.

Следовательно, по теореме 3.4Fг (M ) = 2. Множество M содержит 2 оптимальные стратегии: i01 = 2, 3, i02 =1.§14. Необходимые условия для оптимальных стратегий.Рассмотрим операцию без случайных факторов и множеством стратегийM = M0 . В этом случае оптимальная стратегия x0 ∈ M0 является максиминной:W (x0 ) = max W (x), где W (x) = min F (x, y).x∈M0y∈N25Поиск максиминных и минимаксных стратегий у нас встречался при решении антагонистических игр.Найдем необходимые условия для максиминных стратегий и обсудимметод их поиска. Необходимые условия будут использовать формулу дляпроизводной по направлению функции минимума W (x).Напомним определение производной по направлению функции многихпеременных. Пусть в евклидовом пространстве E m задана функция h(x).Возьмем вектор α ∈ E m , задающий направление в E m .Определение.

Величинаlimε→+0h(x + εα) − h(x) def dh(x)=εdαназывается производной функции h(x) по направлению α в точке x.Как известно из курса математического анализа, если функция h(x)дифференцируема в E m , тоmdh(x) X=αi h0xi (x) = (α, h0 (x))dαi=1− скалярное произведение вектора α на градиент h0 (x) в точке x.Функция h(x) может не быть дифференцируемой в точке x0 , но иметьв этой точке производную по направлению.Пример. Пусть h(x) = min[f (x), g(x)], где x ∈ E 1 , функции f (x) иg(x) дифференцируемы, их графики пересекаются в точке x0 и f 0 (x0 ) >0, g 0 (x0 ) < 0 (рис.