Общая задача нелинейного программирования. Условия Куна-Таккера


Скачать 38.94 Kb.
НазваниеОбщая задача нелинейного программирования. Условия Куна-Таккера
Дата публикации30.06.2013
Размер38.94 Kb.
ТипЗадача
userdocs.ru > Математика > Задача
Общая задача нелинейного программирования.

Условия Куна-Таккера
Рассмотрим следующую задачу поиска экстремума функции многих переменных при наличии ограничений:

(1)

где - n-мерное действительное евклидово пространство,



Задача (1) называется общей задачей нелинейного программирования.

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

Приведем задачу (1) к задаче с ограничениями в форме равенств при условии неотрицательности переменных. Для этого введем m-мерный вектор неотрицательных вспомогательных переменных



Теперь задачу (1) можно записать в виде:

(2)

1. Сначала исследуем эту задачу, исключив из не условия неотрицательности переменных. В этом случае вместо (2) мы будем иметь классическую задачу на условный экстремум:

(2′)

Составим функцию Лагранжа для этой задачи:



где - вектор неопределенных множителей Лагранжа.

Необходимое условие экстремума в задаче (2′) имеет вид:







Предположим, что эту систему мы решили, и - соответствующий вектор множителей Лагранжа из этого решения. Тогда, как было показано выше, задача (2′) равносильна задаче на безусловный экстремум

(3)

2. Теперь учтем в этой трансформированной задаче условия неотрицательности переменных: В результате приходим к задаче

(3′)

Необходимые условия экстремума для этой задачи, согласно приведенной выше теореме, имеют вид:







С учетом вида функции Лагранжа получим условия:





Кроме того, с учетом ограничений задачи (2) имеем:



Положив в полученных формулах получим условия:













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

Удобно записывать условия Куна-Таккера, используя привычную стандартную функцию Лагранжа



В этом случае условия Куна-Таккера можно записать так:

1)

2)

3)

4)

5)

6)

Замечание. В случае задачи на максимум функции f(x) в условии 1 нужно изменить направление неравенства (≤ 0). Условия 2 и 5 можно записать в компонентной форме:

2′)

5′)

Из условий Куна-Таккера 2 и 5 следует, что

(I)

(II)

Определение. Условия (I) и (II) называются условиями дополняющей нежесткости в общей задаче нелинейного программирования.

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

1) Рассмотрим функцию Лагранжа при x = x*, λ = λ*:



По условию Куна-Таккера 5 второе слагаемое в правой части равенства нулевое, поэтому



Вывод. Значение функции Лагранжа в точке (x*, λ*) равно минимальному значению целевой функции в общей задаче нелинейного программирования.

2) Из условия Куна-Таккера 1 следует, что при фиксированном λ = λ* существует некоторая окрестность точки х*, что если из нее переместиться в любую допустимую точку этой окрестности, то значение функции Лагранжа может только возрасти. Аналогично из условия Куна-Таккера 4 следует, что при фиксированном х = х* существует некоторая окрестность точки λ = λ*, что если из нее переместиться в любую допустимую точку этой окрестности, то значение функции Лагранжа может только уменьшиться. Точка (x*, λ*), обладающая таким свойством, называется седловой точкой функции Лагранжа.

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



Задача нахождения точки (x*, λ*), удовлетворяющей этому двойному неравенству, называется задачей о седловой точке.

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

Теорема. Чтобы точка х* была оптимальной точкой в общей задаче нелинейного программирования, необходимо, чтобы существовала точка такая, что пара (x*, λ*) является седловой точкой функции Лагранжа.

Замечание. Условия Куна-Таккера в общем случае дают только необходимые условия оптимальности в задаче нелинейного программирования. Однако при выполнении некоторых дополнительных условий они оказываются достаточными. В частности, такая ситуация имеет место в задаче выпуклого программирования, когда функции являются выпуклыми, и кроме того, выполняется условие регулярности Слейтера, которое означает, что существует допустимая точка х, удовлетворяющая строгим неравенствам Задачу выпуклого программирования мы рассмотрим несколько позже.

Похожие:

Общая задача нелинейного программирования. Условия Куна-Таккера iconПонятие программы и программирования. Свойства программ. Назначение...
Системы счисления. Сущность перевода чисел из одной системы счисления в другую: примеры
Общая задача нелинейного программирования. Условия Куна-Таккера iconВари­ант
В приведенной далее таблице 4 для каждого варианта указаны значения параметров целевой функции задачи нелинейного программирования...
Общая задача нелинейного программирования. Условия Куна-Таккера iconЗадачами целочисленного
В противном случае, когда хотя бы одна зависимость будет нелинейной, это будет целочисленной задачей нелинейного программирования....
Общая задача нелинейного программирования. Условия Куна-Таккера iconМожет ли быть решена транспортная задача как обычная задача линейного программирования?
Назначение транспортной задачи – определить объём перевозок из пунктов отправления в пункты назначения с минимальной суммарной стоимостью...
Общая задача нелинейного программирования. Условия Куна-Таккера icon6. задача о рюкзаке
Циклический алгоритм целочисленного программирования
Общая задача нелинейного программирования. Условия Куна-Таккера icon05. базисные условия поставки товаров 4/2 ч
Общая характеристика базисных условий контрактов купли-продажи. Базисные условия поставки товаров (бупт) 2
Общая задача нелинейного программирования. Условия Куна-Таккера iconЛабораторная работа №1 Среда программирования Visual C++. Программирование линейных алгоритмов 6
Б 92 Основы алгоритмизации и программирования в среде Visual C++ : лаб практикум по курсу «Основы алгоритмизации и программирования»...
Общая задача нелинейного программирования. Условия Куна-Таккера iconВопросы к экзамену по курсу "Технологии программирования" для потока ас-09
Обзор основных моделей программирования. Императивное (процедурное) программирование (пример программы на Pure c или Pascal)
Общая задача нелинейного программирования. Условия Куна-Таккера iconТема 1: Эволюция языков программирования
Процедурное программирование, Объектно-ориентированное программирование (ооп), Декларативные языки программирования
Общая задача нелинейного программирования. Условия Куна-Таккера iconЛабораторная работа 1
Б 35 Основы программирования на языке Object Pascal в среде delphi: Лаб практикум по курсам «Программирование» и «Основы алгоритмизации...
Вы можете разместить ссылку на наш сайт:
Школьные материалы


При копировании материала укажите ссылку © 2020
контакты
userdocs.ru
Главная страница