Главная › Настройки › Условия куна таккера в геометрической форме. Понятие седловой точки. Теорема Куна-Таккера

Условия куна таккера в геометрической форме. Понятие седловой точки. Теорема Куна-Таккера

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

Теорема 1. Необходимость условий Куна-Таккера

Рассмотрим задачу нелинейного программирования (0) - (2). Пусть - дифференцируемые функции, а х* - допустимое решение данной задачи. Положим. Далее пусть линейно независимы. Если х* - оптимальное решение задачи нелинейного программирования, то существует такая пара векторов, что является решением задачи Куна-Таккера (3) - (7).

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

1. Все ограничения в виде равенств и неравенств содержат линейные функции.
2. Все ограничения в виде неравенств содержат вогнутые функции, все ограничения-равенства - линейные функции, а также существует, по крайней мере, одна допустимая точка х, которая расположена во внутренней части области, определяемой ограничениями-неравенствами. Другими словами, существует такая точка х, что

Если условие линейной независимости в точке оптимума не выполняется, то задача Куна-Таккера может не иметь решения.

Минимизировать

при ограничениях

На рис. 1 изображена область допустимых решений сформулированной выше нелинейной задачи. Ясно, что оптимальное решение этой задачи есть. Покажем, что условие линейной независимости не выполняется в точке оптимума.

Рис.

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

Запишем условия Куна-Таккера и проверим, выполняются ли они в точке (1, 0). Условия (3), (6) и (7) принимают следующий вид;

При из уравнения (11) следует, что, тогда как уравнение (14) дает, Следовательно, точка оптимума не является точкой Куна - Таккера.

Заметим, что нарушение условия линейной независимости не обязательно означает, что точка Куна-Таккера не существует. Для того чтобы подтвердить это, заменим целевую функцию из этого примера функцией. При этом оптимум по-прежнему достигается в точке (1,0), в которой условие линейной независимости не выполняется. Условия Куна-Таккера (12) - (16) остаются неизменными, а уравнение (11) принимает вид

Нетрудно проверить, что точка является точкой Куна-Таккера, т.е. удовлетворяет условиям Куна-Таккера.

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

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

Теорема 2. Достаточность условий Куна-Таккера

Рассмотрим задачу нелинейного программирования (0) - (2). Пусть целевая функция выпуклая, все ограничения в виде неравенств содержат вогнутые функции, а ограничения в виде равенств содержат линейные функции. Тогда если существует решение, удовлетворяющее условиям Куна-Таккера (3) - (7), то х* - оптимальное решение задачи нелинейного программирования.

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

Теорему 2 можно также использовать для доказательства оптимальности данного решения задачи нелинейного программирования. В качестве иллюстрации опять рассмотрим пример:

Минимизировать

при ограничениях

С помощью теоремы 2 докажем, что решение является оптимальным. Имеем

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

чтобы показать, что функция является вогнутой, вычислим

Поскольку матрица отрицательно определена, функция является вогнутой. Функция входит в линейное ограничение в вяде равенства. Следовательно, все условия теоремы 2 выполнены; если мы покажем, что - точка Куна-Таккера, то действительно установим оптимальность решения. Условия Куна-Таккера для примера 2 имеют вид

Точка удовлетворяет ограничениям (24) - (26) и, следовательно, является допустимой. Уравнения (22) и (23) принимают следующий вид:

Положив, получим и. Таким образом, решение х*=(1, 5), удовлетворяет условиям Куна-Таккера. Поскольку условия теоремы 2 выполнены, то оптимальное решение задачи из примера 3. Заметим, что существуют также и другие значения и, которые удовлетворяют системе (22) - (29).

Замечания

1. Для встречающихся на практике задач условие линейной независимости, как правило, выполняется. Если в задаче все функции дифференцируемы, то точку Куна-Таккера следует рассматривать как возможную точку оптимума. Таким образом, многие из методов нелинейного программирования сходятся к точке Куна-Таккера. (Здесь уместно провести аналогию со случаем безусловной оптимизации, когда соответствующие алгоритмы позволяют определить стационарную точку.)
2. Если условия теоремы 2 выполнены, точка Куна-Таккера в то же время оказывается точкой глобального минимума. К сожалению, проверка достаточных условий весьма затруднительна, и, кроме того, прикладные задачи часто не обладают требуемыми свойствами. Следует отметить, что наличие хотя бы одного нелинейного ограничения в виде равенства приводит к нарушению предположений теоремы 2.
3. Достаточные условия, установленные теоремой 2, можно обобщить на случай задач с невыпуклыми функциями, входящими в ограничения в виде неравенств, невыпуклыми целевыми функциями и нелинейными ограничениями-равенствами. При этом используются такие обобщения выпуклых функций, как квазивыпуклые и псевдовыпуклые функции.

