Formularea și demonstrarea teoremei Kuhn-Tucker. Conceptul de punct de șa. Teorema Kuhn-Tucker

Teorema Kuhn-Tucker este o generalizare a metodelor de rezolvare a problemelor de optimizare în două direcții:

Programare liniară pentru cazul neliniar, care prin analogie a primit numele nu foarte reușit „nu programare liniară»;

Constrângeri de egalitate neliniară asupra constrângerilor de inegalitate.

Metoda și condițiile Karush-Kuhn-Tucker ( Condiții Karush-Kuhn-Tucker, KKT) sunt condiții formal necesare pentru optimitatea unei probleme de programare neliniară. In afara de asta, conditiile necesare includ așa-numitele condiții de regularitate pentru punctele staționare - nedegenerarea setului de gradienți de constrângere. Metoda este o generalizare a metodei multiplicatorului Lagrange în cazul constrângerilor de inegalitate.

Kuhn și Tucker au generalizat metoda multiplicatorului Lagrange (pentru utilizarea în construirea criteriilor de optimitate pentru problemele cu constrângeri de egalitate) la cazul unei probleme generale de programare neliniară cu atât constrângeri de egalități, cât și de inegalități.

Metoda principală în programarea neliniară rămâne încă utilizarea funcției Lagrange obținută prin transferarea restricțiilor la funcția obiectiv. Din acest principiu derivă și condițiile Kuhn-Tucker.

William Karush în a lui munca de diplomaîn 1931 a găsit condiţiile necesare în caz general restricţii ale egalităţilor şi inegalităţilor. În mod independent, Harold Kuhn și Albert Tucker au ajuns la aceleași concluzii mai târziu în 1941. Rezultatele lor au fost mai generale.

Dacă, sub restricțiile impuse, este o soluție la problemă, atunci există un vector de multiplicatori Lagrange astfel încât pentru funcția Lagrange sunt indeplinite conditiile:

- staționaritate: ;

- moliciune complementară: ;

- non-negativitatea:.

Condițiile necesare enumerate pentru minimul unei funcții nu sunt suficiente în cazul general. Există mai multe opțiuni conditii suplimentare, care le fac suficiente:

- stare simplă – 1) punctul este staționar, 2) condiția de non-rigiditate complementară este îndeplinită, 3) multiplicatori Lagrange;

- Starea lui Slater (mai slab) – 1) punctul este staționar, 2) condiția de non-rigiditate complementară este îndeplinită, 3) .

Să trecem direct la demonstrarea teoremei Kuhn-Tucker.

Dacă o funcție continuă de n variabile x = (x1,...,xn) F(x) are în punctul X opt maxim, atunci există ε > 0 astfel încât pentru toate X din vecinătatea ε a punctului X angro

F(x)≤F(x opt)

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

Să alegem două tipuri de increment x j de-a lungul j coordonatele

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

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

Trecând în aceste relații la limita la Δ x j→0, obținem:

Din aceste relaţii rezultă că

(3.6.1)

O relație similară poate fi obținută pentru cazul unei funcții minime. Astfel, necesitatea condițiilor (3.6.1) pentru a se realiza la punctul x en-gros functia maxima sau minima f(x), adică dacă există o extremă, atunci condițiile (3.6.1) sunt îndeplinite. Dar egalitatea la zero a tuturor derivatelor la punctul x en-gros nu asigură încă existența unui extremum în el, adică condițiile (3.6.1) nu sunt suficiente. Din punct de vedere geometric, aceasta înseamnă că în cazul unei derivate zero a unei funcții a unei variabile poate exista un punct de inflexiune, și nu un maxim (sau un minim), iar în cazul unei funcții a două variabile, un punct de șa și nu un extremum etc. Prin urmare, punctele x en-gros, în care relațiile (3.6.1) sunt satisfăcute se numesc staționari.

Rețineți că condiția (3.6.1) a fost obținută datorită capacității de a atribui o variabilă X incremente de două semne, care este locul în care cele două inegalități au apărut la și la . Dacă intervalul valid X limitat la valori nenegative X≥0, apoi în interiorul regiunii în care X> 0, condiția (3.6.1) rămâne valabilă, deoarece acolo sunt permise creșteri ale ambelor semne. La hotarul regiunii X≥ 0, unde X= 0, numai incrementul pozitiv Δ este permis X>0, putem vorbi doar despre o derivată unilaterală, iar din (3.6.1) urmează următoarea condiție necesară pentru un maxim:

