Методы идемпотентной алгебры в задачах моделирования и анализа сложных систем

Актуальность темы

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

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

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

Одной из первых публикаций по идемпотентной алгебре и ее приложениям является работа С. К. Клини [96], опубликованная в 1956 г. Ссылки на другие ранние публикации можно найти в подробных обзорах, приведенных в монографиях [81,128].

В работах H.H. Воробьева [7−9], а также A.A. Корбута [16,17] была построена алгебраическая теория идемпотентных векторных полумодулей и заданных на таких полумодулях линейных операторов (в этих работах они назывались соответственно экстремальными пространствами и линейными экстремальными операторами). В частности, была сформулирована и решена проблема собственных значений оператора, изучены уравнения вида Ах = Ь, заданные на векторных полумодулях, а также рассмотрен ряд примеров практических приложений полученных результатов. Следует заметить, что в качестве основного объекта исследования в этих работах рассматривалось числовое идемпотентное полукольцо, в котором для всякого ненулевого элемента существует обратный по умножению. Такое полукольцо часто называют идемпотентным полуполем.

В это же время И. В. Романовским в рамках изучения асимптотических свойств решений задачи динамического программирования был получен идемпотентный аналог известного результата о спектре ограниченного линейного оператора в банаховом пространстве [61−63] (см. также [50]).

Следующий шаг в развитии теории и методов идемпотентной алгебры связан с появлением монографий P.A. Кунингхайма-Грина [81], Б.А. Kappe [74] и У. Циммерманна [128]. Часть вопросов, которые рассматриваются в [81], повторяют тематику исследований H.H. Воробьева. Однако представленные в работе результаты опираются на применение несколько иной алгебраической техники, которая, в частности, позволяет записывать эти результаты в компактной матричной форме. Наряду с идемпотентными полуполями изучаются более общие идемпотентные полукольца.

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

Дальнейшее развитие это область получила в материалах научной школы, возглавляемой акад. В. П. Масловым, в рамках изучения идемпотентного анализа как теории полумодулей функций со значением в идемпотентном полукольце [11,51−54,65,66]. Эти и другие работы В. П. Маслова, В.Н. Ко-локольцова, Г. Л. Литвинова, А. Н. Соболевского, Г. Б. Шпиза и их коллег заложили основы и сформировали методологическую базу нового направления — идемпотентной математики, которая объединяет идемпотентныи вариант алгебры, анализа, а также функционального анализа.

Различные аспекты теории и применения идемпотентной алгебры при решении прикладных задач исследовали Ф. Бачелли, Я. Г. Олсдер, Д. С. Голан, Б. Хейдерготт и другие авторы. Среди опубликованных ими работ имеются монографии [68,77,78,92,93], каждая из которых содержит подробный обзор литературы, относящейся к рассматриваемому кругу вопросов.

К числу публикаций, в которых развитие моделей и методов идемпотентной алгебры сочетается с решением прикладных задач, относятся работы В. Д. Матвеенко [55−57,123−125], С. Л. Блюмина [3,4,71], а также работы автора [14,20−50,83−85,90,97−119].

В частности, в работах [55−57,123−125] на основе методов идемпотентной алгебры решен ряд задач исследования структуры моделей экономической динамики. В [124,125] рассматривается проблема собственных значений для полумодуля над идемпотентным полукольцом, которое не является полуполем. Публикации [3,4,71] посвящены изучению взаимосвязей и параллелей между обычной линейной алгеброй и обобщенной линейной алгеброй над полукольцами разного вида, включая идемпотентные полукольца. Обсуждаются различные приложения, а также роль и значения обобщенной линейной алгебры в задачах искусственного интеллекта и других областях прикладной математики.

Среди значительного числа публикаций в области идемпотентной алгебры имеется относительно небольшая часть, которая посвящена решению стохастических задач (см., например, [44,67,68,76,86−88,92,94,111,112]). Такие задачи обычно связаны с исследованием эргодических свойств обобщенных линейных стохастических динамических систем и включают исследование асимптотического поведения вектора состояний системы. Одной из наиболее распространенных задач такого типа является вычисление средней асимптотической скорости роста вектора состояний, которую часто называют показателем Ляпунова системы.

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

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

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

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

