К надежности информационных систем

7.2.1. Постановка задачи и принципы обоснования требований
к надежности ЭИС

Возможны постановки задачи обоснования требований к надежности ЭИС:

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

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

Так, если в ЭИС входят n последовательно (по структурной схеме надежности) соединенных групп устройств и для нее определена в ТЗ вероятность безотказной работы Р^*₃, то необходимо так распределить затраты DS_i на повышение надежности отдельных i-х устройств DР_i,

чтобы при выполнении условия

Р_i³ P^*₃ (7.4)

минимизировать затраты

DS = DS_i. (7.5)

На практике находят применение принципы выбора необходимых значений Р_i:

а) равная надежность всех групп устройств;

б) равные затраты на все группы устройств;

в) обратная пропорциональность затрат DS_i удельным затратам на повышение надежности dS_i i-го устройства;

г) минимум дополнительных затрат на обеспечение надежности.

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

, (7.6)

где DH_i = H_i – H^*_i = P^*_i – P_i – величина уменьшения ненадежности H_i =1- P_i i-го устройства, позволяющая повысить надежность i-х устройств до величин, обеспечивающих выполнение условия (7.4).

7.2.2. Распределение требований к надежности

Задача сводится к нахождению DH₁, DH₂,…, DH_n, минимизирующих целевую функцию при ограничениях

; DH_i ³ 0; i = 1,n,

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

7.3. Методы теории игр в задачах с конфликтными ситуациями

7.3.1. Основные понятия теории игр

Примерами таких задач могут быть:

1) разработка вооружения и его боевого применения;

2) выбор тактики спортивных игр;

3) выбор стратегии (сценария) финансовой политики;

4) выбор линии поведения продавца и покупателя на рынке;

5) исследования издержек измерений на компьютерном рынке;

6) выбор технической политики с учетом конкуренции.

Теорию игр определяют как математическую теорию конфликтных ситуаций, в которых сталкиваются интересы 2-х или более сторон, преследующих разные цели. Будем рассматривать игры только двух участников (К – красные и С – синие), имеющих m и n возможных стратегий К₁, К₂, …, К_mи С₁, C₂,..., С_n, каждой из которых соответствует определенный выигрыш K_j или проигрыш C_j (табл. 7.1). Если K_j известны для каждой пары стратегий, число которых конечно, то игра является полностью определенной и ее условия записываются в виде платежной матрицы m х n, приведенной к нормальной форме.

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

Таблица 7.1. Платежная матрица

	Cтратегии	Синие
Красные		С₁	С₂	С₃	…	…	С_n
К₁	К₁₁	К₁₂	…	…	…	К ₁_n
К₂	К₂₁	К₂₂	…	…	…	К ₂_n
К₃	К₃₁	К₃₂	К₃₃	…	…	…
…	…	…	…	…	…	…
…	…	…	…	…	…	…
К_m	К_m1	К_m2	…	….	…	К_mn

Таблица 7.2. Платежная матрица

	Преступник1
Преступник2	сознается	отрицает
сознается
отрицает

7.3.2. Задача теории игр. Принцип минимакса

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

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

Пример. Боевые применения оружия

У Красных 2 вида вооружения – К₁ и К₂, у Синих 2 вида помех – С₁ и С₂, K_ij – вероятность поражения цели при различных комбинациях вооружение – помехи. Решить игру при условии, что пользоваться каждому игроку можно только одной стратегией.

Пусть платежная матрица имеет вид (табл. 7.3).

Таблица 7.3. Платежная матрица

	c₁	c₂	Минимумы строк
k₁	0,2	0,8	0,2
k₂	0,7	0,3	α =0,3
Максимумы столбцов	β =0,7	0,8

Максимум из минимумов по строкам таблицы называется максимином, или нижней ценой игры (α = 0,3). Это максимальный выигрыш, который может быть гарантированным для одной стратегии.

Минимум из максимумов по столбцам таблицы называется минимаксом, или верхней ценой игры (β = 0,7). Это минимальный проигрыш, на который могут рассчитывать Синие, выбрав одну из своих стратегий в расчете на наихудшую для себя стратегию Красных.

