Сделай Сам Свою Работу на 5

Теория игр. Сведение матрицы игры к задаче линейного программирования.





Метод теории игр –применении теории игр при принятии управленческих решений в условиях неопределенности. Наиболее часто игры применяют в экономике при выборе решения в условиях неопределенности в корпоративных ситуациях, где сталкиваются интересы двух и более сторон.

Когда неопределенность взятая из практики очень сложна и анализ ситуации в этом случае затруднен из-за наличия неопределенных факторов. Чтобы сделать возможным математический анализ ситуации, строится ее математическая модель, которая называется игрой. От реальной ситуации игра отличается тем, что ведется по определенным правилам, которые устанавливают права и обязанности участников, а так же исход игры, выигрыш или проигрыш участника.

Различают парные и множественные игры. Развитие игры во времени представляется как ряд последовательных ходов участников. Ходом называется выбор игроком одного из предусмотренных правилами игры, действий и его осуществления. Стратегия игрока – совокупность правил, определенный выбор варианта действий при каждом личном ходе в зависимости от сложившейся ситуации. Игры делятся на конечные и бесконечные, в зависимости от числа стратегий игры. У конечных игроков имеется ограниченное число стратегий. Задачей теории игр является выявление оптимальной стратегии игроков. Расчет ведется из условия разумного противника.



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

Рассмотрим игру двух лиц с нулевой суммой, заданную платежной матрицей

.Если платежная матрица не имеет седловой точки, т.е. a <b и , то решение игры представлено в смешанных стратегиях (x1, x2, ..., xm) и (y1, y2, ..., yn). Применение первым игроком оптимальной стратегии опт должно обеспечить ему при любых действиях второго игрока выигрыш не меньше цены игры. , .Рассмотрим задачу отыскания оптимальной стратегии игрока А, для которой имеют место ограничения



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

(1)

где , .(2)

По условию x1 + x2 + … +xm = 1. Разделим обе части этого равенства на v. .

Оптимальная стратегия (x1, x2, ..., xm) игрока А должна максимизировать величину v, следовательно, функция (3)

должна принимать минимальное значение.

Таким образом, получена задача линейного программирования: найти минимум целевой функции (3) при ограничениях (1), причем на переменные наложено условие неотрицательности (2). Решая ее, находим значения , и величину1/v, затем отыскиваются значения xi = vti.

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

, .

Рассмотрим задачу отыскания оптимальной стратегии игрока B, для которой имеют место ограничения

Преобразуем систему ограничений, разделив все члены неравенств на v.

(4)

Где , .(5)

По условию y1 + y2 + … +yn = 1. Разделим обе части этого равенства на v.

. Оптимальная стратегия (y1, y2, ..., yn) игрока В должна минимизировать величину v, следовательно, функция (6)

должна принимать максимальное значение.

Получена задача линейного программирования: найти максимум целевой функции (6) при ограничениях (4), причем на переменные наложено условие неотрицательности (5).

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



 

 








Не нашли, что искали? Воспользуйтесь поиском по сайту:



©2015 - 2024 stydopedia.ru Все материалы защищены законодательством РФ.