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

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 с.

Страницы: 1, 2