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

Задачей нелинейного программирования общего вида называется задача: Найти

(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].

Таким образом получим множество значений целевой функции . ( может быть положительной и отрицательной). Для всех элементов . Выберем теперь . Соответствующий элемент матрицы запоминаем. Пусть это будет .Выберем теперь в строке i₁ элемент , такой, что . Запомним также этот элемент.