TERMINATE 6 страница. Переход системы из состояния S0 в S1 происходит под воздействием простейшего потока заявок интенсивностью λ01

Переход системы из состояния S0 в S1 происходит под воздействием простейшего потока заявок интенсивностью λ₀₁ , а из состояния S1 в состояние S0 систему переводит поток обслуживания с интенсивностью λ₁₀. Граф состояний системы обслуживания с проставленными интенсивностями потоков у стрелок называется размеченным. Поскольку пребывание системы в том или ином состоянии носит вероятностный характер, то вероятность рi(t) того, что система будет находиться в состоянии Si в момент времени t, называется вероятностью i-го состояния СМО и определяется числом поступивших заявок k на обслуживание.

Случайный процесс, происходящий в системе, заключается в том, что в случайные моменты времени t0, t1, t2, ….., tk ,….., tn система оказывается в том или другом заранее известном дискретном состоянии последовательно. Такая случайная последовательность событий называется Марковской цепью, если для каждого шага вероятность перехода из одного состояния Si в любое другое Sj не зависит от того, когда и как система перешла в состояние Si. Описывается Марковская цепь с помощью вероятности состояний, причем они образуют полную группу событий, поэтому их сумма равна единице. Если вероятность перехода не зависит от номера k, то Марковская цепь называется однородной. Зная начальное состояние системы обслуживания, можно найти вероятность состояний для любого значения k – числа заявок, поступивших на обслуживание.

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

3.1.3 Потоки событий СМО.

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

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

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

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

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

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

Чаще всего считается, что входной и выходной потоки могут быть отнесены к простейшим. Предположим, статистические наблюдения позволили получить величину λ­ среднего число заявок, появляющихся за единицу времени (интенсивность входного потока). Интенсивность простейшего потока постоянна в силу его стационарности. Обратная ей величина 1/ λ, — средний интервал времени между двумя соседними заявками.

λ ­ параметр потока, может быть выражен в разных единицах:

Плотность вероятности входного потока описывается функцией:

f (t) = λ e^-λτ, t≥0. (3.1)

Математическое ожидание ­1/ λ, (3.2)

Дисперсия ­ 1/ λ2, (3.3)

Среднеквадратичное отклонение ­ 1/ λ. (3.4)

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

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

Обратная величина 1/ μ определяет среднее время обслуживания одной заявки.

Имеет смысл рассматривать те проекты СМО, для которых среднее время обслуживания 1/μ меньше среднего промежутка времени 1/λ между поступлением заявок, ибо в противном случае очередь будет постоянно расти. В том же случае, когда 1/μ < 1/λ, через некоторое время после начала работы система перейдет в стационарный режим.

Обозначив отношение λ/μ через р, можно показать, что стационарный режим устанавливается при р < 1. Величину р называют нагрузкой системы.

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

• коэффициент простоя системы

Е₁ = 1-р, (3.5)

• среднее число заявок в системе

Е₂ = p/(1-p), (3.6)

• средняя длина очереди

Е₃= p²(1-p), (3.7)

• среднее время пребывания заявки в системе

Е₄ =l /(μ-λ), (3.8)

• время пребывания заявки в очереди

Е₅ = р/(μ-λ). (3.9)

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

3.1.4 Пример простой СМО.

В качестве примера применения системы массового обслуживания рассмотрим задачу проектирования автозаправочной станции (АЗС).

Пример 3.1 Пусть необходимо выбрать один из нескольких вариантов строительства АЗС. Автомобили прибывают на станцию случайным образом и, если не могут быть обслужены сразу, становятся в очередь. Дисциплина очереди: «первым пришел — первым обслужен». Предположим для простоты, что во всех вариантах рассматривается только одна бензоколонка, а вариант от варианта отличается лишь ее мощностью. Средний интервал времени между прибытием автомобилей ( ) составляет 4 минуты и не зависит от варианта строительства.

Величина среднего времени обслуживания одного автомобиля ( )зависит от выбранного варианта строительства АЭС и составляет (соответственно вариантам): 5 мин, 3,5 мин, 2 мин, 1 мин, 0,5 мин. Результаты расчетов по исследованию раз­личных вариантов строительства АЗС по формулам (3.5 ÷3.9) сведены в табл. 3.1:

Таблица 3.1

Из анализа результатов расчетов следует.

Первый вариант строительства АЗС не годен из-за того, что очередь в этом случае будет расти до бесконечности (р>1).

Второй вариант приемлем по показателю загруженности оборудования

р = 0,88 и, следовательно, малой средней доли простоя оборудо­вания Е₁ = 0,13, но при этом варианте возникают большие очереди и, следовательно, большие средние времена простоя автомобилей Е₄ ≈ 27 мин.

Третий вариант приводит к тому, что оборудование в среднем половину времени простаивает, но среднее число автомобилей в системе равно только 1, а средние потери времени равны 4 мин при среднем времени обслуживания 2 мин.

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

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

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

Вопросы по теме

