Предметный указатель

Глава 10. Многошаговая оптимизация

1. Основные понятия и постановка задачи

2. Принцип оптимальности и процедура динамического программирования

3. Модификации основной постановки

4. Предметный указатель

Основные понятия и постановка задачи

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

1. Рассматриваемой системе естественно сопоставляется некоторое множество S её состо-яний, так что функционирование системы фактически состоит в переходах из одних состояний в другие.

2. Для каждого состояния s Î S определено множество Q_s возможных воздействий на рас-сматриваемую систему, находящуюся в данном состоянии s. Под воздействием частного уп-равления v Î Q_s система переходит из состояния s в новое состояние s’ Î S, которое однозначно определяется «старым» состоянием s и частным управлением v Î Q_s по формуле

s’ = φ (s, v), (1)

где φ (s, v) – так называемая функция перехода, определяющая переходы системы между состоя-ниями.

3. При переходе системы из состояния s в состояние s’ = φ (s, v) под действием частного управления v доход от функционирования системы равен ψ (s, v), где функция ψ (s, v) называется функцией дохода. Функция дохода, как и функция перехода, определена при всех s Î S и при всех v Î Q_s при заданном состоянии s. При ψ (s, v) < 0 доход превращается в убыток.

4. Управление u = (v ₁, v ₂, …, v_N) является последовательностью частных управлений v ₁, v ₂, …, v_N, под действием которых система последовательно переходит из заданного начального состояния s ₀ в состояния

s ₁ = φ (s ₀, v ₁), s ₂ = φ (s ₁, v ₂), …, s_N = φ (s_{N −1}, v_N). (2)

При этом общий доход от управления u = (v ₁, v ₂, …, v_N) является суммой доходов от частных управлений:

ψ (u) = ψ (s ₀, v ₁) + ψ (s ₁, v ₂) + … + ψ (s_{N −1}, v_N), (3)

где s ₁, s ₂, …, s_N определяются формулами (2).

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

Основная задача многошаговой оптимизации состоит в максимизации дохода ψ (u) при за-данном начальном состоянии s ₀ и числе шагов N. Эта задача является дискретной при конечнос-ти множества S состояний и множеств управлений Q_s при всех s Î S. Далее в главе будут рас-сматриваться только дискретные задачи многошаговой оптимизации.

Всякую дискретную задачу многошаговой оптимизации можно представить как задачу оп-тимизации на графе. Именно, определим орграф G следующим образом. Множеством вершин орграфа G является конечное множество состояний S. Рассмотрим любую вершину s Î S. Каждо-му управлению v Î Q_s, под действием которого система переходит из состояния s в состояние s’ = φ (s, v), сопоставим дугу графа G с началом в вершине s и концом в вершине s’. За вес этой ду-ги примем величину ψ (s, v). При этом исходная задача многошаговой оптимизации перейдёт в задачу поиска ориентированного пути с максимальным суммарным весом при заданном началь-ном состоянии s ₀ и числе шагов N. Именно последняя задача и рассматривается в настоящей главе.

В разделе 1 дано краткое описание и постановка задачи многошаговой оптимизации; в разделе 2 приведён общий метод решения общей задачи многошаговой оптимизации – динами-ческое программирование; в разделе 3 рассмотрены некоторые модификации общей задачи, ко-торые проиллюстрированы развёрнутыми примерами важных классов задач: о замене машины и о критическом пути в сетевом графике.

Дата добавления: 2015-10-16