Контрольні запитання

1. Якому типу приорітету відповідає розглянута модель СМО (відносному чи абсолютному).

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

Рекомендована література

1. Г. Вагнер. Основы исследования операций. Том 3, «Мир», М., 1973.

16. Лекція 16

Метод динаміки середніх

План лекції

1. Суть методу динаміки середніх.

2. Приклад вирішення задачі методом динаміки середніх.

1. Метод динаміки середніх

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

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

Відповідь позитивна – можна. Але не завжди. Іноді досить точно, іноді з деякими наближеннями.

Для демонстрації ідей цього методу розглянемо приклад.

Нехай існує складна система S, що складається з великої кількості N однорідних елементів, кожен з яких може змінювати свої стани.

Припустимо, що кожний елемент може бути у довільному з nможливих станів:

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

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

або

(1)

Ця величина є випадковою величиною функції часу.

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

(2)

(3)

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

Нехай ці інтенсивності нам відомі. Тоді чисельність кожного стану можна представити як суму випадкових величин, кожна з яких пов’язана з окремим елементом. Якщо цей елемент у момент часу tзнаходиться у стані , то вона дорівнює одиниці, а якщо ні, то нулю:

1 – i-й елемент у стані

(4)

0 – і-й елемент там не знаходиться

Загальна чисельність стану дорівнює сумі

або

(5)

Якщо інтенсивності переходів елементу із стану в стан нам відомі, то

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

,

(6)

;

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

(7)

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

Математичне очікування буде дорівнювати:

тобто вірогідність того, що окремий елемент буде знаходитись у стані .

Дисперсія

Якщо ці вирази для тау вирази (6), отримаємо:

(8)

(9)

Середньоквадратичне відхилення відповідно до (8) і (9) буде дорівнювати:

(10)

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

(11)

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

Якщо ми знаємо вірогідності станів одного елементу

як функцій часу, то нам відомі і середні чисельності станів

та їх дисперсії

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

Нехай система S складається з Nоднорідних елементів. Граф станів кожного елементу представлений як на малюнку:

В початковий момент t=0 усі елементи знаходяться у стані .

Запишемо рівняння Колмогорова:

(12)

Помножимо ліву та праву частини кожного з рівнянь (12) на N, та введемо N під знак кожної похідної у лівій частні:

(13)

Тепер зробимо заміну:

Можна тепер переписати рівняння (13) як:

(14)

Для кожного t середня чисельність станів відповідає умові:

Одне з рівнянь можна відкинути. Систему треба вирішувати при початкових умовах:

Припустимо, що ми про інтегрували систему рівнянь (14) та отримали 4 функції:

Тоді можна обчислити дисперсії станів. З урахуванням (9) та того, що отримаємо: