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

Оглавление

 

1. ПОСТАНОВКА ЗАДАЧИ

            Служба заказа такси имеет 4 каналa дня одновременного приема заказов по телефону. Интервалы времени между попытками вызова такси распределены по закону Эрланга второго порядка со средним 170 секунд. Абонент затрачивает 20 секунд на набор номера. Время обработки заказа клиента по телефону составляет 2 минуты. Если он застает все каналы заказа занятыми или после соединения выясняет, что очередь на обслуживание превышает 2 заказа (в таком случае заказы не принимаются), то через 20 секунд он повторяет набор. После 9 попыток абонент прекращает набор. Служба заказа имеет в своем распоряжении 10 машин для обслуживания пассажиров. Время, затраченное для проезда к клиенту, зависит от расстояния. Распределение расстояния приведено в табл. Стоимость проезда к клиенту недоплачивается. Скорость движения машины равномерно распределена в интервале 50±8 километров в час. Время обслуживания клиента равномерно распределено в интервале 35±15 минут. Стоимость предварительно заказа составляет 4 рубля, стоимость проезда 1 км равна 70 копеек табл.

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

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

Таблица

Расстояние, км	5	8	9	11	12	20
Вероятность	0,10	0,20	0,25	0,17	0,23	0,05

 

2. АНАЛИЗ ВОЗМОЖНЫХ МЕТОДОВ РЕШЕНИЯ ПОСТАВЛЕННОЙ ЗАДАЧИ

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

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

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

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

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

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

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

3. РАЗРАБОТКА КОНЦЕПТУАЛЬНОЙ МОДЕЛИ

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

• определение и уточнение  характеристик объектов исследования,

• улучшение управления объектами исследования,

• повышение эффективности  использования объектов исследования и т.д.

     Составим структурную схему обслуживающей системы для определения способов взаимодействия составляющих её элементов.

                         

 

 

 

 

 

 

 

 

 

Описание  входных и выходных переменных и  параметров модели.

Входные переменные:

         N₁ – каналы дня одновременного приема заказов по телефону;

         N₂ – количество машин которое имеет в своем распоряжение служба такси;

 

Выходные переменные:

         V₁ – минимальное время выполнения заказа;

         V₂ – максимальное время выполнения заказа;

                    X – экономическая прибыль.

Параметры модели

Интервалы времени  между попытками вызова такси распределены по закону Эрланга второго порядка со средним T₁ – 170 сек;

Т₂  – Время затраченное на набор номера абонентом, 20 сек;

Т₃  – Время через которое абонент повторяет набор номера, 40 сек;

Т₄  – Время обслуживания клиента на машине, 35±15 минут;

Т₅  – Время на обработку заказа клиента по телефону, 120 сек.;

N – Количество заявок в очереди на выполнение, после которого заявки больше не принимаются, 2;

K – Количество попыток которое делает абонент чтобы заказать такси, 9 ;

С – Скорость движения машин такси, 50±8 км/ч ;

S₁ – Стоимость предварительного заказа такси, 4 рубля;

S₂ – Стоимость проезда 1 км, 70 коп.;

S₃ – Заработная плата 1 работника, 15 рублей;

 

 

 

 

 

 

 

Ограничения на изменения величин.

Рассмотрим  ограничения на входные переменные данной модели.

Исходя из условий  задачи, общий штат сотрудников службы такси не должен превышать 

14 человек. Исходя  из этого:

1 £ N₁ £ 13

1 £ N₂ £ 13

4. Выбор программных средств моделирования

Для работы с  системами массового обслуживания (Q-схемой)  в ма-шинной реализации моделей ориентированы следующее языки имитационного моделирования: SIMSCRIPT, SIMULA, GPSS. Немаловажным фактом, определяющим выбор языка моделирования, является их  анализ, где главными критериями выбора того или иного программного средства должны выступить возможности  этого языка, т.е. доступность восприятия и использование, удобство описания процесса функционирования системы, удобство ввода исходных данных моделирования и варьирования структуры, алгоритма и параметров модели, эффективность анализа и вывода результатов моделирования, простота отладки и контроля работы моделирующей программы.

Моделирование с помощью языка  SIMSCRIPT  включает в себя сле-дующие этапы:

а) элементы моделируемой системы S описываются и вводятся с помощью карт определений;

б) вводятся начальные  условия;

в) фиксируются  и вводятся исходные значения временных  параметров;

г) составляются подпрограммы для каждого события;

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

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

Cимула (от SIMUIation LAnguage, т.е. язык моделирования  — специ-альный язык программирования, облегчающий доведение модели  реальной системы до готовой  компьютерной программы) — семейство языков программирования, разработанных в Норвегии. Широкую известность и распространение получили языки Симула-1 и Симула-67. Они базируются на Алголе-60 и содержат его в качестве своего подмножества.

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

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

В язык Симула-67 введено понятие объект, которое  возникло из понятия процесс языка  Симула-1. Под объектом понимается экземпляр  описания класса, имеющий свои собственные локальные данные и действия. В языке есть элементарные операторы, которые позволяют организовать выполнение программы в виде последовательных активных фаз объектов. Такое выполнение называют квазипараллельным. Квазипараллельное выполнение программ дает возможность отойти от обычной схемы решения задачи (в виде последовательности шагов) и представить ее в виде ряда взаимодействующих объектов, получивших название сопрограмм.

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

Идеи, заложенные в языке Симула-67, оказали существенное влияние на языки программирования, которые появились позже. В частности, понятие класс нашло свое воплощение в понятии абстрактные типы данных, а понятие объект -  в объектно-ориентированном программировании, хотя при разработке Симулы не ставилась цель создать объектно-ориентированный язык. (Объектно-ориентированное программирование утвердило свой статус в языке Смолток.) Средствами Симулы-67, помимо языков моделирования, описаны языки работы с базами данных, машинной графики и некоторые другие.

GPSS (General Purpose Simulation System) – общецелевая система моделирования  сложных систем (представляющая  самостоятельную систему программирования), разработанная Джеффри Гордоном в приблизительно в 1960 году  и привнесшая множество важных концепций в каждую из коммерческих реализаций языков компьютерного моделирования дискретных событий, разработанных с тех пор. Первоначально разрабатывалась и поддерживалась компанией IBMВ настоящее время имеются версии различных разработчиков. Система GPSS World, разработанная компанией Minuteman Software (США), – это самая современная версия GPSS для персональных ЭВМ и ОС Windows, является мощной средой компьютерного моделирования общего назначения, разработана для профессионалов в области имитационного моделирования. Это комплексный моделирующий инструмент, охва-тывающий области как дискретного, так и непрерывного компьютерного моделирования, обладающий высочайшим уровнем интерактивности и визуального представления информации.

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

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

 

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

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

GPSS World был разработан, чтобы полностью использовать  возможности вычислительной системы.  Использование механизма виртуальной  памяти позволяет моделям реально достигать размера миллиарда байт. Вытесняющая многозадачность и многопоточность обеспечивают высокую скорость реакции на управляющие воздействия и дают возможность GPSS World одновременно выполнять множество задач. Это также означает, что система моделирования GPSS World может использовать вычислительные возможности, предоставляемые симметричными многопроцессорными архитектурами (SMP).

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

Версия GPSS World включает в себя массу нововведений, позволяю-щих проводить более эффективные исследования и сделать работу с систе-мой максимально простой и удобной для пользователя.

Кроме  версии GPSS World доступна и свободно распространяемая версия  GPSS   World   Student  Version.  Она предназначена для исследования поведения проектируемого устройства при различных условиях его эксплуатации, при различных значениях конструктивных параметров или для расчета определенных параметров его поведения. Полученные в результате значения можно сразу использовать для проведения статистических исследований.

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

При создании объекта  моделирования GPSS World Student  Version создает подробный отчет обнаруженных на этом этапе ошибок. Для каждой ошибки указывается ее положение в тексте (номер строки и столбца), описание ошибки и собственно сам текст ошибочной строки. Также пользователю всегда доступна подробная справка GPSS World Reference Manual, в которой описано практически все, что может понадобиться при создании моделей от общих концепций моделирования и описания параметров всех блоков GPSS до сообщений об ошибках и советов по увеличению производительности моделей.

Основными понятиями  языка  GPSS  World Student  Version являются транзакт, блок, оператор. Транзакт GPSS World Student  Version - это динамический объект, под которым может подразумеваться клиент, требование, вызов или заявка на обслуживание прибором обслуживания. То есть основное назначение GPSS World Student  Version - это  моделирование  систем массового обслуживания, хотя наличие дополнительных встроенных средств позволяет моделировать и некоторые другие системы (например, распределение ресурсов между потребителями). Транзакты в GPSS World Student  Version могут создаваться (вводиться), уничтожаться (выводиться), задерживаться, размножаться, сливаться, накапливаться и т. д. Именно благодаря на-личию транзакта GPSS World Student  Version обладает такой изящностью и простотой. Другим фундаментальным понятием GPSS является понятие "блок". Блок GPSS World Student  Version представляет собой некоторый самостоятельный элемент моделируемой системы. Каждый блок реализует одну или несколько операций над транзактом, группой транзактов или параметрами транзактов, а совокупность блоков составляет моделирующую программу. Таким образом, GPSS World Student  Version имеет блочную структуру и, вообще говоря, легко может быть приспособлен и для структурно-функционального  моделирования  не очень сложных систем. GPSS  World Student  Version достаточно легок в освоении, а наличие в нем функций, переменных, стандартных атрибутов, графики и статистических блоков существенно расширяет его возможности.

