Теория массового обслуживания. Многоканальная смо с неограниченной очередью

⁰

Система с ограниченной длиной очереди . Рассмотрим канальную СМО с ожиданием, на которую поступает поток заявок с интенсивностью ; интенсивность обслуживания (для одного канала) ; число мест в очереди .

Состояния системы нумеруются по числу заявок, связанных системой:

нет очереди:

Все каналы свободны;

Занят один канал, остальные свободны;

Заняты каналов, остальные нет;

Заняты все каналов, свободных нет;

есть очередь:

Заняты все n каналов; одна заявка стоит в очереди;

Заняты все n каналов, r заявок в очереди;

Заняты все n каналов, m заявок в очереди.

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

Многоканальная экспоненциальная СМО отличается от одноканальной следующим. Число каналов в ней более одного. Приходящая заявка становится в очередь, если все каналы заняты. В противном случае заявка занимает свободный канал. (5.56)

Напишем выражения для предельных вероятностей состояний, используя обозначение : (см.5.45)

Вероятность отказа . Поступившая заявка получает отказ, если заняты все n каналов и все m мест в очереди:

(5.57)

Относительная пропускная способность дополняет вероятность отказа до единицы:

Абсолютная пропускная способность СМО:

(5.58)

Среднее число занятых каналов . Для СМО с отказами оно совпадало со средним числом заявок, находящихся в системе. Для СМО с очередью среднее число занятых каналов не совпадает со средним числом заявок, находящихся в системе: последняя величина отличается от первой на среднее число заявок, находящихся в очереди.

Обозначим среднее число занятых каналов . Каждый занятый канал обслуживает в среднем заявок в единицу времени, а СМО в целом обслуживает в среднем А заявок в единицу времени. Разделив одно на другое, получим:

Среднее число заявок в очереди можно вычислить непосредственно как математическое ожидание дискретной случайной величины:

(5.59)

Здесь опять (выражение в скобках) встречается производная суммы геометрической прогрессии (см. выше (5.50), (5.51)-(5.53)), используя соотношение для нее, получаем:

Среднее число заявок в системе:

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

Если заявка застанет не все каналы занятыми, ей вообще не придется ждать (соответствующие члены в математическом ожидании равны нулю). Если заявка придет в момент, когда заняты все п каналов, а очереди нет, ей придется ждать в среднем время, равное (потому что «поток освобождений» каналов имеет интенсивность ). Если заявка застанет все каналы занятыми и одну заявку перед собой в очереди, ей придется в среднем ждать в течение времени (по на каждую впереди стоящую заявку) и т. д. Если заявка застанет в очереди заявок, ей придется ждать в среднем в течение времени . Если вновь пришедшая заявка застанет в очереди уже m заявок, то она вообще не будет ждать (но и не будет обслужена).

Среднее время ожидания найдем, умножая каждое из этих значений на соответствующие вероятности:

(5.60)

Так же, как и в случае одноканальной СМО с ожиданием, отметим, что это выражение отличается от выражения для средней длины очереди (5.59) только множителем , т. е.

Среднее время пребывания заявки в системе , так же, как и для одноканальной СМО , отличается от среднего времени ожидания на среднее время обслуживания, умноженное на относительную пропускную способность:

Системы с неограниченной длиной очереди .

Мы рассмотрели канальную СМО с ожиданием, когда в очереди одновременно могут находиться не более m заявок.

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

Вероятности состояний получим из формул (5.56) предельным переходом (при ). Заметим, что сумма соответствующей геометрической прогрессии сходится при и расходится при > 1. Допустив, что < 1 и устремив в формулах (5.56) величину m к бесконечности, получим выражения для предельных вероятностей состояний:

(5.61)

Вероятность отказа, относительная и абсолютная пропускная способность. Так как каждая заявка рано или поздно будет обслужена, то характеристики пропускной способности СМО составят:

Среднее число заявок в очереди получим при из (5.59):

а среднее время ожидания - из (5.60):

Среднее число занятых каналов , как и ранее, определяется через абсолютную пропускную способность:

Среднее число заявок, связанных с СМО, определяется как среднее число заявок в очереди плюс среднее число заявок, находящихся под обслуживанием (среднее число занятых каналов):

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

СеМО представляет собой совокупность конечного числа обслуживающих узлов, в которой циркулируют заявки, переходящие в соответствии с маршрутной матрицей из одного узла в другой. Узел всегда является разомкнутой СМО . При этом отдельные СМО СМО − структуру системы, а требования, циркулирующие по СеМО , − составляющие материальных потоков (сообщения (пакеты) в коммуникационной сети, задания в мультипроцессорных системах, контейнеры грузопотоков и т.п.).

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

В теории СеМО фундаментальным является понятие состояния сети. Важнейшая характеристика сетей МО − вероятности их состояний. Для определения вероятностей состояний СеМО исследуют протекающий в сети случайный процесс. В качестве моделей протекающих в СеМО процессов также наиболее часто используют марковские и полумарковские.

