9.2. Аналитические модели оптимальных решений задач

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

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

(9.1)

где Р(m,a) – вероятность появления события при заданном значении параметра а, равна m раз; а = λt – математическое ожидание (среднее число событий за данный отрезок времени); m – случайная величина, число событий за данный отрезок времени; t – отрезок времени, за который рассматривается поведение случайной величины; е = 2,71… - основание натурального логарифма.

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

, (9.2)

где z – сумма случайных величин.

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

В практической работе задача оптимизации процессов в обслуживаемой системе включает следующие этапы:

1. Наблюдение за данными в эксплуатации автомобилей и их группировка;

2. Выбор закона распределения для аппроксимации данных (закон Пуассона, Эрланга и другие);

3. Оценка конкретных параметров закона и построение аналитической модели рассматриваемого процесса;

4. Получение оптимального решения по аналитической модели процесса.

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

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

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

f (t) = λ·e^{-λ t} , (9.3)

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

На рис. 9.4 приведено распределение затрат времени на ремонт автомобилей (замену двигателя) для автомобилей одного типа (обслуживающая система). Всего было зафиксировано время по 400 случаям ремонтов. Время ремонтов разбито на 7 разрядов по одному часу в каждом разряде. Можно видеть, что распределение затрат времени составляет: 128 случаев – 1,5-2,5 ч; 70 случаев - 2,5-3,5 ч … 23 случая – 6,5-7,5 ч, ….и так далее (см. рис. 9.4). Распределение времени, очевидно, соответствует показательному закону.

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

9.3. Примеры решений задач

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

Пример 9.1. На базу для разгрузки прибывают автомобили со скоропортящимися грузами. Прием и разгрузка грузов осуществляются в рабочие дни недели с 8.00 до 9.00 ч.

Требуется:

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

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

Исходные данные для решения

Были зарегистрированы N = 300 наблюдений за прибытием автомобилей с грузом на базу в период с 8.00 до 9.00 ч по рабочим дням.

Результаты сгруппированы в первой колонке табл. 9.1 в 9 разрядов по количеству прибывавших на базу автомобилей (0…8 единиц), во второй колонке- в поразрядные частоты m_i по числу случаев прибытия в таком количестве.

Можно видеть (табл. 9.1), что в 10 случаях автомобили в период с 8.00 до 9.00 ч вообще не прибывали на базу, в 46 случаях прибывал 1 автомобиль, в 72 случаях – 2 автомобиля, в 78 случаях - 3 автомобиля, 53 случаях – 4 автомобиля, 25 случаях – 5 автомобилей и так далее. Прибытия 8 автомобилей зафиксированы 2 раза.

Решение

Вычисляем частости попадания случайной величины (случаи прибытия автомобилей на базу) в разряды по формуле

и т. д.

Результаты заносим в колонку 3 табл. 9.1. Строим гистограмму распределения частостей (рис. 9.5). Рассматривая рис. 9.5, предполагаем, что прибытие автомобилей следует закону Пуассона.

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

автомобиля.

Находим статистическую дисперсию:

автомобилей.

Находим несмещенную оценку среднего квадратического отклонения:

автомобиля.

Вычисляем значения вероятностей P(m, a) при математическом ожидании a ≈ 2,9, используя данные приложения 1 (распределение вероятностей закона Пуассона) и приложение 2 (значения показательной функции), и заносим значения в колонку 4 табл. 9.1.

;

;

;

-------------------------------

.

На основе полученных данных строим выравнивающую кривую (рис. 9.5).

Вычисляем теоретические частоты попадания в разряды и заносим в колонку 5 табл. 9.1.

m_o = P₁ · N= 0,55·300 = 16,5;

m₁ = P₂ · N= 0,16·300 = 48;

……………………………..

m₈ = P₈ · N= 0,0077·300 = 2.

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

Вычисляем критерий xи – квадрат Пирсона:

.

Входим в таблицу распределения xи – квадрат Пирсона (см. приложение 3) при числе степеней свободы Ч=6:

P(х²; Ч) = Р(8,3; 6) = 0,25>0,1.

Следовательно, при уровне значимости 0,1 гипотеза о принадлежности экспериментальных данных закону Пуассона не отвергается.

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

< 3 . (9.4)

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

= 0,66 < 3.

Вычисляем доверительный интервал разброса среднего арифметического M(m)=2,884 при доверительной вероятности 90 %. При решении используется способ обратной интерполяции по таблице Лапласа. Получаем следующий результат:

,

где arqФ (90%) берется по таблице Лапласа (см. приложение 4).

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

2,884 – 0,94 < M(m) < 2,884+0,94;

1,9 < M(m) < 3,82 .

Заключение Установлено, что распределение частости прибытия автомобилей на базу разгрузки следует закону Пуассона с математическим ожиданием 2,9 автомобиля/ч. С доверительной вероятностью 90 % на базу прибывают в период с 8.00 до 9.00 не более четырех автомобилей. Следовательно, в случае установки на базе четырех разгрузочных постов девять из десяти автомобилей будут попадать сразу под разгрузку, а один из десяти будет становиться в очередь и ожидать начало разгрузки.

Пример 9.2. Выполняется анализ процесса разгрузки автомобилей из примера 9.1 со скоропортящимся грузом, прибывших на базу.

Требуется

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

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

Исходные данные для решения

Зафиксировано время N = 175 случаев разгрузки автомобилей. Результаты наблюдений, сгруппированные в 12 разрядов по 10 минут каждый, представлены в колонках 1-3 табл. 9.2. Число случаев разгрузки , попавшее в каждый разряд, представлено в колонке 4 табл. 9.2.

Решение

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

; ;

;……. =0,011.

Результаты заносим в колонку 5 табл. 9.2.

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

Вычисляем среднее арифметическое длительности времени разгрузки (математическое ожидание):

мин,

следовательно, имеют место μ = 2 разгрузки автомобилей/ч.

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

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

P_i (d_i < t_i < β_i) =

Логарифмируем выражение и получаем

ℓq m_i = ℓq N + ℓq μ - μt_i ℓq e + ℓq ∆t. (9.5)

Положим,

ℓq m_i = y; t_i = x_i; - μ ℓq e = а;

ℓq N + ℓq μ + ℓq ∆t = b.

Известно, что в логарифмических координатах уравнение (9.5) представляется в виде прямой линии

y = ax + b.

Для рассматриваемого примера

b = ℓq 175 + ℓq 0,0335 + ℓq 10 = 2,243 + 2,525 + 1 = 1,768.

Поэтому для середины первого интервала

ℓq m₁ = -0,0335·0,433·5 + 1,768 = 1,694.

Потенцируя по таблицам антилогарифмов, получаем m₁ = 50.

Для середины второго интервала t_2cр.

ℓq m₂ = -0,0335·0,433·15 + 1,768 = 1,55.

Потенцируя, получаем m₂ = 36.

Аналогичными вычислениями получаем теоретические частоты попадания случайной величины в остальные разряды: m₃ = 25; m₄ = 18; m₅ = 13 и так далее.

Полученные значения теоретических частот заносим в графу 6 табл. 9.2, на основании которых строим на рис. 9.6 теоретическую кривую показательного закона, выравнивающую опытную гистограмму.

Проверяем гипотезу о принадлежности экспериментальных данных показательному закону по критерию согласия Пирсона (при уровне значимости х=0,1). Для этого вычисляем критерий xи-квадрат Пирсона:

.

Входим в таблицу xи-квадрат Пирсона (приложение 3) при числе степеней свободы Ч = К – S = 12 – 2 = 10, при этом получаем

Р(х²; Ч) = Р(9,22; 10) = 0,342 > 0,1.

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

Проверяем также принятую гипотезу по критерию Романовского, согласно которому должно выполняться неравенство (9.4). Неравенство выполняется.

Вычисляем величину доверительного интервала разброса среднего арифметического (математического ожидания) времени разгрузки при доверительной вероятности 95 %. Полуинтервал разброса равен

мин,

где σ_(t) = = 29,97 – для показательного закона среднее квадратическое отклонение равно математическому ожиданию: arqФ (P_q = 95 %) = 1,96 – берется по таблице Лапласа (см. приложение 4).

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

29,97 – 16,5 < M_(m) <29,97 + 16,5;

