Содержание
Введение стр. 3
1. 5
2. 6
2.1. 9
3. 14
3.1. 14
3.2. 16
3.3. 20
3.4. 22
3.5. 22
3.6. 23
4. 25
5. 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).
Введем в рассмотрение множествоконстант
если не смежна с и , если смежна с и мощность Иногда для может быть задано множествоконстант , , мощности , используемое при формированиимаршрутной матрицы . В этом случае,если смежна с и , то при наличии в множестве элемента
,соответствующего полагается,что .
Объединение множества и дает множество
, элементы которого определяют значение соответствующихмаршрутных вероятностей .
Для определения маршрутных вероятностей сети значительный интерес представляютвозможно имеющиеся данные о сравнительной величине встречных потоков между и . Относительные интенсивности потоков требований из в равны .Обозначим отношениеинтенсивностей через , т. е. . Величина называетсякоэффициентом обмена, а уравнение — уравнением обмена.
Обозначим через множество коэффициентовобмена. Задание этого множества определяет уравнений обмена, которыемогут быть использованы при определении .
Следовательно для решения неизвестных маршрутныхвероятностей может быть использована система Е линейных алгебраическихуравнений, включающая три подсистемы:
a)
b)
c) уравнений):
Число уравнений обмена зависит от топологии сети и значений , и может быть меньше [1].
Теорема 1. Для концептуальной симметричной виртуальной СеМОконсервативного, регулярного или равномерного типа с концептуальнымвектором маршрутнаяматрица всегда существует и ее элементы определяются соотношениями . Доказательство приведено в [1].
Теорема 2. Для концептуальной стандартной виртуальной СеМОконсервативного, регулярного или равномерного типов маршрутная матрицасуществует, если совместна система уравнений:
(15)
(16)
(17)
Значения элементов матрицы определяются решением этой системы. Теорема доказана в [1].
Замечание Общее решение системы (15) — (17) определяет бесконечноечисло подобных матриц . Дляконкретизации матрицы задаютконкретные значения свободных неизвестных.
Теорема 3. Для концептуальной эталонной виртуальной сети любого типа с концептуальным вектором , заданной топологией, определяемойорграфом , матрицы смежности , заданным множеством коэффициентовобмена , маршрутная матрицасуществует, если совместна система уравнений
(18)
(19)
(20)
(21)
(22)
приограничениях (23)
Доказательство см. в [1].
Примеры виртуальных СеМО различных видов рассмотрены в [1].
3. Методы построения маршрутных матриц СеМО.
3.1. Общее решение.
Задача построения маршрутной матрицы виртуальной СеМО может быть решенаследующим образом:
Пусть дана концептуальная эталонная виртуальная СеМО , состоящая из L СМО. Для которойопределены вектор , орграф , матрица смежности , множество , множество коэффициентов обмена.
Необходимо сформулировать маршрутную матрицу , т.е. найти L2неизвестных , .
Из уравнений (22) — (23) получили значения неизвестных , где Х определяется (14).
В результате получили систему линейных алгебраических уравнений (18) — (20) от Х неизвестных (индекссверху — порядковый номер неизвестной).
Решая систему методом Гаусса, получим один из трех возможных вариантов:
a) , а следовательно и виртуальную эталоннуюСеМО невозможно.
b) неравенствам (23). Если неравенства выполняются, то полученное решениедает значения оставшихся Х неизвестных , т. о. заканчивается формирование маршрутной матрицы . Если (23) не выполняется, тосформировать
невозможно.
c) — (20) фактически определяет бесконечноемножество подобных матриц дляконкретной концептуальной СеМО. Задание конкретных значений свободныхпеременных определяет конкретную маршрутную матрицу для такой СеМО. Очевидно,что это конкретное решение должно удовлетворять ограничениям (23).
Пусть первые m переменных — свободные, тогда если , то остальные , можно записать как . Т.е. остальные (Х-m) переменных могут быть линейно выражены через . Подставляя полученные выраженияв неравенства
(24)
получим систему неравенств:
(25)
Эта система неравенств образует так называемое многогранноемножество в m — мерном пространстве. Если это множество не пусто, то, таккак оно ограничено, оно является выпуклым многогранником. Точка называется вершиной выпуклогомногогранника в , если она являетсядопустимой и представляет собой точку пересечения m линейно независимыхгиперплоскостей. (Каждое линейное уравнение задает гиперплоскость, каждомулинейному неравенству из (25) сопоставляется ограниченное гиперплоскостьюполупространство; гиперплоскость получают, заменяя знак неравенства на знакравенства.) Вершина вырожденная, если она является точкой пересечения более чемm гиперплоскостей.
Вершину нельзя представить ввиде выпуклой линейной комбинации двух других точек допустимой области для всех допустимых точек( ).Всякое многогранное множество имеет конечное число вершин. Если допустимаяобласть образована n неравенствами и m уравнениями, то она можетиметь самое большее вершин. Т.к. допустимая область в данном случае является выпуклым многогранником, токаждая допустимая точка имеет по меньшей мере одно представление:
(26),
где — вершины многогранника; .
Таким образом, если мы найдем все вершины многогранника(если они существуют. В противном случае решения не существует), то мы получимобщее решение задачи формирования матрицы .
где — допустимая точка,найденная по формуле (26). Получим оставшиеся Х неизвестных и завершимпостроение маршрутной матрицы.
3.2. Пример нахождения общего решения.
Дана концептуальная эталонная виртуальная СеМО , с L=5, для которой определеныконцептуальный вектор , орграф ,матрица смежностей .
Множество .
Из уравнений (21), (22) получим значения 15 неизвестныхмаршрутных вероятностей из 25. Оставшиеся неизвестные занумеруем ,
получим:
Рассмотрим систему линейных уравнений (18), (19), (17).Применяя к ней алгоритм Гаусса получим:
a)
b)
Решаем систему и получаем:
(*)
Подставим результаты в (25). Получим систему типа (26):
(27)
Эта система неравенств образует многогранное множество,изображенное на рис. 1.
Любая пара принадлежащая допустимой области удовлетворяет системе (27).
Многограннику имеет 5 вершин:
Любая точка допустимого множества имеетпредставление , где — вершины, , , . Пусть, например, , тогда
. Подставим значения и в (*), получим
Рисунок 1.
3.3. Метод формирования маршрутной матрицы виртуальной СеМО.
Задача построения виртуальной СеМО может быть сведена кзадаче нелинейного программирования.
Пусть задана концептуальная виртуальная СеМО , для которой задан концептуальныйвектор , орграф , матрица смежностей , множество .
Задачей нелинейного программирования общего виданазывается задача: Найти
(2.1)
при ограничениях
(2.2)
Введем в рассмотрение функцию ; очевидно,что если отыщется такая,что , то есть искомая маршрутная матрица. Т. о. мыполучили задачу:
(2.3)
приограничениях
(2.4)
Задача (2.3) — (2.4) является задачей нелинейногопрограммирования. Ее можно отнести к задачам квадратичного программирования — класс задач для которых целевая функция квадратична, а все ограничения линейны.
Решая задачу (2.3) — (2.4) одним из методов,рассмотренных в [3-5] можно получить один из результатов:
1) , где . В этом случаесформировать маршрутную матрицу невозможно.
2) . В этомслучае есть искомая маршрутнаяматрица виртуальной СеМО.
Для решения ЗНП разработан ряд методов, позволяющих,отправляясь от некоторого начального решения, получать последовательнозначения, которые находятся все ближе к искомой точке максимума (минимума).Группа методов, основанных на вычислении и сравнении значений целевой функции вряде точек перед следующим шагом, называется поисковыми методами оптимизации.
В задаче можно представить целевую функцию как гиперповерхность.Максимальное значение достигается в вершине самого высокого холма. Поискэкстремума начинают с любой удобной точки, причем двигаются в направлениинаискорейшего подъема, пока не достигают либо вершины, либо границы. Придостижении границы необходимо исключить перемещение за пределы ограничений. Придостижении вершины, которая встретилась в направлении наискорейшего подъемаповорачивают во вновь выбранном направлении наискорейшего подъема. Такимобразом достигают точки, где движение в любом направлении приводит к спуску. Вэтом случае утверждают, что найден по крайней мере локальный экстремум.
На практике, при реализации этого метода возникают две трудности.Во-первых, это относительная малая скорость сходимости. Для преодоления этогослужат методы нахождения более эффективных направлений, чем направлениенаискорейшего подъема. Вторая трудность состоит в том, что этот метод позволяетобнаружить локальные максимумы, но не дает гарантии достижения абсолютного(глобального) экстремума. Чтобы преодолеть эту трудность обычно начинают поискиз различных точек, и, если вычисления сходятся к разным вершинам, то выбираютнаиболее высокую из них. Также можно использовать метод, известный подназванием “метод тяжелого шарика”, при котором движение точки напоминаетдвижение тяжелого шарика по бугристой поверхности. Рассмотрим некоторые изметодов поисковой оптимизации.
3.4. Поиск по статистическому градиенту.
Пусть надо найти максимум . В точке делается m случайных испытаний ивычисляются приращения целевой функции
где — случайные величины, — случайный шаг.
Далее определяют величину
Усредненное по всем реализациям значения совпадает с истинным направлениемнаискорейшего подъема, т. е.
Далееиз точки совершается очереднойрабочий шаг:
3.5. Метод “тяжелого шарика”.
Рассмотрим простейший вариант случайного поиска:
пусть — произвольная точка. Из совершаетсядвижение с шагом в случайномнаправлении с равномерным распределением.
Движение представляющей точки описывается так:
Этот алгоритм без памяти может быть усовершенствован.Направление удачных проб запоминается и вероятность шага в этих направленияхвозрастает. Для этого введем вектор памяти , проекции которого на координатные оси определяют вероятность выбора положительного направления поi — ой оси. — монотонная,неубывающая функция, тогда , а изменяется так:
где — параметрзапоминания, — характеризуетскорость обучения, .
Этот метод называется методом “тяжелого шарика”.
3.6.Формирование маршрутной матрицы.
Пусть поставлена задача (2.3) — (2.4). Для нахождениярешения применим метод последовательной оптимизации.
Описание метода.
1. Начальный шаг к=0.
В качестве начальногоприближения выберем некоторую матрицу . Матрица должнаудовлетворять условиям 2.4. Зададим точность .
Замечание. Вышебыло сказано, что для того, чтобы повысить вероятность нахождения глобальногоэкстремума выбирают несколько начальных приближений. может быть выбрана случайно, либообласть определения может быть разбита на интервалы и в качестве выбираются узлы полученной сетки. Методывыбора числа случайных проб или размерности сетки описаны в [3] — [7].
2. к-ый шаг. Выбор направления движения.
Для каждого элемента , где вычислимзначения целевой функции , где — матрица, в которой все элементыравны элементам матрицы , кромеодного этого элемента , которыйравен . Значениевеличины выбирается из соображений оточности, с которой ищется .Методы выбора величины описаны в[3] — [7].
Таким образом получиммножество значений целевой функции . ( может быть положительнойи отрицательной). Для всех элементов . Выберем теперь .Соответствующий элемент матрицы запоминаем. Пусть это будет .Выберем теперь в строке i1 элемент , такой, что . Запомним также этот элемент.
Рассмотрим двавозможных варианта:
а) Если , то запоминаем компоненты , и переходим к 3.
б) Если , то , переходимк 4.
3. к-ый шаг. Движение в выбранном направлении.
Из точки переходим к следующим образом:
Если ,то определяется следующим образом:
к:=к+1, переходим к 3.
Если ,то , к:=к+1, переходим к 2.
4. Конечный шаг.
Если ( — величина, определяющая точностьвычисления экстремума), то — искомая маршрутная матрица.
Если , то выбирают другоеначальное приближение и переходят к 2. Если множество начальных приближенийисчерпано, то полагают, что сформировать маршрутную матрицу невозможно.
4. Алгоритм программы,реализующий метод построения
маршрутной матрицы.
Алгоритм состоит из 6 функциональных блоков, выполняемыхв порядке, который схематично изображен на рисунке 2 “Схема алгоритма”. Нижеприведено назначение и содержание всех 6-ти функциональных блоков. Алгоритмреализует описанный выше метод.
Блок 1.
Назначение: Ввод данных, необходимых дляпостроения маршрутной матрицы.
Содержание: Ввод данных, конкретизирующихрешаемую задачу (т. е. задачу построения маршрутной матрицы виртуальной СеМО(2.3) — (2.4)). Эти данные должны содержать число СМО в сети и матрицусмежности исходной концептуальной виртуальной СеМО, а также концептуальныйвектор .
Блок 2.
Назначение: Задание начального приближения.
Содержание: Матрица формируется путем присвоения случайныхзначений элементам таких, что , где I — множество номеровэлементов матрицы смежности, таких что
При этом необходимо соблюдать стохастичность матрицы, т.е. условия (2.4). Остальные элементы получают следующим образом:
( — элементы матрицы смежности).
Т. о. блок 2 реализует пункт 1 рассмотренного вышеметода.
Блок 3. Реализует пункт 2 метода формированиямаршрутной матрицы.
Назначение: Выбор направления, в котором будетосуществляться поиск экстремума.
Содержание: 3.1) Вычисление целевой функции текущей матрицы .
3.2) Выбор таких элементов и и величины , (положительнойили отрицательной), что
После того как эти условия выполнены и элементы найденыпереходят к условию 1:
1) Если ,то передаются вкачестве исходных данных в Блок 4 и управление передается Блоку 4.
2) Если 1) не выполняется, то текущая матрица запоминается как и управление переходит на Блок 5.
Подробно выбор элементов и описан выше в пункте 2 метода формирования матрицы .
Блок 4. Реализует пункт 3.
Назначение: Осуществляет движение в направлениивыбранном Блоком 3 до тех пор пока не будет достигнута граница (условия(2.4)), либо вершина на этом направлении.
Содержание: Пока не будет достигнута граница, т.е. не перестанут выполняться условия:
( — выбраны Блоком 2)
Либо не будет достигнута вершина для текущегонаправления, т. е.
(*)
( (*)- условие достижения вершины в точке ). Повторяют рабочий шаг: присваивают значение .
Как только движение прекращается текущая матрица запоминается и управление передается в Блок3.
Блок 5.
Назначение: Определить достигнут ли глобальныйэкстремум в точке , определенной Блоком2. Т. е. достигнуто ли решение задачи (2.3) — (2.4).
Содержание: Проверяются условия 2:
Если ( — величина, определяющаяточность, с которой ищется экстремум, содержится во входных данных), тоделается вывод, что
— решение задачи (2.3) — (2.4);
Если , то если раз не былдостигнут один и тот же минимум, управление передается в Блок 2 ( может быть задана в исходных данных).
В противном случае полагается, что решения задачи (2.3)- (2.4) достичь невозможно.
После проверки условия 2 управление передается вБлок 6.
Блок 6.
Назначение: Формирование выходных данных.
Содержание: Формируется сообщение, следующимобразом:
Если решение найдено, то выходными даннымиявляетс