Одна схема управляемой цепи Маркова, уравнение Беллмана

Будем условно говорить о некоторой физической системе, шаг за шагом меняющей свое фазовое состояние.

Обозначим ε1, ε2, . ее возможные состояния и ξ(t) - ее состояние через t шагов.

Будем считать, что процесс эволюции системы, описываемый цепочкой

является случайным марковским процессом, причем вероятности рij перехода из состояния εi в соответствующие состояния εj зависят от некоторого управляющего параметра, так что, если система на каком-либо шаге находится в состоянии εi и в соответствии с этим наблюдатель выбирает определенное значение управляющего параметра d, то вероятности перехода на следующем шаге будут pij = pij(d).

Совокупность возможных значений управляющего параметра d обозначим D.

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

Поскольку течение процесса ξ(t) зависит не только от воли управляющего этим процессом оператора, но и от случая, привести систему в одно из фазовых состояний указанного множества Е, вообще говоря, можно лишь с некоторой вероятностью Р, зависящей от способа управления.

Предположим, что управляющий процессом оператор руководствуется следующей программой управления: для каждого состояния εi , куда система может прийти на некотором шаге n, предусматривается выбор соответствующего значения управляющего параметра d - для каждой пары εi и n свое значение d = d(εi , n).

Вся программа может быть описана функцией d = d(x, t) от х = ε1, ε2, . и t = 0, 1, . называемой решающей функцией. Если выбрана программа управления с решающей функцией d = d(x, t), то течение случайного процесса ξ(t) происходит таким образом, что при попадании на n-м шаге в состояние εi , на следующем шаге с вероятностями pij = pij(d), d = d(εi , n), осуществляется переход в соответствующие состояния εj, j = 1, 2.

Ясно, что вероятность того, что система будет приведена в одно из заданных состояний, зависит от выбора программы управления, от выбора решающей функции d = d(x, t):

P = P(d)

