РОЗДІЛ 2.
МАКСИМІЗАЦІЯ ПРИБУТКУ ТА МІНІМІЗАЦІЯ РИЗИКУ В МЕРЕЖАХ НАПІВМАРКОВСЬКОГО ТИПУ
2.1. Процес накопичення прибутку в мережі типу
Розглянемо стохастичну мережу, яка функціонує наступним чином.
На “r” вузлів іззовні надходить один загальний потік пакетів, який керується
напівмарковським процесом Це означає, що моменти надходження пакетів
співпадають з моментами змін станів x(t). Якщо у моменти процес x(t) переходить
у стан “i”, то пакет з номером “n” з імовірністю надходить для обробки у вузол
“j”, – прямокутна матриця розміром Через будемо позначати напівмарковську
матрицю процесу x(t), – матриця перехідних імовірностей вкладеного ланцюга
Маркова для x(t), – функція розподілу часу перебування у стані “i”.
Кожен з “r” вузлів представляє собою багатоканальну стохастичну систему. При
надходженні пакету у таку систему зразу починається його обробка. Розподіл часу
обробки залежить від номера вузла, через будемо позначати його функцію
розподілу. Після обробки у j-ому вузлі пакет з імовірністю надходить у вузол
“k” і з імовірністю залишає мережу, – матриця маршрутизації мережі. Додатковий
вузол з номером “r+1” інтерпретується як “вихід” з мережі. Надалі будемо
вважати, що , , що завжди виконується на практиці. Для спрощення аналітичних
викладок будемо також вважати, що , де . Ця умова не є істотною. За рахунок
ускладнення фазового простору x(t) можна побудувати напівмарковський процес,
для якого напівмарковська матриця задовольняє цій умові (див., наприклад, [79],
стор. 17).
Нехай – число пакетів у j-ому вузлі в момент часу
Тоді представляє собою багатовимірний процес обробки інформації в мережі типу
Через будемо позначати число пакетів у j-ому вузлі в момент часу t, якщо у
початковий момент мережа порожня, і момент надходження першого пакету в мережу
співпадає з моментом виходу з “i”.
Для векторів введемо генератриси
Траєкторія пакету від моменту надходження в мережу до моменту виходу з неї може
бути описана напівмарковським процесом y(t), який приймає значення у множині
станів і визначається напівмарковською матрицею
– дельта Кронекера.
Стан “r+1” для процесу y(t) є поглинаючим. Поглинання у “r+1” інтерпретується
як вихід пакету з мережі. Через будемо позначати перехідні імовірності
напівмарковського процесу y(t).
Зазначимо, що при вивченні процесу обробки пакетів у – мережі можна обмежитись
аналізом r-вимірних процесів , яким відповідають генератриси
На процесі обробки пакетів у – мережі визначимо адитивний функціонал де – число
пакетів, обробка яких завершилася в j-ому вузлі за час t при умові, що у
початковий момент мережа порожня і .
Нехай – генератриси векторів Для справедливий такий результат.
Теорема 2.1. Функції є єдиним розв’язком системи інтегральних рівнянь
(2.1)
(2.2)
де – перехідна матриця вкладеного ланцюга Маркова для напівмарковського процесу
x(t).
Доведення. Процес обробки пакетів у – мережі разом із введеними вище адитивними
функціоналами будемо моделювати гіллястим процесом Беллмана-Харріса
з типами частинок Кожна з частинок має випадкову тривалість життя з функцією
розподілу , причому
Генератриси , безпосередніх нащадків від однієї частинки типу дорівнюють
Зв’яжемо з напівмарковським процесом випадкові процеси , , індикаторного типу
де , представляє собою N-вимірний вектор, j-та компонента якого дорівнює 1, а
інші – 0, – перехідні імовірності процесу x(t).
Функції у моделі Беллмана-Харріса підібрані таким чином, що
де означає рівність за розподілом.
Відомо ([74], стор. 231), що генератриси
задовольняють системі інтегральних рівнянь
З останнього рівняння випливає, що Використовуючи цей факт і перепозичивши
,
приходимо до системи інтегральних рівнянь (2.1), (2.2). Теорему доведено.
Нехай
.
Тоді як наслідок теореми 2.1 будемо мати наступний результат.
Наслідок 2.1. Функції є єдиним розв’язком системи інтегральних рівнянь:
(2.3)
. (2.4)
Очевидно, що середній прибуток від роботи мережі на проміжку [0,t] виписується
через функції . Останній результат показує, що дослідження середнього прибутку
вимагає аналізу двох взаємопов’язаних систем інтегральних рівнянь типу
марковського відновлення.
2.2. Оптимальне керування вхідним потоком для
задачі максимізації прибутку
Головна мета цього підрозділу – виписати через параметри – мережі функціонал
для задачі максимізації прибутку та з’ясувати тип оптимізаційної задачі.
При умові, що існують границі , будемо позначати їх через Очевидно, що
залежать від параметрів – мережі: . У подальшому будемо вважати,що є заданими,
а вибір матриці H знаходиться у нашому розпорядженні. Таким чином .
Перейдемо до постановки оптимізаційної задачі.
Нехай – прибуток від обробки одного інформаційного пакету в j-ому вузлі. Тоді
важливе значення має наступна задача:
(2.5)
при умові
(2.6)
Розв’язок задачі (2.5) – (2.6) представляє собою таке управління вхідним
потоком, яке максимізує середній прибуток від роботи всієї мережі.
Для того, щоб знайти залежність від матриці H, розглянемо систему рівнянь
марковського відновлення (2.4) і введемо перетворення Лапласа і
Лапласа – Стільтьєса для функцій
Справедливий такий результат.
Лема 2.1. Якщо спектральний радіус матриці маршрутизації P строго менший 1, то
,
де – одинична матриця.
Доведення. В термінах перетворень Лапласа систему (2.4) можна записати так
або, використовуючи матричні позначення, для A(s) маємо рівняння
(2.7)
де – діагональна матриця.
Розв’язком (2.7) буде