Исследование операций. Линейное, динамическое программирование




Исследование операций - часть 72


Требуется так провести дорогу из А и В,

чтобы суммарные затраты на сооружение участка были минимальны.

В этой задаче, в отлично от трех предыдущих, нет естественного членения на шаги: его приходится вводить искусственно, для чего, например, можно отрезок АВ разделить на т частей, провести через точки деления прямые, перпендикулярные АВ, и считать за «шаг» переход с одной такой прямой на другую. Если провести их достаточно близко друг от друга, то можно считать на каждом шаге участок пути прямолинейным. Шаговое управление на г-м шаге представляет собой угол

, который составляет участок пути с прямой АВ. Управление всей операцией состоит из совокупности шаговых управлений:

х = (

).

Требуется выбрать такое (оптимальное) управление х*, при котором суммарные затраты па сооружение всех участков минимальны:

W =

 => min.            (12.12)

Итак, мы рассмотрели несколько примеров многошаговых задач исследования операций. А теперь поговорим о том, как можно решать подобного рода задачи?

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

Такая идея постепенной, пошаговой оптимизации и лежит в основе метода динамического программирования. Оптимизация одного шага, как правило, проще оптимизации всего процесса: лучше, оказывается, много раз решить сравнительно простую задачу, чем один раз — сложную.

С первого взгляда идея может показаться довольно тривиальной. В самом деле, чего казалось бы, проще:

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

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


Содержание  Назад  Вперед