Файл: Маршрутное такси (Узел QUEUE моделирует очередь транзактов).pdf
Добавлен: 29.06.2023
Просмотров: 78
Скачиваний: 3
Введение
В современном мире мы повсюду сталкиваемся с системами массового обслуживания. Это могут быть билетные кассы, станки на производстве или даже экзамены. Как часто прибегая в кассу, мы слышали, что рабочий день уже окончен, хотя на часах есть еще пять минут. Обидно, но интересно узнать, почему это происходит. И как определить руководителю предприятия, сколько станков нужно, чтобы справиться с работой, при минимуме простоев? Это и есть задача имитационного моделирования СМО.
Цели проведения имитационных экспериментов могут быть самыми различными – от выявления свойств и закономерностей исследуемой системы, до решения конкретных практических задач. С развитием средств вычислительной техники и программного обеспечения, спектр применения имитации существенно расширился в сфере экономики. В настоящее время ее используют как для решения задач внутрифирменного управления, так и для моделирования управления на макроэкономическом уровне.
Работа маршрутного такси – типичная задача имитационного моделирования.
Цель работы – необходимо на основе заданных параметров построить и проанализировать модель, имитирующую работу маршрутного такси.
Исходные данные
На остановку маршрутного такси приходят пассажиры и подъезжают такси. Поток пассажиров распределен по экспоненциальному закону со средним временем 1 мин, поток такси – по нормальному закону со средним временем 8 мин и среднеквадратичным отклонением 2,7 мин. Если пришедший пассажир не обнаруживает стоящего такси, он встает в очередь. Если такси, имеющее 10 посадочных мест, подъехало на пустую остановку, оно ждет пассажиров и уезжает после того, как будут заполнены все места. Если подъехавшее такси застает на остановке другое такси, оно встает в очередь такси.
Необходимо смоделировать процесс работы магазина на протяжении 18 ч и определить:
- средний размер очереди пассажиров,
- средний размер очереди такси,
- среднее время ожидания пассажирами приезда такси,
- среднее время ожидания пассажиром отправления такси,
- среднее время ожидания посадки пассажиров подъехавшим такси,
- среднее нахождения такси на остановке.
Существующие подходы к моделированию экономических процессов
Математическое моделирование экономических процессов и последовательное установление логических связей для обеспечения возможности наблюдения, контроля и управления ими, является наиболее эффективным средством для решения различных проблем. Существующие математические методы и модели могут позволить решать задачи большей размерности и учитывать широкий перечень показателей и факторов влияния, а время решения задач значительно сокращается с применением компьютеров. Кроме того, в ряде сложных задач не всегда может быть получено оптимальное решение. Речь может идти только о приближении к этому решению.
В качестве средств, применяемых наиболее часто для построения математических моделей некоторых отдельных процессов в экономике, можно рассматривать методы линейного, динамического и целочисленного программирования, теории массового обслуживания, теории графов, сетевого планирования. Они используются для моделирования задач перевозки грузов, оптимизации плана продажи и покупки товаров, назначения и распределения ресурсов, анализа устойчивости коммерческой деятельности предприятия и других.
Методы линейного программирования позволяют описать некоторый набор хорошо исследованных экономических задач, таких как: планирование товарооборота; размещение розничной торговой сети города; планирование капиталовложений; оптимизация межотраслевых связей торговли. В задачах линейного программирования критерий эффективности и функции в системе ограничений линейны. Если содержательный смысл требует получения решения в целых числах, то такая задача является задачей целочисленного программирования. В задачах параметрического программирования целевая функция или функции, определяющие область возможных изменений переменных, зависят от некоторых параметров. Если эти функции носят случайный характер, то имеем задачу стохастического программирования. Если в задаче математического программирования имеется переменная времени, а критерий эффективности выражается через уравнения, описывающие протекание операций во времени, то такая задача является задачей динамического программирования.
Теория массового обслуживания рассматривает разнообразные процессы в экономике, как процессы удовлетворения каких-либо запросов и заказов. При всем разнообразии эти процессы имеют общие черты: требования на обслуживание нерегулярно (случайно) поступают в канал обслуживания и в зависимости от его занятости, продолжительности обслуживания и других факторов, образуют очередь требований. Данная теория изучает статистические закономерности поступления требований и на этой основе вырабатывает решения, то есть такие характеристики, при которых затраты времени на ожидание в очереди, с одной стороны, и на простой каналов обслуживания - с другой, были бы наименьшими. Всю систему производства и потребления товаров можно трактовать как систему массового обслуживания, где встречаются люди (клиенты) и товары.
Теория графов - математическая теория, содержание которой формулируется двояко в зависимости от трактовки ее исходного понятия граф: теоретико-множественной или геометрической. В первом случае предметом теории являются графы как некие объекты, определяемые двумя множествами - множеством элементов и множеством бинарных отношений между ними. Во втором случае - свойства геометрических схем (графов), образованных множеством точек и соединяющих их линий. В обоих случаях главное понятие теории - граф, изучаемый как абстракция, независимо от его содержания. Обнаруженные соотношения, закономерности находят применение в самых различных областях экономики. С их помощью можно решать задачи по построению наилучшего плана перевозок продукции от поставщика к потребителям, вырабатывать маршруты различных перевозок, рассчитывать наилучшее распределение рабочих по машинам на производстве и так далее.
Сетевое планирование и управление применяется в экономике для управления процессами, включающими в себя большой набор операций, и основано на использовании ЭВМ и сетевых графиков. С помощью сетевого графика компьютер может произвести анализ состояния процесса в каждый заданный момент времени, определить последовательности работ, которые могут задержать выполнение плана к намеченному сроку (критический путь), и, таким образом, "посоветовать" руководству оперативно принять необходимые меры. Система сетевого планирования ориентирована на какой-либо один критерий: время, стоимость работ и так далее. Реальные сетевые графики содержат сотни и даже тысячи работ и событий. Их анализ возможен только с помощью ЭВМ. В этих условиях сам график теряет преимущество наглядности и тогда применяется цифровое представление сети. Важно, что методы расчетов по сетевым графикам в своей основе стандартны, что позволяет вести расчеты только для однотипных экономических объектов или процессов. Поэтому, сетевое планирование и управление применяется в сочетании с другими экономико-математическими методами, например, теорией массового обслуживания.
Наиболее часто для решения экономических задач применяют аналитические технологии, основанные на методах оптимального управления, решения дифференциальных уравнений и так далее. Для того, чтобы они были применимы, необходимо, чтобы данная задача полностью описывалась определенной детерминированной моделью. В таком случае модель дает точный ответ и показывает свою эффективность.
На практике часто встречаются задачи, связанные с наблюдением случайных величин - например, задача прогнозирования курса акций. Для подобных задач не удается построить детерминированные модели, поэтому применяется вероятностный подход. Такого рода методы предполагают, что известна некоторая вероятностная модель задачи. Например, в задаче прогнозирования курса можно предположить, что завтрашний курс акций зависит только от курса за последние два дня. Если это верно, то наблюдения курса в течение нескольких месяцев позволяют достаточно точно оценить коэффициенты этой зависимости и прогнозировать курс в будущем.
Выбор и обоснование выбранной модели
Задача является задачей массового обслуживания, поэтому наиболее предпочтительный способ ее решения – имитационное моделирование.
Многие экономические системы относятся к системам массового обслуживания. На входе экономической системы имеются заявки на производство товаров или оказание услуг. Целью функционирования экономических систем является получение прибыли. Обслуживание заявки состоит в ее выполнении, то есть в преобразовании в выходную продукцию предприятия, которая далее преобразуется в прибыль.
Имитационные модели СМО имитируют обслуживание потока заявок.
Имитационная модель
Для построения имитационной модели будет использована программа Piligrim.
Схема имитационной модели представляет собой направленный граф, вершины которого представляют собой компоненты элементарных процессов, а дуги определяют направление потоков заявок.
В системе имитационного моделирования PILGRIM граф модели описывает взаимодействия дискретных и непрерывных компонент имитационной модели и представляет собой стохастическую сеть.
Каждый узел графа - это ветвь моделирующей программы[2].
Непрерывные компоненты представляют собой разностные уравнения, причем каждый очередной интервал (или шаг) интегрирования - это отрезок времени между двумя ближайшими событиями в стохастической сети.
Одновременность моделирования всех компонент системы имитируется с помощью единой службы модельного времени.
Основной динамической единицей любой модели, работающей под управлением имитатора, является транзакт.
Транзакт - это формальный запрос на какое-либо обслуживание, например сигнал о загрязнении какого-то пункта местности, телеграмма, поступающая на узел коммутации сообщений, проба загрязненной почвы, ожидающая соответствующего анализа и т.д. Пути «миграции» транзактов по графу определяются логикой функционирования дискретных компонентов модели.
Узлы графа представляют собой центры обслуживания транзактов. В узлах транзакты могут задерживаться, обслуживаться, порождать семейства новых транзактов, уничтожать другие транзакты.
Вид обслуживания транзакта определяется типом узла.
Существуют следующие типы узлов:
Узел-генератор транзактов AG. Предназначен для создания транзактов имитационной модели. Транзакты генерируются по одному через определенные пользователем промежутки времени.
Узел SERV - это обслуживающий прибор (сервер), осуществляющий какое-либо обслуживание транзактов в течение модельного времени, отличного от нуля. С точки зрения имитационной модели обслуживание заключается в задержке транзакта на заданный промежуток времени.
Узел QUEUE моделирует очередь транзактов.
Узел TERM удаляет из модели входящий в него транзакт и фиксирует время его существования, начиная с момента выхода этого транзакта из генератора.
Узел KEY - клапан или ключ - работает в модели по принципу «шлагбаума».
Узел CREAT предназначен для создания нового семейства транзактов.
Узел DELET предназначен для уничтожения группы транзактов, принадлежащих семействам из заданного диапазона;
Узлы SEND и DIRECT моделируют работу с бухгалтерскими счетами.
Узлы ATTACH и MANAGE Предназначены для моделирования динамики использования материальных ресурсов, необходимых для работы в моделируемых процессах.
Узел PROC представляет собой специальную функцию моделирования транзактно-управляемого непрерывного процесса.
Узел DYNAM предназначен для моделирования обслуживания транзактов в очереди с динамическими пространственно-зависимыми приоритетами.
Для построения модели необходимо знать следующие функции [4, стр.56].
Функция INTERRUPT выполняет прерывание модели. После выполнения этой функции в каком-либо узле работа модели прекращается, а экспериментатор может исследовать полученные результаты.
Функция CHEG перенастраивает генератор транзактов AG на новые значения параметров.
Функция RELS открывает узел-клапан KEY. После выполнения RELS клапан принимает состояние «открыт», если до этого он был закрыт.
Функция HOLD закрывает узел-клапан KEY. После выполнения HOLD клапан принимает состояние «закрыт», если до этого он был в открытом состоянии.
Функция ACTIV переводит процесс (узел типа PROC) в активное состояние, если он был пассивен.
Функция PASSIV переводит процесс (узел типа PROC) в пассивное состояние, если он был активен.
Функция SUPPLY изменяет объем ресурса, имеющегося на складе ATTACH.
Функция DETACH возвращает ресурс обратно на склад.
Функция ASSIGN ассигнует на счет SEND денежные средства.
Функция FREED изгоняет уничтожающий транзакт из узла DELET.
Функция SEWT помещает текущий транзакт в определенную точку пространства.
Функция SEWK помещает узел в определенную точку пространства.