Оптимальное решение игры двух лиц с нулевой суммой

Описание сетевой модели с помощью кодирования работ

Номера событий		Код работы	Продолжительность работы
начального	конечного
1	2	(1,2)	6
1	3	(1,3)	5
1	7	(1,7)	16
2	4	(2,4)	9
3	5	(3,5)	10
4	6	(4,6)	12
5	6	(5,6)	11
5	7	(5,7)	3
6	7	(6,7)	14
7	8	(7,8)	15

 

                                         A                     F

                                          9                    12

             C    

               6                                                      I

                 D                    B                          11

                 5                     10                        J    14 G

                                                     E                  3                   H

                                                  16                                               15

 

Рис.1 Сетевая модель

 

Таблица 2

Временные параметры работ

(i,j)	t (i,j)	TPH (i,j)	TPO (i,j)	TПН (i,j)	TПО (i,j)	RП (i,j)	RC (i,j)
(1,2)	6	0	6	0	6	0	0
(1,3)	5	0	5	1	6	1	0
(1,7)	16	0	16	25	41	25	0
(2,4)	9	6	15	6	15	0	0
(3,5)	10	5	15	6	16	1	1
(4,6)	12	15	27	15	27	0	0
(5,6)	11	15	26	16	27	1	1
(5,7)	3	15	18	38	41	23	23
(6,7)	14	27	41	27	41	0	0
(7,8)	15	41	56	41	56	0	0

Исходные данные для оптимизации загрузки

 

Таблица 3

Код работ	Продолжительность работ	Количество исполнителей
(1,2)	6	6
(1,3)	5	4
(1,7)	16	5
(2,4)	9	8
(3,5)	10	3
(4,6)	12	2
(5,6)	11	5
(5,7)	3	7
(6,7)	14	1
(7,8)	15	3

 

Допустим, что организация, выполняющая проект, имеет в распоряжении только N = 11 исполнителей. Но в соответствии с графиком загрузки (рис.2), в течение интервала времени с 3 по 16 день для выполнения проекта требуется работа одновременно 41, 39 и затем 40 человек. Таким образом, возникает необходимость снижения максимального количества одновременно занятых исполнителей с 41 до 15 человек.

Проанализируем возможность уменьшения загрузки (41 человек) в течение 5 дня. Используя Rc (5,6) = 5, сдвинем работу (5,7) на 1 день, что снизит загрузку 5-го дня до 2 человек, но при этом в 11 день появится пик - 42 исполнителя. Для его устранения достаточно сдвинуть работу (6,7) на 1 день, используя Rc (6,7) = 1.

                                                                                             

        15                                                                              16

                  14                         12

                                      11                   10            

                                                                                  9

 

                            3                                                                                    6

                

                                                                                                                         

7,8                                                                                                                 3

6,7                                                                                               1

5,7                                                                      7

5,6                                                                         5

4,6                                                                          2

3,5                                         3

2,4                                          8

1,7               5

1,3            4

1,2            6

Рис.2 Графики загрузки (а) и привязки (b) до оптимизации.

 

Проанализируем возможность уменьшения загрузки (38 человек) с 7-го по 12 день, т.е. в течение интервала времени в 6 дней. Так работа (2,4) является единственной, которую можно сдвинуть таким образом, чтобы она не выполнялась в указанные 6 дней с 7-го по 12 день. Для этого, используя Rп (2,4) = 8, сдвинем работу T_у (i,j) на 4 дня, после чего она будет начинаться уже не в 6-й, а в 10 день, к чему мы и стремились. Но поскольку Rс (2,4) = 0 и для сдвига работы T_н (i,j) был использован полный резерв, то это влечет за собой обязательный сдвиг на 7 дней работы (6,7), следующей за работой (2,4).

В результате произведенных сдвигов максимальная загрузка сетевой модели уменьшилась с 41 до 15 человек, что и являлось целью проводимой оптимизации. Окончательные изменения в графиках привязки и загрузки показаны на рис.3 пунктирной линией.

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

                                                                                                 

                 15                                                     16

       14                     12

                                                     11    10        

                                                                                               9

 

                            3                                                                                    6

                                                                                                                         

7,8                                                                                                                 3

6,7                                                                                                                      1

5,7                                                                      7

5,6                                                                                                      5

4,6                                                                          2

3,5                                         3

2,4                                                                       8

1,7               5

1,3            4

1,2            6

 

Рис.3 Графики загрузки (а) и привязки (b) после оптимизации.

 

Оптимальное решение игры двух лиц с нулевой суммой

 

Определите оптимальные стратегии и цену игры. Для 1) - в чистых стратегиях, для 2) - в смешанных.

 

1)  2)

Таблица 5

	B1	B2	B3	B4
A1	1	3	4	1	1
A2	5	6	9	1	1
A3	2	8	4	3	2
	5	8	9	3

 

Решение

Все расчеты удобно проводить в таблице, к которой, кроме матрицы Р, введены столбец  и строка  (табл.1). Анализируя строки матрицы (стратегии игрока А), заполняем столбец : а₁ = 1; а₂ = 1; а₃ = 2 - минимальные числа в строках 1, 2,3. Аналогично  = 5; = 8;  = 9;  = 3 - максимальные числа в столбцах 1, 2, 3 соответственно. Нижняя цена игры ,  (1; 1;

2) = 2 (наибольшее число в столбце ) и верхняя цена игры ,  (5; 8; 9;

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

 

 

Средний выигрыш игрока А, если он использует оптимальную смешанную стратегию

,

 

а игрок В чистую стратегию В₁ (это соответствует первому столбцу платежной матрицы Р), равен цене игры v:

 

 

Тот же средний выигрыш получает игрок А, если 2-й игрок применяет стратегию В₂, т.е.

 

.

 

Учитывая, что  получаем систему уравнений для определения оптимальной стратегии S*_A и цены игры v:

 

 

Решая эту систему, получим оптимальную стратегию

 

 

и цену игры

 

Применяя теорему об активных стратегиях при отыскании  - оптимальной стратегии игрока В, получаем, что при любой чистой стратегии игрока А (А₁ или А₂) средний проигрыш игрока В равен цене игры v, т.е.

 

 

Тогда оптимальная стратегия  ( ) определяется формулами:

 

 

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

 

 

Поэтому ищем решение в смешанных стратегиях: для игрока А средний выигрыш равен цене игры v (при В₁ и В₂) для игрока В средний проигрыш равен цене игры v (при А₁ и А₂). Системы уравнений приведенные выше в данном случае имеют вид:

 

Решая эти системы, получаем  v = 0.

Это означает, что оптимальная стратегия каждого игрока состоит в том, чтобы чередовать свои чистые стратегии случайным образом, выбирая каждое из убежищ с вероятностью -3 и 4 при этом средний выигрыш равен 0.

Оптимальное решение игры двух лиц с нулевой суммой.

Определите оптимальные стратегии и цену игры. Для 1) - в чистых стратегиях, для 2) - в смешанных.

 

1)  2)

 

Таблица 5

	B1	B2	B3	B4
A1	2	3	4	2	2
A2	3	5	2	4	2
A3	2	5	4	6	2
	3	5	4	6

 

Решение.

Все расчеты удобно проводить в таблице, к которой, кроме матрицы Р, введены столбец  и строка  (табл.1). Анализируя строки матрицы (стратегии игрока А), заполняем столбец : а₁ = 2; а₂ = 2; а₃ = 2 - минимальные числа в строках 1, 2,3. Аналогично  = 3; = 5;  = 4;  = 6 - максимальные числа в столбцах 1, 2, 3 соответственно. Нижняя цена игры ,  (2; 2;

2) = 2 (наибольшее число в столбце ) и верхняя цена игры ,  (3; 5; 4;

6) = 3 (наименьшее число в строке ). Эти значения не равны, т.е. , и, так как они достигаются ни на одной и той же паре стратегий, то игра седловой точки не имеет.

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

Пусть игра задана платежной матрицей

 

 

Средний выигрыш игрока А, если он использует оптимальную смешанную стратегию

 

,

 

а игрок В чистую стратегию В₁ (это соответствует первому столбцу платежной матрицы Р), равен цене игры v:

 

 

Тот же средний выигрыш получает игрок А, если 2-й игрок применяет стратегию В₂, т.е.

.

 

Учитывая, что  получаем систему уравнений для определения оптимальной стратегии S*_A и цены игры v:

 

 

Решая эту систему, получим оптимальную стратегию

 

 

и цену игры

 

 

Применяя теорему об активных стратегиях при отыскании  - оптимальной стратегии игрока В, получаем, что при любой чистой стратегии игрока А (А₁ или А₂) средний проигрыш игрока В равен цене игры v, т.е.

 

Тогда оптимальная стратегия  ( ) определяется формулами:

 

 

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

Игра задана платежной матрицей без седловой точки:

 

 

Поэтому ищем решение в смешанных стратегиях: для игрока А средний выигрыш равен цене игры v (при В₁ и В₂) для игрока В средний проигрыш равен цене игры v (при А₁ и А₂). Системы уравнений приведенные выше в данном случае имеют вид:

 

 

Решая эти системы, получаем  v = 0.

Это означает, что оптимальная стратегия каждого игрока состоит в том, чтобы чередовать свои чистые стратегии случайным образом, выбирая каждое из убежищ с вероятностью -1 и 2 при этом средний выигрыш равен 0.