Теорема Куна-Таккера является обобщением методов решения оптимизационных задач в двух направлениях:

Линейного программирования на нелинейный случай, который получил по аналогии не очень удачное название «нелинейного программирования»;

Нелинейных ограничений равенств на ограничения неравенства.

Метод и условия Каруша-Куна-Таккера (Karush-Kuhn- Tucker conditions , KKT) формально являются необходимыми условиями оптимальности задачи нелинейного программирования. Кроме того, необходимые условия включают, так называемые условия регулярности стационарных точек – невырожденность множества градиентов ограничений. Метод является обобщением метода множителей Лагранжа на случай ограничений неравенств.

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

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

Вильям Каруш в своей дипломной работе в 1931 году нашёл необходимые условия в общем случае ограничений равенств и неравенств. Независимо от него к тем же выводам позднее в 1941 году пришли Гарольд Кун и Альберт Таккер. Полученные ими результаты были более общими.

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

- стационарности : ;

- дополняющей нежёсткости : ;

- неотрицательности :.

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

- простое условие – 1) точка стационарна, 2)выполняется условие дополняющей нежесткости, 3) множители Лагранжа ;

- условие Слейтера (более слабое) – 1) точка стационарна, 2) выполняется условие дополняющей нежесткости, 3) .

Перейдём непосредственно к доказательству теоремы Куна-Таккера.

Если непрерывная функция n переменных x = (x1,...,xn) F(х) имеет в точкех опт максимум, то существует ε > 0 такое, что для всех x из ε-окрестности точких опт

F(x)≤F(x опт)

F(x)-F(x опт)≤0.

Выберем два вида приращения x j вдоль j -й координаты

Δx j =x j -x jопт >0,

Δx j =x j -x jопт <0.

Переходя в этих соотношениях к пределу при Δx j →0, получаем:

Из этих соотношений следует, что

(3.6.1)

Аналогичное соотношение можно получить для случая минимума функции. Таким образом, доказана необходимость условий (3.6.1) для достижения в точке х опт максимума или минимума функции f(х) , т. е. если имеется экстремум, то условия (3.6.1) удовлетворяются. Но равенство нулю всех производных в точке х опт еще не обеспечивает существования в ней экстремума, т. е. условия (3.6.1) не являются достаточными. Геометрически это означает, что в случае нулевой производной от функции одной переменной может иметь место точка перегиба, а не максимум (или минимум), а в случае функции двух переменных - седловая точка, а не экстремум и т. д. Поэтому точки х опт , в которых выполняются соотношения (3.6.1), называются стационарными.

Заметим, что условие (3.6.1) удалось получить благодаря возможности придавать переменной х приращения двух знаков, откуда и возникли два неравенства при и при . Если допустимая область значений х ограничена неотрицательными значениями х ≥0, то внутри области, где х > 0, справедливость условия (3.6.1) сохраняется, так как там допустимы приращения обоих знаков. На границе области х ≥ 0, где х = 0, допускается только положительное приращение Δх >0, можно говорить только об односторонней производной, и из (3.6.1) следует следующее необходимое условие максимума:

Соответственно, необходимое условие минимума на границе области х j = 0 запишется в виде

б) Задача на условный экстремум

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

g i (x) = b i , i = 1, ..., m,

f(x)=max;

g i (x)=b i ;

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

(3.6.2)

где λ i - неопределенные множители Лагранжа.

Полагая, что функция является частным случаем функционала, получаем, что необходимые условия экстремума находятся прямым дифференцированием соотношения (3.6.2) и записываются в виде

Если ввести в рассмотрение векторы

соотношения (17-8) и (17-9) перепишутся как

grad Φ = grad F - λ grad φ = 0; (3.6.6)

