Тема 1. Марковские процессы. Уравнение Чепмена-Колмогорова. Эргодичность

Тема 1. Марковские процессы. Уравнение Чепмена-Колмогорова. Эргодичность.

Введем следующие обозначения: пусть пространство состояний состоит из чисел   Pij 0 1 2 3 i j n-1 n …

Тема 2. Метод Z-преобразования для анализа марковських процессов.

Рассмотрим функцию

 

– это время.

 

-3 -2 -1 0 1 2 3

Z-преобразованием функции f (производящей функцией) называют функцию , при условии, что этот ряд сходится.

Для каждой функции f(n) ее Z-преобразование определяется однозначно и по Z-преобразованию функции можно однозначно восстановить саму функцию.

Свойства -преобразования

1)

2)

3) Рассмотрим функцию единичного скачка

 

4)

– число

 

 

5)

 

6)

 

 

Метод Z-преобразований для анализа марковских процессов

(1)

 

Обозначим –Z-преобразование вектора (Z-преобразование берется покомпонентно: ).

Возьмем Z-преобразование от обеих частей равенства (1).

E – единичная матрица, I=E.

 

(2)

 

А). Из примера 1.

 

 

 

 

 

 

Обозначим H(n) – обратное Z-преобразование матрицы .

 

 

Берем обратное преобразование равенства (2).

 

Рассмотрим 2 случая.

1) Первый случай.

 

 

2) Второй случай (когда мастер начинает с неудачной игрушки).

 

Замечание. Компонента H(n) содержит по крайней мере одну стохастическую матрицу (обозначим ее через S), которая называется стационарной компонентой или стационарной составляющей.

Для r-годических процессов строки этой матрицы равны.

Вторая составляющая H(n) – это сумма одной или нескольких матриц, умноженная на числа вида . Обозначим эту компоненту через T(n). Ее называют переходной составляющей.

Сама матрица из T(n) называется дифференциальной и характеризуется тем, что сумма элементов каждой строки равна нулю.

 

 

 

Тема 3. Марковські процессы с доходами.

  Чему равен ожидаемый доход за шагов, если мы находимся в состоянии i? – ожидаемый доход за шагов, если мы находимся в состоянии i. Если рассматривать , то

Преобразований.

– ожидаемый доход за шагов, если мы начинаем из состояния i.

– вектор полных ожидаемых доходов.

– Z-преобразование, примененное к i-й компоненте.

 

Применяем Z-преобразование к обеим частям последнего равенства

 

– обратное преобразование к Z-преобразованию такого выражения

 

– асимптотические выражения для полных ожидаемых доходов.

Тема 5. Процессы последовательных решений. Рекуррентный метод.

Пример с мастером игрушек.

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

 

 

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

 

Увеличение затрат на исследование (если мастер на данный момент имеет неудачную игрушку) повышает вероятность получения удачной игрушки, то при этом возрастает и стоимость пребывания в данном состоянии.

 

Если имеется система с N состояниями, то, если мы находимся в состоянии 1 и используем 1-ю стратегию, соответствующие вероятности переходов в каждое из N состояний будут равны соответственно .

Если находимся в состоянии 1 и исп. 2-ю стратегию, то вероятности переходов:

стратегия :

2:

В состоянии N:

N:

Каждой вероятности соответствует доход .

 

 

Состояния i	Стратегия k	Вероятности переходов	доходы	Непосредственно ожидаемый доход
1 (удачная игрушка)	1 (без рекламы)	0,5	0,5
2 (с рекламой)	0,8	0,2
2 (неудачная игрушка)	1 (без исследований)	0,4	0,6		-7	-3
2 (с исследованиями)	0,7	0,3		-19	-5

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

– номер стратегии, выбираемой в состоянии i, в котором будет использоваться, если осталось шагов.

Поведение определено или решение найдено, если для всех i и задана величина .

Введем величину – полный ожидаемый доход за шагов при оптимальном поведении, если мы находимся в состоянии i.

 

Предположим, что для количества оставшихся шагов оптимальные стратегии найдены, т.е. максимизированы величины

 

Как же максимизировать доход на шаге?

и найти .

Воспользуемся рекуррентным соотношением: если в i-м состоянии воспользоваться стратегией k, то ожидаемый доход за шаг будет составлять:

 

Чтобы эта величина была максимальна, нужно рассмотреть все стратегии k и взять максимум:

 

Это рекуррентное соотношение для полных доходов при оптимальном поведении.

 

 

 

					…
			8,2	10,22	…
		-3	-7,7	0,23	…
	–				…
	–				…

Это был рекуррентный метод, который позволяет вычислить стратегии за небольшое количество шагов.

 

 

Тема 6. Ітераційний метод.

 

N, P, R.

Рассмотрим эргодический процесс.

 

– вектор ожидаемых доходов за 1 шаг.