Недостаток минимаксных стратегий – их неустойчивость, проявляющаяся в том, что они могут быть нарушены, если другая сторона раздобудет информацию о действиях своего противника. Исключение составляют игры, для которых α = β.Тогда говорят о чистой цене игры или просто о цене игры и обозначают ее ν. При этом в матрице имеется один или несколько элементов одновременно минимальных в своей строке и максимальных в своем столбце, называемых седловой точкой.

7.3.3. Решение игры в смешанных стратегиях.
Чистые и смешанные стратегии

При разных нижней и верхней ценах больший выигрыш достигается, когда применяются не одна единственная чистая стратегия, а комбинированные стратегии, т.е. несколько чистых, чередующихся случайным образом с определенной вероятностью (частотой) P, так называемые смешанные стратегии. При этом цена игры α<= ν<= β.

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

где p_i и q_i – частоты стратегий Красных и Синих соответственно.

В оптимально смешанную стратегию могут входить не все стратегии. Входящие в решение стратегии называются активными. Если активны все стратегии, то игра полностью усредненная.

7.3.4. Элементарные способы решения игр

в смешанных стратегиях (2х2)

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

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

Пример решения игры 2х2. Издержки измерений на компьютерном рынке представлены в табл. 7.4.

Пусть k_ij – условная доля прибыли посредника (издержек покупателя) при совершении сделки на компьютерном рынке.

Таблица 7.4. Платежная матрица

	Покупатель 1	Покупатель 2
Посредник 1	k₁₁=0,2	k₁₂=0,3	α =0,2
Посредник 2	k₂₁=0,35	k₂₂=0,1
		β =0,3

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

Решение. α = 0,2, β = 0,3. Игра не имеет седловой точки. Тогда в соответствии со свойством оптимальных смешанных стратегий выигрыш от использования посредником оптимальной стратегии S^*_k будет:

k₁₁p₁+k₂₁p₂= ν при использовании покупателем стратегии c₁,

k₁₂p₁+k₂₂p₂= ν при использовании покупателем стратегии c₂,

p₁₊ p₂=1.

Отсюда p₁= (k₂₂- k₂₁)/(k₁₁+ k₂₂- k₁₂- k₂₁) = 0,71;

p₂=1- p₁= 0,29;

ν = 0,24.

При любой стратегии величина ν та же, поэтому k₁₁q₁+ k₁₂q₂= ν для k₁.

С учетом того что q₁+ q₂=1, q₁= (ν- k₁₁)/(k₁₁- k₁₂) = 0,6, q₂= 0,4.

Геометрическая интерпретация этого решения представлена на рис. 7.1.

K¹₁

q₂

k₂₂

k₁₂

k₂₁

k¹₁

Стратегия Синих

k₁₁

K¹₂

q₁

k₁

Линия стратегии k₁

Линия стратегии k₂

Рис. 7.1. Графическое решение игры 2х2 в смешанных стратегиях

7.3.5. Решение игр 2хn

Для любой игры mxn, где m<n, существует решение, в котором с каждой стороны участвует не больше m активных стратегий. Отсюда следует, что у любой игры 2xn есть решение, в котором с каждой стороны участвует не более 2 активных стратегий, то есть любая игра 2xn сводится к игре 2x2.

Для этого строят линии стратегии Синих, выделяют нижнюю границу выигрыша и на ней находят точку N с минимальной ординатой. Линии, пересекающиеся в точке N, представляют 2 активные стратегии.

Аналогично решают задачу mx2, только меняют ролями Красные и Синие и строят верхнюю границу проигрыша.

Если через точку N проходит более двух линий, то в качестве активной можно взять любую из них.

Геометрическая интерпретация решения представлена на рис. 7.2.

C₃

C₂

C₁

C₄

C¹₄

C¹₂

C¹₁

C¹₃

K₅

K₃

K₂

K₄

K₁

K¹₄

K¹₁

K¹₃

K₁

C₁

C₂

K₂

Стратегия Красных

Стратегия Синих

mx2

2xn

Рис. 7.2. Графическое решение игры 2хn в смешанных стратегиях

7.3.6. Методы решения игр при m>2 и n>2

Геометрическая интерпретация в этом случае не помогает (даже при 3xn – не наглядно). Поэтому применяют 4 пути сведения таких игр к более простым, поддающимся решению рассмотренными выше или другими методами:

