Balanțe și optimizări în energetică 4

Definiţia 1: o soluţie admisibilă a problemei de programare liniară este un vector X=(X1, X2, ...,Xn) care satisface sistemul de acuaţii al restricţiilor de nenegativitate.

Definiţia 2: o soluţie admisibilă de bază este o soluţie admisibiă care conţine cel puţin n – m componente Xi care au valoarea zero.

n – numărul de variabile

m – numărul de ecuaţii ale sistemului de restricţii

Definiţia 3: o soluţie admisibilă de bază nedegenerată are exact m componenete ale vectorului X cu valoare pozitivă.

Definiţia 4: o soluţie optimală este o soluţie admisibilă care optimizează (maximizează sau minimizează) funcţia obiectiv.

Teorema 1: funcţia obiectiv îţi realizează optimul într-un punct extrem al mulţimii restricţiilor. Dacă îşi realizează optimul în mai mult de un punct extrem atunci funcţia obiectiv are aceeaşi valoare în fiecare punct de pe segmentul de dreaptă ce uneşte două puncte optimale.

Teorema 2: un vector X=(X1, X2, ...,Xn) este un punct extrem al mulţimii restricţiilor unei probleme de programare liniară dacă şi numai dacă X este o soluţie admisibilă de bază.

Pe baza celor enunţate o problemă de programare liniară adusă la forma standard are o soluţie care extremizează funcţia obiectiv, pentru una din soluţiile admisibile da bază ale sistemului de restricţii în prezenţa condiţiilor de nenegativitate.

Să considerăm sistemul de restricţii:

:alk

Pentru a aduce acest sistem la o formă din care se poate deduce direct o soluţie admisibilă de bază se efectuează o serie de operaţii elementare prin care se elimină pe rând o parte din necunoscute din toate liniile cu excepţia unei singure linii.

Să presupunem că am ales variabila Xk care se va elimina din toate ecuaţiile cu excepţia ecuaţiei l. Coeficientul pe care-l are variabila Xk în ecuaţia l se va numi element de pivot şi trebuie să fie diferit de zero (alk – elementul pivot ales în cazul nostru).

Pentru a elimina variabila Xk din toate celelalte ecuaţii vom proceda astfel:

 Se împarte ecuaţia prin elementul pivot alk;

 Ecuaţia l, în noua formă, o vom înmulţi succesiv cu coeficienţii a1k/a2k/.../amk;

 Şi o vom scade din ecuaţiile 1, 2 respectiv m.

În aceste fel variabila Xk va mai apare doar în ecuaţia l, iar sistemul va avea următoarea formă:

Coeficienţii sistemului vor suporta următoarele modificări:

(cazul nostru)

Curs 5 : Definiţii şi teoreme de bază ale programării liniare