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

1-й метод: Матрица игры имеет седловую точку, тогда решение сводится к поиску седловой точки матрицы, координаты которой (i₀,j₀) определяют элемент a_i0,j0 – цену игры, i₀ – чистая оптимальная стратегия 1-го игрока, j₀ – чистая оптимальная стратегия 2-го игрока.

Пример: Игра имеет матрицу

α₁=2; α₂=5; α₃=4; - min элемент в строке.→ max=5=α – верхняя цена игры.

β₁=10; β₁=10; β₁=5; β₁=14; β₁=12; - max элемент столбца→ min=5=β – нижняя цена игры.

a_2,3=5=α=β=υ – цена игры, т.е. оптимальная стратегия 1-го игрока №2, 2-го игрока № 3.

2-й метод: Матрица А имеет размер 2 x n (m x 2) или сводима к этим размерам, тогда задача может быть решена графически. Рассмотрим ситуацию 2 x n , тогда 1-й игрок имеет 2 стратегии и его искомая смешанная стратегия U(x₁,x₂), где x_i – это вероятности с которыми игрок применяет свои i стратегии, тогда средний выигрыш игрока 1-го, если 2-й игрок применяет свою стратегию y_j, равен: L(x,y_j)=x₁*a_1j+x₂*a_2j. Это может быть интерпретировано графически как прямая. Изобразив все стратегии 2-го игрока, как ответы на ход 1-го, определим максиминную стратегию, оптимальную для 1-го игрока. Аналогично, если матрица имеет размер m x 2, изображаем стратегии 1-го как ответы на ход второго. Найдем минимаксную стратегию, оптимальную для 2-го и находят его оптимальную смешанную стратегию.

Пример:

решаем систему.

В результате получим: х₁=2/3; х₂=1/3; U^*=(2/3; 1/3)

10 υ=8 (цена игры)

9 9

8

7 6

х₁ 1/3 х₂ y₁=y₂=1/2; y₃=0; υ=8;

X^*(2/3;1/2)→ 67% времени 1-й игрок применяет свою стратегию №1 и 33% времени стратегию № 2.

Пример 2:

Т.к. 2-й игрок имеет 2 стратегии, то решаем задачу для 2-го игрока, изображая стратегии 1-го как ответ на ход 2-го.

8

7

6

5

4

2

1

y₁₌3/8; y₂=5/8; υ=43/8

x₁=7/8; x₂=0; x₃=0; x₄=1/8 X^*(7/8;0;0;1/8)

Пример 3:

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

доминирующие

, т.е. седловой точки нет, но матрица после упрощения примет вид:

, и решаем задачу графически:

8

7 7

6

2

1

x₁=x₃=1/2; x₂=0; υ=4,5

y₄=y1=0; y₂=7/12; y₃=0; y₅=5/12

X^*(1/2;0;1/2);

Y^*(0;7/12;0;0;5/12);

υ=4,5;

3 метод. Матрица А имеет размер m x n , не имеет седловой точки и не может быть решена графически. Тогда задача теории игр сводится к задаче линейного программирования, а именно к паре взаимодвойственных задач для 1-го и 2-го игрока соответственно.

Задача 1-го игрока: Задача 2-го игрока:

F=υ→max Ф=U→min

y_j≥0

x_i≥0

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

I игрока II игрока

Примечание: При составлении ЗЛП важно, что все элементы матрицы a_ij≥0, если это не так, то рассматриваем матрицу:

, где , υ^/=υ+С.

Решив вспомогательные задачи 1-го и 2-го игрока, найдем оптимальные стратегии и основных задач.

Заметим, что при реализации симплекс-метода целесообразно сразу составлять задачу 2-го игрока.

Пример:

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

Решаем задачу симплекс-методом:

Базис	B
	1	1	2	0	1	0	0
	1	1	0	1	0	1	0
	1	2	1	0	0	0	1
Оценки	0	-1	-1	-1	0	0	0

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

Базис	B
	1/2	1	1	0	1/2	0	0
	1	1	0	1	0	1	0
	1/2	2	0	0	-1/2	0	1
Оценки	3/2	1/2	0	0	1/2	1	0

Решение вспомогательной задачи 1-го игрока, т.е. решение двойственной задачи для задачи 2-го

→

Методы искусственного интеллекта

1. Прикладные возможности нейронных сетей.

2. Экспертные системы.

3. Применение искусственных нейронных сетей.

4. Ассоциативные сети и системы фреймов.

5. Модели представления знаний.

6. Языки представления знаний. Логическое программирование.

7. Методы распознавания образов.

8. Свойства знаний и данных. Методы представления знаний.

9. Продукционные системы.

10. Разработка систем, основанных на знаниях.

11. Представление неопределенности знаний.

12. Технологии инженерии знаний.

13. Искусственные нейронные сети.

. Экспертные системы

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

Классификация экспертных систем, в основу которой положена специфика решаемых задач:

• интерпретирующие системы, формирующие описание ситуаций по результатам наблюдений или данных, полученных из внешней среды (например, распознавание образов, определение структуры веществ);

• прогнозирующие системы, производящие логический анализ возможных последствий заданных ситуаций или событий (например, предсказание погоды, прогноз ситуаций на финансовых рынках);

• диагностические системы, обнаруживающие источники неисправностей по результатам наблюдений за поведением контролирующей системы (например, диагностика в медицине, механике, электронике);

• системы проектирования, синтезирующие компоненты системы при заданных ограничениях и параметрах (например, синтез электронных схем, оптимальное размещение объектов в ограниченном пространстве);

• системы планирования, формирующие планы последовательности операций, приводящей к цели (например, составление маршрутов транспорта, планирование поведения роботов);

• системы мониторинга, производящие анализ поведения контролируемой системы (контроль движения воздушного транспорта, состояния энергетических объектов);

• наладочные системы, производящие рекомендации по устранению неисправностей в контролируемой системе (например, системы отладки программного обеспечения);

• обучающие системы, производящие анализ знаний в определенной области, выясняющие пробелы в знаниях и намечающие средства их ликвидации;

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

Классификация Кленси, в основу которой положены родовые операции, выполняемые в экспертных системах, выделены синтетические операции, результатом которых является изменение структуры системы, и аналитические операции, которые изучают свойства системы, не изменяя ее. Классификация этих операций представлена на схеме:

А нализ Синтез

идентификация проектирование

мониторинг конфигурирование

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

предсказание спецификация

управление сборка

Многоуровневый подход, порождает следующую классификацию экспертных систем: