Управление марковской цепью: принятие решений при конечном числе этапов

Рассмотрим систему, которая имеет n возможных состояний , , …,  и которая в фиксированные моменты времени , , …,  () переходит скачком (мгновенно) из одного возможного состояния в другое (или остается в прежнем). Будем предполагать, что вероятность перехода системы в любое возможное состояние в момент времени  (т.е. после i-го шага) определяется тем состоянием, в котором система находилась в момент времени (т.е. после -го шага), и не зависит от того, когда и как она пришла в это состояние. Таким образом, полагаем, что процесс изменения состояний системы представляет собой марковскую цепь. Напомним, что марковская цепь определена, если задан вектор начальных вероятностей состояний системы и матрицы переходов  каждого k-го шага .

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

С каждой альтернативой  свяжем матрицу доходов ), элементы которой  выражают доход за один шаг при переходе системы из состояния i в состояние j в случае использования l-ой альтернативы. Доход за m шагов складывается из доходов с 1-го шага по m-ый шаг включительно.

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

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

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

Рассмотрим подробно k-ый шаг процесса управления. Пусть после -го шага  система пришла в состояние  и мы выбрали альтернативу . Под воздействием выбранного управления  система случайным образом перейдет в одно из состояний , , …, . Если это состояние , то выражение  определит суммарные доходы, которые мы будем иметь с k-го шага по последний, если на k-ом шаге мы выберем управление , а на всех последующих шагах используем оптимальное управление. В свою очередь сумма

Ссылка на основную публикацию
Adblock detector