1. Объединение некоторых стратегий в смешанные, например из соображений симметрии, и сведение игры к 2xn.

2. Сведение игры к m x m и решение m уравнений.

3. Приближенные методы решения игр путем итерации.

4. Выделение активных стратегий и решение игры методами линейного программирования.

Некоторые из них рассмотрены ниже на конкретных примерах.

Пример 1. Распределение усилий (выбор технической политики) в условиях конкуренции (табл. 7.5).

Красные и Синие конкурируют за рынок в 2-х сферах. Ресурсы Красных – 2 у.е., Синих – 3 у.е. Возможные распределения ресурсов представлены в матрице. Явное преимущество оценивается вероятностью Р = 1 и достигается стороной в той сфере, где она сосредоточивает в 1,5 – 2 раза больше ресурсов или не встретила вообще противодействия конкурентов. При равных вложениях ресурсов (1 против 1 и 2 против 2) в одной сфере победа достается Красным с вероятностями Р₁и Р₂ соответственно. Цель Красных – завоевать преимущество хотя бы в одной сфере бизнеса.

Таблица 7.5. Платежная матрица

	C₁ (3, 0)	C₂ (0, 3)	C₃ (1, 2)	C₄ (2, 1)	Минимум строк
K₁ (2,0)				P₂
K₁₂	0,5	0,5	0,5(1+P₂)	0,5(1+P₂)	0,5
K₂ (0,2)			P₂
K₃ (1,1)			P₁	P₁	Р1
Максимум столбцов

Из таблицы следует, что α = Р₁; β = 1.

Игра имеет решение в области смешанных стратегий. Из симметрии стратегий К₁ и К₂, С₁ и С₂, С₃ и С₄ следует возможность объединения их в смешанные С₁₂, К₁₂ и С₃₄ с вероятностями p₁= p_2, q₁= q₂, q₃= q_4, равными 0,5, и с выигрышами, определяемыми как среднее арифметическое из соответствующих строк матрицы. Тогда матрица будет иметь вид

	С₁₂	С₃₄
К₁₂	0,5	0,5+(1+Р₂)
К₃		Р₁

Игра 2x2 может быть решена при любых значениях Р₁ и Р₂, например: при Р₁= 0,5, Р₂= 0,75 получим

	С₁₂	С₃₄
К₁₂	0,5	0,875
К₃		0,5

Решение игры:

0,5-1 = 0,57; 0,5+0,5-1-0,87

Р₁₂=

Р₃= 1-Р₁₂= 0,43;

ν = 0,5·0,572+1·0,43 = 0,71;

K₁₂ K₃ 0,57 0,47

S^*_k =;

0,75 - 0,875 = 0,43; 0,5 - 0,875

q₁₂=

q₃₄= 1-0,43 = 0,57;

C₁₂ C₃₄ 0,43 0,57

S*_c=,

то есть для Красных предпочтительно сосредоточение ресурсов в одной сфере, а для Синих – распределение по двум направлениям. Если же 0,5(1+Р₂)<Р₁(игра имеет седловую точку (К₃, С₃₄), то и Синим и Красным выгодно рассредоточить ресурсы по двум направлениям.

Пример 2. Решить игру 3x3 методом приближенных итераций. Идея метода сводится к следующему. Считается, что противники (конкуренты) на каждую выбранную противоположной стороной стратегию K_i отвечают такой своей чистой стратегией C_j, которая является наихудшей мерой для противника против всех его предыдущих выборов. Эти предыдущие выборы рассматриваются как своеобразная «смешанная стратегия», где чистые стратегии смешаны в пропорциях, соответствующих частоте их применения в прошлом. Аналогично, на каждую новую стратегию Синих C_l Красные отвечают своей стратегией K_m, наихудшей для всех предыдущих выборов Синих. Если такой процесс продолжать достаточно долго, то средний выигрыш, приходящийся на одну партию (однократные осуществления игры), будет стремиться к цене игры, а частоты применения стратегий – к оптимальным частотам. Сходимость метода медленная, но вполне приемлемая для практики. Конкретизация данного метода на числовом примере приведена в подразделе 8.5. Более подробно данный материал изложен в подразделе 8.5, а также в [1].