Введение к работе
Актуальность работы. Начиная с конца 40-х годов, при исследовании стохастических моделей, в частности моделей теории массового обслуживания и надежности, наряду с проведением математического анализа характеристик изучаемой системы используется имитационное моделирование, которое позволяет исследовать процесс, воспроизводя его поведение с помощью ЭВМ. Очень часто изучение сложной стохастической системы может быть сведено к изучению вложенной цепи Маркова.
Однако, прямые методы моделирования часто оказываются малоэффективными, так как оценке подлежат вероятности редких событий, например, обуславливающих отказ системы. В настоящее время разработаны многочисленные методы ускорения моделирования. К сожалению, большинство из них требует значительных сведений об исследуемой цепи, в частности задания в явном виде вероятностей перехода, что неприемлимо во многих практических задачах. При алгоритмическом задании цепи Маркова перспективным представляется применение метода ветвления траекторий (МВТ).
Идея метода под названием "расщепление и русская рулетка" была предложена фон Нейманом и Уламом еще в 1948 г. В дальнейшем идея этого метода использовалась различными исследователями, например, в теории переноса излучений она применялась В.Н.Огибиным. Однако метод остается недостаточно исследова-ным, что отмечалось в монографии Г.А.Михайлова (1987). Применение этого метода при моделировании систем массового обслуживания исследовалось в монографии С.М.Ермакова и В.Б.Меласа "Design and analysis of simulation experiments" (Kluwer, 1995).
В основе подхода, разработанного В.Б.Меласом, лежит введение вероятностей меры, управляющей процессами размножения и отмены траекторий. Этот подход позволяет определить план имитационного эксперимента с ветвлением траекторий как указанную вероятностную меру. Оптимальный выбор этого плана аналогичен задачам математической теории планирования эксперимента. Важным критерием оптимальности является критерий Д-оптимальности, требующий минимизации определителя дисперсионной матрицы оценок.
Значительным преимуществом метода ветвления траекторий является его универальность. При реализации этого метода не требу-
ется моделирование каких-либо распределений, отличающихся от тех, которые образуют исследуемый случайный процесс. Это дает возможность создать для реализации МВТ универсальный алгоритм, позволяющий исключить дополнительную алгоритмическую и вычислительную работу.
Цель работы. Целью работы явилось исследование эффективности Д-оптимальных планов при оценке стационарного распределения цепей Маркова с помощью МВТ и разработка метода ее повышения, основанного на преобразовании исходной цепи.
Научная новизна, В диссертации получены следующие новые результаты:
-
Найдена верхняя граница эффективности Д-оптимальных планов при оценке стационарного распределения цепей Маркова с помощью МВТ.
-
Предложены способы повышения эффективности МВТ для цепей Маркова с конечным числом состояний.
-
Разработаны алгоритмы и программы для построения Д-оптимальных планов для конечных цепей Маркова и для моделирования систем массового обслуживания с помощью МВТ.
-
Построены Д-оптимальные планы для некоторых классов цепей Маркова.
-
Проведено сравнение различных методов построения оценок.
Методы исследования. При исследовании использованы методы теории вероятностей и статистического моделирования.
Практическая ценность. Результаты диссертационной работы носят, в основном, теоретический характер, но могут найти непосредственное применение при разработке программного обеспечения для исследования сложных стохастических систем с помощью имитационного моделирования.
Апробация результатов и публикации. Основные результаты диссертации опубликованы в работах [1, 2, 3, 4, 5]. Результаты диссертации докладывались на двух международных конференциях: International workshop on mathematical methods and tools
in computer simulation, Сапкт-Петербург, 24-28 мая 1994 г, The 2-nd St.Petrsburg workshop on simulation. Санкт-Петербург, 18-21 июня, 1996, на семинарах кафедры статистического моделирования математико-механического факультета Санкт-Петербургского государственного университета.
Работа над диссертацией была поддержана грантом правительства Санкт-Петербурга для молодых ученых и аспирантов. Материалы, вошедшие в первую главу диссертации, были поддержаны грантом РФФИ №96-01-00644.
Структура и объем работы. Диссертация состоит из введения и четырех глав, изложенных на 117 страницах машинописного текста и списка литературы, состоящего из 48 наименований. СОДЕРЖАНИЕ РАБОТЫ