где равенство нулю векторов понимается покомпонентно.

Рисунок 3.6.1 - Пояснение к задаче на условный экстремум

В случае n = 2 и m = 1 геометрическая задача об отыскании условного экстремума сводится (рис. 17-6) к отысканию точки касания А кривой φ = b к одной из кривых постоянного уровня f = const.

Постановка задачи

Рассмотрим задачу нелинейной оптимизации. Пусть есть функции

При условиях .

Вильям Каруш в своей дипломной работе нашёл необходимые условия в общем случае, когда накладываемые условия могут содержать и уравнения, и неравенства. Независимо от него к тем же выводам пришли Гарольд Кун и Альберт Таккер.

Необходимые условия минимума функции

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

Достаточные условия минимума функции

Простая формулировка

Если для допустимой точки выполняются условия стационарности, дополняющей нежёсткости и неотрицательности, а также λ 1 > 0 , то .

Более слабые условия

Если для допустимой точки выполняются условия стационарности, дополняющей нежёсткости и неотрицательности, а также (условие Слейтера ), то .

Wikimedia Foundation . 2010 .

Смотреть что такое "Условия Каруша - Куна - Таккера" в других словарях:

В теории оптимизации условия Каруша Куна Таккера (англ. Karush Kuhn Tucker conditions, KKT) необходимые условия решения задачи нелинейного программирования. Чтобы решение было оптимальным, должны быть выполнены некоторые… … Википедия

Вильям Каруш William Karush Дата рождения: 1 марта 1917(1917 03 01) Место рождения: Чикаго, США Дата смерти … Википедия

У этого термина существуют и другие значения, см. Оптимизация. Оптимизация в математике, информатике и исследовании операций задача нахождения экстремума (минимума или максимума) целевой функции в некоторой области конечномерного векторного … Википедия Википедия

Метод множителей Лагранжа, метод нахождения условного экстремума функции f(x), где, относительно m ограничений, i меняется от единицы до m. Содержание 1 Описание метода … Википедия

Теорема 7.2. Для задачи выпуклого программирования (7.4)–(7.6), множество допустимых решений которой обладает свойством регулярности, план является оптимальным планом тогда и только тогда, когда существует такой вектор , что
– седловая точка функции Лагранжа.

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

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

Теорема Куна-Таккера в теории нелинейного программирования занимает центральное место. Она справедлива и для задач так называемого квадратичного программирования, т.е. где целевая функция
при ограничениях:

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

Пример 7.3. С помощью теоремы Куна-Таккера найдём
при ограничениях

Решаем графически (рис. 7.2) и находим:
;
;
(более подробно решение см. ниже). Покажем, что существует векторY 0 0, при котором в точке оптимума выполняются условия Куна-Таккера. Составим функцию Лагранжа:

Решение
находим из системы:
. Из второго уравнения
подставляем в первое уравнение системы. Дифференцируем по:
. В выраженияиподставляем значения
и
. Имеем значения частных производных больше нуля, а по условию должны быть равно нулю, тогда =0 и =0. С другой стороны,может принимать ненулевые значения, т.к.
отсюда
; все
т.е. условия Куна-Таккера выполняются, следовательно, эта точка – точка экстремума.

Рис.7.2. Графическое решение задачи нелинейного

программирования примера 7.3

Необходимое условие оптимальности для задачи нелинейного программирования можно сформулировать следующим образом. Пусть
– оптимальное решение задачи (7.4)–(7.6), причём функции
,
,
дифференцируемы в этой точке. Если
– неособая точка допустимого множества задачи (7.4)–(7.6), то она является точкой Куна-Таккера этой задачи.

Таким образом, если допустимое множество
задачи (7.4)-(7.6) не имеет особых точек, а функцииF (М), g i (М), (
) дифференцируемы во всех точках
, то оптимальное решение этой задачи следует искать среди точек Куна-Таккера.

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

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

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

Действительно,

Таким образом, – линейно зависимая система.

Градиент функции
– это вектор, координаты которого соответственно равны значениям частных производных функции
в точкеM 0 . Этот вектор показывает направление быстрейшего роста функции.

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

Достаточное условие оптимальности для задачи нелинейного программирования: если
– седловая точка функции Лагранжа для задачи (7.4)–(7.6), то
является оптимальнымрешением этой задачи.

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

