Курсовая работа: Линейное программирование
Разделим все уравнения и неравенства в (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) =
=