Основные результаты и научная новизна. Основные результаты, представленные в работе, являются новыми, получены лично соискателем и состоят в следующем.

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

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

3. Доказаны теоремы сходимости для итераций линейного оператора на векторном полу модуле над идемпотентным полуполем.

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

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

6. Построены оценки для показателя Ляпунова для случаев, когда матрица системы является регулярной или неразложимой.

7. Построены и исследованы алгебраические модели систем с очередями с синхронизацией движения требований, разработаны и изучены алгоритмы имитационного моделирования многофазных систем.

8. Решены задачи вычисления и оценки среднего времени цикла обслуживания систем с очередями с синхронизацией, а также оценки среднего времени безотказной работы в таких системах.

9. Разработан комплекс программных средств решения вычислительных задач идемпотентной алгебры.

Достоверность и обоснованность результатов подтверждается приведенными доказательствами и рассмотренными примерами.

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

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

Разработанные методы решения уравнений и проблемы собственных значений реализованы в виде комплекса программных средств.

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

Апробация работы. Основные результаты обсуждались на семинарах на математико-механическом факультете и факультете менеджмента Санкт-' Петербургского государственного университета, в Санкт-Петербургском экономико-математическом институте РАН, Санкт-Петербургском отделении Математического института им. В. А. Стеклова РАН, Институте проблем управления им. В. А. Трапезникова РАН, Институте кибернетики им. В. М. Глушкова Национальной академии наук Украины, Центре экономических исследований университета Тилбурга (Нидерланды), на Отделении автоматического управления университета Линчопинга (Швеция), Факультете компьютерных наук Национального университета Сингапура (Сингапур), в Школе бизнеса им. Г. Р. Гербергера университета Сент-Клауда (США), Институте математики Свободного университета Берлина (Германия).

Результаты представлены па следующих научных конференциях: 3rd.

International Workshop on Model-Oriented Data Analysis (Санкт-Петербург, 1992), St. Petersburg Workshop on Simulation (Санкт-Петербург, 1994;2009), NATO Advanced Study Institute «Current Issues and Challenges in the Reliability and Maintenance of Complex Systems» (Анталия, Турция, 1995), International Workshop on Discrete Event Systems (Эдинбург, Великобритания, 1996), International Conference on Random Dynamical Systems (Бремен, Германия, 1997), 10th INFORMS Applied Probability Conference (Ульм, Германия, 1999), XII Международная конференция «Проблемы теоретической кибернетики» (Нижний Новгород, 1999), 2nd International Workshop «New Models of Business: Managerial Aspects and Enabling Technology» ' (Санкт-Петербург, 2002), Международный конгресс «Нелинейный динамический анализ» (Санкт-Петербург, 2007), 6th International Conference on Mathematical Modelling (Вена, Австрия, 2009), Всероссийская конференция по вычислительной математике (Новосибирск, 2009).

Связь работы с научными программами. Исследования проводились в рамках инициативных научных проектов, поддержанных грантами РФФИ №№ 00−01−760, 04−01−840, 06−01−763, 09−01−808.

Часть результатов получена в ходе работ по теме «Оптимальное математическое моделирование нечетко заданных взаимосвязанных процессов и систем нестационарными моделями, задаваемыми над дистрибутивными решетками» (гос. per. № 0120.804 162) согласно тематическому плану НИР НИИММ СПбГУ по заданию Рособразования.

Публикация результатов. Результаты исследований отражены в работах [14,20−50,83−85,90,97−119], включая статьи [20,25,27,29,32,33,35,36, 38,46,48,49], опубликованные в изданиях, входящих в перечень ВАК на момент публикации, статьи [83, 98, 99,105] в изданиях, включенных в систему цитирования Web of Science (Science Citation Index Expanded), а также монографию [45].

