Перечисление графов функционирования систем

Гориславский Ростислав Станиславович

Перечисление графов функционирования систем

Гориславский Ростислав Станиславович. Перебор графов функционирования систем. Научный руководитель: д.ф.-м.н., проф. Сушков Юрий Акимович. Направление прикладная математика и информатика, вычислительная стохастика и статистические модели. В результате дипломной работы были получены следующие результаты: выполнен анализ систем, состоящих из 2 аппаратов, на каждом из которых могут выполняться 2 операции; произведена классификация схем функционирования таких систем; была написана программа, позволяющая автоматически составлять граф перехода состояний, моделировать работу системы 3 различными методами, анализировать различные характеристики эффективности работы системы. Количество использованных источников: 3. Гориславский, Р. С. Перебор графов функционирования систем: бакалаврская работа / Гориславский Ростислав Станиславович. – СПб., 2016. – 23 с. – Библиогр.: с. 23.

Математика

Дипломы

Вуз: Санкт-Петербургский государственный университет (СПбГУ)

ID: 587d36415f1be77c40d58ac1

UUID: 9515e2e7-121c-4386-a774-4134115a716b

Язык: Русский

Опубликовано: больше 7 лет назад

Просмотры: 14

Гориславский Ростислав Станиславович

Источник: Санкт-Петербургский государственный университет

Комментировать 0

Рецензировать 0

Скачать - 265941 bytes

Поделиться работой

Санкт-Петербургский государственный университет Прикладная математика и информатика Вычислительная стохастика и статистические модели Гориславский Ростислав Станиславович Перебор графов функционирования систем Бакалаврская работа Научный руководитель: д. ф.-м. н., профессор Ю. А. Сушков Рецензент: к. ф.-м. н., доцент Ю. Н. Каштанов Санкт-Петербург 2016

Saint Petersburg State University Applied Mathematics and Computer Science Computational Stochastics and Statistical Models Gorislavskii Rostislav Stanislavovich Enumeration of graphs of system functionality Bachelor’s Thesis Scientific Supervisor: Associate Professor U. A. Sushkov Reviewer: Associate Professor U. N. Kashtanov Saint Petersburg 2016

3 Оглавление Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 Глава 1. Перебор схем функционирования систем . . . . . . . . . . . . . . . . 5 1.1. Обозначения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.2. Требования, выдвигаемые для схем . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.3. Классификация схем . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 Глава 2. Анализ схемы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.1. Графы перехода состояний систем . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.2. Численные характеристики системы . . . . . . . . . . . . . . . . . . . . . . . . 11 Глава 3. Автоматизация процесса моделирования систем . . . . . . . . . . . . 14 3.1. Построение графа перехода состояний в режиме диалога . . . . . . . . . . . . 14 3.2. Моделирование систем . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 Глава 4. Программа . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 Заключение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 Список литературы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

4 Введение В наше время человечество стремится во всех управленческих решениях достичь наи большей выгоды. Лицам, принимающим такие решения, необходимо учитывать множество факторов, влияющих на поведение систем массового обслуживания, которыми они управ ляют. Поэтому становится все более актуальным разработка математических моделей раз личного типа для анализа современных проблем. Под системой в данной работе будет подразумеваться именно система массового об служивания (магазин, цех, СТО, банк). В систему с некоторой интенсивностью поступают заявки. Узлом системы будет называться такой ее элемент, который способен выполнять некоторые операции над поступающими на него заявками (например, мастер у станка, опе рационист в банке, кассир и т.д.). В данной работе рассматривается общий класс систем 𝑆 , состоящих из двух узлов: 𝐴 и 𝐵 , которые обрабатывают поступающие в систему с интенсивностью 𝜆 заявки. На каждом из узлов могут выполняться 2 операции Ω1 , Ω2 , за среднее время 𝜏1 и 𝜏2 соответственно, также операция Ω12 , которая является последовательным выполнением операций Ω1 и Ω2 за время 𝜏12 6 𝜏1 + 𝜏2 . Операция Ω1 приоритетней операции Ω2 , что означает, что Ω1 должна выполняться раньше Ω2 . Для оценки качества работы системы могут рассматриваться такие количественные ха рактеристики, как среднее количество обработанных заявок, среднее относительное время, которое система проводит в том или ином состоянии.

