- •Лекции по дисциплине
- •Основные этапы операционного исследования
- •Глава 1. Задачи линейного программирования
- •Возможные случаи допустимого множества решений задачи линейного программирования
- •Возможные случаи оптимальных решений (планов) задачи линейного программирования.
- •Графоаналитический способ решения задач линейного программирования
- •Симплекс-метод
- •Алгоритм симплекс-метода
- •1.5. Метод искусственного базиса (м-метод)
- •Алгоритм м-метода:
- •1.6. Элементы теории двойственности
- •Основная теорема двойственности
- •Вторая теорема двойственности
- •Глава 2. Элементы матричных игр
- •2.1. Формальное представление игр. Понятие матричной игры
- •2.2. Принцип миинимакса решения матричных игр.
- •2.3. Смешанные стратегии. Основные свойства решений в смешанных стратегиях.
- •2.4. Методы решения матричных игр.
- •Упрощение игр с помощью отбрасывания доминируемых стратегий.
- •3. Графический метод решения игр 2хn и mх2.
- •Метод сведения матричной игры к задаче линейного программирования.
- •4.5. Итерационный метод Брауна – Робинсон.
- •2.5. Игры с природой.
- •Список рекомендуемой литературы.
Метод сведения матричной игры к задаче линейного программирования.
Рассмотрим универсальный метод решения матричных игр, позволяющий в принципе исследовать игру любой размерности.
Пусть имеется игра mхn без седловой точки и без доминируемых стратегий, заданная матрицей
.
Априорно допустим, что цена этой игры положительна. Это значение заранее неизвестно, но, согласно свойству 2 из п.2.2, vS, где - нижняя цена игры. Так что при 0 условие vS0 выполнено. Если же 0, то выполнение такого условия можно гарантировать, прибавив, например, ко всем элементам матрицы Н число с и получив матрицу Н новой игры. Согласно свойству 1 из п. 2.2, новая игра имеет то же самое решение, что и исходная игра, а ее цена vS'=vS+c.
Итак, пусть vS0. Мы хотим найти две оптимальные смешанные стратегии SA*=(р1,…,рm) и SB*=(р1,…,рn), дающие каждому игроку максимально возможные для него средние выигрыши. Найдем SA*. Уже известно, что, если игрок А применяет свою оптимальную стратегию, то игрок В не может улучшить свое положение, отступая от своей оптимальной стратегии: H(SA*,SB)H(SA*,SB*)=vS для всех SB (проигрыш В будет не меньше, чем vS). В частности, если игрок В пользуется какой-либо чистой стратегией Вj, то:
H(SA*,Bj)=a1jp1+…+amjpmvS при всех j=1,…,n.
Получим следующую систему неравенств:
(2.8)
Так как vS0, то при почленном делении левых и правых частей неравенств (2.8) на vS знаки неравенств не изменятся. Вводя, кроме того, обозначения xj=pj/vS, перепишем систему (2.8) в виде:
(2.9)
Условие р1+р2+…+рm=1 равносильно условию x1+x2+…+xm=1/vS.
Но vS – гарантированный выигрыш игрока А. Целью игрока А в игре является максимизация этого значения и, следовательно, минимизация выражения 1/vS. Получили следующую задачу линейного программирования:
Найти неотрицательные значения x1, x2,…, xm, которые удовлетворяют линейным ограничениям – неравенствам (2.9) и обращают в минимум целевую функцию L=x1+x2+…+xm.
Полученная задача может быть решена, например, симплекс-методом. Пусть (x1*,x2*,…,xm*) - некоторое решение этой задачи, L* - минимальное значение целевой функции L . Тогда цена игры vS=1/L*, а компоненты оптимальной стратегии игрока А равны: pj*=xj*/L* (j=1,…,m).
Оптимальная стратегия игрока В находится аналогично. В результате приходим к задаче линейного программирования, двойственной к первой:
y1+y2+…+yn max
(2.10)
Решение (y1*,y2*,…,yn*) этой задачи и компоненты q1*,q2*,…,qn* оптимальной стратегии игрока В связаны соотношениями: qi*=yi*/L*, где L* - максимальное значение целевой функции задачи (2.10), совпадающее с минимальным значением предыдущей задачи.
Пример 2.7. Найти решение игры, заданной матрицей
.
Во-первых, заметим, что данная игра не имеет доминируемых стратегий, так что сокращение размерности матрицы невозможно. Далее проверим, не имеет ли матрица седловую точку. Найдем нижнюю и верхнюю цены игры:
, . Так как , то седловая точка отсутствует. Приступаем к поиску решения игры в смешанных стратегиях, используя метод сведения игры к задаче линейного программирования.
Прибавим ко всем элементам матрицы Н модуль ее наименьшего отрицательного элемента, т. е. 2. Получим матрицу
,
которая задает игру с заведомо положительной ценой vS. Для нахождения оптимальной смешанной стратегии игрока А составим следующую задачу линейного программирования:
L =x1+x2+x3 min
(2.11)
Для нахождения оптимальной стратегии игрока В составим двойственную задачу:
L1=y1+y2+y3 max
(2.12)
Симплекс-методом удобнее решать задачу (2.12). Опуская процесс расчетов этим методом, запишем лишь результат: у1*=1/4, у2*=5/4, у3*=0 – решение задачи (2.12), максимальное значение целевой функции L1*=3/2. Отсюда находим компоненты оптимальной смешанной стратегии игрока В: q1*=(1/4):(3/2)=1/6, q2*=(5/4):(3/2)=5/6, q3*=0; цена игры vS=1/L1*. При решении задачи линейного программирования симплекс-методом в итоговой симплекс-таблице содержится также и решение двойственной задачи, в нашем случае - задачи (2.11): х1*=0, х2*=1/2, х3*=1. Учитывая, что L*=L1*, отсюда получим: p1*=0:(3/2)=0, p2*=(1/2):(3/2)=1/3, p3*=1:(3/2)=2/3. Согласно свойству 1 решения матричных игр (п.2.3), оптимальные смешанные стратегии исходной игры совпадают с найденными оптимальными стратегиями: SA*=(0,1/3,2/3), SB*=(1/6,5/6,0). Цена vS исходной игры и найденная цена vS вспомогательной игры связаны соотношением vS=vS+2. Поэтому vS=2/32=4/3.