Динамическое программирование
Введение
динамический программирование математика
Термин случайный процесс был введен в начале 20 века рядом ученых, а именно, Колмогоровым А.Н. (1903-1987), Хинчиным А.Я. (1894-1959), Слуцким Е.Е. (1880-1948) и Винером Н. (1894-1965) и другими.
В конце 19 века физика и химия требовали от математики развития аппарата для изучения физических процессов и явлений природы, например: изучение броуновского движения стало началом создания раздела теории вероятностей - теории случайных процессов. Массовое развитие телефонных сетей так же потребовало разработки динамических моделей их функционирования, что и было сделано на основе теории вероятностей. Опираясь на труды Эрланга А.К. (1878-1929) по изучению загруженности телефонных сетей, начали развиваться некоторые разделы теории случайных процессов, в частности процессы гибели и размножения. Опорными точками в создании и развитии теории считаются следующие работы: Н. Винер в середине 20-х годов прошлого столетия ввел понятие винеровского процесса, российский математик А.А. Марков (1856-1922) создал работу по описанию цепных зависимостей.
В 1931 году А.Н. Колмогоров опубликовал статью Об аналитических методах в теории вероятностей, которая изложила основы марковских процессов, а в 1934 году А.Я.Хинчин опубликовал статью Теория корреляции стационарных стохастических процессов, описывающая основы стационарных процессов. Обе эти статьи считают началом построение общей теории случайных процессов, которая послужила основой для будущих исследований. В. Феллер К теории стохастических процессов (1936) построил интегро-дифференциальные уравнения для скачкообразных марковских процессов. 1
Теория полумарковских процессов имеет на данный момент более чем полувековую историю. Сама теория управляемых полумарковских процессов является одной из наиболее бурно развивающихся отраслей современной теории случайных процессов, так как полумарковские процессы позволяют составлять модели для теории массового обслуживания, теории резервирования и т. д.
В настоящее время теория случайных процессов является одной широко используемых математических дисциплин.
В работе рассматриваются модели задач надежности, массового обслуживания и динамического управления, решения которых являются во многих аспектах схожими с поставленной задачей построения абстрактного полумарковского процесса. Кроме того, был изучен метод динамического программирования, и его основы были использованы для составления и решения системы уравнений, соответствующей построенному функционалу достижения на каждом шаге управляемого полумарковского процесса.
1.Теоретические основы
1.1Основные определения и обозначения
Теория случайных процессов- это раздел теории вероятностей, который изучает закономерности случайных явлений и событий в динамике их развития.
Под случайным процессом понимается семейство случайных величин, индексированных некоторым параметром, чаще всего играющим роль времени.
Случайный процесс задается случайной функцией о(w,t)=X(t).
Классификация случайных процессов:
·Случайный процесс X(t) называется процессом с дискретным временем, если он изменяет свои состояния только в моменты времени , число которых может быть конечно или счетно.
·Случайный процесс X(t) называется процессом с непрерывным временем, если он переходит в иное состояние в любой момент времени.
·Случайный процесс X(t) называется процессом с непрерывными состояниями, если исследуемая случайная величина является непрерывной.
·Случайный процесс X(t) называется процессом с дискретными состояниями, если исследуемая случайная величина является дискретной.
·Случайный процесс X(t) называется стационарным в узком (строгом) смысле, если его функция распределения любого порядка не изменяется при замене последовательности на при любом временном сдвиге
·Случайные процесс X(t) называется стационарным в широком смысле, если его среднее значение, дисперсия не зависят от времени, а корреляционная функция зависит от разности времен .
·Случайный процесс X(t) называется процессом с независимыми приращениями, если для являются независимыми.
·Случайный процесс X(t) называется Марковским, если для каждого момента времени вероятность нахождения в состоянии в будущем зависит от того, где процесс находится в настоящем и не зависит от поведения в прошлом.
Частыми примерами случайных процессов, которые описываются в научной литературе, являются цепи Маркова.
Цепью Маркова называют Марковский случайный процесс с дискретным временем и конечным или счетным множеством состояний. Цепь Маркова можно задать переходными вероятностями или матрицей переходных вероятностей P и начальным распределением, иначе распределением вероятностей процесса в нулевой момент времени. Матрица переходных вероятностей P должна быть стохастической, то есть матрица должна иметь неотрицательные элементы, сумма элементов по строке равна 1.
Переходные вероятности цепи Маркова описываются следующими выражениями:
справедливо для неоднородной цепи, в которой вероятность перехода зависит от номера шага n.
выполняется для однородной цепи, для которой характерно отсутствие зависимости вероятности от номера шага - условная вероятность перехода из состояния i в состояние j за единицу времени.
-вектор начальных распределений
Теперь можно дать точное определение цепи Маркова как последовательность случайных величин { с конечным или счетным множеством значений с дискретным временем, начальным распределением и матрицей перехода P.
Одно из важнейших свойств, которым обладают марковские цепи - марковское свойство.
Для случайного процесса X(t) свойство заключается в том, что для любого набора моментов времени вероятность преобразуется в выражение вида
,
то есть условное распределение состояний в будущих моментах времени зависит только от состояния в настоящий момент.
Классификация состояний цепи Маркова:
·Состояние k достижимо из j, если вероятность того, что процесс через конечное число шагов будет находиться в состоянии k, при условии, что процесс стартовал из j, положительна, то есть
·Два состояния i и j называются сообщающимися, если они достижимы друг из друга , обозначают
·Состояние называется несущественным, если . Иначе - существенное.
·Возвратное состояние
вероятность того, что на n шаге процесс впервые попадет в состояние I, стартуя из состояния i.
Критерий возвратности:
- по формуле полной вероятности.
, где
·Состояние называется положительным, если M(v)<, где М(v) есть условное математическое ожидание времени первого достижения состояния i, при условии, что процесс стартует из состояния i
·Состояние называется нулевым, если М(v)=.
·Состояние называется поглощающим, если процесс сможет выйти из него с нулевой вероятностью.
Понятия случайный процесс и цепь Маркова находят применения во многих сферах, не только в теории вероятностей, а так же в экономике, теории связи, теории надежности и естествознании.
В настоящее время большой интерес вызывают управляемые процессы, в которых присутствует стратегия управления в каждом состоянии, которые принимает процесс.
Стратегией управления называют некоторое правило выбора решений из заданного множества допустимых управлений, а так же правило выбора моментов принятия решения.
Стратегия управления называется рандомизированной стратегией, если в процесс принятия того или иного управления введен случайный эксперимент, который определяется некоторой вероятностной мерой.
Стратегия управления называется детерминированной или нерандомезированной стратегией, если вероятностная мера является вырожденной. 3
Более того, стратегия может быть неупреждающей, марковской, однородной.
В этой работе используются понятия рандомезированной и вырожденной стратегии.
1.2 Теоретический материал, относящийся к теории полумарковских процессов
Марковские процессы являются частным случаем более общей модели полумарковского процесса. Дадим ему определение.
« Полумарковский процесс определяется однородной двумерной марковской цепью или однородным процессом марковского восстановления:
Однородная марковская цепь определяется переходными вероятностями, которые будем в дальнейшем называть полумарковским ядром:
» 3
В соответствии с тем, что полумарковский процесс является обобщенной моделью марковского процесса, то в нем можно ввести управление на каждом шагу.
«Управляемый полумарковский процесс X(t)={определяется однородной трехмерной марковской цепью или однородным управляемым процессом марковского восстановления:
, » 3
Задачи, в которых используются управляемые полумарковские процессы, по большей части оптимизационные, то есть необходимо определить наилучшую стратегию управления и чем она превосходит другие. С этой целью должен быть построен критерий, по которому будут определять качество работающей системы, с математической точки, в качестве данной характеристики может выступать функционал, построенный на траекториях случайного процесса. Смысл данного функционала - вычислить математическое ожидание дохода (убытка) от функционирования данной системы. Следовательно, необходимо определить оптимальную стратегию управления, которая бы доставила функционалу качества максимум (минимум).
Большинство специализированной литературы, описывающие полумарковские процессы и анализирующие задачи оптимизации, построенных на случайных процессах, выдвигают методологию решения нахождения оптимальной стратегии. Алгоритм построения оптимальной стратегии реализуется в следующем порядке. 8
1)Определение марковских моментов и множество состояний E;
)Определение множества управлений и стратегий;
)Нахождение полумарковского ядра и построение полумарковской матрицы;
)Построение функционала накопления , как математическое ожидание накопленного эффекта;
)Определение математического ожидания времени непрерывного пребывания процесса в состоянии;
)Определение математического ожидания дохода ;
)Нахождения стационарных вероятностей состояний вложенной цепи Маркова;
8)Построение функционала качества и нахождения экстремума целевого функционала и выбор оптимальной стратегии управления.
- семейство вероятностных мер, для которых выполнено
Функционал качества, удовлетворяющий системе интегральных уравнений
, где
.
По теореме о структуре функционала накопления 8
имеет дробно-линейную структуру и зависит от всех вероятностных мер , то есть
Построение оптимальной стратегии заключается в том, чтобы определить вероятностные меры , - множество допустимых стратегий, для которых
о).
Теорема. 8
«Если максимум целевого функционала по множеству допустимых стратегий управления существует, если множество вырожденных стратегий является подмножеством множества допустимых стратегий, то:
.
Равенство означает, что множество стратегий, на которых достигается экстремум дробно-линейного функционала, пересекается с множеством вырожденных стратегий.»
Кроме функционала накопления, в стохастических моделях часто используются функционалы достижения. Физический смысл их довольно прост. Пусть имеются два непересекающихся множества , назовем их подмножество «плохих» состояния и «хороших состояний» соответственно, причем , то есть, объединение дает все множество состояний E. Таким образом, функционал достижения описывает математическое ожидание стоимости (затраченного времени) до момента первого попадания в множество «плохих состояний», при условии, что процесс стартовал из множества «хороших состояний». Строится он аналогично функционалу качества, нахождением математических ожиданий стоимости переходов или затраченного времени пребывания процесса в состоянии, в зависимости от критерия, по которому строится функционал.
Эти функционалы удовлетворяют следующим системам алгебраических уравнений
(критерий стоимости);
(критерий времени).
Решение этих систем также являются дробно-линейными функционалами, экстремум которых достигается на вырожденных распределениях.
Данная работа опирается на труды, относящиеся к приложениям теории случайных процессов, в частности полумарковских, для теории надежности, массового обслуживания и др. Приведенные примеры работ выбраны по причине схожести подходов решения поставленных задач.
Сперва введем следующие понятия.
Теория надежности - наука, изучающая закономерности распределения отказов технических устройств и конструкций, причины их возникновения.
Математическая теория надежности-«общая научная дисциплина, изучающая общие методы и приемы, которых следует придерживаться при проектировании, приемке, транспортировке и эксплуатации изделий для обеспечения максимальной их эффективности в процессе использования, а также разрабатывающая общие методы расчета качества устройств по известным качествам составляющих их частей».7
Надежность-свойство изучаемого объекта сохранять в течении времени способность выполнять требуемые функции. Надежность - важный показатель качества объекта. 4
Множество работ направлены на изучении времени безотказной работы, его математического ожидания для достаточно сложных систем.
Безотказность-свойство объекта находиться в течении некоторого времени в работоспособном состоянии до частичного или полного отказа системы.
Примером использования цепей Маркова для анализа характеристик безотказности может служить работа 2.
Авторами была исследована система из n приборов, соединенных последовательно, и m приборов, находящихся в резерве, каждый из которых имеет собственные характеристики работоспособности. Более того, порядок основных приборов (начавших работу в начальный момент времени) и приборов в резерве (последовательность их подключения в работу на место основных после их отказа) в начальный момент времени фиксирован, то есть каждый прибор в начальный момент пронумерован, и ему присвоен номер k, . Отказ очередного прибора проявляется мгновенно и с вероятностью, равной единице, на его место подключают резервный элемент, при наличии работоспособных. Отказ системы происходит в момент, когда отказал элемент на месте основного, а в резерве нет работоспособных. Необходимо заметить, что элементы, которые находятся в резерве, могут отказать с положительной вероятностью, не побывав на месте основного, то есть резерв облегченный. Поэтому при расчете для k-го элемента его времени безотказной работы необходимо учитывать случайные величины - случайное время, которое данный элемент провел в резерве, другими словами, старение данного элемента.
Цель работы состоит в определении функции распределения момента отказа системы, обозначаемого через Х, F(t)=P{X<t}, и математического ожидания времени безотказной работы системы через исходные характеристики.
Очевидно, что X=, что следует из определения отказа системы - момент, когда нужно подключить следующий (n+m+1) элемент, который отсутствует. Выражая через исходные характеристики , k=n+1…n+m+1, авторы получили
)
Для вычисления функции распределения был предложен метод, основанный на рекуррентном процессе в виде неоднородной многомерной марковской цепи
- номер прибора на месте основного на шаге s, - момент подключения на место основного.
Обозначим через
условную вероятность того, что за время t>0 не потребуется включать элемент с номером (n+m+1) при условии, что начальный момент на основных местах находятся элементы с номерами , которые были подключены в моменты .
Далее вероятность (1) расписывают по формуле полной вероятности при Полученное выражение при произвольной s является искомой функцией распределения момента отказа системы.
Алгоритм завершается при s=0 по формуле P(t,(1,0),(2,0),…, (n,0))=1-F(t) поиском искомой функции.
Математическое ожидание положительной случайной величины c функцией распределения F(x) имеет вид
.
Таким образом, искомое математическое ожидание времени безотказной работы можно получить интегрированием функции распределения, полученной ранее.
Особый подход, который использовали авторы этой работы, состоит в том, что анализируется марковская цепь, а время безотказной работы рассматривается как функционал, построенный на траекториях этой цепи.
В целом, вопросы резервирования возникают в моменты, когда появляется желание увеличить надежность исследуемой системы. С этой целью резервировать можно как всю систему в целом, так и отдельные ее части: блоки и элементы.
Кроме структуры наблюдаются различия в типах резервирования: горячее, холодное и облегченное резервирование. Облегченное резервирование является промежуточным между холодным и горячим.
Каштанов В.А. 4 рассматривает задачу облегченного резервирования системы, состоящей из (n+1) элементов. В отличие от 2 в данной работе только 1 элемент находится в основном рабочем состоянии, а остальные n приборов являются резервными. Резервные элементы могут отказывать, не начиная работать на основном месте, но вероятность отказа в резерве меньше, чем вероятность безотказной работы, следовательно, резервные элементы находятся в облегченном режиме.
Введем некоторые обозначения, p(x) - надежность элемента в резерве; P(t,x) - вероятность, что элемент проработает на основном месте время до момента t при условии, что он начал работать в момент x.
Цель работы заключается в нахождении оптимального порядка подключения резерва для обеспечения максимального среднего времени безотказной работы системы.
Для функции распределения времени работы системы, имеющей (n+1) прибор, верно соотношение
(2)
По формуле (2) можно вычислить функцию распределения времени работы системы, для этого необходимо решить n раз интеграл свертки.
Для сравнительного анализа облегченного и холодного резервирования были предложены функции распределения времени работы при холодном способе резервирования.
Основная цель работы - это нахождение математического ожидания (среднего)
времени работы системы.
Известно, что
После расчётов и сравнительного анализа получилось, что относительный проигрыш облегченного резервирования по сравнению с холодным в среднем времени равен , где -интенсивности отказа в резерве и в рабочем состоянии соответственно.
Можно утверждать, что порядок включения элементов играет роль в системах, у которых есть различия в надежностях в рабочем и резервном состояниях. Приведем некоторые примеры:
)Функция надежности одинакова у всех элементов в рабочем состоянии, но положим ее произвольной функцией P(x), в то время как в резервном состоянии функции надежности у всех элементов в резерве различны и равны p(x). Если для какого-то i и j выполняется , где , значит, что надежность элемента с номером I выше, чем у элемента с номером j. Таким образом, установив цепь элементов с различными надежностями в порядке увеличения, получается, что надо сначала подключать элементы с меньшей надежностью, чтобы как можно меньше элементов выходила из строя в резерве.
)Функции надежности в резерве и в рабочем состоянии у каждого элемента различны. Для упрощения ситуации, рассмотрим при n=1. Существует только два возможных варианта: либо 0 элемент поставить на рабочее место, а 1 в резерв, либо наоборот.
)Первый вариант будет наилучшим при
Управление вводится в задачи, чтобы по возможности усложнить рассматриваемые модели и сделать их приближенными к реальным жизненным ситуациям. Управлять можно как структурой, так и техническим обслуживанием. Задачи управления структурой имеют дело с порядком подключения того или иного прибора. Задачи управление обслуживанием описываются следующие типы работ:
Рис.1 Типы восстановительных работ
Постановка задачи оптимизации технического обслуживания: «в заданном множестве разрешенных стратегий технического обслуживания определить оптимальную стратегию, для которой достигается экстремум функционала эффективности, определенного на траекториях случайного процесса, описывающего эволюцию технической системы во времени.» 8
1.3 Элементы динамического программирования
Случайные процессы и управляемые случайные процессы используется не только в инженерии и задачах надежности, но и в задачах динамического характера, который основывается на методе динамического программирования, из-за схожести методик построения искомого функционала, используемых динамическим программированием. Управляемые полумарковские процессы можно рассматривать как последовательность шагов принятия решения в некоторые моменты времени, в то время как, принцип динамического программирования, иначе говоря, это многошаговый процесс решения сложной задачи, путем разбиения ее на более простые, решая которые необходимо определить оптимальное поведение. 9
Появление метода связано с американским ученым Ричардом Беллманом в начале 50-х годов 20 столетия, который применил к ряду прикладных задач принцип максимума (оптимальности), который позже был назван его именем.
Классические задачи динамического программирования - управление запасами некоторого предприятия, распределения ресурсов, задача о «ранце», задача распределения капиталовложений и др.
Введем некоторые основные формулы и термины:
Принцип оптимальности Беллмана говорит, «что на каждом шаге следует стремиться не к изолированной оптимизации функции , а выбирать оптимальное управление , в предположении об оптимальности всех последующих шагов.» 9
Перейдем к общей постановке задачи динамического программирования:
Рассматривается управляемая система, которая в ходе переходов меняет свое состояние из начального в конечное через промежуточные состояния . Последовательное изменение шагов происходит под действием управлений где - управление на k-м шаге. Управление на каждом шаге состоит в выборе одного управления на данном шаге из множества возможных , k=1…m. Так же предполагается, что управление на k-м шаге зависит только от предыдущего состояния k-1. Такое свойство получило название отсутствие последействия.
- уравнение состояния
Рис. 2 Схема решения задачи динамического программирования
(3)
Уравнение Беллмана:
(4)
- условно оптимальный показатель оптимальности на k-м шаге.
Для построения модели динамического программирования необходимо:
)Выбрать способ деления процесса на шаги.
)Определить состояния и управления .
)Записать уравнение состояния
)Вывести показатель эффективности на каждом шаге (3).
5)Записать уравнения Беллмана (4) и решить систему.
)Определить условно оптимальные управления .
Метод динамического программирования, как итерационный метод, нередко используется для решений задач , основанных на случайных процессах.
Ховард Р.А. 12 описывает связь между последовательными итерационными методами решения задач и моделями управляемых марковских процессов.
«Случайный процесс с непрерывным временем и дискретным множеством состояний E называется марковским, если для любого целого n>0, любого набора моментов и любого набора состояний ( для условных вероятностей справедливо равенство
». 3
Автор предлагает разные подходы для нахождения оптимального управления для систем, описываемых марковскими процессами и непрерывным и дискретным временем. В данной работе представлены аналитические модели принятия оптимального решения на примерах задач управляемых и неуправляемых марковских процессов с доходами. Вводя стратегии управления, автором были предложены решения задач итерационным и рекуррентным методом.
Как можно увидеть, многие бытовые проблемы, с которыми люди сталкиваются ежедневно, можно представить в виде модели управляемого марковского процесса и применить к ним один из методов решения, и динамическое программирование используется во многих случаях.
Еще один пример использования методов динамического программирования в решении задач, основанных на марковском процессе. Подробнее обратимся к задаче о «выборе транспорта», которая решается методом динамического программирования.11
Пусть существует некоторый человек, который хочет добраться из пункта А в пункт В, и у него есть три возможности: дойти пешком, доехать на автобусе или трамвае.
Цель задачи - добраться до конечного пункта, затратив минимальное время.
Интервалы между соседними моментами прихода автобуса есть независимые, одинаково распределенные случайные величины, имеющие показательное распределение, то есть, в любое время, когда бы пассажир не пришел на остановку, вероятность прихода автобуса равна , а ждать придется время не меньше Аналогичная ситуация для трамваев, интервалы распределены по показательному закону с параметром d. Состояние В называется поглощающим.
Состояние в начальный момент времени обозначим через 0, множество управлений для этого состояния состоит из элементов: идти пешком или ждать транспорт, если путник выберем управление «ждать», то уйти уже будет нельзя.
При переходе к неоднородному случаю необходимо зафиксировать число шагов n , а также, фиксировать финальную плату в состояниях 0, С, В и D. Плата в состоянии B принимает значение 0, в остальных точках берем достаточно крупное положительное число.
Для того, чтобы выписать уравнения оптимальности, введем управления: на t-ом шаге: -идти пешком, - автобус, - трамвай, -ждать, где t=1..n.
v(0)=max
(1)
Далее решение зависит от того, чему равен x. Рассмотрены 3 случая: при x, при x.
Пропуская выкладки, осуществляется поиск простой оптимальной стратегии. Для этого необходимо задать эту стратеги только в состоянии 0 и .
Отсюда оптимальная стратегия
При
При
Таким образом, при следует идти пешком, при следует ехать на первом попавшемся транспорте, . Данный ответ показывает, что авторы доказали «пороговость» решения данной задачи, то есть существование некоторых значений, при которые необходимо принимать только 1 конкретное управление.
2. Постановка задачи
2.1 Описание задачи
Дан абстрактный управляемый полумарковский процесс, обладающий следующими свойствами: множество состояний разбиты на подмножества, которые могут быть рассмотрены как слои, и особое подмножество поглощающих состояний, находящееся вне слоев.
Цель задачи определить максимальное время до первого попадания системы в поглощающее состояние, строя функционал достижения и находя его экстремум.
2.2 Множество состояний и множество управлений
Слои пронумерованы от 0 до n+1, n-конечно. Каждый слой состоит из двух отдельных, не пересекающихся подмножеств, из каждого с разной вероятностью можно попасть в поглощающее состояния. Подмножества будут называться А и В соответственно. Множество поглощающих состояний обозначим через С.
Для каждого подмножества определено множество управлений.
Множество управлений на каждом слое:
·для нулевого слоя: , - переход в поглощающее состояние, -переход в любое из подмножеств первого слоя;
·для первого слоя: , - переход в поглощающее состояние, -переход на второй слой;
·для i-го слоя, i=1,n: ;
·для n+1-го слоя: ;
Для состояния из подмножества В (рис.4) существует только одно решение-переход в поглощающее состояние. Для состояния из подмножества А существует два решения- перейти на следующий слоев в одно их два подмножеств или перейти в поглощающее состояние.
Вероятностная мера, соответствующая каждому решению, дискретна. Вероятности принятия решения обладают стохастическим свойством, то есть =1, где i-номер слоя, j-индекс принимаемого решения. Введем следующие обозначения вероятности для каждого слоя: для нулевого слоя вероятность принятия решения вероятность принятия решения для подмножества А первого слоя вероятности аналогичны для 0 и любого другого слоя; для подмножества А i-го слоя вероятности принимают вид . Иначе выглядит вероятность для подмножества В любого уровня, так как для него множество управлений состоит только из одно управления, поэтому вероятность принятия решения равна 1. Далее предлагается схема работы этой системы.
Рис. 4 Граф переходов полумарковского процесса
.3 Полумарковское ядро
Для описания модели необходимо ввести переходные вероятности или полумарковские ядра По определению, полумарковское ядро - это условная вероятность перехода в состояние j за время, меньшее времени t, при условии, что процесс стартовал из состояния I и было принято решение u.
Для данного специфического полумарковского процесса существует следующие переходы и соответствующие полумарковские ядра:
Из любого состояния слоя «0» существуют переходы в состояние из множества поглощающих при выборе управления , С - подмножество поглощающих состояний. Запишем ядро в вероятностных терминах:
Пусть процесс пронимает на некотором шаге k случайную величину , тогда вероятность будет иметь следующий вид
Кроме того, также существуют переходы из любого состояния из «0» в два подмножества А и В слоя «1» при выборе управления со следующими переходными вероятностями: , -подмножество А слоя «1», либо ;
Из подмножества существуют и возможны переходы в поглощающее состояние при выборе управления c ядром , . Следовательно, при выборе управления процесс может перейти в одно из состояний следующего слоя, принадлежащего либо подмножеству либо , а ядро принимает вид , .
Аналогично строятся остальные полумарковские ядра для всех слоев, так как множества управлений и возможные переходы однотипны для остальных слоев.
Строки матрицы можно представить в виде таблицы:
Таблица 1. Полумарковское ядро
0 0 0 000 0 0 0 0 0 0 0 000 0 000 0
2.4Построение функционала, определяющий функционал достижения
Следующий шаг алгоритма построения модели -функционал , а именно, условного математического ожидания накопленного эффекта между соседними моментами изменения состояния, при условии, что процесс прибывал в состоянии i, перешел в состояние j, время перехода равно t, было принято решение u.
Для приближения задачи к реальной, можно дополнительно ввести параметры, отвечающие за стоимость перехода из одного состояния в другое:
·Если достигается состояние подмножества поглощающих состояний из подмножества А, то система платит eд./ в ед. времени;
·Если достигается состояние подмножества поглощающих состояний из подмножества В, то система платит eд./ в ед. времени;
·Если достигается состояние подмножества А из подмножества А предыдущего слоя, то система платит eд./ в ед. времени;
·Если достигается состояние подмножества В из подмножества А предыдущего слоя, то система платит eд./ в ед. времени;
·Если достигается состояние подмножества поглощающих состояний из подмножества «0» слоя, то система платит eд./ в ед. времени;
Далее записываем функционал. Пусть - случайная величина длительности перехода из состояния «0» слоя в состояние подмножества А первого слоя при выборе управления , - случайная величина длительности перехода из состояния «0» слоя в состояния подмножества В первого слоя, - случайная величина длительности перехода из состояния слоя «0» в подмножество поглощающих состояний. Тогда функционал, описывающий переход из состояния «0» слоя в состояние подмножества А первого слоя, принимает вид
,
По определению математическое ожидание непрерывной величины записывается в виде: .
(1)
Функционал, описывающий переход из состояния «0» слоя в состояние подмножества В первого слоя, принимает вид
(2)
Для функционала, описывающего переход в поглощающее состояние справедливо
,
(3)
Для остальных слоев функционалы будут записываться аналогично. Осталось только записать функционалы для перехода в поглощающие состояния.
Пусть - случайная величина длительности перехода из состояния подмножества А в поглощающее состояние, - случайная величина длительности перехода из состояния подмножества В в поглощающее состояние.
Функционал накопленного эффекта за время перехода из состояния подмножества А любого слоя в поглощающее состояние можно записать
, (4)
Функционал накопленного эффекта за время перехода из состояния подмножества В любого слоя в поглощающее состояние можно записать
, (5)
2.5Функционал достижения
Функционал достижения определяется как математического ожидание стоимости процесса до первого попадания в поглощающее состояние, при условии, что процесс стартует из любого состояния j любого слоя.
Функционал достижения описывает математическое ожидание времени до первого попадания в поглощающее состояние, при условии, что процесс стартует из любого состояния j нулевого слоя.
Найдя данный функционал и используя теоремы, описанные в гл. 1.2., появляется возможность нахождения max или min данного функционала, а затем определить оптимальные управления, на которых доставляют экстремум функционала.
Для построения функционала необходимо еще определить переходные вероятности, которые определяются по следующему правилу:
Принимая допущение, что функционал достигает максимума на вырожденных распределениях, тогда переходные вероятности принимают вид
(6)
Из этой формулы определяем все вероятности, находя предел соответствующего полумарковского ядра, устремляя время к бесконечности.
Для получения итогового выражения для функционала достижения не хватает только математического ожидания дохода, для которого верно
(7)
И благодаря формулам (1)-(7), появилась возможность определить функционал достижения
,-множество всех состояний, исключая поглощающие.
Для понимания процесса можно с легкостью утверждать, что функционал достижение по критерию стоимости имеет такой же физический смысл, как и функционал достижения по критерию времени, поэтому функционал строится аналогично.
Для построения функционала достижения, найденному по критерию времени, необходимо знать следующие значения: математического ожидания непрерывного пребывания процесса в фиксированном состоянии, для которого справедлива формула
,
а также, переходные вероятности.
Тогда функционал достижения по критерию времени принимает вид
кроме поглощающих.
Для использования теоремы о достижении максимума дробно-линейного функционала на вырожденных распределениях необходимо доказать, что найденный функционал достижения имеет дробно-линейную структуру. Для этой цели привлекаем теоретические основы линейной алгебры и применяем метод Крамара для решения системы линейных уравнений. Решение данной системы очень трудоемкое, даже при маленьком числе слоев: необходимо перебирать все возможные вырожденные распределения для поиска максимума, но использование принципа динамического программирования как метод решения системы линейных уравнений заметно облегчает задачу. Как показывает теория, решать систему функционалов принято с последнего слоя, где i=n+1, для которого функционал имеет только одно слагаемое и может быть легко найден, далее подставляется значение найденного функционала в предпоследнее уравнение для i=n и продолжаем, доходя до слоя с номером «0». Такие операции стоит проделать для всех возможных распределений на каждом слое и дойти до нахождения максимума.
Построенную модель полумарковского процесса можно проиллюстрировать на примере, рассмотренном в гл.1.3.
2.6Пример использования построенной модели
Вернемся к задаче о выборе транспорта. Можно рассмотреть очередной трамвай как слой полумарковского процесса. Следовательно, появляется возможность для построение системы функционала достижения, используя весь теоретический материал, описанный в прошлом пункте. В отличии от рассмотренной задачи, описанной Дынкиным и Юшкевичем, задача, которая будет рассчитываться тут, будет иметь другие параметры, а именно, интервалы времени между соседними приездами трамвая будут иметь произвольную функцию распределения, обозначенную G(x), для сохранение марковских свойств интервалы времени между соседними автобусами распределены по экспоненциальному закону с параметром время, затраченное на поездку на каждом виде транспорта, обозначаются .
Выполнение всех шагов алгоритма:
)Множество состояний:
Множество состояний состоит из слоев, которые совпадают с номером пришедшего трамвая, более того, каждый слой разбит на два непересекающихся подмножества, которые могут быть рассмотрены, как подмножество, отвечающее приезду трамвая, и подмножество, отвечающее приезду автобуса. Из каждого подмножества любого слоя существует вероятность перехода в поглощающее состояние. Состояния можно записать иначе: «0» - состояние в начальный момент времени, когда человек только приходит на остановку, «а» - приезд автобуса, «k» - приезд k-го трамвая, k=1…n.
)Множество управлений:
Множество управлений на каждом шаге записывается следующим образом:
·для нулевого слоя: , - идти пешком, -остаться ждать на остановке;
·для первого слоя: , -уехать на трамвае, -остаться ждать;
·для i-го слоя, i=1,n: ;
·для n+1-го слоя: ;
Вероятностная мера дискретна. Введем следующие обозначения: для первого слоя: - вероятность того, что было принято решение идти пешком, - вероятность того, что было принято решение остаться ждать на остановке; для первого слоя: - вероятность того, что было принято решение уехать на первом трамвае, - вероятность того, что было принято решение остаться ждать. Аналогично, строятся и остальные вероятности для остальных слоев.
Рис. 5 Граф переходов в задаче «о выборе транспорта»
Пропуская выкладки по построение полумарковского ядра и остальных функций, обязательных для нахождения функционала достижения, запишем сразу систему.
Для проверки применимости теоремы о вырожденности необходимо доказать, что функционал достижения имеет дробно-линейную структуру. С этой целью система (8) преобразуется в выражение вида , где - матрица размерности (n+1)x(n+1), - вектор размерности (n+1)x1. Тогда по методу Крамера получается
, , …, ,
где - определитель матрицы В, - определитель матрицы, в котором k-ый столбец заменен на вектор C.
Перебирая все вырожденные распределения и решая систему с каждым набором, находим минимальное (максимальное) время, за которое возможно добраться до конечного пункта назначения.
2.7Численный пример
Пример из гл. 2.6 является модификацией задачи, рассмотренной Дынкиным и Юшкевичем 11, в которой были введены некоторые допущения относительно времени, затраченного на путь тем или иным транспортом, а также были взяты функции распределения интервалов между соседними приходами автобуса таким образом, чтобы облегчить вычислительную часть задачи. В данной работе эти параметры были взяты, как некоторые числовые константы, а функции распределения интервалов между соседними моментами прихода транспорта были взяты экспоненциальным распределением для автобуса и произвольным распределением для трамвая.
Чтобы проиллюстрировать то, что модель и расчеты для нее верны, предоставлена программа, реализованная на языке СИ++.
Благодаря ей, решается система уравнений (8), только с некоторыми поправками:
в качестве функции распределения времени между соседними моментами прихода трамвая была взята функция распределения Эрланга 2-го порядка с параметром .
Таким образом, систему (8) можно переписать с данными замечаниями:
А временные константы и количество слоев задаются пользователем программы самостоятельно.
рис. 6 Интерфейс пользовательской программы
Программа реализует алгоритм, который, пользуясь методом динамического программирования, решает систему уравнений и на выходе выдает ответ в виде минимального времени, потраченного путником на дорогу, и оптимальную стратегию. Выбирая различные параметры времен, можно определить «пороговое» значение.
Рис. 7(а) Пример вывода программы рис.7(б)
Рис.7(а) иллюстрирует, что при таком выборе параметров, путнику выгоднее всего дождаться первого трамвая и уехать на нем, не дожидаясь приезда автобуса. Как показывают дальнейшие вычисления, этот показатель является пороговым, то есть если время поездки на трамвае будет в рамках 0,30, то всегда стоит выбирать первый трамвай. Как только времена, затраченное на путь автобусом и трамваем выравнивается, то необходимо выбирать автобус, как показано на рис. 7(б). Ответ кажется очевидным, но программа доказывает это математически, поменяв количество слоев и параметр, ответ поменяется значительным образом. Манипулируя таким образом входными данными, можно определять «пороговые значения для любого выбранного параметра «время на автобусе».
Заключение
В данной работе были проанализированы достижения математики в теории полумарковских процессов, так же была проанализирована связь управляемых полумарковских процессов и динамического программирования, схожести их методов решения и возможность комбинирования этих методов.
Так же была предложена модель управляемого полумарковского процесса, множество состояний которого было разбито на слои. Для иллюстрации применения данной модели была модернизирована задача о выборе транспорта 11, а для нахождения решения данной задачи была подготовлена программа, реализованная на языке программирования СИ++. Результаты подтвердили предположение о наличия «порога», который легко вычислим при реализации программы.
Список литературы
1. Гнеденко Б.В. Очерк по истории теории вероятностей. изд. Эдиториал УРСС, 2001. ISBN: 5-8360-0395-5.
. Каштанов В.А., Медведев А.И. Алгоритм вычисления характеристик безотказности резервированной системы. Вопросы теории безопасности и устойчивости систем. Выпуск 4. изд. Вычислительный центр им. А.А.Дородницына РАН,2002. ISBN:5-201-09783-9
. Каштанов В.А. Элементы теории случайных процессов. Учебное пособие. М: Московский государственный институт электроники и математики, 2010. С.113с.
. Вентцель Е. С. Исследование операций. М.: Советское радио, 1972. С.552.
. Каштанов В.А. Об одной задаче резервирования. Вопросы радиоэлектроники. Серия общетехническая №23, 1962.
.Гнеденко Б.В., Беляев Ю.К., Соловьев А.Д., Математические методы в теории надежности: Основные характеристики надежности и их статистический анализ. М.: Изд.2-е, испр. и доп. Книжный дом «ЛИБРОКОМ», 2013. С.584.
. Каштанов В.А., Зайцева О.Б. Исследование операций. Линейное программирование и стохастические модели. Учебник. Изд.: Курс, 2016. ISBN: 978-5-906818-78-2
Приложение
Текст программы:integralType1(double Lambda, double Sa);integralType2(double Lambda, double Sn);calculate(double Tfoot, double Tbus, double Ttram, double Lambda, int N);calculate(double Tfoot, double Tbus, double Ttram, double Lambda, int N)
{SN+1; //массив Sn, N+1 значение от 0 до NpN+12; //двумерный массив, хранящий матрицу P
//последнее уравнение(Ttram < integralType1(Lambda,Tbus))
{= Ttram;= 0;= 1;
}
{= integralType1(Lambda,Tbus);= 1;
pN2 = 0;
}
//цикл по количеству уравнениям от (N-1)-го до 1-го
for(int i = N-1; i >= 0; i--)
{(Ttram < integralType1(Lambda,Tbus)+integralType2(Lambda,Si+1))
{= Ttram;= 0;= 1;
}
{= integralType1(Lambda,Tbus);= 1;= 0;
}
}
//первое уравнение(Tfoot < integralType1(Lambda,Tbus)+integralType2(Lambda,S1))
{= Tfoot;= 0;= 1;
}
{= integralType1(Lambda,Tbus)+integralType2(Lambda,S1);= 1;= 0;
}S0;
}integralType1(double Lambda, double Sa)
{3*Sa/4 + 1/(2*Lambda);
}integralType2(double Lambda, double Sn)
{(1+Lambda*Sn)/(4*Lambda*Lambda);
}