Математические методы исследования экономики

К.А.ДЖАФАРОВ МАТЕМАТИЧЕСКИЕ МЕТОДЫ ИССЛЕДОВАНИЯ ЭКОНОМИКИ Курс лекций I. Случайные процессы Теория случайных процессов изучает закономерности случайных явлений в динамике их развития. Случайный процесс – это функция x(t,), которая определяется так: при фиксированном t x(t,) является обычной случайной величиной (сечение случайного процесса в момент t). при фиксированном  x(t,) является обычной функцией (реализация случайного процесса). Имеем функцию x(t,), , t, . x(t,)=X(t) Реализация процесса.  (x,t) – плотность распределения случайных процессов. Случайный процесс Х(t) – это совокупность всех сечений при всевозможных значениях t. Поэтому для его описания необходимо рассмотреть многомерную случайную величину, состоящую из всех сечений данного процесса (Х(t1),X(t2),…,X(tn) ) через многомерную плотность ( х1,…,xn t1,…,tn) Числовые характеристики случайного процесса 1. Математическое ожидание. Математическим ожиданием случайного процесса Х(t) называется неслучайная функция ax(t), которая при любом значении t равна математическому ожиданию соответствующего сечения случайной процесса Х(t). ax(t)=Е Х(t) 2. Дисперсия. Дисперсией случайных процессов называется функция Dx(t), которая при любом значении t равна дисперсии соответствующего сечения случайного процесса. Dx(t)=D Х(t) Среднеквадратичное отклонение - х= Математическое ожидание характеризует среднюю траекторию всех возможных его реализаций, а его дисперсия характеризует разброс реализаций относительно средней траектории. Зависимость между сечениями характеризуется корреляционной функцией. Корреляционной функцией называется неслучайная функция: Кх(t1,t2)=E[(x(t1) – ax(t1)) (x(t2) – ax(t2))],которая при каждой паре t1 и t2 равна ковариации соответствующих сечений. Кх(t1,t2) характеризует не только степень тесноты линейной зависимости между сечениями, но и разброс этих сечений относительно математического ожидания. Нормированная корреляционная функция определяет степень тесноты линейной зависимости между сечениями. х= Пример. Пусть случайный процесс определяется формулой Х(t) =Х cos t, где Х – случайная величина. ЕХ = а, DX = 2. Найти числовые характеристики процесса. ax(t)= Е Х(t) = E[Х cos t] = cos t EX = a cos t Dx(t)=D Х(t) = D(Xcos t) = 2 cos2 t Кх(t1,t2)=E[(x(t1) – ax(t1)) (x(t2) – ax(t2))] = = E[(Х cos t1 - a cos t1)( Х cos t – a cos t2) = cos t1 cos t2 E(X – a)2 х== = 1 Примеры известных случайных процессов: Марковские процессы. Случайный процесс Х(t) называется марковским без последствия, если для любого момента t0 вероятностные характеристики процесса в будущем зависят только от его состояния в данный момент (t0). Х(t0) = k – процесс в состоянии k. И не зависит от того, когда и как система пришла в это состояние. Пусть Х(t) – марковский процесс. Еk – состояние процесса. Это множество значений этого процесса. Оно счётное. Ek = { X(t) = k} – процесс принимает значение k в момент t. t – дискретное. X(t) – марковский процесс со счётным множеством значений и дискретным временем (дискретные цепи Маркова). t – непрерывное. X(t) – марковский процесс со счётным множеством значений и непрерывным временем. Пусть Pij(t) - вероятность перехода их состояния Ei в состояние Ej за промежуток времени t. Эти вероятности подчиняются уравнению Колмогорова-Чепмена. Pij(t+s) = Pik(t) Pjk(s) Рассмотрим промежуток времени t+s. Вероятность попасть из состояния i в состояние j за промежуток времени t+s определяется так: Система переходит в состояние Ek за время t, а в состояние Ej за время s. От того, в какой момент система была в Ei и перешла в Ej вероятность не зависит. Это однородность времени: вероятность зависит от длины промежутка t, а не от его нахождения. Пуассоновский процесс. X(t) – пуассоновский процесс, для которого вероятности состояний определяются так: P ( X(t) = k ) = X(t) имеет пуассоновское распределение с параметром t. Пуассоновский процесс – это процесс, когда переход из состояния Еi в состояние Ej возможен только в состояние Ei+1 с интенсивностью . Остальные переходы маловероятны. Смысл : вероятность перехода из состояния Ej в состояние Ei+1 будет равна t+ o(t), где o(t) – бесконечно малая. Остальные вероятности перехода будут равны o(t). Свойства пуассоновского процесса (см.ниже). Процесс размножения и гибели (ПРГ) (более подробно ниже) X(t) – процесс, для которого переход из состояния Ei возможен либо в состояние Ei+1, либо в состояние Ei – 1. Остальные переходы маловероятны. Если переход в Ei+1, то это размножение, а если в Ei – 1, то это гибель. i – числовая характеристика, отвечающая за размножение (интенсивность размножения). i – числовая характеристика, отвечающая за гибель (интенсивность гибели). ПРГ соответствует следующая диаграмма состояний (граф). II. Теория массового обслуживания § 1. Введение Теория массового обслуживания иначе называется Теория очередей. И действительно, теория массового обслуживания в значительной степени посвящена изучению очередей, возникающих в различных системах. Основными характеристиками систем массового обслуживания являются следующие случайные величины: • среднее время пребывания клиента в очереди; • доля времени, в течение которого система простаивает (из-за отсутствия клиентов). Функциональные возможности систем массового обслуживания определяются следующими факторами: • распределение моментов распределения клиентов; • распределение продолжительности обслуживания; • конфигурация обслуживающей системы (последовательное, параллельное или параллельно-последовательное обслуживание); • дисциплина в очереди (обслуживание в порядке поступления, обслуживание в обратном порядке, случайный отбор клиентов); • вместимость блока ожидания (ограниченная или неограниченная); • емкость или мощность источника требования (ограниченная и неограниченная); • некоторые другие характеристики системы (возможности клиентов переходить из одной очереди в другую, ненулевая вероятность отказа и др.). Основными факторами являются первые два. Любая система массового обслуживания состоит из следующих основных элементов: • входной поток клиентов; • обслуживающий прибор; • дисциплина в очереди. § 2. Входной поток клиентов Рассмотрим последовательности случайных величин . Предположим, что to = 0 – начальный момент функционирования системы; t1 = to + τ1, t2 = t1 + τ2, …, tk = tk-1 + τk, …., где τk – независимые случайные величины, имеющие показательное распределение с параметром λ. Здесь t1 – момент поступления первого клиента, τ1 – промежуток времени между началом работы системы и моментов прихода первого клиента, τ2 – промежуток времени между моментами прихода первого и второго клиентов, и т.д. Последовательность , заданная вышеуказанным образом называется простейшим (пуассоновским) потоком. А постоянная называется параметром простейшего потока. Свойства простейшего потока 1. Сдвиг потока на величину Т Пусть имеется простейший поток с параметром λ. Сдвигая поток на величину Т, получаем поток , который также будет являться простейшим потоком с тем же параметром λ. Например, если T находится между и , то новый поток выглядит так: , …. 2. Слияние двух потоков Пусть имеются два независимых простейших потока с параметрами λ(1), λ(2) соответственно. Будем говорить, что поток образовался в результате слияния двух потоков, если множество {tk} есть объединение множеств {tk(1)}, {tk(2)} и элементы множества {tk} упорядочены в порядке возрастания. Поток , получившийся в результате слияния двух независимых простейших потоков , является тоже простейшим потоком с параметром λ = λ(1) + λ(2), где λ(j) – параметр потока 3. Разделение простейшего потока Пусть имеется простейший поток с параметром λ, и последовательность независимых случайных величин , принимающих два значения: P(ξi = 1) = p, P(ξi = 0) = q, p  0, q  0, p + q = 1. Такие случайные величины называются бернуллиевскими (с параметром p). Процедура разделения потока {tk} состоит в следующем: число ti отнесем к первому потоку, если ξi = 1; если же ξi = 0, то число ti отнесем ко второму потоку. Такую операцию разделения потока на два назовем бернуллиевской (с параметром p). Потоки , полученные в результате бернуллиевского разделения простейшего потока , являются независимыми простейшими потоками с параметрами λ(1) = λp, λ(2) = λq соответственно. Отметим, что доказательства этих свойств простейшего потока можно найти в [ ]. Через X(t) в дальнейшем будем обозначать число клиентов в системе в момент t, т.е. Свойства пуассоновских процессов 1) X(t) есть пуассоновский процесс с параметром λ, т.е. 2) Приращение пуассоновского процесса однородное. Обозначим через X((a,b]) = X(b) – X(a) приращение процесса, которое может быть интерпретировано как число клиентов, поступающих в систему в промежутке (a,b]. Однородность означает выполнение условия: P(X((a,b]) = k) = P(X((0,b-a]) = k) = P(X(b-a) = k), т.е. распределение вероятностей числа клиентов, поступающих в систему в промежутке (a,b], зависит только от длины этого промежутка. 3) Приращения пуассоновского процесса независимы. Рассмотрим промежуток (0, b] и предположим, что он разбит на непересекающиеся промежутки (0, b1], (b1, b2], , (bN-1, bN]. Пусть b0 = 0. Тогда X((b0, b1]), X((b1, b2]), , X((bN-1, bN]) – число клиентов, поступающих в систему в соответствующие периоды времени. Эти величины независимы, т.е. P(X((b0, b1]) = i1, , X((bN-1, bN]) = iN) = = P(X((b0, b1]) = i1)  P(X((bN-1, bN]) = iN). Доказательства этих свойств можно найти в [1 ]. Задачи к § 2. 2.1. Имеются две случайные величины 1 и 2. Они независимые и имеют показательное распределение с параметрами 1 и 2 соответственно. Введем следующую случайную величину:  = min{1, 2}. Доказать, что эта величина имеет показательное распределение с параметром =1+2. 2.2. Даны две независимые случайные величины 1 и 2, имеющие пуассоновское распределение с параметром 1 и 2 соответственно. Пусть случайная величина  =1+2. Доказать, что эта величина имеет распределение Пуассона с параметром =1+2. 2.3. Пусть  - число клиентов в магазинах и имеет распределение Пуассона с параметром . Пусть каждый клиент с вероятностью p делает покупку в этом магазине. Требуется доказать, что число клиентов, сделавших покупку в этом магазине, имеет распределение Пуассона с параметром p. 2.4. Посетители приходят в ресторан в соответствии с пуассоновским потоком со средней частотой 20 посетителей в час. Ресторан открывается в 11.00. Найти: а) вероятность того, что в 11.12 в ресторане окажется 20 посетителей при условии, что в 11.07 в ресторане было 18 посетителей; б) вероятность того, что новый посетитель прибудет в ресторан в интервале между 11.28 и 11.30, если известно, что предыдущий посетитель прибыл в ресторан в 11.25. 2.5. Продукция берется со склада, вмещающего 80 единиц складируемой продукции, в соответствии с пуассоновским потоком с интенсивностью 5 единиц продукции вдень. Найти: а) вероятность того, что в течении первых двух дней со склада будет взято 10 единиц продукции; б) вероятность того, что к концу четвертого дня на складе не останется ни одной единицы продукции. § 3. Процесс гибели и размножения Построим процесс гибели и размножения X(t) «конструктивно». Рассмотрим две последовательности и . Первая - отвечает за поступление клиентов в систему (размножение), а вторая - за обслуживание клиентов (гибель): • интенсивность поступления клиентов (число клиентов, которое поступает в систему за единицу времени, если в ней i клиентов). • интенсивность обслуживания клиентов (число клиентов, которое обслуживается в системе за единицу времени, если в ней i клиентов). Кроме того, пусть заданы две независимые последовательности независимых случайных величин с показательным распределением с параметром =1. Процесс X(t) строится так. Пусть , где . Тогда на интервале процесс X(t) сохранит свое значение , где , . В момент t1 значение процесса X(t) либо увеличится, либо уменьшится на единицу в соответствии с тем, какой из двух моментов наступит раньше: Мы положили, таким образом, значение процесса X(t) в точке t1 равным ; тогда эволюция процесса X(t) на интервале , где и , подчиняется тому же закону закону: X(t) не меняется на этом интервале в момент t2 увеличивается на единицу, если , и уменьшается на единицу в противном случае. Если же , то значение процесса X(t) увеличивается на единицу в случайный момент . Построенный таким образом процесс , называется однородным по времени процессом гибели и размножения; его распределения полностью определяются набором параметров , и начальным распределением X(0): Удобно использовать следующую диаграмму для представления развития процесса X(t): Стрелочки сверху соответствуют динамике процесса размножения: из i-го состояния процесс переходит в (i+1)-е состояние с интенсивностью ; стрелочки снизу соответствуют динамике процесса гибели: с интенсивностью процесс из i-го состояния переходит в (i-1)-е состояние. Набор функций описывает распределение процесса X(t); ниже мы приведем систему уравнений, которым удовлетворяют эти функции. Отметим, что не всякому набору параметров отвечает «невырожденный» процесс X(t); дело в том, что если числа растут очень быстро при , то процесс X(t) в конечный момент t может «взорваться», т.е. с положительной вероятностью превысить любой уровень и возрасти до . Так ведут себя, например, популяция бактерий в благоприятной среде. Аналогично устроены процессы, описывающие химические реакции, приводящие к взрыву. Процессы X(t), для которых все , относятся к так называемым процессам чистого размножения. Процессы, для которых , называют процессами чистой гибели. Следующая лемма дает необходимые и достаточные условия на параметры , которые гарантируют конечность процесса чистого размножения с параметрами . Лемма. Пусть процесс чистого размножения с параметрами . Тогда для конечности процесса необходимо и достаточно, чтобы расходился ряд Пусть X(t) процесс гибели и размножения с теми же параметрами процесса , а также параметрами . Очевидно, что P(X(t)  )  P(X+(t)  ) . Поэтому из леммы получаем следствие. Следствие. Если для произвольного процесса гибели размножения X(t) выполнено условие , то для любого справедливо P(X(t)  ) = 1, т.е. процесс конечен. Доказательство леммы можно найти в [ 1 ]. Задачи к § 3 3.1. Рассмотрим процесс гибели и размножения, для которого Требуется изобразить диаграмму, отвечающую этому процессу. 3.2. Пусть клиенты, которые хотят получить справку по телефону, образуют простейший поток с параметром . Пусть каждый разговор длится -показательное время. Пусть X(t) – число клиентов в системе в момент t. Изобразить диаграмму, отвечающую процессу X(t). 3.3. Пусть в условиях задачи 3.2 1) телефон имеет память на одного клиента: если клиент звонит и телефон занят, но память телефона свободна, то автомат предлагает положить трубку и ждать звонка. Когда телефон освободится, звонок прозвучит; 2) имеется автоматический коммутатор и два телефона, у каждого телефона свой оператор: если в момент звонка клиента имеется свободный телефон, то коммутатор автоматически адресует клиента на этот телефон; 3) коммутатор (см п.2)) имеет память на одного клиента; 4) каждый телефон (см.п.2)) имеет память на одного клиента. Для всех вышеперечисленных случаев изобразить диаграмму, отвечающему процессу X(t). 3.4. Установить, являются ли конечными процессы чистого размножения со следующими интенсивностями размножения: а) k =k+, >0,  >0, k = 0, 1, ... б) 0 = 1, k+1 = (k+1)k, k = 0, 1, ... в) k = k, k = 0, 1, ...  > 0. § 4. Дифференциальные уравнения, отвечающие процессу гибели и размножения Предположим, что X(t) – процесс гибели и размножения с характеристиками и . Пусть для некоторых конечных чисел A и B имеют место неравенства i  A + Bi, i = 0, 1, ...Это условие гарантирует конечность процесса X(t). При этом мы условимся, что в каждое состояние приходит верхняя стрелочка слева (даже в состояние 0), при этом интенсивность рождения λ может равняться нулю (например, λ–1= = 0); из каждого состояния выходит нижняя стрелочка влево, и интенсивность гибели μ тоже может равняться нулю (например, λ–1 = 0). Доопределение таким образом диаграммы не меняет суть дела, однако в дальнейших рассуждениях будет полезно. Рассмотрим диаграмму, отвечающую нашему процессу X(t): Обозначим, как и ранее, через Pk(t) = P(Х(t) = k), k = 0,1,…, вероятности того, что в фиксированный момент t число клиентов X(t) будет равно k. Теорема 1. Характеристики процесса X(t), определенное выше, удовлетворяет следующей системе дифференциальных уравнений где k = 0,1,…, и начальным условиям Нелишне пояснить, что первая строка (при k = 0) системы уравнений (1) имеет вид Доказательство. Обозначим через Pk(t + Δ) = P(X(t + Δ) = k). Воспользуемся определением производной функции одной переменной: . Рассмотрим такие события: A0(t, Δ) = {на отрезке [t, t +Δ] процесс X(t) не совершил ни одного скачка}; A1(t, Δ) = {на отрезке [t, t +Δ] процесс X(t) совершил ровно один скачок}; A2(t, Δ) = {на отрезке [t, t +Δ] процесс X(t) совершил два скачка и более}. Тогда очевидно, что Обозначим далее через три показательные случайные величины с параметрами ; через три показательные случайные величины с параметрами . Пусть все эти величины независимы. Тогда верно В последнем равенстве мы воспользовались следующим свойством показательной функции: e–Δ = 1 – Δ + o(Δ) при Δ → 0. Аналогично получаем Точно также устанавливается соотношение Пусть – момент последнего перед t+Δ скачка процесса Х(t); – момент предпоследнего перед t+Δ скачка процесса X(t). Обозначим еще Тогда очевидно, что Это событие заключается в том, что происходят ровно два скачка. Осталось заметить, что Т.е вероятность того, что в системе будет два и более скачка равна нулю. Подставляя в (2) полученные соотношения, приходим к следующему равенству: Переходя в последнем равенстве к пределу при Δ → 0, получаем уравнение (1). Теорема доказана. Рассмотрим систему дифференциальных уравнений: если существуют пределы: удовлетворяющие условию то вероятности Рk называются стационарными вероятностями (характеристиками), а относительно системы говорят, что она находится в стационарном (установившемся) режиме. Стационарные вероятности удовлетворяют следующей системе алгебраических уравнений: (4) Система (4) получается, если приравнять нулю левую часть системы (1). Решая последовательно систему (4), можно выразить числа Рk через Р0: Подставляя в соотношение (3) получаем: Очевидно далее, что сходимость ряда есть условие существования стационарного режима в системах массового обслуживания. В этом случае стационарные характеристики Рk процесса X(t) находятся с помощью формул Задачи к § 4 4.1. Для процесса гибели и размножения из задачи 3.2 выписать дифференциальные уравнения, связывающие вероятности Pk(t) = P(в системе в момент t находится k клиентов). Найдите решение системы дифференциальных уравнений, а также стационарные вероятности. 4.2. Для процессов гибели и размножения из задачи 3.3 выписать дифференциальные уравнения, связывающие вероятности Pk(t) = P(в системе в момент t находится k клиентов). Найти стационарные вероятности. § 5. Основные типы систем массового обслуживания Для описания СМО используется обозначение  (). Первое место в этом обозначении характеризует входной поток, а именно, характеризует распределение вероятностей промежутков поступлений между соседними клиентами. Второе место является характеристикой обслуживающих приборов, а именно, характеризует распределение вероятностей времени обслуживания. Третье место характеризует число обслуживающих приборов. Четвертое место характеризует дисциплину очереди. В основном мы будем изучать системы, когда в качестве распределения, стоящих на первом и втором местах, будет использоваться показательное распределение. Это связано с тем, что такие СМО адекватно описываются процессами гибели и размножения, которые мы изучали выше. И, такие системы будут обозначаться следующим образом: MMm (очередь длины N) или MMm (очередь длины N). Рассмотрим подробно некоторые известные системы. 1. Система MM1 (с очередью) Предположим, что X(t) – число клиентов в системе в момент t, и интенсивность поступления и обслуживания клиентов не меняется, т.е. k =, k = 0, 1, ... k = , k = 1, 2, ... Диаграмма выглядит так: Cоставляем систему дифференциальных уравнений для нахождения вероятности Pk(t) = P(X(t) = k). Для этого исследуем сходимость ряда Обозначим . Если   1, то S   и стационарный режим существует. Если же   1, то S= . Таким образом в данной системе стационарный режим существует тогда и только тогда, когда В условиях существования стационарного режима найдем: среднее число клиентов в системе: среднее число клиентов в очереди: Еще одной важной характеристикой системы является q – время ожидания начала обслуживания в стационарном режиме. Лемма 1. Если   1, то вероятность того, что P(q  x) равна Т.е. прежде чем начнут обслуживать, придется ждать как минимум x единиц времени. Отсюда можно получить (проверьте самостоятельно) среднее время ожидания начала обслуживания, или среднее время, проведенное в очереди: Величина Eq является важной характеристикой «качества» обслуживания»: чем меньше Eq, тем обслуживание лучше. Обозначим через Ev – среднее время, проведенное в системе: Тогда 2. Система MMm (с очередью) Пусть X(t) – число клиентов в системе в момент t. Предположим, что Найдем условие стационарности. Для этого исследуем сходимость ряда S. Если , то S <  и стационарный режим существует. Таким образом в данной системе стационарный режим существует тогда и только тогда, когда   m. В условиях существования стационарного режима Предположим, что q – время, проведенное в очереди. Лемма 2. При   m вероятность того, что P(q  x) равна - вероятность того, что все приборы заняты. Тогда среднее время, проведенное в очереди (проверьте самостоятельно) 3. Система MM Это система, когда любому вновь прибывшему клиенту находят прибор. Предположим, что k = , k = 0, 1, ; k = k, k = 1, 2,  Диаграмма выглядит так: Найдем условие стационарности. Т.е. независимо от того, какой , стационарный режим существует всегда. Отсюда, Для системы <М│М│∞> можно вывести формулы:(самостоятельно) . Также можно привести формулы для оценки Pk(t) и в случае, когда процесс еще не достиг стационарного режима. , где . Как видно, и для неустановившегося режима X(t) подчиняется пуассоновскому распределению. Очевидно, что EX(t) = α. 4. Ненагруженный резерв Пусть у нас имеется система, в которой основной элемент выходит из строя через λ-показательное время; вышедший из строя элемент немедленно заменяется новым, который был в резерве. Пусть в начальный момент времени исправных основных элементов было n. Обозначим через X(t) количество элементов, вышедших из строя к моменту t. Очевидно, что X(t) есть процесс чистого размножения, отвечающий диаграмме : Введем, как обычно, функции Pk(t) = P(X(t) = k), k = 0,1,…,n. Они удовлетворяют уравнениям ………………………… и начальному условию P0(0) = 1. Непосредственно проверяется, что 5. Нагруженный резерв Пусть в предыдущей задаче все n элементов находятся в работе, выходя из строя по тому же λ-показательному закону. В этом случае процессу X(t) отвечает следующая диаграмма : Функции Pk(t) удовлетворяют уравнениям ………………………………. и начальному условию P0(0) = 1. Легко проверить, что 6. Система <М│М│1> (очередь ≤ N) Эта система описывается процессом гибели и размножения X(t) с диаграммой : Очевидно, что при любом соотношении λ и μ существует стационарный режим и 1) при ρ ≠ 1: , . Можно вычислить также среднее число клиентов в системе в стационарном режиме: 2) при ρ = 1 , 7. Система <М│М│m> (очередь ≤ N) Пусть X(t) число клиентов в системе, характеристики этой системы: Напомним, что в этой системе длина очереди не может превышать N-m. Найдем стационарные характеристики (они существуют). Пусть В случае В случае следовательно От системы <М│М│m> (с очередью) эта система отличается тем, что выражения для Р0 не совпадают, и что ρ ≤ m – не обязательное условие для стационарности. Можно найти если и если . Среднее время, проведенное в очереди Здесь λ(1 - pN ) – фактическое число клиентов, обслуженных в единицу времени, т.е. “эффективная” интенсивность входного потока. Иногда λ(1 - pN ) обозначают через λэфф. 8. Система <М│М│m> с ограниченным числом мест в очереди и ограниченным числом источника клиентов Например, система, где бригада из m специалистов обслуживают N клиентов. Предполагается, что m продолжительность обслуживания одного клиента равняется 5 мин., а средняя длина интервала времени между последовательными поступлениями заявок на обслуживание составляет 8 мин. Система работает достаточно долго. Найти: а) вероятность возникновения задержки заявки в обслуживающей системе; б) вероятность того, что хотя бы один из обслуживающих приборов будет незагруженным; в) вероятность того, что незагруженным окажутся оба обслуживающих приборов. 5.4. Закусочная, расположенная около автомагистрали, имеет прилавок, возле которого может остановиться один автомобиль. По статистическим оценкам автомобили подъезжают к закусочной в соответствии с пуассоновским потоком со средней частотой 2 автомобиля за 5 мин. Подъездная дорожка к закусочной позволяет встать в очередь 10 автомобилям (очевидно, что если подъездная дорожка полностью занята очередью автомобилей, то дополнительно прибывающие к месту расположения закусочной автомобили могут расположиться для ожидания в каких-нибудь других местах). Для выполнения заказов клиентов требуется в среднем по 1,5 мин., и продолжительности обслуживания распределены по показательному закону. Требуется вычислить: а) вероятность того, что у закусочной не окажется ни одного автомобиля; б) среднее число ожидающих начала обслуживания клиентов; в) среднее время ожидания от момента прибытия клиента до начала его обслуживания; г) вероятность того, что количество прибывших к закусочной автомобилей превысит 10. 5.5. Рассмотрим работу пункта по обмену валюты. Клиенты приходят в пункт в соответствии с пуассоновским потоком в среднем каждые 6 минут. Время обслуживания одного клиента подчиняется показательному распределению со средним значением, равным 6 минутам. Каждый обслуженный клиент приносит доход в два доллара США (в среднем). Пункт имеет одну кассу обслуживания и два места для ожидания. Посетители, заставшие места для ожидания занятыми, теряются для системы. Для улучшения работы пункта рассматриваются два инвестиционных проекта: а) затратив 200 долларов, оборудовать 4 места для ожидания (добавить еще два кресла); б) затратив 1000 долларов, увеличить число мест для ожидания до 10. Найти среднее время, за которое окупится каждый из этих проектов, если пункт работает 8 чесов в сутки. 5.6. Решить задачу 5.5. для случая, когда клиенты приходят в пункт в среднем каждые 12 минут в соответствии в пуассоновским потоком, а время обслуживания одного клиента то же. 5.7. Предположим, что имеются три проекта строительства морского порта: П1 - Построить два порта и в каждом порту соорудить один причал; П2 – Построить один порт с двумя причалами и П3 – Построить один порт с одним причалом, но с производительностью в два раза выше, чем в предыдущих проектах. Какому из проектов следует отдать предпочтение? 5.8. В системе с самообслуживанием входной поток является пуассоновским и имеет интенсивность, равная 50 клиентам в час. Продолжительность обслуживания в расчете на одного клиента распределена показательно со средним значением 5 минут. Определить: а) среднее число клиентов, находящихся в произвольно выбранный момент времени в стадии обслуживания; б) часть времени, в течение которого система простаивает § 6. Системы массового обслуживания с последовательными узлами (приборами) обслуживания Системы массового обслуживания, где процесс обслуживания заканчивается лишь после прохождения клиента через все приборы обслуживания. Рассмотрим несколько примеров таких систем. 1. Двухфазная модель систем массового обслуживания с нулевой вместимостью блока ожидания Простой случай: Клиент должен сначала пройти прибор 1, а затем прибор 2. Предположим, что продолжительности обслуживания в каждом из приборов распределены показательно с параметром μ и что входной поток пуассоновский с интенсивностью λ. Введем условие: образование очередей возле узлов недопустимо. Введем: прибор 1 заблокирован, если обслуживание в прибор 1 завершено, а прибор 2 не готов к приему данного клиента (по причине не завершения обслуживания предыдущего клиента), т.е. клиент не имеет права на ожидание в промежутке между приборами 1 и 2. Для описания модели предположим, что 0, 1 и δ представляют состояние «прибор свободен», «прибор занят» и «прибор заблокирован». Поскольку у нас 2 прибора, то состояние системы будет иметь вид ( i, j ), где i – состояние прибора 1, а j – прибора 2. Тогда множество состояний обслуживающей системы: {(i, j)} = {(0,0), (1,0), (0,1), (1,1). (δ,1)} Обозначим через Pij(t) – вероятность того, что в момент времени t система находится в состоянии (i, j). Эти вероятности удовлетворяют следующей системе дифференциальных уравнений: Замечание: Для пояснения изменения состояния системы в промежутке приведем следующие таблицы: Обозначим через и в указанных уравнениях переходим к пределу. Получаем систему для стационарного режима: Обозначим и учитывая, что , мы получим, решение этой системы: Отсюда, например, можем найти среднее чисто клиентов в системе: Пример 1. Конвейер, на котором производится обработка агрегатов, обслуживается двумя операторами, каждый из которых выполняет конкретную совокупность операций. Размеры агрегатов таковы, что возле рабочего места операторов нельзя разместить более одного агрегата. Те агрегаты, которые не могут быть немедленно приняты для обработки на рассматриваемый конвейер, направляются на другие конвейерные линии. Пусть агрегаты поступают в соответствии с пуассоновским потоком с интенсивностью 10 штук в час. Продолжительность обслуживания – 5 минут в расчете на один агрегат. Тогда: λ = 10, μ = 12, ρ = 0,833; 3ρ2 + 4ρ + 2 = 3(0,833)2 + 4(0,833) + 2 = 7,417. Получаем: Р00 = 0,2697; Р01 = 0,2247; Р10 = 0,3181; Р11 = Рδ1 = 0,0936; EX = 0,917. Вероятность того, что поступающий агрегат будет принят Прибором 1 равна P00 + P01 = 0,4944, тогда эффективная интенсивность поступления: λэфф = 0,4944·10 = 4,944. Следовательно полное время сборки на конвейерной линии: EX совпадает (по смыслу) со средней продолжительностью обработки одного агрегата, т.к. образование очереди на конвейере не разрешено. В среднем, агрегат может подвергаться обработке 5+5=10 мин. Отсюда для того, чтобы прибор 2 не оказался заблокированным (для данного примера), имеется резерв времени: 0,185 - 0,167 = 0,018 – эту разность можно интерпретировать как среднюю продолжительность задержки в приборе 1 из-за невозможности перехода в прибор 2. 2. k-фазная модель с неограниченной вместимостью блока ожиданий Рассмотрим следующую систему массового обслуживания: Поступления в соответствии с пуассоновским распределением с интенсивностью . Распределение продолжительности показательное с интенсивностью i, i = 1,...,k. Можно доказать, что в условиях задачи поток клиентов, обслуживаемых каждым из k приборов, является простейшим, и каждый прибор можно рассматривать независимо с помощью СМО MM1 (с очередью). Это означает, что для i-го прибора вероятность Pni в стационарном режиме определяется: число клиентов, находящихся в системе содержащей i-й блок обслуживания. Естественно, этот результат справедлив лишь в том случае, когда Такой же результат справедлив и в случае, когда i-й прибор состоит из mi параллельно обслуживающих приборов, которые характеризуются основными i. В этом случае каждый блок можно рассматривать независимо от других как систему MMmi (с очередью). И результат справедлив при условии   mii. Пример 2. Пусть на технической линии в цехе промышленного предприятия имеется 5 последовательных приборов. Пусть на прибор1 интенсивность 20 заявок в час. Продолжительность технических процедур – показательное, 2 процедуры в 1 мин. Доля качественной продукции, производимой i-м прибором, обозначим через i, интерпретируя i как соотношение произведенной в i-м приборе качественной продукции к суммарному объему поступающих в данный прибор заявок на выполнение соответствующего вида работ. Тогда 1-i есть доля бракованной продукции, производимой в i-м технологическом приборе. Вероятность того, что в i-м приборе находится ni изделий: , где Требуется найти: какую вместимость должны иметь располагаемые между приборами блоки складирования, если требуется разместить все поступающие в очередной технологический блок изделия в течении -й доли времени, необходимого для обработки изделий в этом приборе. Требования к вместимости блоков будут удовлетворены при условии, если в месте, отведенном для промежуточного складирования, удастся разместить Ni-1 изделий, где Ni определяется из: Пусть i = 0,9. Тогда 1==20; 2=11=18; 3=211=16,2; 4=3211=14,58; 5=43211=13,12. Так как i==30 в час, то 1=0,67; 2=0,6; 3=0,54; 4=0,486; 5=0,437. Задачи к § 6 6.1. В примере 1 § 6 предположим, что обслуживающая система располагает тремя работающими последовательно узлами. Провести анализ этой модели с теми же исходными данными. § 7. Практическое применение Теории массового обслуживания Практическое применение ТМО предполагает: а) выбор подходящей математической модели, адекватно представляющей реальную систему с тем, чтобы определить операционные характеристики исследуемой системы; б) практическое использование полученных результатов. Трудности, возникающие при моделировании СМО. Трудности рассматриваются с двух точек зрения: 1) степени сложности математического описания той или иной обслуживающей системы; 2) гибкости математических моделей. 1. Степень сложности Классические модели массового обслуживания строятся и используются в предположении, что как характеристики входящего потока, так и показатели, относящиеся к обслуживающему прибору, предсказуемы и могут быть представлены количественно. Если исходить из этого положения, то основные системы, встречающиеся в реальной жизни, можно разбить на 3 категории: К1: СМО, в которых в качестве клиентов и обслуживающих единиц выступают люди; К2: полуавтоматические системы, в которых в качестве клиентов или обслуживающих единиц выступают люди. (Ремонтный цех – «клиент» техническое устройство; а ремонт – производит «механик»); К3: автоматические. Такое разделение сделано с той целью, чтобы дифференцировать способы определения степени применимости традиционных моделей массового обслуживания для решения конкретных практических задач. Например, системы К1 – труднее поддаются математическому моделированию. Поведение человека в большинстве случаев точно предсказать невозможно. Поэтому при моделировании процессов функционирования обслуживающих систем следует в большей мере ориентироваться на ситуации с К2 или К3. В этих случаях системы поддаются более точному представлению существующими в ТМО математическими моделями. Вряд ли существует универсальный «математический» рецепт для совершенствования систем массового обслуживания типа К1. Можно сказать, что система типа К1 поддается «лечению» лишь в той степени, в которой претендующие на «совершенствование обслуживания» меры не вызывают активного сопротивления либо обслуживаемых, либо тех, кто выполняет функции обслуживания. 2. Гибкость математических моделей обслуживания Сложность анализа систем массового обслуживания с помощью математических методов может обнаружиться: 1) в процессе построения и аналитической реализации математической модели конкретной ситуации; 2) в связи с получением числовых операционных характеристик моделей системы и возникающими при этом затруднениями математического характера. Если выясняется, что результаты, получаемые с помощью модели, оказываются относительно слабо чувствительными к вариациям исходных допущений, то такую модель следует назвать гибкой в том смысле, что ее можно применять для описания различных по характеру систем массового обслуживания. Примером наиболее гибкой «модели» в Теории массового обслуживания может служить известная формула: EX = Ev. Эта формула универсальна в том смысле, что возможность ее использования не зависит ни от вида распределения моментов поступления клиентов, ни от распределения времени обслуживания. Но таких универсальных формул ни так много. Поэтому специально подчеркивается, что можно ставить вопрос о таких аппроксимациях сложных систем массового обслуживания, которые остаются правомерными лишь в некоторых допустимых пределах. В теории массового обслуживания имеются возможности выявить те основные предположения, при которых модельное представление обслуживающих систем можно упрощать, оставляя вместе с тем в допустимых пределах ошибки в определении числовых операционных характеристик системы. Кажется, модели массового обслуживания во многих реальных ситуациях, на первый взгляд, применить невозможно. Однако трудности можно одолеть одним из следующих способов: Способ 1: можно модифицировать структурно-функциональные характеристики обслуживающих систем так, чтобы чисто логическим путем достичь желательных операционных показателей этой системы и одновременно сделать рассматриваемую систему массового обслуживания поддающейся анализу одной из стандартных математических моделей; Способ 2: можно признать справедливыми некоторые упрощающие предположения относительно реальной обслуживающей системы, и, следовательно, возможно представить ее с помощью определенной математической модели без риска получить существенные ошибки в численных оценках операционных характеристик системы. Способ 2 более перспективный – он увеличивает круг задач, решение которых может быть обеспечено путем использования уже разработанных моделей и методов. Задачи к § 7 7.1. Укажите, к какой категории (К1, К2 или К3) следует отнести системы массового обслуживания, рассмотренные в § 5 § 8. Подготовка исходных данных и проверка гипотез Как мы отмечали выше, выбор метода для исследования функциональных характеристик системы определяется законами распределения моментов поступления клиентов и продолжительности обслуживания. Чтобы установить характер распределения, необходимо осуществить наблюдения за реально функционирующей системой и зарегистрировать ряды чисел, получаемых в ходе наблюдений. При этом возникают вопросы: 1) когда осуществлять наблюдения? 2) каким образом систематизировать данные? Любая система массового обслуживания характеризуется так называемыми периодами повышенной загруженности, поэтому лучше осуществлять наблюдения в течение таких периодов. Сбор данных можно осуществить следующими способами: Способ 1: путем регистрации временных интервалов между последовательными поступлениями клиентов и последовательными выходами обслуженных клиентов из системы; Способ 2: путем подсчета числа поступивших в единицу времени клиентов на обслуживание и числа выходящих из системы в единицу времени обслуженных клиентов. После этого необходимо систематизировать и обобщить данные с тем, чтобы получить возможность построить в результате интересующие исследования распределения вероятностей. Этого можно достичь путем представления гистограмм (полигонов). Затем выбирается «теоретическое» распределение вероятностей, которые хорошо подходят для описания полученных данных. Далее, для проверки степени пригодности выбранного распределения для описания реального процесса применяется одна из стандартных статистических тестовых процедур. Задачи к § 8 8.1. В таблице приведены значения частоты появления события, заключающегося в том, что число поступлений заявок на обслуживание в течение часа равняется n: n 1 2 3 4 5 6 7 8 9 6 15 22 24 15 9 4 3 2 Проверьте, можно ли принять гипотезу о том, что входной поток является пуассоновским. Если данная гипотеза принимается, то покажите, какой конкретный вид будет иметь функция распределения вероятностей, которую можно использовать для анализа процесса X(t) – число заявок в момент t. § 9. Принятие решений с использованием моделей массового обслуживания Сначала рассмотрим модели со стоимостными характеристиками. Такие модели массового обслуживания направлены на определение такого уровня функционирования обслуживающих систем, при котором достигается «компромисс» между следующими двумя экономическими показателями: 1) прибылью, получаемой за счет предоставления услуг; 2) потерями прибыли, обусловленными задержками в предоставлении услуг. Рассматривается два типа моделей: Модели 1-го типа ориентированы на определение оптимальной средней скорости обслуживания , когда система массового обслуживания располагает одним прибором; Модели 2-го типа направлены на определение оптимального числа обслуживающих приборов в случае многоканальной системы массового обслуживания. Оптимальная скорость обслуживания . Пусть в системе с одним прибором интенсивность поступлений , а интенсивность обслуживания . Предположим, что  поддается регулированию; требуется определить её оптимальное значение на основе стоимости модели. Введем обозначения: C1 – выраженный в стоимостной форме выигрыш за счет увеличения на единицу значения  в течении единичного интервала времени (например за 1 час); С2 – «цена» ожидания (т.е. потери, обусловленные вынужденным ожиданием) в единицу времени и в расчете на одного клиента; С() – стоимостной показатель, определяемый формулой: C() = C1 + C2EX,  - непрерывная величина, поэтому оптимальное значение находится из равенства к нулю первой производной С() по . Например, для MM1 (с очередью): Следовательно Как видно,  (оптимальное) зависит от . Это логично, если это было бы не так, то  могло бы быть больше 1. Для системы MM1 (очередь  N) C() = C1 + C2EX + C3N + C4pN, где С3 – «стоимость» увеличения (на единицу времени) вместимости блока ожидания, С4 – экономические потери, связанные с невозможностью включить в блок ожидания системы еще одного нуждающегося в обслуживании клиента. Заметим, что pN – число клиентов, потерянных системой в единицу времени. Получить решение этой задачи в явном виде невозможно. Необходимы соответствующие численные методы. Оптимальное число обслуживающих приборов. Рассмотрим многоканальную систему массового обслуживания (допустим m - приборов). Пусть ,  - фиксированы. Пусть С(m) = C1m + C2EX, где С1 – отнесенные к единице времени затраты на обеспечение функционирования одного дополнительного обслуживающего прибора, EX – среднее число клиентов. Так как m – дискретно, то дифференцировать нельзя. Оптимальное значение находится – m может быть найдено путем выполнения условий: С(m-1)  С(m) С(m+1)  С(m) EX(m) – EX(m+1)  C1C2  EX(m-1) – EX(m), где EX(m) – среднее число клиентов в системе с m-приборами. В заключение, несколько слов о моделях, в которых осуществляется учет предпочтительного уровня обслуживания. Заметим, что в таких моделях при определении оптимального числа приборов учитывается то, что «конкурирующими» являются показатели: средняя продолжительность ожидания Eq и доля времени , в течении которого обслуживающий прибор простаивает. Эти показатели и определяют потенциальный характер процесса массового обслуживания. Обозначим верхние пределы Eq и  через  и  соответственно. Учет предпочтительности уровня функционирования обслуживающей системы можно представить математически так: определим число m так, чтобы Eq   и   . Выражение для  имеет вид : Для системы MMm значение Eq также найдена (см. § 5). Рис.1 Используя эти значения, решение задачи находится графически: для этого нужно построить графики функций и , далее указав графически уровни и выявляется приемлемый диапазон значений m (Рис.1). Задачи к § 9 9.1. Бутылки с фруктовым соком поступают на автоматическую линию в соответствии с пуассоновским распределением вероятностей со средней интенсивностью 10 партий в день. В конце конвейера бутылки закупориваются автоматическим устройством. Установлено, что увеличение производительности на одну единицу обойдется фирме в $100 в неделю. Задержка же в выполнении указанной выше технологической операции приведет к сокращению объема производства; при этом экономические потери из расчета на одну партию бутылок равняются $200 в неделю. Определите оптимальную скорость работы автомата. 9.2. В цехе промышленного предприятия имеется 10 одинаковых станков. Каждый час работы станка обеспечивает прибыль, равную $4. Поломка каждого станка за семичасовой период времени происходит в среднем один раз. Один механик тратит на ремонт станка в среднем четыре часа, хотя фактически наблюдаемые продолжительности ремонта одного станка распределены по показательному закону. Механик, осуществляющий ремонт станков, получает $6 в час. Определите а) число механиков, обеспечивающих минимизацию суммарных экономических потерь; б) число механиков, которое необходимо для того, чтобы среднее количество простаивающих из-за неисправности станков было меньше четырех; в) число механиков, при котором среднее время простоя станка из-за возникновения в нем неисправности не превышало четырех часов.