20. Транспортные задачи с ограничениями на пропускную способность сети.

21. Матричные игры. Платежная матрица. Игра с нулевой суммой.

Теория игр – это раздел математики, изучающий методы анализа и оценки конфликтных ситуаций.

Значения выигрыша при каждой паре стратегий (в каждой ситуации), удобно записывать в виде матрицы:

Полученная матрица имеет размер и называется матрицей игры, или платёжной матрицей. Строки матрицы А соответствуют стратегиям первого игрока, а столбцы – стратегиям второго.

Парная игра называется игрой с нулевой суммой, если сумма платежей равна нулю, т.е. если проигрыш одного игрока равен выигрышу второго (имеет место равенство ).

При анализе такой игры можно рассматривать выигрыши только одного из игроков.

22. Принцип минимакса и максимина. Верхняя и нижняя цена игры.

Число называется нижней ценой игры.

Принцип построения стратегии игрока А, основанный на максимизации минимальных выигрышей, называется принципом максимина, а выбираемая в соответствии с этим принципом стратегия - максиминной стратегией игрока А.

Число называется верхней ценой игры.

Принцип построения стратегии игрока B, основанный на минимизации максимальных потерь, называется принципом минимакса, а выбираемая в соответствии с этим принципом стратегия - минимаксной стратегией игрока B.

23. Оптимальные стратегии игроков. Решение матричной игры с седловой точкой.

24. Чистые и смешанные стратегии игроков. Вероятностная интерпретация. Теорема о существовании решения игры в смешанных стратегиях (теорема о минимаксе).

Смешанной стратегией игрока называется распределение вероятностей на множестве его стратегий.

Иными словами, смешанной стратегией первого игрока является произвольная случайная величина, принимающая значения 1, 2, 3, , , с вероятностями , , , , , , . Аналогично, смешанная стратегия второго игрока есть произвольная случайная величина, принимающая значения 1, 2, 3, , с вероятностями , , , , , , .

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

25. Графическое решение в случае игры 2 m и n2 .

26. Сведение решения игры в произвольном случае к задаче линейного программирования.

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

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

,

.

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

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

хотя бы для одного допустимого набора . Обозначая , получаем следующую задачу линейного программирования

,

.

Если решение задачи, то

, .

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