5 Глава 1 Перебор схем функционирования систем 1.1. Обозначения Для описания схем функционирования систем введем следующие обозначения. Для каждой операции 𝑖 = 1, 2 и 𝑗 = 𝐴, 𝐵 : ∙ Ω𝑗𝑖 означет, что операция Ω𝑖 является основной именно на узле 𝑗 , таким образом, при наличии свободного узла 𝑗 операция Ω𝑖 будет выполняться на нем, а узел, на котором Ω𝑖 является основной, обозначим через 𝑀𝑖 ; ∙ (Ω𝑗𝑖 ) означает, что операция Ω𝑖 является условной на узле 𝑗 , т.е. выполняется на нем только, если узел 𝑀𝑖 занят; ∙ (Ω𝑗𝑖 , Θ) означает, что операция Ω𝑖 является условной на узле 𝑗 и выполняется следую щим образом: если узел 𝑀𝑖 занят, то заявка ждет время Θ. Если за это время узел 𝑀𝑖 освободился, Ω𝑖 выполняется на нем, иначе Ω𝑖 выполняется на узле 𝑗 ; ∙ (Ω𝑗𝑖 , ∞) означает, что операция Ω𝑖 является условной на узле 𝑗 и выполняется следу ющим образом: если узел 𝑀𝑖 занят, то заявка поступает на узел 𝑗 и ждет до тех пор, пока узел 𝑀𝑖 не освободится; ∙ Ω𝑗𝑖 означает, что операция Ω𝑖 не выполняется на узле 𝑗 . Таким образом, было выделено 5 видов операций помимо операции Ω12 , и как видно из общего вида схем (таблица 1.1), всего возможно 900 вариантов схем функционирования систем. Таблица 1.1: Общий вид схем функционирования систем Узел 𝐴 Узел 𝐵 Операция 1 Ω1 |(Ω1 )|(Ω1 , Θ)|(Ω1 , ∞)|Ω1 |Ω12 Ω1 |(Ω1 )|(Ω1 , Θ)|(Ω1 , ∞)|Ω1 |Ω12 Операция 2 Ω2 |(Ω2 )|(Ω2 , Θ)|(Ω2 , ∞)|Ω2 Ω2 |(Ω2 )|(Ω2 , Θ)|(Ω2 , ∞)|Ω2

6 1.2. Требования, выдвигаемые для схем Для описания всех схем функционирования систем, рассматриваемых в данной работе, выдвинем несколько правил, по которым могут строиться эти самые схемы. Изначально заметим, что будем перебирать только неизоморфные схемы. В силу этого замечания сразу выдвигается требование, что операция Ω1 выполняется первой на узле 𝐴. 𝐵 Заметим, что ровно одна операция из Ω𝐴 𝑖 и Ω𝑖 должна быть основной. Этим правилом мы отсеиваем конструкции, которые представлены в таблицах 1.2 – 1.5, и изоморфные им. Таблица 1.2: Конструкция 1 вида Узел 𝐴 Узел 𝐵 Операция 1 Ω1 Ω1 |(Ω1 )|(Ω1 , Θ)|(Ω1 , ∞)|Ω1 Операция 2 Ω2 Ω2 Таблица 1.3: Конструкция 2 вида Узел 𝐴 Узел 𝐵 Операция 1 Ω1 Ω1 |(Ω1 )|(Ω1 , Θ)|(Ω1 , ∞)|Ω1 Операция 2 (Ω2 )|(Ω2 , Θ)|(Ω2 , ∞) (Ω2 )|(Ω2 , Θ)|(Ω2 , ∞) Таблица 1.4: Конструкция 3 вида Узел 𝐴 Узел 𝐵 Операция 1 Ω1 Ω1 |(Ω1 )|(Ω1 , Θ)|(Ω1 , ∞)|Ω1 Операция 2 Ω2 Ω2 Конструкции вида 1 и 2 не устраивают нас, потому что возникает неопределенность в выборе узла, на котором выполнять Ω2 . Конструкции 3 вида не являются схемами работы систем, т.к. Ω2 не выполняется ни на одном узле системы. А в конструкции 4 вида узел

7 Таблица 1.5: Конструкция 4 вида Узел 𝐴 Узел 𝐵 Операция 1 Ω1 Ω1 Операция 2 Ω2 |(Ω2 )|(Ω2 , Θ)|(Ω2 , ∞) Ω2 𝐵 вообще не принимает участия в работе системы, т.е. система состоит из 1 узла, что противоречит изначально поставленной задаче. 1.3. Классификация схем В ходе анализа поставленной задачи было выявлено 4 не пересекающихся класса допу стимых схем функционирования систем, которые будут представлены ниже. 1.3.1. Схемы I класса Под этот класс попадают схемы, описанные в таблице 1.6. Таблица 1.6: Схемы I класса Узел 𝐴 Узел 𝐵 Операция 1 Ω1 (Ω1 )|(Ω1 , Θ)|(Ω1 , ∞)|Ω1 Операция 2 Ω2 (Ω2 )|(Ω2 , Θ)|(Ω2 , ∞)|Ω2 В конечном счете было выявлено 8 схем, полученных пересечением данного класса с множеством схем, ограниченных выдвинутыми в предыдущем пункте требованиями, что на единицу меньше максимально допустимой мощности данного класса. А именно, были отброшена схемы, для которых на узле 𝐵 выполнялись операции (Ω1 , ∞), Ω1 . В таких схемах узел 𝐵 служит только для простоя и не принимает участия в работе системы, и, таким образом, они попадают под Конструкции 4 вида.

8 1.3.2. Схемы II класса Таблица 1.7: Схемы II класса Узел 𝐴 Узел 𝐵 Операция 1 Ω1 (Ω1 )|(Ω1 , Θ)|(Ω1 , ∞)|Ω1 Операция 2 (Ω2 )|(Ω2 , Θ)|(Ω2 , ∞)|Ω2 Ω2 Общий вид схем, попадающих под данный класс, представлен таблицей 1.7. В ходе рассмотрения элементов II класса схем было замечено, что все 16 схем, попадающие под общий вид данного класса, удовлетворяют требованиям, описанным в разделе 1.2. 1.3.3. Схемы III класса Таблица 1.8: Схемы III класса Операция 1 Узел 𝐴 Узел 𝐵 Ω12 (Ω12 ) Операция 2 Данный класс представлен таблицей 1.8 и состоит ровно из одной схемы. 1.3.4. Схемы IV класса Общий вид схем, попадающих под данный класс, представлен таблицей 1.9. Он состо ит из 2 схем: схемы, у которых на узле 𝐵 выполняются операции (Ω1 , ∞), Ω1 , абсолютно совпадают со схемой III класса.

9 Таблица 1.9: Схемы IV класса Узел 𝐴 Узел 𝐵 Операция 1 Ω1 (Ω12 ) Операция 2 Ω2 (Ω2 )|(Ω2 , Θ)|(Ω2 , ∞)|Ω2

10 Глава 2 Анализ схемы 2.1. Графы перехода состояний систем Рассмотрим некоторую систему 𝑆 . Как уже было сказано ранее, ей соответствует неко торая схема функционирования. На узлах системы выполняются операции Ω𝑖 строго опре деленным образом, установленным схемой системы. Следовательно, каждый узел системы может находиться в одном из нескольких состояний: 0 — узел свободен, 1 — на узле выполня ется Ω1 , 2 — выполняется Ω2 ,12 — выполняется Ω12 , 𝑤 — такое состояние узла, при котором заявка на этом узле не обслуживается, а только «занимает место» и ждет, пока освободится узел, на котором текущая операция является основной, а 𝑣1 и 𝑣2 — на узле выполняется (Ω1 , Θ) и (Ω2 , Θ) соответственно, при этом узел находится в ожидании. Таким образом, со стояние системы однозначно определяется состоянием его узлов, и будут записываться 𝑢𝑣 , где 𝑢 — состояние узла 𝐴, 𝑣 — узла 𝐵 . Под графом перехода состояний системы будем понимать ориентированный граф, вер шинами которого являются возможные состояния системы, а ребра — интенсивности пере хода из одного состояния в другое(величины, обратные среднему времени работы). Рассмот рим следующий пример, который поможет лучше понять данное определение. Пример 1. СМО работает по следующему принципу. На нее поступают заявки с ин тенсивностью 𝜆. Изначально система находится в состоянии покоя. При поступлении заявки над ней выполняется операция Ω1 на узле 𝐴, после этого заявка переходит на узел 𝐵 , где выполняется Ω2 . Если узел 𝐴 занят, то операция Ω1 образом система соответствует схеме Ω1 (Ω1 ) Ω2 Ω2 выполняется на узле 𝐵 . Таким . Узел 𝐴 может находиться только в состояниях 0, 1, 𝑤, а узел 𝐵 — в 0, 1, 2. Заметим, что единственный случай, когда узел 𝐴 может перейти в состояние 𝑤, это, когда на 𝐴 закончила выполняться Ω1 , а узел 𝐵 занят, а при его освобождении заявка сразу переходит на 𝐵 и выполняется Ω2 . Таким образом, система не может находиться в состоянии 𝑤0. Также заметим, что состояние 01 не допустимо, так как Ω2 не выполняется на 𝐴, а операция Ω1 выполняется приоритетнее на 𝐴.

