POLITEHNICA Bucureşti

Facultatea de Inginerie Industrială şi Robotică

Cercetare operaţională
Cursul 5

© Conf. dr. ing. mat. Ovidiu Blăjină

© Blăjină Ovidiu Cap.9. Teoria stocurilor
 Cercetare operațională – Cursul 5

Capitolul 3

PROGRAMARE NELINIARĂ

© Blăjină Ovidiu Cap.3. Programare neliniară 1/59

 Cercetare operațională – Cursul 5

1. Mulţimi şi funcţii convexe

2. Condiţii necesare şi/sau suficiente
de optimalitate
3. Programare pătratică
4. Programare convexă cu restricţii
liniare
5. Programare convexă

© Blăjină Ovidiu Cap.3. Programare neliniară 2/59

 Cercetare operațională – Cursul 5

O problemă de programare matematică în

forma generală constă în a optimiza (minimizare sau
maximizare) o funcţie reală, de n variabile reale,
supusă, sau nu, unui număr finit de restricţii.
Fie X  Rn şi f: X → R, g: X → Rm, h: X → Rk.
Modelul matematic al unei probleme de
optimizare cu restricţii are forma:
 min [max] f ( x)
 g ( x)  0

 (1)
 h( x ) = 0
 x  X

© Blăjină Ovidiu Cap.3. Programare neliniară 3/59

 Cercetare operațională – Cursul 5

unde f se numeşte funcţia obiectiv, iar g şi h sunt

restricţiile problemei (1).
Definiţie. Dacă cel puţin una din funcţiile f, gi (i =
1,..., m), hj (j = 1,..., k) este neliniară, atunci
problema (1) este de programare neliniară.

© Blăjină Ovidiu Cap.3. Programare neliniară 4/59

 Cercetare operațională – Cursul 5

1. Mulţimi şi funcţii convexe

© Blăjină Ovidiu Cap.3. Programare neliniară 5/59

 Cercetare operațională – Cursul 5

Definiţie. Fie vectorii x1, x2  Rn. Mulţimea


[ x1, x 2 ] = x  R n x = x1 + (1 − ) x 2 ,   [0, 1] 
se numeşte segment, cu extremităţile x1 şi x2.
Definiţie. Mulţimea X  Rn se numeşte convexă dacă
 x1, x2  X avem [x1, x2]  X.
Observaţie. Mulţimea vidă  şi spaţiul Rn sunt
mulţimi convexe.
Proprietăţi ale mulţimilor convexe:
1) O mulţime X  Rn este convexă dacă şi numai
dacă orice combinaţie convexă
x = 1x1 +  2 x 2 +  +  k x k  X
© Blăjină Ovidiu Cap.3. Programare neliniară 6/59
 Cercetare operațională – Cursul 5

în care x1,..., xk  X, 1,..., k  0, cu 1 +  +  k = 1.

2) Intersecţia unei familii arbitrare de mulţimi
convexe este o mulţime convexă.
Definiţie. Fie f : X  Rn → R şi x0  X. Funcţia f
este convexă în punctul x0 dacă
f (x + (1 − ) x0 )  f ( x) + (1 − ) f ( x0 ) (2)
x X,   (0, 1), pentru care x + (1 − ) x  X . 0

Definiţie. Funcţia f este strict convexă în punctul x0

dacă inegalitatea din relaţia (2) este strictă (<).
Definiţie. Funcţia f este concavă (strict concavă) în
punctul x0 dacă -f este convexă (strict convexă) în x0.
© Blăjină Ovidiu Cap.3. Programare neliniară 7/59
 Cercetare operațională – Cursul 5

Observaţii:
1) O funcţie f este convexă (concavă) pe mulţimea
X dacă este convexă (concavă) în oricare punct al
mulţimii X.
2) O funcţie f care este simultan convexă şi
concavă se numeşte afină. Ea satisface condiţia:
f (x1 + (1 − ) x 2 ) = f ( x1 ) + (1 − ) f ( x 2 )
x1,  X,   (0, 1), cu x + (1 − ) x  X.
x2 0

3) Orice funcţie liniară este afină.

4) O funcţie liniară nu este nici strict convexă, nici
strict concavă.

© Blăjină Ovidiu Cap.3. Programare neliniară 8/59

 Cercetare operațională – Cursul 5

Definiţie. Se numeşte gradient al funcţiei f : Rn → R

vectorul derivatelor parţiale ale funcţiei f:
T
 f f f 
f =  , ,..., 
 x1 x2 xn 

Definiţie. Se numeşte matrice hessiană asociată

funcţiei f : Rn → R matricea derivatelor parţiale de
ordinul doi ale funcţiei f:
 2 f 
Hf =   , i, j = 1,..., n
 xi x j 

© Blăjină Ovidiu Cap.3. Programare neliniară 9/59

 Cercetare operațională – Cursul 5

Exemplu. Fie x0 = [1, 2, 3] T şi funcţia f : R3 → R,

f(x1, x2, x3) = 2 x13x2 x3 − x2 x32 . Să se calculeze f(x0) şi
Hf(x0).
Soluţie:
 6 x12 x2 x3 
   36
f =  2 x13 x3 − x32  f ( x 0 ) = − 3
2 x13 x2 − 2 x2 x3  − 8

12 x1x2 x3 6 x12 x3 6 x12 x2 

  72 18 12
Hf =  6 x1 x3
2
0 2 x1 − 2 x3  Hf ( x ) = 18 0 − 4
3 0

 6 x12 x2 2 x13 − 2 x3 − 2 x2  12 − 4 − 4

❑
© Blăjină Ovidiu Cap.3. Programare neliniară 10/59
 Cercetare operațională – Cursul 5

Proprietăţi ale funcţiilor convexe (concave):

1) Orice punct de minim (maxim) local al unei
funcţii convexe (concave) f pe o mulţime convexă şi
închisă X este un punct de optim global.
2) Dacă funcţia f este strict convexă (concavă) pe
mulţimea convexă X şi are un punct de minim
(maxim), atunci acest punct este unic.
3) O funcţie f este convexă (strict convexă) dacă
şi numai dacă matricea hesssiană Hf este pozitiv
semidefinită (definită).

© Blăjină Ovidiu Cap.3. Programare neliniară 11/59

 Cercetare operațională – Cursul 5

Propoziţie. O matrice pătratică A  M n  n este

pozitiv definită (semidefinită) dacă satisface una din
următoarele două condiţii:
1) Minorii principali ai matricei A sunt pozitivi
(nenegativi).
2) y  R \ {0}, avem y  HA  y  [] 0 .
n T

Exemplu. Să se arate că funcţia f : R2 → R,

f(x1, x2) = x1 − x1 + 2 x2 − 3x2 + 5 este strict convexă.
2 2

Soluţie: Se calculează
 2 x1 − 1  ; 2 0
f =  Hf =
4 x2 − 3 0 4
© Blăjină Ovidiu Cap.3. Programare neliniară 12/59
 Cercetare operațională – Cursul 5

Funcţia f este strict convexă dacă matricea

hessiană Hf este pozitiv definită. Într-adevăr matricea
Hf este pozitiv definită deoarece:
- minorii principali sunt pozitivi:
1 = 2 = 2  0 ;  2 = 2 0 = 8  0
0 4
sau
- fie un vector oarecare y = [y1, y2] T  [0, 0] T şi se
calculează
2 0  y1 
y  Hf  y =  y1
T
y2        = 2 y1
2
+ 4 y2 0
2
0 4  y2 
❑

© Blăjină Ovidiu Cap.3. Programare neliniară 13/59

 Cercetare operațională – Cursul 5

2. Condiţii necesare şi/sau suficiente de

optimalitate

© Blăjină Ovidiu Cap.3. Programare neliniară 14/59

 Cercetare operațională – Cursul 5

Fie problema generală de minimizare cu

