Разработка программы моделирования СМО

Реферат

программа массовый обслуживание моделирование Цель работы — изучить технологию разработки и тестирования программного обеспечения в среде Visual Studio на примере создания демонстрационной программы моделирования СМО, изучить и реализовать аналитические и имитационные методы моделирования СМО с разными дисциплинами обслуживания заявок.

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

Основные конструктивные и технико-эксплуатационные показатели: визуализация процесса моделирования, надежность, удобство работы, интуитивно понятный интерфейс.

Программная разработка может использоваться без ограничений при обучении студентов различных технических специальностей при изучении курса «Моделирование систем массового обслуживания».

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

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

Решением подобных задач занимается теория систем массового обслуживания. Под системой массового обслуживания (СМО) понимают динамическую систему, предназначенную для эффективного обслуживания потока заявок (требований на обслуживание) при ограничениях на ресурсы системы.

В теории систем массового обслуживания (СМО) обрабатываемую заявку называют требованием. В общем случае под требованием понимают запрос на удовлетворение некоторой потребности, например, разговор с абонентом, посадка самолета, покупка продуктов, получение материалов на складе.

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

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

В общем, модели СМО очень распространены и применяются во многих сферах деятельности человека и реализуются при помощи вычислительных систем.

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

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

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

1. Обзор методов моделирования разомкнутых систем массового обслуживания

1.1 Теория моделирования

1.1.1 Основные определения и понятия

Теория моделирования — теория замещения объекта-оригинала его моделью и исследования свойств объекта на его модели.

Моделирование — метод исследования, основанный на замене исследуемого объекта-оригинала его моделью и на работе с ней (вместо объекта) [6, 14].

Модель (объекта — оригинала) (от лат. modus — «мера», «объем», «образ») — вспомогательный объект, отражающий наиболее существенные для исследования закономерности, суть, свойства, особенности строения и функционирования объекта-оригинала.

Когда говорят о моделировании, обычно имеют в виду моделирование некоторой системы.

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

При моделировании систем используют два подхода: классический (индуктивный), сложившийся исторически первым, и системный, получивший развитие в последнее время [6, 14].

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

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

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

1.1.2 Основные методы моделирования

Методы моделирования можно классифицировать на три основные группы: аналитические, численные и имитационные [7, 14, 16].

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

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

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

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

1.2 Элементы теории массового обслуживания, применяемые при моделировании систем

1.2.1 Основные определения и понятия

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

Первые задачи теории массового обслуживания (ТСМО) были рассмотрены сотрудниками Копенгагенской телефонной компании, датским ученым А. К. Эрлангом (1878 г. — 1929 г.) в период между 1908 и 1922 гг. Эти задачи были обусловлены стремлением упорядочить работу телефонной сети и разработать методы, позволяющие заранее повысить качество обслуживания потребителей в зависимости от числа используемых устройств. Оказалось, что ситуации, возникающие на телефонных станциях, являются типичными не только для телефонной связи. Работа аэродромов, работа морских и речных портов, магазинов, библиотек, радиолокационных станций и комплексов, терминальных классов, вычислительных систем и сетей, автоматизированных систем управления и т. д. может быть описана в рамках ТСМО.

Классификация СМО. Выделяют различные признаки классификации СМО: системы с отказами и системы без отказов; замкнутые и разомкнутые; многоканальные и одноканальные; с равными (с точки зрения порядка обслуживания) заявками и с приоритетными заявками.

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

В замкнутых СМО в системе циркулирует определенное конечное число заявок (конечное число требований). В разомкнутых СМО количество заявок, поступающих в систему — теоретически бесконечно.

В n — канальной CМО одновременно могут обслуживаться n заявок, в одноканальной системе — только одна заявка. В простейшем случае каждый канал характеризуется своей производительностью (интенсивностью обслуживания заявок). Если в СМО поступают заявки нескольких типов, то для каждого типа заявок может быть задана соответствующая интенсивность обслуживания. Интервал между поступлением заявок в систему и длительность обслуживания заявки каналом в общем случае — это случайные величины с заданными законами распределения.