В работах [47−49] соискателем осуществлена постановка задачи, построение и анализ модели системы, а также получены верхние оценки среднего времени безотказной работы системы. Соавтором построены нижние оценки, разработаны программные средства и проведены численные расчеты. В [83, 84] соискателем выполнено построение и анализ сложности алгоритмов имитационного моделирования систем, а соавтором — постановка задачи и анализ методов решения.

В [14,85] соискателем построены и изучены имитационные модели систем с очередями. Остальные результаты принадлежат соавторам.

В работах [90,117] соискателем выполнена разработка математических моделей и методов анализа бизнес-процессов, а соавтору принадлежит постановка задачи и интерпретация результатов в терминах предметной области. В f статье [50] соискателем получены неравенства для собственного числа, нормы" и следа степени матрицы, а также теорема о сходимости итераций линейного оператора. Постановка задачи и анализ существующих результатов выполне-" ны соавтором.

В [118,119] соискателю принадлежит теорема о среднем времени цикла обслуживания в многофазных системах с очередями, а соавтору — аналитический обзор результатов, связанных с оценкой средних значений максимумов сумм независимых случайных величин.

Структура и объем работы. Диссертация состоит из введения, десяти глав, списка литературы и приложения. Объем диссертации составляет 300 страниц, включая 10 иллюстраций и 4 таблицы.

Список литературы

содержит 128 наименований.

1. Бачелли Ф., Маковски А. М. Использование методов теории массового обслуживания для анализа систем с ограничениями по синхронизации // Труды ИИЭР. 1989. Т. 77, № 1. С. 99−128.

2. Беллман Р.

Введение

в теорию матриц. М.: Наука, 1976. 352 с.

3. Блюмин С. Л. Математические проблемы искусственного интеллекта: регулярность по Дж. фон Нейману в линейной и «линейной» алгебрах // Системы управления и информационные технологии. 2003. Т. 1−2(12). С. 90−94.

4. Блюмин С. Л. Математические проблемы искусственного интеллекта: булева «линейная» алгебра // Системы управления и информационные технологии. 2005. Т. 3(20). С. 4−10.

5. Боровков A.A. Теория вероятностей. М.: Наука, 1986. 432 с.

6. Воеводин В. В. Математические модели и методы в параллельных процессах. М.: Наука, 1986. 296 с.

7. Воробьев H.H. Экстремальная алгебра матриц // Доклады АН СССР. 1963. Т. 152, № 1. С. 24−27.

8. Воробьев H.H. Экстремальная алгебра положительных матриц // Elektronische Informationsverarbeitung und Kybernetik. 1967. Bd. 3, N 1. S. 39−72.

9. Воробьев H.H. Экстремальная алгебра неотрицательных матриц // Elektronische Informationsverarbeitung und Kybernetik. 1970. Bd. 6, N 4/5. S. 303−312.

10. Гантмахер Ф. Р. Теория матриц. M.: Наука, 1988. 552 с.

11. Дудников П. И., Самборский С. Н. Эндоморфизмы полумодулей над полукольцами с идемпотентной операцией // Известия АН СССР. Сер. матем. 1991. Т. 55. № 1. С. 93−109.

12. Ермаков С. М. Метод Монте-Карло и смежные вопросы. М.: Наука, 1975. 472 с.

13. Ермаков С. М., Михайлов Г. А. Статистическое моделирование. М.: Наука, 1982. 296 с.

14. Калашников В. В., Рачев С. Т. Математические методы построения стохастических моделей обслуживания. М.: Наука, 1988. 312 с.

15. Корбут A.A. Экстремальные пространства // Доклады АН СССР. 1965. Т. 164, № 6. С. 1229−1231.

16. Корбут A.A. Экстремальные векторные пространства и их свойства // Elektronische Informationsverarbeitung und Kybernetik. 1972. Bd. 8, N 8/9. S. 525−536.

17. Кофман А., Крюон Р. Массовое обслуживание. Теория и приложения. М.: Мир, 1965. 302 с.

18. Коэн Г., Моллер П., Кадра Ж.-П., Вьо М. Алгебраические средства оценивания характеристик дискретно-событийных систем // Труды ИИЭР. 1989. Т. 77, № 1. С. 30−53.

19. Кривулин Н. К. Об оптимизации сложных систем при имитационном моделировании // Вестн. Ленингр. ун-та. Сер. 1. 1990. Вып. 2 (№ 8) С. 100— 102.

20. Кривулин Н. К. Оптимизация динамических систем с дискретными событиями на основе имитационного моделирования // Автореф. дисс.. канд. физ.-мат. наук. Л.: Ленингр. гос. ун-т, 1990. 17 с.

21. Кривулин Н. К. Алгебраические модели сетей с очередями // Математические модели и информационные технологии в менеджменте: Сб. науч. статей / Под ред. Н. К. Кривулина, В. В. Трофимова. СПб.: Изд-во С.-Петерб. ун-та, 2001. С. 25−38.

22. Кривулин Н. К. Среднее время цикла обслуживания в ациклических сетях с операциями разъединения и объединения требований // Проблемы оптимизации дискретных систем: Сб. науч. статей / Под. ред. М. К. Чиркова. СПб.: НИИХ СПбГУ, 2001. С. 97−109.

23. Кривулин Н. К. Вычисление среднего времени цикла в сетях с операциями разъединения и объединения требований // Вестн. С.-Петерб. ун-та. Сер. 1, 2002. Вып. 3 (№ 17). С. 27−35.

24. Кривулин Н. К. Оценивание константы Ляпунова для обобщенных линейных стохастических систем // Математические модели. Теория и приложения: Сб. науч. статей / Под ред. М. К. Чиркова, Вып. 2. СПб.: Изд-во НИИХ СПбГУ, 2002. С. 150−163.

25. Кривулин Н. К. Оценивание скорости роста вектора состояний обобщенной линейной динамической системы со случайной матрицей // Вестн. С.-Петерб. ун-та. Сер. 1, 2003. Вып. 3 (№ 17). С. 47−55.

26. Кривулин Н. К. Неравенства и теоремы сходимости для степеней матрицы в идемпотентной алгебре // Математические модели. Теория и приложения. Вып. 4. Сб. науч. статей / Под ред. М. К. Чиркова. СПб.: ВВМ, 2004. С. 64−72.

27. Кривулин Н. К. Теорема сходимости для степеней матрицы и вычисление собственного числа в идемпотентной алгебре // Вестн. С.-Петерб. ун-та. Сер. 1, 2004. Вып. 2. С. 49−55.

28. Кривулин Н. К. О представлении решений линейных уравнений в идемпотентной алгебре // Математические модели. Теория и приложения. Вып. 4. Сб. науч. статей / Под ред. М. К. Чиркова. СПб.: ВВМ, 2004. С. 139−145.

29. Кривулин Н. К. О решении линейных векторных уравнений в идемпотентной алгебре // Математические модели. Теория и приложения: Сб. науч. статей. Вып. 5 / Под ред. М. К. Чиркова. СПб.: ВВМ, 2004. С. 105 113.

30. Кривулин Н. К. Скорость роста вектора состояний обобщенной линейной динамической системы со случайной треугольной матрицей // Вестн. С.-Петерб. ун-та. Сер. 1, 2005. Вып. 1. С. 33−38.

31. Кривулин Н. К. Об оценке средней скорости роста вектора состояний линейной динамической стохастической системы в идемпотентной алгебре // Вестн. С.-Петерб. ун-та. Сер. 1, 2005. Вып. 2. С. 45−54.

32. Кривулин Н. К. О решении линейных уравнений и проблемы собственных значений в идемпотентной алгебре // Математические модели. Теория и приложения: Сб. науч. статей. Вып. 6 / Под ред. М. К. Чиркова. СПб.: ВВМ, 2005. С. 186−212.

33. Кривулин Н. К. О решении обобщенных линейных векторных уравнений в идемпотентной алгебре // Вестн. С.-Петерб. ун-та. Сер. 1, 2006. Вып. 1. С. 23−36.

