Способы принятия решений

1. Проведение эксперимента на реальной системе

2. Использование данных о поведении системы в прошлом

3. Проведение эксперимента на модели

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

Модель – это абстрактное описание системы в некоторой форме, отличной от формы её реального существования.

Моделирование – это деятельность по созданию и применению моделей.

Виды моделирования

1. Физическое моделирование – воспроизведение физических свойств реального объекта.

2. Концептуальное моделирование – представление системы с помощью специальных знаков, символов.

3. Структурно-функциональное моделирование – моделями являются блок-схемы, графики, диаграммы, таблицы со специальными правилами их построения и преобразования.

4. Логико-математическое моделирование –модели строятся средствами математики.

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

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

Сущность метода имитационного моделирования

Метод имитационного моделирования (ИМ) – это метод исследования реальной системы по её имитационной модели, который сочетает в себе особенности экспериментального подхода и специфические условия использования вычислительной техники.

Основные элементы имитационного исследования

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

Классификация систем по типу поведения

- статическая и динамическая

Система называется статической, если она может находиться только в одном состоянии. Если состояний больше одного, система называется динамической.

- детерминированные и стохастические

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

- системы с дискретными переходами и системы с непрерывными переходами

Смена состояний может происходить либо в фиксированные моменты времени (системы с дискретными переходами), либо непрерывно (системы с непрерывными переходами).

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

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

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

Этап 1. Формулировка проблемы и целей моделирования

Результат данного этапа – содержательное описание.

Этап 2. Составление концептуальной модели

Результат данного этапа – концептуальная модель.

Этап 3. Формализация имитационной модели

Результат данного этапа – формальное описание.

Этап 4. Алгоритмизация и программирование

Результат данного этапа – имитационная модель.

Этап 5. Подготовка исходных данных Этап 5. Испытание и исследование свойств модели

Результат данного этапа – программа и результаты испытаний

Этап 6. Планирование и проведение эксперимента

Результат данного этапа – план и результаты эксперимента

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

Результат данного этапа – принятое решение

Этап 1. «Формулировка проблемы и целей моделирования»

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

1. Структурирование исходной проблемы (описание места проблемы, множества значимых факторов, условий решения проблемы и методов её решения)

2. Выявление целей (оценка функционирования системы, сравнение альтернатив, прогноз, анализ чувствительности, оптимизация)

3. Формирование критерия эффективности

Этап 2. «Составление концептуальной модели»

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

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

1. Определение границ системы, внешних факторов

2. Выдвижение гипотез – предположений, требующих доказательств. Гипотезы выдвигаются относительно вариантов достижения поставленной цели.

3. Декомпозиция системы

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

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

Этап 3. «Формализация имитационной модели»

Задачи этапа формализации имитационной модели.

1. Выбор способа формализации.

- Q-схемы для моделирования непрерывно-стохастических систем (систем массового обслуживания);

- N-схемы (сетевые модели), применяемые при структуризации причинно-следственных связей;

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

2. Составление формального описания системы

Этап 4. «Алгоритмизация и программирование»

Задачи этапа программирования имитационной модели.

1. Построение схемы алгоритма

2. Получение математических соотношений

3. Выбор средств и языка программирования

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

Этап 5. «Подготовка исходных данных»

Задачи этапа подготовки исходных данных.

1. Подготовка наблюдения

2. Сбор данных и их контроль

3. Сводка и группировка данных

4. Анализ данных

Этап 6. «Испытание и исследование свойств модели»

Задачи этапа испытания и исследования свойств модели.

1. Верификация и проверка адекватности модели

2. Проверка устойчивости, оценка точности результатов моделирования, анализ чувствительности

Этап 6. «Планирование и проведение эксперимента»

Задачи этапа планирования и проведения эксперимента.

1. Стратегическое планирование эксперимента

2. Тактическое планирование эксперимента

3. Проведение рабочих расчётов

Этап 7. «Интерпретация результатов моделирования»

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

Формализация имитационных моделей.

Непрерывно-стохастические модели (Q-схемы)

1. Понятие системы массового обслуживания и её основные элементы

2. Классификация систем массового обслуживания (СМО)

3. Q-схемы

4. Показатели качества СМО

Понятие системы массового обслуживания и её основные элементы

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

Пример: обработка заявок на складе, деятельность магазина и т.д.

Поток заявок – это совокупность заявок, распределённая во времени. Характеристикой потока заявок является интенсивность – число заявок на единицу времени.

