МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ

ВОЛГОГРАДСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ

УНИВЕРСИТЕТ

В. С. Лукьянов, Г. В. Слесарев

ПРОЕКТИРОВАНИЕ КОМПЬЮТЕРНЫХ СЕТЕЙ МЕТОДАМИ

ИМИТАЦИОННОГО МОДЕЛИРОВАНИЯ

Учебное пособие

Волгоград 2001 УДК 62.529 Рецензенты: В. Н Крымов, М.В. Белодедов Лукьянов В. С., Слесарев Г. В. Проектирование компьютерных сетей методами имитационного моделирования: Учеб. пособие/ ВолгГТУ. Волгоград, 2001. - 72с.

ISВN 5-230-03878-0 Показана сущность имитационного моделирования, приведены области и основные модели использования средств имитационного эксперимента на ЭВМ. Изложены основные методы формирования дискретных и непрерывных случайных величин в соответствии с заданными законами их распределения.

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

Пособие предназначено для студентов специальностей 2201, 2202, 2203.

Ил. 32. Табл.2. Библиогр.: 3 назв.

Печатается по решению редакционно-издательского совета Волгоградского государственного технического университета © Волгоградский государственный технический университет. Оглавление

ОГЛАВЛЕНИЕ

)

ВВЕДЕНИЕ

)

1. СУЩНОСТЬ ИМИТАЦИОННОГО МОДЕЛИРОВАНИЯ. ОБЛАСТИ

ПРИМЕНЕНИЯ ИМИТАЦИОННЫХ МОДЕЛЕЙ

)

1. 1. ОБЛАСТИ ПРИМЕНЕНИЯ ИМИТАЦИОННОГО МОДЕЛИРОВАНИЯ В МАШИНОСТРОЕНИИ

] 1. 2. ВИДЫ МОДЕЛИРОВАНИЯ СИСТЕМ ]

1. 3. СУЩНОСТЬ ИМИТАЦИОННОГО МОДЕЛИРОВАНИЯ

1.4. ОСНОВНЫЕ МОДЕЛИ ИМИТИРУЕМЫХ СИСТЕМ

Непрерывно-детерминированные модели (Д-схемы) Дискретно-детерминированные модели (F-схемы) Дискретно-стохастические модели (P-схемы) Непрерывно-стохастические модели (Q-схемы) Обобщенные модели (А-схемы)

2. ОРГАНИЗАЦИЯ ИМИТАЦИОННОГО МОДЕЛИРОВАНИЯ НА ЭВМ

2. 1. СПОСОБЫ ФОРМИРОВАНИЯ СЛУЧАЙНЫХ РАВНОМЕРНО РАСПРЕДЕЛЕННЫХ ЧИСЕЛ

2. 2. МОДЕЛИРОВАНИЕ СЛУЧАЙНЫХ СОБЫТИЙ И ДИСКРЕТНЫХ СЛУЧАЙНЫХ ВЕЛИЧИН

2. 3. МОДЕЛИРОВАНИЕ СЛУЧАЙНЫХ ВЕЛИЧИН ПО ЗАДАННЫМ ЗАКОНАМ

РАСПРЕДЕЛЕНИЯ

2.3.1. Моделирование случайной величины, распределенной по показательному закону 2.3.2. Моделирование случайной величины, распределенной по линейному закону 2.3.3. Моделирование случайнойвеличины, распределенной по равномерному закону 2.3.4. Моделирование случайной величины, распределенной по закону Вейбулла 2.3.5. Моделирование случайной величины, распределенной по нормальному закону 2.3.6. Моделирование пуассоновского потока 2.3.7. Моделирование потока Эрланга 2.3.8. Моделирование гиперэкспоненциального распределения

2.4. МОДЕЛИРОВАНИЕ ЦЕПЕЙ МАРКОВА С ДИСКРЕТНЫМ ВРЕМЕНЕМ

2.5. ОПРЕДЕЛЕНИЕ ОБЪЕМА ИМИТАЦИОННЫХ ЭКСПЕРИМЕНТОВ

3. 1. ОСНОВНЫЕ ПРИНЦИПЫ МОДЕЛИРОВАНИЯ НЕПРЕРЫВНО-СТОХАСТИЧЕСКИХ

СИСТЕМ

3.2. МОДЕЛИРОВАНИЕ ПРОЦЕССОВ В ОДНОКАНАЛЬНОЙ СИСТЕМЕ МАССОВОГО

ОБСЛУЖИВАНИЯ С ОТКАЗАМИ

3.3. МОДЕЛИРОВАНИЕ ПРОЦЕССОВ В МНОГОКАНАЛЬНОЙ СИСТЕМЕ С ОТКАЗАМИ

3.4. МОДЕЛИРОВАНИЕ ПРОЦЕССОВ В ОДНОКАНАЛЬНОЙ СИСТЕМЕ С ОГРАНИЧЕННЫМ

ОЖИДАНИЕМ

ВВЕДЕНИЕ

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

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

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

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

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

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

1. СУЩНОСТЬ ИМИТАЦИОННОГО МОДЕЛИРОВАНИЯ.

ОБЛАСТИ ПРИМЕНЕНИЯ ИМИТАЦИОННЫХ МОДЕЛЕЙ

1. 1. Области применения имитационного моделирования в Современный этап развития машиностроения характеризуется бурным внедрением автоматизированных систем управления технологическими процессами и производством в целом, гибких автоматизированных производств на базе робототехнических систем.

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

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

Аналитическая модель здесь проста. Для большого числа исходных деталей вероятность брака Рбр = 2 -5 = 0, 5 5 = 0, 1375.

Решим задачу розыгрышем, путем бросания монеты пять раз подряд. Если во всех случаях при бросании монеты выпадает герб или только плата, будем считать изделие бракованным. Повторим этот опыт много раз. Для общего числа N испытаний получим К случаев попаданий только одной стороны монеты (герба или платы). Тогда отношение К / N будет в определенной степени соответствовать вероятности брака.

Результат будет достоверным лишь при большом числе испытаний. Уже на этом примере видно, что для проведения статистического моделирования требуется большое число испытаний, которое без помощи ЭВМ реализовать практически невозможно.

В данном примере аналитическое решение задачи оказалось проще.

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

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

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

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

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

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

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

Оптимальное распределение ресурсов и плановых заданий между подразделениями.

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

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

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

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

Моделирование является одним из основных средств исследования закономерностей объекта, явления, процесса. Известны три основные формы моделей — аналитические, имитационные и экспериментальные.

Аналитическая модель базируется на математическом описании объекта /1,2 /. Анализ характеристик объекта по аналитическим зависимостям может быть проведен лишь при значительной степени абстракции модели по отношению к отображаемому объекту. Как правило, при создании аналитической модели приходится идти на существенные упрощения и допущения, что может привести к получению лишь общих приближенных и даже недостоверных результатов. Если выбранные критерии, характеризующие поведение объекта, удается выразить в виде аналитических зависимостей, то такая модель имеет решение. Однако при исследовании многих объектов аналитическое решение в явном виде не получается. Например, часты ситуации, когда решение представляется в виде преобразования Лапласа, или в виде системы сложных интегродифференциальных уравнений. Следует отметить, что в последние годы возможности исследования аналитических моделей значительно возросли благодаря бурному развитию и внедрению методов вычислительной математики с численным решением на ЭВМ.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

В стохастических моделях или внешнее воздействие, или внутренние параметры связаны со случайными факторами. Эти модели оперируют соответственно с дискретным и непрерывным временем.

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

воспроизводимых уравнений.

В цифровой ЭВМ структура остается неизменной, а изменяется последовательность работы ее узлов в соответствии с заложенной в нее программой. Сравнение АВМ и ЦВМ наглядно показывает разницу между имитационным и статистическим моделированием.

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

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

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

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

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

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

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

Дискретно-стохастические модели (P-схемы) Применяются при исследовании работы вероятностных автоматов.

В автоматах этого типа переходы из одного состояния в другое осуществляются под воздействием внешних сигналов и с учетом внутреннего состояния автомата. Однако в отличие от Г-автоматов, эти ] перехода не строго детерминированы, а могут осуществляться с определенными вероятностями.

Пример такой модели представляет дискретная марковская цепь с конечным множеством состояний. Анализ F-схем основан на обработке и преобразовании матриц вероятностей переходов и анализе вероятностных графов. Уже для анализа сравнительно простых устройств, поведение которых описывает ся F-схемами, целе сообразно применение имитационного моделирования. Пример такого моделирования приведен в рассматриваемых как системы массового обслуживания. В качестве процесса обслуживания могут быть представлены различные по своей физической природе процессы: потоки поставок продукции предприятию, потоки комплектующих заказных деталей и изделий, потоки деталей на сборочном конвейере, потоки управляющих воздействий от центра управления АСУ на рабочие места и обратные заявки на обработку Как правило, эти потоки зависят от многих факторов и конкретных ситуаций. Поэтому в большинстве случаев эти потоки случайны во времени с возможностью изменений в любые моменты. Анализ таких схем производится на основе математического аппарата теории массового обслуживания. К ним относится непрерывная марковская цепь. Несмотря на значительные успехи, достигнутые в разработке аналитических методов, теория массового обслуживания, анализ Q-схем аналитическими методами может быть проведен лишь при значительных упрощающих допущениях и предположениях. Детальное исследование большинства этих схем, тем более таких сложных, как АСУТП, робототехнические системы, может быть проведено только с помощью имитационного моделирования.

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

]

