7.3. Схемы оптимизации

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

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

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

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

Так как то является планом данной задачи. А в силу леммы оптимальный план этой

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

Третий метод является обобщением ховардовских итерационных алгоритмов нахождения стратегий. Пусть выполнены условия монотонности и -сжатия, и пусть в определении оператора А (см. (7.10)) точная верхняя грань достигается при всех т. е. для некоторой политики у, зависящей, вообще говоря, от Пусть произвольное фиксированное натуральное число.

Процедура улучшения решения.

1. Взять произвольную начальную политику 8.

2. Вычислить

3. Вычислить и положить

4. Если то заменить на и перейти к п. 2.

Если то вычислить и остановиться. Из лемм 7.1 и. 7.2 следует, что