Обслуживающее устройство (канал обслуживания) – это элемент системы, в котором происходят операции по обработке заявок. Характеристика обслуживающего устройства – время обслуживания заявки, состояние (свободен/занят).

Очередь – это накопитель заявок, ожидающих обслуживание. Характеристики у очереди: ёмкость очереди (максимальное количество заявок, которые могут стоять в очереди), состояние очереди (число заявок в текущий момент времени).

Классификация систем массового обслуживания (СМО)

1. По числу параллельно соединённых каналов:

- одноканальные;

- многоканальные.

2. По числу последовательно соединённых каналов:

- однофазные;

- многофазные.

3. По наличию очереди:

- без очередей (с потерями заявок);

- с неограниченным ожиданием;

- с ограниченным ожиданием (по времени или длине).

4. По виду приоритета заявок:

- системы со статическим приоритетом (обслуживание в порядке поступления заявок);

- системы с динамическим приоритетом:

o с относительным приоритетом (заявка высокого приоритета ожидает окончания обслуживания заявки с более низким приоритетом);

o системы с абсолютным приоритетом (заявка высокого приоритета при поступлении немедленно вытесняет заявку с более низким приоритетом);

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

Q-схемы

Wi – входящий поток заявок;

Yi – выходящий поток заявок;

Ki – поток обслуживания – набор параметров, которыми можно влиять на работу системы;

Пi – прибор обслуживания (совокупность каналов и накопителей одной фазы);

Hi – накопитель.

В общем виде Q-схема задаётся в виде множества

Q = <W,U,Y,H,R,Z,A>

где W – множество входящих потоков заявок;

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

Y –множество выходящих потоков заявок;

H – множество собственных параметров системы: фаз, каналов, накопителей и их характеристик;

R – оператор сопряжения элементов структуры (каналов накопителей);

Z– множество состояний системы;

Z=(Z_i^H,Z_i^K) – состояние накопителя (Z_i^H) и состояние каналов (Z_i^K)

Z_i^H=0 – в накопителе нет заявок, Z_i^H=1 – в накопителе 1 заявка, Z_i^H=Li – наполнитель полон;

Z_i^K=0 – канал свободен, Z_i^K=1 – канал занят.

A – оператор алгоритмов поведения и обслуживания заявок.

Показатели качества СМО

1. Общее количество обслуженных заявок за какой-либо промежуток времени

2. Доля заявок обслуженных (из общего числа)

3. Доля заявок получивших отказ (из общего числа)

4. Время пребывания заявки в системе

5. Среднее время обслуживания

6. Средняя длина очереди

7. Среднее время ожидания

8. Загрузка канала (коэффициент использования) – доля времени, в течение которого канал был занят (время работы, делёное на общее время)

ПримерQ-схемы

____________________________________________________________________________

Блок TEST. Проверка числовых выражений

TEST X, b, [C]

БлокTEST определяет номер следующего блока для вошедшего в него транзакта в зависимости от того выполняется требуемое условие или нет.

X – мнемоническое обозначение операции сравнения, которое может принимать следующие значения: L–<; LE – ≤;E – =; NE–≠; G–>; GE– ≥.

A – параметр левой части выражения сравнения.

B – параметр правой части выражения.

С – блок, к которому осуществляется переход в случае невыполнения условия.

Q$BARBER

Пример

TEST L Q$BARBER, 3, GO_EXIT

QUEUEBARBER

…

GO_EXITTERMINATE

Блоки работы с многоканальными устройствамиENTERи LEAVE

Ёмкость многоканального устройства – число параллельно соединённых каналов обслуживания.

CRANE– имя многоканального устройства;

STORAGE – команда, задающая ёмкость;

n – значение ёмкости.

CRANESTORAGE 3

_________________________________________________

ENTERA, [B] – это команда занятия многоканального устройства транзакта.

LEAVEA, [B] – освобождение МКУ транзакта.

A – имя многоканального устройства (МКУ);

B– количеств занимаемых (освобождаемых) устройств транзакта.

ENTERCRANE

ADVANCE 20; 5

LEAVE CRANE

Элементыстандартногоотчёта

REMAIN – количество единиц свободной ёмкости МКУ в конце периода моделирования;

CAP. – ёмкость МКУ;

MIN, MAX – минимальное и максимальное количество используемой ёмкости;

ENTRIES – количество входов в МКУ;

AVE.C. – среднее значение занятой ёмкости;

UTIL. – коэффициент использования всех устройств МКУ.

Команды GPSSWorld