3.3. Система массового обслуживания как модель

1.5. Сети массового обслуживания

Марковским процессом с непрерывным временем описывают функционирование экспоненциальных СеМО.

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

Теория экспоненциальных СеМО наиболее разработана, и ее широко применяют как для исследования сетей ПД так и для исследования мультипроцессорных вычислительных систем (ВС). Разработаны практические формулы расчета вероятностно-временных характеристик (ВВХ) таких сетей и систем.

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

Анализ работ, посвященных исследованию или расчету немарковских моделей, показывает, что решения, как правило, получены алгоритмически путем сложных численных расчетов с использованием преобразований Лапласа-Стилтьеса, реализуются программно, отличаются большой трудоемкостью, либо значительными погрешностями в оценке показателей производительности информационных систем (ИС) в области средней и большой нагрузки. Поэтому для моделирования СеМО, выходящих из класса мультипликативных, используют приближенные методы.

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

Аналитические методы расчета характеристик ИС базируются, как правило, на анализе экспоненциальных СеMO. При использовании этого математического аппарата удается получить аналитические модели для решения широкого круга задач исследования систем. CеМО − это, прежде всего, совокупность взаимосвязанных систем массового обслуживания. Поэтому необходимо вспомнить основные особенности этих систем.

Сеть массового обслуживания представляет собой совокупность конечного числа N обслуживающих узлов, в которой циркулируют заявки, переходящие в соответствии с маршрутной матрицей из одного узла в другой. Узел всегда является разомкнутой СМО (причем СМО может быть любого класса). При этом отдельные СМО отображают функционально самостоятельные части реальной системы, связи между СМО - структуру системы, а требования, циркулирующие по СеМО, - составляющие материальных потоков (сообщения (пакеты) в коммуникационной сети, задания в мультипроцессорных системах, контейнеры грузопотоков и т.п.).

Для наглядного представления СеМО используется граф, вершины которого (узлы) соответствуют отдельным СМО , а дуги отображают связи между узлами.

Переход заявок между узлами происходит мгновенно в соответствии с переходными вероятностями , p ij - вероятность того, что заявка после обслуживания в узле i перейдет в узел j . Естественно, если узлы непосредственно не связаны между собой, то p ij = 0. Если из i- го узла переход только в один какой-либо узел j , то p ij = 1.

СеМО классифицируют по нескольким признакам (рис. 4).

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

l j = a ij l i ,

где a ij - коэффициент пропорциональности, или относительно источника

l j = a j l 0 ,.

Коэффициент a j называют коэффициентом передачи, он характеризует долю заявок, поступающих в j- й узел от источника заявок, либо - среднее число прохождений заявкой через данный узел за время нахождения заявки в сети.

Если интенсивности потоков заявок в узлах сети связаны нелинейной зависимостью (например, ), то сеть называется нелинейной ..

Сеть всегда линейна, если в ней заявки не теряются и не размножаются.

Разомкнутая сеть – это такая отрытая сеть, в которую заявки поступают из внешней среды и уходят после обслуживания из сети во внешнюю среду. Другими словами, особенностью разомкнутой СеМО (РСеМО) является наличие одного или нескольких независимых внешних источников, которые генерируют заявки, поступающие в сеть, независимо от того, сколько заявок уже находится в сети. В любой момент времени в РСеМО может находиться произвольное число заявок (от 0 до ¥).

Рис. 4. Классификация сетей массового обслуживания

В замкнутой СеМО (ЗСеМО) циркулирует фиксированное число заявок, а внешний независимый источник отсутствует. Исходя из физических соображений, в ЗСеМ О выбирается внешняя дуга, на которой отмечается псевдонулевая точка, относительно которой могут измеряться временные характеристики.

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

В однородной сети циркулируют заявки одного класса. И, наоборот, в неоднородной сети могут присутствовать заявки нескольких классов. Заявки относятся к разным классам, если они различаются хотя бы одним из следующих атрибутов:

Законом распределения длительности обслуживания в узлах;

Приоритетами;

Маршрутами (путями движения заявок в сети).

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

Если хотя бы в одном узле осуществляется приоритетное обслуживание, то это – приоритетная сеть. Приоритет – это признак, определяющий очередность обслуживания. Если обслуживание заявок в узлах осуществляется в порядке поступления, то такая сеть бесприоритетная.

Таким образом, экспоненциальной будем называть СеМО , отвечающую требованиям:

Входные потоки СеМО пуассоновские;

Во всех N СМО время обслуживания заявок имеет экспоненциальную функцию распределения вероятностей, и заявки обслуживаются в порядке прихода;

Переход заявки с выхода i -й СМО на вход j -й является независимым случайным событием, имеющим вероятность p ij ; p i0 - вероятность ухода заявки из CeМО.

Если заявки приходят в сеть и уходят из нее, то сеть называется разомкнутой. Если заявки не приходят в сеть и из нее не уходят, сеть называется замкнутой. Число заявок в замкнутой сети постоянное.

Отказ в обслуживании заявки происходит, когда все m мест в очереди заняты, т.е.:

Относительная пропускная способность равна:

Абсолютная пропускная способность:

Среднее число занятых каналов

21. Многоканальная СМО с ожиданием

Система с ограниченной длиной очереди. Рассмотрим канальную СМО с ожиданием, на которую поступает поток заявок с интенсивностью ; интенсивность обслуживания (для одного канала) ; число мест в очереди .

Состояния системы нумеруются по числу заявок, связанных системой:

нет очереди:

Все каналы свободны;

Занят один канал, остальные свободны;

Заняты каналов, остальные нет;

Заняты все каналов, свободных нет;

есть очередь:

Заняты все n каналов; одна заявка стоит в очереди;

Заняты все n каналов, r заявок в очереди;

Заняты все n каналов, r заявок в очереди.

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

Среднее число занятых каналов. Для СМО с очередью среднее число занятых каналов не совпадает со средним числом заявок, находящихся в системе: последняя величина отличается от первой на среднее число заявок, находящихся в очереди.

Обозначим среднее число занятых каналов . Каждый занятый канал обслуживает в среднем заявок в единицу времени, а СМО в целом обслуживает в среднем А заявок в единицу времени. Разделив одно на другое, получим:

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

Среднее число заявок в системе:

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

Среднее время пребывания заявки в системе, так же, как и для одноканальной СМО, отличается от среднего времени ожидания на среднее время обслуживания, умноженное на относительную пропускную способность:

23/24. Системы с неограниченной длиной очереди. Мы рассмотрели канальную СМО с ожиданием, когда в очереди одновременно могут находиться не более m заявок.

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

Вероятности состояний получим из формул предельным переходом (при ). Заметим, что сумма соответствующей геометрической прогрессии сходится при и расходится при > 1. Допустив, что < 1 и устремив в формулах (5.56) величину m к бесконечности, получим выражения для предельных вероятностей состояний:

Среднее число заявок в очереди получим при из (5.59):

асреднее время ожидания - из (5.60):

Среднее число занятых каналов , как и ранее, определяется через абсолютную пропускную способность:

СМО с ограниченным временем ожидания. Ранее рассматривались системы с ожиданием, ограниченным только длиной очереди (числом m заявок, одновременно находящихся в очереди). В такой СМО заявка, раз ставшая в очередь, не покидает ее, пока не дождется обслуживания. На практике встречаются СМО другого типа, в которых заявка, подождав некоторое время, может уйти из очереди (так называемые «нетерпеливые» заявки).

Рассмотрим СМО подобного типа, предполагая, что ограничение времени ожидания является случайной величиной.

Предположим, что имеется n-канальная СМО с ожиданием, в которой число мест в очереди не ограничено, но время пребывания заявки в очереди является некоторой случайной величиной со средним значением , таким образом, на каждую заявку, стоящую в очереди, действует своего рода пуассоновский «поток уходов» с интенсивностью

Если этот поток пуассоновский, то процесс, протекающий в СМО, будет марковским. Найдем для него вероятности состояний. Нумерация состояний системы связывается с числом заявок в системе - как обслуживаемых, так и стоящих в очереди:

нет очереди:

Все каналы свободны;

Занят один канал;

Заняты два канала;

Заняты все n каналов; есть очередь:

Заняты все n каналов, одна заявка стоит в очереди;

Заняты все n каналов, r заявок стоят в очереди и т. д.

Граф состояний и переходов системы показан на рис. 5.10.

Разметим этот граф, как и раньше; у всех стрелок, ведущих слева направо, будет стоять интенсивность потока заявок . Для состояний без очереди у стрелок, ведущих из них справа налево, будет, как и раньше, стоять суммарная интенсивность потока обслуживании всех занятых каналов. Что касается состояний с очередью, то у стрелок, ведущих из них справа налево, будет стоять суммарная интенсивность потока обслуживании всех n каналов плюс соответствующая интенсивность потока уходов из очереди. Если в очереди стоят r заявок, то суммарная интенсивность потока уходов будет равна

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

Отметим некоторые особенности СМО с ограниченным ожиданием сравнительно с ранее рассмотренными СМО с «терпеливыми» заявками.

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

Напротив, в СМО с «нетерпеливыми» заявками, уходящими рано или поздно из очереди, установившийся режим обслуживания при достигается всегда, независимо от приведенной интенсивности потока заявок . Это следует из того, что ряд для в знаменателе формулы сходится при любых положительных значениях и .

Для СМО с «нетерпеливыми» заявками понятие «вероятность отказа» не имеет смысла - каждая заявка становится в очередь, но может и не дождаться обслуживания, уйдя раньше времени.

Относительная пропускная способность, среднее число заявок в очереди. Относительную пропускную способность q такой СМО можно подсчитать следующим образом. Очевидно, обслужены будут все заявки, кроме тех, которые уйдут из очереди досрочно. Подсчитаем, какое в среднем число заявок покидает очередь досрочно. Для этого вычислим среднее число заявок в очереди:

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

заявок. Относительная пропускная способность СМО будет составлять:

Среднее число занятых каналов по-прежнему получаем, деля абсолютную пропускную способность А на :

Среднее число заявок в очереди. Соотношение (5.64) позволяет вычислить среднее число заявок в очереди , не суммируя бесконечного ряда (5.63). Из (5.64) получаем:

а входящее в эту формулу среднее число занятых каналов можно найти как математическое ожидание случайной величины Z, принимающей значения 0, 1, 2, ..., n с вероятностями , :

25. Игры с противоположными интересами. Основные понятия. Платежная матрица.

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

Игра-мероприятие, состоящее из ряда действий сторон.

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

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

Стороны, участвующие в конфликте наз. игроками, а исход конфликта-проигрышем(выигрышем).

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

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

Стратегические игры моделируют конфликтные ситуации, в которых действуют не менее двух сторон, каждая из которых выступает со своими вариантами действий. Нестратегические игры моделируют конфликтные ситуации, когда либо действует одна сторона, либо существует коалиция сторон, все участники которой выступают с одним набором вариантов действий. Игра называется парной, если в ней участвуют ровно 2 игрока и множественной, если число игроков больше двух. Парная стратегия является антагонистической, если цели сторон прямопротивоположны. В этом случае выигрыш одного игрока является проигрышем другого. Конечные стратегии игры описывают конфликтную ситуацию, в которой все стороны имеют конечное число возможных вариантов действий. Если хотя бы одна сторона имеет бесконечное число вариантов, игра относится к классу бесконечных. При одноходовой игре, любая из сторон имеет по одному ходу. При многоходовой, делается более двух ходов.

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

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

А, В	В 1	В 2	…	В n
А 1	a 11	a 12	…	a 1n
А 2	a 21	a 22	…	a 2n
…	…	…	…	…
А m	a m1	a m2	…	a mn

Строки этой матрицы соответствуют стратегиям игрока A , а столбцы – стратегиям игрока B .

26. Нижняя и верхняя цена игры. Принцип минимакса.

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

Выбранная таким образом стратегия гарантирует одной стороне максимально возможный выигрыш (А) при самой неблагоприятной для него стратегии для любой стороны.

А: оценивает для каждой своей стратегии минимально возможный выигрыш αij..

αi= min αij i=1,m

βj= max αij j=1,n

α= max αi i=1,m

α= max min αij i=1,m, j=1,n –нижняя цена игры

β= min max αij i=1,m, j=1,n –верхняя цена игры

Стратегия игрока А, доставляющая максимальный выигрыш, называется максимальной стратегией. Стратегия В, доставляющая минимальной проигрыш, называется минимальной стратегией.

Величина υ=α=β наз. чистой ценой игры.

27. Игры с седловой точкой.

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

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

При наличии седловой точки, решением игры является пара оптимальной стратегии (A * ij , B * ij), соответствующая этой точке.

Совокупность оптимальных стратегий наз. решением игры чистых стратегий.

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

2. Если В выбрал оптим. стратегию, то какой бы стратегии не придерживался бы А, выигрыш В не превысит чистой цены игры.

28. Решение игры в смешанных стратегиях. Активные стратегии. Теорема об активных стратегиях.

Рассмотрим α ≠β, α<β, α<υ<β.

В случае, если α ≠β, то у такой игры нет седловой точки В этом случае принцип минимакса или максимина не подходит.

(Решение игр 2х2)

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

Активными называются те стратегии, которые доминируют над другими.

Рассмотрим игру 2хn

Наносим на оси цену игрока В.

Из самой высокой точки опускаем перпендикуляр.

Самая высокая точка нижней ломаной является точкой пересечения прямых, соответствующих активным стратегиям В*1 и В*2.

Таким образом исходная игра сокращается до игры 2х2.

Решаем игру и находим вероятности активных стратегий. Вероятности активных стратегий.

Вероятности пассивных стратегий приравниваем к нулю.

36. Игра 2*2.Аналитический и графический способы решения.

В общем случае игра 2 2 определяется матрицей

Прежде всего необходимо проверить, есть ли у данной игры седловая точка. Если да, то игра имеет решение в чистых стратегиях, причём оптимальными стратегиями игроков 1 и 2 соответственно будут чистая максиминная и чистая минимаксная стратегии. Если же игра с матрицей выигрышей А не имеет чистых стратегий, то оба игрока имеют только такие оптимальные стратегии, которые используют все свои чистые стратегии с положительными вероятностями. В противном случае один из игроков (например 1) имеет чистую оптимальную стратегию, а другой – только смешанные. Не ограничивая общности, можно считать, что оптимальной стратегией игрока 1 является выбор с вероятностью 1 первой строки. Далее, по свойству 1 следует, что а 11 = а 12 =  и матрица имеет вид

Легко видеть, что для матриц такого вида одна из стратегий игрока 2 является доминируемой. Следовательно, по свойству 4 этот игрок имеет чистую стратегию, что противоречит предположению.

Пусть Х = (, 1   ) – оптимальная стратегия игрока 1. Так как игрок 2 имеет смешанную оптимальную стратегию, из свойства 1 получим, что (см. также свойство 7)

Отсюда следует, что при   0 столбцы матрицы А не могут быть пропорциональны с коэффициентом пропорциональности, отличным от единицы. Если же коэффициент пропорциональности равен единице, то матрица А принимает вид

и игрок 1 имеет чистую оптимальную стратегию (он выбирает с вероятностью 1 ту из строк, элементы которой не меньше соответствующих элементов другой), что противоречит предположению. Следовательно, если   0 и игроки имеют только смешанные оптимальные стратегии, то определитель матрицы А отличен от нуля. Из этого следует, что последняя система уравнений имеет единственное решение. Решая её, находим

;

Аналогичные рассуждения приводят нас к тому, что оптимальная стратегия игрока 2 Y = ( , 1 -  ) удовлетворяет системе уравнений

Графический метод применим к играм, в которых хотя бы один игрок имеет только две стратегии.

Первый случай.

Рассмотрим игру (2х2) с матрицей без седловой точки.

Решением игры являются смешанные стратегии игроков и , где

х 1 - вероятность применения первым игроком первой стратегии,

х 2 - вероятность применения первым игроком второй стратегии,

у 1 - вероятность применения вторым игроком первой стратегии,

у 2 - вероятность применения вторым игроком второй стратегии.

Очевидно, что

Найдем решение игры графическим методом (рис.1).

На оси ОХ отложим отрезок, длина которого равна единице.

Левый конец (х = 0) соответствует стратегии первого игрока А 1 , правый
(х = 1) - стратегии А 2 .

Внутренние точки отрезка будут соответствовать смешанным стратегиям
первого игрока, где

Через концы отрезка проведем прямые, перпендикулярные оси ОХ, на которых будем откладывать выигрыш при соответствующих чистых стратегиях. Если игрок В применяет стратегию В 1 , то выигрыш при использовании первым игроком стратегий А 1 и А 2 составит соответственно а 11 и а 21 . Отложим эти точки на прямых и соединим их отрезком В 1 В 1 . Если игрок А применяет смешанную стратегию, то выигрышу соответствует некоторая точка М, лежащая на этом отрезке.

Аналогично строится отрезок В 2 В 2 , соответствующий стратегии В 2 игрока В.

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

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

В игре (2х2) обе стратегии являются активными.

Ломаная В 1 КВ 2 является нижней границей выигрыша (рис. 2), получаемого игроком А. Точка К, в которой он максимален, определяет цену игры и ее решение.

Найдем оптимальную стратегию первого игрока. Запишем систему уравнений

Приравнивая выражения для v из уравнений системы и учитывая, что получим

(1)

(2)

Составляя аналогичную систему

и учитывая условие

можно найти оптимальную стратегию игрока В:

(3)

Если игра 2xn или mx2 не является игрой в чистых стратегиях, то необходимо попытаться уменьшить размер игры за счет дублирования и доминирования. Если же это не удается, то с помощью графо-аналитического метода выявить активные стратегии.

Замечание. Активной стратегией называются те стратегии, которые доминируют над другими(те, которые останутся после сокращения)

Рассмотрим игру 2xn

Решаем игру 2х2 и находим вероятности активых стратегий. Вероятностям пассивных стратегий присваиваем нули.

Рассмотрим игру mx2

	В1	В2
А1	a 11	a 12
А2	a 21	a 22
…	…..	……
Аn	a m1	a m2

Нижняя точка верхней ломаной соответствует активным стратегиям ai и aj.

После этого задача сводится к размеру 2х2 и решается способом упомянутом выше.

38. игры m x n сведение решения игры m x n к задаче линейного програмирования. Основная теорема теории игр.

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

Имеется n -канальная СМО с неограниченной очередью. Поток заявок, поступающих в СМО, имеет интенсивность , а поток обслуживаний – интенсивность . Необходимо найти предельные вероятности состояний СМО и показатели ее эффективности.

Система может находиться в одном из состояний s 0 , s 1 , s 2 ,…,s k ,…,s n , нумеруемых по числу заявок, находящихся в СМО: s 0 – в системе нет заявок (все каналы свободны); s 1 – занят один канал, остальные свободны; s 2 – заняты два канала, остальные свободны;…; s k – занято k каналов, остальные свободны;…; s n – заняты все n каналов (очереди нет); s n +1 – заняты все n каналов, в очереди одни заявка;…; s n + r – заняты все n каналов, r заявок в очереди.

Граф состояний приведен на рис. 7

… …

В отличие от одноканальной СМО интенсивность потока обслуживаний не остается постоянной, а по мере увеличения числа заявок в СМО от 0 до n увеличивается от величины до , т.к. соответственно увеличивается число каналов обслуживания. При числе заявок больше, чем n , интенсивность потока обслуживаний сохраняется равной . Если в системе n каналов обслуживания с интенсивностью , интенсивность входящего потока равна , то, чтобы очередь не стала бесконечно большой, необходимо выполнение условия стационарности

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

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

Используя формулы (11)для процесса гибели и размножения, можно получить формулы для предельных вероятностей состояний n -канальной СМО с неограниченной очередью

(31)

,…, ,…, (32)

,…,

Вероятность того, что в системе заняты обслуживанием все n каналы, определяется по формуле

(33)

Для n -канальной СМО с неограниченной очередью, используя прежние приемы, можно найти:

Среднее число занятых каналов

Среднее число заявок в очереди

Среднее число заявок в системе

Среднее время обслуживания заявки

Среднее время ожидания обслуживания

Полученные выше формулы значительно упрощаются в случае одно – или двухканальной системы

При n=1

Т.к.

;

При n=2

Т.к.

Пример 7. К двум продавцам поступает на обслуживание поток покупателей с интенсивностью 220 человек в час. Каждый из продавцов затрачивает на обслуживание покупателя в среднем 30 секунд. Определите среднюю длину очереди и показатели занятости продавцов.

Решение. , ,

– интенсивность загрузки

– среднее число занятых обслуживанием каналов

– средняя длина очереди

– доля времени простоя продавцов

– доля времени занятости одного из двух продавцов

– доля времени занятости двух продавцов

Пример 8. В универсаме к узлу расчета поступает поток покупателей с интенсивностью . Средняя продолжительность обслуживания контролером-кассиром одного покупателя . Определить минимальное количество контролеров-кассиров n мин , при котором очередь не будет расти до бесконечности и соответствующие характеристики обслуживания при n=n мин .

Решение. По условию , . Очередь не будет возрастать до бесконечности при условии , т.е. при . Таким образом, минимальное количество контролеров-кассиров n min =3 .Р отк =0 , относительная пропускная способность Q=1 , а абсолютная пропускная способность равна интенсивности входящего потока заявок, т.е. .

Для нашей задачи абсолютная пропускная способность узла расчета A=1,35 1/мин или 81 1/ч , т.е. 81 покупатель в час.

Анализ характеристик обслуживания свидетельствует о значительной перегрузке узла расчета при наличии трех контролеров-кассиров.

В систему поступает пуассоновский поток требований интенсивностью λ, поток обслуживания имеет интенсивность μ, максимальное число мест в очереди – т. Если заявка поступает в систему, когда все места в очереди заняты, она покидает систему необслуженной.

Финальные вероятности состояний такой системы всегда существуют, так как число состояний конечно:

S 0 – система свободна и находится в состоянии простоя;

S 1 – обслуживается одна заявка, канал занят, очереди нет;

S 2 – одна заявка обслуживается, одна в очереди;

S m +1 - одна заявка обслуживается,т в очереди.

Граф состояний такой системы показан на рисунке номер 5:

S 0 S 1 S 2 S m+1

μ μ μ ………. μ μ

Рисунок 5: Одноканальная СМО с ограниченной очередью.

В формуле для р 0 найдем сумму конечного числа членов геометрической прогрессии:

(52)

С учетом формулы для ρ получим выражение:

В скобках находится (m+2) элементов геометрической прогрессии с первым членом 1 и знаменателем ρ. По формуле суммы (m+2) членов прогрессии:

(54)

(55)

Формулы для вероятностей предельных состояний будут иметь вид:

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

(57)

Отсюда вероятность обслуживания (а также и относительная пропускная способность ) равны вероятности противоположного события:

Абсолютная пропускная способность – число заявок, обслуженных системой в единицу времени:

(59)

Среднее число заявок под обслуживанием:

(60)

(61)

Среднее число заявок в системе:

(62)

Одноканальную СМО с ограниченной очередью можно рассмотреть в Mathcad.

Пример :

На стоянке обслуживается 3 машины с интенсивностью потока 0,5 и средним временем обслуживания 2,5 минуты. Определить все показатели системы.

6 Многоканальная смо с неограниченной очередью

Пусть дана система S, имеющаяп каналов обслуживания, на которые поступает простейший поток требований интенсивностью λ. Пусть поток обслуживания также простейший и имеет интенсивность μ. Очередь на обслуживание не ограничена.

