Примери за теорема на Кун Тъкър. Достатъчни условия за минимум на функция

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

Ако приемем, че целта функция
и функции са непрекъснати и диференцируеми, тогава теоремата на Кун-Тъкър може да бъде допълнена с аналитични изрази, които определят необходимото и достатъчно условие за точката
беше седловата точка на функцията на Лагранж, т.е. беше решение на проблема с изпъкналото програмиране. Тези изрази имат следната форма:

Където И са стойностите на съответните частични производни на функцията на Лагранж, изчислени в седловата точка.

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

В общия случай на решаване на проблеми с нелинейно програмиране за определяне на глобалния екстремум на проблема, няма ефективен изчислителен метод, ако не е известно, че всеки локален екстремум е също и глобален. По този начин, в проблем с изпъкнало и квадратично програмиране, множеството от възможни решения е изпъкнало, тогава ако целевата функция е вдлъбната, всеки локален максимум е също глобален.

Пример 7.3.Използвайки теоремата на Кун-Тъкър намираме
под ограничения

Решаваме графично (фиг. 7.2) и намираме:
;
;
(вижте решението по-долу за повече подробности). Нека покажем, че има вектор Y 0 0, при което условията на Kuhn-Tucker са изпълнени в оптималната точка. Нека съставим функцията на Лагранж:

Решение
намираме от системата:
. От второто уравнение
заместваме в първото уравнение на системата. Разграничете по :
. В изрази И заменете стойностите
И
. Имаме стойности на частични производни по-големи от нула и според условието те трябва да са равни на нула, тогава =0 И =0. От друга страна, може да не приеме нулеви стойности, защото
оттук
; всичко
тези. условията на Kuhn-Tucker са изпълнени, следователно тази точка е точка на екстремум.

Фиг.7.2. Графично решение на нелинейната задача

пример за програмиране 7.3

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

По този начин, ако допустим набор
задача (7.4)-(7.6) няма особени точки и функциите Е(М),ж аз (М), (
) диференцируеми във всички точки
, тогава оптималното решение на този проблем трябва да се търси сред точките на Kuhn-Tucker.

Както е известно от математическия анализ, специална точкамножества от допустими решения на система от линейни уравнения и неравенства от вида

набор от възможни решения

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

Наистина ли,

Следователно това е линейно зависима система.

Градиентна функция
е вектор, чиито координати са съответно равни на стойностите на частните производни на функцията
в точката М 0 . Този вектор показва посоката на най-бързия растеж на функцията.

Необходимото условие за оптималност е малко полезно за решаването на повечето проблеми с нелинейното програмиране, тъй като Само в редки случаи е възможно да се намерят всички точки на Kuhn-Tucker на проблем с нелинейно програмиране.

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

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

Известни са различни методи, които позволяват приблизително да се намери оптималното решение на проблем с нелинейно програмиране. Въпреки това, тези методи осигуряват доста добро приближение само за проблема с изпъкнало програмиране, където всеки локален екстремум е също и глобален. Като цяло под градиентметодите разбират методи, при които движението към оптималната точка на функция съвпада с посоката на градиента на тази функция, т.е. започвайки от някаква точка
извършва се последователен преход към някои други точки, докато се идентифицира приемливо решение първоначален проблем. В този случай градиентните методи могат да бъдат разделени на 2 групи.

ДА СЕ първиТази група включва методи, при които изследваните точки не излизат извън обхвата на възможните решения на проблема. Най-често срещаният от тези методи е методът Франк-Волф (Вълк). Такива методи включват метода проектирани градиенти на Розен,метод валидни указания на Zeutendijk.

Co. второТази група включва методи, при които изследваните точки могат или не могат да принадлежат към областта на осъществимите решения. Въпреки това, в резултат на изпълнението на итеративния процес се намира точка в областта на възможните решения, която определя приемливо решение.

От тези методи най-често използваният метод е наказателни функцииили метод Arrow-Hurwitz.

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

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

Използвайки пример, ще покажем общото значение на градиентните методи за решаване на проблеми с нелинейно програмиране.

Нека има функция на две променливи
. Нека първоначалните стойности на променливите са
, и стойността на функцията
. Ако
не е екстремум, тогава се определят такива нови стойности на променливите
И
така че следващата стойност на функцията
се оказа по-близо до оптимума от предишния.

