🗊Презентация Задачи нелинейного программирования

Задачи нелинейного программирования Общая задача НП заключается в отыскании экстремального значения ЦФ, зависящей от n переменных. Точка Х0 является точкой максимума, если в ее окрестностях значение функции f(X) не превосходит f(Х0). Для минимума - f(Х)≤f(Х0).

Рассмотрим функцию f(X) на отрезке [a,b]. . Рассмотрим функцию f(X) на отрезке [a,b]. .

Необходимое условие существования экстремума функции f(x) в точке x0 является равенство нулю градиента функции в этой точке grad f(x0)=0 Необходимое условие существования экстремума функции f(x) в точке x0 является равенство нулю градиента функции в этой точке grad f(x0)=0 grad f(X)=(df/dx1,……..df/dxn) – задает угол наклона касательной к графику функции. Это условие не является достаточным, т.к. оно выполняется для точек перегиба и седловых точек, их называют стационарными точками.

Методы решения задач НП

Аналитические методы Основаны на использовании необходимых и достаточных условий экстремумов функций. Для их использования необходимо, чтобы ЦФ и функции ограничений были непрерывными вместе с их частными производными первого порядка.

Численные методы Для поиска экстремума функции, зависящей от 1-й переменной. Выделяется диапазон значений x , на котором может находиться точка экстремума, затем диапазон сужается до тех пор, пока не будет найдена точка экстремума с заданной точностью

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

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

Градиентные методы Основаны на использовании градиента ЦФ (градиент в точке указывает направление скорейшего возрастания функции). Пошаговый переход от одного допустимого решения к другому в направлении градиента. Получаем приближенное решение с заданной точностью. Это наиболее универсальные методы.

Непрямые методы Сведение задачи НП к более простой задаче, например задаче ЛП. В зависимости от вида ЦФ и функций ограничений выделяют следующие классы

Методы квадратичного программирования Целевая функция представляет собой сумму линейной функции и квадратичной формы, а функции ограничений являются линейными функциями. F=∑cjxj+∑∑aikxjxk j=1,n k=1,n

Методы сепарабельного программирования Функции ограничений сепарабельны: F(x1….xn)=F1(x1)+…+Fn(xn) Методы решения основаны на линейной аппроксимации ЦФ и применении симплекс-метода.

Методы геометрического программирования. Целевая функция и функции ограничений являются полиномами и имеют следующий вид: F=∑uk

Методы стохастического программирования. Целевая функция и функции ограничений являются линейными, но при этом коэффициенты aij, bi – случайные числа, а ограничения должны выполняться с некоторыми вероятностями.

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

Вектор Вектор

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

Для задачи ЛП множество допустимых решений задачи образует выпуклый многогранник, при этом оптимальное решение достигается в одной из его вершин, т.е. за конечное число шагов мы можем найти оптимальное решение (если оно существует). Для задачи ЛП множество допустимых решений задачи образует выпуклый многогранник, при этом оптимальное решение достигается в одной из его вершин, т.е. за конечное число шагов мы можем найти оптимальное решение (если оно существует). В НП множество допустимых решений образует область, которая не всегда выпукла. Оптимальное решение может находиться не только на границе области, но и в любой внутренней точке. Следовательно, его нельзя найти с помощью перебора.

В ЛП множество точек, в которых ЦФ принимает постоянное значение есть гиперплоскость c1x1+……cnxn=const. При различных значениях const мы получаем параллельные гиперплоскости. В ЛП множество точек, в которых ЦФ принимает постоянное значение есть гиперплоскость c1x1+……cnxn=const. При различных значениях const мы получаем параллельные гиперплоскости. В НП множество точек, в которых ЦФ принимает постоянное значение есть гиперповерхность f(x1……xn)=const. При различных значениях const мы получаем гиперповерхности, которые могут пересекаться.

Геометрический метод решения задач НП Если определена область допустимых решений, то нахождение решения задачи нелинейного программирования сводится к определению такой точки этой области, через которую проходит гиперповерхность наивысшего уровня (в случае максимизации) или наинизшего уровня (в случае минимизации):

Решение задачи нелинейного программирования графическим способом : Находят область допустимых решений задачи. Если она пуста, то задача решения не имеет. Строят гиперповерхность .

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

Пример. Найти максимальное и минимальное значение функции При выполнении условий

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

Полагая значение целевой функции F равным некоторому числу h, получаем линии уровня

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

Рассматривая X2 как неявную функцию от переменной X1 и дифференцируя уравнение окружности, получим Рассматривая X2 как неявную функцию от переменной X1 и дифференцируя уравнение окружности, получим

получим систему: получим систему:

Целевая функция F принимает максимальное значение в точке C.. Целевая функция F принимает максимальное значение в точке C..

Координаты точки C находят решая систему уравнений, соответствующих прямым BC и AC Координаты точки C находят решая систему уравнений, соответствующих прямым BC и AC