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

Кривулин, Николай Кимович

Математическое моделирование, численные методы и комплексы программ

автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Методы идемпотентной алгебры в задачах моделирования и анализа сложных систем

доктора физико-математических наук: Кривулин, Николай Кимович
город: Санкт-Петербург
год: 2009
специальность ВАК РФ: 05.13.18
цена: 450 рублей

Диссертация по информатике, вычислительной технике и управлению на тему «Методы идемпотентной алгебры в задачах моделирования и анализа сложных систем»

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

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

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

КРИВУЛИН Николай Кимович

0034Э0955

МЕТОДЫ ИДЕМПОТЕНТНОЙ АЛГЕБРЫ В ЗАДАЧАХ МОДЕЛИРОВАНИЯ И АНАЛИЗА СЛОЖНЫХ СИСТЕМ

05.13.18 — Математическое моделирование, численные методы и комплексы программ

АВТОРЕФЕРАТ

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

2 8 ЯНБ 20ш

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

003490955

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

Научный консультант:

доктор физико-математических наук, профессор РОМАНОВСКИЙ Иосиф Владимирович

Официальные оппоненты:

доктор физико-математических наук, профессор ДЕМЬЯНОВ Владимир Федорович (Санкт-Петербургский государственный университет)

доктор физико-математических наук, МАТВЕЕНКО Владимир Дмитриевич (Санкт-Петербургский экономико-математический институт РАН)

доктор физико-математических наук, профессор СОКОЛОВ Андрей Владимирович (Институт прикладных математических исследований Карельского НЦ РАН)

Ведущая организация: Финансовая академия при Правительстве РФ

1 8.02.2010 1 5- 3 0

Защита состоится "_"_20_г. в_часов на заседании

совета Д212.232.51 по защите докторских и кандидатских диссертаций при Санкт-Петербургском государственном университете по адресу: 198504, Санкт-Петербург, Петродворец, Университетский пр., 28, математико-механический факультет, ауд. 405.

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

? Я 1? 7004

Автореферат разослан 1<" сиид 20_г.

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

Даугавет И.К.

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

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

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

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

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

Различные аспекты теории и применения идемпотентной алгебры при решении прикладных задач исследовали П.И. Дудников, С.Н. Самборский, В.Д. Матвеенко, C.JÎ. Блюмин, R.A. Cuninghame-Green, В.A. Carré, U. Zimmermann, F. Baccelli, G.J. Olsder, J.S. Golan, В. Heidergott, а также другие российские и зарубежные авторы.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Апробация работы. Основные результаты обсуждались на семинарах на математико-механическом факультете и факультете менеджмента Санкт-Петербургского государственного университета, в Санкт-Петербургском экономико-математическом институте РАН, Санкт-Петербургском отделении Математического института им. В.А. Стек-

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

Результаты представлены на следующих научных конференциях: 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-00760, 04-01-00840, 06-01-00763, 09-01-00808.

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

Публикация результатов. Результаты исследований отражены в работах [17-75], включая статьи [17-28], опубликованные в изданиях, входящих в перечень ВАК на момент публикации, статьи [29-32] в изданиях, включенных в систему цитирования Web of Science (Science Citation Index Expanded), а также монографию [33].

В работах [27,28,51] соискателем осуществлена постановка задачи, построение и анализ модели системы, а также получены верхние оцен-

ки среднего времени безотказной работы системы. Соавтором построены нижние оценки, разработаны программные средства и проведены численные расчеты. В [29, 53] соискателем выполнено построение и анализ сложности алгоритмов имитационного моделирования систем, а соавтором — постановка задачи и анализ методов решения.

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

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

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

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

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

Глава 1. Идемпотентная алгебра

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

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

Пусть X — числовое множество. Рассмотрим коммутативное полукольцо с нулем и единицей (X, 0 Д, ф, <8>), в котором сложение ф идем-потентно, а каждый ненулевой элемент имеет обратный по умножению

Такое полукольцо обычно называют идемпотентным полуполем.

На идемпотентном полуполе обычным путем вводится операция возведения в целую, а затем — в рациональную степень.

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

На полуполе Ж определен частичный порядок так, что х < у тогда и только тогда, когда хфу = у. Предполагается, что X всегда можно дополнить элементом оо таким, что х < оо для всякого х € Ж.

Введем на X функцию расстояния р. Для любых х, у ф С положим

р{х,у) = у~1х®х~1у. (1)

Одним из примеров полуполей рассматриваемого типа является ^шах,+ = (К и {—оо}, —оо, 0, тах,+}. В полуполе Ктах,+ для всех х, у е К функция (1) совпадает с обычной метрикой й{х,у) — \х — у\.

В §1.2 изучается векторный полумодуль над идемпотентным полуполем. Операциям полумодуля дается наглядная геометрическая интерпретация на плоскости в декартовой системе координат. Обсуждается свойство линейной зависимости векторов. На полумодуле вводится метрика на основе метрики (1) для скалярного полукольца.

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

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

Изучаются условия существования обратной матрицы. Для любой матрицы А = (а^) определяется псевдообратная матрица А~ — (а^) с элементами а~ = если а^ ф 0, и а~- = 0, если а^ = 0.

На основе метрики (1) вводится функция расстояния для матриц.

В §1.4 дается общий вид линейного уравнения, а также двух частных случаев, которые называются уравнениями 1-го и 2-го рода.

Глава 2. Линейные уравнения 1-го рода

Многие приложения идемпотентной алгебры приводят к задаче решения относительно неизвестного вектора жбХ" уравнения

Ах = Ь, А е Хтхп, Ь е Жт. (2)

