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

Abstract

В цій роботі розглядаються моделі циклічних мереж як частин деякої більшої системи. Матеріал спирається на результати досліджень авторів Р. К. Чорнея, Г. Дадуни та П. С. Кнопова, висвітлених у статті про керовані Марковські поля зі скінченним простором станів на графах (див. [1]). В розділі 1 подається основний теоретичний матеріал, де вводяться поняття керованого марковського поля над графом або керованого Марковського процесу із синхронними компонентами, що взаємодіють локально; ядер переходів - імовірнісних правил, що диктують зміну поведінки системи з часом; описується дві моделі. Циклічна мережа подається у вигляді скінченного неорієнтованого графа, в якому рухається фіксована кількість вимог. Вузли представляють пункти надання деякого сервісу, в кожному з яких може утворюватися черга. Переходи вимог до наступного (попереднього) вузла мають імовірнісний характер та можуть відбуватися синхронно по всій мережі. Довжина черги в кожному вузлі відслідковується багатокроковим процесом, керованим деякою стратегією. Метою роботи є побудова застосунку, що вирішуватиме основну задачу – пошук такої (оптимальної) стратегії, що мінімізує середні витрати мережі за одиницю часу. Для її вирішення застосовується ітеративний метод покращення стратегії ([1]). В розділі 2 наводиться опис реалізованих методів у програмі, а також її результати на різних вхідних даних для моделей, описаних у теоретичній частині роботи (вихідний код додається).