Cercetări Operaționale

PROGRAMARE LINIARA

1. Forma generala a unei probleme de programare liniara

Problemele de maxim si de minim apar frecvent în cele mai diferite domenii ale matematicilor pure sau aplicate. În domeniul economic, asemenea probleme sunt foarte naturale. Astfel, firmele încearca sa maximizeze profiturile sau sa minimizeze costurile. Expertii în planificare macroeconomica se preocupa de maximizarea bunastarii unei comunitati economico-sociale. Consumatorii doresc sa cheltuiasca venitul lor într-un mod care sa le maximizeze satisfactia (de natura materiala dar si spirituala etc.)

Programarea liniara se ocupa de o clasa speciala de probleme de optimizare care apar deseori în aplicatiile economice. Aceste probleme constau în maximizarea sau minimizarea unei functii liniare, numita functie obiectiv, ale carei variabile trebuie sa satisfaca:

- un sistem de relatii date sub forma unor ecuatii si / sau inecuatii liniare nestricte, denumite generic restrictii;

- cerinta de a lua numai valori numerice nenegative (³0).

1.1 Exemple

1) Problema firmei. Consideram un sistem de productie, de exemplu o firma, care produce n bunuri G1,G2,...,Gn utilizând pentru aceasta m categorii de resurse R1,R2,...,Rm (materii prime, forta de munca, capacitati de productie, combustibili si energie etc.). Adoptam ipoteza ca tehnologia de transformare a resurselor în bunuri este liniara în sensul ca:

- Pentru fiecare bun, consumul dintr-o anumita resursa este direct proportional cu cantitatea produsa.

- Consumurile dintr-o resursa sau alta nu se conditioneaza reciproc.

Fie atunci aij cantitatea din resursa i utilizata pentru producerea unei unitati din bunul Gj. Fie deasemeni bi cantitatea disponibila din resursa Ri si cj pretul (sau profitul) unitar al bunului Gj.

- Pretul unui bun nu depinde de cantitatea produsa si nici de situatia vânzarilor celorlalte bunuri.

Problema consta în determinarea unui program de fabricatie care sa maximizeze venitul (sau profitul) firmei.

Sa notam cu xj cantitatea din bunul Gj care urmeaza a fi produsa. Problema enuntata mai înainte devine:

Sa se gaseasca valorile numerice x1,x2,...,xn care maximizeaza functia:

cu satisfacerea restrictiilor:

si a conditiilor de nenegativitate:

Observatie: Ipotezele de liniaritate facute nu sunt verificate întotdeauna în practica. Ratiunea lor este dubla:

- conduc la modele matematice în general simple;

- pe baza modelelor liniare se pot formula concluzii calitative si legitati economice care îsi mentin valabilitatea - în anumite limite - si într-un context neliniar.

2) Problema dietei a devenit o ilustrare clasica a programarii liniare, fiind întâlnita în mai toate textele de specialitate. Ea se ocupa cu hranirea unei colectivitati, sa zicem un grup de militari, în cel mai economic mod cu conditia satisfacerii anumitor cerinte de nutritie. Mai concret, este vorba de a prepara un aliment complex pornind de la n sortimente de hrana F1,F2,...,Fn. Un numar de elemente sau principii nutritive N1,N2,...,Nm - proteine, glucide, grasimi calciu,etc. sunt avute în vedere în sensul ca alimentul combinat trebuie sa contina cel putin b1,b2,...,bm unitati specifice din fiecare. Sa presupunem cunoscute urmatoarele:

- cantitatea aij din principiul nutritiv Ni continuta într-o unitate din tipul de hrana Fj;

- pretul unitar cj al tipului de hrana Fj.

Notam cu x1,x2,...,xn cantitatile din felurile de hrana F1,F2,...,Fn care trebuie cumparate în vederea elaborarii dietei. Formal, x1,x2,...,xn vor trebui determinate astfel încât:

- costul al alimentelor cumparate sa fie minim.

- amestecul sa contina principiile nutritive N1,N2,...,Nm în cantitati cel putin egale cu b1,b2,...,bm, adica:

Din nou au fost tacit utilizate ipotezele de liniaritate întâlnite si în modelul precedent.

1.2 Solutii admisibile ale unei probleme de programare liniara

Consideram o problema de programare liniara (P) cu m restrictii egalitati si/sau inegalitati nestricte, n variabile si cu functia obiectiv f. Un ansamblu de n valori numerice care satisfac restrictiile se va numi solutie a programului (P). Daca în plus sunt verificate si conditiile de nenegativitate, ansamblul se numeste solutie admisibila. O solutie admisibila care maximizeaza sau minimizeaza - dupa caz - functia obiectiv se va numi solutie optima. Notând cu A multimea solutiilor admisibile , problema (P) se scrie: