POLITEHNICA Bucureşti

Facultatea de Inginerie Industrială şi Robotică

Cercetare operaţională
Cursul 2

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

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

Capitolul 1

PROGRAMARE LINIARĂ
(II)

© Blăjină Ovidiu Cap.1. Programare liniară 1/55

 Cercetare operațională – Cursul 2

3. Metoda SIMPLEX
4. Dualitate în programarea liniară

© Blăjină Ovidiu Cap.1. Programare liniară 2/55

 Cercetare operațională – Cursul 2

3. Metoda SIMPLEX
3.1. Fundamente teoretice
3.2. Algoritmul simplex
3.3. Metoda coeficienţilor de penalizare

© Blăjină Ovidiu Cap.1. Programare liniară 3/55

 Cercetare operațională – Cursul 2

3.1. Fundamente teoretice

Cea mai utilizată metodă pentru rezolvarea
problemelor de PL este metoda simplex datorată
matematicianului american G. B. Dantzig (1947).
Metoda simplex permite cercetarea sistematică
a mulţimii soluţiilor admisibile de bază ale unui
model de problemă de PL în forma standard. Presu-
punând cunoscută o astfel de soluţie iniţială, se
construiesc succesiv soluţii realizabile de bază din ce
în ce "mai bune" pînă la obţinerea soluţiei optime.
Metoda oferă şi un criteriu de recunoaştere a
optimului infinit.
© Blăjină Ovidiu Cap.1. Programare liniară 4/55
 Cercetare operațională – Cursul 2

Prezentarea metodei simplex se va referi la

modelul de PL în forma standard de minimizare:
 min c T x

 Ax = b
 x0

unde x, c  Rn, b  Rm, A  Mm  n , cu rang A = m < n.
Fie B o bază primal admisibilă extrasă din
matricea A şi xB = B-1b soluţia de bază iniţială asociată.
Coeficienţii numerici ai problemei corespunză-
tori bazei B se înscriu în tabelul simplex asociat bazei
B, de forma:
© Blăjină Ovidiu Cap.1. Programare liniară 5/55
 Cercetare operațională – Cursul 2

© Blăjină Ovidiu Cap.1. Programare liniară 6/55

 Cercetare operațională – Cursul 2

Tabelul simplex conţine:

- în prima coloană, variabilele de bază (V.B.);
- în a doua coloană, valorile variabilelor de bază
(V.V.B.);
- în următoarele n coloane, vectorii y j , j = 1,..., n.
B

- pe ultima linie, valoarea funcţiei obiectiv în baza B,

notată cu z ; diferenţele z j - c j , j = 1, n .
B B

La aplicarea algoritmului metodei simplex,

fiecărei baze B îi corespunde un tabel simplex de
acest tip.

© Blăjină Ovidiu Cap.1. Programare liniară 7/55

 Cercetare operațională – Cursul 2

3.2. Algoritmul simplex

Algoritmul simplex pentru problema de minimizare:
Pasul 1. Se determină o bază primal admisibilă
iniţială B.
Pasul 2. Se calculează x , z, y j , z Bj − c j , j = 1,..., n .
B B B

Pasul 3. Dacă z Bj − c j  0, j = 1, n , atunci STOP:

este program optim; altfel se determină mulţimea

J + = j  J z Bj − c j  0 
şi se trece la pasul 4.
Pasul 4. Se determină indicele k  J+ cu criteriul de
intrare în bază:
© Blăjină Ovidiu Cap.1. Programare liniară 8/55
 Cercetare operațională – Cursul 2

max ( z Bj − c j ) = zkB − ck
jJ +

Dacă ykB  0, atunci STOP: problema are optim

infinit; altfel se determină indicele l  I cu criteriul
de ieşire din bază:
 x iB  x lB
min  B  = B
iI yik  ylk
y ik  0
B 

Pasul 5. Fie baza B’ obţinută din B prin înlocuirea

coloanei A(l) cu coloana A(k) . Se trece la pasul 2,
înlocuind peste tot baza B cu baza B’ .

© Blăjină Ovidiu Cap.1. Programare liniară 9/55

 Cercetare operațională – Cursul 2

Algoritmul simplex pentru problema de maximizare:

Pasul 3. Dacă j − c j  0, j = 1, n , atunci STOP: este
z B

program optim; altfel se determină mulţimea (nevidă)


