2.5. Взаимоотношение между двумя алгоритмами

В разделе 1.4 было показано, что для марковских процессов принятия решений с переоценкой итерационный алгоритм и алгоритм линейного программирования эквивалентны с математической точки зрения. Теперь

мы установим аналогичное свойство для процессов с одним эргодическим классом.

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

Прямая задача:

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

В равенствах (2.51) лишнее ограничение при опущено. Обозначим двойственные переменные

Двойственная задача:

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

Поскольку прямая задача имеет решение и значение оптимума равно то, используя теорему двойственности (см., например, [25]), можно записать двойственную задачу в следующем виде.

Двойственная задача:

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

свободны от ограничений при считается, что

Двойственную задачу можно непосредственно получить из построений раздела 2.3. Поскольку вывод ее почти совпадает с выводом, приведенным в разделе 1.2, то здесь он опускается.

Исчерпывающую информацию о задаче дает диаграмма Таккера (табл. 2.1) для прямой и двойственной задач. В двойственной задаче равенство соответствует отсутствию лишнего ограничения при в (2.51) для прямой задачи.

Таблица 2.1 (см. скан) Диаграмма Таккера для марковского процесса принятия решений с одним эргодическим классом

Здесь, как и в разделе 1.4, можно опустить фазу I и с помощью теоремы 2.3 сразу получить допустимое базисное решение. В качестве начальных переменных можно, например, выбрать

Для любого допустимого базисного решения имеем следующую базисную матрицу:

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

где -мерный вектор, элемент которого равен а верхний индекс означает транспонирование. Расписывая (2.62) поэлементно и полагая получим

что соответствует процедуре определения весов в итерационном алгоритме, рассмотренном в разделе 2.3.

Симплексный критерий на следующем шаге равен

Очевидно, что для базисных переменных

Если для всех

или, используя (2.65), для всех

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

Если по крайней мере для одной пары имеет место

или

то существует улучшенное решение, или улучшенная стратегия, соответствующие процедуре улучшения решения. Выберем так, чтобы достигался

Мы уже видели из теоремы 2.3, что такие подстановки приводят к улучшенным стратегиям.

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