În consecință, condiția necesară pentru un minim la limita regiunii x j= 0 se va scrie ca

b) Problemă extremum condiționată

La determinarea extremul condiționat funcții atunci când trebuie să determinați maximul (sau minimul) unei funcții F(x) in conditii limitative:

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

f(x)=max;

g i (x)=b i ;

Se folosește și metoda multiplicatorilor Lagrange care, ca și în cazul calculului clasic al variațiilor, constă în introducerea funcției Lagrange.

(3.6.2)

unde λ i sunt multiplicatorii Lagrange nedeterminați.

Presupunând că funcția este un caz special al funcționalului, obținem că condițiile necesare pentru extremum se găsesc prin diferențierea directă a relației (3.6.2) și se scriu sub forma

Dacă introducem vectori

relaţiile (17-8) şi (17-9) vor fi rescrise ca

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

unde egalitatea vectorilor cu zero este înțeleasă componente.

Figura 3.6.1 - Explicația problemei extremumului condiționat

Când n= 2 și m= 1, problema geometrică a găsirii unui extremum condiționat se reduce (Fig. 17-6) la găsirea punctului de tangență A al curbei φ = b la una dintre curbele de nivel constant f= const.

Teorema 7.2. Pentru o problemă de programare convexă (7.4)–(7.6), a cărei mulțime de soluții fezabile are proprietatea de regularitate, un plan este un plan optim dacă și numai dacă există un vector astfel încât
– punctul de șa al funcției Lagrange.

Presupunând că funcţia obiectiv
si functii sunt continue și diferențiabile, atunci teorema Kuhn-Tucker poate fi completată cu expresii analitice care determină condiția necesară și suficientă pentru punctul
a fost punctul de șa al funcției Lagrange, i.e. a fost o soluție la problema de programare convexă. Aceste expresii au următoarea formă:

Unde Și sunt valorile derivatelor parțiale corespunzătoare ale funcției Lagrange calculate la punctul de șa.

Teorema Kuhn-Tucker ocupă un loc central în teoria programării neliniare. Este valabil și pentru așa-numitele probleme de programare pătratică, adică. unde este functia obiectiv
cu restrictii:

În cazul general al rezolvării problemelor de programare neliniară pentru a determina extremul global al problemei, nu există o metodă de calcul eficientă dacă nu se știe că orice extremă locală este de asemenea globală. Astfel, într-o problemă de programare convexă și pătratică, mulțimea soluțiilor fezabile este convexă, atunci dacă funcția obiectiv este concavă, orice maxim local este și el global.

Exemplul 7.3. Folosind teorema Kuhn-Tucker găsim
sub restricții

Rezolvăm grafic (Fig. 7.2) și găsim:
;
;
(vezi soluția de mai jos pentru mai multe detalii). Să arătăm că există un vector Y 0 0, la care condițiile Kuhn-Tucker sunt îndeplinite în punctul optim. Să compunem funcția Lagrange:

Soluţie
găsim din sistem:
. Din a doua ecuație
înlocuiți în prima ecuație a sistemului. Diferențierea prin :
. În expresii Și înlocuiți valorile
Și
. Avem valori ale derivatelor parțiale mai mari decât zero și, conform condiției, acestea trebuie să fie egale cu zero, atunci =0 Și =0. Pe de alta parte, poate să nu accepte valori zero, deoarece
de aici
; Toate
acestea. condițiile Kuhn-Tucker sunt îndeplinite, prin urmare, acest punct este un punct extremum.

Fig.7.2. Rezolvare grafică a problemei neliniare

exemplu de programare 7.3

Condiție necesară pentru optimitate pentru o problemă de programare neliniară poate fi formulată după cum urmează. Lăsa
este soluția optimă pentru problema (7.4)–(7.6) și funcțiile
,
,
diferențiabilă în acest moment. Dacă
este un punct nesingular al mulțimii admisibile a problemei (7.4)–(7.6), atunci este un punct Kuhn-Tucker al acestei probleme.

