Методи стабілізації та розрахунку розподілів неоднорідних систем марковського типу

Показана можливість застосування методів стабілізації до задач розрахунку та оптимізації параметрів систем масового обслуговування. Внаслідок обробки статистичного матеріалу про прохідність точки в різний час доби були отримані значення інтенсивності вхідного потоку замовлень на постачання. З використанням запропонованого методу була визначена оптимальна інтенсивність обслуговування заявок на поставку товару в СМО, яка розглядається, для заданого рівня значущості витрат і проведений аналіз зміни загальносистемних витрат. Знайдено оптимальний обсяг обслуговування у системі постачання, яка розглядається, протягом дня, значення вектора , який визначає оптимальні обсяги обслуговування на кожному часовому проміжку. У задачі, що розглядається, додаткове уточнення оптимального плану обслуговування дало змогу на 17% зменшити коливання обсягів на послідовних кроках процесу. Застосування даного методу може бути корисним при визначенні оптимального режиму використання технічних засобів з урахуванням навантаження на канали обслуговування в різні моменти часу.

У додатку наведені акти впровадження результатів роботи.

ОСНОВНІ РЕЗУЛЬТАТИ ТА ВИСНОВКИ

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

Найважливіші наукові та практичні результати роботи:

1. Обґрунтовано доцільність застосування нового підходу до керування неоднорідними марковськими процесами, що базується на стабілізації розподілів цих процесів. Цей підхід є достатньо універсальнім в теоретичному аспекті та конструктивним з прикладної точки зору.

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

3. Для широкого класу марковських процесів отримані умови збіжності до стаціонарного розподілу та умови їх стабілізації. Встановлено, що за ослаблення деяких умов, що забезпечують точне фокусування, матиме місце стабілізація процесу, коли компоненти граничного вектора розподілу локалізуються в околі деяких фіксованих значень. Знайдено достатні умови фокусування розподілу неоднорідного дискретного напівмарковського процесу (або ланцюга Маркова із змінюваною тривалістю одиничного кроку).

4. Визначена множина початкових розподілів, для яких мають місце збіжності до стаціонарного розподілу неоднорідного ланцюга Маркова за скінченну кількість кроків. Поняття стабілізації поширене на неоднорідні системи, що мають так звану “властивість зберігання”, і отримані умови збіжності до наперед заданої точки простору станів за як завгодно малий час.

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

6. Уведено поняття перемішуючої матриці для ланцюга Маркова із змінною кількістю станів. Установлені характеристичні властивості перемішуючих матриць. Сформульовано й доведено умови сильної ергодичності для ланцюгів Маркова із змінною кількістю станів. Для марковських процесів із змінною кількістю станів зазначені умови існування граничного розподілу за виконання декотрих природних умов, що накладаються на послідовність інфінітезимальних матриць даного процесу.

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

8. Розроблено ефективну з точки зору мінімізації обчислювальних витрат модифікацію числових методів розв'язання систем диференціальних рівнянь (неявні методи Ейлера і трапецій) на випадок системи диференціальних рівнянь з виродженою матрицею та матрицею із сингулярними особливостями. Показано, що для ефективного розв'язання даної задачі застосовні методи, область абсолютної стійкості яких містить клин . Розглянуто модельні приклади систем з різними видами сингулярностей, знайдені їх числові розв'язки і показано, в яких випадках має місце точне фокусування розподілів. Виявлені особливості стабілізації ймовірностей станів під час впливу на процес розподілених у часі чинників різної природи (регулярних і випадкових). Показано, що у найкращий спосіб на стабілізацію впливають регулярні впливи, щільність яких згущується на момент стабілізації.

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

10. Проведено числовий аналіз розв'язків нескінченної системи диференціальних рівнянь Колмогорова для типових випадків поведінки коефіцієнтів інфінітезимальної матриці. Отримано умови стабілізації щільності ймовірності неоднорідного дифузійного марковського процесу за скінченний час.

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

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

1. Bondarenko M., Chetverikov G., Gerasin S. The application reduction methods in multymeaning stochastic structures // Теоретичний та науково-практичний журнал радіозв'язку, радіомовлення і телебачення "Праці УНДІРТ". ? 1996. ? № 1(5) ? C. 24?27.

2. Герасин С.Н. Управление параметрами марковского процесса с целью стабилизации его характеристик за конечное время // Теоретичний та науково-практичний журнал радіозв'язку, радіомовлення і телебачення "Праці УНДІРТ". ? 1997. ? № 2(10). ? С.71?74.

3. Герасин С.Н., Дикарев В.А., Числин Н.И. О числе степеней свободы стохастических матриц с фиксированными жордановыми нормальными формами // Автоматизированные системы управления и приборы автоматики. ? Харьков: ХТУРЕ, 1997. ? Вып.103. ? C. 34?40.

4. Герасин С.Н. Области локализации характеристических корней квазистохастических матриц // Проблемы бионики. ? Харьков: ХТУРЕ, 1998. ? Вып.49. ? С. 113?117.

5. Герасин С.Н. Неоднородные марковские системы с медленно меняющимися параметрами // Радиоэлектроника и информатика. ? 1998. ? № 1(02). ? С. 70?71.

6. Герасин С.Н., Дикарев В.А., Числин Н.И. Существование предельных вероятностей для конечных процессов Маркова с убывающими к нулю временными промежутками перехода // Доповіді НАН України. ? 1998. ? № 7. ? С. 15?19.

7. Бондаренко М.Ф., Герасин С.Н. Расчет предельного распределения неоднородных процессов Маркова, инфинитезимальные матрицы которых имеют точки фокусировки // Радиоэлектроника и информатика. - 1998. ? № 2(03). ? С. 80?81.

8. Герасин С.Н., Дикарев В.А., Родзинский А.А. Расщепление марковского процесса на несвязанные фрагменты с одновременной фокусировкой в каждом из них // Радиоэлектроника и информатика. ? 1998. ? № 3(04). ? С. 111?114.

9. Герасин С.Н. Взаимодействующие марковские процессы с доминирующими связями // Радиоэлектроника и информатика. ? 1998. ? № 4(05). ? C. 72?74.

10. Герасин С.Н., Лизгин В.А., Лобас А.Н. Моделирование процесса ?фокусировки распределений неоднородных марковских процессов // Вестник ХГПУ. ? Харьков: ХГПУ, 1999. ? Вып. 65. ? С. 72?77.

11. Герасин С.Н., Лизгин В.А. Нейронные структуры, обладающие свойством кратковременной памяти, как средство хранения информации // Радиоэлектроника и информатика.- 1999. - №4(09). - С.129-130.

12. Герасин С.Н. Алгоритм нахождения стационарного распределения слабо взаимодействующих систем // Теоретичний та науково-практичний журнал радіозв'язку, радіомовлення і телебачення "Праці УНДІРТ". ? 1999. ? № 2(18). ? С. 6?9.

13. Герасин С.Н. Приведение распределения неоднородной марковской системы к заданным значениям при помощи возмущения ее параметров // Радиоэлектроника, информатика, управление. ? 1999. ? № 2. ? С. 59?63.

14. Герасин С.Н., Лизгин В.А., Лобас А.Н. Метод редукции в задачах нахождения предельного распределения марковских процессов с бесконечным числом состояний // Радиоэлектроника и информатика. ? 2000. ? № 2(11). - С. 45?47.

15. Дикарев В.А., Герасин С.Н., Слипченко Н.И. Стабилизация вероятностей состояний марковского процесса при локальных возмущениях его параметров // Доповіді НАН України. ? 2000. ? № 8. ? С. 90?93.

16. Герасин С.Н. Условия стабилизации распределений марковских цепей с переменным числом состояний // Автоматизированные системы управления и приборы автоматики. ? Харьков: ХТУРЭ, 2000. ? Вып. 113. ? С. 52?60.

17. Герасин С.Н., Дикарев В.А., Слипченко Н.И. Управление неоднородным процессом диффузии с целью стабилизации его плотности распределения вероятностей // Доповіді НАН України. ? 2001. ? № 4. ? С. 74?76.