34. Кривулин Н. К. Собственные значения и векторы матрицы в идемпотент-ной алгебре // Вести. С.-Петерб. ун-та. Сер. 1, 2006. Вып. 2. С. 29−40.

35. Кривулин Н. К. О решении некоторых видов линейных уравнений в идем-потентной алгебре // Математические модели. Теория и приложения: Сб. науч. статей. Вып. 7 / Под ред. М. К. Чиркова. СПб.: ВВМ, 2006. С. 80−88.

36. Кривулин Н. К. Скорость роста вектора состояний обобщенной линейной стохастической системы с симметричной матрицей // Зап. науч. семинаров ПОМИ. 2007. Т. 341. С. 134−141. (Принято к печати 30 ноября 2006г-).

37. Кривулин Н. К. Вычисление скорости роста вектора состояний для одной модели обобщенной линейной стохастической системы // Вестн. С.-Петерб. ун-та. Сер. 1, 2007. Вып. 3. С. 91−99.

38. Кривулин Н. К. Примеры построения моделей и решения задач на основе методов идемпотентной алгебры // Математические модели. Теория и приложения: Сб. науч. статей. Вып. 8 / Под ред. М. К. Чиркова. СПб.: Золотое сечение, 2007. С. 158−183.

39. Кривулин Н. К. О вычислении скорости роста вектора состояний обобщенной линейной стохастической системы второго порядка // Вестн. С.-Петерб. ун-та. Сер. 1, 2008. Вып. 1. С. 38−48.

40. Кривулин Н. К. Вычисление показателя Ляпунова в стохастических динамических моделях систем с очередями // Стохастическая оптимизация в информатике. Вып. 4 / Под ред. О. Н. Граничина. СПб.: Изд-во С.-Петерб. ун-та, 2008. С. 90−120.

41. Кривулин Н. К. Спектральный радиус матрицы некоторых обобщенных линейных операторов // Математические модели. Теория и приложения: Сб. науч. статей. Вып. 9 / Под ред. М. К. Чиркова. СПб.: ВВМ, 2008. С. 73−82.

42. Кривулин Н. К. Вычисление показателя Ляпунова обобщенных линейных систем с показательным распределением элементов переходной матрицы // Вестн. С.-Петерб. ун-та. Сер. 1, 2009. Вып. 2. С. 37−46.

43. Кривулин Н. К. Методы идемпотентной алгебры в задачах моделирования и анализа сложных систем. СПб.: Изд-во С.-Петерб. ун-та, 2009. 256 с.

44. Кривулин Н. К. О решении одного класса векторных уравнений в идемпотентной алгебре // Вестн. С.-Петерб. ун-та. Сер. 10. 2009. Вып. 3. С. 6477.

45. Кривулин Н. К., Милое Д. С. Оценки среднего времени безотказной работы одного класса сетей с очередями // Вести. С.-Петерб. ун-та. Сер. 1, 2001. Вып. 1 (№ 1). С. 23−30.

46. Кривулин Н. К., Милое Д. С. Оценка среднего времени работы для сетей с очередями со случайной топологией // Вестн. С.-Петерб. ун-та. Сер. 1, 2001. Вып. 3 (№ 17). С. 27−31.

47. Кривулин Н. К., Романовский И. В. О сходимости степеней матрицы обобщенного линейного оператора в идемпотентной алгебре // Проблемы математического анализа. № 34 / Под ред. H.H. Уральцевой. 2006. С. 69−77.

48. Литвинов Р. Л., Маслов В. П., Соболевский А. Н. Идемпотентная математика и интервальный анализ // Вычислительные технологии. 2001. Т. 6, № 6. С. 47−70.

49. Литвинов Г. Л., Маслов В. П., Шпиз Г. Б. Линейные функционалы на идемиотентных пространствах. Алгебраический подход // Доклады РАН. 1998. Т. 363, № 3. С. 298−300.

50. Литвинов Г. Л., Маслов В. П., Шпиз Г. Б. Идемпотентный функциональный анализ. Алгебраический подход // Математические заметки. 2001. Т. 69, № 5. С. 758−797.

