КУРСОВОЙПРОЕКТ
ПОВЫСШЕЙ МАТЕМАТИКЕ
НАТЕМУ
МАТЕМАТИЧЕСКОЕМОДЕЛИРОВАНИЕ И ОПТИМИЗАЦИЯ СИСТЕМЫ МАССОВОГО ОБСЛУЖИВАНИЯ
СОДЕРЖАНИЕ
ВВЕДЕНИЕ
ПОСТАНОВКА ЗАДАЧИ
РЕШЕНИЕ ЗАДАЧИ
ЗАКЛЮЧЕНИЕ
СПИСОК ЛИТЕРАТУРЫ
ВВЕДЕНИЕ
Теория массовогообслуживания –область прикладной математики, занимающаяся анализом процессов в системахпроизводства, обслуживания, управления, в которых однородные событияповторяются многократно, например, на предприятиях бытового обслуживания; всистемах приема, переработки и передачи информации; автоматических линияхпроизводства и др. [1]
Предметом теории массового обслуживанияявляется установление зависимостей между характером потока заявок, числомканалов обслуживан6ия, производительностью отдельного канала и эффективнымобслуживанием с целью нахождения наилучших путей управления этими процессами. [1]
Задача теориимассового обслуживания – установить зависимость результирующих показателей работы системымассового обслуживания (вероятности того, что заявка будет обслужена;математического ожидания числа обслуженных заявок и т.д.), от входныхпоказателей (количества каналов в системе, параметров входящего потока заявок ит.д.). Результирующими показателями или интересующими нас характеристиками СМОявляются – показатели эффективности СМО, которые описывают, способна ли даннаясистема справляться с потоком заявок. [1]
Системы массовогообслуживания могут быть одноканальными или многоканальными.
Заметим, что за последниегоды область применения математических методов теории массового обслуживаниянепрерывно расширяется и все больше выходит за пределы задач, связанных с«обслуживающими организациями» в буквальном смысле слова. Каксвоеобразные системы массового обслуживания могут рассматриваться: электронныецифровые вычислительные машины; системы сбора и обработки информации;автоматизированные производственные цехи, поточные линии; транспортные системы;системы противовоздушной обороны и т. д. [2]
Задачи массовогообслуживания условно делят на задачи анализа и задачи синтеза — оптимизациисистем массового обслуживания. Первые предполагают определение основныхпараметров функционирования системы массового обслуживания при неизменных,наперед заданных исходных характеристиках: структура системы, дисциплинаобслуживания, потоки требований и законы распределения времени на ихобслуживание. Вторые направлены на поиск оптимальных параметров системмассового обслуживания. [4]
Оптимизационныемодели широко используются в экономике и технике. Среди них задачи подборасбалансированного рациона питания, оптимизации ассортимента продукции,транспортная задача и пр., и пр.
Задача оптимизации –задача выбора из множества возможных вариантов наилучшего, оптимального. Оптимизация– от латинского слова «оптимус» — наилучший – поиск наилучшего, поискнаилучшего проектного изделия. [4]
Каждая задача оптимизацииобязательно должна иметь три компоненты:
неизвестные (что ищем, то есть, план);
ограничение на неизвестные (область поиска);
целевая функция (цель, для которой ищем экстремум).
Математическая модель, такоторая определена с помощью математических формализмов. Математическая модельне является точной, а является идеализацией.
Определение параметровсостояния — задача моделирования. Определение переменных проектирования –задачи проектирования или задачи оптимизации. [3]
Выявление основныхособенностей, взаимосвязей и количественных закономерностей
Функционирование любойсистемы массового обслуживания можно представить через все возможные состоянияее и интенсивность перехода из одного состояния в другое. Основными параметрамифункционирования СМО являются вероятности ее состояния, то есть возможностиналичия n требований в системе — Рn.
Важным параметромфункционирования СМО является также среднее число требований, находящихся всистеме Nsyst, то есть в очереди на обслуживание, а также средняядлина очереди Noch. Исходными параметрами, характеризующими системумассового обслуживания, являются: число каналов обслуживания — n; число требований — m; интенсивностьпоступления одного требования на обслуживание — λ, то есть числопоступлений требований в единицу времени; интенсивность обслуживания требований- μ.
Многоканальная СМОс отказами
Рассмотрим n-канальнуюСМО с отказами. Будем нумеровать состояния системы по числу занятых каналов(или, что в данном случае то же, по числу заявок, связанных с системой).Состояния будут:
S0 — все каналы свободны, S1 — занят ровно один канал,остальные свободны,
Sk — занятыровно k каналов, остальные свободны, Sn — заняты все n каналов.
Граф состояний СМОпредставлен на рис.1. Разместим граф, т.е. проставим у стрелок интенсивностисоответствующих потоков событий. По стрелкам слева на право систему переводитодин и тот же поток — поток заявок с интенсивностью l.
/>
Рис.1
Если система находиться всостоянии Sk (занято k каналов) и пришла новая заявка, системапереходит (перескакивает) в состояние Sk+1
Определим интенсивностипотоков событий, переводящих систему по стрелкам справа налево.
Пусть система находитьсяв состоянии S1 (занят один канал). Тогда, как только закончитьсяобслуживание заявки, занимающей этот канал, система перейдет в S0;значит, поток событий, переводящий систему по стрелке S1 ® S0,Имеет интенсивность m. Очевидно, если обслуживанием занято два канала, а неодин, поток обслуживаний, переводящий систему по стрелке S2 ® S1,будет вдвое интенсивнее (2m); если занято k каналов — в k раз интенсивнее (km).Проставим соответствующие интенсивности у стрелок, ведущих справа налево.
Из рис.1 видно, чтопроцесс, протекающий в СМО, представляет собой частный случай процесса гибели иразмножения.
Пользуясь общимиправилами, можно составить уравнения Колмогорова для вероятностей состояний:
/> (1)
Уравнения (1) называютсяуравнениями Эрланга. Естественными начальными условиями для их решенияявляются:
p0(0)=1; p1(0)=p2(0)=...=pn(0)=0(в начальный момент система свободна).
Интегрирование системыуравнений (1) в аналитическом виде довольно сложно; на практике такие системыдифференциальных уравнений обычно решаются численно, на ЭВМ. Такое решение даетнам все вероятности состояний p0(t), p1(t),..., pn(t)как функции времени.
Естественно, нас большевсего будут интересовать предельные вероятности состояний p0, p1,..., pk ,..., pn, характеризующие установившийся режимработы СМО (при t ® ¥). Для нахождения предельных вероятностейвоспользуемся уже готовым решением задачи, полученным для схемы гибели иразмножения. Согласно этому решению,
/> (2)
В этих формулахинтенсивность потока заявок l и интенсивность потока обслуживаний (для одногоканала) m не фигурируют по отдельности, а входят только своим отношением l /m.Обозначим это отношение l /m=r и будем называть величину r «приведеннойинтенсивностью» потока заявок. Физический смысл ее таков: величина rпредставляет собой среднее число заявок, приходящих в СМО за среднее времяобслуживания одной заявки.
С учетом этогообозначения, формулы (2) примут вид:
/> (3)
Формулы (3) называютсяформулами Эрланга. Они выражают предельные вероятности всех состояний системы взависимости от параметров l, m и n (l — интенсивность потока заявок, m — интенсивность обслуживания, n — число каналов СМО).
Зная все вероятностисостояний p0, p1 ,..., pk ,..., pn,можно найти характеристики эффективности СМО: относительную пропускнуюспособность q, абсолютную пропускную способность А и вероятность отказа Pотк.
Действительно, заявкаполучает отказ, если приходит в момент, когда все n каналов заняты. Вероятностьэтого равна
/> (4)
Вероятность того, чтозаявка будет принята к обслуживанию (она же относительная пропускнаяспособность q) дополняет Pотк до единицы:
/> (5)
Абсолютная пропускнаяспособность:
/> (6)
Одной из важныххарактеристик СМО с отказами является среднее число занятых каналов (в данномслучае оно совпадает со средним числом заявок, находящихся в системе).Обозначим это среднее число k-.
Величину k- можновычислить непосредственно через вероятности p0, p1,...,pn по формуле:
/> (7)
как математическоеожидание дискретной случайной величины, принимающей значения 0,1,...,n свероятностями p0, p1,..., pn. однакозначительно проще выразить среднее число занятых каналов через абсолютнуюпропускную способность А, которую мы уже знаем. Действительно, А есть не чтоиное, как среднее число заявок, обслуживаемых в единицу времени; один занятыйканал обслуживает в среднем за единицу времени m заявок; среднее число занятыхканалов получится делением А на m:
/>
или, переходя кобозначению l/m = r,
/> (8)
[5], [6].
Цель данной работызаключается в разработке модели, имитирующей работу поста ГИБДД. Такая задачабыла поставлена для того, чтобы выявить эффективность работы системы обслуживанияпоста ГИБДД для дальнейшей ее оптимизации.
В данной работепредлагается к использованию одна из методик, которая предполагает разделениепроцесса моделирования на две части. Первая часть –обеспечивает нахождениепараметров работы исходной задачи. Вторая часть – производится оптимизацияопределенных параметров при неизменных остальных параметров в таблицах MSExcel. Строятся графики функций. Производится их анализ и делаются выводы.
Рассмотрим подробнеематематическую модель работы поста ГИБДД как системы массового обслуживания.Для решения задачи было принято допущение, что очередь клиентов ограничена, и,следовательно, данная модель является СМО с ограниченной очередью, где n –количество каналов обслуживания. Также принимаем допущение, что все потокисобытий (случайные события) в системе являются Марковскими. Напомним, чтослучайный процесс, протекающий в системе, называется Марковским, если длялюбого момента времени t0 вероятностные характеристики процесса вбудущем зависят только от его состояния в данный момент t0 и независят от того, когда и как система пришла в это состояние.
Поток нарушителей всистему поступают с интенсивностью />. Тогда />
Вероятность отказа />.
Относительная пропускнаяспособность />.
Абсолютная пропускнаяспособность />.
Среднее число заявок, связанныхс системой />.
Средняя длина очереди />.
Количество, ожидающих вочереди />.
Время в очереди />.
Время в системе />.
В результате планируетсяполучить наиболее приближенную к реальности модель работы поста ГИБДД.Практическая значимость данной работы очевидна: модель позволяет путемэкспериментов выявить наиболее оптимальное распределение ресурсов для повышенияэффективности его работы. Также можно предположить применение данной модели нареальном объекте.
ПОСТАНОВКА ЗАДАЧИ
На шоссепроверяет скорость пост ГИБДД. На посту в течении дня работает 5 инспекторов.Рабочий день инспектора равен 10 часам. Режим работы – раз в трое суток.Затраты на одного инспектора равны 35000рублей в месяц (зарплата, налоги,спецобмундирование и др.). Инспектор оформляет протокол примерно за 12 минут. Втечение часа скоростной режим нарушают в среднем 35 водителей. Инспекторыостанавливают машину, если ожидают оформления не более четырех машин. Среднийразмер штрафа равен 250 рублям.
Определитьпараметры работы системы. Найти процент оштрафованных нарушителей. Каковосреднее время, которое тратит водитель в ожидании оформления протокола?Сколько, в среднем, машин ожидает оформления? Какова средняя сумма от штрафовза месяц? Каковы месячные затраты на пост ДПС? Определить «прибыль» поста замесяц. (Ознакомительная задача).
Определитьоптимальное (с точки зрения прибыли) число инспекторов на посту при сохраненииостальных условий задачи.
Имеетсявозможность арендовать оборудование, позволяющее ускорить процесс оформленияпротокола. Стоимость аренды оборудования для одного инспектора линейно зависитот его эффективности и изображения на графике. Максимально возможная скорость –10 протоколов в час. Определить оптимальные затраты на оборудование принеизменных остальных условиях задачи (число инспекторов равно пяти) и при числеинспекторов, полученных в п. 2. Определить параметры работы системы при этихзатратах.
/>
Рис. 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и R1. При /> авт./час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, время в очереди W0, время в системе Wc, среднюю сумму штрафа за месяц Сштр, затраты наодин канал 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. lib.vvsu.ru/books/Bakalavr01/page0220.asp
6. masteroid.ru/content/view/909/42/