Мегаобучалка Главная | О нас | Обратная связь


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



2015-11-11 1425 Обсуждений (0)
Задача выпуклого программирования 0.00 из 5.00 0 оценок




Если в задаче математического программирования требуется найти экстремум функции, например:

(4.7)

на множестве допустимых решений, заданных ограничениями

, (4.8)

причем:

1) целевая функция является дифференцируемой и вогнутой, т.е. для нее выполняется условие:

при любых ,

2) а левые части всех ограничений — дифференцируемыми и выпуклыми функциями, т.е. для них выполняются условия:

при любых ,

Тогда задача (4.7)-(4.8) называется задачей выпуклого программирования.

Любая линейная функция одновременно удовлетворяет условиям и выпуклости, и вогнутости; т.е. её можно считать как выпуклой, так и вогнутой. Это позволяет считать линейные задачи частным случаем задач выпуклого программирования.

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

Введём три определения:

1). Функцией Лагранжа задачи выпуклого программирования (4.7)-(4.8) называется функция:

,

, (4.9)

2). Говорят, что задача выпуклого программирования (4.7)-(4.8) удовлетворяет условию регулярности, если существует хотя бы одна внутренняя точка множества допустимых решений , определяемого строгими неравенствами, полученными из (4.8) (т.е. ).

3). Точка называется седловой точкой функции , если для всех выполнено:

(4.10)

Если целевая функция (убрать)

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

Теорема Куна-Таккера. Если задача выпуклого программирования (4.7)-(4.8) удовлетворяет условию регулярности, то точка является оптимальным решением этой задачи тогда и только тогда, когда существует такая точка с неотрицательными координатами, что является седловой точкой функции Лагранжа данной задачи.

Условия Каруша-Куна-Таккера в дифференциальной форме:

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

,

,

,

Пример.

Найти максимум функции

на множестве допустимых решений .

Решение:

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

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

Найдём седловую точку функции Лагранжа из условий:

.

В данном случае седловой точкой является пара , .

Ответ:

Теорема Куна-Таккера обосновывает сведение задачи выпуклого программирования к задаче поиска седловой точки функции Лагранжа. Чтобы такое сведение имело практический смысл, необходимо, чтобы получившаяся задача была в чём-то проще исходной. Это происходит не всегда, поэтому разработан ряд прямых методов поиска решения нелинейной задачи (4.5), (4.6). Рассмотрим некоторые из них.



2015-11-11 1425 Обсуждений (0)
Задача выпуклого программирования 0.00 из 5.00 0 оценок









Обсуждение в статье: Задача выпуклого программирования

Обсуждений еще не было, будьте первым... ↓↓↓

Отправить сообщение

Популярное:
Модели организации как закрытой, открытой, частично открытой системы: Закрытая система имеет жесткие фиксированные границы, ее действия относительно независимы...
Как вы ведете себя при стрессе?: Вы можете самостоятельно управлять стрессом! Каждый из нас имеет право и возможность уменьшить его воздействие на нас...
Личность ребенка как объект и субъект в образовательной технологии: В настоящее время в России идет становление новой системы образования, ориентированного на вхождение...



©2015-2020 megaobuchalka.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. (1425)

Почему 1285321 студент выбрали МегаОбучалку...

Система поиска информации

Мобильная версия сайта

Удобная навигация

Нет шокирующей рекламы



(0.008 сек.)