PROGRAMARE CONVEXĂ, o secțiune de programare matematică care studiază problema maximizării funcției obiectiv concave f(x) a argumentului vectorial x = (x 1, ..., x n), satisfăcând constrângerile g i (x) ≥ 0, x Є X, i = 1, ..., m, unde g i sunt funcții concave, X este o mulțime convexă. Un punct x care satisface aceste restricții se numește admisibil. Principalul rezultat al teoriei programării convexe este teorema punctului de șa: pentru ca punctul admisibil x* al unei probleme de programare convexă să fie optim, este necesar (în condiții destul de largi) și suficient pentru existența vectorului y * = (y* 1, ..., y m *) cu componente nenegative y* astfel încât punctul (x*, y*) este un punct de șa pentru funcția Lagrange
probleme de programare convexe, adică pentru orice x Є X și y cu componente nenegative, inegalitățile sunt satisfăcute
Un număr de metode de programare convexă se bazează pe teorema punctului de șa, în care funcția φ(y 1 , ..., y m) = max x Є X L(x, y) este minimizată pentru y i ≥ 0, i = 1, . ., m, sau punctul de șa se găsește direct și, în loc de funcția Lagrange, sunt folosite uneori unele dintre modificările acesteia. O altă abordare a rezolvării problemei de programare convexă este asociată cu căutarea posibilelor direcții de mișcare ale unui punct admisibil x, care nu derivă din mulțimea punctelor admisibile și la deplasarea de-a lungul cărora funcția obiectiv crește. Această abordare este implementată printr-o succesiune de iterații. La fiecare iterație se calculează direcția posibilă care emană din următorul punct, după care se face o deplasare în această direcție cu o anumită distanță până la următorul punct. Există metode de rezolvare a problemelor de programare convexă care sunt special adaptate cazului în care funcția obiectiv este neliniară și constrângerile sunt liniare. De obicei, metodele de programare convexe necesită un număr infinit de iterații pentru a determina cu precizie punctul optim. Excepție fac problemele de programare pătratică (funcția obiectiv este suma unei funcții patratice și liniare concave, constrângerile sunt liniare) și programarea liniară (funcția obiectiv și constrângerile sunt liniare), pentru care se folosesc în principal metode finite. Multe metode de programare convexă computațională sunt implementate ca programe de calculator; Există, de asemenea, pachete software care acoperă probleme de programare liniară și de programare convexă. Vezi și Cercetare operațională.
Lit.: Golshtein E. G. Programare convexă. Elemente de teorie. M., 1970; Zangwill U. I. Programare neliniară. Abordare unificată. M., 1973.
Considerarea acestei clase de probleme începe de obicei cu o afirmație Metoda lui Lagrange a multiplicatorilor nedeterminați. Pentru a face acest lucru, să presupunem că/(x b..., X")și g(x b..., X")- funcții continue împreună cu derivatele lor parțiale, să eliminăm deocamdată condițiile de nenegativitate a variabilelor și să formulăm următoarea problemă pentru un extremum condiționat:
Pentru a-i găsi soluția, vă prezentăm Multiplicatori de Lagrange / = 1, Tși creați așa-numitul Funcția Lagrange:
să găsim și să echivalăm cu zero derivatele sale parțiale în raport cu toate variabilele
după ce a primit sistemul p + t ecuații pentru necunoscute x b x p,
Ui-, Sus-
Dacă funcţia f(x h ..., X") la punct 
are un extremum, atunci există un astfel de vector Y (0> = (y, 0 ,..., y°) că punctul (A r(0) , F (0)) este o soluție a sistemului (2.23). În consecință, rezolvând sistemul (2.23), obținem puncte în care funcția (2.20) poate avea un extrem. În continuare, punctele găsite sunt examinate în același mod ca atunci când se rezolvă problema unui extremum necondiționat.
Astfel, metoda multiplicatorului Lagrange presupune parcurgerea următorilor pași.
- 1. Compuneți funcția Lagrange.
- 2. Găsiți derivate parțiale cu privire la XjȘi y, din funcția Lagrange și echivalează-le cu zero.
- 3. Rezolvarea sistemului (2.23), găsiți puncte la care funcția obiectiv poate avea un extremum.
- 4. Printre punctele care sunt candidate pentru extrem, găsiți cele la care este atins extremul și calculați valorile funcției f(x, ..., X") in aceste puncte.
Metoda prezentată este aplicabilă problemelor de programare convexă, adică. la cele în care funcția obiectiv este convexă (sau concavă) și regiunea soluțiilor fezabile, determinată de constrângeri, este de asemenea convexă.
Definiția 1. Funcţie f(x,..., x n), definită pe o mulțime convexă X, se numește convex dacă pentru orice punct X, X 2 din Hee pentru orice număr X, 0 X 1 inegalitatea este valabilă
Definiția 2. Funcţie/(*, X„), definită pe o mulțime convexă X, se numește concav dacă pentru orice puncte X X, X 2 din Hee pentru orice număr X, 0 X
Definiția 3. Setul de soluții fezabile la o problemă de programare convexă satisface condiția de regularitate dacă există cel puțin un punct Xj, aparţinând regiunii soluţiilor fezabile pentru care g^XJ) =b h i = 1, T.
Teorema 1. Orice extremă locală a unei probleme de programare convexă este globală.
Definiția 4. Funcția Lagrange a unei probleme de programare convexă este funcția
unde y este multiplicatorul Lagrange.
Definiția 5. Punct (X(0) , T(0)) = (x,°,..., X (',y, 0,..., y” ) numit punctul de șa al funcției Lagrange, Dacă
Să prezentăm două scurte teoreme care sunt de natură auxiliară.
Teorema 2. Planul optim X (0) sarcini NP- Acest
unde DA) este o funcție diferențiabilă neliniară care îndeplinește condițiile
unde este gradientul funcției /
în punctul A" (0) .
Dovada.
Să extindem funcția obiectiv într-o serie Taylor în vecinătatea punctului X (())
Unde OH- vector de incremente mici X (0);
I - desemnarea normei (lungimii) vectorului.
Din expresia (2.26) rezultă că dacă orice valoare a coordonatei vectoriale x| 0) > 0, atunci derivata va fi neapărat egală cu zero
, deoarece altfel de-a lungul coordonatei x k Poate sa,
cu valori fixe ale variabilelor rămase, continuați minimizarea funcției obiectiv, scăderea valorii lui x[ 0) dacă derivata este mai mare decât zero, sau creșterea xf dacă derivata este mai mică
zero. Dacă x| 0) = 0, atunci ar trebui să fie 
deoarece
altfel ai putea reduce valoarea f(Xm), crescând cu 4 0) cu suma Dx*, fără a modifica valorile altor variabile. Prin urmare, pentru orice La egalitatea este valabilă:
Teorema este demonstrată.
Să determinăm acum condițiile necesare și suficiente pentru existența unui punct de șa al funcției Lagrange.
Teorema 3. Astfel încât punctul (A 10 *, I 0)) cu coordonate nenegative este un punct de șa al funcției diferențiabile L(X,Y), trebuie îndeplinite următoarele condiții:
Dovada.
1) Necesitate. Fie (X (0), Y" (0)) un punct de șa, adică:
Formula (2.29) este echivalentă cu expresia
Pe baza (2.29) și (2.30), condițiile (2.27) și (2.28) sunt îndeplinite. Necesitatea a fost astfel demonstrată.
- 2) Adecvarea. Să presupunem că sunt îndeplinite condițiile (2.27) și (2.28). Să extindem funcția L(X, Y)într-o serie Taylor în vecinătatea unui punct
Din expansiunea (2.31) și luând în considerare condițiile (2.27) și (2.28) rezultă că
Ultimele două expresii sunt echivalente cu formula (2.29). Teorema este demonstrată.
După teoremele de mai sus, formulăm teorema Kuhn-Tucker, acum practic evidentă.
Teorema 4 (Kuhn - Tucker). Pentru problema de programare convexă (2.20) - (2.21), al cărei mulțime de soluții admisibile are proprietatea de regularitate, punctul X (0) =(xj 0 *,..., x’ 0)), x,- 0> >0, / = 1, P este un plan optim dacă și numai dacă există un astfel de vector T = (y 1 (0),..., yi 0)), V/ 0) > 0, / = 1, T, că punctul (T (0), H 0>) este un punct de șa al funcției Lagrange.
Dacă în problema de programare convexă (2.20) - (2.21) funcția obiectiv și constrângerile sunt diferențiabile continuu, atunci teorema Kuhn-Tucker poate fi completată cu expresii analitice care determină condițiile necesare și suficiente pentru punctul (X (0), Y i(l), ) a fost punctul de șa al funcției Lagrange, i.e. a fost o soluție la problema de programare convexă. Acestea sunt expresiile (2.27) și (2.28). Ele sunt satisfăcute de problema de programare pătratică. Pentru formularea sa finală, prezentăm mai multe definiții și o teoremă.
Definiția 6. Forma pătratică în raport cu variabilele X[, ..., X" se numește funcție numerică a acestor variabile, având forma:
Definiția 7. Forma pătratică F se numeste definit pozitiv/negativ daca F(X) > 0/F(X) 0 pentru toate valorile variabilelor care alcătuiesc vectorul X.
Definiția 8. Forma pătratică F se numeste semidefinit pozitiv/negativ daca F(X") > O / YES") X și, în plus, există un astfel de set de variabile - o componentă a vectorului X", Ce F(X") = 0.
Teorema 5. O formă pătratică este o funcție convexă/concavă dacă este semidefinită pozitivă/negativă.
Definiție 9. Sarcina de a minimiza/maximiza valoarea unei funcții
sub restricții
unde este o formă pătratică semidefinită pozitivă/negativă, numită problema de programare pătratică(ZKP).
Pentru această problemă, funcția Lagrange are forma:
Dacă funcția Lagrange are un punct de șa, atunci condițiile (2.27), (2.28) sunt îndeplinite. Introducând acum variabile suplimentare care transformă inegalitățile în egalități (această tehnică este folosită și la rezolvarea problemelor LP), scriem aceste condiții sub forma:
Pentru a găsi o soluție la ZKP, este necesar să se determine o soluție nenegativă a sistemului de ecuații algebrice liniare (2.32). O astfel de soluție poate fi găsită metoda pe baza artificiala, aplicat pentru a afla valoarea minimă a funcției obiectiv artificiale F = ^Pj, underu sunt variabile artificiale. Metoda, cum-
Se știe că într-un număr finit de pași va găsi planul optim sau va stabili imposibilitatea de rezolvare a problemei.
Deci, procesul de găsire a unei soluții la cererea de cerere include următorii pași.
- 1. Compuneți funcția Lagrange.
- 2. Sub forma expresiilor (2.27), (2.28) notăm condițiile necesare și suficiente pentru existența unui punct de șa al funcției Lagrange.
- 3. Folosind metoda bazei artificiale se stabilește absența unui punct de șa pentru funcția Lagrange sau se găsesc coordonatele acesteia.
- 4. Notați soluția optimă a problemei inițiale și găsiți valoarea funcției obiectiv.
Să luăm în considerare elementul exemplu numeric(Nr. 1) din cartea lui I. L. Akulich „Programarea matematică în exemple și probleme”. Conform planului de producție, întreprinderea trebuie să producă 180 de produse. Ele pot fi fabricate folosind două tehnologii. In productie X de produse folosind metoda 1, costurile au fost xf+4x, frecare și în timpul producției x 2 produsele în al 2-lea mod sunt egale x + 8x 2 frecare. Determinați câte produse ar trebui produse folosind fiecare metodă pentru a minimiza costul comenzii.
Soluţie. Următoarea funcție ar trebui redusă la minimum:
in conditii: 
Funcția Lagrange în acest caz va arăta astfel:
Să calculăm derivatele parțiale ale acestei funcții în raport cu X, x 2, yși setați-le egale cu zero: 
Continuând în prima și a doua ecuație laîn partea dreaptă și echivalând laturile stângi, obținem după abrevieri evidente:
Rezolvând această ecuație împreună cu cea de-a treia ecuație a sistemului, constatăm că 
Acest punct este un candidat pentru extremă.
Folosind derivate parțiale secunde, este ușor să arăți că punctul găsit este minimul condiționat al funcției /
Probleme similare celei luate în considerare sunt prezentate în multe feluri de practica economică. Adevărat, problemele reale conțin, de regulă, un număr mare de variabile și restricții, ceea ce face imposibilă rezolvarea lor fără utilizarea unui computer. Cu toate acestea, eficiența utilizării software-ului standardizat este determinată de cunoașterea cercetătorului asupra esenței transformărilor efectuate de computer. Acest lucru îl ajută să navigheze corect în varietatea de metode, proceduri de calcul și pachete software propuse pentru rezolvarea problemelor de optimizare.
Pentru a consolida subiectul, să luăm în considerare încă unul exemplu numeric(Nr. 2). Găsiți valoarea maximă a unei funcții
in conditii:
Soluţie. Funcția / este concavă deoarece este suma unei funcții liniare f = 2х 2 + 4х ъ care poate fi considerat ca fiind concav și de formă pătratică / 2 = -x -2x1, care este definit negativ. Constrângerile conțin doar constrângeri liniare. Prin urmare, putem folosi teorema Kuhn-Tucker și schema de soluții ZKP.
1. Să compunem funcția Lagrange:
2. Să notăm condițiile necesare și suficiente pentru existența unui punct de șa al funcției L.
3. Să introducem variabile suplimentare nenegative v b V2 în sistemul de inegalități liniare, w, w2, transformarea inegalităţilor în egalităţi. Obținem un sistem de ecuații:
În acest caz, desigur, sunt îndeplinite următoarele condiții:
Este necesar să se găsească o soluție de bază a sistemului de ecuații (2.33) pentru a determina coordonatele punctului șa al funcției Lagrange. În acest scop, vom folosi metoda bazei artificiale. Minimizarea unei funcții obiective artificiale
Unde Zi, Zi- variabile artificiale, in urmatoarele conditii:
Aici soluția de bază fezabilă evidentă arată astfel:
Funcția țintă F Să o exprimăm în termeni de variabile non-bazice:
Pentru a completa raționamentul nostru, observăm că acesta merge la zero atunci când Xj (0) = 1, = 1 și alte variabile au valori zero. Astfel, T (0) = (1, 1) este planul optim pentru problema inițială,
(Document)
n1.doc
Programare convexă. Teorema Kuhn-Tucker. Condițiile Kuhn-Tucker
În condiții
(1.3)
Unde sunt funcțiile 
se presupune că sunt convexe.
Dacă 
și sunt funcții concave, atunci avem o problemă de maximizare 
sub restricții 
Și 
Să compunem funcția Lagrange pentru această problemă:
Un punct se numește punct de șa al funcției (1.4) dacă punctul este punctul minim al funcției 
, iar punctul este punctul maxim al funcției. Cu alte cuvinte, pentru un punct de șa pentru toți 
Și 
relatia tine
(1.5)
Teorema 1 (teorema Kuhn-Tucker). Să existe măcar un punct 
, pentru care 
. Apoi o condiție necesară și suficientă pentru optimitatea vectorului 
, aparținând domeniului soluțiilor fezabile la problema (1.1)-(1.5), este existența unui astfel de vector 
adica pentru toata lumea si 
inegalitățile (1.5) țin
Să acceptăm această teoremă fără dovezi.
Teorema Kuhn-Tucker se mai numește și teorema punctului de șa.
Dacă 
Și 
sunt funcții diferențiabile, atunci inegalitățile din (1.5) sunt echivalente cu următoarele condiții Kuhn-Tucker locale:
Aceste expresii înseamnă că valorile derivatelor sunt luate la punctul 
.
1.2. Programare pătratică. Metoda Barankin-Dorfman.
Un caz special de problemă de programare convexă este o problemă de programare pătratică. Problema principală în programarea pătratică este minimizarea funcției Z, care este suma unei funcții liniare și a unei funcții pătratice:
Sub constrângeri liniare
Se presupune că matricea D este simetrică și definită nenegativă. În acest caz, funcția (2.1) va fi convexă.
Pentru problema (2.1) - (2.3), să compunem condițiile Kuhn-Tucker locale (1.6) - (1.7), care sunt condiții necesare și suficiente pentru optimitatea soluției problemei (2.1) - (2.3).
Funcția Lagrange în acest caz are forma:
Să găsim derivatele parțiale ale acestei funcții:
Să notăm
Ținând cont de aceste notații și relații (2.4) și (2.5), condițiile Kuhn-Tucker (1.6) – (1.7) iau următoarea formă
Egalitățile (2.6) și (2.7) formează un sistem de N=n+m ecuații liniare cu 2N=2(n+m) necunoscute: .
Deci, în conformitate cu teorema Kuhn-Tucker, soluția 
problema (2.1) – (2.3) de programare pătratică este optimă dacă și numai dacă, împreună cu soluția 
exista solutii 
Și 
astfel încât este o soluție a sistemului (2.6) – (2.8) supus egalității (2.9).
Condiția (2.9) pentru problema (2.1) – (2.3) este echivalentă cu îndeplinirea condiției
Există mai multe metode pentru rezolvarea unei probleme de programare pătratică. Să luăm în considerare una dintre ele - metoda Barankin-Dorfman.
Cu această metodă, mai întâi sistemul de ecuații (2.6) – (2.7) se reduce la forma:
Unde 
(variabile de bază) și 
(variabilele libere) sunt elemente diferite ale unor permutări de variabile și toate 
sunt numere nenegative (i=1,2,…,N).
Apoi din sistemul (2.11) se găsește soluția de referință inițială
Sistemele (2.6) – (2.8), și componentele vectoriale 
aranjate in ordine.
Daca pentru rezolvare 
condiția (2.10) este îndeplinită, atunci problema (2.1) – (2.3) este rezolvată și soluția optimă a acesteia este 
se găsește din componentele corespunzătoare ale vectorului .
Dacă condiția (2.10) nu este îndeplinită, atunci următorul tabel este compilat pentru a trece la o altă soluție de referință (Tabelul 2.1). Partea principală a acestui tabel include rânduri pentru toate variabilele, aranjate în ordine. Pentru variabilele de bază, elementele rând sunt preluate din sistemul (2.11), iar pentru variabilele libere - din relații
Parametrii părții suplimentare din tabelul 2.1 sunt următorii:
A) 
se gasesc din formula 
Unde 
- un vector compus din elementele coloanei a S-a a părții principale a tabelului;
B) pentru acele s pentru care 
, se calculează restul parametrilor: 
(elementele coloanelor corespunzătoare care oferă minimum 
, marcat cu un asterisc), 
.
Coloana care corespunde celui mai mic negativ 
, este atribuit ca coloană de rezoluție, rândul cu elementul marcat cu un asterisc în această coloană este un rând de rezolvare, iar acest element în sine este un element de rezolvare, iar cu ajutorul lor se realizează o transformare simplex a tabelului 2.1.
în care:
Ca rezultat, se obține o nouă soluție de referință a sistemului (2.6) – (2.8). Acest proces continuă până când condiția (2.10) este îndeplinită. Dacă totul 
, A 
, apoi se alege o altă soluție ca inițială.
1.3 Un exemplu de rezolvare a unei probleme folosind metoda Barankin-Dorfman
Minimizați funcția
Cu restricții:
; 
.
Soluţie
Găsim soluția inițială suport a sistemului (2.12). În acest caz, valoarea funcției obiectiv este egală cu .
Atunci condiția (2.10) nu este îndeplinită și, prin urmare, soluția nu este optimă.
Să compilam tabelul 2.2 pentru a trece la o nouă soluție de referință a sistemului (2.12) - (2.13). Să completăm partea principală a acestui tabel folosind sistemul (2.12).
A) pentru partea suplimentară a tabelului găsim:
B) pentru pozitiv 
Și 
Să calculăm parametrii rămași:
A patra coloană, care corespunde celui mai mic negativ 
, atribuim o coloană de rezoluție, un rând cu elementul 3 al acestei coloane ca rând de rezoluție și elementul 3 însuși ca element de rezolvare, iar cu ajutorul lor realizăm o transformare simplex a tabelului 2.2.
Ca rezultat, obținem tabelul 2.3 care conține o nouă soluție de referință.
Pentru aceasta solutie
Prin urmare, completăm partea suplimentară a tabelului 2.3 în același mod ca și în cazul precedent, pentru a trece la o nouă soluție de referință a sistemului (2.12) - (2.13).
Supunând tabelul 2.3 unei transformări simplex cu un element de rezoluție de 13.30, obținem un alt tabel cu o soluție de referință pentru care 
.
Astfel, s-a găsit soluția optimă 
, la care funcția obiectiv Z a acestei probleme este minimizată. în care 
1.4 Sarcină individuală: rezolvarea problemei folosind metoda Barankin-Dorfman
;
Soluţie
Din relațiile (2.6) - (2.7) obținem următorul sistem de ecuații:
După transformări simple, aducem acest sistem la forma:
(2.14)
De unde, ținând cont de non-negativitate
Găsirea soluției de bază inițiale 
sisteme (2.14). În acest caz, valoarea funcției obiectiv este egală cu 
.
Deoarece , atunci condiția (2.10) nu este îndeplinită și, prin urmare, soluția nu este optimă.
Să compilam tabelul 2.4 pentru a trece la o nouă soluție de bază a sistemului (2.14) - (2.15).
Tabelul 2.4
| 1 | -  | -  | -  |
||||
| | 0 | -1 | 0 | 0 |
|||
| | 0 | 0 | -1 | 0 |
|||
 | 4 | 1 | -2 | 0 |
