Теория случайных процессов (1042226), страница 9

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 9)

0,25 0,250,75 −0,251,1bk = (1, 1) ⇒ I − P = I −=⇒0,2 0,3−0,2 0,7 −1=⇒ I − pb1,1 = 0,475 ⇒ I − Pb1,11=0,4750,7 0,250,2 0,75⇒ Vβ∞ (1, 1) ==1,473 0,5260,421 1,5791,473 0,5260,421 1,5796−3=⇒7,26−2,21;k = (1, 2) ⇒ I − Pb 1,2 = 0,25 0,250,75 −0,25=I−=⇒ I − Pb1,2 = 0,55 ⇒0,35 0,15−0,35 0,851,545 0,454=⇒0,636 1,364 1,545 0,45467,0=⇒ Vβ∞ (1, 2) =,0,636 1,364−5−3,0⇒ (I − Pb 1,2 )−1 =10,550,85 0,250,35 0,75в памяти ЭВМ остается политика (1, 1).Далее аналогично анализируется политика, скажем, k =6,101= (2, 2) с результатом Vβ∞ (2, 2) =. В памяти ЭВМ−3,367вновь сохраняется k = (1, 1).Перебор всех возможных политик завершается рассмотрением k = (2, 1) со значением предельного дохода Vβ∞ (2, 1) =6,25=. Таким образом, оптимальным при n → ∞ оказыва−2,50ется первый из рассмотренных вариантов — (1, 1), не требующийрекламной поддержки ни в одном из состояний, что согласуетсяс результатом примера 9.1.3 Г.А.

Соколов66Разд. 2. Дискретные цепи МарковаАлгоритм ХовардаСогласно (9.1)Vβ n, k n = Qkn + βP kn Vβ n − 1, kn−1 ,причем lim Vβ n, k n < ∞, что позволяет записать это соотn→∞ношение в скалярной форме (опустив для простоты некоторыеиндексы) и перейти к пределу при n → ∞. В результате будетполучена система N уравнений относительно N неизвестныхпредельных доходов vi∞ :NXvi (n) = qi + βpij vj (n − 1) ⇒ hn → ∞i ⇒j=1X kpiji vj∞ , i = 1, 2, ... , N , (10.3)⇒ vi∞ = qiki + βесли стратегии ki считать фиксированными.

Эта система уравнений лежит в основе итерационного алгоритма Ховарда, блоксхема которого представлена на рис. 25.Блок выбора управления kБлок оценки управления (БОУ)Определение v∞i из системыуравненийNXkiv∞i = qiki + βpijv∞j ,j=1нет1, 2, ... , N ; ki фиксированыБлок организациицикла (БОЦ)′k =k ?Блок улучшения управления(БУУ)′Определение k из условияNX kqiki + βpiji vj∞ → max,j=1ki1, 2, ... , N ; vj∞ фиксированыБлок выбора предельныхдоходов v∞iРис. 25даконец67Лекция 10. Оптимальное управление на бесконечном горизонтеРабота алгоритма начинается либо с блока выбора управления (политики), либо с блока выбора предельных доходов.В первом исходные данные формируются в виде k , qiki , pkiji , i == 1, 2, ...

, N . Во втором — как правило, в виде k ′ = 0, vi∞ = 0 ∀ i.В блоке оценки управления (БОУ) определяются предельныедоходы vi∞ в результате решения системы уравнений (10.3) прификсированных qiki и pkiji . В блоке улучшения управления (БУУ)для каждого i определяется новое значение ki′ , максимизирующееправую часть (10.3) при фиксированных значениях предельныхдоходов vi∞ . В блоке организации цикла (БОЦ) сравниваютсястарое ki и новое ki′ значения i-й стратегии, i = 1, 2, ...

, N . Еслиki′ 6= ki хотя бы при одном значении i, то БОУ и БУУ циклическизамыкаются через БОЦ. Если же для всех i выполняется ki′ = ki ,то БОЦ останавливает процесс итераций и полученные значенияki , vi∞ объявляются оптимальными. Обоснование алгоритма Ховарда имеется в [1].Заметим, что изложенный алгоритм Ховарда позволяет найтиоптимальную политику при n → ∞ всегда, когда предельныйдоход конечен, в том числе при β = 1 (см. лекцию 11).Пример 10.2 (продолжение примеров 8.1–8.3, 9.1, 10.1).Рассмотрим решение задачи РФ с помощью алгоритма Ховарда.Основные соотношения• Оценка управления: vi∞ = qiki + β• Улучшение управления: maxkiqikiNPj=1+βkipijvj∞ ⇒ vi∞ ;NPj=1kipijvj∞!⇒ ki ,где β = 0,5, i = 1, 2, ... , N , N = 2, ki ∈ {1, 2}, рамками обведены фиксируемые параметры.

