Нелинейная задача оптимизации. Условный экстремум.

 

Задача нелинейного программирования ставится как задача нахождения оптимума определенной целевой функции при выполнении условий:

, ,

где , — параметры, , - ограничения, — количество параметров, — количество ограничений. Целевая функция или ограничение есть нелинейная функция

В отличие от задачи линейного программирования, в задаче программирования нелинейного оптимум не обязательно лежит на границе области, определенной ограничениями.

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

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

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

. (1.29)

Задачи НЛП несравнимо сложнее задач ЛП, и для них не существует общего, универсального метода решения (аналогично симплексному методу).Есть целый ряд методов решения задач НЛП. В пакете Excel реализован метод мно­жителей Лагранжа, идея которого заключается в следующем: задачу условной оптимизациипреобразуют взадачу безусловной оптимизациии решают последнюю либо градиентными методами, либо методами Ньютона. Чаще применяются градиентные методы.

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

Следует отметить, что в подавляющем большинстве практиче­ских задач оптимизации существует только один оптимум.

Решение задачи НЛП (реализация модели нелинейной оптимизации) средствами Excel отличается от решения ЗЛП следующим:

§ назначаются начальные значения искомых переменных , так, чтобы ЦФ в начальной точке не была равна нулю:

0;

§ в диалоговом окне Поиск решения в режиме Параметры не надо вводить флажок Линейная модель.

В Excel на каждой итерации вычисляется величина относительного приращения целевой функции

(1.30)

Оптимум считается достигнутым, если выполняется условие

,

где - относительная погрешность, назначаемая при решении задачи (режим Параметры).

Пример 4. Через точку провести плоскость, образующую с плоскостями координат тетраэдр наименьшего объема.

Решение.

Переменные - отрезки, которая плоскость отсекает на осях координат.

Целевая функция- объем тетраэдра, который надо минимизировать:

Ограничение на переменные накладывает задание точки :

Рабочий лист Excel может быть по дготовлен в виде, представленном на рис. 1.22., формулы этого листа приведены в ячейках DЗ:D4.

 

 

Рисунок.1.22. Исходные данные, условия и полученное решение задачи

 

Ответ. Реализуя решение приведенной задачи средствами Excel (рис. 1.6.1), получим величины отрезков, при которых достигается оптимум . Объем тетраэдра равен .