Постановка задачи. Динамическое программирование

Динамическое программирование

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

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

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

Предположим, что процесс управления можно разбить на n-шагов.

S_i – состояния системы к началу (i+1) шага.

S_n – конечное состояние системы.

Через U_i – обозначим управление на i-шаге.

Тогда процесс управления можно изобразить следующим образом:

Предположим, что с переводом системы из состояния S₀ в состояние S_n связана заинтересованность, которая численно выражается с помощью критерия W (max W).

В простых задачах начальное состояние S₀ и конечно S_n задано в более сложной системе.

В более сложных задачах эти состояния являются элементами некоторых дополнительных множеств.

S₀ ℮ – множество начальных состояний

S_n ℮ – множество конечных состояний

Среди множества всех дополнительных управлений U = (U₁…U_n) переводят систему S из начального S₀ ℮ в S_n ℮ выбрать то, которое доставляет max функции W.

Дата добавления: 2015-04-23