2. Порядок выполнения лабораторной работы

1. Разработать алгоритм и программу поиска минимума функции двух переменных методом Монте-Карло. (Вариант задания тот же, что и в Лабораторной работе № 1). Число испытаний m=121. Применить датчик случайных чисел с равномерным распределением Random.

2. Построить область поиска экстремума и линии уровней минимизируемой функции с учетом параметрических функциональных ограничений. Нанести на график с линиями уровней точку с минимальным значением функции.

3. Требования к защите лабораторной работы

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

Контрольные вопросы:

1. Структура оптимизационной модели.

2. Задачи анализа и синтеза в общей схеме оптимизации.

3. Классификация задач оптимизации.

4. Классификация методов оптимизации.

5. Сравнение метода Монте-Карло с методом прямого перебора по сетке.

Лабораторная работа № 3

МЕТОД ХУКА-ДЖИВСА

Цель работы: Изучение локальных методов прямого поиска, их практическая реализация в задачах условной и безусловной минимизации.

1. Описание метода

Поиск состоит из последовательности шагов исследующего поиска вокруг базисной точки, за которой в случае успеха следует поиск по образцу. Процедура поиска выглядит следующим образом:

А. Выбрать начальную базисную точку b1 и шаг длиной hj для каждой пере-менной хj, j=1,2,…,n.

Б. Вычислить у(х) в базисной точке b1 с целью получения сведений о локальном поведении функции у(х). Эти сведения будут использоваться для нахождения перспективного направления поиска по образцу, с помощью которого можно надеяться достичь большего убывания значения функции. Исследующий поиск в базисной точке b1 проводится следующим образом:

1. Вычисляется значение функции y(b1) в базисной точке b1.

2. Каждая переменная по очереди изменяется прибавлением длины шага. Таким образом, вычисляем значение функции y(b1+h1e1), где e1 – единичный вектор в направлении оси x1. Если это приводит к уменьшению значения функции, то b1 заменяется на b1+h1e1. В противном случае вычисляется значение функции у(b1-h1e1), и если ее значение уменьшилось, то b1 заменяем на b1-h1e1. Если ни один из проделанных шагов не приводит к уменьшению значения функции, то точка b1 остается неизменной, и рассматриваются изменения в направлении оси х2, т.е. находится значение функции у(b1+h2e2) и у(b1-h2e2). Когда будут рассмотрены все n переменных, то получим базисную точку b2.

3. Если b2=b1, т.е. уменьшение функции не было достигнуто, то исследование повторяется вокруг той же базисной точки b1, но с уменьшенной длиной шага. На практике удовлетворительным является уменьшение шага (шагов) в десять раз от начальной длины.

4. Если y(b2)<y(b1), то производится поиск по образцу, т.е. поиск в направлении, заданном минимальным значением функции.