Известны различные методы, позволяющие найти оптимальное решение задачи нелинейного программирования приближённо. Однако эти методы дают достаточно хорошее приближение лишь для задачи выпуклого программирования, где всякий локальный экстремум является одновременно и глобальным. В общем случае под градиентными методами понимают методы, в которых движение к точке оптимума функции совпадает с направлением градиента этой функции, т.е. начиная с некоторой точки
осуществляется последовательный переход к некоторым другим точкам до тех пор, пока не выявится приемлемое решение исходной задачи. При этом градиентные методы могут быть подразделены на 2 группы.

К первой группе относятся методы, при использовании которых исследуемые точки не выходят за пределы области допустимых решений задачи. Наиболее распространенным из таких методов является метод Франка-Вольфа (Вулфа) . К числу таких методов относится метод проектируемых градиентов Розена, метод допустимых направлений Зойтендейка .

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

Из таких методов наиболее часто используется метод штрафных функций или метод Эрроу-Гурвица .

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

Решение сложных задач нелинейного программирования градиентными методами связано с большим объёмом вычислений и целесообразно только с использованием ЭВМ.

На примере покажем общий смысл градиентных методов решения задач нелинейного программирования.

Пусть имеется функция двух переменных
. Пусть исходные значения переменных будут
, а значение функции
. Если
не является экстремумом, то определяют такие новые значения переменных
и
, чтобы следующее значение функции
оказалось ближе к оптимуму, чем предыдущее.

Каким же образом определяется величина приращений и ? Для этого в точках иопределяется направление изменения функции в сторону экстремума с помощью градиента. Чем больше значение частной производной, тем быстрее происходит изменение функции в сторону экстремума. Поэтому приращенияивыбирают пропорциональными значению частных производныхив точках
и
. Таким образом,
и
, где – величина, называемая шагом, котораяустанавливает масштаб изменений и.

Пример 7.4.

Пусть необходимо максимизировать функцию

(максимум в точке (3;2))

В точке
,
при
имеем

;
,

Проведём ещё одну итерацию. В точке
,
при
имеем

;
,

Рис.7.3. Геометрическая интерпретация двух шагов

градиентного метода для примера 7.4

На рис. 7.3 показано движение по градиенту, которое было проведено в данном примере. Отношение указывает направление изменения функции в сторону максимума. Если градиент взять со знаком минус, то будем двигаться в сторону минимума.

Специфической проблемой градиентных методов является выбор величины шага t . Если задаться малым шагом, то оптимум будем искать очень долго. Если выбрать его значение слишком большим, то оптимум можно "проскочить". Соответствующими методами решается промежуточная задача выбора оптимальной величины шага. Если шаг t определяется приближённо, то, как правило, попадают не в оптимум, а в его зону. Градиентные методы обеспечивают определение локальных оптимумов. При отыскании глобального оптимума с помощью градиента нередко бывает сомнение в том, что найденный оптимум является глобальным. В этом недостаток этого метода при решении задач невыпуклого программирования.

Вопросы для самопроверки

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

Процесс нахождения решения задачи нелинейного программирования с использованием её геометрической интерпретации.

Алгоритм метода Лагранжа решения задачи нелинейного программирования.

Применение метода Лагранжа к решению задачи нелинейного программирования в случае, когда условия связи представляют собой неравенства.

Вспомогательные определения и теоремы, необходимые для рассмотрения центральной теоремы нелинейного программирования – теоремы Куна-Таккера.

Теорема Куна-Таккера.

Необходимое и достаточное условие оптимальности для задачи нелинейного программирования.

Общий смысл градиентных методов приближённого решения задач нелинейного программирования.

Группы градиентных методов приближённого решения задач нелинейного программирования.

Центральное место в теории нелинейного программирования занимает теорема Куна-Таккера. Пусть дана задача нелинейного программирования:

найти максимальное значение функции Z =f (х 1 , х 2 , ..., х n ) при ограничениях

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

(4.2)

Если выполняется условие регулярности (существует по крайней мере одна точкаX, для которой g i (X )>0 для всех i ), то имеет место следующая теорема.

Теорема. Вектор X (0) тогда и только тогда является оптимальным решением задачи (4.1), когда существует такой вектор Λ (0) , что при для всех