18. Герасин С. Н., Гибкина Н. В., Лизгин В.А. Стабилизация распределения неоднородной марковской системы при влиянии распределенных стабилизирующих факторов // Радиоэлектроника и информатика. - 2001. - № 1(14). - С. 71?75.

19. Герасин С.Н., Огиенко А.А., Слипченко Н.И. Анализ динамики поведения стохастической нейронной сети // Доповіді НАН України. ? 2001. ? № 9. ? С. 89?93.

20. Герасин С.Н. Стабилизация решений в задачах динамического распределения ресурсов // Доповіді НАН України. ? 2001. ? № 10. ? С. 73?78.

21. Герасин С.Н. Некоторые условия эргодичности распределений неоднородных полумарковских систем // Радиоэлектроника и информатика. ? 2002. ? № 4. ? С. 62?65.

22. Герасин С.Н., Паршин О.В. Оптимизация режимов дозирования лекарственных препаратов // Радиоэлектроника и информатика. ? 2002. ? № 3. ? С. 120?123.

23. Герасин С.Н., Огиенко А.А. Анализ дискретной марковской цепи, моделирующей стохастическую нейронную сеть // Искусственный интеллект. ? 2002. ? № 4. - С. 675?685.

24. Герасин С.Н., Дикарев В.А. Условия сходимости к предельному распределению в конечных неоднородных цепях Маркова за конечное время// Доповіді НАН України. - 2003. - № 11. - С. 57?60.

25. Герасин С.Н., Лобас А.Н. Достаточные условия стабилизации распределения марковского процесса при локальных возмущениях его фрагментов// Радиоэлектроника и информатика. - 2003. - № 2. - С. 61?65.

26. Гибкина Н.В., Герасин С.Н. Неоднородная марковская модель массопереноса в условиях ограничений // Математичне моделювання. - 2003. ? № 2(10). ? С. 7?10.

27. Герасин С.Н. Стабилизация распределений марковских цепей с переменным числом состояний за конечное время // Доповіді НАН України. - 2004. - №12. - С.59-63.

28. Герасин С.Н. Расчет вероятностей состояний при взаимодействии марковских процессов // Дифференциальные уравнения и прикладные задачи. - Тула: Тульский ун-т, 1995. ? С. 123?128.

29. Герасин С.Н. Условия сходимости к предельному распределению в неоднородных цепях Маркова за конечное время // Вісник Харківського національного університету. ? 2000. ? № 456, ч.2. ? С. 256?259.

30. Герасин С.Н. Условия слабой эргодичности неоднородных марковских систем // Теория и техника передачи, приема и обработки информации: Материалы 2-й Международной конференции (17-19 сентября). - Туапсе: ХТУРЭ 1996. ? Ч.2. - С. 313.

31. Герасин С.Н. Управление параметрами марковской системы с целью стабилизации ее характеристик за конечное время // Контроль i управлiння в технiчних системах: Матеріали 4-ї Міжнародної конференції (21-23 жовтня). - Вiнниця: Вінницький політехнічний ун-т, 1997. ? Т.1. ? С. 57?63.

32. Герасин С.Н. Алгоритм перехода к стационарному распределению за конечное время в дискретной неоднородной цепи Маркова // 6-я Международная конференция им. акад. М.Кравчука: Материалы конференции (13-15 травня). - К.: КПИ, 1997. ? С. 103.

33. Gerasin S. The conditions of transition to the beforehand given limit distribution nonhomogeneous Markov process // 22-nd European Meeting of Statisticians. - Vilnius, 1998. ? P. 216.

34. Герасин С. Н. The conditions of existence focusing points in non - homogeneous Markov process // Вычислительные методы. Проблемы и перспективы: Тезисы докладов международной конференции. - Гомель, Белоруссия. - 1998. - С. 151-153.

35. Герасин С. Н., Гибкина Н. В., Лизгин В.А. Приведение системы колмогоровского типа к заданному распределению // Аналитические методы анализа и дифференциальные уравнения: Тезисы докладов международной конференции (15-19 февраля). - Минск: Беларусь, 2001. ? С. 40.