Astfel, dacă un set admisibil
problema (7.4)-(7.6) nu are puncte singulare, iar funcțiile F(M),g i (M), (
) diferențiabilă în toate punctele
, atunci soluția optimă la această problemă ar trebui căutată printre punctele Kuhn-Tucker.

După cum se știe din analiza matematică, punct special multimi de solutii admisibile la un sistem de ecuatii liniare si inegalitati de forma

adică seturi de soluții fezabile

dacă la punct
gradienții acelor funcții sunt liniar dependenți
, care în ea se transformă în . De exemplu,
– punctul singular al multimii

Într-adevăr,

Astfel, este un sistem dependent liniar.

Funcția gradient
este un vector ale cărui coordonate sunt, respectiv, egale cu valorile derivatelor parțiale ale funcției
la punct M 0 . Acest vector arată direcția celei mai rapide creșteri a funcției.

Condiția de optimitate necesară este de puțin folos pentru rezolvarea majorității problemelor de programare neliniară, deoarece Numai în cazuri rare este posibil să găsiți toate punctele Kuhn-Tucker ale unei probleme de programare neliniară.

Condiție suficientă pentru optimitate pentru o problemă de programare neliniară: dacă
este punctul de șa al funcției Lagrange pentru problema (7.4)–(7.6), atunci
este soluția optimă la această problemă.

Această condiție nu este necesară în cazul general: funcția Lagrange poate să nu aibă puncte de șa, în timp ce, în același timp, problema de programare neliniară originală are o soluție optimă.

Sunt cunoscute diferite metode care permit să se găsească aproximativ soluția optimă pentru o problemă de programare neliniară. Cu toate acestea, aceste metode oferă o aproximare destul de bună doar pentru problema de programare convexă, unde fiecare extremă locală este de asemenea globală. În general, sub gradient metodele înțeleg metode în care mișcarea către punctul optim al unei funcții coincide cu direcția gradientului acestei funcții, i.e. începând de la un punct
se efectuează o tranziție secvențială către alte puncte până când se identifică o soluție acceptabilă problema initiala. În acest caz, metodele de gradient pot fi împărțite în 2 grupuri.

LA primul Acest grup include metode în care punctele studiate nu depășesc gama de soluții fezabile ale problemei. Cea mai comună dintre aceste metode este metoda Frank-Wolf (lupul). Astfel de metode includ metoda gradienții Rosen proiectați, metodă indicații valabile de la Zeutendijk.

Co. al doilea Acest grup include metode în care punctele studiate pot aparține sau nu regiunii soluțiilor fezabile. Totuși, ca urmare a implementării procesului iterativ, se găsește un punct din regiunea soluțiilor fezabile care determină o soluție acceptabilă.

Dintre aceste metode, cea mai folosită metodă este funcții de penalizare sau metoda Arrow-Hurwitz.

Atunci când se găsesc soluții la probleme folosind metode de gradient, inclusiv cele menționate mai sus, procesul iterativ se desfășoară până la acel moment, în timp ce gradientul funcției
la punctul următor
nu va deveni egal cu zero sau până când
, Unde – un număr pozitiv destul de mic care caracterizează acuratețea soluției rezultate.

Rezolvarea problemelor complexe de programare neliniară folosind metode de gradient implică o cantitate mare de calcule și este recomandabilă doar folosind un computer.

Folosind un exemplu, vom arăta semnificația generală a metodelor de gradient pentru rezolvarea problemelor de programare neliniară.

Să fie o funcție a două variabile
. Fie valorile inițiale ale variabilelor
, și valoarea funcției
. Dacă
nu este un extremum, atunci se determină astfel de valori noi ale variabilelor
Și
astfel încât următoarea valoare a funcției
s-a dovedit a fi mai aproape de optim decât precedentul.

Cum se determină mărimea incrementelor? Și ? Pentru a face acest lucru, la puncte Și Direcția de schimbare a funcției spre extremum este determinată folosind gradientul. Cum mai multă valoare derivată parțială, cu atât funcția se schimbă mai rapid spre extremum. Prin urmare, creșterile Și sunt alese proporțional cu valoarea derivatelor parțiale Și la puncte
Și
. Prin urmare,
Și
, Unde – o valoare numită pas, care stabilește scara schimbării Și .

