Tucker kun podmínky v geometrické podobě. Koncept sedlového bodu. Kuhn-Tuckerův teorém

V předchozí části byly konstruovány Kuhnovy podmínky-Tucker pro úkoly podmíněná optimalizace. Pomocí metody Lagrangeova multiplikátoru byla získána intuitivní představa, že podmínky Kuhn-Tanker úzce souvisí s podmínkami nutné optimality. V tato sekce Jsou uvažovány rigorózní formulace nutných a postačujících podmínek pro optimalitu řešení problému nelineárního programování.

Věta 1. Nezbytnost Kuhn-Tuckerových podmínek

Uvažujme problém nelineárního programování (0) - (2). Nechť být diferencovatelné funkce a x* je přípustné řešení tohoto problému. Řekněme to. Dále ať jsou lineárně nezávislé. Pokud je x* optimálním řešením problému nelineárního programování, pak existuje dvojice vektorů, která je řešením Kuhn-Tuckerova problému (3) - (7).

Podmínka, že musí být lineárně nezávislé, se nazývá podmínka lineární nezávislost a v podstatě představuje určitou podmínku pravidelnosti přípustné oblasti, která je téměř vždy splněna pro optimalizační problémy vyskytující se v praxi. Obecně je však kontrola splnění podmínky lineární nezávislosti velmi obtížná, neboť se vyžaduje, aby bylo předem známo optimální řešení problému. Podmínka lineární nezávislosti je přitom vždy splněna u problémů nelineárního programování, které mají následující vlastnosti.

• 1. Všechna omezení ve formě rovností a nerovností obsahují lineární funkce.
• 2. Všechna omezení nerovnosti obsahují konkávní funkce, všechna omezení rovnosti obsahují lineární funkce a existuje alespoň jeden proveditelný bod x, který se nachází uvnitř oblasti definované omezeními nerovnosti. Jinými slovy, existuje bod x takový, že

Pokud není splněna podmínka lineární nezávislosti v optimálním bodě, pak Kuhn-Tuckerův problém nemusí mít řešení.

Minimalizovat

pod omezeními

Na Obr. Zobrazena 1 oblast přípustná řešení formulované výše nelineární problém. Je jasné, že na tento problém existuje optimální řešení. Ukažme, že podmínka lineární nezávislosti není v optimálním bodě splněna.

Rýže.

Je snadné vidět, že vektory jsou lineárně závislé, tzn. není splněna podmínka lineární nezávislosti v bodě.

Zapišme si Kuhn-Tuckerovy podmínky a zkontrolujme, zda jsou splněny v bodě (1, 0). Podmínky (3), (6) a (7) mají následující formu;

Z rovnice (11) vyplývá, že zatímco rovnice (14) dává, Optimálním bodem tedy není Kuhn-Tuckerův bod.

Všimněte si, že porušení podmínky lineární nezávislosti nutně neznamená, že Kuhn-Tuckerův bod neexistuje. Abychom to potvrdili, nahradíme účelovou funkci z tohoto příkladu funkcí. V tomto případě je optima stále dosaženo v bodě (1,0), ve kterém není splněna podmínka lineární nezávislosti. Kuhn-Tuckerovy podmínky (12) - (16) zůstávají nezměněny a rovnice (11) má tvar

Je snadné zkontrolovat, že bod je Kuhn-Tuckerův bod, tzn. splňuje podmínky Kuhn-Tucker.

Věta o nutnosti Kuhn-Tuckerových podmínek nám umožňuje identifikovat neoptimální body. Jinými slovy, Věta 1 může být použita k prokázání, že daný proveditelný bod, který splňuje podmínku lineární nezávislosti, není optimální, pokud nesplňuje Kuhn-Tuckerovy podmínky. Na druhou stranu, pokud jsou v tomto bodě splněny Kuhn-Tuckerovy podmínky, pak neexistuje žádná záruka, že bylo nalezeno optimální řešení nelineárního problému. Jako příklad zvažte následující problém nelineárního programování.

Následující věta stanoví podmínky, za kterých Kuhn-Tuckerův bod automaticky odpovídá optimálnímu řešení problému nelineárního programování.

Věta 2. Dostatečnost Kuhn-Tuckerových podmínek

