НОУ ІНТУЇТ | лекція | Типові математичні моделі

1. 2.1. Дискретні марковские процеси

Анотація: В лекції розглядаються елементи теорії марковських процесів та ряд аналітичних моделей, в основі яких лежить припущення про марковости протікають в модельованих об'єктах процесів.

У багатьох випадках модель може бути представлена ​​у вигляді конструкцій з математичних символів. У першій темі такі моделі ми назвали аналітичними, щоб відокремити від інших математичних моделей - імітаційних. З розвитком останніх область застосування аналітичних моделей скоротилася. Однак актуальність такого моделювання зберігається для систем, особливо тих, в яких протікають так звані процеси без післядії. Процеси без післядії знаходять місце при функціонуванні багатьох технічних систем. Вперше один з типів такого процесу ввів у науковий обіг і досліджував вітчизняний математик А. А. Марков, тому процеси без післядії і системи, в яких вони протікають, названі марковскими, а один з типів такого процесу названий ланцюгом Маркова. В даний час теорія марковських процесів розроблена широко і детально, в основному, завдяки вітчизняним ученим А. Я. Хинчин, Б. В. Гнеденко, А. Н. Колмогорова і іншим. Популярність цієї теорії полягає ще і в тому, що вона може бути застосована і до систем з післядією, які за допомогою деяких хитрощів можна трактувати як марковские.

У цій темі розглядаються елементи теорії марковських процесів та ряд аналітичних моделей, в основі яких лежить припущення про марковости протікають в модельованих об'єктах процесів. До таких, в першу чергу, відноситься широкий клас найрізноманітніших об'єктів, що мають загальну назву систем масового обслуговування (СМО). Для ряду стандартних структур СМО аналітичні моделі, що зв'язують показники ефективності СМО з характеристиками елементів СМО, наведені у відповідних довідниках. Тут же наводяться класифікація СМО і прийоми побудови графів станів СМО, що дозволяють будувати або застосовувати готові аналітичні моделі.

Зауважимо, що для ряду сучасних складних СМО аналітичне моделювання неприйнятно в силу недостатності адекватних математичних засобів. У цих випадках слід застосовувати імітаційне моделювання, яке детально розглядається в наступних темах.

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

2.1. Дискретні марковские процеси

Найбільш повне дослідження процесу функціонування систем виходить, якщо відомі явні математичні залежності, що зв'язують шукані показники з початковими умовами, параметрами і змінними досліджуваної системи. Для багатьох сучасних систем, які є об'єктами моделювання, такі математичні залежності відсутні або малопридатні, і слід застосовувати інше моделювання, як правило, імітаційне.

Однак є ряд конкретних математичних схем, перевірених практикою і які довели ефективність моделюванням. Метою вивчення даної теми є освоєння таких математичних моделей.

В інженерній практиці часто виникає завдання моделювання процесів випадкової зміни станів в досліджуваному об'єкті. В рамках нашої професії нас цікавлять дискретні стану. Наприклад, технічний стан об'єкта може характеризуватися дискретними станами: справний - несправний, завантажений - знаходиться в просте і т. П. Чисельність бойових засобів протиборчих сторін змінюються дискретно, черги об'єктів, які очікують обслуговування, і багато іншого.

Вид чергового стану може визначатися випадковим чином, зміна станів може відбуватися в випадкові або невипадкові моменти часу.

Великий клас випадкових процесів складають процеси без післядії, які в математиці називають марковскими процесами в честь Андрія Андрійовича Маркова - старшого (1856-1922), видатного російського математика, який розробив основи теорії таких процесів.

Сутність процесу без післядії зрозуміла з визначення.

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

Практично будь-який випадковий процес є марковским або може бути зведений до Марковський. В останньому випадку досить в поняття стану включити всю передісторію змін станів системи.

А. А. Марков має додаток до прізвища "старший" тому, що його син - теж Андрій Андрійович Марков - видатний математик, фахівець в області теорії алгоритмів і ін.

А. А. Марков - старший відомий також як дав розподіл усіх обгрунтування методу найменших квадратів, який призвів один з доказів граничної теореми теорії ймовірностей і багато іншого.

Подальший розвиток теорія марковських процесів отримала в роботах видатного вітчизняного математика Андрія Миколайовича Колмогорова.

Марковские процеси діляться на два класи:

• дискретні марковские процеси (марковские ланцюга);
• безперервні марковские процеси.

Дискретної марковської ланцюгом називається випадковий процес, при якому зміна дискретних станів відбувається в певні моменти часу.

Безперервним марковским процесом називається випадковий процес, при якому зміна дискретних станів відбувається в випадкові моменти часу.

Отже, моделювання на основі дискретних марковських процесів.

