Исследование методов планирования имитационных экспериментов тема автореферата и диссертации по математике, 01.01.07 ВАК РФ

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

ОД

На правах рукописи

Фомина Татьяна Вениаминовна

ИССЛЕДОВАНИЕ МЕТОДОВ ПЛАНИРОВАНИЯ ИМИТАЦИОННЫХ ЭКСПЕРИМЕНТОВ

01.01.07 — вычислительная математика

АВТОРЕФЕРАТ

Диссертации на соискание учёной степени кандидата физико-математических наук

Санкт-Петербург 1997

Работа выполнена на кафедре статистического моделирования математико-механического факультета Санкт-Петербургского государственного университета.

Научный руководитель: доктор физико-математических наук Мелас В.Б.

Официальные оппоненты: доктор физико-математических наук, профессор Седунов Е.В.

кандидат физико-математических наук, доцент Буре В.М.

Ведущая организация: Санкт-Петербургский государственный технический университет

заседании диссертационного совета Л 063.57.30 по защите диссертаций на соискание учёной степени доктора наук в Санкт-Петербургском государственном университете по адресу: 198904, Санкт-Петербург, Старый Петергоф, Библиотечная пл., д. 2, математико-механический факультет.

С диссертацией можно ознакомиться в Центральной научной библиотеке Санкт-Петербургского государственного университета по адресу: 199034, Санкт-Петербург, Университетская наб., д. 7/9.

Защита состоится « ¿¿г »

-

1997 г. в ?час

час. на

Автореферат разослан «

»

1997 г.

Ученый секретарь диссертационного совета, кандидат техн. наук

Сушков Ю.А.

ОБШАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность работы. Начиная с конца 40-х годов, при исследовании стохастических моделей, в частности моделей теории массового обслуживания и надежности, наряду с проведением математического анализа характеристик изучаемой системы используется имитационное моделирование, которое позволяет исследовать процесс, воспроизводя его поведение с помощью ЭВМ. Очень часто изучение сложной стохастической системы может быть сведено к изучению вложенной цепи Маркова.

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

Идея метода под названием "расщепление и русская рулетка" была предложена фон Нейманом и Уламом еще в 1948 г. В дальнейшем идея этого метода использовалась различными исследователями, например, в теории переноса излучений она применялась В.Н.Огибиным. Однако метод остается недостаточно исследова-ным, что отмечалось в монографии Г.А.Михайлова (1987). Применение этого метода при моделировании систем массового обслуживания исследовалось в монографии С.М.Ермакова и В.Б.Меласа "Design and analysis of simulation experiments" (Kluwer, 1995).

В основе подхода, разработанного В.Б.Меласом, лежит введение вероятностой меры, управляющей процессами размножения и отмены траекторий. Этот подход позволяет определить план имитационного эксперимента с ветвлением траекторий как указанную вероятностную меру. Оптимальный выбор этого плана аналогичен задачам математической теории планирования эксперимента. Важным критерием оптимальности является критерий Д-оптимальности, требующий минимизации определителя дисперсионной матрицы оценок.

Значительным преимуществом метода ветвления траекторий является его универальность. При реализации этого метода не требу-

ется моделирование каких-либо распределений, отличающихся от тех, которые образуют исследуемый случайный процесс. Это дает возможность создать для реализации МВТ универсальный алгоритм, позволяющий исключить дополнительную алгоритмическую и вычислительную работу.

Цель работы. Целью работы явилось исследование эффективности Д-оптимальных планов при оценке стационарного распределения цепей Маркова с помощью МВТ и разработка метода ее повышения, основанного на преобразовании исходной цепи.

Научная новизна, В диссертации получены следующие новые результаты:

1. Найдена верхняя граница эффективности Д-оптимальных планов при оценке стационарного распределения цепей Маркова с помощью МВТ.

2. Предложены способы повышения эффективности МВТ для цепей Маркова с конечным числом состояний.

3. Разработаны алгоритмы и программы для построения Д-оптимальных планов для конечных цепей Маркова и для моделирования систем массового обслуживания с помощью МВТ.

4. Построены Д-оптимальные планы для некоторых классов цепей Маркова.

5. Проведено сравнение различных методов построения оценок.

Методы исследования. При исследовании использованы методы теории вероятностей и статистического моделирования.

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

Апробация результатов и публикации. Основные результаты диссертации опубликованы в работах [1, 2, 3, 4, 5]. Результаты диссертации докладывались на двух международных конференциях: International workshop on mathematical methods and tools

in computer simulation, Санкт-Петербург, 24-28 мая 1994 г, The 2nd St.Petrsburg workshop on simulation. Санкт-Петербург, 18-21 июня, 1996, на семинарах кафедры статистического моделирования математико-механического факультета Санкт-Петербургского государственного университета.

Работа над диссертацией была поддержана грантом правительства Санкт-Петербурга для молодых ученых и аспирантов. Материалы, вошедшие в первую главу диссертации, были поддержаны грантом РФФИ №96-01-00644.

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

СОДЕРЖАНИЕ РАБОТЫ

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

Рассмотрим цепь Маркова сп + 1 состоянием. Пусть Р = (pij)f=0 — матрица переходных вероятностей цепи Маркова, я- = (Я|)?=о — стационарное распределение. Введем понятие плана эксперимента г = (tv)«=о,..„п, Где £Г=о П = 1, т; >0, (г = 0,..., п), г является вероятностной мерой, управляющей процессами размножения и отмены траекторий.

Естественным критерием оптимальности является определитель дисперсионной матрицы оценок, задача минимизации которого эквивалентна задаче минимизации определителя матрицы

вд = Е

где

А = {PijVjk -PijPik)j,k=i,...,n (i = 0,...,гс). Будем называть план эксперимента т* Л-оптимальным, если

det B(r*) = inf det B(r).

Введем понятие эффективности эксперимента с ветвлением по отношению к непосредственному моделированию:

Наша задача будет заключаться в определении максимально возможной эфективности Д-оптимальных планов. В явном виде Д-оптимальные планы найти не удается, но В.Б.Меласом построена рекуррентная процедура их нахождения, на которой основаны алгоритм и программа построения Д-оптимального плана для конечных цепей Маркова, описанные в §1.4.

В следующих трех параграфах исследуются цепи Маркова с двумя и тремя состояниями. Такие цепи, возникающие вследствие укрупнения состояний цепи, достаточно часто используются в практических приложениях.

В §1.5 найдена точная верхняя граница эффективности Д-опти-мального плана для цепей Маркова с конечным числом состояний. Основным результатом главы является теорема 1.5.1. Теорема 1.5.1 Эффективность Д-оптимального плана для цепей Маркова сп + 1 состоянием и стационарным распределением 7Г, упорядоченным по возрастанию, не превышает I** = тах;=о,...,п где

и может быть сколь угодно близка к этой величине.

В ходе доказательства теоремы выделены классы цепей Маркова, для которых эффективность Д-оптимальных планов будет наибольшей. В §1.6 приведены результаты компьютерных вычислений, наглядно показывающих, что наибольшая эффективность Д-оптимального плана действительно достигается для цепей, "близких" к указанным классам.

§1.7 посвящен обобщению результатов §1.5 на случай цепей Маркова со счетным числом состояний. Здесь доказывается теорема

1

1.7.1, которая позволяет вычислять верхнюю границу эффективности Д-оптимального плана. Для каждого фиксированного п будем считать, что тго,..., т„ расположены в невозрастающем порядке. Введем обозначения:

{у/^п-г + у/^п-т)'

г, г = 1, 2,..., п.

Теорема 1.7.1 Эффективность Д-оптималъпого плана 1{т*) для цепей Маркова со счетным -числом состояний и стационарныл1 распределением 7г = (т«)<=о удовлетворяет следующим неравенствам:

ЛП » 1=1

<

ПШ --,

/ Ро Р1 Р2 • .. \

Ро Р1 Р2 •

0 Ро Р1 •

0 0 РО •

V ; ; • • /

где тг^ = пнп{хо,..., 7Г„}.

С помощью этой теоремы вычислена, верхняя граница эффективности Д-оптимального плана, для цепи Р, матрица переходных вероятностей которой имеет следующий вид:

Р ~

где {рл;} — произвольное распределение. Эта цепь встречается в теории массового обслуживания при построении цепи, вложенной в систему с одним обслуживающим прибором.

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

оптимальном проведении операции расщепления эффективность Д-оптимального плана для новой цепи (образовавшейся после расщепления) может значительно превышать эффективность для исходной Цепи.

В §2.1 вводится операция расщепления одного состояния цепи на & + 1 состояние с весовым вектором расщепления а = (ао, • • •,«(:),

а» — ai > 0 (г = 0,..., к), и доказывается теорема 2.1.1. Теорема 2.1.1 Эффективность Д-оптималъного плана т* для цепи, полученной в результате расщепления состояния j на k + 1 состояние, не зависит от весового вектора расщепления и определяется следующим равенством:

f(0 =__.

ЬЧ(£Г=Л>х)*<1<*2?(Г))

Анализ полученных выражений показывает, что применение этого приема может значительно увеличить эффективность МВТ.

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

В §2.4 подробно исследуется применение операции расщепления к цепи Маркова с двумя состояниями. Показывается, что при проведении расщепления состояния, соотвествуклцего минимуму стационарного распределения, эффективность Д-оптимального плана увеличивается. В §2.5 приводятся результаты численного эксперимента, Показывающие, что применение процедуры расщепление способно значительно повысить эффективность моделирования. 14 в §2.6 описывается еще один способ повышения эффективности моделирования, который заключается в преобразовании цепи с двумя состояниями в цепь с тремя состояниями специального вида (в матрице переходных вероятностей элементы, стоящие на главной диагонали, равны нулю).

Глава 3 посвящена сравнению некоторых модификаций Д-критерия оптимальности, введенных в монографии С.М.Ермаковаи В.Б.Меласа "Design and analysis of simulation experiments", а также нахождению Д-

оптимальных планов для некоторых классов цепей. В упомянутой работе рассмотрен, в частности, следующий критерий оптимальности ветвящегося имитационного плана ¡3 для цепи Маркова с конечным числом состояний, для которой переходы "вверх" возможны только в соседнее состояние:

где величина щ является несмещенной оценкой параметра гу, равного числу попаданий в состояние./.

Для рассматриваемого критерия ветвящийся имитационный план

в*:

7Го

является единственным оптимальным планом. Этот план привлекает простотой вычисления. Далее рассматривается план I* = (/д,...,Ц = т^Н—у, соответствующий оптимальному плану /?* и вводится величина ./(г*), равная отношению эффективно-стей Д-оптимального плана г* и плана I*. Приводятся результаты численного эксперимента, позволяющие сравнить эффективности оптимальных планов.

В §3.2 строится Д-оптимальный план для цепи Маркова с п + 1 состоянием, которая соответствует случайному блужданию с отражающими экранами и с переменными вероятностями перехода. Д-оптимальный план этой цепи и его эфективность определяются теоремой 3.2.1.

Теорема 3.2.1. Для цепи Маркова, соответствующей случайному блужданию с матрицей переходных вероятностей V и стационарным распределением тг Д-оптимальный план г* равен

г* = (0, ,-,...,-). п п

Эффективность Д-оптимального плана I* равна

Г-—1__

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

Следующие параграфы главы 3 посвящены сравнению различных методов моделирования систем массового обслуживания. В §3.4 приводятся некоторые сведения о системах массового обслуживания. В качестве основной модели рассматривается система обслуживания достаточно общего вида, для которой не существует исчерпывающего математического исследования — система С1[С/\/(Х). В §3.5 приводятся необходимые теоретико-вероятностные сведения об этой системе, а также определяется параметр <3 —■ вероятность превышения заданного времени ожидания обслуживания, оценку которого мы и будем искать. В §3.6 описаны две оценки параметра ф: вл — оценка регенеративного метода и — оценка МВТ. В §3.7 описан алгоритм построения оценки МВТ, и в §3.8 приведены результаты численного эксперимента, позволяющие сравнить эффективность трех исследуемых методов. Результаты моделирования подтверждают, что МВТ гораздо более эффективен, нежели РМ, и отличие эффективности тем больше, чем меньшее значение имеет оцениваемая величина:

В последней главе диссертации иллюстрируется возможность применения МВТ к оценке стационарных вероятностей цепей Маркова, вложенных в различные системы массового обслуживания. В §4.2 рассматривается модель Пальма с т приборами (приборы с экспоненциально распределенным временем безотказной работы ремонтируются в ремонтной мастерской в порядке их выхода из строя. После окончания ремонта приборы сразу же включаются в работу). В следующем параграфе исследуется модель М/С/1/оо. Для цепей Маркова вложенных в эти системы численно найдены Д-оптимальные планы, эффективность моделирования и продемонстрирована эффективность приема расщепления. §4.4 и §4.5 посвящены определению стационарных вероятностей в смешанной открыто-замкнутой сети и в модели сборочного устройства.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ ДИССЕРТАЦИИ 1. Найдена точная верхняя граница эффективности Д-оптимальных

планов для цепей Маркова с конечным числом состояний. Проведены численные эксперименты подтверждающие теоретические выводы.

2. Найдена верхняя граница эффективности Д-оптимальных планов для цепей Маркова со счетным числом состояний.

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

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

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

6. Найден в явном виде Д-оптимальный план для конечного случайного блуждания.

7. Разработан алгоритм и написана программа для моделирования систем массового обслуживания с помощью МВТ. Проведено численное сравнение эффективности моделирования системы СЦС1\(оо с помощью МВТ, регенеративного метода и метода существенной выборки.

8. В ходе численных экспериментов исследована эффективность МВТ при определении стационарных распределений цепей Маркова, вложенных в различные системы массового обслуживания.

Основные результаты диссертации опубликованы в работах:

[1] Об эффективности моделирования некоторых цепей Маркова по методу ветвления траекторий. Вестник СПбГУ. Сер.1. вып.2 (№). 1996. С.110-112.

[2] Об эффективности метода ветвления для конечных цепей Маркова. Вестник СПбГУ. Сер.1, 1997,вып.2 (№8), с.28-33 (совместно с В.Б.Меласом).

[3] Он the efficiency of branching variance reduction technique for the simulation of markov chains with three states. Proceedings of the 2-nd St.Petrsburg workshop on simulation. St.Petersburg. June 18-21. 1996. Saint Petersburg. Publishing house of Saint Petrsburg University. 1996. pp.189-193.

[4] On numerical study of branching technique efficiency for random walks simulation. International workshop on mathematical methods and tools in computer simulation. May 24-28, 1994. Saint Petersburg. V.I.Smirnov scientific research institute of mathematics and mechanics. Saint Petersburg, pp.59-60 (Co-author V.B.Melas).

[5] A way to increase the efficiency of branching variance reduction technique. Proceedings of the 2-nd St.Petrsburg workshop on simulation. St.Petersburg. June 18-21. 1996. Saint Petersburg. Publishing house of Saint Petrsburg University. 1996. pp.194-201 (Co-author V.B.Melas).

Подписано к печати .04.97 г. Заказ 282 Тираж 100 экз. Объем 1.1 п.л. Отдел оперативной полиграфии НИИ Химии СПбГУ, 198904, Санкт-Петербург, Старый Петергоф, "Университетский пр., 2