Контрольная работа по "Исследование операций"

Задача № 11.

 По заданному графу состояний, руководствуясь известными формальными правилами, записать уравнения Колмогорова для отображённого графом случайного Марковского процесса. Предварительно пометить все стрелки символами λ_ij

 

Решение:

 

Формальные правила записи уравнения Колмогорова:

 

Количество уравнений равно  количеству состояний, в которых  система пребывает по ходу процесса.

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

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

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

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

 

- возможное состояние системы

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

 

 

 

 

 

 

В соответствии с данными правилами  и графом получаю:

 

   

 

   

 

 

- вероятность того, что система находится в состоянии  
Задача № 12.

По заданному графу состояний, руководствуясь известными формальными  правилами, записать алгебраические уравнения  для вероятностей состояний в  отображённом ниже уже размеченным графом случайном Марковском процессе. Найти вероятности состояний при следующих числовых значениях интенсивностей: λ₁₂=2;  λ₁₃ =3;

λ₃₂=2;  λ ₄₃ =2;

λ₃₁ =1;  λ₂₄ =1. 

Решение:

 

- возможное состояние системы

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

- вероятность того, что система  находится в состоянии 

 

 

 

В соответствии с формальными правилами  записи уравнения Колмогорова получаю:

 

   

 

  

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

 

Подставляю  значения:

 

   

  

   

  

 

Ответ:       

 

Задача № 13.

Разметить граф  состояний символами  λ_ij и в буквенном виде найти вероятности состояний.

 

Решение:

 

 

- возможное состояние системы

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

- вероятность того, что система  находится в состоянии 

 

 

Для циклических Марковских процессов  справедливо:

     

При подстановке  в уравнение  последующего состояния получаю:

   

Вероятность первого состояния  нахожу из условия нормировки вероятностей

Подставляю все только что полученные выражения:

Для циклических Марковских процессов вероятность каждого состояния равна:

доле времени, которую в ходе процесса система провидит, именно, в этом состоянии: , где ,

, следовательно: 

, следовательно: 

, следовательно: 

 

 

Задача № 14. Древний вычислительный комплекс (типа БЭСМ).

 

Возможные состояния:

S₁ – комплекс исправен и эксплуатируется;

S₂ – комплекс отказал, неисправность локализуется;

S₃ –  комплекс ремонтируется;

S₄ –  комплекс отремонтирован, загружается, тестируется, готовится к эксплуатации.                                             2

                                                                                  

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

 

Решение:

 

     

                        

 

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

 

1/ряд

 

 

 

 

 

 

 

 

 

Задача № 15. Учебная задача о справочном бюро.

В справочном бюро  в среднем  каждые  0,8  минуты раздаётся звонок.

Поиск информации и выдача справки в среднем занимает 1,5 минуты (t_обсл.=1,5мин.).

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

 

Решение:

 

Уточняем  параметры системы массового обслуживания – единственного в бюро телефонного канала. У системы два состояния: S₀ – канал свободен и S₁– канал занят.

Интенсивность потока заявок – ₀₁ = 0.8 = 1,25 (запросов в одну минуту).

Интенсивность потока обслуживаний – ₁₀ = 1/ t_обсл. = 1/1,5 = (количество справок в одну минуту).

 

По характеру  графа состояний определяем, что  в системе со временем установится 

                                                                 стационарный и более того – эргодический процесс.

         Граф состояний  системы                        (это – процесс «гибели-размножения»)                     

                                ₀₁                                                        В соответствии с этим, записываем алгебраические                                

                                                          уравнения для отыскания вероятностей  состояний

                                ₁₀                          (по правилу:  «сколько втекает – столько вытекает»):

 

             ₀₁ P₀  =   ₁₀ P₁                           Эту  пару уравнений, где  P₀ и P₁ – вероятности

             ₁₀ P₁= ₀₁ P₀                      состояний S₀ и, S_{1 ,}  соответственно, дополняем соотношением  P₀+ P₁= 1 (условие нормировки вероятностей для полной группы событий, которую составляют оба возможных состояния нашей системы).

 

Из этого  последнего соотношения выразим  P₁= 1– P₀ , и это выражение вставим в первое уравнение.

Получаем: ₀₁ P₀  =   ₁₀ (1– P₀)   = ₁₀ – ₁₀ P₀ .  Или:                

₀₁ P₀ + ₁₀ P₀    =   ₁₀ . Отсюда: P₀ ( ₀₁+ ₁₀ )    =   ₁₀

 

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