51. Маслов В. П., Колокольцов В. Н. Идемпотентный анализ и его применение в оптимальном управлении. М.: Физматлит, 1994. 144 с.

52. Матвеенко В. Д. Оптимальные траектории схемы динамического программирования и экстремальные степени неотрицательных матриц // Дискретная математика. 1990. Т. 2. Вып. 1. С. 59−71.

53. Матвеенко В. Д. Структура оптимальных траекторий в моделях экономической динамики // Автореф. дисс.. докт. физ.-мат. наук. СПб.: Санкт-Петербургский экономико-математический институт РАН, 2004. 38 с.

54. Матвеенко В. Д. Структура оптимальных траекторий моделей экономической динамики с точки зрения алгебры // Инструменты анализа и управления переходными состояниями в экономике / Сб. статей. Екатеринбург: Изд-во Урал, ун-та, 2007. С. 99−110.

55. Михл, ин С. Г. Лекции по линейным интегральным уравнениям. М.: Физматлит, 1959. 232 с.

56. Ортега Дж.

Введение

в параллельные и векторные методы решения линейных систем. М.: Мир, 1991. 367 с.

57. Петровский И. Г. Лекции по теории интегральных уравнений. М.: Изд-во Моск. ун-та, 1984. 136 с.

58. Романовский И. В. Оптимизация стационарного управления дискретным детерминированным процессом // Кибернетика. 1967. № 2. С. 66−78.

59. Романовский И. В. Асимптотическое поведение дискретного детерминированного процесса с непрерывным множеством состояний // Оптимальное планирование / Сборник трудов Института математики СО АН СССР. 1967. № 8. С. 171−193.

60. Романовский И. В. Детерминированные процессы динамического программирования с дополнительными ограничениями // Кибернетика. 1971. № 5. С. 69−71.

61. Саати Т. Н. Элементы теории массового обслуживания и ее приложения. М.: Советское радио, 1971. 520 с.

62. Шпиз Г. Б. Решение алгебраических уравнений в идемпотентных полуполях // Успехи математических наук. 2000. Т. 55. Вып. 5(335). С. 185−186.

63. Шпиз Г. Б. Теорема о собственном векторе в идемпотентных пространствах // Доклады РАН. 2000. Т. 374, № 1. С. 26−28.

64. Baccelli F., Canales М. Parallel simulation of stochastic Petri nets using recurrence equations // ACM Transactions on Modeling and Computer Simulation. 1993. Vol. 3, N 1. P. 20−41.

65. Baccelli F., Cohen G., Olsder G.J., Quadrat J.-P. Synchronization and linearity: An algebra for discrete event systems. Chichester: Wiley, 1992. 514 p.

66. Blyurnin S.L., Golan J.S. One-sided complements and solutions of the equation aXb = с in semirings // International Journal of Mathematics and Mathematical Sciences. 2002. Vol. 29, N 8. P. 453−458.

67. Braker J.G., Olsder G.J. The power algorithm in Max algebra // Linear Algebra and Its Applications. 1993. Vol. 182. P. 67−89.

68. Carre B.A. An algebra for network routing problems // IMA Journal of Applied Mathematics. 1971. Vol. 7, N 3. P. 273−294.

69. Carre B. Graphs and networks. Oxford: Oxford University Press, 1979. 277 p.

70. Chen L., Chen C.-L. A fast simulation approach for tandem queueing systems // Proc. 1990 Winter Simulation Conf., New Orleans, LA, Dec. 9−12. Piscataway: IEEE, 1990. P. 539−546.

71. Cohen J.E. Subadditivity, generalized products of random matrices and operations research // SIAM Review. 1988. Vol. 30, N 1. P. 69−86.

72. Golan J.S. Semirings and their applications. Dordrecht: Kluwer, 1999. 396 p.

73. Golan J.S. Power algebras over semirings with applications in mathematics and computer science. Dordrecht: Kluwer, 1999. 216 p. (Mathematics and Its Applications, Vol. 488).

