Методы оптимизации

 

Разделим элементы строки 1 на 26/25.

 

базисные переменные	x1	x2	x3	x4	x5	x6	свободные члены	отношение
x4	0	0	1	25     26	25     26	- 20     13	5     13	5     13
x1	1	0	8     5	0	5     2	- 3     2	1	5     8
x2	0	1	- 1	0	- 5     2	5     2	0	-
L	0	0	- 2     5	0	0	1	1	-

 

От элементов строки 2 отнимает соответствующие элементы строки 1 умноженные на 8/5.

От элементов строки 3 отнимает соответствующие элементы строки 1 умноженные на -1.

От элементов строки L отнимает соответствующие элементы строки 1 умноженные на -2/5.

 

базисные переменные	x1	x2	x3	x4	x5	x6	свободные члены	отношение
x3	0	0	1	25     26	25     26	- 20     13	5     13	-
x1	1	0	0	- 20     13	25     26	25     26	5     13	-
x2	0	1	0	25     26	- 20     13	25     26	5     13	-
L	0	0	0	5     13	5     13	5     13	15     13	-

 

X ₃ = ( 5/13 , 5/13 , 5/13 , 0 , 0 , 0 )

Значение функции L для  данного решения: L (X 3) = 15/13

L =

15/13

-5/13 x4

-5/13 x5

-5/13 x6

Учитывая, что все x i 0 по условию задачи, наибольшее значение функции равно свободному члену 15/13.

x1 = 5/13

x2 = 5/13

x3 = 5/13

Учитывая правило формирования ответа симметричной двойственной задачи, запишем ее решение, на основании все той же последней симплекс таблицы.

y1 = 5/13

y2 = 5/13

y3 = 5/13

Максимальное значение функции прямой задачи равно минимальному значению функции двойственной задачи.

Lmax = 15/13 , Fmin = 15/13

Найдем цену игры v .

v = 1 / Fmax = 1 / Lmin = 13/15

Теперь, мы можем найти  оптимальное решение нашей игры.

p*1 = y1 * v = 5/13 * 13/15 = 1/3

p*2 = y2 * v = 5/13 * 13/15 = 1/3

p*3 = y3 * v = 5/13 * 13/15 = 1/3

q*1 = x1 * v = 5/13 * 13/15 = 1/3

q*2 = x2 * v = 5/13 * 13/15 = 1/3

q*3 = x3 * v = 5/13 * 13/15 = 1/3

Ответ :

P* = ( 1/3 , 1/3 , 1/3 )

Q* = ( 1/3 , 1/3 , 1/3 )

Цена игры v = 13/15.

Дадим объяснение полученному ответу.

Выигрыш игрока А составит 13/15

Проигрыш игрока В составит 13/15

Игрок А :

использует стратегию A1 на 33.3333333333333 %

использует стратегию A2 на 33.3333333333333 %

использует стратегию A3 на 33.3333333333333 %

Игрок B :

использует стратегию B1 на 33.3333333333333 %

использует стратегию B2 на 33.3333333333333 %

использует стратегию B3 на 33.3333333333333 %

 

 

2. Рассмотреть игру с матрицей потерь первого игрока . Ответьте на вопросы: а) есть ли цена в простой игре; если есть, то найдите оптимальные стратегии игроков; б) если цены нет, то составьте системы уравнений для нахождения решения этой игры;

Шаг:1

 

Определим нижнюю цену игры - α

Нижняя цена игры α — это максимальный выигрыш, который мы можем гарантировать себе, в игре против разумного противника, если на протяжении всей игры будем использовать одну и только одну стратегию (такая стратегия называется "чистой").

 

Найдем в каждой строке платежной матрицы минимальный элемент и запишем его в дополнительный столбец (Табл.1).

 

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

 

Таблица 1

 

 

	Стратегии "B"
Стратегии "A"	B1	B2	B3	B4	Минимумы строк
A1	2	0	0	-2	-2
A2	6	2	0	0	0*
A3	4	7	0	-1	-1
A4	0	7	-1	-2	-2

 

В нашем случае нижняя цена игры равна: α = 0, и для того чтобы гарантировать себе выигрыш не хуже чем 0 мы должны придерживаться стратегии A₂

 

Шаг:2

 

Определим верхнюю  цену игры - β

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

 

Найдем в каждом столбце  платежной матрицы максимальный элемент и запишем его в дополнительную строку снизу (Табл.2 ).

 

Затем найдем минимальный элемент дополнительной строки (в нашем случае таких элементов 2, - отмечены плюсами), это и будет верхняя цена игры.

 

Таблица 2

	Стратегии "B"
Стратегии "A"	B1	B2	B3	B4	Минимумы строк
A1	2	0	0	-2	-2
A2	6	2	0	0	0*
A3	4	7	0	-1	-1
A4	0	7	-1	-2	-2
Максимумы столбцов	6	7	0+	0+

 

 

В нашем случае верхняя  цена игры равна: β = 0, и для того чтобы гарантировать себе проигрыш не хуже чем 0 противник ( игрок "B") должен придерживаться одной из стратегий B₃ , B₄

 

 

Шаг:3

Сравним нижнюю и верхнюю  цены игры, в данной задаче они совпадают, т.е. α = β = 0 . Это значит, что игра имеет решение в так называемых "чистых", минимаксных стратегиях. Это как раз те стратегии для игроков "A" и "B" которые были найдены выше, при поиске нижней и верхней цен игры. То есть, в нашем случае для игрока "A" оптимальной будет стратегия A₂, а для игрока "В" - B₃. Нетрудно заметить, что элемент платежной матрицы расположенный на пересечении чистых оптимальных стратегий (строка 2, столбец 3) является одновременно минимальным в строке и максимальным в столбце (отмечен знаками *+ см. Табл.3). Такие элементы называются седловыми точками, именно их наличие и определяет существование решения игры в чистых стратегиях, а его значение (в нашем случае 0) совпадает с чистой ценой игры или просто ценой игры - v. Пара оптимальных стратегий, в играх имеющих седловую точку, всегда проходит через последнюю.