Решить задачу транспортную задачу ЛП

Задача 1. Найти решение игры:

1) в чистых стратегиях:

2) в смешанных стратегиях (графическим методом)

3), если платежная матрица задана в виде:

1) 2)

Решение.

1) Найдем нижнюю цену игры (Назовем нижней ценой игры или максимальным выигрышем (максимином). Это гарантированный выигрыш игрока А при любой стратегии игрока В):

Найдем верхнюю цену игры (назовем верхней ценой игры или минимаксом. Это минимальный гарантированный проигрыш игрока В):

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

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

Найдем верхнюю цену игры (назовем верхней ценой игры или минимаксом. Это минимальный гарантированный проигрыш игрока В):

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

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

Смешанной стратегией игрока А называется применение чистых стратегий А ₁, А ₂, …, А _m c вероятностями u ₁, u ₂, …, u _m.

Обычно смешанную стратегию первого игрока обозначают как вектор: U = (u ₁, u ₂, …, u _m), а стратегию второго игрока как вектор: Z = (z ₁, z ₂, …, z _m).

Очевидно, что:

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

Теорема Неймана. Каждая конечная игра с нулевой суммой имеет решение в смешанных стратегиях.

Пусть U^* = (, ,..., ) и Z^* = (, ,..., ) - пара оптимальных стратегий. Если чистая стратегия входит в оптимальную смешанную стратегию с вероятностью, отличной от нуля, то она называется активной.

Теорема об активных стратегиях. Если один из игроков придерживается своей оптимальной смешанной стратегии, то выигрыш остается неизменным и равным цене игры v, если второй игрок не выходит за пределы своих активных стратегий.

ЗАМЕЧАНИЕ. Эта теорема имеет большое практическое значение - она дает конкретные модели для нахождения оптимальных стратегий при отсутствии седловой точки.

Упростим платежную матрицу:

Исключим 4 - ую строку матрицы, так как ее элементы не превосходят элементы 2-ой строки (4 – ая доминируемая 2- ой). Получим

Столбцы 1 и 3 дублируют друг друга, исключим 3. Получим

Элементы 3 – его столбца в новой матрице не меньше элементов 1 - ого и 2 – ого столбцов, следовательно, он доминируем и мы его исключаем. Получим

.

Найдем координаты точки М (точка пересечения прямых A ₁ A ^'₁ и A ₃ A ^'₃).

Пусть

Прямая A ₁ A ^'₁ (проходит через точки с координатами ((0,7) и (1,6)):

Прямая A ₃ A ^'₃ (проходит через точки с координатами ((0,5) и (1,6)):

Решим систему

.

.

Зная, что М - точка пересечения прямых A ₁ A ^'₁ и A ₃ A ^'₃, можем найти оптимальную стратегию при помощи матрицы (). Для нахождения составим систему:

Решение задачи: .