Разработка метода формирования маршрутных матриц однородной замкнутой экспоненциальной сети массового обслуживания
Разработка метода формирования маршрутных матриц однородной замкнутой экспоненциальной сети массового обслуживания
Содержание
Введение стр. 3
1. Постановка задачи 5
2. Виртуальные СеМО 6
3. Маршрутные матрицы виртуальных СеМО 9
4. Методы построения маршрутных матриц виртуальных СеМО 14
e. Общее решение 14
6. Пример нахождения общего решения 16
7. Метод формирования маршрутной матрицы 20
8. Поиск по статистическому градиенту 22
9. Метод “тяжелого шарика” 22
10. Формирование матрицы. Описание метода 23
11. Алгоритм программы, реализующей метод 25
12. Назначение и описание программы 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).
Введем в рассмотрение множество констант
если не смежна с и , если смежна с и
мощность Иногда
для может быть задано множество констант ,
, мощности , используемое при формировании
маршрутной матрицы . В этом случае, если смежна с и
, то при наличии в множестве элемента
, соответствующего полагается, что .
Объединение множества и дает множество
, элементы которого определяют значение соответствующих маршрутных
вероятностей .
Для определения маршрутных вероятностей сети значительный
интерес представляют возможно имеющиеся данные о сравнительной величине
встречных потоков между и . Относительные интенсивности потоков
требований из в равны .Обозначим отношение
интенсивностей через , т. е.
. Величина называется коэффициентом обмена, а уравнение
- уравнением обмена.
Обозначим через множество коэффициентов обмена.
Задание этого множества определяет уравнений обмена,
которые могут быть использованы при определении
.
Следовательно для решения неизвестных маршрутных вероятностей может
быть использована система Е линейных алгебраических уравнений, включающая
три подсистемы:
d) подсистема уравнений потоков (L уравнений):
e) подсистема уравнений нормировки (L уравнений):
f) подсистема уравнений обмена ( уравнений):
Число уравнений обмена зависит от топологии сети и значений
, и может быть меньше [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) Система разрешима неоднозначно. Общее решение системы (18) - - (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) решение неоднозначно 10-8=2 неизвестных могут быть выбраны
произвольно.
Решаем систему и получаем:
(()
Подставим результаты в (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.
Назначение: Формирование выходных данных.
Содержание: Формируется сообщение, следующим образом:
Если решение найдено, то выходными данными является .
Если принято решение о невозможности достичь решения, то выходными
данными будет сообщение о том, что решение не существует.
Рисунок 2. Структурная схема алгоритма реализующего
метод формирования маршрутной матрицы.
5. Назначение программы OPTIM и описание программы.
Программа OPTIM написана на языке Turbo Pascal. Программа
предназначена для решения задачи формирования маршрутной матрицы
виртуальной СеМО. Программа представляет собой реализацию алгоритма
приведенного в предыдущей главе. Программа проста в использовании, требует
незначительный объем оперативной памяти. Недостатком программы является
недостаточно высокое быстродействие, как и у многих других программ,
реализующих подобные методы оптимизации.
Маршрутные матрицы и матрицы смежности являются разряженными
матрицами, т. е. матрицами, содержащими относительно малое число ненулевых
элементов. Поэтому для исследования виртуальных СеМО большой размерности в
программе OPTIM предусмотрено представление матриц смежности в виде
вектора, содержащего номера столбцов, содержащих ненулевые элементы
записанные в порядке возрастания номеров столбцов и строк. Номер последнего
положительного элемента в строке берется со знаком “-”. Подобное
представление матрицы смежности позволяет повысить скорость ввода исходных
данных.
Программу можно условно разбить на функциональные блоки, выполненные
в виде отдельных процедур и функций.
1. Ввод исходных данных. Реализует пункт 1 алгоритма. Выполнен в виде
процедуры InputData.
Содержание: считывает исходные данные из файла OPT.DAT . Исходные
данные выбираются в следующем порядке:
к - число ненулевых элементов матрицы смежности.
L - число СМО.
Svect - упакованная матрица смежности (вектор размерности к).
- концептуальный вектор (размерности L).
2. Задание начальной матрицы реализует Блок 2 алгоритма.
Выполнен в виде процедур MatrSmez и TetaMatr. Процедура MatrSmez формирует
матрицу смежности на основании вектора Svect. Процедура TetaMatr
преобразует матрицу смежности в матрицу (подробно описано в алгоритме
в Блоке 2).
3. Выбор направления спуска. Реализует Блок 3 алгоритма. Выполнен в
виде процедуры IndLocate. Для работы использует функции target (teta) и
stepish, вычисляющие значение целевой функции и степень полуисхода вершины
соответственно.
4. Осуществляет движение в выбранном направлении. Реализует Блок 4
алгоритма, выполнена в виде процедуры Move.
5. Обработка результатов и формирования файла выходных данных.
Реализует Блоки 5 и 6 алгоритма. Выполнен в виде процедуры OutputData.
Содержание: Обрабатывает результаты работы Блоков 2, 3, 4. Выходные
данные формируются в виде выходного файла OPT. REZ
Выходной файл содержит либо полученную маршрутную матрицу виртуальной
СеМО, либо сообщение о невозможности сформировать ее.
Текст программы помещен в приложении.
Заключение.
Целью данной работы являлась разработка метода решения задачи
формирования маршрутных матриц виртуальной СеМО.
Были рассмотрены некоторые методы оптимизации и на их основе
предложен метод формирования маршрутной матрицы.
Для него был разработан алгоритм и написана программа. Программа была
испытана на контрольных примерах.
Так же был предложен метод получения общего решения поставленной
задачи.
Список литературы.
Митрофанов Ю. И., Синтез сетей массового обслуживания.- Саратов: Изд-во
ГуНЦ “Колледж”, 1995 -168 с.
Башарин Г. П., Бочаров П. П., Коган Я. А. Анализ очередей в вычислительных
сетях. Теория и методы расчета. - М. Наука. Гл. ред. физ.-мат. лит., 1989 -
336 с.
Жиглявский А. А., Жилинскас А. Т. Методы поиска глобального экстремума. -М.
Наука, Гл. ред. физ.-мат. лит., 1991 - 248 с.
Поляк Б. Т. Введение в оптимизацию. - М. Наука, 1983 - 384 с.
Зайченко Ю. П. Исследование операций. - Киев, Вища школа, 1975, 320 с.
Митрофанов Ю. И., Брагина И. Т., Тананко И. Е., Юдаева Н. В. Анализ и
оптимизация сетей массового обслуживания. Программное обеспечение. -
Саратов, Изд-во “Колледж”, 1995 - 144 с.