Прищепа Оксана Володимирівна Керовані системи з обмеженим числом повторів

brief description

Прищепа Оксана Володимирівна, старший викладач кафедри прикладної математики Націо­нального університету водного господарства та при­родокористування: «Керовані системи з обмеженим числом повторів» (01.05.04 - системний аналіз і теорія оптимальних рішень). Спецрада Д 26.001.35 у Київському національному університеті імені Тараса Шевченка

Київський національний університет імені Тараса Шевченка
Міністерство освіти і науки України
Київський національний університет імені Тараса Шевченка
Міністерство освіти і науки України
Кваліфікаційна наукова
праця на правах рукопису
ПРИЩЕПА ОКСАНА ВОЛОДИМИРІВНА
УДК 519.21
ДИСЕРТАЦІЯ
КЕРОВАНІ СИСТЕМИ З ОБМЕЖЕНИМ ЧИСЛОМ ПОВТОРІВ
01.05.04 – cистемний аналіз і теорія оптимальних рішень
Подається на здобуття наукового ступеня кандидата фізико-математичних
наук
Дисертація містить результати власних досліджень. Використання ідей,
результатів і текстів інших авторів мають посилання на відповідне джерело
________________ О.В. Прищепа
Науковий керівник Лебєдєв Євген Олександрович,
доктор фізико-математичних наук, професор
Київ – 2017

ЗМІСТ
ВСТУП................................................................................................................... 18
РОЗДІЛ 1. ОГЛЯД................................................................................................ 25
1.1. Стохастичні системи з повторними викликами .................................... 26
1.2. Модифікації систем з повторними викликами...................................... 34
1.3. Оптимізаційні задачі для систем з повторними викликами................. 37
Висновки до першого розділу .......................................................................... 43
РОЗДІЛ 2. ПОРОГОВІ СТРАТЕГІЇ КЕРУВАНННЯ СИСТЕМАМИ З
ОДНІЄЮ ПОВТОРНОЮ СПРОБОЮ ................................................................ 44
2.1. Математична модель .................................................................................. 46
2.2. Дослідження стаціонарного режиму системи типу
M / M /1/
з
однією повторною спробою.............................................................................. 53
2.3. Дослідження стаціонарного режиму системи типу
M / M / 2/
з
однією повторною спробою.............................................................................. 61
2.4. Дослідження стаціонарного режиму системи типу
M / M / c /
з
однією повторною спробою.............................................................................. 65
2.5. Вибір оптимальної стратегії керування ................................................. 71
2.6. Приклади ................................................................................................... 75
Висновки до другого розділу............................................................................ 78
РОЗДІЛ 3. ГІСТЕРЕЗИСНІ СТРАТЕГІЇ КЕРУВАННЯ СИСТЕМАМИ З
ОДНІЄЮ ПОВТОРНОЮ СПРОБОЮ ................................................................ 79
3.1. Керування при гістерезисній стратегії ................................................... 80
3.2. Дослідження стаціонарного режиму систем типу
M / M /1/
з однією
спробою при гістерезисній стратегії керування ............................................. 86
3.3. Дослідження стаціонарного режиму системи типу
M / M / c /
з
однією повторною спробою при гістерезисній стратегії керування ............ 91
3.4. Оптимальний вибір параметрів при гістерезисній стратегії
керування.......................................................................................................... 102
3.5. Приклади ................................................................................................. 104
17
Висновки до третього розділу ........................................................................ 107
РОЗДІЛ 4 РЕКУРЕНТНІ ОБЧИСЛЮВАЛЬНІ АЛГОРИТМИ ДЛЯ СИСТЕМ
З ОБМЕЖЕНИМ ЧИСЛОМ ПОВТОРІВ.......................................................... 109
4.1. Рекурентний обчислювальний алгоритми для стаціонарних
ймовірностей систем з однією спробою повтору......................................... 111
4.2. Рекурентний алгоритм знаходження стаціонарних ймовірностей для
систем з обмеженим числом повторних спроб............................................. 115
4.3. Порогові стратегії керування ................................................................ 129
4.4. Приклади ................................................................................................. 132
Висновки до четвертого розділу .................................................................... 135
ВИСНОВКИ.................................................................................................... 136
СПИСОК ВИКОРИСТАНИХ ДЖЕРЕЛ ...................................................... 138
ДОДАТКИ........................................................................................................... 153
Додаток A......................................................................................................... 153
Додаток Б ......................................................................................................... 158
Додаток В......................................................................................................... 159
18
ВСТУП
В даній роботі представлено дослідження одного класу стохастичних
моделей – систем масового обслуговування з повторними викликами, які
мають широку сферу застосування. Зокрема, це є комп’ютерні мережі
(локальні та глобальні), системи керування посадкою повітряних суден,
системи мобільного зв’язку та інші. Принцип роботи даних систем є
наступний. Ззовні до системи надходять вимоги отримати обслуговування.
Якщо у момент надходження є хоча б один вільний прилад, вимога відразу
починає обслуговуватися і після цього залишає систему. Якщо всі прилади
зайняті, вимога утворює так зване джерело повторних викликів. Це означає,
що через деякий час повторюється спроба зайняти вільний прилад та
отримати обслуговування. Класичні моделі теорії масового обслуговування
не беруть до уваги можливість повторного звернення вимог до системи та не
можуть використовуватися для розв’язку практично важливих задач. Саме
тому є досить актуальним питання дослідження систем з повторними
викликами.
Ще в 50-х роках минулого століття з’явились перші роботи присвячені
системам з повторними викликами. Використання таких систем для
ефективного моделювання роботи телефонних мереж показали Л. Костен
[49], Р. Вілкіксон [94], Дж.В. Коен [25]. Велика кількість інших дослідників
займалася дослідженням систем з повторними викликами, в результаті чого
з’явилося чимало робіт, що присвячені даній тематиці. Серед них
заслуговують на увагу роботи, в яких проводиться порівняльний аналіз даних
систем із класичними моделями, та визначаються переваги систем з
повторами, наприклад [6]. Особливе значення мають монографії Г. І. Фаліна,
Дж. Г. Темплетона [34], Є. Р. Арталєго та А. Гомеса-Корала [7], в яких
досліджено базові моделі систем з повторними викликами. В Україні суттєві
результати для систем з повторними викликами отримали І.М. Коваленко,
19
О.В. Коба [106], [108], [112], [113], В.В. Анісімов [3], [4], Є.О. Лебєдєв [55],
[116], [119], [141] та їх учні.
Зазвичай при дослідженні систем з повторними викликами вважається,
що кожна з вимог може повторно звертатися до системи до тих пір, поки не
отримає обслуговування. Це є лише наближенням до реальних ситуацій, тому
що число повторних звернень до системи часто буває обмеженим.
Дослідження систем з обмеженим числом повторних спроб отримати
обслуговування, що включає пошук умов існування стаціонарного режиму і
побудову алгоритмів підрахунку стаціонарного розподілу, є досить
актуальним на даний час, зокрема, з точки зору їх оптимізації. Особливе
практичне значення мають задачі оптимального вибору інтенсивності
вхідного потоку. У процесі оптимального вибору стратегії керування, як
правило, обмежуються класом порогових або гістерезисних стратегій. При
керуванні інтенсивністю вхідного потоку це означає відповідну залежність
інтенсивності від кількості джерел повторних викликів. Такі модифікації
математичної моделі з повторними викликами ще більш ускладнюють процес
дослідження.
Зв'язок роботи з науковими програмами, планами, темами.
Дисертаційна робота виконувалась відповідно до плану наукових досліджень
кафедри прикладної статистики факультету комп’ютерних наук та
кібернетики Київського національного університету імені Тараса Шевченка в
рамках науково-дослідної теми № 08ДФ015-05 "Розробка математичних
методів дослідження та оптимізації марковських систем з повторними
викликами та керованими локальними характеристиками" (№ держреєстрації
0108U007058), теми № 07ДФ015-09 "Аналіз та оптимізація стохастичних
систем з повторними викликами" (№ держреєстрації 0107U010798), теми
№ 16КФ015-03 "Розвиток теорії стохастичних систем мережевої структури,
методів оптимального вибору керуючих параметрів та інтернет технологій
для впровадження результатів в освіту" (№ держреєстрації: 0116U007787),
20
№ 16БФ015-02 "Розробка нових математичних методів системного аналізу і
теорії оптимальних рішень та їх застосування” (№ держреєстрації:
0116U002529).
Мета і задачі дослідження. Основною метою даного дисертаційного
дослідження є аналіз ланцюгів Маркова, що моделюють процес
обслуговування у системах з обмеженим числом повторних спроб та
керованим вхідним потоком при різних стратегіях перемикання
інтенсивності вхідного потоку.
Відповідно до сформульованої мети дослідження виникають наступні
задачі:
‒ дослідження умов існування стаціонарного режиму для процесу
обслуговування, що описує функціонування системи з обмеженим числом
повторних спроб;
‒ пошук явних формул для стаціонарного розподілу двовимірного ланцюга
Маркова, що описує процес обслуговування у системі з однією спробою
повтору зі сталою та змінною інтенсивністю вхідного потоку, керованою
пороговогою стратегією ;
‒ пошук явного подання стаціонарних ймовірностей тривимірного ланцюга
Маркова, що описує процес обслуговування у системі з однією спробою
повтору та керованим у класі гістерезисних стратегій вхідним потоком;
‒ побудова рекурентних обчислювальних алгоритмів знаходження
стаціонарних ймовірностей для систем з обмеженим числом повторних
спроб;
‒ постановка та розв’язок задач багатокритеріальної оптимізації
функціонування систем з обмеженим числом повторних спроб;
‒ побудова функціоналів якості в явному вигляді через стаціонарні
ймовірності.
Об’єкт дослідження – системи з обмеженим числом повторних спроб
та керованим вхідним потоком.
21
Предметом дослідження є аналітичні та обчислювальні методи
дослідження функціонування систем з обмеженим числом повторів та
керованим вхідним потоком.
Методи дослідження. В роботі використовуються методи теорії
ймовірностей, теорії масового обслуговування, марковських процесів,
системного аналізу.
Наукова новизна отриманих результатів. Всі основні результати
дисертаційної роботи є новими. Вони математично обґрунтовані й порівняні
з відомими результатами у цій галузі, а також повністю викладені у наукових
публікаціях автора. В дисертації отримані такі результати:
вперше
– встановлено умови існування стаціонарного режиму процесу
обслуговування для системи з обмеженим числом повторних спроб;
– знайдено явні векторно-матричні подання стаціонарних ймовірностей
двовимірного ланцюга Маркова, що моделює роботу системи з однією
спробою повтору;
– отримано явні формули в термінах гіпергеометричних функцій для
генератрис стаціонарних ймовірностей процесу обслуговування в
некерованих одноканальних системах;
– отримано з використанням ланцюгових дробів явні формули для
стаціонарних ймовірностей процесу обслуговування двоканальної
системи з однією спробою;
– отримано явні формули для стаціонарних ймовірностей тривимірного
процесу обслуговування для систем з однією спробою повтору у випадку
гістерезисних стратегій керування;
– сформульовано та розв’язано на основі алгоритму підрахунку відповідних
функціоналів якості задачу максимізації прибутку та мінімізації витрат;
набув подальшого розвитку
– рекурентний обчислювальний алгоритм знаходження стаціонарних
ймовірностей для процесу обслуговування систем з обмеженим числом
22
повторних спроб на основі моделей процесів квазі народження та
загибелі.
Практичне значення отриманих результатів. Дисертаційна робота
має як теоретичне, так і практичне значення, є суттєвим внеском у теорію
стохастичних систем з повторними викликами.
Отримані результати дисертаційного дослідження можуть знайти
застосування для розв’язання реальних практичних задач, що виникають,
зокрема, в локальних та глобальних комп’ютерних мережах,
телекомунікаційних мережах, при керуванні посадкою повітряних суден.
Визначення загального плану та напрямок досліджень, постановка
задач належить науковому керівнику – Є.О. Лебєдєву. Всі результати
дисертації, що виносяться на захист, належать автору.
Апробація результатів дисертації. Результати дисертації
доповідалися та обговорювалися на:
– Міжнародних конференціях "Problems of Decision Making Under
Uncertainties" (PDMU): Київ-Рівне (2008), Східниця (2009), Ялта (2011),
Мукачево (2012), Брно, Чеська Республіка (2012), Чеський Рудолец,
Чеська Республіка (2014), Мукачево (2014), Одеса (2015), ТбілісіБатумі, Грузія (2016), Брно, Чеська Республіка (2016), Мукачево (2017);
– XXXVIII Міжнародній конференції "Ogólnopolska Konferencja
Zastosowań Matematyki", Zakopane (2009);
– Міжнародній науковій конференції "Сучасні проблеми математичного
моделювання, прогнозування та оптимізації", Кам’янець-Подільський
(2014);
– XV Міжнародній науковій конференції імені академіка М.Кравчука,
Київ (2014);
– Міжнародній науково-практичній конференції "Інформаційні
технології та комп’ютерне моделювання", Івано-Франківськ (2016);
– Всеукраїнській науковій конференції "Сучасні проблеми прикладної
математики та інформатики”, Львів (2016).
23
Матеріали наукового дослідження також доповідались та отримали
позитивний відгук на наукових семінарах: кафедри системного аналізу та
теорії прийняття рішень і кафедри прикладної статистики факультету
комп’ютерних наук та кібернетики Київського національного університету
імені Тараса Шевченка; кафедри комп’ютерної математики та інформаційної
безпеки ДВНЗ "Київський національний економічний університет імені
Вадима Гетьмана".
Публікації. За результатами дисертаційного дослідження було
опубліковано 6 наукових статей, всі у фахових виданнях, які затверджено
МОН України, з них 3 статті опубліковано одноосібно, 1 – у науковому
фаховому виданні, включеному до міжнародних наукометричних баз, та 16
тез конференцій.
Робота складається зі вступу, чотирьох розділів, висновків, списку
використаних джерел та додатків. У вступі обґрунтовано актуальність
обраної теми, відображено зв’язок роботи з науковими програмами, планами
та темами, сформульовано мету та визначено основні задачі дослідження,
визначено наукову новизну роботи і практичне значення отриманих
результатів. Наведено особистий внесок здобувача, відомості щодо апробації
основних результатів роботи та публікації за темою дисертації.
У першому розділі наведено огляд основних стохастичних систем з
повторними викликами, проведено аналіз існуючих методів дослідження.
Показано необхідність дослідження систем з обмеженим числом повторних
спроб (з нетерплячими вимогами) та необхідність розв’язання проблеми їх
оптимізації при різних стратегіях керування.
У другому розділі представлено математичну модель системи масового
обслуговування з однією спробою повтору, керованим та некерованим
вхідним потоком. Сформульовано багатокритеріальну задачу оптимізації для
системи у випадку, коли перемикання інтенсивності вхідного потоку
здійснюється відповідно до порогової стратегії керування. Для такої системи
24
запропоновані методи знаходження стаціонарних ймовірностей: у випадку
одноканальної системи побудовано явні формули, для двоканальних систем
побудовано формули з використанням ланцюгових дробів; у випадку більше
двох приладів отримано подання стаціонарних ймовірностей у векторноматричному вигляді. На основі стаціонарних ймовірностей виписані
функціонали якості багатокритеріальної задачі оптимізації. Також наведені
приклади розв’язку сформульованої оптимізаційної задачі.
У розділі 3 розглядається система масового обслуговування з однією
спробою повтору у випадку гістерезисних стратегій керування інтенсивністю
вхідного потоку. Знайдено умови існуванні стаціонарного режиму. У випадку
одноканальної системи побудовані явні формули для стаціонарних
ймовірностей. У випадку багатоканальних систем для знаходження
стаціонарних ймовірностей використано урізану модель системи.
Cтаціонарні ймовірності урізаної моделі подано у векторно-матричному
вигляді та показано, що вони наближують відповідні ймовірності вихідної
системи. В класі гістерезисних стратегій керування сформульовано
багатокритеріальну задачу оптимізації, запропоновано алгоритм підрахунку
функціоналів якості і розв’язання сформульованої оптимізаційної задачі.
В четвертому розділі розглядаються рекурентні обчислювальні
алгоритми для систем з обмеженим числом повторних спроб, що
моделюються процесами квазі народження та загибелі. Для цього
використовується відповідна модель системи з урізаним простором станів.
Запропоновано алгоритм підрахунку функціоналів якості, сформульовано та
розв’язано багатокритеріальну задачу оптимізації.
Структура та обсяг роботи. Дисертаційна робота складається зі вступу,
чотирьох розділів, висновків, списку використаних джерел (144
найменування на 15 сторінках) та трьох додатків (7 сторінок). Обсяг
дисертації становить 159 сторінок.

bibliography

ВИСНОВКИ
У дисертації отримано нові науково обґрунтовані результати для
стохастичних систем з обмеженим числом повторних спроб та керованим
вхідним потоком у класі порогових та гістерезисних стратегій керування.
Основні наукові результати дисертації:
вперше
‒ встановлено умови існування стаціонарного режиму процесу
обслуговування для систем з обмеженим числом повторних спроб;
‒ знайдено явні векторно-матричні подання стаціонарних ймовірностей
двовимірного ланцюга Маркова для системи з однією спробою
повтору;
‒ отримано явні формули в термінах гіпергеометричних функцій для
генератрис стаціонарних ймовірностей процесу обслуговування
некерованих одноканальних систем;
‒ з використанням ланцюгових дробів отримано явні формули для
стаціонарних ймовірностей процесу обслуговування двоканальної
системи з однією спробою повтору у випадку керованого вхідного
потоку;
‒ отримано явні формули для стаціонарних ймовірностей тривимірного
процесу обслуговування для систем з однією спробою повтору у
випадку гістерезисних стратегій керування;
‒ сформульовано та розв’язано задачі максимізації прибутку та
мінімізації витрат, що базуються на алгоритмах підрахунку
відповідних функціоналів якості;
набув подальшого розвитку
‒ рекурентний обчислювальний алгоритм знаходження стаціонарних
ймовірностей для процесу обслуговування систем з обмеженим числом
137
повторних спроб на основі моделей процесів квазі народження та
загибелі.
Результати дисертаційного дослідження можуть знайти застосування
для розв’язання реальних практичних задач, де виникає необхідність
враховувати явище повторних викликів.
Результати роботи впроваджено в навчальних процесах Київського
національного університету імені Тараса Шевченка та Національного
університету водного господарства та природокористування.