Математическое моделирование и оптимизация системы массового обслуживания
КУРСОВОЙ ПРОЕКТ
ПО ВЫСШЕЙ МАТЕМАТИКЕ
НА ТЕМУ
МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ И ОПТИМИЗАЦИЯ СИСТЕМЫ МАССОВОГО ОБСЛУЖИВАНИЯ
СОДЕРЖАНИЕ
ВВЕДЕНИЕ
ПОСТАНОВКА ЗАДАЧИ
РЕШЕНИЕ ЗАДАЧИ
ЗАКЛЮЧЕНИЕ
СПИСОК ЛИТЕРАТУРЫ
ВВЕДЕНИЕ
Теория массового обслуживания – область прикладной математики, занимающаяся анализом процессов в системах производства, обслуживания, управления, в которых однородные события повторяются многократно, например, на предприятиях бытового обслуживания; в системах приема, переработки и передачи информации; автоматических линиях производства и др. [1]
Предметом теории массового обслуживания является установление зависимостей между характером потока заявок, числом каналов обслуживан6ия, производительностью отдельного канала и эффективным обслуживанием с целью нахождения наилучших путей управления этими процессами. [1]
Задача теории массового обслуживания – установить зависимость результирующих показателей работы системы массового обслуживания (вероятности того, что заявка будет обслужена; математического ожидания числа обслуженных заявок и т.д.), от входных показателей (количества каналов в системе, параметров входящего потока заявок и т.д.). Результирующими показателями или интересующими нас характеристиками СМО являются – показатели эффективности СМО, которые описывают, способна ли данная система справляться с потоком заявок. [1]
Системы массового обслуживания могут быть одноканальными или многоканальными.
Заметим, что за последние годы область применения математических методов теории массового обслуживания непрерывно расширяется и все больше выходит за пределы задач, связанных с "обслуживающими организациями" в буквальном смысле слова. Как своеобразные системы массового обслуживания могут рассматриваться: электронные цифровые вычислительные машины; системы сбора и обработки информации; автоматизированные производственные цехи, поточные линии; транспортные системы; системы противовоздушной обороны и т. д. [2]
Задачи массового обслуживания условно делят на задачи анализа и задачи синтеза - оптимизации систем массового обслуживания. Первые предполагают определение основных параметров функционирования системы массового обслуживания при неизменных, наперед заданных исходных характеристиках: структура системы, дисциплина обслуживания, потоки требований и законы распределения времени на их обслуживание. Вторые направлены на поиск оптимальных параметров систем массового обслуживания. [4]
Оптимизационные модели широко используются в экономике и технике. Среди них задачи подбора сбалансированного рациона питания, оптимизации ассортимента продукции, транспортная задача и пр., и пр.
Задача оптимизации – задача выбора из множества возможных вариантов наилучшего, оптимального. Оптимизация – от латинского слова «оптимус» - наилучший – поиск наилучшего, поиск наилучшего проектного изделия. [4]
Каждая задача оптимизации обязательно должна иметь три компоненты:
неизвестные (что ищем, то есть, план);
ограничение на неизвестные (область поиска);
целевая функция (цель, для которой ищем экстремум).
Математическая модель, та которая определена с помощью математических формализмов. Математическая модель не является точной, а является идеализацией.
Определение параметров состояния - задача моделирования. Определение переменных проектирования – задачи проектирования или задачи оптимизации. [3]
Выявление основных особенностей, взаимосвязей и количественных закономерностей
Функционирование любой системы массового обслуживания можно представить через все возможные состояния ее и интенсивность перехода из одного состояния в другое. Основными параметрами функционирования СМО являются вероятности ее состояния, то есть возможности наличия n требований в системе - Р>n>.
Важным параметром функционирования СМО является также среднее число требований, находящихся в системе N>syst>, то есть в очереди на обслуживание, а также средняя длина очереди N>och>. Исходными параметрами, характеризующими систему массового обслуживания, являются: число каналов обслуживания - n; число требований - m; интенсивность поступления одного требования на обслуживание - λ, то есть число поступлений требований в единицу времени; интенсивность обслуживания требований - μ.
Многоканальная СМО с отказами
Рассмотрим n-канальную СМО с
отказами. Будем нумеровать состояния
системы по числу занятых каналов (или,
что в данном случае то же, по числу
заявок, связанных с системой). Состояния
будут:
S>0> - все каналы свободны,
S>1> - занят ровно один канал, остальные
свободны,
S>k> - заняты ровно k каналов, остальные свободны, S>n> - заняты все n каналов.
Граф состояний СМО представлен на рис.1. Разместим граф, т.е. проставим у стрелок интенсивности соответствующих потоков событий. По стрелкам слева на право систему переводит один и тот же поток - поток заявок с интенсивностью l.
Рис.1
Если система находиться в состоянии S>k> (занято k каналов) и пришла новая заявка, система переходит (перескакивает) в состояние S>k+1>
Определим интенсивности потоков событий, переводящих систему по стрелкам справа налево.
Пусть система находиться в состоянии S>1> (занят один канал). Тогда, как только закончиться обслуживание заявки, занимающей этот канал, система перейдет в S>0>; значит, поток событий, переводящий систему по стрелке S>1> ® S>0>, Имеет интенсивность m. Очевидно, если обслуживанием занято два канала, а не один, поток обслуживаний, переводящий систему по стрелке S>2> ® S>1>, будет вдвое интенсивнее (2m); если занято k каналов - в k раз интенсивнее (km). Проставим соответствующие интенсивности у стрелок, ведущих справа налево.
Из рис.1 видно, что процесс, протекающий в СМО, представляет собой частный случай процесса гибели и размножения.
Пользуясь общими правилами, можно составить уравнения Колмогорова для вероятностей состояний:
|
|
(1) |
Уравнения (1) называются уравнениями Эрланга. Естественными начальными условиями для их решения являются:
p>0>(0)=1; p>1>(0)=p>2>(0)=...=p>n>(0)=0 (в начальный момент система свободна).
Интегрирование системы уравнений (1) в аналитическом виде довольно сложно; на практике такие системы дифференциальных уравнений обычно решаются численно, на ЭВМ. Такое решение дает нам все вероятности состояний p>0>(t), p>1>(t),..., p>n>(t) как функции времени.
Естественно, нас больше всего будут интересовать предельные вероятности состояний p>0> , p>1> ,..., p>k> ,..., p>n>, характеризующие установившийся режим работы СМО (при t ® ¥). Для нахождения предельных вероятностей воспользуемся уже готовым решением задачи, полученным для схемы гибели и размножения. Согласно этому решению,
|
|
(2) |
В этих формулах интенсивность потока заявок l и интенсивность потока обслуживаний (для одного канала) m не фигурируют по отдельности, а входят только своим отношением l /m. Обозначим это отношение l /m=r и будем называть величину r "приведенной интенсивностью" потока заявок. Физический смысл ее таков: величина r представляет собой среднее число заявок, приходящих в СМО за среднее время обслуживания одной заявки.
С учетом этого обозначения, формулы (2) примут вид:
|
|
(3) |
Формулы (3) называются формулами Эрланга. Они выражают предельные вероятности всех состояний системы в зависимости от параметров l, m и n (l - интенсивность потока заявок, m - интенсивность обслуживания, n - число каналов СМО).
Зная все вероятности состояний p>0> , p>1> ,..., p>k> ,..., p>n>, можно найти характеристики эффективности СМО: относительную пропускную способность q, абсолютную пропускную способность А и вероятность отказа P>отк>.
Действительно, заявка получает отказ, если приходит в момент, когда все n каналов заняты. Вероятность этого равна
|
|
(4) |
Вероятность того, что заявка будет принята к обслуживанию (она же относительная пропускная способность q) дополняет P>отк> до единицы:
|
|
(5) |
Абсолютная пропускная способность:
|
|
(6) |
Одной из важных характеристик СМО с отказами является среднее число занятых каналов (в данном случае оно совпадает со средним числом заявок, находящихся в системе). Обозначим это среднее число k-.
Величину k- можно вычислить непосредственно через вероятности p>0> , p>1>,..., p>n> по формуле:
|
|
(7) |
как математическое ожидание дискретной случайной величины, принимающей значения 0,1,...,n с вероятностями p>0> , p>1>,..., p>n>. однако значительно проще выразить среднее число занятых каналов через абсолютную пропускную способность А, которую мы уже знаем. Действительно, А есть не что иное, как среднее число заявок, обслуживаемых в единицу времени; один занятый канал обслуживает в среднем за единицу времени m заявок; среднее число занятых каналов получится делением А на m:
|
|
или, переходя к обозначению l/m = r,
|
|
(8) |
Цель данной работы заключается в разработке модели, имитирующей работу поста ГИБДД. Такая задача была поставлена для того, чтобы выявить эффективность работы системы обслуживания поста ГИБДД для дальнейшей ее оптимизации.
В данной работе предлагается к использованию одна из методик, которая предполагает разделение процесса моделирования на две части. Первая часть –обеспечивает нахождение параметров работы исходной задачи. Вторая часть – производится оптимизация определенных параметров при неизменных остальных параметров в таблицах MS Excel. Строятся графики функций. Производится их анализ и делаются выводы.
Рассмотрим подробнее математическую модель работы поста ГИБДД как системы массового обслуживания. Для решения задачи было принято допущение, что очередь клиентов ограничена, и, следовательно, данная модель является СМО с ограниченной очередью, где n – количество каналов обслуживания. Также принимаем допущение, что все потоки событий (случайные события) в системе являются Марковскими. Напомним, что случайный процесс, протекающий в системе, называется Марковским, если для любого момента времени t0 вероятностные характеристики процесса в будущем зависят только от его состояния в данный момент t0 и не зависят от того, когда и как система пришла в это состояние.
Поток нарушителей в систему
поступают с интенсивностью >
>.
Тогда >
>
Вероятность отказа >
>.
Относительная пропускная
способность >
>.
Абсолютная пропускная способность
>
>.
Среднее число заявок, связанных
с системой >
>.
Средняя длина очереди >
>.
Количество, ожидающих в очереди
>
>.
Время в очереди >
>.
Время в системе >
>.
В результате планируется получить наиболее приближенную к реальности модель работы поста ГИБДД. Практическая значимость данной работы очевидна: модель позволяет путем экспериментов выявить наиболее оптимальное распределение ресурсов для повышения эффективности его работы. Также можно предположить применение данной модели на реальном объекте.
ПОСТАНОВКА ЗАДАЧИ
На шоссе проверяет скорость пост ГИБДД. На посту в течении дня работает 5 инспекторов. Рабочий день инспектора равен 10 часам. Режим работы – раз в трое суток. Затраты на одного инспектора равны 35000рублей в месяц (зарплата, налоги, спецобмундирование и др.). Инспектор оформляет протокол примерно за 12 минут. В течение часа скоростной режим нарушают в среднем 35 водителей. Инспекторы останавливают машину, если ожидают оформления не более четырех машин. Средний размер штрафа равен 250 рублям.
Определить параметры работы системы. Найти процент оштрафованных нарушителей. Каково среднее время, которое тратит водитель в ожидании оформления протокола? Сколько, в среднем, машин ожидает оформления? Какова средняя сумма от штрафов за месяц? Каковы месячные затраты на пост ДПС? Определить «прибыль» поста за месяц. (Ознакомительная задача).
Определить оптимальное (с точки зрения прибыли) число инспекторов на посту при сохранении остальных условий задачи.
Имеется возможность арендовать оборудование, позволяющее ускорить процесс оформления протокола. Стоимость аренды оборудования для одного инспектора линейно зависит от его эффективности и изображения на графике. Максимально возможная скорость – 10 протоколов в час. Определить оптимальные затраты на оборудование при неизменных остальных условиях задачи (число инспекторов равно пяти) и при числе инспекторов, полученных в п. 2. Определить параметры работы системы при этих затратах.
0100090000037400000002001c00000000000400000003010800050000000b0200000000050000000c02d9024d05040000002e0118001c000000fb02ceff0000000000009001000000cc0440001254696d6573204e657720526f6d616e0000000000000000000000000000000000040000002d0100000400000002010100050000000902000000020d000000320a2d00000001000400000000004c05d802201316001c000000fb021000070000000000bc02000000cc0102022253797374656d00000000000000000000180000000100000098d22100e3040000040000002d010100030000000000
Рис. 2.
Провести оптимизацию по двум параметрам: числу инспекторов и затратам на ускоряющее оборудование. Определить параметры работы системы при паре оптимальных параметров. Сравнить с оптимизацией по каждому отдельному параметру.
РЕШЕНИЕ ЗАДАЧИ
Формализуем задачу.
Данную задачу можно
отнести к задачам СМО с ограниченной
очередью. Максимальная длина очереди
равна m=5.
Интенсивность потока требований (в
качестве которого выступает поток
нарушителей) равна >
>водителей
в час. Исходно имеется пять каналов
обслуживания (пять инспекторов находятся
на посту единовременно): n=5.
Среднее время обслуживания одним каналом
(среднее время, которое тратит инспектор
на один автомобиль) равно >
>,
тогда >
>авт./мин
>
>
авт./час.
Найдем параметры работы исходной задачи.
>
>
>
>
>
>
>
>
30,4 % нарушителей не будет оштрафовано.
>
>
Процент оштрафованных нарушителей равен 69,6 %.
>
>
В среднем 24,35 автомобилей будет оштрафовано в час.
>
>
Почти все инспекторы (4,8 из 5)заняты.
Найдем среднюю длину очереди:
>
>
>
>
В среднем ожидает оформления 3 машины.
>
>
Время в очереди и системе:
>
>часа
= 7,2 мин.
>
>
Таким образом, среднее время, которое тратит водитель в ожидании оформления протокола, равно 7,2 мин.
Найдем среднюю сумму штрафов за
месяц >
>.
Так как >
>авт./час.,
сумма штрафа в среднем равна 250 руб., в
месяце 30 дней по 10 рабочих часов, то:
>
>тыс.руб.
Так как затраты на одного инспектора равны f=35000 руб./мес., а инспекторов по трижды по 5 человек, то месячные затраты на пост ДПС равны:
>
>руб.
= 525 тыс. руб.
«Прибыль» поста складывается из суммы штрафов («дохода») минус затраты на инспекторов («расхода»). Таким образом, месячная «прибыль» поста равна:
>
>
тыс.руб.
Определить оптимальное число инспекторов можно двумя способами. Во-первых, вручную вычислить все интересующие величины. Во-вторых, все величины можно вычислить в пакете MS Excel.
Составим таблицу 1. В строках 1-5 записаны исходные данные задачи. В столбце А с 10-й по 24-ую строку введены числа инспекторов.
Таблица 1.
В последнем столбце получено значение прибыли поста за месяц. Построим график этой величины в зависимости от числа инспекторов (рис.3). Тип диаграммы – точечная.
Рис. 3.
Из графика и по значениям в таблице 1 видно, что максимальная прибыль достигается при значении n=8 и равна 1635431 руб. в месяц.
Вывод: При прочих постоянных параметрах, выгоднее нанять 24 инспектора (по 8 инспекторов одновременно).
Определим оптимальные капиталовложения на ускорение оформления протоколов при пяти инспекторах. Требуется формализовать задачу.
Как видно из графика (рис.2),
стоимость аренды оборудования для
одного инспектора (будем ее обозначать
R)
линейно зависит от скорости оформления
протокола (интенсивности >
>),
т.е.
>
>.
Найдем значения параметров R>0>>
>и R>1>.
При >
>
авт./час R=0.
При >
>
авт./час R=2000
руб./день. Тогда:
>
>
Откуда получаем:
>
>
Т.о.
>
>.
При этом >
>
Оказывается удобнее выразить
затраты на аренду через >
>,
потому что все формулы содержат именно
этот параметр. Так как >
>
авт./час, то
>
>
и следовательно
>
>.
(1)
При этом
>
>
Месячная «прибыль» поста в этом случае будет вычисляться по формуле:
>
>
(2)
При n=5 получаем:
>
>(руб./мес.).
(3)
Подставляя (1) в (3) получаем:
>
>
(4) (тыс. руб./мес.) при
>
>
Определив, при каком >
>
достигается максимум функции прибыли
>
>,
мы определим по формуле (1) оптимальные
затраты на аренду оборудования.
Распишем функцию >
>:
>
>
Однако, анализировать такие громоздкие формулы неудобно. Анализ проведем в MS Excel. В табл. 2 показаны проведенные расчеты.
В строках 1-4 приведены данные задачи.
В столбце А с 7 по 42 строки
протабулирован параметр >
>
Таблица 2.
Построим график прибыли (рис.4):
Рис.
4.
Уточним оптимальное значение
параметра >
>,
дополнительно разбив промежуток >
>
на более мелкие интервалы. График функции
на этом промежутке приведен на рис.5.
Рис.
5.
Фрагмент уточненной таблицы приведен в таблице 3.
Таблица 3.
Из графиков и по таблице 3 с
высокой степенью точности можем принять
в качестве оптимального значения >
>,
а оптимальная прибыль равна примерно
1764 тысячи 17 рублей в месяц.
Определим, при каких затратах на аренду мы получим такую прибыль. Из (1):
>
>
руб./день.
Это позволит оформлять протоколы с интенсивностью
>
>
маш./час.
Вывод: если на посту работает одновременно 5 инспекторов, то наиболее выгодно вложить 1581 рубль в день в аренду техники для каждого инспектора. Тогда прибыль за месяц будет оптимальной и равной примерно 1764 тыс. 17 рублей.
Необходимо провести оптимизацию
по двум параметрам n
и >
>.
Имеем функцию >
>
от двух переменных. Будем использовать
формулу >
>.
(1)
Определив, при каких >
>
и n
достигается максимум функции прибыли
>
>,
мы определим по формуле (1) оптимальные
затраты на аренду оборудования.
Составим таблицы 4 – 5. В таблице
4 - n=3,
n=4,
n=5,n=6,
в таблице 5 - n=7,
n=8,
n=9,
n=10
. Рассмотрим промежуток
>
>
Таблица 4.
Таблица 5.
Рис. 6.
Из значений таблицы и графика, оптимальное число инспекторов равно 4. Построим для n=4 уточненный график (рис.7).
Рис. 7.
Из значений таблицы можно
определить, что оптимальная интенсивность
нагрузки равна >
>.
Тогда оптимальные затраты на аренду
равны:
>
>
руб./день.
Интенсивность работы инспектора равна:
>
>
маш./час.
Вывод: имея возможность менять число инспекторов на посту и арендовать ускоряющую технику, нужно организовать работу так, чтобы на посту одновременно находилось 4 инспектора, и для каждого из них арендовать техники на 2000 рублей в день. Это позволит получить прибыль 1779337 рублей в месяц.
ЗАКЛЮЧЕНИЕ
В данном курсовом проекте представлена тема "Математическое моделирование и оптимизация системы массового обслуживания". Системы массового обслуживания имеют огромное практическое применение в наше время, что показано в рассмотренном примере.
Целью данного курсового проекта было определение
- параметров работы системы;
- оптимального числа инспекторов на посту при сохранении остальных условий задачи;
- оптимальных затрат на оборудование при неизменных остальных условиях задачи
- параметров работы системы при паре оптимальных параметров.
Данная задача является СМО с
ограниченной очередью или СМО с ожиданием.
В данной работе в первой части решения
задачи проводится ее анализ, т.е.
определяются основные параметры
функционирования СМО при неизменных,
наперед заданных исходных характеристиках.
Исходные характеристики – это
интенсивность потока требований >
>,
максимальная длина очереди m,
количество каналов
обслуживания n,
среднее время обслуживания
одним каналом >
>,
интенсивность обслуживания требований
>
>.
В ходе решения первой части задачи мы
определили такие основные параметры
функционирования СМО: интенсивность
нагрузки>>,
предельные вероятности >
>
и вероятность отказа >
>,
относительную пропускную способность
Q,
абсолютную пропускную
способность >
>,
среднее число заявок, связанных с
системой >
>,
среднюю длину очереди D,
время в очереди W>0>,
время в системе W>c>,
среднюю сумму штрафа за месяц С>штр>,
затраты на один канал f,
затраты на пост в месяц F,
прибыль поста Z.
При решении задачи использовались
формулы Эрланга. Во второй, третьей и
четвертой частях решения задачи
проводился синтез – оптимизация СМО.
Здесь действия направлены на поиски
оптимальных параметров СМО. Во второй
и третьей частях определяются оптимальное
число инспекторов на посту и затраты
на оборудование соответственно, при
неизменных остальных условиях задачи.
Рассматриваются функции >
>и
>
>,
строятся их графики. В четвертой части
решения задачи проводится оптимизация
по двум параметрам, т.е рассматривается
функция >
>.
Модель СМО реализована с помощью программы MS Excel. Все расчеты выполнялись при помощи данной программы, что упростило процесс решения задач оптимизации. В процессе нескольких реализаций работы СМО были получены результаты функционирования системы. На основе полученных данных были построены графики, позволяющие провести исследование работы СМО. С помощью графиков проведен анализ полученных данных и сделаны выводы о работе системы. Из графика (рис.3) и по значениям в таблице 1 видно, что максимальная прибыль достигается при значении n=8 и равна 1635431 руб. в месяц. При прочих постоянных параметрах, выгоднее нанять 24 инспектора (по 8 инспекторов одновременно). Из графиков (рис.4, 5) и по значениям таблиц 2 и 3 видно, что если на посту работает одновременно 5 инспекторов, то наиболее выгодно вложить 1581 рубль в день в аренду техники для каждого инспектора. Тогда прибыль за месяц будет оптимальной и равной примерно 1764 тыс. 17 рублей. Из графиков (рис.6, 7) и таблиц 4,5 видно, что имея возможность менять число инспекторов на посту и арендовать ускоряющую технику, нужно организовать работу так, чтобы на посту одновременно находилось 4 инспектора, и для каждого из них арендовать техники на 2000 рублей в день. Это позволит получить прибыль 1779337 рублей в месяц.
Итак, создание имитационной модели системы массового обслуживания позволяет получить информацию, характеризующую приспособленность рассматриваемой системы для выполнения поставленных перед ней задач. Анализ численных значений критериев позволяет сделать выводы относительно реальной эффективности системы и выработать рекомендации по ее повышению.
СПИСОК ЛИТЕРАТУРЫ
Основная литература:
1. Клейнрок Л. Теория массового обслуживания. М.: Машиностроение, 1979.
2. Матвеев В.Ф., Ушаков В.Г. Системы массового обслуживания. М.: Изд-во МГУ, 1984.
3. Советов Б.А., Яковлев С.А. Моделирование систем, М: Высшая школа, 1985.
Периодические издания:
4. Иголкин В.Н. Об оптимизации одной системы массового обслуживания // Вопросы механики и процессов управления. Вып.15. СПб.: Изд-во СПбГУ, 1992.
Интернет-ресурсы:
5. http://lib.vvsu.ru/books/Bakalavr01/page0220.asp
6. http://masteroid.ru/content/view/909/42/