Пусть имеется игра G (3´4), представленная в матричном виде (табл. 7.1).
После ввода матрицы, выбора метода решения (метода Лагранжа) и активизации процедуры поиска решения главное окно системы будет иметь вид, представленный на рис. 7.3.
Таблица 7.1
Bj Ai | B 1 | B 2 | B 3 |
A 1 | 7 | 2 | 9 |
A 2 | 2 | 9 | 0 |
A 3 | 9 | 0 | 11 |
Рис. 7.3. Вид главного окна с полученными результатами
Ход решения и полученные результаты отображены в окне Процесс поиска решения:
Поиск решения методом Лагранжа.
Поиск и удаление доминируемых и дублируемых стратегий.
Поиск седловой точки:
Седловая точка не найдена.
Поиск решения в смешанных стратегиях.
Методом Лагранжа найдено решение в смешанных стратегиях:
p = (0,250000; 0,500000; 0,250000)
q = (0,250000; 0,500000; 0,250000)
Цена игры: V = 5,000000.
В случае выбора для решения симплекс-метода окно Процесс поиска решения примет следующий вид:
Поиск решения симплекс-методом.
Поиск седловой точки:
Седловая точка не найдена.
Поиск решения в смешанных стратегиях.
Симплекс-методом найдено решение в смешанных стратегиях:
p = (0,250000; 0,500000; 0,250000)
q = (0,250000; 0,500000; 0,250000)
Цена игры V = 5,000000.
В случае выбора для решения итерационного метода Брауна-Робинсона окно Процесс поиска решения примет следующий вид:
Поиск решения методом Брауна-Робинсона.
Поиск седловой точки:
Седловая точка не найдена.
Поиск решения в смешанных стратегиях…
Методом Брауна-Робинсона найдено решение в смешанных стратегиях:
p = (0,249000; 0,500000; 0,251000)
q = (0,249000; 0,500000; 0,251000)
Цена игры V = 5,000000.
Результаты последних итераций в табличном виде будут представлены в специальном окне (рис. 7.4).
Рис. 7.4. Окно с результатами последних итераций
Рассмотрим еще один пример для игры G (5´5)при наличии дублируемых и доминируемых стратегий. Вид главного окна с полученными результатами при использовании метода Лагранжа представлен на рис. 7.5.
Рис. 7.5. Вид главного окна с полученными результатами для метода Лагранжа
В окне Процесс поиска решения будет выведена следующая информация:
Поиск решения методом Лагранжа.
Поиск и удаление доминируемых и дублируемых стратегий:
Стратегия В1 доминирует над стратегией B 2!
Стратегия В1 доминирует над стратегией B 5!
Стратегия В3 доминирует над стратегией B 4!
Стратегия В3 доминирует над стратегией B 5!
Стратегия В4 доминирует над стратегией B 5!
Удаление стратегии B 2!
Удаление стратегии B 5!
Удаление стратегии B 4!
Стратегия A 1 дублирует стратегию A 3!
Стратегия A 1 доминирует над стратегией A 4!
Стратегия A 2 доминирует над стратегией A 4!
Стратегия A 2 дублирует стратегию A 5!
Стратегия A 3 доминирует над стратегией A 4!
Стратегия A 5 доминирует над стратегией A 4!
Удаление стратегии A 3!
Удаление стратегии A 4!
Удаление стратегии A 5!
Поиск седловой точки:
Седловая точка не найдена.
Поиск решения в смешанных стратегиях.
Методом Лагранжа найдено решение в смешанных стратегиях:
Sa = (0,600000; 0,400000; 0,000000; 0,000000; 0,000000)
Sb = (0,800000; 0,000000; 0,200000; 0,000000; 0,000000)
Цена игры: V = 3,599999.
При использовании симплекс метода соответственно получим:
Поиск решения симплекс-методом.
Поиск седловой точки:
Седловая точка не найдена.
Поиск решения в смешанных стратегиях.
Симплекс методом найдено решение в смешанных стратегиях:
Sa = (0,600000; 0,400000; 0,000000; 0,000000; 0,000000)
Sb = (0,800000; 0,000000; 0,200000; 0,000000; 0,000000)
Цена игры V = 3,599999.
При использовании метода Брауна-Робинсона будет выдана следующая информация:
Поиск решения методом Брауна-Робинсона.
Поиск и удаление доминируемых и дублирующих стратегий:
Стратегия В1 доминирует над стратегией B 2!
Стратегия В1 доминирует над стратегией B 5!
Стратегия В3 доминирует над стратегией B 4!
Стратегия В3 доминирует над стратегией B 5!
Стратегия В4 доминирует над стратегией B 5!
Удаление стратегии B 2!
Удаление стратегии B 5!
Удаление стратегии B 4!
Стратегия A 1 дублирует стратегию A 3!
Стратегия A 1 доминирует над стратегией A 4!
Стратегия A 2 доминирует над стратегией A 4!
Стратегия A 2 дублирует стратегию A 5!
Стратегия A 3 доминирует над стратегией A 4!
Стратегия A 5 доминирует над стратегией A 4!
Удаление стратегии A 3!
Удаление стратегии A 4!
Удаление стратегии A 5!
Поиск седловой точки:
Седловая точка не найдена.
Поиск решения в смешанных стратегиях.
Методом Брауна-Робинсона найдено решение в смешанных стратегиях:
Sa = (0,600000; 0,400000; 0,000000; 0,000000; 0,000000)
Sb = (0,800000; 0,000000; 0,200000; 0,000000; 0,000000)
Цена игры V = 3,599500.
Фрагмент таблица значений для последних 100 итераций представлен на рис. 7.6.
Рис. 7.6. Окно с результатами последних итераций
Практический пример
Снова вернемся к уже рассмотренной ранее (см. п. 3.4) задаче о конкурсе на реализацию двух проектов при участии конструкторских бюро КБ1 и КБ2. Напомним, что у КБ1 (игрока A) имеется 5 стратегий: A 1=(4; 0), A 2=(3; 1), A 3=(2; 2), A 4=(1; 3), A 5=(0; 4); у КБ2 (игрока B) – 4 стратегии: B 1=(3; 0), B 2=(2; 1), B 3=(1; 2), B 4=(0; 3).
Пусть a =16, b =2(т.е. финансированиепервого проекта существенно превосходит финансирование второго проекта).
После приведения данной игры G (5´4)к антагонистической посредством вычитания из выигрышей игрока A средней величины финансирования обоих проектов (a + b) / 2=9, получим ее матричное представление в виде табл. 7.2.
Таблица 7.2
Bj Ai | B 1 | B 2 | B 3 | B 4 |
A 1 | 8 | 7 | 7 | 7 |
A 2 | 1 | 8 | 7 | 7 |
A 3 | –7 | 1 | 8 | 7 |
A 4 | –7 | –7 | 1 | 8 |
A 5 | –7 | –7 | –7 | 1 |
Далее, после проверки на отсутствие седловой точки и упрощения матрицы игры путем удаления доминируемой стратегии A 5, получим игру G (4´4), представленную табл.7.3.
Таблица 7.3
Bj Ai | B 1 | B 2 | B 3 | B 4 |
A 1 | 8 | 7 | 7 | 7 |
A 2 | 1 | 8 | 7 | 7 |
A 3 | –7 | 1 | 8 | 7 |
A 4 | –7 | –7 | 1 | 8 |
В табл. 7.4 приведены результаты, полученные программной системой MatrixGames при использовании приближенного метода Брауна-Робинсона (при задании различного числа итераций) и точного метода Лагранжа (последняя строка таблицы) с округлением результата до трех знаков после запятой.
Из таблицы видно, что некоторая стабилизация для итерационного метода (особенно относительно величины V *) наступает при числе итераций более 10000.
Таблица 7.4
Число итераций | V* | ||||||||
100 | 0.99 | 0.01 | 0 | 0 | 0.06 | 0.03 | 0.93 | 0 | 7.03 |
200 | 0,885 | 0,110 | 0,005 | 0 | 0,045 | 0,240 | 0,485 | 0,230 | 7,027 |
500 | 0,954 | 0,044 | 0,002 | 0 | 0,018 | 0,096 | 0,194 | 0,692 | 7,009 |
1000 | 0,977 | 0,022 | 0,001 | 0 | 0,009 | 0,048 | 0,097 | 0,846 | 7,006 |
3000 | 0,905 | 0,089 | 0,006 | 0,003 | 0,003 | 0,023 | 0,175 | 0,798 | 7,002 |
10000 | 0,895 | 0,093 | 0,013 | 0,001 | 0,004 | 0,023 | 0,180 | 0,793 | 7,003 |
100000 | 0,879 | 0,107 | 0,013 | 0,002 | 0,002 | 0,014 | 0,111 | 0,873 | 7,002 |
1000000 | 0,876 | 0,109 | 0,013 | 0,002 | 0,002 | 0,013 | 0,110 | 0,875 | 7,002 |
Точный метод | 0,875 | 0,110 | 0,013 | 0,002 | 0,002 | 0,013 | 0,110 | 0,875 | 7,002 |
Вернёмся теперь к исходной задаче. Вычеркнутая стратегия A 5 будет присутствовать в итоговом результате с вероятностью 0:
SA *=(0,875;0,110;0,013;0,002;0);
SB *=(0,002;0,013;0,110;0,875);
V* =7,002.
Если теперь вернуться к начальной ситуации с возможным финансированием КБ1 и КБ2 и округлить результаты, то получим:
SA =(0,9;0,1;0,0;0,0;0,0);
SB =(0,0;0,0;0,1;0,9);
VA =16,0;
VB = 2,0,
Таким образом, КБ1 рекомендуется все усилия направить на выполнение первого проекта, возможно, выделив один отдел на выполнение второго проекта, а КБ2 – наоборот, все усилия направить на выполнение второго проекта, возможно, выделив один отдел на выполнение первого.