Методы оптимизации, основанные на классической математике.

1. Экстремум функции одной переменной

=>Находится X_опт

2. Экстремум функции многих переменных

 

=> Находится X_опт

 

- матрица вторых производных.

Исследуем матрицу: Если все элементы матрицы больше 0, то в точке наблюдается минимум.

3. Метод замены переменных

Когда ограничения имеют вид неравенств, число ограничений меньше числа переменных (неизвестных).

Выражаем m первых переменных:

Выражаем через остальные. Получаем систему уравнений.

Затем уже находятся все остальные переменные подствавлением в эти.

- целевая функция зависит от меньшего числа переменных

Достоинства:

1) позволяет избавиться от ограничений;

2) позволяет понизить размерность задачи.

Недостатки:

1) не всегда можно разрешить систему уравнений, относительно m - первых неизвестных (переменных).

2) Необходимо, чтобы функция была дифференцируема.

4. Метод неопределенных множителей Лагранжа.

Достоинства:

1) Нет ограничения на условие, что количество переменных

Задача с ограничениями сводится к задаче без ограничений.

Составляется ф-я Лагранжа: ,

где - неопределенные множители Лагранжа.

Находим производные:

(1)

Находим производные по каждой из :

(2)

Решаем (1) и (2) и находим:

(1) =›

(2) =›

т.о. уходим от ограничений.

Недостатки:

1) функция должна быть дифференцируема;

2) трудность решения систем уравнений;

3) повышена размерность задачи.

 

Пример: Спроектировать термостат цилиндрической формы, т.о., чтобы он имел min поверхность при заданном объеме.

r, h -?

Нелинейное программирование

 

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

1) Многошаговые интеграционные процессы, в которых производится постепенное сведение к оптимальному решению. Точки друг от друга различаются на шаг.

,

где шаг, k - номер интеграции, номер шага.

2) Большую трудность вызывает выбор шага (если большой – рискуем пройти оптимум, но с большой скоростью; если маленький – существует возможность «утонуть» в вычислениях).

3) Заранее определить число шагов нельзя.

4) Эффективность методов зависит от результата, полученного в предыдущем шаге.

5) В алгоритме поиска необходимо иметь правило окончания работы. Оно заключается в достижении требуемой точности.

6) Некоторые задачи могут не иметь решения, а иметь лишь особые точки.

 

Классификация методов нелинейного программирования:

1. Градиентные методы:

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

- метод релаксации;

- метод наискорейшего спуска;

- метод тяжелого шарика;

1. Безградиентный способ:

- метод общего поиска;

- метод дихотомии;

- метод золотого сечения;

- метод чисел Фибоначчи;

- метод сканирования;

- симплексный метод;

1. Группа случайного поиска:

- метод «слепого» поиска;

- метод случайных направлений.

Градиентные методы нелинейного программирования.

Метод релаксации.

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

Исходная задача разбивается на ряд подзадач.

В области определения выбирается точка и составляется функция вида:

Все переменные оставляем const, а xосвобождаем

Находим производную:

=0 => x₁⁽¹⁾=const

Значение подставляется в функцию :

Дальше таким же образом берется производная и находится:

и т.д.

т. е. за шагов вычисляем , производим сравнение и

Сравнивая ,…, выбирают max и min значения.

После сравнения выбираются максимальное и минимальное значение функции, которые и дают наиболее оптимальные значения

– оптимальное значение.

Достоинства:

1) Простота и наглядность.

Недостатки:

2) Долгий путь решения задачи.

3) Необходимо иметь аналитические выражения целевой функции по всем параметрам.

Метод градиента.

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

Требование: Функция должна быть дифференцируема, унимодальная (иметь 1 экстремум) на определенном промежутке.