2. ОРГАНИЗАЦИЯ ИМИТАЦИОННОГО

МОДЕЛИРОВАНИЯ НА ЭВМ

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

При табличном способе случайные числа заранее формируются с помощью специального механического (простейший вид рулетка) или электронного устройства. Последовательность таких чисел затем записывается в память ЭВМ. Данный способ не получил распространения вследствие трудоемкости заготовки таблиц, необходимости в большом объеме памяти, отводимой под эти таблицы, больших затратах времени в процессе моделирования при размещении этой таблицы во внешнем При аппаратном способе последовательность случайных чисел вырабатывается отдельным электронным узлом-генератором случайных В ГСЧ используется задающий элемент — источник шумов, которые затем усиливаются, селектируются на определенном уровне с последующим формированием последовательности случайных импульсов с равновероятным появлением токовых и бестоковых, или нулевых и единичных импульсов (Р0 = Р1 = 0,5) на любом месте такой случайной по следовательно сти. Недо статками данного метода являются необходимость аппаратного усложнения ЭВМ и невозможность повторного получения идентичных последователей, что важно при отладке программ и проведении сравнительных расчетов.

Для обеспечения возможности неоднократного воспроизведения ] одинаковых последовательностей можно использовать так называемые генераторы псевдослучайных чисел (ГПСЧ), схемно реализованные в регистрах сдвига с обратными связями. При длине регистра сдвига, равной n разрядов, получается псевдослучайная последовательность с максимальной длиной 2n-1 импульсов (тактов).

Следует отметить, что с совершенствованием технологии микросхем изготовление большой интегральной схемы (БИС) на одном кристалле, вмещающем в себя регистр с обратной связью, например, на 60-90 разрядов, на сегодняшний день не представляется затруднительным.

Естественно, что такой ГПСЧ, имеющий периодичность 290 1027 тактов, может рассматриваться как генератор случайных чисел. Например, при моделировании сложной задачи, на которую необходимо затратить восемь часов непрерывной работы шестнадцатиразрядной ЭВМ с расходом случайных чисел через 2 мс потребуется 3600 • 8 • 103 • 16 4,5 • тактов. Поэтому наличие в ЭВМ дополнительной БИС, реализующей ГПСЧ, представляется перспективным направлением. Быстродействие ЭВМ при этом выше, чем при использовании других способов получения случайных чисел, так как ЭВМ в процессе моделирования будет использовать готовые числа от внутреннего датчика — БИС ГПСЧ.

На сегодняшний день наибольшее распространение имеет алгоритмический способ получения случайных чисел. Еще на ранних стадиях создания ЭВМ основоположник ЭВМ Нейман предложил следующий способ. Берется произвольное число, состоящее из 2n двоичных цифр. Величина 0 возводится в квадрат, который состоит уже из 4n цифр. Далее выбирается 1 из 2n средних двоичных цифр квадрата, и в дальнейшем процесс повторяется в той же последовательности.

В настоящее время в основном используется так называемый конгруэнтный алгоритм Лемера. Числа а и b конгруэнтны по модулю m, если их разность кратна числу m. Отношение сравнения (конгруэнтности) записывают так a: b(mod m). Эта запись означает, что разность a b делится на m без остатка или, другими словами, числа a и b дают ] одинаковый остаток при делении на m. Например, 1364 = 4(mod 10), 1262 = 162(mod 100). Применяются следующие конгруэнтные алгоритмы получения случайных чисел:

r i+1 = a ri (mod m) мультипликативный алгоритм, a, m -неотрицательные целые числа, ri, ri+1 очередное и последующее случайное число, ri+1 ri + ri-1 (mod m) аддитивный алгоритм.

