Марковские процессы

Аннотация

              Целью курсового проекта является создание автоматизированного метода решения Задачи Марковский процесс с дискретными состояниями и непрерывным временем. Уравнения Колмогорова для вероятностей состояний.

              Данный курсовой проект состоит из трёх частей:

—            Программы, написанной на языке Delphi 6.0;

—            Пояснительной записки, содержащей документацию и к её применению;

—            Графической части.

Введение

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

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

1. Постановка задачи

1.1. Формулировка условия задачи

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

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

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

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

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

Окончание ремонта (восстановления) этого элемента также может произойти в заранее не зафиксированный момент и т.д.

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

1.2. Определение целей моделирования, их приоритеты

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

Целью курсового проекта на тему “Марковский процесс с дискретными состояниями и непрерывным временем. Уравнения Колмогорова для вероятностей состояний” является реализация на компьютере специального алгоритма вывода системы уравнений методом Колмогорова.

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

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

Из исследования подмоделей следует, что модель – это некоторая система объектов или способов изображения описания.

1.3 Описание данных

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

       S1 – дискретное состояние

       S1, S2,…,Sn – ряд дискретных состояний

       i – порядковый номер состояния

       t – любой момент времени

       Pij – переходная вероятность

       λij – плотность вероятностей перехода

2. Предмодельный анализ

2.1. Анализ существующих аналогов и подсистем

К аналогичным системам можно отнести «Пуассоновские потоки событий и непрерывные Марковские цепи».

Рассмотрим некоторую физическую систему S с дискретными состояниями S1, S2,…, Sn, которая переходит из состояния в состояние под влиянием каких-то случайных событий, например, вызовы на телефонной станции, выходы из строя (отказы) элементов аппаратуры, выстрелы, направленные по цели и т.д.

Будем себе это представлять так, будто события, переводящие системы из состояния в состояние, представляют собой какие-то потоки событий (потоки вызовов, потоки отказов, потоки выстрелов и т.д.).

Пусть система S с графом состояний, в момент t находится в состоянии Si и может перейти из него в состояние Sj под влиянием какого-то пуассоновского потока событий с интенсивностью λij: как только появляется первое событие этого потока, система мгновенно переходит (перескакивает) из состояния Si в состояние Sj. Вероятность этого перехода за элементарный промежуток времени Δt (элемент вероятности перехода) равна λijΔt. Таким образом, плотность вероятности перехода λij в непрерывной цепи Маркова представляет собой не что иное, как интенсивность потока событий, переводящего систему по соответствующей стрелке.

2.2. Анализ технического обеспечения среды моделирования

Для разработки и функционирования программы составленной для решения задачи математического исследования, а именно Марковский процесс с дискретными состояниями и непрерывным временем. Уравнения Колмогорова для вероятностей состояний, необходима электронная вычислительная машина типа РС с такими техническими параметрами:

-Процессор

Intel Pentium I – 133 MHz

- Оперативная память

32 Mb

- Операционная система

WIN 98

- 350 Mb свободного места на диске

2.3-2.4. Анализ программного, математического обеспечения среды моделирования

В процессе выполнения курсового проекта необходимо разработать программное обеспечение на языке визуального программирования Delphi 6.0.

Delphi 6.0 отвечает требованиям

            Понятность.

            Универсальность.

            Поддержку математических модулей

            Практичность.

Язык программирования Delphi 6.0, был создан на основе языка программирования Pascal . Команды и операторы логически подобранны корректно, легко запоминаются и т.д. и т.п.

Delphi - это комбинация нескольких важнейших технологий:

       Высокопроизводительный компилятор в машинный код

       Объектно-ориентированная модель компонент

       Визуальное (а, следовательно, и скоростное) построение приложений из программных прототипов

       Масштабируемые средства для построения баз данных

Компилятор, встроенный в Delphi, обеспечивает высокую производительность, необходимую для построения приложений в архитектуре “клиент-сервер”.  Этот компилятор в настоящее время является самым быстрым в мире, его скорость компиляции составляет свыше 120 тысяч строк в минуту на компьютере 486DX33. Он предлагает легкость разработки и быстрое время проверки готового программного блока, характерного для языков четвертого поколения (4GL) и в то же время обеспечивает качество кода, характерного для компилятора 3GL.  Кроме того, Delphi обеспечивает быструю разработку без необходимости писать вставки на Си или ручного написания кода (хотя это возможно).

3. Анализ задачи и модели

3.1. Разработка структур данных             

i, j – переменные циклов

formul – переменная вывода результата формул на экран

х – переменная создания таблицы

3.2. Разработка входных и выходных спецификаций

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

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

=-λ12p1-λ13p1

= λ12p1+ λ32p3

= λ13p1- λ32p3

3.3. Проектирование структуры и состава модели

Этап проектирования модели является завершающим в общем цикле проектирования модели.

На этом этапе выполняется процесс внешнего проектирования модели, а также проектирование и кодирование логики модели.

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

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

