Замечание. Выше было сказано, что для того, чтобы повысить вероятность нахождения глобального экстремума выбирают несколько начальных приближений. может быть выбрана случайно, либо область определения может быть разбита на интервалы и в качестве выбираются узлы полученной сетки. Методы выбора числа случайных проб или размерности сетки описаны в [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, вычисляющие значение целевой функции и степень полуисхода вершины соответственно.