Теория массового обслуживания и экономико-математическое моделирование

Размещено на http://www.allbest.ru/

Академия управления при президенте республики беларусь

Курсовая работа

На тему Теория массового обслуживания и экономико-математическое моделирование

Минск 2022



ОГЛАВЛЕНИЕ

ВВЕДЕНИЕ



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

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

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

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

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



ГЛАВА 1. ОСНОВЫ ТЕОРИИ МАССОВОГО ОБСЛУЖИВАНИЯ

1.1 Предмет и задачи теории массового обслуживания

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

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

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

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

Система массового обслуживания.

Система обслуживания считается заданной, если известны:

1) поток требований, его характер;

2) множество обслуживающих приборов;

3) дисциплина обслуживания (совокупность правил, задающих процесс обслуживания).

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

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

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

Характеристики СМО.

Перечень характеристик систем массового обслуживания можно представить следующим образом:

-среднее время обслуживания;

-среднее время ожидания в очереди;

-среднее время пребывания в СМО;

-средняя длина очереди;

-среднее число заявок в СМО;

-количество каналов обслуживания;

-интенсивность входного потока заявок;

-интенсивность обслуживания;

-интенсивность нагрузки;

-коэффициент нагрузки;

-относительная пропускная способность;

-абсолютная пропускная способность;

-доля времени простоя СМО;

-доля обслуженных заявок;

-доля потерянных заявок;

-среднее число занятых каналов;

-среднее число свободных каналов;

-коэффициент загрузки каналов;

-среднее время простоя каналов.

1.2 Потоки событий, их свойства и математическое описание

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

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

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

Поэтому

где f(t) - плотность распределения длительностей интервалов между событиями. Для стационарного потока л = const.

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

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

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



где б = лф - среднее число событий, приходящихся на участок ф.

Поэтому простейший поток часто называют стационарным пуассоновским потоком. Для нестационарного пуассоновского потока

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

т.е. вероятность того, что . Эта вероятность равна вероятности того, что на участок времени t попадает хотя бы одно событие, т.е.

где - вероятность того, что на участок t не попадает ни одно событие. Учитывая выражение (1.2.2), получим

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

Экспоненциальное распределение обладает замечательным свойством «не помнить о прошлом»: если рассматриваемый промежуток времени уже «длился» некоторое время, то это никак не влияет на закон распределения оставшейся части этого промежутка. Доказательство этого положения приведено в работе [2]. Применительно к потоку заявок указанное свойство простейшего потока можно сформулировать так: вероятность поступления заявки в течение некоторого интервала времени не зависит от того, сколько времени прошло после поступления предыдущей заявки. Именно поэтому простейший поток иногда называют «совершенно случайным потоком».

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



ГЛАВА 2. ОСНОВНЫЕ ПОНЯТИЯ ЭКОНОМИКО- МАТЕМАТИЧЕСКОГО МОДЕЛИРОВАНИЯ

2.1 Понятие модели

Экономико-математическая модель [economic model, economico-mathematical model] -- математическое описание экономического процесса или объекта, произведенное в целях их исследования и управления ими: математическая запись решаемой экономической задачи (поэтому часто термины “модель” и “задача” употребляются как синонимы). Существует еще несколько вариантов определения этого термина.

В самой общей форме модель -- условный образ объекта исследования, сконструированный для упрощения этого исследования. При построении модели предполагается, что ее непосредственное изучение дает новые знания о моделируемом объекте. Все это полностью относится и к экономико-математической модели. В принципе в экономике применимы не только математические (знаковые), но и материальные модели. Например, гидравлические (в которых потоки воды имитируют потоки денег и товаров, а резервуары отождествляются с такими экономическими категориями, как объем промышленного производства, личное потребление и др.) и электрические (в США была известна модель «Эконорама», представлявшая собой сложную электрическую схему, в которой имитировались экономические процессы). Но все эти попытки имели лишь демонстрационное применение, а не служили средством изучения закономерностей экономики. С развитием же электронно-вычислительной техники потребность в них, по-видимому, и вовсе отпала.

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

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

2.2 Экономико-математические модели и их классификация

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

В зависимости от формы построения можно выделить следующие типы моделей:

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

- графическая модель создается в виде рисунка, географической карты или чертежа. Например, зависимость между ценой и спросом может быть выражена в виде графика, на оси ординат которого отложен спрос (D), а на оси абсцисс -- цена (Р). Кривая нам наглядно иллюстрирует, что с ростом цены спрос падает, и наоборот (рисунок 2.2.1);



Рисунок 2.2.1 - Графическая модель, отображающая зависимость между спросом и ценой

- физические, или вещественные, модели создаются для конструирования пока еще несуществующих объектов.

По степени агрегирования объектов моделирования различают модели:

- микроэкономические (эти модели разрабатываются для углубленного анализа структуры производства, позволяют выявить резервы роста объемов производства продукции);

- локальные (это модели, с помощью которых анализируются и прогнозируются некоторые показатели развития отрасли);

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

По учету фактора времени различают модели:

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

- динамические (эти модели описывают экономическую систему в развитии).

По учету фактора неопределенности различают модели:

- детерминированные (с однозначно определенными результатами);

- стохастические (с различными вероятностными результатами).

По цели создания и применения различают модели:

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

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

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

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

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

Однако существуют и такие сетевые модели, которые ориентированы не на критерий времени, а, например, на минимизацию стоимости работ):

- модели систем массового обслуживания (создаются для минимизации затрат времени на ожидание в очереди и времени простоев каналов обслуживания).

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

Проблемы моделирования. Как все средства и методы, модели науки управления в случае их применения могут привести к ошибкам. Эффективность модели иногда снижается действием ряда потенциальных погрешностей.

Недостоверные исходные допущения. Любая модель опирается на некоторые исходные допущения, или предпосылки. Это могут быть поддающиеся оценке предпосылки, например то, что расходы на рабочую силу в следующие шесть месяцев составят 200 тыс. долл. Такие предположения можно объективно проверить и просчитать. Вероятность их точности будет высока. Некоторые предпосылки не поддаются оценке и не могут быть объективно проверены. Предположение о росте сбыта в будущем году на 10 % -- пример допущения, не поддающегося проверке. Никто не знает наверняка, произойдет ли это действительно. Поскольку такие предпосылки -- основа модели, точность последней зависит от точности предпосылок. Модель нельзя использовать для прогнозирования, например, потребности в запасах, если неточны прогнозы сбыта на предстоящий период. обслуживание математический моделирование

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

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

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

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

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

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

2.3 Экономико-математическое моделирование и его основные этапы

Процесс экономико-математического моделирования включает:

* идентификацию объекта или процесса;

* спецификацию модели;

* идентификацию и оценку параметров модели;

* установление зависимостей между параметрами модели;

* проверку модели.

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

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

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

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

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

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

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

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

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

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

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

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

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

После построения модели определяется ее тип и выбирается соответствующий этому типу метод решения.

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

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

* подходящий метод вообще отсутствует, и тогда необходима его разработка;

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

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

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

Оценка качества алгоритма обычно определяется:

* сходимостью (если алгоритм не сходится, то невозможно получить решение);

* скоростью сходимости (чем она выше, тем меньше шагов требуется для получения решения);

* затратами времени (зависит не только от числа шагов, но и от других обстоятельств, например объема вычислений на каждом шаге);

* удобством обращения;

* возможностью работы в интерактивном (диалоговом) режиме.

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

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

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

* алгоритмы, для которых известно, что на каждой итерации решение улучшается, причем число таких итераций для достижения оптимума конечно;

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

* алгоритмы, основанные на методе проб и ошибок, которые обеспечивают улучшение в целом, но не на отдельной итерации.

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

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

* включение в модель несущественных (для данной задачи) переменных;

* игнорирование в модели существенных переменных;

* недостаточно точная оценка параметров модели;

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

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

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

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



ГЛАВА 3. СИСТЕМЫ МАССОВОГО ОБСЛУЖИВАНИЯ

3.1 Классификация систем массового обслуживания

Каждая система массового обслуживания (СМО) имеет определенные правила формирования очереди и дисциплину обслуживания, но общими основными элементами СМО являются:

* входящий поток заявок (требований) на обслуживание;

* очередь заявок на обслуживание;

