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

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

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

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

(1)

 

где

(2)

 

-не пустое, ограниченное замкнутое множество.

Нам понадобятся далее понятия множителей Лагранжа и функции Лагранжа. Функция Лагранжа для задачи (1) с ограничениями (2) определяется формулой

(3)

 

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

Нам понадобится также понятие условия регулярности ограничивающих функций. Если точка , то условие линейной независимости векторов называется условием регулярности задачи (1), (2) в точке . Данное условие означает, в частности, что количествоограничивающих функций

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

Рис. 1. Ситуации, в которых в двумерном случае ( n =2) не выполняется условие регулярности системы функций h (X) в точке X*.

Исключительно важное место в теории и практике решения задач нелинейного программирования с ограничениями типа равенств занимает следующая теорема (правило Лагранжа для задачи оптимизации с ограничениями типа равенств).

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

(4)

 

Доказательство теоремы приведем для одного частного случая. Пусть =3, т.е. минимизируемая функция , и пусть заданы два ограничения типа равенств

(5)

 

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

 

(6)

 

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

 

(7)

 

Поскольку функция () имеет точку минимума , производная по функции в точке равна нулю:

(8)

 

Дифференцируя по выражения (5), получим

(9)

 

Запишем уравнения (8), (9) в виде матричного уравнения

(10)

 

Поскольку вектор не нулевой, то равенство (10) возможно лишь в том случае, когда . Но это возможно лишь в том случае, когда вектора-строки матрицы линейно зависимы. Значит, существуют такие скаляры , не все равные нулю, что

(11)

 

В выражении (11) скаляр a не может быть равен нулю, поскольку противное означало бы линейную зависимость векторов , что противоречит условию теоремы. Поэтому после деления на из (11) получим

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

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


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |

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



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