11 𝜆 00 1/𝜃2𝐵 10 𝜆 1/𝜃1𝐴 02 11 1/𝜃2𝐵 𝜆 1/𝜃1𝐴 1/𝜃1𝐵 12 𝜔1 1/𝜃1𝐵 1/𝜃1𝐴 𝜔2 Рис. 2.1: Граф перехода состояний для Примера 1 В результате, построен граф перехода состояний, представленный на рисунке 2.1. Здесь Θ𝑗𝑖 — среднее время выполнения операции Ω𝑖 на узле 𝑗 . А следовательно, интенсивности перехода из одного состояния в другое обратно пропорциональны времени выполнения со ответствующей операции. 2.2. Численные характеристики системы Как было показано в предыдущем пункте, по схеме функционирования системы можем быть построен граф перехода состояний. В [1] был предложен метод исследования свойств системы по построенному графу перехода состояний. Рассмотрим применение данного ме тода на Примере 1. За 𝑝𝑖 (𝑡) обозначим вероятность того, что в момент времени 𝑡 система находится в со стоянии 𝑖. Для определенности, рассмотрим состояние 00. Найдем вероятность того, что в момент времени 𝑡 + ∆𝑡 система находится в состоянии 00. Разобьем это событие на 2: в момент времени 𝑡 система уже была в состоянии 00 и за время ∆𝑡 не вышла из этого состояния; в момент времени 𝑡 система была в состоянии 02 и за время ∆𝑡 перешла в состояние 00. Вероятность первого варианта найдем как произведение вероятности 𝑝00 (𝑡) того, что в момент времени 𝑡 система находится в состоянии 00, на условную вероятность того, что будучи в состоянии 00, система за время ∆𝑡 не перейдет в состояние 10. Эта условная веро ятность равна 1 − ∆𝑡𝜆. Аналогичные рассуждения и для нахождения вероятности второго варианта. В результате получена формула:

12 𝑝00 (𝑡 + ∆𝑡) = 𝑝00 (𝑡)(1 − ∆𝑡𝜆) + 𝑝02 (𝑡) ∆𝑡 . Θ𝐵 2 (2.1) Перенеся в левую часть 𝑝00 (𝑡) в формуле (2.1), поделив обе части на ∆𝑡 и перейдя к пределу при ∆𝑡 → 0, получим: 𝜕𝑝00 1 (𝑡) = −𝑝00 (𝑡)𝜆 + 𝑝02 𝐵 . 𝜕𝑡 Θ2 (2.2) Применив аналогичные рассуждения для всех состояний системы, получим систему обыкновенных дифференциальных уравнений первого порядка: ⎧ ⎪ 𝜕𝑝00 ⎪ (𝑡) = −𝑝00 (𝑡)𝜆 + 𝑝02 (𝑡) Θ1𝐵 , ⎪ 𝜕𝑡 ⎪ 2 ⎪ ⎪ ⎪ ⎪ 𝜕𝑝10 ⎪ (𝑡) = 𝑝00 (𝑡)𝜆 + 𝑝12 (𝑡) Θ1𝐵 − 𝑝10 (𝑡)𝜆 − 𝑝10 (𝑡) Θ1𝐴 , ⎪ ⎪ 𝜕𝑡 2 1 ⎪ ⎪ ⎪ ⎪ 𝜕𝑝11 1 1 ⎪ ⎪ (𝑡) = 𝑝10 (𝑡)𝜆 − 𝑝11 (𝑡) Θ𝐵 − 𝑝11 (𝑡) Θ𝐴 , ⎪ ⎪ 1 1 ⎨ 𝜕𝑡 𝜕𝑝02 (𝑡) = 𝑝10 (𝑡) Θ1𝐴 + 𝑝𝑤2 (𝑡) Θ1𝐵 − 𝑝02 (𝑡) Θ1𝐵 − 𝑝02 (𝑡)𝜆, 𝜕𝑡 ⎪ 1 2 2 ⎪ ⎪ ⎪ ⎪ 𝜕𝑝 1 1 12 ⎪ (𝑡) = −𝑝12 (𝑡) Θ𝐵 − 𝑝12 (𝑡) Θ𝐴 + 𝑝02 (𝑡)𝜆 + 𝑝11 (𝑡) Θ1𝐵 , ⎪ 𝜕𝑡 ⎪ 2 1 1 ⎪ ⎪ ⎪ ⎪ 𝜕𝑝𝑤1 ⎪ (𝑡) = −𝑝𝑤1 (𝑡) Θ1𝐵 + 𝑝11 (𝑡) Θ1𝐴 , ⎪ ⎪ 𝜕𝑡 1 1 ⎪ ⎪ ⎪ ⎪ ⎩ 𝜕𝑝𝑤2 (𝑡) = −𝑝 (𝑡) 1 + 𝑝 (𝑡) 1 + 𝑝 (𝑡) 1 . 12 𝑤1 𝑤2 𝜕𝑡 Θ𝐵 Θ𝐴 Θ𝐵 2 1 (2.3) 1 Добавив к системе (2.3) начальные условия, можно получить зависимость 𝑝𝑖 (𝑡). Заметим, что нашу СМО можно рассмотреть как марковскую цепь с конечным числом состояний. Тогда к нашему графу применима Теорема 1, описанная в [2]: Теорема 1. Неприводимая непериодическая цепь Маркова обладает инвариантным рас пределением вероятностей тогда и только тогда, когда она эргодична. Таким образом, существуют 𝑝𝑖 = lim 𝑝𝑖 (𝑡) и их можно вычислить, перейдя к пределу 𝑡→∞ при 𝑡 → ∞ в системе (2.3). В результате получится система (2.4):

13 ⎧ ⎪ ⎪ ⎪ 0 = −𝑝00 𝜆 + 𝑝02 Θ1𝐵 , ⎪ ⎪ 2 ⎪ ⎪ ⎪ ⎪ 1 ⎪ 0 = 𝑝00 𝜆 + 𝑝12 Θ𝐵 − 𝑝10 𝜆 − 𝑝10 Θ1𝐴 , ⎪ ⎪ 2 1 ⎪ ⎪ ⎪ ⎪ ⎪ 0 = 𝑝10 𝜆 − 𝑝11 Θ1𝐵 − 𝑝11 Θ1𝐴 , ⎪ ⎪ 1 1 ⎪ ⎪ ⎪ ⎪ 1 1 ⎨0 = 𝑝10 𝐴 + 𝑝𝑤2 𝐵 − 𝑝02 1𝐵 − 𝑝02 𝜆, Θ Θ Θ 1 2 2 (2.4) ⎪ ⎪ ⎪ 0 = −𝑝12 Θ1𝐵 − 𝑝12 Θ1𝐴 + 𝑝02 𝜆 + 𝑝11 Θ1𝐵 , ⎪ ⎪ 2 1 1 ⎪ ⎪ ⎪ ⎪ 1 1 ⎪ 0 = −𝑝𝑤1 Θ𝐵 + 𝑝11 Θ𝐴 , ⎪ ⎪ 1 1 ⎪ ⎪ ⎪ ⎪ ⎪0 = −𝑝𝑤2 1𝐵 + 𝑝12 1𝐴 + 𝑝𝑤1 1𝐵 , ⎪ Θ2 Θ1 Θ1 ⎪ ⎪ ⎪ ⎪ ∑︀ ⎪ ⎩ 𝑝𝑖 = 1. Решение системы (2.4) и будет значениями финальных вероятностей 𝑝𝑖 . Рассмотрим значение 𝑝 = 𝑝00 + 𝑝10 + 𝑝02 + 𝑝𝑤1 + 𝑝𝑤2 . Каждая из этих вероятностей равна относительному количеству времени, которая система провела в состояниях 00, 10, 02, 𝑤1, 𝑤2 соответственно. А в сумме это время, которое система, рассматриваемая в примере 1, прове ла в состоянии ожидания. Таким образом была получена одна из численных характеристик системы.

14 Глава 3 Автоматизация процесса моделирования систем 3.1. Построение графа перехода состояний в режиме диалога Для проверки полученных результатов и упрощения занесения графов функционирова ния систем была написана программа на языке 𝑅, которая по заданной схеме 𝑚𝑎𝑝 и вектору состояний, в которых может находиться система, согласно данной схеме, ℎ𝑒𝑎𝑑 составляет таблицу смежности графа перехода состояний. Алгоритм построения такой таблицы смежности основан на полном переборе элементов множества всех возможных состояний системы 𝑆 = 𝑆1 × 𝑆1 , где 𝑆1 =< 0, 1, 2, 12, 𝑤, 𝑣1 , 𝑣2 > — множество возможных состояний одного из узлов системы, и на анализе предложенной схемы 𝑚𝑎𝑝. Через 𝑤 здесь обозначается такое состояние узла, при котором заявка на этом узле не обслуживается, а только «занимает место» и ждет, пока освободится другой узел, а 𝑣𝑖 — выполняется первая часть операции (Ω𝑖 , Θ). Состояния 0𝑤, 0𝑣1 , 0𝑣2 , 𝑤0, 𝑣1 0, 𝑣2 0 недопустимы ни для одной схемы. Из состояния 00 можно перейти в 10, если 𝑚𝑎𝑝[1, 1] == ”1”, и в 120, если 𝑚𝑎𝑝[1, 1] == ”12”. К примеру, если состояние 𝑖0 ∈ ℎ𝑒𝑎𝑑 при 𝑖 ∈< 1, 2, 12 >, то система может перейти в следующие состояния: ∙ 𝑖𝑤, если 𝑚𝑎𝑝[1, 2] == ”(1, 𝑖𝑛𝑓 )”; ∙ 𝑖𝑣1 , если 𝑚𝑎𝑝[1, 2] == ”(1, Θ)”; ∙ 𝑖1, если 𝑚𝑎𝑝[1, 2] == ”(1)”; ∙ 𝑖12, если 𝑚𝑎𝑝[1, 2] == ”(12)”. Из состояния 𝑖1 при 𝑖 ∈< 0, 1, 2, 12, 𝑤, 𝑣2 > можно перейти в: ∙ 𝑖𝑤, если 𝑚𝑎𝑝[2, 2] == ”(2, 𝑖𝑛𝑓 )” или 𝑚𝑎𝑝[2, 2] ==; ∙ 𝑖𝑣2 , если 𝑚𝑎𝑝[2, 2] == ”(2, Θ); ∙ 𝑖2, если 𝑚𝑎𝑝[1, 2] == ”(2)” или 𝑚𝑎𝑝[1, 2] == ”2”;

