Шпаргалка по "Исследованию операций в экономике"

     13. Системы массового  обслуживания (СМО)  и показатели их эффективности.

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

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

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

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

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

     14. Уравнения динамики  для вероятностных  состояний (уравнения Колмогорова). Предельные вероятности состояний.

     Формально дифференцируя уравнение Колмогорова—Чепмена  по s при s = 0 получаем прямое уравнение  Колмогорова:

     

     где

     

     Формально дифференцируя уравнение Колмогорова — Чепмена по t при t = 0 получаем обратное уравнение Колмогорова

     

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

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

     На  рис. показаны граф состояния и переходов, удовлетворяющие поставленному  условию: из любого состояния система  рано или поздно может перейти  в любое другое состояние. Условие  не будет выполняться при изменении направления стрелки 4—3 на графе рис , а на противоположное.

     Допустим, что поставленное условие выполнено, и, следовательно, предельные вероятности  существуют:

     

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

     

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

     15. Процесс гибели и размножения.

     

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

     Потоками  размножения λi(t) будем называть пуассоновские потоки, ведущие к  увеличению функции X(t). Соответственно μi(t) – потоки гибели, ведущие к уменьшению функции X(t).

     Составим  по графу уравнения Колмогорова:

     

     Если  поток с конечным числом состояний:

     

     Система уравнений Колмогорова для процесса гибели и размножения с ограниченным числом состояний имеет вид:

     

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

     

     

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

     

     

     16. Системы массового  обслуживания с  отказами.

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

     Следует отметить, что в данном случае количество каналов равно 1 (). Этот канал принимает пуассоновский поток заявок, интенсивность которого равняется . Время оказывает влияние на интенсивность:

     

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

     

     

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

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

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

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

       —канал свободен;

       —канал занят, очереди нет;

• — канал занят, одна заявка стоит в очереди;
• —канал занят, k - 1 заявок стоят в очереди;
• — канал занят, т заявок стоят в очереди.

18. Методы принятия  решений в условиях  конфликта. Матричные игры. Чистые и смешанные стратегии игр.

          Матричная игра – это конечная игра двух игроков с нулевой суммой, в которой задаётся выигрыш  игрока 1 в виде матрицы (строка матрицы соответствует номеру применяемой стратегии игрока 2, столбец – номеру применяемой стратегии игрока 2; на пересечении строки и столбца матрицы находится выигрыш игрока 1, соответствующий применяемым стратегиям).

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

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

     Первый  игрок имеет  m  стратегий  i = 1,2,...,m, второй имеет  n  стратегий  j = 1,2,...,n. Каждой паре стратегий  (i,j)  поставлено в соответствие число аij, выражающее выигрыш игрока 1 за счёт игрока 2, если первый игрок примет свою i-ю стратегию, а 2 – свою j-ю стратегию.

     Каждый  из игроков делает один ход: игрок 1 выбирает свою i-ю стратегию (i=), 2 –  свою j-ю стратегию (j=), после чего игрок 1 получает выигрыш аij за счёт игрока 2 (если аij<0, то это значит, что игрок 1 платит второму сумму  | аij|). На этом игра заканчивается.

     Каждая  стратегия игрока  i=;  j =  часто  называется чистой стратегией.

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

     Таким образом, если игрок 1 имеет  m  чистых стратегий  1,2,...,m, то его смешанная  стратегия  x– это набор чисел  x = (x1,..., xm) удовлетворяющих соотношениям

     xi³  0     (i= 1,m),     =1.

     Аналогично  для игрока 2, который имеет  n  чистых стратегий, смешанная стратегия  y– это набор чисел

     y = (y1, ..., yn),     yj ³ 0,   (j = 1,n),     = 1.

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

     Чистая  стратегия есть частный случай смешанной  стратегии. Действительно, если в смешанной  стратегии какая-либо i-я  чистая стратегия применяется с вероятностью 1, то все остальные чистые стратегии не применяются. И эта  i-я  чистая стратегия является частным случаем смешанной стратегии. Для соблюдения секретности каждый игрок применяет свои стратегии независимо от выбора другого игрока. 

     19. Геометрический метод  решения матричной  игры.

     Решение игр размера 2xn или nx2 допускает наглядную  геометрическую интерпретацию. Такие  игры можно решать графически.

     На  плоскости XY по оси абсцисс отложим  единичный отрезок A1A2 (рисунок 5.1). Каждой точке отрезка поставим в соответствие некоторую смешанную стратегию U = (u1, u2). Причем расстояние от некоторой промежуточной точки U до правого конца этого отрезка – это вероятность u1 выбора стратегии A1, расстояние до левого конца - вероятность u2 выбора стратегии A2. Точка А1 соответствует чистой стратегии А1, точка А2 – чистой стратегии А2.

     В точках А1 и А2 восстановим перпендикуляры и будем откладывать на них  выигрыши игроков. На первом перпендикуляре (совпадающем с осью OY) покажем  выигрыш игрока А при использовании стратегии А1, на втором – при использовании стратегии A2. Если игрок А применяет стратегию A1, то его выигрыш при стратегии B1 игрока B равен 2, а при стратегии B2 он равен 5. Числам 2 и 5 на оси OY соответствуют точки B1 и B2. Аналогично на втором перпендикуляре найдем точки B'1 и B'2 (выигрыши 6 и 4).