Uvažujme problém nelineárního programování (0) - (2). Nechť je účelová funkce konvexní, všechna omezení nerovnosti obsahují konkávní funkce a omezení rovnosti obsahují lineární funkce. Pokud pak existuje řešení, které splňuje Kuhn-Tuckerovy podmínky (3) - (7), pak x* je optimálním řešením problému nelineárního programování.

Pokud jsou splněny podmínky věty 2, pak nalezení Kuhn-Tuckerova bodu poskytuje optimální řešení problému nelineárního programování.

Větu 2 lze také použít k prokázání optimality toto rozhodnutí problémy nelineárního programování. Pro ilustraci, zvažte znovu příklad:

Minimalizovat

pod omezeními

Pomocí věty 2 dokážeme, že řešení je optimální. My máme

Protože je matice kladně semidefinitní pro všechna x, funkce se ukáže jako konvexní. První omezení nerovnosti obsahuje lineární funkce, který je konvexní i konkávní zároveň. Pro to

abychom ukázali, že funkce je konkávní, vypočítáme

Protože je matice záporně definitní, funkce je konkávní. Funkce je zahrnuta v lineárním omezení v rovnici rovnosti. V důsledku toho jsou splněny všechny podmínky věty 2; pokud ukážeme, že jde o Kuhn-Tuckerův bod, skutečně určíme optimálnost řešení. Kuhn-Tuckerovy podmínky pro příklad 2 mají tvar

Bod splňuje podmínky (24) - (26), a proto je přípustný. Rovnice (22) a (23) mají následující tvar:

Dáme to, dostaneme a. Řešení x*=(1, 5) tedy splňuje Kuhn-Tuckerovy podmínky. Vzhledem k tomu, že jsou splněny podmínky věty 2, je optimálním řešením úlohy z příkladu 3. Všimněte si, že existují i ​​jiné hodnoty a splňující systém (22) - (29).

Poznámky

• 1. U problémů vyskytujících se v praxi je obvykle splněna podmínka lineární nezávislosti. Pokud jsou všechny funkce v problému diferencovatelné, pak by měl být Kuhn-Tuckerův bod považován za možný bod optimální. Mnoho metod nelineárního programování tedy konverguje ke Kuhn-Tuckerovu bodu. (Zde je vhodné nakreslit analogii s případem neomezené optimalizace, kdy odpovídající algoritmy umožňují určit stacionární bod.)
• 2. Pokud jsou splněny podmínky věty 2, Kuhn-Tuckerův bod se zároveň ukazuje jako globální minimální bod. Bohužel kontrola dostatečných podmínek je velmi obtížná a navíc aplikované problémy často nemají požadované vlastnosti. Je třeba poznamenat, že přítomnost alespoň jednoho nelineárního omezení ve formě rovnosti vede k porušení předpokladů věty 2.
• 3. Dostatečné podmínky stanovené Větou 2 lze zobecnit na případ problémů s nekonvexními funkcemi zahrnutými do omezení ve formě nerovností, nekonvexních cílových funkcí a omezení nelineární rovnosti. V tomto případě se používají taková zobecnění konvexních funkcí, jako jsou kvazikonvexní a pseudokonvexní funkce.

Kuhn-Tuckerův teorém je zobecněním metod pro řešení optimalizačních problémů ve dvou směrech:

Lineární programování pro nelineární případ, který byl získán analogií nepříliš dobré jméno"nelineární programování";

Nelineární omezení rovnosti na omezeních nerovností.

Karush-Kuhn-Tucker metoda a podmínky ( Podmínky Karush-Kuhn-Tucker, KKT) jsou formálně nutné podmínky pro optimalitu problému nelineárního programování. Kromě, potřebné podmínky zahrnují tzv. podmínky pravidelnosti pro stacionární body - nedegeneraci množiny gradientů omezení. Metoda je zobecněním metody Lagrangeova multiplikátoru pro případ omezení nerovností.

Kuhn a Tucker zobecnili Lagrangeovu multiplikační metodu (pro použití při konstrukci kritérií optimality pro problémy s omezeními rovnosti) na případ obecného problému nelineárního programování s omezeními rovnosti i nerovností.

Hlavní metodou v nelineárním programování stále zůstává použití Lagrangeovy funkce získané přenesením omezení na účelovou funkci. Z tohoto principu jsou odvozeny i Kuhn-Tuckerovy podmínky.

