Modele - optimizarea
Optimizarea cu ajutorul unui algoritm – programare matematică
Programarea matematică reprezintă un set de metode şi instrumente pentru rezolvarea
problemelor manageriale în care decidentul trebuie să aloce o cantitate limitată de
resurse mai multor activităţi în scopul optimizării valorii unui obiectiv (măsurabil).
Cea mai cunoscută şi des utilizată metodă o reprezintă programarea liniară care
presupune:
• un set de elemente măsurabile, valori pentru care se caută valoarea optimă –
variabilele de decizie;
• un set de restricţii asupra acestor variabile, care sunt reprezentate sub forma
unor relaţii (de egalitate sau inegalitate faţă de anumite valori) liniare - de
exemplu, într-o problemă de alocare a resurselor, cantitatea acestora este
limitată;
• o funcţie obiectiv – o relaţie matematică liniară între variabilele de decizie şi
scopul urmărit - a cărei valoare trebuie maximizată (mărimea profitului, de
exemplu) sau minimizată (nivelul costurilor, de exemplu);
• existenţa unor legături între toate aceste elemente, reprezentate prin relaţii
matematice (ecuaţii) în care intervin coeficienţi în cadrul modelului de
programare liniară
Modelul unei probleme de programare liniară se reprezintă astfel:
• determinarea min (max) unei funcţii obiectiv de una sau mai multe
variabile ale cărei valori trebuie sa satisfacă o mulţime (posibil vidă) de condiţii
implicite (ce apar sub forma unor ecuaţii şi/sau inecuaţii numite restricţii) sau
explicite (condiţii care se referă la felul valorilor pe care le pot lua variabilele).
• problemele de programare matematică sunt caracterizate de prezenţa
restricţiilor “inegalităti “ şi a condiţiilor explicite impuse cel puţin unora dintre
variabile.
Deosebim :
- probleme de programare liniară (relaţii liniare intre variabile). Rezolvarea
acestora se bazează pe algoritmul Simplex ([Link] 1947) care oferă o soluţie
optimă într-un număr finit de paşi.
- probleme de programare neliniară (există cel puţin o relaţie neliniară între
variabile). Metodele de rezolvare a acestor probleme oferă doar o aproximare a
soluţiei optime şi se pot clasifica în: metode de tip Simplex, metode provenite din
programarea dinamica, metode gradient.
Forma generala a modelului de programare liniara este:
(1) max (min) f(x1,x2,.......,xn) = c1x1 + c2x2 +.........cnxn
ìa11x1 + a12 x 2+...........................+ a1nxn £ b1
ï
ïa 21x1 + a 22 x 2+...........................+ a 2nxn ³ b2
ï
ï
(2) í
ï
ï
ï
ï
îam1x1 + am2 x 2+.........................+ amnxn £ bm
(1) funcţia obiectiv
(2) restricţii
Forma standard : toate restricţiile sunt ecuaţii şi toate variabilele sunt >=0
max(min) f(x) = cx
Ax = B
x >=0
Forma canonica : toate restricţiile sunt concordante şi toate variabilele sunt >=0
max f(x) = cx
Ax <= B min f(x) =cx
x>=0 Ax >=B
x >=0
Aceste probleme se rezolvă cu ajutorul unui algoritm – algoritmul SIMPLEX
(Dantzing 1951)– care constituie o procedură iterativă, la fiecare pas obţinându-se o
îmbunătăţire a soluţiei, oferind în final:
- soluţia admisibilă (satisface doar condiţiile explicite) SAU
- soluţia optimă
Există programe standard pentru rezolvarea problemelor de programare liniară (de
exemplu, în EXCEL, componenta SOLVER).
Problema 1
O companie producatoare de echipamente (4 tipuri de produse) doreste sa-si
eficientizeze planul de productie in luna urmatoare. Datele referitoare la costurile cu
materiile prime, resursa umana si cererea pentru produsele respective sunt cele din
tabelele de mai jos.
Date de intrare
salariu orar 8
cost unitar m1 0.5
cost unitar m2 0.75
produse p1 p2 p3 p4
ore munca/p 2 1 3 2
m1/p 4 2 1 2
m2/p 6 2 1 2
pret vanzare/p 28.5 12.5 29.25 21.5
Plan de productie
p1 p2 p3 p4
cerere 1000 2000 500 1000
utilizat disponibil
ore munca 4000
m1 6000
m2 10000
Determinati planul optim de productie