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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Содержание:

 

Введение. ……..………………………………………………………………………………...3

I Классификация методов решения задач нелинейного программирования. Особенности задач не линейного программирования. Примеры. ………………………………………………..4

1. Общая задача нелинейного программирования. …………………………………………….4

2. Метод множителей Лагранжа. ………………………………………………………………..5

3. Выпуклое программирование. ………………………………………………………………..6

4. Задача выпуклого программирования. ………………………………………………………7

5. Квадратичное программирование. …………………………………………………………...9

6. Градиентные методы. …………………………………………………………………………9

7. Особенности задач нелинейного программирования. …………………………………….11

II Краткая характеристика метода конфигураций Хука-Дживса. Алгоритм Хука-Дживса. Задача на данный алгоритм. ……………………………………………………………………….12

1. Метод Конфигураций Хука-Дживса. ……………………………………………………….12

2. Алгоритм метода Хука-Дживса. ………………………………………………………….....12

Заключение. ………………………………………………………………………………..…15

Список используемой литературы. ………………………………………………………....16

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Введение

 

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

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

I Классификация методов решения задач нелинейного программирования. Особенности задач не линейного программирования. Примеры.

 

1. ОБЩАЯ ЗАДАЧА НЕЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

 

В общем виде задача нелинейного программирования состоит в определении максимального (минимального) значения функции       (1)

при условии  ,    (2)

где и   - некоторые известные функции n переменных, а - заданные числа.

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

 

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

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

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

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

•    (2а)

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

 

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

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

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

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

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

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

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

 Пример 1

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

 при ограничении          

 Исключив переменную , с помощью уравнения , получим оптимизационную задачу с двумя переменными без ограничений min

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

 

2. МЕТОД МНОЖИТЕЛЕЙ ЛАГРАНЖА

 

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

,

 

находят частные производные 

и рассматривают систему n+m  уравнений

                       (3)

 

с n+m неизвестными , . Решив систему уравнений (3), получают все точки, в которых функция (1) может иметь экстремальные значения. Дальнейшее исследование найденных точек проводят так же, как и в случае безусловного экстремума. Метод множителей Лагранжа имеет ограниченное применение, так как система (3), как правило, имеет несколько решений.

 

Пример 2

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

 при ограничении   =0

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

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

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

 

 

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

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

 

3. ВЫПУКЛОЕ   ПРОГРАММИРОВАНИЕ

 

Определение: Функция  , заданная   на   выпуклом   множестве   X, называется выпуклой, если для любых двух точек и из X и любого выполняется соотношение

     (4)                              

Определение: Функция ,   заданная    на   выпуклом   множестве X, называется вогнутой, если для любых двух точек и из X и любого выполняется соотношение

   (5)

Если неравенства (4) и (5) считать строгими и они  выполняются при , то функция является строго выпуклой (строго вогнутой). Выпуклость и вогнутость функций определяется только относительно выпуклых множеств.

Если , где , - выпуклые (вогнутые) функции на некотором выпуклом множестве , то функция f(x) - также выпуклая (вогнутая) на X.

Основные  свойства выпуклых и вогнутых функций:

1. Множество точек минимума выпуклой функции, заданной на выпуклом множестве, - выпукло.

2.  Пусть f(x) - выпуклая функция, заданная на замкнутом выпуклом множестве . Тогда локальный минимум f(x) на X является и глобальным.

 

3.  Если глобальный  минимум достигается в двух различных точках, то он достигается и в любой точке отрезка, соединяющего данные точки.

4.  Если f(x) - строго выпуклая функция, то ее глобальный минимум на выпуклом множестве X достигается в единственной точке.

5.  Пусть функция f(x) - выпуклая функция, заданная на выпуклом множестве X, и, кроме того, она непрерывна вместе со своими частными производными первого порядка во всех внутренних точках X. Пусть - точка, в которой . Тогда в точке достигается локальный минимум, совпадающий с глобальным минимумом.

6. Множество  точек глобальных (следовательно,  и локальных) минимумов выпуклой  функции f(x) , заданной на ограниченном замкнутом выпуклом множестве X, включает хотя бы одну крайнюю точку; если множество локальных минимумов включает в себя хотя бы одну внутреннюю точку множества X, то f(x)   является функцией-константой.

 

4. ЗАДАЧА ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ

 

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

       (6)

при ограничениях

,    (7)

.    (8)

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

Говорят, что множество  допустимых решений задачи (6) - (8) удовлетворяет условию регулярности, или условию Слейтера, если существует, по крайней мере, одна точка , принадлежащая области допустимых решений такая, что . Задача (6) - (8) называется задачей выпуклого программирования, если функция   является вогнутой (выпуклой), а функции   - выпуклыми. Функцией Лагранжа задачи выпуклого программирования (6) - (8) называется функция

,

где - множители Лагранжа.

Точка называется седловой точкой функции Лагранжа, если для всех и .

Теорема 1 (Куна - Таккера): Для задачи выпуклого программирования (6) - (8), множество допустимых решений которой обладает свойством регулярности, является оптимальным решением тогда и только тогда, когда существует такой вектор   , что - седловая точка функции Лагранжа.