- •Введение
- •Содержание дисциплины лекции
- •Раздел 1. Основы моделирования
- •Раздел 2. Математическое моделирование
- •Раздел 3. Имитационное моделирование.
- •Раздел 4. Системы массового обслуживания и модели прогнозирования
- •Практические занятия
- •Самостоятельная работа
- •Рекомендуемый библиографический список
- •Саратовский государственный социально-экономический университет кафедра теоретических основ информатики и информационных технологий
- •Рабочая программа
- •Федеральное агентство по образованию
- •Саратовский государственный социально-экономический университет
- •Кафедра теоретических основ информатики
- •И информационных технологий
- •Рабочая программа
- •Учебно-методическая карта дисциплины Форма 1
- •3. Содержание учебной дисциплины
- •Раздел 1. Основы моделирования
- •Раздел 2. Математическое моделирование
- •Раздел 3. Имитационное моделирование.
- •Раздел 4. Системы массового обслуживания и модели прогнозирования
- •Практические занятия
- •Самостоятельная работа
- •1. Компьютерное моделирование как метод научного познания
- •Раздел 1. Основы моделирования
- •Этапы компьютерного моделирования
- •Модели. Разновидности моделирования.
- •Раздел 2. Математическое моделирование
- •Компьютерное математическое моделирование
- •Различные классификации математических моделей
- •1.Программирование математической модели.
- •2.Испытание модели
- •3.Исследование свойств имитационной модели.
- •4.Эксплуатация имитационной модели
- •5.Анализ результатов моделирования
- •1. Детерминированные модели
- •2. Моделирование свободного падения тела
- •3. Модель движения тела, брошенного под углом к горизонту
- •4. Уравнения матфизики
- •5. Классификация уравнений матфизики
- •6. Моделирование процесса теплопроводности
- •Экологические модели
- •Компьютерное моделирование в экологии
- •Модели внутривидовой конкуренции
- •Динамика численности популяций хищника и жертвы
- •Раздел 3. Имитационное моделирование
- •Имитационное моделирование
- •Игра "Жизнь"
- •Динамические модели популяций
- •1. Понятие случайных событий
- •2. Вычисление площадей методом Монте-Карло
- •3. Задача Бюффона
- •4. Модели случайных и хаотических блужданий
- •Раздел 4. Системы массового обслуживания и модели прогнозирования
- •Модели потоков
- •Модели потоков
- •6. Классификация потоков.
- •Марковские системы массового обслуживания
- •Сети систем массового обслуживания
- •1. Моделирование в системах массового обслуживания
- •2. Очередь к одному "продавцу"
- •Прочие методологии
- •Практические занятия
- •Тема 1. Этапы и цели компьютерного математического моделирования
- •Некоторые приемы программирования, используемые при моделировании
- •Основные этапы построения математических моделей. Типовые прикладные результаты решения задач математического моделирования Модель движения системы материальных точек
- •Математические системы. Реализация алгоритма для математических систем Методы численного интегрирования и дифференцирования
- •Динамические системы. Реализация алгоритма для механических систем Модель явлений переноса (теплопроводность, диффузия)
- •Тема 6,7. Динамические системы. Реализация алгоритма для экологических систем
- •Тема 8. Модели физических процессов. Модели радиоактивного распада и цепной реакции ядерного взрыва Моделирование систем с одной степенью свободы
- •Модель двумерного движения материальной точки
- •Модели биологических систем. Модель распространения эпидемий Моделирование автоволновых процессов
- •Моделирование распространения волны
- •Тема 10, Тема 11. Модели биологических систем. Динамики развития популяций Моделирование колебаний связанных осцилляторов
- •Метод Монте-Карло
- •Нахождение площадей методом Монте-Карло
- •6.1.Вычисление кратных интегралов методом Монте – Карло
- •Самостоятельная работа
- •Примеры решения задач
- •Решение задачи 8 методом Монте-Карло
- •И их натуральных логарифмов
- •Задания для самостоятельного решения к теме № 3
- •Задания для самостоятельного решения к теме № 4
- •Задания для самостоятельной работы к теме 5
- •Задания для самостоятельного решения к теме 7
- •Задания для самостоятельного решения к теме 8
- •Задания для самостоятельного решения
- •Задания для самостоятельной работы к теме 9
- •Задания для самостоятельного решения к теме 10-11
- •Компьютерное моделирование в экологии. Общие рекомендации
- •Задания к самостоятельной работе
- •Задание для самостоятельного решения к теме смо
- •Вопросы к зачету
Марковские системы массового обслуживания
Математическое изучение функционирования СМО значительно упрощается, если протекающий в ней случайный процесс является Марковским. В этом случае работа СМО сравнительно легко описывается с помощью аппарата конечных систем обыкновенных линейных дифференциальных уравнении первого порядка, а в предельном режиме (при достаточно длительном функционировании СМО) — с помощью аппарата конечных систем линейных алгебраических уравнений, и в результате удается выразить в явном виде основные характеристики эффективности функционирования СМО через параметры СМО, потока заявок и дисциплины работы СМО.
Случайный процесс, протекающий в СМО, называется Марковским (или процессам без последействия, или процессом без памяти), если вероятность любого состояния СМО в будущем зависит только от ее состояния в настоящем и не зависит от ее состояний в прошлом. Этот процесс назван "Марковским" по имени математика А.А. Маркова, впервые исследовавшего эти процессы.
Марков Андрей Андреевич (1856 - 1922) - известный русский математик, ординарный академик Петербургской академии наук, заслуженный профессор Петербургского университета. Основные исследования А.А. Маркова относятся к теории чисел, теории вероятностей и математическому анализу.
Чтобы случайный процесс был Марковским, необходимо и достаточно, чтобы все потоки событий, под воздействием которых происходят переходы системы из состояния в состояние, были пуассоновскими. Поток событий, обладающий свойствами отсутствия последействия (для любых двух непересекающихся промежутков времени, число событий, наступающих за один из них, не зависит от числа событий, наступающий за другой) и ординарностью (вероятность наступления за элементарный - малый промежуток времени более одного события пренебрежимо мала по сравнению с вероятностью наступления за этот промежуток времени одного события), называется пуассоновским.
Пуассон Симеон (1781 - 1840) - французский математик, механик и физик, профессор Политехнической школы в Париже (с 1806 г.), член института Франции и Бюро долгот (с 1812 г.), член Совета французского университета (с 1816 г.), наблюдатель за преподаванием математики во всех коллежах Франция (с 1820 г.), почетный член Петербургской академии наук (с 1826 г.); получил выдающиеся результаты в области теории рядов, теории неопределенных интегралов, вариационного исчисления, теории вероятностей, математической физики, теоретической механики; предложил (названный его именем) один из важнейших законов распределения случайных величин в теории вероятностей.
В СМО потоками событий являются потоки заявок, потоки "обслуживании" заявок и т. д. Если СМО такова, что хотя бы один из ее потоков не является пуассоновским, то характеристики ее эффективности все же могут быть приближенно оценены с помощью Марковской теории массового обслуживания. При этом, чем сложнее СМО, чем больше в ней каналов обслуживания — тем точнее оказываются приближенные формулы, полученные при предположении выполнимости в СМО Марковских условий. Полезность Марковских моделей мотивируется и тем, что во многих случаях для обоснованных рекомендаций по практическому управлению СМО совсем не требуется знаний точных ее характеристик, а вполне достаточно иметь в своем распоряжении их приближенные значения.
В зависимости от характера потоков СМО можно разделить на Марковские и немарковские.
Под марковской СМО будем понимать систему, в которой все потоки событий, переводящие ее из состояния в состояние, пуассоновские. Если хотя бы один из потоков не является пуассоновским, то СМО будет называться немарковской.
Например, в системах со строго выполняющимся расписанием, с ленточным конвейером и им подобным поток входящих заявок является регулярным и, следовательно, не является пуассоновским.
Напомним, в пуассоновском стационарном потоке П (называемом в этом случае простейшим) случайная величина Т, представляющая собой промежуток времени между любыми двумя соседними событиями, распределена по показательному закону
(t)=e-, (1)
где называется параметром этого закона распределения и представляет собой интенсивность потока П ( Интенсивностью или средней плотностью потока называется среднее число событий в единицу времени).
Если вывод системы S из какого-то ее состояния si происходит под воздействием нескольких простейших потоков, то непрерывная случайная величина T, представляющая собой время пребывания системы (подряд) в данном состоянии si, также распределена по показательному закону (1), в котором - суммарная интенсивность всех потоков, выводящих систему S из данного состояния si.
По числу каналов СМО подразделяют, как уже отмечалось ранее, на одноканальные (когда имеется один канал) и многоканальные, (когда количество каналов п 2). Здесь и далее будем полагать, что каждый канал одновременно может обслуживать только одну заявку и, если не оговорено специально, каждая находящаяся под обслуживанием заявка обслуживается только одним каналом. Многоканальные СМО могут состоять из однородных каналов, либо из разнородных, отличающихся длительностью обслуживания одной заявки. Практически время обслуживания каналом одной заявки Тоб является непрерывной случайной величиной. Однако при условии абсолютной однородности поступающих заявок и каналов время обслуживания может быть и величиной постоянной ( То6=const).
По дисциплине обслуживания СМО подразделяют на три класса:
1. СМО с отказами (нулевым ожиданием или явными потерями), в которых заявка, поступившая на вход СМО в момент, когда все каналы заняты, получает "отказ" и покидает СМО ("пропадает"). Чтобы эта заявка все же была обслужена, она должна снова поступить на вход СМО и рассматриваться при этом как заявка, поступившая впервые. Примером СМО с отказами может служить работа АТС: если набранный телефонный номер (заявка, поступившая на вход) занят, то заявка получает отказ, и, чтобы дозвониться по этому номеру, следует его набрать еще раз (заявка поступает на вход как новая),
2. СМО с ожиданием (неограниченным ожиданием или очередью). В таких системах заявка, поступившая в момент занятости всех каналов, становится в очередь и ожидает освобождения канала, который примет ее к обслуживанию. Каждая заявка, поступившая на вход, в конце концов будет обслужена. Такие СМО часто встречаются в торговле, в сфере бытового и медицинского обслуживания, на предприятиях (например, обслуживание станков бригадой работников).
3. СМО смешанного типа (ограниченным ожиданием). Это такие системы, в которых на пребывание заявки в очереди накладываются некоторые ограничения.
Эти ограничения могут накладываться на длину очереди, т.е. максимально возможное число заявок, которые одновременно могут находиться в очереди.
В качестве примера такой системы можно привести мастерскую по ремонту автомобилей, имеющую ограниченную по размерам стоянку для неисправных машин, ожидающих ремонта.
Ограничения ожидания могут касаться времени пребывания заявки в очереди, по истечению которого она выходит из очереди и покидает систему, либо касаться общего времени пребывания заявки в СМО (т.е. суммарного времени пребывания заявки в очереди и под обслуживанием).
В СМО с ожиданием и в СМО смешанного типа применяются различные схемы обслуживания заявок из очереди. Обслуживание может быть упорядоченным, когда заявки из очереди обслуживаются в порядке их поступления в систему, и неупорядоченным, при котором заявки из очереди обслуживаются в случайном порядке. Иногда применяется обслуживание с приоритетом, когда некоторые заявки из очереди считаются приоритетными и поэтому обслуживаются в первую очередь.
По ограничению потока заявок СМО делятся на замкнутые и открытые (разомкнутые).
Если поток заявок ограничен и заявки, покинувшие систему, могут в нее возвращаться, то СМО является замкнутой, в противном случае — открытой. Классическим примером замкнутой СМО служит работа группы наладчиков в цеху. Станки являются источниками заявок на обслуживание, и их количество ограничено, наладчики — каналы обслуживания. После проведения ремонтных работ вышедший из строя станок снова становится источником заявок на обслуживание.
По количеству этапов обслуживания СМО делятся на однофазные и многофазные системы. Если каналы СМО однородны, т.е. выполняют одну и ту же операцию обслуживания, то такие СМО называются однофазными. Если каналы обслуживания расположены последовательно и они неоднородны, так как выполняют различные операции обслуживания, то СМО называется многофазной. Примером работы многофазной СМО может служить обслуживание автомобилей на станции технического обслуживания (мойка, диагностирование и т.д.).