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

Ранее, в разделе 1.2, был приведен итерационный алгоритм нахождения стратегий. В разделе 1.3 рассматриваемая задача была сформулирована как задача линейного программирования. Здесь будет показано, что указанные два алгоритма эквивалентны.

Перепишем прямую задачу линейного программирования

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

Двойственная задача к (1.20) — (1.22) имеет вид

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

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

при всех Расписывая (1.26) поэлементно, получим ограничения (1.24). Целевой функцией является суммарный средний доход с учетом переоценки при начальном распределении а:

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

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

или

что соответствует начальной стратегии, рассмотренной в разделе 1.2. В данном разделе звездочка отмечает

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

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

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

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

Поскольку (единичная матрица), то

или

где индекс означает транспонирование матрицы. Из (1.32) следует, что является вектором симплекс-множителей для прямой задачи и вектором двойственных переменных. Таким образом,

Расписывая (1.34), получим

что соответствует процедуре определения весов в итерационном алгоритме, рассмотренном в разделе 1.2. Другими словами, решение системы из линейных уравнений (1.35) эквивалентно нахождению симплекс-множителей (и также двойственных переменных) для прямой задачи (этот вывод непосредственно следует из принципа дополнительной нежесткости).

Рассмотрим далее симплексный критерий для следующего шага, используя найденные симплекс-множители. Пусть симплекс-множитель для целевой функции равен 1, и запишем

Коэффициенты соответствующей задачи линейного программирования могут быть записаны в виде

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

Для базисных переменных

Если для всех

или согласно (1.38) для всех

то это означает, что оптимальное решение найдено.

Если существует по крайней мере одна пара такая, что

или, учитывая (2.38),

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

Следовательно, итерационный алгоритм нахождения стратегий является лишь специальным случаем алгоритма линейного программирования, обладающего тем свойством, что его ведущие операции выполняются одновременно над многими (не более чем переменными. В разделе 1.2 было уже показано, что эти подстановки для многих переменных приводят к улучшенной стратегии. Но даже, если есть только одна пара удовлетворяющая (1.41), то придется решать систему из линейных уравнений (1.35), что является недостатком метода. Подобные вопросы, возникающие при нахождении оптимальной стратегии, будут обсуждаться далее в гл. 2.