Постановка задачи нелинейного программирования. Теорема Куна-Таккера (с) Н.М. Светлов, 2007 Лекция 7. Постановка задачи нелинейного программирования. Теорема.

Презентация:



Advertisements
Похожие презентации
Постановка задачи нелинейного программирования. Теорема Куна-Таккера Содержание лекции: Формулировка общей задачи математического программирования Формулировка.
Advertisements

Лекция 4. Теория двойственности Содержание лекции: 1. Двойственная задача линейного программирования Двойственная задача линейного программирования Двойственная.
Метод искусственного базиса. Сущность метода Если в системе ограничений, приведенной к каноническому виду, не удается сразу выделить базисные переменные,
1) Экономическая интерпретация ЗЛП: задача об оптимальном использовании ограниченных ресурсов, двойственная задача и ее экономическое содержание 2) Экономический.
Лекция 3. Математические методы в логистике Содержание лекции: 1. Формулировка общей задачи управления запасами Формулировка общей задачи управления запасами.
Часть 2 Двойственные задачи Правила построения двойственных задач.
Экономические приложения выпуклого программирования: числовые модели Содержание лекции: Градиентные методы решения задач выпуклого программирования Градиентные.
Лекция 5. Транспортные задачи и задачи о назначениях Содержание лекции: 1. Формулировка транспортной задачи Формулировка транспортной задачи Формулировка.
Двойственные задачи. Каждой задаче линейного программирования соответствует задача, называемая двойственной или сопряженной по отношению к исходной задаче.
Сфера и границы применения ЭММ (с) Н.М. Светлов, / 13 Лекция 1. Сфера и границы применения экономико- математического моделирования Содержание лекции:
1 Стандартная задача Матричная форма записи § 1.4. Специальные виды задач ЛП максимизацииминимизации Обозначения.
Симплекс-метод Симплексный метод – это вычислительная процедура, основанная на принципе последовательного улучшения решений при переходе от одной базисной.
Графический метод решения задач математического программирования 1. Общий вид задачи математического программирования Z = F(X) >min Z = F(X) >min g i (x.
Симплекс-метод. Сущность метода Первый шаг. Найти допустимое решение (план), соответствующее одной из вершин области допустимых решений. Второй.
Аналитический метод решения задач математического программирования.
LOGO Примеры задач линейного программирования. Для изготовления двух видов продукции Р1 и Р2 используют четыре вида ресурсов: S1, S2, S3 и S4. Задача.
Нелинейное программирование Практическое занятие 2.
Применение линейного программирования в математических моделях (с) Н.М. Светлов, / 23 Лекция 3. Применение линейного программирования в математических.
Кафедра математики и моделирования Старший преподаватель Е.Г. Гусев Курс «Высшая математика» Лекция 17. Тема: Графический метод и симплекс-метод задачи.
Двойственность линейного программирования. Правила построения двойственных задач: 1. Если в исходной задаче целевая функция исследуется на min, то в двойственной.
Транксрипт:

Постановка задачи нелинейного программирования. Теорема Куна-Таккера (с) Н.М. Светлов, 2007 Лекция 7. Постановка задачи нелинейного программирования. Теорема Куна-Таккера Содержание лекции: Формулировка общей задачи математического программирования Формулировка общей задачи математического программирования Формулировка общей задачи математического программирования Формулировка общей задачи математического программирования Классификация задач нелинейного программирования Классификация задач нелинейного программирования Классификация задач нелинейного программирования Классификация задач нелинейного программирования Понятие о функции Лагранжа Понятие о функции Лагранжа Понятие о функции Лагранжа Понятие о функции Лагранжа Теорема Куна-Таккера. Интерпретация множителей Лагранжа Теорема Куна-Таккера. Интерпретация множителей Лагранжа Теорема Куна-Таккера. Интерпретация множителей Лагранжа Теорема Куна-Таккера. Интерпретация множителей Лагранжа

Постановка задачи нелинейного программирования. Теорема Куна-Таккера (с) Н.М. Светлов, /11 Литература Шелобаев С.И. Экономико-математические методы и модели: Учеб. пособие для вузов. 2-е изд. М.: ЮНИТИ-ДАНА, Разделы 4.1 (до начала подраздела «Аналитические методы решения задач условной оптимизации»), 4.2. Шелобаев С.И. Экономико-математические методы и модели: Учеб. пособие для вузов. 2-е изд. М.: ЮНИТИ-ДАНА, Разделы 4.1 (до начала подраздела «Аналитические методы решения задач условной оптимизации»), 4.2. Исследование операций в экономике: Учебн. пособие для вузов / Под ред. Н.Ш. Кремера. М.: Банки и биржи, ЮНИТИ, Разделы 10.2, Исследование операций в экономике: Учебн. пособие для вузов / Под ред. Н.Ш. Кремера. М.: Банки и биржи, ЮНИТИ, Разделы 10.2, 11.2.

Формулировка общей задачи математического программирования 7.1 Постановка задачи нелинейного программирования. Теорема Куна-Таккера (с) Н.М. Светлов, 2007 (часто формулируют без условий неотрицательности) (часто формулируют без условий неотрицательности) 3/11

7.1 Вышеприведённым формулировкам отвечают: задача линейного программиро- вания z(x) и все qi (x), i =1…m – линейные функции задача нелинейного программиро- вания среди z(x) и qi (x), i =1…m есть хотя бы одна нелинейная функция Постановка задачи нелинейного программирования. Теорема Куна-Таккера (с) Н.М. Светлов, /11

7.2 Постановка задачи нелинейного программирования. Теорема Куна-Таккера (с) Н.М. Светлов, 2007 Повторение 5/11

Классификация задач нелинейного программирования Задачи нелинейного программирования Экстремальные задачи без ограничений Задачи выпуклого программирования Задачи дробно- линейного программирования Задачи квадратичного программирования Прочие Задачи невыпуклого программирования 7.2 Постановка задачи нелинейного программирования. Теорема Куна-Таккера (с) Н.М. Светлов, /11

Понятие о функции Лагранжа Решение любой задачи математического программирования (в том числе нелинейного) можно свести к решению задачи нелинейного программирования без ограничений. Для этого необходимо на основе исходной ЗМП построить функцию Лагранжа: 7.3 Постановка задачи нелинейного программирования. Теорема Куна-Таккера (с) Н.М. Светлов, 2007 В отсутствие условий неотрицательности: 7/11

Теорема Куна- Таккера7.4 Постановка задачи нелинейного программирования. Теорема Куна-Таккера (с) Н.М. Светлов, 2007 её единственный оптимум x1*,x2*,…,x n * (если имеется) соответствует единственной седловой точке функции Лагранжаеё единственный оптимум x1*,x2*,…,x n * (если имеется) соответствует единственной седловой точке функции Лагранжа Если исходная задача строго выпукла и все ограничения – равенства любой из существующих оптимумов соответствует седловой точке функции Лагранжалюбой из существующих оптимумов соответствует седловой точке функции Лагранжа Если исходная задача выпукла и все ограничения – равенства любой из существующих оптимумов соответствует точке Куна-Таккера функции Лагранжалюбой из существующих оптимумов соответствует точке Куна-Таккера функции Лагранжа любая седловая точка обязательно является точкой К.Т.; обратное не всегда вернолюбая седловая точка обязательно является точкой К.Т.; обратное не всегда верно точка К.Т. не обязательно соответствуют оптимумам исходной задачиточка К.Т. не обязательно соответствуют оптимумам исходной задачи В остальных случаях см. следующий слайд 7.4 8/11 Это утверждение называется теоремой Куна-Таккера Если задача строго выпукла, точек Куна-Таккера не более одной. Если т. К.-Т. имеется, то в ней находится оптимум.

7.4 Точка Куна-Таккера (x 1 *,x 2 *,…,x n *,λ 1 *, λ 2 *, …, λ т+n *) определяется следующими условиями Точка Куна-Таккера (x 1 *,x 2 *,…,x n *,λ 1 *, λ 2 *, …, λ т+n *) определяется следующими условиями Постановка задачи нелинейного программирования. Теорема Куна-Таккера (с) Н.М. Светлов, /11

7.4 Переменные λ i называются множителями Лагранжа. Экономическая интерпретация множителей Лагранжа, соответствующих оптимальному решению, аналогична интерпретации двойственных оценок ограничений ЗЛП Они показывают величину изменения целевой функции в расчёте на единицу изменения свободного члена ограничения, которому соответствует множитель Лагранжа, в очень малой окрестности оптимума Они показывают величину изменения целевой функции в расчёте на единицу изменения свободного члена ограничения, которому соответствует множитель Лагранжа, в очень малой окрестности оптимума Если ограничение можно рассматривать в качестве баланса ресурса и максимизируется прибыль, то множитель Лагранжа в точке оптимума равен оптимальной цене Если ограничение можно рассматривать в качестве баланса ресурса и максимизируется прибыль, то множитель Лагранжа в точке оптимума равен оптимальной цене Если найдётся рынок, где ресурс дешевле, то его покупка увеличит прибыльЕсли найдётся рынок, где ресурс дешевле, то его покупка увеличит прибыль Если найдётся рынок, где ресурс дороже, то для увеличения прибыли его следует продатьЕсли найдётся рынок, где ресурс дороже, то для увеличения прибыли его следует продать В отличие от случая ЗЛП, множители Лагранжа (кроме частных случаев) не обладают свойством устойчивости В отличие от случая ЗЛП, множители Лагранжа (кроме частных случаев) не обладают свойством устойчивости Они меняют свои значения даже при сколь угодно малом изменении свободных членов ограничений Они меняют свои значения даже при сколь угодно малом изменении свободных членов ограничений Постановка задачи нелинейного программирования. Теорема Куна-Таккера (с) Н.М. Светлов, /11

7.4 Теорема Куна-Таккера используется для аналитического отыскания оптимума задачи нелинейного программирования Впрочем, этот приём приводит к успешным результатам отнюдь не для любой задачи Главное, чем полезна теорема Куна- Таккера: выяснение роли множителей Лагранжа в формулировании условий оптимальности выяснение роли множителей Лагранжа в формулировании условий оптимальности экономическая интерпретация множителей Лагранжа экономическая интерпретация множителей Лагранжа Постановка задачи нелинейного программирования. Теорема Куна-Таккера (с) Н.М. Светлов, /11