Федеральноеагентство по образованию
ГОУ ВПО«Нижегородский государственный архитектурно – строительный университет»
Международныйинститут экономики, права и менеджмента
Кафедраинформационных систем в экономике
Курсоваяработа
подисциплине: Математические методы и модели
на тему:
«Имитационноемоделирование группового обслуживания с несколькими этапами и двойной очередью:работа оптового магазина»
Выполнил студент:
Чикунова Е. О.
Проверил:
Прокопенко Н. Ю.
г. Н.Новгород
2010 г.
Оглавление
Введение
1 Имитационноемоделирование
2 Описаниесистемы
2.1 Модельное время
2.2 Классы и объекты
2.3 События и методы
3 Реализациямодели
3.1 Программная реализация
3.2 Построение графиков
3.2.1 Программа gnuplot
3.2.2 Использование программы для построения графиков
4 Анализрезультатов
Списокиспользованной литературы
Введение
В современном мирегарантией эффективной работы любого предприятия служит рациональноеиспользование денежных средств и трудового фактора. Именно поэтому для расчетаэкономического эффекта работы оптового магазина необходимо провестиимитационное моделирование на основании предварительно установленныхзависимостей.
Термин имитационноемоделирование означает, что речь идет о моделях с помощью, которых нельзявычислить или предсказать результат и поэтому с их помощью проводитьсявычислительный эксперимент при заданных исходных данных.
Метод имитационногомоделирования дает возможность широкого использования математического аппаратаи вычислительной техники для исследования хода экономических процессов.
Таким образом, сущностьимитационного моделирования состоит в том, что с помощью ЭВМ воспроизводится поведениеисследуемой системы, а исследователь, управляет ходом процесса и анализируетполучаемые результаты. Поэтому под имитацией следует понимать численный методпроведения на ЭВМ экспериментов с алгоритмами, описывающими поведение системы иопределения интересующих нас функциональных характеристик.
Целью данной курсовойработы является разработка модели группового обслуживания с несколькими этапамии двойной очередью, то есть работа оптового магазина. Основой для разработкимодели в данной курсовой работе является метод имитационного моделирования. Также курсовая работа предполагает создание программы на языке C++, обеспечивающей ввод исходнойинформации, ее обработку, реализацию алгоритма имитации процесса и выдачунеобходимой информации.
1. Имитационное моделирование
Можнодать следующее определение понятия модель: это такое описание, котороеисключает несущественные подробности и учитывает наиболее важные особенности системы. Моделирование же можноопределить как методологию изучения системы путем наблюдения отклика модели наискусственно генерируемый входной поток. К. Шеннон пишет так: «Имитационноемоделирование есть процесс конструирования модели реальной системы и постановкиэкспериментов на этой модели с целью либо понять поведение системы, либо оценить (в рамках ограничений, накладываемыхнекоторым критерием или совокупностьюкритериев) различные стратегии, обеспечивающие функционирование даннойсистемы...» Имитационное моделирование является экспериментальной и прикладнойметодологией, имеющей следующие цели [1]:
· Описание поведения системы;
· Построение теорий и гипотез, которые могут объяснить наблюдаемоеповедение;
· Использование этих теорий для предсказания будущего поведениясистемы, то есть тех воздействий, которые могут быть вызваны изменениямив системе или изменениями способов еефункционирования.
Авторы однойметодологической работы сформулировали основные факторы, влияющие на принятие правильного решения порезультатам моделирования:
· адекватноепонимание решаемой задачи, т. е. если задача не полностью определена и недостаточно четко описана, очень мало шансов, что ее решение принесеткакую-либо пользу. Это фундаментальное утверждение относится ко всем задачам, а не только к моделированию.
· корректная модель. Это первостепенный фактор для техническиили экономически эффективного решения, если брать всю задачу в целом. Ошибки в модели, если они не выявлены,скорее всего, приведут к принятию результатов, основанных на неверной модели.Стоимость такого типа ошибок обычно оченьвысока. Даже если ошибка обнаружена, но это произошло на поздних этапахпроекта, стоимость исправлений включает также и повторное прохождение всехпредшествующих этапов.
· корректнаяпрограмма. Программирование— последний этап разработки, и корректная программа может быть написана толькопо корректной модели. Аргументы в пользукорректности программы такие же, что и для модели.
· планирование эксперимента. Разработка модели и программы должнаотражатьцели, для которых выполняется моделирование. Для получения требуемых ответовпрограмме нужно правильно задать вопросы, то есть спланироватьпоследовательность вычислительных экспериментов с полным пониманием проблемы.
· интерпретациярезультатов. Никакаямоделирующая программа не дает ответа состопроцентной достоверностью. Результаты моделирования получаются наоснове обработки случайных чисел, поэтому для их правильного понимания требуется применение статистическихметодов.
Такимобразом, моделирование — это больше, чем просто программа. Достижение целеймоделирования требует пристального вниманияко всем указанным факторам.
Типовая последовательность имитационного моделированиявключает следующие этапы[1]:
1. Концептуальный:разработкаконцептуальной схемы и подготовка области исходных данных;
2. Математический: разработкаматематических моделей и обоснование методов моделирования;
3. Программный: выбор средств моделирования иразработка программных моделей;
4. Экспериментальный:проверкаадекватности и корректировка моделей, планированиевычислительных экспериментов, непосредственно моделирование, интерпретация результатов.
Имитационноемоделирование на компьютере, в принципе, позволяет проанализировать любую реальную систему произвольнойсложности. Концептуально, промоделировать сложную систему так же легко, как ипростую, разница будет состоять тольков объеме программного кода. Имитационная модель может учесть любой нюансв дисциплине обслуживания всего лишь путем небольшой модификации текстаодной-двух процедур, а в аналитической модели это может потребовать коренной переделки всех уравнений, сделать модель необозримосложной или оказаться вообще невозможным. Этот факт отражает как силу, так ислабость имитационной методологии. С одной стороны, имитационное моделированиедаст метод анализа, применимый в тех случаях, когда математическая модель чрезмерно сложна и позволяет аналитикуполучить более точные результаты. Нос другой стороны, имитационная модель не позволяет глубоко заглянуть в сущностьсистемы, выявить ее «изюминки» и законы, по которым она живет, построитькачественные зависимости между «входом» и «выходом», как это позволяет сделатьматематическая модель, если ее, конечно, удалось решить. То, что при взгляде наматематический результат видно сразу, при имитационном моделировании может быть выявлено только в результате постановкизначительного количества экспериментов (еще говорят «прогонов»)[1].
Главнаяи наиболее очевидная цель имитационного моделирования — выяснить, как повлияют на производительность отдельныеизменения конфигурации системы или увеличение нагрузки на нее. Процессмоделирования включает три фазы. На фазе валидации строитсябазовая модель существующей системы, проверяютсяи обосновываются предположения, лежащие в ее основе. На фазе проектирования модельиспользуется в прогностических целях для предсказания влияния различныхмодификаций на производительность. На фазе верификации реальнаяпроизводительность модифицированной системы сравнивается с результатамимоделирования. Взятые вместе, эти три фазы образуют модельный цикл [1].
Фаза валидации.
Начинается с описания модели и включает выбортех ресурсов и элементов деятельности, которые будут представлены; выявлениеособенностей системы,которые требуют внимания; выбор структуры модели; процедуры расчета необходимыхпоказателей по результатам имитационного эксперимента.
Далее в реально функционирующей системе проводятся замерывходных параметров, которые послужат рабочим материалом для модели, а также замерыпроизводительности,результаты которых будут сравниваться с выходными данными модели для оценки ее точности. Модель проверяется, в результате чегоможет потребоваться внести в нееизменения. Значимые различия между выходными данными системы и моделисвидетельствуют об изъянах модели — какое-то допущение оказалось некорректным,какие-то факторы проигнорированы неправомерно. Но и отсутствие таких различийеще не гарантирует того, что модель сумеет правильно предвидеть влияниеколичественных и качественных изменений всистеме.
Фаза проектирования.
На этой фазе входные параметры меняются в соответствии смодификацией системы,эффективность которой нужно проверить с помощью модели. Это довольно сложный иответственный процесс, ведь необходимо правильносформулировать вопрос дли модели. Результаты затем анализируются, ихотличия от выходных данных исходной модели и представляют собой эффект от модификации системы.
Фаза верификации.
На фазе верификации измерения снимаются с обновленнойсистемы, и снова проводитсясравнение. Производительность системы сравнивается с данными моделирования. Наблюдаемые различия могут объяснятьсядвумя причинами:
· либо присоставлении модели упущены некоторые ее свойства, что дает о себе знать не всегда, а лишь при стечении определенныхобстоятельств;
· либо система отреагировала на изменения совсем не так, какпрогнозировалось в модели.
Кроме того, точность выходных данных модели не может бытьлучше точности, скоторой заданы входные параметры.
Модельный цикл отнюдь не является строго последовательнымпроцессом. Между отдельнымисоставляющими фаз валидации и проектирования могут существовать жесткие зависимости. Может потребоватьсясовместимость между описанием модели, замерами данных и методикой оценкимодели. Достижение такой совместимости и еесогласование с конкретными целями моделирования являются по своейсущности процессами итерационными.[1]
2. Описание системы
В оптовом магазине используется новаяпроцедура обслуживания клиентов. Клиенты, попадая в магазин, определяют покаталогу наименования товаров, которые они хотели бы приобрести. После этогоклиента обслуживает клерк, который идет на расположенный рядом склад и приноситнеобходимый товар. Клиент ожидает дважды, сначала приема заказа, затем еговыполнения. Каждый из клерков может обслуживать одновременно не более шестиклиентов. Время, которое затрачивает клерк на путь к складу, равномернораспределено на интервале от 0.5 до 1,5 мин. Время поиска нужного товара зависит от числанаименовании, которые клерк должен найти на складе. Это времянормально распределено с математическим ожиданием, равным утроенному числуискомых наименований, и среднеквадратичным отклонением, равным одной пятойматематического ожидания. Следовательно, если, например, со склада надо взятьтовар одного наименования, время на его поиск будет нормально распределено сматематическим ожиданием, равным 3 мин. и среднеквадратичным отклонением, равным 36 с. Время возвращения со склада равномернораспределено на интервале от 0.5 до 1,5 мин. По возвращении со склада клерк рассчитываетсясо всеми клиентами, которых он обслуживает. Время расчета с клиентом равномернораспределено на интервале от 1 до 3 мин. Расчет производится в том порядке, в каком кклерку поступали заявки на товар. Интервалы между моментами поступления заявокна товары от клиентов экспоненциально распределены с математическим ожиданием,равным 2 мин Клиентов в магазине обслуживают три клерка. Цель моделирования —определить следующее:
Озагрузку клерков;
Осреднее время, необходимое наобслуживание одного клиента с момента подачи заявки на товар до оплаты счета запокупку;
Осреднее число заявок,удовлетворяемых клерком за один выход на склад.
Продолжительность имитационного прогонасоставляет 1000 мин.
2.1 Модельное время
Так как время в задаче размерное, заединицу модельного времени примем секунд. Равномерное распределение будемгенерировать непосредственно в секундах, а нормальное и экспоненциальное — вминутах, с последующим умножением на 60 и округлением до ближайшего целого.2.2 Классы иобъекты
В задаче описана открытая многоканальнаясистема с неограниченным буфером, имеющая, однако, ряд довольно интересныхособенностей. Обслуживание заявки в канале(клерком) представляет собой многоэтапный процесс с параметром — количествомединовременно обслуживаемых клиентов. Эта дисциплина носит название групповое обслуживание. Таким образом, текущее состояние процесса обслуживания характеризуетсяне одним значением — временем, оставшимся до завершения, а несколькими —номером этапа, временем, оставшимся до завершения этапа, и числом клиентов.Таких этапов четыре — путь на склад, поиск товара, путь обратно, расчет. Напервых трех этапах число клиентов остается постоянным, на четвертом онопостепенно уменьшается до нуля, так как расплатившийся клиент покидает систему.
Интересна здесь также система очередей. Время пребыванияклиента в магазине состоит из двух стадии. Сначала он стоит в общей очереди(назовем ее первичной) и ждет, когда один из клерков обратит на него внимание и примет заказ.Клиенты, находящиеся в первичной очереди, не связаны пока ни с каким клерком, аотносятся как бы ко всему магазину в целом. После приема заказа клиентпереходит в очередь, состоящую из людей, которые сделали заказ и ждутвозвращения «своего» клерка со склада с товаром (назовем ее вторичной). Вторичная очередь соотносится с конкретным клерком, ее длина, согласноусловию задачи, не может превышать шест, а количество вторичных очередей равнотрем — общему количеству клерков. В противоположность этому первичная очередьможет быть только одна и ограничений на длину не имеет. Разумеется, какпервичная, так и любая из вторичных очередей может в течение некоторого временибыть пустой.
Заметим, что именно такая система обслуживания принятасейчас в большинстве магазинов, торгующих компьютерной и оргтехникой, в томчисле и в том, услугами которого при необходимости пользуется автор. Некоторуюаналогию можно провести и с обслуживанием в ресторане, гае клиент тоже сначалаждет прихода официанта, а затем — исполнения заказа, но понятие очереди в этомслучае не столь акцентированное, да и система взаимоотношений официанта склиентом ресторана все-таки несколько сложнее.
Все сказанное свидетельствует в пользу того, что логикуработы клерка и всего магазина в целом надо отделить друг от друга и определитьв разных классах, иначе сам принцип объектного моделирования будет выхолощен.Введем классы Клерк (Clerk) и Магазин (Shop)- Прежде чем перечислять их поля данных, подчеркнем следующееобстоятельство. В условии задачи дано максимальное значение объема группы — шесть. В общем случае можно ограничить и минимальное значение, которое назовем минимальным индексом группы (МИГ)- Смысл новою понятия заключается в то, что свободный клерк неначнет обслуживание клиентов до тех пор, пока длина первичной очереди не станетравна значению МИГ. Если к моменту накоплениянужного количества клиентов свободных клерковнесколько, выбор клерка, начинающего обслуживать эту группу, осуществляетсяслучайным образом. Понятно, что стандартное значение МИГ — единица.
Еще один вопрос —взаимные ссылки между классами. В рассматриваемой системе объекты классов Clerk и Shop не являются равноправными, так как каждый изобъектов класса Clerk входит взону ответственности единственного объекта класса Shop, но не наоборот.Поскольку объект Shop управляет системой в целом, ему необходим доступ к любому объекту Clerk для передачи емуразличных сообщений (например, указание принять заказ). Каждый из клерковотвечает только за себя, и ему ссылка на Shop не нужна, так как всем информационным обменом руководит Shop. Посколькуперекрестных ссылок пет, тип указателя при объявлении поля класса Shop можно указывал, вявном виде (Clerk**), если, конечно, класс Clerk описан в header-файле раньше, чем класс Shop.
Перечислим поля данных класса Clerk.
Неизменяемые поля:
· среднее время нахождения клерка в пути (60с);
· максимальное отклонение от среднего длявремени нахождения клерка в пути (30 с);
· среднее время расчета одного клиента (120с);
· максимальное отклонение от среднего длявремени расчета одного клиента (60 с);
· уникальный номер клерка.
Изменяемые поля:
· вторичная очередь. Моделируется массивом указателейна объекты класса Client. Если клерк свободен, очередь пуста;
· клиент, с которым в данный моментпроизводится расчет. Поле данных имеет смысл только при нахождении клерка в состоянии Расчет;
· текущее число клиентов, у которых принятзаказ и которые ожидают возвращения клерка. Не то же самое, что длина вторичнойочереди, поскольку в процессе расчета клиентов длина очереди меняется. Эго поледанных характеризует именно размер пакета заказов. Равен -1, если клерксвободен;
· время, оставшееся до прибытия клерка насклад. Значение поля данных активно только в состоянии движения на склад затоваром. В любом другом состоянии равно -1;
· время, оставшееся до возвращения клерка сосклада Значение поля данных активно только в состоянии движения со склада стоваром. В любом другом состоянии равно -1;
· время, оставшееся до окончания расчетатекущего клиента. Значение поля данных активно только в состоянии расчетаклиентов. В любом другом состоянии рано -1;
· время, оставшееся до завершения поискатоваров. Значение поля данных активно только в состоянии поиска товаров принахождении клерка на складе. В любом другом состоянии равно -1;
· время, прошедшее с момента принятия заказаПоле данных необходимо для сбора статистики о длительности цикла клерка — отпринятия заказа до расчета последнего клиента. Если клерк свободен, значениеравно -1.
Поля данных класса Shop. Неизменяемые поля:
· количество клерков (3).Для удобства реализации сделано глобальной переменной;
· максимальный объёмодного заказа (6). Для удобства реализации сделано глобальной переменной;
· минимальный индексгруппы (1);
· средняя интенсивностьвходного потока (0,5 заявок в минуту);
· массив указателей наобъекты класса Clerk.
Изменяемыеполя:
· первичная очередьклиентов. Из-за отсутствия ограничений на максимальную длину моделируетсясвязным списком;
· время, оставшееся доприбытия следующей заявки из входного потока;
· текущая длина первичнойочереди (вычисляемое поле).
Отношения дружественности между классамипостроены следующим образом: друзьями класса Client являются Clerk и Shop, другом класса Clerk — класс Shop.2.3 События и методы
Каждому из пяти возможных состоянийклерка соответствует событие, в результате которого он покидает это состояние ипереходит в другое. Каждому событию, в свою очередь, сопоставлен отдельныйметод. Перечислим эти события:
1. Прибытие клерка насклад.
2. Завершение поисказаказанного товара.
3. Прибытие клерка стоваром к ожидающим ею клиентам.
4. Завершение расчетов сочередным клиентом.
5. Принятие заказа уклиентов из первичной очереди.
Подробнее остановимся на реализациипоследнего метода. Если первичная очередь не пуста и ее длина достигла значенияМИГ, объект Shop пытается препоручить как можно больше клиентоводному из свободных клерков. После того как клерк выбран, ему посылаетсясообщение, соответствующее методу 5, с двумя параметрами: указателем напервичную очередь, чтобы клерк мог скопировать часть ее клиентов во вторичную,и количеством клиентов, заказы у которых магазин предписывает принять клерку.Возвращает же он объекту Shop указатель на клиента первичной очереди, которыйтеперь становится в этой очереди первым, то есть на новую голову связногосписка. Первичную очередь Shop продвигает сам. Все эти действия выполняетметод-диспетчер run().
Методы класса Shop:
· прибытие нового клиентаиз внешнего потока и постановка ею в первичную очередь;
· выбор клерка, которыйдолжен принять заказ. Метод выбирает случайным образом одного клерка из числасвободных в данный момент.
3. Реализация модели
3.1 Программнаяреализация
Имитационное моделирование это процесс конструированиямодели реальной системы и постановки экспериментов на этой модели с целью либопонять поведение системы, либо оценить (в рамках ограничений) различныестратегии, обеспечивающие функционирование системы. Имитационное моделированиеявляется экспериментальной и прикладной методологией, которая:
· описывает поведение системы;
· строит теории и гипотезы, которые могутобъяснить наблюдаемое поведение;
· использует эти теории для предсказаниябудущего поведения системы, то есть тех воздействий, которые могут быть вызваныизменениями в системе или изменениями способов ее функционирования.[1]
При выполнении данной программы генерируются числозанятых клерков, среднее время периода занятости клерка, средняя длинапервичной очереди, среднее число клиентов в магазине, среднее время пребыванияклиента в магазине, средний объем одного заказа. Другими словами, вимитационном эксперименте входные данные «пропускаются» через логическуюструктуру, чей ответ «подражает» ответы реальной системы на входные данные. Требуетсясоставить алгоритм, и реализовать его. Для моделирования системы групповогообслуживания с несколькими этапами и двойной очередью (работа оптовогомагазина), был выбран высокоуровневый язык программирования C++ и написана программа на этомязыке, позволяющая в полной мере отразить функционирование системы. Дляпроведения анализа зависимостей некоторых показателей друг от друга былаиспользована программа gnuplot.
3.2 Построениеграфиков
3.2.1 Программа gnuplot
Gnuplot портативная программа для визуализации данных исоздания графиков функций для операционных систем UNIX, IBM OS/2, MS Windows, DOS, Macintosh, VMS, Atariи многих других. Эта программа защищена авторским правом, но свободна дляраспространения.
Gnuplot поддерживает множество видов графиков как двух-, таки трехмерных. Он может рисовать, используя линии, точки, боксы, контуры,векторные поля, поверхности и различный связанный текст.[2]
Gnuplot имеет собственную систему команд, может работатьинтерактивно (в режиме командной строки) и выполнять скрипты, читаемые изфайлов. Также используется в качестве системы вывода изображений в различныхматематических пакетах: GNU Octave, Maxima и других. [3]
Gnuplot поддерживает много различных форматов для выдачи:интерактивные графические терминалы (с мышью и функциями горячих клавиш),прямой вывод на плоттеры и современные принтеры, запись в различные форматыфайлов (eps, fig, jpeg, LaTeX, metafont, pbm, pdf, png, postscript, svg и так далее). Gnuplot легко расширяем для включения новых функций. [2]/>3.2.2 Использованиепрограммы для построения графиков
Для того, чтобы нарисовать график, достаточно указать набор команд втэгах .... Основные команды состоят из задания областиопределения функции (для одномерных графиков это переменная «x», для двухмерных«x», «y»), и команды отрисовки одномерной или двухмерной функции, заданной всимвольном виде. Синтаксис функции интуитивно понятен, «+», «-», «*», «/»обозначают стандартные арифметические операторы (умножение должно быть явным,никаких математических сокращений типа «3x» и т. п.), «**» означает возведениев степень, скобки "(", «)» используются для задания приоритета.
Кроме операторов, есть набор стандартныхматематических функций:
Тригонометрические функции sin, cos, tan, константаpi, и им обратные asin, acos, atan.
Гиперболические функции sinh, cosh, tanh.
Экспонента exp и натуральный и десятичный логарифмы:log и log10 соответственно.
Трехмерные графики рисуются аналогично, нужно задатьдиапазоны для области определения и использовать команду «splot». [4]
4. Анализ результатов
Цифровыеданные, полученные при 1000-минутном моделировании. Усредненные результаты:
· Количествопоступлений – 477;
· Обслуженоклиентов – 460;
· Средне число занятыхклерков – 2,65
· Средняядлительность периода занятости клерка – 11,84 мин;
· Средняя длинапервичной очереди – 1,31;
· Среднее числоклиентов в магазине – 8,55;
· Среднее времяпребывания клиента в магазине – 18,04 мин;
· Средний объемодного заказа – 2,026;
· Среднее времяпребывания в первичной очереди – 18,04-11,84=6,2 мин.
На рис. 1-3 приведеныграфики зависимости от числа клерков, соответственно, загрузки системы,среднего числа клерков и среднего времени пребывания клиента в системе. Изграфиков видно, что оптимальное число клерков – четыре. Дальнейшее увеличениечисла клерков к значимому улучшению показателей функционирования не приводит.Добавление же четвертого клерка все еще позволяет существенно улучшить этипоказатели. Приведем их:
· Средне числозанятых клерков – 3,32
· Средняядлительность периода занятости клерка – 11,78 мин;
· Средняя длинапервичной очереди – 1,192;
· Среднее числоклиентов в магазине – 8,451;
· Среднее время пребыванияклиента в магазине – 16,05 мин;
· Средний объемодного заказа – 1,983;
· Среднее времяпребывания в первичной очереди –
16,05-11,78=4,27 мин.
/>
Рис. 1 Зависимость коэффициентов загрузки от числа клерков
/>
Рис. 2 Зависимость среднего числа клиентов в магазине от числа клерков
/>
Рис. 3 Зависимость среднего времени пребывания клиента в магазине отчисла клерков