Моделирование систем управления

МИНИСТЕРСТВО ТРАНСПОРТА РОССИЙСКОЙ ФЕДЕРАЦИИ ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ «РОССИЙСКИЙ УНИВЕРСИТЕТ ТРАНСПОРТА (МИИТ)» (РУТ (МИИТ) Одобрено кафедрой «ЖЕЛЕЗНОДОРОЖНАЯ АВТОМАТИКА ТЕЛЕМЕХАНИКА И СВЯЗЬ» Протокол № от 201 г. Автор: ЛЕКЦИИ ПО ДИСЦИПЛИНЕ Моделирование систем управления Уровень ВО: Бакалавриат Форма обучения: Заочная Курс: 4 Специальность/Направление: 27.03.04 Управление в технических системах (УТб) Специализация/Профиль/Магистерская программа: Системы и технические средства автоматизации и управления (УТ) Москва Лекции по дисциплине «Моделирование систем управления» для студентов 4 курса направления «Управление в технических системах» профиля: «Системы и технические средства автоматизации и управления» Лекция 1. Основные понятия теории моделирования, современное состояние и общая характеристика проблемы моделирования систем. Объект - все то, на что направлена человеческая деятельность. Под объектом может пониматься техническое устройство, его часть, система устройств, процесс, явление. Аналогия – сходство двух объектов в каких-либо свойствах. Умозаключение по аналогии – знание, полученное из рассмотрения какого либо объекта, переносится на менее изученный, сходный по существенным свойствам, качествам объект. Такие умозаключения являются одним из источников гипотез. Гипотеза - предположение о свойствах объекта, выдвигаемое для объяснения каких либо фактов, основывающиеся на недостаточном количестве данных не позволяющем признать гипотезу достоверной научной теорией. Для проверки достоверности гипотезы проводятся эксперименты, часто сначала с моделями, а затем и с самими объектами. Модель - объект-заместитель объекта, обеспечивающий изучение некоторых свойств оригинала. Модель позволяет упростить проведение исследования некоторых свойств объекта- оригинала. Математическая модель – совокупность математических формул, устанавливающих в общем случае связь между выходными характеристиками (свойствами) объекта моделирования, его параметрами, входными воздействиями и воздействиями внешней среды. Моделирование - замещение одного объекта другим с целью получения информации о важнейших свойствах (характеристиках) объекта - оригинала с помощью объекта-модели (далее заменяется термин объект-оригинал на термин объект, а объект-модель - на модель). Верификация – контроль правильности работы модели на основе сравнения результата моделирования с другими данными, полученными в результате проведения эксперимента или использования других моделей. Интерпретация – истолкование (объяснение) результата исследования математической модели. Основные свойства моделей • Адекватность модели объекту - совпадение результатов моделирования и результатов экспериментов с объектом. Если результаты моделирования подтверждаются и могут служить основой для прогнозирования процессов в исследуемых объектах, то говорят, что модель эквивалентна объекту. Модели должны быть адекватны соответствующим системам или технологическим задачам. • Точность модели – количественная характеристика адекватности, см. также. • Робастность – устойчивость модели к погрешности в исходных данных. • Простота (в трактовке автора) – свойство модели, отражающее отсутствие учета второстепенных факторов для решения рассматриваемой задачи. • Полнота – свойство, заключающееся в учете в математической модели особенностей объекта, существенных с точки зрения поставленной цели исследования. Для решения задачи математическая модель является полной (в трактовке автора), если она позволяет определить с приемлемой точностью все характеристики объекта моделирования, интересующие её пользователя. • Продуктивность (в трактовке автора) свойство модели, отражающее её способность быть использованной для решения широкого класса задач. • Наглядность – свойство модели, заключающееся в том, что при её просмотре пользователю понятен смысл отдельных её элементов. Требования к моделированию • модели должны быть адекватны соответствующим системам или технологическим задачам; • должна обеспечиваться необходимая точность; • должно обеспечиваться удобство работы пользователя – специалиста по технологии или по обработке информации (управлению); • понятный интерфейс управления моделированием; • достаточная скорость работы; • наглядность результатов; • приемлемая стоимость разработки и использования средств моделирования. Подходы к исследованию систем управления Классический (индуктивный) подход – рассматривает систему путем перехода от частного к общему и синтезирует (конструирует) систему путем слияния её компонент, разрабатываемых раздельно. Процесс синтеза систем управления на основе классического подхода представлен на рис. 1. Рис. 1. Процесс синтеза модели на основе классического подхода Реальный объект разбивается на отдельные подсистемы. Эти подсистемы представляют собой выбранные исходные данные Д и поставленные цели Ц, отображающие отдельные стороны процесса моделирования. По отдельной совокупности данных Д ставится цель моделирования отдельной стороны функционирования системы. На базе этой цели формируется некоторая компонента К будущей модели. Совокупность компонент объединяется в модель М. Таким образом, разработка модели М на базе классического подхода означает суммирование отдельных компонент в единую модель, причем каждая из компонент решает свои собственные задачи и изолирована от других частей модели. Поэтому классический подход может быть использован для реализации сравнительно простых моделей, в которых возможно разделение и взаимно независимое рассмотрение отдельных сторон функционирования реального объекта. Отличительные стороны классического подхода: • наблюдается движение от частного к общему, создаваемая модель (система) образуется путем суммирования отдельных ее компонент, • не учитывается возникновение нового системного эффекта. Системный подход предполагает последовательный переход от общего к частному, когда в основе рассмотрения лежит цель, причем исследуемый объект выделяется из окружающей среды. В основе системного подхода лежит рассмотрение системы как интегрированного целого, причем это рассмотрение при разработке начинается с формулировки цели функционирования. Процесс синтеза модели М на основании системного подхода представлен на рис. 2. Рис. 2. Процесс синтеза модели на основе системного подхода Сначала формулируются исходные требования Т к модели системы S на основе: • исходных данных Д, которые известны из анализа внешней системы, • ограничений, которые накладываются на систему сверху либо исходя из возможностей ее реализации, • на основе цели функционирования. На базе этих требований формируются ориентировочно некоторые подсистемы П и элементы Э. Затем осуществляется наиболее сложный этап синтеза – выбор В составляющих системы, для чего используются специальные критерии выбора КВ. Классификация видов моделирования систем В основе моделирования лежит теория подобия, которая утверждает, что абсолютное подобие может иметь место лишь при замене одного объекта другим точно таким же. При моделировании абсолютное подобие не имеет места и стремятся к тому, чтобы модель достаточно хорошо отображала исследуемую сторону функционирования объекта. В зависимости от характера изучаемых процессов в системе все виды моделирования могут быть разделены на детерминированные и стохастические, статические и динамические, дискретные, непрерывные и дискретно-непрерывные (рис. 3). Рис. 3. Классификация видов моделирования систем Детерминированное моделирование отображает детерминированные процессы, т. е. процессы, в которых предполагается отсутствие всяких случайных воздействий. Стохастическое моделирование отображает вероятностные процессы и события. В этом случае анализируется ряд реализаций случайного процесса, и оцениваются средние характеристики, т. е. набор однородных реализаций. Статическое моделирование служит для описания поведения объекта в какой-либо момент времени. Динамическое моделирование отражает поведение объекта во времени. Дискретное моделирование служит для описания процессов, которые предполагаются дискретными, соответственно непрерывное моделирование позволяет отразить непрерывные процессы в системах. Дискретно-непрерывное моделирование используется для случаев, когда требуется выделить наличие как дискретных, так и непрерывных процессов. В зависимости от формы представления объекта (системы) можно выделить мысленное и реальное моделирование. При реальном моделировании используется возможность исследования различных характеристик либо на реальном объекте целиком, либо на его части. Такие исследования могут проводиться как на объектах, работающих в нормальных режимах, так и при организации специальных режимов для оценки интересующих исследователя характеристик (при других значениях переменных и параметров, в другом масштабе времени и т. д.). Реальное моделирование является наиболее адекватным, но при этом его возможности с учетом особенностей реальных объектов ограничены. Разновидностями реального моделирования являются натурное и физическое. Натурным моделированием называют проведение исследования на реальном объекте с последующей обработкой результатов эксперимента на основе теории подобия (научный и производственный эксперименты, комплексные испытания). При функционировании объекта в соответствии с поставленной целью удается выявить закономерности протекания реального процесса. Другим видом реального моделирования является физическое, отличающееся от натурного тем, что исследование проводится на установках, которые сохраняют природу явлений и обладают физическим подобием. В процессе физического моделирования задаются некоторые характеристики внешней среды и исследуется поведение либо реального объекта, либо его модели при заданных или создаваемых искусственно воздействиях внешней среды. Физическое моделирование может протекать в реальном и нереальном (псевдореальном) масштабах времени, а также может рассматриваться без учета времени. В последнем случае изучению подлежат так называемые «замороженные» процессы, которые фиксируются в некоторый момент времени. Наибольшие сложность и интерес с точки зрения верности получаемых результатов представляет физическое моделирование в реальном масштабе времени. Мысленное моделирование часто является единственным способом моделирования объектов, которые либо практически нереализуемы в заданном интервале времени, либо существуют вне условий, возможных для их физического создания. Например, на базе мысленного моделирования могут быть проанализированы многие ситуации микромира, которые не поддаются физическому эксперименту. Мысленное моделирование может быть реализовано в виде наглядного, символического и математического. При наглядном моделировании на базе представлений человека о реальных объектах создаются различные наглядные модели, отображающие явления и процессы, протекающие в объекте. Символическое моделирование представляет собой искусственный процесс создания логического объекта, который замещает реальный и выражает основные свойства его отношений с помощью определенной системы знаков или символов. Под математическим моделированием понимается процесс установления соответствия данному реальному объекту некоторого математического объекта, называемого математической моделью, и исследование этой модели, позволяющее получать характеристики рассматриваемого реального объекта. Рассмотрим другой способ классификации моделей, представленный в виде непрерывного спектра, простирающегося от точных моделей до совершенно абстрактных (рис. 4). Рис. 4. Схема классификации моделей в виде непрерывного спектра Модели, находящиеся в начале спектра, называют физическими или натурными, потому что они внешне напоминают изучаемую систему. Такие макеты выполняются либо в натуральную величину, либо являются уменьшенными моделями объекта в определенном масштабе (масштабированные). Аналоговыми моделями являются модели, в которые свойство реального объекта представляется некоторым другим свойством аналогичного по поведению объекта. Задача иногда решается путем замены одного свойства другим, после чего полученные результаты надо истолковывать применительно к исходным свойствам объекта. Различного рода структурные схемы являются полезными аналоговыми моделями. В так называемых управленческих (деловых) играх человек взаимодействует с информацией, поступающей с выхода вычислительной машины (которая моделирует все другие свойства деловой игры), и принимает решение на основе полученной информации. Решения человека затем снова вводятся в машину в качестве входной информации, которая используется системой. Продолжая процесс усложнения объектов исследования дальше, приходим к машинному моделированию. К математическим (аналитическим), моделям относятся те, в которых для представления процесса или системы используются символы, а не физические устройства. Обычным примером представления систем в этом случае можно считать системы дифференциальных уравнений. Лекция 2. Методы математического моделирования Под математическим моделированием понимается процесс установления соответствия данному реальному объекту некоторого математического объекта, называемого математической моделью, и исследование этой модели, позволяющее получать характеристики рассматриваемого реального объекта. Вид математической модели зависит как от природы реального объекта, так и задач исследования объекта и требуемой достоверности и точности решения этой задачи. Любая математическая модель, как и всякая другая, описывает реальный объект лишь с некоторой степенью приближения к действительности. Математическое моделирование для исследования характеристик процесса функционирования систем можно разделить на аналитическое и имитационное. Аналитический метод моделирования Для аналитического моделирования характерно то, что процессы функционирования элементов системы записываются в виде некоторых функциональных соотношений (алгебраических, интегродифференпиальных, конечно-разностных и т. п.) или логических условий. Аналитическая модель может быть исследована следующими методами: а) аналитическим, когда стремятся получить в общем виде явные зависимости для искомых характеристик; б) численным, когда, не умея решать уравнений в общем виде, стремятся получить числовые результаты при конкретных начальных данных; в) качественным, когда, не имея решения в явном виде, можно найти некоторые свойства решения (например, оценить устойчивость решения). Выделим четыре случая, когда обычно используется этот метод. 1. Для нахождения каждой искомой величины используется, для удобства ручных расчётов, отдельная формула, в общем явном виде связывающая её с исходными данными, причем формула может, как содержать логические условия, так и быть без них. 2. При компьютерных расчетах часто удобнее в выше приведенном случае использовать некоторую совокупность формул содержащих промежуточные результаты. Использование этих двух вариантов предполагает существенное упрощение моделей, что может привести к получению результатов, имеющих неудовлетворительную точность. 3. В тех случаях, когда не удается решить уравнения в общем виде, используются численные методы их решения, позволяющие исследовать более широкий класс систем, получив числовые результаты при конкретных начальных данных. При использовании численных методов целесообразно применение ЭВМ, в виду их трудоёмкости при ручных расчетах 4. Проводится качественное исследование, позволяющее при отсутствии решения в общем виде найти некоторые свойства решения, например, оценить является ли решение устойчивым. Имитационный метод моделирования Алгоритм, реализующий имитационную модель, воспроизводит процесс функционирования реальной модели во времени, имитируя элементарные явления, составляющие процесс, с сохранением их логической структуры и последовательности протекания во времени. Это позволяет по исходным данным получить сведения о состоянии процесса в определенные моменты времени, дающие возможность оценки характеристик (показателей) реальной системы. Представим имитационную модель в виде некоторого алгоритмического преобразования вектора входных параметров X = (x1, …, xn ) в вектор выходных параметров Y = (y1, …, ym): Y = , (1) где – вектор, характеризующий «случайные воздействия» внешней среды. Формулу (1) можно интерпретировать в виде схемы, представленной на рис. 5. Рис. 5. Формальное представление имитационной модели Основные классы задач, которые ставятся перед имитационной моделью: 1. Статистическая оценка выходных параметров (операционных характеристик) модели с заданной степенью точности и надежности. К таким характеристикам можно отнести оценку вероятностей состояний системы, среднюю длину очереди, среднее время обслуживания заявки, среднее время простоя канала обслуживания и т.д. В этом случае необходимо вычислять оценки характеристик (статистики). Данная задача заключается в определении значений оценок вектора Y выходных параметров: (2) К этому же классу задач относятся задачи оценки распределения вероятностей указанных выходных параметров модели. 2. Определение и исследование зависимости между вектором входных параметров модели и вектором выходных параметров, а также статистической значимости этой зависимости. Эта задача решается с помощью методов регрессионного анализа. С позиций формализованного представления эта задача заключается в нахождении функциональной зависимости: Y = A(X). (3) 3. Поиск оптимальных значений выходных параметров модели на некотором допустимом множестве значений входных параметров модели. Это наиболее сложная задача синтеза системы, которая носит оптимизационный характер. Формально в этой задаче нужно найти такие значения параметров X системы, которые оптимизируют заданный критерий качества F(x) работы системы: (4) где B – область допустимых значений параметров X системы. Основные свойства имитационного моделирования 1. Численный метод решения задач. Имитационное моделирование используется, когда нет аналитических способов исследования этой модели. 2. Имитационное моделирование является экспериментом. 3. Имитационное моделирование позволяет исследовать поведение модели, как в определенные моменты времени (статическая имитация), так и в течение продолжительных периодов времени (динамическая имитация). 4. Имитационное моделирование и программное реализация этого моделирования является не разделимыми. 5. Имитационное моделирование в большинстве случаев является стохастическим. Метод Монте-Карло как основа имитационного моделирования В основе исследования стохастических процессов лежит метод Монте-Карло, который определяется как «численный метод решения математических задач при помощи случайных величин». Пример моделирования методом Монте-Карло: одним из самых простых и понятных применений метода Монте-Карло является вычисление площади некоторой произвольной фигуры на плоскости. Это может быть совсем произвольная фигура с криволинейной границей, заданная графически или аналитически. Например, необходимо с помощью метода Монте-Карло оценить площадь плоской фигуры, эллипса S (рис. 6). Для применения метода опишем вокруг эллипса S единичный квадрат. Рис. 6. Решение задачи оценки площади фигуры методом Монте-Карло Идея оценки истинного значения площади, заключается в следующем. Предположим, что каким-либо способом мы равномерно «разбросали» внутри единичного квадрата N случайных точек. Обозначим через N’ число точек, попавших внутрь и на границу области S. Тогда геометрически очевидно, что оценка S’ истинной площади S приближенно равна S’ = N’/ N. Особенности метода Монте-Карло • Простая структура вычислительного алгоритма. В рассматриваемом примере по существу проводился вычислительный эксперимент по «бросанию случайным образом точки» в единичный квадрат. Такой эксперимент имеет два исхода: точка либо попала, либо не попала в область S. Поэтому иногда метод Монте-Карло называют методом статистических испытаний. Конечно, необходимо вычислять координаты равномерно распределенных точек, поскольку от качества этого распределения зависит точность данного метода оценки площади. • При увеличении числа опытов N ошибка оценки площади уменьшается. Эта ошибка, как правило, пропорциональна , где D – некоторая постоянная, а N – число испытаний. Согласно соотношению, чтобы уменьшить ошибку в 10 раз, нужно увеличить объем вычислений N в 100 раз. Типичная относительная точность, достигаемая методом Монте-Карло, составляет 5-10%. Однако одну и ту же задачу можно решать различными вариантами метода Монте-Карло, которым отвечают различные значения D (при помощи моделирования случайных величин c различными распределениями). Как правило, постоянная D равна так называемой выборочной дисперсии оценки. В некоторых задачах при одинаковом объеме испытаний удается значительно увеличить точность, выбрав специальный способ расчета, которому соответствует значительно меньшее значение D. Этапы моделирования В процессе разработки модели можно условно выделить такие этапы описания, как концептуальный, математический и программный. Кроме того, кроме собственно разработки модели необходимо выполнить еще ряд действий, без которых моделирование не может привести к требуемому результату. Рекомендуемый порядок работ в рамках статистического моделирования: 1) создание концептуальной модели. Концептуальная модель – это абстрактная модель, определяющая состав и структуру исследуемой системы, свойства элементов и связей. Строится обычно в словесно- графической форме; 2) подготовка исходных данных. Этот этап включает в себя : • сбор фактических данных (измерения, анализ документов, метод экспертных оценок); • подбор законов распределения случайных величин (по численным значениям параметра строится гистограмма распределения, затем она аппроксимируется кривой, потом эта кривая сравнивается с кривыми плотности распределения различных теоретических законов, выбирается наиболее подходящий из них и проводится оценка степени совпадения эмпирического и теоретического распределения). В случае необходимости на этом этапе возможны аппроксимация функций, описывающих связи между элементами и выдвижение гипотез по значению новых элементов или параметров; 3) разработка математической модели. Создание математической модели преследует две основные цели: дать формализованное описание структуры и процесса функционирования системы для однозначности их понимания; попытаться представить процесс функционирования в виде, допускающем аналитическое исследование системы. Разработка единой методики создания математических моделей не представляется возможной; 4) выбор метода моделирования. Разработанная математическая модель может быть исследована аналитически и статистически. 5) выбор средств моделирования. Рекомендуется следующая последовательность выбора: • применить готовые специальные программы, здесь - их освоение, подготовка данных, анализ результатов. Эти средства должны быть корректными. Является грубейшей ошибкой жертвовать адекватностью модели с целью применения того или иного средства моделирования. Если готовых средств нет, то • применить средства хорошо зарекомендовавших себя пакетов программ, лучше - ориентированных на моделирование. В данном случае придется изучать возможности и порядок работы, готовить данные в специфическом виде; • разрабатывать свое программное средство, используя те или иные среды программирования. 6) проверка адекватности и корректировка модели. Проверка адекватности модели необходима, так как по неверным результатам моделирования могут быть приняты неверные решения. Проверка может производиться путем сравнения показателей, полученных на модели, с реальными, а также путем экспертного анализа. Если по результатам проверки адекватности выявляются недопустимые расхождения между системой и ее моделью, в модель вносят необходимые изменения; 7) проведение экспериментов с моделью. Этот этап связан с выполнением предыдущего этапа, а также с определением необходимой точности и, как следствие, числа прогонов программы модели. Кроме того, рекомендуется не включать в статистику результаты начала моделирования, пока модель не войдет в стационарный режим. Также этот этап связан с получением статистических оценок функционирования системы в результате выполнения программы модели на ЭВМ; анализом и использованием результатов моделирования. Это целиком зависит от того, с какой целью проводилось моделирование. Лекция 3. Аналитическое и имитационное моделирование систем массового обслуживания Анализ большого числа технических систем и процессов, происходящих в них, показывает, что большинство из них может быть представлено в виде моделей массового обслуживания. Основные элементы систем массового обслуживания Схематически система массового обслуживания (СМО) может быть представлена в виде, изображённом на рис. 2.1. Рис. 7. Обобщенная структурная схема однофазной системы массового обслуживания СМО работает следующим образом. Из источника 1 заявки (или требования) поступают в буфер 2, который может иметь ограниченное количество мест ожидания m. Если все места в буфере заняты, то заявки получают отказ и покидают систему, организуя поток отказов. Если время ожидания в буфере превышает заданную величину, то заявки также покидают систему из буфера, организуя поток «нетерпеливых» заявок. Из очереди заявки выбираются в соответствии с некоторым правилом, называемым дисциплиной обслуживания (например, «первым пришел – первым обслужен») и поступают на один из n свободных каналов обслуживания. Обслуженные заявки образуют выходной поток. Теперь более подробно остановимся на формальном представлении всех элементов системы массового обслуживания. Параметры систем массового обслуживания Каждая система массового обслуживания, кроме своей структуры характеризуется численными значениями определенных величин, которые называются параметрами системы. Это внутренние параметры системы и они, как правило, являются исходными характеристиками при моделировании. К основным параметрам СМО относятся следующие: • входящий поток требований (или заявок); • число каналов; • дисциплина обслуживания; • время обслуживания заявки каналом обслуживания; • выходящий поток требований. Входящий (или входной) поток требований Входящий поток представляет собой совокупность требований (или заявок, клиентов), которые поступают в систему и нуждаются в обслуживании. Само требование рассматривается как запрос на удовлетворение какой-либо потребности. Обычно требование отождествляется с его носителем. Примерами входящих потоков служат: поток заданий, поступающих на сервер в сети коллективного пользования, поток клиентов, приходящих в парикмахерскую; больных, поступающих в больницу, поликлинику; приходящие в порт суда и т.д. Входной поток может быть детерминированным (регулярным) или случайным. Регулярный поток представляет собой последовательность событий, разделенных строго одинаковыми интервалами времени (рис. 2.2): Рис. 8. Регулярный входной поток заявок Очевидно, что для регулярного потока математическое ожидание равно интервалу , а дисперсия – нулю. Теория СМО основное внимание уделяет случайным входным потокам, поскольку именно фактор случайности является типичным отражением действительных условий функционирования систем массового обслуживания. Для формального определения случайного входного потока обратимся к рис. 9. Рис. 9. Случайный входной поток заявок Пусть в систему массового обслуживания заявки поступают через случайные интервалы времени i, i = 1, 2, … . Тогда моменты поступления tk каждой k-й заявки определяются по формуле: (1) Обозначим через i промежуток времени между поступлениями i-м и (i + 1)-м событием: (2) Если интервалы i (i = 1, 2, …) независимы между собой, то в этом случае поток событий называется потоком с ограниченным последействием или потоком Пальма. Поток событий называется ординарным, если вероятность P>1(t, t) того, что на малый промежуток времени t (рис. 2.4), примыкающий к моменту времени t, попадет больше одного события, пренебрежимо мала по сравнению с вероятностью P1(t, t) того, что на тот же интервал времени попадет ровно одно событие: P1(t, t) ≫ P>1(t, t). (3) Стационарным потоком событий называется поток, для которого вероятность появления того или другого числа событий на участке времени  зависит лишь от длины этого участка и не зависит от того, где на оси времени взят этот участок. Очевидно, регулярный поток с одинаковыми интервалами между событиями, а также поток Пальма с одинаково распределенными интервалами времени i представляют собой стационарные потоки. Тип входного потока определяется видом распределения случайных интервалов i. Случайные интервалы времени i между наступлениями событий в потоке могут подчиняться различным законам распределения, например, равномерному или нормальному. Однако в подавляющем большинстве работ по теории массового обслуживания рассматривается, как правило, пуассоновский (простейший) поток. Распределение Пуассона имеет важное свойство, которое играет огромную роль в имитационном моделировании: всякий раз, когда количество поступлений требований в систему характеризуется пуассоновским распределением, то интервалы времени между последовательными поступлениями требований распределены экспоненциально, и наоборот. Важной характеристикой потока является его интенсивность, которая определяется как математическое ожидание числа требований, поступающих в единицу времени. Во многих практических задачах физические условия появления требований таковы, что предположения об их ординарности и отсутствии последействия вполне приемлемы. В то же время предположение стационарности внушает большие сомнения, а иногда заведомо ошибочно. Такие потоки называются нестационарными простейшими потоками. Для потоков этого типа вероятность появления k требований за время t зависит не только от величины t, но и от момента t0, который является началом этого промежутка. На рис. 10 дано графическое представление интенсивности  для стационарного и нестационарного потоков. Примером нестационарного потока может быть поток пассажиров в метро. Здесь изменение интенсивности потока связано со временем суток, например утренние и вечерние часы «пик». Рис. 10. Интенсивности  стационарного и нестационарного потоков требований Практические задачи анализа СМО при нестационарных входных потоках можно решать, как правило, только с помощью имитационного моделирования. Разновидности входящего потока. Вид и параметры закона распределения входящего потока определяется характером физических процессов, протекающих в моделируемом объекте. Основываясь на практике имитационного моделирования, считается, что для моделей достаточно использовать следующие распределения входящего потока: • показательное; • распределение Эрланга k-го порядка; • распределение Релея; • нормальное распределение; • равномерное распределение на интервале [a,b]. Входящие потоки, описываемые перечисленными распределениями, должны быть расширены включением входящего потока с групповым поступлением заявок. В последнем случае предполагается, что заявки могут поступать группами, причем промежуток времени между поступлениями групп заявок представляет собой случайную величину с одним из перечисленных выше законов распределения. Число заявок в группе также является случайной величиной со своим законом распределения обычно из того же набора. Число каналов обслуживания Число каналов обслуживания является одной из основных характеристик СМО. Каналом обслуживания называется вся совокупность технических устройств, обеспечивающих обслуживание одного требования или заявки. По числу каналов обслуживания системы подразделяются: • одноканальные системы массового обслуживания; • многоканальные системы массового обслуживания. В свою очередь, многоканальные системы могут состоять из однотипных и разнотипных по производительности приборов. Длительность обслуживания заявки в канале, как правило, является случайной величиной. Для моделирования времени обслуживания обычно используется тот же набор распределений, как и для входного потока. Работа каждого канала характеризуется тем временем, которое затрачивается на обслуживание одной заявки. Время обслуживания является важнейшей характеристикой каждого канала (прибора, аппарата, линии) обслуживания системы и определяет ее пропускную способность. В общем случае это время является случайным, и в теории СМО оно, как правило, имеет экспоненциальное распределение с параметром . Одна из важнейших характеристик канала определяется его надежностью. Будем различать системы с абсолютно надежными каналами и системы с ненадежными каналами. В последних системах, длительность безотказной работы канала является случайной величиной с заданным законом распределения. Кроме того, существуют системы, в которых ненадежные каналы могут быть восстановлены в процессе работы системы, а в другом классе систем каналы не восстанавливаются. Дисциплина обслуживания Дисциплина обслуживания является наиболее существенным признаком классификации систем обслуживания. По этому критерию все системы можно разбить на три большие группы: • системы с отказами; • системы с неограниченным временем ожидания; • системы смешанного типа. В системах с отказами (которые также называются системами с потерями) всякое вновь поступившее требование, застав все каналы занятыми, покидает систему необслуженным. Эти необслуженные требования составляют выходной поток, так называемых, необслуженных требований. Противоположными системами являются такие, в которых требования могут ожидать момента своего обслуживания неограниченное время, т.е. требования «терпеливые». Такие системы классифицируются как системы с ожиданием, и они составляют наиболее многочисленную группу СМО. Системы смешанного типа занимают промежуточное положение между СМО с отказами и СМО с неограниченным временем ожидания. Поступившее в систему смешанного типа требование, застав все приборы занятыми, становится в очередь. Но в ней оно может находиться ограниченное, как правило, случайное время, после чего, не дождавшись обслуживания, покидает ее. Конечно, кроме перечисленных разновидностей СМО на практике могут встретиться и более сложные системы, для исследования которых применяют комбинирование перечисленных типов СМО. В ряде случаев длительность ожидания, как и вообще возможность попасть в очередь на обслуживание, зависит от того, наложены ли ограничения на длину очереди. В соответствии с этим СМО можно подразделить на системы без ограничения на длину очереди и СМО с ограничением по длине очереди. В первом случае заявка может стать в очередь в любой момент, в то время как во втором она вынуждена покинуть систему, если очередь превышает заданную длину в момент прихода заявки или в процессе ожидания. Дисциплина обслуживания – это правило обработки очереди. Основными дисциплинами обслуживания являются такие: • «первым пришел – первым обслужен»; • «последним пришел – первым обслужен»; • случайный выбор заявок из очереди. Существенным признаком, определяющим организацию самой очереди, т.е. дисциплину ожидания является степень равнозначности всех заявок, поступающих в систему. Если заявки не одинаковы по важности, то говорят, что имеет место преимущество или приоритет в поступлении на обслуживание. С этой точки зрения системы разделяются на системы с приоритетами и без приоритетов. Системы с приоритетами в свою очередь делятся на системы с абсолютными и относительными приоритетами. В СМО с абсолютными приоритетами происходит прерывание процесса обслуживания заявки, если в течение этого периода обслуживания поступит заявка с более высоким приоритетом. Такие системы еще называются системами с прерыванием обслуживания. В противоположность им в системах с относительными приоритетами процесс обслуживания заявок не прерывается. Нужно еще добавить, что в системах с прерываниями возможно два случая: прерванная в обслуживании заявка либо вновь становится на обслуживание, либо она выбывает из системы необслуженной до конца. Выходящий поток Выходящий поток может играть весьма важную роль, особенно когда он сам образует входящий поток для других приборов, расположенных последовательно с первыми. Это очень важно при рассмотрении многофазных СМО, которые состоят из последовательно расположенных групп приборов (или одиночных приборов). Входящий поток требований должен обязательно пройти через все последовательно расположенные приборы. Естественно, что этот поток, проходя через каждую группу приборов, изменяется. Изменение происходит при прохождении потока требований через последовательно расположенные приборы, для которых входящим потоком является выходящий поток необслуженных требований на предыдущем приборе (группе приборов). Например, если система состоит из n последовательно расположенных приборов, проверяющих качество продукции, движущейся по конвейеру, на котором она расположена в произвольном порядке, то для i-го прибора (2  i  n) входящим потоком будет поток непроверенной продукции (i-1)-м автоматом. Во всех задачах с последовательно связанными системами обслуживания входящий в i-ю систему поток по своей структуре будет отличаться от потока, входящего в (i + 1)-ю систему обслуживания. Поэтому, если входящий поток простейший, то выходящий поток из этой системы не всегда будет простейшим т.к. ему будет присуще последействие. В свою очередь, наличие последействия будет увеличивать вероятность отказа в обслуживании. Цель исследования систем массового обслуживания Основными задачами массового обслуживания являются задача анализа и задача синтеза. Задача анализа: определение количественных показателей функционирования систем массового обслуживания и их зависимости от структуры собственно системы (ее состава и функциональных связей) и параметров входящего потока. К количественным показателям функционирования относятся такие, как, например, среднее время пребывания заявки в очереди, среднее время занятости канала обслуживания и многие другие. Решение задачи анализа дает возможность найти в системе слабые звенья, определить их влияние на эффективность обслуживания и найти пути их улучшения. Типичным методом анализа сложных систем обработки информации является моделирование их на ЭВМ. Особенно характерно использование метода моделирования на этапе проектирования новой системы, когда представление о её элементах и структурных связях ещё весьма поверхностное, и в моделях они обычно заменяются упрощёнными эквивалентными схемами. Задача синтеза: при заданных характеристиках входного потока требований, времени обслуживания и критерии качества обслуживания дать предложения по структуре системы, которая обеспечит выполнение поставленной перед ней задачей. Эта задача носит оптимизационный характер, когда требуется найти наиболее эффективный вариант системы из множества возможных альтернатив. При этом имитационное моделирование должно быть организовано в виде некоторого поискового процесса. В этом случае особое значение имеют методы планирования имитационного эксперимента. Лекция 4. Количественные показатели функционирования СМО Количественные показатели функционирования СМО — это, по существу, показатели эффективности обслуживающих систем. Под эффективностью обслуживающей системы понимают характеристику уровня (или степени) выполнения этой системой тех функций, для которых она предназначена. Выбор показателя эффективности зависит от той задачи, которая поставлена перед исследователем. Показатели эффективности зависят от трех групп факторов: • 1-я группа факторов включает характеристики качества и надежности системы обслуживания; • 2-я группа состоит из экономических показателей, характеризующих работу системы (ее стоимости, трудовых затрат обслуживающего персонала, убытков, связанных с несвоевременным обслуживанием или отказов в обслуживании, и т.д.); • 3-я группа факторов отражает особенности ситуации, в которой эксплуатируется система (параметры потока требований, ограничения на длину очереди и время ожидания и др.). Модель системы выбирается в зависимости от условий эксплуатации системы и принятого показателя или критерия эффективности. При этом выбранный показатель или критерий должен быть чувствительным к изменению варьируемых параметров СМО. Эффективность систем обслуживания можно характеризовать большим числом различных количественных показателей. Рассмотрим наиболее часто применяемые показатели эффективности СМО. Заметим, однако, что предлагаемый перечень показателей далеко не полный, и при решении практических задач может появиться необходимость в использовании других показателей или их комбинаций. К числу наиболее часто применяемых конкретных показателей эффективности функционирования СМО относятся следующие. Вероятность Pn потери требования в системе. Эта оценка равна вероятности занятости всех n каналов системы и равна вероятности отказа в обслуживании Pотк. Вероятность того, что в системе находятся на обслуживании ровно k требований, равна Pk, ( k = 0, 1, …, n). Это наиболее полная характеристика системы, частными случаями которой являются уже известная вероятность Pn и P0 (вероятность того, что все приборы свободны, т.е. вероятность простоя системы). Среднее число занятых приборов Nз. Характеристика показывает степень загрузки СМО: . (4) Среднее число свободных от обслуживания приборов N0. Показатель прямо противоположный (4): . (5) Коэффициент простоя каналов обслуживания Kп является производным от вышеуказанного показателя: (6) Коэффициент занятости системы Kз определяется аналогично (6): . (7) Среднее время ожидания требований в очереди до начала обслуживания при наличии n каналов в системе (для систем обслуживания с ожиданием): , (8) где ; – условная вероятность того, что время ожидания tож > t при условии, что в момент поступления требования в систему в ней уже обслуживалось k требований. Средняя длина очереди Qср: при k  n, (9) где Pk – вероятность того, что в системе находится ровно k требований. Среднее число требований Kср, находящихся в системе, тесно связано со средней длиной очереди: . (10) Вероятность того, что число требований в очереди, ожидающих начала обслуживания, больше некоторого числа m (этот показатель особенно необходим при оценке возможностей размещения требований при ограниченности времени для ожидания): . (11) Кроме перечисленных критериев при оценке эффективности систем массового обслуживания могут быть использованы экономические или стоимостные показатели. К ним относятся следующие основные показатели. Sобс – стоимость обслуживания каждого требования в системе. Sож – стоимость потерь, связанных с простаиванием требований в единицу времени. Sу – стоимость убытков, связанных с уходом требований из системы без обслуживания. Sk – стоимость эксплуатации каждого k-го прибора системы в единицу времени. Sпk – стоимость единицы времени простоя k-го прибора системы. При выборе оптимальных параметров СМО иногда полезно применять интегральные показатели работы. Например, можно минимизировать функцию Fn потерь n-канальной системы с ожиданием, которая имеет вид: . (12) где Т – интервал времени работы системы. Аналогичный показатель для систем с отказами: . (13) Для смешанных систем массового обслуживания: . (14) При решении некоторых задач целесообразно пользоваться критерием экономической эффективности системы массового обслуживания Есмо: . (15) где с – экономический эффект, полученный при обслуживании каждого требования. Классификация систем массового обслуживания Рис. 11. Классификация систем массового обслуживания В свою очередь, класс СМО с потерями (или с отказами) составляет: • многоканальная однофазная система с отказами из-за занятости каналов (это классическая система Эрланга); • многоканальная многофазная система с отказами. Эти основные типы СМО включают в себя массу вариантов, например • системы с отказами и недостоверным обслуживанием; • системы с отказами и полной взаимопомощью между каналами; • системы с отказами и частичной взаимопомощью между каналами; • системы с отказами, взаимопомощью и отсутствием информации о результатах обслуживания. Класс систем массового обслуживания с ожиданием составляет: • классическая СМО с ожиданием; • СМО с ожиданием и полной взаимопомощью между каналами; • СМО с ожиданием и приоритетом в обслуживании. На практике важное место занимают СМО с различными ограничениями на время пребывания заявки в системе – смешанные СМО: • СМО с ограничением времени пребывания в очереди; • система с ограниченным временем пребывания на обслуживании. Приведенная классификация включает в себя только разомкнутые системы. Моделирование систем массового обслуживания с отказами В качестве элементарной модели принимается модель однофазной СМО с одним входящим потоком и одним каналом обслуживания (рис. 12), который является абсолютно надежным. Если заявка приходит в момент, когда канал занят, то она немедленно получает отказ и покидает систему необслуженной (теряется). Эта модель действительно элементарная т.к. она является самой простой моделью системы обслуживания. Рис. 12. Структурная схема элементарной модели СМО Для имитационного моделирования сначала необходимо определить исходные данные: • вид и параметры распределения времени поступления заявок, т.е. параметры входного потока; • вид и параметры распределения времени обслуживания; • длительность одного прогона модели и количество прогонов модели. Блок-схема алгоритма имитационного моделирования элементарной СМО изображена на рис. 13. Таким образом, элементарная модель соответствует однофазной одноканальной системе обслуживания с отказами. Можно согласиться с тем, что это достаточно простая схема процесса обслуживания, но, несмотря на свою простоту логической структуры, она содержит основные процедуры имитации дискретного стохастического процесса, сбора и статистической обработки информации. Рис. 13. Алгоритм имитационного моделирования элементарной модели СМО Многоканальная СМО с отказами (система Эрланга) Добавив к элементарной модели n параллельно функционирующих каналов обслуживания, получим модель многоканальной СМО с отказами, схема которой показана на рис. 14. Для проведения имитационного моделирования над этой моделью нужно модифицировать блок 3 алгоритма на рис. 13 так, чтобы после поступления очередной заявки последовательно проверялась занятость каналов. При этом, как только будет найден свободный канал, фиксируется номер этого канала и заявка становится на обслуживание. Естественно, что в блоке 1 нужно предусмотреть ввод количества каналов. Рис. 14. Многоканальная модель СМО Такая многоканальная СМО называется системой Эрланга, по имени инженера одной из телефонных кампаний, который впервые получил аналитическую модель такой системы. Программную реализацию многоканальной имитационной модели системы массового обслуживания рассмотрим в виде словесных алгоритмов Пусть для определенности входной поток заявок будет экспоненциальным с интенсивностью , а время обслуживания каждого канала одинаковое и распределено экспоненциально с интенсивностью . Требуется найти оценку вероятности отказа в обслуживании Pотк. Шаг 1. Ввести начальные параметры модели: количество каналов обслуживания: Nкан; длительность прогона: Tпрог; параметр входного потока: ; параметр времени обслуживания: . Установить счетчики: количество отказов: Nотк = 0; моменты освобождения каналов: Tсв(k) = 0 (при k = 1, 2, …, Nкан); счетчик номера требования: i = 0. Шаг 2. Вычислить время поступления в систему очередного требования: Tвх = Tвх + ΔT1, где – экспоненциально распределенная случайная величина с требуемым параметром , а R – базовое случайное число. Шаг 3. Проверить, не исчерпано ли время прогона: если Tвх  Tпрог, то перейти к шагу 10; Шаг 4. Увеличить счетчик количества требований, поступивших в систему: i = i + 1. Шаг 5. Проверить наличие свободного канала обслуживания: если Tвх < Tсв(k), для всех для k = 1, 2, …, Nкан, то Nотк = Nотк + 1 и перейти к шагу 2; иначе зафиксировать номер свободного канала k. Шаг 6. Вычислить момент окончания обслуживания i-й заявки на k-м канале: Tсв(k) = Tсв(k) + ΔT2, где – время обслуживания. Шаг 7. Проверить, не исчерпано ли время прогона: если Tсв(k) > Tпрог, то i = i – 1. Шаг 8. Перейти к шагу 10. Шаг 9. Увеличить значение счетчика количества отказов на единицу: Nотк = Nотк + 1, и перейти к шагу 2. Шаг 10. Вычислить оценку вероятности отказа в обслуживании: Шаг 11. Вывести на печать результаты и закончить моделирование. Статистическая обработка данных имитационного эксперимента Основные задачи обработки данных эксперимента Прежде чем приступать к эксплуатации имитационной модели необходимо ясно представлять себе цель или задачи эксперимента. Нужно различать следующие типичные задачи обработки данных эксперимента. 1. Оценка параметров имитационной модели: математического ожидания, дисперсии, среднеквадратического отклонения и других моментов более высокого порядка. Эти оценки являются определяющими для более общей задачи – оценки распределения вероятностей параметров модели. 2. Проверка статистических гипотез. Сравнение средних и дисперсий различных альтернатив или гипотез. 3. Дисперсионный анализ. Суть дисперсионного анализа заключается в разложении общей вариации (дисперсии) наблюдаемой случайной величины на независимые слагаемые, каждое из которых характеризует влияние той или иной причины или их взаимодействия. 4. Однофакторные эксперименты. Они довольно просты, и основные вопросы, возникающие перед экспериментатором при их проведении, – это вопросы определения размера выборки, задания начальных условий моделирования, а также определение наличия или отсутствия автокорреляции. 5. Корреляционный анализ. Определение важности учета (или значимости) влияния переменных и ограничений, наложенных на эти переменные. Этим экспериментам посвящено большинство книг по планированию экспериментов и анализу их результатов. 6. Регрессионный анализ, основная задача которого заключается в изучении функциональной зависимости между реакцией или откликом модели и ее входными параметрами. 7. Отыскание оптимальных значений параметров модели на некотором множестве допустимых значений. Данный тип экспериментов обычно предполагает использование методов оптимизации для нахождения оптимального решения в ограниченной области параметров. В данном разделе рассматриваются методы определения неизвестных параметров закона распределения по ограниченному числу экспериментов с имитационной моделью. Оценка параметров Статистика имеет дело с данными, подверженными случайной изменчивости, и поэтому эти данные могут описываться законом распределения вероятностей, если они являются выборкой, или более сложными моделями (факторными, регрессионными и т.п.), если данные неоднородны. Эти законы распределения вероятностей и модели содержат неизвестные величины (параметры) – среднее значение, дисперсию, вклады факторов, коэффициенты функциональных зависимостей и т.п. Исследователя обычно интересует либо сами эти параметры, либо некоторые заранее известные функции от них. К сожалению, в силу случайной изменчивости наблюдаемых данных, а также из-за их ограниченного объема, нельзя указать совершенно точное значение параметров. Приходится довольствоваться лишь приближенными значениями. Фундаментальными понятиями статистической теории оценивания являются понятия генеральной совокупности и выборки. Генеральная совокупность обычно интерпретируется как совокупность всех мыслимых (возможных) результатов наблюдений над случайной величиной, которые в принципе могут быть проведены при данных условиях. Содержательный смысл этого понятия состоит в том, что предполагается существование некоторых вполне определенных свойств, неслучайных закономерностей, присущих данной совокупности, т.е. тех свойств, или значений, которые и должны быть выяснены исследователем. Практически эти свойства являются объективным отображением вероятностных свойств изучаемого объекта, которые могут быть охарактеризованы с помощью соответствующих законов распределения вероятностей или связанных с ними числовых параметров. Считается, что указанные свойства не изменяются во времени и поэтому присущие генеральной совокупности неслучайные закономерности сохраняют постоянным свой характер, т.е. являются устойчивыми. Выборка – это конечный набор значений случайной величины, полученный в результате наблюдений (эксперимента). Число элементов выборки называется ее размером или объемом. Выборка называется репрезентативной (представительной), если она достаточно полно характеризует свойства генеральной совокупности. Оцениванием в статистике называется указание приближенного значения интересующего параметра (или функции от некоторых параметров) на основе наблюдаемых (экспериментальных) данных, представленных в виде выборки ограниченного объема. Оценка (или статистика) – это правило вычисления приближенного значения параметра (или функции от некоторых параметров) по наблюдаемым данным. Статистическая обработка результатов моделирования Выходные данные имитационного эксперимента представляющие собой, как правило, массивы случайных чисел, описывают соответствующие операционные характеристики модели. Как известно, исчерпывающей характеристикой случайной величины Х является ее закон распределения вероятностей F(x) – правило, позволяющее определять вероятность попадания этой величины в любую заданную область ее значений. Чтобы найти закон распределения экспериментальным путем, нужно располагать достаточно обширным статистическим материалом: порядка нескольких тысяч опытов (или наблюдений, экспериментов). На практике редко удается собрать такое количество экспериментального материала, а иногда это и не требуется – достаточно определить только оценки некоторых основных характеристик (параметров) закона распределения, таких как математическое ожидание, дисперсию. Поэтому необходимо уметь получать статистические оценки при ограниченных опытных данных. Задачи статистической обработки экспериментальных данных, как правило, решаются в условиях, когда вид закона распределения анализируемой случайной величины не известен. Однако бывают исключения. Так, если вид закона распределения случайной величины известен заранее, то задача статистической обработки упрощается и заключается только в нахождении некоторых параметров закона распределения, которые полностью определяют соответствующий закон распределения. Например, если априори известно, что закон распределения случайной величины Х нормальный (гауссовский), то задача обработки данных сводится к определению двух его параметров: математического ожидания (Mx), – средне квадратического отклонения (x). В некоторых задачах имитационного моделирования вид закона распределения несущественен, а требуется знать только его числовые характеристики (параметры). Задачи такого рода называются задачами параметрической оценки. Следует отметить, что любое значение искомого параметра, вычисленное на основе ограниченного числа экспериментальных данных, всегда будет содержать элемент случайности, а значит и ошибку. Такое приближенное, случайное значение будем называть оценкой параметра. Например, оценкой для математического ожидания случайной величины X может служить среднее арифметическое наблюденных значений в n независимых опытах. При очень большом количестве опытов среднее арифметическое будет с большой вероятностью весьма близко к истинному значению математического ожидания. Если же число опытов n невелико, то замена математического ожидания средним арифметическим приводит к некоторой ошибке. То есть эта ошибка обратно пропорциональна числу опытов. Аналогичная ситуация и с оценками других неизвестных параметров. Математическое ожидание mx случайной величины Х = { x1, x2, …, xn } называется сумма произведений всех n возможных значений случайной величины на вероятности pi этих значений: . (16) В случае гауссовского (нормального) распределения для истинного математического ожидания mx существует его оценка , вычисляемая по выборке объема n случайной величины Х = (x1, x2, …, xn): . (17) Для истинной дисперсии Dx (характеристика рассеивания случайной величины около ее математического ожидания) ее оценка при известном математическом ожидании mx вычисляется так: , (18) где x является средне квадратическим отклонением. В случае неизвестного математического ожидания дисперсию нужно вычислять по формуле: . (19)