Forma generala a problemei de programare liniara

Forma generala a problemei de programare liniara

Forma generala a unei probleme de programare liniara este:

O problema de programare liniara poate fi formulata si matriceal daca toate inecuatiile sistemului de restrictii au acelasi sens (conditie care poate fi usor indeplinita inmultind cu -1 inecuatiile (2.1.) sau (2.2.).

De exemplu, notand cu si problema din exemplul 1. Se scrie:

Forma standard a unei probleme de programare liniara este:

Orice problema de programare liniara poate fi adusa la forma standard si anume:

Toate inecuatiile din sistemul de restrictii pot fi transformate in egalitati adunand sau scazand (dupa caz) o serie de variabile nenegative numite variabile ecart sau de compensare.    In acest fel din matricea obtinem matricea obtinuta din la care s-au adaugat l vectori coloana cu toate elementele nule cu exceptia elementului situat pe linia j care este +1 pentru inecuatiile sau -1 pentru inecuatiile , iar vectorul devine obtinut din prin adaugarea a l componente nenegative si care reprezinta activitati fictive. Analog devine , adaugand la C, l componente nule.

Variabilele nenegative raman aceleasi, iar in locul variabilelor negative vom introduce noi variabile nenegative prin substitutiile

().

Variabilele care nu au semnul specificat se pot inlocui fictiv cu diferenta a doua variabile presupuse nenegative si anume:

, , , ().

Aceste modificari conduc la forma extinsa a problemei de programare liniara:

care este forma standard.

Exemplul 1. Sa se aduca la forma standard problema de programare liniara:

fara restrictii de semn

Pentru si care sunt negative facem substitutiile

iar variabilele si care nu au restrictii de semn se vor inlocui cu

Cu aceste inlocuiri sistemul de restrictii devine:

si

Pentru forma standard adaugam variabilele ecart , , si obtinem:

, , , , , , ,

, , , , ,

De mentionat ca in orice cerinta de optimizare maximul si minimul se pot inlocui reciproc, anume: