Задача математического программирования формулируется следующим образом: найти значения переменных х 1, х 2,…, х n,, доставляющие максимум или минимум целевой функции y = f (х 1, х 2,…, х n) при условиях gj (х 1, х 2,…, х n) = (£, ³) bj, (
).
Особенность задач нелинейного программирования заключается в том, что функции y и (или) gj не линейны. Разработано множество численных методов решения задач нелинейного программирования.
Классификация численных методов решения задач нелинейного программирования
Универсального метода, с помощью которого можно было бы решить любую задачу оптимизации, не существует. Поэтому для решения конкретной задачи применяют один или несколько численных методов.
Численные методы поиска экстремума функции одной переменной:
- классический метод;
- метод равномерного перебора;
- метод золотого сечения;
- метод Фибоначчи и т. д.
Численные методы поиска экстремума функции n-переменных:
- метод покоординатного спуска;
- метод линеаризации;
- метод Ньютона;
- метод сопряженных направлений;
- метод условного градиента;
- метод барьерных функций;
- метод штрафных функций;
- метод Хука-Дживса и т. д.
Классический метод минимизации (максимизации) функции одной переменной
Этот метод применяется в однопараметрических задачах оптимизации. В них ищется один оптимальный параметр. Таким образом, целевая функция – это функция одной переменной.
Постановка задачи. Найти значение переменной х, доставляющее минимум или максимум целевой функции y = f (x), при условиях
gj (х) = (£, ³) bj, ().
Пусть a £ х £ b, функция f (x) непрерывна на этом отрезке и имеет на нём непрерывную производную. Вычисляют значение производной f ¢(x) и определяют критические точки, т. е. такие внутренние точки отрезка
[ a, b ], в которых производная обращается в нуль или не существует. В окрестности каждой такой критической точки исследуют знак производной и отбирают те из них, при переходе через которые производная меняет знак с минуса на плюс (точки локального минимума) или с плюса на минус (точки локального максимума). Затем вычисляют значения целевой функции в этих точках и на границах отрезка [ a, b ]. Эти значения сравнивают между собой и определяют точку, в которой достигается минимум (максимум) целевой функции. Эта точка является точкой глобального минимума (максимума) функции f (x) на отрезке [ a, b ].
При решении реальных задач оптимизации данный метод применяется редко, т. к. зачастую производную целевой функции определить сложно или невозможно.
