Навигация
Сведение задач теории игр к задачам линейного
31578
знаков
23
таблицы
14
изображений
4. Сведение задач теории игр к задачам линейного
программирования
Предположим, что цена игры положительна (u > 0). Если это не так, то согласно свойству 6 всегда можно подобрать такое число с, прибавление которого ко всем элементам матрицы выигрышей даёт матрицу с положительными элементами, и следовательно, с положительным значением цены игры. При этом оптимальные смешанные стратегии обоих игроков не изменяются.
Свойство 1. Тройка (хо, yо, u) является решением игры G = (Х,Y,А) тогда и только тогда, когда (хо, yо, кu +а) является решением игры G(Х,Y,кА+а), где а – любое вещественное число, к > 0.
Свойство 2. Для того, чтобы хо = (
) была оптимальной смешанной стратегией матричной игры с матрицей А и ценой игры u, необходимо и достаточно выполнение следующих неравенств
(j = 
) 
Аналогично для игрока 2 : чтобы yо = (
, ...,
, ...,
) была оптимальной смешанной стратегией игрока 2 необходимо и достаточно выполнение следующих неравенств:
(i = 
) 
Из последнего свойства вытекает: чтобы установить, является ли предполагаемые (х, y) и u решением матричной игры, достаточно проверить, удовлетворяют ли они неравенствам (*) и (**). С другой стороны, найдя неотрицательные решения неравенств (*) и (**) совместно со следующими уравнениями
, 
получим решение матричной игры.
Итак, пусть дана матричная игра с матрицей А порядка m х n. Согласно свойству 7 оптимальные смешанные стратегии х = (х1, ..., хm), y = (y1, ..., yn) соответственно игроков 1 и 2 и цена игры u должны удовлетворять соотношениям.
Разделим все уравнения и неравенства в (4.4) и (4.5) на u (это можно сделать, т.к. по предположению u > 0) и введём обозначения:
, 
,
Тогда (1) и (2) перепишется в виде:
, 
, 
, ,
, 
, 
, .
Поскольку первый игрок стремится найти такие значения хi и, следовательно, pi , чтобы цена игры u была максимальной, то решение первой задачи сводится к нахождению таких неотрицательных значений pi , при которых
, . 
Поскольку второй игрок стремится найти такие значения yj и, следовательно, qj, чтобы цена игры u была наименьшей, то решение второй задачи сводится к нахождению таких неотрицательных значений qj, , при которых
, . 
Формулы (3) и (4) выражают двойственные друг другу задачи линейного программирования (ЛП).
Решив эти задачи, получим значения pi , qj и u.Тогда смешанные стратегии, т.е. xi и yj получаются по формулам:
Похожие работы
... систем стимулирования. Она полезна также для формирования и развития внутрифирменных культур. Важный вклад в использование теории игр вносят экспериментальные работы. Многие теоретические выкладки отрабатываются в лабораторных условиях, а полученные результаты служат импульсом для практиков. Теоретически было выяснено, при каких условиях двум эгоистически настроенным партнерам целесообразно ...
... общую цель. Однако разные члены коллектива могут быть по-разному информированы об обстановке проведения игры. Выигрыш или проигрыш сторон оценивается численно, другие случаи в теории игр не рассматриваются, хотя не всякий выигрыш в действительности можно оценить количественно. Игрок - одна из сторон в игровой ситуации. Стратегия игрока - его правила действия в каждой из возможных ситуаций игры. ...
... запасов сырья, материалов, полуфабрикатов, когда противоборствуют две тенденции: увеличение запасов, гарантирующих бесперебойную работу производства, сокращения запасов в целях минимизации затрат на их хранение. В сельском хозяйстве теория игр может применяться при решении таких экономических задач, как посева одной из возможных культур, урожай которой зависит от погоды, если известны цена единицы ...
... , находящихся в обслуживающей системе, обслуживаемых и ожидающих обслуживания: или 8.Среднее число свободных обслуживающих каналов . 9.Коэффициент простоя обслуживающего канала: II. Практическое применение теории игр в задачах моделирования экономических процессах Пример №1 На базе торговой фирмы имеется n типов товара ассортиментного минимума. В магазин фирмы должен ...
0 комментариев