Целевая функция

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Целевая функция — вещественная или целочисленная функция нескольких переменных, подлежащая оптимизации (минимизации или максимизации) в целях решения некоторой оптимизационной задачи. Термин используется в математическом программировании, исследовании операций, линейном программировании, теории статистических решений и других областях математики в первую очередь прикладного характера, хотя целью оптимизации может быть и решение собственно математической задачи[1]. Помимо целевой функции в задаче оптимизации для переменных могут быть заданы ограничения в виде системы равенств или неравенств. В общем случае аргументы целевой функции могут задаваться на произвольных множествах.

Примеры[править | править вики-текст]

Гладкие функции и системы уравнений[править | править вики-текст]

Задача решения любой системы уравнений

может быть сформулирована как задача минимизации целевой функции

Если функции гладкие, то задачу минимизации можно решать градиентными методами.

Для всякой гладкой целевой функции можно приравнять к частные производные по всем переменным. Оптимум целевой функции будет одним из решений такой системы уравнений. В случае функции это будет система уравнений метода наименьших квадратов (МНК). Всякое решение исходной системы является решением системы МНК. Если исходная система несовместна, то всегда имеющая решение система МНК позволяет получить приближённое решение исходной системы. Число уравнений системы МНК совпадает с числом неизвестных, что иногда облегчает и решение совместных исходных систем.

Линейное программирование[править | править вики-текст]

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

Комбинаторная оптимизация[править | править вики-текст]

Типичным примером комбинаторной целевой функции является целевая функция задачи коммивояжёра. Эта функция равна длине гамильтонова цикла на графе. Она задана на множестве перестановок вершины графа [2] и определяется матрицей длин рёбер графа. Точное решение подобных задач часто сводится к перебору вариантов.

Примечания[править | править вики-текст]

  1. Целевая функция, математическое программирование // Математический энциклопедический словарь. — М.: «Сов. энциклопедия », 1988.
  2. Такая перестановка взаимно однозначно задаёт гамильтонов цикл для асимметричной матрицы длин рёбер графа.

См. также[править | править вики-текст]

Литература[править | править вики-текст]

  • Бурак Я. И., Огирко И. В. Оптимальный нагрев цилиндрической оболочки с зависящими от температуры характеристиками материала // Мат. методы и физ.-мех. поля. — 1977. — Вып. 5. — С.26-30