Оптимизация

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

Математическое программирование — дисциплина, изучающая теорию и методы решения задачи оптимизации. Постановка задачи оптимизации

Мы часто сталкиваемся с проблемой, когда из нескольких вариантов требуемся сделать выбор. Выбор предусматривает: · анализ ситуации; · сравнение вариантов по тому или иному критерию; · выбор наилучшего (с вашей точки зрения). Optimum в переводе с греческого означает «лучший». Варианты, из которых производится выбор – альтернативы. При решении задачи оптимизации мы решаем для себя следующие проблемы: 1. Что нужно улучшить? (определяем предмет оптимизации)э 2. Что значит «лучше»? (увеличить ил уменьшить?) 3. За счет чего можно добиться улучшения? (выбор параметров) 4. В каких пределах можно изменять выбранные параметры? (ОДЗ, ограничения). Отвечая на все поставленные вопросы, мы формулируем «критерий оптимизации» (как правило в количественном выражении). Что позволяет выразить количественное выражение величины, зависящее от параметров? Конечно функция, представляющая собой некоторую математическую модель оптимизируемого процесса. Такую функцию называют критериальной (или целевой). Как всякая функция, целевая функция имеет свои параметры – параметры оптимизации. , где f - имя критериальной функции, а x, y, z – параметры оптимизации.

По количеству независимых переменных различают задачи одномерной оптимизации (n=1) и многомерной оптимизации (n³ 2).

При этом задача нахождения максимума целевой функции сводится к задаче нахождения минимума путем замены функции f(x) на -f(x), поэтому в дальнейшем будем говорить только о поиске минимума функции, то есть такого x*Î[a, b], при котором f(x*) = minf(x).

Действительно, как видно из рисунка, найдя точку x* при f(x) = -f(x), мы можем найти f(x*).

В области допустимых значений функция f(x) может иметь несколько экстремумов (минимумов или максимумов - рис. 4.6.1).

Говорят, что функция f(x) имеет в точке x* локальный минимум, если существует некоторая положительная величина d, такая, что если ½х – х*½<d, то f(x)³f(x*), т.е. существует d - окрестность точки х*, такая, что для всех значений х в этой окрестности f(x)³f(x*).

Функция f(x) имеет глобальный минимум в точке x*, если для всех х справедливо неравенство f(x)³f(x*).

Таким образом, глобальный минимум является наименьшим из локальных.

Рис. 1.6.1-1

Если допустимое множество , то такая задача называется задачей безусловной оптимизации, в противном случае — задачей условной оптимизации.