P₀  = ₁₀[ ₀₁+ ₁₀ ] ^{– 1}  и  P₁ = 1– P₀ = 1– ₁₀[ ₀₁+ ₁₀ ] ^{– 1}  = ₀₁ [ ₀₁+ ₁₀ ] ^{– 1}  .

Это и есть запрошенная в задаче вероятность  отказа.

 

Теперь  об абсолютной  пропускной способности А.   

По  определению, А= qх ₀₁, где q – относительная пропускная способность, которая равна доле обслуживаемых системой заявок, то есть – доле заявок, которые приходят в систему в те периоды времени, когда она свободна. Это происходит с вероятностью P₀.

Следовательно, q = P₀ = ₁₀[ ₀₁+ ₁₀ ] ^{– 1}  и А= qх ₀₁ = _{01 10}[ ₀₁+ ₁₀ ] ^{– 1} .

 

В «буквенном виде» задача решена.

 

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

P₀ = 0,8х [0,8+ ] ^{– 1}  = 0,8х [1,466… ] ^{– 1} 0,455  (около 45,5%).

P₁= 1– P₀ = 1–0,455 0,545 ( 54,5%). А= qх ₀₁=P₀х ₀₁=0,455х0,8 0,66 (спр. в минуту).

 

Задача № 16. Более реальная задача о справочном бюро.

В справочном бюро  в среднем  каждые  0,8  минуты раздаётся звонок. Поиск информации и выдача справки  в среднем занимает 1,5 минуты (t_обсл.=1,5мин.).

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

Привести  полное решение задачи.

 

Решение:

 

Граф состояний системы

 

 λ λ    λ

 

 

   μ            2μ                    3μ

 

S0 – все линии свободны

S1 – 1 занята, 2 свободны

S2 – 2 заняты, 1 свободна

S3 – все линии заняты

 

(звонков в минуту)   (справок в минуту)

 

По характеру графа состояний  определяем, что в системе со временем установится стационарный и более  того – эргодический процесс (это – процесс «гибели-размножения»)                     

Использую формулу Эрланга:

, где:     - мера относительной загрузки системы

Подставляю значения и получаю:

Вероятность того, что все линии  свободны:

,следовательно: 

Остальные вероятности можно найти по формуле:

Вероятность того, что все линии  заняты:

, следовательно: 

 
Следовательно вероятность того, что свободна хотя бы одна линия:

 

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

справок в минуту.

 

Задача № 17. Задача о докерах.

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

Найти:

-    относительную и

-    абсолютную пропускную  способность порта;    

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

• среднее время пребывания судна в порту и вероятность (для прибывающего сухогруза) провести часть ожидания вне бухты.

 

 

 

 

 

 

Решение:

             λ               λ                 λ                λ                λ              λ      λ                λ

             μ                μ                   μ                   μ               μ             μ     μ                  μ

 

S₀ – канал свободен.

S₁ – канал занят, очереди нет.

S₂ – канал занят, одна заявка находится в очереди на внутреннем рейде.

S₃ – канал занят, две заявки находятся в очереди на внутреннем рейде.

S₄ – канал занят, три заявки находятся в очереди на внутреннем рейде.

S₅ – канал занят, внутренний рейд занят, одна заявка на внешнем рейде.

S_k – канал занят, внутренний рейд занят, заявок на внешнем рейде.

 

В сутки поступает две заявки, следовательно:

 

Время обслуживания одной заявки 9ч36мин, следовательно:

 

Мера относительной загрузки системы :  

 

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

 

Абсолютная пропускная способность:  сухогруза в сутки

 

 

Среднее кол-во судов, ожидающих разгрузки:

 

, где  - число мест в очереди, при получаю:

 

Среднее кол-во судов, ожидающих разгрузки  в бухте:

 

 

Среднее кол-во судов, ожидающих разгрузки на внешнем рейде:

 

 

Среднее время простоя судов  на внутреннем рейде:

 

суток

 

Среднее время простоя судов  на внешнем рейде:

 

суток

 

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

 

суток

 

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

 

=

 

=  
Задача № 18. Задача об автозаправочной станции.

АЗС с двумя бензораздаточными колонками имеет на своей территории парковочную площадку для трех автомобилей. На заправку, которая здесь в среднем длится две минуты, каждую минуту прибывают две автомашины. Часть из них сразу же отъезжает, если все места на площадке ожидания заняты.