Целевая функция: различия между версиями
| [отпатрулированная версия] | [отпатрулированная версия] |
Содержимое удалено Содержимое добавлено
Нет описания правки |
|||
Строка 1:
'''Целевая функция''' — вещественная или целочисленная [[функция (математика)|функция]] нескольких переменных, подлежащая [[оптимизация (математика)|оптимизации]] ([[Минимум (математика)|минимизации]] или [[Максимум (математика)|максимизации]]) в целях решения некоторой оптимизационной задачи. Термин используется в математическом программировании, [[Исследование операций|исследовании операций]], [[Линейное программирование|линейном программировании]], [[теория статистических решений|теории статистических решений]] и других областях математики в первую очередь прикладного характера, хотя целью оптимизации может быть и решение собственно математической задачи<ref>{{книга
|часть = Целевая функция, математическое программирование
|заглавие = Математический энциклопедический словарь
Строка 7:
|место = М.
|издательство = [[Большая Российская энциклопедия (издательство)|«Сов. энциклопедия »]]
}}</ref>. Помимо целевой функции в задаче оптимизации для переменных могут быть заданы ограничения в виде системы равенств или неравенств. В общем случае аргументы целевой функции могут задаваться на произвольных множествах.
== Примеры ==
Задача решения любой [[Система уравнений|системы уравнений]]
: <math> \left\{ \begin{matrix} F_1(x_1, x_2, \ldots, x_M) = 0 \\ F_2(x_1, x_2, \ldots, x_M) = 0 \\ \ldots \\ F_N(x_1, x_2, \ldots, x_M) = 0 \end{matrix} \right. </math>
Строка 17 ⟶ 18 :
может быть сформулирована как задача минимизации целевой функции
: <math>S = \sum_{j=1}^N F_j^2(x_1, x_2, \ldots, x_M) \qquad (1)</math>
Если функции гладкие, то задачу минимизации можно решать [[Градиентные методы|градиентными методами]].
Если функции гладкие, то задачу минимизации можно решать [[Градиентные методы|градиентными методами]]. Также при этом условии приравнивание к <math>0</math> частных производных целевой функции позволяет построить систему уравнений [[метод наименьших квадратов|метода наименьших квадратов]] (МНК). Всякое решение исходной системы является решением системы МНК. Если исходная система несовместна, то система МНК позволяет получить приближённое решение. Число уравнений системы МНК всегда совпадает с числом неизвестных, что иногда облегчает и решение совместных систем.▼
▲
Другим известным примером целевой функции является линейная функция, которая возникает в задачах линейного программирования. В отличие от квадратичной целевой функции оптимизация линейной функции возможна только при наличии ограничений в виде системы линейных равенств и неравенств.▼
=== Линейное программирование ===
▲Другим известным примером целевой функции является линейная функция, которая возникает в задачах линейного программирования. В отличие от квадратичной целевой функции оптимизация линейной функции возможна только при наличии ограничений в виде системы линейных равенств
=== Комбинаторная оптимизация ===
Типичным примером [[Комбинаторная оптимизация|комбинаторной]] целевой функции является целевая функция [[Задача коммивояжёра|задачи коммивояжёра]]. Эта функция равна длине [[Гамильтонов цикл|гамильтонова цикла]] на [[Граф (математика)|графе]]. Она задана на множестве перестановок <math>n-1</math> вершины графа <ref>Такая перестановка однозначно задаёт гамильтонов цикл.</ref> и определяется матрицей длин рёбер графа. Точное решение подобных задач часто сводится к перебору вариантов.
== Примечания ==
| |||