Заявки в СМО могут иметь одинаковый приоритет и разный приоритет. При поступлении в СМО нескольких типов заявок с разными приоритетами могут быть организованы отдельные очереди для заявок каждого типа. Кроме размера, для каждой такой очереди указывается приоритет находящихся в ней заявок. Приоритеты обычно кодирует целыми числами 0,1,2,3,…, причем, чем меньше число, тем меньше приоритет соответствующих заявок. При наличии приоритетной организации в СМО на обслуживание в первую очередь выбираются заявки с высшими приоритетами.

Различают заявки с относительным и абсолютным приоритетами. Если заявка с абсолютным приоритетом поступила в CMО в тот момент, когда на обслуживании находятся заявка с меньшим приоритетом, то поступившая заявка сразу начинает обслуживаться, прерывая на время своего обслуживания находящуюся там заявку. Вытесненная таким образом заявка возвращается в начало своей очереди и ожидает продолжение обслуживания (дообслуживания), либо выводится из системы. Для заявок с относительным приоритетом их приоритет вступает в действие не в момент их поступления в СМО, а в момент выбора следующей заявки из очереди (из очередей) на обслуживание. Прерываний в этом случае нет. Приоритеты заявок также бывают статические (постоянные) и динамические (изменяющиеся во времени).

Основные задачи ТСМО заключаются:

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

— в оценке и анализе эффективности функционирования СМО на основе рассчитанных характеристик;

— в оптимизации характеристик функционирования СМО.

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

1.3.1 Определение имитационного моделирования

Известный американский ученый Роберт Шеннон дает следующее определение [17]: «Имитационное моделирование — процесс конструирования модели реальной системы и постановки экспериментов на этой модели с целью либо понять поведение системы, либо оценить (в рамках ограничений, накладываемых некоторым критерием или совокупностью критериев) различные стратегии, обеспечивающие функционирование данной системы». Все имитационные модели используют принцип черного ящика. Это означает, что они выдают выходной сигнал системы при поступлении в нее некоторого входного сигнала. Поэтому в отличие от аналитических моделей для получения результатов необходимо осуществлять «прогон» имитационных моделей, т. е. подачу некоторой последовательности сигналов, объектов или данных на вход модели и фиксацию выходной информации, а не «решать» их. Происходит своего рода «выборка» состояний объекта моделирования (состояния — свойства системы в конкретные моменты времени) из пространства (множества) состояний (совокупность всех возможных значений состояний). Насколько репрезентативной окажется эта выборка, настолько результаты моделирования будут соответствовать действительности. Этот вывод показывает важность статистических методов оценки результатов имитации.

1.3.2 Условия и проблемы применения имитационного моделирования

Применение имитационного моделирования целесообразно при выполнении определенных условий [17]:

1. Не существует законченной математической постановки данной задачи, либо еще не разработаны аналитические методы решения сформулированной математической модели. К этой категории относятся многие модели массового обслуживания, связанные с рассмотрением очередей.

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

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

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

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

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

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

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

1.3.3 Технология разработки имитационной модели

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

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

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

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

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

1.3.4 Принципы построения моделирующих алгоритмов

Задача имитационного моделирования — получение траектории движения (изменения) состояний рассматриваемой системы в n — мерном пространстве (), а также вычисление некоторых показателей, зависящих от выходных сигналов системы и характеризующих ее свойства.

Известны два принципа построения моделирующего алгоритма процесса функционирования систем: принцип и принцип особых состояний () [2, 7, 10, 12−14, 16].

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

При использовании принципа состояния системы фиксируются только в «особые» моменты времени, шаг по времени в этом случае не постоянен, является величиной случайной и вычисляется в соответствии с информацией о предыдущем особом состоянии. К системам, имеющим особые состояния, относятся системы массового обслуживания (СМО). Особые состояния появляются в моменты поступления заявок, в моменты освобождения каналов и т. д. Для таких систем применение принципа нерационально, так как при этом возможны пропуски особых состояний и необходимы методы их обнаружения. Принцип дает возможность для ряда систем существенно уменьшить затраты машинного времени на реализацию моделирующих алгоритмов по сравнению с принципом. Для исследования процесса функционирования больших систем рационально использование комбинированного принципа построения моделирующих алгоритмов, сочетающего в себе преимущества каждого из рассмотренных принципов.

1.4 Аналитический метод моделирования систем

1.4.1 Постановка задачи

К разомкнутым относятся системы, в которых поступающий поток требований теоретически неограничен [8], а количество ожидающих заявок в очереди наоборот, ограничено. Для примера можно взять работу автозаправки с несколькими бензоколонками. Автомобиль, заправившись, покидает систему. Если все заправочные места заняты, автомобили могут вставать в общую очередь. В случае, если величина очереди к бензоколонкам слишком большая, автомобиль покидает систему не обслуженным.

В подобных системах общее число циркулирующих требований ограничено (рисунок 1.1).

Рисунок 1.1 — Размеченный граф состояний разомкнутой СМО

В приведенном графе, состоянию S₀ соответствует простой системы, то есть заявки на обслуживания не поступали или все поступившие были обслужены. Состояниям с S₁ по S_N сопоставимы события, когда в системе присутствуют N требований, при этом все они обслуживаются N каналами. И состояния с S_N+1 по S_N+m представляют собой ситуации, когда требования не могут быть обслужены, вследствие занятости каналов обслуживания, и помещены в очередь на обслуживание. m — величина, ограничивающая длину очереди (в другой терминологии — m — количество мест в накопителе очереди). Следующие параметры являются входными и задают структуру и особенности функционирования системы.

м — интенсивность потока обслуживания;

л — интенсивность входного потока;

N — число каналов (приборов) обслуживания;

m — величина, ограничивающая длину очереди.

Основные задачи теории моделирования разомкнутых СМО заключаются:

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

— в оценке и анализе эффективности функционирования СМО на основе рассчитанных характеристик;

— в оптимизации характеристик функционирования СМО.

1.4.2 Процесс обслуживания как случайный процесс

Пусть имеется некоторая система S, которая в процессе функционирования может принимать различные состояния S_i, i=1, 2,…, n. Если состояния системы меняются случайным образом, то последовательность состояний системы образует случайный процесс.

В каждый момент рассматриваемая система может находиться в одном из следующих состояний: в момент t в системе находятся k требовании (k=0, 1, 2,…). Если kN, то в системе находятся и обслуживаются k требований, а N-k — приборов свободны. Если k > N, то N требований обслуживаются, а k-N находятся в очереди и ожидают обслуживания. Обозначим через S_k состояние, когда в системе находятся k требований. Таким образом, система может находиться в состояниях S₀, S₁, S₂, … Обозначим через P_b(t) — вероятность того, что система в момент t окажется в состоянии S_b.

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

— моментами окончания обслуживаний, производящихся в момент t₀;

— моментами появления новых требований;

— длительностью обслуживания требований, поступивших после t₀.

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

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

1.4.3 Нахождение вероятностей состояний системы. Система уравнений Колмогорова

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

На рисунке 1.2 представлен граф состояний системы, описываемой процессом «гибели и размножения».

Рисунок 1.2. Граф состояний системы, описываемой процессом «гибели и размножения»

Для нулевого состояния алгебраическое уравнение Колмогорова имеет вид:

. (1.1)

Для первого состояния алгебраическое уравнение Колмогорова имеет вид:

В силу (1.1) можно сократить равные друг другу члены и получим:

Аналогичные уравнения получаются для всех состояний системы. В результате система уравнений Колмогорова имеет вид:

(1.2)

Для решения системы (1.2) из первого уравнения выразим :

Из второго уравнения выразим :

Аналогично вероятности всех состояний выражаются через. Подставим полученные выражения в нормировочное условие:

Откуда

.

Остальные вероятности находятся через p₀.

1.4.4 Формулы для расчета разомкнутой СМО на основе систем уравнений Колмогорова

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

Вероятности состояний системы:

, ,

Вероятность загрузки системы:

.

Вероятность отказа в обслуживании: .

Относительная пропускная способность:

Абсолютная пропускная способность:

Среднее число требований в очереди:

Среднее время ожидания в очереди:

