К надежности информационных систем
7.2.1. Постановка задачи и принципы обоснования требований
к надежности ЭИС
Возможны постановки задачи обоснования требований к надежности ЭИС:
прямая – максимизировать значение показателя надежности ЭИС при выполнении ограничений на некоторые ресурсы, например стоимость, массогабаритные, энергетические и др. характеристики;
обратная – при заданных значениях надежности ЭИС распределить имеющиеся ограниченные ресурсы между отдельными компонентами (устройствами) ЭИС так, чтобы минимизировать один (например, стоимость) или несколько видов ресурсов.
Так, если в ЭИС входят n последовательно (по структурной схеме надежности) соединенных групп устройств и для нее определена в ТЗ вероятность безотказной работы Р*3, то необходимо так распределить затраты DSi на повышение надежности отдельных i-х устройств DРi,
чтобы при выполнении условия
Рi ³ P*3 (7.4)
минимизировать затраты
DS = DSi. (7.5)
На практике находят применение принципы выбора необходимых значений Рi:
а) равная надежность всех групп устройств;
б) равные затраты на все группы устройств;
в) обратная пропорциональность затрат DSi удельным затратам на повышение надежности dSi i-го устройства;
г) минимум дополнительных затрат на обеспечение надежности.
При наличии ограничений по нескольким ресурсам наибольший эффект дает применение последнего принципа, в соответствии с которым требуемые для выполнения условия (7.4) затраты можно представить в виде
, (7.6)
где DHi = Hi – H*i = P*i – Pi – величина уменьшения ненадежности Hi =1- Pi i-го устройства, позволяющая повысить надежность i-х устройств до величин, обеспечивающих выполнение условия (7.4).
7.2.2. Распределение требований к надежности
Задача сводится к нахождению DH1, DH2,…, DHn, минимизирующих целевую функцию 
при ограничениях
; DHi ³ 0; i = 1,n,
что соответствует стандартному виду задачи линейного программирования, решаемой известными способами.
7.3. Методы теории игр в задачах с конфликтными ситуациями
7.3.1. Основные понятия теории игр
Примерами таких задач могут быть:
1) разработка вооружения и его боевого применения;
2) выбор тактики спортивных игр;
3) выбор стратегии (сценария) финансовой политики;
4) выбор линии поведения продавца и покупателя на рынке;
5) исследования издержек измерений на компьютерном рынке;
6) выбор технической политики с учетом конкуренции.
Теорию игр определяют как математическую теорию конфликтных ситуаций, в которых сталкиваются интересы 2-х или более сторон, преследующих разные цели. Будем рассматривать игры только двух участников (К – красные и С – синие), имеющих m и n возможных стратегий К1, К2, …, Кm и С1, C2,..., Сn, каждой из которых соответствует определенный выигрыш Kj или проигрыш Cj (табл. 7.1). Если Kj известны для каждой пары стратегий, число которых конечно, то игра является полностью определенной и ее условия записываются в виде платежной матрицы m х n, приведенной к нормальной форме.
В качестве иллюстрации приведем пример «Дилемма заключенных», показывающий привлечение преступников к сотрудничеству с полицией (табл. 7.2) за счет снижения наказания при сотрудничестве.
Таблица 7.1. Платежная матрица
| Cтратегии | Синие | ||||||
| Красные | С1 | С2 | С3 | … | … | Сn | |
| К1 | К11 | К12 | … | … | … | К 1n | |
| К2 | К21 | К22 | … | … | … | К 2n | |
| К3 | К31 | К32 | К33 | … | … | … | |
| … | … | … | … | … | … | … | |
| … | … | … | … | … | … | … | |
| Кm | Кm1 | Кm2 | … | …. | … | Кmn |
Таблица 7.2. Платежная матрица
| Преступник1 | |||
| Преступник2 | сознается | отрицает | |
| сознается | |||
| отрицает |
7.3.2. Задача теории игр. Принцип минимакса
Целью теории игр является определение оптимальной стратегии каж-дого из игроков в конфликтной ситуации. Решить игру – значит найти оптимальные стратегии. Оптимальной называется стратегия, обеспечивающая при многократном повторении игры максимально возможный средний выигрыш или минимально возможный средний проигрыш.
Для ее реализации необходимо придерживаться принципа – выбирай свое поведение так, чтобы оно было рассчитано на наихудший для тебя образ действий противника. Такой принцип, диктующий каждому игроку выбор своей наиболее осторожной (перестраховочной) стратегии, носит название минимакса, а стратегии, рекомендуемые этим принципом, – минимаксными.
Пример. Боевые применения оружия
У Красных 2 вида вооружения – К1 и К2, у Синих 2 вида помех – С1 и С2, Kij – вероятность поражения цели при различных комбинациях вооружение – помехи. Решить игру при условии, что пользоваться каждому игроку можно только одной стратегией.
Пусть платежная матрица имеет вид (табл. 7.3).
Таблица 7.3. Платежная матрица
| c1 | c2 | Минимумы строк | |
| k1 | 0,2 | 0,8 | 0,2 |
| k2 | 0,7 | 0,3 | α =0,3 |
| Максимумы столбцов | β =0,7 | 0,8 |
Максимум из минимумов по строкам таблицы называется максимином, или нижней ценой игры (α = 0,3). Это максимальный выигрыш, который может быть гарантированным для одной стратегии.
Минимум из максимумов по столбцам таблицы называется минимаксом, или верхней ценой игры (β = 0,7). Это минимальный проигрыш, на который могут рассчитывать Синие, выбрав одну из своих стратегий в расчете на наихудшую для себя стратегию Красных.
Недостаток минимаксных стратегий – их неустойчивость, проявляющаяся в том, что они могут быть нарушены, если другая сторона раздобудет информацию о действиях своего противника. Исключение составляют игры, для которых α = β.Тогда говорят о чистой цене игры или просто о цене игры и обозначают ее ν. При этом в матрице имеется один или несколько элементов одновременно минимальных в своей строке и максимальных в своем столбце, называемых седловой точкой.
7.3.3. Решение игры в смешанных стратегиях.
Чистые и смешанные стратегии
При разных нижней и верхней ценах больший выигрыш достигается, когда применяются не одна единственная чистая стратегия, а комбинированные стратегии, т.е. несколько чистых, чередующихся случайным образом с определенной вероятностью (частотой) P, так называемые смешанные стратегии. При этом цена игры α<= ν<= β.
Используются специальные обозначения для смешанных стратегий, например:
,
,
где pi и qi – частоты стратегий Красных и Синих соответственно.
В оптимально смешанную стратегию могут входить не все стратегии. Входящие в решение стратегии называются активными. Если активны все стратегии, то игра полностью усредненная.
7.3.4. Элементарные способы решения игр
в смешанных стратегиях (2х2)
Решение игр mхn, особенно при больших m и n, очень трудная задача. Поэтому пытаются их упростить, сведя к игре 2х2. Пути упрощениямогут быть следующие: вычеркивание стратегий дублирующих, заведомо невыгодных, практически мало отличающиеся от других стратегий и доведение матрицы до вида 2хn.
Если придерживаться своей оптимальной смешанной стратегии, то выигрыш будет неизменным и равным цене игры ν независимо от того, что делает другой игрок, если только он не выходит за пределы своих активных стратегий.
Пример решения игры 2х2. Издержки измерений на компьютерном рынке представлены в табл. 7.4.
Пусть kij – условная доля прибыли посредника (издержек покупателя) при совершении сделки на компьютерном рынке.
Таблица 7.4. Платежная матрица
| Покупатель 1 | Покупатель 2 | ||
| Посредник 1 | k11=0,2 | k12=0,3 | α =0,2 |
| Посредник 2 | k21=0,35 | k22=0,1 | |
| β =0,3 |
Значения выбранных величин Kij учитывают не только денежные и временные затраты, но и косвенно потерю репутации посредника при отказе клиента от недобросовестных услуг, а также неоправданность отказа от части добросовестных услуг покупателем технически неграмотным.
Решение. α = 0,2, β = 0,3. Игра не имеет седловой точки. Тогда в соответствии со свойством оптимальных смешанных стратегий выигрыш от использования посредником оптимальной стратегии S*k будет:
k11 p1+k21 p2 = ν при использовании покупателем стратегии c1,
k12 p1 +k22 p2= ν при использовании покупателем стратегии c2,
p1+ p2=1.
Отсюда p1 = (k22 - k21 )/(k11 + k22 - k12 - k21 ) = 0,71;
p2 =1- p1 = 0,29;
ν = 0,24.
При любой стратегии величина ν та же, поэтому k11 q1 + k12 q2= ν для k1.
С учетом того что q1 + q2 =1, q1 = (ν- k11)/( k11 - k12) = 0,6, q2 = 0,4.
Геометрическая интерпретация этого решения представлена на рис. 7.1.
| N |
| K11 |
| q2 |
| k22 |
| k12 |
| II |
| I |
| k21 |
| k2 |
| k11 |
| Стратегия Синих |
| k11 |
| K12 |
| q1 |
| II |
| k1 |
| ν |
| I |
| Линия стратегии k1 |
| Линия стратегии k2 |
Рис. 7.1. Графическое решение игры 2х2 в смешанных стратегиях
7.3.5. Решение игр 2хn
Для любой игры mxn, где m<n, существует решение, в котором с каждой стороны участвует не больше m активных стратегий. Отсюда следует, что у любой игры 2xn есть решение, в котором с каждой стороны участвует не более 2 активных стратегий, то есть любая игра 2xn сводится к игре 2x2.
Для этого строят линии стратегии Синих, выделяют нижнюю границу выигрыша и на ней находят точку N с минимальной ординатой. Линии, пересекающиеся в точке N, представляют 2 активные стратегии.
Аналогично решают задачу mx2, только меняют ролями Красные и Синие и строят верхнюю границу проигрыша.
Если через точку N проходит более двух линий, то в качестве активной можно взять любую из них.
Геометрическая интерпретация решения представлена на рис. 7.2.
| C3 |
| C2 |
| C1 |
| C4 |
| C14 |
| C12 |
| C11 |
| C13 |
| K5 |
| K3 |
| K2 |
| K4 |
| K1 |
| K14 |
| N |
| ν |
| K11 |
| K13 |
| ν |
| K1 |
| C1 |
| C2 |
| K2 |
| N |
| Стратегия Красных |
| Стратегия Синих |
| mx2 |
| 2xn |
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) в одной сфере победа достается Красным с вероятностями Р1 и Р2 соответственно. Цель Красных – завоевать преимущество хотя бы в одной сфере бизнеса.
Таблица 7.5. Платежная матрица
| C1 (3, 0) | C2 (0, 3) | C3 (1, 2) | C4 (2, 1) | Минимум строк | |
| K1 (2,0) | P2 | ||||
| K12 | 0,5 | 0,5 | 0,5(1+P2) | 0,5(1+P2) | 0,5 |
| K2 (0,2) | P2 | ||||
| K3 (1,1) | P1 | P1 | Р1 | ||
| Максимум столбцов |
Из таблицы следует, что α = Р1; β = 1.
Игра имеет решение в области смешанных стратегий. Из симметрии стратегий К1 и К2, С1 и С2, С3 и С4 следует возможность объединения их в смешанные С12, К12 и С34 с вероятностями p1 = p2, q1 = q2, q3 = q4 , равными 0,5, и с выигрышами, определяемыми как среднее арифметическое из соответствующих строк матрицы. Тогда матрица будет иметь вид
| С12 | С34 | |
| К12 | 0,5 | 0,5+(1+Р2) |
| К3 | Р1 |
Игра 2x2 может быть решена при любых значениях Р1 и Р2 , например: при Р1 = 0,5, Р2 = 0,75 получим
| С12 | С34 | |
| К12 | 0,5 | 0,875 |
| К3 | 0,5 |
Решение игры:
| 0,5-1 = 0,57; 0,5+0,5-1-0,87 |
Р12=
Р3 = 1-Р12 = 0,43;
ν = 0,5·0,572+1·0,43 = 0,71;
| K12 K3 0,57 0,47 |
S*k = ;
| 0,75 - 0,875 = 0,43; 0,5 - 0,875 |
q12 =
q34 = 1-0,43 = 0,57;
| C12 C34 0,43 0,57 |
S*c= ,
то есть для Красных предпочтительно сосредоточение ресурсов в одной сфере, а для Синих – распределение по двум направлениям. Если же 0,5(1+Р2)<Р1 (игра имеет седловую точку (К3, С34), то и Синим и Красным выгодно рассредоточить ресурсы по двум направлениям.
Пример 2. Решить игру 3x3 методом приближенных итераций. Идея метода сводится к следующему. Считается, что противники (конкуренты) на каждую выбранную противоположной стороной стратегию Ki отвечают такой своей чистой стратегией Cj, которая является наихудшей мерой для противника против всех его предыдущих выборов. Эти предыдущие выборы рассматриваются как своеобразная «смешанная стратегия», где чистые стратегии смешаны в пропорциях, соответствующих частоте их применения в прошлом. Аналогично, на каждую новую стратегию Синих Cl Красныеотвечают своей стратегией Km, наихудшей для всех предыдущих выборов Синих. Если такой процесс продолжать достаточно долго, то средний выигрыш, приходящийся на одну партию (однократные осуществления игры), будет стремиться к цене игры, а частоты применения стратегий – к оптимальным частотам. Сходимость метода медленная, но вполне приемлемая для практики. Конкретизация данного метода на числовом примере приведена в подразделе 8.5. Более подробно данный материал изложен в подразделе 8.5, а также в [1].