Учитывая, что уравнение (2) можно рассматривать как выражение линейной зависимости между векторами, методы его анализа и решения представляют также определенный теоретический интерес.

Задача решения уравнения и ее связь с линейной зависимостью векторов изучалась в работе H.H. Воробьева [1]. В случае матрицы с ненулевыми элементами предложен метод разрешающих покрытий на основе анализа подмножеств строк некоторой приведенной матрицы.

В работе [11] теория и методы решения уравнения получили дальнейшее развитие, направленное, в частности, на решение уравнений с матрицей, которая может иметь нулевые элементы. Найдено условие существования решений уравнения в виде векторного равенства.

В работах [8,16] применяется алгебраический подход с использованием понятия подрешения уравнения и операции вычисления остатка, в терминах которой дано выражение для максимального решения. В [15] вводится некоторый аналог определителя матрицы, называемый доминантом, и предлагается метод решения уравнений при помощи аналога правила Крамера с заменой определителя на доминант.

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

В §2.1 вычисляется расстояние от произвольного вектора Ь е Жгп до линейной оболочки А системы векторов ai,...,an € Xm. Пусть А — (ai,..., ап) — матрица, составленная из векторов системы. Рассмотрим задачу определения величины

p(A,b) — min p(Ax,b). хежп

Наряду с матрицей А введем матрицу А следующим образом. Пусть вектор b ф 0 имеет нулевые координаты. Тогда в качестве А берется матрица А, у которой заменены все столбцы с ненулевыми элементами на пересечении со строками, соответствующими нулевым координатам вектора Ь. В матрице А все элементы этих столбцов, кроме тех элементов, которые лежат на пересечении с указанными строками, приравниваются к нулю. Если Ъ > 0, то полагают А = А.

Матрица А называется согласованной с вектором Ь. Показано, что задачи определения расстояния от Ь до линейных оболочек столбцов матриц А и А эквивалентны в том смысле, что при всех ж € X™ выполняется равенство р(Ах,Ь) = р(Ах,Ь). Учитывая этот результат, далее всегда предполагается, что матрица А и вектор Ь согласованы.

При условии, что матрица А является регулярной, определяется величина

А(А,Ь) = (А(Ь~А)-)-Ь.

Если матрица А — нерегулярная, то полагают Д(А, Ь) = оо.

Доказано, что для любой матрицы А и вектора Ь ф D выполняется

р(А,Ь) = л/А(Л,Ь).

При этом минимум р(Ах,Ь) достигается при х — у/А(Л,b)(b~A)~.

Одно из следствий состоит в том, что для любой матрицы А и вектора b ф 0 решение неравенства Ах < b имеет вид х < (Ь~А)~.

Кроме того, вектор b принадлежит линейной оболочке Л тогда и только тогда, когда A(A,b) = 1. При этом Ъ = Ах, где х = (Ъ~А)~.

Последний результат применяется в §2.2 для изучения линейной зависимости векторов. Пусть A(¿) = (aj,..., a¿_i, a¿+1,..., ап) — матрица, полученная из А = (ai,..., ап) путем удаления столбца a¿,

<5(Л)= min А(А{г},а{).

Установлено, что система векторов a1,...,an является линейно независимой тогда и только тогда, когда ¿(Л) > 1.

В §2.3 даны условия существования и единственности решения уравнения (2), а также вид общего решения этого уравнения.

Теорема 2.1. Уравнение (2) имеет решение тогда и только тогда, когда Д(A,b) = 1. При этом х = (Ь~А)~ является максимальным решением. Если столбцы матрицы А образуют минимальную систему, порождающую вектор Ь, то других решений нет.

Пусть I — набор индексов столбцов матрицы А, которые образуют минимальную порождающую b систему векторов, G¡ — диагональная матрица, у которой в строке i на диагонали стоит число 0, если г € I, и 1, если i £ I. Обозначим множество всех таких наборов I через X.

Теорема 2.2. Пусть уравнение (2) разрешимо. Тогда его общим решением является семейство решений

xi = (Ь~А ®vTGi)~, weX", leí.

Рассмотрено решение системы, состоящей из уравнения Ах = Ь и неравенства Сх < d, а также решение уравнения Ах ф d = b.

Представлены примеры практических задач сетевого планирования и управления, которые приводят к решению уравнения (2).

Глава 3. Однородное и неоднородное уравнения 2-го рода

Одним из основных объектов исследования в идемпотентной алгебре являются уравнения 2-го рода относительно вектора х € X™

Ах = х, АхфЬ = х, ЛеХпх", 6еХ". (3)

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

В существующей литературе задача решения однородного уравнения обычно сводится к проблеме собственных значений матрицы А. Иногда эта задача рассматривается в контексте анализа неоднородного уравнения, которое становится однородным при 6 = 0.

Большинство известных результатов (см., например, [4,12,16]) связано с исследованием условий существования решений неоднородного уравнения и определением его минимального решения. Условия существования и единственности решения обычно формулируются в терминах теории графов в виде ограничений на значения весов циклических путей в графе, соответствующим матрице А.

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

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

В §3.1 для любой квадратной матрицы А € Жпхп определяется величина

ЪА =

т=1

Показано, что для всякого вектора х € X" справедливы следующие утверждения:

1) если Тг А < 1, то х~Ах > Тг Л;

2) если Тг А > 1, то х'Ах > (ТтЛ)1/".

Вводятся матрицы

А+ = 1®А®---®Ап~\ Лх = ЛЛ+ = Ае---фАп.