J− = j  J z − c j  0 B
j 
şi se trece la pasul 4.
Pasul 4. Se determină indicele k  J- cu criteriul de
intrare în bază:
min ( z Bj − c j ) = zkB − ck
j J −

Dacă k  0, atunci STOP: problema are optim

B
y
infinit; altfel se determină indicele l  I cu criteriul
de ieşire din bază.
© Blăjină Ovidiu Cap.1. Programare liniară 10/55
 Cercetare operațională – Cursul 2

Observaţie: Elementul y se numeşte pivot.

B
lk

Formulele de schimbare a bazei sunt echiva-

lente cu următoarele reguli de transformare ale
tabelului simplex asociat bazei B:
a) elementele situate pe linia pivotului se împart la
pivot;
b) elementele situate pe coloana pivotului devin
zero, cu excepţia pivotului, care devine 1;
c) celelalte elemente ale tabelului simplex se tran-
sformă după formula dreptunghiului. Se consideră
dreptunghiul imaginar a cărui diagonală este deter-
minată de elementul de transformat şi de pivot:
© Blăjină Ovidiu Cap.1. Programare liniară 11/55
 Cercetare operațională – Cursul 2

Formula dreptunghiului:
yijB ylkB − yljB yikB
yijB =
ylkB
© Blăjină Ovidiu Cap.1. Programare liniară 12/55
 Cercetare operațională – Cursul 2

© Blăjină Ovidiu Cap.1. Programare liniară 13/55

 Cercetare operațională – Cursul 2
START

Construieşte
tabelul simplex
iniţial

Există Nu
Indică
valori pozitive (negative) pe STOP
soluţia optimă
linia diferenţelor?

Da
Determină
coloana pivotului

Există Nu Nu există
valori pozitive în coloana soluţie optimă STOP
pivotului ? finită

Da
Determină
linia pivotului

Calculează un nou
tabel simplex
© Blăjină Ovidiu Cap.1. Programare liniară 14/55
 Cercetare operațională – Cursul 2

Construieşte tabelul simplex iniţial

Cât timp există valori pozitive (negative) pe linia diferenţelor

execută

Determină coloana pivotului

Există valori pozitive în

coloana
Processpivotului ?
Da Process Nu

Determină linia pivotului Nu există

soluţieProcess
optimă finită
Calculează
noul tabel simplex STOP

Prezintă tabelul simplex final (ce conţine soluţia optimă)

© Blăjină Ovidiu Cap.1. Programare liniară 15/55

 Cercetare operațională – Cursul 2

Exemplu. Să se rezolve cu algoritmul simplex

problema de PL:
 min (4 x1 − 3 x2 + 5 x3 )
 3 x1 − 2 x2 + x3  4

 − 2 x1 + x2 + 2 x3  −1
 2 x1 + 4 x2 − 3 x3  6
 x  0, x  0, x  0
 1 2 3

Soluţie. Se aduce problema la forma standard. Pentru

aceasta se introduc variabilele de compensare x4 , x5 ,
x6 nenegative în cele trei restricţii. Se înmulţeşte cea
de-a doua restricţie cu -1 şi obţinem:
© Blăjină Ovidiu Cap.1. Programare liniară 16/55
 Cercetare operațională – Cursul 2

 min (4 x1 − 3x2 + 5 x3 )
 3x − 2 x + x + x =4
 1 2 3 4

 2 x1 − x2 − 2 x3 + x5 =1
 2 x1 + 4 x2 − 3x3 + x6 = 6
 x  0, i = 1, 6
 i
Matricea sistemului de restricţii a formei de mai
sus a problemei este:
 3 − 2 1 1 0 0
A =  2 − 1 − 2 0 1 0
 
 2 4 − 3 0 0 1 
cu m = 3, n = 6, rang (A) = 3 < 6.
© Blăjină Ovidiu Cap.1. Programare liniară 17/55
 Cercetare operațională – Cursul 2

Se poate forma o bază, B, cu ultimele trei coloane

ale matricei A, aceasta fiind matricea unitate:
1 0 0
B = 0 1 0 
 
