Методы динамического программирования

Предварительные замечании

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

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

составляющим основу декомпозиции, является оптимальность.

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

Очевидно, что никакая математическая модель не может описать действительность с исчерпывающей полнотой (как утверждал небезызвестный Козьма Прутков, «никто нс может объять необъятное»). Более того, рост сложности модели требует и более сложного математического аппарата для ее анализа.

Потому, согласно Р. Веллману, «ученый должен идти прямой и узкой тропой между Западнями Персунрощсния и Болотом Переусложения».

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

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ   След >