1. Каковы основные составляющие систем массового обслуживания? Каковы могут быть устройства блоков обслуживания?

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

3. Какими показателями характеризуются системы массового обслуживания?

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

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

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

3.2 Имитационное моделирование

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

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

3.2.1 Общие сведения о GPSSW (язык имитационного моделирования GPSS в среде ОС WINDOWS).

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

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

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

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

Рисунок 3.3 Процесс моделирования в GPSSW.

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

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

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

· Динамические объекты, соответствующие заявкам в системах массового обслуживания, называются в GPSSW транзактами. Они «создаются» и «уничтожаются» так, как это необходимо по логике модели в процессе моделирования. С каждым транзактом может быть связано произвольное число параметров, несущих в себе необходимую информацию об этом транзакте. Кроме того, транзакты могут иметь различные приоритеты.

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

· Аппаратные объекты GPSSW — соответствуют обслуживающим приборам (устройствам) в СМО. К ним относятся одноканальные и многоканальные устройства. Одноканальное устройство, которое для краткости далее будем называть просто устройством, может обслуживать одновременно только один транзакт. Многоканальное устройство (МКУ) может обслуживать одновременно несколько транзактов. Многоканальное устройство иногда называют памятью.

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

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

· Запоминающие объекты GPSS/PC обеспечивают хранение в памяти ПК отдельных величин, используемых в модели, а также массивов таких величин. К ним относятся так называемые сохраняемые величины и матрицы сохраняемых величин.

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

3.2.2 Управление последовательностью выполнения программы GPSS: понятие симулятора и таймера модельного времени.

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

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

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

1) транзакт входит в блок, функцией которого является удаление транзакта из модели;

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

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

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

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

Таймер GPSS/PC имеет следующие особенности:

1) регистрируются только целые значения (все временные интервалы в модели изображаются целыми числами);

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

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

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

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

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

Симулятор GPSS/PC помещает транзакты в зависимости от условий в модели в тот или иной список и переносит транзакты из списка в список, просматривает списки, выбирая следующий транзакт для обработки, корректирует таймер модельного времени после обработки всех транзактов в списке текущих событий.

3.2.3 Основные операторы GPSSW и связанные с ними объекты.

Исходная программа на языке GPSSW, как и программа на любом языке программирования, представляет собой последовательность операторов. Операторы исходного текста GPSSW записываются и вводятся в ПК в следующем формате (в скобках указаны необязательные части):

[ имя ] операция операнды [; комментарии]

Отдельные операторы могут иметь имя для ссылки на эти операторы в других операторах. Если такие ссылки отсутствуют, то этот элемент оператора не является обязательным.

В поле операции записывается ключевое слово (название оператора), указывающее конкретную функцию, выполняемую данным оператором. Это поле оператора является обязательным.

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

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

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

1) Операторы связанные с транзактами.

С транзактами связаны операторы создания, уничтожения и задержки транзактов.

Для создания транзактов, входящих в модель, служит оператор GENERATE (генерировать), имеющий следующий формат:

имя GENERATE A,B,C,D,E

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

Например,оператор GENERATE 100,40

создает транзакты через случайные интервалы времени, равномерно распределенные на отрезке [60;140].

В поле С задается момент поступления в модель первого транзакта. Если это поле пусто или равно 0, то момент появления первого транзакта определяется операндами А и В.

Поле D задает общее число транзактов, которое должно быть создано оператором GENERATE. Если это поле пусто, то блок генерирует неограниченное число транзактов до завершения моделирования.

В поле Е задается приоритет, присваиваемый генерируемым транзактам. Число уровней приоритетов неограничено, причем самый низкий приоритет — нулевой. Если поле Е пусто, то генерируемые транзакты имеют нулевой приоритет.

Для удаления транзактов из модели служит блок TERMINATE (завершить), имеющий следующий формат:

имя TERMINATE A

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

Блок TERMINATE A с ненулевым полем А используется для управления временем моделирования (см. рис.3.4):

Рисунок 3.4 Управление временем моделирования в GPSSW.

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

Для задержки транзактов на определенный отрезок модельного времени служит блок ADVANCE (задержать), имеющий следующий формат:

имя ADVANCE А,В

Операнды в полях А и В имеют тот же смысл, что и в соответствующих полях блока GENERATE. Следует отметить, что транзакты, входящие в блок ADVANCE, по истечении вычисленного времени задержки продолжают продвижение по блок-схеме. Если вычисленное время задержки равно 0, то транзакт в тот же момент модельного времени переходит в следующий блок.

GENERATE 100,40

ADVANCE 80,50

TERMINATE

Рис. 3.5

Например, в сегменте, приведенном на рис.3.5, транзакты, поступающие в модель из блока GENERATE через случайные интервалы времени, имеющие равномерное распределение на отрезке [60;140], попадают в блок ADVANCE. Здесь определяется случайное время задержки транзакта, имеющее равномерное распределение на отрезке [30;130]. По истечении времени задержки транзакт входит в блок TERMINATE, где и уничтожается.