АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

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

Читайте также:
  1. I. 1.2. Общая постановка задачи линейного программирования
  2. I. 3.1. Двойственная задача линейного программирования
  3. I.5.3. Подготовка данных для задачи линейного программирования
  4. I.5.4. Решение задачи линейного программирования
  5. II.2. Задача о назначениях
  6. II.4. МЕТОД ВЕТВЕЙ И ГРАНИЦ В ЗАДАЧАХ ЦЕЛОЧИСЛЕННОГО ПРОГРАММИРОВАНИЯ
  7. K-7.Точкапрорыва
  8. VI. Общая задача чистого разума
  9. ZANKTXSP (ЗП.Сотрудник Налоговая карточка(спецификация))
  10. Анализ безубыточности деятельности. Денежная точка равновесия, вклад на покрытие, запас финансовой прочности, операционный рычаг.
  11. Анализ чувствительности задач линейного программирования
  12. Архитектура программирования SSAS.

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

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

Данное выражение называют неравенством для седловой точки. Очевидно, что в седловой точке выполняется условие

Между понятием седловой точки функции Лагранжа и решением задачи НП существует взаимосвязь, которая устанавливается в следующей теореме.

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

и

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

Определим функцию Лагранжа следующим образом:

Тогда теорему Куна-Таккера можно записать в виде

Заметим, что множители Лагранжа в задаче НП с ограничениями-равенствами являются знаконеопределенными, тогда как в теореме Куна-Таккера они должны быть положительными.

Каждой задаче линейного программирования соответствует двойственная задача. Двойственная задача по отношению к исходной задаче строится по следующим правилам:

· Если исходная задача ставится на максимум, то двойственная ставится на минимум и наоборот.

· Коэффициенты целевой функции исходной задачи становятся правыми частями ограничений двойственной задачи. Правые части ограничений исходной задачи становятся коэффициентами целевой функции двойственной задачи.

· Если A-матрица коэффициентов исходной задачи, то транспонированная матрица T A будет матрицей коэффициентов двойственной задачи.

· В задаче на максимум все ограничения имеют знак ≤ (=), а в задаче на минимум все ограничения имеют знак ≥.

· Число переменных в двойственной задаче равно числу ограничений в исходной задаче. Каждому ограничению исходной задачи соответствует переменная двойственной задачи. Если ограничение исходной задач имеет знак (≥), то соответствующая переменная двойственной задачи неотрицательна. Если ограничение имеет знак (=), то соответствующая переменная двойственной задачи может принимать положительные и отрицательные значения и наоборот.


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |

Поиск по сайту:

Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.088 сек.)