restricţii, scrisă în forma vectorială:
 min f ( x)
 g ( x)  0
 (3)

 h( x ) = 0
 x  X

unde mulţimea X  Rn, funcţia reală f : X → R, iar

funcţiile vectoriale g : X → Rm, h : X → Rk.

© Blăjină Ovidiu Cap.3. Programare neliniară 15/59

 Cercetare operațională – Cursul 5

Mulţimea soluţiilor posibile (programelor) ale

problemei (3) se notează cu:
P = x  X g ( x)  0, h( x) = 0
A rezolva problema revine la determinarea
punctelor de minim global ale funcţiei f pe X.
Definiţie. O soluţie posibilă x*  P a problemei (3)
este optimă dacă f(x*)  f(x), x  P.
Definiţie. Se numeşte lagrangian (funcţia lui
Lagrange) asociat problemei (3) funcţia
L( x, u, v) = f ( x) + u T g ( x) + vT h( x)
unde x  X, u  R m+ , v R k.
© Blăjină Ovidiu Cap.3. Programare neliniară 16/59
 Cercetare operațională – Cursul 5

Deoarece h( x) = 0  h( x)  0, − h( x)  0 se
va considera problema (3) adusă la forma:
 min f ( x)

 g ( x)  0 (4)
 x X

În plus, presupunem că X  Rn este mulţime
convexă, iar f şi g sunt funcţii convexe, adică
problema (4) este de programare convexă.
Mulţimea programelor problemei (4)
P = x  X g ( x)  0
este convexă ca intersecţie de mulţimi convexe.
© Blăjină Ovidiu Cap.3. Programare neliniară 17/59
 Cercetare operațională – Cursul 5

Teoremă. (Kuhn-Tucker). Dacă funcţiile convexe f şi

g sunt şi diferenţiabile în punctul x* X  Rn, atunci
condiţia necesară şi suficientă ca x* să fie soluţie
optimă a problemei (4) este să existe u*  R m+
astfel încât:
 (u* )T  g ( x* ) = 0
 (5)
 x L ( x*
, u*
)=0

 g ( x*
)0

Obs.: Relaţiile (5) se numesc condiţiile Kuhn-Tucker.

© Blăjină Ovidiu Cap.3. Programare neliniară 18/59

 Cercetare operațională – Cursul 5

Exemplu. Se consideră gestiunea unui stoc cu perioa-

dă fixă şi cerere constantă, cu ruptură de stoc, relativ
la un produs, în condiţiile ce urmează. Pe durata t0 =
360 zile este disponibilă o cantitate N = 20000 buc. Se
va lansa o aceeaşi comandă x, la perioade de timp
egale T. Costul de lansare a unei comenzi este cl = 100
u.m., iar costul de stocare a unei unităţi de produs pe
unitatea de timp este cs = 1/3 u.m./buc. zi. Se admite
lipsa de stoc, costul de penalizare pentru lipsa unei
unităţi de produs pe unitatea de timp fiind cp = 1/3
u.m./buc.zi. Fiecare comandă lansată nu poate depăşi
1000 buc.
© Blăjină Ovidiu Cap.3. Programare neliniară 19/59
 Cercetare operațională – Cursul 5

Să se determine nivelul optim al stocului y, al

comenzii x şi al perioadei T astfel încât cheltuielile
totale să fie minime.
Soluţie: Cheltuielile totale efectuate pentru o coman-
dă sunt date de suma dintre costul de lansare a co-
menzii, costul mediu al stocării celor y buc. de produs
şi costul mediu datorat lipsei produselor din stoc:

© Blăjină Ovidiu Cap.3. Programare neliniară 20/59

 Cercetare operațională – Cursul 5

N  cl 1 cs  t0  y 2 c 
1 p 0t  ( x − y ) 2
f ( x, y) = + +
x 2 x 2 x
2000000 60 y 2 60( x − y )2
f ( x, y) = + +
x x x
Restricţia privind mărimea comenzii x este:
g ( x) = x − 1000  0
Modelul problemei este de forma:
 min f ( x, y )

 g ( x)  0
 x, y  0

© Blăjină Ovidiu Cap.3. Programare neliniară 21/59
 Cercetare operațională – Cursul 5

Lagrangianul este L = f(x, y) + ug(x), u  0.

Sistemul condiţiilor Kuhn-Tucker se scrie:
 L 60 x 2 − 120 y 2 − 2000000
 = +u =0
 x
2
x
 L 240 y − 120 x
 y = x
=0

 x − 1000  0

 u ( x − 1000) = 0
Din ultima restricţie rezultă x0 = 1000 sau u0 = 0.
Dacă x0 = 1000, atunci din a doua restricţie rezultă
1
y0 = x0 = 500.
2
© Blăjină Ovidiu Cap.3. Programare neliniară 22/59
 Cercetare operațională – Cursul 5

Din prima restricţie rezultă u0 = -28 < 0, fals. Deci

u0 = 0.
Din primele două restricţii (pentru x > 0) rezultă:
200 100
x0 = 15 buc.; y0 = 15 buc.
3 3
Deci ((x0, y0)T, u0) este punct şa.
Aşadar (x0, y0)T este program optim al problemei
considerate.
Perioada optimă de lansare a comenzilor este:
x0  t0 6
T0 = = 15 zile ❑
N 5

© Blăjină Ovidiu Cap.3. Programare neliniară 23/59

 Cercetare operațională – Cursul 5

3. Programare pătratică

© Blăjină Ovidiu Cap.3. Programare neliniară 24/59

 Cercetare operațională – Cursul 5

O problemă de programare pătratică constă în

optimizarea (maximizarea sau minimizarea) unei
funcţii obiectiv pătratice cu restricţii liniare:
 1 T
 max [min] f ( x) = c x + 2 x Q x
T

 (6)
 Ax  [=, ] b
 x0


unde: A  M m  n; b  Rm; c  Rn; Q este o matrice
simetrică; f este o funcţie convexă dacă este mini-
mizată sau concavă dacă este maximizată.
© Blăjină Ovidiu Cap.3. Programare neliniară 25/59
 Cercetare operațională – Cursul 5

Observaţii:
1) Funcţia Qx se numeşte formă pătratică.
x T

2) Condiţia ca matricea Q să fie simetrică nu re-

1 T
strânge generalitatea deoarece x Qx = x (Q + QT ) x ,
T

x  Rn. 2
3) Forma pătratică x TQx este convexă (strict conve-
xă) dacă şi numai dacă matricea Q este semipozitiv
(pozitiv) definită.
Pentru rezolvarea problemei (6) se poate aplica
metoda elaborată de P. Wolfe, care utilizează, în
esenţă, o versiune uşor modificată a algoritmului
simplex.
© Blăjină Ovidiu Cap.3. Programare neliniară 26/59
 Cercetare operațională – Cursul 5

© Blăjină Ovidiu Cap.3. Programare neliniară 27/59

 Cercetare operațională – Cursul 5

© Blăjină Ovidiu Cap.3. Programare neliniară 28/59

 Cercetare operațională – Cursul 5

în care F este o matrice pătratică n  n, a cărei formă

este precizată în enunţul algoritmului.
Algoritmul lui Wolfe se bazează pe algoritmul
simplex, dar cu o anumită modificare la criteriul de
intrare în bază.

© Blăjină Ovidiu Cap.3. Programare neliniară 29/59

 Cercetare operațională – Cursul 5

 Algoritmul lui Wolfe forma scurtă:

Pasul 1. Se testează dacă mulţimea programelor
(soluţiilor admisibile) ale problemei iniţiale
P = {x  R n Ax  [=, ] b, x  0}
este nevidă.
Dacă P = , atunci STOP; altfel, fie o soluţie
0
de bază x .
Pasul 2. Se determină matricea pătratică F de dimen-
siune n  n, F = ( f 1 , f 2 ,..., f n ) , a cărei coloană oare-
care este:

 e , dacă (e ) Q x + c  0
j j T 0
( )
f =
( )
j
0

 − e , dacă (e ) Q x + c  0
j j T

© Blăjină Ovidiu Cap.3. Programare neliniară 30/59

 Cercetare operațională – Cursul 5

unde e j = [0 ... 0 1 0 ...0]T , unica componentă nenulă

fiind pe poziţia j.
Pasul 3. Se construieşte problema de programare
liniară auxiliară cu funcţia obiectiv min ( z1 + z2 + ... + zn )
şi restricţiile (*).
Se rezolvă această problemă cu algoritmul simplex
primal, dar cu următoarea modificare: variabilele xj
şi vj (j = 1,..., n), respectiv, yi şi ui (i = 1,..., m) sunt
complementare (restricţia (**)), adică:
- dacă xj este variabilă bazică, atunci vj nu poate intra
în bază;
- dacă vj este variabilă bazică, atunci xj nu poate intra
© Blăjină Ovidiu Cap.3. Programare neliniară 31/59
 Cercetare operațională – Cursul 5

în bază;
- dacă yi este variabilă bazică, atunci ui nu poate intra
în bază;
- dacă ui este variabilă bazică, atunci yi nu poate intra
în bază.
Valorile x j (j = 1,..., n) din soluţia optimă a
problemei auxiliare reprezintă soluţia optimă a
problemei iniţiale de programare pătratică.

© Blăjină Ovidiu Cap.3. Programare neliniară 32/59

 Cercetare operațională – Cursul 5

Exemplu. Să se rezolve problema de programare

pătratică:
 [min] f = 3x12 + 2 x22 − x1x2 − 4 x1 − 3x2

 x1 + 2 x2  5

 2 x1 + 3x2  9
 x,x 0
 1 2
Soluţie. Avem
c = − 4 Q =  6 − 1  x1  A = 1 2 5
x=  b =
 − 3 − 1 4  x2  2 3 9

H( f ) = Q =  6 − 1
− 1 4
© Blăjină Ovidiu Cap.3. Programare neliniară 33/59
 Cercetare operațională – Cursul 5

Minorii principali sunt:

6 =60 6 − 1 = 23  0
−1 4
Deci funcţia f este strict convexă şi, pentru
rezolvarea problemei, se poate aplica algoritmul lui
Wolfe forma scurtă.
Mulţimea programelor problemei este:
P = {x  R2 x1 + 2 x2  5, 2 x1 + 3x2  9, x1  0, x2  0}  
0
Fie x = [0 0]T  P , o soluţie de bază.
Se construieşte matricea F = ( f 1 , f 2 ) , după deter-
minarea celor două coloane:
− −
1 T 
(e )  Q x + c  = 1 0    
= −4  0  f = −e = 0 
0 4 1 1 1
   − 3  
© Blăjină Ovidiu Cap.3. Programare neliniară 34/59
 Cercetare operațională – Cursul 5

2 T   −  0
(e )  Q x + c  = 0 1  4
0
= −3  0  f = −e =  
2 2
   − 3 − 1
 − 1 0
Deci F = 
 0 − 1
Se construieşte problema de programare liniară
auxiliară:
 min ( z1 + z2 )
 Ax + y = b


 Qx + A T
u − v − Fz = −c
 x, y , u , v, z  0


© Blăjină Ovidiu Cap.3. Programare neliniară 35/59

 Cercetare operațională – Cursul 5

 min ( z1 + z2 )
 x + 2x + y =5
 1 2 1
 2 x1 + 3 x2 + y2 =9

 6 x1 − x2 + u1 + 2u2 − v1 + z1 =4
 − x1 + 4 x2 + 2u1 + 3u2 − v2 + z2 = 3

 x1 , x2 , y1, y2 , u1, u2 , v1, v2 , z1 , z2  0
Pentru rezolvarea acestei probleme se aplică
algoritmul simplex, cu respectarea restricţiei supli-
mentare de intrare în bază din algoritmul lui Wolfe.
În partea inferioară a tabelelor simplex sunt
marcate cu asterisc (*) coloanele variabilelor care nu
pot intra în bază la iteraţia respectivă.
© Blăjină Ovidiu Cap.3. Programare neliniară 36/59
 Cercetare operațională – Cursul 5

© Blăjină Ovidiu Cap.3. Programare neliniară 37/59

 Cercetare operațională – Cursul 5

Tabelul de mai sus conţine soluţia optimă a

problemei auxiliare.
Soluţia optimă a problemei iniţiale de programare
pătratică este: x1 = 19/23, x2 = 22/23.
Valoarea optimă corespunzătoare a funcţiei
obiectiv este fmin = f(x1, x2) = -71/23. ❑

© Blăjină Ovidiu Cap.3. Programare neliniară 38/59

 Cercetare operațională – Cursul 5

4. Programare convexă cu restricţii

liniare

© Blăjină Ovidiu Cap.3. Programare neliniară 39/59

 Cercetare operațională – Cursul 5

Fie problema de programare neliniară convexă

cu restricţii liniare:
 min f ( x)

 Ax  b (7)
 x0

unde f este o funcţie convexă, diferenţiabilă.
Mulţimea soluţiilor posibile (programelor) ale
problemei (7) se notează cu:
P = {x  Rn | Ax  b, x  0}

© Blăjină Ovidiu Cap.3. Programare neliniară 40/59

 Cercetare operațională – Cursul 5

 Algoritmul metodei direcţiilor admisibile:

Pasul 1. Se testează dacă mulţimea P este nevidă.
Dacă P = , atunci STOP; altfel, fie k = 0 şi xk  P.
Pasul 2. Se calculează f ( x k ) .
Dacă f ( x ) = 0, atunci xk este soluţie optimă,
k

STOP; altfel se trece la pasul 3.

Pasul 3. Se determină ~x k soluţia optimă a problemei
de programare liniară auxiliară:
 min ( x T  f ( x k ))

 xP
Pasul 4. Se calculează δk = (~ x k − x k )T  f ( x k ) .
© Blăjină Ovidiu Cap.3. Programare neliniară 41/59
 Cercetare operațională – Cursul 5

Dacă k = 0, atunci xk este soluţie optimă, STOP;

altfel se trece la pasul 5.
Pasul 5. Fie λ k  (0, 1] , λ k = min {ˆλ k , 1} , unde λ̂ k este
soluţie a ecuaţiei algebrice:
x k − x k )T  f ( x k + ˆλ k ( ~
(~ x k − x k )) = 0
Se determină x k +1 = x k + λ k ( ~
x k − xk ) .
k  k +1 şi se revine la pasul 2.

© Blăjină Ovidiu Cap.3. Programare neliniară 42/59

 Cercetare operațională – Cursul 5

Exemplu. Să se rezolve problema de programare

neliniară:
 min f = x12 + x23 − 2 x1 + 3 x2

 x1 + 2 x2  5

 4 x1 + x2  8
 x,x 0
 1 2
Soluţie. Matricea hessiană ataşată funcţiei obiectiv f
H( f ) =  2 0 
0 6 x2 
are minorii principali:
2 =20 2 0 = 12 x  0
0 6 x2 2

© Blăjină Ovidiu Cap.3. Programare neliniară 43/59

 Cercetare operațională – Cursul 5

deci funcţia obiectiv f este convexă.

Mulţimea programelor problemei este:
P = {x  R 2
x1 + 2 x2  5, 4 x1 + x2  8, x1, x2  0}  
Pentru rezolvarea problemei se poate aplica metoda
direcţiilor admisibile.
Iteraţia 1.
Fie k = 0. O soluţie admisibilă a problemei este
.x 0 = (0, 0) T  P .
Deoarece f ( x0 ) = (−2, 3)T  (0, 0) , x0 nu verifică
criteriul de optimalitate.
Se construieşte problema de PL auxiliară:
© Blăjină Ovidiu Cap.3. Programare neliniară 44/59
 Cercetare operațională – Cursul 5

 min ( x , x )   − 2 
 min x  f ( x )
T
 0
1 2  3
   
 xP  x  P
 min (−2 x1 + 3 x2 )
 x + 2x  5
 1 2
 (*)
 4 x1 + x2  8
 x1 , x2  0
Se rezolvă problema (*) cu algoritmul simplex sau
metoda grafică şi se obţine soluţia optimă ~ x 0 = (2, 0)T
~  − 2
δ0 = ( x − x )  f ( x ) = (2, 0)    = −4  0
0 0 T 0
 3
© Blăjină Ovidiu Cap.3. Programare neliniară 45/59
 Cercetare operațională – Cursul 5

 x0 nu este soluţie optimă a problemei iniţiale.

Se rezolvă ecuaţia: ( ~ 0 0 T 0 ˆ ~
x − x )  f ( x + λ0 ( x − x )) = 0
0 0

  0  ˆ  2    2ˆλ 0 
(2, 0)  f    + λ 0    = 0  (2, 0)  f  =0
 0  0  0 
 
 4ˆλ 0 − 2 
 (2, 0)    = 0  λ̂ 0 = 1/2.

 3 
λ 0 = min {ˆλ 0 , 1} = 1/2
O nouă soluţie admisibilă a problemei iniţiale este:
~  0  1  2 1
x = x + λ0 ( x − x ) =   +   =  
1 0 0 0
 0 2  0  0
k = 0 +1 = 1
© Blăjină Ovidiu Cap.3. Programare neliniară 46/59
 Cercetare operațională – Cursul 5

Iteraţia a 2-a.
f ( x1 ) = (0, 3)T  (0, 0)  x1 nu verifică criteriul
de optimalitate.
Se construieşte problema de programare liniară
auxiliară:
 min (3 x2 )
 min x  f ( x )
T 1
 x + 2x  5
  1
 x  P 
2
(**)
 4 x1 + x2  8
 x1 , x2  0
~
Soluţia optimă a problemei (**) este x = (0, 0)T.
1

~  0
δ1 = ( x − x )  f ( x ) = (−1, 0)    = 0
1 1 T 1
 3
© Blăjină Ovidiu Cap.3. Programare neliniară 47/59
 Cercetare operațională – Cursul 5

 x1 = (1, 0)T este soluţia optimă a problemei ini-

ţiale.
Valoarea optimă corespunzătoare a funcţiei
obiectiv a problemei iniţiale este f(x1) = -1. ❑

© Blăjină Ovidiu Cap.3. Programare neliniară 48/59

 Cercetare operațională – Cursul 5

5. Programare convexă

© Blăjină Ovidiu Cap.3. Programare neliniară 49/59

 Cercetare operațională – Cursul 5

Fie problema de programare neliniară convexă:

 min f ( x)
 (8)
 g ( x)  0
unde f : Rn → R, g: Rn → Rm, f, g funcţii convexe,
diferenţiabile.
Mulţimea soluţiilor posibile (programelor) ale
problemei (8) se notează:

P = x  R g ( x)  0
n

© Blăjină Ovidiu Cap.3. Programare neliniară 50/59
 Cercetare operațională – Cursul 5

Metoda planului de secţiune, elaborată de J. E.

Kelley, pentru rezolvarea problemei (8), are la bază
ideea ca la fiecare iteraţie k să se rezolve o problemă
de programare liniară, cu funcţia obiectiv cTx şi
restricţii liniare care să determine un tronson convex
Pk ce include mulţimea P.

© Blăjină Ovidiu Cap.3. Programare neliniară 51/59

 Cercetare operațională – Cursul 5

 Algoritmul metodei planului de secţiune:

Pasul 1. Fie k = 1.
Pasul 2. Se construieşte problema de programare
liniară auxiliară:
 min c T x (9)

 x  Pk , Pk  P
Se rezolvă problema (9) şi fie xk soluţia optimă.
Pasul 3. Se calculează gl ( xk ) = max { gi ( xk ), i = 1,..., m }
Pasul 4. a) Dacă gl ( x )  0  x  P  xk este
k k