0 0 1 
Pentru a putea aplica algoritmul simplex se
verifică, în prealabil, dacă baza B este primal
admisibilă. Într-adevăr, B fiind matrice unitate, avem
B-1 = B, iar x B = B−1b = b = 4 1 6 T > 0.
Se construiesc tabelele simplex (v. fig. urm.).
Problema admite soluţia optimă finită: x1= 0;
x2= 1,5; x3= 0; x4= 7; x 5= 2,5; x6= 0; zmin= -4,5.
© Blăjină Ovidiu Cap.1. Programare liniară 18/55
 Cercetare operațională – Cursul 2

❑
© Blăjină Ovidiu Cap.1. Programare liniară 19/55
 Cercetare operațională – Cursul 2

Exemplu. Să se rezolve problema de PL:

 max ( x1 + 3x2 + 2 x3 )
 x1 − x2 + x3  2
 − 2x + 2x − x  4
 1 2 3
 x1 , x2 , x3  0
Soluţie. Se aduce problema la forma standard, prin
introducerea variabilelor de compensare x4 , x5:
 max ( x1 + 3x2 + 2 x3 )
 x1 − x2 + x3 + x4 =2
 − 2x + 2x − x + x5 = 4
 1 2 3
 xi  0, i = 1, 5
© Blăjină Ovidiu Cap.1. Programare liniară 20/55
 Cercetare operațională – Cursul 2

Cu ultimele două coloane din matricea siste-

mului de restricţii (ecuaţii) se poate forma baza B,
respectiv, matricea unitate.
Baza B este o bază primal admisibilă deoarece
B −1b = b = 2 4  0 ; aşadar, se poate aplica algorit-
T

mul simplex.
Tabelele simplex corespunzătoare sunt prezen-
tate în figurile următoare.
În ultimul tabel se constată că există zk - ck < 0; J-
= {1, 2}, deci soluţia obţinută nu este optimă. Pe de
altă parte, toţi coeficienţii yi1 de pe coloana
variabilei x1 sunt nepozitivi. Rezultă că problema
dată are optim infinit (nu are soluţie optimă finită).
© Blăjină Ovidiu Cap.1. Programare liniară 21/55
 Cercetare operațională – Cursul 2

❑
© Blăjină Ovidiu Cap.1. Programare liniară 22/55
 Cercetare operațională – Cursul 2

3.3. Metoda coeficienţilor de penalizare

Pentru a putea începe aplicarea algoritmului
simplex este necesar a fi îndeplinite două condiţii:
➢ problema să fie în formă standard;
➢ să dispunem de o soluţie de bază iniţială.
Pentru cea de-a doua condiţie, alegerea la
întâmplare a unei baze formate din m vectori oarecare
dintre vectorii coloană ai matricei A poate conduce la
soluţii de bază nerealizabile, cu care aplicarea
algoritmului simplex nu poate începe.
Determinarea unei soluţii de bază iniţială se
poate realiza cu metoda coeficienţilor de penalizare.
© Blăjină Ovidiu Cap.1. Programare liniară 23/55
 Cercetare operațională – Cursul 2

Fie problema de PL de minimizare:

 [min] z = c1 x1 + c2 x2 +  + cn xn
 a11 x1 + a12 x2 +  + a1n xn  b1
 (1)
 
 am1x1 + am 2 x2 +  + amn xn  bm
 x ,..., x  0
 1 n

Presupunem că toţi termenii liberi sunt pozitivi:

b1  0,..., bm  0 şi că matricea A nu conţine nici un
vector coloană unitar.
Prin adăugarea variabilelor de compensare
(nenegative) cu semnul "-“ în fiecare restricţie, se
obţine sistemul de restricţii în forma standard:
© Blăjină Ovidiu Cap.1. Programare liniară 24/55
 Cercetare operațională – Cursul 2

 a11x1 + a12 x2 +  + a1n xn − xn +1 = b1


 a21x1 + a22 x2 +  + a2 n xn − xn + 2 = b2
 


 am1x1 + am 2 x2 +  + amn xn − xn + m = bm
Considerând ca soluţie iniţială de bază:
x1 = x2 = ... = xn = 0, xn +1 = -b1 , xn +2 = -b2 ,...,
xn + m = = -bm
aceasta nu este realizabilă (admisibilă) şi nu satisface
condiţiile algoritmului simplex.
Pentru a obţine o soluţie admisibilă de bază se
introduce în fiecare restricţie câte o variabilă
artificială (nenegativă) xn + m +1 , xn + m + 2 , ..., xn + 2m ,
© Blăjină Ovidiu Cap.1. Programare liniară 25/55
 Cercetare operațională – Cursul 2