Exemplul 7.4.

Să fie necesar să maximizăm funcția

(maxim la punctul (3;2))

La punctul
,
la
avem

;
,

Să mai facem o iterație. La punctul
,
la
avem

;
,

Fig.7.3. Interpretarea geometrică a două etape

metoda gradientului de exemplu 7.4

În fig. 7.3 prezintă mișcarea de-a lungul gradientului, care a fost efectuată în în acest exemplu. Atitudine indică direcția de schimbare a funcției spre maxim. Dacă luăm gradientul cu semnul minus, atunci ne vom îndrepta spre minim.

O problemă specifică cu metodele de gradient este alegerea mărimii pasului t. Dacă facem pași mici, vom căuta optimul pentru o perioadă foarte lungă de timp. Dacă alegeți valoarea sa prea mare, atunci optimul poate fi „depășit”. Problema intermediară a alegerii mărimii optime a pasului este rezolvată prin metode adecvate. Dacă pas t este determinată aproximativ, apoi, de regulă, nu se încadrează în optim, ci în zona sa. Metodele de gradient asigură determinarea optimilor locali. Când căutați un optim global folosind un gradient, există adesea îndoieli că optimul găsit este global. Acesta este dezavantajul acestei metode atunci când se rezolvă probleme de programare neconvexe.

Întrebări de autotest

Enunțul problemei de programare neliniară.

Procesul de găsire a unei soluții la o problemă de programare neliniară folosind interpretarea geometrică a acesteia.

Algoritmul metodei Lagrange pentru rezolvarea unei probleme de programare neliniară.

Aplicarea metodei Lagrange la rezolvarea unei probleme de programare neliniară în cazul în care condițiile de conexiune sunt inegalități.

Definiții și teoreme auxiliare necesare pentru a considera teorema centrală a programării neliniare - teorema Kuhn-Tucker.

Teorema Kuhn-Tucker.

Condiție de optimitate necesară și suficientă pentru o problemă de programare neliniară.

Sensul general al metodelor de gradient pentru rezolvarea aproximativă a problemelor de programare neliniară.

Grupuri de metode de gradient pentru rezolvarea aproximativă a problemelor de programare neliniară.

Să scriem funcția Lagrange: (4)
unde λ i , i=1..m – multiplicatori Lagrange nedeterminați; z(X) și q i (X) sunt funcții convexe în sus.

Teorema Kuhn-Tucker. Pentru ca planul X 0 să fie o soluție la problema (1) – (4), este necesar și suficient să existe un vector λ 0 ≥ 0 astfel încât perechea (X 0 ,λ 0) pentru toate X ≥ 0 și λ ≥ 0.
L(X, λ 0) ≤ L(X 0 ,λ 0) ≤ L(X 0 ,λ)

Scopul serviciului. Un calculator online este folosit pentru a găsi extremul unei funcții prin multiplicatorii Lagrange în modul online cu verificarea soluției în MS Excel. În acest caz, sunt rezolvate următoarele sarcini:

funcția Lagrange L(X) este compilată sub forma unei combinații liniare a funcției F(X) și constrângeri g i (x);
se găsesc derivatele parțiale ale funcției Lagrange, ∂L/∂x i , ∂L/∂λ i ;
este compilat un sistem de ecuații (n+m), ∂L/∂x i = 0.
se determină variabilele x i şi multiplicatorii Lagrange α i.

Pentru ca funcția a două variabile vectoriale (4) să aibă un punct de șa, este necesar și suficient să se îndeplinească următoarele: Condițiile Kuhn-Tucker:
(5)
(6)
(7)
(8)

Dacă problema este rezolvată minimizarea, atunci există un punct de șa (X 0 , Y 0) dacă relațiile sunt satisfăcute
L(X, λ 0) ≤ L(X 0, Y 0) ≤ L(X 0, Y)
Condițiile Kuhn-Tucker pentru existență punct de șa funcțiile Lagrange vor schimba semnul în (5) și (7) la opus.

Exemplu. Verificați îndeplinirea condițiilor Kuhn-Tucker. Găsiți punctul optim al unei probleme de programare liniară cu constrângeri:
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

Soluţie:
Funcția Lagrange: 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))
O condiție necesară pentru extremul funcției Lagrange este egalitatea la zero a derivatelor sale parțiale în raport cu variabilele x i și factori nedeterminați λ.
Să verificăm îndeplinirea condițiilor Kuhn-Tucker. Să calculăm matricele derivatelor secunde funcție obiectivăși funcții de constrângere.

Matricea hessiană H f este semidefinită pozitivă pentru toate valorile lui x, prin urmare f(x) este o funcție convexă.
Constrângere g 1 (x) – funcție liniară, care este atât convex, cât și concav.
Matricea hessiană pentru funcția g 2 (x) are forma:

Δ 1 = -2, Δ 2 = 4.
Deoarece matricea H g 2 este definită negativ, g 2 (x) este concavă.
Funcția h 1 (x) este inclusă în constrângerea liniară sub formă de egalitate. Prin urmare, condițiile (a), (b) și (c) ale teoremei 1 sunt îndeplinite. Să găsim acum punctul optim x *.
Avem:

Ecuația ia următoarea formă:

Pentru j=1 și, respectiv, j=2, se pot obține următoarele expresii:
j=1, 2x 1 -μ 1 + 2x 2 μ 2 + λ 1 = 0
j=2, -1 + 2x 2 μ 2 + λ 1 = 0
Astfel, condițiile Kuhn-Tucker pentru exemplul nostru sunt următoarele:
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

Din a treia ecuație găsim: x 1 = 6-x 2. Înlocuind valoarea x 1 în ecuațiile rămase, obținem:
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
Să substituim x 2 = 5 în prima și a doua ecuație:

Din a doua ecuație exprimăm λ și îl înlocuim în prima ecuație:
3 - μ 1 - 8μ 2 = 0
Fie μ 1 = 0,1 ≥ 0, apoi μ 2 = 2,2 ≥ 0. Astfel, punctul x * = este punctul minim.

Locul central în teoria programării neliniare este ocupat de teorema Kuhn-Tucker. Să fie dată o problemă de programare neliniară:

găsiți valoarea maximă a unei funcții Z=f(x 1, x 2, ..., x n) cu restricții

Să compunem funcția Lagrange pentru această problemă:

(4.2)

Dacă condiția de regularitate este îndeplinită (există cel puțin un punct X, pentru care g i(X)>0 pentru toată lumea i), atunci este valabilă următoarea teoremă.

Teorema. Vector X(0) dacă și numai dacă este soluție optimă problema (4.1), când există un vector Λ (0) astfel încât pt pentru toți

Punct ( X(0),Λ (0)) se numește şa punct pentru funcție F(X,Λ), iar teorema se numește teorema punctului șei. Să demonstrăm suficiența condițiilor (4.3).

Dovada. Lăsa X(0) >0 și Λ (0) >0 - punctul de șa al funcției F(X,Λ). Dacă în (4.3) în schimb F(X,Λ) înlocuiți valoarea lui (4.2), obținem

la .

Prin urmare, inegalitatea corectă este valabilă pentru orice

Apoi din stânga inegalitatea obținem

Întrucât în acest caz

Acea f(X(0))>f(X).

Deci ideea X(0) satisface (4.1) și în toate celelalte puncte care satisfac (4.1), funcția ia o valoare mai mică decât la X(0).

Această afirmație conduce la rezolvarea problemei NLP la găsirea punctelor de șa ale funcției Lagrange F(X,Λ).

Dovada necesității condițiilor (4.3) nu este luată în considerare din cauza complexității sale.

Dacă f(X) Și g i(X)-funcții diferențiabile, atunci condițiile (4.3) sunt echivalente cu următoarele condiții locale Kuhn-Tucker:

Expresie

înseamnă că valoarea derivatei parțiale a funcției Lagrange este luată în punctul ( X(0), Λ (0)), unde

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

Aceste condiții pot fi scrise sub formă vectorială:

Exemplu. Găsiți max Z=-X 1 2 -X 2 2 cu restricții

Să arătăm că există Λ (0) 0 pentru care condițiile Kuhn-Tucker (4.4), (4.5) pentru funcție sunt îndeplinite în punctul optim F(X,Λ):

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

Conform condițiilor (4.5), λ 2 și λ 3 trebuie să ia valori zero, deoarece, substituind X 1 =0,8 și X 2 = 0,4 în expresie

avem valori mai mari decât zero și după condiție

Conform condiției, λ 1 poate lua o valoare diferită de zero, deoarece

În conformitate cu (2.16), derivata

trebuie să ia valori zero, deoarece coordonatele vectorului X(0) sunt diferite de zero. Găsim λ 1 =0,8. Prin urmare, în punctul ( X(0),Λ (0)) condițiile Kuhn-Tucker sunt îndeplinite și este într-adevăr un punct extremum.

Să luăm în considerare condițiile Kuhn-Tucker într-o formă ușor diferită.

Să avem o problemă de optimizare cu constrângeri sub formă de egalități:

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

in conditii:

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.

Punctul minim condiționat al funcției f coincide cu punctul de șa al funcției Lagrange:

În acest caz, punctul de șa trebuie să ofere un minim în variabilele sale x iși maxim peste variabilele λ j.

Condițiile necesare pentru un punct staționar sunt ca derivatele parțiale de ordinul întâi față de toate variabilele să fie egale cu zero:

Rețineți că a doua ecuație implică că numai punctele valide vor îndeplini condițiile necesare.

Pentru a obține o condiție suficientă pentru existența unui minim, este necesar să se adauge cerința ca Hessianul funcției obiectiv să fie pozitiv definit.

Sa luam in considerare general problema de programare matematica:

Z= f(X) → min,

in conditii:

Constrângerile de inegalitate pot fi convertite în constrângeri de egalitate adăugând la fiecare dintre ele slăbire variabile

Să formăm funcția Lagrange:

Atunci condițiile minime necesare iau forma:

A doua ecuație poate fi transformată prin eliminarea variabilelor de atenuare și trecerea la constrângeri de inegalitate. Să obținem constrângerile problemei inițiale. A treia ecuație poate fi înmulțită cu ui/2 și înlocuiți variabilele de slăbire exprimându-le din a doua ecuație a sistemului.

Mai este o condiție care trebuie îndeplinită la punctul minim. Această condiție: λ i= 0, care este o consecință a analizei sens fizic coeficienții funcției Lagrange.

Se poate arăta că

coeficientul Lagrange la punctul minim;

f* - valoare optimă funcții.

Evident, pe măsură ce b crește i regiunea admisibilă se extinde, ceea ce înseamnă că valoarea minima poate doar să scadă, adică derivata trebuie să fie negativă (nepozitivă). Prin urmare, în punctul de minim condiționat

Obținem în sfârșit condițiile necesare pentru condițional minim:

Expresiile din a doua linie asigură că punctul optim este valabil.

A treia linie conține următoarea informație: Dacă constrângerea este activă (adică expresia dintre paranteze este egală cu zero), atunci coeficientul Lagrange corespunzător este strict pozitiv. Pozitivitatea coeficientului Lagrange înseamnă că constrângerea corespunzătoare este activă, i.e. Faptul că această limitare este deficitară este ceea ce oprește îmbunătățirea ulterioară a funcției țintă. Dacă constrângerea nu este activă (adică expresia dintre paranteze nu este egală cu zero), atunci coeficientul Lagrange corespunzător ar trebui să fie egal cu zero, adică Această limitare nu este deficitară; nu afectează îmbunătățirea ulterioară a funcției țintă.

Pentru punctul maxim condiționat, coeficienții Lagrange schimbă semnul în sens opus (deoarece valoarea optimă a funcției obiectiv la punctul maxim condiționat ar trebui să crească).

Condițiile de mai sus sunt echivalente Teorema Kuhn-Tuckerși sunt adesea numite la fel.

Stare suficientă căci minimul (maximul) este convexitatea (concavitatea) funcției obiectiv într-un punct staționar. Aceasta înseamnă că Hessianul trebuie să fie pozitiv (negativ) definit.

Un rezumat al materialului din acest capitol poate fi vizualizat în două prezentări:

fișier „Programare neliniară”;

fișierul „Teorema Kuhn-Tucker”.

Slide-urile 10-14 ale prezentării „Teorema Kuhn-Tucker” prezintă un exemplu de rezolvare a problemei Kuhn-Tucker.

