Задачи

Рассмотрим $\mathrm{M}(\lambda ) / \mathrm{M}(\mu ) / k$ с ограничением, что прибывающие клиенты, которые видят $N$ клиентов впереди себя в очереди, уходят и никогда не возвращаются. Найдите стационарное распределение длины очереди для случаев $k = 1$ и $k = 2$.

Рассмотрим $\mathrm{M}(\lambda ) / \mathrm{M}(\mu ) / 1$ с ограничением, что если прибывающий клиент видит $n$ клиентов впереди себя в очереди, он присоединяется к очереди с вероятностью $p(n)$, а иначе уходит в негодовании.

В московском супермаркете покупатели стоят в очереди у кассы, чтобы оплатить нужный им товар; затем они переходят во вторую очередь, где ожидают выдачи этого товара. Если покупатели прибывают в магазин по закону пуассоновского процесса с параметром $\lambda$, и все времена обслуживания независимы и экспоненциально распределены с параметром $\mu_{1}$ на первой кассе и $\mu_{2}$ на второй, найдите стационарные распределения длин очередей, когда они существуют, и покажите, что в любой заданный момент времени длины двух очередей независимы в состоянии равновесия.

Рассмотрим M/G/1 с модификацией, при которой сервер может обслуживать одновременно до $m$ клиентов. Если длина очереди меньше $m$ в начале периода обслуживания, то она обслуживает всех, кто ожидает в этот момент. Найдите формулу, которой удовлетворяет производящая функция вероятностей стационарного распределения длины очереди в моменты отправлений, и вычислите эту производящую функцию явно в случае, когда $m = 2$ и времена обслуживания экспоненциально распределены.

Рассмотрим $\mathrm{M}(\lambda ) / \mathrm{M}(\mu ) / 1$, где $\lambda < \mu$. Найдите производящую функцию моментов длины $B$ типичного периода занятости и покажите, что $\mathbb {E}\left[B\right] = (\mu -\lambda )^{-1}$ и $\operatorname {Var}\left(B\right) = (\lambda +\mu ) /(\mu -\lambda )^{3}$. Покажите, что плотность $B$ равна

где $I_{1}$ — модифицированная функция Бесселя.

Рассмотрим $\mathrm{M}(\lambda ) / \mathrm{G} / 1$ в состоянии равновесия. Получите выражение для средней длины очереди в моменты отправлений. Покажите, что среднее время ожидания в состоянии равновесия прибывающего клиента равно $\frac{1}{2} \lambda \mathbb {E}\left[S^{2}\right] /(1-\rho )$, где $S$ — типичное время обслуживания и $\rho = \lambda \mathbb {E}\left[S\right]$.

Среди всех возможных распределений времени обслуживания с заданным средним найдите то, для которого среднее время ожидания минимально.

Пусть $W_{t}$ — время, которое клиенту пришлось бы ждать в очереди $\mathrm{M}(\lambda ) / \mathrm{G} / 1$, если бы он прибыл в момент времени $t$. Покажите, что функция распределения $F(x ; t) = \mathbb {P}\left(W_{t} \leq x\right)$ удовлетворяет

где $S$ — типичное время обслуживания, независимое от $W_{t}$. Предположим, что $F(x, t) \rightarrow H(x)$ для всех $x$ при $t \rightarrow \infty$, где $H$ — функция распределения, удовлетворяющая $0 = h-\lambda H+\lambda \mathbb {P}\left(U+S \leq x\right)$ при $x > 0$, где $U$ независима от $S$ и имеет функцию распределения $H$, а $h$ — плотность $H$ на $(0, \infty )$. Покажите, что производящая функция моментов $M_{U}$ величины $U$ удовлетворяет

где $\rho$ — интенсивность трафика. Можете считать, что $\mathbb {P}\left(S = 0\right) = 0$.

Рассмотрим очередь $\mathrm{G} / \mathrm{G} / 1$, в которой времена обслуживания постоянно равны $2$, тогда как времена между поступлениями принимают либо значение 1, либо 4 с равной вероятностью $\frac{1}{2}$. Найдите предельное распределение времени ожидания.

Рассмотрим крайне идеализированную модель телефонной станции с бесконечным числом доступных каналов. Вызовы поступают по закону пуассоновского процесса с интенсивностью $\lambda$, и каждый требует один канал в течение времени, имеющего экспоненциальное распределение с параметром $\mu$, независимо от процесса поступлений и от продолжительности других вызовов. Пусть $Q(t)$ — число вызовов, обрабатываемых в момент времени $t$, и предположим, что $Q(0) = I$.

Определите производящую функцию вероятностей $Q(t)$ и выведите $\mathbb {E}\left[Q(t\right]), \mathbb {P}\left(Q(t\right) = 0)$ и предельное распределение $Q(t)$ при $t \rightarrow \infty$.

Предполагая, что очередь находится в состоянии равновесия, найдите долю времени, в течение которого ни один канал не занят, и среднюю длину периода простоя. Выведите отсюда, что средняя длина периода занятости равна $\left(e^{\lambda / \mu }-1\right) / \lambda$.

Клиенты прибывают в магазин по закону пуассоновского процесса с интенсивностью $\lambda$, где $0 < \lambda < 1$. Их обслуживают по одному в порядке прибытия, и каждому требуется время обслуживания единичной длины. Пусть $Q(t)$ — число людей в очереди в момент времени $t$. Сравнивая $Q(t)$ с $Q(t+1)$, определите предельное распределение $Q(t)$ при $t \rightarrow \infty$ (можете считать, что рассматриваемые величины сходятся). Отсюда покажите, что средняя длина очереди в состоянии равновесия равна $\lambda \left(1-\frac{1}{2} \lambda \right) /(1-\lambda )$.