По данным выражениям легко составляется стандартная подпрограмма получения случайных чисел. Например, при использовании мультипликативного алгоритма для получения последующего случайного числа ri+1 нужно взять последнее случайное число ri умножить его на a и взять модуль полученного числа по m, т.е. разделить на m и принять за остаток ri+1. Выбор a, m, r0 (первого числа) производится из условия обеспечения минимальной корреляции между генерируемыми числами и максимального периода повторения последовательности цифр. Обычно m=2b, где b число двоичных цифр в машинном слове.

Во всех выпускаемых в настоящее время ЭВМ, включая микроЭВМ, заложена стандартная подпрограмма RANDOM (случайный), сокращенно записываемая RAND или RND, по которой вырабатывается случайное число, равномерно распределенное в интервале 0 < r < 1.

Например, подпрограмма для ЕС ЭВМ, записанная на языке ФОРТРАН,

RETURN

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

IY — полученное целое случайное число, требуемое при последующих обращениях к подпрограмме 0 < IY Р событие не имеет места (рис. 2. 1).

На принципе попадания случайного числа r на то или иное место участка 0-1 можно моделировать более сложные случаи.

Для полной группы событий, имеющих вероятности P1+P2+...+Pn=1, необходимо интервал 0-1 разделить на n частей, длины каждой из которых равны соответственно значениям P1, P2,...Pn. При попадании случайного числа на отдельный участок, например участок К, считается, что наступило Например, согласно рис. 2.2, наступило событие А3. При этом В ходе моделирования генерируемая случайная величина последовательно сравнивается с элементами массива, возрастающих чисел ] Вариант алгоритма моделирования полной группы событий показан на рис. 2. 3. Значение А будет соответствовать разыгранному событию и используется для дальнейшего решения. Следует заметить, что проверка условия i>n в этом алгоритме является излишней, так как всегда r < 1, а последнее значение элемента массива Р (n) =1.

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

Например, для двух событий А и В возможны следующие варианты При r1< А и r2 < В принимается, что наступило сложное событие При моделировании сложных зависимых событий А и В, наряду с вероятностями Ра, Рb, необходимо учитывать условную вероятность наступления события В при условии, что событие А имело место (Рb/a). Эта вероятность задается в качестве исходной величины.

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

r1 < Рa, r2 < Pa / b принимается событие АВ;

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

Рассмотренный способ моделирования полной группы событий может быть использован также для моделирования дискретной случайной величины Х с заданным законом распределения Р (Х i ) = P i, i = 1 n, При попадании генерируемого случайного числа r на участок К принимается, что случайная величина Х приняла значение Хk.

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

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

Как известно, случайная величина Х описывается интегральной этих функций, можно предсказать поведение случайной величины во времени. Обе функции связаны между собой ] Интегральная функция представляет собой вероятность того, что какое-то взятое фиксированное значение Х будет меньше текущего Найдем распределение этой величины Fr (r).

На основании приведенных выражений Согласно выражению (2.1), вероятность попадания случайной величины в интервал 0 – r равна длине этого интервала, и это есть признак того, что данное распределение равномерное.

В результате получаем алгоритм формирования непрерывной случайной величины Х по заданному закону распределения. Поскольку ri = F ( xi ), то необходимо выполнить преобразование ri — равномерно распределенное случайное число;

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

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

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

В соответствии с выражением (2.2) имеем ri = 1 – e -xi. Разрешив его относительно xi, получим xi = -(1/ )ln(1-ri).

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

(i = 2, S = S + A(2) = 0,35) и вновь производится сравнение r и S. Эта цепь алгоритма выполняется до нарушения условия r>S, когда для данного примера i = 4, S = 0,69. С этого момента начинают выполняться блоки 7, 8, а именно, разыгрывается новое значение равномерно распределенной случайной величины и определяется интервал до момента времени наступления нового события по экспоненциальному распределению с параметром выбранной фазы (4) = 0,36. Полученная случайная величина ] затем используется в основной программе имитационного моделирования исследуемого процесса.

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

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

Рассмотрим систему, состоящую из трех измерительных комплектов (Ж), контролирующих параметры технологического процесса. Результаты измерений подаются в центральный управляющий вычислительный комплекс АСУ через фиксированные интервалы времени Т. В момент передачи измерительных сигналов система может находиться в различных состояниях, характеризующихся количеством неисправных ИК (рис. 2. 15).

] Состояние Е0 соответствует исправному состоянию всех трех ПК. За время Т система может остаться в этом состоянии с вероятностью P00 или же перейти в другие состояния Еi, (i =1, 2, 3), при которых неисправны i измерительных комплектов с соответствующими вероятностями Р0i. При нахождении системы в состоянии Еi она может перейти в другое состояние с вероятностью Pij или остаться в прежнем состоянии с вероятностью Pij.

Система считается работоспособной, если исправны не менее двух приборов. В этом случае из трех потоков сигналов методом выбора по большинству выбираются идентичные сигналы, которые принимаются за истинные. При наличии хотя бы двух исправных ПК измерительные сигналы с их выходов будут идентичными. Сигналы третьего ИК при этом в расчет приниматься не будут. Такая система является реализацией так называемого метода мажоритарного резервирования, применяемого для повышения надежности работы системы. Очевидно, состояния Е0, Е1 будут соответствовать случаю, когда система работоспособна, а состояния Е2, Е — случаю отказа системы.

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

Промежуточные состояния и переходы системы внутри интервала t i t i + (t i + 1 – t i = Т), нас не интересуют. С этой точки зрения рассматриваемая система относится к цепи Маркова с дискретным временем. Таким образом, рассматривае ] мая система, в зависимости от методов ее анализа, может рассматриваться как цепь Маркова с непрерывным или дискретным временем.

Для определения марковской цепи необходимо знать совокупность начальных состояний Р i, соответствующих нахождению системы в начальный момент времени в состоянии Еi. Кроме того, для установления зависимостей, связывающих каждую пару состояний (Еi, Еj), составляется матрица вероятностей переходов:

где ] j =1 для каждого фиксированного значения I, так как каждая строка матрицы состоит из вероятностей, составляющих полную группу событий переходов из состояния i в любое возможное состояние j, включая Данная матрица называется стохастической. Если характеристики установившегося режима не зависят от начальных вероятностей Рi (0), то такая марковская цепь называется эргодической.

Процесс моделирования рассмотренной цепи Маркова состоит в заданной матрицей переходов. Алгоритм моделирования будет основан на определении марковской цепи, а именно на том, что исход каждого последующего перехода зависит только от результата предыдущего. При моделировании необходимо взять (n+1) участков (0, 1). Первый участок разбивается на отрезки в соответствии с вероятностями начальных соответствующими строкам матрицы P1i, P2i,..., Pni (рис. 2.16).

] При моделировании вначале определяется начальное состояние ] распределенное на участке (0, 1), Затем, согласно вышеописанной процедуре моделирования дискретной случайной величины, определяется состояние Sk, исходя из условия РК (0) < r < Pk+1 (0) для первого участка.

Вновь разыгрывается следующее случайное число и сравнивается с вероятностями К, строки матрицы Рki. Состояние системы не изменится при условии Рк,к < r < Рк,к+1 или осуществится переход в следующее состояние при условии Дальнейшие шаги моделирования идентичны. При большом числе испытаний N система Lk раз будет находиться в К состоянии. Отношение Lk /N будет соответствовать вероятности К состояния (P(Sk) = Lk /N).

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

2.5. Определение объема имитационных экспериментов Объем моделирования определяется характером исследуемых величин (случайных событий, величин или процессов), требуемой точностью, конкретными условиями проведения моделирования.

Определим необходимое число экспериментов при оценке вероятности наступления события, оценкой которой является частота P* = L / N, где L — количество успешных опытов в процессе случайной величиной, так как она будет принимать разные значения при повторении серии опытов N. Согласно предельной теореме теории вероятностей, случайная величина P* распределена приблизительно по нормальному закону.

Введем дискретную случайную величину Z с законом ] Математическое ожидание и дисперсия величины Z равны Затем определим математическое ожидание и дисперсию случайной Найдем число испытаний, при котором значение Х отличается от вероятности P* меньше, чем на заданную величину с заданной достоверностью.

С учетом нормального закона распределения величины ] X выражение ( 2. 23) будет иметь вид При моделировании величина Р* обычно неизвестна. Поэтому вначале проводится моделирование объемом N = 50 100 выборок, по ] которому определяется P*, а затем из (2. 26) окончательно находится N.

В табл. 2.2. приводится необходимое число реализации для получения оценки L / N с точностью и достоверностью = 0,95 для различных значений Р*.

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

]

3. РЕШЕНИЕ ЗАДАЧ, ОПИСЫВАЕМЫХ НЕПРЕРЫВНОСТОХАСТИЧЕСКИМИ МОДЕЛЯМИ

Непрерывно-стохастические системы наиболее характерны для исследования вероятностных моделей компьютерных сетей.

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

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

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