Розглянемо ситуацію, коли моделюється володіє наступними особливостями.

система має можливих станів: , , ..., . Взагалі кажучи, число станів може бути нескінченним. Однак модель, як правило, будується для кінцевого числа станів.

Зміна станів відбувається, будемо вважати, миттєво і в строго певні моменти часу Надалі будемо називати тимчасові точки кроками.

Відомі ймовірності переходу системи за один крок зі стану в стан .

Мета моделювання: визначити ймовірності станів системи після -го кроку.

Позначимо ці ймовірності (Не плутати з вірогідністю ).

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

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

значення зазвичай зводяться в матрицю перехідних ймовірностей:

значення можуть також вказуватися на графі станів системи. на Мал. 2.1 показаний розмічений граф для чотирьох станів системи. Зазвичай ймовірності переходів "в себе" - , і т. д. на графі станів годі й проставляти, так як їх значення доповнюють до 1 суму перехідних ймовірностей, зазначених на ребрах (стрілках), які виходять з даного стану.

Чи не вказуються також нульові ймовірності переходів. Наприклад, на Мал. 2.1 це ймовірності , та ін.

Математичною моделлю знаходження ймовірностей станів однорідної марковської ланцюга є рекуррентная залежність

де - ймовірність -го стану системи після -го кроку, ;

- ймовірність -го стану системи після -го кроку, ;

- число станів системи;

- перехідні ймовірності.

Мал.2.1.

Розмічений граф станів системи

Для неоднорідної марковської ланцюга ймовірності станів системи знаходяться за формулою:

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

Приклад 2.1. По групі з чотирьох об'єктів проводиться три послідовних пострілу. Знайти ймовірності станів групи об'єктів після третього пострілу.

Матриця перехідних ймовірностей має вигляд:

Розмічений граф станів наведено на Мал. 2.2 .

Розмічений граф станів чотирьох об'єктів

Перш ніж приступити до обчислень, необхідно відповісти на наступні питання.

1. Чи є даний процес ураження цілей марковским? Так, так як ступінь ураження об'єкта (зміна його стану) не залежить від того - коли і яким чином об'єкт був приведений в даний стан, а залежить тільки від його поточного стану.
2. Чи підходить розглянута задача під схему марковської ланцюга? Так, так як час являє собою дискретні відрізки - час між пострілами (кроки).
3. Процес однорідний або неоднорідний? Є підстави вважати, що процес однорідний, так як перехідні ймовірності не залежать від часу. Крім цього, ми вважаємо, що об'єкти - нерухомі і в часі обстрілу змінювати своє положення не можуть (що привело б до змін після кожного пострілу).
4. І, нарешті, треба правильно визначити початковий стан системи, так як від цього можуть істотно залежати результати моделювання. У нашому випадку цілком природно вважати початковим стан - всі об'єкти цілі.

Отже, є всі підстави для застосування раніше введеного рекуррентного вираження (2.1).

Рішення. Так як до першого пострілу всі об'єкти цілі, то .

Після першого пострілу все значення ймовірностей відповідають першому рядку матриці перехідних ймовірностей. Розрахуємо ймовірності інших станів.

Сформулюємо методику моделювання по схемі дискретних марковських процесів (марковских ланцюгів).

1. Зафіксувати досліджуване властивість системи.

   Визначення якості залежить від мети дослідження. Наприклад, якщо досліджується об'єкт з метою отримання характеристик надійності, то в якості властивості слід вибрати справність. Якщо досліджується завантаження системи, то - зайнятість. Якщо, як в прикладі 2.1, стану об'єктів, то - вражений або непоражен.

2. Визначити кінцеве число можливих станів системи і переконатися в правомірності моделювання по схемі дискретних марковських процесів.
3. Скласти і розмітити граф станів.
4. Визначити початковий стан.
5. За рекуррентной залежності (2.1) визначити шукані ймовірності.

В рамках викладеної методики моделювання вичерпної характеристикою поведінки системи є сукупність ймовірностей .

При неоднорідному марковском процесі перехідна ймовірність являє собою умовну ймовірність переходу

, Що залежить від - чергового тимчасового кроку. У цьому випадку повинні бути вказані більше однієї матриці значень (Для деяких кроків матриці можуть бути однаковими).

Наприклад, при нанесенні ударів по об'єктах, які можуть переміщатися (танкове угруповання, кораблі і т. П.), Останні будуть вживати заходів щодо розосередження коштів або іншого захисного маневру, аж до активної протидії нападникам. Очевидно, всі ці заходи приведуть до зменшення вражаючих можливостей боку, завдає удари, т. Е. До відповідної зміни перехідних ймовірностей. Процес стає неоднорідним.