2.4. Алгоритм линейного программирования

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

где вектор стационарных вероятностей для матрицы удовлетворяющий соотношениям (2.18)-(2.20). Найдем оптимальную стратегию такую, что

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

Целевая функция равна

в силу (2.38) и определения величин Ограничения, в которые входят величины имеют вид

Полагая

и используя тот факт, что получим следующую задачу линейного программирования:

Для процесса с одним эргодическим классом ранг поскольку ранг Таким образом, одно из ограничений (2.46) излишнее, поэтому одно из равенств (2.46), например, соответствующее значению будем опускать. Тогда ограничения состоят из равенств (2.46) для (2.47) и неравенств (2.48).

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

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

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

Следствие. Любое допустимое базисное решение задачи линейного программирования порождает чистую (нерандомизированную) стационарную стратегию.

Доказательство. Из (2.44) и равенства имеем

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