.

Среднее число заявок в системе:

Среднее число занятых каналов:

Среднее время пребывания требования в системе:

.

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

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

1.5.1 Равномерный закон распределения

Непрерывная случайная величина имеет равномерное распределение на отрезке [a, b], если на этом отрезке плотность распределения случайной величины постоянна, а вне него равна нулю.

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

Рисунок 1.3 — График функции плотности распределения

Получаем. Найдем функцию распределения F (x) на отрезке [a, b].

Рисунок 1.4 — Функция распределения

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

Вероятность попадания случайной величины в заданный интервал:

Случайная величина X, распределенная по равномерному закону в пределах [a; b], обычно моделируется на компьютере по простейшему алгоритму [3]:

X = Math. random ()*(b-a)+a

Где Math. random () — функция генерации случайного числа по равномерному закону, в интервале [0; 1].

1.5.2 Нормальный закон распределения

Нормальным называется распределение вероятностей непрерывной случайной величины, которое описывается плотностью вероятности

Нормальный закон распределения также называется законом Гаусса. Нормальный закон распределения занимает центральное место в теории вероятностей. Это обусловлено тем, что этот закон проявляется во всех случаях, когда случайная величина является результатом действия большого числа различных факторов. К нормальному закону приближаются все остальные законы распределения. Можно легко показать, что параметры m_x и у_x, входящие в плотность распределения являются соответственно математическим ожиданием и средним квадратическим отклонением случайной величины Х. Найдем функцию распределения F (x).

График плотности нормального распределения называется нормальной кривой или кривой Гаусса. Нормальная кривая обладает следующими свойствами:

— функция определена на всей числовой оси;

— при всех х функция распределения принимает только положительные значения;

— ось ОХ является горизонтальной асимптотой графика плотности вероятности, т.к. при неограниченном возрастании по абсолютной величине аргумента х, значение функции стремится к нулю;

— найдем экстремум функции,

т.к. при y' > 0 при x < m и y' < 0 при x > m, то в точке х = m функция имеет максимум, равный

— функция является симметричной относительно прямой х = а, т.к. разность (х — а) входит в функцию плотности распределения в квадрате;

— для нахождения точек перегиба графика найдем вторую производную функции плотности

При x = m + s и x = m — s вторая производная равна нулю, а при переходе через эти точки меняет знак, т. е. в этих точках функция имеет перегиб. В этих точках значение функции равно

Построим график функции плотности распределения.

Рисунок 1.5 — График функции плотности распределения

Построены графики при m =0 и трех возможных значениях среднего квадратичного отклонения s = 1, s = 2 и s = 7. Как видно, при увеличении значения среднего квадратичного отклонения график становится более пологим, а максимальное значение уменьшается. Если, а > 0, то график сместится в положительном направлении, если, а < 0 — в отрицательном. При, а = 0 и s = 1 кривая называется нормированной. Уравнение нормированной кривой:

Случайная величина X, распределенная по нормальному закону с математическим ожиданием m и с.к.о. у, обычно моделируется на компьютере по следующему алгоритму:

y = 0;

