Алгоритм и этапы решения задачи

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

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

Решение.

Рассмотрим этапы табличного метода расчета данной сетевой модели. Результаты расчетов приведены в табл. 5.3 в графах 1—9.

Пояснения

Этап 1. Перечень работ и их продолжительность запишем в гр. 2 и 3 табл. 5.3, при этом работы записываются последовательно в гр. 2: сначала — начинающиеся с номера 1, затем с ном.2 и т.д.

Этап2. В первой графе поставим число Kпр, показывающее количество работ, непосредственно предшествуюших событию i, с которого начинается рассматриваемая работа. Для работ, начинающихся с номера 1 предшествующих работ нет. Для работы, начи­нающейся с

 

номера к, просматриваются все верхние строки второй гра-фы и отыскиваются работы, начинающиеся на к. Количество найденных работ записывается во все строки гр.1, которые соответствуют рабо-там, начинающимся с номера k Например, для работы (4, 5) в гр. 1 поставим цифру 2, так как на номер 4 оканчиваются две работы: (1, 4) и (3, 4).

Этап 3. Заполнение таблицы начинается с расчета раннего срока работ tp(i). Для работ, имеющих цифру «НОЛь» в первой гра­фе, в гр. 4 также заносятся нули и рассчитываются соответствую­щие значения гр. 5 (ранний срок окончании tро(I,j) как суммы соответствующих чисел в гр. 2 и 3 (см. формулу (5.41)). В нашей мо­дели таких работ три; в первой строке гр. 5 ставим 6 + 0 = 6, ана­логично во второй и третьей строках.

Для заполнения следующих строк гр. 4. для работ (i,j)просмат­риваются заполненные строки гр. 5, котОрые содержат работы, оканчивающиеся на номер i, и максимальНое из наИденных значе­ний (если их несколько) переносится в гр 4 для обрабатываемых строк. Так, в нашем примере в четвертой строке в гр. 4 ставим 6, а гр 5

15 (9 + 6 = 15).

Аналогично в пятой строке гр. 4 и 5 ставим соответственно 5 и 17

(12 + 5 = 17).

В последней, шестой, строке гр. 4 ставим 17 (наибольшее из чисел 8 и 17 в гр 5) и соответствен­но в гр. 5 ставим 21 (4 + 17 = 21).

Этап 4. Графы 7 и 6 заполняются «обратным ходом», т.е. снизу вверх. Для этого просматриваются строки (работы), оканчи­вающиеся на номер N последнего события, и из гр.5 выбирается величина. Эта величина записывается в гр. 7 по всем строкам, оканчивающимся на N (см. формулу (5.42) с учетом ра­венства tn(N) = tp(N)). Затем заполняется гр. 6 по этим строкам как разность между гр. 7 и 3 (см. формулу (5.43)).

В нашем примере таких строк две (четвертая и шестая), в гр. 5 стоят числа 15 и 21; выбираем наибольшее из них (21) и записываем его в гр. 7 по этим строкам, после чего заносим соответствующие числа в гр. 6.

Далее просматриваются строки, оканчивающиеся на номер со­бытия, предшествующего заверша-ющему, т.е. на (N — 1). Для этих строк просмат-риваются все строки гр. 6, лежащие ниже и начинающиеся с номера (N — 1). Среди них в гр. 6 выбирается минимальная величина, которая переносится в гр. 7 по обрабатываемым строкам, после чего заполняется гр. 6. В нашем примере таких строк две (третья и пятая); ниже их с номера 4 начинается одна (последняя) работа, и в гр. 6 стоит 17, следовательно, в гр. 7 по этим строкам ставим число 17, после чего заполняется гр. 6.

Затем аналогичный процесс повторяется для строк, оканчивающихся на (N — 2), (N — 3) и т д., до тех пор, пока не будут заполнены все строки по гр. 7 и 6. В нашем примере результаты приведены в соответствующих графах табл. 5.3.

Этап 5. Показатели гр. 8 рассчитываются как разности соответствующих показателей гр. 6 и 4 или гр. 7 и 5 (см. формулы (5.39) или (5.44)). Чтобы заполнить гр. 9, можно предварительно рассчитать резервы времени каждого события по формуле (5.39), а затем воспользоваться формулой (5.46). В нашем примере резервы времени для каждого из пяти событий равны соответственно: R(1) = 0; R(2) = 12 - 6 = 6; R(3) = 5-5 = 0; R(4) = 17 - 17 = 0; R(5) = 0. Последующие результаты по формуле (5.46) приведены в гр. 9 табл. 5.3.

Этап 6. На этом этапе подводятся основные итоги расчета. Учитывая, что нулевой резерв времени имеют только работы (Rn = 0) и события (R(i) = 0), принадлежащие критичес-кому пути, получаем, что критическим является путь LKp = (1, 3, 4, 5), продолжитель­ность которого (tкр) равна 21 дню.

Так как работы (1, 2), (1, 4) и (2, 5) имеют ненулевые резервы Rn, то очевидно, что путем перевода некоторого числа рабочих с этих работ на работы, принадлежащие критиче-кому пути, можно сократить продолжитель-ность этого пути и тем самым сократить сроки выполнения проекта в целом.

 

19.4. Сети Петри

Сети Петри — математический аппарат для моделирования динамических дискретных систем.

Впервые описаны Карлом Петри в 1984 году.

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

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

Пример сети Петри. Белыми кружками обозначены позиции, полосками — переходы, чёрными кружками — метки.

Некоторые виды сетей Петри:

• Временная сеть Петри — переходы обладают весом, определяющим продолжительность срабатывания (задержку).
• Стохастическая сеть Петри — задержки являются случайными величинами.
• Функциональная сеть Петри — задержки определяются как функции некоторых аргументов, например, количества меток в каких-либо позициях, состояния некоторых переходов.
• Цветная сеть Петри — метки могут быть различных типов, обозначаемых цветами, тип метки может быть использован как аргумент в функциональных сетях.
• Ингибиторная сеть Петри — возможны ингибиторные дуги, запрещающие срабатывания перехода, если во входной позиции, связанной с переходом ингибиторной дугой, находится метка.
• Иерархическая сеть — содержит не мгновенные переходы, в которые вложены другие, возможно, также иерархические, сети. Срабатывание такого перехода характеризует выполнение полного жизненного цикла вложенной сети.
• WF-сети

Основными свойствами сети Петри являются:

• ограниченность — число меток в любой позиции сети не может превысить некоторого значения K;
• безопасность — частный случай ограниченности, K=1;
• сохраняемость — постоянство загрузки ресурсов, постоянна. Где N_i — число маркеров в i-той позиции, A_i — весовой коэффициент;
• достижимость — возможность перехода сети из одного заданного состояния (характеризуемого распределением меток) в другое;
• живость — возможность срабатывания любого перехода при функционировании моделируемого объекта.

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

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

Как и в системах массового обслуживания, в сетях Петри вво­дятся объекты двух типов: динамические, которые изображаются метками (маркерами) внутри позиций, и статические, которым соответствуют вершины сети Петри.

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

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

Правила срабатывания переходов (рис. 2.8) конкретизируют следующим образом: переход срабатывает, если для каждой из его входных позиций выполняется условие N_i> К_i, где N_i - число маркеров в i-й входной позиции, K_i - число дуг, идущих от i-й пози­ции к переходу; при срабатывании перехода число маркеров в i-й входной позиции уменьшается на К_i, а в j-й выходной позиции уве­личивается на М_j, где М_j - число дуг, связывающих переход с j-й позицией.

На рис. 19.2. показан пример распределения маркеров по позициям перед срабатыванием, эту маркировку записывают в виде (2, 2, 3, 1) или (2231). После срабатывания перехода маркировка принимает вид (1,0,1,4).

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

 

Рис. 19.2. Фрагмент сети Петри Рис. 19.3. Конфликтная ситуация

 

Если задержки являются случайными величинами, то сеть на­зывают стохастической. В стохастических сетях возможно вве­дение вероятностей срабатывания возбужденных переходов. Так, на рис. 2.9 представлен фрагмент сети Петри, иллюстрирующий конфликтную ситуацию - маркер в позиции p может запустить либо переход t ₁,либо переход t₂. В стохастической сети предусматрива­ется вероятностный выбор срабатывающего перехода в таких си­туациях.

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

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

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

Введенные понятия поясним на следующих простых примерах.

Пример 1. Требуется описать с помощью сети Петри функционирование системы из предприятий A, В и С. Предприятия А и В поставляют узлы Х1 и X2 соответственно, а на предприя­тии С происходит сборка, в каждый сборочный узел входит один узел X1 и два узла X2. На рис. 2.10 предприятиям А, В и С соответствуют переходы t₁, t₂ и t₃.

 

 

 

Рис. 19.4 Сеть Петри для примера 1

 

Срабатывание перехода t₃ происходит только в том слу­чае, если, во-первых, в позиции p_l имеется метка, а в позиции р₂ - не менее двух меток, что
означает поступление от пред-приятии А и В соответствующих комплектующих, и, во-вторых, имеется метка в позиции p₄, что означает, что предприятие С закончило сборку предыдущего изделия и готово приступить к сборке следующего. Пока очередное изделие не будет собрано, метки в p₄ не будет, следовательно, запросы, пришедшие во входные позиции р₁ и р₂, вынуждены ожидать срабатывания перехода t₄. Переходам t₁, t₂ и t₃ поставлены в соответствие процедуры вычисления задержек срабатывания. Задержки в первых двух переходах равны интервалам времени между появлениями готовых узлов, задержка в t₃ равна времени сборки изделия.

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

Рис. 2.11. Сеть Петри для примера 2

 

 

В нашем примере значение M в позиции р₂ соответствует числу имеющихся в системе блоков. Переходы отображают следующие события: t₁ - отказ блока, t₂- поиск неисправного блока, t₃ - его за­мена, t₄ - окончание ремонта.

Очевидно, что при непустой позиции р_г переход t₁ срабатывает, но с задержкой, равной вычисленному случайному значению мо­делируемого отрезка времени между отказами. После выхода маркера из t₁ он попадает через р ₁ в t₂, если имеется метка в пози­ции р₆, это означает, что обслуживающая систему бригада специа­листов свободна и может приступить к поиску возникшей неисп­равности. В переходе t₂ метка задерживается на время, равное случайному значению длительности поиска неисправности. Далее маркер оказывается в р₃ и если имеется запасной блок (маркер в р₄), то запускается переход t₃, из которого маркеры выйдут в р₂ , р₅ и р₆ через отрезок времени, требуемый для замены блока. После этого в t₄ имитируется восстановление неисправного блока.

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

 

19.5. Марковские случайные процессы

 

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

Марковский процесс — дискретный или непрерывный случайный процесс X (t), который можно полностью задать с помощью двух величин:

· вероятности P (x, t) того, что случайная величина x (t) в момент времени t равна x, и

· вероятности P (x ₂, t ₂| x ₁, t ₁) того, что если x при t = t ₁ равен x ₁, то при t = t ₂ он равен x ₂.

Вторая из этих величин называется вероятностью перехода из состояния x ₁ при t = t ₁ в состояние x ₂ при t = t ₂.

Цепями Маркова называют дискретные по времени и значению Марковские

процессы.

Пример 1

Предположим, что речь идет о последовательных бросаниях монеты при игре "в орлянку "; монета бросается в условные моменты времени t = 0, 1,... и на каждом шаге игрок может выиграть ±1 с одинаковой вероятностью 1/2, таким образом в момент t его суммарный выигрыш есть случайная величина ξ(t) с возможными значениями j = 0, ±1,... При условии, что ξ(t) = k, на следующем шаге выигрыш будет уже равен ξ(t+1) = k ± 1, принимая указанные знчения j = k ± 1 c одинаковой вероятностью 1/2. Условно можно сказать, что здесь с соответствующей вероятностью происходит переход из состояния ξ(t) = k в состояние ξ(t+1) = k ± 1.

 

19.5.1. Формулы и определения Марковских цепей

 

Обобщая этот пример, можно представить себе "систему" со счетным числом возможных "фазовых" состояний, которая с течением дискретного времени t = 0, 1,... случайно переходит из состояния в состояние.

Пусть ξ(t) есть ее положение в момент t в результате цепочки случайных переходов ξ(0) - ξ(1) -... - ξ(t) -...... (1)

Формально обозначим все возможные состояния целыми i = 0, ±1,... Предположим, что при известном состоянии ξ(t) = k на следующем шаге система переходит в состояние ξ(t+1) = j с условной вероятностью

p_kj = P(ξ(t+1) = j|ξ(t) = k)... (2)

независимо от ее поведения в прошлом, точнее, независимо от цепочки переходов (1) до момента t:

P(ξ(t+1) = j|ξ(0) = i,..., ξ(t) = k) = P(ξ(t+1) = j|ξ(t) = k) при всех t, k, j... (3) - марковское свойство.

Такую вероятностную схему называют однородной цепью Маркова со счетным числом состояний - ее однородность состоит в том, что определенные в (2) переходные вероятности p_kj, ∑_j p_kj = 1, k = 0, ±1,..., не зависят от времени, т.е.

P(ξ(t+1) = j|ξ(t) = k) = P_ij - матрица вероятностей перехода за один шаг не зависит от n. Ясно, что P_ij - квадратная матрица с неотрицатель-ными элементами и единичными суммами по строкам. Такая матрица (конечная или бесконечная) называется стохастической матрицей. Любая стохастическая матрица может служить матрицей переходных вероятностей.

Практический пример 1.

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

1) после осуществления доставки в А следующая доставка в 30 случаях осуществляется в А, в 30 случаях - в В и в 40 случаях - в С;

2) после осуществления доставки в В следующая доставка в 40 случаях осуществляется в А, в 40 случаях - в В и в 20 случаях - в С;

3) после осуществления доставки в С следующая доставка в 50 случаях осуществляется в А, в 30 случаях - в В и в 20 случаях - в С.

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

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

Например, р₁₂ = 0.4 - это вероятность того, что после доставки в район В следующая доставка будет производиться в районе А. Допустим, что каждая доставка с последующим перемещением в следующий район занимает 15 минут. Тогда, в соответствии со статистическими данными, через 15 минут 30% из курьеров, находившихся в А, будут в А, 30% будут в В и 40% - в С. Так как в следующий момент времени каждый из курьеров обязательно будет в одном из округов, то сумма по столбцам равна 1. И поскольку мы имеем дело с вероятностями, каждый элемент матрицы 0<р_ij<1. Наиболее важным обстоятельством, которое позволяет интерпретировать данную модель как цепь Маркова, является то, что местонахождение курьера в момент времени t+1 зависит только от местонахождения в момент времени t.

Теперь зададим простой вопрос: если курьер стартует из С, какова вероятность того, что осуществив две доставки, он будет в В, т.е. как можно достичь В в 2 шага? Итак, существует несколько путей з С в В за 2 шага:

1) сначала из С в С и потом из С в В;

2) С-->B и B-->B;

3) С-->A и A-->B.

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

P = P(CA)*P(AB) + P(CB)*P(BB) + P(CC)*P(CB)

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

P = 0.5*0.3 + 0.3*0.4 + 0.2*0.3 = 0.33

Полученный результат говорит о том, что если курьер начал работу из С, то в 33 случаях из 100 он будет в В через две доставки. Ясно, что вычисления просты, но если Вам необходимо определить вероятность через 5 или 15 доставок - это может занять довольно много времени.

Рассмотрим более простой способ вычисления подобных вероятностей. Для того, чтобы получить вероятности перехода из различных состояний за 2 шага, возведем матрицу P в квадрат:

Тогда элемент (2, 3) - это вероятность перехода из С в В за 2 шага, которая была получена выше другим способом. Заметим, что элементы в матрице P² также находятся в пределах от 0 до 1, и сумма по столбцам равна 1.

Т.о. если Вам необходимо определить вероятности перехода из С в В за 3 шага:

1 способ. p(CA)*P(AB) + p(CB)*P(BB) + p(CC)*P(CB) = 0.37*0.3 + 0.33*0.4 + 0.3*0.3 = 0.333, где p(CA) - вероятность перехода из С в А за 2 шага (т.е. это элемент (1, 3) матрицы P²).

2 способ. Вычислить матрицу P³:

Матрица переходных вероятностей в 7 степени будет выглядеть следующим образом:

Легко заметить, что элементы каждой строки стремятся к некоторым числам. Это говорит о том, что после достаточно большого количества доставок уж не имеет значение в каком округе курьер начал работу. Т.о. в конце недели приблизительно 38,9% будут в А, 33,3% будут в В и 27,8% будут в С. Подобная сходимость гарантировано имеет место, если все элементы матрицы переходных вероятностей принадлежат интервалу (0, 1).

Пример 2. Автомобильное страхование и Система Бонус-Малус (СБМ)

 

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

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

Система Бонус-Малус (СБМ)

Из всего сказанного выше следует, что оптимальным алгоритмом для расчета прогноза аварийности является исследование "послужного списка" каждого водителя, его предыдущей аварийности. Поэтому, в 1950-х годах была выдвинута идея об апостериорной корректировке, которая проводилась бы в зависимости от истории страховых случаев каждого страхователя. Такая система, называемая либо расчетом ставок страховой премии с учетом индивидуальной практики, либо системой со скидками за ненаступление страхового случая, либо системой бонус-малус (сбм), штрафует страхователей, ответственных за одну или более ДТП, надбавками к страховой премии, - это называется малусом - и поощряет страхователей, не совершивших ни одного страхового случая, уменьшением их страховой премии, или бонусом.

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

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

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

Определение системы бонус-малус

По определению, компания использует СБМ, если

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

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

Такая система определяется тремя элементами:

1. Премиальной шкалой b=(b₁....b_n)

2. Начальным классом C_i0

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

Эти правила можно ввести в виде преобразований T_k таких, что T_k(i)=j, если полис переходит из класса C_i в класс C_j, при условии, что зарегистрировано k страховых случаев. Преобразование T_k можно представить в виде матрицы

Tk=(t_ij(k)),

где t_ij(k)=1, если T_k(i)=j и

t_ij(k)=0 в противном случае.

Вероятность перехода из класса С_i в класс C_j для страхователя характеризуется некоторым параметром L, например, частотой страховых случаев и имеет вид

Здесь P_k(L) есть вероятность того, что водитель с частотой L повинен в k страховых случаях в течение года. Очевидно, что P_ij(L) не меньше нуля и что

Матрица

является переходной матрицей для цепи Маркова.

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

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

 

19.6. Теория массового обслуживания

 

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

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

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

 

Методы анализа систем массового обслуживания

 

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

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

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

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

Для простейшего потока частота поступлений требований в сис­тему подчиняется закону Пуассона, т.е. вероятность поступления за время t ровно к требований задается формулой:

Простейший поток обладает тремя основными свойствами:

1) ординарностью,

2) стационарностью и

3) отсутствием после­действия.

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

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

Отсутствие последействия означает, что число требований, по­ступивших в систему до момента t, не определяет того, сколько требований поступит в систему за промежуток времени от t до t + Dt

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

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

т.е. вероятность того, что время обслуживания не превзойдет неко­торой величины t, определяется формулой (5.2), где µ — параметр экспоненциального закона распределения времени обслуживания требований в системе, т.е. величина, обратная среднему времени обслуживания

Системы массового обслуживания классифицируются:

1. В зависимости от условий ожидания начала обслуживания:

· СМО с потерями (отказами)

· СМО с ожиданием

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

