|
ИСТИНА |
Войти в систему Регистрация |
ИСТИНА ЦЭМИ РАН |
||
Об алгоритме Сонина решения задачи оптимальной остановкистатья
- Автор: Пресман Э.Л.
- Журнал: Обозрение прикладной и промышленной математики
- Том: 15
- Номер: 4
- Год издания: 2008
- Издательство: Научное издательство «ТВП»
- Местоположение издательства: Москва
- Первая страница: 756
- Последняя страница: 757
- Аннотация: Мы рассматриваем задачу оптимальной остановки цепи Маркова на бесконечном интервале времени. Наиболее общий подход к нахождению функции выигрыша состоит в следующем. Рассматривается рекуррентная последовательность iV /i(х) - max[7(z), i7V/isupik/i/supi~/isupil/i/supi /i(i)], ik /i^ 1, где iV°(x) = g(x), g(x) /i- плата за остановку, i"Р /i- оператор переоценки, при этом iV/isupik/i/supi(x) /iотвечает функции выигрыша при оптимальной остановке не более чем за ik /iшагов. Доказывается, что последовательность iV/isupik/i/supi(x) /iсходится к функции выигрыша в задаче на бесконечном интервале времени, и говорится iСедьмая Международная Петрозаводская конференция/i757 о том, что указанная процедура дает конструктивный способ нахождения функции выигрыша. Однако даже для цепи Маркова с двумя состояниями указанная процедура дает точное значение функции выигрыша только за бесконечное число шагов. Сонин (см. [1], [2]) для случая цепи с конечным числом m состояний предложил алгоритм, который позволяет найти функцию выигрыша и множество остановки не более чем за 2т шагов. В основе алгоритма лежит тот факт, что в тех точках, в которых выигрыш от остановки меньше, чем выигрыш от продолжения на один шаг, останавливаться заведомо не нужно. Поэтому эти точки можно исключить из рассмотрения и изучать новую цепь, с новым пространством состояний и переходными вероятностями, совпадающими с распределением точки первого возвращения старой цепи в новое пространство состояний. Эти переходные вероятности легко пересчитываются из старых. В случае конечного числа состояний за конечное число шагов приходим к ситуации, когда для всех точек выигрыш от остановки больше или равен выигрышу от продолжения. В этой ситуации множество остановки совпадает со всем пространством. В [3] обсуждались возможности применения этого алгоритма для некоторых ситуаций со счетным пространством состояний. Мы рассматриваем случай произвольного пространства состояний. Оказалось, что для проведения доказательств удобно несколько видоизменить алгоритм. Нужно рассмотреть новую цепь Маркова с тем же пространством состояний и тем же начальным состоянием, что и у исходной. Состояние новой цепи в момент п совпадает с состоянием старой цепи в момент n-го попадания в множество Яsup1/sup, которое получается из пространства состояний Д° старой цепи исключением тех точек, в которых заведомо не надо останавливаться. Мы показываем, как переходной оператор новой цепи связан с переходным оператором старой, и доказываем, что функция выигрыша и множество остановки для новой цепи совпадает с функцией выигрыша и множеством остановки исходной цепи. Рассмотрим цепь, построенную на fe-м шаге, и пусть Д*sup+1/sup - соответствующее этой цепи множество. Пусть iV/isupik/i/supi(x) /i- выигрыш от остановки цепи, построенной на ik-м /iшаге, в момент первого попадания в множество Д* sup+/sup sup1/sup. Мы показываем, что последовательность V*(i) сходится к функции выигрыша исходной задачи, и что последовательность iR/isupik/i/supi /iне возрастает и сходится к множеству остановки исходной задачи. Рассматриваются примеры, когда для нахождения функции выигрыша и множества остановки достаточно конечного числа шагов. Работа выполнена при поддержке РФФИ, проект 07-01-00541