74. Greenberg A.G., Lubachevsky B.D., Mitrani I. Algorithms for unboundedly parallel simulation // ACM Transactions on Computer Systems. 1991. Vol. 9, N 3. P. 201−221.

75. Gumbel E.J. The maxima of the mean largest value and of the range // The Annals of Mathematical Statistics. 1954. Vol. 25. P. 76−84.

76. Cuninghame-Green R.A. Minimax algebra. Berlin: Springer-Verlag, 1979. 258 p. (Lecture Notes in Economics and Mathematical Systems, Vol. 166).

77. Cuninghame-Green R.A. Minimax algebra and applications // Fuzzy Sets and Systems. 1991. Vol. 41. P. 251−267.

78. Ermakov S.M., Krivulin N.K. Efficient algorithms for tandem queueing system simulation // Applied Mathematics Letters. 1994. Vol. 7, N 6. P. 4549.

79. Ermakov S.M., Melas V.B., Krivulin N.K. Efficient methods of queueing systems simulation // Modelling and Simulation 1991: Proc. 1991 Europ. Simulation Multiconf., Copenhagen, Denmark, June 17−19, 1991 / Ed. by E. Mosekilde. P. 8−20.

80. Glasserman P., Yao D.D. Stochastic vector difference equations with stationary coefficients // Journal of Applied Probability. 1995.Vol. 32. P. 851 866.

81. Glasserman P., Yao D.D. Subadditivity and stability of a class of discrete-event systems // IEEE Transactions on Automatic Control. 1995.Vol. 40, N 9. P. 1514−1527.

82. Gondran M., Minoux M. Linear algebra in dioids: A survey of recent results // Annals of Discrete Mathematics. 1984. Vol. 19. P. 147−164.

83. Hartley H.O., David H.A. Universal bounds for mean range and extreme observation // The Annals of Mathematical Statistics. 1954. Vol. 25. P. 8599.

84. Heidergott B. Max-Plus linear stochastic systems and perturbation analysis. New York: Springer-Verlag, 2007. 320 p. (The International Series on Discrete Event Dynamic Systems, Vol. 15).

85. Heidergott B., Olsder G.J., van der Woude J. Max-Plus at work: Modeling and analysis of synchronized systems. Princeton: Princeton University Press, 2006. 226 p.

86. Jean-Marie A. Analytical computation of Lyapunov exponents in stochastic event graphs // Performance Evaluation of Parallel and Distributed Systems. Solution Methods: Proc. 3rd QMIPS Workshop. Amsterdam: CWI, 1994. P. 309−341. (CWI Tracts, Vol. 106).

87. Kingman J.F.C. Subadditive ergodic theory // The Annals of Probability. 1973. Vol. 1. P. 883−909.

88. Kleene S.C. Representation of events in nerve nets and finite automata // Automata Studies / Ed. by C.E. Shannon and J. McCarthy. Princeton: Princeton University Press, 1956. P. 3−42. (Annals of Mathematics Studies, N 34).

89. Krivulin N.K. Unbiased estimates for gradients of stochastic network performance measures // Acta Applicandae Mathematicae. 1993. Vol. 33. P. 21−43.

90. Krivulin N.K. A recursive equations based representation for the G/G/m queue // Applied Mathematics Letters. 1994. Vol. 7, N 3. P. 73−78.

91. Krivulin N.K. Using max-algebra linear models in the representation of queueing systems // Proc. 5th SIAM Conf. on Applied Linear Algebra, Snowbird, UT, June 15−18, 1994 / Ed. by J.G. Lewis. Philadelphia: SIAM, 1994. P. 155−160.

92. Krivulin N.K. Recursive equations based models of queueing systems // Proc. 1994 SCS Europ. Simulation Symp., Istanbul, Turkey, Oct. 9−12, 1994 / Ed. by A.R. Kaylan, A. Lehmann, T.I. Oren. San Diego: SCSI, 1994. P. 252 256.

