Rezolvarea grafică a problemei de programare liniară reprezintă un prim pas în
înţelegerea conceptelor, termenilor şi modului în care se rezolvă problemele de
optimizare prin programare liniară.
Actuala simulare permite însuşirea de către student a:
Terminologiei utilizate în problemele de optimizare, cu precădere a celor
care pot fi rezolvate prin programare liniară.
Etapelor implicate în rezolvarea grafică a problemelor de programare liniară.
În acest context, folosind limbajele HTML5, PHP şi SVG a fost dezvoltată aplicaţia de mai jos
care:
Introduce terminologia aferentă.
Permite înţelegerea etapelor implicate.
Vizualizează grafic, în mod automat, aceste etape.
Animează elementele astfel încât ele să devină mai atractive şi să permită
dezideratele menţionate mai sus.
Permite reluarea procedurilor de câte ori este nevoie.
Permite utilizatorului să modifice parametrii de intrare astfel încât să
studieze diverse scenarii.
Scop
Programarea liniară este un procedeu de
optimizare matematică.
Optimizarea este procedeul prin care se găseşte
valoarea maximă sau minimă a unui obiectiv
(e.g. maximizarea beneficiului/profitului, minimizarea costurilor, etc.).
Problema de programare presupune maximizarea sau minimizarea unei funcţii obiectiv,
în timp ce sunt satisfăcute un număr de condiţii restrictive sau constrângeri.
Toate relaţiile unei probleme de programare liniară sunt funcţii liniare ale
variabilelor de decizie.
În cele ce urmează vom ilustra, pe baza unei probleme,
rezolvarea grafică a problemei de programare liniară.
Animaţia următoare rezumă etapele de rezolvare.
Etape de rezolvare
Problema
Fie următoarea problemă a produselor mixte.
Un producător doreşte să producă 2 tipuri de rame (R1 si R2),
folosind două tipuri de resurse (manoperă şi metal) şi având
următoarele date de intrare:
2.25 unităţi monetare profit rama tip 1.
2.60 unităţi monetare profit rama tip 2.
4000 ore manoperă disponibile.
2 ore manoperă / ramă tip 1.
1 ora manoperă / ramă tip 2.
5000 u.m. de metal.
1 u.m. metal /ramă tip 1.
2 u.m. metal /ramă tip 2.
Construcţia formei tabelare a problemei şi identificarea variabilelor de decizie
Rezolvarea problemei presupune parcurgerea mai multor paşi sau etape.
Un prim pas este elaborarea modelului matematic în care se identifică:
Variabilele de decizie,
uzual notate cu x1,
x2, etc.
Expresia funcţiei obiectiv,
uzual notată cu z
Restricţiile sau constrângerile problemei
Condiţiile de nenegativitate, deoarece valorile variabilelor de decizie trebuie să
fie şi mărimi fizice
Pentru aceasta este foarte utilă organizarea datelor problemei întro formă
tabelară, care permite apoi identificarea foarte uşoară a elementelor
menţionate mai sus.
Astfel vom nota cu R1 şi R2 tipul ramelor care trebuie produse pentru a obţine
profitul maxim.
Variabilele de decizie vor fi x1 şi x2, cantităţile
pe care nu le cunoaştem încă dar care vor trebui produse pentru a
obţine profitul maxim.
Manopera [ore]
Metal [u.m.]
Profit unitar [u.m.]
Var.dec. [buc]
R1
2
1
2.25
x1
R2
1
2
2.6
x2
Val.max.
4000
5000
x1 >= 0
x2 >= 0
Pe ultima linie a tabelului am introdus condiţia de negativitate. De ce?
Putem oare avea valori negative pentru cantităţile ramelor R1 şi R2?
Evident, răspunsul este nu. Mai mult, ar trebui impusă şi condiţia
ca aceste valori să fie întregi. Dar, pentru simplitate vom omite această
restricţie.
Dacă insă cantităţile rezultate nu sunt şi intregi,
va trebui să avem în vedere şi această restricţie.
Modelul matematic al problemei
Funcţia obiectiv:
z = 2.25*x1 + 2.6*x2 --> MAX
Restricţia 1:
2*x1 + 1*x2 <= 4000
Restricţia 2:
1*x1 + 2*x2 <= 5000
Cond.de nenegativitate:
x1 >= 0; x2 >= 0
Trasare şi marcare axe
Deoarece problema are doar două variabile de decizie, ea poate fi rezolvată grafic.
Astfel vom considera axa orizontală, uzual x, ca fiind axa x1 şi
axa verticală, uzual y, ca fiind axa x2.
Condiţia de nenegativitate ne limitează
doar la utilizarea primului cadran.
Figura alăturată ilustrează trasarea originii şi axelor Ox1 şi Ox2
Trasarea primei drepte a restricţiilor şi identificarea zonei
soluţiilor fezabile
Rezolvarea problemei continuă cu identificarea zonei soluţiilor fezabile.
Asa cum îi spune numele, zona soluţiilor fezabile este zona în care problema
are soluţii care respectă restricţiile problemei.
Pentru aceasta, vom lua pe rând fiecare restricţie în parte şi vom
transforma inecuaţiile în ecuaţii.
Paşii necesari sunt:
transformarea inecuaţiei a11*x1 + a12*x2 <= b1 în ecuaţie.
aflarea intersecţiilor cu axele (tăieturile):
Dacă x1 = 0 atunci x2 = b1/a12 = 4000/1=4000
Rezultă pct. A de coordonate (0,4000)
Dacă x2 = 0 atunci x1 = b1/a11 = 4000/2=2000
Rezultă pct. B de coordonate (2000,0).
Se trasează dreapta ce trece prin punctele A şi B
Se introduc coordonatele originii în ecuaţia primei restricţii
Deoarece 0 < 4000, originea se afla în zona fezabilă
Se haşurează zona fezabilă OAB.
Trasarea celei de-a doua drepte a restricţiilor şi identificarea zonei soluţiilor fezabile
Se introduc coordonatele originii în ecuaţia celei de a doua restricţii
Deoarece 0 < 5000, originea se afla în zona fezabilă
Se haşurează zona fezabilă OCD.
Stabilirea punctului de intersecţie al restricţiilor
Dreapta AB se intersectează cu dreapta CD în punctul E.
Pentru a afla coordonatele punctului E se rezolvă sistemul de ecuaţii: a11 * x1 + a12 * x2 = b1 a21 * x1 + a12 * x2 = b2
respectiv:
2 * x1 + 1 * x2 = 4000
1 * x1 + 2 * x2 = 5000
Rezultă punctul E de coordonate (1000,2000)
Stabilirea zonei soluţiilor fezabile ale problemei
Intersecţia celor două zone fezabile corespunzătoare celor două restricţii,
determină zona soluţiilor fezabile ale problemei, respectiv zona OCEB.
Soluţia sau soluţiile problemei se găseşte/găsesc în această
zonă, cel mai probabil pe contur.
Trasarea dreptei de izoprofit
Din ecuaţia profitului, respectiv: z = 2.25 * x1 + 2.6 * x2,
dacă se extrage x2 ca funcţie de x1 se observă că se cunoaşte panta dreptei, adică: x2 = -(c1/c2) * x1 + z/c2 = -0.86538461538462 * x1 + z/2.6
Astfel, cunoscând panta, se poate trasa o dreaptă paralelă cu dreapta profitului,
dreaptă numită dreaptă de izoprofit.
Pentru exemplificare, sunt trasate dreptele care trec prin punctele:
B (dreapta BG)
C (dreapta CF)
E (dreapta TF)
A (dreapta AH)
Şi apoi este animată dreapta de izoprofit.
Identificarea punctului de optim şi soluţiei problemei
Fiind o problemă de Maxim, ne interesează punctul cel mai indepărtat de origine.
Se observă ca acest punct este E de coordonate (1000,2000)
Înlocuind coordonatele acestui punct in expresia profitului se obţine:
