Конспект лекций case cals. Конспект_САСТ-2. Конспект лекций по дисциплине case и cals технологии по направлению подготовки
 Скачать 3.53 Mb.
|
|
Определение: Поток требований называют однородным, если он удовле- творяет условиям: 1) все заявки потока с точки зрения обслуживания являются равноправны- ми; 2)вместо требований (событий) потока, которые по своей природе могут быть различными, рассматриваются толь ко моменты их поступления. Определение: Регулярным называются поток, если события в потоке сле- дуют один за другим через строгие интервалы времени. Функция f(х) плотности распределения вероятности случайной величины Т – интервала времени между событиями имеет при этом вид: , где - дельта функция, М т - математическое ожидание, причем М т =Т, дисперсия D т =0 и интенсивность наступления событий в поток =1/M т =1/T. Определение: Поток называют случайным, если его события происходят в случайные моменты времени. Случайный поток может быть описан как случайный вектор, который, как известно, может быть задан однозначно законом распределения двумя способа- ми: а) Заданием закона распределения моментов появления событий 205 Здесь n ..., , , 2 1 - случайные моменты времени появления событий в по- токе, t 1 , t 2 , t n - их назначение, Р – вероятность; б) Заданием многомерного закона распределения системы случайных ве- личин Т 1 , Т 2 , …, Т n , являющихся длинами интервалов между последовательными событиями : где z i - значения T i (i=1,…,n), В этом случае моменты наступления событий могут быть вычислены следующим образом t 1 =t 0 +z 1 t 2 =t 1 +z 2 ………, где t 0 - момент начала потока. 11.1.7.2. Простейший пуассоновский поток. Для решения большого числа прикладных задач бывает достаточным при- менить математические модели однородных потоков, удовлетворяющих требо- ваниям стационарности, без последействия и ординарности. Определение: Поток называется стационарным, если вероятность появле- ния n событий на интервале времени (t,t+T) зависит от его расположения на вре- менной оси t. 206 Определение: Поток событий называется ординарным, если вероятность появления двух или более событий в течении элементарного интервала времени t есть величина бесконечно малая по сравнению с вероятностью появления од- ного события на этом интервале, т.е. при n=2,3,… Определение: Поток событий называется потоком без последствия, если для любых непересекающихся интервалов времени число событий, попадающих на один из них, не зависит от числа событий попадающих на другой. Определение: Если поток удовлетворяет требованиям стационарности, ор- динарности и без последствия он называется простейшим, пуассоновским пото- ком. Доказано, что для простейшего потока число n событий попадающих на любой интервал z распределено по закону Пуассона: (11.1) Вероятность того, что на интервале времени z не появится ни одного со- бытия равна: z e z P ) , 0 ( (11.2) тогда вероятность противоположного события: z e z T P 1 ) ( где по определению P(T z e dz dF z f ) ( (11.3) 207 параметр называют плотностью потока. Причем, Впервые описание модели простейшего потока появились в работах вы- дающихся физиков начала века – А. Эйнштейна и Ю.Смолуховского, посвящен- ных броуновскому движению. 11.1.7.3. Свойства простейшего пуассоновского потока Известны два свойства простейшего потока, которые могут быть исполь- зованы при решении практических задач. 1) Введем величину z a . В соответствии со свойствами Пуассоновского распределения при оно стремится к нормальному. Поэтому для больших а для вычисления Р{Z(а)меньше, либо равно n}, где Z(а) – случайная величина распределенная по Пуассону с матожиданием а можно воспользоваться следую- щим приближенным равенством: , 2 ) ( exp 2 1 ) ( 2 1 2 2 1 a a n dt a a t a n a Z P n (11.4) где z dt t z 0 2 2 exp 2 2 2) Еще одно свойство простейшего потока связано со следующей теоре- мой: 208 Теорема: При показательном распределении интервала времени между требованиями Т, независимо от того, сколько он длился, оставшаяся его часть имеет тот же закон распределения. Доказательство: пусть Т распределено по показательному закону: Предположим, что промежуток а уже длился некоторое время а<Т. Найдем условный закон распределения оставшейся части промежутка Т1=Т-а Fa(x)=P(T-a По теореме умножения вероятностей: P((T>a)(T-a Отсюда, равносильно событию а Fa(x)=(F(z+a)-F(a))/(1-F(a)) Отсюда, учитывая (12.3): 209 Этим свойством обладает только один вид потоков – простейшие пуассо- новские 11.1.7.4. Простейший поток и решение практических задач Исследование задач ТСМО становится намного проще в предположении, что исходный поток является простейшим пуассоновским. Однако критическое изучение условий, которые приводят к простейшему потоку, заставляют сделать вывод, что простейшие потоки встречаются не так часто. Например, зачастую нарушается ординарность – одновременно происхо- дят заказ одного и того же номера по телефону, необходимо ставить несколько машин под загрузку или разгрузку и т.д. Условие стационарности так же часто не выполняется, например меняется интенсивность заказов на переговоры в те- чении суток. Несоблюдение условия без последствия так же является обычным. Примером этого может служить поломка машин таксопарка, которая может при- вести (из-за увеличения нагрузки) к поломкам других машин. Но в действительности простейшие потоки встречаются гораздо чаще, чем это кажется после приведенных соображений. Объяснением этого занимался шведский ученый Пальма. Позднее Хинчин А.Я. доказал одну общую теорему, которая представляет исключительную теоретическую ценность. Хинчин доказал, что если поток является суммой большого числа n неза- висимых ординарных, стационарных потоков интенсивности которых и ни один из них не является сравнимым по мощности со всем суммарным пото- ком, то при некоторых аналитических ограничениях суммарный поток сходится к простейшему с интенсивностью 210 Теорема Хинчина широко применяется на практике. Так под руководством Гнеденко был исследован поток судов, прибывающих в грузовой порт. Стати- стическая обработка позволила сделать вывод о достаточно хорошем совпадении реального потока с простейшим. На основании этого были сделаны прогнозы относительно прибытия судов на последующие месяцы. 11.1.7.5. Нестационарные пуассоновские потоки Теорема Хинчина была обобщена на случай, когда слагаемые потоки яв- ляются неординарными и нестационарными. При этом, если слагаемые потоки независимы и их интенсивность приблизительно одинакова, то суммарный поток близок к пуассоновскому, но с примененным параметром ) (t Причем (t) называется мгновенной плотностью. Она является пределом отношения среднего числа событий, приходящихся на элементарный интервал времени (t, t+x) к длине интервала, когда последний стремится к нулю. Здесь M(t) – мат ожидание числа событий на интервале t. t Доказано, что для такого потока число событий n попадающих на времен- ной интервал z, начинающихся в момент t 0 , распределено по закону Пуассона, а именно: , (11.5), 211 где - математическое ожидание числа событий на интервале (t 0 ,t+x), рав- ные: Здесь очевидно зависит от длины интервала и от его положения на вре- менной оси. Аналогично тому, как была выведена функция плотности распределения вероятности для простейшего пуассоновского потока (5.3), можно получить функцию плотности распределения вероятности Т для нестационарного пуассо- новского потока: Рассматриваемая модель принадлежит математику из Вильнюса Б.И. Гри- гелионису. Этой математической моделью описывается огромнейшее число по- токов – вызов врача к больному, поток телеграмм, поток заказов на переговоры, потоки пассажиров и т.д. 11.1.7.6. Потоки с ограниченным последствием (потоки Пальма). Другим обобщением простейшего потока является поток Пальма: Определение: Потоком Пальма называется поток, обладающий свойствами стационарности, ординарности и независимости интервалов времени Т между событиями. 212 Требование независимости интервалов Т является более слабым чем тре- бование без последствия, поэтому такие потоки называют также потоками с ог- раниченными последствиями. Теорема: пусть в систему поступает поток заявок типа Пальма. Заявка, за- ставшая все каналы занятыми, получает отказ. Если при этом время обслужива- ния имеет показательный закон распределения, то поток не обслуженных заявок является потоком Пальма. Простейший поток является частным случаем потока Пальма. Его незави- симые интервалы распределены по показательному закону. Еще одним примером потоков Пальма являются потоки Эрланга, которые могут быть получены следующим образом: Если из простейшего потока исключается каждое второе требование, то оставшийся поток образует поток второго порядка, если в потоке сохраняется каждое третье, то это – поток третьего порядка и т.д. Для потока к-го порядка функция плотности для интервала Т имеет вид: (11.6) C увеличением порядка k функция f k (х) убывает, но М[Т] возрастает: При достаточно большом k (практически при k-5) поток Эрланга k-ого по- рядка можно считать нормальным с указанными М[T] и D[T]. Это следует из то- го, что интервал времени Т между двумя последовательными событиями в пото- ке Эрланга k-ого порядка представляет собой сумму k независимых случайных 213 величин с одним законом распределения. Тогда на основании центральной пре- дельной теоремы теории вероятностей имеем доказательство утверждения. Задавая различные значения k в (11.6) можно получить потоки, обладаю- щие различными последействиями – от полного его отсутствия (k=1) до полной функциональной связи между моментами появления событий (регулярный по- ток). На самом деле: при k=1 получаем простейший поток, а при l =const и при k поток Эрланга приближается к регулярному. Свойства потоков Эрланга дает возможность широкого применения этой математической модели. 11.1.7.7. Потоки восстановления. На практике нередко приходится сталкиваться с потоками, получившими название потоков восстановления. Примером образования такого потока являет- ся ситуация, когда в состоянии непрерывной работы должно находиться устрой- ство. Как только оно перестает выполнять свои функции (старение, поломка) его заменяют на такое же, но новое. Моменты замены t k , k=1,2, … являются случай- ными, так как длительность безотказной работы каждого устройства тоже вели- чина случайная, независимая и имеет свое распределение F(z). В литературе та- кие потоки обозначают GI – общий входящий поток (general imput). Для потоков восстановления существует большое число разнообразных задач; в частности задача определения вероятности того, что в течении заданно- го промежутка времени T появится k событий потока. Простых формул, которые были выведены для простейшего потока, здесь уже нет. Интересными для практики являются потоки, которые с течениями време- ни “редеют”, проходя через последовательность приборов обслуживания. При- мером этого может быть деталь, которая проходит ряд операций и на каждой операции есть вероятность обнаружения скрытого дефекта. В таких случаях де- таль устраняется, а первоначальный поток редеет. Еще одним примером может 214 служить исправление последовательно во времени текста несколькими коррек- торами. При этом количество незамеченных опечаток редеет. Венгерским мате- матиком А.Реньи был получен интересный результат, который заключается в следующем. Поток восстановления подвергается операции: каждое требование остается в потоке с вероятностью q и выбрасывается из потока с вероятностью p=1-q. Одновременно производится изменение масштаба времени: за единицу масштаба считается промежуток длиной q-1. Если это двойное преобразование обозначить символом R q , то последовательное проведение преобразований R q1 , R q2 , …, R qn эквивалентно одному преобразованию R q1q2…qn . Теорема Реньи со- стоит в том, что если длительность безотказной работы распределена по закону F(х) имеет конечное математическое ожидание М и то последовательность редеющих потоков стремится к простейшему пуас- соновскому потоку. Таким образом, в определенных условиях потоки восстановления стано- вятся простейшими, что еще раз подтверждает справедливость теоремы Хинчи- на. 11.2 Сети Петри Сети Петри – аппарат для моделирования динамических дискретных сис- тем (преимущественно асинхронных параллельных процессов). Сеть Петри оп- ределяется как четверка <Р, Т, I, О>, где Р и Т – конечные множества позиций и переходов, I и О – множества входных и выходных функций. Другими словами, сеть Петри представляет собой двудольный ориентированный граф, в котором позициям соответствуют вершины, изображаемые кружками, а переходам – вер- шины, изображаемые утолщенными черточками; функциям I соответствуют ду- 215 ги, направленные от позиций к переходам, а функциям О – от переходов к пози- циям. Как и в системах массового обслуживания, в сетях Петри вводятся объек- ты двух типов: динамические – изображаются метками (маркерами) внутри по- зиций и статические – им соответствуют вершины сети Петри. Распределение маркеров по позициям называют маркировкой. Маркеры могут перемещаться в сети. Каждое изменение маркировки называют событием, причем каждое событие связано с определенным переходом. Считается, что со- бытия происходят мгновенно и разновременно при выполнении некоторых усло- вий. Каждому условию в сети Петри соответствует определенная позиция. Со- вершению события соответствует срабатывание (возбуждение или запуск) пе- рехода, при котором маркеры из входных позиций этого перехода перемещаются в выходные позиции. Последовательность событий образует моделируемый про- цесс. Правила срабатывания переходов (рис. 12.1) конкретизируют следующим образом: переход срабатывает, если для каждой из его входных позиций выпол- няется условие N t > K t , где N t – число маркеров в t-й входной позиции, К t - число дуг, идущих от t-й позиции к переходу; при срабатывании перехода число маркеров в t-й входной позиции уменьшается на K t , а (t+1)-й выходной по- зиции увеличивается на K t , где K t – число дуг, связывающих переход с t-й пози- цией. На рис. 6 показан пример распределения маркеров по позициям перед сра- батыванием, эту маркировку записывают в виде (2,2,3,1). После срабатывания перехода маркировка становится иной: (1,0,1,4). Можно вводить ряд дополнительных правил и условий в алгоритмы моде- лирования, получая ту или иную разновидность сетей Петри. Так, прежде всего полезно ввести модельное время, чтобы моделировать не только последователь- ность событий, но и их привязку ко времени. Это осуществляется приданием пе- реходам веса – продолжительности (задержки) срабатывания, которую можно 216 определять, используя задаваемый при этом алгоритм. Полученную модель на- зывают временной сетью Петри. Если задержки являются случайными величинами, то сеть называют сто- хастической. В стохастических сетях возможно введение вероятностей срабаты- вания возбужденных переходов. Так, на рис. 12.2 представлен фрагмент сети Петри, иллюстрирующий конфликтную ситуацию – маркер в позиции р может запустить либо переход t 1 , либо переход t 2 . В стохастической сети предусматри- вается вероятностный выбор срабатывающего перехода в таких ситуациях. Р t 1 t 2 Рис. 11.1. Фрагмент сети Петри Рис. 11.2. Конфликтная ситуация Если задержки определяются как функции некоторых аргументов, кото- рыми могут быть количества маркеров в каких-либо позициях, состояния неко- торых переходов и т. п., то сеть называют функциональной. Во многих задачах динамические объекты могут быть нескольких типов, и для каждого типа нужно вводить свои алгоритмы поведения в сети. В этом слу- чае каждый маркер должен иметь хотя бы один параметр, обозначающий тип маркера. Такой параметр обычно называют цветом; цвет можно использовать как аргумент в функциональных сетях. Сеть Петри при этом называют цветной. Среди других разновидностей сетей Петри следует упомянуть ингибитор- ные сети, характеризующиеся тем, что в них возможны запрещающие (ингиби- торные) дуги. Наличиемаркера во входной позиции, связанной с переходом ин- 217 гибиторной дугой, означает запрещение срабатывания перехода. Введенные по- нятия поясним на следующих примерах. Пример 1. Требуется описать с помощью сети Петри работу группы поль- зователей на единственной рабочей станции WS при заданных характеристиках потока запросов на пользование WS и характеристиках поступающих задач. Сеть Петри представлена на рис. 11.2. Здесь переходы связаны со следующими событиями: 1 t – поступление за- проса на использование WS, 2 t – занятие станции, 3 t – освобождение станции, 4 t – выход обслуженной заявки; позиция р 4 используется для отображения состоя- ния WS: если в р 4 имеется метка, то WS свободна и пришедшая заявка вызывает срабатывание перехода 2 t ; пока эта заявка не будет обслужена, метки в р 4 не бу- дет, следовательно, пришедшие в позицию 2 p запросы вынуждены ожидать сра- батывания перехода t 3 t 1 t 2 t 4 t 3 p 1 p 2 p 3 p 4 Рис. 11.3. Сеть Петри к примеру 1 |