Вид оптимизационной задачи

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

Пусть f(x) – функция, определённая на множестве V, а Ω - некоторое подмножество множества V.

Оптимизационная задача задается тройкой (V, F, Ω). При этом функция f(x) называется целевой функцией, а Ω – допустимым множеством (множеством допустимых значений) оптимизационной задачи.

Оптимизационные задачи бывают двух типов: задачи минимизации и задачи максимизации. Задача минимизации (максимизации) (V, F, Ω) состоит в отыскивании наименьшего (наибольшего) значения целевой функции f(x) на допустимом множестве Ω.

Для того, чтобы решить задачу минимизации (максимизации) (V, F, Ω), достаточно найти её оптимальное решение, т.е. указать x₀ÎΩ такое, что f(x₀)£f(x₁…,x_n)=f(x) (или f(x₀)³f(x)) при любом xÎΩ.

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

Решить оптимизационную задачу – значит либо найти её оптимальное решение, либо установить неразрешимость этой задачи.

Любая задача максимизации (V, F, Ω) сводится к задаче минимизации (V, -F, Ω): эти задачи либо обе неразрешимы, либо имеют одно и тоже оптимальное решение.

Две задачи минимизации (максимизации) называются эквивалентными, если они имеют одно и тоже множество допустимых решений. На любом допустимом решении значения целевых функций этих задач совпадают. Эквивалентные оптимизационные задачи либо обе неразрешимы, либо имеют одно и тоже оптимальное решение.

Методы решения оптимизационных задач, в которых целевая функция является функцией n переменных, часто называют методами математического программирования. Термин «программирование» в данном случае обусловлен тем, что в задачах имеется некоторая программа действий, это не программирование на ЭВМ. В зависимости от вида целевой функции, которая может быть линейной или нелинейной, в математическом программировании выделяют основные разделы:

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

- нелинейное (выпуклое программирование).