4.5. Întrebări de control

(Dezvoltat de Afanasyev M.Yu. și Suvorov B.P.)

Intrebarea 1. Dată o funcție reală f(X S= . Lăsa X 1 și X 2 - puncte ale acestui segment și 0 £ l £ 1.

Care dintre următoarele inegalități este o condiție pentru convexitatea unei funcții?

Raspunsuri posibile:

Intrebarea 2. Dată o funcție reală f(X), definite pe segment numere reale S=. Lăsa X 1 și X 2 sunt punctele acestui segment și 0 £ l £ 1.

Care dintre următoarele inegalități este o condiție pentru ca o funcție să fie strict concavitată?

Raspunsuri posibile:

Întrebarea 3. Funcţie

1) convex;

2) strict convex;

3) concav;

4) strict concav;

5) convex și concav.

Întrebarea 4. Funcţie

3) concav; 4) strict concav;

5) convex și concav.

Întrebarea 5. Funcţie

1) convex; 2) nici convex, nici concav;

3) strict convex; 4) concav:

5) convex și concav.

Întrebarea 6. Model nou motocicleta de mare viteză „Snail” este vândută de companie la prețul de (30 – 2 X) mii de dolari pe bucată, unde X- numărul de motociclete vândute. Costurile variabile de producție sunt de 6.000 USD pe unitate, iar costurile fixe sunt de 30.000 USD. Maximizați profitul companiei dvs. pentru săptămână.

Să presupunem că modificarea cotei impozitului pe vânzări a dus la o taxă suplimentară de 4.000 USD pentru fiecare motocicletă vândută.

Cum se va schimba producția optimă de motociclete față de situația inițială?

(Rezolvați folosind funcția Lagrange.)

Raspunsuri posibile:

1) va crește cu 2 ; 2) va scădea cu 2 ;

3) nu se va schimba; 4) va crește cu 1 ;

5) va scădea cu 1 .

Întrebarea 7. Să presupunem că aveți 2 săptămâni (14 zile) de vacanță de petrecut în Insulele Canare și Nisa. Fie ca funcția ta de utilitate să fie de forma 2 KN – 3K 2 – 4N 2, Unde LAȘi N- numărul de zile pe care le petreci în Insulele Canare și, respectiv, în Nisa.

Câte zile ar trebui să petreceți în Nisa pentru a vă maximiza funcția de utilitate?

(Pentru a rezolva, utilizați funcția Lagrange. Rotunjiți rezultatul la cel mai apropiat număr întreg. Verificați dacă sunt îndeplinite condițiile de optimitate Kuhn-Tucker.)

Raspunsuri posibile:

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

Întrebarea 8. Pentru problema de la întrebarea 7, găsiți valoarea estimării duale a constrângerii.

(Rotunjiți rezultatul la cel mai apropiat număr întreg.)

Raspunsuri posibile:

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

Întrebarea 9. Monopolistul plănuiește un program de producție și vânzări pentru perioada următoare. Preturi: R 1 = 14 – 0,25X 1 (pe produs 1); R 2 = 14 – 0,5X 2 (pe produs 2), unde X 1 și X 2 - volumele vânzărilor de produse. Să presupunem că toate produsele produse sunt vândute. Volumul total maxim de vânzări este de 57.

Care este lansarea optimă a produsului 2?

Raspunsuri posibile:

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

Întrebarea 10. Proprietarul unei întreprinderi mici are 100 de mii de ruble pentru luna următoare, pe care le poate cheltui pentru creșterea activelor fixe LA(achiziționarea de echipamente) la un preț de 1 mie de ruble pe unitate sau pentru achiziționarea de forță de muncă suplimentară L la un pret de 50 rub./ora. Creșterea produselor finite care pot fi vândute cu 10 mii de ruble. pe unitate, determinată de funcția de producție F(K, L)= L 2/7 K 2/5.

Câți bani ar trebui cheltuiți pentru creșterea activelor fixe?

Raspunsuri posibile:

1) 74,36 mii freca.; 2) 58,33 mii de ruble; 3) 63,44 mii de ruble;

4) 45,66 mii de ruble; 5) 39,77 mii de ruble.

Răspunsuri la întrebări:

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

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