Как се определя размерът на инкрементите? И ? За да направите това, в точки И Посоката на промяна на функцията към екстремума се определя с помощта на градиента. Колкото по-голяма е стойността на частната производна, толкова по-бързо функцията се променя към екстремума. Следователно увеличенията И се избират пропорционално на стойността на частните производни И по точки
И
. По този начин,
И
, Където – стойност, наречена стъпка, която определя мащаба на промяната И .

Пример 7.4.

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

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

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

;
,

Нека направим още една итерация. В точката
,
при
ние имаме

;
,

Фиг.7.3. Геометрична интерпретация на две стъпки

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

На фиг. 7.3 показва движението по наклона, което е извършено в в този пример. Поведение показва посоката на промяна на функцията към максимума. Ако вземем градиента със знак минус, тогава ще се придвижим към минимума.

Специфичен проблем с градиентните методи е изборът на размер на стъпката T. Ако правим малки стъпки, ще търсим оптимума много дълго време. Ако изберете неговата стойност твърде голяма, тогава оптимумът може да бъде „превишен“. Междинният проблем за избора на оптимален размер на стъпката се решава с помощта на подходящи методи. Ако стъпка Tсе определя приблизително, тогава те като правило попадат не в оптимума, а в неговата зона. Градиентните методи осигуряват определянето на локалните оптимуми. Когато се търси глобален оптимум с помощта на градиент, често има съмнение, че намереният оптимум е глобален. Това е недостатъкът на този метод при решаване на проблеми с неконвексно програмиране.

Въпроси за самопроверка

Постановка на проблема с нелинейното програмиране.

Процесът на намиране на решение на проблем с нелинейно програмиране, използвайки неговата геометрична интерпретация.

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

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

Помощни определения и теореми, необходими за разглеждане на централната теорема на нелинейното програмиране - теоремата на Кун-Тъкър.

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

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

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

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

В предишния раздел бяха конструирани условията на Кун-Тъкър за задачи условна оптимизация. Използвайки метода на умножителя на Лагранж, беше получена интуитивна идея, че условията на Kuhn-Tanker са тясно свързани с необходимите условия за оптималност. IN този разделРазгледани са строги формулировки на необходими и достатъчни условия за оптималност на решаването на задача на нелинейно програмиране.

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

Нека разгледаме проблема с нелинейното програмиране (0) - (2). Нека са диференцируеми функции и x* е допустимо решение на тази задача. Нека го поставим. Освен това нека са линейно независими. Ако x* е оптималното решение на проблем с нелинейно програмиране, тогава има двойка вектори, която е решение на проблема на Kuhn-Tucker (3) - (7).

Условието, че те трябва да бъдат линейно независими, е известно като условие за линейна независимост и по същество е някакъв вид условие за редовност за осъществимия регион, което почти винаги е изпълнено за проблеми с оптимизацията, срещани на практика. Като цяло обаче проверката на изпълнението на условието за линейна независимост е много трудна, тъй като се изисква предварително да се знае оптималното решение на проблема. В същото време условието за линейна независимост винаги е изпълнено за проблеми с нелинейно програмиране, които имат следните свойства.

1. Всички ограничения под формата на равенства и неравенства съдържат линейни функции.
2. Всички ограничения за неравенство съдържат вдлъбнати функции, всички ограничения за равенство съдържат линейни функции и също така има, според поне, една възможна точка x, която се намира във вътрешността на областта, определена от ограниченията на неравенството. С други думи, има точка x, такава че

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

Минимизиране

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

На фиг. Фигура 1 показва областта на възможните решения на нелинейния проблем, формулиран по-горе. Ясно е, че има оптимално решение на този проблем. Нека покажем, че условието за линейна независимост не е изпълнено в оптималната точка.

Ориз.

Лесно се вижда, че векторите са линейно зависими, т.е. условието за линейна независимост в точката не е изпълнено.

Нека запишем условията на Kuhn-Tucker и проверим дали са изпълнени в точка (1, 0). Условия (3), (6) и (7) приемат следната форма;

От уравнение (11) следва, че докато уравнение (14) дава, Следователно, оптималната точка не е точка на Kuhn-Tucker.

Имайте предвид, че нарушаването на условието за линейна независимост не означава непременно, че точката на Kuhn-Tucker не съществува. За да потвърдим това, нека заменим целевата функция от този пример с функцията. В този случай оптимумът все още се постига в точка (1,0), в която условието за линейна независимост не е изпълнено. Условията на Kuhn-Tucker (12) - (16) остават непроменени и уравнение (11) приема формата

Лесно се проверява, че точката е точка на Кун-Тъкър, т.е. удовлетворява условията на Kuhn-Tucker.

Теоремата за необходимостта от условията на Kuhn-Tucker ни позволява да идентифицираме неоптимални точки. С други думи, теорема 1 може да се използва, за да се докаже, че дадена възможна точка, която удовлетворява условието за линейна независимост, не е оптимална, ако не удовлетворява условията на Kuhn-Tucker. От друга страна, ако в този момент условията на Kuhn-Tucker са изпълнени, тогава няма гаранция, че е намерено оптималното решение на нелинейния проблем. Като пример, разгледайте следния проблем с нелинейно програмиране.

Следващата теорема установява условията, при които точката на Kuhn-Tucker автоматично съответства на оптималното решение на проблем с нелинейно програмиране.

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

Нека разгледаме проблема с нелинейното програмиране (0) - (2). Нека целевата функция е изпъкнала, всички ограничения за неравенство съдържат вдлъбнати функции, а ограниченията за равенство съдържат линейни функции. Тогава, ако има решение, което удовлетворява условията на Kuhn-Tucker (3) - (7), тогава x* е оптималното решение на проблема с нелинейното програмиране.

Ако условията на теорема 2 са изпълнени, тогава намирането на точката на Kuhn-Tucker осигурява оптимално решение на проблема с нелинейното програмиране.

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

Минимизиране

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

С помощта на теорема 2 доказваме, че решението е оптимално. Ние имаме

Тъй като матрицата е положително полуопределена за всички x, функцията се оказва изпъкнала. Първото ограничение на неравенството съдържа линейна функция, която е едновременно изпъкнала и вдлъбната. За това

за да покажем, че функцията е вдлъбната, изчисляваме

Тъй като матрицата е отрицателно определена, функцията е вдлъбната. Функцията е включена в линейното ограничение в уравнението за равенство. Следователно, всички условия на теорема 2 са изпълнени; ако покажем, че това е точката на Kuhn-Tucker, ние наистина ще установим оптималността на решението. Условията на Kuhn-Tucker за пример 2 имат формата

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

Поставяйки го, получаваме и. Така решението x*=(1, 5) удовлетворява условията на Kuhn-Tucker. Тъй като условията на теорема 2 са изпълнени, тогава оптималното решение на задачата от пример 3. Имайте предвид, че има и други стойности на и които удовлетворяват системата (22) - (29).

Бележки

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

Нека напишем функцията на Лагранж: (4)
където λ i , i=1..m – неопределени множители на Лагранж; z(X) и q i (X) са изпъкнали нагоре функции.

Теорема на Кун-Тъкър. За да бъде план X 0 решение на задача (1) – (4), е необходимо и достатъчно да съществува вектор λ 0 ≥ 0, така че двойката (X 0 ,λ 0) за всички X ≥ 0 и λ ≥ 0.
L(X, λ 0) ≤ L(X 0 ,λ 0) ≤ L(X 0 ,λ)

Цел на услугата. Използва се онлайн калкулатор за намиране на екстремума на функция чрез множителите на Лагранж в онлайн режимс проверка на решението в MS Excel. В този случай се решават следните задачи:

функцията на Лагранж L(X) се компилира под формата на линейна комбинация от функцията F(X) и ограничения g i (x);
намират се частните производни на функцията на Лагранж, ∂L/∂x i , ∂L/∂λ i ;
компилира се система от (n+m) уравнения, ∂L/∂x i = 0.
определят се променливите x i и множителите на Лагранж α i.

За да може функцията на две векторни променливи (4) да има седлова точка, е необходимо и достатъчно да се изпълни следното Условия на Kuhn-Tucker:
(5)
(6)
(7)
(8)

Ако проблемът е решен минимизиране, тогава има седлова точка (X 0 , Y 0), ако отношенията са изпълнени
L(X, λ 0) ≤ L(X 0, Y 0) ≤ L(X 0, Y)
Условията на Kuhn-Tucker за съществуване на седлова точка на функцията на Лагранж ще променят знака в (5) и (7) на противоположния.

Пример. Проверете изпълнението на условията на Kuhn-Tucker. Намерете оптималната точка на проблем с линейно програмиране с ограничения:
f(x) = x 1 2 -x 2 → min
g 1 (x) = x 1 - 1 ≥ 0
g 2 (x) = 26 - x 1 2 -x 2 2 ≥ 0
h 1 (x) = x 1 + x 2 - 6 = 0

Решение:
Функция на Лагранж: L(X, λ) = x 1 2 -x 2 - λ 1 (1-x 1) + λ 2 (26-(x 1 2 +x 2 2)) + λ 3 (6-(x 1) +x 2))
Необходимо условие за екстремума на функцията на Лагранж е равенството на нула на нейните частни производни по отношение на променливите x i и неопределените фактори λ.
Нека проверим изпълнението на условията на Kuhn-Tucker. Нека изчислим матриците на вторите производни целева функцияи ограничителни функции.

Хесианската матрица H f е положително полуопределена за всички стойности на x, следователно f(x) е изпъкнала функция.
Ограничение g 1 (x) – линейна функция, който е едновременно изпъкнал и вдлъбнат.
Матрицата на Хесиан за функцията g 2 (x) има формата:

Δ 1 = -2, Δ 2 = 4.
Тъй като матрицата H g 2 е отрицателно определена, g 2 (x) е вдлъбната.
Функцията h 1 (x) е включена в линейното ограничение под формата на равенство. Следователно условията (a), (b) и (c) на теорема 1 са изпълнени. Нека сега намерим оптималната точка x *.
Ние имаме:

Уравнението приема следната форма:

За j=1 и j=2 съответно могат да се получат следните изрази:
j=1, 2x 1 -μ 1 + 2x 2 μ 2 + λ 1 = 0
j=2, -1 + 2x 2 μ 2 + λ 1 = 0
По този начин условията на Kuhn-Tucker за нашия пример са както следва:
2x 1 -μ 1 + 2x 2 μ 2 + λ 1 = 0
-1 + 2x 2 μ 2 + λ 1 = 0
x 1 + x 2 – 6=0
μ 1 (x 1 -1) = 0
μ 2 (26 - x 1 2 – x 2 2) = 0
μ 1 , μ 2 ≥ 0

От третото уравнение намираме: x 1 = 6-x 2. Замествайки стойността x 1 в останалите уравнения, получаваме:
2(6-x 2) - μ 1 + 2μ 2 (6-x 2)
-1 + 2x 2 μ 2 + λ 1 = 0
μ 1 (6-x 2 -1) = 0 → x 2 = 5, x 1 = 1
μ 2 (26 – (6-x 2) 2 – x 2 2) = 0
Нека заместим x 2 = 5 в първото и второто уравнения:

От второто уравнение изразяваме λ и го заместваме в първото уравнение:
3 - μ 1 - 8μ 2 = 0
Нека μ 1 = 0,1 ≥ 0, тогава μ 2 = 2,2 ≥ 0. Така точката x * = е минималната точка.

Формулиране на проблема

Нека разгледаме проблем с нелинейна оптимизация. Нека има функции

При условия.

Уилям Каруш в дипломната си работа намери необходимите условияв общия случай, когато наложените условия могат да съдържат както уравнения, така и неравенства. Независимо един от друг Харолд Кун и Албърт Тъкър стигат до същите заключения.

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

Ако при наложените ограничения има решение на задачата, тогава съществува ненулев вектор от множители на Лагранж, така че за функцията на Лагранж изпълнени са условията:

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

Изброените необходими условия за минимум на функция в общия случай не са достатъчни. Вариантите са няколко допълнителни условия, което ги прави достатъчни.

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

Ако за една допустима точка са изпълнени условията за стационарност, допълнителна нетвърдост и неотрицателност, както и λ 1 > 0, то .

По-слаби условия

Ако за допустима точка са изпълнени условията за стационарност, допълващи нетвърдостта и неотрицателността, както и ( Състоянието на Слейтър), Че .

Фондация Уикимедия. 2010 г.

Вижте какви са „условията на Каруш-Кун-Тъкър“ в други речници:

В теорията на оптимизацията условията на Karush Kuhn Tucker (KKT) са необходими условия за решаване на проблем с нелинейно програмиране. За да бъде решението оптимално, трябва да се направят определени неща... ... Wikipedia

В теорията на оптимизацията условията на Karush Kuhn Tucker (KKT) са необходими условия за решаване на проблем с нелинейно програмиране. За да бъде решението оптимално, трябва да бъдат изпълнени някои условия за редовност.... ... Wikipedia