35. Герасин С.Н., Дикарев В.А. Конкурирующие возмущения в задаче о фокусировке распределений марковских процессов // Математика. Экономика. Образование: Материалы 10-й Международной конференции (27 мая - 2 июня). - Ростов-на-Дону: РГУ, 2002. ? С. 151.

36. Герасин С.Н., Шляхов В.В. Условия сходимости к предельному распределению неоднородной марковской цепи за конечное время // Колмогоров и современная математика: Сборник докладов Международной конференции (16-21 июня). - М.: МГУ - 2003. - С. 625-626.

37. Герасин С.Н., Лобас А.Н. Стабилизация распределения неоднородной марковской системы под действием распределенных стабилизирующих факторов // Материалы 10-й международной конференции по автоматическому управлению “Автоматика-2003”, Севастополь. - 2003. - Т.1. - C. 31-32.

38. Герасин С.Н., Лобас А.Н. Марковские модели классификации ландшафтных комплексов по данным космической съемки // 10-я Международная конференция “Теория и техника передачи, приема и обработки информации”. - Харьков-Туапсе. - 2004. - С. 205-206.

АНОТАЦІЯ

Герасін С.М. Методи стабілізації та розрахунку розподілів неоднорідних систем марковського типу. - Рукопис.

Дисертація на здобуття наукового степеня доктора технічних наук за спеціальністю 01.05.02 - математичне моделювання та обчислювальні методи. - Харківський національний університет радіоелектроніки, Харків, 2006.

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

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

Ключові слова: неоднорідні марковські системи, методи стабілізації розподілів, методи фокусування розподілів, стрибкоподібні збурення, системи зі змінною кількістю станів, редукція систем.

АННОТАЦИЯ

Герасин С.Н. Методы стабилизации и расчета распределений неоднородных систем марковского типа. - Рукопись.

Диссертация на соискание ученой степени доктора технических наук по специальности 01.05.02 - математическое моделирование и вычислительные методы. - Харьковский национальный университет радиоэлектроники, Харьков, 2006.

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

Исследуются различные спектральные свойства стохастических и квазистохастических матриц. Дано полное описание множества стохастических и инфинитезимальных матриц с заданными спектральными характеристиками (в частности, набором собственных чисел и собственных и присоединенных векторов). Разработан комплекс программ для генерации стохастических матриц-функций с заданными спектральными характеристиками, предложенный программный комплекс позволяет, в частности, для любой заданной матрицы-функции построить ее модификации, множество которых представляет собой -сеть для всех матриц, достаточно близких к исходной. Найдено число степеней свободы матриц, строчные суммы которых равны единице. Предложена процедура генерации всех стохастических матриц-функций, подобных (в смысле линейного преобразования подобия) заданной стохастической матрице-функции. Дано описание множества на комплексной плоскости, которое содержит все собственные числа квазистохастических матриц.

В работе получены условия стабилизации для полумарковских систем с непрерывным временем, доказаны соответствующие теоремы о достаточности этих условий. Изучаются условия сходимости к предельному распределению для случая неоднородных цепей с дискретным временем. Показано, что существуют такие начальные распределения, начиная с которых марковская система за конечное число шагов переходит в стационарное состояние. Исследуются марковские процессы с континуальным множеством состояний, и для них приводятся условия стабилизации и фокусировки распределений. Рассмотрены системы колмогоровского типа, для которых также сформулированы и доказаны условия стабилизации решений.

В диссертации введены и исследованы марковские системы с переменным числом состояний. Для таких систем определено понятие согласованного класса распределения, который является аналогом предельного распределения для неоднородной цепи Маркова. Получены условия существования таких согласованных классов распределений, то есть решена задача стабилизации. Показано, что существуют такие начальные распределения, начиная с которых система с переменным числом состояний перейдет в “стационарный режим” за конечное время. На системы с переменным числом состояний распространено понятие сильной и слабой эргодичности, получены различные достаточные условия сильной и слабой эргодичности.

Предложены различные методы управления марковской системой с целью приведения ее распределения к заранее заданным значениям путем специально подобранных управляющих воздействий. Показано, что время достижения предельного распределения конечно и может быть сделано сколь угодно малым. Исследованы марковские системы, которые в некоторый момент времени распадаются на не взаимодействующие фрагменты, причем каждый из них стабилизируется. Приведены различные модельные примеры, иллюстрирующие процедуру стабилизации, предложены модификации вычислительных алгоритмов, необходимых для расчета систем дифференциальных уравнений с сингулярными особенностями. Приведены модельные примеры процессов, для которых имеет место стабилизация распределений в некоторой заданной окрестности. Установлена зависимость между точностью стабилизации и величиной воздействий. Качественно исследован вопрос о влиянии на стабилизацию начального момента времени.

Выявлены особенности стабилизации вероятностей состояний при воздействии на процесс распределенных во времени факторов различной природы (регулярных детерминированных и случайных). Показано, что наилучшим образом на стабилизацию влияют регулярные воздействия, плотность которых сгущается к моменту стабилизации.

Изучены марковские системы с бесконечным числом состояний. Для систем со счетным числом состояний обосновано применение метода редукции, при котором бесконечная система заменяется конечной, “близкой” к исходной в смысле близости ее параметров. Получены условия сходимости последовательности редуцированных распределений к стационарному распределению исходной бесконечной системы. Изучены процессы с континуальным множеством состояний (диффузионный процесс), для них найдены условия стабилизации плотности вероятности неоднородного диффузионного марковского процесса за конечное время. Это означает, что плотность распределения вероятностей процесса будет находиться в заданных границах, начиная с некоторого заранее заданного момента времени.

Показана возможность и целесообразность применения полученных результатов для решения конкретных практических задач из области моделирования систем массового обслуживания, экономики, медицины, радиотехники. Достоверность полученных результатов подтверждается экспериментальными исследованиями и результатами внедрений.

Ключевые слова: неоднородные марковские системы, методы стабилизации распределений, методы фокусировки распределений, скачкообразные возмущения, системы с переменным числом состояний, редукция систем.

ABSTRACT

Gerasin S.M. Stabilization and calculation methods of nonhomogeneous system distribution of markovian type.-Manuscript.

The thesis for a doctor of technical sciences on the specialty 01.05.02 - mathematical modeling and computing methods. - Kharkiv national university of radioelectronics, Kharkiv, 2006.

An important scientific and technical problem of constructional stabilization theory development of nonhomogeneous systems distribution| of a markovian type has been formulated and solved in the thesisthesis.

The complex of methods of the exact and approximate distribution| stabilization, which are conceivably used on model problems as well as real systems has been suggested. Complete description of a set stochastic and infinitesimal matrices under given spectral characteristics ones given. Description of a set on a complex plane, which| contains all eigenvalue of quasistochastic matrices is presented. Coincidence condition to the stationary distribution and their stabilization condition have been obtained for Markov processes. The sufficient conditions of focusing nonhomogeneous discrete semimarkovian process distribution have been found. A set of initial| distributions for which coincidences to the stationary distribution of the nonhomogeneous Markov chain for |final number of steps takes place, has been determined. For Markov processes with a variable number of the states existence conditions of limit distribution for the fulfillment of differently shaped condition, which are superimposed on the sequence of terms of infinitesimal matrices of given process have been found. The control method of nonhomogeneous process parameters with the aid of it is possible at the fixed moment of time to obtain probabilities of the heterogeneous process states which equal to the stationary distribution of arbitrary homogeneous process has been proposed. is offered, The reduction method of discrete homogeneous markovian processes with counted number of states and discrete Markov chains has been suggested. It has been found that coincidence of reduced systems solving of Kolmogorov equations up to initial system solving takes place. The numerical analysis infinite system solving of Kolmogorov differential equations for standard cases of behavior of infinitesimal matrices have been carried out. Stabilization conditions of probability density of heterogeneous diffusional Markov process for completed time have been obtained.

Keywords: nonhomogeneous markovian systems, stabilizstion methods of distribution, focusing methods of distribution, step disturbance, systems with the variable number of states|, system reduction.

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