Южно-Уральский Государственный Университет

Кафедра АиУ

реферат на тему:

Нелинейное программирование

Выполнил: Пушников А. А., ПС-263.

Проверил: Разнополов О.А.

Челябинск – 2003.

Оглавление

1.         Постановка задачи нелинейного программирования

2.         Критерии оптимальности в задачах с ограничениями

2.1.     Задачи с ограничением в виде равенств

2.2.     Множители Лагранжа

3.         Условия Куна-Таккера

3.1.     Условия Куна-Таккера и задача Куна-Таккера

3.2.     Интерпретация условий Куна-Таккера

3.3.     Теоремы Куна-Таккера

4.         Функции нескольких переменных

4.1.     Методы прямого поиска

4.1.1. Метод поиска по симплексу (S2 - метод)

4.1.2. Метод поиска Хука-Дживса

1. Постановка задачи нелинейного программирования.

В задаче нелинейного программирования (НЛП) требуется найти значение многомерной переменной х=(), минимизирующее целевую функцию f(x) при условиях, когда на переменную х наложены ограничения типа неравенств

 ,   i=1,2,…,m                                 (1)

а переменные , т.е. компоненты вектора х, неотрицательны:

                                                          (2)

Иногда в формулировке задачи ограничения (1) имеют противоположные знаки неравенств. Учитывая, однако, что если  , то  , всегда можно свести задачу к неравенствам одного знака. Если некоторые ограничения входят в задачу со знаком равенства, например , то их можно представить в виде пары неравенств , , сохранив тем самым типовую формулировку задачи.

2. Критерии оптимальности в задачах с ограничениями.

Ряд инженерных задач связан с оптимизацией при наличии некоторого количества ограничений на управляемые пере­менные. Такие ограничения существенно уменьшают размеры об­ласти, в которой проводится поиск оптимума. На первый взгляд может показаться, что уменьшение размеров допустимой области должно упростить процедуру поиска оптимума. Между тем, напро­тив, процесс оптимизации становится более сложным, поскольку установленные выше критерии оптимальности нельзя использовать при наличии ограничений. При этом может нарушаться даже ос­новное условие, в соответствии с которым оптимум должен достигаться в стационарной точке, характеризующейся нулевым гра­диентом. Например, безусловный минимум функции  имеет место в стационарной точке х=2. Но если задача минимиза­ции решается с учетом ограничения , то будет найден условный минимум, которому соответствует точка x=4. Эта точка не является стационарной точкой функции f, так как (4)=4. Далее исследуются необходимые и достаточные условия оптимальности решений задач с ограничениями. Изложение начинается с рассмот­рения задач оптимизации, которые содержат только ограничения в виде равенств.

  2.1. Задачи с ограничениями в виде равенств

Рассмотрим общую задачу оптимизации, содержащую несколь­ко ограничений в виде равенств:

Минимизировать            

при ограничениях           ,  k=1,…,n

Эта задача в принципе может быть решена как задача безусловной оптимизации, полученная путем исключения из целевой функции k независимых переменных с помощью заданных равенств. Наличие ограничений в виде равенств фактически позволяет уменьшить размерность исходной задачи с n до n-k.. ............