Таким образом, можно сделать вывод, что в качестве языка моделирования  для решения поставленных задач  и целей курсовой работы  наиболее удобно использовать программу GPSS World Student Version (далее GPSS).

5. Описание имитационной модели

 Блок диаграммами GPSS:

 

Описание программной  реализации имитационной модели.

Proezd function RN1,D6                     ;функция распределения расстояния

0.1,5/0.3,8/0.55,9/0.72,11/0.95,12/1,20    ;проезда к клиенту

 

EXPDIS function  RN1,C24              ; функция задает пуассоновский поток

0,0/.100,.104/.200,.222/.300,.355/.400,.509

.500,.690/.600,.915/.700,1.200/.750,1.380

.800,1.600/.840,1.830/.880,2.120/.900,2.300

.920,2.520/.940,2.810/.950,2.990/.960,3.200

.970,3.500/.980,3.900/.990,4.600/.995,5.300

.998,6.200/.999,7/1,8

 

INITIAL X$Pribil,0 ;переменная для хранения выручки от такси

INITIAL X$ChPribil,0 ; переменная хранит чистую прибыль

INITIAL X$VremyaMin,0 ; переменная хранит минимальное время выполнения заказа

INITIAL X$VremyaMax,0; переменная хранит максимальное время выполнения заказа

INITIAL X$Per,9 ; переменная для организации цикла

 

Operatori STORAGE 4 ;задаем емкость устройства Operatori

Taksi       STORAGE 10 ; задаем емкость устройства Taksi

 

10 GENERATE ,,,1 ; генерируем звонки абонентов

20 RET    ADVANCE 85,FN$EXPDIS ;

30          ADVANCE 85,FN$EXPDIS; звонки абонентов поступают по закону

40         SPLIT 1,RET; Эрланга второго порядка

50 Label1 ADVANCE 20; абонент набирает номер 20 сек

60           TEST G R$Operatori,0,Label4; проверка заняты ли операторы

70           ENTER Operatori; занимаем оператора   

75           ADVANCE 120 ; время уходящее на обслуживание на клиента

80           TEST LE Q$OceredbTaksi,2,Label2; проверяем очередь заказов

90           ASSIGN 1,1

100 Label3  LEAVE Operatori; освобождаем оператора

110           TEST E  P1,1,Label4; если очередь больше 2 то звоним заново

          

130           QUEUE OceredbTaksi,1; занимаем место в очереди заказов

140           MARK 2

150           ENTER Taksi; заказ уходит на выполнение

160           DEPART OceredbTaksi,1; освобождаем место в очереди заказов

170           ADVANCE (FN$Proezd#(60/Uniform(1,42,58)#60));таксист едет к клиенту

180           ADVANCE 2100,900; таксист выполняет заказ клиента

190           SAVEVALUE Pribil+, (((Uniform(1,20,50)#60)/((60/Uniform(1,42,58))#60))#70+400 ;прибыль от 1 поездки

200           LEAVE Taksi; заказ выполнен

210           TEST NE X$VremyaMax,0,Label8

220 Label10   TEST NE X$VremyaMin,0,Label9

230 Label11   TEST LE MP2,X$VremyaMax,Label5; если время больше чем самое большее предыдущее сохраняем его.

240           TEST GE MP2,X$VremyaMin,Label6; если время меньше чем самое меньшее предыдущее сохраняем его.

 

250 Label7    TERMINATE

          

270           GENERATE 86400; моделируем сутки работы службы такси

280           SAVEVALUE ChPribil,(X$Pribil-(4+10)#1500); подсчет чистой прибыли

290           TERMINATE 1;заканчиваем моделирование

 

300           START 1

 

300 Label2  ASSIGN 1,0

310           TRANSFER ,Label3

 

320 Label4     ADVANCE 40 ; абонент ждет 40 секунд перед следующим звонком

330            TEST G X$Per,1,MPER

340            SAVEVALUE Per-,1

350            TRANSFER ,Label1

360 MPER  TERMINATE

 

370 Label5 SAVEVALUE VremyaMax,MP2; сохраняем максимальное время

380           TRANSFER ,Label7

 

390 Label6 SAVEVALUE VremyaMin,MP2; сохраняем минимальное время

400           TRANSFER ,Label7

 

410 Label8 SAVEVALUE VremyaMax,MP2

420           TRANSFER ,Label10

 

430 Label9 SAVEVALUE VremyaMin,MP2

440           TRANSFER ,Label11

6. ОЦЕНКА АДЕКВАТНОСТИ МОДЕЛИ.

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

Рассмотренный метод не претендует на  абсолютную  точность,  но, тем не  менее,  позволяет примерно  оценить соответствие  модели  реальной ситуации в цеху.

Метод заключается  в  сравнение временных показателей модели.

Метод будет  применен при условии, что:

Количество  телефонных оператор, в службе такси: 4 человека.

Количество  машин, в службе такси: 10 машин.

 

Модель, как должно быть.

 

 

                                                                                

 

 

 

 

 

 

Модель, при прогоне.

                                                                                                                                                                                               

 

 

 

          

 

 

При прогоне  модели с заданными значениями получили что:

Показатели	Модель, как должно быть	Модель, при прогоне
Время затрачиваемое  операторами на прием заказа	120	120
Время затрачиваемое для проезда к клиенту	60/50±8*(5,8,9,11,12,20)*60 MIN= 310    MAX=1714	554
Время затрачиваемое  для выполнения заказа клиента	2100±900	1449

 

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

7. Организация экспериментов с моделью И АНАЛИЗ РЕЗУЛЬТАТОВ.

Цель  исследования – Найти оценку интервала времени выполнения заказа (время от момента заказа такси до момента доставки клиента на место).

Проведем прогон модели с  параметрами:

Количество  телефонных оператор, в службе такси: 4 человека.

Количество машин, в службе такси: 10 машин.

 

                                                                    Отчет №1

 

              GPSS World Simulation Report - Taksi.357.1

 

 

                   Monday, January 17, 2011 13:51:49 

 

           START TIME           END TIME  BLOCKS  FACILITIES  STORAGES

                0.000          86400.000    43        0          2

 

 

              NAME                       VALUE 

          CHPRIBIL                    10003.000

          EXPDIS                      10001.000

          LABEL1                          5.000

          LABEL10                        22.000

          LABEL11                        23.000

          LABEL2                         29.000

          LABEL3                         11.000

          LABEL4                         31.000

          LABEL5                         36.000

          LABEL6                         38.000

          LABEL7                         25.000

          LABEL8                         40.000

          LABEL9                         42.000

          MPER                           35.000

          OCEREDBTAKSI                10009.000

          OPERATORI                   10007.000

          PER                         10006.000

          PRIBIL                      10002.000

          PROEZD                      10000.000

          RET                             2.000

          TAKSI                       10008.000

          VREMYAMAX                   10005.000

          VREMYAMIN                   10004.000

 

 

LABEL              LOC  BLOCK TYPE     ENTRY COUNT CURRENT COUNT RETRY

                    1    GENERATE             1             0       0

RET                 2    ADVANCE            498             0       0

                    3    ADVANCE            498             1       0

                    4    SPLIT              497             0       0

LABEL1              5    ADVANCE            505             0       0

                    6    TEST               505             0       0

                    7    ENTER              504             0       0

                    8    ADVANCE            504             0       0

                    9    TEST               504             0       0

                   10    ASSIGN             312             0       0

LABEL3             11    LEAVE              504             0       0

                   12    TEST               504             0       0

                   13    QUEUE              312             0       0

                   14    MARK               312             3       0

                   15    ENTER              309             0       0

                   16    DEPART             309             0       0

                   17    ADVANCE            309             3       0

                   18    ADVANCE            306             7       0

                   19    SAVEVALUE          299             0       0

                   20    LEAVE              299             0       0

                   21    TEST               299             0       0

LABEL10            22    TEST               299             0       0

LABEL11            23    TEST               299             0       0

                   24    TEST               293             0       0

LABEL7             25    TERMINATE          299             0       0

                   26    GENERATE             1             0       0

                   27    SAVEVALUE            1             0       0

                   28    TERMINATE            1             0       0

LABEL2             29    ASSIGN             192             0       0

                   30    TRANSFER           192             0       0

LABEL4             31    ADVANCE            193             0       0

                   32    TEST               193             0       0

                   33    SAVEVALUE            8             0       0

                   34    TRANSFER             8             0       0

MPER               35    TERMINATE          185             0       0

LABEL5             36    SAVEVALUE            6             0       0

                   37    TRANSFER             6             0       0

LABEL6             38    SAVEVALUE            2             0       0

                   39    TRANSFER             2             0       0

LABEL8             40    SAVEVALUE            1             0       0

                   41    TRANSFER             1             0       0

LABEL9             42    SAVEVALUE            1             0       0

                  43    TRANSFER             1             0       0

 

 

QUEUE              MAX CONT. ENTRY ENTRY(0) AVE.CONT. AVE.TIME   AVE.(-0) RETRY

OCEREDBTAKSI        3    3    312     40     1.976    547.329    627.819   0