soluţie optimă pentru problema (8), STOP.

b) Dacă gl ( x )  0, atunci se construieşte tronsonul
k

© Blăjină Ovidiu Cap.3. Programare neliniară 52/59

 Cercetare operațională – Cursul 5

Pk +1 = Pk  {x  R n g l ( x k ) + ( x − x k )T   gl ( x k )  0}
Fie k  k + 1 şi se revine la pasul 2 al algoritmului.
Observaţie: Aplicarea algoritmului precedent implică
operaţia de înlăturare, treptată, a unor tronsoane
împreună cu valorile optime corespunzătoare
fiecăruia. Aceste tronsoane definesc planele de
secţiune.

© Blăjină Ovidiu Cap.3. Programare neliniară 53/59

 Cercetare operațională – Cursul 5

Exemplu. Să se rezolve problema de programare

neliniară:
 min ( x1 + 3x2 )
 2
 x1 + x2  4
2

 x1 + x2  2

Soluţie. Funcţia obiectiv f : R2 → R, f(x) = x1 + 3x2
este o funcţie liniară, deci diferenţiabilă şi convexă.
Restricţiile problemei sunt determinate de funcţiile:
g1 : R → R, 1
2 g ( x ) = x1
2
+ x2 − 4 ( 0)
2

g2 : R2 → R, g2 ( x) = 2 − x1 − x2 ( 0)
Matricea hessiană a funcţiei g1 : H( g1 ) = 2 0
0 2
© Blăjină Ovidiu Cap.3. Programare neliniară 54/59
 Cercetare operațională – Cursul 5

are minorii principali

2 =20 2 0 =40
0 2
deci funcţia g1 este strict convexă.
Funcţia g2 fiind liniară este convexă. g1, g2 sunt
funcţii diferenţiabile.
Prin urmare, pentru rezolvarea problemei se poate
aplica metoda planului de secţiune.
Iteraţia 1
Mulţimea programelor problemei
P = { x  R 2 x12 + x22  4, x1 + x2  2}
este reprezentată haşurat în figura următoare:
© Blăjină Ovidiu Cap.3. Programare neliniară 55/59
 Cercetare operațională – Cursul 5

Fie k = 1. Fie P1 = { x  R 2 0  x1  2, 0  x2  2}

© Blăjină Ovidiu Cap.3. Programare neliniară 56/59

 Cercetare operațională – Cursul 5

Fie problema de programare liniară auxiliară:

 min ( x1 + 3x2 )
 x P
 1
Se rezolvă această problemă cu algoritmul simplex
sau pe cale grafică şi se obţine soluţia optimă:
x1 = (0, 0)T.
Se calculează:
max {g1(x1) , g2(x1)} = max {-4, 2}= g2(x1) = 2 > 0
Deci x1 nu este soluţie optimă pentru problema
iniţială.
Avem g 2 ( x) =  − 1
 − 1
© Blăjină Ovidiu Cap.3. Programare neliniară 57/59
 Cercetare operațională – Cursul 5

g2 ( x ) + ( x − x )   g2 ( x )  0  x1 + x2  2
1 1 T 1

Atunci P2 = P1  {x  R 2 x1 + x2  2}
Iteraţia a 2-a
k = 1+1 = 2. Se rezolvă problema de programare
liniară auxiliară:
 min ( x1 + 3x2 )
 x P
 2

şi se obţine soluţia ei optimă x2 = (2, 0)T.

Avem max {g1(x2) , g2(x2)} = 0.
Rezultă că x2 = (2, 0)T este soluţia optimă pentru
© Blăjină Ovidiu Cap.3. Programare neliniară 58/59
 Cercetare operațională – Cursul 5

problema iniţială.
Valoarea optimă a funcţiei obiectiv este f(x2) = 2.
❑

© Blăjină Ovidiu Cap.3. Programare neliniară 59/59