По числу заявок, находящихся в системе, обозначим состояния системы: S 0 ,S 1 ,S 2 ,…,S k ,… S n , гдеS k – состояние системы, когда в ней находитсяkзаявок (максимальное число заявок под обслуживанием -n). Граф состояний такой системы изображается в виде схемы на рисунке номер 6:

λ λ λ λ λ λ λ

……. …….

S 0 S 1 S 2 S m+1 S n

μ 2μ 3μ ………. kμ (k+1)μ …… nμ nμ

Рисунок 6: Многоканальная СМО с неограниченной очередью.

Интенсивность потока обслуживаний меняется в зависимости от состояния системы: kμ при переходе из состоянияS k в состояниеS k -1 так как может освободиться любой изk каналов; после того, как все каналы заняты обслуживанием, интенсивность потока обслуживаний остается равнойпμ, при поступлении в систему следующих заявок.

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

(63)

Отсюда формулы для финальных вероятностей выражаются через

Для нахождения р 0 получим уравнение:

Для слагаемых в скобках, начиная с (n+ 2)-го, можно применить формулу нахождения суммы бесконечно убывающей геометрической прогрессии с первым членоми знаменателем ρ/n:

(66)

Окончательно получим формулу Эрланга для нахождения вероятности простоя системы:

(67)

Приведем формулы для расчета основных яоказателей эффективности работы системы.

Система будет справляться с потоком заявок, если

выполнено условие

, (68)

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

Отсюда вероятность обслуживания (а также иотносительная пропускная способность системы) равны вероятности противоположного события, то есть единице:

(69)

Абсолютная пропускная способность - число заявок, обслуженныхсистемой в единицу времени:

(70)

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

ν=λ . (71)

Так как каждый канал обслуживает μ заявок в единицу времени, то среднее число занятых каналов можно вычислить:

(72)

Среднее время обслуживания каналом одной заявки;

. (73)

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

(74)

Число заявок, находящихся под обслуживанием, равно числу занятых каналов:

(75)

Среднее число заявок в очереди:

(76)

Тогда среднее число заявок в системе:

(77)

Среднее время пребывания заявки в системе (в очереди):

(78)

(79)

Многоканальную СМО с неограниченной очередью можно рассмотреть в системе Mathcad.

Пример 1 :

Салон-парикмахерская имеет 5 мастеров. В час пик интенсивность потока клиентов равна 6 человек. В час. Обслуживание одного клиента длится в среднем 40 минут. Определить среднюю длину очереди, считая ее неограниченной.

Фрагмент решения задачи в Mathcad.

Пример 2:

В железнодорожной кассе имеются 2 окна. Время на обслуживания одного пассажира 0,5 минут. Пассажиры подходят к кассе по 3 человека. Определить все характеристики системы.

Фрагмент решения задачи в Mathcad.

Продолжение решения задачи в Mathcad.

2.2 Многоканальная СМО с ожиданием

Состояния системы нумеруются по числу заявок, связанных системой:

нет очереди:

Все каналы свободны;

Занят один канал, остальные свободны;

Заняты -каналов, остальные нет;

Заняты все -каналов, свободных нет;

есть очередь:

Заняты все n-каналов; одна заявка стоит в очереди;

Заняты все n-каналов, r-заявок в очереди;

Заняты все n-каналов, r-заявок в очереди.

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

Рис. 17. Многоканальная СМО с ожиданием

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

Таким образом, все вероятности состояний найдены.

Определим характеристики эффективности системы.

Вероятность отказа. Поступившая заявка получает отказ, если заняты все n-каналов и все m-мест в очереди:

(18)

Относительная пропускная способность дополняет вероятность отказа до единицы:

Абсолютная пропускная способность СМО:

(19)

Среднее число занятых каналов. Для СМО с отказами оно совпадало со средним числом заявок, находящихся в системе. Для СМО с очередью среднее число занятых каналов не совпадает со средним числом заявок, находящихся в системе: последняя величина отличается от первой на среднее число заявок, находящихся в очереди.

Обозначим среднее число занятых каналов . Каждый занятый канал обслуживает в среднем -заявок в единицу времени, а СМО в целом обслуживает в среднем А-заявок в единицу времени. Разделив одно на другое, получим:

(20)

Здесь опять (выражение в скобках) встречается производная суммы геометрической прогрессии (см. выше (11), (12) - (14)), используя соотношение для нее, получаем:

Среднее число заявок в системе:

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

Если заявка застанет не все каналы занятыми, ей вообще не придется ждать (соответствующие члены в математическом ожидании равны нулю). Если заявка придет в момент, когда заняты все n-каналов, а очереди нет, ей придется ждать в среднем время, равное (потому что «поток освобождений» -каналов имеет интенсивность ). Если заявка застанет все каналы занятыми и одну заявку перед собой в очереди, ей придется в среднем ждать в течение времени (по на каждую впереди стоящую заявку) и т. д. Если заявка застанет в очереди -заявок, ей придется ждать в среднем в течение времени . Если вновь пришедшая заявка застанет в очереди уже m-заявок, то она вообще не будет ждать (но и не будет обслужена). Среднее время ожидания найдем, умножая каждое из этих значений на соответствующие вероятности:

(21)

Так же, как и в случае одноканальной СМО с ожиданием, отметим, что это выражение отличается от выражения для средней длины очереди (20) только множителем , т. е.

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

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

Вероятности состояний получим из формул предельным переходом (при ). Заметим, что сумма соответствующей геометрической прогрессии сходится при и расходится при >1. Допустив, что <1 и устремив в формулах величину m к бесконечности, получим выражения для предельных вероятностей состояний:

(22)

Среднее число заявок в очереди получим при из (20):

а среднее время ожидания - из (21):

Среднее число занятых каналов , как и ранее, определяется через абсолютную пропускную способность:

Пример 2. Автозаправочная станция с двумя колонками (n = 2) обслуживает поток машин с интенсивностью =0,8 (машин в минуту). Среднее время обслуживания одной машины:

В данном районе нет другой АЗС, так что очередь машин перед АЗС может расти практически неограниченно. Найти характеристики СМО.

Поскольку<1, очередь не растет безгранично и имеет смысл говорить о предельном стационарном режиме работы СМО. По формулам (22) находим вероятности состояний:

и т. д.

Среднее число занятых каналов найдем, разделив абсолютную пропускную способность СМО А==0,8 на интенсивность обслуживания =0,5:

Вероятность отсутствия очереди у АЗС будет:

Среднее число машин в очереди:

Среднее число машин на АЗС:

Среднее время ожидания в очереди:

Среднее время пребывания машины на АЗС:

СМО с ограниченным временем ожидания. Ранее рассматривались системы с ожиданием, ограниченным только длиной очереди (числом m-заявок, одновременно находящихся в очереди). В такой СМО заявка, разраставшая в очередь, не покидает ее, пока не дождется обслуживания. На практике встречаются СМО другого типа, в которых заявка, подождав некоторое время, может уйти из очереди (так называемые «нетерпеливые» заявки).

Рассмотрим СМО подобного типа, предполагая, что ограничение времени ожидания является случайной величиной.

Предположим, что имеется n-канальная СМО с ожиданием, в которой число мест в очереди не ограничено, но время пребывания заявки в очереди является некоторой случайной величиной со средним значением, таким образом, на каждую заявку, стоящую в очереди, действует своего рода пуассоновский «поток уходов» с интенсивностью:

нет очереди:

Все каналы свободны;

Занят один канал;

Заняты два канала;

Заняты все n-каналов;

есть очередь:

Заняты все n-каналов, одна заявка стоит в очереди;

Заняты все n-каналов, r-заявок стоят в очереди и т. д.

Граф состояний и переходов системы показан на рис. 23.

Рис. 23. СМО с ограниченным временем ожидания

Разметим этот граф, как и раньше; у всех стрелок, ведущих слева направо, будет стоять интенсивность потока заявок . Для состояний без очереди у стрелок, ведущих из них справа налево, будет, как и раньше, стоять суммарная интенсивность потока обслуживании всех занятых каналов. Что касается состояний с очередью, то у стрелок, ведущих из них справа налево, будет стоять суммарная интенсивность потока обслуживания всех n-каналов плюс соответствующая интенсивность потока уходов из очереди. Если в очереди стоят r-заявок, то суммарная интенсивность потока уходов будет равна .

(24)

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

Напротив, в СМО с «нетерпеливыми» заявками, уходящими рано или поздно из очереди, установившийся режим обслуживания при достигается всегда, независимо от приведенной интенсивности потока заявок . Это следует из того, что ряд для в знаменателе формулы (24) сходится при любых положительных значениях и .

На каждую из этих заявок действует «поток уходов» с интенсивностью . Значит, из среднего числа -заявок в очереди в среднем будет уходить, не дождавшись обслуживания, -заявок в единицу времени и всего в единицу времени в среднем будет обслуживаться -заявок. Относительная пропускная способность СМО будет составлять:

Среднее число занятых каналов по-прежнему получаем, деля абсолютную пропускную способность А на :

(26)

Среднее число заявок в очереди. Соотношение (26) позволяет вычислить среднее число заявок в очереди , не суммируя бесконечного ряда (25). Из (26) получаем:

В заключение заметим, что если в формулах (24) перейти к пределу при (или, что то же, при ), то при

Очередь длины k, остается в ней с вероятностью Pk и не присоединяется к очереди с вероятностью gk=1 - Pk,". именно так обычно ведут себя люди в очередях. В системах массового обслуживания, являющихся математическими моделями производственных процессов, возможная длина очереди ограничена постоянной величиной (емкость бункера, например). Очевидно, это частный случай общей постановки. Некоторые...