Dynamic network inventory control model with interval demand uncertaintyand storage loss in the network nodes.pdf Динамические сетевые модели описывают широкий класссистем управления запасами [1, 2]. В качестве примера мож-но привести системы снабжения, производства-распределения,транспортные, информационные, финансовые и другие систе-мы. Узлы сети задают виды и размеры управляемых запасов,а дуги - управляемые и неуправляемые потоки в сети. Управ-ляемые потоки перераспределяют ресурсы между узламисети, возможно, перерабатывая их, и планируют поставкиизвне. Неуправляемые потоки описывают спрос на ресурсы вузлах сети, который формируется как со стороны других уз-лов, так и внешнего окружения.Проблеме оптимизации динамических потоков в сети по-священо большое количество работ (см., к примеру, [1, 2] и об-ширную библиографию к ним). Современная теория предлагаеталгоритмы оптимального управления как детерминированными,так и стохастическими динамическими сетями. Однако детер-минированные модели не учитывают априорную неопределен-ность, свойственную реальным системам управления запасами.Вероятностные - требуют точного задания вероятностных ха-рактеристик неопределенных параметров системы (факторовнеопределенности) и довольно сложны в смысле получениячисленных результатов. При этом во многих случаях нет осно-вания или недостаточно информации, чтобы рассматривать фак-торы неопределенности как случайные (то есть адекватно опи-сываемые теоретико-вероятностными моделями). Это приводитк необходимости учета неопределенности нестохастической(или, в общем случае, неизвестной) природы.Интересный подход, основанный на концепции «неизвестных,но ограниченных» воздействий (unknown-but-bounded inputs),предлагается в работах Ф. Бланчини, Ф. Ринальди и В. Уковича[3−5]. В них рассматриваются динамические сетевые моделисистем управления запасами в предположении, что неизвест-ный спрос принадлежит заданному множеству. Такой подходприводит к минимаксным игровым постановкам и гарантиро-ванным решениям в смысле заданного критерия. Авторы [3−5]используют аппарат теории множеств. Однако теоретико-мно-жественное представление результатов приводит к трудностямпри проверке условий существования оптимальных стратегийуправления и вычисленияОпределение 1. Будем называть функцию u(t)=U (x(t), t),u(t)U, допустимым на интервале X управлением длясостояния x(t) в момент времени t, t ≥ 0, если для любо-го значения спроса d(t)D выполнено включениеx(t+1)X,, где x(t) определяется рекуррентным соотно-шением (1).Определение 2. Будем называть стратегию Φ={u(t),t ≥ 0}, u(t)U, допустимой на интервале X стратегиейуправления для начального состояния x(0)X, если u(t)является допустимым на интервале X управлением длясостояния x(t) в момент времени t, t ≥ 0, где x(t) опреде-ляется рекуррентным соотношением (1).Определение 3. Будем называть xˆ, xˆ  X , допусти-мым уровнем запаса в сети, если для любого начально-го состояния x(0)X существует допустимая на интер-вале X стратегия ց Φ(x(0)) такая, что x (t) X(0, xˆ),t ≥ ƒ ≥ 0, где интервальнозначная [11−13] функцияX(a, b) = [a, b] определена для любых a ≤ b, a,bRn;Φ(x(0)) - множество стратегий, допустимых на интер-вале X при начальном состоянии x(0)X, а x(t) опреде-ляется рекуррентным соотношением (1).Очевидно, что если для любого начального состоя-ния x(0)X существует допустимая стратегия управле-ния ƒ ƒ(x(0)), то X является допустимым уровнемзапаса. Однако, как известно, при неоправданно высо-ком уровне запаса системастояния x(0)X существует допустимая стратегияƒ ƒ(x(0)) такая, что x(t + 1) = Ax(t) + Bu(t) + Ed(t) X(0,xˆ), t ≥ ƒ −1 ≥ 0, для любого d(t)D. Следова-тельно,x t Ax t Bu t ,x , t .x t Ax t Bu t 0,x , t( 1) ( ) ( ) (0 ˆ) opp 1 0( 1) ( ) ( ) ( ˆ) 1 0 + = +  + ≥ ƒ − ≥+ = + +  ≥ ƒ − ≥ X EDED X(Заметим, что здесь, в отличие от определения 3, ƒ ≥ 1.Однако, если x(0) X(0,xˆ) , то получаем ƒ ≥ 0.) Послед-нее соотношение имеет смысл, если и только еслиED x ED x ED ED.,x ,x − ≤ −  ≤ −+ ≤ + ˆ ˆX(0 ˆ) oppED X(0 ˆ) oppEDУчитывая то, что xˆ  X , получаем xˆ [ED − ED, X ] (всилу (8) этот интервал - правильный).Далее, так как функция затрат (5) монотонно воз-растает по xˆ , то для любого вектора h ≥ 0, h  0, мини-мум функции (5) доставляет xˆ* = ED − ED , что и тре-бовалось доказать.Замечание 2. Для оптимального допустимого уров-ня запаса xˆ* вида (10) справедливо включениеwidED ≤ widX(0, xˆ*) . (11)Допустим, что в некоторый момент времени ƒ* со-стояние системы попало в интервал X(0, xˆ*) . Учиты-вая (11), можно применить теорему 1 для X= X(0, xˆ*) .По теореме 1 для любого состояния x(t) X(0, xˆ*) в мо-мент времени t, t ≥ 0, допустимое на интервале X(0, xˆ*)управление u(t)=U(x(t),t), u(t)U, существует и опреде-ляется из включенияAx(t) + Bu(t)  X(0, xˆ*) + oppED . (12)С учетом того, что X( 0, xˆ* ) + oppED = [−ED,−ED] , из(12) получаем матричное уравнениеAx(t) + Bu(t) = −ED . (13)Управления u(t), u(t)U, удовлетворяющие (13), га-рантируют включения x(t) X(0, xˆ*) для t ≥ ƒ* и со-ставляют оптимальную стратегию управления (будемназывать их оптимальными управлениями).Замечание 3. Величина −ED определяет опти-мальный уровень предельного запаса в системе дляt ≥ ƒ*. Причем любое управление u(t), u(t)U, удовле-творяющее (13), является оптимальным в смысле (6). Вэтом случае для t ≥ ƒ* управления u(t) логично выби-рать, минимизируя затраты на управления (транспорт-ные расходы, затраты на производство и т.д.) при усло-виях u(t)U и (13).ОПРЕДЕЛЕНИЕ ОПТИМАЛЬНОЙДОПУСТИМОЙ СТРАТЕГИИ УПРАВЛЕНИЯПусть для любого начального состояния x(0)X суще-ствует допустимая на интервале X стратегия управления.Для существования оптимальной в смысле (6) допустимойстратегии управления этого достаточно в двух случаях:− когда оптимальный допустимый уровень запасаxˆ* = X , тогда любая допустимая на интервале X стра-тегия управления будет оптимальной;− когда оптимальный допустимый уровень запасаxˆ* ≤ X, xˆ*  X , и начальный уровень запаса x(0)  X(0, xˆ*) , тогда любая допустимая на интервалеX(0, xˆ*) стратегия управления будет оптимальной.В этих случаях проблема существования оптималь-ной допустимой стратегии управления не возникает искорость сходимости ƒ*=0. Оптимальные управленияu*(t), u*(t)U, составляющие оптимальную стратегиюƒ* ƒ(x(0)), являются решениями уравнения (13) вкаждый момент времени t ≥ 0.Рассмотрим далее случай, когда начальный запаспревосходит оптимальный допустимый уровень запасаx(0)  X(xˆ* ,X ), xˆ* ≤ X, xˆ*  X . Определим для этогослучая условия существования оптимальной допусти-мой стратегии ƒ* ƒ(x(0)) и скорость сходимости ƒ* коптимальному допустимому уровню запаса xˆ*.Терема 3. (о существовании оптимальной допусти-мой стратегии). Для любого начального состоянияx(0)X существует оптимальная допустимая на интер-вале X стратегия управления ƒ* ƒ(x(0)), если выпол-нены условия (8), (9) и существует ƒ>0 такое, чтоX(ED,AED) + ƒ X(0,ƒ)  {−BU}, (14)где ƒ  Rn , ƒ = X − xˆ*. Причем сходимость к оптималь-ному допустимому уровню запаса xˆ* достигается неболее чем за конечное число шагов1ln1lnmax1+⎥ ⎥ ⎥ ⎥⎥⎤⎢ ⎢ ⎢ ⎢⎢⎡ƒ− ƒ + ƒƒ== iii ,nT , (15)где ⎡x⎤ - наименьшее целое, большее числа x.Доказательство. Введем вектор~x(t +1) = Ax(t) + Bu(t), t ≥ 0 ,который определяет уровень запаса в сети после по-ставки в момент времени t, но до очередного предъяв-ления спроса. Тогда x(t +1) = ~x (t +1) + Ed(t), t ≥ 0 .Покажем, что x(t+1)X для любого значения спросаd(t)D, если и только если ~x(t +1)  X + oppED .Действительно,x t x t .d t | x t Ed tED X X EDD X~( 1) ~( 1) opp( ) ~( 1) ( ) + +   +  +  + +  Покажем по индукции, что для любого начального со-стояния x(0)X существует допустимая на интервале Xстратегия ƒ ƒ(x(0)) такая, что ~x(t)  [− ED,max{− ED, At −1 (X − ED) −− ƒ(I + A +K+ At−2 )ƒ}] , t ≥ 1, (16)где I  Rnn - единичная матрица. Так как выполнены усло-вия (8), (9), то по теореме 1 для любого начального состоянияx(0)X существует допустимое управление такое, что~x(1)  X + oppED = [−ED,X − ED] .С учетом соотношения − ED = xˆ* −ED ≤ X − ED ясно,что для t = 1 включение (16) справедливо. Далее, пусть(16) справедливо для произвольного t, t ≥ 2. Покажем,что оно справедливо для t + 1. Заметим, что условие(14) можно представить в видеX(AED,AED) + ƒX(0,ƒ) + X((I − A)ED,0)  {−BU}. (17)Рассмотрим ~x(t +1) = Ax(t) + Bu(t) = A(~x (t) + Ed(t − 1) ++ Bu(t)  ƒƒ(t)  ~ƒ(t) . Согласно условию (17), сущест-вует управление u(t)U такое, что AEd(t −1) + ƒƒ(t) ++ ~ƒ(t) + Bu(t) = 0 для любого d (t − 1)D и любыхƒ(t)  X(0,ƒ) , ~ƒ(t)  X((I − A)ED,0) . Тогда~x(t +1) = Ax(t) − ƒƒ(t) − ~ƒ(t) , (18)гдеƒ(t)  X(0,ƒ) , ~ƒ(t)  X((I − A)ED,0) . (19)Определим вектора ƒ(t), ~ƒ(t) с компонентами( ) ⎩⎨⎧ƒ +ƒ = ƒ − ƒƒ ≥ −⎪⎩⎪⎨⎧⎟⎠⎞⎜⎝⎛ƒƒ +ƒ ƒ − ƒƒ ≥ −ƒ =min 0, ~ ( ) , else.~ ( ) 0, if ~ ( ) ,, else,~max 0,, if ~ ( ) ,( )i i ii i i iii i ii i i i iix t EDt x t EDx (t) EDx t EDt(20)Покажем, что ƒ(t), ~ƒ(t) вида (20) удовлетворяют усло-вию (19). Согласно (20), ƒi(t) либо принимает значение ƒi(верхней границы i-ой компоненты интервала X(0, ƒ)), либоравна нулю (нижней границе i-й компоненты интервалаX(0, ƒ)), либо 0~ ( )( ) >ƒƒ +ƒ = i i iix t EDt , причем из условияƒi~xi (t) − ƒƒi < −EDi следует ii i iix t EDt < ƒƒƒ +ƒ = ~ ( )( ) , от-куда получаем включение ƒ(t)  X(0,ƒ) . Далее, ~i (t) ƒ либоравна нулю (верхней границе i-ой компоненты интервалаX((I − A)ED,0) ); либо ( ) ~ ( ) 0~ = ƒ + < θi t i xi t EDi , причем всилу предположения индукции (16) имеем ~xi (t) ≥ −EDi ,откуда θi (t) (1 αi )EDi~ ≥ − , что и доказывает включение( ) (( ) 0)~ θ t  X I − A ED, .Таким образом, из (18) получаем⎩ ⎨ ⎧−ƒ − ƒƒ ƒ − ƒƒ ≥ −+ = , иначе,~ ( ) , если ~ ( ) ,~ ( 1)ii i i i i i ii EDx t x t EDx tоткуда, с учетом предположения индукции (16), ~ ( +1)  [− ,max{− , ƒ ( − ) − i itxi t EDi EDi X ED i(1 1) }] .itii − ƒ + ƒ + + ƒ − ƒ K (21)Кроме того, учитывая соотношенияˆ* ,( ) (1 1 ) ,i i i ii i itii i itED x ED X EDX ED X ED i− = − ≤ −ƒ − − ƒ + ƒ + + ƒ − ƒ ≤ − Kполучаем включение[ { }][ , ] .,max , ( ) (1 1)i i iitii i iti iED X EDED ED X ED i − −− − ƒ − −ƒ + ƒ + + ƒ − ƒ  KТаким образом, ~x(t +1)  X + oppED и x(t+1)X длялюбого d(t)D. По определению 1 управление u(t),удовлетворяющее (21), является допустимым на интер-вале X в момент времени t. Следовательно, утвержде-ние (16) имеет силу для любого t ≥ 1.Покажем, что стратегия ƒ ƒ(x(0)), является оптималь-ной, т.е. начиная с некоторого момента времени ƒ* выпол-нено включение (6). Рассмотрим случай, когда ƒi = 0( xˆi* = Xi ). При этом включение (16) примет вид~x (t)  [− ED ,max{− ED , ƒ −1(xˆi* −EDi )}], t ≥ 1ti i i i .Заметим, чтоi i i iti i itƒi−1(xˆ *−ED ) = ƒ −1(−ED ) ≤ 0 < ƒ ≤1,ED ≤ 0 ≤ −ED ,следовательно,~xi (t)  [− EDi ,−EDi ]= X(0, xˆi*) + oppEDi , t ≥ 1 ,что гарантирует включение xi (t) X(0, xˆi*), t ≥ 0 (с уче-том того, что xi (0)  X(0, xˆi*), t ≥ 0 ).Для случая, когда ƒi>0, найдем момент времени ƒ*,начиная с которого ~xi (t) [− EDi ,−EDi], t ≥ ƒ*. Рас-смотрим функциюX ED .f t X EDiitii ititii i itiiiƒ− ƒ− ƒ= ƒ − − ƒ= ƒ − − ƒ + ƒ + + ƒ ƒ =−−− −11( )( ) ( ) (1 )111 K 2Учитывая то, что,1111( )1( ) ( ) 1111111iitiitiiitii itiitii itiiiiEDEDf t X EDƒ− ƒ− ƒ≤ − + ƒ ƒ − ƒƒ ≤− ƒ− ƒ= ƒ ƒ − − ƒƒ =− ƒ− ƒ= ƒ − − ƒ−−−−−−нетрудно показать, что функция fi(t) убывает по t иfi (t) ≤ −EDi для 1ln1ln+⎥ ⎥ ⎥ ⎥⎥⎤⎢ ⎢ ⎢ ⎢⎢⎡ƒ− ƒ + ƒƒ≥it i .Следовательно, из (16) имеем[ ]ln 1,ln1~ ( ) , X(0, ˆ *) opp ,+⎥ ⎥ ⎥ ⎥⎥⎤⎢ ⎢ ⎢ ⎢⎢⎡ƒ− ƒ + ƒƒ≥ − − = +iii i i i itx t ED ED x EDоткуда получаем14444244443Tx t x tiii ,n=+⎥ ⎥ ⎥ ⎥⎥⎤⎢ ⎢ ⎢ ⎢⎢⎡ƒ− ƒ + ƒƒ ≥=1ln1ln( ) (0, ˆ*), max1X .Таким образом, стратегия ƒ ƒ(x(0)), удовлетво-ряющая (16), является оптимальной, а скорость сходи-мости к оптимальному допустимому уровню ƒ*=T, где Tопределяется соотношением (15). Теорема доказана.Из доказательства теоремы 3 следует, что если выби-рать управление u(t)U в момент времени t так, чтобы [− {− − −ƒ − − ƒ}]+ ,max , ( ) ( )− ( )( ) ( )ED ED At X ED I A 1 I AtAx t Bu t [− ED,max{− ED,−ED +(At − ƒ(I − A)−1 (I − At ))θ}] ,то, начиная с момента времени T-1, будем иметьAx(t) + Bu(t)  [− ED,− ED]= −ED, t ≥ T −1 ,что гарантируетx(t)  X( 0, xˆ*), t ≥ T ,следовательно, стратегия ƒ={u(t), t≥0}является опти-мальной в смысле (6).Для того чтобы увеличить скорость сходимостисистемы, будем определять управления u*(t) в моментвремени t, t ≥ 0 , составляющие оптимальную страте-гию ƒ*={u*(t), t≥0} из решения следующей оптимиза-ционной задачи:nnii u t ƒ ƒ ƒ ƒ=( ), ,K 1 1min (22)при ограничениях( ) U, , , , 0,( ) ( ) , ,1 2  ƒ ƒ ƒ ≥− ≤ + ≤ − + ƒƒ − + ƒƒ ≤ −u t nED Ax t Bu t ED ED X EDKгде x(t) определяется рекуррентным соотношением (1)(x(0) - известное начальное состояние запаса);ƒ=Diag(ƒ1, ƒ2,…, ƒn) - диагональная n n -матрица; ƒ1,ƒ2,…, ƒnR - вспомогательные параметры. Моментвремени ƒ*, ƒ*

Скачать электронную версию публикации