William Karush ve svém diplomová práce v roce 1931 našel potřebné podmínky v obecný případ omezení rovnosti a nerovnosti. Nezávisle na tom, Harold Kuhn a Albert Tucker dospěli ke stejným závěrům později v roce 1941. Jejich výsledky byly obecnější.

Pokud je v rámci uložených omezení řešením problému, pak existuje vektor Lagrangeových multiplikátorů takový, že pro Lagrangeovu funkci jsou splněny podmínky:

- stacionárnost: ;

- doplňková měkkost: ;

- nezápornost:.

Uvedené nezbytné podmínky pro minimum funkce v obecném případě nestačí. Možností je několik dodatečné podmínky, díky čemuž jsou dostatečné:

- jednoduchý stav – 1) bod je stacionární, 2) je splněna podmínka komplementární nerigidity, 3) Lagrangeovy multiplikátory;

- Slaterův stav (slabší) – 1) bod je stacionární, 2) je splněna podmínka komplementární nerigidity, 3) .

Pokračujme přímo k důkazu Kuhn-Tuckerovy věty.

Li kontinuální funkce n proměnných x = (x1,...,xn) F(x) má v bodě X opt maximum, pak existuje ε > 0 takové, že pro všechny X z ε-okolí bodu X velkoobchod

F(x)≤F(x opt)

F(x)-F(x opt)≤0.

Zvolme dva typy přírůstku x j podél j souřadnice

Δx j =x j -x jopt >0,

Δx j =x j -x jopt<0.

Přechod v těchto vztazích k limitě v Δ x j→0, dostaneme:

Z těchto vztahů vyplývá, že

(3.6.1)

Podobný vztah lze získat pro případ minimální funkce. Tedy nutnost podmínek (3.6.1) dosáhnout v bodě x velkoobchod maximální nebo minimální funkce f(x), tj. pokud existuje extrém, jsou splněny podmínky (3.6.1). Ale rovnost nuly všech derivací v bodě x velkoobchod ještě nezajišťuje existenci extrému v něm, tedy podmínky (3.6.1) nejsou dostatečné. Geometricky to znamená, že v případě nulové derivace funkce jedné proměnné může existovat inflexní bod, nikoli maximum (nebo minimum), a v případě funkce dvou proměnných sedlový bod, resp. ne extrém atd. Proto body x velkoobchod, ve kterých jsou vztahy (3.6.1) splněny, nazýváme stacionární.

Všimněte si, že podmínka (3.6.1) byla získána díky možnosti přiřadit proměnnou X přírůstky dvou znamének, což je místo, kde dvě nerovnosti vznikly v a v . Li platná oblast hodnoty X omezena na nezáporné hodnoty X≥0, pak uvnitř oblasti, kde X> 0, podmínka (3.6.1) zůstává v platnosti, protože jsou zde povoleny přírůstky obou znamének. Na hranici regionu X≥ 0, kde X= 0, je povolen pouze kladný přírůstek Δ X>0, můžeme hovořit pouze o jednostranné derivaci a z (3.6.1) vyplývá následující nutná podmínka pro maximum:

V souladu s tím je nezbytná podmínka pro minimum na hranici regionu x j= 0 se zapíše jako

b) Problém podmíněného extrému

Při určování podmíněný extrém funkce, když potřebujete určit maximum (nebo minimum) funkce F(x) za omezujících podmínek:

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

f(x)=max;

gi(x)=bi;

Používá se také metoda Lagrangeových multiplikátorů, která stejně jako v případě klasického variačního počtu spočívá v zavedení Lagrangeovy funkce

(3.6.2)

kde λ i - neurčité faktory Lagrange.

Za předpokladu, že funkce je speciálním případem funkcionálu, dostaneme, že potřebné podmínky pro extrém najdeme přímou derivací vztahu (3.6.2) a zapíšeme je ve tvaru

Zavedeme-li vektory

vztahy (17-8) a (17-9) budou přepsány jako

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

kde rovnost vektorů k nule je chápána komponentně.

Obrázek 3.6.1 - Vysvětlení problému podmíněného extrému

Když n= 2 a m = 1 geometrický problém o nalezení podmíněného extrému dojde (obr. 17-6) k nalezení bodu tečnosti A křivky φ = b do jedné z křivek konstantní úroveň F= konst.

Formulace problému

Uvažujme nelineární optimalizační problém. Nechť jsou funkce

Za podmínek.

William Karush ve své práci našel potřebné podmínky v obecném případě, kdy uložené podmínky mohou obsahovat jak rovnice, tak nerovnice. Harold Kuhn a Albert Tucker nezávisle na sobě došli ke stejným závěrům.

Nezbytné podmínky pro minimum funkce

Pokud pod uloženými omezeními existuje řešení problému, pak existuje nenulový vektor Lagrangeových multiplikátorů takový, že pro Lagrangeovu funkci jsou splněny podmínky:

Dostatečné podmínky pro minimum funkce

Uvedené nezbytné podmínky pro minimum funkce v obecném případě nestačí. Existuje několik možností pro dodatečné podmínky, které je činí dostatečnými.

Jednoduchá formulace

Pokud jsou pro přípustný bod splněny podmínky stacionarity, komplementární nerigidity a nezápornosti a také λ 1 > 0, pak .

Slabší podmínky

Pokud jsou pro přípustný bod splněny podmínky stacionarity, doplňkové k nerigiditě a nezápornosti, stejně jako ( Slaterův stav), Že .

Nadace Wikimedia. 2010.

Podívejte se, jaké jsou podmínky „Karush-Kuhn-Tucker“ v jiných slovnících:

V teorii optimalizace jsou podmínky Karush Kuhn Tucker (KKT) nezbytnými podmínkami pro řešení problému nelineárního programování. Aby bylo řešení optimální, je třeba udělat určité věci... ... Wikipedie

V teorii optimalizace jsou podmínky Karush Kuhn Tucker (KKT) nezbytnými podmínkami pro řešení problému nelineárního programování. Aby bylo řešení optimální, musí být splněny určité podmínky pravidelnosti... ... Wikipedie

William Karush William Karush Datum narození: 1. března 1917 (1917 03 01) Místo narození: Chicago, USA Datum úmrtí ... Wikipedia

Tento termín má jiné významy, viz Optimalizace. Optimalizace v matematice, informatice a operačním výzkumu, problém hledání extrému (minima nebo maxima) Objektivní funkce v nějaké doméně konečných rozměrů vektoru ... Wikipedie Wikipedie

Metoda Lagrangeova multiplikátoru, metoda pro nalezení podmíněného extrému funkce f(x), kde se vzhledem k m omezením i mění od jedné do m. Obsah 1 Popis metody ... Wikipedie

Věta 7.2. Pro úlohu konvexního programování (7.4)–(7.6), jejíž množina přípustných řešení má vlastnost pravidelnosti, je plán optimální plán tehdy a jen tehdy, když existuje vektor takový, že
– sedlový bod funkce Lagrange.

Za předpokladu, že účelová funkce
a funkcí jsou spojité a diferencovatelné, pak lze Kuhn-Tuckerův teorém doplnit o analytické výrazy, které určují nutnou a postačující podmínku bodu
byl sedlový bod funkce Lagrange, tzn. bylo řešením problému konvexního programování. Tyto výrazy mají následující tvar:

Kde A jsou hodnoty odpovídajících parciálních derivací Lagrangeovy funkce vypočítané v sedlovém bodě.

Kuhn-Tuckerův teorém zaujímá ústřední místo v teorii nelineárního programování. Platí i pro problémy tzv. kvadratického programování, tzn. kde je účelová funkce
s omezeními:

.

V obecném případě řešení problémů nelineárního programování pro určení globálního extrému problému neexistuje účinná výpočetní metoda, pokud není známo, že jakýkoli lokální extrém je také globální. V konvexním a kvadratickém programovacím problému je tedy množina možných řešení konvexní, pak je-li účelová funkce konkávní, jakékoli lokální maximum je také globální.

Příklad 7.3. Pomocí Kuhn-Tuckerovy věty najdeme
pod omezeními

Řešíme graficky (obr. 7.2) a zjistíme:
;
;
(podrobnosti viz řešení níže). Ukažme, že existuje vektor Y 0 0, při které jsou Kuhn-Tuckerovy podmínky splněny v optimálním bodě. Složme Lagrangeovu funkci:

Řešení
ze systému zjistíme:
. Z druhé rovnice
dosadit do první rovnice soustavy. Rozlišovat podle :
. Ve výrazech A nahradit hodnoty
A
. Máme hodnoty parciálních derivací větší než nula a podle podmínky se tedy musí rovnat nule =0 A =0. Na druhé straně, nemusí přijmout nulové hodnoty, protože
odtud
; Všechno
těch. Kuhn-Tuckerovy podmínky jsou splněny, proto je tento bod extrémním bodem.

