Содержание к диссертации
Введение
Глава 1. Стационарное управление.
1.1. Оптимальное стационарное управление. 10
1.2. Качество управления при различных параметрах СМО . 15
1.3 .Замечания и комментарии. 21
Глава 2. Программное управление . 23
2.1. Оптимальное программное управление. 23
2.2. Замечания и комментарии . 24
Глава 3. Позиционное управление.. 26
3.1. Оптимальное позиционное управление 26
3.2. Замечания и комментарии. 31
Глава 4. Обобщения и уточнения 33
4.1. К стационарному управлению. 33
4.2. К программному управлению. 35
4.3. К позиционному управлению. 38
Список литературы.
- Качество управления при различных параметрах СМО
- Замечания и комментарии
- Оптимальное позиционное управление
- К программному управлению.
Качество управления при различных параметрах СМО
Приведем точные формулировки главных результатов. Рассматривается система Mk/Dk/l/(ni,...,nk): на 1 однотипных обслуживающих приборов поступают к 2 независимых потоков требований, причем і-й поток формируется конечным источником объема ПІ так, что каждое требование поступает (независимо от других) после пребывания в источнике показательно распределенное с параметром X случайное время. Ориентированный на і-й поток прибор «разогревается» время ч, затем мгновенно обслуживает (т.е. возвращает в і-й источник) все требования, затем «остывает» время S;, после чего снова готов к работе (т.е. к ориентации на тот или иной поток). Считается, что ti+S; 0 для всех і = 1,.. .k1 .
Положим х = x(t) = {x;(t)} (і = l,...,k; t є [0, x )), где xi(t) = nr1yi(t), УІ(Ґ) есть число требований, содержащихся в і-м источнике в момент времени t (xj(t) есть мгновенный коэффициент готовности і-го источника). Управлением назовем пару Здесь и далее смотри соответствующий пункт «Замечаний и комментариев» в конце введения (главы). {
Управление определяет дисциплину обслуживания требований: j-й прибор включается в момент т? и действует непрерывно; если т" (п = 0,1,...) есть n-й по счету момент готовности прибора, то он (прибор) ориентируется на і-й поток с вероятностью pij(Xp х(тр). Уточним, что конкретная ориентация осуществляется вероятностным диспетчером, в который поступает лишь вектор pij = ру(т", х(т? )), «внутренняя» же работа диспетчера не зависит ни от т?, ни от х, ни от работы диспетчера в прошлом2. (везде в работе E — знак математического ожидания; Ri есть коэффициент готовности і-го источника, R — равномерный коэффициент готовности системы). Пусть Uo есть некое подмножество U. Рассмотрим задачу: найти UOEUO такое, что R(u0) = sup R(u)3 (u0 — называется оптимальным в классе Uo).
Исследованы три случая: 1. Uo состоит из таких и, у которых функции pij(t,x) не зависят ни от t, ни от х (стационарное управление). 2. Uo состоит из таких и, у которых функции py(t,x) не зависят от х (программное управление). 3. Uo = U (позиционное управление). Исследованию сформулированной оптимизационной задачи для этих случаев посвящены соответственно главы 1 — 3 диссертации. Кроме того, имеется глава 4, содержащая обобщения и уточнения полученных результатов.
Во втором параграфе исследуется и определяется качество оптимального стационарного управления в зависимости от параметров а і,.. .а Глава 2.
Здесь найдено точное решение задачи нахождения оптимального программного управления. Для управления u, i=l,..,k и j=!,..,! положим tj =t-x Ці-т]) Замечание 1. Таким образом, оптимальным является управление, при котором приборы включаются через равные промежутки времени и последовательно обслуживают все потоки требований. Замечание 2. Разумеется, о единственности оптимального управления здесь не может быть и речи, так как R; вообще не зависят от управления на любом конечном отрезке времени. Кроме того, обслуживаемые потоки допускают любую перестановку.
В процессе исследования экстремальной задачи для позиционного управления получена эффективная оценка, обозначающая ситуации, когда можно обойтись программным управлением.
Нижеследующие теоремы 4 и 5 имеют отрицательный характер; они касаются возможностей некоторых обобщений теорем 1 и 2. Одним (добавим, наиболее труднодоказуемым) из утверждений теоремы 1 является справедливость равенств R1(u0) = ... = Rk(u0). Приводимая ниже теорема 4 сильно уменьшает кажущуюся очевидность этих равенств. Именно, если величины t-b Si (смотри описание СМО) случайные, то равенства, вообще, говоря, нарушаются.
Теорема 4. Пусть к=2. Существуют случайные величины t;,Si (i=l,2) такие что: 1) оптимальное стационарное управление щ существует; 2) для любого оптимального стационарного управления щ справедливо R,(u0) Ф R2(u0).
В рассмотренной СМО время переориентации каждого прибора с і-го на т-й поток равнялось Si+tm. Обобщим ситуацию: пусть указанное время переориентации равняется Tjm; во всем остальном СМО функционирует по вышеописанным правилам. В свете теоремы 2 представлялась естественной гипотеза, что (в измененной ситуации) оптимальным управлением будет следующее: т =(j-l)s/l, j-й прибор последовательно ориентируется на потоки с номерами іі,і2,. ..ДкДіДг?-- -ДкДь- ? где ііДг -ДкДі есть замкнутый маршрут коммивояжера с матрицей {iim}, s — временная протяженность маршрута. Однако попытки доказать эту гипотезу успехом не увенчались, а далее выяснилось, что иначе и не могло быть.
Теперь изменим работу СМО следующим образом: времена пребывания требований в і-ом источнике есть независимые одинаково распределенные случайные величины с функцией распределения F(t) (а не с показательной как было раньше). Теоремы 6 и 7 касаются возможностей обобщения теорем 2, 4 на этот случай. Ниже используется обозначение т0 = т;. Для любых к, 1, П;, і;, є 0 существуют функция распределения F и управление ueU такие, что Щ &, R(u) l-s. 3. Замечания и комментарии.
1. На практике это условие выполняется всегда (к тому же во время tj+S; следует включить время работы вероятностного диспетчера (смотри основной текст введения)). Теоретически же представляет интерес случай tj+Si=0 (для некоторых і); здесь возможны некоторые осложнения и (порой существенные) отклонения от результатов (см. следующее замечание, а также замечания 1.З.1., 1.З.2.).
2. Описанным правилом дисциплина обслуживания действительно определяется однозначно в силу неравенств tj+Sj 0. Тоже верно и при более слабом условии minX(ti+si)pij(t,x) 0; здесь, однако, уже возможны «неприятности»(см. замечание 1.З.2.). Если же не выполнено и это условие, то возможны «мертвые» состояния для некоторых приборов. Способы выхода из таких состояний должны быть оговорены дополнительно, но в любом случае неоднозначны; это приводит к неопределенности случайного процесса x(t), случайных величин К{ и т.д.
3. Ранее рассматривалась задача оптимизации в среднем (см. [37,38]). Точнее: искалось управление (в приведенных работах — детерминированное), минимизирующее общее (т.е. по всем потокам) число требований. Ясно, однако, что во многих ситуациях рассматриваемая нами задача является более естественной.
Замечания и комментарии
Наши предположения (оц 0) гарантируют положительность знаменателя; это также верно при условии а 0. Если а=0, то выражение для Rm имеет форму -. И действительно в данном случае случайная величина Rm определена неоднозначно (см. замеч. 2., введение). Если а;=0 для некоторых і, то теорема теряет силу как в части существования оптимума, так и в части единственности. Все же в этом случае правая часть (11) равна supR(u) (см. теорему 1.2.2.). ueU0
Как видно, основная часть доказательства теоремы посвящена установлению равенств Ri=... = Rk (при оптимальном управлении). На первый взгляд равенства представляются очевидными. Однако очевидность эта кажущаяся. Дело в том, что СМО, управляемая вероятностным диспетчером, функционирует по довольно сложным законам (см. (1)). В частности, здесь возможны «гироскопические эффекты»: увеличение рт может приводить к уменьшению Rm. Причину этого, впрочем, понять нетрудно. Однако следующий результат уже можно отнести к разряду патологических. А именно, изменим работу вероятностного диспетчера следующим образом: в каждый момент готовности прибора тп он (прибор) с вероятностью р0 «отдыхает» время т0 (так что тп+1=тп+т0), а с вероятностью 1-р0 функционирует по описанному во введении правилу (т. е. ориентируется на і-й поток с вероятностью р;, ]Гр; =1). Величина R определяется как во введении (разумеется теперь R=R(p0,plv..,pk) ). Так вот, построен пример, когда p0 q0, но R(p0,p1,...,pk) R(q0,p1,...,pk); другими словами, прибор отдыхает больше, но система функционирует лучше (и это при неизменной приоритетности потоков требований !). Конечно, в этом примере управление (plv..,pk) далеко от оптимального. В главе 4 будет показано, что равенства R, =... = Rk могут нарушаться, если величины t;, ss - случайные.
Можно, однако, доказать, что и недостижима: мешают неравенства aj 0. Если мы предположим только, что ос 0, и при а, =... = ак_, =0, ак=а, р О,... ,, , рк=0 определим дисциплину обслуживания так, что прибор затрачивает нулевое время для обслуживания первых к-1 потоков и потом ориентируется на k-й поток (т. е. выходит из «мертвого» состояния), тогда мы имеем R0 = (сопоставим с доказательством неравенства R0 ).
Можно доказать, что а является внутренней точкой компакта ограничений (25) (т. е. а; 0). Однако, и без этого решение задачи (25) однозначно определяет работу СМО. Действительно, по крайней мере два значения а1 положительны (иначе будет R0(a,k) = - правой части (26)); поэтому z l (см. (9)) и отсюда (см. (9), (10)) рт 0 для всех т, так что а 0, и дисциплина обслуживания определена (см. замеч. 2., введение). 1.3.7. В действительности справедливы строгие неравенства R0(a,k) R0(a,k-l). 1.3.8. Явное аналитическое выражение для R0(a,k) невозможно. Гипотеза R0(a,k)= правой части (26) неверна (даже при к ). На самом деле R0(a,k) является корнем некоторого трансцендентного уравнения, которое не приведено в работе из-за его сложной структуры и практической бесполезности. Некоторым удовлетворением является то, что (26) определяет R0(a,k) достаточно точно (особенно для больших к и малых a).
. Результаты теорем 1.2.2.-1.2.4. приводят к следующим заключениям: оптимальный вероятностный диспетчер работает наиболее эффективно при сильно перекошенных значениях параметров о (a, =... = ак_, = 0,ак =а).В этом случае эффективность даже достигает эффективности оптимального программного управления (см. теорему 2.1.1.). Условия для наихудшей работы оптимального диспетчера неизвестны, однако они близки (особенно при больших к) к условиям a, =... = ak (см. предыдущий пункт и формулы (23),(26),(28)).
Для равномерного диспетчера (р,=... = рк) картина прямо противоположная. Наибольшая эффективность достигается, когда a!=... = ak, и наименьшая при сц =... = ak4 =0, ak = a.
Интересно, что области значений функций R0(alv..,ak), Rv(alv..,ak) это почти непересекающиеся интервалы, а при увеличении к общая часть этих интервалов стремится к нулю (см. (26), (28) и теорему 1.2.4.). Оценки, полученные для R0 и Rv принимают простую форму в случае высокоготовных систем (а мало). Действительно, с точностью до о(а2) справедливы неравенства — l - R0 a, Напомним, что все теоремы главы 1 доказаны для случая 1=1. В случае 1 1 анализ работы стационарного диспетчера резко усложняется и здесь возможно разве что лишь приближенное нахождение оптимального управления. Глава 2. Программное управление.
Для управления и введем обозначения: 4Г т_и момент обслуживания (не важно каким прибором) требований і-го потока ( =0); m(i,T)=min{m: " Т}; которые доказывают теорему.2 2 3 2 2 2.2. Замечания и комментарии. . Это детерминированное управление заключается в следующем: приборы включаются через равные промежутки времени —, каждый прибор последовательно ориентируется на потоки с номерами 1,...,к. Отметим, что такое управление перестает быть оптимальным , если величины t;, s{ - случайные (даже «абсолютно» независимые). Контрпример построен для 1=1, к=2. Этот факт заметно уменьшает интуитивную очевидность теоремы 2.1.1. (см. еще 2.2.5.).
Теорема 2.1.1. дает точное и простое решение задачи программной оптимизации. В связи с этим может возникнуть вопрос: зачем вообще необходима глава 1? Ответ следующий: помимо чисто теоретического интереса к стационарному управлению, легко представить и практическую ситуацию, когда программное управление трудно реализуемо (или невозможно). В добавление к сказанному, актуальными являются две задачи: задача, когда требования однородны лишь в пределах одного источника (т. е. X заменяется на Х{, см. введение) и задача с резервированием. В этих случаях оптимальное программное управление неизвестно, но можно (для любого 1) найти хорошее приближение к оптимальному стационарному управлению.
Оптимальное позиционное управление
Найти это управление не удалось. Естественная гипотеза: прибор ориентируется на поток, источник которого имеет минимальный мгновенный коэффициент готовности, неверна. Для случая 1=1 и чисто позиционного управления (р;(1,х) = р;(х)) мы свели задачу нахождения оптимума к нелинейной алгебраической системе размерности (n, +l)x(n2 +l)x...x(nk+l); решение (даже численное) такой системы при сколько-нибудь заметных к, п; невозможно.
Величина т-т-1 зависит от процесса x(t) на интервале [0, "]. Подчеркнем здесь, что в лемме 3.1.1. мы рассматривали все величины Q- R1, а не только те, которые имеют отношение к процессу х (t) (см. также 3.2.5.).
Здесь и далее не обосновывается законность перестановок сумм (или сумм и интегралов), поскольку все величины неотрицательны.
Доказательство значительно упростилось бы, если бы величина гаЧ не зависела от величин {pm,pm+,,...}. Однако это не так: хотя процесс x(t) на интервале (Е,т \ т) не зависит от шЧ, разность g m_ m-1 зависит от ш_1 (т 1). Более того, эта зависимость сохраняется даже при фиксированной точке вероятностного пространства, формирующего поступления требований из всех источников, исключая і-й, и определяющей внутреннюю работу вероятностного диспетчера (указанная зависимость очевидна в случае явной зависимости рц от времени t; менее очевидна, но также верна, когда p;j(t,x) = ру(х)).
Леммы 3.1.1.,3.1.2. дают решение задачи 3 для случая k=l, tx = sx = 0 при естественном дополнительном ограничении lim у («нечастое» обслуживание): необходимо выжидать до поступления г требований (г определяется условием zr у zr+1), потом ждать некоторое случайное время (см. определение случайной величины 4Г)Т перед леммой З.1.1.; т определено условием А гт=у) и затем переходить к обслуживанию. При таком управлении получим R=cp(y).
В случае t, + Sj 0 для нахождения оптимального управления необходимо решить экстремальную задачу 0(4)- max,4 t,+s,, E y. , — марковский момент для процесса x(t) (без последнего условия обслуживание станет нереальным: диспетчер должен видеть будущее). Сформулированная задача может быть решена; обслуживание снова единственно и чисто позиционно; естественно, что R p(y). Чисто позиционный характер оптимального обслуживания системы M,/D,/l/n,, а также некоторые другие соображения дают основание полагать, что решение задачи 3. существует (к 2) в классе чисто позиционных управлений. Однако вопрос о справедливости этой гипотезы остается открытым.
Аналоги лемм 3.1.1.,3.1.2. справедливы также в случае, указанном в замечании 2.2.6. (глава 2): меняются только числа zr (выражения для них могут быть записаны в явной форме, но несколько сложнее) и, конечно, естественным образом изменяются также правые части (37), (39).
Отметим, что применяя стандартные дисперсионные соотношения, можно получить лишь скорость сближения порядка тахп; 2.
Безнадежны попытки обобщения (во всяком случае прямого) теоремы 3.1.4. на ситуацию, указанную в замечании 2.2.6. (гл. 2): для любого є 0 существуют функция распределения F и управление ueU такие что R s, R(u) l-s (см. главу 4, теорему 4.3.1.). Глава 4. Обобщения и уточнения 4.1. К стационарному управлению.
В этом параграфе рассматривается система массового обслуживания, отличающаяся от рассмотренной в главе 1 тем, что времена t; «разогрева» и Sj «остывания» прибора есть величины случайные. Считается, что случайные векторы (tj,Sj) независимы при различных і, не зависят от времени пребывания в источнике требований и P{tj+Sj 0} 0 для і = l,...,k. В остальном система функционирует по прежним правилам.
В главе 1 (теорема 1.1.2.) доказано, что если величины tbSi не случайные, то оптимальное стационарное управление существует, единственно и выполняются равенства R = R1(u0) = ... = Rk(u0). (49) Ниже доказывается, что в общем случае ситуация иная: хотя оптимальное управление и существует, но равенства (49) могут нарушаться. Соответствующий пример построен уже для к=2 (!). Пусть к=2; t O; Si — случайная величина, принимающая значение - с
Теорема 2.1.1. (глава 2) гласит, что оптимальным программным управлением является такое управление, при котором приборы включаются через равные промежутки времени и последовательно обслуживают все потоки требований. Однако теорема доказана для ситуации, когда время переориентации каждого прибора с і-го на m-й поток равнялось Si+tm (см. введение). Обобщим ситуацию: пусть указанное время равняется т;т; во всем остальном СМО функционирует по прежним правилам (в момент т j-й прибор ориентируется на какой-угодно поток — это не имеет значения; моментом готовности прибора к работе считается момент окончания очередного акта обслуживания). В свете теоремы 2.1.1. представлялась естественной гипотеза, что (в измененной ситуации) оптимальным управлением будет следующее: т- = (j — 1 )s/l; j-й прибор последовательно ориентируется на потоки с номерами іі,і2,...іьіі,І25---іь---5 где ibi2,...ik,ii есть замкнутый маршрут коммивояжера с матрицей {xim }, s — длина маршрута. Однако гипотеза оказалась неверна. Сейчас мы построим контрпример для 1=1, к=4 (при к 4 такой пример невозможен). Обозначим через Rs коэффициент готовности системы при ориентации прибора по маршруту коммивояжера.
Рассмотрим другое управление (и). Оно заключается в следующей ориентации прибора: m раз прибор ориентируется на потоки с номерами 1,2,1, затем 2,3, далее m раз на потоки 3,4,3, и наконец 4,1. Дальнейшая ориентация происходит в той же последовательности. Найдем R для описанного управления (т.е. R(u )) по определению, данному во введении. Так как обход всех потоков завершается за фиксированный период Т=2тє+є+1+2тє+є+1, то учитывая, что Exi(t)=e" и xj(0)=l, имеем
К программному управлению.
Приведем точные формулировки главных результатов. Рассматривается система Mk/Dk/l/(ni,...,nk): на 1 однотипных обслуживающих приборов поступают к 2 независимых потоков требований, причем і-й поток формируется конечным источником объема ПІ так, что каждое требование поступает (независимо от других) после пребывания в источнике показательно распределенное с параметром X случайное время. Ориентированный на і-й поток прибор «разогревается» время ч, затем мгновенно обслуживает (т.е. возвращает в і-й источник) все требования, затем «остывает» время S;, после чего снова готов к работе (т.е. к ориентации на тот или иной поток). Считается, что ti+S; 0 для всех і = 1,.. .k1 .
Положим х = x(t) = {x;(t)} (і = l,...,k; t є [0, x )), где xi(t) = nr1yi(t), УІ(Ґ) есть число требований, содержащихся в і-м источнике в момент времени t (xj(t) есть мгновенный коэффициент готовности і-го источника). Управлением назовем пару Здесь и далее смотри соответствующий пункт «Замечаний и комментариев» в конце введения (главы). {Pij} {т}, где Управление определяет дисциплину обслуживания требований: j-й прибор включается в момент т? и действует непрерывно; если т" (п = 0,1,...) есть n-й по счету момент готовности прибора, то он (прибор) ориентируется на і-й поток с вероятностью pij(Xp х(тр). Уточним, что конкретная ориентация осуществляется вероятностным диспетчером, в который поступает лишь вектор pij = ру(т", х(т? )), «внутренняя» же работа диспетчера не зависит ни от т?, ни от х, ни от работы диспетчера в прошлом2. Обозначим через U множество всех управлений. Далее для определенности считаем, что х(0) = {1, ..., 1} (это предположение несущественно). Для ueU положим (везде в работе E — знак математического ожидания; Ri есть коэффициент готовности і-го источника, R — равномерный коэффициент готовности системы). Пусть Uo есть некое подмножество U. Рассмотрим задачу: найти UOEUO такое, что R(u0) = sup R(u)3 (u0 — называется оптимальным в классе Uo).
Исследованы три случая: 1. Uo состоит из таких и, у которых функции pij(t,x) не зависят ни от t, ни от х (стационарное управление). 2. Uo состоит из таких и, у которых функции py(t,x) не зависят от х (программное управление). 3. Uo = U (позиционное управление). Исследованию сформулированной оптимизационной задачи для этих случаев посвящены соответственно главы 1 — 3 диссертации. Кроме того, имеется глава 4, содержащая обобщения и уточнения полученных результатов.
В первом параграфе для 1=1 найдено точное решение поставленной задачи для первого случая (т.к. 1=1, то индекс] опускается). Т.к. ясно, что переменная R; не зависит от х, полагаем т=0. Во втором параграфе исследуется и определяется качество оптимального стационарного управления в зависимости от параметров а і,.. .а Глава 2. Здесь найдено точное решение задачи нахождения оптимального программного управления.
В процессе исследования экстремальной задачи для позиционного управления получена эффективная оценка, обозначающая ситуации, когда можно обойтись программным управлением.
Нижеследующие теоремы 4 и 5 имеют отрицательный характер; они касаются возможностей некоторых обобщений теорем 1 и 2. Одним (добавим, наиболее труднодоказуемым) из утверждений теоремы 1 является справедливость равенств R1(u0) = ... = Rk(u0). Приводимая ниже теорема 4 сильно уменьшает кажущуюся очевидность этих равенств. Именно, если величины t-b Si (смотри описание СМО) случайные, то равенства, вообще, говоря, нарушаются.
Теорема 4. Пусть к=2. Существуют случайные величины t;,Si (i=l,2) такие что: 1) оптимальное стационарное управление щ существует; 2) для любого оптимального стационарного управления щ справедливо R,(u0) Ф R2(u0).
Далее опять величины t;,Sj — не случайные. В рассмотренной СМО время переориентации каждого прибора с і-го на т-й поток равнялось Si+tm. Обобщим ситуацию: пусть указанное время переориентации равняется Tjm; во всем остальном СМО функционирует по вышеописанным правилам. В свете теоремы 2 представлялась естественной гипотеза, что (в измененной ситуации) оптимальным управлением будет следующее: т =(j-l)s/l, j-й прибор последовательно ориентируется на потоки с номерами іі,і2,. ..ДкДіДг?-- -ДкДь- ? где ііДг -ДкДі есть замкнутый маршрут коммивояжера с матрицей {iim}, s — временная протяженность маршрута. Однако попытки доказать эту гипотезу успехом не увенчались, а далее выяснилось, что иначе и не могло быть.
Теорема 5. При k 3 указанная гипотеза неверна. Теперь изменим работу СМО следующим образом: времена пребывания требований в і-ом источнике есть независимые одинаково распределенные случайные величины с функцией распределения F(t) (а не с показательной как было раньше). Теоремы 6 и 7 касаются возможностей обобщения теорем 2, 4 на
Теорема 8. Для любых к, 1, П;, і;, є 0 существуют функция распределения F и управление ueU такие, что Щ &, R(u) l-s. 3. Замечания и комментарии.
1. На практике это условие выполняется всегда (к тому же во время tj+S; следует включить время работы вероятностного диспетчера (смотри основной текст введения)). Теоретически же представляет интерес случай tj+Si=0 (для некоторых і); здесь возможны некоторые осложнения и (порой существенные) отклонения от результатов (см. следующее замечание, а также замечания 1.З.1., 1.З.2.).
2. Описанным правилом дисциплина обслуживания действительно определяется однозначно в силу неравенств tj+Sj 0. Тоже верно и при более слабом условии minX(ti+si)pij(t,x) 0; здесь, однако, уже возможны «неприятности»(см. замечание 1.З.2.). Если же не выполнено и это условие, то возможны «мертвые» состояния для некоторых приборов. Способы выхода из таких состояний должны быть оговорены дополнительно, но в любом случае неоднозначны; это приводит к неопределенности случайного процесса x(t), случайных величин К{ и т.д.