Сам характер проце ссов, происходящих в непрерывностохастических системах, исходит из того факта, что состояние отдельных ее узлов изменяется с моментом времени, совпадающего с наступлением определенных событий — поступлением очередной заявки на обслуживание, окончания ее обработки, момента выхода из строя ] оборудования и т.п. Поэтому моделирование таких систем удобно проводить, используя событийный принцип. Этот принцип заключается в том, что текущее время в моделируемой системе изменяется дискретно, проходя последовательно через все события, т. е. моменты изменения состояния блоков системы. Момент наступления следующего события в системе определяется минимальным значением моментов времени из их списка будущих событий, которые будут происходить в каждом блоке В процессе имитационного моделирования этих потоков заявок можно определить случайные времена наступления первого и второго события при каждой реализации ( соответственно t1 и t2). При t1 N блок 10), то поступившая заявка теряется ( Nn= Nn+1 блок 16). Затем генерируется время поступления следующей заявки t1, (блоки При минимальном времени окончания обслуживания заявки в i приборе ( t2(i) = min, t2(i) < Тм ) фиксируется число обслуженных заявок ( Nоб = Nоб + 1), находится время пребывания заявки в системе tпр = t2(i)— t1(i), после чего устанавливаются исходные данные для освободившегося прибора (Z (i) = 0, t1(i) = t2(i) = ) (блоки 21-24). Следует заметить, что ] блок 22, в котором определяется время пребывания заявки в системе, может быть опущен, так как это время будет соответствовать задаваемому времени об. Введение этого блока позволяет контролировать соответствие вырабатываемых ЭВМ случайных чисел с заданным законом.

По окончании моделирования (t2 > Тм ) осуществляется вывод на печать полученных результатов — Nn, Nоб, N, Рn = N / Nn, гистограммы распределения tпр в случае надобности.

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

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

Ограничения на ожидание определяются допустимой длиной очереди М g =2. Поступающая в момент времени t 1 первая заявка застает обслуживающий прибор ОП свободным и сразу же начинает обслуживаться, время начала ее обслуживания t1'' равно времени ее поступления в систему t1'' = t1. Поступающие заявки образуют поток событий с заданным законом распределения. Время занятости обслуживающего прибора (длительность обслуживания) является случайной величиной, также описываемой конкретным законом распределения. Заявки в системе обслуживаются в порядке очереди, т.е. в том порядке, в котором они поступили в систему. Для рассматриваемого случая первая заявка успевает отслужиться в момент времени t1об раньше поступления следующей заявки. Поэтому поступающая в момент t вторая заявка застает обслуживающий прибор свободным и сразу же поступает на обслуживание t2'' = t2. Во время обслуживания этой заявки ] ] тельностью 2 в моменты времени t3, t4, t5 поступают следующие заявки, которые застают ОП занятым. Третья и четвертая заявки дожидаются освобождения прибора от обслуживания предыдущей заявки, после чего сразу же принимаются на обслуживание t3'' = t2об, t4'' = t3об. Для пятой заявки нарушается условие допустимой длины очереди Mg = 2, так как эта заявка поступила еще в момент обслуживания второй заявки. В результате этого эта заявка получает отказ в обслуживании. Следующая шестая заявка поступает в момент обслуживания третьей заявки, т.е. становится второй в очереди за четвертой заявкой. Следовательно, она может ожидать начала своего обслуживания.