93. Krivulin N.K. Unbiased gradient estimation in queueing networks with parameter-dependent routing // Proc. Intern. Conf. on Control and Information 1995 / Ed. by Wong Wing-Shing. Hong Kong: The Chinese University Press, 1995. P. 351−356.

94. Krivulin N.K. Algebraic models in simulation of tandem queueing systems // Proc. 1995 Summer Computer Simulation Conf. / Ed. by T.I. Oren, L.G. Birta. San Diego: SCS, 1995. P. 9−14.

95. Krivulin N.K. A max-algebra approach to modeling and simulation of tandem queueing systems // Mathematical and Computer Modelling. 1995. Vol. 22, N 3. P. 25−37.

96. Krivulin N.K. An algebraic approach in modelling and simulation of queueing networks // Circuits, Systems and Computers'96: Proc. Intern. Conf., July 15−17, 1996, Piraeus, Greece. Hellenic Naval Academy, 1996. Vol. 2. P. 668−672.

97. Krivulin N.K. Max-plus algebra models of queueing networks // Proc. Intern. Workshop on Discrete Event Systems (WODES96), University of Edinburgh, UK, Aug. 19−21, 1996. London: IEE, 1996. P. 76−81.

98. Krivulin N.K. The max-plus algebra approach in modelling of queueing networks // Proc. 1996 SCS Summer Computer Simulation Conf., July 2125, 1996, Portland, OR / Ed. by V.W. Ingalls, J. Cynamon, A. Saylor. San Diego: SCS, 1996. P. 485−490.

99. Krivulin N.K. Bounds on mean cycle time in acyclic fork-join queueing networks // Proc. 4th Workshop on Discrete Event Systems (WODES98), Cagliari, Italy, Aug. 26−28, 1998. London: IEE, 1998. P. 469−474.

100. Krivulin N.K. Monotonicity properties and simple bounds on the mean cycle time in acyclic fork-join queueing networks // Recent Advances in Information Science and Technology / Ed. by N. Mastorakis. Singapore: World Scientific, 1998. P. 147−152.

101. Kriuvlin N.K. Evaluation of Lyapunov exponent in generalized linear dynamical models of queueing networks // Proc. MATHMOD 09 Vienna Full Papers CD Volume (I. Troch, F. Breitenecker, eds.). Vienna: ARGESIM, 2009. P. 706−717.

102. Krivulin N.K., Nevzorov V.B. On evaluation of the mean service cycle time in tandem queueing systems // Applied Statistical Science V / Ed. by M. Ahsanullah, J. Kennyon, S.K. Sarkar. N.Y.: Nova Science Publishers, 2001. P. 145−155.

103. Lindley D. V. The theory of queues with single server // Mathematical Proceedings of the Cambridge Philosophical Society. 1952. Vol. 48. P. 277 289.

104. Mahr B. Iteration and summability in semirings // Annals of Discrete Mathematics. 1984. Vol. 19. P. 229−256.

105. Marcinkiewi. cz J., Zigmund A. Sur les fonctions independantes // Fundamenta Mathematicae. 1937. Vol. 29. P. 60−90.

106. Matveenko V. Development with positive externalities: The case of the Russian economy // Journal of Policy Modeling. 1995. Vol. 17, N 3. P. 207 221.

107. Matveenko V.D. Optimal paths in oriented graphs and eigenvectors in max—® systems // Discrete Mathematics and Applications. 2009. Vol. 19, N 4. P. 389−409.

108. Olsder G.J., Resing J.A.C., De Vries R.E., Kea/ne M.S., Hooghiemstra G. Discrete event systems with stochastic processing times / / IEEE Transactions on Automatic Control. 1990. Vol. 35, N 3. P. 299−302.

109. Olsder G.J., Roos C. Cramer and Cayley-Hamilton in the Max algebra // Linear Algebra and Its Applications. 1988. Vol. 101. P. 87−108.

110. Zimmermann U. Linear and combinatorial optimization in ordered algebraic structures. Amsterdam: North-Holland, 1981. 390 p. (Annals of Discrete Mathematics, Vol. 10).