Clasificarea solutiilor probl de progr lin
Fie probl de progr lin data in forma standard matricial:
, unde
Sist de ec Ax=b are o infinitate de solutii, deci trebuie sa se gaseasca in multimea solutiilor o sol ce realizeaza valoarea optima (min sau max) a functiei obiectiv.
1.Solutie admisibila
Un vector x=(x1,x2,.,xn) E (R la n) care satisface restrictiile si conditia de nenegativitate se numeste solutie admisibila sau posibila a probl de progr lin.
Multimea solutiilor admisibile S este: S=
Sistemul de ec,avand m ec si n nec ,cu m<n si rang A=m are m nec principale si n-m nec secundare.O solutie de baza se obtine prin anularea celor n-m nec sec,deci are cel mult m comp nenule.
2.Solutia admisibila de baza
Se numeste solutie admisibila de baza pentru sist Ax=b, vectorul x^, ce satisface cond:
a)x^ solutie a sisiemului : Ax =b;
b)coloane1e din A,corespunzatoare componenetelor lui x^ nenule ,formeaza o multime liniar independenta
In cazul cand o solutie de baza are mai putin de m comp diferite de 0, atunci ea s.n. solutie degenerata,in caz contrar ea fiind nedegenerata.
3.Solutie optimala
O solutie admisibila care face optima
functia z=min(max) (c
Este posibila ca probl de progr lin sa aiba solutie optima unica ,sa aiba mai multe solutii optime sau sa nu admita solutie optima.
4.Solutie grafica
Realizand o analiza dpdv grafic putem observa :
a).egalitatea a11x1+a12x2=b1 reprez o dreapta.Multimea solutiilor (x1 x2) apartine acestei drepte (d),iar aceasta dreapta (curba de nivel) imparte planul (0 x1 x2) in 2 semiplane
b).inegalitatea a11x1+a12x2<b1 -multimea solutiilor fiind reprez in acest caz printr-o arie ,dreapta imparte planul (0 x1 x2)
in 2 semiplane ce au o arie comuna si in final un punct comun.
Ptr aflarea solutie optime,daca ea exista trebuie aflata mai intai multimea sol admisib S-multime ce satisface sist de restrictii si cond de nenegativitate.In reprezentarea grafica aceasta va fi o multime convexa reprezentata printr-un domeniu numit admisibil
Teorema .Daca probl de progr lin in forma standard admite un program (solutie admisibila),atunci ea are cel putin un program de baza.Daca probl are un progr optim ,atunci are un progr optim de baza.
|
