Файл: Материалы по курсу (часть 1).docx

10. Метод динамического программирования (дп). Алгоритм решения задач управления состоянием организма в биотехнических системах. Основное рекуррентное уравнение дп.

Рассмотрим управляемый процесс, который переводит некоторую систему G из нач. состояния S₀ в конеч. состояние S_m. При наличии промежуточных состояний такой перевод представляется в виде траектории, состоящей из конкретной последовательности промежуточных состояний (рис. 1). Если промежуточные состояния могут быть различными, то траектория перевода G из S₀ в S_m неоднозначна и зависит от вырабатываемых управляющих воздействий x.

Рис.1.

Введя целевую функцию W =W(x), зависящую от выбранного управления x, можно сравнивать (по величине W) траектории друг с другом и ставить задачу об отыскании оптимальной траектории, при которой достигается экстремум W (т.е. мин или мах функции).

В зависимости от содержания целевой функции в процессе оптимизации ее стремятся либо мах-ть, либо мин-ть. Далее будет рассматриваться оптимизация, при которой W → min. Таким образом, задача заключается в отыскании оптимального управления x*, при котором целевая функция W достигает своего минимального значения W*, т. е.

.

Представим себе процесс управления состоящим из конечного числа последовательных шагов. В этом случае траектория перехода G из S₀ в S_m будет иметь вид последовательности промежуточных состояний S₀, S₁, S₂, …, S_m, которая является результатом пошагового управления x, также имеющего вид последовательности x = x₁, x₂, …, x_m.

Пусть S_i - состояние системы G, а x_i – управление на i-м шаге для произвольной траектории. Для конкретной траектории конкретное управление переводит G в конкретное состояние S_i′.

(!) управления x₁, x₂, …, x_m в общем случае не числа, а векторы, функции, и т. п. (!) Пусть на каждом отдельном i-м шаге, заключающемся в переходе из S_i−1 в S_i, известно значение целевой функции W, которое обозначается w_i . Считая выбранный критерий W аддитивным (суммирующимся), т. е. полагая, что

задачу оптимизации можно сформулировать следующим образом.

Требуется найти такое оптимальное управление x* = x₁*, x₂*, …, x_m* (где x_i* – оптимальное шаговое управление на i-м шаге), при котором целевая функция W принимает минимальное значение, т. е.

Последовательность оптимальных шаговых управлений x₁*, x₂*, …, x_m* приводит к оптимальной траектории S₀, S₁*, S₂*, …, S_m-1*, S_m перевода G из S₀ в Sm.

Что-то вроде примера

Рис.2

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

Пусть W′ > W′′ , тогда второй вариант является оптимальным, т. е. x* = x′′, W* =W′′ .

Тут типо конец примера и важный вывод:

(!)Поиск оптимального управления x∗ методом ДП основан на использовании общего принципа, известного как принцип оптимальности:

каково бы ни было состояние S системы G в результате какого-то числа шагов, мы должны выбирать управление на ближайшем шаге так, чтобы оно в совокупности с оптимальным управлением на всех последующих шагах приводило к минимальному значению целевой функции на всех оставшихся шагах, включая данный.(!)

Схема решения (Алгоритм).

После выбора способа описания состояний управляемой системы и разбиения всего процесса управления на шаги применяется следующая процедура:

1) Перечислить набор шаговых управлений x_i для каждого шага и налагаемые на них ограничения.

2) Для каждого i-го шага определить значение в функции от состояния S_i−1 на (i−1) -м шаге и от шагового управления x_i

= f_i (S_i−1, x_i ) .

3) Определить, как изменяется состояние S_i−1 системы G под влиянием управления x_i на i-м шаге: оно переходит в новое состояние

S_i = ϕ_i (S_i−1, x_i ) .

(не пугаемся, ϕ – это произвольная функция)

4) Пусть W_i (S_i−1) – условный оптимум (наилучший вариант) целевой функции, получаемый на всех последующих шагах, начиная с i-го и до конца. Надо записать основное рекуррентное уравнение динамического программирования, выражаю-

щее W_i (S_i−1)) через уже известную функцию W_i+1 (S_i),

Этому условному оптимуму целевой функции соответствует условное оптимальное управление на i-м шаге x_i (S_i−1), которое совместно с оптимальным управлением на всех последующих шагах обращает целевую функцию на всех оставшихся шагах, начиная с данного, в минимум.

5) Произвести условную оптимизацию последнего, m-го шага, задав множество состояний S_m−1, из которых можно за один шаг дойти до конечного состояния, вычисляя для каждого S_m−1 условный оптимум целевой функции по формуле

и находя условное оптимальное управление x_m (S_m−1), для которого этот минимум достигается.

6) Произвести условную оптимизацию (m – 1)-го, (m – 2)-го и т. д. шагов по

формуле из п.4, полагая в ней i = (m −1), (m − 2), …, и для каждого шага указать

условное оптимальное управление x_i (S_i−1), при котором достигается минимум.

Так как начальное состояние системы S₀ одно и оно известно, то на первом шаге варьировать состояние системы не нужно – оптимальное значение целевой функции для S₀ находится непосредственно. Это и есть оптимум функции цели за весь процесс перевода:

W*=W₁(S₀) .

7) Произвести безусловную оптимизацию управления, учитывая выработанные ранее рекомендации на каждом шаге. На первом шаге оптимальное шаговое управление x₁* = x₁(S₀) . Пользуясь формулой из пункта 3, находим изменившееся состояние системы S₁, для него определяем оптимальное управление на втором

шаге x₂*, и т. д. до конца.

11. Управление переходом организма из исходного в конечное состояние методом дп: использование ориентированного графа.

(в квадратных скобках не такая супер-важная инфа, что прям важно в них, я подчеркнула)

[Управляемый процесс перевода системы G из начального S₀ - в конечное S_m -состояние можно интерпретировать как процесс лечения, который переводит организм человека из состояния «болен» в состояние «здоров», или процесс нормализации состояния человека-оператора, переводящий организм из состояния «не норма» в состояние «норма».

Если при этом реализуется возможность выделения конечного множества состояний организма, являющихся промежуточными между S₀ и S_m, и можно описать шаговые управления, переводящие организм из одного состояния в другое, то для оптимизации процесса лечения или нормализации состояния можно применить метод динамического программирования.]

С помощью этого метода может быть заранее рассчитана оптимальная траектория перевода организма из S₀ в S_m. В качестве критериев оптимизации, т. е. целевых функций W, могут выступать следующие: время лечения (нормализации состояния, выздоровления, вывода из опасного состояния и т. п.), токсичность применяемых медикаментов – «вредность» лечения, его стоимость, вероятность благоприятного исхода, риск осложнений и др.

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

Далее в примерах мы будем использовать лишь один аддитивный критерий – время лечения или нормализации состояния.

Сформулируем задачу следующим образом. Имеется два заболевания B1 и B2, каждое из которых состоит из n последовательных стадий болезни: 1-й, 2-й, …, n -й. Стадия n – это «норма», а стадия 1 – наибольшая выраженность заболевания. За один шаг лечения посредством направленных лечебных воздействий можно изменить (увеличить) стадию только одного заболевания на 1. Условия задачи иллюстрирует рис. 2.3, где при n = 5 все возможные состояния пациента задаются узлами построенной прямоугольной сетки.

Рис.3

Для задания значений целевой функции на отрезках прямых, соединяющих узлы сетки, должны быть проставлены числа, равные времени перевода организма из состояния в состояние. Траектория перевода организма из S₀ в S_m будет иметь вид ступенчатой линии. Требуется найти такую траекторию, при которой общее время лечения будет минимальным. Решение этой задачи рассмотрим в виде следующего конкретного примера.