CBRR1978 (Разработка метода формирования маршрутных матриц однородной замкнутой экспоненциальной сети массового обслуживания)

35

Содержание

Введение стр. 3

1. Постановка задачи 5

2. Виртуальные СеМО 6

   1. Маршрутные матрицы виртуальных СеМО 9

3. Методы построения маршрутных матриц виртуальных СеМО 14

   1. Общее решение 14

   2. Пример нахождения общего решения 16

   3. Метод формирования маршрутной матрицы 20

   4. Поиск по статистическому градиенту 22

   5. Метод “тяжелого шарика” 22

   6. Формирование матрицы. Описание метода 23

4. Алгоритм программы, реализующей метод 25

5. Назначение и описание программы OPTIM 29

Заключение 31

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

Приложение 1. Список идентификаторов 33

Приложение 2. Текст программы 34

Введение

Широкое результативное применение сетей массового обслуживания (СеМО) различных классов [1-2] в качестве математических моделей дискретных систем с сетевой структурой и стохастическим характером функционирования обуславливает дальнейшее интенсивное развитие теории сетей массового обслуживания, методов решения задач их анализа, синтеза и оптимизации, а как же методологии моделирования дискретных систем сетями массового обслуживания. Сети обслуживания, являющиеся моделями соответствующих дискретных систем будем считать объектными.

При решении задач анализа, синтеза и оптимизации объектных часто используется понятие некоторой “оптимальной” СеМО. Содержание термина “оптимальная” в значительной степени определяется содержанием решаемых задач. Например, многие задачи анализа СеМО связаны с поиском “узких” мест в СеМО, т.е. систем массового обслуживания, м.о. числа пребывающих требований в которых превышают некоторые допустимые значения. После нахождения узких мест их устраняют, например, увеличивается интенсивность обслуживания в соответствующих СеМО, или изменяя маршрутные матрицы СеМО. Таким образом в качестве оптимальной может рассматриваться, например, СеМО, во всех системах которой математические ожидания длительностей обслуживания одинаковы. Часто целью решения задач синтеза и оптимизации является формирования СеМО возможно большей пропускной способности.

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

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

1. Постановка задачи

Пусть задана объектная СеМО, определяемая набором [1]

Пусть так же заданы - концептуальный вектор, построенный на основании теорем, приведенных в [1] и S - матрица смежностей, определяемая следующим образом:

- несформированная матрица .

Необходимо построить виртуальную СеМО эталонного типа, а если это невозможно, то сеть стандартного или симметричного видов [1]. Для этого необходимо задать набор [1-2], которым определяется однородная замкнутая экспоненциальная сеть. Этот набор отличается от набора только тем, что для него сформирована маршрутная матрица . Т.о. задача состоит в том, чтобы найти неизвестные маршрутные вероятности , эта задача называется задачей синтеза [1].

2. Виртуальные СеМО

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

При решении задач анализа, синтеза и оптимизации объектных СеМО используют СеМО, которые будем называть виртуальными. Параметры виртуальных СеМО формируются на основе параметров, соответствующих объектных СеМО. В частности, виртуальные СеМО могут отличаться от соответствующих объектных СеМО только своими маршрутными матрицами. Рассматриваются виртуальные СеМО трех видов: эталонные, стандартные и симметричные [1].

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

Виртуальные СеМО каждого вида могут быть одного из следующих типов: консервативного, регулярного, равномерного [1]. Тип определяется требованиями, предъявляемыми при формировании сети к некоторым ее характеристикам.

Исходя из соображений, приведенных в [1], при исследовании дискретных систем во многих случаях в качестве их моделей (объектных СеМО) могут весьма эффективно использоваться экспоненциальные СеМО.

В качестве виртуальных СеМО рассматриваются экспоненциальные, однородные, замкнутые СеМО, определяемые набором

(1)

Основные стационарные характеристики рассмотрены в [1], [2].

Считая известными вектор вероятностей перехода требований в системы сети обслуживания при их очередных переходах (вектор является решением уравнения с условием нормировки ) и множества величин

и ( - множество номеров СеМО). Маршрутные матрицы виртуальных СеМО, , определяются решением системы уравнений (2)-(4) с возможным использованием условий (5)-(6).

(2)

(3)

(4)

(5)

(6)