В работе [9] Б.А. Kappe установил, что при условии Тг А < 1 для любого целого к > 0 выполняется неравенство Ак < А+. В настоящей главе получено обобщение неравенства Kappe в следующем виде.

Пусть Тг Л ф (D. Тогда при любом целом к > 0 справедливы следующие утверждения:

1) если Тг Л < 1, то Ак < (Тг Л)<*+1>/п-М+;

2) если Тг Л > 1, то Ак < (Тг А)кА+.

Рассмотрим произвольную матрицу Л. Пусть af и а* обозначают столбцы с индексом г матриц Л+ и Лх. Для представления общего решения уравнений введем матрицу Л* со столбцами а*. При условии Tl-Л = 1 определим а* = af, если af = af, и а* = (D, если ф агх, для всех г = 1,..., гг. В случае Тг Л ф 1 положим А* = 0.

Далее в §3.2 определяется общий вид однородного и неоднородного уравнений и даются необходимые определения.

Решение уравнений в случае неразложимой матрицы Л изучается в §3.3. Для однородного уравнения получен следующий результат.

Пусть х — общее решение однородного уравнения с неразложимой матрицей Л. Тогда справедливы следующие утверждения:

1) если Тг Л = 1, то х = A*v для всех v € X";

2) если Тг Л ф 1, то имеется только тривиальное решение х = 0.

Для неоднородного уравнения устанавливается, что такое уравнение с неразложимой матрицей Л имеет решение тогда и только тогда, когда выполняется хотя бы одно из условий: ТгЛ < 1 и/или Ъ = 0. При этом х = А+Ь является минимальным частным решением, а общий вид решения уравнения определяется в теореме 3.1.

Теорема 3.1. Пусть решение неоднородного уравнения с неразложимой матрицей Л существует, х — общее решение уравнения.

Тогда справедливы следующие утверждения:

1) если Тг Л < 1, то имеется единственное решение х = Л+Ь;

2) если Тг Л = 1, то х = А+Ь ® A*v для всех v е X";

3) если Тг Л > 1, то имеется только тривиальное решение х = 0.

Полученные результаты решения однородного и неоднородного

уравнений обобщаются в §3.4 на случай разложимых матриц.

В качестве следствия полученных результатов в §3.5 найдены решения однородного Ах < х и неоднородного Ах ф Ь < х неравенств.

В §3.6 рассмотрены задачи совместного решения уравнений и неравенств разных типов. В §3.7 обсуждаются вопросы определения размерности пространства решений уравнений и неравенств.

Примеры приложений полученных результатов для решения задач сетевого планирования и управления представлены в §3.8.

Глава 4. Собственные значения и векторы матрицы

Одно из первых исследований проблемы собственных значений было проведено в работе H.H. Воробьева [1|, в которой собственные значения и векторы находятся прямо из уравнения Ах = Хх путем его решения относительно Л и ж. При доказательстве существования собственного вектора использовалась теорема Брауэра о неподвижной точке. Для нахождения собственных векторов применялась процедура на основе анализа соответствующего матрице контурного графа.

Подход к решению проблемы собственных значений на основе изучения контурных графов развивался в [5]. Похожая техника, которая сочетает алгебраический подход и методы теории графов, применялась также в работах [8,11,16]. В весьма общем виде проблема собственных значений решается в работах [2,4,7] в рамках развитого в этих работах идемпотентного функционального анализа. Подходы, которые опираются на различные способы задания идемпотентного аналога характеристического многочлена и его анализ, рассматриваются в [12,15].

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

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

Далее в §4.2 для произвольной матрицы А G Жпхп обычным путем вводятся собственное число Л € X и собственный вектор х G X".

Характеристическим многочленом матрицы А называется функция — Тг(Л-1у1) относительно параметра Л € X, а характеристическим уравнением — уравнение х(^) = 1В §4.3 решается проблема собственных значений для неразложимой

матрицы. Доказано следующее утверждение.

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

В виде следствия из теоремы показано, что для любой неразложимой матрицы А существует единственное собственное число

Л = 0tr1/m(ylm). (4)

m=1

Устанавливается, что собственный вектор неразложимой матрицы А, соответствующий А, имеет вид х = A\v, где v е X", А\ = А~1А.

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

В §4.5 получено дальнейшее обобщение неравенства Kappe. Доказано, что для любой матрицы А и целого к > 0 выполняется

п-1

Ак < 0Ак-1А1, 1=0

где число А вычисляется в соответствии с формулой (4).

В §4.6 определяется спектральный радиус в(А) матрицы А как ее максимальное (в смысле отношения порядка, индуцированного идем-потентным сложением) собственное число. Показано, что спектральный радиус всегда вычисляется по формуле (4).

Некоторые экстремальные свойства спектрального радиуса изучаются в §4.7. Пусть А — неразложимая матрица, А — ее собственное число. Тогда имеют место равенства

min х~ Ах = А, min (Ах)~х = А-1,

ж€Х'+' хежу

причем минимум достигается на собственном векторе матрицы А.

Этот результат обобщается на случай разложимых матриц.

В §4.8 рассматриваются задачи вычисления спектрального радиуса для определенных типов матриц, включая симметричные матрицы,

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

Затем изучаются матрицы единичного ранга. Исследована задача приближения произвольной матрицы с помощью матрицы ранга 1.

Пусть А — регулярная матрица, ß = р(АА~) — спектральный радиус матрицы АА~~. Тогда имеет место равенство

min р(А,ху~) = д1/2,

причем минимум достигается, когда х и у = ц~112А~х — собственные векторы матриц АА" и А~А, соответствующие ц.

В §4.9 даны примеры решения задач моделирования экономического развития, планирования и управления производством.

Глава 5. Сходимость итераций линейного оператора

Важным результатом спектральной теории линейных операторов в идемпотентной алгебре является теорема сходимости, которая устанавливает, что для любого оператора А последовательность \\Ак]\1^к сходится при к —> оо к спектральному радиусу оператора.