13,5 мин. < M_(m) < 46,5 мин.

Это значит, что с вероятностью 95 % время разгрузки автомобилей будет не меньше 13,5 мин и не больше 46,5 мин.

Заключение

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

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

Из примера 9.2 следует, что время ожидания разгрузки для стоящего в очереди автомобиля с вероятностью 95 % не будет превышать 46,5 мин.

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

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

Например, транспортный процесс доставки груза включает четыре составляющих – погрузку, движение между пунктами, выгрузку и негруженый пробег к пункту следующей погрузки. Проверка показала отсутствие парной корреляции между рассматриваемыми составляющими транспортного процесса (имеет место случай, показанный на рис. 2.1,а). Для этого случая аналитическая вероятностная модель для расчета затрат времени Т₁ на доставку груза с доверительной вероятностью 90 % будет иметь вид

Т₁ = Т_п + Т_qв + Т_в + Т_х ± ∑ (∆t_п + ∆t_qв+ ∆t_в+ ∆t_х), (9.6)

где Т_п , Т_qв , Т_в , Т_х – соответственно среднее арифметическое (математическое ожидание) значение времени погрузки, движения между пунктами, выгрузки и порожнего пробега; ∆t_п, ∆t_qв, ∆t_в, ∆t_х – соответственно односторонние доверительные интервалы разброса среднего арифметического времени погрузки, движения между пунктами, выгрузки и негруженого пробега , вычисленные при доверительной вероятности 98 %.

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

При обнаружении сильных корреляционных связей между отдельными составляющими модель (9.6) не может использоваться. Например, обнаруживается тесная корреляционная связь между процессом погрузки и выгрузки (имеет место технологическая связь процессов). В этом варианте мы имеем случай, показанный на рис. 2.1,в. При этом следует рассматривать погрузку-выгрузку как единый процесс с отличными от других параметрами вероятностного закона распределения. Модель для доверительной вероятности 90 % будет иметь вид (9.7)

Т₂ = Т_пв + Т_qв + Т_х ± ∑ (∆t_пв + ∆t_qв+ ∆t_х), (9.7)

где Т_пв – среднее арифметическое процесса погрузки-выгрузки; ∆t_пв– односторонний доверительный интервал разброса среднего арифметического времени погрузки-выгрузки.

Вычисления составляющих для модели (9.7) необходимо проводить с доверительной вероятностью 96 %.

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

Полученную зависимость f_пв(t) следует анализировать на соответствие виду вероятностного закона; нахождению характеристик распределения, математического ожидания, доверительного интервала.

В общем случае общая зависимость f_пв(t), получаемая на базе процессов, подчиняющихся законам Пуассона, Эрланга и показательному, должна стремиться к нормальному закону распределения вероятности.

9.5. Статистический метод моделирования Монте-Карло

Если система массового обслуживания не является пуассоновской, ее расчет с помощью аналитических методов становится сложным. Искомое решение легче получить, используя метод статистических испытаний, – численный метод решения математических задач при помощи моделирования случайных процессов и событий, который получил название метода Монте-Карло. Этот метод разработан и введен в практику расчетов в 1944 г. в США. Широкое распространение этот метод получил только после появления быстродействующих ЭВМ.

В методе Монте-Карло особую роль играет моделирование случайных величин с заданными распределениями (время обслуживания, время ожидания и другие). Такое моделирование осуществляют путем преобразования одного или нескольких независимых значений случайного числа t, распределенного равномерно в интервале 0…1. Последовательности «выборочных» значений t получают на ЭВМ с помощью специальных алгоритмов. Такие числа называются псевдослучайными.

Для моделирования отдельно взятого случайного события с вероятностью Р достаточно одного равномерно распределенного на интервале 0…1 числа r. При попадании r в интервал О…Р считают, что событие (например, прибытие автомобиля) наступило, в противном случае – не наступило.

Вопросы для самоконтроля

1. Опишите общую модель системы массового обслуживания.

2. Сформулируйте понятия обслуживающей и обслуживаемой систем, приведите примеры систем.

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

4. Перечислите этапы работы по оптимизации процессов в обслуживаемой системе.

5. Перечислите этапы работы по оптимизации процессов в обслуживающей системе.