Один из вариантов блок-схемы алгоритма для реализации системы с ограниченным ожиданием на ЭВМ приведен на рис. 3.6. В первом блоке этой модели задаются необходимые исходные данные — число поступивших заявок i = 0, число обслуженных и потерянных заявок Nоб = 0, Nn = 0, допустимая длина очереди Мg, начальные значения времени поступления и обслуживания t0 = 0, t0об = 0. Необходимо задать также моделирования на ЭВМ Тм, вид и параметры входящего потока заявок и времени обслуживания. Например, для пуассоновского потока заявок при экспоненциальном распределении времени обслуживания одной заявки задается интенсивность пуассоновского потока и интенсивность обслуживания µ. В блоке 2 предусматривается реализация подпрограммы формирования времени генерации очередной заявки 3, в соответствии с заданным потоком распределения. Примеры таких подпрограмм были рассмотрены в главе 2. Блоки 3, 4 отражают количество i и момент времени поступления в систему очередной заявки ti = ti-1 + 3. После формирования очередной заявки осуществляется проверка на достижение в ЭВМ заданного времени моделирования (t1>Тм?, блок 5). При невыполнении этого условия осуществляется следующая проверка сравнения времени поступления очередной заявки со временем окончания обслуживания предыдущей заявки (ti < tобi-1, блок 6). При выполнении этого условия, т.е.

] при занятом состоянии ОП, проверяется условие превышения допустимой длины очереди (i > Мg, блок 7). Если очередь выше допустимой, то вновь поступившая заявка теряется, что фиксируется в счетчике потерянных заявок (Nn = Nn+1, блок 8). Для продолжения работы модели условно принимается, что момент времени окончания обслуживания потерянной Затем осуществляется возврат к формированию следующей заявки. При наличии очереди заявок в допустимых пределах ( i Mg ). время начала обслуживания поступившей заявки принимается равным времени Определение ti'' осуществляется также в блоке II, переход к которому происходит в ситуации, когда вновь поступившая заявка застает ОП свободным (при условии ti ti-1об ). В этом случае заявка сразу же принимается на обслуживание (ti'' = ti, блок II). В блоках 12-15 реализуется процесс обслуживания очередной заявки. В блоке 12, аналогично блоку 2, реализуется подпрограмма формирования времени обслуживания об в соответствии с заданным временем его распределения, в блоке определяется момент окончания времени обслуживания tiоб = ti'' + об, в блоке 14 находится общее время пребывания заявки в системе, включая время ее ожидания и время обслуживания i = tiоб — ti. Блок осуществляет подсчет общего числа обслуженных заявок Nоб = Nоб + 1.

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

обслуживания с ожиданием сравнительно прост, но весьма неэкономичен в отношении использования памяти ЭВМ, так как необходимо предусмотреть массивы t (i), t"(i), t об (i), (i) для больших значений i.

] Например, при интен ] сивности пуассоновского потока заявок =10 заявок/мин при Тм=I час среднее значение поступивших заявок составит i = 600. Для получения достоверных оценок моделирования, особенно при построении гистограммы i, потребуется значение i порядка нескольких тысяч.

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

Во втором варианте используются два особых состояния системы — время поступления очередной заявки t3 без учета ее номера и время обслуживания tоб. Выполнение условия t3 < tоб соответствует случаю поступления в данный момент времени очередной заявки. Вслед за этим определяется состояние обслуживающего прибора. При Z = 0 (блок 6) ОП свободен. Тогда время начала обслуживания этой заявки совпадает со временем ее поступления, а ОП переходит в занятое состояние (Z = 1, блок 7). Данное значение времени фиксируется в качестве первого элемента массива заявок T3 (1) = t3, блок 8. Затем выполняется подпрограмма формирования времени об и определяется момент времени окончания обслуживания данной заявки tоб = t3+ об ( блоки 9, 10), после чего осуществляется переход на формирование новой заявки.

Если поступающая заявка застает обслуживающий прибор занятым (Z 0, блок 6), то значение очереди заявок увеличивается на единицу (Z = Z+1, блок II), и осуществляется проверка на превышение допустимой обслуживания поступившей заявки Nn= Nn + 1, после чего общая очередь Z уменьшается на 1. При Z Mg, в массив заявок записывается значение времени поступившей заявки (T3(z)= t3, блок 13).

наступления другого события в системе— окончанию обслуживания очередной заявки, которая в массиве заявок является первой. После этого определяется время пребывания заявки в системе np = tоб — t3(1), сразу же определяется соответствующий интервал гистограммы, в который попадает значение об (блок 17), фиксируется число обслуженных заявок ] Nоб = Nоб+1 (блок 18), число заявок в системе Z уменьшается на I ( блок 18). Затем проверяется условие освобождения обслуживающего прибора (Z = 0, блок 20). Ситуация Z=0 соответствует случаю, когда в момент окончания обслуживания очередной заявки другие заявки в ОП не поступили. Обслуживающий прибор становится свободным и находится с этого момента в режиме простоя, ожидая поступления следующей заявки.

Поскольку время окончания обслуживания еще не поступившей заявки неизвестно, то оно условно принимается равным бесконечности ( tоб =, блок 21). При составлении программы на ЭВМ это время следует задавать большим числом, например, больше Тм. Аналогично это большое значение для tоб задается в начале выполнения программы ( блок I).