К числу первых результатов в этой области относится работа И.В. Романовского [6], в которой исследовались асимптотические свойства решений задачи динамического программирования. С использованием теоретико-графического подхода было показано, что рассматриваемый предел существует и вычисляется по формуле (4).

В то же время в работе [1] было установлено, что величина (4) является максимальным собственным числом матрицы А.

Для операторов, действующих в векторном полумодуле над произвольным идемпотентным полукольцом, доказательство теоремы сходимости в общем виде было получено В.П. Масловым и В.Н. Коло-кольцовым [4] с применением развитой ими теории на основе сочетания классического и идемпотентного анализа.

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

В §5.1 показано, что при всех целых к > О для любой матрицы А и диагональной матрицы D выполняется тождество

{А © D)k = 0 ApD9Ar.

p+q+r—k

В §5.2 получен ряд неравенств для собственного числа, следа и нормы произвольной матрицы, все элементы которой отличны от нуля. Пусть матрица А не имеет нулевых элементов, А — ее собственное число. Тогда для любого целого к > 0 выполняются неравенства

Afc < \\Ак\\ < Afc||AA-||, Afc||yL4~||_1 < trAk < Xk.

Основной результат главы составляют теоремы 5.1 и 5.2, которые представлены в §5.3. В этих теоремах устанавливается, что для любой матрицы А существуют пределы

lim ||Afc||1/fc = е{А), lim ff) tr1'"1^"1) = ¿»(Л).

m—1

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

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

Глава 6. Линейные стохастические системы

При анализе реальных систем в технике, экономике, управлении и других областях находят применение стохастические динамические модели, в которых эволюция состояний системы описывается при помощи линейных в смысле полукольца ¡RtnaX;+ векторных уравнений. Одной из важных характеристик таких систем является средняя асимптотическая скорость роста вектора состояний, которую часто называют показателем Ляпунова системы.

Условия существования показателя Ляпунова изучались в работах [8,10], где рассматривались системы с матрицами, которые удовлетворяют некоторым дополнительным ограничениям (например, матрицы без нулевых элементов или неразложимые матрицы).

Вычисление значения показателя Ляпунова обычно оказывается довольно сложной задачей. Известные решения по существу ограничиваются случаем систем с матрицей малой размерности (как правило, с матрицей второго порядка), элементы которой независимы и имеют одинаковое распределение вероятностей [8,10,14].

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

В §6.1 исследуются свойства математического ожидания, связанные со скалярными и матричными операциями в полукольце Ктах,+-

В §6.2 рассматривается стохастическая динамическая система, эволюция которой описывается в полумодуле IR," ах>+ уравнением

х(к) = А(к)х(к - 1), к= 1,2,..., (5)

где А(к) — случайная матрица, х(к) — вектор состояний системы.

Предполагается, что {А{к)\к > 1} — последовательность независимых и одинаково распределенных случайных матриц, а координаты начального вектора х(0) с вероятностью 1 (с в. 1) ограничены.