* приборы (каналы) обслуживания;

* выходящий поток обслуженных заявок (рис. 3.1.1).

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

Рисунок 3.1.1 Общая схема систем массового обслуживания

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

Рассмотрим характеристики входящего потока требований:

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

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

3) поток событий называется ординарным, если невозможно одновременное поступление двух или более событий;

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

где Рк(т) -- вероятность поступления к заявок за время т;

X -- интенсивность входного потока.

Важное для исследования свойство, которым обладает пуассоновский поток, заключается в том, что процедура разделения и объединения дает снова пуассоновские потоки. Тогда, если входной поток формируется из N независимых источников, каждый из которых порождает пуассоновский поток интенсивностью (i = 1, 2, ..., АО, то его интенсивность будет определяться по формуле

В случае разделения пуассоновского потока на N независимых потоков получим, что интенсивность потока А, будет равна г, А,

где г, -- доля i-ro потока во входном потоке требований.

Соответствующие значения вероятностей Р^Ст) нетрудно определить с помощью таблицы пуассоновского распределения. Например, если средний темп поступления заявок -- две заявки в час, то вероятность того, что в течение часа в систему не поступит ни одной заявки, равна 0,135, вероятность появления одной заявки -- около 0,27, двух -- также около 0,27, три заявки могут появиться с вероятностью 0,18, четыре -- с вероятностью около 0,09 и т. д. Вероятность того, что за час в систему поступят девять заявок или более, близка нулю.

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

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

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

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

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

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

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

Очередь заявок на обслуживание характеризуется длиной и правилами (дисциплиной) обслуживания.

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

Порядок поступления заявок на обслуживание называется дисциплиной обслуживания (правилом обслуживания).

В СМО с очередью могут быть следующие варианты дисциплины обслуживания:

а) обслуживание в порядке поступления заявок (первым пришел -- первым обслужился);

б) обслуживание в порядке обратном поступлению, т. е. последняя заявка обслуживается первой (последним пришел -- первым обслужился);

в) обслуживание с приоритетом;

г) обслуживание в случайном порядке.

Большинство реальных систем использует правило «первым пришел -- первым ушел» (англ, first in --first out, FIFO). В некоторых случаях в дополнение к этому правилу могут устанавливаться различные приоритеты. В период посевной кампании ремонт сеялки обладает приоритетом по сравнению с ремонтом зерноуборочного комбайна.

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

Системы обслуживания различаются:

1) по числу каналов обслуживания. Обычно количество каналов можно определить, как число клиентов, обслуживание которых может быть начато одновременно, например: число подъемников в автомастерской. Примеры одноканальной системы обслуживания: банк, в котором открыто единственное окошко для обслуживания клиентов, или ресторан, обслуживающий клиентов в автомобилях. Если же в банке открыто несколько окошек для обслуживания, клиент ожидает в общей очереди и подходит к первому освободившемуся окну, то мы имеем дело с многоканальной однофазовой системой обслуживания. Большинство банков, также, как почтовые отделения и авиакассы, являются многоканальными системами обслуживания;

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

Рисунок 3.1.2 Системы обслуживания различной конфигурации

