Помощь в учёбе, очень быстро...
Работаем вместе до победы

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

Диссертация: Методы идемпотентной алгебры и анализа при исследовании сетей с очередями
ДиссертацияПомощь в написанииУзнать стоимостьмоей работы

Методы анализа динамических систем условно можно разделить на две основные, несомненно, пересекающиеся части: аналитические методы и имитационные. Те и другие получили широкое признание во всем мире, своих приверженцев и противников, свои научные школы и направления в развитии. На данный момент затруднительно перечислить даже малую долю всех научных докладов, статей и монографий, которые… Читать ещё >

Содержание

  • 1. Идемпотентная алгебра
    • 1. 1. Идемпотёнтные полугруппы и полукольца
    • 1. 2. Определение и обозначения скалярной (тах,+)-алгебры
    • 1. 3. Основные свойства скалярной (тах,+)-алгебры
    • 1. 4. Матричная (тах,+)-алгебра и ее основные свойства
    • 1. 5. Матрица смежностей ориентированного графа в (тах,+)-алгебре и ее свойства
    • 1. 6. Уравнение х = А

Методы идемпотентной алгебры и анализа при исследовании сетей с очередями (реферат, курсовая, диплом, контрольная)

Методы анализа динамических систем условно можно разделить на две основные, несомненно, пересекающиеся части: аналитические методы и имитационные. Те и другие получили широкое признание во всем мире, своих приверженцев и противников, свои научные школы и направления в развитии. На данный момент затруднительно перечислить даже малую долю всех научных докладов, статей и монографий, которые посвящены этой теме. К примеру, в книге Ермакова С. М. [10], вышедшей в свет в 1971 году, указывается тот факт, что в период с 1955 по 1970 годы только в нашей стране вышло более 2000 научных публикаций посвященных лишь методу Монте-Карло, а ведь это. не охватывает всей области, в которой ведутся исследования посвященные анализу динамических систем и смежным вопросам.

Большой вклад в данную область внесли исследования аналитических методов анализа в работах Гнеденко Б. В. 7, 8], Колмогорова А. Ц. [8, 15], Феллера В. [28] и др.

В области имитационных методов анализа динамических систем хотелось бы отметить работы Бусленко Н. П. [3, 4], Ермакова С. М. [10, 11, 12, 35, 36, 37], Романовского И. В. [26], Соболя И. М. [27] и др.

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

В последние годы в мире получил довольно широкое признание и интерес метод анализа, который основан на использовании аппарата идемпотентных алгебр. Здесь можно привести в пример работы Кинг-мена Ж.Ф.С. 45], Колокольцова В. Н. 24], Кунингхэм-Грина Р.А. 33], Маслова В. П. [24] и др.

Однако стоит отметить, что вопросы, связанные с данной областью, поднимались еще в 60-е годы Романовским И. В. в [26], где были получены результаты, связанные с решением дискретного уравнения Бел-лмана, а также Воробьевым H.H. [5], которым был описан ряд задач и методика их решения с помощью аппарата минимаксной алгебры.

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

В последние годы заметный интерес возник к описанию динамики сетевых систем с очередями с помощью идемпотентных алгебр, в частности, (тах,+)-алгебры. Здесь стоит отметить работы Кривулина Н. К. [20, 21, 22, 47, 48, 49, 50, 51, 52, 53, 55, 56, 57, 58, 63, 64, 65].

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

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

Также в диссертации рассматриваются свойства (обычные и вероятностные) ряда матричных операторов в данной (тах,+)-алгебре. С их помощью находится или оценивается ряд динамических характеристик для систем.

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

Первая глава носит вводный характер и дает краткий обзор понятий, связанных с идемпотентными алгебрами и с (тах,+)-алгеброй, в частности.

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

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

Четвертая глава целиком посвящена стохастическим сетям, где автор определяет новый класс сетей с очередями со случайной топологией сетевого графа, вводит понятие сбоя в работе сетей данного типа и среднего времени их работы. Рассматривается ряд оценок полученных автором совместно с его научным руководителем.

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

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

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

Отметим, что область применения аппарата (тах,+)-алгебры, несомненно, шире и заслуживает пристального внимания.

Основные результаты диссертационной работы можно сформулировать следующим образом:

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

Определено динамическое уравнение в идемпотентной (тах,+)-алгебре для нового класса сетей с очередями.

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

Введено понятие среднего времени работы до момента сбоя для нового класса сетей с очередями. Построен ряд оценок для данной величины.

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

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

Дан пример программной реализации (на основе объектно-ориентированной модели) работы сетей с очередями из рассматриваемого в диссертации класса. Результаты программного моделирования использовались в ряде примеров в диссертации.

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

Заключение

.

