Граничні теореми для керованих систем

Размещено на http://allbest.ru

Київський національний університет імені Тараса Шевченка

Автореферат

дисертації на здобуття наукового ступеня кандидата фізико-математичних наук

01.05.04 - системний аналіз і теорія оптимальних рішень

ГРАНИЧНІ ТЕОРЕМИ ДЛЯ КЕРОВАНИХ СИСТЕМ

Виконала Лисак Наталія Пилипівна

Київ - 2005

АНОТАЦІЯ

ЛИСАК Н.П. Граничні теореми для керованих систем. - Рукопис.

Дисертація на здобуття наукового ступеня кандидата фізико-математичних наук за спеціальністю 01.05.04 - системний аналіз i теорія оптимальних piшень. - Київський національний університет імені Тараса Шевченка, Київ, 2005.

Дисертаційна робота присвячена дослідженню та аналізу рідинних та нестандартних систем масового обслуговування. Основні результати роботи для систем першого типу стосуються встановлення умов існування стаціонарного режиму, знаходження в явному вигляді їх стаціонарних розподілів (або характеристичних функцій) та дослідження поведінки стаціонарних характеристик систем в умовах великого чи малого завантаження. Для системи M/G/1 з дисципліною обслуговування LRPT змістовні результати встановлено в умовах великого завантаження. Характер отриманих результатів принципово новий.

пуассонівський ланжевін керований

1. ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ

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

Рідинні системи (в англомовній літературі вживається термін “fluid queues”) змінили традиційне уявлення про природу вимог, що надходять до системи з метою отримання того чи іншого типу обслуговування: якщо раніше мав місце тільки дискретний характер змодельованих явищ та процесів, то в рідинних системах роль окремої вимоги відіграє деяка неперервна сутність, що називається рідиною. Таким чином, рідинна система ? це система входу-виходу, де вхідним потоком є рідина, яка надходить у накопичувач (буфер, обслуговуючий пристрій), та залишає його з деякими інтенсивностями (стохастичними або постійними). Рідинні моделі є важливим інструментом для аналізу експлуатаційних показників мереж високошвидкісної передачі даних та систем серійного виробництва, де обробляється велика кількість відносно малих завдань. Активно досліджуються рідинні моделі, що знайшли своє застосування в галузі телекомунікацій. Початок досліджень в цьому напрямку поклали роботи Anick, Mitra & Sondhi (1982), Kosten (1974) та Mitra (1988). Досить повне дослідження рідинних моделей з одним буфером провів Kulkarni (1997). Вивчення рідинних моделей із пріоритетами мотивується тим, що їх можна використовувати для аналізу ефективності ATM-комутаторів (ATM - asynchronous transfer mode - режим асинхронної передачі) і IP-маршрутизаторів (IP - internet protocol), що підтримують класи трафіка з різною якістю обслуговування. Використання пріоритету є ефективним засобом для контролю перевантаження в сучасних високошвидкісних інтегрованих мережах, таких як Internet. Наприклад, для гарантії гарної якості обслуговування провайдер має розрізняти й встановлювати пріоритети між різними потоками даних, такими як відео/звукові і стандартні. У зв'язку зі зростаючою важливістю й різноманітністю Internet-трафіка вивчення рідинних моделей є актуальною галуззю досліджень. Рідинні моделі також використовуються в транспортних системах для моделювання потоку транспортних засобів на вуличних перехрестях і в теорії гребель. В теорії масового обслуговування рідинні моделі використовуються при дослідженні систем, які обробляють певні об'єми роботи, що миттєво надходять до системи і залишають її з неперервною інтенсивністю.

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

Більшість робіт по дослідженню описаних вище систем присвячено знаходженню основних ймовірнісно-часових стаціонарних характеристик, таких як кількість рідини в буфері, тривалість перебування вимоги в системі, тривалість чекання початку обслуговування та ін. Математичний апарат, який розроблено в дисертаційній роботі "Граничні теореми для керованих систем", дозволяє формулювати теореми про поведінку основних стаціонарних характеристик керованих рідинних та нестандартних систем масового обслуговування при граничних значеннях параметрів систем (ці системи є керовані в тому розумінні, що характер їх функціонування визначається дисципліною обслуговування вимог). Крім того, розглянуті системи мають широкий спектр застосувань. Усе вищесказане свідчить про актуальність вибраного напрямку досліджень.