for (i=0; i

y += Math. random ();

y -= N;

X = m + у*y;

Где Math. random () — функция генерации случайного числа по равномерному закону, в интервале [0; 1], N — некоторое число, часто равное 6−8.

1.5.3 Экспоненциальный закон распределения

Показательным (экспоненциальным) называется распределение вероятностей непрерывной случайной величины Х, которое описывается плотностью

где л — положительное число. Найдем закон распределения.

Рисунок 1.6 Графики функции распределения и плотности распределения

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

Результат получен с использованием того факта, что

Для нахождения дисперсии найдем величину

Дважды интегрируя по частям, аналогично рассмотренному случаю, получим:

Тогда

Итого:

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

Показательное распределение широко используется в теории надежности. Допустим, некоторое устройство начинает работать в момент времени t₀=0, а через какое-то время t происходит отказ устройства. Обозначим Т непрерывную случайную величину — длительность безотказной работы устройства. Таким образом, функция распределения F (t) = P (T

R (t) = P (T>t) = 1 — F (t).

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

y = Math. random ();

if (y = 0) y = 0.00…1; // с необходимой точностью

if (y = 1) y = 0.99…9;

X = (-1/л) * Math. log (y);

Где Math. random () — функция генерации случайного числа по равномерному закону, в интервале [0.00…1; 0.99…9]. Math. log — натуральный логарифм.

2. Техническое задание на разработку

2.1 Общие сведения

2.1.1 Наименование системы

Демонстрационная программа моделирования разомкнутых систем массового обслуживания.

2.1.2 Основание для разработки

Заказ кафедры ВТ.

2.1.3 Сроки разработки системы

Начало разработки: 15.02.2012.

Окончание разработки: 24.05.2012.

2.1.4 Разработчики

Студент Парменов К. Р. группы АМ-809

2.1.5 Функции заказчика

— утверждение плана работ;

— приёмка у разработчика технической документации;

— приёмка программы в опытную эксплуатацию.

2.1.6 Функции разработчика

— выбор и обоснование метода расчета характеристик СМО со взаимопомощью каналов для программной реализации;

— разработка ТЗ;

— разработка демонстрационной программы для решения задачи расчета характеристик СМО со взаимопомощью каналов и анализа эффективности ее функционирования;

— тестирование программы;

— подготовка итогового отчета.

2.2 Цель создания системы

- повысить эффективность процесса обучения студентов имитационному и аналитическому методам моделирования СМО, расчету основных характеристик эффективности функционирования СМО с взаимопомощью каналов;

— удобство, наглядность представления учебных материалов.

2.3 Требования к программе

2.3.1 Общие положения

Основные требования, предъявляемые к программе, перечислены в порядке убывания их приоритетов:

— реализация программы по технологии C#;

— визуализация результатов работы;

— отсутствие ошибок в работе программы;

— удобный пользовательский интерфейс;

— бесперебойность работы программы;

— высокое быстродействие работы программы.

2.3.2 Требования к техническому обеспечению

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

Минимальные требования:

— процессор Intel Pentium 500 MHz (или совместимый);

— ОЗУ 32 Mb RAM;

— ОС семейства Windows,

— Установленный. Net Framework версии 4.0 (или выше).

2.3.3 Требования к программному обеспечению (со стороны разработчика)

Для разработки программы использовался язык программирования С#. Изначально предполагалось использовать такой инструмент, как Flash, но в ходе выполнения бакалаврской работы было проведено исследование быстродействия этих двух инструментов. По итогам исследования удалось выяснить, что по производительности C# показывает лучшие результаты, нежели flash, поэтому, после согласования с руководителем было принято решение в качестве среды разработки выбрать платформу Visual Studio 2010 и язык программирования C#. Это мощный язык программирования, обладающий свойствами безопасности и интернациональности.

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

2.3.4 Требования к программному обеспечению (со стороны пользователя)

Программа может работать в любой ОС семейства Windows 9х/NT/2000/XP/Server 2003/Server2008/Vista/7. Стоит упомянуть что для запуска программы необходим установленный пакет. Net Framework версии 4.0 и выше, так как он содержит требуемые библиотеки для корректной работы приложения.

Тестировалась программа в ОС Windows 7 и Windows XP.

2.4 Задачи и функции программы

2.4.1 Общие положения

Программа предназначена для использования студентами. Она позволяет проводить эксперимент и моделировать СМО на разных входных данных и получать результат в графическом виде (имитационно). В результате работы программы, по

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

2.4.2 Возможности программы

— имитационное моделирование СМО без визуализации;

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

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

2.4.3 Задачи программы

— облегчить получение знаний студентами;

— обучить студентов основным навыкам для решения задачи;

— натренировать студентов в решении задач;

— улучшить качество получаемых студентами знаний.

2.4.4 Функции программы

— тренирирующая;

— вычислительная;

— информирующая;

— развлекательная.

3. Разработка программного обеспечения

3.1 Общие положения

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

Рисунок 3.1 — Организационная диаграмма взаимосвязи использованных классов

На рисунке 3.1 показано взаимодействие использованных классов и компонентов программы. Так, компоненты, отвечающие за ввод информации (Button, TexBox, ComboBox, …), используются для принятия от пользователя входных данных и передачи их в программу, в которой используется взаимодействие пользовательских и базовых классов. В результате этого взаимодействия, в программе реализовывается механизм аналитического и имитационного модулей. Вывод результатов происходит посредством компонентов, отвечающих за вывод информации (List, PictureBox, …).

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

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

3.2.1 Структуры хранения и обработки данных

Структура программы моделирования СМО с разными дисциплинами обслуживания

Принципом построения моделирующего алгоритма процесса функционирования СМО с разными дисциплинами взаимопомощи были выбран метод дz с наращением времени до следующего события.

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

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

while (arrivalTime < renderTime)

{

arrivalTime = arrivalTime — 1 / requestIntensity * Math. Log (generator. NextDouble ());

if (events. Count > chCount)

{ratio = 1;

processingTime = -1 / executIntensity * Math. Log (generator. NextDouble ()) / ratio;}

else {

if (events. Count≠ 0)

{ratio = chCount / events. Count;

processingTime = -1 / executIntensity * Math. Log (generator. NextDouble ()) / ratio;}

else

{processingTime = -1 / executIntensity * Math. Log (generator. NextDouble ());}

Стоит пояснить значения некоторых переменных:

— processingTime — переменная, в которой хранится время обработки заявки;

— arrivalTime — время прихода заявки в систему;

— renderTime — период моделирования, который задается пользователем при запуске алгоритма моделирования.

— ratio — переменная, определяющая отношение количества заявок к количеству каналов работающих в данный момент в системе.

Так как в данной программе отсутствует графическая визуализация моделирования процесса, мы смогли учесть это при создании «Счетчика времени». Суть данного цикла заключается в том, что он инкрементация времени происходит именно на величину времени обработки заявки, которая вычисляется исходя из нескольких параметров системы: количество заявок в системе, количество каналов. Поэтому после завершения работы этого цикла мы имеем все данные о процессе моделирования, который был выполнен.

Класс Form1

Класс Form1 фактически является основополагающей формой данной разработки.

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

— в очереди (в системе);

— на обработке (в системе);

— обработана (не в системе);

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

Некоторые функции, используемые в программе

Функция отрисовки графиков

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

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

Цикл, обработки поступающих заявок

while (events. Count≠ 0)

{

if (events[0] < arrivalTime)

{

chance [events. Count] += events[0] - checkPoint;

checkPoint = events[0];

events. RemoveAt (0);

}

else break;

}

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

3.3 Описание пользовательского интерфейса

3.3.1 Руководство по использованию имитационной системы

Программа имитационного моделирования СМО с разными дисциплинами обслуживания позволяет не только рассчитать экспериментальным путем основные характеристики системы, но и пронаблюдать особенности ее функционирования и выявить некоторые зависимости. Интерфейс программы встречает пользователя главным экраном, стилизованным под экран планшетника фирмы Apple (рисунок 3.7). Это решение было выбрано для того, чтобы придать программе, основной целью которой, все же, является вычислительная функция, удобоваримый вид.

Главный экран программы

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

Нормальный закон распределения

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

Равномерный закон распределения

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

Экспоненциальный закон распределения

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

· Сосредоточенная

· С дополнительными каналами

· Равномерная

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

Следующей частью интерфейса программы идет непосредственно панель управления.

Кнопка (1) — кнопка информации. При нажатии на нее открывается форма, в которой пользователь может ознакомиться с постановкой задачи, реализованной в демонстрационной программе.

Кнопка (2) — кнопка сохранения. Она выполняет функцию сохранения результатов выполнения программы в текстовый файл, который создается в директории нахождения выполняемого файла приложения.

Кнопка (3) — построение графика. При нажатии открывается форма, в которой программа моделирования строит график исходными данными для которого являются результаты моделирования системы.

Графики

Кнопка (4) — кнопка «Моделировать». Она запускает алгоритм имитационного моделирования учитывая все заданные заранее параметры. Результаты выполнения программы отображаются в текстовом поле, располагающемся справа от панели управления.