Маршрутное такси (Узел QUEUE моделирует очередь транзактов)

Содержание:

Введение

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

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

Работа маршрутного такси – типичная задача имитационного моделирования.

Цель работы – необходимо на основе заданных параметров построить и проанализировать модель, имитирующую работу маршрутного такси.

Исходные данные

На остановку маршрутного такси  при­­­­ходят пассажиры и подъезжают такси. Поток пассажиров распределен по экспоненциальному закону со средним временем 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 помещает узел в определенную точку пространства.

Функция GEOWAYопределяет расстояние между точками A и B по их географическим координатам.

Для данной задачи получен следующий граф (рис.1).

Рис.1. Граф модели

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

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

Узлы 1 и 5 имитируют соответственно очереди пассажиров и такси. Ключ 6 в начале работы модели находится в открытом состоянии (по умолчанию), а ключ 2 закрывается при приходе в очередь 1 первого транзакта-пассажира. Это делается для того, чтобы в узел delet первым вошел транзакт-такси, а не пассажир (иначе пассажир станет «тележкой»).

Как только в delet войдет первый транзакт-такси, ключ 6 закрывается, а ключ 2 одновременно с ним открывается. Теперь выходящие из генератора 6 транзакты-такси стоят в очереди 5, а транзакты-пассажиры заходят в узел delet (идет заполнение такси). Когда в узле delet накопятся 10 транзактов-пассажиров, транзакт-такси перейдет в терминатор (заполненное такси уедет). После этого ключ 6 открывается, чтобы в delet мог зайти следующий транзакт-такси, а ключ 2 в это же время закрывается, чтобы транзакты-пассажиры стояли в очереди 1 до прихода в delet транзакта-такси.

Таким образом, ключи 2 и 6 в модели всегда находятся в противоположных состояниях: если один открыт, то другой закрыт. Тем самым чередуется доступ к узлу delet разных типов транзактов-такси и пассажиров.

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

В результате выполнения программы был сгенерирован следующий код C++:

#include <Pilgrim.h>

forward

{

int fw;

modbeg("nonamed", 109, none, (long)time(NULL), none, none, none,none, 2);

ag("Запросы такси", 101, none, expo, 1, none, none, 103);

ag("Приходы такси", 102, none, norm, 8, 2,7, 10, 104);

network(dummy, dummy)

{

top(103):

queue("Очередь", none, 105);

place;

top(104):

queue("Такси ждет?", none, 106);

place;

top(105):

key("Есть такси?", 107);

place;

top(106):

key("Стоянка свободна?", 107);

place;

top(107):

if( 1 )

{

fw=108;

}

else

if( 1 )

{

fw=105;

}

else

{

fw=106;

}

delet("Вход в такси", none, none, none, none, fw);

place;

top(108):

term("Такси уехало");

place;

fault(123);

}

modend("pilgrim.rep", 1, 8, page);

return 0;

}

Анализ результатов

Результаты моделирования выводятся в виде таблицы.

Были получены следующие результаты:

Расшифруем названия столбцов.

№ узла – смысл очевиден.

Тип узла – смысл очевиден (ag, serv, key, queue, term, creat, delet, proc, dyna, send, direct, attach,manage);

Точка – номер последней точки пространства, в которой находится узел типа creat, delet или proc в момент окончания моделирования;

Загрузка – подсчитывается коэффициент использования транзактами узлов типа serv, key или proc в процентах. Если производятся пространственные перемещения узлов типа proc, creat или delet, то подсчитывается пройденный путь (для пространств типа geo путь считается в километрах). Узел key используется, когда через него проходят транзакты. Для узла attach это - коэффициент использования ресурса.

M[t] среднее – среднее значение времени задержки транзакта в узле или иной интервал времени, зависящий от типа узла:

1) для serv - это среднее время пребывания в узле (оно может быть больше времени обслуживания у неприоритетных транзактов при u=abs, т.е. при наличии приоритетных транзактов и правила абсолютных приоритетов);

2) для queue, send и attach - это среднее время задержки в очереди;

3) для ag - это среднее время между двумя сгенерированными транзактами;

4) для term или delet - это среднее время существования уничтоженных транзактов;

5) для key - это среднее время пребывания в закрытом состоянии;

6) для creat и dynam - всегда нулевое значение;

7) для proc при r=none, r=norm, r=expo или r=unif - это среднее время пребывания в узле (оно может быть больше времени обслуживания транзакта при переводе узла в пассивное состояние);

8) для proc при r=geo или r=dcr - это суммарное время пребывания транзакта в узлах dynam и proc с учетом возможных возвратов транзактов из proc в dynam

C[t] вариации - отношение дисперсии этого интервала к квадрату среднего значения времени задержки (коэффициент вариации, возведенный в квадрат). Для очереди коэффициент вариации равен среднему размеру группы транзактов, приходящих о очередь одновременно (при достаточно большом значении).

Счетчик входов - число транзактов, прошедших через узел, либо число сгенерированных транзактов (для ag или creat), либо уничтоженных (для term или delet). Для key - число выданных команд hold.

Кол.кан. – число каналов в узле.

Ост.тр. - количество транзактов, которые остались в узле в момент завершения моделирования;

Состояние узла в этот момент - состояние узла в момент окончания прогона модели: узел может быть «открыт» или «закрыт» для входа очередного транзакта (узлы serv и key), «активен» или «пассивен» (узел proc).

Сервер открыт, есть в нем есть хотя бы один свободный канал.

Для узлов send и attach в данном поле таблицы указывается остаток и дефицит ресурса (литеры «S» и «D» соответственно).

Заключение

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

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

Список использованной литературы

1. Афанасьев М.Ю., Суворов Б.П. Исследование операций в конкретных ситуациях. - М.: Изд-во МГУ, 1999.
2. Березин Д.А. Компьютерное моделирование систем массового обслуживания. Учебно-методическое пособие. Екатеринбург: Изд-во УрГУ, 2005
3. Варфоломеев В.И. «Алгоритмическое моделирование элементов экономических систем». - М.: Финансы и статистика, 2000г.
4. Емельянов А.А., Власова Е.А. Имитационное моделирование экономических процессов. - М. Московский международный институт эконометрики, информатики, финансов и права. 2002. – 92 с.
5. Кеольтон В., Лод А. «Имитационное моделирование. Классика CS» издание 3-е, 2004г.;
6. Кобелев Б.Н. Основы имитационного моделирования сложных экономических систем. - М.: Дело, 2003.