7. Programarea liniara

Notiuni fundamentale, interpretare geometrica si exemple de modelare

1. Modele de programare liniara

Programarea liniara studiaza optimizarea unei functii liniare in prezenta unor restrictii liniare. Un model raspunde la trei intrebari: ce decidem? , ce urmarim? si ce limite trebuie respectate?

max / min   z = c 1 x 1 + ... + c n x n
sub restrictiile   Ax ≤ b,   x ≥ 0

Aplicatii: planificarea productiei, transport, alocarea resurselor, amestecuri, planificarea personalului.

Ipoteze: proportionalitate, aditivitate, divizibilitate si coeficienti cunoscuti.

2. Variabile de decizie

Variabilele reprezinta marimile pe care le putem alege. Ele trebuie definite precis, impreuna cu unitatile de masura si domeniul lor.

Exemplu: O fabrica produce doua articole A si B.
x = numarul de unitati A produse;
y = numarul de unitati B produse.
Conditii: x ≥ 0, y ≥ 0.

Daca produsele nu pot fi fractionate, sunt necesare variabile intregi: se obtine o problema de programare liniara intreaga.

3. Functia obiectiv

Exprima criteriul de optimizare: profit maxim, cost minim, timp minim sau consum minim de resurse.

max z = 3x + 5y

Interpretare: fiecare unitate A aduce un profit de 3 unitati monetare, iar fiecare unitate B un profit de 5.

Coeficientii functiei obiectiv arata contributia marginala a fiecarei variabile, in ipoteza liniaritatii.

4. Restrictii si domeniul solutiilor

Restrictiile descriu capacitatile, bugetele, necesarul minim sau relatiile tehnologice.

x + y ≤ 4
x + 3y ≤ 6
x ≥ 0,   y ≥ 0

Solutie admisibila: orice pereche (x,y) care satisface toate restrictiile simultan. Domeniul admisibil: multimea tuturor acestor perechi; este o multime convexa.

Problema poate avea solutie optima unica, solutii optime multiple, domeniu vid sau obiectiv nemarginit pe domeniul admisibil.

5. Forma standard

Exista mai multe conventii. In conventia folosita aici, forma standard are restrictii de egalitate si variabile nenegative:

min c T x
Ax = b,   x ≥ 0

O restrictie de tip ≤ se transforma in egalitate prin adaugarea unei variabile de abatere nenegative:

x + y ≤ 4   ⇔   x + y + s 1 = 4,   s 1 ≥ 0

O problema de maximizare poate deveni una de minimizare prin schimbarea semnului functiei obiectiv. O variabila libera se poate scrie ca diferenta a doua variabile nenegative.

6. Interpretarea geometrica

Fiecare restrictie liniara determina un semiplan. Intersectia semiplanelor este poligonul admisibil (in doua variabile).

In cazul unui domeniu poliedral nevid si marginit, o functie liniara atinge un optim intr-un varf. Daca o latura este paralela cu dreptele de nivel ale obiectivului, pot exista infinit de multe solutii optime.

Pentru exemplul nostru, maximizam z = 3x + 5y .

Optim: (3, 1), z = 14

x y 0 1 2 3 4 1 2 3 4 (4,0) (3,1) (0,2) Regiunea colorata = domeniul admisibil

7. Exemple de modelare

Exemplul A: planificarea productiei

O intreprindere fabrica produsele A si B, cu profituri unitare 3 si 5. Exista doua resurse: prima permite cel mult 4 unitati totale, iar a doua este consumata cu 1 unitate de A si 3 unitati de B, cu disponibil 6.

max z = 3x + 5y
x + y ≤ 4
x + 3y ≤ 6
x, y ≥ 0

Rezultat: x = 3, y = 1, profit maxim z = 14.

Exemplul B: dieta la cost minim

Doua alimente F1 si F2 costa 2, respectiv 3 unitati pe portie. F1 furnizeaza 2 unitati de nutrient N1 si 1 de N2; F2 furnizeaza 1 de N1 si 2 de N2. Necesarul minim este de 8 unitati pentru fiecare nutrient.

min C = 2x + 3y
2x + y ≥ 8
x + 2y ≥ 8
x, y ≥ 0

Rezultat: x = 8/3, y = 8/3, cost minim C = 40/3.

Exemplul C: transport

Doua depozite trimit marfa catre doua magazine. Definim x ij = cantitatea transportata de la depozitul i la magazinul j.

min C = 2x 11 + 4x 12 + 3x 21 + x 22
x 11 + x 12 = 20
x 21 + x 22 = 30
x 11 + x 21 = 25
x 12 + x 22 = 25
x ij ≥ 0

Rezultat: x 11 = 20, x 12 = 0, x 21 = 5, x 22 = 25, cost minim C = 80.

Recapitulare

Modelarea incepe cu definirea variabilelor, continua cu formularea functiei obiectiv si a restrictiilor, apoi cu verificarea domeniului admisibil. Interpretarea geometrica explica de ce varfurile domeniului joaca un rol central in optimizarea liniara.