Список сокращений. Gpss(general Purpose Simulation System) – многоцелевая система моделирования

GPSS (General Purpose Simulation System) – многоцелевая система моделирования

PR – приоритет

АСУ – автоматизированная система управления

ИМ – имитационное моделирование

МКУ – многоканальное устройство

ОКУ – одноканальное устройство

СМО – система массового обслуживания

СЧА – системный числовой атрибут

сек – секунды

мс – миллисекунды

мин – минуты

у.е. – условные единицы

ВВЕДЕНИЕ

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

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

Универсальным инструментальным средством создания моделей являются языки программирования общего пользования (Pascal, C/C++ и др.). На основе этих языков в настоящее время бурное развитие получили средства визуального проектирования программ (Delphi, Visual C++), облегчающие выполнение некоторых трудоёмких операций, например, создание интерфейса программы. Но эти языки сложны и требуют специального изучения и навыков программирования.

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

Эта технология бурно начала развиваться в 60-е годы, но и сейчас является основной в области моделирования систем массового обслуживания, реинжиниринга бизнес-процессов, моделирования мультиагентных систем и др. В настоящее время существует несколько сред имитационного моделирования, отличающихся подходами, средствами, функциональными возможностями, из наиболее известных GPSS, Micro Saint, Simpas, Anylogic, Arena и др. В данном пособии технология имитационного моделирования излагается на основе языка GPSS World, достаточного с точки зрения функциональных возможностей для моделирования процессов сервиса и несложного для освоения в рамках учебного курса.

Студенческая версия языка является бесплатной, что позволяет использовать её в учебном процессе в аудитории и дома для самостоятельной работы. Она отличается от обычной лишь ограничением на количество блоков в программе (около 170), но как показывает практика это достаточно для построения учебных моделей. Учебную версию можно скачать на портале разработчиков языка www.minutemansoftware.cоm, также полезную информацию и новости можно найти на русифицированном сайте www.gpss.ru

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

Желаю успехов и интереса в освоении!

ГЛАВА 1. ОСНОВНЫЕ ПОНЯТИЯ МОДЕЛИРОВАНИЯ СИСТЕМ, КЛАССИФИКАЦИЯ МОДЕЛЕЙ И МЕТОДОВ

С точки зрения философии, моделирование представляет собой один из методов познания мира.

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

1.1. Основные понятия теории моделирования

Базовые понятия теории моделирования: моделирование, модель, система [7, c. 8].

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

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

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

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

Приведём основные свойства системы:

1) свойство эмергентности, или эмерджентности: свойства системы не сводятся к совокупности свойств частей, из которых она состоит, и не выводятся из них. Результат поведения системы даёт эффект отличный от «сложения» (независимого соединения) любым способом результатов поведения всех, входящих в систему элементов;

2) свойство целостности: система рассматривается как нечто целое, обособленное от окружающей среды;

3) свойство структурированности: система имеет части, целесообразно связанные между собой;

4) свойство подчинённости цели: вся организация системы подчинена некоторой цели;

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

6) свойство бесконечности: невозможность полного познания системы и её всестороннего представления любым конечным множеством моделей;

7) свойство иерархичности: система может иметь несколько качественно разных уровней строения, при декомпозиции системы каждая её подсистема или часть может рассматриваться как целостная подсистема. Сама система является, в свою очередь, частью некоторой надсистемы – более широкой системы.

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

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

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

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

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

Математическое моделирование можно разделить на аналитическое, численное и имитационное.

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

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

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

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

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

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

Применение имитационного моделирования целесообразно при наличии определённых условий. Эти условия определяет Р. Шеннон:

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

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

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

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

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

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

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

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

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

1.3. Классификация моделей

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

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

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

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

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

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

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

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

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

Выводы

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

Контрольные вопросы и задания

1. К каким методам моделирования можно отнести известный метод решения систем дифференциальных уравнений Рунге-Кутта?

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

3. В чём состоит основная идея метода имитационного моделирования?

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

5. Объясните способ генерации случайных чисел по методу серединных квадратов.

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

7. Объясните на примере конкретных систем, как Вы понимаете основные свойства системы.

ГЛАВА 2. МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ СИСТЕМ С ИСПОЛЬЗОВАНИЕМ МАРКОВСКИХ

СЛУЧАЙНЫХ ПРОЦЕССОВ

Среди различных видов систем, окружающих нас: технических, информационных, социальных и т. д. нас будут интересовать системы, которые возникают в сервисных процессах, в процессах обслуживания. В прикладной математике они так и называются – системы массового обслуживания (СМО). Математический аппарат изучения этих систем давно разработан и позволяет построить модели таких систем для описания процессов обслуживания и вычислить основные характеристики функционирования системы с целью определения её эффективности [7, c. 78]. Этот аппарат основывается на теории вероятностей и теории случайных процессов. Рассмотрим основные идеи и понятия.

2.1. Элементы теории марковских случайных процессов,
используемые при моделировании систем

Функция X(t) называется случайной, если её значение при любом аргументе t является случайной величиной.

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

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

Определение. Случайный процесс, протекающий в какой-либо системе S, называется марковским, или процессом без последейст­вия, если он обладает следующим свойством: для любого момента времени t₀ вероятность любого состояния системы в будущем зависит только от её состояния в настоящем и не зависит от того, когда и каким образом система S пришла в это со­стояние.

Классификация марковских процессов. Классификация марковских случайных процессов производится в зависимости от непре­рывности или дискретности множества значений функции X (t) и параметра t.

Различают следующие основные виды марковских случай­ных процессов:

- с дискретными состояниями и дискретным временем (цепь Маркова);

- с непрерывными состояниями и дискретным временем (марков­ские последовательности);

- с дискретными состояниями и непрерывным временем (непре­рывная цепь Маркова);

- с непрерывным состоянием и непрерывным временем.

Мы будем рассматривать только марковские процессы с дискретными состояниями S₁, S₂,..., S_{n .}

Граф состояний. Марковские процессы с дискретными состо­яниями удобно иллюстрировать с помощью так называемого графа состояний (рис. 2.1), где кружками обозначены состояния S₁, S₂,... системы S, а стрелками – возможные переходы из состо­яния в состояние.

Рис. 2.1. Пример графа состояний системы S

На графе отмечаются только непосредственные переходы, а не переходы через другие состояния. Возможные за­держки в прежнем состоянии изображают «петлёй», т. е. стрел­кой, направленной из данного состояния в него же. Число состо­яний системы может быть как конечным, так и бесконечным (несчётным).

2.2. Марковские цепи

(2.1)

(2.2)

(2.1)

Марковский случайный процесс с дискретными состояниями и дискретным временем называют марковской цепью. Для такого процесса моменты времени t₁, t₂..., когда система S может менять своё со­стояние, рассматривают как последовательные шаги процесса, а в качестве аргумента, от которого зависит процесс, выступает не вре­мя t, а номер шага 1, 2,.., k,.... Случайный процесс в этом случае характеризуется последовательностью состояний S (0), S (1), S (2),..., S (k), где S (0) – начальное состояние системы (перед первым шагом); S(1) – состояние системы после первого шага (в момент времени t₁) и т. д.

Событие S (k) = S_i , состоящее в том, что сразу после k-го ша­га система находится в состоянии S_i (i = 1, 2,...), является случай­ным событием. Последовательность состояний S (0), S (1),..., S (k),... можно рассматривать как последовательность случайных событий. Такая случайная последовательность событий называется марковской цепью, если для каждого шага вероятность перехода из любого состояния S_i в любое S_jне зависит от того, когда и как система пришла в состояние S_i.

Вероятностями состояний цепи Маркова называются вероятно­сти P_i (k) того, что после k -гo шага и до (k + 1)-го система S будет находиться в состоянии S_i (i = 1, 2,..., п).

Понятно, что для каждого k:

Начальным распределением вероятностей Марковской цепи называется распределение вероятностей в момент t = 0: P₁ (0), P₂ (0), P_n (0). В частном случае, если S (0) = S_i, то P_i (0) = 1, а остальные равны 0.

Вероятностью перехода из состояния S_i в состояние S_j (переходной вероятностью) называется вероятность того, что система окажется в состоянии S_j,при условии, что до этого она находилась в состоянии S_i. Поскольку система может пребывать в одном из n состояний, то для каждого момента надо задать n² вероятностей, которые записывают в матрицу переходных вероятностей:

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

Отметим особенности переходной матрицы:

- каждая строка характеризует выбранное состояние системы и её элементы – это вероятности переходов за один шаг из этого состояния в любое другое или в само себя;

- элементы столбцов показывают вероятности переходов из любого состояния в конкретное;

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

- по главной диагонали стоят вероятности того, что система не выйдет, а останется в прежнем состоянии.

Если для однородной марковской цепи задано начальное распределение вероятностей и матрица переходных вероятностей известна, то вероятности состояний системы P_i (k) в момент времени k определяются по формуле:

. ( 2.1)