Исследование операций. Линейное, динамическое программирование


Исследование операций - часть 112


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

1) К сожалению, этим недостатком страдает и книга [6] автора, где ряд выводов получен недостаточно просто.

 

§ 19. Схема гибели и размножения. Формула Литтла

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

 

 

 

Рис.19.1

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

Граф состояний для схемы гибели и размножения имеет вид, показанный на рис. 19.1. Особенность этого графа в том, что все состояния системы можно вытянуть в одну цепочку, в которой каждое из средних состояний (S1, S2,…,Sn-1) связано прямой и обратной стрелкой с каждым из соседних состояний — правым и левым, а крайние состояния (S0, Sn) — только с одним соседним состоянием. Термин «схема гибели и размножения» ведет начало от биологических задач, где подобной схемой описывается изменение численности популяции.

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

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

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


Начало  Назад  Вперед



Книжный магазин