Теория случайных процессов (1042226), страница 8
Текст из файла (страница 8)
сведемв табл. 8.1, а графики функций vi (n) приведем на рис. 23.n0v1 (n)0v2 (n)014Т а б л и ц а 8.15→∞2367,58,559,55510,5555→∞−3−2, 4−1,44−0,4440,5556→∞vi (n)10v1 (n)5v2 (n)045◦n−5Рис. 23Из таблицы и графиков видно, что если n → ∞, тоv1 (n), v2 (n) → ∞, v1 (n) − v2 (n) → 10, vi (n) − vi (n − 1) → 1,i = 1, 2.В [1] эти экспериментальные результаты теоретически обоснованы. Аналогами соотношений (8.1)–(8.3), учитывающимиприведение будущих доходов к текущему времени, являются57Лекция 8. Дискретные цепи Маркова с доходамиviβ (n) =NXj=1pij [rij + βvjβ (n − 1)] ⇒⇒ viβ (n) = qi + βNXj=1pij vjβ (n − 1) ,i = 1, 2, ...
, n ⇒⇒ Vβ (n) = Q + βP Vβ (n − 1) ,Vβ (0) = 0, (8.4)где β (0 < β 6 1) — коэффициент переоценки (КП): по определению доход в один рубль, полученный через n лет, эквивалентенβ n рублям в настоящий момент.Пример 8.2. Продолжим рассмотрение примера 8.1, полагая β = 0,5 и используя соотношение (8.4). Результаты сведеныв табл.
8.2.Т а б л и ц а 8.25→∞n01234v1β (n)066,757,017,147,2v2β (n)0−3−2,46−2,34−2,27−2,77,266−2,211В отличие от табл. 8.1 величины viβ (n) имеют конечныепределы, которые далее будут исследованы теоретически. Всюдув дальнейшем предполагается, что β < 1; случай β = 1 достаточно подробно рассмотрен в [1].Асимптотика полного ожидаемого доходаВ результате n-кратного применения формулы (8.4) получаемVβ (n) = Q + βP V (n − 1) = Q + βP (Q + βP V (n − 2)) == Q + βP Q + (βP )2 V (n − 2) == Q + βP Q + (βP )2 (Q + βP V (n − 3)) == Q + βP Q + (βP )2 Q + (βP )3 Q + ... ++ (βP )n Vβ (0) =n−X1i=0(βP )i Q. (8.5)58Разд. 2.
Дискретные цепи МарковаОтсюда следует формула для так называемого предельногодоходаVβ∞ = lim Vβ (n) =n→∞∞Xi=0(βP )i Q = (1 − βP )−1 Q < ∞.(8.6)Здесь мы воспользовались леммой об обратной матрице (доказательство см. [1, прил. 5]).Пример 8.3. Продолжим рассмотрение задачи руководителя фирмы (примеры 8.1 и 8.2) и вычислим предельный доход.При β = 0,5 имеем!!0,50,50,250,25Pb = βP = 0,5=⇒0,4 0,60,20 0,30⇒ I − Pb =0,75 −0,25−0,20 0,70⇒ Vβ∞ = I − Pb −1!−1=⇒ I − Pb1,474 0,5260,421 1,579!⇒!1,474 0,5266Q==−30,421 1,579!7,266=⇒ см.
табл. 8.2.−2,211Управляемые дискретные цепи Маркова с доходамиДЦМ с доходами называется управляемой, если на каждом шаге n процесса функционирования системы и в каждомсостоянии i = 1, 2, ... , N человекможет по своему усмотрениювыбрать строку МВП pki i = pik1i , ... , pkiNi и строку МОД riki =ki= rik1i , ...
, riNиз множества заданных. Величина ki называетсястратегией управления в i-м состоянии, Ki = {ki } — множество стратегий управления в i-м состоянии, |Ki | < ∞. Вектор стратегий k = (k1 , k2 , ... , kN ) называется политикой. Еслистратегия или политика выбираются на n-м шаге, то ki или kснабжаются индексом n: kin или kn = (k1n , k2n , ...
, kN n ). Последовательность выбранных на каждом шаге политик образуетЛекция 9. Оптимальное управление на конечном горизонте59управление k = k 1 , k2 , ... , однозначно определяющее функционирование системы. Пусть nmax — продолжительность горизонтауправления. Если nmax < ∞, то говорят о конечном, если nmax == ∞, то говорят о бесконечном горизонте управления.Для управляемых ДЦМ с доходами ПОД на горизонте продолжительностью nmax принято обозначать Vβ (nmax , k) , тогдазадача оптимального управления на конечном горизонте состоит в построении управления k∗ , максимизирующего ПОДVβ (nmax , k).
При бесконечном горизонте (следуя [1]) оптимальное управление будем искать в классетак называемых стационарных управлений kc = k , k, ... , т. е. управлений, представляющих собой последовательность политик, не зависящих от n.В качестве критерия оптимальности примем (так как β < 1)предельный доход, функционально зависящий от политики k.Итак, задача оптимального управления на бесконечном го∗ризонте состоит в определении политики k , максимизирующейпредельный доход.Лекция 9.
Построение оптимального управленияна конечном горизонтеНапомним постановкузадачи: найти управление k == k1 , k 2 , ... , k nmax , где kn = (k1n , k2n , ... , kN n ), kin ∈ Ki ,максимизирующее ПОД V (nmax , k) на интервале функционирования системы продолжительностью nmax (< ∞) шагов, еслидля всех стратегий kin заданы k k q1 1np11nQkn = ... , P kn = ... .kN nkN nqNpNЗдесь qikin — СОД в i-м состоянии на n-м шаге, отвечающийkinkin kinkinстратегии kin ; pi = pi1 , pi2 , ...
, piN— i-я строка МВПP kn , отвечающая политике kn ; n — число шагов до завершениягоризонта управления n = 1, 2, ... , nmax .Соотношение (8.4), если P и Q зависят от k, принимает видVβ n, k n = Qkn + βP kn Vβ n − 1, kn−1 ,(9.1)n = 1, 2, ... , nmax , Vβ (0) = 0.60Разд. 2. Дискретные цепи Маркова∗∗Обозначим оптимальные значения kn и Vβ∗ (n) ≡ Vβ n, k n и положим Vβ∗ (0) ≡ Vβ (0); тогда, опираясь на (9.1), последовательнонаходим методом динамического программирования (ДП):∗Vβ∗ (1) = max Qk1 → k1 , Vβ∗ (1);k1Vβ∗ (2)∗= max[Qk2 + βP k2 Vβ∗ (1)] → k2 , Vβ∗ (2) ;k2.........................................Vβ∗ (n)=max[Qknkn+ βP kn Vβ∗ (n − 1)]→∗kn , Vβ∗ (n) ;(9.2).........................................и т.
д. до n = nmax .Результаты вычислений сводятся в табл. 9.1.Важное замечание: метод ДП решает задачу на конечномгоризонте управления не только при β < 1, но и при β = 1.Т а б л и ц а 9.1in1v1∗ (n)......N∗vN(n)1k1∗n......N∗kNn012...nmaxПример 9.1 (продолжение примеров 8.1–8.3). Рассмотримзадачу РФ с управлением. Фирма производит и продает произведенные изделия. Она может находиться в одном из двухсостояний: объем сбыта высокий (i = 1) или объем сбыта низкий(i = 2). По усмотрению РФ возможны две стратегии управления:без рекламной поддержки (k = 1) и с рекламной поддержкойсбыта изделий (k = 2).
При k = 1, если объем сбыта высокий, тос вероятностью 0,5 он останется таким же в следующем месяце;если же объем сбыта низкий, то в следующем месяце он можетЛекция 9. Оптимальное управление на конечном горизонте61стать высоким с вероятностью 0,4. Таким образом, МВП имеетвид0,5 0,51P =,0,4 0,6при этом месячный доход составит 9 ед., если сбыт останетсявысоким, или 3 ед. в противном случае. При низком уровне сбытамесячный доход составит 3 ед., если в следующем месяце сбытстанет высоким, или −7 ед. в противном случае.Таким образом, МОД при k = 1 принимает вид931R =.3 −7В случае рекламной поддержки МВП и МОД с учетом стоимостирекламы имеют соответственно вид0,8 0,24422P =и R =.0,7 0,31 −19Требуется найти оптимальное управление фирмой при горизонте длительностью 5 месяцев.
Полагая β = 0,5 и переходя отМВП P k к матрице Pbk = βP k , удобно все исходные данныесосредоточить в табл. 9.2 и, опуская индекс β (для упрощения),записать соотношения (9.2) в обозначениях pbkij по каждому состоянию i = 1, 2 и для двух возможных стратегий k = 1, 2:)(2Pki1ki1 ∗∗n = 1 ⇒ vi (1) = max qi +pbij vj (0) =ki1j=1= max{qi1 , qi2 } → vi∗ (1) , ki∗1 ;n = 2 → vi∗ (2) = max{qiki2 +ki2n > 2 → vi∗ (n) = max{qikin +kin2Pj=12Ppbijki2 vj∗ (1)} → vi∗ (2) , ki∗2 ;j=1pbijkin vj∗ (n − 1)} →∗ , i = 1, 2.→ vi∗ (n), kinРешение примера по формулам (9.3):(9.3)62Разд.
2. Дискретные цепи МарковаТ а б л и ц а 9.2Cостояние iCтратегия kpbik11 (высокийобъем сбыта)1 (без рекламы)0,252 (с рекламой)0,42 (низкийобъем сбыта)1 (без рекламы)2 (с рекламой)kpbijpbki2rik1krbijСОДrik2qik360,2590,44440,20,33−7−30,350,151−19−5n = 1 ⇒ vi∗ (1) = max qiki1 = max{qi1 , qi2 } =ki1=(i = 1 : max{6, 4} = 6,∗∗⇒ k11= 1, k21= 1;i = 2 : max{−3, −5} = −32Xki2ki2 ∗∗n = 2 ⇒ vi (2) = max qi +pbij vj (1) =ki2j=1i = 1 : max{6 + 0,25 (6) − 0,25 (3) ;4 + 0,4 (6) − 0,1 (3)},==i = 2 : max{−3 + 0,2 (6) − 0,3 (3) ;−5 + 0,35 (6) − 0,15 (3)}=(∗ = 1,i = 1 : max{6,75; 6; 1} = 6,75 ⇒ k12∗ = 1;i = 2 : max{−2, 7; −3,35} = −2,7 ⇒ k222Xn = 3 ⇒ vi∗ (3) = max qiki3 +pbijki3 vj∗ (2) =ki3j=1i = 1 : max{6 + 0,25 · 6,75 + 0,25 (−2,7) ;4 + 0,4 · 6,75 − 0,1 · 2,7},==i=2:max{−3+0,2·6,75−0,3·2,7;−5 + 0,35 · 6,75 − 0,15 · 2,7}=(∗ = 1,i = 1 : max{7,01; 6,67} = 7,01 ⇒ k13∗ = 1;i = 2 : max{−2,46; −3,04} ⇒ −2,46 ⇒ k23Лекция 9.
Оптимальное управление на конечном горизонтеn=4⇒vi∗ (4)= maxki4qiki4+2Xj=1ki4 ∗vj (3)pbij63=i = 1 : max{6 + 0,25 · 7,01 − 0,25 · 2,46;4 + 0,4 · 7,01 − 0,1 · 2,46},== i = 2 : max{−3 + 0,2 · 7,01 − 0,3 · 2,46;−5 + 0,35 · 7,01 − 0,15 · 2,46}=n=5⇒=(∗ = 1,i = 1 : max{7,137; 6,618} = 7,137 ⇒ k14∗ = 1;i = 2 : max{−2,336; −2,916} = −2,336 ⇒ k24vi∗ (5)= maxki5qiki5+2Xj=1ki5 ∗pbijvj (4)=i = 1 : max{6 + 0,25 · 7,137 − 0,25 · 2,336;4 + 0,4 · 7,137 − 0,1 · 2,336},i = 2 : max{−3 + 0,2 · 7,137 − 0,3 · 2,336;−5 + 0,35 · 7,137 − 0,15 · 2,336}=(=∗ = 1,i = 1 : max{7,2; 6,622} = 7,2 ⇒ k15∗ = 1.i = 2 : max{−2,273; −2,852} = −2,273 ⇒ k25Таким образом, при всех n и в обоих состояниях оптимальное управление не требует проведения рекламной кампании.Табл.
9.1 для рассмотренного примера имеет вид, представленный в табл. 9.3.Т а б л и ц а 9.3in012346,757,017,13751v1∗(n)062∗vN(n)0−3−2,7−2,46−2,336−2,2731k1∗n–111112k2∗n–111117,264Разд. 2. Дискретные цепи МарковаЛекция 10. Построение оптимального управленияна бесконечном горизонтеНапомним, что при n → ∞ оптимальное управление строитсяв классе стационарных управлений, т. е. управлений, представляющих последовательность политик. Критерием оптимальностиявляется конечный предельный доход−1 Vβ∞ k = I − βP kQk .(10.1)∗Мы рассмотрим два метода построения политики k , максимизирующей (10.1): ∗Vβ k = max V k .(10.2)kМетод полного перебора предельно прост, но он реализуем лишьпри малых значениях числа возможных политик. Второй, наиболее популярный, — метод Ховарда — лишен этого недостатка,но технически сложнее. Исходными данными для обоих методовявляются матрицы P k и Rk , представленные в виде совокупностистрок pki i и riki , i ∈ S , ki ∈ Ki .Метод полного перебораЭтот метод реализуется обычно на ЭВМ по схеме, представленной на рис.
24, и состоит в следующем. Последовательно,для всех возможных политик k по формуле (10.1) вычисляютсязначения критерия Vβ∞ k . На каждом шаге вычислительногопроцесса определяется и сохраняется в памяти лучшая политика.Таким образом, оптимальное решение будет получено автоматически по завершении перебора (без повторений) всех возможныхвариантов.PkVβ∞ (k)max Vβ∞ (k)Qk∀kkRkРис. 24Лекция 10. Оптимальное управление на бесконечном горизонте65Пример 10.1 (продолжение примеров 8.1–8.3, 9.1). По исходным данным в табл. 9.2 вычислим значение критерия для каждойиз четырех политик k , полагая β = 0,5.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
