Концептуальная стандартная СеМО имеет полносвязную топологию без петель. Все элементы матрицы смежности равны единице, кроме элементов главной диагонали.
Топология концептуальной эталонной СеМО может быть произвольной и должна удовлетворять лишь одному требованию - быть тождественной топологии соответствующей объектной СеМО. Поэтому тождественен орграфу объектной СеМО, матрицы и тождественны. Из связи с следует:
1) если не смежна с , то .
2) если смежна с , то если , .
3) число неизвестных сети
(14).
Введем в рассмотрение множество констант
если не смежна с и , если смежна с и мощность Иногда для может быть задано множество констант , , мощности , используемое при формировании маршрутной матрицы . В этом случае, если смежна с и , то при наличии в множестве элемента
, соответствующего полагается, что .
Объединение множества и дает множество
, элементы которого определяют значение соответствующих маршрутных вероятностей .
Для определения маршрутных вероятностей сети значительный интерес представляют возможно имеющиеся данные о сравнительной величине встречных потоков между и . Относительные интенсивности потоков требований из в равны .Обозначим отношение интенсивностей через , т. е. . Величина называется коэффициентом обмена, а уравнение - уравнением обмена.
Обозначим через множество коэффициентов обмена. Задание этого множества определяет уравнений обмена, которые могут быть использованы при определении .
Следовательно для решения неизвестных маршрутных вероятностей может быть использована система Е линейных алгебраических уравнений, включающая три подсистемы:
a) подсистема уравнений потоков (L уравнений):
b) подсистема уравнений нормировки (L уравнений):
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) Система разрешима неоднозначно. Общее решение системы (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) . В этом случае есть искомая маршрутная матрица виртуальной СеМО.
Для решения ЗНП разработан ряд методов, позволяющих, отправляясь от некоторого начального решения, получать последовательно значения, которые находятся все ближе к искомой точке максимума (минимума). Группа методов, основанных на вычислении и сравнении значений целевой функции в ряде точек перед следующим шагом, называется поисковыми методами оптимизации.
В задаче можно представить целевую функцию как гиперповерхность. Максимальное значение достигается в вершине самого высокого холма. Поиск экстремума начинают с любой удобной точки, причем двигаются в направлении наискорейшего подъема, пока не достигают либо вершины, либо границы. При достижении границы необходимо исключить перемещение за пределы ограничений. При достижении вершины, которая встретилась в направлении наискорейшего подъема поворачивают во вновь выбранном направлении наискорейшего подъема. Таким образом достигают точки, где движение в любом направлении приводит к спуску. В этом случае утверждают, что найден по крайней мере локальный экстремум.
На практике, при реализации этого метода возникают две трудности. Во-первых, это относительная малая скорость сходимости. Для преодоления этого служат методы нахождения более эффективных направлений, чем направление наискорейшего подъема. Вторая трудность состоит в том, что этот метод позволяет обнаружить локальные максимумы, но не дает гарантии достижения абсолютного (глобального) экстремума. Чтобы преодолеть эту трудность обычно начинают поиск из различных точек, и, если вычисления сходятся к разным вершинам, то выбирают наиболее высокую из них. Также можно использовать метод, известный под названием “метод тяжелого шарика”, при котором движение точки напоминает движение тяжелого шарика по бугристой поверхности. Рассмотрим некоторые из методов поисковой оптимизации.