Дипломная работа по Программирование на тему Разработка программы моделирования, предназначенной для использования в образовательных учреждениях( на примере системы массового обслуживания предмета "математическое моделирование")

В большинстве областей финансов, экономики, производства и быта немаловажную роль получают системы массо¬вого обслуживания (СМО), тобишь такие системы, которые рассматривают, с одной стороны, возникающие массовые требования (заявки) на выполнение (обслуживание) (получения каких-либо услуг или какого-либо процесса), и с другой стороны, процессы, направленные на удовлетворение этих требований.
В качестве якрих примеров СМО в сфере финансов и экономики можно будет привести системы, представляющие из себя: страховые организа¬ции, банки разнообразных типов, ау-диторские службы, налоговые инспекции, разннобразные системы связи (в том числе, традиционно для этой области, те¬лефонные станции), автозаправочные станции, товарные станции (погрузочно-разгрузочные участки), различные предприятия и компании, работающие в сфере обслуживания (предприятия массового питания, магазины, справочные бюро, билетные кассы, парикмахерские, пункты обмена валют, больницы, ремонтные мастерские).
Такие сис¬темы как вычислительные сети, транспортные системы, системы сбора информации, хранения и обра¬ботки информационных потоков, автоматизирован¬ные участки производственных комплексов, поточные конвеерные линии также могут быть рассмотрены как своеобразные СМО.
В сфере торговых взаимоотношений выполняется достаточно большое количество операций в процессе перемещения массы товаров из производственного участка в участок сбыта и потребления. Одними из этих операций являются: пере¬возка товаров, погрузка и выгрузка, упаковка, хранение, фасовка, выкладка, продажа и т. д.
Для деятельности в сфере торговли характерны массовые поступления денег, товаров, массовое обслу¬живание клиентов и покупателей и т. д., помимо этого, также выполнение сопутсвующих операций, которым присущ случайный характер. Эти и многие другие факторы создают не¬равномерность в работе торговых компаний и предприятий производства, порождает перегрузки, простои и недогрузки. Достаточно много расходуется на очереди, такие например как, у простых покупателей в точках сбыта, водителей, перевозящих товары, на товарных базах, ожидающих, как своей, так и чужой разгрузки или погрузки.
В следствии чего возникают задачи анализа процессов работы, например торгового предприятия, тор¬гового отдела или секции, для выявления просчётов, недостатков, резервов, оценки их деятельности и принятия в конеч¬ном счёте мер, имеющих направленность на увеличение их эффективности. Акромя, возникают задачи оптимизационного характера, по созданию и внедре¬нию ещё более приемлимых и экономичных способов и методов выполнения операций как узких рамках секций и отделов, так и в масштабах торговых предприятий, овощных баз, управлений торговли и т.п. Исходя из этого, в организа¬ции торговой деятельности методы и подходы теории массового обслуживания более доступно позволяют определить необходимое количество точек тороговли одного выбранного профиля, количество торгового персонала, интервалы завоза товаров и многие другие параметры.
Ещё характерными примерами систем массового обслуживания смогут послужить склады или базы сбытовых и снабженческих организаций, на их уровне поставновка задачи к теории массового обслуживания зачастую сводится лишь к тому, чтобы определить оптимальные соотношения между числом через определённые интервалы времени поступающих на склад запросов (требований на обслуживание) к числу устройств обслуживания, при котором общие расходы на обслуживание и потенциальные убытки от простоя техники и транспорта были бы наименьшими. Теория массового обслуживания вновь также сможет найти применение уже при расчёте площадей складских помещений, но только при этом площадь складского помещения рассматривается в качестве обслуживающего устройства, а транспортные средства, прибывшие на выгрузк или загрузку – как требование.
СМО в основном всегда состоит из следующих элементов: источник требований, поток входящих требований, очередь заявок, обрабатывающее устройство (канал обслуживания), поток вышедшых требований (заявок после обслуживания).
Каждая СМО предназначается для обработки (обслуживания) некоторого случайного потока заявок (обращений), поступающих в произвольные моменты времени на вход системы(зачастую – нерегулярно). Обслуживание заявок, к тому же, также не длится постоянное и заранее определённое время, а произвольное время, которое зависит от множества (порою неизвестных) других случайных величин. После обработки каждой заявки канал считается освободившеимся и готовым принять к обслуживанию следующую заявку.
К неравномерной загруженности приводит поток заявок случайного характера и непредсказуемые затраты времени на их обслуживание: в некоторые временные промежутки на входе могут скапливаться необработанные обращения, что обуславливает состояние перегрузки, в некоторые дру¬гие же временные промежутки, при освободившихся каналах, на входе системы не будет обращений, что обуславливает её недогрузку, т.е. каналы обслуживания простаивают впустую. Заявки, скапливающиеся на входе сиситемы, либо «ставятся» в очередь, либо по какой-либо причине покидают СМО необслуженными из-за дальнейшей невозможности пребывания в очереди.
Каждая СМО содержит в своей структуре некоторое число устройств обработки заявок, которые обычно называют каналами обслуживания. В этом качестве каналов могут выступать различные приборы, линии связи, работники, выполняющие те или иные процедуры (операторы, кассиры, продавцы), автомобили и прочие тому подобные вещи.
Каждая СМО исключительно в зависимости от собственных параметров: какого-либо характера потока обращений, числа обслуживающих устройств и их производи¬тельности, и также от организационных правил работы наделена определенной функциональной эффективностью, или же просто – пропускной способностью, котрая позволяет ей более или менее достаточно успешно справляться со входящим потоком обращений.
Поток заявок случайного характера и длительности об¬служивания каждого обращения порождает в СМО свой процесс такого же случайного характера. Поскольку моменты и промежутки времени поступления обращений, продолжительность операций обработки, про¬стоя в очереди и сама длина очереди — взаимосвязанные случайные величины, то необходимые характеристики параметров состояния всей системы массового обслуживания имеют ярко выраженный вероятностный характер. В следвии чего, для нахождения решения задач согласно теории массового обслуживания, этот самый случайный процесс необходимо изучить, то есть разработать, реализовать и проанализировать его адекватную, работоспособную математическую модель.
Математическое моделирование и изучение функциональных процессов СМО серьезно упрощается, если происходящие в ней случайные процессы является марковскими. Для того, чтобы случайный процесс стал бы являться марковским, необходимо и достаточно добится того, чтобы все потоки событий, из-за воз¬действия которых система производит переходы из одного состояния в другое состояние, были простейшими (пуассоновскими).
Простейшие потоки обладают тремя главными особенностями: стационарности, ординарности и отсутствия последействий обслуживания заявок.
Ординарность потока подразумевает практическую невозмож¬ность единовременного поступления более одного обращения. К ¬примеру, достаточно малой считается вероятность того, что в магазине с самообслуживанием единовременно станут неработоспособными сразу несколько единиц контрольно кассовой техники.
Стационарным признаётся поток, для которого справедливо, что математиче¬ское ожидание количества обращений, поступающих в систему за дискретную единицу времени (обычно обзначают как λ), не изменяется с течением времени. Следовательно, таким образом можно считать что, вероятность того, что в систему поступит определённое количество обращений в течение определённого временного интервала, зависит от величины этого интервала и никак не зависит от начала момента его отсчёта по оси времени.
Под отсутствием последействий принято считать, что число обращений, поступивших в систему до определённого момента, никак не определяет того, сколько обращений может поступить в систему за какой-либо промежуток времени время. К примеру, если вдруг в кассовом аппарате в текущий момент произо¬шло окончание кассовой ленты, и была вставлена новая лента, то это никак не влияет на то, что лента окочится снова на данном кассовом аппарате в следующий момент и тем более никак не влияет на вероятность окончания ленты на других аппаратах.
Частота поступления обращений в систему для простейшего потока подчиняется закону Пуассона.
Классфикация систем массового обслуживания выполняется по разным признакам.
По количеству каналов обработки СМО подразделяются на одноканальные и многоканальные.
Например, к одноканальным СМО в торговом деле можно отнести почти любой приходящий на ум вариант местного обслуживания заявки, например, выполняемое действие одним продавцом, экономистом, товароведом, торговым автоматом.
В зависимости от взаимного размещения обслуживающих каналов системы можно разделить на СМО с последовательными и с параллельными каналами. В системе с параллельными каналами входящий поток обращений на обслуживание является для всех каналов общим, и поэтому обращения в очереди мо¬гут обрабатываться любым свободным каналом. Оче¬редь на обработку для таких систем можно расценивать как общую.
Для многоканальной СМО с последовательным размещением каналов отдельно каждый канал также может рассматриваться в свою очередь как отдельная СМО с одним каналом, либо фаза обработки. Очевидно, выходной поток обработанных обращений одной СМО тут же приходится потоком входящих обращений для последующей СМО.

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

В разомкнутых системах выходной поток обработанных обращений не связан ни коем образом с входным потоком обращений на обработку.
В замкнутых системах обработанные заявки после некоторой, возможно неопределённой, временной задержки вновь поступают на вход системы, и тогда получается, что источник обращений входит в состав самой системы. В замкнутой системе циркулирует всегда одно и то же определённое конечное число возможных обращений, для примера, посуда в столовой — через раздачу, место приёма пищи и мойку. Пока потенциальное обращение циркулирует и ещё не преобразовалась на входе счистемы в обращение на обратку, считается, что это обращение находится в линиях задержки.
Привычные типовые варианты СМО также подразделяются и дисциплиной очереди установленной в них, обычно, которая зависит от привелегий в обслу¬живании, то есть приоритета отбора обращений на обслужива¬ние. Который, в свою очередь, может быть следующим: первый пришёл — первым обработан, последним пришёл — первым обработан, со случайным отбором и др. Далее об этом будет описано чуть подробнее. Для систем с ожиданием и приоритетному обслуживанию возможны и допустимы следующие виды: относительный приоритет, например для начальника торговли на подведомственных ему участках; абсолютный приоритет, например для владельца фирмы или его представителей; особые правила приоритета, когда порядок обработки за¬явок оговорён в соответствующих документах. Также выделяют и другие типы существующих систем: с групповым поступлением заявок, с разной производительностью каналов, со потоком заявок смешанного типа.
Совокупности СМО различных типов, объединенных параллельно и последовательно, формируют структуры более сложных систем: отделы магазина, секции, торговые организации и т.п. Подобное сложное моделирование позволяет более чётко выявить существенные пересечения в тор¬говле, успешно применить модели и методы из теории массового обслуживания непосредственно для их формализованного описания, оценить текущую эффективность обработки и разра¬ботать рекомендации для оптимизации протекающих процесов.
Достаточно грамотная, экономико-математически правильная постановка вопросов задачи в сущесчтвенной степени предопределяет эффективность полученных рекомендаций по совершенствованию процессов массового обслуживания в сфере услуг, в торговле и т.д. Следовательно, в связи с этим необходимо проводить наблюдениия за обслуживанием, точно выявлять существенные связи проблем, чётко формулировать цели и определять необходимые экономические критерии оценки корректности работы СМО. Как вариант, в качестве общего, внутрисистемного критерия могут определяться затраты, где с одной стороны, СМО выступает как системы обслуживавния, а с другой — обращений, которые, возможно, могут иметь достаточно разную базу. В качестве прмиера, для продукции, поступающей в торго¬вую сеть, данный критерий тесно связан со скоростью и временем их обраще¬ния, и отношением объёма и скорости поступления в банк денежных средств.
Далее рассмотрим моделирование СМО в сфере тоговли. Оно непосредственно должно брать в расчёт анализ затрат временного характера в процессе обработки обращений, например, покупателей или продавцов в процедурах продажи-покупки товаров. Далее при помощи соответствующих приёмов методов необходимо выстроить модели свя¬зей с другими необходимыми показателями СМО в сфере торговли торговли.
Например, особенностью харктеристики для системы массвого обслуживания с отказами является то, что показатель времени ожидания обращений в очереди равно нулю. Поскольку в таком случае существование очередей по факту невозможно, то длина очереди также равна нулю и, как следствие, вероятность её образования тоже равна нулю. По числу обращений определяются состояние системы и режим её работы: при количестве обращений равным нулю — простой каналов обработки, при количестве обращений больше одного и меньше максимально возможного числа для данной системы — обслуживание заявок, при количестве обращений больше максимально возможного числа для данной системы — обслуживание и отказ. Основными показателями таких систем являются: вероятность обработки, вероятность отказа в обработке, средняя длительность простоя канала, среднее количество соответственно свободных и занятых каналов обработки, среднее вре¬мя обработки, абсолютная для системы пропускная способность.
Характерные показатели для СМО с неограниченным ожиданием – вероятность обработки обращения равно ста процентам (единице), поскольку не ограничены время ожидания в очереди начала обслуживания и длина самой очереди. Для подобных систем возможны следующие рабочие режимы: при при количестве обращений равным нулю наблюдается простой каналов обработки, при количестве обращений больше одного и меньше максимально возможного числа для данной системы — обслуживание и при количестве обращений больше максимально возможного числа для данной системы — обслуживание и очередь ожидания. Показателями эффективности для подобных СМО являются: среднее количество обращений в системе, среднее количество обращений в очереди, среднее время нахождения обращения в системе, абсолютная для системы пропускная способность.
В системе с ожиданием и с лимтом на длину очереди, если число обращений в системе равно нулю, то наблюдается простой обрабатывающих каналов. При количестве обращений больше одного и меньше максимально возможного числа для данной системы — обработка, при количестве обращений больше максимально возможного числа для данной системы за данную единицу времени, но находящегося по количсетву в пределах длинны очереди — обработка и очередь и при количестве обращений больше максимально возможного числа для данной системы за данную единицу времени и также превосходящих лимит очереди — обработка, очередь и отказ в обработке. Показателями эффективности подобных систем являются вероятность обработки, вероятность отказа в обработке, среднее число обращений в очереди, среднее число обращений в системе, среднее время нахождения обращения в си¬стеме, абсолютная для системы пропускная способность.
Во время процесса постановки задачи предельно необходимо раскрыть внутренние взаимо-связи рабочих показателей эффективности системы, которые обычно можно разделить на пару основных групп по базовой своей принадлежности, и которые в следсвии, образуют две выделяемые совокупности.
Итак, первую группу показателей можно связать с особенностями обращения СМО в сфере торговли, котрые определяются расходами на содержание системы, количеством занятых обработкой каналов, интенсивностью обработки, степенью загрузки устройств осбуживания, эффективностью использования каналов, пропускной способностью системы и т.п.
Вторую группу показателей определяется особенностями соб¬ственно обращений, поступающих на обработку, которые формируют входящий поток и взаимосвязаны с такими показателями эффективности как время ожидания обработки, длина очереди, вероятность отказа в обработке, время пребывания обращения в системе и др.
Системным обобщенным показателем, характеризующим эффективность, включающим возможности и требования обеих групп, вполне может быть крите¬рий эффективности экономического плана, включающий как особенности издержек первой группы, так и второй группы, которые, как логично предположить, будут иметь наиболее оптимальное значение при достижении минимума общих затрат.
Рабочие издержки содержат в себе затраты, связанные с эксплуатацией СМО и простоем каналов обработки, а издержки обращений включают потери, напрямую связанные с покиданием очереди необслуженных обращений и с как таковым нахождением в очереди.
В зависимости от поставленных задач управляемыми показателями могут такие показатели, как: количество каналов обработки, организация кана¬лов обработки (последовательно, параллельно, смешанным образом), приоритет в обслуживании заявок, дисциплина очереди, взаимопомощь между обслуживающими каналами и др. Часть таких показателей в задачах может фигурировать в качестве неуправляемых, в таком случае они обычно даются как исходные вводные данные. Также следует заметить, что в качестве основного критерия эффек¬тивности в целевой функции может стать товарооборот торговой компании или же, например, обычная рентабельность.
Тогда становится очевидным, что оптимальные показатели управляемых значений СМО находятся обычно уже при их предельных значениях и необходимо определённым соответствующим образом преобразовать целевую функцию.
После предварительного построения целевой функции также необходимо определить и условия решения поставленной задачи, то есть установить начальные значения показателей, найти ограничения, выделить показатели недоступные для управления и подобрать или построить совокупность моделей взаимосвязей всех показателей для текущего анализируемого типа системы, чтобы, в конечном счёте, найти наиболее оптимальные количественные значения управляемых показателей. К примеру, количество тех же продавцов, кассиров, фасовщиков, грузчиков, объёмы и площади складских помещений, размещение в них товаров и в торговом зале и др.
Каждая система массового обслуживания (СМО) предназначена для выполнения (обслуживания) некоторого имеющегося потока требований (заявок), поступление которых формирует входящий поток системы по большей части не является регулярным, а происходит в произвольные моменты времени. Выполнение обслуживания заявок точно также происходит не за постоянное и заранее известное время, а полностью случайное, зависещее от многих, порою никому неизвестных, причин. Затем, после окончания обслуживания текущей заявки происходит освобождение канала, и он переходит в состояние готовности приёма последующей заявки. Произвольный характер входящего потока заявок и времени, затрачиваемого на их обслуживание, приводит к неравномерной загруженности СМО. На входе СМО в некоторые временные интервалы заявки могут скапливаться в значительные очереди, что приводит СМО в состояние перегрузки, в другие временые интервалы каналы (устройства обслуживания) освобождаются, и на входе СМО отсутствуют заявки, данная ситуация приводит уже к недогрузке СМО, проще говоря, к простаиванию устройств обслуживания. В итоге – заявки, представляющие собой входной поток СМО, формируют очередь, либо по той или иной причине невозможности дальнейшего нахождения в очереди покидают СМО без обслуживания.
Ниже приведена обшая схема для СМО (рисунок 1.1)