4. Исследование модели

4.1. Выбор метода исследования модели, подмоделей

Пусть система S имеет четыре возможных состояния:

S1, S2, S3, S4.

Поставим себе задачу: найти одну из вероятностей состояний, на­пример, Pi(t). Это есть вероятность того, что в момент t система будет находиться в состоянии S1.

Придадим t малое приращение ∆t и найдем вероятность того, что в момент t + ∆t система будет находиться в состоянии S1.

Как это событие может произойти? Очевидно, двумя способами:

— в момент t система уже была в состоянии S1, а за время ∆t не вышла из этого состояния или

— в момент t система была с состоянии S3, а за время ∆t перешла из него в S1.

Вероятность первого варианта найдем как произведение вероят­ности P1(t) того, что в момент t система была в состоянии S1 на услов­ную вероятность того, что, будучи в состоянии S1 система за время ∆t не перейдет из него в S2. Эта условная вероятность (с точностью до бесконечно малых высших порядков) равна 1 — λ12∆t.

Аналогично, вероятность второго варианта равна вероятности то­го, что в момент t система была в состоянии S3, умноженной на услов­ную вероятность перехода за время ∆t в состояние S1: P3(t)λ31∆t.

Применяя правило сложения вероятностей, получим:

P1(t+λ12∆t) = P1 (t) (1 — λ12∆t) + P3(t)λ31∆t.

Раскроем скобки в правой части, перенесем Pi(t) в левую и разде­лим обе части равенства на ∆t; получим:

P1(t+λ12∆t) – P1(t)

------------------------   =  — λ12P1(t) + λ31P3(t).

∆t             

Теперь устремим ∆t к нулю и перейдем к пределу:

P1(t+λ12∆t) – P1(t)

Lim       ---------------------------   =  — λ12P1(t) + λ31P3(t).

       ∆t→0              ∆t             

Левая часть есть не что иное, как производная   функции

dP1(t)

-------   =   — λ12P1(t) + λ31P3(t).

  dt

Таким образом, выведено дифференциальное урав­нение, которому должна удовлетворять функция P1(t). Аналогич­ные дифференциальные уравнения могут быть выведены и для осталь­ных вероятностей состояния: P2(t), P3(t), P4(t).

4.2. Выбор или построение алгоритмов и их псевдоизображения

   Алгоритм  точное и понятное предписание исполнителю совершить последовательность действий, направленных на решение поставленной задачи за конечное число шагов.

   Алгоритм вычисления уравнения Колмогорова по матрице состояний

4.3. Сборка модели

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

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

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

   Таким образом пошаговый метод сборки модели был выбран интуитивно как наиболее оптимальный и лёгкий применительно к данному курсовому проекту.

   Создание программы происходило следующим образом:

-   был создан интерфейс программы

к интерфейсу были подключены все позднее созданные процедуры.

4.4.-4.5. Идентификация подмодели или модели. Формулировка критериев адекватности, чувствительности, устойчивости модели.

  Идентичность программы предоставленной математической модели соответствует первоначальной её постановке на 90%, так как невозможен прямой перевод формул на программный язык без их некоторой модификации. Во всяком случае, числовое решение задачи распределения ресурсов полностью идентично ответам задач, решённых «ручным» способом или предоставленным в книге, откуда и брались методы решения поставленной цели.

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

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

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

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

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

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

Основные количественные показатели надёжности:

1)            вероятность безотказной работы;

2)            вероятность отказа;

3)            частота (интенсивность) отказа системы;

4)            средняя наработка до отказа системы;

5)            среднее время восстановления;

6)            коэффициент готовности

5. Программирование

5.1. Выбор методов тестирования

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

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

–    статистический;

–    детерминированный;

–    стохастический;

–    в реальном времени.

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

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

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

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

   Наиболее эффективным является детерминированное тестирование. Оно основано на двух подходах:

1.                 Структурное тестирование

2.                 Функциональное тестирование

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

5.2.- 5.3. Кодирование на языке программирования. Комментирование программы

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

– следование (линейная);

– разветвление (не линейная);

– циклическая.

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

В созданном программном обеспечений было применено два модуля иследующие процедуры:

       TForm 1 – в этом модуле вводятся и обрабатываются данные описывающие непрерывную цепь Маркова.

o        procedure Edit1Change – процедура ограничений на ввод количества состояний.

o        procedure Button1Click – по переменной из процедуры  Edit1Change заполняет матрицу состояний первичными данными.

o        procedure Button2Click – по матрице состояний рассчитывает уравнения Колмогорова и вызывает модуль TForm 2.

       TForm 2 – в этом модуле выводятся данные на экран.

o        procedure Button1Click – процедура вызова модуля TForm 1 для повторного применения программы.

o        procedure Button2Click – процедура закрытия программы по окончанию всех работ.

6. Тестирование и отладка

6.1. Синтетическая отладка

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