Краткие теоретические сведения

↑

▷ Содержание

⇐ ПредыдущаяСтр 3 из 3

Краткие теоретические сведения

Постановка задачи и описание метода решения

Пусть некоторая система (сбыт, потребление, здоровье, плодородие, комнатная температура и пр.) в любой фиксированный момент t может находиться в одном из n состояний и перейти из этого состояния в любое другое. Пусть вероятность Pt(i,j) перехода в момент t из i-го состояния в j-е не зависит от предыстории системы. Такая система называется марковской. Если вероятности перехода не зависят от времени, марковская система обладает свойством стационарности, т.е. функция Xt(j) вероятности нахождения системы в момент t в j-ом состоянии при t®Ґ асимптотически сходится к функции X(j), удовлетворяющей уравнениям:

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

Предположим, что вероятности перехода зависит от некоторой политики (выбора) q и переход сопровождается получением некоторого благоприятного эффекта Ri j(q).

Обозначим через Fk(i) ожидаемый эффект функционирования системы, находившейся в начальный момент в i-м состоянии, за k периодов при использовании оптимальной политики. Руководствуясь принципом оптимальности, требующим независимо от начального состояния i и от начального выбора q далее действовать оптимально, т.е. гарантировать максимум ожидаемого эффекта в последующем процессе, приходим к рекуррентным соотношениям вида:

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

Fk (i) = Fi + k G , ( 2 )

где G - средний эффект за период и Fi -составляющая суммарного эффекта, определяемая начальным состоянием. Подставляя (2) в (1) и учитывая

которую можно решать приближением в поведениях. Приведенную систему можно получить, если записать уравнение для бесконечношагового процесса с учетом дисконтирования, положить величину дисконтированного эффекта равной Fi + G/(1-a) и принять a = 1 .

5.2. Пример решения задачи

Для иллюстрации марковского процесса принятия решений рассмотрим "задачу о такси" .

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

Для каждого города ( i ) и каждого выбора ( q ) известны вероятности поездки в тот или иной город и соответствующие доходы, сведенные в таблице:

Возьмем за начальное поведение q0 = (1, 1, 1), т.е. во всех городах будем придерживаться первого выбора. Для выбранного поведения стро-им систему n уравнений с n+1 неизвестными

разрешимую с точностью до константы. Для нашего примера :

F1 + G = 1/2 [ 10 + F1 ] + 1/4 [ 4 + F2 ] + 1/4 [ 8 + F3]

F2 + G = 1/2 [ 14 + F1] + 1/2 [18 + F3]

F3 + G = 1/4 [ 10 + F1 ] + 1/2 [ 2 + F2 ] + 1/4 [ 8 + F3 ]

Полагая, например, F3 = 0, получаем F1 = 4/3, F2 = 7.47 и G = 9.2, т.е. выбранная политика дает средний доход за одну поездку, равный 9.2.

Вычисляем

при всех i и q и найденных значениях Fi:

T1(1) = 1/2 [10+4/3 ] + 1/4 [ 4+7.47 ] + 1/4 [ 8+0 ]

T1(2) = 1/16 [ 8+4/3 ] + 3/4 [ 2+7.47 ] + 3/16 [ 8+0 ]

T1(3) = 1/4 [ 4+4/3 ] + 1/8 [ 6+7.47 ] + 5/8 [ 4+0 ]

T2(1) = 1/2 [14+4/3 ] + 1/2 [18+0 ]

T2(2) = 1/16 [ 8+4/3 ] + 7/8 [16+7.47 ] + 1/16 [ 8+0 ]

T3(1) = 1/4 [10+4/3 ] + 1/2 [ 2+7.47 ] + 1/4 [ 8+0 ]

T3(2) = 1/8 [ 6+4/3 ] + 3/4 [ 4+7.47 ] + 1/8 [ 2+0 ]

T3(3) = 3/4 [ 4+4/3 ] + 1/16 [ 0+7.47 ] + 3/16 [ 8+0 ].

Выбирая максимальное из значений Ti(q) по q, получаем улучшенное поведение q =(1, 2, 2). Строим и решаем систему уравнений:

F1 + G = 1/2 [ 10 + F1] + 1/4 [ 4 + F2 ] + 1/4 [ 8 + F3 ]

F2 + G = 1/16 [ 8 + F1] + 7/8 [16 + F2 ] + 1/16 [ 8 + F3]

F3 + G = 1/8 [ 6 + F1] + 3/4 [ 4 + F2 ] + 1/8 [ 2 + F3] ,

получая F3 = 0, F2 = -3.88, F1 = 12.85, G = 13.15.

Попытка дальнейшего улучшения дает политику q =(2, 2, 2), для которой F3 = 0, F2 = -1.18, F1 = 12.86, G = 13.34. Очередная попытка улучшения приводит к той же политике, откуда напрашивается вывод о том, что оптимальная политика состоит в использовании второго выбора во всех городах и обеспечивает средний ожидаемый доход за одну поездку, равный 13.34.

Познавательные статьи:



Техника прыжка в длину с разбега

Организация работы процедурного кабинета

Области применения синхронных машин

Оптимизация по Винеру и Калману