Теория случайных процессов (1042226), страница 10
Текст из файла (страница 10)
Два класса прикладных задачv2∗ (2) = q (2, 0) + 0,5 p22 v2∗ (1) + p21 v1∗ (1) + p20 v0∗ (1) == 19,3 + 0,5(0,1 · 19,3 + 0,5 · 12,5 + 0,4 · 2,5) = 23,89,∗k22= 0.Пусть n = 3, тогда:nv0∗ (3) = max q (0, 0) + 0,5p00 v0∗ (2) ;q (0, 1) + 0,5 p11 v1∗ (2) + p10 v0∗ (2) ;oq (0, 2) + 0,5 p22 v2∗ (2) + p21 v1∗ (2) + p20 v0∗ (2) =n= max 0 + 0,5 · 1 · 4,25, 2,5 + 0,5 0,1 · 14,25 + 0,9 · 4,25 ;o∗− 0,7 + 0,5(0,1 · 23,89 + 0,5 · 14,25 + 0,4 · 4,25) = 5,125, k03= 1,nv1∗ (3) = max q (1, 0) + 0,5 p11 v1∗ (2) + p10 v0∗ (2) ;oq (1, 1) + 0,5 p22 v2∗ (2) + p21 v1∗ (2) + p20 v0∗ (2) =n= max 12,5 + 0,5(0,1 · 14,25 + 0,9 · 4,25); 9,3 + 0,5(0,1 · 21,6 +o+ 0,5 · 14,25 + 0,4 · 4,25) = 15,125,∗k13= 0,+ 0,5(0,1 · 23,89 + 0,5 · 14,25 + 0,4 · 4,25) = 24,907,∗k23= 0.v2∗ (3) = q (2,0) + 0,5 p22 v2∗ (2) + p21 v1∗ (2) + p20 v0∗ (2) = 19,3 +Для рассмотренного примера оптимальное управление на конечном горизонте состоит в том, что на всех шагах тольков нулевом состоянии магазину следует заказать одну единицутовара.
Табл. 11.1 значений ПОД имеет видТ а б л и ц а 11.1PPP ni PPPP0123002,54,255,1251012,514,2515,1252019,323,8924,90774Разд. 2. Дискретные цепи МарковаНеуправляемый режим функционирования состоит в том, чтонезависимо от n магазин всегда заказывает (N − i) единиц товара, т. е. i + kin = N .
Тогда СОД будет зависеть только от i.Действительно,!N−1MXXq (i, kin ) = dmp (m) + Np (m) − =m=Nm=1= −eследовательно,vi (n) = const + ci + βM−NXm=1NXm=0mp (N + m) − c (N − i) = const + ci,pN ,N −m vN −m (n − 1) ,n > 1,vi (0) = 0,и мы получили рекуррентное соотношение для ПОД в неуправляемом режиме.
В частности, для рассматриваемого примераvi (n) = 10i − 0,5++ 0,5 p22 v2 (n − 1) + p21 v1 (n − 1) + p20 v0 (n − 1) == 10i − 0,5 + 0,5 0,1v2 (n − 1) + 0,5v1 (n − 1) + 0,4v0 (n − 1) ,n > 1,Значения ПОД,в табл. 11.2.вычисленныепоvi (0) = 0,этойi = 0, 1, 2.формуле,сведеныТ а б л и ц а 11.2PPP ni PPPP012300−0,52,754,375109,512,7514,3752019,522,7524,375Следуя (11.6), найдем оптимальное стационарное управлениепри n → ∞.
Фиксируем управление k0 = 1, k1 = k2 = 0 и находим его оценку v0∞ , v1∞ , v2∞ , являющуюся решением системы75Лекция 11. Два класса прикладных задачуравнений (индекс ∞ для упрощения записи опускается)v = q (0,1) + 0,5(p11 v1 + p10 v0 ), 0⇒v1 = q (1,0) + 0,5(p11 v1 + p10 v0 ),v2 = q (2,0) + 0,5(p22 v2 + p21 v1 + p20 v0 )v = 6,v0 = 2,5 + 0,5(0,1v1 + 0,9v0 ), 0⇒ v1 = 12,5 + 0,5(0,1v1 + 0,9v0 ),⇒ v1 = 16,v2 = 19,3 + 0,5(0,1v2 + 0,5v1 + 0,4v0 )v2 = 25,79.Фиксируем полученные значения ПОД и пытаемся улучшитьуправление. Пусть i = 0, тогдаnmax q (0, 0) + 0,5p00 v0 ; q (0, 1) + 0,5(p11 v1 + p10 v0 );oq (0, 2) + 0,5(p22 v2 + p21 v1 + p20 v0 ) =n= max 0 + 0,5 · 1 · 6; 2,5 + 0,5(0,1 · 16 + 0,9 · 6);o− 0,7 + 0,5(0,1 · 25,79 + 0,5 · 16 + 0,4 · 6) == 6,k0′ = 1 = k0 .Совершенно аналогично, рассматривая второе и третье состояния, убеждаемся в том, что ki′ = ki , i = 1, 2; следовательно,в классе стационарных управление k0 = 1, ki = 0, i = 1, 2 является оптимальным.В заключение остановимся кратко на некоторых особенностях построения оптимального стационарного управления методом полного перебора.
Формулы (10.1), (10.2) остаются в силе;при этом, фиксируя политику k = (k0 , k1 , ... , ki , ... , kN ) и полагая i := i + ki для всех i, по матрице P строим матрицу P k .Вектор Qk строится по матрице Q путем выбора элементовq (i, ki ) для каждого i. Например, для рассматриваемого примераимеется шесть вариантов политик:k1 = (0,0,0) ,k2 = (1,0,0) ,k3 = (2,0,0) ,k4 = (0,1,0) ,k5 = (1,1,0) ,k6 = (2,1,0) ;76Разд. 2. Дискретные цепи Марковав частности, для k5 имеем0,9 0,1 0P 5 = 0,4 0,5 0,1 ,0,4 0,5 0,12,5Q5 = 9,3 .19,3Управление по остановкеПусть работа некоторой системы моделируется ДЦМ со множеством состояний S = {1, 2, ... , N } и МВП P . Предположим,что человек имеет возможность наблюдать траекторию цепи, т. е.состояния i в дискретные моменты времени n = 0, 1, 2, ... .
Еслив момент n человек останавливает работу системы в состоянии i, то он получает доход fi (fi — заданная функция). Внесяопределенную неотрицательную плату ci , человек может не останавливать работу системы в надежде через один или несколькошагов оказаться в состоянии j , которому соответствует большийдоход fj .Какого правила должен придерживаться человек, если онхочет получить максимальный доход? Это правило определяетнекоторое управление ДЦМ, которое называется управлениемпо остановке, т.
е. в каждом состоянии i и на каждом шаге nвозможны две стратегии управления: kin = 1 — «остановка»и kin = 0 — «продолжение».Из рекуррентного соотношения ДП (9.3) с учетом специфических особенностей управления по остановке следует рекуррентное соотношение для определения последнего:()NP∗∗ vi (n) = max fi ,pij vj (n − 1) − ci , n = 1, 2, ... ; v ∗ (0 ) = f ,iij=1(11.7)i ∈ S,т.
е. в любом состоянии оптимальный доход есть максимум издвух доходов: это доход от остановки процесса, равный fi , и доNXход от его продолжения, равныйpij vj∗ (n − 1) − ci . Решаемj=1систему (11.7):Лекция 11. Два класса прикладных задач77при n = 1vi∗ (1) XN∗= max fi ,pij vj (0) − ci =j=1= max fi ,j=1pij fj − ci , i ∈ S ⇒N 1, если f > X p f − c ,iij ji⇒ ki1 =j=10 в противном случае;при n = 2vi∗ (2)NX XN∗= max fi ,pij vj (1) − ci ,j=1i∈S⇒N 1, если f > X p v ∗ (1) − c ;iij ji⇒ ki2 =j=10 в противном случае;при произвольном n > 1 XN∗∗vi (n) = max fi ,pij vj (n − 1) − ci ,j=1⇒ kin(11.8)(11.9)i∈S⇒N 1, если f > X p v ∗ (n − 1) − c ,iij ji=j=10 в противном случае.(11.10)Мы получили метод построения оптимального управленияпо остановке на конечном горизонте.
Рассмотрим ряд егосвойств.Свойство 1. Для всех i ∈ S последовательность оптимальных значений ПОД vi∗ (n) не убывает по n:fi = vi∗ (0) 6 vi∗ (1) 6 ... 6 vi∗ (n) 6 ... .(11.11)Д о к а з а т е л ь с т в о. Воспользуемся методом математическойиндукции. Согласно (11.8) vi∗ (1) > fi = vi∗ (0).
Предположим,78Разд. 2. Дискретные цепи Марковачто (11.11) справедливо для n − 1, и покажем, что оно справедливо также для n. Cогласно (11.10)NX∗vi (n) = max{fi ,pij vj∗ (N − 1) − ci } >j=1> max{fi ,NXj=1pij vj∗ (n − 2) − ci } = vi∗ (n − 1) .Свойство 2. Для всех i ∈ S и n > 0 оптимальные значенияПОД ограничены с двух сторон:min fj 6 vi∗ (n) 6 max fj .jjД о к а з а т е л ь с т в о. Действительно, согласно предыдущемусвойству vi∗ (n) > fi > min fj .
Для доказательства правой частиjнеравенства заметим, что vi∗ (0) = fi 6 max fj , и вновь воспользуjемся методом математической индукции. Пусть vi∗ (k) 6 max fj ,jk = 1, 2, ... , n − 1, тогда согласно (11.10) XN∗∗vi (n) = max fi ,pij vj (n − 1) − ci 6j=16 max fi ,NXj=1pij max fj − cij= max fi , max fj − ci 6 max fi .jjСледствие. Если при i = m функция fi достигает∗максимума, то оптимальные стратегии равны kmnдля всехn > 1.Cвойство 3. Последовательность оптимальных значенийПОД при n → ∞ имеет конечный предел (называемый предельным доходом и обозначаемый vi∗ ).Это свойство следует из предыдущих, так как по известнойтеореме математического анализа неубывающая и ограниченнаясверху числовая последовательность имеет конечный предел.Свойство 4 (монотонности). Если при некотором m выпол∗ = 1, то при всех n < m имеет место k ∗ = 1; еслиняется kimin∗ = 0, то при всех n > m справедливо равенство k ∗ = 0.же kiminЭто свойство очевидно.79Лекция 11.
Два класса прикладных задачРассмотрим бесконечный горизонт управления. В силу свойства 3 в соотношении (11.7) можно перейти к пределу приn → ∞ и получить систему n уравнений с n неизвестными,которая позволяет найти оптимальное стационарное управлениепо остановке: XNvi∗ = max fi ,pij vj∗ − ci , i = 1, 2, ... , N.(11.12)j=1Система (11.12) лежит в основе итерационного алгоритмаХоварда, аналогичного рассмотренному в лекции 10. В БОУрешается системаfi ∀ i : ki = 1,Nvi = Xpij vj − ci ∀ i : ki = 0j=1относительно переменных vi , которые оценивают управление(k1 , k2 , ...
, kN ). В БУУ предпринимается попытка улучшитьNXуправление. Для этой цели вычисляются выраженияpij vj −j=1− ci ∀ i и сравниваются с fi . По результатам сравнения получаем:NPдля тех i, для которыхpij vj − ci 6 fi , полагаем ki = 1; дляj=1остальных i полагаем ki = 0.Пример 11.2. Пусть N = 5, n 6 3, все исходные данныесодержатся в табл. 11.3.Т а б л и ц а 11.3ip1p2p3p4p5fc10100010420010021300,500,502,514000018350,5000,5042Здесь pj , j = 1, 2, ...
, 5 — j -й столбец МВП.80Разд. 2. Дискретные цепи МарковаВ силу свойства 2, следуя (11.8)–(11.10), получим при n = 1:v1∗ (1) = f1 = 10 ⇒ k1∗n = 1 ∀ n > 1,v2∗ (1) = max{f2 ; 1 · f3 − c2 } =∗= max{2; 2,5 − 0,5} = 2 ⇒ k21= 1,v3∗ (1) = max{f3 ; p32 f2 + p34 f4 − c3 } =∗max{2,5; 0,5 · 2 + 0,5 · 8 − 1} = 4 ⇒ k31= 0,v4∗ (1) = max{f4 ; p45 f5 − c4 } =∗= 1,= max{8; 1 · 4 − 3} = 8 ⇒ k41v5∗ (1) = max{f5 ; p54 f4 + p51 f1 − c5 } =∗= max{4; 0,5 · 8 + 0,5 · 10 − 2} = 7 ⇒ k51= 0,результаты сведем в табл.
11.4.Т а б л и ц а 11.4vi∗i12345(1)10248711010∗kinПусть n = 2, тогда:∗v1∗ (2) = f1 = 10 ⇒ k12= 1,v2∗ (2) = max{f2 ; p23 v3∗ (1) − c2 } =∗= max{2; 1 · 4 − 2} = 2 ⇒ k22= 1,v3∗ (2) = max{f3 ; p32 v2∗ (1) + p34 v4∗ (1) − c3 } =∗= max{2,5; 0,5 · 2 + 0,5 · 8 − 1} = 4 ⇒ k32= 0,v4∗ (2) = max{f4 ; p45 v5∗ (1) − c4 } =∗= max{8; 1 · 7 − 3} = 8 ⇒ k42= 1,v5∗ (2) = max{f5 ; p54 v4∗ (1) + p51 v1∗ (1) − c5 } =∗= max{4; 0,5 · 8 + 0,5 · 10 − 2} = 7 ⇒ k42= 0.Литература81Результаты этого шага совпадают с приведенными в табл. 11.4.Следовательно, те же результаты будут получены и для последующих шагов.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
