Математические методы исследования операций в экономике (стр. 35 из 37)

6.1.5. Решение матричных игр методами линейного программирования. Рассмотрим некоторые способы решения матричных игр. Задача, решаемая первым игроком, (6.10) была сформулирована как максимизация наименьшей из сумм

но если определить некоторое х_m+1, для которого выполняется

то она может быть сведена к задаче линейного программирования:

при ограничениях

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

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

Достаточно легко проверить, что задачи (6.16)-(6.17) и(6.18)-(6.19) образуют двойственную пару. Здесь в определенном смысле мы вернулись к проблемам, уже рассматривавшимся во второй главе, а именно к взаимосвязи между наличием решения у некоторой оптимизационной задачи и существованием седловой точки у соответствующей функции Лагранжа. В данном случае аналогичная связь прослеживается между седловой точкой игры и решением пары задач оптимизации.

6.1.6. Графические методы решения игр. Следует отметить, что применение для решения задач (6.16)-(6.17), (6.18)-(6.19) стандартных алгоритмов линейного программирования далеко не всегда является рациональным. Помимо этого существуют иные методы, которые основываются на использовании специфики данных задач. В настоящем пункте мы остановимся на очень простом классическом способе поиска оптимальных смешанных стратегий в матричных играх, где один из участников имеет только две стратегии (это так называемые 2 х п итх 2 игры).

Для определенности положим, что игрок I имеет возможность выбирать между двумя стратегиями с вероятностями x₁ и x₂ = 1-x₁, тогда его ожидаемые выигрыши, соответствующие чистым стратегиям игрока II, примут вид

или

т. е. ожидаемые выигрыши могут быть представлены в виде графиков линейных функций, зависящих от переменной x₁∊ [0; 1] (рис. 6.1, где предполагается, что игрок II имеет три стратегии).

Линии, изображенные на рис.6.1, задают зависимости среднего выигрыша игрока I от значения вероятности x₁ , с которой он выбирает свою первую стратегию, для случаев, когда его противник выбирает первую, вторую или третью чистую стратегию. Тогда значениям минимального гарантированного дохода первого игрока соответствует нижняя огибающая всех трех прямых. Согласно принципу максимина, оптимальному выбору игрока I будет соответствовать наивысшая точка, лежащая на данной огибающей, отмеченная на рисунке как (x₁*,z*). Зная ее, можно определить оптимальную смешанную стратегию первого игрока х* = (x₁*, 1-x₂*) и цену игры, равнуюz*.

Исходя из отношения двойственности, которым, как было установлено в п. 6.1.5, связаны задачи обоих игроков, по оптимальной стратегии первого участника х* однозначно определяетсяоптимальная стратегия его противника у*. Поскольку у*является результатом решения задачи линейного программирования, то он обладает всеми свойствами допустимого базисного плана, т. е. в случае 2 х п игры имеет не более чем две ненулевых компоненты и не менее чем (п-2) нулевых. Номера ненулевых элементов у* определяются номерами линий, пересечение которых определило оптимальную стратегию первого игрока. Действительно, игрок II знает оптимальную стратегию соперника, и применение им стратегий, соответствующих прямым, проходящим выше точки (х₁*,z*), только увеличило бы его проигрыш.

В рассматриваемом примере это линии z₂ и z₃, и, следовательно, в своей оптимальной стратегии второй игрок должен с ненулевыми вероятностями применять вторую и третью чистые стратегии (у₂>0, у₃ >0). На основе этого, а также учитывая условие нормировки

можем выразить: y₃ =l – y₂ тогда оптимальное значение y₂* может быть найдено из условия

или

В результате получаем оптимальную стратегию игрока II у*=(0, у₂*, у₃*).

Очевидно, что поиск решения в игре т х 2 осуществляетсяаналогичным образом с точностью до наоборот: строятся графики ожидаемого проигрыша игрока II, находится их верхняя огибающая и т. д.

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

6.2. ТЕОРИЯ ОПТИМАЛЬНОГО УПРАВЛЕНИЯ

6.2.1. Постановка и классификация задач теории оптимального управления. В подавляющем большинстве рассмотренных нами задач факторы, связанные с изменением изучаемых объектов и систем в течение времени, выносились за скобки. Возможно, при выполнении определенных предпосылок такой подход является конструктивным и правомерным. Однако очевидно и то, что это допустимо далеко не всегда. Существует обширный класс задач, в которых необходимо найти оптимальные действия объекта, учитывающие динамику его состояний во времени и пространстве. Методы их решения составляют предмет математической теории оптимального управления.

В весьма общем виде задача оптимального управления может быть сформулирована следующим образом:

Имеется некоторый объект, состояние которого характеризуется двумя видами параметров — параметрами состояния и параметрами управления, причем в зависимости от выбора последних процесс управления объектом протекает тем или иным образом. Качество процесса управления оценивается с помощью некоторого функционала*, на основе чего ставится задача: найти такую последовательность значений управляющих параметров, для которой данный функционал принимает экстремальное значение.

*Функционалом называется числовая функция, аргументами которой, как правило, служат другие функции.

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

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

Существуют различные подходы к классификации задач оптимального управления. Прежде всего, их можно классифицировать в зависимости от объекта управления:

- задачи управления с сосредоточенными параметрами;

- задачи управления объектами с распределенными параметрами.

Примером первых является управление самолетом как единым целым, а вторых — управление непрерывным технологическим процессом.

В зависимости от типа исходов, к которым приводят применяемые управления, выделяют детерминированные и стохастические задачи. В последнем случае результатом управления является множество исходов, описываемых вероятностями их наступления.

По характеру изменения управляемой системы во времени различают задачи:

- с дискретно изменяющимся временем;

- с непрерывно изменяющимся временем.

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