| CATEGORII DOCUMENTE |
Multimea sistemelor economice concrete si multitudinea problemelor conducerii acestora au creat o diversitate de reprezentari economico-matematice, denumite modele.
Varietatea acestora este determinata, in principal, de structura 'obiectului' analizat, de scopul cercetarii precum si de informatia disponibila.
Modelele de programare matematica si mai ales subclasa acestora - modelele de programare liniara - ocupa un loc deosebit de important, atat in teoria cat si in practica economica. Teoria economica a beneficiat de aportul abordarii interdisciplinare care a permis aprofundarea analizei eficientei maximale a sistemelor complexe, a permis descoperirea unor concepte noi ale optimului economic, a perfectionat metodele de cercetare si cunoastere iar practica economica s-a imbogatit cu un instrument deosebit de util analizei economice si fundamentarii deciziilor.
Structura modelului general de programare liniara se constituie in primul rand prin multimea de activitati care compun sistemul economic analizat, multimea de resurse utilizate precum si prin relatiile tehnico-economice dintre acestea. Legatura dintre activitati si resurse este determinata de tehnologia de fabricatie corespunzatoare fiecarei activitati Aj (j=1,,n) si poate fi caracterizata numeric prin vectorul coloana a(j) de componente (a1j, a2j, amj). Elementele se numesc coeficienti tehnici sau coeficienti de consum specific si arata ce cantitate din resursa Ri se consuma pentru producerea unei unitati din produsul (serviciul) Pj (ca rezultat al activitatii Aj). Toate 'tehnologiile' de fabricatie definite de vectorii coloana a(j) se pot organiza intr-o matrice A cu m linii si n coloane; fiecare linie se refera la o resursa Ri (i = 1,,m) si fiecare coloana se refera la o activitate Aj (j = 1,,n).
Notand cu xj (j = 1,,n) rezultatul activitatii Aj intr-o perioada data si cu bi (i = 1,,m) cantitatile disponibile din resursele Ri (i = 1,,m), se pot scrie matematic urmatoarele restrictii tehnico-economice:
sau A x b
unde A = 
; x = 
si b = 
Fiecare inecuatie/restrictie incorporeaza doua afirmatii:
a. cantitatea consumata dintr-o resursa nu poate depasi volumul disponibil (propozitie de logica economica)
b. consumul total Rij din resursa Ri pentru efectuarea activitatii Aj este proportional cu intensitatea acesteia, adica cu xj, deci Rij( = aij xj (ipoteza simplificatoare)
Sistemul de restrictii (1) realizeaza legatura dintre resurse si activitati prin intermediul celor m restrictii liniare.
Modelul problemei de programare liniara contine restrictii de tipul (1) precum si un criteriu de 'performanta' care sa permita evaluarea eficientei fiecarei activitati. In functie de scopul urmarit, putem alege drept criteriu de eficienta un indicator care masoara efortul, unul care masoara rezultatul sau un indicator exprimat ca raport intre rezultat si efort (sau efort pe rezultat).
Este evident ca eficienta maxima inseamna minimizarea efortului si maximizarea rezultatului, iar conceptul de optim se defineste, in acest caz, ca un program xI Rn care minimizeaza sau maximizeaza o functie obiectiv si, in acelasi timp, satisface toate restrictiile tehnico-economice.
Presupunand ca fiecare componenta a vectorului linie c = (c1, c2, , cn) masoara eficienta unei unitati din rezultatul activitatii Aj, atunci se poate introduce functia liniara:
f(x) = c1 x1 + c2 x2 + + cn xn
care evalueaza performanta oricarui program x.
Sintetizand, obtinem urmatorul program de programare liniara:
|
relatia (1),
unde f(x) = 
este denumita functia obiectiv de
eficienta a problemei, evalueaza eficienta/performanta
fiecarei variante de program x;
relatiile (2)
de tipul 
reprezinta restrictii de tip resurse; iar
restrictiile de tipul 
se refera la restrictii tehnico-economice de tip
calitativ (si ca urmare indicatorul bk este limita
inferioara impusa 'retetei optime';
relatia (3) xj 0 j = 1,,n, numita conditia de nenegativitate a variabilelor, asigura obtinerea unei solutii realizabile din punctul de vedere al logicii economice.
Dupa cum s-a aratat la inceput, structura concreta a unei aplicatii in economie este determinata in primul rand de obiectivul urmarit.
Astfel, in cazul problemei determinarii structurii sortimentale optime a productiei, se cunosc cantitatile disponibile (cantitatile de care se poate face rost pe perioada analizata) din fiecare materie prima , coeficientii tehnologici (aij reprezinta cantitatea din materia prima i necesara fabricarii unei unitati din produsul de tipul j), cantitatile maxime si minime ce pot fi produse din fiecare sortiment in perioada analizata si profiturile unitare ale fiecarui tip de produs. Se cere gasirea acelor cantitati xj care trebuie fabricate din fiecare tip de produs astfel incat sa se obtina profitul maxim, in conditiile nedepasirii disponibilurilor din fiecare resursa.
Pentru simplificarea modelului, se presupune ca pretul unui bun nu depinde de cantitatea produsa din acesta sau din celelalte, consumul din fiecare materie prima este direct proportional cu cantitatea produsa si, pentru fiecare bun, consumurile dintr-o resursa sau alta nu se conditioneaza reciproc.
Problema matematica echivalenta este:
In unele probleme, in loc de profiturile pj se cunosc veniturile unitare vj sau costurile unitare cj sau alt criteriu de eficienta, scopul fiind maximizarea venitului, minimizarea costurilor respectiv optimul indicatorului de eficienta respectiv, sau toate la un loc. De asemenea pot lipsi conditiile de limitare a productiei sau pot exista si alte conditii.
La o problema de programare operativa a productiei restrictiile se refera la o serie de masini (utilaje) cu care se executa produsele dorite, bi fiind disponibilul de timp al utilajului i pe perioada analizata iar aij timpul necesar prelucrarii unui produs de tipul j pe utilajul i, scopul fiind maximizarea productiei.
Ca urmare, modelul are forma:
Daca se doreste obtinerea unui meniu (retete furajere), care sa asigure necesarurile dintr-un numar de m substante esentiale organismului, avand la dispozitie un numar de n alimente, cunoscandu-se cantitatile din fiecare substanta pe care le contine o unitate de masura din fiecare aliment si costurile unei unitati de masura din fiecare aliment, putem scrie modelul:
Variabilele xj reprezinta, in acest caz,
cantitatea din fiecare aliment ce va intra in meniu iar f(x) = este costul total al
retetei definita de vectorul x.
Vom incheia exemplificarea cu prezentarea
modelului
amestecului optim de produse petroliere. Presupunem ca o
rafinarie dispune de n tipuri de benzine, prin amestecarea acestora
urmand sa obtina o benzina cu m caracteristici impuse
si la un pret minim posibil. O serie de caracteristici trebuie
sa fie indeplinite cu o limita inferioara (de exemplu cifra
octanica), altele cu o limita superioara (de exemplu densitatea
sau temperatura de fierbere) si altele cu egalitate (de exemplu cantitatea
necesara), aceste limite fiind
, i = 1,,m1 , 
, i = 1,,m2 respectiv 
, i = 1,,m3 cu m1 + m2 +
m3 = m. De asemenea, trebuie tinut cont de
cantitatile disponibile din fiecare benzina Di, i =
1,,n. Se cunosc caracteristicile fiecarei benzine disponibile, date
intr-o matrice A I Mm n, unde aij este valoarea
caracteristicii i pentru benzina j si preturile unitare ale
fiecarei benzine, notate pj, j = 1,,n. Daca notam
cu xj, j = 1,,n, cantitatile din fiecare benzina
care vor forma amestecul optim, atunci avem de rezolvat problema:
Programarea matematica
Se observa ca toate aceste probleme, cu toate ca reprezinta situatii economice total diferite, sunt aplicatii in sfera activitatii economice ale urmatoarei probleme de optimizare:
in care functiile f,gi : Rn R pot avea orice forma si proprietati (liniare, convexe, continui, diferentiabile etc) iar W poate fi orice submultime a lui Rn (continua sau discreta, marginita sau nemarginita, convexa sau neconvexa, finita sau infinita etc) si in care dorim sa gasim minimul sau maximul functiei f in variabilele xi care indeplinesc restrictiile 1.2 si 1.3. O astfel de problema se numeste problema de programare matematica.
Functia (1.1) se numeste functia obiectiv a problemei de optimizare. In aplicatiile economice, ea reprezinta criteriul de performanta urmarit: maximizarea beneficiului, maximizarea productiei marfa, minimizarea costului productiei, maximizarea gradului de incarcare al utilajelor sau minimizarea timpului de stationare al acestora, maximizarea veniturilor etc.
Inegalitatile (1.2), in care gi sunt functii de n variabile iar bi sunt constante, se numesc restrictii ale problemei de optimizare. Ele traduc in limbaj matematic conditiile de natura economica sau tehnologica in care se desfasoara procesul economic modelat, cum ar fi: nedepasirea stocurilor disponibile de resurse (materii prime, capacitati de productie, forta de munca, fonduri banesti, timp etc), indeplinirea sau depasirea unor indicatori economici (productia fizica, neta) etc.
Conditiile (1.3), impuse 'direct' variabilelor, depind de natura problemei studiate. De cele mai multe ori, W este multimea vectorilor x = (xl,,xn) I Rn cu toate componentele nenegative si acest fapt se justifica prin aceea ca, in general, xi reprezinta 'nivelele' unor activitati de productie, nivele care nu pot fi negative. In unele probleme de optimizare, cum ar fi cele de croire sau ordonantare, variabilele desemneaza marimi indivizibile si deci nu pot lua decat valori intregi. Multimea W va fi formata in acest caz din vectori x cu toate componentele intregi si nenegative. In alte probleme, ca de pilda cele de afectare, portofoliu etc, variabilele nu pot lua decat valorile 0 sau 1 (variabile bivalente) si ca atare W va fi formata din vectorii x = (x1, .,xn) cu toate componentele 0 sau 1. Caracteristic acestor tipuri de probleme este faptul ca W devine o submultime discreta din Rn, de unde si numele generic de probleme de optimizare discreta dat acestora.
O solutie a unei astfel de probleme are deci trei proprietati:
P1. verifica restrictiile 1.2
P2. verifica restrictiile 'directe' 1.3
P3. optimizeaza functia obiectiv pe multimea vectorilor care indeplinesc conditiile P1. si P2.
In teoria programarii matematice se folosesc, pentru claritatea si simplitatea expunerii, urmatoarele notiuni:
|
solutie a problemei de optimizare |
un vector x I Rn care verifica restrictiile 1.2 |
|
|
solutie admisibila a problemei de optimizare |
un vector x I Rn care verifica restrictiile 1.2 si 1.3 o solutie care verifica restrictiile 1.3 |
|
|
solutie optima a problemei de optimizare |
un vector x I Rn care verifica restrictiile 1.2 si 1.3 si optimizeaza functia obiectiv pe multimea tuturor vectorilor cu aceasta proprietate o solutie care verifica restrictiile 1.3 si optimizeaza functia obiectiv pe multimea tuturor solutiilor cu aceasta proprietate o solutie admisibila care optimizeaza functia obiectiv pe multimea solutiilor admisibile |
Izvorata din studiul problemelor extremale ale analizei matematice clasice, programarea matematica a cunoscut in ultimele decenii o dezvoltare spectaculoasa, explicabila numai in parte prin progresele inregistrate in matematica. Intr‑adevar, aceasta dezvoltare a fost puternic stimulata de cresterea vertiginoasa a complexitatii activitatilor economice, care a furnizat probleme cu structuri din ce in ce mai complicate, ca si de rapida perfectionare a mijloacelor automate de calcul, singurele capabile sa testeze eficienta practica a metodelor teoretice elaborate. La randul ei, programarea matematica, prin rezultatele ei, a adus un considerabil aport la perfectionarea metodelor de conducere in economie si a impulsionat cercetarile ‑ in plan teoretic ‑ privind modelarea sistemelor economice complexe, studiul si interpretarea legilor si proceselor economice.
In ceea ce priveste rezolvarea acestor probleme, este evident ca varietatea extrema a acestora face imposibila gasirea unui algoritm practic care sa le poata rezolva pe toate, dar putem gasi (sau ne putem astepta sa gasim), pentru fiecare caz particular, un algoritm de rezolvare care sa-si traga eficacitatea tocmai din folosirea tuturor particularitatilor cazului respectiv. In prezent exista sute de algoritmi de rezolvare, cercetarea problemei evoluand din ce in ce mai mult spre testarea si imbunatatirea acestora decat spre gasirea unora noi.
Problema de programare liniara
Definitia Daca intr-o problema de programare matematica functia obiectiv f si functiile gi, din restrictiile 1.2, sunt functii liniare atunci problema se numeste problema de programare liniara. O problema de programare liniara este, deci, un caz particular al problemelor de programare matematica si, tinand cont de forma oricarei functii liniare, rezulta ca forma generala a oricarei probleme de programare liniara este:
unde cj (coeficientii functiei obiectiv), aij (coeficientii restrictiilor) si bi (termenii liberi) sunt constate reale.
Forma conica si forma standard a unei probleme de programare liniara
Cu toate ca problema de programare liniara este cea mai simpla dintre problemele de programare matematica, ea este inca destul de complicata, prin faptul ca orice restrictie poate avea trei forme diferite iar obiectivul poate fi minimizarea sau maximizarea functiei f. Este putin probabil ca exista un algoritm si simplu si aplicabil la toate cazurile.
Din acest motiv este mult mai simplu sa gasim o anumita forma (cat mai simpla) cu proprietatea ca pentru orice problema P, exista o alta problema P' de aceasta forma, echivalenta cu problema initiala P (spunem ca doua probleme sunt echivalente daca exista un izomorfism intre multimile solutiilor celor doua probleme si un homeomorfism intre functiile lor obiectiv) si sa dispunem de un algoritm care sa rezolve problemele de aceasta forma si de o regula prin care sa gasim solutia problemei initiale P din solutia problemei P', gasita cu acest algoritm.
In acest sens (dar si din cauza frecventei aparitiei lor in practica) s-au evidentiat doua forme ale problemelor de programare liniara, forma canonica si forma standard.
Definitia 2. Spunem ca o problema este la forma canonica daca are una din urmatoarele doua forme:
|
Forma canonica de minim |
Forma canonica de maxim |
|
|
|
Aceasta forma este cel mai des intalnita in practica (vezi problema determinarii structurii sortimentale optime a productiei sau problema dietei) si, in plus, restrictiile economice sunt in general inegalitati si foarte rar egalitati. De asemenea, aceasta forma este invarianta la anumite transformari (vezi problema duala) si asigura existenta solutiei (orice problema la aceasta forma, care are termenii liberi si coeficientii restrictiilor pozitivi, are solutie).
Definitia 3. Spunem ca o problema este la forma standard daca are forma:
Aceasta forma, desi nenaturala din punct de vedere economic, este cea care se preteaza cel mai bine la rezolvarea cu metodele algebrei clasice.
Propozitie Pentru orice problema de programare liniara P exista o problema la forma canonica PFC si o problema la forma standard PFS echivalente cu P.
Demonstratie. Intr-adevar:
a) orice problema de maxim poate fi transformata in una de minim si reciproc folosind relatia:
max f(x) = - min f(-x)
b) orice restrictie de tipul ' ' poate fi transformata intr-o restrictie de forma ' ' si reciproc folosind relatia:
a b -a b
c) orice restrictie inegalitate poate fi transformata in egalitate, prin introducerea unei variabile suplimentare nenegative si folosind relatiile:
a b 
si a b 
Toate variabilele introduse pentru transformarea inegalitatilor in egalitati se numesc variabile de abatere sau variabile de compensare.
d) orice restrictie egalitate poate fi transformata in restrictii inegalitate, folosind relatia:
a b 
e) orice variabila cu restrictie de semn negativa (x 0) poate fi inlocuita cu o variabila cu restrictie de semn pozitiva (y 0), folosind relatia:
x 
f) orice variabila fara restrictie de semn poate fi inlocuita cu doua variabile cu restrictie de semn pozitiva, folosind relatia:
x oarecare 
Se demonstreaza fara un efort matematic deosebit ca daca P' se obtine din P folosind doar transformarile de mai sus (numite si transformari elementare) atunci P si P' sunt doua probleme echivalente si intre solutiile lor optime exista o bijectie.
Din cele de mai sus rezulta cum poate fi adusa orice problema de programare liniara la forma standard (sau canonica) si cum se obtine solutia problemei initiale din solutia problemei la forma standard (sau canonica).
Exemplu: Problemei P de mai jos ii corespunde problema la forma standard PFS alaturata:
|
P |
PFS |
|
(min) f = 3x1 -2x2 + 4x3
|
(max) g = +3a1 + 2y2 - 2z2 - 4x3
|
Problema PFS are o singura solutie optima:
a1 = 3, y2 = 
, z2 = 0, x3 = 0, x4 = 
, x5 = 0, x6 = 
, x7 = 0
care da
un maxim al functiei g egal cu 
.
Acestei solutii ii corespunde singura solutie optima pentru P:
x1 = -3, x2 = , x3 = 0
care da
un minim al functiei f, egal cu 
.
Rezolvarea problemei de programare liniara.
Analiza problemei
Fie o problema P despre care presupunem (fara a restrange generalitatea) ca a fost adusa la forma standard. De asemenea presupunem (tot fara a restrange generalitatea) ca variabilele problemei au fost numerotate si denumite xj cu j = 1,,n (n = numarul de necunoscute), coeficientii variabilelor din functia obiectiv f cu cj (cj = coeficientul variabilei xj), ca in ecuatii variabilele apar in ordinea indicilor, ecuatiile fiind numerotate de la 1 la m (m = numarul de ecuatii) si ca am notat cu bi termenul liber al ecuatiei i si cu aij coeficientul variabilei j din ecuatia i. In acest caz putem aseza variabilele problemei intr-un vector cu n componente, coeficientii functiei obiectiv intr-un vector cu n componente, termenii liberi intr-un vector cu m componente, coeficientii variabilelor din ecuatii intr-o matrice cu m linii si n coloane si vom avea:
x = , c = 
, b = , A =
(vom nota cu xT, cT si bT transpusii acestor vectori si cu AT transpusa matricei A).
Alegerea asezarii ca vectori coloana a fost facuta din ratiuni de usurinta a calculelor si a memorarii acestora. Dupa aceste notatii, problema poate fi scrisa mult mai simplu:
sau 
Se stie ca un sistem de
forma A x = b are solutie doar daca
rang(A) = rang(
), unde este matricea
extinsa obtinuta adaugand matricei A vectorul b, in acest
caz sistemul devenind echivalent cu sistemul obtinut prin eliminarea
restrictiilor care nu corespund minorului principal (daca sistemul nu
are solutie atunci evident nici problema nu are solutii, caz care
este total neinteresant).
Presupunem ca au fost eliminate aceste restrictii. Daca rang A = n atunci sistemul are o singura solutie care, daca este admisibila, este si solutia optima cautata, altfel problema nu are solutie. Este evident ca si acest caz este la fel de neinteresant ca primul.
Presupunem deci in continuare ca:
rang(A) = m < n
Rezolvarea sistemului A x = b se poate face intr-un mod simplu (cel putin teoretic) folosind algebra matriciala astfel:
impartim coloanele matricei A in doua submatrici: minorul principal (notat cu B, care este o matrice patratica de dimensiune m si va fi numit baza a sistemului) si restul coloanelor (notat cu S, care este o matrice cu m linii si n - m coloane);
impartim variabilele problemei in doi vectori: vectorul variabilelor principale (corespunzatoare coloanelor bazei) si vectorul variabilelor secundare (notat cu xS). Facand eventual o renumerotare, pentru usurinta expunerii si fiind evident ca nu se restrange generalitatea problemei, presupunem ca variabilele principale sunt chiar primele m (aceasta presupunere va fi facuta de cate ori va fi posibil, fara a mai specifica acest lucru).
aducem succesiv sistemul la forma de mai jos:
A x = b (BS) 
= b B xB + S xS
= b B xB = b - S xS xB
= B-1 b - B-1 S xS
solutia sistemului va fi submultimea lui Rn:
DB = / xS I Rn-m oarecare, xB = B-1 b - B-1 S xS}
Orice alegere a lui xS da o solutie. Dintre toate alegerile posibile este remarcabila (prin simplitatea ei) solutia xS = 0, care duce la solutia particulara:
xB = 
numita solutia de baza asociata bazei B. Deci xB este xB = B-1 b la care se adauga n-m zerouri. Cu toate acestea, vor fi ambele numite solutie de baza, rezultand din context de care este vorba.
Observatie: Este evident ca fiecarui minor principal al sistemului (= minor de dimensiune m = baza) ii corespunde o unica solutie de baza. O solutie de baza care are toate componentele nenule strict pozitive se va numi solutie de baza admisibila iar o solutie optima care este de baza se va numi solutie optima de baza. Se observa ca o solutie de baza are cel mult m componente diferite de 0. Din cauza importantei lor in rezolvarea problemei, vom evidentia solutiile de baza care au mai putin decat m componente nenule, numite solutii degenerate si pe cele care au fix m elemente nenule, numite solutii nedegenerate.
DB este izomorfa cu Rn, adica are tot atatea elemente cate puncte sunt intr-un spatiu cu n_- m dimensiuni. 'Alegandu-le' din acestea doar pe cele cu toate elementele pozitive, gasim multimea in care vom 'cauta' vectorul (vectorii) care da (dau) extremul lui f.
Rezolvarea problemei poate duce la urmatoarele rezultate:
R1. Sistemul A x = b nu are solutii sau nu are solutii admisibile. In acest caz problema nu are solutie.
R2. Imaginea functiei obiectiv pe multimea solutiilor admisibile este nemarginita (la + intr-o problema de maxim sau la - intr-o problema de minim). In acest caz spunem ca problema are optim infinit.
R3. Imaginea functiei obiectiv pe multimea solutiilor admisibile este marginita. In acest caz problema are cel putin o solutie si spunem ca problema are optim finit.
Greutatea gasirii solutiei problemei consta in imensitatea numarului de solutiilor posibile ale sistemului si in respectarea conditiei de nenegativitate a celor printre care cautam extremul dorit al functiei f. Este natural ca primele incercari in rezolvare sa caute in primul rand o limitare cat mai puternica a locului in care cautam. Pe baza unor reprezentari geometrice ale problemei au fost descoperite urmatoarele proprietati ale problemei, care poarta denumirea de teoreme fundamentale ale programarii liniare:
Teorema 1. Daca problema de programare liniara are solutii admisibile atunci are si solutii de baza admisibile.
Teorema 2. Daca problema de programare liniara are solutii optime atunci are si solutii optime de baza.
Teorema 3. Multimea solutiilor admisibile (optime) este inchisa si convexa. Daca este si marginita atunci punctele extremale ale acesteia sunt chiar solutiile admisibile (optime) de baza ale problemei.
Cele doua teoreme realizeaza
efectiv trecerea catre o problema rezolvabila pe calculator.
Intr-adevar, deoarece o baza este un minor de ordinul m al matricii A
si unei baze ii corespunde o unica solutie de baza
rezulta ca sunt cel mult 
solutii de baza, adica un numar finit. In
acest moment s-ar parea ca nu avem decat sa lasam
calculatorul sa calculeze toate solutiile de baza si
valorile functiei obiectiv in cele admisibile gasind-o prin comparare
pe cea care da minimul sau maximul functiei printre acestea.
Totusi, aceasta varianta se dovedeste nepractica la o
analiza mai atenta, tinand cont de urmatoarele
observatii:
faptul ca
numarul solutiilor de baza este finit ne asigura doar
ca problema se va termina candva, ceea ce, din punct de vedere economic,
este evident nemultumitor. Noi dorim ca problema sa fie
rezolvata in timp util, adica repede. Rezolvand problema ca mai sus
vom avea, pentru o problema cu 50 variabile si 20 restrictii, de
calculat, listat si comparat 
solutii de
baza, adica in jur de 1020. Presupunand ca suntem
dotati cu un supercalculator care ar termina un miliard de baze pe
secunda, rezolvarea ar dura 3000 ani. De altfel, o problema ca cea de
sus este foarte mica in comparatie cu problemele 'serioase'
ce au peste 1000 de variabile si 100 de restrictii. In plus, un
calculator ca cel de sus nu exista inca, deci in nici un caz nu e
disponibil intreprinderilor obisnuite.
Cu algoritmul de mai sus vom gasi cea mai buna solutie dintre solutiile admisibile de baza, fara insa sa stim daca problema admite, de fapt, optim (ar putea sa aiba optim infinit).
Nu vom sti daca un minor de m m este baza decat dupa ce-i vom calcula determinantul si nu vom sti daca solutia de baza corespunzatoare este admisibila decat dupa ce o vom calcula.
Solutia optima, odata gasita, nu va fi recunoscuta ca atare decat dupa ce vom calcula toate celelalte solutii de baza, chiar daca ea a aparut chiar la inceputul calculelor.
In concluzie, pentru a fi eficient, un algoritm ar trebui sa aiba urmatoarele proprietati:
a) sa dispuna de un criteriu de recunoastere a faptului ca problema nu are solutii admisibile;
b) sa dispuna de un criteriu de recunoastere a faptului ca problema are optim infinit;
c) sa dispuna de un criteriu de recunoastere daca o solutie este optima sau nu;
d) sa treaca de la o solutie de baza admisibila la una cel putin la fel de buna (o solutie x este mai buna decat o solutie y daca f(x) > f(y) intr-o problema de maxim si f(x) < f(y) intr-o problema de minim;
e) sa treaca de la o solutie la cea mai buna dintre solutiile cel putin la fel de bune posibile ca succesoare;
f) sa nu revina la o solutie deja analizata;
g) sa efectueze un numar de iteratii comparabil polinomial cu dimensiunea problemei.
h) sa nu introduca erori de rotunjire (sau nu prea mari);
i) sa fie cat mai simplu de implementat;
Conditiile de mai sus reprezinta de fapt un algoritm ideal. La inceputurile cercetarii operationale era suficient, de fapt, si un algoritm care sa indeplineasca macar conditiile b), c), d), e) si h). Acest algoritm a fost dat de G.B. Dantzig, in 1947, care la numit algoritmul simplex. El ramane si in zilele noastre cel mai eficient algoritm in ceea ce priveste viteza de lucru, simplitatea si implementarea pe calculator, pentru problemele care apar efectiv in practica economica.
Totusi, el nu indeplinea conditiile a), f) si g).
Conditia a) este relativ usor de indeplinit si ea este acoperita prin introducerea unei faze initiale suplimentare la algoritmul simplex, rezultand algoritmul simplex in doua faze.
Conditia f) a fost pusa in momentul in care s-a observat ca, in conditiile existentei solutiilor degenerate, se poate ajunge in situatia cand, de la o solutie data, nu se poate ajunge decat la una la fel de buna si tot asa, astfel incat, daca nu se iau masuri de evitare, se poate ajunge la o solutie care a mai fost, fenomen numit ciclare. Astfel de exemple a fost efectiv gasite, unul fiind exemplul lui Beale prezentat mai jos:
Se observa imediat baza
admisibila B0 = (a1,a2,a3), de
la care, aplicand algoritmul sub forma clasica, se vor obtine
succesiv bazele admisibile B1 = (a4,a2,a3),
B2 = (a4,a5,a3), B3 = (a6,a5,a3),
B4 = (a6,a7,a3), B5 = (a6,a2,a3),
B6 = (a4,a2,a3) . Cititorul
poate verifica usor ca toate aceste baze au ca solutie de
baza solutia (0,0,1,0,0,0,0) si valoarea functiei 0, dar nu
indeplinesc conditia de optim. Pe de alta parte se vede ca B6
= B1 si deci algoritmul va repeta la infinit aceasta
succesiune de baze, neatingand niciodata valoarea maxima 
, corespunzatoare solutiei (
,0,0,1,0,1,0).
Aceasta situatie este ingrijoratoare nu atat din considerente practice imediate (inca nu a fost gasita o problema din practica la care sa apara acest fenomen, toate exemplele existente fiind artificial construite, ca si cel de mai sus) cat din faptul ca un algoritm implementat pe calculator s-ar putea sa fie pus in fata unei astfel de probleme, situatie in care n-am putea rezolva problema nici pe calculator, nici manual, ea fiind prea mare. Situatia a fost depasita prin diferite tehnici suplimentare adaugate celei de trecere la o solutie cel putin la fel de buna (insuficienta, cum s-a vazut), cea mai cunoscuta fiind cea care foloseste ordonarea lexicografica a solutiilor, care va fi prezentata si in aceasta carte.
In fine, referitor la conditia g), a durat mult timp pana s-a demonstrat ca algoritmul, sub aceasta forma, nu este in timp polinomial, un exemplu fiind clasa de probleme de mai jos, gasita de Klee si Minty in 1972, in care algoritmul trebuie sa analizeze 2n baze (n = numarul de necunoscute) pana la gasirea celei optime.
Pentru o astfel de problema, la 100 de variabile, algoritmul va avea 2100 1030 iteratii, si chiar la o viteza de un miliard iteratii pe secunda (mult peste puterea unui calculator actual) va termina in 1013 ani.
Nu se stie inca daca exista sau nu o alta modalitate de trecere de la o baza la alta, folosind tabelele simplex, prin care algoritmul sa devina in timp polinomial. Au fost insa gasiti algoritmi care nu folosesc tabelele simplex, primul fiind algoritmul de punct interior al lui Karmakar, despre care s-a demonstrat ca lucreaza in timp polinomial.
In ceea ce priveste erorile de rotunjire, inevitabile cand se fac calculele pe un calculator, algoritmul se comporta intr-adevar foarte rau, orice eroare propagandu-se imediat la tot tabelul cu efecte foarte mari. Acest lucru poate fi insa depasit aplicand o varianta a algoritmului, numita varianta revizuita a algoritmului simplex.
Toate punctele slabe ale algoritmului, amintite mai sus, nu au inmormantat insa algoritmul simplex, deoarece folosirea acestuia aduce informatii mult mai ample decat gasirea solutiei propriu-zise, este mult mai maleabil in cazul modificarilor ulterioare ale datelor problemei (vezi analiza senzitivitatii solutiei la datele problemei), se preteaza mult mai bine la interpretari economice, este usor de scris un program de calculator asociat, este implementat pe foarte multe calculatoare si in plus, asa cum aminteam mai sus, inca nu a aparut o problema practica in fata caruia sa clacheze. Noii algoritmi raman doar ca alternative teoretice sau pentru cazurile in care algoritmul simplex este lent, dar ei nu-l pot inlocui complet.
Fundamentarea matematica a algoritmului simplex
Algoritmul simplex pleaca de la presupunerea ca dispunem deja de o solutie admisibila de baza xB, corespunzatoare unei baze B. De asemenea, presupunem ca am rezolvat sistemul A x = b folosind aceasta baza, rezultand astfel variabilele principale in functie de cele secundare:
xB = B-1 b - B-1 S xS
Inlocuind variabilele, cu formula gasita, in functia obiectiv, obtinem:
f(x) = 
(B-1 b - B-1 S xS) + 
xS = B-1 b - ( B-1 S - ) xS =
= f(xB) - ( B-1 S - ) xS = f(xB) - (z- ) xS = f(xB) - D xS
unde:
f(xB) = B-1 b este valoarea functiei
obiectiv in solutia de baza
B-1 S = z este un vector n-m componente z = (zm+1, zm+2,,zn).
D = z - este un vector n-m
componente D Dm+1 Dm+2 Dn
Obtinem urmatoarea forma a problemei:
Din motive de organizare si concentrare a datelor problemei, Danzig le-a trecut pe acestea intr-un tabel ca cel de mai jos, numit tabel simplex.
|
|
|||
|
cB |
xB |
xB |
x1 x2 xm xm+1 xn |
|
c1 c2
cm |
x1 x2
xm |
B-1 b |
Im B-1 S |
|
f(xB) |
0 zm+1 zn |
||
|
0 Dm+1 Dn |
Fiecarei solutii de baza ii corespunde un tabel simplex si reciproc, deci, de fiecare data cand vom vorbi de un tabel simplex, vom spune si care este baza asociata.
Din forma functiei obiectiv se vede ca:
intr-o problema de maxim
xB este solutie optima 
oricare ar fi xS
0 oricare ar fi xS Dj 0, j = 1,,n (toti Dj sunt pozitivi
intr-o problema de minim
xB este solutie optima 
oricare ar fi xS
0 oricare ar fi xS Dj 0, j = 1,,n (toti Dj negativi
Pentru a evita complicarea expunerii vom presupune in continuare ca problema este de maxim, pentru cazul de minim rationamentul fiind analog.
Rezultatul obtinut reprezinta criteriul de recunoastere a optimalitatii solutiei sau, mai simplu, criteriul de optim.
Daca solutia nu este optima atunci exista evident o alta solutie de baza admisibila mai buna. Se poate demonstra ca daca x si y sunt doua solutii admisibile de baza cu f(x) f(y) si numarul de variabile principale prin care difera cele doua este k, cu 1 k m, atunci exista un sir de solutii admisibile de baza: astfel incat:
f(xi) f(xi+1) oricare ar fi 1 i < k
xi difera de xi+1 printr-o singura variabila, oricare ar fi 1 i < k
Din cele de mai sus rezulta ca e suficient sa cautam o solutie de baza admisibila mai buna doar printre cele care difera de cea actuala printr-o singura variabila.
Trebuie deci sa gasim acea variabila principala care iese din baza si acea variabila secundara care intra in baza. Rezultatul schimbarii trebuie sa fie:
o solutie de baza (deci coloanele corespunzatoare noii variabile sa formeze un minor principal);
o solutie admisibila (adica sa aiba toate componentele pozitive);
o solutie mai buna;
cea mai buna posibila dintre solutiile mai bune.
Presupunem ca inlocuim variabila principala xi (1 i m) cu variabila secundara xj (m+1 j m). Aceasta este echivalent cu a scoate din ecuatia i (singura in care apare xi) variabila xj, in functie de variabila xi si de celelalte variabile secundare. Este evident ca acest lucru (care este echivalent cu faptul ca noua solutie trebuie sa fie de baza) este posibil doar daca coeficientul lui xj din aceasta ecuatie este diferit de 0 (aij ). In acest caz avem succesiv:
xi + 
+ aij xj
= xi xj + 
+ 
xi = xi
xj = xi -- xi
Inlocuind variabila xj in celelalte ecuatii obtinem:
xs + 
+ asj ( xi - 
- xi ) = xs
xs +
- 
xi = xs - xi pentru s = 1,,m si s i
Conform formulelor de mai sus rezulta ca noua solutie de baza este admisibila daca:
xs - xi 0 oricare ar fi s =1,,m diferit de i 
oricare ar fi s
=1,,m, s i
si in urma schimbarii noua solutie de baza va fi:
= xi si 
= xs - xi pentru s i
In concluzie, daca ne hotaram sa introducem in baza variabila j, singura variabila care o poate inlocui (pentru ca noua solutie sa fie admisibila de baza) nu poate fi decat aceea care corespunde acelui aij strict pozitiv din coloana j din matricea B-1 S, pentru care se obtine valoarea minima a rapoartelor dintre componentele solutiei de baza actuale si componentele coloanei j. Pentru evidentierea acestora, ele se noteaza cu qs si avem:
qi = 
Conditia de mai sus este numita criteriul de iesire din baza.
Mai inainte am vazut ce efect are schimbarea unei variabile din baza asupra sistemului. Este important insa sa vedem efectul ei si asupra functiei obiectiv. Valoarea functiei obiectiv in noua solutie de baza va fi:
f(
) = 
= 
Pentru ca aceasta solutie sa fie cel putin la fel de buna trebuie ca:
f() f(xB) 
f(xB) 
Dj
In concluzie, daca vrem sa
obtinem o solutie strict mai buna vom alege o variabila xj
corespunzatoare unui Dj < 0. Noua solutie va exista efectiv doar daca pe coloana
j din matricea B-1 S
exista o componenta aij strict pozitiva si va fi
efectiv strict mai buna doar daca componenta corespunzatoare xi din solutia de
baza este diferita de 0, imbunatatirea fiind
egala cu 
.
Situatia in care toate componentele coloanei j din matricea B-1 S sunt mai mici sau egale cu 0 este lamurit de urmatoarea teorema:
Teorema: Daca pe coloana j din matricea B-1 S, corespunzatoare unei variabile xj cu Dj < 0, toate componentele sunt mai mici sau egale cu zero atunci problema are optim infinit.
Demonstratie: Fie o solutie particulara a sistemului, in care variabila secundara xj = l > 0, l oarecare iar celelalte sunt 0. In acest caz, variabilele principale vor fi: yli = xi - aij l si vor fi toate pozitive, tinand cont de faptul ca toti aij 0 si, deci, solutia va fi admisibila. Pentru o astfel de solutie, valoarea functiei obiectiv este:
f(yl) = f(xB) - Dj l. si avem: 
deci imaginea functiei f este nemarginita si afirmatia este demonstrata.
Presupunem in continuare ca exista o componenta aij strict pozitiva. Deoarece dorim sa trecem la cea mai buna dintre bazele posibile, vom alege dintre toate variabilele cu Dj < 0, pe cea pentru care se obtine:
Aceasta conditie este criteriul de intrare in baza.
Deoarece calculul necesar gasirii
acestuia este laborios, Danzig a preferat inlocuirea acestei alegeri cu
alegerea acelui j care corespunde celui mai negativ Dj (= -
), varianta care este usor de aplicat,
imbunatateste solutia si prin care se
obtine, in marea majoritate a cazurilor, acelasi j.
In acest moment stim cum sa gasim o solutie mai buna, daca ea exista si am putea calcula din nou elementele necesare analizarii noii solutii, din tabelul simplex, folosind formulele fiecaruia:
xB = B-1 b
z = B-1 A
D = z - c
Acest mod de lucru este efectiv folosit in anumite variante ale algoritmului simplex (vezi forma revizuita) dar el presupune calcularea inversei matricei B, ceea ce necesita foarte mult timp. Acest motiv era suficient de convingator pentru ca Danzig sa-si fi pus problema daca nu cumva noul tabel simplex poate fi calculat pe baza fostului tabel simplex, facand mult mai putine calcule si utilizand formule usor de memorat si aplicat. Aceasta intrebare era natural de pus, daca tinem cont ca noua solutie difera de fosta solutie printr-o singura variabila. Aceste formule au fost efectiv gasite, ele putand fi obtinute urmarind efectul inlocuirii lui xi cu xj asupra sistemului:
noua solutie de
baza 
se obtine din fosta solutie cu formulele deja
gasite mai sus:
= xi si
= xs - xi pentru s i
noii coeficientii ai variabilelor in cele m ecuatii vor fi:
variabila principala xs va avea coeficientul 1 in ecuatia k si 0 in celelalte ecuatii;
o variabila secundara xk, diferita de xi,
va avea coeficientii 
in ecuatiile s i si coeficientul 
in ecuatia i.
noua variabila secundara xi va avea
coeficientii - in ecuatiile s i si coeficientul in ecuatia i.
noua valoare a functiei obiectiv va fi: f() =
noii Dj ii obtinem inlocuind in functia obiectiv variabila xj in functie de xi:
f(x) = f(
) - 
- Dj (- - xi + xi
= - 
-
xi =
= f() - 
- xi
de unde rezulta ca 
pentru k i si 
Desi par sa fie foarte multe formule complicate, frumusetea algoritmului si meritul lui Danzig consta tocmai in faptul ca toate respecta o regula vizuala usor de memorat, numita regula dreptunghiului, asa cum se va vedea in algoritmul simplex.
ALGORITMUL SIMPLEX
Reamintim ca presupunem ca problema este la forma standard de maxim si ca dispunem de o solutie de baza admisibila.
Pasul 1. Se construieste tabelul simplex corespunzator bazei de care dispunem in ordinea urmatoare:
pe linia a doua se trec toate variabilele intr-o ordine oarecare;
pe prima linie se trec coeficientii functiei obiectiv, fiecare deasupra variabilei corespunzatoare;
se construieste matricea A, fiecare coloana fiind formata din coeficientii unei variabile din toate ecuatiile (ordinea in care se parcurg ecuatiile trebuie sa fie aceeasi pentru toate variabilele), avand grija ca, coloanele sa fie trecute in ordinea in care au fost trecute variabilele pe linia 2;
se construieste baza B, ordinea coloanelor fiind cea in care apar ele in matricea A;
se calculeaza B-1;
se calculeaza B-1 A si se trece in partea centrala a tabelului;
se trec variabilele principale in a doua coloana, in asa fel incat, la intersectia liniei si coloanei corespunzatoare acestei variabile, sa se afle valoarea 1.
se trec in prima coloana coeficientii corespunzatori variabilelor principale din functia obiectiv, fiecare in dreptul variabilei corespunzatoare;
se calculeaza solutia de baza cu formula B-1 b, avand grija ca ordinea in care au fost trecuti termenii liberi in vectorul b sa fie aceeasi cu ordinea in care au fost parcurse ecuatiile la formarea matricii A;
se trec in a treia coloana valorile variabilelor principale din solutia de baza, fiecare in dreptul variabilei corespunzatoare;
se calculeaza f(xB) inmultind doua cate doua componentele coloanei 1 cu cele din coloana 3 aflate pe aceeasi linie si adunand toate produsele intre ele (adica facem produsul scalar dintre cB si xB);
se calculeaza pe rand fiecare zj j = 1,,n un zj obtinandu-se inmultind scalar cB cu coloana j din B-1 A aflata in centrul tabelului (aceasta linie se calculeaza si se trece doar in primul tabel, scopul ei fiind calcularea lui D
se calculeaza pe rand fiecare Dj j = 1,,n scazand din linia lui z linia lui c (Dj = zj - cj)
Pasul 2. Se analizeaza valorile Dj corespunzatoare variabilelor secundare (e usor de vazut ca intotdeauna, cei corespunzatori variabilelor principale sunt toti 0, deci neinteresanti).
daca toti sunt mai mari sau egali cu 0 atunci solutia actuala este cea optima. Daca exista Dj = 0 in afara bazei, atunci pot aparea doua cazuri:
toate elementele din coloana aj din B-1 A sunt mai mici sau egale cu 0. Atunci toate solutiile de forma xB - aj l sunt solutii optime, unde l > 0 oarecare;
exista o componenta aij a coloanei aj strict pozitiva. Atunci introducand variabila xj in baza in locul variabilei principala xi obtinem alta solutie de baza optima.
Daca apar numai cazuri de tipul 2), obtinem toate solutiile de baza optime, multimea tuturor solutiilor optime fiind formata din toate combinatiile convexe ale acestora. Daca apare si cazul 1) atunci multimea solutiilor optime este nemarginita fiind formata din combinatiile convexe ale solutiilor de forma xB - aj l unde xB sunt toate solutiile optime de baza.
daca
exista Dj < 0
atunci il alegem pe cel mai negativ: Dk = 
. Variabila xj va fi cea care intra in noua
baza. Daca minimul este multiplu atunci alegem, la intamplare, unul
dintre acestia (cei minimi).
Pasul 3. Se analizeaza elementele coloanei aj din B-1 A, corespunzatoare variabilei alese la pasul 2.
Daca toate sunt mai mici sau egale cu 0 atunci problema are optim infinit si algoritmul ia sfarsit;
Daca
exista componente strict pozitive, pentru acestea se calculeaza
rapoartele qs = 
. Variabila xi
corespunzatoare raportului minim este cea care va iesi din baza.
Daca acest minim este multiplu sunt posibile doua cazuri:
minimul este strict pozitiv. In acest caz se alege unul dintre acestia la intamplare;
minimul este 0.
Atunci xi
corespunzatori sunt 0, deci solutia este degenerata si noua
solutie este la fel de buna. Aceasta situatie poate duce la
ciclarea algoritmului si alegerea la intamplare nu mai este
suficienta, fiind nevoie de o regula de alegere suplimentara
care sa evite ciclarea. O metoda de alegere se bazeaza pe faptul
ca, asa cum vom vedea, intotdeauna prima baza este matricea
unitate si in dreptul ei, in toate tabelele simplex, se va afla inversa
bazei corespunzator fiecaruia. In acest caz, pentru pozitiile in
care s-a obtinut minimul impartim
prima coloana a lui B-1 la coloana aj si
alegem minimul dintre aceste rapoarte. Daca minimul dintre acestia
este tot multiplu continuam procedeul, pentru pozitiile ce dau noul
minim, cu coloana a doua din B-1 si asa mai departe,
pana minimul ramane unic. Nu este posibil sa se epuizeze toate
coloanele lui B-1 si minimul sa ramana multiplu,
deoarece, in acest caz, am avea: 
, pentru toti indicii jk ai coloanelor lui B-1,
i1 si i2 fiind doi din indicii care dau acelasi
minim pana la sfarsit sau altfel scris 
pentru orice jk
T liniile i1 si i2
din B-1 sunt proportionale, fapt ce contrazice faptul ca B-1
este inversabila.
Pasul 4. Se calculeaza componentele tabelului simplex corespunzator noii baze pe baza tabelului actual si folosind urmatoarele reguli:
se incadreaza elementul aij, aflat la intersectia coloanei variabilei care intra in baza cu linia variabilei care iese din baza, care a fost numit de Danzig pivot, intr-un dreptunghi
coloana pivotului va avea 1 in dreptul pivotului si 0 in rest (inclusiv Dj
linia pivotului este linia actuala impartita la pivot (inclusiv in solutia de baza);
restul elementelor se calculeaza cu regula dreptunghiului (inclusiv solutia de baza, D si f(xB)). Regula dreptunghiului se bazeaza pe observatia ca in toate formulele prin care se calculeaza acestea nu apare decat valoarea lor actuala, pivotul si cele doua elemente care ar completa dreptunghiul ce are pozitia de calculat si pivotul pe diagonala. Regula dreptunghiului se enunta literar astfel: 'noua valoare = produsul dintre elementele de pe diagonala pivotului minus produsul dintre cele aflate pe cealalta diagonala totul impartit la pivot'. (pentru scurtarea timpului de lucru se poate observa ca elementele unei linii care are 0 pe coloana pivotului raman aceleasi si de asemenea elementele unei coloane care are 0 pe linia pivotului)
Operatia de calculare a noului tabel prin regulile de mai sus poarta denumirea de pivotare.
Pasul 5. Se reia algoritmul de la pasul 2.
Exemplu: Fie problema de programare liniara:
pentru care stim ca baza formata din coloanele a1, a2, a3 este admisibila. Pentru rezolvare vom aduce problema la forma standard de maxim introducand variabilele de abatere x7, x8, x9 obtinand:
Vom aseza in tabelul simplex variabilele in ordinea indicilor si vom avea:
c = 
, A = 
, B = 
, cB = 
vom calcula
matricea B-1 = 
si pe baza
acesteia solutia de baza xB
= B-1 b = 
si matricea B-1 A = 
care se trec in
tabelul simplex:
|
3 2 1 4 3 5 0 0 0 |
|||
|
cB |
xB |
xB |
x1 x2 x3 x4 x5 x6 x7 x8 x9 |
|
x1 x2 x3 |
|
||
si in final se vor calcula valoarea functiei obiectiv in aceasta solutie, zj si Dj
|
|
3 2 1 4 3 5 0 0 0 |
||
|
cB |
xB |
xB |
x1 x2 x3 x4 x5 x6 x7 x8 x9 |
|
|
x1 x2 x3 |
|
|
|
|
|||
|
|
Din tabel se observa ca exista Dj < 0, acestia fiind D D D D iar minimul lor este D
Observatie Daca vom cauta acel Dj care da cea mai buna imbunatatire vom avea de
gasit acel Dj dintre
cei negativi pentru care se obtine 
si deci de
calculat:
= 
= 
= 
= 
= 
= 
= 
= 
si in final max (,,,) = si corespunde tot
lui D
In concluzie, solutia actuala nu este optima si solutia cea mai buna dintre cele posibile ca succesoare va avea variabila x6 printre cele principale.
Analizand coloana a6 observam ca exista componente strict pozitive (de fapt, in acest caz sunt chiar toate) si calculam pentru acestea rapoartele qi obtinand:
q = 
= 
, q = 
= 14, q = 
= 
deci minimul corespunde variabilei x1 si aceasta este cea care va iesi din baza. In cest moment cunoastem noua baza si vom construi tabelul simplex pe baza regulilor de calcul de la pasul 4:
pivotul este a16
= 
de exemplu, pentru elementul de pe pozitia a34 avem dreptunghiul:
si noua
valoare de pe aceasta pozitie va fi: 
= -1
In final, tabelul corespunzator noii baze va fi:
|
3 2 1 4 3 5 0 0 0 |
|||
|
cB |
xB |
xB |
x1 x2 x3 x4 x5 x6 x7 x8 x9 |
|
|
x6 x2 x3 |
|
|
|
|
|
Continuand algoritmul vom gasi tabelele:
|
3 2 1 4 3 5 0 0 0 |
|||
|
cB |
xB |
xB |
x1 x2 x3 x4 x5 x6 x7 x8 x9 |
|
|
x6 x2 x8 |
|
|
|
|
|
|
3 2 1 4 3 5 0 0 0 |
|||
|
cB |
xB |
xB |
x1 x2 x3 x4 x5 x6 x7 x8 x9 |
|
x6 x5 x8 |
|
||
|
|
Ultimul tabel contine solutia optima, deoarece toti Dj 0. Deoarece nu mai exista nici un Dj = 0 in afara celor din baza rezulta ca solutia optima este unica.
Determinarea unei solutii de baza admisibile de start
Presupunem inca odata ca problema este la forma standard.
Algoritmul simplex necesita, pentru pornire, o solutie admisibila de baza. Gasirea acesteia pur si simplu prin incercari nu este deloc o sarcina usoara, gandindu-ne ca aceasta presupune gasirea unui minor principal, inversarea acestuia si calcularea solutiei, abia in acest moment putand vedea daca aceasta are toate componentele pozitive, aceasta cautare putand dura foarte mult.
Rezolvarea problemei pleaca de la observatia ca singura baza pentru care calculul de mai sus se poate face imediat este matricea unitate, caz in care solutia de baza corespunzatoare este chiar vectorul termenilor liberi. Aceasta presupune ca problema sa aiba toti termenii liberi mai mari sau egali cu 0 si in matricea A sa existe toate coloanele matricii unitate.
Daca toti termenii liberi pot fi facuti mai mari sau egali cu 0 foarte simplu, prin inmultirea eventual cu -1 a restrictiei respective, existenta tuturor coloanelor matricii unitate este evident ca este foarte putin probabila si mai greu de obtinut.
In acest sens plecam de la observatia ca existenta unui vector din coloana unitate printre coloanele matricii A este echivalenta cu existenta unei variabile care apare doar in ecuatia corespunzatoare lui 1 din acel vector, cu coeficientul 1. Acest lucru poate fi obtinut in doua moduri:
a) Incepand de la prima ecuatie, cautam o variabila care are coeficientul de acelasi semn cu termenul liber, o scoatem din aceasta ecuatie in functie de celelalte variabile, o inlocuim in celelalte si repetam procedeul pornind de la a doua ecuatie. Pot aparea trei cazuri:
la un moment dat obtinem o ecuatie in care toti coeficientii variabilelor au semn contrar termenului liber, macar unul dintre toti fiind diferit de 0. In acest caz ecuatia nu are evident solutie admisibila(pozitiva) si deci problema nu are solutie;
toti coeficientii variabilelor si termenul liber sunt 0. In acest caz rezulta ca aceasta ecuatie rezulta din cele anterioare si ea va fi eliminata, trecandu-se la urmatoarea;
se epuizeaza toate ecuatiile. In acest moment, variabilele care au fost scoase din fiecare ecuatie formeaza baza dorita.
Procedeul de mai sus poate parea atractiv, dar presupune introducerea unui algoritm diferit de simplex, cu efect asupra omogenitatii calculelor si a vitezei de lucru. De asemenea, prin efectuarea calculelor de mai sus, datele problemei nu mai au semnificatia economica initiala, ne mai putandu-se face interpretari economice.
b) Pentru toti vectorii coloana introducem in ecuatiile corespunzatoare cate o variabila cu coeficientul 1. Vom obtine evident un nou sistem de restrictii si ramane de vazut ce legatura este intre solutiile acestuia si cel initial. Cele doua sisteme au forma:
A x = b si A x + y = b
Este evident ca o solutie a primului sistem este solutie si a celui de-al doilea (luam y = 0) iar o solutie a celui de-al doilea este solutie si pentru primul doar daca y = 0. Scopul nostru va fi deci, ca pornind de la solutia initiala a celei de-a doua probleme sa ajungem la o solutie a acesteia in care y = 0. Tinand cont ca in solutiile de baza, variabilele secundare sunt toate egale cu 0, vom incerca sa scoatem din baza variabilele y. Scopul algoritmului simplex este insa maximizarea functiei obiectiv, nu scoaterea a uneia sau alteia din variabile din baza. Pentru a echivala cele doua scopuri putem proceda in doua feluri:
Alegem o noua functie obiectiv care sa-si atinga extremul printre solutiile pozitive chiar pentru y = 0 si in momentul cand am obtinut solutia respectiva pornim cu aceasta ca solutie initiala algoritmul simplex pentru fosta problema.
Adaugam la fosta functie obiectiv noile variabile cu niste coeficienti de asemenea natura alesi incat aportul variabilelor y la valoarea functiei sa fie contrar scopului dorit (foarte mari pozitivi intr-o problema de minim si foarte mari negativi intr-o problema de maxim).
Vom detalia in continuare cele doua metode:
Algoritmul simplex in doua faze
Data problema de programare liniara la forma standard de maxim:
in care am aranjat deja ca toti termenii liberi sa fie pozitivi (b
Faza 1 Construim problema:
pe care o rezolvam cu algoritmul simplex pornind rezolvarea de la baza matrice unitate, putand ajunge la doua situatii:
minimul functiei g este strict pozitiv. Aceasta este echivalent cu faptul ca egalitatea Ax + y = b se poate obtine doar pentru y > 0 sau altfel spus Ax > b pentru orice x 0, deci sistemul Ax = b nu are solutii admisibile si in concluzie problema initiala nu are solutie.
minimul functiei g este 0. In acest caz, solutia optima obtinuta are y = 0, deci verifica Ax = b fiind in concluzie o solutie admisibila de baza a primei probleme.
Faza 2 Incepand de la solutia gasita la faza 1 se rezolva problema initiala cu algoritmul simplex.
Dezavantajul metodei consta in faptul ca tabelul simplex final de la faza 1 trebuie modificat pentru a obtine tabelul simplex initial de la faza 2 (vectorii x, c, cB, z, D, f(xB), se elimina coloanele corespunzatoare lui y) si in plus nu vom mai avea in tabelele simplex ale problemei initiale inversa bazei (care se gasea in dreptul coloanelor matricii unitate din prima faza) necesara in anumite variante ale algoritmului simplex.
Metoda bazei artificiale (metoda penalizarii)
Data problema de programare liniara la forma standard de maxim:
in care am aranjat deja ca toti termenii liberi sa fie pozitivi (b
Construim problema:
in care M este o constanta presupusa foarte mare (mai mare decat orice constanta care ar putea apare in rezolvarea problemei). Rezolvam problema cu algoritmul simplex pornind rezolvarea de la baza matrice unitate, putand ajunge la trei situatii:
problema are optim infinit. In acest caz, problema initiala are optim infinit.
problema are optim finit si in solutia de baza avem cel putin o variabila din vectorul y. In acest caz problema initiala nu are solutii admisibile.
problema are optim finit si in solutia de baza nu avem nici o variabila din vectorul y. In acest caz problema initiala are optim finit, solutia optima si maximul functiei fiind aceleasi cu cele ale problemei modificate.
In final vom remarca faptul ca variabilele y nu corespund unor marimi economice ca celelalte, ele fiind introduse doar ca un artificiu de calcul pentru a putea porni algoritmul simplex. Din acest motiv ele se numesc variabile artificiale.
Exemplu Fie problema de programare liniara:
Forma standard a problemei va fi:
Avem deja termenii liberi si o
coloana a matricii unitate 
corespunzatoare
variabilei x3. Pentru a obtine si a doua coloana 
vom introduce
variabila x5 cu coeficientul 1 in a doua ecuatie si in
final vom avea de rezolvat problema:
|
Algoritmul simplex in doua faze |
Metoda bazei artificiale |
|
|
|
Aplicand algoritmul simplex in doua faze vom obtine in prima faza succesiunea de tabele:
|
cB |
xB |
xB |
x1 |
x2 |
x3 |
x4 |
x5 |
|
|
x3 | ||||||
|
x5 | |||||||
|
cB |
xB |
xB |
x1 |
x2 |
x3 |
x4 |
x5 |
|
x3 |
|
|
|
|
|||
|
x2 |
|
|
|
|
|||
|
|
Am obtinut optimul egal cu 0 in solutia de baza (x3,x2) care va fi solutia initiala pentru algoritmul simplex aplicat problemei initiale in a doua faza. Eliminam din tabel coloana lui x5, inlocuim valorile coeficientilor functiei obiectiv si deci si valoarea acesteia, valorile D si obtinem tabelul:
|
cB |
xB |
xB |
x1 |
x2 |
x3 |
x4 |
|
x3 |
|
|
|
|||
|
|
x2 |
|
|
|
||
|
|
|
|
|
cB |
xB |
xB |
x1 |
x2 |
x3 |
x4 |
|
|
x3 | |||||
|
x1 | ||||||
|
cB |
xB |
xB |
x1 |
x2 |
x3 |
x4 |
|
x4 |
|
|
| |||
|
|
x1 |
|
|
| ||
|
|
|
|
|
cB |
xB |
xB |
x1 |
x2 |
x3 |
x4 |
|
x4 | ||||||
|
x2 | ||||||
Solutia optima a primei probleme este deci x1 = 0 si x2 = 10 care da un maxim al functiei egal cu 30. Daca aplicam a doua metoda vom obtine succesiv tabele:
|
-M |
|||||||
|
cB |
xB |
xB |
x1 |
x2 |
x3 |
x4 |
x5 |
|
x3 | |||||||
|
|
x5 | ||||||
|
-2M |
-M |
-4M |
M |
-M |
|||
|
-M-2 |
-4M-3 |
M |
|
-M |
|||||||
|
cB |
xB |
xB |
x1 |
x2 |
x3 |
x4 |
x5 |
|
x3 |
|
|
|
|
|||
|
|
x2 |
|
|
|
|
||
|
|
|
|
M+ |
|
-M |
|||||||
|
cB |
xB |
xB |
x1 |
x2 |
x3 |
x4 |
x5 |
|
|
x3 | ||||||
|
x1 | |||||||
|
2+M |
|
-M |
|||||||
|
cB |
xB |
xB |
x1 |
x2 |
x3 |
x4 |
x5 |
|
x4 |
|
|
| ||||
|
|
x1 |
|
|
| |||
|
|
|
|
M |
|
-M |
|||||||
|
cB |
xB |
xB |
x1 |
x2 |
x3 |
x4 |
x5 |
|
x4 | |||||||
|
x2 | |||||||
|
M |
Rezultatul final este evident acelasi.
VARIANTE ALE ALGORITMULUI SIMPLEX
Algoritmul simplex dual
Pentru expunerea acestui algoritm trebuie introduse notiunile de baza dual admisibila si solutie dual admisibila de baza. Prin definitie numim:
|
solutie de baza dual admisibila |
solutie de baza pentru care toti Dj |
|
|
baza dual admisibila |
baza corespunzatoare unei solutii de baza dual admisibile |
Ca si in cazul algoritmului simplex, pentru a putea rezolva problema cu algoritmul simplex dual trebuie sa dispunem deja de o baza initiala dual admisibila. Aceasta solutie poate exista ca urmare a unor calcule anterioare (vezi capitolul cu reoptimizarea) sau, ca si in cazul algoritmului simplex, poate fi aplicata o procedura prin care sa gasim aceasta baza. Prezentarea acesteia este mai complicata decat cea de la algoritmul simplex astfel incat:
daca dispunem de o baza dual admisibila vom rezolva problema cu algoritmul simplex dual
daca nu dispunem de o baza dual admisibila vom rezolva problema cu algoritmul simplex.
Pentru a evita orice confuzie, vom numi in continuare algoritmul simplex obisnuit algoritm simplex primal si o baza admisibila baza primal admisibila.
Se observa ca o solutie dual admisibila nu este in general primal admisibila si reciproc, iar o solutie care este simultan primal si dual admisibila este o solutie optima si reciproc.
Presupunem ca am adus problema la forma standard de maxim si dispunem de o baza dual admisibila si dispunem deja de de o baza dual admisibila. Algoritmul simplex dual consta in urmatorii pasi:
Pasul 1. Se construieste tabelul simplex asociat acestei baze, la fel ca si la algoritmul simplex primal;
Pasul 2. Se analizeaza componentele solutiei:
Daca toate componentele sunt mai mari sau egale cu 0 atunci solutia este si primal admisibila, deci optima.
Daca exista componente strict negative,
variabila corespunzatoare celei mai negative (xi = 
) este cea care iese din baza. Daca minimul este
multiplu se ia una la intamplare.
Pasul 3. Se analizeaza linia li corespunzatoare variabilei xi aleasa la pasul 2:
Daca toate componentele aij j = 1,,n sunt mai mari sau egale cu 0, atunci am avea o ecuatie cu toti coeficientii necunoscutelor pozitivi si termenul liber strict negativ, deci problema nu are solutii primal admisibile.
Daca exista componente strict negative,
atunci pentru acestea se gaseste acel indice pentru care se
obtine 
(prin 
am notat modulul
numarului a). Daca
minimul este multiplu alegem unul dintre acestia la intamplare. Variabila
corespunzatoare acestuia este cea care intra in baza.
Pasul 4. Se construieste tabelul corespunzator noii baze aplicand aceleasi reguli ca la algoritmul simplex primal;
Pasul 5. Se reia algoritmul de la pasul 2
Forma secundara
Este evident ca modul de organizare al datelor in tabelul simplex nu este unicul mod de a organiza datele intr-un tabel. Forma secundara este tocmai o astfel de alternativa. Presupunem si in acest caz ca problema este la forma standard de maxim, ca problema este la forma standard si ca dispunem de o solutie initiala de baza care este primal sau dual admisibila.
Pasul 1. Datele problemei vor fi organizate intr-un tabel de forma:
|
cS |
|||
|
c |
x |
f |
xS |
|
f(xB) |
DS |
||
|
cB |
xB |
xB = B-1 b |
B-1 S |
|
cS |
xS |
-In-m |
Se observa ca singura diferenta este ca la coloana variabilelor bazei din stanga se adauga si cele secundare, pe orizontala se lasa doar variabilele secundare iar in loc de matricea unitate in dreptul variabilelor principale vom avea matricea unitate in dreptul celor secundare (dar cu minus), D fiind calculat la fel, neglijandu-se cei din dreptul variabilelor principale, care oricum erau 0.
Pasul 2. + Pasul 3. Se gasesc variabila care iese din baza si cea care intra in baza cu aceleasi reguli ca la algoritmul simplex primal sau, dupa caz, ca la cel dual.
Pasul 4. Se construieste tabelul asociat noii baze aplicand regulile:
Pivotul este acelasi ca la tabelul simplex;
Linia pivotului are -1 in dreptul pivotului si 0 in rest;
Coloana pivotului se imparte la pivotul cu semn schimbat
Celelalte elemente se calculeaza cu regula dreptunghiului
Pasul 5. Se reia algoritmul de la pasul 2.
Exemplu Fie problema de programare liniara rezolvata mai sus:
Forma standard a problemei va fi:
iar dupa
introducerea variabilelor artificiale obtinem:
Tabelul corespunzator va fi:
|
cB |
xB |
xB |
x1 |
x2 |
x4 |
|
-2M |
-M-2 |
-4M-3 |
M |
||
|
x1 | |||||
|
x2 | |||||
|
x3 | |||||
|
x4 | |||||
|
|
x5 |
Aplicam simplex primal si obtinem cel mai negativ Dj corespunzator lui x2 si qi minim corespunzator lui x5. In acest moment avem o solutie de baza a problemei initiale si putem elimina variabila x5. Obtinem:
|
-M |
| ||||||||||
|
cB |
xB |
xB |
x1 |
x5 |
x4 |
cB |
xB |
xB |
x1 |
x4 |
|
|
|
|
M+ |
|
| |||||||
|
|
x1 |
|
x1 | ||||||||
|
|
x2 |
x2 | |||||||||
|
x3 |
|
|
x3 |
|
| ||||||
|
x4 |
x4 | ||||||||||
|
-M |
x5 |
si in continuare:
|
cB |
xB |
xB |
x2 |
x4 |
cB |
xB |
xB |
x2 |
x3 |
|
|
|
|
|
||||||||
|
|
x1 |
x1 |
|
|
|
|||||
|
x2 |
x2 | |||||||||
|
|
x3 |
|
x3 | |||||||
|
x4 |
x4 |
|
|
|
|
cB |
xB |
xB |
x1 |
x3 |
|
|
x1 | |||||
|
x2 | |||||
|
x3 | |||||
|
x4 |
Din rezolvarea de mai sus se observa ca aceasta metoda este mai eficienta doar daca numarul variabilelor secundare este mai mic decat numarul variabilelor principale. Totusi, motivul principal pentru care a fost introdusa aceasta varianta, este existenta unor probleme in care, pe parcursul rezolvarii, se adauga foarte multe restrictii (de exemplu rezolvarea problemelor in numere intregi), pentru o restrictie in plus tabelul simplex marindu-se cu o linie si o coloana (cum se va vedea la capitolul de reoptimizare) iar tabelul corespunzator formei secundare doar cu o linie.
Forma revizuita a algoritmului simplex
O problema mare (de exemplu cu 1000 variabile si 100 restrictii) necesita in algoritmul simplex introducerea, memorarea si lucrul cu un tabel cu 100.000 componente, adica un numar imens de date. Din acest motiv, si remarcand faptul ca in algoritmul simplex doar o parte din acestea contribuie efectiv la luarea deciziilor, s-a construit un algoritm care sa tina cont de observatiile de mai sus, numit 'forma revizuita a algoritmului simplex', in care se lucreaza cu minimul necesar din datele tabelului simplex. Astfel, pentru testarea solutiei actuale si trecerea eventuala la o noua baza avem nevoie doar de urmatoarele elemente:
inversa bazei curente B-1
componentele vectorului D pentru a face testul de optim si a gasi variabila care intra in baza (daca solutia nu e optima)
coloana ak din B-1A corespunzatoare celui mai negativ Dj (daca exista strict negativi) pentru a face testul de optim infinit
solutia curenta pentru a gasi variabila care iese din baza (daca mai e cazul)
Aceste elemente se aseaza intr-un tabel de forma:
|
cB |
xB |
xB = B-1b |
B-1 |
|
f(xB) |
π
= |
numit tabelul simplex redus.
Operatiile ce se efectueaza in cadrul algoritmului simplex revizuit sunt (presupunem ca problema este la forma standard de maxim si detinem o solutie admisibila de baza si inversa bazei corespunzatoare):
Pasul 1. Se calculeaza Dj corespunzatori variabilelor secundare cu formula cunoscuta:
Dj = B-1 Pj - cj = π Pj - cj
unde Pj este coloana corespunzatoare variabilei xj din matricea initiala.
Pasul 2. Se analizeaza Dj calculati:
daca toti sunt mai mari sau egali cu 0 solutia curenta este optima. STOP
daca exista Dj strict negativi se alege minimul dintre acestia Dk, variabila xk va intra in baza si se trece la pasul 3.
Pasul 3. Se calculeaza ak = B-1Pk care se ataseaza ca noua coloana la tabel:
|
cB |
xB |
xB = B-1b |
B-1 |
ak = B-1Pk |
|
f(xB) |
π
= |
Dk |
Pasul 4. Se analizeaza componentele coloanei ak:
daca toate sunt mai mici sau egale cu 0 problema are optim infinit. STOP
daca exista aik strict pozitivi se alege cel pentru care se obtine:
ark = 
si variabila xr va iesi din baza apoi se trece la pasul 5.
Pasul 5. Se pivoteaza intregul tabel simplex si se elimina ultima coloana.
Pasul 6. Se reia algoritmul de la pasul 2.
Exemplu Fie problema de programare liniara rezolvata mai sus:
Forma standard a problemei va fi:
iar dupa
introducerea variabilelor artificiale obtinem:
Iteratia 1. Prima baza este B = I2 = B-1
corespunzatoare variabilelor x3 si x5 de unde
rezulta xB = 
si π =
(0,-M) I2 = (0,-M). Primul tabel redus
va fi:
|
-M |
x3 x5 | |||
|
-2M |
-M |
Se calculeaza DS S - cS = (0,-M) 
- 
= 
de unde rezulta
ca cel mai negativ este D si vom calcula coloana a2 = I2 
= care se adauga la tabelul anterior rezultand:
|
-M |
x3 x5 | ||||
|
-2M |
-M |
-4M-3 |
qi minim este cel corespunzator lui x5 si deci variabila x2 va intra in locul variabilei x5.
Dupa pivotare si eliminarea ultimei coloane obtinem:
|
x3 x2 |
| |||
|
|
Deoarece variabila artificiala x5 a iesit din baza ea va fi eliminata din problema.
Iteratia 2. DS S - cS = (0,) 
- 
= (
)
cel mai negativ este D si vom calcula coloana a1 = 
=
care se adauga la tabelul anterior rezultand:
|
|
x3 x2 |
|
|
||
|
|
|
qi minim este cel corespunzator lui x2 si deci variabila x1 va intra in locul variabilei x2.
Dupa pivotare si eliminarea ultimei coloane obtinem:
|
x3 x1 | ||||
Iteratia 3. DS S - cS = (0,2) 
- 
= (
)
cel mai negativ este D si vom calcula coloana a4 = 
=
care se adauga la tabelul anterior rezultand:
|
|
x3 x1 | ||||
qi minim este cel corespunzator lui x3 si deci variabila x4 va intra in locul variabilei x3.
Dupa pivotare si eliminarea ultimei coloane obtinem:
|
x4 x1 |
|
| ||
|
|
|
Iteratia 4. DS S - cS = (
,0) 
- = (
)
cel mai negativ este D si vom calcula coloana a2 = 
=
care se adauga la tabelul anterior rezultand:
|
|
x4 x1 |
|
|
|
|
|
|
|
|
qi minim este cel corespunzator lui x1 si deci variabila x2 va intra in locul variabilei x1.
Dupa pivotare si eliminarea ultimei coloane obtinem:
|
x4 x2 | ||||
Iteratia 5. DS S - cS = (3,0) 
- = (
) >0 deci solutia este optima (si
unica) STOP
Chiar daca la prima vedere calculele par mai imprastiate si deci mai lente, pentru probleme mari, pe calculator se economiseste foarte multa memorie si se mareste foarte mult viteza de calcul.
Totusi, marele avantaj al acestei metode este acela ca, la fiecare iteratie, se folosesc datele problemei initiale, ceea ce face ca erorile inerente de rotunjire sa nu se propage, ramanand in limite acceptabile.
|
Politica de confidentialitate | Termeni si conditii de utilizare |
Vizualizari: 2692
Importanta: 
Termeni si conditii de utilizare | Contact
© SCRIGROUP 2024 . All rights reserved
; i = 1,,m; j = 1,,n