15 И аналогично для других состояний. Результатом работы программы является квад ратная матрица ранга 𝑙𝑒𝑛𝑔𝑡ℎ(ℎ𝑒𝑎𝑑) — длина массива ℎ𝑒𝑎𝑑. 3.2. Моделирование систем В теории массового обслуживания существуют достаточно простые методы опреде ления необходимых характеристик для некоторого «упрощенного» класса систем. Но на практике реальные системы массового обслуживания оличаются от них. К примеру, поток поступающих событий не обязан быть пуассоновским, а время обслуживания в узлах систе мы может иметь любое распределение. Многие сложные задачи могут быть успешно решены при помощи метода статистических испытаний (метод Монте-Карло)[3].Также задачи моде лирования работы систем можно решать и аналитическими методами, при которых работа системы представляется в виде совокупности дифференциальных уравнений. 3.2.1. Аналитическая вероятностная модель Под аналитическ моделью будем подразумевать нахождение стационарного распреде ления вероятностей нахождения в каждом состоянии алгоритмом, рассмотренным в главе 2. В результате выполнения алгоритма, описанного в разделе 3.1, получена матрица 𝐴 — матрица смежности графа перехода состояний. Обобщив формулу 2.1 для производной системы, можно понять, что производная вероятности нахождения в состоянии 𝑖 равна: ∑︁ ∑︁ 𝜕𝑝𝑖 (𝑡) = 𝑝𝑗 (𝑡)𝐴[𝑗, 𝑖] − 𝑝𝑖 (𝑡) 𝐴[𝑖, 𝑗]. 𝜕𝑡 𝑗̸=𝑖 𝑗̸=𝑖 (3.1) Применив формулу 3.1 для всех 𝑖 ∈ ℎ𝑒𝑎𝑑 и перейдя к пределу при 𝑡 → ∞, мы получим линейно зависимую систему линейных уравнений 3.2: 0= ∑︁ 𝑝𝑗 𝐴[𝑗, 𝑖] − 𝑝𝑖 𝑗̸=𝑖 ∑︁ 𝐴[𝑖, 𝑗], (3.2) 𝑗̸=𝑖 где 𝑖 ∈ ℎ𝑒𝑎𝑑. Необходимо добавить ограничение, что ∑︀ 𝑖∈ℎ𝑒𝑎𝑑 𝑝𝑖 = 1. Решив полученную систему, получаем стационарное распределение вероятностей, а из него находим показатели эффек тивности работы системы.

16 3.2.2. Моделирование по принципу ∆𝑡 Общее время моделирования 𝑇 разбивается на маленькие участки ∆𝑡 — такт времени. При этом предполагается, что существенные изменения состояний системы могут происхо дить только в точках вида 𝑘∆𝑡. Пусть существует функция 𝑧(𝑡), которая по заданому моменту времени определяет текущее состояние системы. И если можно легко определить значение 𝑧(𝑡 + ∆𝑡) при извест ном значении 𝑧(𝑡), то процесс моделирования функционирования системы заключается в последовательном моделировании значений 𝑧(𝑘∆𝑡) при условии, что известно предыдущее значение. Рассмотрим соответствующий алгоритм. Пусть мы находимся в состоянии 𝑍0 , и из него система может перейти в состояния 𝑍1 , . . . , 𝑍𝑛 , где время перехода для каждого 𝑖 имеет функцию распределения 𝐹𝑖 (𝑡). Тогда наличие перехода в состояние 𝑍𝑖 определяется выполнением неравенства 3.3: 𝐹𝑖 ((𝑘 + 1)∆𝑡) − 𝐹𝑖 (𝑘∆𝑡) > 𝛼. 1 − 𝐹𝑖 (𝑘∆𝑡) (3.3) Нетрудно видеть, что левая часть неравенства есть условная вероятность, что система перейдет в состояние 𝑍𝑖 в промежуток времени 𝑡 ∈ [𝑘∆𝑡, (𝑘+1)∆𝑡], при условии, что система находится в состоянии 𝑍0 . Очевидно, что при моделировании таким способом времены переходов могут быть опре делены лишь с точностью ∆𝑡. Поэтому для увеличения точности уменьшают значение ∆𝑡, что в свою очередь увеличивает число шагов моделирование, что приводит к значительным затратам как времени моделирования, так и требуемой памяти. 3.2.3. Моделирование методом узловых точек Пусть распределение времени между приходом заявок и распределения времени выпол нения операций являются однопараметрическими. Пусть система находится в состоянии 𝑖. Пусть 𝑛𝑒𝑥𝑡 — множество всех состояний, которые достижимы из 𝑖. Далее моделируются случайные величины 𝜉𝑘 с параметрами 𝐴[𝑖, 𝑘], 𝑘 ∈ 𝑛𝑒𝑥𝑡. Пусть 𝑚 — индекс минимальной среди 𝜉𝑘 . Тогда следующим состоянием становится 𝑚, а текущее время изменяется на 𝜉𝑚 . Запишем соответствующий алгоритм: ∙ текущее время 𝑐𝑢𝑟𝑡 = 0