Решение системы (2)-(4) в случае, когда все равны 1, а условия (5)-(6) не используются определяет матрицу для виртуальных СеМО симметричного вида, имеющих полносвязную топологию с петлями.

Использование при решении (2)-(4) только условий (5) дает полносвязную топологию без петель стандартного вида.

При определении маршрутных матриц эталонных виртуальных СеМО используются условия (5)-(6). Очевидно, использование данных условий позволяет в общем случае задать произвольную топологию эталонной сети, в которой не допускаются петли. Т.е. маршрутная матрица эталонной сети может иметь структуру, тождественную (в отношении числа и расположения нулевых элементов) структуре маршрутной матрицы, соответствующей объектной СеМО. Эти матрицы могут отличаться только значениями ненулевых элементов. Заметим, что подсистема (4) определяет отношения относительных интенсивностей встречных потоков требований из с_i в с_j и обратно.

Определение 1. Маршрутные матрицы и однородных, замкнутых СеМО и с одноприборными СМО, определяемыми наборами

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

Определение 2. СеМО и , определенные наборами

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

Определение 3. Однородная замкнутая экспоненциальная СеМО с одноприборными СМО, определяемая набором

и удовлетворяющая условиям:

называется виртуальной СеМО консервативного типа.

Определение 4. Однородная замкнутая СеМО с одноприборными СМО, определяемая набором

и удовлетворяющая условию называется виртуальной СеМО регулярного типа.

Определение 5. СеМО , определяемая набором

и удовлетворяющая условию

( - м. о. длительности пребывания требования в с_i ) называется виртуальной СеМО равномерного типа.

В [1] рассмотрены основные характеристики виртуальных СеМО различных типов и доказан ряд теорем, на основании которых могут быть построены эти характеристики. (В том числе вектор .)

2.1 Маршрутные матрицы виртуальных СеМО.

Решение вопроса о существовании виртуальных СеМО соответствующих видов и типов зависит от значений параметров L, N, вектора . При этом для исключения тривиальных случаев достаточно потребовать, чтобы значения параметров L и N удовлетворяли очевидным соотношениям (7), а значения компонент вектора удовлетворяли неравенству (8).

Для виртуальной СеМО равномерного типа на значения

накладывается дополнительное ограничение

(9),где

(10)

В [1] показано, что вероятности существуют и удовлетворяют требованиям:

(11)

для виртуальных СеМО консервативного и регулярного типов при выполнении ограничений (7), (8), а для виртуальных СеМО равномерного типа (7),(8),(9). Поэтому будем считать, что для представляющих теоретический интерес виртуальных СеМО параметры L, N, и таковы, что (7),(8),(9) выполняются и существует вектор построенный на основании теорем, приведенных в [1].

Определение 6. Виртуальные СеМО, параметры L, N, которых удовлетворяют ограничениям (7),(8), (9), а вектор определяется на основании теорем [1] и удовлетворяет условиям (11) называются концептуальными виртуальными СеМО, а вектор - концептуальным вектором.

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

(13).

Другими словами виртуальная СеМО не существует пока не определены все элементы набора , в том числе и . Поэтому интерес представляет условие существования маршрутных матриц для коцептуальных СеМО.

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

Введем в рассмотрение орграф , отображающий топологию СеМО . Вершины соответствуют СМО, а дуги - траекториям переходов требований между системами.

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

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

Концептуальная стандартная СеМО имеет полносвязную топологию без петель. Все элементы матрицы смежности равны единице, кроме элементов главной диагонали.

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

1. если не смежна с , то .

2. если смежна с , то если , .

3. число неизвестных сети

   (14).

   Введем в рассмотрение множество констант

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

   , соответствующего полагается, что .

   Объединение множества и дает множество

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

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

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

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

4. подсистема уравнений потоков (L уравнений):

5. подсистема уравнений нормировки (L уравнений):

6. подсистема уравнений обмена ( уравнений):

Число уравнений обмена зависит от топологии сети и значений , и может быть меньше [1].

Теорема 1. Для концептуальной симметричной виртуальной СеМО консервативного, регулярного или равномерного типа с концептуальным вектором маршрутная матрица всегда существует и ее элементы определяются соотношениями . Доказательство приведено в [1].

Теорема 2. Для концептуальной стандартной виртуальной СеМО консервативного, регулярного или равномерного типов маршрутная матрица существует, если совместна система уравнений:

(15)

(16)