STARTA, [B] – инициация начала моделирования, установка значения счётчика завершения.

А – значение счётчика завершения;

В – операнд вывода статистики. Если операнд принимает значение NP, то статистика не выводится.

RESET – сброс статистики и системных числовых атрибутов, но не удаление транзактов из модели.

CLEAR [A] – сброс статистики и удаление транзактов из модели. Операнд А=OFF – сохраняемые величины и матрицы остаются без изменений.

EXIT – выход из модели.

HALT – прерывание процесса моделирования.

CONTINUE – продолжить процесс моделирования.

STEPА – пошаговое выполнение моделирования. Операнд А – счётчик прохождения блоков.

REPORT – формирование отчёта.

STOP[A], [B], [C] – задаёт и снимает условия остановки моделирования.

А – номер транзакта, удовлетворяющий условию основного;

В – номер блока, удовлетворяющий условию основного;

С – флажок состояния команды. ON, OFF.

Формализация имитационных моделей. Сетевые модели (N-схемы)

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

Основными элементами сетевой модели являются условия и события.

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

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

Условия, с фактами выполнения которых связана истинность предиката, называются «до-условиями».

В результате наступления события становятся истинными другие простые условия, которые называются «пост-условиями».

Таблица - События, происходящие при обработке детали на станке

Графические элементы систем Петри

Позиция (условие)

Переход (событие)

Разновидности сетевых моделей:

- иерархические сети (переход является не мгновенным событием, а составным действием, то есть некоторое время переход находится в активном состоянии);

- сети событий (вершинами сети являются события, а дугами – связи между различными событиями).

Пример

На ЭВМ, находящиеся в машинном зале, поступают запросы. Первоначально все запросы обрабатываются на ЭВМ 1 и с вероятностью 50% требуемая информация находится. Если информация на ЭВМ 1 не обнаружена, то запросы переходят на ЭВМ 2, где и удовлетворяются.

События:

- запрос поступил=t₁

_- начало обработки на ЭВМ 1 =t₂

_- начало обработки на ЭВМ 2=t₃

_- завершение обработки запроса =t₄, t₅

- постановка в очередь =t₆, t₇

_- выход из очереди =t₈, t₉

-

Р₁ - время заявки наступило

Алгоритмизация и программирование имитационной модели.

Управление модельным временем

1. Представление времени в модели

2. Изменение времени с постоянным шагом

3. Продвижение времени по особым состояниям

Представление времени в модели

Три представления времени в модели

1. Реальное (физическое), в котором происходит функционирование имитируемой системы.

2. Модельное (системное), в масштабе которого организуется работа модели.

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

3. Машинное, отражающее затраты времени ЭВМ на проведении имитации

Существует 2 метода реализации механизма модельного времени.

1. Моделирование с постоянным шагом (пошаговый метод; «принцип ∆t»). Применяются фиксированные интервалы изменения времени.

2. Моделирование по особым состояниям (пособытийный метод; «принцип ∆z»). Применяются переменные интервалы изменения времени. При этом величина шага измеряется интервалом до следующего события.

4 bWxQSwUGAAAAAAQABADzAAAA9gUAAAAA " filled="f" stroked="f" strokeweight=".5pt">

T = t₀ + ∆t + ∆t

Плюсы:

- простота машинной реализации.

Минусы:

_- метод не позволяет указать истинное положение событий внутри интервала; теряются причинно-следственные связи; последовательные события становятся параллельными;

_- требуется много процессорного времени на обработку «пустых» интервалов.

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

Алгоритм моделирования систем по принципу ∆t

Продвижение времени по особым состояниям

Плюсы:

- соблюдение последовательности наступления событий;

- экономия машинного времени на имитацию.

Минусы:

- сложность реализации специальной процедуры – календаря событий.

Моделирование случайных событий и величин

1. Генератор случайных чисел

2. Моделирование случайных событий

3. Моделирование случайных величин

Генератор случайных чисел

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

Моделирование случайных событий

А – событие, Р_А – вероятность события А (10%).

Рис. 1

Пусть имеется группа несовместных (независимых) событий А₁, А₂, …, А_kcвероятностью Р₁, Р₂, …, Р_k.

ΣP_i =1

Рис. 2

Моделирование случайных величин

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

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

Равномерный закон распределения случайной величины X в интервале (a, b)

Рис. 3

Пример

Время прихода автобуса к остановке – случайная величина, распределённая в интервале от 3 до 7 минут. Смоделировать время прихода автобуса, используя ГСЧ.

Рис. 4.