Рисунок 1.1 Общая схема систем массового обслуживания
В качестве основных признаков систем массового обслуживания принято выделять следующие элементы:
блок обслуживания;
поток заявок;
очередь заявок ожидания обслуживания.
Блок обслуживания предназначен для выполнения последованности действий согласно требованиям заявок, поступающих в систему.
Второй составляющей систем массового обслуживания определяют поток поступающих заявок, которые, как было упомянуто ранее, случайным образом поступают в сиситему. В обыкновении предполагают, что входной поток находится в подчинени некоторому определяемому вероятностному закону длительности временных интервалов между парой последовательно поступающих заявок, причем этот закон распределения принято считать неизменяющимся в течении некоторого временного отрезка достаточной продолжительности. В свою очерердь, источник заявок ничем не ограничевается.
Третьей составляющей принято считать дисциплину очереди. Это характеристика, описывающая то, в каком порядоке происходит обслуживание поступающих на вход системы заявок. В виду того, что пропускнуая способность обслуживающего блока, в большинстве случаев, является ограниченной, а поступление заявок нерегулярно, то периодически возникает очередь ожидающих обслуживания заявок, но в другие моменты система обслуживания может простаивать в ожидании заявок.
Различают следующие виды дисциплин обслуживания:
без приоритетов;
с приоритетами.
Безприоритетные дисциплины обслуживания характеризуются наличием преимущественного права на обслуживание у каждой заявки, пришедшей на вход в систему, а выборка заявок из очереди происходит согласно какому-либо определённому правилу.
Этопу принципу соответсвует дисциплина обслуживания FIFO (First In – First Out, что значит: первым пришёл – первым ушёл: выборка заявок из очереди производится по прямому порядку). Также данная дисциплина обслуживания широко известна под названием круговой.
В качестве примера данного кругового обслуживания может подойти привычная очередь в банковскую кассу или контрольному пункту проезда через мост.
Также является бесприоритетной и дисциплина обслуживания LIFO (Last In – First Out, что значит: последним пришёл – первым ушёл). Соответствуя этой дисциплине обслуживания устроена так называемая стековая, или магазинная память.
Примером для данного вида обслуживания может служить процесс заряжания патронов в обойму и их последующее извлечение.
В случае дисциплин обслуживания с приоритетами заявки выставляются по рангу в зависимости от их приоритета. Необходимо существование минимум двух уровней приоритета.
Ввыделяют приоритеты следующих основных типов:
относительный приоритет;
абсолютный приоритет;
динамический приоритет.
При абсолютном приоритете обслуживание более приоритетной заявки начинается сразу же после её поступления, а обслуживание текущей заявки прерывается, и она возвращается в очередь.
В качестве примера можно использовать междугородний телефонный звонок, разъединяющий текущий звонок прямо во время разговора.
При относительном приоритете продолжается обслуживание текущей заявки и только после её завершения производится обслуживание более приоритетной на данный момент поступившей заявки.
В качестве примера можно признать распределение пищи «вне очереди» в столовой предприятия, для работников.
При динамическом приоритете у заявок может изменяться их текущий приоритет во время её нахождения в очереди системы массового обслуживания.
Также существуют и другие, более сложные дисциплины процесса обслуживания.
Случайность является основным свойством, присущим процессам массового обслуживания. При этом всегда имеются пара взаимодействующих между собой сторон: обслуживающая и обслуживаемая. При случайном поведении, как минимум, одной из сторон придаёт случайный характер процессу обслуживания в целом. Два типа случайных событий являются источниками случайности взаимодействия двух этих сторон.
Первый тип – момент возникновение заявки (требования) в обслуживании. Причиной случайности этого события зачастую является потребностью в обслуживании массового характера (все и сразу).
Второй тип – момент окончания обаботки очередной заявки. В причинах случайности данного события кроются как случайная величина продолжительности самого обслуживания, так и случайность момента начала обслуживания очередной заявки.
Приведённые выше случайные события лежат в основе формирования в СМО двух потоков системы: входной поток – заявки на обслуживание и выходной поток – обслуженные заявки.
Результатом взаимодействия вышеупомянутых потоков случайных событий является количество находящихся в СМО на данный момент времени заявок. Этот числовой показатель принято называть текущеим состоянием системы.
В зависимости от производительности каналов обслуживания и их числа, собственных параметров и специфики потока заявок, не исключая дисциплины и правил организации работ, любая СМО обладает определённой пропускной способностью (эффективностью функционирования), способствующей ей достаточно успешно справляться со сформирвавшем потоком очереди заявок.
Теория массового обслуживания (ТМО) – отдельная специальная область прикладной математики, всецело занимающаяся анализированием процессов, происходящих внутри систем массового обслуживания. В нынешнее время авматизации её примение для решения прикладных задач выглядит всё более выгодно
Предметом изучения в теории массового обслуживания являются системы массового обслуживания.
Целью теории массового обслуживания является разработка рекомендаций по наиболее эффективному построению СМО, организации рационального функционирования и регулированию потока заявок для наиболее эффективного обеспечения высокой производительности функционирования СМО. Задачи теории массового обслуживания ставятся для достижения этой цели. Они состоят в выявлении зависимостей обеспечения эффективного функционирования СМО от спсобов её построения.
По характеру, задачи теории массового обслуживания являются оптимизационными и в конечном итоге направлены на нахождение такого удовлетворяющего варианта системы, который будет обеспечивать минимальное значение суммарных затрат на ожидание обслуживания, потери времени и растрату ресурсов на само обслуживание и от простоев блока обслуживания. Знание этих характеристик предоставляет управляющему информацию для разарботки мер направленного воздействия на данные характеристики для возможности управления эффективностью процессов обеспечения массового обслуживания [10].
Обычно используются три следующие основные группы для обозначения характеристик рабочей эффективности СМО (обычно усреднённых) показателей значений:
Показатели эффективности применения системы:
Относительная пропускная способность - отношение среднего числа обращений, обрабатываемых системой за долю времени, к среднему числу обращений поступающих за ту же единицу времени.
Абсолютная пропускная способность - среднее количество обращений, которое сможет обработать система за определённую единицу времени системы.
Коэффициент использования - средняя часть времени, в период которого система занимается обработкой обращений, и т.п.
Средняя длительность периода полной занятости системы.
Качественные показатели обработки заявок:
Средняя длительность ожидания обращения в очереди.
Средняя продолжительность пребывания обращения в системе.
Вероятность отказа в обработке обращения без ожидания очереди.
Вероятность того, что поступившее обращение незамедлительно будет принята к обработке.
Закон распределения времени нахождения обращения в очереди.
Закон распределения времени поступления обращения в систему.
Среднее количество обращений, находящихся в очереди.
Среднее количество обращений, пребывающих в системе, и т.п.
Показатели эффективности функционирования сопряжения «СМО − потребитель», где под «потребителем» миеют в виду всю совокупность обращений(заявок) или какой-либо их источник [9]. К ним относится средний доход, приносимый СМО за единицу времени и т.д. и т.п.
Заметим, что третья группа показателей является наиболее полезной в тех случаях, когда получаемый от обработки обращений некоторый доход и затраты на обработку вычисляются в одних и тех же единицах измерения [1]. Данные показатели обычно имеют вполне определённый характер, и их определяет специфика самой СМО, обработки обращений и дисциплиной обслуживания.
Процессы поступления и обработки обращений в СМО являются случайными, что обуславливается случайным характером самого потока обращений и длительности их обработки.
Далее будем рассматривать СМО со случайным процессом, котрый подходит под определние марковского, то есть когда показатели вероятности состояний данной системы в будущем будет зависеить только от её текущего состояния и никак не зависеть от прошлого состояния (процесс без последействий обработки или без памяти). Для условий случайного марковского процесса необходимо то, чтобы способствующие переходу системы из одного состояния в другое (потоки обращений, потоки обработки и т.д.) потоки событий, подчинились пуассоновскому закону. Поток событий пуассоновского типа обладает рядом необходимых свойств, в том числе такими свойствами как отсутствия последействий, стационарности ординарности.
В самом простейшем пуассоновском потоке событийная случайная величина равномерно распределена согласно показательному закону (где λ - интенсивность входящего потока): f(t)=1⋅e^(-λ⋅t),t≥0
Основной целью для применения теории систем массового обслуживания обычно является разработка рекомендаций по более рациональному перестроению, реорганизации работ и попыток регулирования потока заявок. Следовательно, отсюда же вытекают и задачи, связанные с применением теорией массового обслуживания: полное установление зависимостей работы системы от её организационного построения, характеристики потока обращений, количества каналов обработки и их производительности, установленных правил работы системы.
В любой СМО основой является определенное количество устройств обработки – каналов обслуживания.
Для людой СМО назначение состоит в обработке потока обращений (требований, заявок), представляющих собою последовательность событий, возникающих нерегулярно и в заранее неопределённые и случайные моменты времени. Процедура самого обслуживания обращений также имеет случайный и непостоянный характер. Случайность характера потока обращений и времени их обработки обусловливает неравномерное распределение загрузки системы: необслуженные обращения могут накапливаться на входе (перегрузка СМО) или обращений нет либо их меньше, чем имеется свободных каналов обоработки (недогрузка СМО).
Очевидно, что таким образом, в сиситему поступают обращения, часть из которых незамедлимтельно принимается на обработку каналами системы, а другая часть становится в очередь на обработку, а остальная часть покидает систему необработанными.
Итак, подитожим вышеописанное…
Основными элементами СМО являются:
каналы обслуживания;
очередь;
входной поток обращений;
выходной поток обращений (обработанные заявки).
Пропускная способность определяет эффективность функционирования системы – относительным числом обработанных обращений.
Как уже говорилось ранее, по количетву каналов все СМО разделяются на одноканальные и многоканальные. Системы многоканальные могут быть как однородными (по обрабатывающим каналам), так и разнородными (по средней продолжительности обработки обращений).
Различают обычно три класса систем согласно дисциплине обслуживания:
система с отказами ( с нулевым ожиданием или же явные потери). Ранее отказанное обращение вновь поступает на вход, чтобы её обработали.
система с ожиданием (ожидание без ограничения или очереди). Во время занятости системы обращение поступает в очередь и, итоге, когда-нибудь будет нерпеменно выполнена (сферы торговли, медицинского и бытового обслуживания).
система смешанного типа (с ограниченным ожиданием). Также имеется лимт на длину очереди. Ограничение на время нахождения обращения в системе также может рассматриваться.
Также различают открытые (поток обращений не ограничен ни как), упорядоченные (обращения обрабатываются в порядке их поступления) и однофазные (одинаковые каналы для выполнения одной процедуры) системы.
Эффективную работоспособность систем массового обслуживания обычно характеризуют базовые показатели, их также можно разбить на нижепредставленные группы:
первая группа показателей эффективности использования системы:
абсолютная пропускная способность системы средне число обращений, обрабатываемых за единицу времени, или интенсивность выходного потока обработанных обращений
относительная пропускная способность – это отношение абсолютной пропускной способности к среднему количеству обращений, поступивших в систему за единицу времени;
средняя продолжительность интервала занятости системы;
интенсивность нагрузки, показывающая степень согласованной работы входного и выходного потоков обращений канала обработки и определяет показатель устойчивости системы в целом;
коэффициент использования системы – средний показатель доли времени, в течение которой система занята обработкой обращений.
Показатели качества обработки обращений:
Среднея величина времени ожидания обращения в очереди;
среднее время обработки заявки в системе;
вероятность отказа обращения в обработке без ожидания;
вероятность немедленного принятия обращения к обработке;
закон распределения интервалов времени нахождения обращения в очереди системы;
среднее количество обращений в очереди;
среднее количество обращений, находящихся в системе.
Далее рассмотрим для начала некоторые основные понятия, характеризующие некую «стохастическую неопределенность» – это когда входящие в задачу неопределённые факторы, представляют из себя случайные величины, вероятностные показатели которых либо уже известны, либо ещё эмприческим путём могут быть получены на деле. Подобную неопределенность также именуют «доброкачественной» или «благоприятной».
Говоря строго, случайные колебания могут сопутствовать любому процессу. Горзадо проще приводить примеры случайного, чем пытаться найти пример «неслучайного» процесса. Если даже, например, процесс хода часововых стрелок (вроде бы даже это очень строгая выверенная рабочая последоваательность) не менее подвержен случайным изменениям (отставание, уход вперед, остановка). Но при этом, до тех пор, пока эти колебания достаточно несущественны и мало влияют на необходимые нам параметры, обычно, мы их порсто пренебрегаем, и рассматриваем процесс как неслучайный, детерминированный.
Определим, что имеется некоторая работоспособная система S (прибор, техническое устройство или группа устройств). В данной системе S происходит случайный процесс, и она способна с течением времени менять своё текущее состояние (переходить из одного состояния в другое), причём, случайным заранее неизвестным образом. Например, система S является технологической системой (некий участок некторых станков). Эти станки неопределённо-периодически, время от времени, приходят в несправное состояние и, предположительно, ремонтируются. Данный процесс, протекающий в определённой системе, полностью случаен. Или же, система S это самолет, совершающий полёт на заранее заданной высоте и по заведомо определенному маршруту. Всевозможные возмущающие факторы – ошибки экипажа, метеоусловияи т.д., последствия – обычная «болтанка», нарушение расписания рейсов и т.д.
Случайный процесс, протекающий в системе, называется Марковским, если для любого момента времени t0 вероятностные характеристики процесса в будущем зависят только от его состояния в данный момент t0 и не зависят от того, когда и как система пришла в это состояние.
Пусть в настоящий момент t0 система находится в определенном состоянии S0. Мы знаем характеристики состояния системы в настоящем и все, что было при t<t0 (предысторию процесса). Можем ли мы предугадать (предсказать) будущее, т.е. что будет при t>t0? В точности – нет, но какие-то вероятностные характеристики процесса в будущем найти можно. Например, вероятность того, что через некоторое время система S окажется в состоянии S1 или останется в состоянии S0 и т.д.
Пример. Система S группа самолетов, участвующих в воздушном бою. Пусть x – количество «красных» самолетов, y – количество «синих» самолетов. К моменту времени t0 количество сохранившихся (не сбитых) самолетов соответственно – x0, y0. Нас интересует вероятность того, что в момент времени численный перевес будет на стороне «красных». Эта вероятность зависит от того, в каком состоянии находилась система в момент времени t0, а не от того, когда и в какой последовательности погибали сбитые до момента t0 самолеты.
На практике Марковские процессы в чистом виде обычно не встречаются. Но имеются процессы, для которых влиянием «предыстории» можно пренебречь. И при изучении таких процессов можно применять Марковские модели (в теории массового обслуживания рассматриваются и не Марковские системы массового обслуживания, но математический аппарат, их описывающий, гораздо сложнее).
В исследовании операций большое значение имеют Марковские случайные процессы с дискретными состояниями и непрерывным временем.
Процесс называется процессом с дискретным состоянием, если его возможные состояния S1, S2, … можно заранее определить, и переход системы из состояния в состояние происходит «скачком», практически мгновенно.
Процесс называется процессом с непрерывным временем, если моменты возможных переходов из состояния в состояние не фиксированы заранее, а неопределенны, случайны и могут произойти в любой момент.
Далее рассматриваются только процессы с дискретным состоянием и непрерывным временем.
Пример. Технологическая система (участок) S состоит из двух станков, каждый из которых в случайный момент времени может выйти из строя (отказать), после чего мгновенно начинается ремонт узла, тоже продолжающийся заранее неизвестное, случайное время. Возможны следующие состояния системы:
S0 - оба станка исправны;
S1 - первый станок ремонтируется, второй исправен;
S2 - второй станок ремонтируется, первый исправен;
S3 - оба станка ремонтируются.
Переходы системы S из состояния в состояние происходят практически мгновенно, в случайные моменты выхода из строя того или иного станка или окончания ремонта.
При анализе случайных процессов с дискретными состояниями удобно пользоваться геометрической схемой графом состояний. Вершины графа – состояния системы. Дуги графа возможные переходы из состояния в состояние. Для нашего примера граф состояний приведен на рис. 1.

Рис. 1. Граф состояний системы
Примечание. Переход из состояния S0 в S3 на рисунке не обозначен, т.к. предполагается, что станки выходят из строя независимо друг от друга. Вероятностью одновременного выхода из строя обоих станков мы пренебрегаем.
1.3 Потоки событий
Поток событий – последовательность однородных событий, следующих одно за другим в какие-то случайные моменты времени.
В предыдущем примере это поток отказов и поток восстановлений. Другие примеры: поток вызовов на телефонной станции, поток покупателей в магазине и т.д.
Поток событий можно наглядно изобразить рядом точек на оси времени O t – рис. 2.

Рис. 2. Изображение потока событий на оси времени
Положение каждой точки случайно, и здесь изображена лишь какая-то одна реализация потока.
Интенсивность потока событий ( ) – это среднее число событий, приходящееся на единицу времени.
Рассмотрим некоторые свойства (виды) потоков событий.
Поток событий называется стационарным, если его вероятностные характеристики не зависят от времени.
В частности, интенсивность стационарного потока постоянна. Поток событий неизбежно имеет сгущения или разрежения, но они не носят закономерного характера, и среднее число событий, приходящееся на единицу времени, постоянно и от времени не зависит.
Поток событий называется потоком без последствий, если для любых двух непересекающихся участков времени и (см. рис. 2) число событий, попадающих на один из них, не зависит от того, сколько событий попало на другой. Другими словами, это означает, что события, образующие поток, появляются в те или иные моменты времени независимо друг от друга и вызваны каждое своими собственными причинами.
Поток событий называется ординарным, если события в нем появляются поодиночке, а не группами по нескольку сразу.
Поток событий называется простейшим (или стационарным пуассоновским), если он обладает сразу тремя свойствами:
1) стационарен;
2) ординарен;
3) не имеет последствий.
Простейший поток имеет наиболее простое математическое описание. Он играет среди потоков такую же особую роль, как и закон нормального распределения среди других законов распределения. А именно, при наложении достаточно большого числа независимых, стационарных и ординарных потоков (сравнимых между собой по интенсивности) получается поток, близкий к простейшему.
Для простейшего потока с интенсивностью интервал T между соседними событиями имеет так называемое показательное (экспоненциальное) распределение с плотностью:

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