Obr.7.2. Grafické řešení nelineární úlohy

příklad programování 7.3

Nutná podmínka pro optimalitu pro problém nelineárního programování lze formulovat následovně. Nechat
je optimálním řešením problému (7.4)–(7.6) a funkcí
,
,
v tomto bodě rozlišitelné. Li
je nesingulární bod přípustné množiny problému (7.4)–(7.6), pak je to Kuhn-Tuckerův bod tohoto problému.

Pokud je tedy přípustná sada
problém (7.4)-(7.6) nemá singulární body a funkce F(M),G i (M), (
) rozlišitelné ve všech bodech
, pak je třeba hledat optimální řešení tohoto problému mezi Kuhn-Tuckerovými body.

Jak je známo z matematické analýzy, speciální bod množiny přípustných řešení soustavy lineárních rovnic a nerovnic tvaru

tj. sady proveditelných řešení

pokud na místě
gradienty těchto funkcí jsou lineárně závislé
, které se v něm proměňují . Například,
– singulární bod množiny

Opravdu,

Jedná se tedy o lineárně závislý systém.

Gradientní funkce
je vektor, jehož souřadnice se rovnají hodnotám parciálních derivací funkce
na místě M 0 Tento vektor ukazuje směr nejrychlejšího růstu funkce.

Nezbytná podmínka optimality je pro řešení většiny problémů nelineárního programování málo použitelná, protože Pouze ve vzácných případech je možné najít všechny Kuhn-Tuckerovy body problému nelineárního programování.

Dostatečná podmínka pro optimalitu pro problém nelineárního programování: pokud
je pak sedlový bod Lagrangeovy funkce pro problém (7.4)–(7.6).
je optimálním řešením tohoto problému.

Tato podmínka není v obecném případě nutná: Lagrangeova funkce nemusí mít sedlové body, zatímco původní problém nelineárního programování má zároveň optimální řešení.

Jsou známy různé metody, které umožňují přibližně najít optimální řešení problému nelineárního programování. Tyto metody však poskytují poměrně dobrou aproximaci pouze pro problém konvexního programování, kde je každý lokální extrém také globální. Obecně platí, že pod spád metodami rozumí metody, ve kterých se pohyb do optimálního bodu funkce shoduje se směrem gradientu této funkce, tzn. počínaje nějakým bodem
sekvenční přechod se provádí do některých dalších bodů, dokud není identifikováno přijatelné řešení původní problém. V tomto případě lze gradientní metody rozdělit na 2 skupiny.

NA První Tato skupina zahrnuje metody, ve kterých zkoumané body nepřekračují rozsah proveditelných řešení problému. Nejběžnější z těchto metod je metoda Frank-Wolf (Vlk). Takové metody zahrnují metodu projektované Rosenovy gradienty, metoda platné pokyny Zeutendijk.

spol. druhý Tato skupina zahrnuje metody, ve kterých zkoumané body mohou nebo nemusí patřit do oblasti proveditelných řešení. V důsledku implementace iteračního procesu je však nalezen bod v oblasti proveditelných řešení, který určuje přijatelné řešení.

Z těchto metod je nejpoužívanější metoda penalizační funkce nebo metoda Arrow-Hurwitz.

Při hledání řešení problémů pomocí gradientních metod, včetně výše uvedených, se iterační proces provádí až do ten okamžik, zatímco gradient funkce
v dalším bodě
nebude rovna nule nebo dokud
, Kde – poměrně malé kladné číslo charakterizující přesnost výsledného řešení.

Řešení složitých problémů nelineárního programování pomocí gradientních metod zahrnuje velké množství výpočtů a doporučuje se pouze pomocí počítače.

Na příkladu si ukážeme obecný význam gradientních metod pro řešení problémů nelineárního programování.

Nechť existuje funkce dvou proměnných
. Nechť jsou počáteční hodnoty proměnných
a hodnotu funkce
. Li
není extrém, pak se určí takové nové hodnoty proměnných
A
takže další hodnota funkce
se ukázalo být blíže optimu než předchozí.

