8 Общая постановка задачи нелинейного программирования, геометрический смысл, примеры. Классификация методов решения задач нелинейного программирования.

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

В отличие от задач линейного программирования, для задач нелинейного программирования не существует общего метода, позволяющего решать любые оптимизационные нелинейные задачи. Геометрический смысл: область допустимых решений может быть невыпуклой, а целевая функция может достигать экстремума не только на границе, но и внутри области допустимых решений системы ограничений. Кроме того, нелинейная целевая функция может иметь несколько локальных экстремумов, среди которых необходимо найти глобальный. А у выпуклых (вогнутых) моделей нелинейного программирования локальный экстремум обязательно является и глобальным экстремумом. Объемное изображение функции: f(x)=10-(x₁-2)²-(x₂-2)² в области определенном ограничениями 0<=x1<=4, 0<=x2<=4. Нелинейность характерна для финансовых, технических, биологических и других процессов.

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

1)экстремальные задачи без ограничений;

2)задачи выпуклого программирования;

2.1)задачи дробнолинейного прогр-я(локальный экстремум обязательно является глобальным);

2.2)задачи квадратичного прогр-я(степень выше 2);

3)задачи невыпуклого программирования.

Методы решения нелинейных задач:

1. аналитический(установление некоторой функциональной зависимости между исходными задачи и ее точным решением);

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

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

Аналитический метод - Метод множителей Лагранжа(В случае задач оптимизации с непрерывно дифференцируемом по всей переменной целевой функцией и ограничениями в форме равенств).

Алгоритмический метод:

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

2. метод Ньютона относится к методам второго порядка, в которых целевая функция в текущей точке апроксимируется в квадратичной функции в разложении в ряд Тейлора. Направлении и величина шага в уравнении Ньютона ведут в точку min функции 2-го порядка, которой заменяются исходная функция в текущей точке. При этом осуществляется переход в центр эллипсоида, построенного в точке x_k, если целевая функция квадратичная, то min достигается всего за 1 шаг.)

Метод ньютона запрашивает больше памяти, но выполняет меньше итераций, чем метод сопряженных градиентов. Если задача слишком велика и если итерации дают малое различие в последовательных вычислениях, то необходимо экономить память.)2.методы нахождения приближенного решения.