Тема 2. 2 нелинейное программирование

 

Как известно, общая задача математического программирования формулируется следующим образом: найти вектор , удовлетворяющий системе ограничений:

£ b_i, i =1,…, m, (система иногда представляется через знак "=", но равенства всегда можно переделать в неравенства) и доставляющий экстремум функции . При этом предполагается, что известны функции   и . Обычно на некоторые переменные из набора   накладывается условие неотрицательности.

Если   и , где   и  - известные константы, то при условии неотрицательности решения получаем задачу линейного программирования. Любую другую задачу математического программирования, не удовлетворяющую таким условиям, будем считать нелинейной.

Задачи нелинейного программирования делятся на следующие типы:

1. Когда нелинейная ЦФ и линейная – система ограничений;

2. Линейная ЦФ и нелинейные ограничения;

3. Нелинейная ЦФ и система нелинейных ограничений.

Особенностью поиска экстремума в задачах нелинейного программирования является то, что решение может находиться как в вершинах ОДР, так на ребрах и внутри ОДР. Может быть несколько локальных экстремумов внутри или на границе ОДР. Как правило, ограничиваются поиском первого локального экстремума.

Оптимальное решение – значение вектора входных параметров x* = x₁,x₂,x_n и соответствующее ему значение ЦФ. L(x*) – достигающая максимального значения.

Локальным оптимальным решением называется значение ЦФ L(x*) экстремальная в некоторой дельта окрестности.

Глобальным оптимальным решением является экстремальное значение ЦФ во всей ОДР.

Допустимость – любой вектор x входных параметров, удовлетворяющий условиям ограничений называется допустимым вектором или допустимой точкой. Множество допустимых точек задает ОДР.

Если наилучшее решение, но не экстремальное находится на границе ОДР, то такое решение называется условно оптимальным.

Ограничение в виде неравенства обеспечивает нахождение вектора входных параметров внутри ОДР.

Ограничение в виде равенства обеспечивает нахождения вектора входных параметров на пересечении гиперповерхностей.

Допустимые или внутренние точки могут находиться внутри ОДР, внутри ОДР на пересечение гиперплоскостей или на границе ОДР. Точки, лежащие за пределами ОДР, называются недопустимыми или внешними.

Градиент. Линией уровня называется множество точек, на которых ЦФ имеет постоянные значения. Если в какой-либо точке функция непрерывна и дифференцируема, то в этой точке существует градиент ЦФ. Градиент указывает направление наискорейшего возрастания функции, антиградиент – противоположные направления – убывания. Градиент определяется как вектор-столбец первых частных производных целевой функции L(x) по переменной x.

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

Линейная аппроксимация выполняется с помощью усеченного ряда Тейлора в окрестности точки x. Квадратичная получается из разложения в ряд Тейлора путем отбрасывания членов третьего и старшего порядков.

Необходимые и достаточные условия оптимальности решения

Полностью критерии оптимальности для задач НЛП не разработаны. Он формулируется для некоторого круга задач. Необходимыми условиями нахождения локального экстремума функции является:

1. ЦФ дифференцируема в точке x*;

2. Если первая производная ЦФ равна 0 в точке x*, то эта точка является стационарной.

Достаточными условиями существования локального экстремума являются названные необходимые условия и следующие: вторые производные ЦФ должны быть положительно определены. В случае поиска максимального значения вторые производные должны быть отрицательно определены.