Jak se určuje velikost přírůstků? A ? K tomu v bodech A Směr změny funkce směrem k extrému je určen pomocí gradientu. Jak větší hodnotu parciální derivace, tím rychleji se funkce mění směrem k extrému. Proto ty přírůstky A jsou voleny úměrně hodnotě parciálních derivátů A v bodech
A
. Tím pádem,
A
, Kde – hodnota zvaná krok, která nastavuje měřítko změny A .

Příklad 7.4.

Nechť je třeba maximalizovat funkci

(maximálně v bodě (3;2))

.

Na místě
,
na
my máme

;
,

Udělejme ještě jednu iteraci. Na místě
,
na
my máme

;
,

Obr.7.3. Geometrická interpretace dvou kroků

gradientová metoda například 7.4

Na Obr. 7.3 ukazuje pohyb po gradientu, který byl proveden v v tomto příkladu. přístup udává směr změny funkce směrem k maximu. Pokud vezmeme gradient se znaménkem mínus, posuneme se směrem k minimu.

Specifickým problémem gradientních metod je volba velikosti kroku t. Pokud budeme dělat malé krůčky, budeme velmi dlouho hledat optimum. Pokud zvolíte jeho hodnotu příliš velkou, můžete „přestřelit“ optimum. Meziproblém výběru optimální velikosti kroku je řešen pomocí vhodných metod. Pokud krok t stanoveny přibližně, pak zpravidla nespadají do optima, ale do jeho zóny. Gradientní metody poskytují určení lokálních optim. Při hledání globálního optima pomocí gradientu často existuje pochybnost, že nalezené optimum je globální. To je nevýhoda této metody při řešení nekonvexních problémů programování.

Samotestovací otázky

Sdělení problému nelineárního programování.

Proces hledání řešení problému nelineárního programování pomocí jeho geometrické interpretace.

Algoritmus Lagrangeovy metody pro řešení problému nelineárního programování.

Aplikace Lagrangeovy metody na řešení problému nelineárního programování v případě, že podmínky spojení jsou nerovnice.

Pomocné definice a věty nezbytné pro uvažování centrální věty nelineárního programování - Kuhn-Tuckerovy věty.

Kuhn-Tuckerův teorém.

Nezbytná a postačující podmínka optimality pro problém nelineárního programování.

Obecný význam gradientních metod pro přibližné řešení problémů nelineárního programování.

Skupiny gradientních metod pro přibližné řešení problémů nelineárního programování.

Ústřední místo v teorii nelineárního programování zaujímá Kuhn-Tuckerův teorém. Nechť je zadán problém nelineárního programování:

nalézt maximální hodnota funkcí Z=F(x 1, x 2, ..., x n) s omezeními

Pojďme sestavit Lagrangeovu funkci pro tento problém:

(4.2)

Pokud je splněna podmínka regulérnosti (je zde alespoň jeden bod X, pro který g i(X)>0 pro všechny i), pak platí následující věta.

Teorém. Vektor X(0) tehdy a jen tehdy, když je optimální řešení problém (4.1), když existuje vektor Λ (0) takový, že pro pro všechny

Tečka ( X (0),Λ (0)) se nazývá sedlo bod za funkci F(X,Λ) a věta se nazývá teorém sedlového bodu. Dokažme dostatečnost podmínek (4.3).

Důkaz. Nechat X(0) >0 a Λ (0) >0 - sedlový bod funkce F(X,Λ). Pokud místo toho v (4.3). F(X,Λ) dosadíme jeho hodnotu (4.2), dostaneme

na .

Správná nerovnost je tedy platná pro všechny

Pak z levé nerovnosti dostaneme

Protože v tomto případě

Že F(X (0))>F(X).

Takže pointa X (0) vyhovuje (4.1) a ve všech ostatních bodech vyhovujících (4.1), funkce nabývá hodnoty menší než při X (0).

Toto tvrzení vede řešení problému NLP k nalezení sedlových bodů Lagrangeovy funkce F(X,Λ).

Důkaz nezbytnosti podmínek (4.3) není vzhledem ke své složitosti uvažován.

Li F(X) A g i(X)-diferencovatelné funkce, pak podmínky (4.3) jsou ekvivalentní následujícímu místní podmínky Kuna-Tucker:

Výraz

znamená, že hodnota parciální derivace Lagrangeovy funkce se bere v bodě ( X (0), Λ (0)), kde

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

