Глава 2. Модели и методы описания систем

Глава 2 Модели и методы описания систем
2.1. Методы описания систем
Методы описания систем классифицируются в порядке возрастания формализованности - от качественных методов, с которыми в основном и связан был первоначально системный анализ, до количественного моделирования с применением ЭВМ. Разделение методов на качественные и количественные носит, конечно, условный характер.
В качественных методах основное внимание уделяется организации постановки задачи, новому этапу ее формализации, формированию вариантов, выбору подхода к оценке вариантов, использованию опыта человека, его предпочтений, которые не всегда могут быть выражены в количественных оценках.
Количественные методы связаны с анализом вариантов, с их количественными характеристиками корректности, точности и т. п. Для постановки задачи эти методы не имеют средств, почти полностью оставляя осуществление этого этапа за человеком.
Между этими крайними классами имеются методы, которые стремятся охватить оба этапа этап постановки задачи, разработки вариантов и этап оценки и количественного анализа вариантов, но делают это с разной степенью формализованности.
Качественные методы описания систем
Качественные методы системного анализа применяются, когда отсутствуют описания закономерностей систем в виде аналитических зависимостей.
Методы типа мозговой атаки. Концепция «мозговой атаки» получила широкое распространение с начала 50-х годов как метод систематической тренировки творческого мышления, нацеленный на открытие новых идей и достижение согласия группы людей на основе интуитивного мышления. Методы этого типа известны также под названиями «мозговой штурм», «конференция идей», а в последнее время наибольшее распространение получил термин «коллективная генерация идей» (КГИ).
Обычно при проведении мозговой атаки или сессий КГИ стараются выполнять определенные правила, суть которых:
обеспечить как можно большую свободу мышления участников КГИ и высказывания ими новых идей;
приветствуются любые идеи, находящиеся на стыке отраслей науки и техники;
не допускается критика, не объявляется ложной и не прекращается обсуждение ни одной идеи;
желательно высказывать как можно больше идей, особенно нетривиальных.
Подобием сессий КГИ можно считать разного рода совещания конструктораты, заседания научных советов по проблемам, заседания специально создаваемых временных комиссий и другие собрания компетентных специалистов.
Методы типа сценариев. Методы подготовки и согласования представлений о проблеме или анализируемом объекте, изложенные в письменном виде, получили название сценария. Первоначально этот метод предполагал подготовку текста, содержащего логическую последовательность событий или возможные варианты решения проблемы, развернутые во времени. Однако позднее обязательное требование явно выраженных временных координат было снято, и сценарием стали называть любой документ, содержащий анализ рассматриваемой проблемы или предложения по ее решению, по развитию системы независимо от того, в какой форме он представлен. Примерами являются послания президента, предвыборные программы, аналитические записки.
Методы экспертных оценок. Термин «эксперт» происходит от латинского слова, означающего «опытный».
При использовании экспертных оценок обычно предполагается, что мнение группы экспертов надежнее, чем мнение отдельного эксперта, хотя это предположение не является очевидным.
При обработке материалов коллективной экспертной оценки используются методы корреляционного анализа. Для количественной оценки степени согласованности мнений экспертов применяется коэффициент конкордации
13 EMBED Equation.2 1415 где 13 EMBED Equation.2 1415
m количество экспертов, j=13 EMBED Equation.2 1415, n количество рассматриваемых объектов (или свойств объекта), 13 EMBED Equation.2 1415 rij место, которое заняло i-й объект в ранжировке j-м экспертом; di отклонение суммы рангов по i-му объекту от среднего арифметического сумм рангов по n объектам.
Коэффициент конкордации W позволяет оценить, насколько согласованы между собой ряды предпочтительности, построенные каждым экспертом. Его значение находится в пределах 0 ( W ( 1. W = 0 означает полную противоположность, а W = 1 полное совпадение ранжировок. Практически достоверность считается хорошей, если W = 0,7...0,8.
Методы типа «Дельфи». Характерный для середины XX века бурный рост науки и техники вызвал большие перемены в отношении к оценкам будущего развития систем. Одним из результатов этого периода в развитии методов анализа сложных систем явилась разработка методов экспертной оценки, известных в литературе как «методы Дельфи». Название этих методов связано с древнегреческим городом Дельфи, где при храме Аполлона с IX века до н.э. до IV века н.э. по преданиям существовал Дельфийский оракул.
Суть метода Дельфи заключается в следующем. В отличие от традиционного подхода к достижению согласованности мнений экспертов путем открытой дискуссии метод Дельфи предполагает полный отказ от коллективных обсуждений. Это делается для того, чтобы уменьшить влияние таких психологических факторов, как присоединение к мнению наиболее авторитетного специалиста, нежелание отказаться от публично выраженного мнения, следование за мнением большинства. В методе Дельфи прямые дебаты заменены тщательно разработанной программой последовательных индивидуальных опросов, проводимых обычно в форме анкетирования. Ответы экспертов обобщаются и вместе с новой дополнительной информацией поступают в распоряжение экспертов, после чего они уточняют свои первоначальные ответы. Такая процедура повторяется несколько раз до достижения приемлемой сходимости совокупности высказанных мнений. Результаты эксперимента показали приемлемую сходимость оценок экспертов после пяти туров опроса.
Метод Дельфи первоначально был предложен О. Хелмером как итеративная процедура при проведении мозговой атаки, которая должна помочь снизить влияние психологических факторов при проведении повторных заседаний и повысить объективность результатов. Однако почти одновременно Дельфи-процедуры стали основным средством повышения объективности экспертных опросов с использованием количественных оценок при оценке деревьев цели и при разработке сценариев.
Методы типа дерева целей (дерева задач). Идея метода дерева целей впервые была предложена Черчменом в связи с проблемами принятия решений в промышленности. Термин «дерево целей» подразумевает использование иерархической структуры, полученной путей разделения общей цели на подцели, а их, в свою очередь, на более детальные составляющие новые подцели, функции и т. д. Как правило, этот термин используется для структур, имеющих отношение строгого древесного порядка, но метод дерева целей используется иногда и применительно к «слабым» иерархиям в которых одна и та же вершина нижележащего уровня может быть одновременно подчинена двум или нескольким вершина» вышележащего уровня.
Древовидные иерархические структуры используются и при исследовании и совершенствовании организационных структур. Не всегда разрабатываемое даже для анализа целей дерево может быть представлено в терминах целей. Иногда, например, при анализе целей научных исследований удобнее говорить о дереве направлений прогнозирования. В. М. Глушковым, например, был предложен и в настоящее время широко используется термин «прогнозный граф». При использовании этого понятия появляется возможность более точно определить понятие дерева как связного ориентированного графа, не содержащего петель, каждая пара вершин которого соединяется единственной цепью.
Морфологические методы. Основная идея морфологических методов систематически находить все «мыслимые» варианты решения проблемы или реализации системы путем комбинирования выделенных элементов или их признаков. Идеи морфологического образа мышления восходят к Аристотелю, Платону, к известной средневековой модели механизации мышления Р. Луллия. В систематизированном виде морфологический подход был разработан и применен впервые швейцарским астрономом Ф. Цвикки и долгое время был известен как метод Цвикки.
Цвикки предложил три метода морфологического исследования.
Первый метод метод систематического покрытия поля, основанный на выделении так называемых опорных пунктов знания в любой исследуемой области и использовании для заполнения поля некоторых сформулированных принципов мышления. Второй метод отрицания и конструирования, базирующийся на идее Цвикки, заключающейся в том, что на пути конструктивного прогресса стоят догмы и компромиссные ограничения, которые есть смысл отрицать, и, следовательно, сформулировав некоторые предложения, полезно заменить их затем на противоположные и использовать при проведении анализа.
Третий метод морфологического ящика, нашедший наиболее широкое распространение. Идея морфологического ящика состоит в определении всех «мыслимых» параметров, от которых может зависеть решение проблемы, и представлении их в виде матриц-строк, а затем в определении в этом морфологическом матрице-ящике всех возможных сочетаний параметров по одному из каждой строки. Полученные таким образом варианты могут затем подвергаться оценке и анализу с целью выбора наилучшего. Морфологический ящик может быть не только двумерным. Например, А. Холл использовал для исследования структуры систем трехмерный ящик.
Морфологические ящики Цвикки нашли широкое применение для анализа и разработки прогноза в технике. Для организационных же систем, систем управления такой ящик, который, по-видимому, был бы многомерным, практически невозможно построить.
Методика системного анализа. Методики, реализующие принципы системного анализа в конкретных условиях, направлены на то, чтобы формализовать процесс исследования системы, процесс постановки и решения проблемы. Методика системного анализа разрабатывается и применяется в тех случаях, когда у исследователя нет достаточных сведений о системе, которые позволили бы выбрать адекватный метод формализованного представления системы.
Общим для всех методик системного анализа является формирование вариантов представления системы (процесса решения задачи), выбор наилучшего варианта, корректировка. Положив в основу методики системного анализа эти три этапа, их затем можно разделить на подэтапы. Например, так выглядят этапы проектирования:













Рис. 2.1. Этапы проектирования систем
В настоящее время трудно привести примеры методик, в которых все этапы были бы проработаны равноценно.
Количественные методы описания систем
Уровни описания систем. При создании и эксплуатации сложных систем требуется проводить многочисленные исследования и расчеты, связанные с:
оценкой показателей, характеризующих различные свойства систем;
выбором оптимальной структуры системы;
выбором оптимальных значений ее параметров.
Выполнение таких исследований возможно лишь при наличии математического описания процесса функционирования системы, т. е. ее математической модели.
Сложность реальных систем не позволяет строить для них «абсолютно» адекватные модели. Математическая модель описывает некоторый упрощенный процесс, в котором представлены лишь основные явления, входящие в реальный процесс, и лишь главные факторы, действующие на реальную систему.
Какие явления считать основными и какие факторы главными существенно зависит от назначения модели, от того, какие исследования с ее помощью предполагается проводить. Поэтому процесс функционирования одного и того же реального объекта может получить различные математические описания в зависимости от поставленной задачи.
Так как математических моделей сложной системы может быть сколько угодно много, и все они определяются принятым уровнем абстрагирования, то рассмотрение задач на каком-либо одном уровне абстракции позволяет дать ответы на определенную группу вопросов, а для получения ответов на другие вопросы необходимо провести исследование уже на другом уровне абстракции. Каждый из возможных уровней абстрагирования обладает ограниченными, присущими только данному уровню абстрагирования возможностями. Для достижения максимально возможной полноты сведений необходимо изучить одну и ту же систему на всех целей сообразных для данного случая уровнях абстракции.
Наиболее пригодными являются следующие подходы абстрактного описания систем:
символический, или, иначе, лингвистический;
теоретико-множественный;
топологический;
логико-математический;
теоретико-информационный; агрегатный
кибернетический;
эвристический.
Лингвистический подход описания наиболее высокий уровень абстрагирования. Из него как частные случаи можно получить другие уровни абстрактного описания систем более низкого ранга. Процесс формализации в математике обычно понимают как отвлечение от изменчивости рассматриваемого объекта. Поэтому формальные построения наиболее успешно используются, когда удается с предметами или процессами действительности каким-то образом сопоставлять некоторые стабильные, неизменные понятия. Используются инструменты формальной лингвистики: предикаты, термы, функторы.
При теоретико-множественном подходе абстракции можно получить только общие сведения о реальных системах, а для более конкретных целей необходимы другие модели, которые позволили бы производить более тонкий анализ различных свойств реальных систем. Эти более низкие уровни абстрагирования, в свою очередь, являются уже частными случаями по отношению к теоретико-множественному уровню формального описания систем.
Если же на элементах рассматриваемых множеств определены некоторые пространственные структуры, то в этом случае приходим к топологическому подходу абстрактного описания систем. При этом может быть использован язык общей топологии или ее ветвей, именуемых гомологической топологией, алгебраической топологией и т. д.
Логико-математический подход описания систем нашел широкое применение для: формализации функционирования автоматов; задания условий функционирования автоматов; изучения вычислительной способности автоматов.
При любом процессе управления или регулирования, осуществляемом живым организмом или автоматически действующей машиной либо устройством, происходит переработка входной информации в выходную. Поэтому при теоретико-информационном подходе абстрактного описания систем информация выступает как способ взаимодействия объектов и явлений, которые посредством отражения передаются от одного объекта к другому и запечатлеваются в его структуре (возможно, в измененном виде).
Отображение множества состояний источника во множество состояний носителя информации называется способом кодирования, а образ состояния при выбранном способе кодирования кодом этого состояния.
Абстрагируясь от физической сущности носителей информации и рассматривая их как элементы некоторого абстрактного множества, а способ их расположения как отношение в этом множестве, приходят к абстрактному понятию кода информации как способа ее представления. При таком подходе любая система представляется в виде кодирующего устройства. Т.е. входы в систему представляются в виде исходной информации, а выходы – в виде информации, преобразованной по формальным правилам.
Кибернетический подход абстрактного описания систем связан с представлением системы как некоторого объекта, куда в определенные моменты времени можно вводить вещество, энергию и информацию, а в другие моменты времени выводить их. Система представляется как объект управления, двигающийся к определенной цели.
Эвристический подход абстрактного описания систем предусматривает поиски удовлетворительного решения задач управления в связи с наличием в сложной системе человека. Эврика это догадка, основанная на общем опыте решения родственных задач. Изучение интеллектуальной деятельности человека в процессе управления имеет очень важное значение. Моделируется человеческое мышление, интуиция.
Таким образом, обзор уровней абстрактного описания систем показывает, что выбор подходящего метода формального описания при изучении той или иной реальной системы является всегда наиболее ответственным и трудным шагом в теоретико-системных построениях. Эта часть исследования почти не поддастся формализации и во многом зависит от эрудиции исследователя, его профессиональной принадлежности, целей исследования и т. д. Наибольшее значение в настоящее время в абстрактной теории систем придается теоретико-множественному, теоретико-информационному и кибернетическому подходам описания систем.
2.1. Теоретико-множественный подход к описанию систем
Для получения математической модели процесса функционирования системы, чтобы она охватывала широкий класс реальных объектов, в общей теории систем исходят из общих предположений о характере функционирования системы:
система функционирует во времени; в каждый момент времени система может находиться в одном из возможных состояний;
на вход системы могут поступать входные сигналы;
система способна выдавать выходные сигналы;
состояние системы в данный момент времени определяется предыдущими состояниями и входными сигналами, поступившими в данный момент времени и ранее;
выходной сигнал в данный момент времени определяется состояниями системы, относящимися к данному и предшествующим моментам времени.
Первое предположение отражает динамический характер процесса функционирования в пространстве и времени. При этом процесс функционирования протекает как последовательная смена состояний системы под действием внешних и внутренних причин. 2-е и 3-е – отражают взаимодействие системы с внешней средой. В 4-м и 5-м предложениях отражается реакция системы на внутренние факторы и воздействия внешней среды: последействие и принцип физической реализуемости.
Последействие – это тенденции, определяющие поведение системы в будущем, зависят не только от того, в каком состоянии находится система в настоящий момент времени, но и в той или иной степени от ее поведения в предыдущие моменты времени.
Принцип физической реализуемости: система не реагирует в данный момент времени на «будущие» факторы и воздействия внешней среды.
Для описания систем ее подсистемы (или элементы) перечисляются с помощью некоторых множеств Vi и устанавливается характер связей между ними.
S ( ( {Vi, i(I}, где
Vi – i-тая компонента декартова произведения ( Vi, называемая объектом системы S, I-множество индексов. Или иначе:
S ( V1(V2(V3(...(Vm
Абстрактно-алгебраические модели описывают связи как семейство отношений (унарных, бинарных ... n-арных)
R = {R1,R2,...,Rn}
Под отношением, введенным на множестве А, понимается подмножество декартового произведения конечной степени An=A(A(....(A данного множества A, т.е. подмножество кортежей (a1, a2, an) из n элементов множества A.
Подмножество R(An называется n-местным или n-арным отношением в множестве A. Число n называется рангом или типом отношения R. Множество всех n-арных отношений в множестве A относительно операций ( и ( является булевой алгеброй.
Примеры отношений на множестве V «Люди»:
унарное отношение «мужчины»: R={v(V | пол(v)=мужской}
бинарное отношение «старше»: R={(v1,v2)(V2 | возраст(v1)>возраст(v2)}
трехместное отношение «являются родителями»: {тройка, где 1-й элемент – отец, второй – мать, третий – ребенок}
Функциональные модели определят связи как множество отображений.
Если множество индексов I конечно, то разобьем его два подмножества Iu и Iy. В общем случае пересечение этих подмножеств может быть не пусто. Iu ( I и Iy.( I. Множество U=({Vi | i(Iu} назовем причинами, а множество Y=({Vi | i(Iy} назовем следствиями. Тогда система S ( U(Y. Система S называется функциональной, если она представляется в виде отображения S: U(Y.
Временные модели в качестве одного из объектов системы S вводят множество моментов времени Т.
Если элементы одного из объектов системы есть функции, например (: T((V(, то этот объект называют функциональным. В случае, когда области определения всех функций для данного объекта V одинаковы, т.е. каждая функция отображает T в V, (: T(V, то T называется индексирующим множеством для (. Если индексирующее множество линейно-упорядочено, то его называют множеством моментов времени. Функции, определенные на множестве моментов времени, принято называть функциями времени. Объект, элементами которого являются временные функции, называют временным объектом, а системы определенные на временных объектах – временными системами.
2.3. Кибернетический подход к описанию систем
Управление как процесс. Кибернетический подход к описанию систем состоит в том, что всякое целенаправленное поведение рассматривается как управление. Управление в широком, кибернетическом смысле это обобщение приемов и методов, накопленных разными науками об управлении искусственными объектами и живыми организмами. Язык управления это использование понятий «объект», «среда», «обратная связь», «алгоритм» и т.д. Основы современной кибернетики заложил Н. Винер.
13 SHAPE \* MERGEFORMAT 1415
Под управлением будем понимать процесс организации такого целенаправленного воздействия на некоторую часть среды, называемую объектом управления, в результате которого удовлетворяются потребности субъекта, взаимодействующего с этим объектом.
Анализ управления заставляет выделить тройку среду, объект и субъект, внутри которой разыгрывается процесс управления (рис.2.2). В данном случае субъект ощущает на себе воздействие среды Q и объекта Y. Причем, если состояние среды Q он изменить не может, то состоянием объекта Y он может управлять с помощью специально организованного воздействия U. Это воздействие и есть управление.
Состояние объекта Y влияет на состояние потребностей субъекта. Потребности субъекта A = (a1,,ak), где ai состояние i-й потребности субъекта, которая выражается неотрицательным числом, характеризующим насущность, актуальность этой потребности. Свое поведение субъект строит так, чтобы минимизировать насущность своих потребностей, т. е. решает задачу многокритериальной оптимизации:
ai min {R}, (13 EMBED Equation.3 1415, (2.1)
где R ресурсы субъекта. Эта зависимость выражает неизвестную, но существующую связь потребностей с состоянием среды Q и поведением U субъекта.
Пусть 13 EMBED Equation.2 1415 решение задачи (2.1), т. е. оптимальное поведение субъекта, минимизирующее его потребности А. Способ решения задачи (2.1), позволяющий определить13 EMBED Equation.2 1415, называется алгоритмом управления
13 EMBED Equation.2 1415 (2.2)
где ( алгоритм, позволяющий синтезировать управление по состоянию среды Q и потребностей Аt. Потребности субъекта изменяются не только под влиянием среды или объекта, но и самостоятельно, отражая жизнедеятельность субъекта, что отмечается индексом t.
Алгоритм управления (, которым располагает субъект, и определяет эффективность его функционирования в данной среде. Обычно алгоритм имеет рекуррентный характер:
13 EMBED Equation.2 1415
т. е. позволяет на каждом шаге улучшать управление. Например, в смысле13 EMBED Equation.2 1415, т. е. уменьшения уровня своих потребностей. Впрочем, потребности еще надо осознать, и это составляет пока неформализуемую стадию управления.

13 SHAPE \* MERGEFORMAT 1415
Структурная схема системы управления (СУ) приведена на рис. 2.3. Здесь Dq и Dy датчики, измеряющие состояние среды и объекта соответственно. Результаты измерений Q'=Dq(Q) и Y'=Dy(Y) образуют исходную информацию {Q', Y'} для устройства управления (УУ), которое на ее основе вырабатывает команду управления (. Исполнительный механизм (ИМ), реализуя команду управления, вырабатывает входное воздействие U на управляемые входы объекта.
Управление целенаправленная организация того или иного процесса, протекающего в системе. В общем случае процесс управления состоит из следующих четырех элементов:
получение информации о задачах управления (A),
получение информации о результатах управления (т. е. о поведении объекта управления Y’);
анализ полученной информации и выработка решения ((=((А,Q',У')),
исполнение решения (т. е. осуществление управляющих воздействий U).
Процесс управления это информационный процесс, заключающийся в сборе информации о ходе процесса, передаче ее в пункты накопления и переработки, анализе поступающей, накопленной и справочной информации, принятии решения на основе выполненного анализа, выработке соответствующего управляющего воздействия и доведении его до объекта управления.
Каждая фаза процесса управления протекает во взаимодействии с окружающей средой при воздействии различного рода помех. Цели, принципы и границы управления зависят от сущности решаемой задачи.
Система управления совокупность взаимодействующих между собой объекта управления и органа управления, деятельность которых направлена заданной цели управления.
В СУ решаются четыре основные задачи управления: стабилизация, выполнение программы, слежение, оптимизация.
Задачами стабилизации системы являются задачи поддержания выходной величины Y вблизи некоторого заранее заданного значения, несмотря на действие помех. Например, стабилизация напряжения и частоты тока в сети вне зависимости от изменения потребления энергии.
Задача выполнения программы возникает в случаях, когда требуется изменять величину U во времени заранее известным образом.
В системах оптимального управления требуется формировать входное воздействие U так, чтобы экстремизировать выход объекта управления Y. при заданных реальных условиях и ограничениях. Понятие оптимальности должно быть конкретизировано для каждого отдельного случая.
Задачи слежения означают, что величину Y требуется поддерживать на уровне, определяемом неконтролируемым воздействием среды Q.
Системы управления делятся на два больших класса: системы автоматического управления (САУ) и автоматизированные системы управления (АСУ). В САУ управление объектом или системой осуществляется без непосредственного участия человека автоматическими устройствами. Это замкнутые системы. Основные функции САУ: автоматический контроль и измерения, автоматическая сигнализация, автоматическая защита, автоматические пуск и остановка различных двигателей и приводов, автоматическое поддержание заданных режимов работы оборудования, автоматическое регулирование. В отличие от САУ в АСУ в контур управления включен человек, на которого возлагаются функции принятия наиболее важных решений и ответственности за принятые решения. Под АСУ обычно понимают человеко-машинные системы, использующие современные экономико-математические методы, средства электронно-вычислительной техники и связи, а также новые организационные принципы для отыскания и реализации на практике наиболее эффективного управления объектом (системой).
2.4. Агрегативное описание систем
Понятие «агрегат» в теории систем
Пусть T – фиксированное подмножество действительных чисел (множество рассматриваемых моментов времени), Z, U, Y, X – множества любой природы. Элементы указанных множеств назовем, как и ранее: t(T – моментом времени; u(U; входным сигналом; z(Z - управляющим сигналом; y(Y – выходным сигналом; x(X состоянием. Разница между входным сигналом и управляющим состоит в следующем – управляющий сигнал влияет на выходной непосредственно, а входной сигнал – опосредованно через состояние. Состояния, входные, управляющие и выходные сигналы, рассматриваемые как функции времени, обозначим x(t), u(t), z(t) и y(t).
Под агрегатом будем понимать объект , где H,G – операторы (вообще говоря, случайные). Операторы переходов и выходов H и G реализуют функции x(t) и y(t) и представляют собой обобщение переходного отображения ( и функции наблюдения (. Структура этих операторов собственно и выделяет агрегаты среди прочих систем.
Предположение 1. Будем предполагать, что за конечный интервал времени в агрегат поступает конечное число входных и управляющих сигналов и вырабатывается конечное число выходных сигналов.
Операторы переходов и выходов агрегата
Операторы переходов. Наряду с состоянием x(t) будем рассматривать также точки x(t+0). Договоримся считать, что для любого t1>t момент (t+0)((t,t1]. Аналогично: x(t-0) означает, что 13 EMBED Equation.3 1415 t0Под особыми состояниями будем понимать его состояния в момент получения входного либо управляющего сигналов или выдачи выходного сигнала. Все остальные состояния агрегата будем называть неособыми.
Предположение 2. Из особых состояний агрегат может переходить в новое состояние скачком.
Пусть x(t*) – некоторое особое состояние агрегата, а zs – последний управляющий сигнал zs(Z. Примем следующие обозначения для операторов, являющихся частными видами оператора H и определяющих состояние агрегата в момент t*+0. Если t* - момент поступления входного сигнала u, то
x(t*+0)=V([x(t*), u, zs] . (2.3)
Аналогично, если t* - момент поступления управляющего сигнала z, то
x(t*+0)=V(([x(t*), z] . (2.4)
При одновременном поступлении u и z
x(t*+0)=V [x(t*), u, z] (2.5)
Наконец, если t* - момент выдачи выходного сигнала y, то
x(t*+0)=W[x(t*), zs] . (2.6)
В интервале между особыми состояниями, значение x(t) определяется при помощи операторов Q, вид которых в общем случае зависит от особого состояния, являющегося для данного интервала времени начальным состоянием:
x(t*+0)=13EMBED Equation.31415[t,x(t*), zs]. (2.7)
Здесь t* - момент особого состояния, являющегося исходным для данного интервала времени. То есть H является общим обозначением операторов Q,V(,V((,V и W.
Оператор выходов. Во множестве X состояний x(t) агрегата выделим класс подмножеств {Xy} (подмножества состояний, влекущих за собой необходимость выдачи выходного сигнала), обладающих следующими свойствами. Выходной сигнал y выдается в момент t( в двух случаях, когда:
x(t()(Xy; x(t(-0)(Xy
x(t(+0)(Xy, но x(t’)(Xy.
Тогда, оператор G можно представить в виде совокупности двух операторов: функционального оператора G(, вырабатывающего выходной сигнал
y(t()=G([x(t(),zs] (2.8)
и логического оператора G((, проверяющего для каждого t принадлежность x(t) к одному из подмножеств Xy. Заметим, что в общем случае, оператор G( является случайным оператором. Это значит, что данным t, x(t), z ставится в соответствие не одно определенное значение выходного сигнала, а некоторое множество значений y с распределением вероятностей, задаваемых оператором G(.
Например, в качестве одной составляющих вектора x(t) (например x1(t)) может быть время, оставшееся до выдачи выходного сигнала. Тогда оператор G(( проверяет неравенство x1(t)>0.
Процесс функционирования агрегата. Агрегат функционирует следующим образом. В начальный момент времени t0 заданы начальное состояние агрегата x0 и начальное значение управляющего сигнала z0.
Пусть t1 и t2 – моменты поступления первого u1 и второго u2 входных сигналов, (1 – момент поступления первого управляющего сигнала z1 и, для определенности t1<(1Рассмотрим полуинтервал (t0,t1]. Состояния агрегата изменяются с течением времени по закону (2.7):
x(t)=13EMBED Equation.31415[t,x0,z0] (t0до тех пор (оператор G((), пока в момент t( состояние x(t() не окажется принадлежащим подмножеству Xy, хотя состояние x(t(-0) не принадлежало подмножеству Xy. В этом случае в момент t( выдается выходной сигнал y1, вырабатываемый оператором G(. Вместе с тем закон изменения состояний (2.7) нарушается и переключается на закон (2.6):
x(t(+0)=W[x(t(),z0].
Пусть теперь в момент t1 поступает входной сигнал u1. Проследим поведение агрегата в момент t1 (см. закон (2.3)). Тогда в силу действия входного сигнала u1 состояние агрегата имеет вид
x(t1+0)=V([x(t1),u1,z0], (2.9)
а в дальнейшем, если состояние (2.9) не соответствует выдаче выходного сигнала, то:
x(t)=13EMBED Equation.31415[t,V([x(t1),u1,z0],z0] t1Пусть в момент (1 в агрегат поступает управляющий сигнал z1. Тогда состояние агрегата имеет вид (см. закон (2.4)).
x((1+0)=V(([x((1),z1],
Необходимо отметить, что управляющий сигнал z в общем случае является параметром, определяющим операторы V(, V((, W, Q, G(, G((. Поэтому в дальнейшем вместо начального значения управляющего сигнала z0 в этих операторах должно использоваться значение z1 до тех пор, пока не поступит следующий управляющий сигнал z2. Например, в полуинтервале ((1, t2], если нет оснований для выдачи выходного сигнала
x(t)=13EMBED Equation.31415[t, x((1+0), z1] (1В частном случае, операторы H и G могут оставаться неизменными при поступлении очередного управляющего сигнала. Аналогично, оператор Q может быть одним и тем же при любых выходных сигналах (при попадании x(t) в любые подмножества Xy).
Агрегат представляет собой математическую схему весьма общего вида, частными случаями которой являются функции алгебры логики, релейно-контактные схемы, конечные автоматы, всевозможные классы систем массового обслуживания, динамические системы, описываемые обыкновенными дифференциальными уравнениями и некоторые другие объекты. С точки зрения моделирования агрегат выступает как достаточно универсальный переработчик информации – он воспринимает входные и управляющие сигналы и выдает выходные сигналы.
Кусочно-линейные агрегаты
Как показывает анализ моделирующих алгоритмов, можно добиться их существенных упрощений, если рассматривать объекты более частные, чем агрегат общего вида, но сохраняющие возможность описания достаточно широкого класса реальных систем. Практически удобным для формализации широкой совокупности разнообразных процессов и явлений материального мира являются так называемые кусочно-линейные агрегаты (КЛА).
Понятие о кусочно-линейном агрегате. Для поставленных здесь задач достаточно считать, что на агрегат не поступают управляющие сигналы z, а поступают лишь входные сигналы u (это допущение не ограничивает общности, так как в качестве u можно рассматривать входной сигнал в широком смысле, в том числе и управляющий). Итак, мы рассматриваем агрегат как объект, который в каждый момент времени t характеризуется внутренним состоянием x(t), имеет вход и выход. На вход агрегат в изолированные моменты времени могут поступать сигналы, с выхода могут сниматься выходные сигналы. Класс кусочно-линейных агрегатов выделяется с помощью конкретизации структуры множеств X, U, Y а также операторов H и G, которые представляют собой линейные пространства. Опишем данную конкретизацию.
Рассмотрим некоторое конечное или счетное множество I. Для определенности предположим, что I = {0,1,2,}, хотя в конкретных задачах I может иметь и другой вид. Назовем I множеством особых состояний, а элементы ((I – особыми состояниями. Каждому особому состоянию ((I поставим в соответствие некоторое целое неотрицательное число ||(||, которое назовем рангом основного состояния (смысл этой величины – размерность вектора (-го состояния). Кроме того, каждому ((I поставим в соответствие выпуклый многогранник X(() (множество допустимых значений для состояния () в евклидовом пространстве размерности ||(||. Будем считать, что X = (X((), т. е. пространство состояний X можно представить состоящим из всевозможных пар вида (13EMBED Equa
·tion.31415), где ((I, а x(() является вектором размерности ||(|| и принимает значения из многогранника X((). Вектор x(() будем называть вектором координат. Если ||(|| = 0 для некоторого (, то это означает, что в данном состоянии ( координаты не определяются.
Процесс функционирования КЛА. Опишем сначала динамику КЛА, т.е. процесс изменения внутренних состояний во времени, в предположении отсутствия поступления u. В предыдущей терминологии, определим действия оператора Q. Пусть в начальный момент времени t0 агрегат находится в состоянии x(t0)=((,x(()(0)), где x(()(0) - внутренняя точка многогранника X((). Тогда при t>t0 точка x(()(t) перемещается внутри многогранника X(() до тех пор, пока не достигнет его границы. Пусть это произойдет в момент t1, который назовем «особым». Тогда при t0((t)=(=const (2.10),
x(()(t)=x(()(0)+ (t-t0)((((). (2.11)
Данному значению ( соответствует вектор ((() (скорость изменения координат) размерности ||(|| (cp. (2.7)).
Значение особого момента t1 определяется траекторией x(t), вернее её некоторыми параметрами и может быть найдено из соотношения
t1=inf{t: x(()(0)+(t-t0)((()(X((), t>t0}. (2.12)
Поскольку X(() – многогранник, то нахождение t1 по правилу (2.12) сводится к следующему. Предположим, что X(() содержит m граней. Эти грани могут быть заданы линейными уравнениями:
13EMBED Equation.31415, j=1,, m ,
где xi(() – компоненты вектора x((), i=1.. ||(||. Легко понять, что (2.12) может быть записано в виде
13EMBED Equation.31415 (2.13)
Обозначим 13EMBED Equation.31415 , j=1,m (2.14)
Пусть (=min{(j;(j>0} (2.15)
Тогда из (2.13)-(2.15) следует, что t1=t0+(
То есть ( – это время, за которое агрегат может достичь ближайшей грани многогранника и прийти к смене состояния, а t1 – ближайший особый момент времени.
В момент t1 состояние рассматриваемого кусочно-линейного агрегата изменяется скачкообразно. Значение x(t1+0) является, вообще говоря, случайным. В момент t1 может выдаваться выходной сигнал y (см. оператор G). Содержание (и необходимость выдачи) y зависит от состояния x(t1). Подмножество Xy, введенное в общем определении агрегата, в данном случае совпадает с 13EMBED Equation.31415. Важно указать, что множество Y имеет структуру, аналогичную X, т.е. выходные сигналы y представляются как y=((, y(()), где ( – элемент некоторого счетного множества, y(() – вектор, принимающий значения из евклидова пространства размерностью, зависящей от (. При t>t1 движение агрегата вновь происходит в соответствии с формулами (2.10) и (2.11) до очередного особого момента t2, где вместо t0 теперь нужно понимать t1 и т.д.
Обратимся теперь к случаю поступления входного сигнала. Подчеркнем, что для КЛА множество U структурно аналогично множествам X и Y, т.е. u=((, u(()), где ( – элемент конечного или счетного множества, а u(() – вектор, размерность которого зависит от (. Следующее описание поведения КЛА можно рассматривать как раскрытие действия оператора V’.
Пусть в рассматриваемый момент t состояние агрегата x(t)=((, x(()) и пусть в этот момент поступает входной сигнал u=((, u(()). При этом состояние агрегата меняется скачкообразно. Значение x(t+0) является случайным, задаваемым распределением, которое, вообще говоря, зависит от x(t) и u. Будем считать, что в рассматриваемый момент может выдаваться выходной сигнал, содержание и необходимость выдачи которого зависит не только от состояния x(t) (и, быть может, x(t+0)), но и от содержания поступившего входного сигнала u. После рассматриваемого момента времени t движение агрегата происходит в соответствии с формулами (2.10) и (2.11) до следующего момента поступления входного сигнала или выхода вектора состояния на границу допустимых значений.
В виде КЛА могут быть формализованы многие реальные процессы: процессы передачи и обмена данными в сетях связи, системы массового обслуживания и материально-технического снабжения, процессы автомобильного движения на дорогах, разнообразные дискретные производственные процессы, вычислительные системы и т.д. При этом всюду основные состояния агрегата указывают на качественно различные состояния моделируемых объектов. Дополнительные же координаты характеризуют происходящие количественные изменения и часто носят сугубо вспомогательный характер, «вбирая» в себя необходимую информацию о предыстории модели. Следует отметить, что представление реальных систем в форме КЛА неоднозначно, поскольку неоднозначно могут быть выбраны состояния агрегатов. Выбор же состояний определяется как целями исследования, так и стремлением уменьшить размерность задачи. При этом всегда приходится идти на компромисс между точностью описания и полнотой получаемой информации с одной стороны и простотой модели – с другой.
Пример 1. Вероятностный автомат Мура. Этот автомат не имеет «жесткой» тактности, а изменяет свое состояние всякий раз, когда поступает входной сигнал. Пусть X – конечное множество внутренних состояний автомата, U – его входной (конечный) алфавит, Y – его выходной (конечный) алфавит. Для определенности будем считать, что
X={1,2,N}, U={1,2,..K}, Y={1,2,..M}.
Динамика автомата описывается следующим образом. Если в момент t состояние автомата x(t)=i и поступил входной сигнал, u(t)=k, то состояние x(t+0)=j выбирается случайно с вероятностью 13EMBED Equation.31415, 13EMBED Equation.31415(0, 13EMBED Equation.31415 при любом k, 1(k(K. Выходной сигнал y(Y, выдаваемый в этот момент, является однозначной функцией «нового» состояния j: y=m=Ф(j), где Ф - некоторая детерминированная функция с областью определения X и множеством значений Y. Представим этот автомат в виде кусочно-линейного агрегата.
Состояние агрегата x(t) ( Х, не имеет дополнительных координат и определяется только его номером (. Следовательно, ||(|| = 0 при всех ((Х. При таком выборе состояния КЛА не определяются многогранники X((), отпадают вопросы о движении внутри многогранника, выходе агрегата на границу.
Все движение рассматриваемого КЛА состоит из скачков состояния при поступлении входных сигналов, причем ввиду отсутствия вектора координат речь идет лишь о скачках основного состояния (. Ecли в момент времени t* состояние агрегата было x(t*) = i и поступил входной сигнал u = k, то в следующий момент времени состояние изменилось: x(t*+0)=j с вероятностью 13EMBED Equation.31415.
Т.о., требуется задать лишь распределение 13EMBED Equation.31415. Содержание же выходного сигнала, выдаваемого в момент поступления входного, определяется только функцией Ф: y(t*+0)=Ф(j). Вообще, если предположить, что ||(||=0, ||(||=0, ||(||=0 ( (, (, (, то легко видеть, что КЛА превращается в вероятностный автомат весьма общего вида.
Пример 2. Система массового обслуживания. Пусть на обслуживающий прибор поступает ординарный поток требований, причем i-е требование характеризуется параметром (i, который представляет собой предельно допустимое время ожидания i-м требованием начала обслуживания. Заявки, для которых реальное время ожидания превышает допустимое (i , получают отказ. Время обслуживания i-того требования равно (i, причем {(i} – последовательность независимых одинаково распределенных случайных величин. Искомыми являются вероятностные характеристики длины очереди и времени ожидания.
Представим данный процесс в виде КЛА. За состояние агрегата выберем вектор x=((, x(()), где ( - число требований, находящихся в системе в текущий момент времени, ||(|| = (, а x(() – вектор, координаты которого определяются только при (>0 и имеют следующий смысл: x1(() – время, оставшееся до окончания обслуживания требования, находящегося на приборе, а xi(() (10 совпадает с первым октантом евклидова пространства размерности (: X(()={x((): xi(()(0, i=1,2,.. (}
В качестве входного сигнала рассмотрим пару (1,(), где символ 1 просто указывает на факт поступления требования (и, таким образом, дискретная компонента ( принимает лишь одно значение 1), а величина ( равна допустимому времени ожидания поступающего требования (т.е. ||(||=1).
13 SHAPE \* MERGEFORMAT 1415
Рассмотрим динамику данного агрегата (рис.2.5). Между особыми моментами времени гладко изменяется лишь первая компонента вектора координат, остальные – неизменны. x1(t) = x1(t0) – (t-t0) (см. формулу (2.11), отсюда (1(()=-1). На рис. 2.5 – это движение от точки t до t*.
Пусть момент t* является моментом окончания обслуживания. Тогда с необходимостью x1(t*) = 0,  t* = x1(t0) +t0 (на рис. 2.5 – точка t*), а x(t*) = ((, 0, x2((),..x((()), где (>0.
Обслуженное требование должно покинуть систему, а его место занимает требование стоящее первым в очереди (если очередь не пуста). Следовательно, из состояния x(t*)  агрегат скачкообразно перейдет в состояние x(t*+0) = ((-1, x2((),..x((()), (на рис.2.5 – точка t*+0). При этом размерность вектора х уменьшилась на 1, а компонента x2(() заняла место компоненты x1((). Будем считать, что в рассматриваемый момент t* выходной сигнал не выдается. Далее происходит обслуживание очередной заявки, что выражается в непрерывном уменьшении компоненты x1((), а на рис. 2.5 отображается движением от точки t*+0 до точки t**.
Рассмотрим теперь случай поступления входного сигнала (1,() в момент t**. Пусть при этом состояние агрегата было x(t**)=((,x(()), где ((0. Поступление рассматриваемого входного сигнала означает приход в систему обслуживания требования, обладающего временем обслуживания ( и предельным временем ожидания (. (на рис. 2.5 – скачок агрегата из точки t** в точку t**+0). Рассмотрим два случая: (=0 и (>0. В первом из них требование поступает в пустую систему, а во втором – в занятую обслуживанием. При (=0 состояние x(t**+0) должно отражать тот факт, что поступившее требование сразу принято к обслуживанию и ему случайным образом назначено время обслуживания, т.е. (=0, x(t**)=(0), x(t**+0)=(1,(), где ( - случайная величина, имеющая заданное распределение. При (>0 состояние x(t**+0) должно отражать тот факт, что требование будет принято к обслуживанию тогда и только тогда, когда его предельное время ожидания ( превосходит реальное (т.е. (>13EMBED Equation.31415) и в случае, если оно принято, ему назначается случайное время обслуживания.
(>0
x(t**)= ((, x1(t**),,x((t**))


x(t**+0)= (19)



Будем считать, что в момент t** выдается входной сигнал, фиксирующий имеющуюся длину очереди, время ожидания и факт принятия или непринятия поступающего требования. В соответствии с этим предположим, что y=((,y), где (=((1,(2), (1 – число требований, находящихся в системе в момент t**, (2=0 или 1, если поступающее требование не принимается или принимается соответственно к обслуживанию, ||(||=(2, а компонента y равна времени ожидания принятым требованиям начала обслуживания.
В данном случае ( представляет собой вектор размерности 2 с целочисленными компонентами. Из сказанного следует, что имеют место зависимости:
(1=(

(2=


y=13EMBED Equation.31415 (координата определяется лишь при (2=1)
Выходной сигнал накапливается в системе сбора статистики. (1 используется для вычисления средней длины очереди, у – для вычисления среднего времени ожидания обслуживания.
2.5. Марковские цепи
Функционирование многих объектов представляет собой последовательность переходов их из одного состояния в другое (ЭВМ, каналы передачи информации).
Система называется системой с дискретными состояниями, если множество ее состояний конечно, а переходы из одного состояния в другое осуществляются скачком.
Последовательность состояний такой системы называется цепью.
Простейшей характеристикой случайного процесса, являющегося цепью, служит набор вероятностей состояний p1(t), p2(t),, pn(t), где pi(t) – вероятность того, что в момент t система находится в состоянии i. p1(t)+p2(t)++ pn(t)=1
Случайный процесс, протекающий в системе, называется марковским, если для любого момента времени t0 вероятность любого состояния системы в будущем (при t > t0) зависит только от ее состояния в настоящем (при t = t0) и не зависит от того, каким образом система пришла в это состояние.
Марков (старший) Андрей Андреевич (1856-1922) – русский математик, доктор физико-математических наук, профессор, академик Петербургской академии наук. Работал профессором Петербургского университета, опубликовал около 70 работ по теории чисел, теории приближенных функций, дифференциальных уравнений, теории вероятностей. В цикле работ, опубликованных в 1906-1912 годах, заложил основы одной из общих схем естественных процессов, которая была названа цепями Маркова. А.А. Марков пользовался большим авторитетом у студентов. Был материалистом и убежденным атеистом.
Переход системы из одного состояния в другое является в общем случае случайным событием. Последовательность смены состояний является потоком событий.
Поток событий является ординарным, если события происходят поодиночке (нет двух одновременных событий). Поток называется стационарным, если его вероятностные характеристики не изменяются во времени. Чаще всего применяются пуассоновские потоки событий, то есть имеющие неизменную интенсивность (плотность) – среднее число событий в единицу времени постоянна. ( = const.
Дискретные марковские цепи
Рассмотрим случайный марковский процесс с дискретными состояниями и дискретным временем. Такой процесс описывает систему S с конечным числом состояний, причем переходы возможны только в фиксированные моменты времени t1, t2,, tK. Процесс функционирования представим в виде цепи S0 (0) ( Si (1) ( Sj (2) ( ( Sm (K).
Случайная последовательность является дискретной марковской цепью, если для каждого шага вероятность перехода из любого состояния Si в любое состояние Sj (i, j = 1, 2, N) не зависит от того, как система пришла в состояние Si (принцип отсутствия последействия)
Каждому переходу системы из состояния Si в состояние Sj в момент времени tk соответствует переходная вероятность pij (tk). Это условная вероятность pij (tk) = P(Sj(tk) | Si(tk-1)). Очевидно, для каждого номера шага k возможные переходы образуют полную группу событий, т.е. 13 EMBED Equation.3 1415 13 EMBED Equation.3 1415. Следует обратить внимание, что13 EMBED Equation.3 1415.
Дискретная марковская цепь называется однородной, если переходные вероятности не зависят от номера шага: pij (tk) = pij.
Полным описанием однородной марковской цепи могут служить квадратная матрица переходных вероятностей PП:
PП=13 EMBED Equation.3 1415
и вектор вероятностей всех начальных состояний P(0)
P(0) = [pi(0)] = [p1(0), p2(0) pN(0)]
Переходные вероятности, соответствующие невозможным переходам, равны нулю, вероятности, расположенные на главной диагонали, соответствуют тому факту, что система не изменила своего состояния.
Для однородной марковской цепи найдем вектор вероятностей всех состояний для любого k-го шага. В соответствии с формулой полной вероятности вероятность i-го состояния на первом шаге равна:
13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415, или в матричной форме: P(1) = P(0)
·PП.
Аналогично, для второго шага: P(2) = P(1)
·PП= P(0)
·PП
·PП
Соответственно, для k-го шага: 13 EMBED Equation.3 1415
Обозначим элемент матрицы 13 EMBED Equation.3 1415 таким образом: pij(k).
Если возможен переход из состояния Si в состояние Sj за k шагов, то pij(k)>0. Если при этом возможен и обратный переход за произвольное число шагов, то состояния Si и Sj называются сообщающимися. Состояние Si называется возвратным, если вероятность того, что система, выйдя из этого состояния, вернется в него за конечное число шагов хотя бы один раз, равна единице, и невозвратным, если вероятность возврата за конечное число шагов меньше единицы.
Эргодические и поглощающие марковские цепи
Динамику переходов системы из состояния в состояние с течением времени можно представить в виде графа. Нередко это иерархический граф, дерево.
Сообщающиеся состояния, находящиеся на последней ступени, называются эргодическим подмножеством состояний. В частном случае, эргодическое множество может состоять из одного элемента, который называется поглощающим. Если все эргодические подмножества цепи состоят только из одного поглощающего состояния, такая цепь называется поглощающей.
Из поглощающего состояния нельзя перейти ни в какое другое. В матрице переходных вероятностей поглощающему состоянию соответствует строка, в которой все переходные вероятности pij=0, кроме одной (диагональной) pii=1.
Для эргодических цепей характерно то, что при достаточно большом шаге k наступает стационарный (установившийся) режим, при котором вероятности состояний pi(k) практически не изменяются с течением времени, т.е. 13 EMBED Equation.3 1415. Вектор PС = [pci] = [pc1, pc2, , pcN] называется вектором стационарных вероятностей. До наступления стационарного режима система находится в переходном режиме. Переходный режим заканчивается, когда ||PC  P(k)||<(, где ( - сколь угодно малая положительная величина. Каждая компонента pci вектора стационарных вероятностей характеризует среднюю долю времени, в течение которого система находится в состоянии Si. Если все состояния цепи являются сообщающимися, то вся цепь является эргодической. В такой системе из любого состояния можно попасть в любое за конечное число шагов, в матрице переходных вероятностей нет нулевых элементов, а граф системы является сильно связанным.
13 SHAPE \* MERGEFORMAT 1415
Для определения стационарных вероятностей pci нахождения системы в состоянии Si нужно составить систему N линейных алгебраических уравнений с N неизвестными:
13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415, причем искомые вероятности удовлетворяют условию нормировки 13 EMBED Equation.3 1415
Для системы на рисунке 2.6 выполняется:
pС1=pС2p21+pС3p31
pС2=pС1p12+pС4p42
pС3=pС1p13+pС4p43
pС4=pС2p24+pС3p34
Условие нормировки: pС1+pС2 +pС3+pС4=1
Эта система уравнений переопределена, есть линейно-зависимые уравнения.
На практике при исследовании эргодических марковских цепей часто ограничиваются рассмотрением стационарных режимов.
Поглощающие марковские цепи характеризуются тем, что эргодическое подмножество состоит из единственного элемента, который и является поглощающим.
13 SHAPE \* MERGEFORMAT 1415
В установившемся режиме, независимо от начального состояния, вероятность нахождения поглощающей марковской цепи в поглощающем состоянии близка к единице, а вероятности остальных состояний близки к нулю. Для примера на рисунке pС1= pС2 = pС3= 0, pС4=1. В связи с этим для исследования интересен только переходный режим.
Пример. Требуется построить математическую модель и определить основные характеристики системы обработки информации, содержащей канал передачи информации К, буфер Б, специализированное вычислительное устройство В. На вход системы поступает информация, генерируемая источником входной информации И.






Рис.2.8. Пример системы обработки информации.
Схема работы вычислительной системы следующая. Источник И выдает один пакет сразу, как только освобождается канал К. Канал К передает пакет в течение двух тактов. В канале может находиться только один пакет. Если буфер занят, канал хранит пакет, но блокируется по входу. Буфер Б может хранить от 0 до N пакетов. Если буфер занят полностью, он не принимает новый пакет. Буфер выдает пакет вычислителю В сразу, как только вычислитель освобождается и тут же может принять новый пакет. Вычислитель В обрабатывает пакет в течение одного такта и выводит его из системы. С вероятностью ( происходит сбой, и обработка пакета повторяется.
Введем множество состояний.
Канал К может находиться в одном из трех состояний:
k=1 – пакет принят и находится в начале передачи (передастся через 2 такта);
k=2 – пакет находится в середине передачи (передастся через 1 такт);
k=0 – передача пакета завершена, но буфер занят и канал заблокирован.
Буфер Б может находиться в одном из N+1 состоянии:
n=0 – буфер свободен;
n=1, 2,, N – в буфере находятся 1, 2,, N пакетов.
Вычислитель В может находиться в одном из двух состояний:
i=0 – вычислитель свободен; i=1 – вычислитель занят.
Состояние системы S на каждом такте описывается вектором трех компонентов (k, n, i). ||S|| = 3
·(N+1)
·2, хотя некоторые состояния являются невозможными.
Построим граф марковской цепи и определим переходные вероятности (рис.2.9).
Начнем с состояния (0,N,1) – вычислитель занят, буфер занят, канал заблокирован и содержит один пакет, готовый к передаче в буфер. Из этого состояния возможны два перехода:













Рис.2.9. Граф марковской цепи, описывающей работу вычислительной системы

Состояние (0,N,1) –
с вероятностью ( произойдет сбой и произойдет возврат в то же состояние (на рис. 2.9 этому случаю соответствует дуга)
с вероятностью 1-( пакет будет обработан, В освободится и тут же будет занят пакетом из буфера (i=1), Б уменьшится и тут же будет вновь заполнен пакетом из К (n=N), канал освободится и тут же получит новый пакет, который будет находиться в начале передачи (k=1). То есть произойдет переход в новое состояние (1,N,1).
Состояние (1,N,1) –
с вероятностью ( произойдет сбой, В по-прежнему будет занят (i=1), Б по-прежнему будет заполнен (n=N), пакет по каналу перейдет на следующую стадию (k=2). Новое состояние (2,N,1).
с вероятностью 1-( пакет будет обработан, В освободится и тут же будет занят пакетом из буфера (i=1), в Б станет на один пакет меньше (n=N-1), пакет по каналу перейдет на следующую стадию (k=2). Новое состояние (2,N-1,1).
Состояние (2,N,1) –
с вероятностью ( произойдет сбой, В по-прежнему будет занят (i=1), Б по-прежнему будет заполнен (n=N), пакет по каналу завершит передачу и канал заблокируется (k=0). Новое состояние (0,N,1).
с вероятностью 1-( пакет будет обработан, В освободится и тут же будет занят пакетом из буфера (i=1), Б уменьшится и тут же будет вновь заполнен пакетом из К (n=N), канал освободится и тут же получит новый пакет, который будет находиться в начале передачи (k=1). Новое состояние (1,N,1).
Состояние (2,N-1,1) –
с вероятностью ( произойдет сбой, В по-прежнему будет занят (i=1), в Б поступит новый пакет (n=N), канал освободится и тут же получит новый пакет, который будет находиться в начале передачи (k=1). Новое состояние (1,N,1).
с вероятностью 1-( пакет будет обработан, В освободится и тут же будет занят пакетом из буфера (i=1), Б уменьшится и тут же будет вновь заполнен пакетом из К (n=N-1), канал освободится и тут же получит новый пакет, который будет находиться в начале передачи (k=1). Новое состояние (1,N-1,1).
И так далее Перейдем к рассмотрению завершающих состояний.
Состояние (1,0,1) –
с вероятностью ( произойдет сбой, В по-прежнему будет занят (i=1), Б по-прежнему будет свободен (n=0), пакет по каналу перейдет на следующую стадию (k=2). Новое состояние (2,0,1).
с вероятностью 1-( пакет будет обработан, В освободится и поскольку в буфере пакетов нет, останется свободным (i=0), Б по-прежнему будет свободным (n=0), пакет по каналу перейдет на следующую стадию (k=2). Новое состояние (2,0,0).
Состояние (2,0,0) – сбой произойти не может, так как вычислитель не работает, пакет из канала завершит передачу и поступит в Б, а затем сразу в В (i=1, n=0), канал получит новый пакет из источника (k=1). Новое состояние (1,0,1) с вероятностью 1.
Матрица переходных вероятностей содержит 6
·(N+1) строк и столбцов. В матрице есть нулевые строки (для невозможных состояний). В каждой ненулевой строке один элемент равен (, другой 1-(, остальные – нулевые, так как из каждого состояния возможен переход только в два других состояния. В строке, соответствующей состоянию (2,0,0), один элемент равен 1, остальные – 0.
Составим систему уравнений для нахождения стационарных вероятностей.
p(0,N,1) = (
·p(0,N,1)+(
·p(2,N,1),
p(1,N,1) = (1-()
·p(0,N,1) + (1-()
·p(2,N,1) + (
·p(2,N-1,1),
p(2,N,1) = (
·p(1,N,1),

для n=N-1, N-2,, 1:
p(1,n,1) = (
·p(2,n-1,1) + (1-()
·p(2,n,1),
p(2,n,1) = (
·p(1,n,1) + (1-()
·p(1,n+1,1),

для n = 0:
p(2,0,1) = (
·p(1,0,1) + (1-()
·p (1,1,1),
p(1,0,1) = p(2,0,0) + (1-()
·p(2,0,1),
p(2,0,0) = (1-()
·p(1,0,1).
Кроме того, выполняется условие нормировки: 13 EMBED Equation.3 1415.
Обозначим p(2,0,0) = p; (/(1-() = (.
Из последнего уравнения: p(1,0,1) = 13 EMBED Equation.3 1415.
Из предпоследнего: 13 EMBED Equation.3 1415=13 EMBED Equation.3 1415=13 EMBED Equation.3 1415.
Из пред-предпоследнего: p(1,1,1)=13 EMBED Equation.3 1415=13 EMBED Equation.3 1415= 13 EMBED Equation.3 1415.
и так далее
p(1,n,1)=13 EMBED Equation.3 1415,
p(2,n,1)=13 EMBED Equation.3 1415.
Из первых трех уравнений вытекает:
из первого
13 EMBED Equation.3 1415;
из второго (с учетом, что p(2,N,1) = (
·p(1,N,1)):
p(1,N,1) = (1-() ( ( p(1,N,1) + (1-() ( p(1,N,1) + ( 13 EMBED Equation.3 1415
p(1,N,1) = p(1,N,1)((1-()((+(1-()() + (2N p
p(1,N,1) = 13 EMBED Equation.3 1415
p(2,N,1) = (2N+1 p
p(0,N,1) = (2N+2 p
из условия нормировки:
13 EMBED Equation.3 1415=13 EMBED Equation.3 1415
отсюда p = (13 EMBED Equation.3 1415)-1
Можно определить стационарные вероятностные характеристики системы. Например, вероятность того, что вычислитель простаивает p(2,0,0) = p, вероятность того, что канал простаивает p(0,N,1) = (2N+2 p.
Самостоятельно определите вероятность того, что в буфере находятся i пакетов; больше, чем i пакетов.
Непрерывные марковские цепи
На практике часто встречаются ситуации, когда система имеет конечное число дискретных состояний, а переходы между состояниями происходят в произвольные моменты времени. Например, отказы аппаратуры могут произойти в любой случайный момент времени.
Случайный процесс с непрерывным временем называется непрерывной марковской цепью, если поведение системы после произвольного момента времени t зависит только от состояния в этот момент времени и не зависит от истории процесса, предшествующей моменту t (соблюдается принцип отсутствия последействия).
Очень часто на практике интервалы времени между двумя переходами между состояниями системы подчинены показательному закону распределения 13 EMBED Equation.3 1415
Для непрерывной марковской цепи определим вероятности всех состояний системы для любого момента времени pi(t), i=1, 2,, N. Так как для любого момента t все состояния образуют полную группу событий, то
13 EMBED Equation.3 1415
Пусть система в момент времени t находится в состоянии Si. Рассмотрим элементарный промежуток времени (t, примыкающий к моменту времени t. Вероятность перехода из состояния Si в Sj за промежуток (t обозначим pij((t). Назовем плотностью вероятности перехода величину (ij, определяемую так:
13 EMBED Equation.3 1415,
то есть, при малых (t вероятность перехода pij((t) ( (ij(t) (t.
Если все плотности вероятностей перехода не зависят от t, то такой марковский процесс называется однородным: (ij(t) = (ij = const (и неоднородным – в противном случае). При этом для случая, когда интервал времени между переходами системы распределен по показательному закону, плотность вероятности перехода равна параметру ( показательного закона.
Пусть известны плотности вероятностей переходов (ij для всех пар состояний Si и Sj. Определим вероятности состояний системы pi(t). Для момента времени t+(t справедливо соотношение:
13 EMBED Equation.3 1415.
Из свойства матрицы переходных вероятностей (сумма вероятностей по строке равна 1) следует:
13 EMBED Equation.3 1415.
Подставив это в предыдущее выражение, получим:
13 EMBED Equation.3 1415,
13 EMBED Equation.3 1415.
Разделим обе части равенства на (t и устремим его к нулю, получаем:
13 EMBED Equation.3 1415.
Получили систему дифференциальных уравнений А.Н.Колмогорова:
13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415.
Интегрирование этой системы по времени позволит вычислить функции pi(t). При этом должно соблюдаться условие нормировки.

Колмогоров Андрей Николаевич (1903 - 1987). Великий русский ученый, один из крупнейших математиков XX столетия, член Национальной Академии наук США и американской Академии искусств и наук, член Нидерландской Королевской академии наук, Академии наук Финляндии, Академии наук Франции, Германской академии естествоиспытателей "Леопольдина", Международной академии истории наук и национальных академий Румынии, Венгрии и Польши, почетный член Королевского статистического общества Великобритании, Лондонского математического общества, Международного статистического института и Математического общества Индии, иностранный член Американского философского общества, Американского метеорологического общества, лауреат самых почетных научных премий: премии П.Л.Чебышева и Н.И.Лобачевского АН СССР, Международной премии фонда Больцано и Международной премии фонда Вольфа, а также государственной и Ленинской премии, награжденный 7-ю орденами Ленина, медалью "Золотая Звезда" Герой Социалистического труда академик Андрей Николаевич Колмогоров сам себя всегда называл "просто профессор Московского университета". На протяжении почти полувека А.Н.Колмогоров был общепризнанным лидером в теории вероятностей. Вместе с А.Я. Хинчиным и многими своими учениками он внес значительный вклад в развитие теории информации. К середине 50-х гг. именно А.Н.Колмогоров предложил наиболее общее определение количества информации в вероятностном смысле, а в дальнейшем развил и другой подход, так называемую алгоритмическую теорию информации, в котором под энтропией понималась сложность объекта, равная сложности алгоритма, описывающего объект.
В эргодических марковских цепях существует установившийся режим, при котором вероятности не меняются с течением времени. Следовательно, pi(t)=pi. Производные в системе дифференциальных уравнений Колмогорова при этом равны 0 и система Колмогорова становится сходной с системой для нахождения стационарных вероятностей для дискретных систем.
Вопросы и задачи к главе 2
1. На телеграфе установлен автоматизированный пункт передачи сообщений, работающий в режиме самообслуживания. Отправителю предоставляется рабочее место с микроЭВМ, позволяющей набрать нужный текст, отобразить его на экране и отредактировать. Набор текста начинается с клавиши «Ввод». Если операции ввода и редактирования отправителем выполнены, то по нажатию специальной клавиши «Завершение» текст запоминается и начинает обрабатываться машиной (распознается адрес, подсчитывается количество символов, определяется наличие признаков срочности телеграммы и т.п.). После завершения обработки на экране появляется символ готовности к передаче. Пользователь может нажать клавишу «Передача» или клавишу «Сброс». В первом случае состоится передача текста, во втором – текст будет удален из памяти ЭВМ и система придет в исходное состояние.
Дать теоретико-множественное описание системы.
Решение. Определим входы, выходы, состояния системы и связи между этими множествами. В качестве входов можно определить вектор из четырех булевских переменных: U = {u1, u2, u3, u4}, принимающих значение Истина, если нажаты клавиши «Ввод», «Завершение», «Передача» и «Сброс» соответственно. Состояниями в этом случае будут две булевских величины X = {х1, х2}. Первая принимает значение Истина, если аппарат находится в режиме редактирования текста, и Ложь, если аппарат находится в режиме простоя. Вторая принимает истинное значение, если аппарат занят, и ложное – в случае простоя аппарата. Выходом системы будет логическая величина у: происходит (Истина) или не происходит (Ложь) передача телеграммы. Функционирование такой системы можно описать таблицей истинности.
u1
u2
u3
u4
х1
х2
у

0
0
0
0
0
0
0

1
0
0
0
1
1
0

0
1
0
0
0
1
0

0
0
1
0
0
1
1

0
0
0
1
0
0
0

Эту же систему можно описать, используя функции алгебры логики: х1 = u1; х2 = u1(u2(u3; у = х2(u3.
2. «Министерский» телефонный аппарат имеет телефонную трубку, N кнопок для вызова абонентов, память на один телефонный номер, кнопку повторного вызова последнего набранного абонента и кнопку стирания номера абонента из памяти. Вызов абонента осуществляется при поднятой телефонной трубке нажатием одной из N клавиш, соответствующей требуемому абоненту. При соединении с абонентом его номер автоматически заносится в память аппарата.
Дать теоретико-множественное описание системы.
3. Игра в большой теннис. Вероятность выигрыша подачи игроком А – 0.6, вероятность выигрыша подачи игроком В – 0.4.
Описать один гейм матча в виде марковской цепи.
4. Укажите положительные и отрицательные стороны применения качественных и количественных методов описания систем.
5. Какие из подходов к описанию систем применены, по-вашему, в следующих случаях: принципиальная электрическая схема прибора; рецепт приготовления борща; уравнения, описывающие движение планет Солнечной системы; запись логической функции; схема плана боевой операции; нотация шахматной партии; нотная запись мелодии; организационная схема управления предприятием; медицинская карта - история болезни человека; конституция государства; блок-схема алгоритма.
6. Чем непрерывная марковская цепь отличается от дискретной?
7. Что значит «описать систему в виде цепи Маркова»?
8. Какую роль играют обратные связи в управлении системами?
9. Чем оптимальное управление отличается от программного управления?
10. Какие допущения вносятся при описании системы в виде кусочно-линейного агрегата?


 Пример взят из кн. Вероятностные методы в вычислительной технике/ А.В.Крайников, Б.А.Курдиков, А.Н.Лебедев и др. – М.: Высш. шк., 1986.
 Сюжет примера взят из кн.: Дегтярев Ю.И. Системный анализ и исследование операций. – М.: Высш. шк., 1996.









И.В.Иванов Теория информационных процессов и систем


Определение проблемы

Реализация

Оценивание

Формирование стратегии

Исследование связей

Назначение целей

Генерация вариантов

Определение критериев

Оценивание вариантов

Выбор варианта

Реализация выбранного варианта

Управление системой

Проверка и переоценка

Q

U

Y

Q

U

Q











Рис.2.3. Структурная схема системы управления

y’ u1 z1 u2

t’ t1 (1 t2
Рис.2.4. Пример наступления событий в агрегате


Q

ИМ


Y

Y’

(

Объект

A

U


Dy

Dq

Q’

УУ


Рис. 2.5. Изменение координат КЛА во времени при (=2.



((, x1(t**),,x((t**)), если ((13EMBED Equation.31415
((+1, x1(t**),,x((t**),(), если (>13EMBED Equation.31415

0, если ((13EMBED Equation.31415
1, в противном случае













Рис.2.7. Пример поглощающей цепи










·

k=1 k=2 k=0

В

Б (N)

И

К

0 N 1

1 N 1

1 N-1 1

1 n 1

1 1 1

1 0 1

2 0 0

2 N 1

2 N-1 1

2 n 1

2 1 1

2 0 1

1-(

(

1-(

(

1-(

(

1-(

(

1-(

(

(

(

1-(

(

1-(

(

1-(

(

1-(

1-(

1-(

1

(








рис. 2.2. Кибернетический подход к процессу управления


объект

Среда

субъект

Q

Среда


Рис.2.6. Пример эргодической марковской цепи



Root EntryEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation Native0Equation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativepEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation Native

Приложенные файлы

  • doc 363267
    Размер файла: 594 kB Загрузок: 0

Добавить комментарий