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

Размещено на http://www.allbest.ru/

Понятие о моделях и моделировании. Свойства моделей. Классификация моделей

динамический модель линейный агрегат

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

Свойства любой модели таковы:

· конечность: модель отображает оригинал лишь в конечном числе его отношений и, кроме того, ресурсы моделирования конечны;

· упрощенность: модель отображает только существенные стороны объекта;

· приблизительность: действительность отображается моделью грубо или приблизительно;

· адекватность: модель успешно описывает моделируемую систему;

· информативность: модель должна содержать достаточную информацию о системе - в рамках гипотез, принятых при построении модели.

Каждая модель характеризуется тремя признаками:

q принадлежностью к определённому классу задач (по классам задач)

q указанием класса объектов моделирования (по классам объектов)

q способом реализации (по форме представления и обработки информации).

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

Материальные модели:

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

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

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

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

1- уравнение теплопроводности (закон Фурье), 2- уравнение диффузии (закон Фика), 3-уравнение электропроводности (закон Ома).

Идеальные модели

a) неформализованные модели, т.е. системы представлений об объекте оригинале, сложившиеся в человеческом мозгу;

b) частично формализованные:

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

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

графические условные - данные наблюдений и экспериментальных исследований в виде графиков, диаграмм, схем;

c) вполне формализованные (математические) модели.

Адекватность и эффективность математических моделей. Общая логика построения моделей (технология математического моделирования).

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

Проблема моделирования состоит из трех задач:

· построение модели (эта задача менее формализуема и конструктивна, в том смысле, что нет алгоритма для построения моделей);

· исследование модели (эта задача более формализуема, имеются методы исследования различных классов моделей);

· использование модели (конструктивная и конкретизируемая задача).

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

Технология математического моделирования содержит следующие этапы: составление модели, идентификация и верификация модели, эксплуатация модели.

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

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

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

Классификация математических моделей по свойствам обобщенного объекта моделирования

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

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

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

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

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

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

Методы построения математических моделей: аналитические модели, модели идентификации

Аналиические

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

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

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

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

Идентифицируемые модели

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

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

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

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

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

1. Методы применяются для линейных по идентифицируемым параметрам моделям. Структура математической модели процесса представляется функцией вида:

, (6.2)

где а_i - i-тый оцениваемый параметр; f_i - i-тая известная функция, - вектор входных воздействий, y - выходная переменная.

Возможно представление идентифицируемой модели в следующей форме:

 (6.3)

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

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

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

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

Идентификация статических линейных систем с несколькими входами

Пусть необходимо идентифицировать систему с «n» входами x₁, x₂,…x_n и одним выходом y. Представим структуру модели в виде линейного алгебраического уравнения вида:

y=a₀ + a₁ x₁+ a₂ x₂+…+ a_nx_n , (6.4)

где a₀, a₁,..a_n - параметры модели, подлежащие идентификации. В результате идентификации мы должны получить вектор оценок истинного вектора . Этому вектору будет соответствовать оценка значения выходной величины .

Для определения значений произведем N последовательных измерений величины у, соответствующих в определенном смысле произвольным набором величин х_i (i=1,2,…n). В результате получим вектор . По N наборам входных величин х_i (i=1,2,…n) будет соответственно N оценок выходных величин

(6.5)

Разница характеризует погрешность каждой модели в каждом из N измерений. Суммарную погрешность будем характеризовать величиной:

(6.6)

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

(i=0,1,2,…n) (6.7)

Уравнения (6.7) позволяют построить вычислительный процесс идентификации вектора на основе N групп измерений y и . Для получения эффективных и несмещенных оценок * необходимо, чтобы N > n. Если N= n+1, то в оценке шум измерений не будет сглажен, окажет негативное влияние и случайность наборов . Мерой ошибки регрессионной модели обычно служит величина среднеквадратичного отклонения . С увеличением N уменьшается флуктуация , их величина и является определяющей для выбора N в рамках принятой структуры модели.

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

(6.8)

С помощью логарифмирования и замены у=lnW, x_i=lnZ_i (i = 1, 2, …m) (6.8) приводится к виду y=. Зависимости (6.8) широко используются при построении моделей по эмпирическим данным в гидравлике, термодинамике, обработке металлов давлением и т.д. Можно сказать, что и другие типы нелинейных регрессионных моделей, в конечном итоге, сводятся к зависимостям (6.4).

Достоверность (адекватность) регрессионной модели. Критерий Фишера.

Рис.

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

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

Для характеристики среднего разброса относительно линии регрессии применяют дисперсию адекватности:

; f - число степеней свободы.

Проверка значимости (качества предсказания) множественного уравнения регрессии можно осуществить на основе F-критерия Фишера. Вычисляют дисперсию среднего:

.

Вычисляют так называемую остаточную дисперсию (дисперсию адекватности):

.

Сравнивают с числом степеней свободы в числителе , в знаменателе . Считают, что уравнение регрессии предсказывает результаты опытов лучше среднего, если F достигает или превышает границу значимости при выбранном уровне значимости р (обычно принимают р = 1 - q = 5 % ). Другими словами, F - критерий Фишера показывает во сколько раз уравнение регрессии предсказывает результаты опытов лучше,чем среднее «у».

При построении математических моделей сложных технических систем эффективным оказывается их последовательное расчленение на подсистемы (декомпозиция системы) с сохранением связей между выявленными подсистемами

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

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

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

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

Детерминированные объекты, функционирующие в дискретном времени, описываются математическими моделями, сводящимися к различным типам конечных автоматов.

Автомат можно представить как некоторое устройство (черный ящик), на которое подаются дискретные входные воздействия (сигналы) и с которого снимаются дискретные выходные воздействия; оно имеет также некоторые внутренние состояния. Автомат функционирует в дискретном автоматном времени, моментами которого являются такты, т.е. примыкающие друг к другу равные интервалы времени, каждому из которых соответствуют постоянные значения входного и выходного сигналов и внутренние состояния. Обозначим состояние, а также входной и выходной сигналы, соответствующие t-тому такту при t = 0,1,2,… через z(t), x(t), y(t). При этом, по условию z(0) = z₀, a z(t) Z, x(t)X, y(t)Y. Абстрактный конечный автомат имеет один входной и один выходной каналы. В каждый момент t = 0,1,2,…дискретного времени автомат находится в определенном состоянии z(t) из множества Z состояний автомата, причем в начальный момент времени t = 0 он всегда находится в начальном состоянии z(0) = z₀. Конечным автоматом называется такой автомат, у которого множества входных сигналов, состояний и выходных сигналов являются конечными множествами. Абстрактно конечный автомат представляет собой математическую схему, характеризующуюся 6 элементами:

1. конечным множеством X входных сигналов (входной алфавит);

2. конечным множеством Z внутренних состояний (алфавитом состояний);

3. конечным множеством Y (выходным алфавитом);

4. начальным состоянием z₀;

5. функцией переходов ц (x,z);

6. функцией выходов (z,y).

В момент t, будучи в состоянии z(t-1), автомат способен воспринять на входном канале сигнал x(t)X и выдать на выходном канале сигнал y(t) = [z(t-1),x(t)], переходя в состояние z(t) = [z(t-1),x(t)], z(t) Z, y(t)Y. Сказанное выше можно описать следующими уравнениями: для автомата, называемого автоматом Мили

z(t) = [z(t-1),x(t)], t = 1,2,… ; (7.1)

y(t) = [z(t-1),x(t)], t = 1,2,… ; (7.2)

Автомат, для которого

y(t) = [z(t)], t = 1,2,3… (7.3)

т.е. функция выходов не зависит от входной переменной, называется автоматом Мура.

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

y(t) = [x(t)], t = 1,2,…

Это функция называется булевой, если алфавиты X и Y, которым принадлежат значения сигналов х и у, состоят из двух букв.

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

Чтобы задать конечный автомат, необходимо описать все элементы кортежа <Z,X,Y,z₀>. Существует несколько способов задания работы автомата, но наиболее часто используются табличный, графический и матричный.

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

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

При другом способе задания конечного автомата используется понятие направленного графа. Граф автомата представляет собой набор вершин, соответствующих различным состояниям автомата и соединяющих вершины дуг графа, соответствующих тем или иным переходам автомата. Если входной сигнал x_k вызывает переход из состояния z_i в состояние z_j, то на графе автомата дуга, соединяющая вершину z_i с вершиной z_j, обозначается x_k. Для того, чтобы задать функцию выходов, дуги графа необходимо отметить соответствующими выходными сигналами. Для автоматов Мили - дуга из z_i помечается парой x_k и y = (z_i,x_k). Для автоматов Мура - дуга, направленная в z_j, - парой x_k и y = (z_j,x_k).

При решении задач моделирования систем часто более удобной формой является матричное задание конечного автомата. При этом матрица соединений автомата есть квадратная матрица C = , строки которой соответствуют исходным состояниям, а столбцы - состояниям перехода. Элемент c_ij =x_k/y_s, стоящий на пересечении i-той строки и j-того столбца, в случает автомата Мили соответствует входному сигналу x_k, вызывающему переход из состояния z_i в состояние z_j, и выходному сигналу y_s, выдаваемому при этом переходе. Если переход из состояния z_i в состояние z_j происходит под действием нескольких сигналов, элемент матрицы c_ij представляет собой множество пар «вход-выход» для этого перехода, соединенный знаком дизъюнкции.

Для автомата Мура элемент c_ij равен множеству входных сигналов на переходе (z_i, z_j), а выход описывается вектором выходов, i-тая компонента которого - выходной сигнал, отмечающий состояние z_i.

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

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

Стохастические объекты (при моделировании которых учитываются случайные факторы), функционирующие в дискретном времени, можно представить вероятностными автоматами. Для такого автомата состояние z(t-1) и входной сигнал x(t) определяют не конечное состояние z(t), а распределение вероятностей P_ij перехода автомата из состояния z_i = z(t-1) в одно из возможных состояний z_j(t) в момент времени t под воздействием входного сигнала x(t) .

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

Математическими моделями стохастических объектов с непрерывным временем являются системы массового обслуживания (представители марковских случайных процессов).

Марковский случайный процесс. Классификация марковских процессов

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

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

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

Классификация марковских процессов

Марковские случайные процессы делятся на классы. Первый классификационный признак - характер спектра состояний. Случайный процесс (СП) называется процессом с дискретными состояниями, если возможные состояния системы S₁, S₂, S₃…можно перечислить, а сам процесс состоит в том, что время от времени система S скачком (мгновенно) перескакивает из одного состояния в другое.

Пример. Техническое устройство состоит из двух узлов I и II, каждый из которых может выйти из строя. Состояния: S₁ - оба узла работают; S₂ - первый узел отказал, второй рабочий; S₃ - второй узел отказал, первый рабочий; S₄ - оба узла отказали.

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

Рис.

Второй классификационный признак - характер функционирования во времени. СП называется процессом с дискретным временем, если переходы системы из состояния в состояние возможны только в строго определенные, заранее фиксированные моменты времени: t₁, t₂… . Если переход системы из состояния в состояние возможен в любой наперед неизвестный случайный момент, то говорят о СП с непрерывным временем.

Расчет марковской цепи с дискретным временем

Пусть имеется физическая система S с дискретными состояниями S₁, S₂, … S_n и дискретным временем t₁, t₂, … , t_k, … (шаги, этапы процесса, СП можно рассматривать как функцию аргумента (номера шага)). В общем случае СП состоит в том, что происходят переходы S₁ S₁ S₂ S₃ S₄ S₁ … в моменты t₁, t₂, t₃ ….

Будем обозначать событие, состоящее в том, что после k - шагов система находится в состоянии S_i. При любом k события образуют полную группу и несовместны. СП, происходящий в системе, можно представить как последовательность событий .

Такая случайная последовательность событий называется марковской цепью. Будем описывать марковскую цепь (МЦ) с помощью вероятностей состояний. Пусть - вероятность того, что после k - шагов система находится в состоянии S_i. Легко видеть, что k . Поставим задачу: найти вероятности состояний системы для любого k.

Для любого шага (момента времени t₁, t₂, … , t_k) существуют какие-то вероятности перехода системы из любого состояния в любое другое (некоторые из них равны нулю, если непосредственный переход за один шаг невозможен), а также вероятности задержки системы в одном состоянии. Будем их называть переходными вероятностями МЦ. Марковская цепь называется однородной, если переходные вероятности не зависят от номера шага, в противном случае - неоднородная МЦ. Рассмотрим однородную МЦ.

Пусть S= S₁, S₂, … S_n. Обозначим переходные вероятности через P_ij. Пусть известна матрица

.

Пользуюсь введенными выше событиями , переходные вероятности можно написать как условные вероятности:. Сумма членов в каждой строке матрицы должна быть равна 1. Вместо матрицы переходных вероятностей часто используют размеченный граф состояний (обозначают на дугах ненулевые вероятности переходов, вероятности задержки не требуются, поскольку они легко вычисляются, например P₁₁=1-(P₁₂+P₁₃)). Имея в распоряжении размеченный граф состояний (или матрицу переходных вероятностей) и зная начальное состояние системы, можно найти вероятности состояний p₁(k),p₂(k),…p_n(k) k.

Пусть начальное состояние системы S_m, тогда

p₁(0)=0 p₂(0)=0… p_m(0)=1… p_n(0)=0.

Первый шаг:

p₁(1)=P_m1, p₂(1)=P_m2,…p_m(1)=P_mm,… ,p_n(1)=P_mn.

После второго шага по формуле полной вероятности получим:

p₁(2)=p₁(1)P₁₁+p₂(1)P₂₁+…p_n(1)P_n1,

p_i(2)=p₁(1)P_1i+p₂(1)P_2i+…p_n(1)P_ni или .

Для произвольного шага k получаем:

(i=1,2,..n).

Для неоднородной МЦ переходные вероятности зависят от номера шага. Обозначим переходные вероятности для шага k через.

Тогда формула для расчета вероятностей состояний приобретает вид:

.

Марковские цепи с непрерывным временем. Уравнения Колмогорова

На практике значительно чаще встречаются ситуации, когда переходы системы из состояния в состояние происходит в случайные моменты времени, которые заранее указать невозможно: например, выход из строя любого элемента аппаратуры, окончание ремонта (восстановление) этого элемента. Для описания таких процессов в ряде случаев может быть с успехом применена схема марковского случайного процесса с дискретными состояниями и непрерывным временем - непрерывная цепь Маркова. Покажем, как выражаются вероятности состояний для такого процесса. Пусть S={S₁,S₂,…S_n}. Обозначим через p_i(t) - вероятность того, что в момент t система S будет находиться в состоянии ). Очевидно . Поставим задачу - определить для любого t p_i(t). Вместо переходных вероятностей P_ij введем в рассмотрение плотности вероятностей перехода

.

Если не зависит от t, говорят об однородной цепи, иначе - о неоднородной. Пусть нам известны для всех пар состояний (задан размеченный граф состояний). Оказывается, зная размеченный граф состояний можно определить p₁(t),p₂(t)..p_n(t) как функции времени. Эти вероятности удовлетворяют определенного вида дифференциальным уравнениям, (уравнения Колмогорова).



Рис.

Интегрирование этих уравнений при известном начальном состоянии системы даст искомые вероятности состояний как функции времени. Заметим, что p₁+p₂+p₃+p₄=1 и можно обойтись тремя уравнениями.

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

Поток событий. Простейший поток и его свойства

При рассмотрении процессов, протекающих в системе с дискретными состояниями и непрерывным временем, часто бывает удобно представить себе процесс так, как будто переходы системы из состояния в состояние происходят под действием каких-то потоков событий. Потоком событий называется последовательность однородных событий, следующих одно за другим в какие-то, вообще говоря, случайные моменты времени. (Поток вызовов на телефонной станции; поток неисправностей (сбоев) ЭВМ; поток грузовых составов, поступающих на станцию; поток посетителей; поток выстрелов, направленных на цель). Будем изображать поток событий последовательностью точек на оси времени ot. Положение каждой точки на оси случайно. Поток событий называется регулярным, если события следуют одно за другим через строго определенные промежутки времени (редко встречается на практике). Рассмотрим специального типа потоки, для этого введем ряд определений. 1. Поток событий называется стационарным, если вероятность попадания того или иного числа событий на участок времени длиной зависит только от длины участка и не зависит от того, где именно на оси ot расположен этот участок (однородность по времени) - вероятностные характеристики такого потока не должны меняться от времени. В частности, так называемая интенсивность (или плотность) потока событий (среднее число событий в единицу времени) постоянна.

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

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

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

Рассмотрим на оси оt, где наблюдается поток событий, некоторый участок длины , начинающийся в момент t₀ и заканчивающийся в момент t₀+. Нетрудно доказать (доказательство дается во всех курсах теории вероятности), что вероятность попадания на этот участок ровно m событий выражается формулой:

(m=0,1…),

где а - среднее число событий, приходящееся на участок .

Для стационарного (простейшего) пуассоновского потока а=, т.е. не зависит от того, где на оси ot взят участок . Для нестационарного пуассоновского потока величина а выражается формулой

и значит, зависит от того, в какой точке t₀ начинается участок .

Рассмотрим на оси ot простейший поток событий с постоянной интенсивностью . Нас будет интересовать интервал времени T между событиями в этом потоке. Пусть - интенсивность (среднее число событий в 1 времени) потока. Плотность распределения f(t) случайной величины Т (интервал времени между соседними событиями в потоке) f(t)=e^-t (t0). Закон распределения с такой плотностью называется показательным (экспоненциальным). Найдем численные значения случайной величины Т: математическое ожидание (среднее значение) и дисперсию

.



Рис.

Промежуток времени Т между соседними событиями в простейшем потоке распределен по показательному закону; его среднее значение и среднее квадратичное отклонение равны , где - интенсивность потока. Для такого потока вероятность появления на элементарном участке времени ?t ровно одного события потока выражается как . Эту вероятность мы будем называть «элементом вероятности появления события». Для нестационарного пуассоновского потока закон распределения промежутка Т уже не будет показательным. Вид этого закона будет зависеть, во первых, от того, где на оси ot расположено первое из событий, во вторых, от вида зависимости . Однако, если меняется сравнительно медленно и его изменение за время между двумя событиями невелико, то закон распределения промежутка времени между событиями можно приближенно считать показательным, полагая в этой формуле величину равной среднему значению на том участке, который нас интересует.

Пуассоновские потоки событий и непрерывные марковские цепи

Рассмотрим некоторую физическую систему S={S₁,S₂,…S_n}, которая переходит из состояния в состояние под влиянием каких-то случайных событий (вызовы, отказы, выстрелы). Будем себе это представлять так, будто события, переводящие систему из состояния в состояние, представляют собой какие-то потоки событий.



Рис.

Пусть система S в момент времени t находится в состоянии S_i и может перейти из него в состояние S_j под влиянием какого-то пуассоновского потока событий с интенсивностью _ij: как только появляется первое событие этого потока, система мгновенно переходит из S_i в S_j . Как мы знаем, вероятность этого перехода за элементарный промежуток времени (элемент вероятности перехода) равна , отсюда вытекает, что плотность вероятности перехода _ij в непрерывной цепи Маркова представляет собой не что иное, как интенсивность потока событий, переводящих систему по соответствующей стрелке. Если все потоки событий, переводящие систему S из состояния в состояние пуассоновские, то процесс, протекающий в системе, будет марковским.

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

Пример. Техническая система S состоит из двух узлов I и II, каждый из которых независимо от другого может отказывать. Поток отказов первого узла пуассоновский с интенсивностью _I, второго также пуассоновский с интенсивностью _II. Каждый узел сразу после отказа начинает ремонтироваться (восстанавливаться). Поток восстановлений (окончаний ремонта узла) для обоих узлов - пуассоновский с интенсивностью . Составить граф состояний системы и написать уравнение Колмогорова. Состояния системы: S₁₁ - оба узла исправны; S₂₁ - первый узел ремонтируется, второй исправен; S_12, S₂₂.

Рис.

t=0 p₁₁=1 p₂₁=p₂₂=p₁₂=0

p₁₁+p₁₂+p₂₁+p₂₂=1.

Предельные вероятности состояний для непрерывной марковской цепи

Пусть имеется физическая система S={S₁,S₂,…S_n}, в которой протекает марковский случайный процесс с непрерывным временем (непрерывная цепь Маркова). Предположим, что _ij=const, т.е. все потоки событий простейшие (стационарные пуассоновские). Записав систему дифференциальных уравнений Колмогорова для вероятностей состояний и проинтегрировав эти уравнения при заданных начальных условиях, мы получим p₁(t), p₂(t),… p_n(t), при любом t. Поставим следующий вопрос, что будет происходить с системой S при t. Будут ли функции p_i(t) стремиться к каким-то пределам? Эти пределы, если они существуют, называются предельными вероятностями состояний. Можно доказать теорему: если число состояний S конечно и из каждого состояния можно перейти (за то или иное число шагов) в каждое другое, то предельные вероятности состояний существуют и не зависят от начального состояния системы. Предположим, что поставленное условие выполнено и предельные вероятности существуют (i=1,2,…n), .

Таким образом, при t в системе S устанавливается некоторый предельный стационарный режим. Смысл этой вероятности: она представляет собой не что иное, как среднее относительное время пребывания системы в данном состоянии. Для вычисления p_i в системе уравнений Колмогорова, описывающих вероятности состояний, нужно положить все левые части (производные) равными 0. Систему получающихся линейных алгебраических уравнений надо решать совместно с уравнением .

Схема гибели и размножения

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