Точка (X (0) ,Λ (0)) называется седловой точкой для функции F (X ,Λ), а теорема называется теоремой о седловой точке. Докажем достаточность условий (4.3).

Доказательство. Пусть X (0) >0 и Λ (0) >0 - седловая точка функции F (X ,Λ). Если в (4.3) вместо F (X ,Λ) подставить ее значение (4.2), то получим

при .

Правое неравенство справедливо при любом , поэтому

Тогда из левого неравенства получим

Так как при этом

то f (X (0) )>f (X ).

Таким образом, точка X (0) удовлетворяет (4.1) и во всех других точках, удовлетворяющих (4.1), функция принимает значение меньшее, чем в X (0) .

Это утверждение приводит решение задачи НЛП к отысканию седловых точек функции Лагранжа F (X ,Λ).

Доказательство необходимости условий (4.3) ввиду его сложности не рассматривается.

Если f (X ) и g i (X )-дифференцируемые функции, то условия (4.3) эквивалентны следующим локальным условиям Куна-Таккера:

Выражение

означает, что значение частной производной функции Лагранжа берется в точке (X (0) , Λ (0)), где

X (0) =(х 1 (0) , х 2 (0) , ..., х n (0)), Λ (0) =(λ 1 (0) , λ 2 (0) , ..., λ n (0)).

Эти условия можно записать в векторной форме:

Пример. Найти maxZ =-x 1 2 -x 2 2 при ограничениях

Покажем, что существует Λ (0) 0, при котором в точке оптимума выполняются условия Куна-Таккера (4.4), (4.5) для функции F (X ,Λ):

F (X ,Λ)=-x 1 2 -x 2 2 +λ 1 (2x 1 +x 2 -2)+λ 2 (8-2x 1 -x 2)+λ 3 (6-x 1 -x 2).

Согласно условиям (4.5) λ 2 и λ 3 должны принимать нулевые значения, так как, подставляя x 1 =0.8 и x 2 =0.4 в выражения

имеем значения, большие нуля, а по условию

Согласно условию λ 1 может принимать ненулевое значение, так как

В соответствии с (2.16) производная

должна принимать нулевые значения, так как координаты вектора X (0) отличны от нуля. Находим λ 1 =0,8. Следовательно, в точке (X (0) ,Λ (0)) выполняются условия Куна-Таккера и она действительно является точкой экстремума.

Рассмотрим условия Куна-Такера в несколько другом виде.

Пусть имеем задачу оптимизации с ограничениями в виде равенств:

z = f (x 1 , x 2 , …, xn ) → min

при условиях:

g 1 (x 1 , x 2 , ... , x n ) = 0,

g 2 (x 1 , x 2 , ... , x n ) = 0,

g n (x 1 , x 2 , . . . , x n ) = 0.

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

При этом седловая точка должна обеспечивать минимум по своим переменным x i и максимум по переменным λj .

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

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

Для получения достаточного условия существования минимума необходимо добавить требование положительной определенности гессиана целевой функции.

Рассмотрим общую задачу математического программирования:

Z = f (X) → min,

при условиях:

Ограничения в виде неравенств могут быть преобразованы в ограничения в виде равенств добавлением к каждому из них ослабляющих переменных

Сформируем функцию Лагранжа:

Тогда необходимые условия минимума принимают вид:

Второе уравнение можно преобразовать, отбросив ослабляющие переменные и переходя к ограничениям-неравенствам. Получим ограничения исходной задачи. Третье уравнение можно умножить на ui /2 и заменить ослабляющие переменные, выразив их из второго уравнения системы.

Есть еще одно условие, которое должно выполняться в точке минимума. Это условие: λ i = 0, которое является следствием анализа физического смысла коэффициентов функции Лагранжа.

Можно показать, что

Коэффициент Лагранжа в точке минимума;

f * - оптимальное значение функции.

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

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

Выражения во второй строке гарантируют, что оптимальная точка будет допустимой.

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

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

Приведенные условия эквивалентны теореме Куна-Такера и часто называются так же.

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

Конспективное представление материала этой главы можно посмотреть в двух презентациях:

файл «Нелинейное программирование»;

файл «Теорема Куна-Таккера».

На слайдах 10-14 презентации «Теорема Куна-Таккера» показан пример решения задачи Куна-Таккера.

