Алгоритм Хаффмена

Содержание

Введение

1. Построение концептуальной модели и её формализация

2. Алгоритм функционирования системы

2.1 Алгоритмизация модели и её компьютерная реализация

2.2 Интерпретация результатов моделирования

Заключение

Список литературы

Введение

Задачей данной контрольной работы является построение модели работы склада готовой продукции.

На склад готовой продукции предприятия каждые 5 ± 2 мин поступают изделия типа А партиями по 500 штук, а каждые 20 ± 5 мин - изделия типа В партиями по 2000 штук. С интервалом времени 10 ± 5 мин к складу подъезжают автомашины, в каждую из которых надо погрузить по 1000 штук изделий типа А и В. Погрузка начинается, если изделия обоих типов имеются на складе в нужном количестве, и продолжается 10 ± 2 мин. У склада одновременно могут находиться не более трех автомашин, включая автомашину, стоящую под погрузкой. Автомашины, не нашедшие места у склада, уезжают с его территории без груза.

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

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

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

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

1. Построение концептуальной модели и её формализация

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

Формализуя реальную систему с помощью Q-схемы, необходимо построить структуру такой системы.

Элементы структуры: И - источник; Н - накопитель; К - канал.

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

На рис.1 показана структурная схема погрузки готовой продукции в автомашины. На рис.2 структура системы в символике Q-схем.

Рис.1. Структурная схема погрузки готовой продукции.

Рис.2. Структурная схема в символике Q-схем.

Обозначения, применяемые на рис.2:

И1 - источник, имитирующий поступление изделий типа А на склад.

И2 - источник, имитирующий поступление изделий типа В на склад.

И3 - источник, имитирующий поступление автомашин к складу.

Н1 - накопитель, имитирующий количество изделий типа А, находящихся на складе.

Н2 - накопитель, имитирующий количество изделий типа В, находящихся на складе.

Н3 - накопитель, имитирующий количество автомашин, находящихся у склада.

К - канал, имитирующий погрузку продукции в автомашины.

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

Кл2 - клапан, контролирующий чтобы количество автомашин, одновременно находящихся у склада, не превышало трёх, включая автомашину, стоящую под погрузкой.

Кл3 - клапан, контролирующий, чтобы автомашина не подъезжала под погрузку пока на складе не наберется 1000 штук продукции каждого типа.

2. Алгоритм функционирования системы

Из Источника 1, каждые 5±2 мин поступают изделия типа А партиями по 500 штук в Накопитель 1, а из Источника 2, каждые 20±5 мин в Накопитель 2 поступают изделия типа В партиями по 2000 штук. Из Источника 3 в Накопитель 3, ёмкость которого равна трём, с интервалом 10±5 мин поступают автомашины для погрузки, осуществляемой через Канал, где погрузка идет в течении 10±2 мин. Автомашины не нашедшие места в Накопителе 3 уезжают без груза.

Параметры системы:

.Количество фаз - LФ=1.

2.Количество каналов - LК=1.

.Количество накопителей - LН=3.

.Ёмкость накопителей - LН1=?; LН2=?; LН3=3.

Переменные модели:

1.tpr1 - время поступления изделия типа А.

2.tpr2 - время поступления изделия типа В.

3.tob - время окончания обслуживания канала.

4.tok - время окончания моделирования.

5.t - текущее время.

6.nak1 - состояние накопителя 1 в текущий момент.

7.nak2 - состояние накопителя 2 в текущий момент.

8.nak3 - состояние накопителя 3 в текущий момент.

9.k - состояние канала в текущий момент.

10.tn - массив моментов особых состояний.

11.nob - количество загруженных автомашин.

12.nnb - количество незагруженных автомашин.

2.1 Алгоритмизация модели и её компьютерная реализация

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

Существует три типа моделирующих алгоритма:

·Детерминированный;

·Синхронный;

·Асинхронный.

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

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

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

После запуска программы моделирования процесса функционирования склада готовой продукции появляется окно (рис.3), в котором содержатся входные и выходные данные, а также таблица состояний. По умолчанию введены исходные данные, представленные в задании. Для того чтобы смоделировать систему функционирования склада нужно ввести входные данные и нажать кнопку "Моделировать". Листинг программы представлен в приложении №2.

Рис. 3. Интерфейс программы моделирования процесса функционирования склада готовой продукции.

2.2 Интерпретация результатов моделирования

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

алгоритм параметр формализация модель

Рис. 4. Результаты проведенных экспериментов.

Для более удобного просмотра результатов занесем их в таблицу:

Номер экспериментаЧисло машин, уехавших без грузаСреднее число изделий типа А, хранящихся на складеСреднее число изделий типа В, хранящихся на складеМаксимальное число изделий типа А, хранящихся на складеМаксимальное число изделий типа В, хранящихся на складе10578045289000700020211494640004000321461225225005000421988149540005000503053201865005000621741286045007000Среднее значение12689,52349,85083,35500

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

Заключение

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

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

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

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

Список литературы

1.Конспект лекций по дисциплине "Моделирование систем".

2.Н.Н. Мухин, Е.Г. Степанова. Методическое пособие по дисциплине "Моделирование систем".

.С.И. Бобровский. Delphi7 - учебный курс. "Питер", 2010.

Больше работ по теме: