Problema de Transport

Extras din referat Cum descarc?

Problema de transport este un model din categoria celor de programare liniara, avand modelul matematic asemanator acestui tip de problema, dar cu unele particularitati care au dus la aparitia unor metode specifice de rezolvare.
1. Modelul matematic 
Fie m centre de expeditie ale aceluiasi produs notate Ai, i=1, ..., m si n centre de primire notate Bj, j=1, ..., n. Cantitatea expediata dintr-un centru Ai este egala cu ai, iar cea solicitata in centrul Bj este egala cu bj . Notam cu cij, i=1, ..., m, j=1, ..., n costul de transport pe unitatea de produs din Ai in Bj si cu xij cantitatea transportata din Ai in Bj.
Se pune problema determinarii cantitatilor transportate xij , i=1,..., m, j=1,...,n astfel incat costul total de transport sa fie minim (sau maxim in unele probleme). Acest costul total de transport este reprezentat de o functie de forma:
f=c11x11+ c12x12+ ...+ c1nx1n+ c21x21+...+ c2nx2n+...+ cmnxmn
care trebuie minimizata (maximizata). Noi vom considera in continuare doar problema de minim.
Ca si in unele probleme obisnuite de programare liniara, exista un sistem de restrictii care in acest caz sunt de forma:
In cazul in care are loc = =S atunci problema de transport se va numi echilibrata, iar daca =S1 S2= se va numi neechilibrata. Vom aborda pentru inceput problemele de transport echilibrate, modelul matematic al unei astfel de probleme fiind de forma:
min f= (1.8)
in conditiile:
Pentru rezolvarea problemei se poate utiliza un tabel de forma:
Tabelul (1.3)
Se numeste celula (casuta) a tabelului (1.3) o pereche de elemente 
notata ( i, j), i=1,..., m, j=1,..., n.
O problema de transport contine m + n ecuatii liniare cu mn necunoscute, dintre acestea m + n- 1 fiind liniar independente deci numarul ecuatiilor liniar independente este mai mic sau egal cu cel al necunoscutelor, sistemul fiind deci nedeterminat.
Definitie: Se numeste solutie admisibila a problemei de transport , o solutie care satisface relatiile (1.9-1.11).
Definitie: Se numeste solutie de baza a problemei de transport, acea solutie 
admisibila, care contine cel mult m + n- 1 valori xij>0, restul fiind nule.
Definitie: Se numeste solutie de baza nedegenerata a problemei de transport, 
acea solutie de baza care contine exact m + n- 1 valori xij>0, restul fiind nule; daca numarul solutiilor xij>0 este strict mai mic decat m + n- 1 se numeste degenerata.
Definitie: Se numeste solutie optima a problemei de transport, acea solutie de 
baza pentru care se obtine optimul (minimul sau maximul) functiei obiectiv.
Definitie: Se numeste baza a problemei de transport, notata cu B multimea celulelor (i, j) i=1,..., m, j=1,..., n care contine valori xij > 0 si este formata din cel mult m + n- 1 celule si cel putin n. Celulele care fac parte din baza le numim bazice si le vom nota (i, j)B, iar celelalte le numim nebazice si le notam (i, j)R.
Definitie: Se numeste ciclu corespunzator unei celule nebazice , o succesiune de celule bazice (cu exceptia celei initiale si finale) , , ..., , , obtinuta in felul urmator:
- se pleaca din celula si se trece intr-o celula situata pe orizontala sau verticala celulei , chiar ,,sarind" peste alte celule bazice si nebazice, astfel incat sa existe posibilitatea ca din sa se poata trece pe o directie perpendiculara, intr-o alta celula bazica .

Fisiere in arhiva (1):

 Problema de Transport.doc