Пусть Аь = А{к)---А{1). Показателем Ляпунова системы называется средняя асимптотическая скорость роста вектора состояний, которая в R[[,ax + определяется как предел

Л - lim ||a:(fc)||1/fc = lim \\Ак\\Чк.

К—»OO К—»oo

Получены условия существования предела в следующей форме.

Теорема 6.3. Пусть {А(к)\к > 1} — стационарная последовательность случайных матриц, Е||Лх|| < оо и ß(EAi) > 0.

Тогда существует конечное число А такое, что

lim ИЛИ1'* = А с в. 1, lim ЕЦ^-Ц1^ = А.

fc—»oo /с—»oo

Примеры вычисления показателя Ляпунова для систем с матрицами частного вида рассмотрены в §6.3. Показано, для случая диагональной матрицы А(к) показатель Ляпунова имеет величину А = tr(EAi). Если А(к) — матрица подобия, то А = Е|| Aj ||. Для матрицы единичного ранга А{к) = u(k)vT(k) выполняется А = Е[ит(1)и(2)].

В §6.4 исследуется система с треугольной матрицей. Вычисление показателя Ляпунова опирается на использование следующего неравенства для нормы произведения треугольных матриц.

Пусть матрица системы имеет порядок п и представлена в виде А(к) = D{k) © Т(к), где D(k) — диагональная матрица, а Т(к) — нильпотентная матрица с индексом г + 1.

Вводится матрица D(l,m) = D(l + 1) ■ ■ - D(m), если m > I, и D{l,m) = I в противном случае. Диагональные элементы матрицы D(l,m) обозначаются через di(l,m), i=l,...,n.

Тогда при любом к = 1,2,... справедливо неравенство

||А||< (ф||т(0||©1) ((g) ф dSM

\l = 1 У \г=1 0 <1<ш<к

Другие вспомогательные результаты составляют оценки для средних значений максимумов сумм независимых и одинаково распределенных случайных величин £1,. ■. Пусть = -----Ь£т.

Тогда, в частности, если Е^ = 0 и < оо, то справедлива оценка

Основной результат состоит в следующем.

Теорема 6.4. Если А(к) — треугольная матрица, то А = ^ЕЛх).

В §6.6 предложен метод вычисления показателя Ляпунова на основе разложения матрицы системы. Применение этого метода в случае матрицы неполного ранга дает следующий результат.

Теорема 6.5. Пусть для матрицы А (к) существует скелетное разложение А(к) = В(к)С(к) с независимыми сомножителями такое, что матрица С(к)В(к) является треугольной. Тогда А = 1г(Е[С(1)В(1)]).

Глава 7. Экспоненциальные системы второго порядка

Рассмотрим стохастическую динамическую систему, эволюция которой описывается в терминах полукольца Ктах,+ уравнением (5).

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

Существующие результаты в этой области включают решения, полученные в работах [8,10,14] для систем с матрицей второго порядка, случайные элементы которой независимы и имеют общее непрерывное (экспоненциальное или нормальное) или дискретное распределение.

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

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

В §7.1 вводится модель системы, динамика которой описывается уравнением (5), для которого

Е тах

0 <1<т<к

|0ш| < 4^2(2^ - 1)Е#

Предполагается, что каждая из последовательностей {ак\к > 1}, {Рк\к > 1}, {7*;!^ > 1} и {&к\к > 1} состоит из независимых случайных величин, которые имеют общее экспоненциальное распределение с параметрами д, г/, а и т соответственно. Случайные величины ак, Ри 7т и 5п являются независимыми при любых к,1,т,п.

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

В §§7.3-7.7 предложенный подход применяется для вычисления показателя Ляпунова для систем с матрицами, у которых некоторые элементы являются константами, равными арифметическому нулю.

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

Рк \ , 4г/2 + 7уд + 4ст2

О ) ' - б1/<г(1/ + <т) '

О \ . _ д4 + д3т + д2т2 + дт3 + т4

бк )' ~~ дт(д + т)(д2 + т2) ;

/Зк \ 2д4 + 7дУ + ЮдУ + 11/л/3 + 4г/4

О У' _ д1/(д+г/)2(3д + 4г/)

Для системы с матрицей с одним нулем на диагонали

исследованы два случая. При условии ст = д выполняется

л_ 48д5 + 238дУ + 495д3г/2 + 581дУ + 326дИ + 68г/5 2дг/(36д4 + 147д3г/ + 215д2г/2 + 130дг/3 + 28И)

Если сг = г/, то результат имеет вид Л = Р(д, 1/)/<5(д, г/), где

Р(д, р) = 15д8 + 152д7^ + 624д V + 1382д5!/3 + 1838д 4И+

+ 1592д3^5 + 973д V + 384дг/ + 64гД д(д, I/) = д!/(д + 1/)2(12д5 + 97д41/ + 286д V + З97д21/3+ + 256дг/4 + 641/5).

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

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

А = q[ui + q%u>2,

где wi = (wio,wn,a>i2,w13)T и ш2 = — векторы,

которые являются решением системы обыкновенных уравнений

{I-Wn)u)l- Wi2U>2= О, -W21W1 + (I - 1^22)^2 = О,

Ию + W20 = 1

при условии, что определенным образом заданы векторы q\ и <72, а также квадратные матрицы W\\, W''12, №21 и W22•

Для указанных векторов и матриц получены выражения для их элементов в виде рациональных функций от параметров распределений вероятностей элементов матрицы А(к).

В §7.12 рассматривается система с матрицей, для которой т = /л, и — V. Найденное при этом решение совпадает с результатом в [14].

В заключение в §7.13 приведены примеры приложения полученных результатов к решению практических задач.

Глава 8. Границы и оценки для показателя Ляпунова

Учитывая, что решение задачи вычисления показателя Ляпунова известно только для некоторых частных случаев стохастических динамических систем, определенный интерес представляет разработка процедур оценивания этой величины. К числу результатов в этой области относится верхняя граница в работе [8], построенная на основе результатов теории вероятностей больших уклонений.

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

В §8.1 рассматривается динамическая система (5), для которой предполагается, что последовательность {А(к)\к > 1} состоит из независимых матриц и удовлетворяет условию теоремы 6.3.

Получены границы для величины А в виде двойного неравенства

£»1/ш(ЕЛ„) < А < Epm||1/m, m > 1.

Для случая, когда матрица системы является регулярной, в §8.2 предложена нижняя оценка

А>||(Ь4т1)-|Г1/т, т> 1.

В §8.3 рассматривается система с матрицей без нулевых элементов. Показано, что для такой системы имеет место неравенство

А>Е||((ЕЛГ)1)-Лт||1/((+т) l,m > 1.

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

Пусть выполняется неравенство А(к) < u(k)vT(k), где и(к) и v(k) — случайные векторы, к = 1,2,... Каждая последовательность {u(fc)|fc > 1} и {v(k)\k > 1} состоит из независимых и одинаково распределенных случайных векторов, E||u(fc)|| < оо и E||u(fc)[| < оо. Тогда справедливо неравенство

А < Е[ит(1)м(2)].

Аналогичным путем можно получить нижнюю оценку, выбирая и(к) и v(k) так, чтобы выполнялось неравенство А(к) > u(k)vT(k).

Построение оценок опирается на использование границ для произвольной матрицы А в виде L < А < U, где L и U — матрицы единичного ранга. В частности, для верхней границы берется матрица U = uvT, где v = и~А, а вектор и находится как решение задачи

min <р(и:А)

иёХ™

для некоторого подходящего критерия уэ.

В §8.5 рассмотрены верхние границы, которые определяются выбором в качестве критерия уз функций

<p1(u-,A)=p(A,U), <р2(и;А) = ффи^ЧИ,

! = 1

где щ — координата г вектора и, п3 — строка з матрицы А.

Показано, что минимум равен спектральному радиусу д(АА~) и достигается на собственном векторе матрицы АА~, который соответствует д(АА~). Кроме того, выполняется равенство

тт^2(гх;А) = 0фК||1/2|к||1/2,

+ ¿=1 з>г

где минимум дает вектор и с координатами щ = Ца'Ц1/2, г = 1,... ,п.

Аналогичным образом строятся нижние границы.

В §8.6 приведены примеры вычисления верхних и нижних оценок для системы с матрицей второго порядка, элементы которой независимы и имеют экспоненциальное распределение с единичным средним.

Глава 9. Алгебраические модели сетей с очередями

Модели сетей с очередями с дополнительными операциями разъединения и объединения требований, которые часто называют сетями с синхронизацией, находят широкое применение при анализе производственных систем, бизнес-процессов, сетей передачи сообщений, вычислительных систем и т.п. [8,13].

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

В §9.1 рассматривается модель сети, состоящей из п узлов, в каждом из которых имеется обслуживающее устройство и накопитель, предназначенный для размещения требований. Топологию сети задает ориентированный граф 9 = {У, Е), где У = {1,..., п), Е с У х У.

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

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

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

В начальный момент времени все обслуживающие устройства сети свободны, а в накопителе узла г имеется с^ > 0 требований. Емкость накопителя определяется величиной Ь{ > 1.

В §9.2 показано, как динамика сети с неограниченной емкостью накопителей описывается при помощи динамического уравнения, линейного в смысле полукольца Ктах,+- Сначала вводятся обозначения

х(к) = (х^к),.. .,хп(к))т, Тк = ..., тпк),

где х^к) — время завершения, а цк — длительность к-то обслуживания в узле г. Пусть £¿(0) = 0 и х^к) = —оо для всех к < 0.