|||
| | 0 | 0 | 0 | -1 |
|||
 | 2 | 4 * | -6 | -2 |
|||
 | 4 | 2 | 0 | -1 |
|||
 | 32 | ||||||
 | 12 | -10 | -4 |
||||
 | 4 | ||||||
 | 1/2 | Tabelul 2.5 | 0 | 0 | -1 |
||
| | 0 | -1 | 0 | 0 |
|||
| | 3 | -1/2 | 3 * | 0 |
|||
| | 110,25 | ||||||
| | -2,5 | 9 | -2 |
||||
| | -3 |
Cursul 11.Programare convexă
Definiția 1. Z problema de programare convexa se numește o problemă de programare neliniară în care toate funcțiile sunt convexe.
Astfel, problema de programare convexă este o problemă de minimizare constrânsă, unde funcția obiectiv este convexă și regiunea fezabilă este o mulțime convexă formată dintr-un sistem de inegalități convexe. Prin urmare, afirmațiile obținute mai devreme în Secțiunea 6 sunt valabile pentru problema de programare convexă. În această secțiune vom specifica aceste rezultate generale și le vom pune într-o formă mai convenabilă pentru studierea și rezolvarea următoarei probleme de programare convexă:
(1)
,
(2)
.
(3)
Vom avea nevoie de câteva construcții auxiliare în spațiu 
vectori 
. Vector al primului 
componenta punctuala 
vom nota prin 
. Asa de, 
.
Pentru problema (1) – (3) definim multimea
Unde 
.
Lema
.
Pentru problema de programare convexă (1) – (3)
o multime de
convex.
Dovada.
Să alegem vectori arbitrari 
din multi 
si numarul 
. Apoi sunt puncte 
Și 
din
ca . Să înmulțim aceste inegalități cu 
Și 
, respectiv, și adună-le. Datorită convexității tuturor funcțiilor, obținem
Din inegalitățile obținute rezultă că mulțimea este convexă 
.
Teorema 1.
(Teorema Kuhn-Tucker sub forma punctului de șa al funcției Lagrange a unei probleme de programare convexă
) Să fie în problema de programare convexă (1) – (3) sistemul (2) să satisfacă condiția Slater cu privire la 
a fost o soluție la problema (1) – (3), este necesar și suficient să existe un vector nenegativ 
astfel încât 
– punctul de șa al funcției Lagrange.
Dovada. Deoarece suficiența acestei condiții a fost deja dovedită pentru o problemă de programare neliniară arbitrară (vezi Teorema 2.6 în introducere), rămâne doar să dovedim necesitatea.
Necesitate.
Lăsa
– rezolvarea problemei (1) – (3). Sa punem 
. Este evident că 
, deoarece
,
Și
.
Să ne asigurăm că 
. Să presupunem contrariul. Aceasta înseamnă că există un punct 
astfel încât 
. Prin urmare, 
– un astfel de punct admisibil, valoarea funcției obiectiv la care este mai mică decât minimul. Primim o contradicție cu faptul că
– rezolvarea unei probleme de programare convexe.
Asa de, 
. Conform lemei, setul 
convex. În consecință, toate cerințele teoremei 8.2 sunt îndeplinite. Prin urmare, există un non-zero
vector 
punct de referinta 
la multe 
:
Să verificăm în continuare că toate coordonatele vectorului 
nu sunt pozitive. Să presupunem contrariul. Să existe o coordonată 
. Să reparăm vectorul 
toate componentele cu excepția 
-Ai. Apoi, având în vedere că produsul 
poate lua valori arbitrar mari (datorită nelimitării de sus a coordonatei 
), obținem o contradicție cu inegalitatea (4).
Este ușor să vezi asta pentru orice 
vectori 
incluse in set 
. Atunci din (4) avem:
Să arătăm asta 
. Să nu fie așa. Apoi 
. Prin urmare, 
. Conform condiției lui Slater, există un vector 
astfel încât 
. De aceea 
. Contradicția rezultată înseamnă că 
.
Să notăm 
. Să arătăm că vectorul construit 
reprezintă vectorul dorit al multiplicatorilor Lagrange. Este evident că 
iar din (5) obținem
Prin urmare, la
ar trebui să
.
(7)
Pe de altă parte, din moment ce 
(deoarece 
) Și 
, obținem inegalitatea
. De aici și din (7) rezultă că la punct 
este îndeplinită condiția de nerigiditate complementară:
.
(8)
Din (6) și (8) avem
sau, ce este la fel,
În continuare, lasă 
. Apoi 
. De aici și din (8) obținem inegalitatea
Inegalitățile (9), (10) înseamnă că 
este punctul de șa al funcției Lagrange a problemei convexe.
sigla de programare. Asta se cerea.
Înainte de a ne familiariza cu o altă versiune a teoremei Kuhn-Tucker, prezentăm următoarea teoremă, care este un criteriu minim condiționat în ceea ce privește conurile vectorului suport.
Teorema 2.
Lăsa 
– convexă și diferențiabilă pe 
funcţie, set 
convex. Apoi, pentru a face un punct
a fost minimul condiționat al funcției 
pe un platou 
, este necesar și suficient pentru ca includerea să aibă loc
.
(11)
Demonstrarea rezultă direct din teorema 6.5 și din definiția conului 
vectori suport la un punct 
la multe
.
Teorema
3.
(Teorema Kuhn-Tucker în formă diferenţială pentru o problemă de programare convexă
) Să fie dată o problemă de programare convexă sub forma (1), (2), unde toate funcțiile 
sunt diferențiabile continuu, sistemul (2) satisface condiția Slater. Apoi, pentru vectorul 
a fost o soluție la problema (1), (2), este necesar și suficient să existe un vector nenegativ 
astfel încât să fie îndeplinite condițiile
,
(12)
.
Dovada.
Să arătăm că condițiile (12) și (13) sunt echivalente cu includerea (11). Lasă punctul 
este asta 
. Apoi 
Și 
.
Lasă-l acum 
. Apoi din teoremele 2 și 10.5 rezultă că o condiție necesară și suficientă pentru un extremum este existența unor astfel de factori. 
,
, pentru care 
. Sa punem 
pentru toți 
iar din ultima egalitate obținem condițiile (12) și (13). Asta se cerea.
Pentru a încheia această secțiune, prezentăm formulările a două teoreme Kuhn-Tucker pentru problema calculului
programare convexă cu constrângeri liniare.
Teorema 4.
Fie în problema de programare convexă (1) – (3) sistemul de constrângeri (2) are forma 
, b – vector dimensiune 
. Apoi, pentru un vector nenegativ
a fost o solutie la problema, este necesar si suficient ca
a existat un vector nenegativ
astfel încât
este punctul de șa al funcției Lagrange a acestei probleme.
Rețineți că în acest caz funcția Lagrange are forma .
Teorema
5.
Fie în problema de programare convexă (1), (2) funcția obiectiv
este continuu diferentiabil, sistemul de restrictii (2) are forma 
, unde A este matricea dimensiunilor 
, b – vector dimensiune 
.
Apoi, pentru vectorul 
a fost o soluție la problemă, este necesar și suficient să existe un vector nenegativ
astfel încât să fie îndeplinite condițiile
,
.
Rețineți că teoremele 4 și 5 nu necesită îndeplinirea condiției Slater, prin urmare nu sunt cazuri speciale ale teoremelor 1 și 3 și necesită dovezi independente.
Să ni se dea un sistem de inegalități de formă
(4.3) și funcție
Z = f (x 1 , x 2 , …, x n), (4.4)
în plus, toate funcțiile sunt convexe pe o mulțime convexă M, iar funcția Z este fie convexă pe mulțimea M, fie concavă.
Problema programării convexe este de a găsi o soluție la sistemul de constrângeri (4.3) în care funcția obiectiv Z atinge o valoare minimă, sau funcția concavă Z atinge o valoare maximă. (Condițiile pentru non-negativitatea variabilelor pot fi considerate incluse în sistemul (4.3)).
Datorită proprietății 3 0, fiecare problemă de programare liniară este un caz special de problemă de programare convexă. În general, problemele de programare convexe sunt probleme de programare neliniară. Separarea problemelor de programare convexe într-o clasă specială se explică prin proprietățile extreme ale funcțiilor convexe: fiecare minim local al unei funcții convexe (maximul local al unei funcții concave) este de asemenea global; în plus, având în vedere proprietatea 2 0, o funcție convexă (concavă) definită pe o mulțime mărginită închisă atinge un maxim global și un minim global pe această mulțime. De aici rezultă că dacă funcția obiectiv Z este strict convexă (strict concavă) și dacă domeniul de soluție al sistemului de constrângeri nu este gol și limitat, atunci problema de programare convexă are întotdeauna o soluție unică.
Se numește funcția F(X) = F(x 1, x 2, …, x n). separabil, dacă poate fi reprezentat ca o sumă de funcții, fiecare dintre ele depinde de o singură variabilă, adică. Dacă
(este posibil ca F i (x i) = 0 pentru unele i).
Fie ca problema de programare convexă să fie dată de un sistem de constrângeri (4.3) și o funcție obiectiv (4.4), iar atât funcția obiectiv Z, cât și toate constrângerile sunt separabile. Atunci problema arată astfel:
Aflați minimul unei funcții convexe (maximul unei concave).
sub restricții
Ideea metodei de aproximare liniară pe bucăți este că toate fi și toate sunt înlocuite cu linii întrerupte constând din segmente drepte. În acest caz, problema de programare convexă inițială este înlocuită cu o problemă nouă, aproximativă, care este o problemă de programare liniară. Această problemă este de obicei rezolvată folosind metoda simplex, iar soluția ei este o soluție aproximativă a problemei de programare convexă inițială.
Figura 12. Rezolvarea problemei de programare convexă utilizând metoda de aproximare liniară pe bucăți
Pentru a construi o problemă aproximativă, luați în considerare o aproximare liniară pe bucăți a unei funcții a unei variabile h(x) definită pe interval. Să împărțim acest segment în r părți prin puncte x 0 Ecuația pentru secțiunea dreptei întrerupte dintre punctele (x k ; h k) și (x k+1 ; h k+1) are forma (ecuația unei drepte bazată pe două puncte). Dacă notăm fiecare dintre relațiile din această egalitate prin: Rețineți că pentru fiecare există o valoare unică care îndeplinește condițiile (4.7). După ce am notat, putem rescrie (4.7) sub forma: [Ecuațiile (4.8) se numesc ecuații parametrice ale segmentului. Dacă h(x) = 0, atunci a doua dintre aceste ecuații devine identitatea 0 = 0, iar prima ia forma (4.1) - ecuația segmentului situat pe axa x]. Astfel, pentru oricare, ecuația liniei întrerupte poate fi scrisă ca: În plus, doar două valori sunt întotdeauna diferite de zero (dacă x este punctul interior al k-lea segment al partiției) sau una (dacă x coincide cu sfârșitul segmentului). Revenind la problema programării convexe cu funcții separabile, observăm că în primul rând (în funcție de sistemul de restricții) este necesar să se determine intervalul de modificare a fiecărei variabile x j. Apoi fiecare dintre acest interval este împărțit în părți prin puncte x jk și folosind formulele (4.9) se construiește o aproximare liniară pe bucăți pentru funcțiile f j și. După aceasta, putem scrie o problemă aproximativă pentru problema inițială (4.6): Găsiți maximul unei funcții sub restricții (4.10) Întrucât problema aproximativă (4.10) este o problemă de programare liniară, care se rezolvă de obicei folosind metoda simplex, condițiile pentru nenegativitatea variabilelor sunt scrise separat de alte restricții. Diferența dintre problema rezultată (4.10) și problema de programare liniară obișnuită este că pentru fiecare x j nu există mai mult de două altele învecinate nenule și, prin urmare, două cu același j și k neînvecinat nu pot fi luate drept variabile principale. De asemenea, rețineți că pentru condițiile de non-negativitate a termenilor variabili f j (x j) și (dacă există) aproximarea liniară pe bucăți, desigur, nu este necesară. Acest capitol a examinat doar câteva dintre metodele de optimizare utilizate de manageri pentru a lua decizii eficiente în întreprinderi. Cu toate acestea, tehnicile descrise fac posibilă înțelegerea principiului de bază al utilizării aparatelor matematice în economie, ceea ce vă permite să alegeți dintre multe opțiuni alternative pe cea optimă pentru un anumit caz sau situație specifică.