Зв'язок роботи з науковими програмами, планами, темами. Дисертаційна робота виконана відповідно до плану наукових досліджень кафедри дослідження операцій факультету кібернетики Київського національного університету імені Тараса Шевченка в межах науково-дослідної теми № 01БФ015-01 “Розвиток теорії і програмного забезпечення стохастичних та алгебраїчних систем із застосуванням в економіці, соціології, техніці та освіті”, № держреєстрації 0101U002173. Автор дисертаційної роботи брала участь у темі як співвиконавець окремих підрозділів.

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

Поставлена мета зумовлює розв'язування таких основних задач:

- аналіз характеру функціонування систем;

- встановлення умов існування стаціонарного режиму в системах;

- визначення розподілів стаціонарних характеристик систем;

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

В якості основних об'єктів дослідження вибрано три системи, які надалі будемо називати так: вертикальна система, горизонтальна система та система M/G/1 з дисципліною обслуговування LRPT. Вибір назв для систем пояснюється характером їх функціонування.

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

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

Якщо позначити через ,

,

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

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

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

Очевидно, об'єм незавершеної роботи в такій системі масового обслуговування буде задовольняти рівняння Ланжевіна:

,

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

Система M/G/1 з дисципліною обслуговування LRPT (longest remaining processing timе discipline) належить до класу нестандартних однолінійних систем масового обслуговування і характеризується такими особливостями:

- вхідний потік є найпростішим;

- в момент надходження кожної вимоги до системи стає відомою її довжина;

- в кожен момент часу обслуговується вимога з максимальною залишковою довжиною; якщо таких вимог , то усі вони обслуговуються одночасно зі швидкістю ;

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

В силу специфіки дисципліни обслуговування цю систему також можна віднести до рідинних систем масового обслуговування.

Предмет дослідження ? стаціонарні характеристики вертикальної системи, горизонтальної системи та системи M/G/1 з дисципліною обслуговування LRPT.

Методи дослідження ? методи теорії масового обслуговування, ймовірнісні методи.

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

Вперше було встановлено такі факти.

Отримано умови існування стаціонарного розподілу розв'язку рівняння Ланжевіна та досліджено його граничну поведінку при (при великому завантаженні) для вертикальної та горизонтальної систем.

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

Досліджено граничну поведінку при (при малому завантаженні) стаціонарного розподілу розв'язку рівняння Ланжевіна у загальному випадку, коли

, ,

- жорданова матриця, неособлива матриця.

Досліджено тривалість перебування вимоги в системі M/G/1 з дисципліною LRPT в умовах великого завантаження, зокрема, отримано граничне значення для перетворення Лапласа тривалості перебування вимоги в системі, знайдено щільність та міру Леві тривалості перебування вимоги в системі.

Практичне значення одержаних результатів. Результати дисертації мають як теоретичне, так і практичне значення. Розглянуті моделі систем природним чином виникають при дослідженні процесів в електричних мережах або в гідротехнічних спорудах, а також при вивченні процесів обробки інформації в інформаційних мережах та процесів масового обслуговування, чим обумовлюється практичне значення результатів. З іншого боку, деякі результати роботи можна використати при викладанні спеціальних курсів для студентів факультету кібернетики Київського національного університету імені Тараса Шевченка.

Особистий внесок здобувача. Усі основні результати дисертації отримано автором самостійно. У роботах, написаних у співавторстві з науковим керівником, дисертанту належать: в роботі [1] - дослідження середніх характеристик та твердження 2; в роботі [3] - усі допоміжні результати, теореми 2-6; в роботі [4] - усі леми, теореми 5.1, 5.2 та наслідки.

2. ОСНОВНИЙ ЗМІСТ ДИСЕРТАЦІЙНОЇ РОБОТИ

У вступі обґрунтовано актуальність роботи, сформульовано мету, задачі та об'єкт дослідження, відзначено наукову новизну одержаних результатів і висвітлено практичне значення результатів дисертації.

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

У другому розділі введено вертикальну систему, проаналізовано характер її функціонування, вказано умови існування стаціонарного режиму в системі та отримано ряд граничних тверджень для стаціонарного розподілу розв'язку рівняння Ланжевіна та для основних стаціонарних характеристик системи в умовах великого завантаження (великих інтенсивностей вхідного потоку).

У третьому розділі введено та проаналізовано горизонтальну систему, вказано умови існування стаціонарного режиму в системі та отримано ряд граничних тверджень для стаціонарного розподілу розв'язку рівняння Ланжевіна і для основних стаціонарних характеристик системи в умовах великого завантаження (при ).

У четвертому розділі досліджено граничну поведінку при стаціонарного розподілу розв'язку рівняння Ланжевіна, де - узагальнений пуассонівський процес із параметром та стрибками, - жорданова матриця, - неособлива матриця.

