Задачи нелинейного программирования

Задача математического программирования формулируется следующим образом: найти значения переменных х ₁, х ₂,…, х _n,, доставляющие максимум или минимум целевой функции y = f (х ₁, х ₂,…, х _n) при условиях g_j (х ₁, х ₂,…, х _n) = (£, ³) b_j, ().

Особенность задач нелинейного программирования заключается в том, что функции y и (или) g_j не линейны. Разработано множество численных методов решения задач нелинейного программирования.

Классификация численных методов решения задач нелинейного программирования

Универсального метода, с помощью которого можно было бы решить любую задачу оптимизации, не существует. Поэтому для решения конкретной задачи применяют один или несколько численных методов.

Численные методы поиска экстремума функции одной переменной:

- классический метод;

- метод равномерного перебора;

- метод золотого сечения;

- метод Фибоначчи и т. д.

Численные методы поиска экстремума функции n-переменных:

- метод покоординатного спуска;

- метод линеаризации;

- метод Ньютона;

- метод сопряженных направлений;

- метод условного градиента;

- метод барьерных функций;

- метод штрафных функций;

- метод Хука-Дживса и т. д.

Классический метод минимизации (максимизации) функции одной переменной

Этот метод применяется в однопараметрических задачах оптимизации. В них ищется один оптимальный параметр. Таким образом, целевая функция – это функция одной переменной.

Постановка задачи. Найти значение переменной х, доставляющее минимум или максимум целевой функции y = f (x), при условиях
g_j (х) = (£, ³) b_j, ().

Пусть a £ х £ b, функция f (x) непрерывна на этом отрезке и имеет на нём непрерывную производную. Вычисляют значение производной f ¢(x) и определяют критические точки, т. е. такие внутренние точки отрезка
[ a, b ], в которых производная обращается в нуль или не существует. В окрестности каждой такой критической точки исследуют знак производной и отбирают те из них, при переходе через которые производная меняет знак с минуса на плюс (точки локального минимума) или с плюса на минус (точки локального максимума). Затем вычисляют значения целевой функции в этих точках и на границах отрезка [ a, b ]. Эти значения сравнивают между собой и определяют точку, в которой достигается минимум (максимум) целевой функции. Эта точка является точкой глобального минимума (максимума) функции f (x) на отрезке [ a, b ].

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