(Управление с решающей функцией d 0 = d 0 (х, t) называется оптимальным, если

где max берется по всем возможным управлениям, по всем возможным решающим функциям d = d(x, t).

Рассмотрим следующую задачу управления случайным процессом ξ(t): через заданное число шагов п с максимально возможной вероятностью привести систему в определенное множество фазовых состояний Е. В этом случае

Пусть P(k, i, d) есть вероятность того, что при попадании на k-м шаге в состояние εi система за оставшиеся n-k шагов будет приведена в одно из состояний заданного множества Е (при этом считается выбранным некоторое управление d = d(x, t)):

Имеет место следующее соотношение:

Оно является простым следствием формулы полной вероятности - на следующем шаге система с вероятностью pij (d), d = d(εi , k), переходит в одно из состояний εj, j = 1, 2. откуда приводится в множество Е с соответствующими вероятностями P(k+1, j, d).

В соотношении (11.9) при k = n-1 фигурирует вероятность

где суммирование идет по всем j, для которых εj входит в заданную совокупность Е. Очевидно, вероятность Р (n-1, i, d) зависит лишь от выбора одного-единственного значения управляющего параметра d(εi , n-1).

Определим d° как точку максимума функции

от параметра d, пробегающего множество D:

(здесь и в дальнейшем предполагается, что рассматриваемые функции от d достигают максимума). Ясно, что для каждой пары (εi , n-1) будет свое значение d 0 = d 0 (εi , n-1), i = 1, 2, .

При k = n-2 формула (11.9) дает следующее соотношение:

Здесь вероятности pij(d) зависят лишь от значений d = d (εi , n-2) решающей функции d = d(x, t), а вероятности Р(n-1, j, d) - лишь от исходных значений d = d(εj, n-1) этой функции.

Если "подправить" решающую функцию d = d(x, t), заменив исходные значения d(εj, n-1) на определенные ранее значения d 0 (εj, n-1), то от этого соответствующие вероятности Р (n-1, j, d) увеличатся до максимально возможных значений Р 0 (n-1, j), что приведет к увеличению вероятности Р (n-2, j, d) до значения

Зависимость от управляющей функции d = d(x, t) здесь проявляется лишь через зависимость переходных вероятностей pij(d) от управляющего параметра d = d(εi , n-2). Определим точку d 0 как точку максимума функции от параметра d, пробегающего множество D:

P 0 (n-2, i) = P(n-2, i, d 0 ) = P(n-2, i, d) (11.12)

Очевидно, для каждой пары (ε, n - 2) будет свое значение d = d (εi , n-2), i = 1, 2, .

Ясно, что если решающая функция d = d(x, t) при х = ε1, ε2, . и t = n-2, n-1 принимает определенные выше значения d 0 (x, t), то вероятности P(k, i, d) при k = n-2, n-1 и всех i = 1, 2, . принимают максимально возможные значения P0(k, i).

Отправляясь от решающей функции d = d(x, t) такой, что

d(x, t) = d 0 (x, t) (11.13)

при всех х = ε1, ε2, . и t = n-2, n-1, переходим затем к следующему соотношению:

и определяем точку d 0 = d 0 (εi, n-3) максимума вероятности P(n-3, i, d) как функции от параметра d. Затем, так же как и ранее, "подправляем" решающую функцию d = d(x,t), определяя при t = n-3 ее значения формулой (11.13) для всех х = ε1, ε2, .

Продолжая этот процесс, можно последовательно найти оптимальную решающую функцию d = d 0 (x, t), x = ε1, ε2, . t = 0, 1, . , при которой вероятность P(d) = P(0, i, d), отвечающая начальному положению ξ(0) = εi, достигает своего максимального значения. На k-м шаге этого последовательного процесса соответствующее значение d 0 = d 0 (εi , n-k) определяется как точка максимума функции

где Р0(k, i) суть максимально возможные значения рассматриваемых вероятностей Р (k, i, d); k = 0, 1, . , n; i = 1, 2, .

лежащее в основе описанного метода нахождения оптимальной решающей функции d 0 = d 0 (x, t), называется уравнением Беллмана.

Пример. Пусть имеются два возможных состояния ε1 и ε2, причем в зависимости от управляющего параметра d переходные вероятности могут непрерывно меняться в пределах α1 ≤p11(d) ≤β1, α2 ≤p21(d) ≤β2.

Как выглядит оптимальное управление, если требуется, чтобы в определенный момент (скажем, через два шага) система была в состоянии ε1?

Видно, что, отправляясь из состояния ε1 следует выбрать максимальной переходную вероятность р11, если β1≥β2 (положив p11 = β1),

И выбрать максимальной переходную вероятность р12 = 1-р11, если β1≤β2 (положив р11 = α1).

Аналогично выглядит оптимальное решение для начального состояния ε2.

Задача о наилучшем выборе. Рассмотрим процедуру выбора наилучшего предмета и отвечающий ей марковский случайный процесс с переходными вероятностями рij вида (см. стр. 76):

Выбор ξ(k)-го предмета можно интерпретировать как остановку соответствующего процесса

В каждом из состояний ε1, . , εm наблюдатель решает, остановить или продолжать процесс выбора.

Первому решению, принятому в состоянии εi , формально соответствуют переходные вероятности pij вида

а второму решению - переходные вероятности, указанные ранее.

Перед нами схема управляемого марковского процесса, переходные вероятности рij которого меняются в зависимости от решения наблюдателя.

Управляющий параметр d здесь принимает два значения, скажем 0, что означает остановку процесса в соответствующем состоянии, и 1, что означает принятие противоположного решения.

Зависимость переходных вероятностей pij = pij(d) указана выше.

Каждая процедура выбора описывается некоторой решающей функцией d = d(x), х = ε1, . , εm, которая предусматривает, в каком состоянии х следует продолжать процесс выбора, а в каком следует его прекратить и остановиться на последнем из осмотренных предметов.

Задача состоит в том, чтобы найти такую процедуру выбора, такую решающую функцию d = d(x), х = ε1, . , εm, чтобы вероятность выбрать абсолютно наилучший предмет была бы максимальной.

Эта вероятность есть

где i/m - вероятность того, что 1-й предмет будет наилучшим, pi - вероятность того, что процесс будет остановлен именно в состоянии εi , а суммирование происходит по всем тем состояниям εj, в которых, согласно решающей функции d = d(x), предписывается остановка процесса. Эта вероятность зависит от выбранной решающей функции d = d(x).

Для нахождения оптимальной решающей функции d 0 = d 0 (x) рассмотрим вероятности P(k, d) выбрать наилучший предмет при условии, что число осмотренных до него предметов не меньше k, т. е. при условии, что рассматриваемый процесс на некотором шаге будет в состоянии εk.

Согласно формуле полной вероятности

Очевидно, если процесс будет в состоянии εm, то m-й предмет и является наилучшим, так что оптимальным значением d = d 0 (εm) решающей функции d = d (х) является d 0 (εm) = 0, при котором P(m,d) = 1. Из соотношений (11.16), (11.17) получаем, что при k = m-1 вероятность наилучшего выбора при значении d(εm) = 1 есть

откуда видно, что оптимальным значением d = d 0 (εm-1) решающей функции d = d(x) является d 0 (εm-1) = 0. При этом есть максимально возможное значение вероятности Р(m-1, d), зависящей от решающей функции d = d (х).

Предположим, что при x = εk, . , εm оптимальные значения решающей функции d = d(x) все равны 0, что соответствует остановке процесса в состояниях εk, . , εm. Каково предшествующее оптимальное значение d 0 (εk-1)?

Очевидно, если процесс останавливается в любом из состояний x = εk, . , εm, то, как следует из соотношений (11.16), (11.17), вероятность наилучшего выбора при условии, что будет осмотрено не менее k-1 предметов, есть

откуда видно, что оптимальное значение d = d 0 (εk-1) решающей функции d = d(x) есть

Легко видеть, что оптимальная решающая функция d = d(x) имеет следующую структуру:

где m0 - некоторое число. При оптимальном выборе следует продолжать процесс осмотра до тех пор, пока не попадется предмет с номером k≤m0, наилучший среди всех ранее осмотренных предметов. На этом k-м по счету предмете и следует остановить свой выбор. Согласно (11.18) число m0 есть наибольшее натуральное число, для которого

Нетрудно установить, что при больших m это число m0 приблизительно равно m/e, e = 2,72.