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

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

Кафедра АиУ


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


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


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

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


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

Оглавление


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

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

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

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

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

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

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

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

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

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

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

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

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.. В качестве иллюстрации рассмотрим следующий пример.

Пример 1

Минимизировать Нелинейное программирование

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

Исключив переменную Нелинейное программирование, с помощью уравнения Нелинейное программирование, получим

оптимизационную задачу с двумя переменными без ограничений

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

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

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

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


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


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

Рассмотрим задачу минимизации функции n переменных с уче­том одного ограничения в виде равенства:

Минимизировать Нелинейное программирование (3)

при ограничениях Нелинейное программирование (4)

В соответствии с методом множителей Лагранжа эта задача преобразуется в следующую задачу безусловной оптимизации:

минимизировать L(x,u)=f(x)-u*h(x) (5)

Функция L(х;u) называется функцией Лагранжа, u — неизвест­ная постоянная, которая носит название множителя Лагранжа. На знак u никаких требований не накладывается.

Пусть при заданном значении u=u0 безусловный минимум функ­ции L(x,u) по х достигается в точке Нелинейное программирование и Нелинейное программирование удовлетворяет урав­нению Нелинейное программирование. Тогда, как нетрудно видеть, x0 минимизирует (1) с учетом (4), поскольку для всех значений х, удовлетворяющих (4), Нелинейное программирование и L(x,u)=min f(x).

Разумеется, необходимо подобрать значение u=u° таким обра­зом, чтобы координата точки безусловного минимума х° удовлетво­ряла равенству (4). Это можно сделать, если, рассматривая u как переменную, найти безусловный минимум функции (5) в виде функции u, а затем выбрать значение u, при котором выполняется равенство (4). Проиллюстрируем это на конкретном примере.

Пример 2

Минимизировать Нелинейное программирование

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

Соответствующая задача безусловной оптимизации записывается в следующем виде:

минимизировать L(x,u)= Нелинейное программирование-uНелинейное программирование

Решение. Приравняв две компоненты градиента L к нулю, получим

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

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

Для того чтобы проверить, соответствует ли стационарная точка х° минимуму, вычислим элементы матрицы Гессе функции L(х;u), рассматриваемой как функция х,

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

которая оказывается положительно определенной. Это означает, что L(х,,u) — выпуклая функция х. Следовательно, координаты Нелинейное программирование ,Нелинейное программирование определяют точку глобального минимума. Оптималь­ное значение u находится путем подстановки значений Нелинейное программирование и Нелинейное программирование в урав­нение Нелинейное программирование=2, откуда 2u+u/2=2 или Нелинейное программирование. Таким образом, условный минимум достигается при Нелинейное программирование и Нелинейное программированиеНелинейное программирование и равен min f(x)=4/5.

При решении задачи из примера 2 мы рассматривали L(х;u) как функцию двух переменных Нелинейное программирование и Нелинейное программирование и, кроме того, предполагали, что значение параметра u выбрано так, чтобы выполнялось ограни­чение. Если же решение системы

Нелинейное программирование, j=1,2,3,…,n

в виде явных функций u получить нельзя, то значения х и u нахо­дятся путем решения следующей системы, состоящей из n+1 урав­нений с n+1 неизвестными:

Нелинейное программирование , j=1,2,3,…,n Нелинейное программирование

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

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

Минимизировать f(x)

при ограничениях Нелинейное программирование=0, k=1, 2, ..., К.

Функция Лагранжа принимает следующий вид:

L(x,u)=f(x)-Нелинейное программирование

Здесь Нелинейное программирование—множители Лагранжа, т.е. неизвестные параметры, значения которых необходимо определить. Приравни­вая частные производные L по х к нулю, получаем следующую систему n уравнении с n неизвестными:

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

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

………..

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

Если найти решение приведенной выше системы в виде функций вектора u оказывается затруднительным, то можно расширить систему путем включения в нее ограничений в виде равенств

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

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


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

Решение расширенной системы, состоящей из n+К уравнений с n+К неизвестными, определяет стационарную точку функции L. Затем реализуется процедура проверки на минимум или максимум, которая проводится на основе вычисления элементов матрицы Гессе функции L, рассматриваемой как функция х, подобно тому, как это было проделано в случае задачи с одним ограничением. Для некоторых задач расширенная система n+К уравнений с n+K неизвестными может не иметь решений, и метод множителей Лагранжа оказывается неприменимым. Следует, однако, отметить, что такие задачи на практике встречаются достаточно редко.

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


В предыдущем разделе было установлено, что множители Лаг­ранжа можно использовать при построении критериев оптималь­ности для задач оптимизации с ограничениями в виде равенств. Кун и Таккер обобщили этот подход на случай общей задачи нели­нейного программирования с ограничениями, как в виде равенств, так и в виде неравенств.

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

минимизировать Нелинейное программирование (0)

при ограничениях Нелинейное программирование (1)

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

Определение:

Ограничение в виде неравенства Нелинейное программирование называется активным, или связывающим, в точке Нелинейное программирование, если Нелинейное программирование, и неактивным, или несвязывающим, если Нелинейное программирование

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

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

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


Найти векторы Нелинейное программирование ,удовлетворяющие следующим условиям

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

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

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

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

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

Прежде всего проиллюстрируем условия Куна — Таккера на примере.

Пример 3

Минимизировать Нелинейное программирование

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

Решение.

Записав данную задачу в виде задачи нелиней­ного программирования (0)-(2), получим

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

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

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

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

Уравнение (3), входящее в состав условий Куна—Таккера, принимает следующий вид:

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

откуда

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

Неравенства (4) и уравнения (5) задачи Куна — Таккера в данном случае записываются в виде

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

Уравнения (5.16), известные как условие дополняющей нежесткости, принимают вид

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

Заметим, что на переменные Нелинейное программирование и Нелинейное программирование накладывается требование не­отрицательности, тогда как ограничение на знак Нелинейное программирование отсутствует.

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

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


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


Для того чтобы интерпретировать условия Куна — Таккера, рассмотрим задачу нелинейного программирования с ограничения­ми в виде равенств:

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

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

Запишем условия Куна—Таккера

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

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

Далее рассмотрим функцию Лагранжа для задачи нелинейного программирования с ограничениями в виде равенств

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

Для этой функции условия оптимальности первого порядка запи­сываются в виде

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

Нетрудно видеть, что условия Куна-Таккера (8) и (9) совпадают с условиями оптимальности первого порядка для задачи Лагранжа.

Рассмотрим задачу нелинейного программирования с ограни­чениями в виде неравенств:

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

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

Запишем условия Куна—Таккера

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

Соответствующая функция Лагранжа имеет вид

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

Условия оптимальности первого порядка записываются как

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

Заметим, что Нелинейное программирование- множитель Лагранжа, соответствующий ограни­чению Нелинейное программирование. Раньше было показано, что Нелинейное программирование представляет неявную цену, ассоциированную с ограничением Нелинейное программирование; другими словами, вели­чина Нелинейное программирование отражает изменение минимального значения целевой функ­ции Нелинейное программирование, вызываемое единичным приращением правой части Нелинейное программирование- го ог­раничения.

Если предположить, что Нелинейное программирование- е ограничение является неактивным (т.е. Нелинейное программирование С другой стороны, если Нелинейное программирование-е ограничение активное (т. е. Нелинейное программирование), то соответствующая неявная цена

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

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: