Лекция 7. Типовые задачи по теории массового обслуживания

Пример1. На станцию метро в данное время суток направляется простейший поток пассажиров с плотностью: . Найти вероятность того, что за минуту на станцию:

а) не войдет ни один пассажир:

б) войдут 1, 2, 3, 4 пассажира;

в) войдет хотя бы один пассажир.

Решение:

Т.к. поток простейший, то число пассажиров, попадающих на заданный участок τ, распределено по закону Пуассона:

вероятность того, что на участке длиной τ появится k пассажиров.

Получаем:

а)

б) полагая k=1,2,3,4, получаем:

в) вычитая из единицы , получаем вероятность того, что на участке τ появится хотя бы один пассажир:

Пример2. Плотность потока вызовов на АТС зависит от времени суток и выражается формулой:

Найти вероятность того, что за промежуток времени от 17 часов до 17 часов 10 минут станция получит не менее двух вызовов.

λ

20

5,6

12

24

t

λ=λ(t)

Будем считать, что имеем нестационарный пуассоновский поток, тогда

– формула Пуассона,

где m – математическое ожидание;

- среднее число вызовов на промежутке времени ( .

Получаем:

Тогда вероятность того, что АТС не получит ни одного вызова или получит один вызов, равна

Вероятность того, что станция получит не менее двух вызовов, найдем через вероятность противоположного события – менее двух вызовов, т.е. 0 или 1 вызов.

Пример3: АТС имеет 4 линии связи. На станцию поступает простейший поток заявок с плотностью λ=3 вызов/мин. Вызов, поступивший в момент, когда все линии заняты, получает отказ. Время каждого разговора имеет показательное распределение с

Найти:

1. вероятность отказа

2. среднее относит. время простоя

3. относит. пропускную способность q;

4. абсолютную пропускную способность A;

5. среднее число занятых линий во время работы АТС.

Решение:

Имеем чистую СМО с отказами, и можем использовать формулы Эрланга.

Т.к. то

(в среднем в систему поступает 6 заявок за время обслуживания одной заявки)

1. 

2. Среднее относит. время простоя есть (вероятность того, что все линии свободны)

3. q=1- , т.е. АТС обслуживает около 53% вызовов.

4. 4) A=λ*q=3*0.53=1.59 вызова/мин (или около 95 вызовов/час)

5. N=α(1-

Основы теории игр Предмет теории игр. Основные понятия

Теория игр – математическая теория конфликтных ситуаций.

Ситуация является конфликтной, если сталкиваются две (или более) стороны, преследующие различные цели, причем результат любого мероприятия каждой из сторон зависит от того, какой образ действий примет его противник.

Схематизированную модель конфликтной ситуации называют игрой

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

Стороны, участвующие в конфликте, называют игроками.

Ходом в теории игр называют выбор одного из предусмотренных правилами игры действий и его осуществление. Результат конфликта для каждой из сторон называют выигрышем игроков.

Ходы бывают личные и случайные.

Личным ходом называют сознательный выбор игроком одного из возможных вариантов действий и его осуществление.

Случайным ходом называют выбор из ряда возможностей, осуществляемый не решением игрока, а каким-либо механизмом случайного выбора.

Для каждого случайного хода правила игры определяют распределение вероятностей возможных исходов.

Некоторые игры состоят только из случайных ходов (чисто азартные игры – рулетка) или только из личных ходов (шахматы).

Большинство карточных игр содержит как личные, так и случайные ходы.

Теория игр занимается анализом только тех игр, которые содержат личные ходы. Ее задача – дать рекомендации игрокам при выборе их личных ходов, т.е. рекомендовать им определенные стратегии.

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

Заметим, что стратегия – задание хода во всех возможных позициях игры – типа домашней заготовки в шахматах.

В зависимости от числа возможной стратегии игры делятся на конечные и бесконечные.

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

Стратегии игроков в тех случаях, когда они в некоторых ситуациях игры отказываются от выбора определенного хода и вместо этого используют личный случайный ход, называются смешанными стратегиями; стратегии, при которых игроки собирают только определенные ходы, называют чистыми стратегиями игроков.

При личном случайном ходе «личность» игрока проявляется в том, что игрок сам задает вероятностное распределение на множестве альтернатив, которое затем реализует механизм случайного выбора (например, подбрасывая монет, игрок задает вероятностное распределение (1/2;1/2) при выборе действия при наличии двух альтернатив).

Дискретные позиционные игры двух игроков

Определение дискретно-позиционной игры двух игроков по Оуэну:

позиционная игра определена, если задано 6 элементов игры:

1. связный ориентированный граф-дерево игры с выделенной вершиной А, являющийся начальной позицией игры. Каждая вершина графа называется позицией игры и соответствует ее определенному состоянию.

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

Вершину Х будем называть конечной позицией игры, если она не предшествует никакой другой позиции игры.

Реализацией или партией игры будем называть любую цепь AX, проходящую по ребрам и вершинам графа-дерева игры и соединяющую начальную позицию игры A с любой из конечных позиций X.

2. вектор – функция выигрыша

которая каждой конечной позиции игры ставит в соотв. два числа , являющиеся выигрышем первого и второго игрока при условии, что игра заканчивается в позиции

3. разбиение множества S всех вершин графа, кроме конечных, на три подмножества очередности хода

– множество вершин граф-дерева игры, в которых производится случайный ход;

– множество вершин графа, в которых ход делает первый игрок;

– множество вершин графа, в которых ход делает второй игрок;

– множество конечных вершин графа, в которых вместо хода игроки получают свои выигрыши.

Подмножества , взаимно не пересекаются.

4. для каждой вершины задано вероятностное распределение:

на множестве ребер-альтернатив , исходящих из , такое, что:

– количество ребер , соединяющих вершину с непосредственно следующими за вершинами графа:

Т.о. четвертый элемент игры определяет в вероятностном смысле развитие игры, если реализация игры попала в вершину .

Это означает, что реализация игры может из позиции пойти по любому из ребер , , причем вероятность случайного события, состоящая в том, что реализация игры пойдет по ребру равна

5. разбиение каждого из множеств очередности хода первого и второго игрока на области информированности игроков (

Необходимость в таком разбиении возникает при наличии у игроков неполной информации о состоянии игры, что соответствует случаю, когда игрок, принимая решение на очередной ход, не знает точно позиции игры, в кот. он в рассм. момент находится, а знает только подмножество позиции игры, среди кот. он находится достоверно. Такое подмножество позиции игры и назыв. областью информированности игрока перед очередным ходом.

Основные свойства области информированности:

1. все позиции из одной и той же области информированности имеют одинаковое количество исходящих ребер альтернатив.

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

В играх с полной информацией о состоянии игры область информированности каждого игрока сужается до одной вершины графа.

6. для каждой из вершин, принадлежащих одной и той же области информированности игроков, задана единая нумерация, исходящих из нее ребер целыми числами .

Каждый номер S ( ребра альтернативы соответствует одному из возможных решений, применяемых игроком в области информированности (или в качестве своего хода в партии игры.