Для любого т. = 0,1,..., М, где М = тах{сг|с^ < оо, г = 1,..., п}, определяется граф <?т = (У,Ет), где Ет = {(г,]) € Е\с^ = га}, а его матрица смежности с элементами 0 и 1 обозначается через Ст.

Доказано следующее утверждение. Пусть граф <5о является ациклическим, г — наибольшая длина пути в этом графе. Тогда вектор удовлетворяет динамическому уравнению в К^ах +

х(к) = 0 Ат{к)х(к - т), (6)

т=1

где

А1(к) = (1®%С1)гТк(1®СТ), (7)

Ат{к) = {I (ВГ^УЪС^ т = 2,...,М. (8)

В §9.3 полученный результат распространяется на сети с конечной емкостью накопителей. Определяется число М = тах{М], Л/г}, где Л/1 = тах{с^|сг < оо, г = 1,..., ?г}, Л/г = тах{Ьг|^ < оо, г = 1,..., п}.

При каждом т = 0,1,...,Л/ вводится матрица смежности #т для графа Нт = (У,Ет), где = {(¿,7) 6 = то}.

Тогда, если граф является ациклическим с длиной наибольшего пути г, то вектор ж(/г) удовлетворяет уравнению (6), где матрицы для производственного типа блокирования записываются в виде

Аг(к) = (/ © ТкС%)Т(Тк(1 Ф в1) ф Я0, (9)

А,п(к) = (/ ф )Г(71-С^ ф Ят), т = 2,..., М; (10)

а для коммуникационного — в виде

А1{к) = {1®ТкС1)гТк{1®С\ фЯг), (11)

Ат{к) = (1® ТквЪуТк^ © Нт), ш = 2,..., М. (12)

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

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

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

Глава 10. Стохастические модели систем с очередями

Применение аппарата идемпотентной алгебры оказывается достаточно полезным при решении задач оценки и вычисления значения показателя Ляпунова стохастических моделей систем с очередями. Такие задачи и методы их решения рассматривались в работах [8,13].

Настоящая глава содержит примеры применения моделей и методов идемпотентной алгебры при исследовании систем с очередями.

В §10.1 изучаются стохастические модели сетей с очередями, динамика которых описывается уравнением (6) с матрицами (7)-(8), (9)-(10), (11)—(12). Предполагается, что в такой модели диагональные элементы матрицы Тк являются неотрицательными случайными величинами, а также, что последовательность {Тк, к > 1} состоит из независимых одинаково распределенных матриц и Е||7!|| < оо.

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

Вначале строится нижняя оценка для среднего времени цикла обслуживания для всех рассматриваемых систем в виде Л > 1;г(Е71).

Затем доказана теорема 10.1, которая устанавливает, что для моделей ациклических сетей с неограниченными накопителями (6)-(8) эта оценка совпадает с соответствующим точным значением.

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

В §10.3 изучается задача оценки среднего времени безотказной работы системы с неограниченной емкостью накопителей, динамика которой описывается уравнением (5) с матрицей А(к) = (I ф ТкСт)гТк-

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

В качестве вспомогательных результатов получен ряд оценок для величины Е||Л<;|| среднего времени завершения цикла к.

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

о = Е||Лх||, /3 = ||ЕГГГ1, 7= ЦЕГ1Ц, 5= 0117111.

Тогда при условии у > /3 выполняется

Т>р(1- Рт)(а -Р)~Р Г- тРт) (7 - /3) + Т^—Ъ

V1-р / 1-Р

где т = [(а — /?)/(у — /?)_]. Если у — Р, то

Т>р(а+^).

Верхняя оценка записывается в виде Т <р ^ 1 ^ + г^ 7 + г(1

где

ед-¿(ч-^^а--л))*™.

при условии, что

2 fx ( к -1 1

erf х = —■= / exp(~t2)dt, М(р) = max < рк ^.

В заключение даны примеры расчета оценок для сети из п = 4 узлов с экспоненциальным распределением времени обслуживания при разных значениях параметров распределения и вероятности р.

Приложение

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

Литература

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

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

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

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

5. Matveenko V. Eigenvectors in systems with operations max and ® // 4 Московская международная конференция по исследованию операций (ORM2004): Москва, 21-24 сентября 2004 г.: Труды / Отв. ред. П.С. Краснощеков, А.А. Васин. М.: МАКС Пресс, 2004. С. 148150.

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

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

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

9. Carré В.A. An algebra for network routing problems // IMA J. Appl. Math. 1971. Vol. 7, N 3. P. 273-294.

10. Cohen 3.E. Subadditivity, generalized products of random matrices and operations research // SIAM Rev. 1988. Vol. 30, N 1. P. 69-86.

11. Cuninghame-Green R.A. Minimax algebra. Berlin: Springer-Verlag, 1979. 258 p.

12. Gondran M., Minoux M. Linear algebra in dioids: A survey of recent results // Ann. Discrete Math. 1984. Vol. 19. P. 147-164.

13. Heidergott B. Max-Plus linear stochastic systems and perturbation analysis. N.Y.: Springer-Verlag, 2007. 320 p.

14. 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.

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

16. Zimmerrnann U. Linear and combinatorial optimization in ordered algebraic structures. Amsterdam: North-Holland, 1981. 390 p.

ПУБЛИКАЦИИ АВТОРА ПО ТЕМЕ ДИССЕРТАЦИИ Статьи в журналах, рекомендованных ВАК

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

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

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

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

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

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

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

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

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

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

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

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

29. Ermakov S.M., Krivulin N.K. Efficient algorithms for tandem queueing system simulation // Appl. Math. Lett. 1994. Vol. 7, N 6. P. 45-49.

30. Krivulin N.K. Unbiased estimates for gradients of stochastic network performance measures // Acta Appl. Math. 1993. Vol. 33. P. 21-43.

31. Krivulin N.K. A recursive equations based representation for the G/G/m queue // Appl. Math. Lett. 1994. Vol. 7, N 3. P. 73-78.

32. Krivulin N.K. A max-algebra approach to modeling and simulation of tandem queueing systems // Math. Comput. Model. 1995. Vol. 22, N 3. P. 25-37.

Монографии

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

Другие публикации

34. Ермаков С.М., Каштанов Ю.Н., Кривулин Н.К., Мелас В.Б. Математические методы стохастического моделирования систем // Сб. избранных работ по грантам в области информатики, радиоэлектроники и систем управления / СПб.: Конкурсный центр грантов при С.-Петерб. гос. электротех. ун-те, 1994. С. 13-25.

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

36. Кривулин H.K. Несмещенное оценивание градиента в задачах оптимизации динамических систем с дискретными событиями // Математическое моделирование дискретных систем: Межвуз. сб. / Под ред. М.К. Чиркова. СПб: Изд-во С.-Петерб. ун-та, 1995. С. 199-219. (Вычислительная техника и вопросы кибернетики; Вып. 28)

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

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

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

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

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

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

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

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

45. Кривулин Н.К. Примеры построения моделей и решения задач на основе методов идемпотентной алгебры // Математические моде-

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

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

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

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

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

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

51. Кривулин Н.К., Милое Д.С. Оценивание среднего времени работы для одного класса сетей с очередями // Дискретные модели. Анализ, синтез и оптимизация / Под ред. М.К. Чиркова, С.П. Маслова. СПб: СПбГУ, 1998. С. 228-242. (Вычислительная техника и вопросы кибернетики; Вып. 29)

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

53. Ermakov S.M., Krivulin N.K. Efficient parallel algorithms for tandem queueing system simulation // Proc. 3rd Beijing Intern. Conf. on System Simulation and Scientific Computing: Delayed papers / Ed. by Xingren Wang et al. Beijing: CASS, 1995. P. 8-12.

54. Ermakov S.M., Mêlas V.B., Krivulin N.K. Efficient methods of queueing systems simulation // Modelling and Simulation 1991: Proc. 1991 Europ. Simulation Multiconf. / Ed. by E. Mosekilde. P. 8-20.

55. Güster D., Krivulin N.K. Modeling and performance evaluation of computer systems security operations // Proc. 4th St. Petersburg Work-

shop on Simulation (S.M. Ermakov, Yu.N. Kashtanov, V.B. Mêlas, eds.). St. Petersburg Univ., 2001. P. 233-238.

56. Krivulin N.K. An analysis of gradient estimates in stochastic network optimization problems // Model-Oriented Data Analysis: Proc. 3rd Intern. Workshop (W.G. Muller et al, eds). Heidelberg: Physical Verlag, 1993. P. 227-240.

57. Krivulin N.K. Using max-algebra linear models in the representation of queueing systems // Proc. 5th SI AM Conf. on Applied Linear Algebra / Ed. by J.G. Lewis. Philadelphia: SIAM, 1994. P. 155-160.

58. Krivulin N.K. Recursive equations based models of queueing systems // Proc. 1994 SCS Europ. Simulation Symp. / Ed. by A.R. Kaylan, A. Lehmann, T.I. Oren. San Diego: SCSI, 1994. P. 252-256.

59. Krivulin N.K. An algebraic approach to modeling and simulation of tandem queueing systems // Modeling and Simulation 1995: Proc. 1995 Europ. Simulation Multiconf. / Ed. by M. Snorek, M. Sujansky, A. Verbraeck. San Diego: SCSI, 1995. P. 271-275.

60. 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 Univ.' Press, 1995. P. 351-356.

61. 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.

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

63. Krivulin N.K. Max-plus algebra models of queueing networks // Proc. Intern. Workshop on Discrete Event Systems (WODES96). London: IEE, 1996. P. 76-81.

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

65. Krivulin N.K. Simple bounds on the mean cycle time in acyclic queueing networks // Proc. 3rd St. Petersburg Workshop on Simulation / Ed. by S.M. Ermakov, Y.N. Kashtanov, V.B. Melas. St. Petersburg: St. Petersburg Univ. Press, 1998. P. 331-337.

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

67. 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.

68. Krivulin N.K. Algebraic modelling and performance evaluation of acyclic fork-join queueing networks // Advances in Stochastic Simulation Methods / Ed. by N. Balakrishnan, V. Mêlas, S. Ermakov. Boston: Birkäuser, 2000. P. 63-81.

69. Krivulin N.K. Products of random matrices and queueing system performance evaluation // Proc. 4th St. Petersburg Workshop on Simulation (S.M. Ermakov, Yu.N. Kashtanov, V.B. Melas, eds.). St. Petersburg Univ., 2001. P. 304-309.

70. Krivulin N.K. Bounds on the state vector growth rate in stochastic dynamical systems // Proc. 5th St. Petersburg Workshop on Simulation (S.M. Ermakov, V.B. Melas, A.N. Pepelyshev, eds.). St. Petersburg Univ., 2005. P. 391-396.

71. Krivulin 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.

72. Krivulin N.K. Evaluation of the Lyapunov exponent for generalized linear second-order exponential systems // Proc. 6th St. Petersburg Workshop on Simulation. Vol. II. Ed. by S.M. Ermakov, V.B. Melas, A.N. Pepelyshev. St. Petersburg: VVM com. Ltd., 2009. P. 875-881.

73. Krivulin N.K., Güster D. Algebraic modeling and performance evaluation of business processes // New Models of Business: Managerial Aspects and Enabling Technology: Proc. 2nd Intern. Workshop / Ed. by N.K. Krivulin. St. Petersburg Univ., 2002. P. 212-220.

74. Krivulin N.K., Nevzorov V.B. Evaluation of the mean interdeparture time in tandem queueing systems // Proc. 4th St. Petersburg Workshop on Simulation (S.M. Ermakov, Yu.N. Kashtanov and V.B. Melas, eds.). St. Petersburg Univ., 2001. P. 310-315.

75. 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.

Подписано к печати 28.10.09. Формат 60 х 84 '/в. Бумага офсетная. Гарнитура Тайме. Печать цифровая. Печ. л. 2,00. Тираж 100 экз. Заказ 4542.

Отпечатано в Отделе оперативной полиграфии химического факультета СПбГУ 198504, Санкт-Петербург, Старый Петергоф, Университетский пр., 26 Тел.: (812) 428-4043, 428-6919

Оглавление автор диссертации — доктора физико-математических наук Кривулин, Николай Кимович

Введение

Глава 1. Идемпотентная алгебра

§1.1. Идемпотентные полукольцо и полуполе.

1.1.1. Свойства операций.

1.1.2. Отношение порядка.

1.1.3. Примеры идемпотентных полуколец.

1.1.4. Метрика.

1.1.5. Биномиальное тождество.

§1.2. Идемпотентный векторный полумодуль.

1.2.1. Свойства операций.

1.2.2. Линейная зависимость векторов.

1.2.3. Метрика.

§1.3. Идемпотентная алгебра матриц.

1.3.1. Свойства операций.

1.3.2. Норма матрицы.

1.3.3. Квадратные матрицы.

1.3.4. След матрицы.

1.3.5. Граф матрицы.

1.3.6. Обратная и псевдообратная матрицы.

1.3.7. Ранг матрицы.

1.3.8. Метрика.

§1.4. Линейные уравнения.

Глава 2. Линейные уравнения 1-го рода

§2.1. Расстояние от вектора до множества.

2.1.1. Вектор с ненулевыми координатами.

2.1.2. Произвольный ненулевой вектор.

§2.2. Линейная зависимость векторов.

§2.3. Решение уравнений и неравенств

2.3.1. Существование и единственность решения.

2.3.2. Общее решение уравнения.

2.3.3. Решение смешанной системы.

2.3.4. Решение уравнения Ах ф (1=Ъ.

Введение 2009 год, диссертация по информатике, вычислительной технике и управлению, Кривулин, Николай Кимович

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

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

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

Одной из первых публикаций по идемпотентной алгебре и ее приложениям является работа С.К. Клини [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. Разработаны методы анализа и решения векторных уравнений на основе анализа расстояния между векторами в метрическом пространстве и использования идемпотептного аналога определителя матрицы, получены условия существования и единственности решений, построены общие решения уравнений.

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

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

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

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

Результаты представлены па следующих научных конференциях: 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).

Публикация результатов. Результаты исследований отражены в работах [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] соискателю принадлежит теорема о среднем времени цикла обслуживания в многофазных системах с очередями, а соавтору — аналитический обзор результатов, связанных с оценкой средних значений максимумов сумм независимых случайных величин.

Библиография Кривулин, Николай Кимович, диссертация по теме Математическое моделирование, численные методы и комплексы программ

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. С. 105113.

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. Carré B.A. An algebra for network routing problems // IMA Journal of Applied Mathematics. 1971. Vol. 7, N 3. P. 273-294.

69. Carré 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. 851866.

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. 252256.

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. 277289.

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 indépendantes // 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. 207221.

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)

Похожие работы

Информатика, вычислительная техника и управление
05.13.00