17 ∙ текущее состояние 𝑐𝑢𝑟𝑖 = 00 ∙ пока 𝑐𝑢𝑟𝑡 < 𝑇 – определяем 𝑛𝑒𝑥𝑡 — индексы 𝑗 элементов 𝐴[𝑐𝑢𝑟𝑖 , 𝑗] > 0 – моделируем вектор 𝑥𝑖 длины 𝑙𝑒𝑛𝑔𝑡ℎ(𝑛𝑒𝑥𝑡) — времена переходов – 𝑚𝑖𝑛𝑡 = 𝑚𝑖𝑛(𝑥𝑖) – 𝑐𝑢𝑟𝑡 = 𝑐𝑢𝑟𝑡 + 𝑚𝑖𝑛𝑡 – увеличиваем счетчик времени 𝑡𝑖𝑚𝑒𝑟[𝑐𝑢𝑟𝑖 ] = 𝑡𝑖𝑚𝑒𝑟[𝑐𝑢𝑟𝑖 ] + 𝑚𝑖𝑛𝑡 – следующее состояние — индекс минимального элемента 𝑥𝑖 ∙ суммируем 𝑡𝑖𝑚𝑒𝑟 по индексам, в которых есть простой Таким образом, при моделировании системы таким методом удается найти ближайший мо мент времени, когда происходит изменение состояния системы. Такой момент и называется . узловой точкой

18 Глава 4 Программа Одной из основных целей данной дипломной работы было написание программы, кото рая помогла бы студенту в обучении решению задач, представленных в курсе «Моделирова ние систем», была бы способна моделировать процесс работы систем различными методами. Также эта программа была бы полезна людям, чье производство или бизнес можно пред ставить как систему массового обслуживания, описанную в данной работе. С помощью нее они смогут определить наилучшую схему работы своего производства. В ходе диалога с программой пользователь может следующее: ∙ выбрать схему, по которой работает система; ∙ перечислить допустимые состояний, в которых может находиться система; ∙ составить граф переходов состояний системы; ∙ выбрать метод моделирования процесса работы системы; ∙ выбрать законы распределения времени поступления заявок и времени выполнения каждой операции на каждом узле; ∙ задать время работы системы и количество реализаций процесса работы системы; ∙ выбрать характеристику системы, которая будет наблядаться; ∙ построить гистограмму распределения наблюдаемой характеристики. Далее будет приведен пример диалога пользователя с программой. На первом шаге пользователю предлагается заполнить допустимые состояния системы (Рис. 4.1) и выбрать схему, по которой функционирует система (Рис. 4.2).

19 imena.png Рис. 4.1: Заполнение допустимых состояний системы. mat.png Рис. 4.2: Выбор схемы функционирования системы. Далее пользователь вводит основные показатели системы, такие как среднее время выполнения каждой операции для каждого узла, интенсивность поступления заявок (Рис. 4.3). sredn.png Рис. 4.3: Среднее время выполнения операций и интенсивность поступления заявок. В результате программа автоматически составляет граф перехода состояний (Рис. 4.4), таким образом, пользователь может увидеть его или сравнить его с тем, который он сам построил.

20 graph.png Рис. 4.4: Граф перехода состояний. Далее пользователь выбирает законы распределения времени поступления заявок и времени выполнения операций (Рис. 4.5). zak.png Рис. 4.5: Законы распределения времени поступления и обработки заявок. После этого пользователю предлагается на выбор 3 метода моделирования, для кото рых он выбирает количество реализаций и время работы системы. А также выбрать харак теристику, за которой будут наблюдать. Затем, в случае статистического метода, программа строит диаграмму распределения наблюдаемой характеристики и выбает её среднее значение. А в случае аналитической мо дели, программа выдаст среднее значение характеристики.

21 Заключение В результате дипломной работы были получены следующие результаты: ∙ выполнен анализ систем, состоящих из 2 аппаратов, на каждом из которых могут выполняться 2 операции; ∙ произведена классификация схем функционирования таких систем; ∙ была написана программа, позволяющая автоматически составлять граф перехода со стояний, моделировать работу системы 3 различными методами, анализировать раз личные характеристики эффективности работы системы.

22 Список литературы 1. Куприяшкин . . Основы моделирования систем. — Норильск : НИИ, 2015. — 135 с. 2. Феллер . Введение в теорию вероятностей и ее приложения. — М. : Мир, 1984. — 528 с. 3. Сушков . . Статистические модели систем. — СПб., 2003. — 83 с.

Рецензии:

Авторизуйтесь, чтобы добавить рецензию

- у работы пока нет рецензий -

Отзывы:

Авторизуйтесь, чтобы оставить отзыв