4.5. Контрольные вопросы

(Разработаны Афанасьевым М.Ю. и Суворовым Б.П. )

Вопрос 1. Дана действительная функция f (х S = . Пусть х 1 и х 2 - точки этого отрезка и 0 £ l £ 1.

Какое из нижеприведенных неравенств является условием выпуклости функции?

Варианты ответов:

Вопрос 2. Дана действительная функция f (x ), определенная на отрезке действительных чисел S= . Пусть x 1 и x 2 - точки этого отрезка и 0 £ l £ 1.

Какое из нижеприведенных неравенств является условием строгой вогнутости функции?

Варианты ответов:

Вопрос 3. Функция

1) выпуклая;

2) строго выпуклая;

3) вогнутая;

4) строго вогнутая;

5) выпуклая и вогнутая.

Вопрос 4. Функция

3) вогнутая; 4) строго вогнутая;

5) выпуклая и вогнутая.

Вопрос 5. Функция

1) выпуклая; 2) ни выпуклая, ни вогнутая;

3) строго выпуклая; 4) вогнутая:

5) выпуклая и вогнутая.

Вопрос 6. Новая модель скоростного мотоцикла «Улитка» продается предприятием по цене (30 – 2x ) тыс. долл. за штуку, где х - количество проданных мотоциклов. Переменные производственные затраты составляют 6 тыс. долл. за штуку, фиксированные затраты - 30 тыс. долл. Максимизируйте прибыль предприятия за неделю.

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

Как изменится оптимальный выпуск мотоциклов по сравнению с начальной ситуацией?

(Решить, используя функцию Лагранжа.)

Варианты ответов:

1) увеличитсяна 2 ; 2) уменьшится на 2 ;

3) не изменится; 4) увеличится на 1 ;

5) уменьшится на 1 .

Вопрос 7. Предположим, что у вас есть 2 недели (14 дней) отпуска, которые вы можете провести на Канарских островах и в Ницце. Пусть ваша функция полезности имеет вид 2KN – 3К 2 – 4N 2 , где К и N - количество дней, которое вы проводите на Канарских островах и в Ницце соответственно.

Сколько дней вы должны провести в Ницце, чтобы максимизировать свою функцию полезности?

(Для решения использовать функцию Лагранжа. Результат округлить до ближайшего целого. Проверить, выполняются ли условия оптимальности Куна - Таккера.)

Варианты ответов:

1) 3 ; 2) 4 ; 3) 5 ; 4) 6 ; 5) 7 .

Вопрос 8. Для задачи вопроса 7 найдите значение двойственной оценки ограничения.

(Результат округлить до ближайшего целого.)

Варианты ответов:

1) 41 ; 2) 34; 3) 29 ; 4) 39 ; 5) 44 .

Вопрос 9. Монополист планирует программу производства и реализации продукции на следующий период. Цены: р 1 = 14 – 0,25x 1 (на продукт 1); р 2 = 14 – 0,5х 2 (на продукт 2), где x 1 и х 2 - объемы реализации продуктов. Предположим, что вся произведенная продукция реализуется. Максимальный суммарный объем сбыта - 57.

Каков оптимальный выпуск продукта 2?

Варианты ответов:

1) 36,4 ; 2) 30,7 ; 3) 26,3 ; 4) 20,6 ; 5) 41,8 .

Вопрос 10. Владелец небольшого предприятия располагает на ближайший месяц 100 тыс. руб., которые он может потратить на увеличение основных фондов К (закупку оборудования) по цене 1 тыс. руб за единицу либо на покупку дополнительной рабочей силы L по цене 50 руб./ч. Увеличение готовой продукции, которая может быть продана по 10 тыс. руб. за единицу, определяется производственной функцией F(K, L)= L 2/7 К 2/5 .

Сколько средств следует потратить на увеличение основных фондов?

Варианты ответов:

1) 74,36 тыс. руб.; 2) 58,33 тыс. руб.; 3) 63,44 тыс. руб.;

4) 45,66 тыс. руб.; 5) 39,77 тыс. руб.

Ответы на вопросы:

1 -4,2 - 1,3 -4,4 - 5,

5 -2, 6 -5,7- 4,8- 2,9- 4,10- 2.