Линейное программирование (стр. 3 из 8)
● дескриптивные (описательные) модели;
● оптимизационные модели;
●многокритериальные модели;
●игровые модели.
Рис. (1).Блок схема математического моделирования.
2.1 Элементы теории матричных игр
СВЕДЕНИЕ МАТРИЧНОЙ ИГРЫ К ЗАДАЧЕ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
Предположим, что цена игры положительна (u> 0). Если это не так, то согласно свойству 6 всегда можно подобрать такое число с, прибавление которого ко всем элементам матрицывыигрышей даёт матрицу с положительными элементами, и следовательно, с положительным значением цены игры. При этом оптимальные смешанные стратегии обоих игроковне изменяются.
Итак, пустьданаматричная игра с матрицейАпорядкаm х n.Согласно свойству 7 оптимальные смешанные стратегиих =(х1, ..., хm), y =(y1, ..., yn) соответственно игроков 1 и 2 и цена игрыu должны удовлетворять соотношениям.
Разделим все уравнения и неравенства в (1) и (2) наu(это можно сделать, т.к. по предположениюu> 0) и введём обозначения :
, 
,Тогда (1) и (2) перепишется в виде :
, 
, 
, , 
, 
, 
, .Поскольку первый игрок стремится найти такие значенияхiи, следовательно,pi, чтобы цена игрыuбыла максимальной, то решение первой задачи сводится к нахождению таких неотрицательных значений pi
, при которых 
, . 
Поскольку второй игрок стремится найти такие значенияyjи, следовательно,qj,чтобы цена игрыuбыла наименьшей, то решение второй задачи сводится к нахождению таких неотрицательных значений qj,
, при которых 
, . 
Формулы (3) и (4) выражают двойственные друг другу задачи линейного программирования (ЛП).
Решив эти задачи, получим значения pi
, qj иu.Тогда смешанные стратегии, т.е.xiиyjполучаются по формулам : 
Пример. Найти решение игры, определяемой матрицей.
Решение. При решении этой игры к каждому элементу матрицыАприбавим 1 и получим следующую матрицу
Составим теперь пару взаимно-двойственных задач :
Решим вторую из них
| Б.п. | q1 | q2 | q3 | q4 | q5 | q6 | Решение | a | Отношение |
| -1 | -1 | -1 | 0 | 0 | 0 | 0 | -3 | ||
| q4 | 1 | 2 | 0 | 1 | 0 | 0 | 1 | 5 | — |
| q5 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 4 |  |
| q6 | 2 | 1 | 0 | 0 | 0 | 1 | 1 | 5 | — |
| Б.п. | q1 | q2 | q3 | q4 | q5 | q6 | Решение | a | Отношение |
| 0 | -1 | 0 | 0 | 1 | 0 | 1 | 1 | ||
| q4 | 1 | 2 | 0 | 1 | 0 | 0 | 1 | 5 |  |
| q3 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 4 | — |
| q6 | 2 | 1 | 0 | 0 | 0 | 1 | 1 | 5 |  |
| Б.п. | q1 | q2 | q3 | q4 | q5 | q6 | Решение | a | Отношение |
| | 0 | 0 | | 1 | 0 |  |  | ||
| q2 | | 1 | 0 | | 0 | 0 | |  | |
| q3 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 4 | |
| q6 | | 0 | 0 |  | 0 | 1 | | |
Из оптимальной симплекс-таблицы следует, что
(q1, q2, q3) = (0;
; 1),а из соотношений двойственности следует, что
(p1, p2, p3) = (
; 1; 0).Следовательно, цена игры с платёжной матрицейА1равна
. 
,а игры с платёжной матрицейА:
.При этом оптимальные стратегии игроков имеют вид:
Х= (х1, х2, х3) = (uр1; uр2; uр3) =
= 
Y= (y1, y2, y3) = (uq1; uq2; uq3) =
= 
.2.2 Решение матричных игр в чистых стратегиях
Матричная игра двух игроков с нулевой суммой может рассматриваться как следующая абстрактная игра двух игроков.
Первый игрок имеет m стратегий i= 1,2,...,m, второй имеетn стратегий j= 1,2,...,n.Каждой паре стратегий (i,j) поставлено в соответствие числоаij,выражающеевыигрышигрока 1 за счёт игрока 2, если первый игрок примет своюi-ю стратегию, а 2 – своюj-ю стратегию.
Каждый из игроков делает один ход: игрок 1 выбирает своюi-ю стратегию (i=
), 2 – своюj-ю стратегию (j= 
), после чего игрок 1 получает выигрышаijза счёт игрока 2 (еслиаij<0, то это значит, что игрок 1 платит второму сумму |аij| ). На этом игра заканчивается.Каждая стратегия игрока i=
; j = часто называется чистой стратегией.Если рассмотреть матрицу
А=
то проведение каждой партии матричной игры с матрицей Асводится к выбору игроком 1 i-й строки, а игроком 2 j-го столбца и получения игроком 1 (за счёт игрока 2) выигрыша аij.
Главным в исследовании игр является понятие оптимальных стратегий игроков. В это понятие интуитивно вкладывается такой смысл: стратегия игрока является оптимальной, если применение этой стратегии обеспечивает ему наибольший гарантированный выигрыш при всевозможных стратегиях другого игрока. Исходя из этих позиций, игрок 1 исследует матрицу выигрышей А следующим образом: для каждого значения i (i =
) определяется минимальное значение выигрыша в зависимости от применяемых стратегий игрока 2