В СМО с ожиданием требование, застав все обслуживающие ка­налы занятыми, становится в очередь и ожидает, пока освободится ^[ один из обслуживающих каналов.

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

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

2. По числу каналов обслуживания СМО делятся на:

• одноканальные;

• многоканальные.

3. По месту нахождения источника тре­бований СМО подразделяются на:

• разомкнутые, когда источник требования находится вне сис­темы;

замкнутые, когда источник находится в самой системе.

 

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

 

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

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

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

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

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

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

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

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

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

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

1. Вероятность того, что все обслуживающие каналы свободны,

(5.14)

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

 

3. Вероятность того, что в системе находится к требований, ко­гда число этих требований больше числа обслуживающих каналов,

(5.16)

4. Вероятность того, что все обслуживающие каналы заняты,

(5.17)

5. Вероятность отказа

(5.18)

6. Средняя длина очереди

7. Среднее число свободных от обслуживания каналов

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

Требуется определить характеристики работы фирмы.

Решение. Данная система относится к типу СМО с ожида­нием и ограниченной длиной очереди. Найдем параметры системы, приняв за единицу времени один час:

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

Вероятность того, что в се машины заняты, определяется по формуле (5.17) и составляет

 

 

Тогда вероятность отказа в принятии заказа на перевозку, рассчитываемая по формуле (5.18) будет равна

 

, а средняя длина очереди в соответствии с формулой (5.19) составит

 

 

Тогда вероятность отказа в принятии заказа на перевозку, рас­считываемая по формуле (5.18), будет равна

а средняя длина очереди в соответствии с формулой (5.19) составит

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

 

Задание 1. Фирма занимается доставкой грузов по заказам и имеет пять машин, которые работают круглосуточно. Поток заказов является простейшим, и в среднем за час поступает одна заявка. Время перевозки грузов подчиняется экспоненциальному закону распределения, и в среднем перевозка одного груза занимает один час. При количестве заказов на перевозки, равном 8, фирма прекращает прием заявок до тех пор, пока очередь не уменьшится.

Требуется определить характеристики работы фирмы.

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

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

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

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

Приведем последовательность расчетов характеристик замкну­тых СМО с ожиданием и необходимые формулы.

 

1. Параметр α=α/µ. - показатель загрузки системы, т.е. мате­матическое ожидание числа требований, поступающих в систему за время, равное средней длительности обслуживания

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

(5.21)

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

(5.22)

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

Величину Р₀ можно получить также путем подстановки в равенство значений Р₁ P_2,. --, Р_т, в которые P_о входитсомножителем. Подставляя их, получаем следующее уравнение для опреде­ления Р₀

откуда

(5.23)

5. Среднее число требований, ожидающих начала обслуживания (средняя длина очереди),

или

(5.24)

6. Коэффициент простоя в очереди обслуживаемого требования (объекта)

(5.25)

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

или

(5.26)

8. Среднее число свободных обслуживающих каналов

(5.27)

9. Коэффициент простоя обслуживающего канала

(5.28)

Рассмотрим примеры расчетов характеристик замкнутых СМО в задаче организации труда.

Пример 3. Рабочий обслуживает группу автоматов, состоя­щую из трех станков. Поток поступающих требований на обслужи­вание станков пуассоновский с параметром λ = 2 ст./ч. Обслужива­ние одного станка занимает у рабочего в среднем 12 минут, а время обслуживания подчинено экспоненциальному закону.

Тогда 1/ µ = = 0,2 ч/ст., т.е. µ = 5 ст./ч, а α = λ/ µ = 0,4.

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

Решение. Обслуживающим каналом здесь является рабо­чий. Так как станки обслуживает один рабочий, то п = 1. Общее число требований не может превзойти числа станков, т.е. т = 3.

Система может находиться в четырех различных состоя­ниях:

1) все станки работают;

2) один станок простаивает и обслуживается рабочим, а два ра­ботают;

3) два станка простаивают, один обслуживается, один ждет об­служивания;

4) три станка простаивают, из них один обслуживается, а два ждут очереди.

Для ответа на поставленные вопросы можно воспользоваться формулами

(5.21) и (5.22):

Сведем вычисления в таблицу (табл. 5.1).

 

 

 

В табл. 5.1 первой вычисляется третья графа, т.е. отношения Рк/Ро

при к = 0, 1, 2, 3. Затем, суммируя величины по графе и учитывая, что

получаем:

 

откуда P₀=0,2822.

Умножая величины третьей графы на Р₀, полу­чаем четвертую графу. Величина Р_о = 0,2822, равная вероятности того, что все автоматы работают, может быть истолкована как веро­ятность того, что рабочий будет свободен. Получается, что в рас­сматриваемом случае рабочий будет свободен более 1/4 всего рабо­чего времени. Однако это не означает, что «очередь» станков, ожи­дающих обслуживания, всегда будет отсутствовать. Математическое ожидание числа автоматов, стоящих в очереди,

, т.к. n=1

Суммируя пятую графу получим математическое ожидание =0,4875. Следовательно, в среднем 0,49 станкова будет простаивать в ожидании, пока освободится рабочий.

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

 

т.е. в среднем 1,2 станка не будут выдавать продукцию. Коэффици­ент простоя станка

т.е. каждый станок простаивает примерно 0,16 часть рабочего вре­мени в ожидании, пока рабочий освободится. Коэффициент простоя рабочего в данном случае совпадает с Р_о, так как n = 1, поэтому

 

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

Требуется определить среднее количество автоматов, простаи­вающих в ожидании ремонта, степень загрузки ремонтников и ко­эффициент простоя оборудования. (по Федосееву)