cu semnul "+":
 a11x1 + a12 x2 +  + a1n xn − xn +1 + xn + m +1 = b1

 a21x1 + a22 x2 +  + a2 n xn − xn + 2 + xn + m + 2 = b2
 


 am1x1 + am 2 x2 +  + amn xn − xn + m + xn + 2 m = bm
Se modifică şi funcţia obiectiv a problemei iniţiale
(1) prin introducerea acestor variabile artificiale cu
coeficientul de penalizare +M.
Se consideră că M are o valoare pozitivă foarte
mare (practic infinit).
Rezultă problema extinsă (2) de mai jos:

© Blăjină Ovidiu Cap.1. Programare liniară 26/55

 Cercetare operațională – Cursul 2

 [min] z = c1 x1 +  + cn xn + Mxn + m +1 +  + Mxn + 2 m

 a11x1 + a12 x2 +  + a1n xn − xn +1 + xn + m +1 = b1

 a21x1 + a22 x2 +  + a2 n xn − xn + 2 + xn + m + 2 = b2
  (2)

 am1 x1 + am 2 x2 +  + amn xn − xn + m + xn + 2 m = bm
 x1, x2 ,..., xn , xn +1,..., xn + m , xn + m +1,..., xn + 2 m  0

Soluţia iniţială de bază pentru problema (2)

poate fi: x1 = x2 = ... = xn = xn +1 = xn +m = 0, xn +m +1 =
= -b1 , xn +m +2 = -b2 , xn +2m = -bm
Soluţia conţine variabilele artificiale, dar este
convenabilă pentru aplicarea algoritmului simplex
problemei (2).
© Blăjină Ovidiu Cap.1. Programare liniară 27/55
 Cercetare operațională – Cursul 2

Se rezolvă problema extinsă (2) fiind posibile

următoarele trei cazuri:
1) Problema (2) are optim infinit. Atunci şi
problema (1) are optim infinit.
2) Problema (2) are optim finit, dar în soluţia
optimă cel puţin o variabilă artificială are o valoare
nenulă (pozitivă). Atunci problema (1) nu are soluţie.
3) Problema (2) are optim finit şi în soluţia optimă
toate variabilele artificiale au valoarea nulă. Atunci
această soluţie, din care se ignoră variabilele artifi-
ciale, este soluţia optimă a problemei (1).

© Blăjină Ovidiu Cap.1. Programare liniară 28/55

 Cercetare operațională – Cursul 2

Fie problema de PL de maximizare:

 [max] z = c1 x1 + c2 x2 +  + cn xn
 a11 x1 + a12 x2 +  + a1n xn = b1
 (3)
 
 am1 x1 + am 2 x2 +  + amn xn = bm
 x ,..., x  0
 1 n
Presupunem că toţi termenii liberi sunt pozitivi:
b1  0,..., bm  0 şi că matricea A nu conţine nici un
vector coloană unitar.
Pentru a obţine o soluţie admisibilă de bază se
introduce în fiecare restricţie din (3) câte o variabilă
artificială (nenegativă), xn +1 , xn + 2 ,..., xn + m , cu
semnul "+".
© Blăjină Ovidiu Cap.1. Programare liniară 29/55
 Cercetare operațională – Cursul 2

Se modifică funcţia obiectiv a problemei (3)

prin introducerea acestor variabile artificiale cu
coeficientul de penalizare -M.
Rezultă problema extinsă:
 [max] z = c1 x1 +  + cn xn − Mxn +1 −  − Mxn + m
 a11x1 + a12 x2 +  + a1n xn + xn +1 = b1

 a21x1 + a22 x2 +  + a2 n xn + xn + 2 = b2
 
 (4)
 am1x1 + am 2 x2 +  + amn xn + xn + m = bm
 x1, x2 ,..., xn , xn +1,..., xn + m  0
Se rezolvă problema (4) fiind posibile aceleaşi
cazuri, relative la problema (3), ca cele prezentate
anterior la problema de minimizare (1).
© Blăjină Ovidiu Cap.1. Programare liniară 30/55
 Cercetare operațională – Cursul 2

Observaţii:
1) Indiferent de tipul problemei (minimizare sau
maximizare), dacă matricea restricţiilor nu conţine
vectori unitari, atunci numărul variabilelor artificiale
introduse va fi egal cu m.
2) Dacă, la aplicarea algoritmului simplex pentru
rezolvarea problemei extinse, o variabilă artificială
iese din bază, ea nu va mai intra niciodată în bază,
fapt care justifică eliminarea (eventuală) din calculele
ulterioare a coloanei variabilei respective.

© Blăjină Ovidiu Cap.1. Programare liniară 31/55

 Cercetare operațională – Cursul 2

Exemplu. Să se rezolve problema de PL cu metoda

coeficienţilor de penalizare:
 min (3x1 + 4 x2 + 7 x3 )
 x1 + 3x2 − x3  10
 x +x +x 6
 1 2 3
 x1, x2 , x3  0
Soluţie. Se aduce mai întâi problema la forma
standard prin introducerea în restricţii a variabilelor de
compensare x4 şi x5.
Se adaugă variabilele artificiale x6 şi x7; ele se
introduc în restricţii cu coeficientul 1 şi în funcţia
obiectiv cu coeficienţii de penalizare +M:
© Blăjină Ovidiu Cap.1. Programare liniară 32/55
 Cercetare operațională – Cursul 2

 min (3x1 + 4 x2 + 7 x3 + Mx6 + Mx7 )

 x1 + 3x2 − x3 − x4 + x6 = 10
x +x +x − x5 + x7 = 6
 1 2 3
 xi  0, i = 1, 7
Soluţia iniţială de bază este x1 = x2 = x3 = x4 = x5 = 0,
x6 = 10, x7 = 6. Primul tabel simplex al problemei
extinse corespunzător acestei baze este:

© Blăjină Ovidiu Cap.1. Programare liniară 33/55

 Cercetare operațională – Cursul 2

© Blăjină Ovidiu Cap.1. Programare liniară 34/55

 Cercetare operațională – Cursul 2

Deoarece zk - ck  0, k = 1,..., 7  tabelul simplex

de mai sus conţine soluţia optimă a problemei extinse,
în care variabilele artificiale x6 şi x7 au valoarea zero.
Soluţia optimă a problemei iniţiale: x1 = 4, x2 = 2,
x3 = 0. Valoarea optimă a funcţiei obiectiv zopt = 20.❑

© Blăjină Ovidiu Cap.1. Programare liniară 35/55

 Cercetare operațională – Cursul 2

4. Dualitate în programarea liniară

4.1. Probleme duale
4.2. Rezultate teoretice

© Blăjină Ovidiu Cap.1. Programare liniară 36/55

 Cercetare operațională – Cursul 2

4.1. Probleme duale

Fiecărei probleme de programare liniară i se
poate asocia o altă problemă de programare liniară,
construită cu aceleaşi date, numită problema duală
sau duala. În acest context, problema iniţială se
numeşte problema primală sau primala.
În esenţă, teoria dualităţii studiază relaţiile
teoretice existente între cele două probleme.
Asocierea primală-duală conferă un plus de
informaţie asupra problemei practice studiate cu
modelul programării liniare şi prezintă eventuale
avantaje calculatorii.
© Blăjină Ovidiu Cap.1. Programare liniară 37/55
 Cercetare operațională – Cursul 2

Regulile de construcţie a unei probleme duale:

a) Dacă în problema primală funcţia obiectiv se
maximizează (minimizează), în problema duală
funcţia obiectiv se minimizează (maximizează).
b) Coeficienţii funcţiei obiectiv din problema
primală devin termeni liberi în problema duală.
c) Termenii liberi din problema primală devin
coeficienţii funcţiei obiectiv în problema duală.
d) Matricea coeficienţilor sistemului de restricţii
duale este transpusa matricei coeficienţilor sistemului
de restricţii primale.
e) Variabila duală (primală) asociată unei restricţii
© Blăjină Ovidiu Cap.1. Programare liniară 38/55
 Cercetare operațională – Cursul 2

primale (duale) care este inegalitate concordantă este

supusă condiţiei de nenegativitate.
f) Variabila duală (primală) asociată unei restricţii
primale (duale) care este inegalitate neconcordantă
este supusă condiţiei de nepozitivitate.
g) Variabila duală (primală) asociată unei restricţii
primale (duale) care este o ecuaţie nu este supusă
nici unei condiţii privind semnul.
Observaţii:
1) Cele două probleme formează un cuplu de
probleme duale.
2) Duala problemei duale este problema primală.
© Blăjină Ovidiu Cap.1. Programare liniară 39/55
 Cercetare operațională – Cursul 2

3) Problema duală are atâtea variabile (restricţii)

câte restricţii (variabile) are problema primală.
4) Regulile de construcţie pot fi exprimate sintetic
sub forma următorului tabel de corespondenţe:

© Blăjină Ovidiu Cap.1. Programare liniară 40/55

 Cercetare operațională – Cursul 2

Exemplu. Un cuplu de probleme duale în care sunt

evidenţiate corespondenţele:

❑
© Blăjină Ovidiu Cap.1. Programare liniară 41/55
 Cercetare operațională – Cursul 2

Cupluri de probleme duale:

 min c x T  max b Tu
  T
 Ax = b (6)  A uc (7)
 x0  u arbitrar
 
 min c T x  max b Tu
  T
 Ax  b (8)  A uc (9)
 x0 u0
 
 min c T x  max (b1Tu1 + b2Tu 2 )
 A x  b  T 1
 1 1 (10)  1
A u + A 2u c
T 2
(11)
 A2 x = b2  u1  0, u 2 arbitrar

 x  0
© Blăjină Ovidiu Cap.1. Programare liniară 42/55
 Cercetare operațională – Cursul 2

4.2. Rezultate teoretice

Fără a restrânge din generalitate vom considera
un cuplu de probleme duale în forme canonice.
Se notează cu P şi Q mulţimile soluţiilor
admisibile (sau programelor) ale problemei primale,
respectiv, ale problemei duale.
Teoremă. Dacă x  P şi u  D, atunci cT x  bT u .
Teoremă. Fie x* P, u *D şi cT x* = bTu*. Atunci x*
este soluţie optimă a problemei primale, iar u este
*

soluţie optimă a problemei duale

© Blăjină Ovidiu Cap.1. Programare liniară 43/55

 Cercetare operațională – Cursul 2

Teoremă. (Teorema fundamentală a dualităţii)

Fie un cuplu de probleme duale în forma
canonică. Atunci una şi numai una din următoarele
situaţii este posibilă:
a) Ambele probleme au soluţii admisibile. În acest
caz, ambele probleme au soluţii optime şi valorile
optime ale funcţiilor obiectiv sunt egale.
b) Una dintre probleme are soluţii admisibile, iar
cealaltă nu are (este incompatibilă). În acest caz,
problema compatibilă are optim infinit.

© Blăjină Ovidiu Cap.1. Programare liniară 44/55

 Cercetare operațională – Cursul 2

Exemplu. Fie problema de PL. (primală):

 [max] f = x1 + x2
 3x1 − 2 x2  5
 x − 2x  1
 1 2
 x1, x2  0

Mulţimea soluţiilor
admisibile ale pro-
blemei este cea din
figura alăturată.
Problema are soluţie
optimă infinită.

© Blăjină Ovidiu Cap.1. Programare liniară 45/55

 Cercetare operațională – Cursul 2

Problema duală:
 [min] g = 5u1 + u2
 3u1 + u2  1 Restricţiile problemei sunt:
 − 2u − 2u  1
 1 2
 u1 , u2  0

Problema nu are soluţii

admisibile, deoarece a
doua restricţie nu poate
fi satisfăcută pentru
valori nenegative ale
variabilelor u1 şi u2 . ❑
© Blăjină Ovidiu Cap.1. Programare liniară 46/55
 Cercetare operațională – Cursul 2

Exemplu. Fie problema de PL (primală):

 [max] f = 3x1 + 7 x2
 4 x1 + 3x2  16
 x + 2x  6
 1 2
 x1, x2  0
Mulţimea soluţiilor
admisibile este cea din
figura alăturată.
Problema admite
soluţia optimă x1 = 0,
x2 = 3, pentru care
valoarea fmax = 21.
© Blăjină Ovidiu Cap.1. Programare liniară 47/55
 Cercetare operațională – Cursul 2

Problema duală:  [min] g = 16u1 + 6u2

 4u1 + u2  3
 3u + 2u  7
 1 2
 u1, u2  0

Mulţimea soluţiilor ad-

misibile este cea din
figura alăturată.
Problema duală admite
soluţia optimă u1 = 0,
u2 = 7/2; valoarea func-
ţiei obiectiv gmin = 21.❑

© Blăjină Ovidiu Cap.1. Programare liniară 48/55

 Cercetare operațională – Cursul 2

Observaţie: Prin rezolvarea unei probleme dintr-un

cuplu de probleme duale se poate determina şi soluţia
celeilalte. Tabelul simplex final corespunzător acelei
probleme conţine componentele soluţiilor optime ale
ambelor probleme.

Exemplu. Să se rezolve cuplul de probleme duale:

 [max] f = 5 x1 + 3 x2 + 2 x3  [min] g = 7u1 + 4u2 + 5u3
 2 x1 + 2 x2 + x3  7  2u1 + u2 + u3  5
 
 x1 − x2 + 2 x3  4  2u1 − u2 + 3u3  3
 x1 + 3x2 − x3  5  u1 + 2u2 − u3  2
 x,x ,x 0  u ,u ,u  0
 1 2 3  1 2 3
© Blăjină Ovidiu Cap.1. Programare liniară 49/55
 Cercetare operațională – Cursul 2

Soluţie. Se rezolvă, pe rând, problemele cu algoritmul

simplex şi se va evidenţia, în fiecare tabel simplex
final, şi soluţia optimă a problemei duale.
Problema de maximizare (primală) se aduce la
forma standard prin introducerea variabilelor de
compensare x4 , x5 , x6 :
 max (5 x1 + 3x2 + 2 x3 )
 2 x1 + 2 x2 + x3 + x4 =7

 x1 − x2 + 2 x3 + x5 =4
 x1 + 3x2 − x3 + x6 = 5
 x , ..., x  0
 1 6

© Blăjină Ovidiu Cap.1. Programare liniară 50/55

 Cercetare operațională – Cursul 2

Soluţia optimă a problemei primale este:

* * * * * *
x1 = 7 / 2; x2 = x3 = x4 = 0; x5 = 1 / 2; x6 = 3/ 2
© Blăjină Ovidiu Cap.1. Programare liniară 51/55
 Cercetare operațională – Cursul 2

Valoarea optimă a funcţiei obiectiv fmax = 35/2.

Soluţia optimă a problemei duale (de minimizare)
apare în tabelul simplex final, pe linia zj - cj , înce-
pând cu coloanele variabilelor de compensare şi
continuând cu primele coloane:
* * * * * *
= 5 / 2;
u1 = =
u2 = 0;
u3 = 2;u4 = 1/ 2 u5 u6
Problema duală este în forma canonică. Pentru a
o aduce în forma standard se introduc variabilele de
compensare, u4 , u5 , u6 , care nu determină, însă, o
matrice unitate. Pentru rezolvare se va utiliza metoda
coeficienţilor de penalizare, care introduce varia-
bilele artificiale u7 , u8 , u9 . Problema devine:
© Blăjină Ovidiu Cap.1. Programare liniară 52/55
 Cercetare operațională – Cursul 2

 min (7u1 + 4u2 + 5u3 + Mu7 + Mu8 + Mu9 )

 2u1 + u2 + u3 − u4 + u7 =5

 2u1 − u2 + 3u3 − u5 + u8 =3
 u1 + 2u2 − u3 − u6 + u9 = 2
 u , ..., u  0
 1 9

© Blăjină Ovidiu Cap.1. Programare liniară 53/55

 Cercetare operațională – Cursul 2

© Blăjină Ovidiu Cap.1. Programare liniară 54/55

 Cercetare operațională – Cursul 2

Soluţia optimă a problemei duale este:

* * * * * *
u1 = 5 / 2; u2 = u3 = u4 = 0; u5 = 2; u6 = 1/ 2
Valoarea optimă a funcţiei obiectiv gmin = 35/2.
Soluţia optimă a problemei primale apare în tabe-
lul simplex final, pe linia zj - cj , cu semne schimbate,
începând cu coloanele variabilelor de compensare şi
continuând cu primele coloane:
* * * * * *
x1 = 7 / 2; x2 = x3 = x4 = 0; x5 = 1 / 2; x6 = 3/ 2
Se constată că prin rezolvarea cuplului de proble-
me duale s-au obţinut aceleaşi soluţii. ❑

© Blăjină Ovidiu Cap.1. Programare liniară 55/55