Технология разработки и тестирования программного обеспечения в среде Visual Studio на примере создания программы моделирования систем массового обслуживания. Аналитические и имитационные методы моделирования с разными дисциплинами обслуживания заявок.
Аннотация к работе
Когда говорят о моделировании, обычно имеют в виду моделирование некоторой системы. В системе с отказами (с потерями, с конечной длиной очереди) заявка, пришедшая в момент, когда все каналы обслуживания заняты или заняты все места в очереди, получает отказ и покидает систему. Основные задачи ТСМО заключаются: - в расчете выходных характеристик СМО, характеризующих эффективность функционирования системы (вероятность простоя системы, вероятность отказа в обслуживании, среднее число заявок в системе, среднее число занятых каналов, среднее время ожидания в очереди и т.д.); Процесс моделирования системы можно укрупнено представить в виде последовательного выполнения трех основных этапов: построение концептуальной модели системы и ее формализация; алгоритмизация и машинная реализация модели системы; получение и интерпретация результатов моделирования системы. Основные задачи теории моделирования разомкнутых СМО заключаются: - в расчете выходных характеристик СМО, характеризующих эффективность функционирования системы (вероятность простоя системы, вероятность отказа в обслуживании, среднее число заявок в системе, среднее число занятых каналов, среднее время ожидания в очереди и т.д.);В ходе выполнения работы, был проведен обзор теоретического материала и выбор среды разработки демонстрационной программы. Выбор Microsoft Visual Studio обусловлен широкими возможностями работы с большими объемами обрабатываемых данных и очень функциональным языком программирования C#. Разработчиком и заказчиком совместно разработано и утверждено техническое задание.
Введение
Во многих областях человеческой деятельности ставятся и решаются задачи, связанные с моделированием поведения некоторой системы в течение времени. Моделирование системы может преследовать разные цели: наблюдение за ходом процесса работы системы, оценка эффективности функционирования системы и ее оптимизация.
Примером такой системы может послужить организация работы станции технического обслуживания. Так число механиков (обработчиков требований) не является случайно взятым, а рассчитано исходя из загруженности СТО в конкретные дни и даже часы, в праздники. Руководство станции следит, чтобы очередь клиентов (требования) была минимальной, и в то же время механиков без работы не было.
Решением подобных задач занимается теория систем массового обслуживания. Под системой массового обслуживания (СМО) понимают динамическую систему, предназначенную для эффективного обслуживания потока заявок (требований на обслуживание) при ограничениях на ресурсы системы [9].
В теории систем массового обслуживания (СМО) обрабатываемую заявку называют требованием. В общем случае под требованием понимают запрос на удовлетворение некоторой потребности, например, разговор с абонентом, посадка самолета, покупка продуктов, получение материалов на складе.
Средства, обслуживающие требования, называются обслуживающими устройствами или каналами обслуживания. Например, к ним относятся каналы телефонной связи, посадочной полосы, мастера-ремонтники, билетные кассиры, погрузочно-разгрузочные точки на базах и складах.
Основной задачей теории СМО является изучение режима функционирования обслуживающей системы и исследование явлений, возникающих в процессе обслуживания. Также, в теории СМО возникают задачи оптимизации: каким образом достичь определенного уровня обслуживания (максимального сокращения очереди или потерь требований) при минимальных затратах, связанных с простоем обслуживающих устройств.
В общем, модели СМО очень распространены и применяются во многих сферах деятельности человека и реализуются при помощи вычислительных систем.
Одной из разновидностей СМО является СМО со взаимопомощью между каналами обслуживания. В ряде случаев встречаются СМО, в которых для ускорения процесса обслуживания допускается подключение нескольких каналов к работе над одной заявкой. Например, два или несколько рабочих могут одновременно ремонтировать один станок или автомашину, по одному самолету может стрелять несколько зенитных орудий, вычисления для одной задачи могут быть, распараллелены между несколькими ЭВМ. При этом возникает задача наилучшего распределения каналов обслуживания по работам, связанным с обслуживанием поступающих заявок.
В рамках бакалаврской работы разрабатывается демонстрационная программа моделирования СМО с разными дисциплинами обслуживания заявок двумя методами: аналитическим, имитационным. Оба метода реализуются в одной программе. Программа позволяет преподносить информацию в удобном для восприятия виде, обладает дружественным интерфейсом. Есть возможность сопровождения процессам моделирования наглядными графиками.
В качестве среды разработки была выбрана динамично развивающаяся на сегодняшний день технология С#. Обладая широкими возможностями для программирования, она в тоже время имеет преимущество в быстродействии при моделировании трудоемких процессов, что, несомненно, делает ее одной из лучших инструментов для разработки демонстрационных программ [7].
1. Обзор методов моделирования разомкнутых систем массового обслуживания
1.1 Теория моделирования
1.1.1 Основные определения и понятия
Теория моделирования - теория замещения объекта-оригинала его моделью и исследования свойств объекта на его модели [14].
Моделирование - метод исследования, основанный на замене исследуемого объекта-оригинала его моделью и на работе с ней (вместо объекта) [6, 14].
Модель (объекта - оригинала) (от лат. modus - «мера», «объем», «образ») - вспомогательный объект, отражающий наиболее существенные для исследования закономерности, суть, свойства, особенности строения и функционирования объекта-оригинала [6].
Когда говорят о моделировании, обычно имеют в виду моделирование некоторой системы.
Система - совокупность взаимосвязанных элементов, объединенных для реализации общей цели, обособленная от окружающей среды и взаимодействующая с ней как целостное целое и проявляющая при этом основные системные свойства. В [6] выделено 15 основных системных свойств, к которым относятся: эмергентность (эмерджентность); цельность; структурированность; целостность; подчиненность цели; иерархичность; бесконечность; эргатичность; открытость; необратимость; единство структурной устойчивости и неустойчивости; нелинейность; потенциальная многовариантность актуальных структур; критичность; непредсказуемость в критической области.
При моделировании систем используют два подхода: классический (индуктивный), сложившийся исторически первым, и системный, получивший развитие в последнее время [6, 14].
При классическом подходе реальный объект, подлежащий моделированию, разбивается на подсистемы, выбираются исходные данные для моделирования и ставятся цели, отражающие отдельные стороны процесса моделирования. По отдельной совокупности исходных данных ставится цель моделирования отдельной стороны функционирования системы, на базе этой цели формируется некоторая компонента будущей модели. Совокупность компонент объединяется в модель. Таким образом, происходит суммирование компонент, каждая компонента решает свои собственные задачи и изолирована от других частей модели. Применим подход только для простых систем, где можно не учитывать взаимосвязи между элементами (компонентами) системы.
Системный подход - методологическая концепция, основанная на стремлении построить целостную картину изучаемого объекта с учетом важных для решаемой задачи элементов объекта, связей между ними и внешних связей с другими объектами и окружающей средой. В основе системного подхода лежит рассмотрение системы как интегрированного целого, причем это рассмотрение при разработке начинается с главного - формулировки цели функционирования. Важным для системного подхода является определение структуры системы - совокупности связей между элементами системы, отражающих их взаимодействие.
Существуют структурные и функциональные подходы к исследованию структуры системы и ее свойств. При структурном подходе выявляются состав выделенных элементов системы и связи между ними. При функциональном подходе рассматриваются алгоритмы поведения системы (функции - свойства, приводящие к достижению цели).
1.1.2 Основные методы моделирования
Методы моделирования можно классифицировать на три основные группы: аналитические, численные и имитационные [7, 14, 16].
1. Аналитические методы моделирования. Аналитические методы позволяют получить характеристики системы как некоторые функции параметров ее функционирования. Таким образом, аналитическая модель представляет собой систему уравнений, при решении которой получают параметры, необходимые для расчета выходных характеристик системы (среднее время обработки задания, пропускную способность и т.д.). Аналитические методы дают точные значения характеристик системы, но применяются для решения только узкого класса задач. Причины этого заключается в следующем. Во-первых, вследствие сложности большинства реальных систем их законченное математическое описание (модель) либо не существует, либо еще не разработаны аналитические методы решения созданной математической модели. Во-вторых, при выводе формул, на которых основываются аналитические методы, принимаются определенные допущения, которые не всегда соответствуют реальной системе. В этом случае от применения аналитических методов приходится отказываться.
2. Численные методы моделирования. Численные методы предполагают преобразование модели к уравнениям, решение которых возможно методами вычислительной математики. Класс задач, решаемых этими методами, значительно шире. В результате применения численных методов получают приближенные значения (оценки) выходных характеристик системы с заданной точностью.
3. Имитационные методы моделирования. С развитием вычислительной техники широкое применение получили имитационные методы моделирования для анализа систем, преобладающими в которых являются стохастические воздействия.
Суть имитационного моделирования (ИМ) заключается в имитации процесса функционирования системы во времени, с соблюдением таких же соотношений длительности операций как в системе оригинале. При этом имитируются элементарные явления, составляющие процесс, сохраняется их логическая структура, последовательность протекания во времени. В результате применения ИМ получают оценки выходных характеристик системы, которые необходимы при решении задач анализа, управления и проектирования.
1.2 Элементы теории массового обслуживания, применяемые при моделировании систем
1.2.1 Основные определения и понятия
Под системой массового обслуживания (СМО) понимают динамическую систему, предназначенную для эффективного обслуживания потока заявок (требований на обслуживание) при ограничениях на ресурсы системы.
Первые задачи теории массового обслуживания (ТСМО) были рассмотрены сотрудниками Копенгагенской телефонной компании, датским ученым А.К. Эрлангом (1878 г. - 1929 г.) в период между 1908 и 1922 гг. Эти задачи были обусловлены стремлением упорядочить работу телефонной сети и разработать методы, позволяющие заранее повысить качество обслуживания потребителей в зависимости от числа используемых устройств. Оказалось, что ситуации, возникающие на телефонных станциях, являются типичными не только для телефонной связи. Работа аэродромов, работа морских и речных портов, магазинов, библиотек, радиолокационных станций и комплексов, терминальных классов, вычислительных систем и сетей, автоматизированных систем управления и т.д. может быть описана в рамках ТСМО.
Классификация СМО. Выделяют различные признаки классификации СМО: системы с отказами и системы без отказов; замкнутые и разомкнутые; многоканальные и одноканальные; с равными (с точки зрения порядка обслуживания) заявками и с приоритетными заявками.
В системе с отказами (с потерями, с конечной длиной очереди) заявка, пришедшая в момент, когда все каналы обслуживания заняты или заняты все места в очереди, получает отказ и покидает систему. В системе без отказов (без потерь, с бесконечной длиной очереди) такая заявка не покидает систему, а становится в очередь и ждет, пока не освободится какой-нибудь канал. Время ожидания в общем случае неограниченно.
В замкнутых СМО в системе циркулирует определенное конечное число заявок (конечное число требований). В разомкнутых СМО количество заявок, поступающих в систему - теоретически бесконечно.
В n - канальной СМО одновременно могут обслуживаться n заявок, в одноканальной системе - только одна заявка. В простейшем случае каждый канал характеризуется своей производительностью (интенсивностью обслуживания заявок). Если в СМО поступают заявки нескольких типов, то для каждого типа заявок может быть задана соответствующая интенсивность обслуживания. Интервал между поступлением заявок в систему и длительность обслуживания заявки каналом в общем случае - это случайные величины с заданными законами распределения.
Заявки в СМО могут иметь одинаковый приоритет и разный приоритет. При поступлении в СМО нескольких типов заявок с разными приоритетами могут быть организованы отдельные очереди для заявок каждого типа. Кроме размера, для каждой такой очереди указывается приоритет находящихся в ней заявок. Приоритеты обычно кодирует целыми числами 0,1,2,3,…, причем, чем меньше число, тем меньше приоритет соответствующих заявок. При наличии приоритетной организации в СМО на обслуживание в первую очередь выбираются заявки с высшими приоритетами.
Различают заявки с относительным и абсолютным приоритетами. Если заявка с абсолютным приоритетом поступила в СМО в тот момент, когда на обслуживании находятся заявка с меньшим приоритетом, то поступившая заявка сразу начинает обслуживаться, прерывая на время своего обслуживания находящуюся там заявку. Вытесненная таким образом заявка возвращается в начало своей очереди и ожидает продолжение обслуживания (дообслуживания), либо выводится из системы. Для заявок с относительным приоритетом их приоритет вступает в действие не в момент их поступления в СМО, а в момент выбора следующей заявки из очереди (из очередей) на обслуживание. Прерываний в этом случае нет. Приоритеты заявок также бывают статические (постоянные) и динамические (изменяющиеся во времени).
Основные задачи ТСМО заключаются: - в расчете выходных характеристик СМО, характеризующих эффективность функционирования системы (вероятность простоя системы, вероятность отказа в обслуживании, среднее число заявок в системе, среднее число занятых каналов, среднее время ожидания в очереди и т.д.);
- в оценке и анализе эффективности функционирования СМО на основе рассчитанных характеристик;
- в оптимизации характеристик функционирования СМО.
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 - Размеченный граф состояний разомкнутой СМО
В приведенном графе, состоянию S0 соответствует простой системы, то есть заявки на обслуживания не поступали или все поступившие были обслужены. Состояниям с S1 по SN сопоставимы события, когда в системе присутствуют N требований, при этом все они обслуживаются N каналами. И состояния с SN 1 по SN m представляют собой ситуации, когда требования не могут быть обслужены, вследствие занятости каналов обслуживания, и помещены в очередь на обслуживание. m - величина, ограничивающая длину очереди (в другой терминологии - m - количество мест в накопителе очереди). Следующие параметры являются входными и задают структуру и особенности функционирования системы. ? - интенсивность потока обслуживания;
? - интенсивность входного потока;
N - число каналов (приборов) обслуживания;
m - величина, ограничивающая длину очереди.
Основные задачи теории моделирования разомкнутых СМО заключаются: - в расчете выходных характеристик СМО, характеризующих эффективность функционирования системы (вероятность простоя системы, вероятность отказа в обслуживании, среднее число заявок в системе, среднее число занятых каналов, среднее время ожидания в очереди и т.д.);
- в оценке и анализе эффективности функционирования СМО на основе рассчитанных характеристик;
- в оптимизации характеристик функционирования СМО.
1.4.2 Процесс обслуживания как случайный процесс
Пусть имеется некоторая система S, которая в процессе функционирования может принимать различные состояния Si, i=1, 2,…, n. Если состояния системы меняются случайным образом, то последовательность состояний системы образует случайный процесс.
В каждый момент рассматриваемая система может находиться в одном из следующих состояний: в момент t в системе находятся k требовании (k=0, 1, 2,…). Если k N, то в системе находятся и обслуживаются k требований, а N-k - приборов свободны. Если k > N, то N требований обслуживаются, а k-N находятся в очереди и ожидают обслуживания. Обозначим через Sk состояние, когда в системе находятся k требований. Таким образом, система может находиться в состояниях S0, S1, S2, … Обозначим через Pb(t) - вероятность того, что система в момент t окажется в состоянии Sb.
Сформулируем, в чем заключается особенность изучаемых нами задач в сделанных предположениях. Пусть в некоторый момент t0 наша система находилась в состоянии Si. Докажем, что последующее течение процесса обслуживания не зависит в смысле теории вероятностей от того, что происходило до момента t0. Действительно, дальнейшее течение обслуживания полностью определяется тремя следующими факторами: - моментами окончания обслуживаний, производящихся в момент t0;
- моментами появления новых требований;
- длительностью обслуживания требований, поступивших после t0.
Процесс, протекающий в системе S, называется Марковским процессом с дискретными состояниями и непрерывным временем (или непрерывной Марковской цепью), если выполняется условие: для любого фиксированного момента времени условные вероятности состояния системы в будущем зависят только от состояния системы в настоящем и не зависят от того, когда (на каком шаге) и откуда система перешла в это состояние [9].
Если в такой системе все потоки, переводящие систему из состояния в состояние Пуассоновские, то процесс называется Марковским случайным процессом «гибели и размножения». Термин ведет начало от биологических задач, процесс описывает изменение численности популяции. Переход из состояния в состояние происходит в момент гибели или рождения особи.
1.4.3 Нахождение вероятностей состояний системы. Система уравнений Колмогорова
На практике значительная часть систем может описываться в рамках схемы «гибели и размножения». Рассмотрим эту схему в общем виде и решим соответствующую систему алгебраических уравнений для нахождения предельных вероятностей состояний системы в стационарном режиме.
На рисунке 1.2 представлен граф состояний системы, описываемой процессом «гибели и размножения».
Рисунок 1.2. Граф состояний системы, описываемой процессом «гибели и размножения»
Для нулевого состояния алгебраическое уравнение Колмогорова имеет вид: . (1.1)
Для первого состояния алгебраическое уравнение Колмогорова имеет вид:
В силу (1.1) можно сократить равные друг другу члены и получим:
Аналогичные уравнения получаются для всех состояний системы. В результате система уравнений Колмогорова имеет вид:
(1.2)
Для решения системы (1.2) из первого уравнения выразим :
Из второго уравнения выразим :
Аналогично вероятности всех состояний выражаются через . Подставим полученные выражения в нормировочное условие: , Откуда
.
Остальные вероятности находятся через p0.
1.4.4 Формулы для расчета разомкнутой СМО на основе систем уравнений Колмогорова
Для нахождения предельных вероятностей состояний составляется система уравнений Колмогорова [8]. Ниже приведены конечные формулы для расчета предельных вероятностей состояний, выведенные из системы уравнений Колмогорова. Характеристики эффективности функционирования системы рассчитываются на основе предельных вероятностей состояний.
Вероятности состояний системы: , , ,
Вероятность загрузки системы: .
Вероятность отказа в обслуживании: .
Относительная пропускная способность: Абсолютная пропускная способность: Среднее число требований в очереди:
Среднее время ожидания в очереди: .
Среднее число заявок в системе:
Среднее число занятых каналов:
Среднее время пребывания требования в системе: .
1.5 Законы распределения интервалов поступления и обслуживания заявок, используемые для генерации случайных чисел
В демонстрационной программе предусмотрено моделирование интервалов между поступлениями требований и интервалов обслуживания по трем законам. Таким образом, пользователь может комбинировать различные законы на поступление и обслуживание и отслеживать их влияние на функционирование системы. Далее рассмотрим подробнее эти законы.
1.5.1 Равномерный закон распределения
Непрерывная случайная величина имеет равномерное распределение на отрезке [a, b], если на этом отрезке плотность распределения случайной величины постоянна, а вне него равна нулю.
Постоянная величина C может быть определена из условия равенства единице площади, ограниченной кривой распределения.
Рисунок 1.3 - График функции плотности распределения
Получаем . Найдем функцию распределения F(x) на отрезке [a, b].
Рисунок 1.4 - Функция распределения
Для того чтобы случайная величина подчинялась закону равномерного распределения необходимо, чтобы ее значения лежали внутри некоторого определенного интервала, и внутри этого интервала значения этой случайной величины были бы равновероятны. Определим математическое ожидание и дисперсию случайной величины, подчиненной равномерному закону распределения [4].
Вероятность попадания случайной величины в заданный интервал:
Случайная величина X, распределенная по равномерному закону в пределах [a; b], обычно моделируется на компьютере по простейшему алгоритму [3]: X = Math.random()*(b-a) a Где Math.random() - функция генерации случайного числа по равномерному закону, в интервале [0; 1].
1.5.2 Нормальный закон распределения
Нормальным называется распределение вероятностей непрерывной случайной величины, которое описывается плотностью вероятности
Нормальный закон распределения также называется законом Гаусса. Нормальный закон распределения занимает центральное место в теории вероятностей. Это обусловлено тем, что этот закон проявляется во всех случаях, когда случайная величина является результатом действия большого числа различных факторов. К нормальному закону приближаются все остальные законы распределения. Можно легко показать, что параметры mx и ?x, входящие в плотность распределения являются соответственно математическим ожиданием и средним квадратическим отклонением случайной величины Х. Найдем функцию распределения F(x).
График плотности нормального распределения называется нормальной кривой или кривой Гаусса. Нормальная кривая обладает следующими свойствами: - функция определена на всей числовой оси;
- при всех х функция распределения принимает только положительные значения;
- ось ОХ является горизонтальной асимптотой графика плотности вероятности, т.к. при неограниченном возрастании по абсолютной величине аргумента х, значение функции стремится к нулю;
- найдем экстремум функции, т.к. при 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<N; i ) y = Math.random();
y -= N;
X = m ?*y;
Где Math.random() - функция генерации случайного числа по равномерному закону, в интервале [0; 1], N - некоторое число, часто равное 6-8.
1.5.3 Экспоненциальный закон распределения
Показательным (экспоненциальным) называется распределение вероятностей непрерывной случайной величины Х, которое описывается плотностью где ? - положительное число. Найдем закон распределения.
Рисунок 1.6 Графики функции распределения и плотности распределения
Результат получен с использованием того факта, что
Для нахождения дисперсии найдем величину
Дважды интегрируя по частям, аналогично рассмотренному случаю, получим:
Тогда
Итого:
Видно, что в случае показательного распределения математическое ожидание и среднеквадратическое отклонение равны. Также легко определить и вероятность попадания случайной величины, подчиненной показательному закону распределения, в заданный интервал.
Показательное распределение широко используется в теории надежности. Допустим, некоторое устройство начинает работать в момент времени t0=0, а через какое-то время t происходит отказ устройства. Обозначим Т непрерывную случайную величину - длительность безотказной работы устройства. Таким образом, функция распределения F(t) = P (T<t) определяет вероятность отказа за время длительностью t. Вероятность противоположного события (безотказная работа в течение времени 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 и язык прогр
Вывод
В ходе выполнения работы, был проведен обзор теоретического материала и выбор среды разработки демонстрационной программы. Выбор Microsoft Visual Studio обусловлен широкими возможностями работы с большими объемами обрабатываемых данных и очень функциональным языком программирования C#.
Разработчиком и заказчиком совместно разработано и утверждено техническое задание.
Разработаны структура и дизайн демонстрационной программы. Выполнено техническое описание программной разработки и описание пользовательского интерфейса.
Проведено тестирование написанной программы и ее дальнейшая доработка. В ходе тестирования наметились основные тенденции дальнейшего развития программы: - введение возможности графических построений;
- увеличение количества используемых законов распределения;
- увеличение точности получаемых результатов.
Список литературы
1. Айвазян С.А., Енюков И.С., Мешалкин Л.Д. Прикладная статистика: Основы моделирования и первичная обработка данных. - М.: «Финансы и статистика», 2010. - 471 с.
3. Арсеньев Б.П., Яковлев С.А. Интеграция распределенных баз данных. - Спб.: Лань, 2010. - 420 с.
4. Губарев В.В. Вероятностные модели / Новосиб. электротехн. ин-т. - Новосибирск, 1992. - Ч. 1. - 198 с; Ч. 2. - 188 с.
5. Губарев В.В. Системный анализ в экспериментальных исследованиях. - Новосибирск: Изд-во НГТУ, 2009. - 99 с.
6. Дрейпер Н., Смит Г. Прикладной регрессионный анализ. - М.: Статистика, 1973.
7. Карпов Ю. Имитационное моделирование систем. Введение в моделирование с ANYLOGIC 5. - СПБ.: БХВ-Петрбург, 2005. - 400 с.
8. Лемешко Б.Ю., Постовалов С.Н. Компьютерные технологии анализа данных и исследования статистических закономерностей: Учеб. пособие. - Новосибирск: Изд-во НГТУ, 2004. - 120 с.
9. Моделирование систем. Практикум: Учеб. пособие для вузов/Б.Я. Советов, С.А. Яковлев. - 2-е изд., перераб. и доп. - М.: Высшая школа, 2003. - 295 с.
10. Рыжиков Ю.И. Имитационное моделирование. Теория и технологии. - СПБ.: КОРОНА принт; М.: Альтекс-А, 2004. - 384 с.
11. Советов Б.Я., Яковлев С.А. Моделирование систем (3-е изд.). - М.: Высшая школа, 2001. - 420 с.