– средний ожидаемый доход за 1 шаг.

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

Определение весов.

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

удовлетворяет рекуррентным соотношениям.

 

N уравнений, неизвестных и (их N+1).

В каждом из этих уравнений к величине прибавим константу a.

 

Полагаем одну из неизвестных .

 

Получаем систему из N уравнений с N неизвестными. Можно показать, что эта система имеет одно решение.

Набор , найденный из системы уравнений, называется относительными весами.

В случае, когда имеется всего два состояния

 

Улучшение решения.

На шаге оптимальную стратегию в i-м состоянии можно найти, максимизируя выражение

 

Итерационный цикл

Определение весов Используя и , для данного решения найти прибыль и из системы уравнений , положив .

Улучшение решения Для каждого состояния i,используя относительные веса предыдущего решения, найти стратегию , которая максимизирует критерий . Затем принять эту стратегию за новую стратегию в i-состоянии заменить на и .

Начинают итерационный цикл со второго блока, полагая все .

Свойства итерационного метода

2) Каждое следующее решение, находящееся с помощью итерационного цикла имеет большую прибыль, чем предыдущее. 3) Итерационный цикл будет окончен при получении решения, которое обеспечивает… Пример. С помощью итерационного метода решить задачу мастера игрушек.

Тема 7. Задача про оптимальну зупинку.

Пусть работа системы моделируется цепью Маркова со множеством состояний и матрицей вероятностей перехода P.

Предположим, что человек имеет возможность наблюдать траекторию цепи, т.е состояния i в дискретные моменты времени . Если в момент времени человек останавливает работу системы и при этом система находилась в состоянии i, то он получает доход f_i.

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

Какого правила следует придерживаться человеку, если он хочет получить максимальный доход? Такое управление называется управлением по остановке, т.е. в каждом состоянии i и на каждом шаге возможны 2 стратегии:

1 – остановка

2 – продолжение.

i

j

0 1 2 3 4 fi fj

В сост. возможны 2 случая:

1) остановить процесс и получить плату или доход f_i.

2) заплатить сумму и продолжить процесс дальше

Во 2-й момент времени те же самые возможности.

Когда следует остановить такой процесс:

1-й случай: когда конечный промежуток времени T. Возможность остановить процесс до момента времени .

2-й случай: бесконечный промежуток времени, бесконечный горизонт времени.

1) конечный горизонт управления.

– оптимальный ожидаемый доход, если мы сейчас находимся в состоянии i и нам предстоит сделать шагов.

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

 

Каждому можно поставить в соответствие разбиение множества всех состояний S на два подмножества.

,

где – множество всех состояний, таких что

,

– множество всех состояний, таких что

 

, – разбиение множества S при оптимальном поведении.

Решается соотношение (*) методом обратной индукции.

 

Если т.е. {систему в i-м состоянии за 1 шаг до конца работы требуется остановить}

Если

 

Если

Если .

Свойства оптимальных управлений и оптимальных доходов

  2) для всех последовательность оптимальных значений полных ожидаемых… .

Задача

Рассматривается процесс случайного блуждания с поглощающими экранами и доходами.

1 2 3 4 5

½ ½

f1=1 f2=0 f3=2 f4=3 f5=0 1 ½ ½ ½ ½ 1

Требуется найти оптимальное управление по установке, если горизонт управления конечный и .

 

 

 

i
			1,5	1,5	1,625	1,625	1,65625
				2,25	2,25	2,3125	2,3125
	или

 

 

 

Предположим, что .

 

i
	или

 

 

ДЗ: при

 

Бесконечный горизонт управления

  – N неизвестных, N уравнений. .

Тема 8. Управление запасами при случайном потреблении.

– полный ожидаемый доход за шагов при оптимальном управлении, если мы находимся в состоянии i. Рекуррентное соотношение для полных ожидаемых доходов:  

Бесконечный горизонт управления

 

Алгоритм нахождения и состоит из 2-х блоков.

1) для заданных значений находим стратегии , максимизирующие выражение

– блок улучшения управления.

2) блок оценки управления: при найденном составляем систему для нахождения новых .

 

K_in^*=(2,1,0) – совпадает с решением в случаи конечного горизонта управления.

 

Модуль 2

 

Тема 1. Управляемые случайные последовательности.

  Заметим, что более естественное определение процесса, при котором состояние в… При определении случайного управления процесса будем считать, что распределение состояний процесса в момент t зависит…

Тема 2. Оптимальное управление.

. Стратегии управления такого вида называются нерандомизированными. Функции также - измеримы. Если заданы управляемый процесс и стратегия управления, то определена… (1)

Тема 3. Управляемые цепи Маркова. Уравнение Беллмана.

Аддитивная стоимость управления. Управление Беллмана.Будем предполагать, что для всех задана функция , определяющая затраты на управление на… . (9) Пусть есть цена управления, если начальное положение процесса совпадает с х. Рассмотрим теперь ту же управляющую…

Тема 4. Оптимальная остановка цепи Маркова.

а) У п р а в л е н и е д л я ц е н ы у п р а в л е н я. Предположим сначала, что процесс рассматривается лишь при . Тогда и моменты остановки … . Если фиксированная величина , то , где на множестве есть момент остановки для цепи . Инфинум этого…

Тема 5. Задача про оптимальное распределение ресурсов. Задача про распределение

Ставок в игре.

Пусть инвестор вкладывает имеющиеся средства как в рисковые активы (например, в акции) так и в безрисковые (например, на банковский счёт). Тогда… В дальнейшем будем предполагать, что величина банковского счёта меняется по… Рассмотрена следующая задача. Инвестор на момент времени n свой капитал делит следующим способом: долю отводит на…

Нахождение оптимального управления

Искать оптимальное управление будем методом, описанным в книге [1]. Перепишем (2) в виде: (3)

Тема 6. Задача о продаже сигарет (управление запасами).

 

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

 

Теперь нам нужно определить стоимость. Пусть затраты на получение у оптового продавца одной партии, состоящей из N пачек, равны , где

 

Таким образом, считаем, что — цена пачки, a — стоимость заказа с доставкой, вне зависимости от размера заказа. Пусть доход, получаемый продавцом от продажи одной пачки, равен а, так что пачка продается по цене . Предположим также, что если у продавца вечером осталось у пачек, то связанные с этим затраты равны , причем имеет, например, вид

 

Здесь — затраты на каждую пачку из имеющегося в наличии товара, которые зависят от таких факторов, как стоимость хранения, сохранность товара, и от того, что вложенный капитал можно было бы использовать по-другому. Стоимость , связанная с отрицательными значениями запаса, возникает, когда спрос превышает первоначальный запас товара. Для простоты будем считать, что спрос всегда удовлетворяется, так что отрицательный запас соответствует ситуации, когда продавец удовлетворяет спрос из побочного источника (например, купив у другого торговца); при этом — дополнительный расход на каждую пачку, если удовлетворять спрос таким образом. Ситуация, когда запас не может принимать отрицательных значений и превышающий спрос должен просто оставаться неудовлетворенным, несколько сложнее, но и ее можно рассмотреть с помощью излагаемых здесь методов.

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

(*)

где математическое ожидание берется относительно спроса . Соотношение (12.3.4) выводится сравнением доходов и расходов в течение дня: стоимость хранения с предыдущего вечера равна ; затраты, связанные с получением утром у оптового торговца товара, равны ; доход , полученный в течение дня, а вечером у продавца остается запас и только дней на реализацию. Мы должны усреднить по , которое неизвестно к моменту, когда выбирается величина заказа . Оптимальным заказом будет значение , максимизирующее математическое ожидание в (*).

Теперь функциональное уравнение (*) можно решать, начиная с , последовательно для и по ходу дела, определять максимизирующие функции .

 

Тема 7. Задача о замене оборудования.

 

Рассмотри задачу о замене автомобиля в течение 10-летнего периода его эксплуатации. Будем осматривать машину каждые три месяца и принимать решения о том, использовать ли ее дальше или произвести замену. Состояние системы i описывается возрастом машины в 3-х месячных периодах при (более 10лет). Если i=40, то машина достигла своего состояния изношенности. В каждом состоянии допускаются следующие стратегии:

состоит в том, чтобы эксплуатировать машину до следующего осмотра

другие предполагают приобретение машины в возрасте

40 состояний, 41 стратегия.

Решений существует .

Заданы следующие величины:

– покупная цена машины возраста .

– выручка от продажи машины возраста

– расходы, связанные с эксплуатацией машины возраста в течение одного периода

– вероятность того, что машина возраста выживет до возраста , не проходя капитального ремонта.

Возраст	Покупная цена	Выручка	Расходы	Вероятность выживания	Стратегия ( g*=-150,99)
				1,000	–
				0,999
				0,998
				0,997	Эксплуатировать
				0,996
				0,994
				0,991
				0,988
				0,985
				0,983
				0,980
				0,975
				0,970
				0,965
				0,960
				0,955
				0,950
				0,945
				0,940
				0,935
				0,930
				0,925
				0,919
				0,910
				0,900
				0,890
				0,880
				0,865
				0,850
				0,820
				0,790
				0,760
				0,730
				0,660
				0,590
				0,510
				0,430
				0,300
				0,200
				0,100

 

Величина

При

 

Окончательные результаты: машину следует продолжить эксплуатировать, если ее возраст больше, чем 0,5 года, но меньше 6,5 лет. Машину любого другого возраста нужно заменить автомобилем 3-х летнего возраста.