Пусть $W$ — время ожидания только что прибывшего клиента, когда очередь находится в состоянии равновесия. Выведите из приведённых выше результатов, что $\mathbb {E}\left[W\right] = \frac{1}{2} \lambda /(1-\lambda )$.

Рассмотрим $\mathrm{M}(\lambda ) / \mathrm{D}(1) / 1$ и предположим, что очередь пуста в момент времени 0. Пусть $T$ — самый ранний момент времени, в который клиент уходит, оставляя очередь пустой. Покажите, что производящая функция моментов $M_{T}$ величины $T$ удовлетворяет

и выведите среднее значение $T$, различая случаи $\lambda < 1$ и $\lambda \geq 1$.

Предположим $\lambda < \mu$, и рассмотрим очередь $\mathrm{M}(\lambda ) / \mathrm{M}(\mu ) / 1, Q$ в состоянии равновесия.

Рассмотрим очередь $\mathrm{M}(\lambda ) / \mathrm{M}(\mu ) / k$, где $k \geq 1$. Покажите, что стационарное распределение $\vect {\pi }$ существует тогда и только тогда, когда $\lambda < k \mu$, и вычислите его в этом случае.

Предположим, что стоимость эксплуатации этой системы в состоянии равновесия составляет

где положительные константы $A$ и $B$ представляют соответственно затраты на найм сервера и неудовлетворённость задержанных клиентов.

Покажите, что при фиксированном $\mu$ существует единственное значение $\lambda^{*}$ в интервале $(0, \mu )$ такое, что дешевле иметь $k = 1$, чем $k = 2$, тогда и только тогда, когда $\lambda < \lambda^{*}$.

Клиенты прибывают в магазин по закону пуассоновского процесса с интенсивностью $\lambda$. Они образуют единую очередь. Имеется два сервера, обозначенных 1 и $2$, серверу $i$ требуется экспоненциально распределённое время с параметром $\mu_{i}$ для обслуживания любого данного клиента. Клиент в голове очереди обслуживается первым свободным сервером; когда оба свободны, прибывающий клиент с равной вероятностью выбирает любой из них.

Рассмотрим очередь $\mathrm{D}(1) / \mathrm{M}(\mu ) / 1$, где $\mu > 1$, и пусть $Q_{n}$ — число людей в очереди непосредственно перед $n$-м прибытием. Пусть $Q_{\mu }$ — случайная величина, имеющая в качестве распределения стационарное распределение марковской цепи $\left\{ Q_{n}\right\}$. Покажите, что $\left(1-\mu^{-1}\right) Q_{\mu }$ сходится по распределению при $\mu \downarrow 1$, причём предельное распределение является экспоненциальным с параметром 2.

Такси прибывают на стоянку по закону пуассоновского процесса с интенсивностью $\tau$, а пассажиры прибывают по закону (независимого) пуассоновского процесса с интенсивностью $\pi$. Если нет ожидающих пассажиров, такси ждут, пока не прибудут пассажиры, а затем отъезжают с пассажирами, по одному на такси. Если нет такси, пассажиры ждут, пока не прибудут такси. Предположим, что первоначально на стоянке нет ни такси, ни пассажиров. Покажите, что вероятность того, что $n$ пассажиров ожидают в момент времени $t$, равна $(\pi / \tau )^{\frac{1}{2} n} e^{-(\pi +\tau ) t} I_{n}(2 t \sqrt{\pi \tau })$, где $I_{n}(x)$ — модифицированная функция Бесселя, т.е. коэффициент при $z^{n}$ в разложении в степенной ряд функции $\exp \left\{ \frac{1}{2} x\left(z+z^{-1}\right)\right\}$

Станки поступают на ремонт по закону пуассоновского процесса с интенсивностью $\lambda$. Каждый ремонт включает два этапа, при этом $i$-й прибывший станок находится в ремонте в течение времени $X_{i}+Y_{i}$, где пары $\left(X_{i}, Y_{i}\right), i = 1,2, \ldots$, независимы и имеют общее совместное распределение. Пусть $U(t)$ и $V(t)$ — числа станков на $X$-этапе и $Y$-этапе ремонта в момент времени $t$. Покажите, что $U(t)$ и $V(t)$ — независимые пуассоновские случайные величины.

Страховая компания выплачивает независимые и одинаково распределённые страховые требования $\left\{ K_{n}: n \geq 1\right\}$ в моменты пуассоновского процесса с интенсивностью $\lambda$, где $\lambda \mathbb {E}\left[K_{1}\right] < 1$. Страховые взносы поступают с постоянной скоростью 1. Покажите, что максимальный дефицит $M$, который когда-либо накопит компания, имеет производящую функцию моментов

Для очереди $\mathrm{M}(\lambda ) / \mathrm{M}(\mu ) / 1$ с $\lambda < \mu$, находящейся в состоянии равновесия, покажите, что ожидаемое время до первого опустошения очереди равно $\lambda (\mu -\lambda )^{-2}$.

Рассмотрим очередь $M(\lambda ) / G / \infty$. Используя теорему о вознаграждении при восстановлении, покажите, что ожидаемая продолжительность периода занятости равна $\left(e^{\rho }-1\right) / \lambda$, где $\rho = \lambda \mathbb {E}\left[S\right]$.