ALTE DOCUMENTE
|
|||||||||
4. Forme ale problemei de programate liniara
O problema de programare liniara este, un caz particular al problemelor de programare matematica si, tinand cont de forma oricarei functii liniare, se poate defini forma generala a problemei de programare liniara.
Functia liniara (1), notata cu z reprezinta functia obiectiv a problemei.
Relatiile (2) reprezinta sistemul de restrictii ale problemei, iar membrul stang al fiecarei relatii aste o functie liniara in variabele x1 .xn, la fel ca si functia obiectiv.
Problema de programare liniara consta in optimizarea unei functii liniare cu restrictii liniare.
A. Forma generala a problemei de programare liniara
(2)
unde:cjE R(j=1,n), aijE R (i=1,m; j=1,n), biE R (i=1,m)
Din analiza mai multor probleme de programare liniara deducem ca intr-o astfel de problema pot apare restrictii scrise sub forma de inegalitati sau egalitati, iar criteriul de optimizare ales impune in unele cazuri maximizarea iar in alte cazuri minimizrea functiei obiectiv.
Rezolvarea probl de progr lin presupune determinarea, valorilor variabilelor xi, care satisfac restrictiile si optimizeaza functia obiectiv a problemei.
B.Forma standard a problemei de programare liniara
O problema de progr lin este data sub forma standard daca toate restrictiile sale sunt date sub forma de ecuatii (egalitati) si tuturor variabilelor li se impun conditii de nenegativitate.
Probl de progr lin data in forma standard se scrie in mod explicit (3):
Probl de progr lin in forma standard poate fi scrisa si sub forma matriciala (4
unde (4)
unde c
Sistemul de restrictii liniare ( Ax=b ) poate fi un sistem compatibil, compatibil unic det sau nedet de m ecuatii si n nec. Pt ca problema de optimizare sa aiba sens,nr de ecuatii trebuie sa fie < decat nr de necun (m<n)(sistem compatibil nedet).
C.Forma canonica a problemei de progr lin
O restrictie a unei probl de progr lin se numeste concordanta (neconcordanta) daca pentru inegalitatea de tip>=(<=) functia obiectiv este minimizata sau respectiv ptr o inegalitate de tip <=(>=) functia obiectiv este maximizata.
O probl de progr lin este data sub forma canonica daca toate restrictiile sale sunt concordante si toate variabilele sunt supuse conditiei de nenegativitate.Probl de progr lin data in forma canonica se scrie in mod explicit (5):
(5)
Probl de progr lin in forma canonica poate fi scrisa si sub forma matriciala (6):
unde (5)
|