1.4 Уравнения Колмогорова для вероятностей состояний. Финальные вероятности состояний
Рассматривая Марковские процессы с дискретными состояниями и непрерывным временем, подразумевается, что все переходы системы S из состояния в состояние происходят под действием простейших потоков событий (потоков вызовов, потоков отказов, потоков восстановлений и т.д.). Если все потоки событий, переводящие систему S из состояния в состояние простейшие, то процесс, протекающий в системе, будет Марковским.
Итак, на систему, находящуюся в состоянии , действует простейший поток событий. Как только появится первое событие этого потока, происходит «перескок» системы из состояния в состояние (на графе состояний по стрелке ).
Для наглядности на графе состояний системы у каждой дуги проставляют интенсивности того потока событий, который переводит систему по данной дуге (стрелке). - интенсивность потока событий, переводящий систему из состояния в . Такой граф называется размеченным. Для нашего примера размеченный граф приведен на рис. 3.

Рис. 3. Размеченный граф состояний системы
На этом рисунке - интенсивности потока отказов; - интенсивности потока восстановлений.
Предполагаем, что среднее время ремонта станка не зависит от того, ремонтируется ли один станок или оба сразу. Т.е. ремонтом каждого станка занят отдельный специалист.
Пусть система находится в состоянии S0. В состояние S1 ее переводит поток отказов первого станка. Его интенсивность равна:

