Лекция: Игры. Методы решения игр.

Теория игр — математический метод изучения оптимальных стратегий в усл. неопредел. Под игрой понимается проц-с, в кот-ом участвуют две и более сторон, ведущих борьбу за реализацию своих интересов. Каждая из сторон имеет свою цель и использует некоторую стратегию, которая может вести к выигрышу или проигрышу — в зависимости от поведения других игроков. Теория игр помогает выбрать лучшие стратегии с учётом представлений о других участниках, их ресурсах и их возможных поступках. Чаще всего методы теории игр находят применение в экономике, социологии, политологии, психологии. Очень важное значение она имеет для искусственного интеллекта и кибернетики, особенно с проявлением интереса к интеллектуальным агентам.

Примеры Простейшим примером игры является игра «Орлянка». Первый игрок прячет монету орлом или решкой вверх, а второй пытается угадать, как она спрятана. Если он не угадывает — он платит первому одну денежную единицу, если угадывает — первый платит ему одну денежную единицу.

Матричной игрой называется игра, осуществляемая по следующим правилам:

1.В игре участвуют два игрока;

2.Каждый из игроков обладает конечным набором стратегий;

3.Игра заключается в том, что каждый из игроков, не имея информации о действиях противника, делает один ход (выбирает одну из своих стратегий). Результатом выбора игроками стратегий является выигрыш и проигрыш в игре.

4. И выигрыш, и проигрыш выражаются числами.

Матричная игра называется игрой с нулевой суммой (или антагонистической) , если в этой игре выигрыш одного игрока равняется проигрышу другого игрока.

Решить игру значит найти опт. стратег и выйгрыш кажд игрока.Стратег оптимтимальна если 1) один игрок получит мах выйгрыш, когда 2-ой придерживается своей стратегии 2) 2-й игрок должен получить мин проигрыш, когда 1-й придерж свой стратег. Первый игрок имеет m стратегий, второй n. c11, C12..c1n и т.д. — выигрышы игрока A (и проигрышы игрока B) при применении игроками стратегий Ai и Bj соответственно. Матрица C называется платежной матрицей игры.

Методы решения игр: принцип минимакса.

Пример. В каждой строке платежной матрицы найдем наименьший элемент, и запишем его справа от матрицы. В каждом столбце платежной матрицы найдем наибольший элемент, и запишем его снизу от матрицы.

Нижняя цена игры 2 Верхняя цена игры 4

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

Графический метод решения игры

Сведение к задаче линейного программирования: Пример. Найти решение игры, определяемой матрицей.

Решение.

Составим пару взаимно-двойственных задач :

Решается графически или симплекс-методом или другими.

20 Решение нелинейного уравнения с одной переменной: постановка задачи, отделение корней (графический и аналитический способы) и уточнение корней с заданной степенью точности (метод хорд).

Постановка задачи: пусть дано уравнение f(x)=0 (1), ф-я f(x) опре-на и непре-на в некотором конечном или б/конечном интервале от A до B и x-изолированный корень. Требуется найти приближ-е зн-е корня с точностью до e (e>0). Корень xназ изолированным, если для него существ-ет окре-ть, не содржащая никаких др корней. Вычисление выполн в 2 этапа: 1.Отделение. Отделить корни ур-я f(x)=0 на [A,B]ÍДf (Дf-область определения) это значит, найти такие промежутки [a,b], в каждом из кото-х содер-я только один корень данного ур-я. Для этого использ теорему: Если ф-я y=f(x) непрерывны на[a,b], f(a)*f(b)<0, f’(x) на (a,b) сохраняет знак, то внутри отрезка [a,b] сущ единственный корень. Графиче-й метод. 1)Для определения корней в с.к. XOY строим график ф-иy=f(x). Абсциссы с точкой пересечения графика оси OX- корни ур-я. Прочитать значения корней с хорошей точностью в большинстве случаев затруднено, но выделить промежутки [ai,bi], в каждом из которых лежит один корень, достаточно просто их выписать x1Î[a1,b1], x2Î[a2,b2] и т.д. 2)когда ф-я f(x) достаточно сложная. Ур-еf(x)=0 приводим к виду f1(x)= f2(x) и в с.к. XOY строим графики ф-й y=f1(x) и y=f2(x). Абсциссы точек пересечения построенных графиков, и есть корни ур-я. Выделяем также промежутки как и в1 случае. Аналитический метод. Для отделения нужно знать: 1)если ф-я y=f(x) – непрерывна на [a,b] и f(a)*f(b)<0, то внутри отрезка [a,b] сущест-ет по крайней мере хотя бы один корень. 2)если ф-я y=f(x) – непрерывна на [a,b] и f(a)*f(b)<0 и производная f’(x) на (a,b) сохраняет знак, то внутри отрезка [a,b] сущест-ет единственный корень. Пусть треб-тся отделить корни ур-я f(x)=0. Найдем область определения ф-иf(x) или такой, достаточно большой промежуток [A,B]ÍДf, на котором требуется отделить действи-ые корни. Выберем достаточно малый шаг h (0,1) и разобьем промежуток [A,B] на промежутки [A,A+h], [A+h, A+2h] …., т.е. на [A+kh, A+(k+1)h], где к=0,1,2… и (A+(k+1)h)£B. На концах каждого из промежутков найдем знаки ф-иf(x). Если окажется, что f(A+kh)*f(A+(k+1)h)<0, то при достаточно малом шаге h с большой точностью вероятности можно утверждать, что на промежутке [A+kh, A+(k+1)h] лежит только один корень. 2.Уточнение корней. Пусть дано ур-е f(x)=0 требуется вычислить один из его действит-х корней x с точностью e. Надо найти приближ зн-е такое, что x=xn±e. Задача отыскания придлиж зн-я корня с точностью доe сводится к нахождению такого [a,b], длина кот-го будет |b-a|<e. Метод деления пополам.

Пусть уравнение (1) имеет на отрезке [ a,b] единственный корень, причем функция F(x) на этом отрезке непрерывна. Разделим отрезок [ a,b] пополам точкой c= ( a+b)/2. Если F(с)¹0, (что практически наиболее вероятно), то возможно 2 случая: либо F(x) меняет знак на отрезке [ a, с]

либо на отрезке [ с,b]

Выбирая в каждом случае тот из отрезков, на котором функция меняет знак, и продолжая процесс половинного деления дальше, можно дойти до сколь угодно малого отрезка, содержащего корень уравнения. Рассмотренный метод можно использовать как метод решения уравнения с заданной точностью. Действительно. если на каком–то этапе процесса получен отрезок [a,b], содержащий корень, то, приняв приближенно x= (a+b)/2, получим ошибку, непревышающую значения D= (b-a)/2. Метод связан с трудоемкими вычислениями, однако он с успехом может использоваться на ЭВМ. Изобразим схему алгоритма уточнения одного корня уравнения (1) на отрезке [ a,b], до заданной точности e методом половинного деления. Из схемы видно, что даже если на каком–то этапе F(c)=0, это не приведет к сбою алгоритма.

Метод хорд (секущих)

F(x)=0 (1) x*Î[a,b]

отделение корня произошло и кореньÎ[a,b]. F(a)F(b)<0

y= F(x)

b,F(b)

a x’ b

a,F(a) x*

Вместо кривой рассмотрим секущую

{xn}¥n®0

y= F(a)+ (x-a) (2)

вместо (1) рассмотрим (2)

F(a)+ (x-a) =0