Исходные данные содержатся втабл. 10.1 (здесь pbkij = βpkij ).Итак:• нулевая итерация: полагаем k = (0, 0), v1∞ = v2∞ = 0.• первая итерация: в БУУ находимmax q1k1 , q1k2 = max (6, 4) = 6 ⇒ k1′ = 1,max q2k1 , q2k2 = max (−3, −5) = −3 ⇒ k2′ = 1;3*68Разд. 2. Дискретные цепи МарковаТ а б л и ц а 10.1ikpki1pki2110,50,50,250,256120,80,20,40,14210,40,60,20,3−3220,70,30,350,15−5в БОУ решаем систему уравнений(v1∞ = 6 + 0,25v1∞ + 0,25v2∞ ,v2∞ = −3 + 0,2v1∞ + 0,3v2∞pbik1pbik2qik⇒ v1∞ = 7,26, v2∞ = −2,21;• вторая итерация: в БУУ находимk1k1max q1k1 + pb11v1∞ + pb12v2∞ =k1 ∈{1,2}= max (6 + 0,25 · 7,26 − 0,25 · 2,21; 4 + 0,4 · 7,26 − 0,1 · 2,21) =maxk2 ∈{1,2}q2k2= max (7,26; 6,68) = 7,26 ⇒ k1′ = 1;k2k2+ pb21v1∞ + pb22v2∞ == max (−3 + 0,2 · 7,26−0,3 · 2,21; −5 + 0,35 · 7,26−0,15 · 2,21) == max (−2,21; −2,79) = −2,21 ⇒ k2′ = 1.Политики, полученные на первой и второй итерациях, совпадают,следовательно, оптимальная политика равна (1, 1).

Соответствующие ей предельные доходы найдены в БОУ на первой итерациии равны v1∞ = 7,26 и v2∞ = −2,21, что совпадает с предыдущимирезультатами.Лекция 11. Два класса прикладных задачуправления цепями с доходамиВ предыдущих трех лекциях мы рассмотрели в качествепримера «задачу руководителя фирмы», точнее, весьма общуюсхему, охватывающую многие задачи управления экономическими процессами. Некоторые из них, отличающиеся большимразнообразием фабулы, вошли в сборник задач. В настоящей69Лекция 11. Два класса прикладных задачлекции предполагается познакомить вас еще с двумя примерамистоль же общего характера, которые также будут использованыв сборнике задач и как задачи для «текущего» решения, и кактемы курсовых (самостоятельных) работ.Управление запасами в условиях неопределенностиРассмотрим n-шаговый процесс функционирования магазина,в котором шаг представляет собой некоторый интервал времени,например, месяц.

В начале n-го шага магазин заказывает kinединиц однородного и неделимого товара по цене c руб. Этоколичество добавляется к i единицам товара (i = 0, 1, 2, ... ),которое могло оказаться непроданным на предыдущих шагах.Таким образом, в начале каждого шага мгновенно создаетсятак называемый сформированный запас в количестве t = i ++ kin единиц. Величина запаса ограничена, например, емкостьюсклада N.На протяжении шага запасенный товар продается по ценеd руб., d > c > 0, в соответствии со спросом. Спрос задаетсядискретной случайной величиной с распределением вероятностейp (m), m = 0, 1, 2, ... , M , M > N .

Если в начале шага запас равен t, то к концу шага он снизится до s c условной вероятностьюp (t − s) , s = 1, 2, ... , t,MXpts =(11.1)p(m),s=0,m=tтак что МВП примет следующий вид:t\s0012...N100...0...0...0...... M Xp(m)p(0)01  m=1M XP =p(m)p(1)p(0)2  m=2... ......... M Xp(m) p(N − 1) p(N − 2)Nm=N...

p(0).70Разд. 2. Дискретные цепи МарковаЕсли спрос превышает запас, то возникает так называемыйнеудовлетворенный спрос (НС), который облагается штрафом,равным e за каждую единицу НС.Получим рекуррентные соотношения ДП для ПОД в случаяхконечного и бесконечного горизонтов управления. Для этой целизаметим, чтоt = i + kin , s = t − m = i + kin − m, 0 6 m 6 i + kin ,pi+kin ,i+kin −mp (m) , m = 1, 2, ... , i + kin − 1,MX=p (m) , m = i + kin .(11.2)m=i+kinСОД зависит от двух величин i и kin . Его можно представитьв виде суммы двух слагаемых.

Первое есть ожидаемый доход отпродажи товараi+kMin −1XXdm p (m) + (i + kin )p (m)m=1m=i+kinза вычетом МО штрафа за неудовлетворенный спросeM −i−kX inm p (i + kin + m).m=1Это слагаемое (обозначим его q (i + kin )) зависит от суммы i ++ kim . Второе слагаемое — это стоимость заказа q (kin ) = ckin ,оно зависит, очевидно, только от kin . Таким образом, СОД равенq (i, kin ) = q (i + kin ) + q (kin ) ,(11.3)и эту функцию удобно представить в виде матрицыi\kin012.........1...2Q = (q(i, kin )) = ... ...

... .........N −2 0 ...N −10 0 ...N0N −2N −1N...0000...00000...000,Лекция 11. Два класса прикладных задач71где 0 6 i, kin 6 N , 0 6 i + kin 6 N . Для ее построения достаточно по формуле (11.3) найти элементы первой строкиq (0, kin ) , kin = 0, 1, 2, ... , N , и далее воспользоваться соотношением (докажите!)q (i − 1, kin + 1) = q (i, kin ) + c,i = 0, 1, 2, ... , N ,kin = N − i.

(11.4)В этих обозначениях имеемq (i, kin ) +vi∗ (n) = max06kin 6N −i+βi+kXinm=0∗pi+kin ,i+kin −m vi+k(n−1),in −mi = 0, 1, 2, ... , N ,n > 1,vi∗ (0) = 0. (11.5)∗ ), i = 1, 2, ... , N , n > 1 — оптимальОтсюда получаем, что (kinное управление при n < ∞.Переходя в (11.5) к пределу при n → ∞, получим соотношение)(i+kXi∗∗vi∞= maxq(i, ki ) + βpi+ki ,i+ki −m vi+k,i −m,∞06ki 6N −im=0i = 0, 1, 2, ... , N , (11.6)лежащее в основе алгоритма Ховарда построения оптимальногостационарного управления∗(k1∗ , k2∗ , ... , kN).Пример 11.1.

Пусть N = 2, n 6 3, c = 10, d = 15, e = 2, β == 0,5, i = 0, 1, 2; распределение вероятностей имеет вид!m0123.p (m) 0,1 0,5 0,3 0,172Разд. 2. Дискретные цепи МарковаТогдаt\s0012100P = 1  0,9 0,1 0 ,20,4 0,5 0,1i\kin0Q=12012−2,8 2,5 −0,7 12,5 9,3 −  .19,3 −−Следуя (11.5), полагаем последовательно n = 1, 2, 3, а при каждом n находим для каждого i = 0, 1, 2 максимум ПОД по всемвозможным значениям стратегий.Итак, пусть n = 1, тогда:v0∗ (1) = max q (0, k01 ) = 2,5,06k01 62v1∗ (1) = max q (1, k11 ) = 12,5,06k11 61∗k01= 1,∗k11= 0,v2∗ (1) = max q (2, k21 ) = q (2, 0) = 19,3,06k21 60∗k21= 0.Пусть n = 2, тогда:nv0∗ (2) = max q (0, 0) + 0,5p00 v0∗ (1) ;q (0, 1) + 0,5 p11 v1∗ (1) + p∗10 (1) v0∗ (1) ;oq (0, 2) + 0,5 p22 v2∗ (1) + p21 v1∗ (1) + p20 v0∗ (1) =n− 2,8 + 0,5 · 1 · 2,5; 2,5 + 0,5(0,1 · 12,5 + 0,9 · 2,5);o∗− 0,7 + 0,5(0,1 · 19,3 + 0,5 · 12,5 + 0,4 · 2,5) = 4,25, k02= 1;nv1∗ (2) = max q (1, 0) + 0,5 p11 v1∗ (1) + p10 v0∗ (1) ;= maxoq (1, 1) + 0,5 p22 v2∗ (1) + p21 v1∗ (1) + p20 v0∗ (1) =n= max 12,5 + 0,5(0,1 · 12,5 + 0,9 · 2,5);o∗9,3 + 0,5(0,1 · 19,3 + 0,5 · 12,5 + 0,4 · 2,5) = 14,25, k12= 0;73Лекция 11.

Характеристики

Список файлов книги