где - среднее время безотказной работы первого станка.
Из состояния S1 в S0 систему переводит поток «окончаний ремонтов» первого станка. Его интенсивность равна:

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

Для нахождения всех вероятностей состояний как функций времени составляются и решаются уравнения Колмогорова – особого вида уравнения, в которых неизвестными функциями являются вероятности состояний. Правило составления этих уравнений приведем здесь без доказательств. Но прежде, чем его приводить, объясним понятие финальной вероятности состояния.
Что будет происходить с вероятностями состояний при ? Будут ли стремиться к каким-либо пределам? Если эти пределы существуют и не зависят от начального состояния системы, то они называются финальными вероятностями состояний.

где - конечное число состояний системы.
Финальные вероятности состояний это уже не переменные величины (функции времени), а постоянные числа. Очевидно, что:

Финальная вероятность состояния – это по–существу среднее относительное время пребывания системы в этом состоянии.
Например, система S имеет три состояния S1, S2 и S3. Их финальные вероятности равны соответственно 0,2; 0,3 и 0,5. Это значит, что система в предельном стационарном состоянии в среднем 2/10 времени проводит в состоянии S1, 3/10 – в состоянии S2 и 5/10 в состоянии S3.
Правило составления системы уравнений Колмогорова: в каждом уравнении системы в левой его части стоит финальная вероятность данного состояния , умноженная на суммарную интенсивность всех потоков, ведущих из данного состояния, а в правой его части – сумма произведений интенсивностей всех потоков, входящих в -е состояние, на вероятности тех состояний, из которых эти потоки исходят.
Пользуясь этим правилом, напишем систему уравнений для нашего примера:
.
Эту систему четырех уравнений с четырьмя неизвестными , казалось бы, можно вполне решить. Но эти уравнения однородны (не имеют свободного члена), и, значит, определяют неизвестные только с точностью до произвольного множителя. Однако можно воспользоваться нормировочным условием: и с его помощью решить систему. При этом одно (любое) из уравнений можно отбросить (оно вытекает как следствие из остальных).
Продолжение примера. Пусть значения интенсивностей потоков равны: .
Четвертое уравнение отбрасываем, добавляя вместо него нормировочное условие:
.
.
Т.е. в предельном, стационарном режиме система S в среднем 40% времени будет проводить в состоянии S0 (оба станка исправны), 20% - в состоянии S1 (первый станок ремонтируется, второй работает), 27% - в состоянии S2 (второй станок ремонтируется, первый работает), 13% - в состоянии S3 (оба станка ремонтируются). Знание этих финальных вероятностей может помочь оценить среднюю эффективность работы системы и загрузку ремонтных органов.
Пусть система S в состоянии S0 (полностью исправна) приносит в единицу времени доход 8 условных единиц, в состоянии S1 – доход 3 условные единицы, в состоянии S2 – доход 5 условных единиц, в состоянии S3 – не приносит дохода. Тогда в предельном, стационарном режиме средний доход в единицу времени будет равен: условных единиц.
Станок 1 ремонтируется долю времени, равную: . Станок 2 ремонтируется долю времени, равную: . Возникает задача оптимизации. Пусть мы можем уменьшить среднее время ремонта первого или второго станка (или обоих), но это нам обойдется в определенную сумму. Спрашивается, окупит ли увеличение дохода, связанное с ускорением ремонта, повышенные расходы на ремонт? Нужно будет решить систему четырех уравнений с четырьмя неизвестными.