Уилям Каруш Уилям Каруш Дата на раждане: 1 март 1917 г. (1917 03 01) Място на раждане: Чикаго, САЩ Дата на смърт ... Wikipedia

Този термин има и други значения, вижте Оптимизация. Оптимизацията в математиката, компютърните науки и изследването на операциите е проблемът за намиране на екстремума (минимум или максимум) на целева функция в някаква област на крайномерен вектор ... Wikipedia Wikipedia

Метод на умножителя на Лагранж, метод за намиране условен екстремумфункции f(x), където, спрямо m ограничения, i варира от едно до m. Съдържание 1 Описание на метода ... Wikipedia

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

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

Нека съставим функцията на Лагранж за този проблем:

(4.2)

Ако условието за редовност е изпълнено (има поне една точка Х,за което g i(х)>0 за всички аз), тогава е валидна следната теорема.

Теорема.вектор х(0) ако и само ако е оптимално решениезадача (4.1), когато има вектор Λ (0), такъв че за за всички

точка ( X (0),Λ (0)) се нарича седлоточка за функция Е(х,Λ), а теоремата се нарича теоремата за седловата точка.Нека докажем достатъчността на условията (4.3).

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

при .

Правилното неравенство е валидно за всяко , Следователно

Тогава от лявото неравенство получаваме

Тъй като в този случай

Че f(X (0))>f(х).

Така че точката X (0)удовлетворява (4.1) и във всички други точки, удовлетворяващи (4.1), функцията приема стойност, по-малка от X (0).

Това твърдение води решението на проблема с НЛП до намиране на седловините на функцията на Лагранж Е(х,Λ).

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

Ако f(х) И g i(х)-диференцируеми функции, тогава условията (4.3) са еквивалентни на следните локални условия на Kuhn-Tucker:

Изразяване

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

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

Тези условия могат да бъдат записани в векторна форма:

Пример.Намерете макс З=-х 1 2 -х 2 2 с ограничения

Нека покажем, че съществува Λ (0) 0, за което условията на Kuhn-Tucker (4.4), (4.5) за функцията са изпълнени в оптималната точка Е(х,Λ):

Е(х,Λ)=- х 1 2 -х 2 2 +λ 1 (2 х 1 +х 2 -2)+λ 2 (8-2 х 1 -х 2)+λ 3 (6- х 1 -х 2).

Съгласно условията (4.5), λ 2 и λ 3 трябва да приемат нулеви стойности, тъй като, замествайки х 1 =0,8 и х 2 =0,4 в израз

имаме стойности, по-големи от нула, и по условие

Съгласно условието λ 1 може да приеме ненулева стойност, тъй като

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

трябва да приема нулеви стойности, тъй като координатите на вектора X (0)са различни от нула. Намираме λ 1 =0,8. Следователно, в точката ( X (0),Λ (0)) условията на Kuhn-Tucker са изпълнени и това наистина е точка на екстремум.

Нека разгледаме условията на Kuhn-Tucker в малко по-различна форма.

Нека имаме оптимизационна задача с ограничения под формата на равенства:

z= f(х 1 , х 2 , …, xn) → мин

при условия:

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

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

ж н(х 1 , х 2 , . . . , x n) = 0.

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

В този случай седловата точка трябва да осигурява минимум в своите променливи x iи максимум по променливи λ й.

Необходими условия за стационарна точка са частните производни от първи ред по отношение на всички променливи да са равни на нула:

Имайте предвид, че второто уравнение предполага, че само валидните точки ще удовлетворят необходимите условия.

За да се получи достатъчно условие за съществуването на минимум, е необходимо да се добави изискването хесианът на целевата функция да бъде положително определен.

Нека помислим общзадача математическо програмиране:

Z= f(X) → min,

при условия:

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

Нека формираме функцията на Лагранж:

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

Второто уравнение може да се трансформира чрез отхвърляне на отслабващите променливи и преминаване към ограничения на неравенството. Нека получим ограниченията на първоначалния проблем. Третото уравнение може да се умножи по потребителски интерфейс/2 и заменете отслабващите променливи, като ги изразите от второто уравнение на системата.

Има още едно условие, което трябва да бъде изпълнено при минималната точка. Това условие: λ аз= 0, което е следствие от анализа физически смисълкоефициенти на функцията на Лагранж.

Може да се покаже, че

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

f* - оптимална стойностфункции.

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

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

Изразите във втория ред гарантират, че оптималната точка е валидна.

Третият ред съдържа следната информация: ако ограничението е активно (т.е. изразът в скоби е равен на нула), тогава съответният коефициент на Лагранж е строго положителен. Положителността на коефициента на Лагранж означава, че съответното ограничение е активно, т.е. фактът, че това ограничение е оскъдно, е точно това, което спира по-нататъшно подобрениецелева функция. Ако ограничението не е активно (т.е. изразът в скоби не е равен на нула), тогава съответният коефициент на Лагранж трябва да бъде равно на нула, т.е. Това ограничение не е недостатъчно; то не засяга по-нататъшното подобряване на целевата функция.

За условната максимална точка коефициентите на Лагранж променят знака на противоположния (тъй като оптималната стойност на целевата функция в условната максимална точка трябва да се увеличи).

Горните условия са еквивалентни Теорема на Кун-Тъкъри често се наричат по същия начин.

Достатъчно условие за минимум (максимум) е изпъкналостта (вдлъбнатостта) на целевата функция в стационарна точка. Това означава, че Хесианът трябва да бъде положително (отрицателно) определен.

Обобщение на материала в тази глава може да се види в две презентации:

файл “Нелинейно програмиране”;

файл "Теорема на Кун-Тъкър".

Слайдове 10-14 от презентацията „Теорема на Кун-Тъкър“ показват пример за решаване на проблема на Кун-Тъкър.

4.5. Контролни въпроси

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

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

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

Възможни отговори:

Въпрос 2.При дадена реална функция f(х), определени върху сегмента от реални числа S=. Позволявам х 1 и х 2 са точките на тази отсечка и 0 £ l £ 1.

Кое от следните неравенства е условие една функция да бъде строго вдлъбната?

Възможни отговори:

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

1) изпъкнал;

2) строго изпъкнали;

3) вдлъбнат;

4) строго вдлъбнати;

5) изпъкнали и вдлъбнати.

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

3) вдлъбнат; 4) строго вдлъбнати;

5) изпъкнали и вдлъбнати.

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

1) изпъкнал; 2) нито изпъкнал, нито вдлъбнат;

3) строго изпъкнали; 4) вдлъбнат:

5) изпъкнали и вдлъбнати.

Въпрос 6. Нов моделвисокоскоростен мотоциклет “Охлюв” се продава от фирмата на цена (30 – 2 х) хиляди долара за парче, където х- брой продадени мотоциклети. Променливите производствени разходи са $6 000 на единица, а постоянните разходи са $30 000. Увеличете максимално печалбата на вашия бизнес за седмицата.

Да кажем, че промяната в ставката на данъка върху продажбите е довела до допълнителни $4000 данък върху продажбите за всеки продаден мотоциклет.

Как ще се промени оптималното производство на мотоциклети в сравнение с първоначалната ситуация?

(Решете с помощта на функцията на Лагранж.)

Възможни отговори:

1) ще се увеличи с 2 ; 2) ще намалее с 2 ;

3) няма да се промени; 4) ще се увеличи с 1 ;

5) ще намалее с 1 .

Въпрос 7.Да приемем, че имате 2 седмици (14 дни) ваканция, която да прекарате на Канарските острови и Ница. Нека вашата функция на полезност е във формата 2 KN – 3К 2 – 4N 2,Където ДА СЕИ Н-броя дни, които прекарвате съответно на Канарските острови и Ница.

Колко дни трябва да прекарате в Ница, за да постигнете максимална полезност?

(За да решите, използвайте функцията на Лагранж. Закръглете резултата до най-близкото цяло число. Проверете дали условията за оптималност на Kuhn-Tucker са изпълнени.)

Възможни отговори:

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,25х 1 (на продукт 1); Р 2 = 14 – 0,5х 2 (за продукт 2), където х 1 и х 2 - обеми на продажби на продукти. Да приемем, че всички произведени продукти са продадени. Максималният общ обем на продажбите е 57.

Какво е оптималното освобождаване на продукт 2?

Възможни отговори:

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

Въпрос 10.Собственикът на малко предприятие има 100 хиляди рубли за следващия месец, които може да похарчи за увеличаване на дълготрайните активи ДА СЕ(закупуване на оборудване) на цена от 1 хил. Рубли на единица или за закупуване на допълнителен труд Лна цена от 50 рубли / час. Увеличение на готовите продукти, които могат да бъдат продадени за 10 хиляди рубли. за единица, определена от производствената функция F(K, L)= L 2/7 K 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.