Tyto podmínky lze zapsat vektorová forma:

Příklad. Najít max Z=-X 1 2 -X 2 2 s omezeními

Ukažme, že existuje Λ (0) 0, pro které jsou Kuhn-Tuckerovy podmínky (4.4), (4.5) pro funkci splněny v optimálním bodě F(X,Λ):

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

Podle podmínek (4.5) musí λ 2 a λ 3 nabývat nulových hodnot, protože dosazením X 1 = 0,8 a X 2 = 0,4 ve vyjádření

máme hodnoty větší než nula a podle podmínky

Podle podmínky může λ 1 nabývat nenulové hodnoty, protože

V souladu s (2.16) derivát

musí mít nulové hodnoty, protože souřadnice vektoru X (0) se liší od nuly. Zjistíme λ 1 =0,8. Proto v bodě ( X (0),Λ (0)) jsou Kuhn-Tuckerovy podmínky splněny a jde skutečně o extrém.

Podívejme se na Kuhn-Tuckerovy podmínky v trochu jiné podobě.

Mějme problém s optimalizací s omezeními ve formě rovnosti:

z= F(X 1 , X 2 , …, xn) → min

za podmínek:

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.

Podmíněný minimální bod funkce F se shoduje se sedlovým bodem funkce Lagrange:

V tomto případě musí sedlový bod poskytovat minimum ve svých proměnných x i a maximum nad proměnnými λ j.

Nezbytné podmínky pro stacionární bod jsou, že parciální derivace prvního řádu vzhledem ke všem proměnným jsou rovny nule:

Všimněte si, že z druhé rovnice vyplývá, že pouze platné body budou splňovat nezbytné podmínky.

Pro získání postačující podmínky pro existenci minima je nutné doplnit požadavek, aby Hessián objektivní funkce byl kladně definitní.

Uvažujme Všeobecnéúkol matematické programování:

Z= F(X) → min,

za podmínek:

Omezení nerovnosti lze převést na omezení rovnosti přidáním ke každému z nich oslabení proměnné

Vytvořme Lagrangeovu funkci:

Pak mají nezbytné minimální podmínky podobu:

Druhou rovnici lze transformovat vyřazením zeslabujících proměnných a přechodem na omezení nerovnosti. Pojďme získat omezení původního problému. Třetí rovnici lze vynásobit ui/2 a nahraďte zeslabující proměnné jejich vyjádřením z druhé rovnice soustavy.

Je tu ještě jedna podmínka, která musí být splněna v minimálním bodě. Tato podmínka: λ i= 0, což je důsledek analýzy fyzikálního významu koeficientů Lagrangeovy funkce.

Dá se to ukázat

Lagrangeův koeficient v minimálním bodě;

F* - optimální hodnotu funkcí.

Je zřejmé, že jak se b zvyšuje i přípustná oblast se rozšiřuje, což znamená, že minimální hodnota může pouze klesat, to znamená, že derivace musí být záporná (nekladná). Tedy na podmíněném minimálním bodu

Nakonec získáme potřebné podmínky pro podmínku minimální:

Výrazy na druhém řádku zajišťují, že optimální bod je platný.

Třetí řádek obsahuje následující informace: Pokud je omezení aktivní (tj. výraz v závorkách je roven nule), pak je odpovídající Lagrangeův koeficient striktně kladný. Kladnost Lagrangeova koeficientu znamená, že odpovídající omezení je aktivní, tzn. skutečnost, že toto omezení je vzácné, je přesně to, co zastaví další zlepšení cílová funkce. Pokud omezení není aktivní (tj. výraz v závorce není roven nule), pak musí být odpovídající Lagrangeův koeficient roven nule, tzn. Toto omezení není nedostatečné, neovlivňuje další zlepšování cílové funkce.

Pro podmíněný maximální bod mění Lagrangeovy koeficienty znaménko na opačné (protože optimální hodnota účelové funkce v podmíněném maximálním bodu by se měla zvýšit).

Výše uvedené podmínky jsou ekvivalentní Kuhn-Tuckerův teorém a jsou často nazývány stejně.

Dostatečný stav neboť minimum (maximum) je konvexnost (konkávnost) účelové funkce ve stacionárním bodě. To znamená, že hesián musí být kladně (záporně) určitý.

