Материал: 4539

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ

УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ «ВОРОНЕЖСКИЙ ГОСУДАРСТВЕННЫЙ ЛЕСОТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ ИМЕНИ Г.Ф. МОРОЗОВА»

Кафедра автоматизации производственных процессов

АЛГОРИТМЫ РЕШЕНИЯ НЕСТАНДАРТНЫХ ЗАДАЧ

Методические указания к практическим занятиям для студентов

по направлению подготовки 27.03.05 - Инноватика

Воронеж 2018

Практическое занятие № 1

Понятие условного экстремума. Метод множителей Лагранжа для нахождения условного экстремума. Достаточные условия для точек условного экстремума.

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

2. Методы условной оптимизации

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

-методы последовательной безусловной оптимизации;

-методы возможных направлений.

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

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

Ко второй группе методов относятся:

-метод проекции градиента;

-метод возможных направлений Зойтендейка.

Методы возможных направлений, используемые для решения задачи условной оптимизации, основаны на движении из одной допустимой точки, где выполнены все ограничения, к другой допустимой точке с лучшим значением целевой функции.

3. Методы последовательной безусловной оптимизации

2

К методам последовательной безусловной оптимизации относят:

-метод штрафов;

-метод барьеров;

-метод множителей;

-метод точных штрафных функций.

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

крешению исходной задачи.

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

Вметоде множителей штрафная функция добавляется не к самой целе-

вой функции, а к ее функции Лагранжа . В результате исследование на экстремум сводится к исследованию модифицированной функции Лагранжа.

В методе точных штрафных функций задача сводится к решению одной задачи безусловной оптимизации.

3.1. Метод штрафов

Алгоритм метода штрафов состоит из следующих этапов.

1 этап. Задать начальную точку x 0 вне области допустимых решений, начальное значение параметра штрафа r0 0 , число C 1 для увеличения параметра штрафа, погрешность расчета 0 . Принять k 0 .

2 этап. Составить вспомогательную функцию

3этап. Найти точку x* (rk ) безусловного минимума функции F(x, rk ) по

xс помощью какого либо метода (нулевого, первого или второго порядка):

F(x* (rk ), rk ) minF(x, rk ) . При этом задать все требуемые выбранным мето-

x Rn

дом параметры. В качестве начальной точки взять x k . Вычислить функцию

этапу 2.

Примечание. Рекомендуемые значения r0 0.01, 0.1,1, параметра C 4 10.

3

3.2. Метод барьерных функций

Алгоритм метода барьерных функций состоит из следующих этапов.

1 этап. Задать начальную точку x 0 внутри области U , начальное значение параметра штрафа r0 0 , число C 1 для уменьшения величины параметра штрафа, погрешность расчета 0 . Принять k 0 .

2 этап. Составить вспомогательную функцию

3этап. Найти точку x* (rk ) безусловного минимума функции F(x, rk ) по

xс помощью какого либо метода (нулевого, первого или второго порядка):

F(x* (rk ), rk ) minF(x, rk ) с проверкой принадлежности текущей точки внут-

x Rn

ренности множества U . При этом задать все требуемые выбранным методом параметры. В качестве начальной точки взять x k .

Примечание. Рекомендуемые значения r0 1,10,100 , параметра C 10,12,16.

Варианты заданий

Варианты заданий приведены в таблице. Таблица. Варианты заданий

4