У п'ятому розділі введено систему M/G/1 з дисципліною обслуговування LRPT, проаналізовано характер її функціонування, досліджено тривалість перебування вимоги в системі та тривалість залишкового періоду зайнятості в умовах великого завантаження. Отримано граничне значення для перетворення Лапласа тривалості перебування вимоги в системі, щільність та міру Леві тривалості перебування вимоги в системі в умовах великого завантаження.

ВИСНОВКИ

Дисертаційна робота присвячена дослідженню та аналізу керованих рідинних та нестандартних систем масового обслуговування, а саме вертикальної системи, горизонтальної системи та системи M/G/1 з дисципліною LRPT, докладно описаних вище, для яких було встановлено ряд граничних теорем про поведінку основних стаціонарних характеристик систем в умовах великого та малого завантаження.

Основні результати дисертації:

Встановлено умови існування стаціонарного розподілу розв'язку рівняння Ланжевіна та досліджено його граничну поведінку в умовах великого завантаження для вертикальної та горизонтальної систем.

Отримано ряд граничних теорем в умовах великого завантаження для таких характеристик вертикальної системи:

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

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

- тривалість перебування вимоги у системі від моменту надходження її в чергу на -й пристрій до моменту повного виходу з системи;

- тривалість перебування вимоги на - му пристрої та в черзі на - му пристрої;

- тривалість обслуговування вимоги на - му пристрої

- в припущенні, що система знаходиться в стаціонарному режимі.

3. Встановлено ряд граничних теорем при для таких стаціонарних характеристик горизонтальної системи:

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

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

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

Досліджено тривалість перебування вимоги в системі M/G/1 з дисципліною обслуговування LRPT в умовах великого завантаження. Зокрема, отримано граничне значення для перетворення Лапласа тривалості перебування вимоги в системі; знайдено щільність та міру Леві тривалості перебування вимоги в системі.

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

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

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

СПИСОК ОПУБЛІКОВАНИХ ПРАЦЬ ЗА ТЕМОЮ ДИСЕРТАЦІЇ

1. Закусило О.К., Лисак Н.П. Система M/G/1 з дисципліною обслуговування найдовшої вимоги в умовах великого завантаження // Вісник Київського університету, сер. фізико-математичні науки. - 2001. - № 4. - С. 246-250.

2. Лисак Н.П. Граничні теореми для розв'язку рівняння Ланжевіна у двовимірному випадку // Вісник Київського університету, сер. фізико-математичні науки. - 2003. - № 2. - С. 155-160.

3. Закусило О.К., Лисак Н.П. Про деякий багатовимірний процес збереження // Теорія ймовірностей та математична статистика. - 2004. - № 71. - С. 72-81.

4. Закусило О.К., Лисак Н.П. Про одну систему масового обслуговування з послідовним обслуговуванням // Теорія ймовірностей та математична статистика. - 2005. - № 72. - С. 24-29.

5. Лисак Н.П. Граничні теореми для однієї керованої мережі // Вісник Київського університету, сер. фізико-математичні науки. - 2005. - № 3. - С. 328-332.

6. Лисак Н.П. Дослідження системи масового обслуговування в умовах великого завантаження // Abstracts of International Conference “Prediction and Decision Making under Uncertainties”. - Kyiv. - 2001. - P. 100-101.

7. Лисак Н.П. Деякі граничні теореми для розв'язку рівняння Ланжевіна // Abstracts of International Conference “Problems of decision making and control under uncertainties”. - Kyiv-Kaniv. - 2002. - P. 78-79.

8. Лисак Н.П. Про один багатовимірний процес збереження // Abstracts of International Conference “Problems of decision making under uncertainties”. - Alushta. - 2003. - P. 122-124.

9. Zakusylo O., Lysak N. Оn a queueing system with consecutive service // Abstracts of International Workshop “Prediction and decision making under uncertainties”. - Ternopil. - 2004. - P. 77-79.

10. Закусило О.К., Лисак Н.П. Граничні теореми для характеристик певних систем масового обслуговування // Thesis of conference reports “Dynamical system modelling and stability investigation”. - Кyiv. - 2005. - P. 184.

11. Закусило О.К., Лисак Н.П. Рідинні мережі обслуговування в умовах великого завантаження // Abstracts of International Conference “Modern problems and new trends in probability theory”. - Chernivtsi. - 2005. - P. 87.

12. Закусило О.К., Лисак Н.П. Дослідження характеристик деякої системи масового обслуговування з послідовним обслуговуванням в умовах великого завантаження // Abstracts of International Conference “Problems of decision making under uncertainties”. - Berdyansk. - 2005. - P. 182-183.

Размещено на Allbest.ru