Shrnutí materiálu v této kapitole lze zobrazit ve dvou prezentacích:

soubor „Nelineární programování“;

soubor "Kuhn-Tuckerův teorém".

Snímky 10-14 prezentace „Kuhn-Tuckerův teorém“ ukazují příklad řešení Kuhn-Tuckerova problému.

4.5. Kontrolní otázky

(Vyvinuto Afanasyevem M.Yu. a Suvorovem B.P.)

Otázka 1. Vzhledem k reálné funkci F(X S= . Nechat X 1 a X 2 - bodů tohoto segmentu a 0 £ l £ 1.

Která z následujících nerovnic je podmínkou konvexnosti funkce?

Možné odpovědi:

Otázka 2. Vzhledem k reálné funkci F(X), definovaný na segmentu reálná čísla S=. Nechat X 1 a X 2 jsou body tohoto segmentu a 0 £ l £ 1.

Která z následujících nerovností je podmínkou pro to, aby funkce byla přísně konkávní?

Možné odpovědi:

Otázka 3. Funkce

1) konvexní;

2) přísně konvexní;

3) konkávní;

4) přísně konkávní;

5) konvexní a konkávní.

Otázka 4. Funkce

3) konkávní; 4) přísně konkávní;

5) konvexní a konkávní.

Otázka 5. Funkce

1) konvexní; 2) ani konvexní, ani konkávní;

3) přísně konvexní; 4) konkávní:

5) konvexní a konkávní.

Otázka 6. Nový model vysokorychlostní motocykl „Snail“ prodává společnost za cenu (30 – 2 X) tisíc dolarů za kus, kde X- počet prodaných motocyklů. Variabilní výrobní náklady jsou 6 000 USD na jednotku a fixní náklady jsou 30 000 USD Maximalizujte zisk svého podniku za týden.

Řekněme, že změna sazby daně z obratu vedla k dodatečným 4 000 USD na dani z prodeje za každý prodaný motocykl.

Jak se změní optimální výroba motocyklů oproti výchozí situaci?

(Vyřešte pomocí funkce Lagrange.)

Možné odpovědi:

1) se zvýší o 2 ; 2) se sníží o 2 ;

3) nezmění se; 4) se zvýší o 1 ;

5) se sníží o 1 .

Otázka 7. Předpokládejme, že máte 2 týdny (14 dní) dovolené strávit na Kanárských ostrovech a v Nice. Nechť má vaše užitečná funkce tvar 2 KN – 3K 2 – 4N 2, Kde NA A N- počet dní, které strávíte na Kanárských ostrovech a v Nice.

Kolik dní byste měli strávit v Nice, abyste maximalizovali své užitečné funkce?

(K řešení použijte Lagrangeovu funkci. Zaokrouhlete výsledek na nejbližší celé číslo. Zkontrolujte, zda jsou splněny podmínky Kuhn-Tuckerovy optimality.)

Možné odpovědi:

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

Otázka 8. Pro problém v otázce 7 najděte hodnotu duálního odhadu omezení.

(Zaokrouhlete výsledek na nejbližší celé číslo.)

Možné odpovědi:

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

Otázka 9. Monopolista plánuje výrobní a prodejní program na další období. Ceny: R 1 = 14 – 0,25X 1 (na produkt 1); R 2 = 14 – 0,5X 2 (na produkt 2), kde X 1 a X 2 - objemy prodeje výrobků. Předpokládejme, že všechny vyrobené produkty jsou prodány. Maximální celkový objem prodeje je 57.

Jaké je optimální vydání produktu 2?

Možné odpovědi:

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

Otázka 10. Majitel malého podniku má na příští měsíc 100 tisíc rublů, které může utratit za zvýšení stálých aktiv NA(nákup vybavení) za cenu 1 000 rublů za jednotku nebo za nákup dalšího pracovní síla L za cenu 50 rub./hod. Zvýšení hotových výrobků, které lze prodat za 10 tisíc rublů. na jednotku, určené produkční funkcí F(K, L) = L 2/7 K 2/5.

Kolik peněz by mělo být vynaloženo na zvýšení stálých aktiv?

Možné odpovědi:

1) 74,36 tis třít.; 2) 58,33 tisíc rublů; 3) 63,44 tisíc rublů;

4) 45,66 tisíc rublů; 5) 39,77 tisíc rublů.

Odpovědi na otázky:

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

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