Показать весь текст

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

  1. Ф., Маковски A.M. Использование методов теории массового обслуживания для анализа систем с ограничениями по синхронизации// Труды Института Инженеров по Электротехнике и Радиоэлектронике. 1989. Т. 1. N 1. С. 99−128.
  2. A.A. Теория вероятностей. М.: Наука, 1986
  3. H.H. Моделирование сложных систем. М.: Наука, 1968.
  4. Н.П., Голенко Д. И., Соболь И. М., Сро/гович В.Г., Шрей-дер Ю. А. Метод статистических испытаний (метод Монте-Карло), СМБ, Физматгиз, М., 1962.
  5. H.H. Экстремальная алгебра положительных матриц// Elektronische Informationscverarbeitung und Kybernetik. 1967. Bd. 3, N 1. S. 39−72.
  6. Е.Г. О статистической аппроксимации// Теория вероятностей и ее применения (1965), 10, N2, 297−300.
  7. .В. Курс теории вероятностей. Гостехиздат, 1954.
  8. .В., Колмогоров А. Н. Предельные распределения для сумм независимых случайных величин. Гостехиздат, 1949.
  9. И. С., Рыжик И. М. Таблицы интегралов сумм, рядов и произведений. М.: Физматгиз, 1962. 1100с.
  10. С.М. Метод Монте-Карло и смежные вопросы. М.: Наука, 1971., 328 стр.
  11. С.М., Мелас В. Б. Математический эксперимент с моделями сложных стохастических систем. Издательство Санкт-Петербургского Университета, 1993.
  12. С.М., Михайлов Г. А. Статистическое моделирование. -М.: Наука, 1982.
  13. Дж. Статистические методы в имитационном моделировании. М.: Статистика, 1978.
  14. Г. П. Сохастические системы обслуживания. М.: Наука, 1966.
  15. А.Н. Основные положения теории вероятности. ГОНТИ, 1936.
  16. Г., Моллер П., Кадра Ж.-П., Въо М. Алгебраические средства оценивания характеристик дискретно-событийных систем // ТИИЭР. 1989. — Т. 77, N 1. — С. 30−53.
  17. Н.К. Оптимизация сложных систем для имитационного моделирования// Вестник Ленинградского Университета. Математика, 23 (1990), N 8, 100−102.
  18. Кривулин Н. К. Использование моделирования для оптимизации дискретных динамических систем, диссертация на соискание степени кандидата физико-математических наук, Санкт
  19. Петербургский Государственный Университет, Санкт-Петербург, 1990.
  20. Н.К., Милое Д. С. Оценки среднего времени безотказной работы для одного класса систем с очередями // Вестник Санкт-Петербургского государственного университета, 10 стр., (в печати).
  21. В.П., Колоколъцов В. Н. Идемпотентный анализ и его применение в оптимальном управлении. М.: Физматлит, 1994. 144с.
  22. Г. А. Некоторые вопросы теории метода Монте-Карло. -Новосибирск, Наука, 1981.
  23. И.В. Оптимизация стационарного управления дискретным детерминированным процессом// «Кибернетика», N 4, К., 1967, cnh 66−78.
  24. И.М. Численные методы Монте-Карло. М., 1981.
  25. Феллер В, Введение в теорию вероятностей и ее приложение: в 2-х томах. М., 1984.
  26. Cassandras C.G., Strickland S.G. Perturbation Analytic Methodologies for Design and Optimization of Communication Networks// IEEE J. Select. Areas Commun., vol 6, issue 1, 1988, p. 158−171.
  27. Chen L., Chen C.-L. A Fast Simulation Approach for Tandem Queueing Systems// Proc. 1990 Winter Simulation Conf. (Balci O., Sadowski R.P., Nance R.E., eds), 1990, p. 539−546.
  28. Cuninghame-Green R.A. Minimax Algebra // Lecture notes in economics and mathematical systems, 166 / Berlin: Springier-Verlag, 1979.
  29. Disney R.L., Konig D. Queueing Networks: a Survey of Their Random Processes// SIAM Review 27 (1985), no. 3, 335−403.
  30. Ermakov S.M., Krhmlin N.K. Efficient Parallel Algorithms for Tandem Queueing System Simulation, in Proc. 3rd Beijing International Conference on System Simulation and Scientific
  31. Computing, Beijing, China, October 17−19, 1995, Delayed Papers, 812.
  32. Ermakov S.M., Krivulin N.K. Efficient Algorithms for Tandem Queueing System Simulation, Applied Mathematics Letters, 7 (1994), no. 6, 45−49.
  33. Ermakov S.M., Krivulin N.K., Melas • V.B. Efficient Methods of Queueing Systems Simulation, in Proc. European Simulation Multiconference, Copenhagen, Denmark, June 17−19, 1991, (Mosekilde E., ed.), 8−20.
  34. Glasserman P., Yao D.D. Stochastic Vestor Differenca equations with stationary coefficients, J. Appl. Probab. 32 (1995), 851−866.
  35. Greenberg A.G., her B.D. Proc. Camb. Phil. Soc. vol 48, 1952, p. 277 289.
  36. Gumbel E.J. The Maxima of the Mean Largest Value and of the Range// Ann. Math. Statist. 25 (1954), 76−84.
  37. Haber S. A Combination of Monte Carlo and Classical method for evaluating multiple integral// Bull. Amer. Math. Soc. 1968, 74, 683 686.
  38. Hammersley J.M., Handscomb D.C. Monte Carlo Method, London, N.Y., 1964.
  39. Hartly H.O., David H.A. Universal Bounds for Mean Range and Extrem Observation// Ann. Math. Statist. 25 (1954), 89−99.
  40. Kiefer J., Wolfowitz J. On the Theory of Queues with Many Servers// Trans. Amer. Math. Soc:., vol 78, 1955, p. 1−18.
  41. Kingman J.F.C. Subadditive Ergodic Theory// Ann. Probab. 1 (1973), 883−909.
  42. Kleinrock L. Queueing Systems, Volume II: Computer Applications, John Wiley, N.Y., 1976.
  43. Krivulin N.K. Simple Bounds on the Mean Cycle Time in Acyclic Queueing Networks// in Proc. 3rd St. Petersburg Workshop on Simulation, St. Petersburg, June 28-July 3, 1998. St. Petersburg Univ. Press, St. Petersburg, 1998, 331−337.
  44. 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 Mastorakis N. World Scientific, 1998. P. 147−152.
  45. Krivulin N.K. Bounds on Mean Cucle Time in Acyclic Fork-Join Queueing Networks// Proc. Intern. Workshop on Discrete Event Systems, Cagliari, Italy, August 26−28, 1998, IEE, London, 1988, pp. 469−474.
  46. Krivulin N.K. Max-plus algebra models of queueing networks// Proc. Intern. Workshop on Discrete Event Systems WODES'96. London: University of Edinburgh, UK, August 19−21, 1996. The Institution of Electrical Engineers, 1996. P. 76−81.
  47. Krivulin N.K. A Max-Algebra Approach to Modeling and Simulation of Tandem Queueing Systems, Mathematical and Computer Modelling, 22 (1995), no.3, 25−31.
  48. Krivulin N.K. Algebraic Models in Simulation of Tandem Queueing Systems, in Proc. 1995 Summer Computer Simulation Conference,
  49. Tuncer I. Oren, Louis G. Birta, eds.), Simulation Councils, Inc., 1995, 9−14.
  50. Krivulin N.K. Unbiased Gradient Estimation in Queueing Networks with Parameter-Dependent Routing, in Proc. International Conference on Control and Information 1995, (Wong Wing-Shing, ed.), The Chinese University Press, Hong Kong, 1995, 351−356.
  51. Krivulin N.K. An Algebraic Approach to Modeling and Simulation of Tandem Queueing Systems, in Proc. European Simulation Multiconference, Prague, Czech Republic, June 5−7, 1995, (Miroslav Snorek, Milan Sujansky, Alexander Verbraeck, eds.), 271−275.
  52. Krivulin N.K. Recursive Equations Based Models of Queueing Systems, in Proc. European Simulation Symposium, Istanbul, Turkey, October 9−12, 1994, (Ali R" Kaylan. Axel Lehmann, Tuncer I. Oren, eds.), 252−256.
  53. Krivulin N.K. Using Max-Algebra Linear Models in the Representation of Queueing Systems, in Proc. 5th SIAM Conference on Applied Linear Algebra, Snowbird, UT, June 15−18, 1994, (John G. Lewis, ed.), 155−160.
  54. Krivulin N.K. A Recursive Equations Based Representation for the G/G/m Queue, Applied Mathematics Letters, 7 (1994), no. 3, 73−78.
  55. Krivulin N.K. Unbiased Estimates for Gradients of Stochastic Network Performance Measures, Acta Applicandae Mathematicae, 33 (1993), 21−43.
  56. Krivulin N.K. An Analysis of the Least Median of Squares Regression Problem, in Proc. 10th Symposium 011 Computational Statistics, Neuchatel, Switzerland, August, 1992, (Dodge Y., Whittaker J., eds.), 1, Physica-Verlag, 1992, 471−476.
  57. Krivulin N.K. Optimization of Complex Systems for Simulation Modeling Vestnik Leningrad University: Mathematics, 23 (1990), no.2, 64−67.
  58. Krivulin N.K., Nevzorov V.B. On Evaluation of the Mean Service Cycle Time in Tandem Queuing Systems. 2000, (in edition).
  59. Loynes R.M. The Stability of a Queue with Non-independent Inter-Arrival and Service Times// Proc. Camb. Phil. Soc. 58 (1962), no. 3, 497−520.
  60. Lindley D. V. The Theory of Queues with Single Server// Proc. Camb. Phil. Soc. vol 48, 1952, p. 277−289
  61. Marci8kiewicz J., Zigmund A. Sur les Fonctions Indepedantes// Fund. Math. 29 (1937), 60−90.
  62. Rubinstein R.Y. Simulation and the Monte Carlo Method, N.Y., 1981.
  63. Sacks J. Ergodicity of Queues in Series// Ann. Math. Statist. 31 (1960), 579−588.
  64. Shaked M., Shanthikamar J.G. Stochastic Convexity and its Applications// Adv. Appl. Prob., vol 20, 1988, p. 427−446.
  65. Shanthikumar J.G., Yao D.D. Second-Order Stochastic Properties in Queueing Systems// Proc. IEEE, vol 77, issue 1, 1989, p. 162−170.
Заполнить форму текущей работой

Пора сдавать?