О -- заявка; [_| -- пункт обслуживания

Основным параметром режима обслуживания считается время обслуживания заявки каналом (обслуживающим прибором j) -- t- (j = 1, 2, ..., m). Величина t в каждом конкретном случае определяется рядом факторов: интенсивностью поступления заявок, квалификацией исполнителя, технологией работ, окружающей средой и т. д. Законы распределения случайной величины L могут быть самыми различными, но наибольшее распространение в практических приложениях получил экспоненциальный закон распределения. Функция распределения случайной величины tj имеет вид:

где ц -- положительный параметр, определяющий интенсивность обслуживания требований;

где Е (0 -- математическое ожидание случайной величины обслуживания требования t;.

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

Если СМО состоит из неоднородных каналов, то р = ? pj, если же все каналы однородные, то ц = т ?

Существуют и другие разновидности СМО: «открытые» и «замкнутые». В открытой СМО характеристики потока заявок не зависят от того, в каком состоянии сама СМО (сколько каналов занято). Для этих систем поступающий поток требований можно считать неограниченным.

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

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

Существуют СМО с «взаимопомощью» между каналами (незанятые каналы «помогают» занятому в обслуживании).

На рис. 12.4, а представлена модель работы системы с регулярным потоком требований. Поскольку известен промежуток между поступлениями требований, то время обслуживания выбрано так, чтобы полностью загрузить систему. Для системы со стохастическим потоком требований ситуация совершенно иная: -- требования приходят в различные моменты времени и время обслуживания тоже является случайной величиной, которая может быть описана неким законом распределения.

По характеру организации СМО бывают: с отказами; с ожиданиями (с очередью); с ограничением ожидания.

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

В зависимости от типа СМО при оценке ее эффективности могут применяться те или иные величины (показатели эффективности).

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

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

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

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

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

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

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

3.3 Уравнения систем массового обслуживания

К уравнениям систем массового обслуживания следует отнести прежде всего систему уравнений Колмогорова, которая представляет систему дифференциальных уравнений, описывающих динамику распределения вероятностей состояний для Марковского процесса с непрерывным временем. Продолжая пример 1, покажем, как может быть получена такая система уравнений. Пусть P1(t), P2 (t), P3 (t) - вероятности того, что в момент времени t система будет находиться в состояниях , , и соответственно.

Тогда вероятность того, в момент 1 S 2 S 3 S t + ?t система окажется в состоянии следует определять по формуле полной вероятности с учётом того, что это может произойти либо в результате перехода из других состояний, либо в результате того, что система, находясь в состоянии, в этом состоянии и осталась. Для любого момента времени t справедливо записать нормировочное условие--сумма вероятностей всех состояний равна 1:

Уpi (t)=p0 (t)+ p1 (t)+ p2 (t)=1 (3.3.1)

где i =0

Проведем анализ системы в момент времени t, задав малое приращение времени Дt, и найдем вероятность р1 (t+ Дt) того, что система в момент времени (t+ Дt) будет находиться в состоянии S1 которое достигается разными вариантами: а) система в момент t с вероятностью p1 (t) находилась в состоянии S1 и за малое приращение времени Дt так и не перешла в другое соседнее состояние -- ни в S0 , ни bS2 . Вывести систему из состояния S1 можно суммарным простейшим потоком c интенсивностью (л10 +л12), поскольку суперпозиция простейших потоков также является простейшим потоком. На этом основании вероятность выхода из состояния S1 за малый промежуток времени Дt приближенно равна (л10 +л12)* Дt. Тогда вероятность невыхода из этого состояния равна [1 -(л10 +л12 )* Дt]. B соответствии с этим вероятность того, что система останется в состоянии Si на основании теоремы умножения вероятностей, равна:



p1 (t) [1 -(л10 +л12)* Дt];

б) система находилась в соседнем состоянии So и за малое время Дt перешла в состояние So Переход системы происходит под воздействием потока л01 с вероятностью, приближенно равной л01 Дt

Вероятность того, что система будет находиться в состоянии S1, в этом варианте равна po (t)л01 Дt; в) система находилась в состоянии S2 и за время Дt перешла в состояние S1 под воздействием потока интенсивностью л21 с вероятностью, приближенно равной л21 Дt. Вероятность того, что система будет находиться в состоянии S1, равна p2 (t) л21 Дt.

Применяя теорему сложения вероятностей для этих вариантов, получим выражение:

p2 (t+Дt) = p1 (t) [1 -(л10 +л12)* Дt]+ po (t)л01 Дt+p2 (t) л21 Дt ,

которое можно записать иначе:

p2 (t+Дt)-p1 (t)/ Дt= po (t)л01 + p2 (t) л21 - p1 (t) (л10 +л12).

Переходя к пределу при Дt-> 0, приближенные равенства перейдут в точные, и тогда получим производную первого порядка

dp2 /dt= p0 л01 +p2 л21 -p1 (л10 +л12),

что является дифференциальным уравнением.

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



dp0 /dt= p1 л1,

dp1 /dt= p0 л01 +p2 л21 -p1 (л10 +л12),

dp2 /dt= p1 л12 +p2 л21.

Для составления уравнений Колмогорова существуют общие правила.

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



Заключение

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

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

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

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

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

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

...