Определение. Задачей линейного программирования в стандартной форме называется задача максимизации линейной функции
(1.21)
при условиях
(1.22)
(1.23)
где - элементы некоторой матрицы размером с вещественными элементами.
Легко убедиться, что решение матричной игры с платежной матрицей можно свести к решению некоторой задачи линейного программирования. Действительно, если игрок А использует стратегию он обеспечивает себе ожидаемый выигрыш не менее , где - любое число, такое, что
(1.24)
Поэтому задача нахождения оптимальной стратегии для игрока сводится к задаче линейного программирования:
(1.25)
при условиях
(1.26)
(1.27)
(1.28)
Аналогично, задача для игрока В сводится к задаче линейного программирования
(1.29)
при условиях
(1.30)
(1.31)
(1.32)
Из теоремы фон Неймана следует, что обе задачи имеют решение. Находя решение задачи (1.25)-(1.28) и (1.29)-(1.32), мы получим оптимальные стратегии игроков А и В в виде и соответственно. Цена игры получится из значения (равенство следует из теории двойственности для задач линейного программирования). Для решения задач (1.25)-(1.28) и (1.29)-(1.32) достаточно решить каким-либо способом (например, с помощью симплекс-метода) одну из них, а затем по окончательной таблице определить решение второй.
|
|