Тема 2. Оптимизационные методы получения детерминированных оценок (стр. 11 )

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

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

Тогда имеют место уравнения:

,

, .

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

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

Пример 2.10 (Распределение тракторов по лесхозам). Управление лесного хозяйства приобрело лесохозяйственных тракторов, которые следует распределить между лесхозами. При поступлении тракторов в -й лесхоз, , уровень технической готовности машинно-тракторного парка повышается на величину , . Функции считаются известными. Какое решение должен принять главный инженер управления по распределению закупленной техники, чтобы получить максимальную техническую готовность парка?

Примем за 1-й этап – отправку тракторов в 1-й лесхоз, за 2-й этап – отправку тракторов во 2-й лесхоз, и т. д. Тогда будем иметь -этапную задачу оптимизации. Перед каждым этапом состояние системы характеризуется одним числом – количеством ещё нераспределённых тракторов. Рассматриваемая система является управляемой. Управления на каждом этапе есть количество тракторов , выделяемых лесхозам. Требуется найти оптимальное управление, т. е. такую совокупность чисел , которые максимизируют уровень технической готовности машинно-тракторного парка.

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

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

,

.

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

.

Пусть , тогда . Если предположить, что компьютер в течение 1с находит допустимых решений и для каждого из них вычисляет значение целевой функции, то для решения задачи потребуется с, или 33 года (). Таким образом, для решения данной задачи при больших и перебор допустимых решений неприменим. Метод динамического программирования решает проблему размерности.

Рассмотрим прямой ход метода динамического программирования – движение от последнего этапа к первому.

Начнём оптимизацию с -го лесхоза (-ый этап). Пусть остаток тракторов к этому этапу равен . Очевидно, что необходимо все тракторов передать -му лесхозу. Поэтому условное оптимальное управление на -ом этапе: , а условный оптимальный выигрыш: .

Перейдем к оптимизации предпоследнего лесхоза (-ый этап), и пусть остаток тракторов к этому этапу равен . Если -му лесхозу выделить тракторов, то -му лесхозу останется тракторов. Тогда выигрыш за -ый и -ый этапы составит . Максимизируя этот выигрыш по , получим условный оптимальный выигрыш за последние 2 этапа: . Значение , для которого достигается максимум, представляет собой условное оптимальное управление на -ом этапе.

Перейдем к оптимизации предпредпоследнего лесхоза (-ой этап). Пусть остаток тракторов к этому этапу равен . Если -му лесхозу выделить тракторов, то на долю -го и -го лесхозов останется тракторов. Тогда условный оптимальный выигрыш за последние 3 этапа составит: . Значение , для которого достигается максимум, представляет собой условное оптимальное управление на -ом этапе.