Ситуация Z 0 ( блок 20) соответствует случаю, когда по окончании обслуживания очередной заявки имеется массив других заявок на обслуживание. Сразу же по освобождении ОП он приступает к обслуживанию следующей заявки, находящейся первой в очереди. При этом длина очереди уменьшается на единицу. Соответственно, уменьшается на единицу номер каждой заявки очереди. Коррекция очереди осуществляется в блоках 22,23. Затем определяется время и момент окончания обслуживания для заявки под номером 1, и производится возврат к блоку 5 на сравнение нового времени окончания обслуживания первой заявки из очереди tоб со временем поступления в систему следующей заявки t3.

По окончании заданного времени моделирования (t3 > Тм,блок 4 ) осуществляется выдача на печать гистограммы времени пребывания заявок в системе (гист пр, блок 26), числа потерянных и обслуженных заявок ( Nn, Второй вариант алгоритма требует значительно меньшей памяти ЭВМ, так как в нем хранится лишь один массив очереди заявок t(z) и нет необходимости запоминать массивы всех поступивших и обслуживаемых заявок, по сравнению с первым вариантом.

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

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

На рис.3.8 приведена блок-схема алгоритма имитационного моделирования сети без восстановления неисправностей. В качестве исходных данных вводятся интенсивности отказов отдельных узлов и соединительных путей между ними ( i, ij ), общее число отказов, разыгрываемых на ЭВМ в процессе моделирования Nмод, число узлов и матрица соединений между узлами.

В начале вычислений определяются возможные пути соединений между рассматриваемыми узлами.

Пример установления соединений для мостиковой схемы на основе последовательной фиксации соединений от исходного узла с непосредственно присоединительными к нему следующими узлами (построение дерева соединений) приведен на рис. 3.9, 3.10. Блок-схема алгоритма определения путей соединений приведена на рис.3.11.

Процесс моделирования продолжается до достижения заданного числа отказов Nмод. В случае отказа узла, не приводящего к отказу системы, данный узел далее не рассматривается ( = i, i = 0) и производится корректировка возможных путей соединений путем исключения путей, проходящих через отказавший узел или соединение. В ] заключение по статистическим формулам находятся среднее время безотказной работы и вероятность безотказной работы системы Тс*, Рс*, а также гистограммы распределения массива Тст* ( i=1— Nмод ).

Оценку показателей надежности для сети с восстановлением необходимо производить с учетом условий восстановления отказавшего узла (рис. 3.12-3.15 ).

Для рассматриваемой сети отказ наступает при одновременном выходе из строя узлов 1,3 или 2,4.

На рис. 3.12 приводится вариант неограниченного восстановления, когда одновременно могут восстанавливаться все отказавшие узлы.

] Восстановление начинается сразу же после отказа любого узла, время восстановления не зависит от состояния сети. Приняты обозначения — toi, tbi, текущее время наступления отказа, восстановление Z — индекс работоспособного (Z= 0) или отказового состояния (Z=1) iго узла, i— отказа i узла. Время отказового состояния системы определяется, пока ремонтируются все узлы ( 1 и 3, 2 и 4), вызвавшие отказовую ситуацию.

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

Условия ремонта сети, согласно рис.3.13, отличаются тем, что время отказового состояния сети определяется временем восстановления всех ] отказавшихся узлов. Считается, что во время ремонта остальные узлы не На рис.3.14 приведен вариант восстановления системы во время плановых профилактических работ, проводимых независимо от состояния системы. Время отказового состояния системы включает в себя время ожидания ближайшей профилактики и время самой профилактики. После проведения профилактики системы полностью восстанавливается. На рис. 3.15 приведен вариант ограниченного восстановления, когда отказавшийся узел ожидает окончания ремонта предыдущего узла и время перерыва t на доставку ремонтного органа от одного узла к другому. В общем случае условия проведения ремонтных работ могут быть разнообразными для каждой конкретной системы.

На рис.3.16 приведена блок— схема алгоритма оценки показателей надежности сети с восстановлением применительно к рис.3.12.

]

СПИСОК ЛИТЕРАТУРЫ

1. Бусленко Н. П. Моделирование сложных систем. - М.: Наука, 1978.

2. Советов Б. Я., Яковлев С. А. М.: Высшая школа, 1985.

3. Лукьянов В. С. Решение задач в машиностроении методами имитационного моделирования: Учеб. пособие, ВолгПИ. Волгоград, 1989.

] Лицензия ЛР № 020251 от 16.04.1996г.

Бумага газетная. Печать офсетная.

Волгоградский государственный технический университет 400131 Волгоград, пр. Ленина, 28.

РПК “Политехник” Волгоградского государственного технического 400131 Волгоград, ул. Советская, 35.

]