7.Formularea unei prob.de transport
Se considera ca un produs este disponibil in m centre producatoare (fabrici, depozite) notate cu Pi(i = 1,...,m ). Acest produs trebuie transportat la n centre consumatoare (de desfacere, destinatari) notati eu Cj (j = 1,...m)
Transportul se poate efectua de la orice Pi la orice Cj(j=1,..m), iar costul unitar de transport este ci. Acest cost depinde de distantele respective, de mijloacele de transport folosite si altele, ceea ce se presupune cunoscut.
Se cunosc de asemenea si cantitatile disponibiIe, aflate in cele m centre producatoare, notate cu ai cu (i = 1,...m) si cantitatile necesare la cele n centre consumatoare, notate bj cu (j = 1,. . . n).
Se noteaza cu xi j , cantitatea transportata in conditiile de mai sus iar datele probl de transport sunt sintetizate conform tabelului de mai jos:
Caracteristicile unei probl de transport clasice sunt:
- fiecare centru producator aprovizioneaza cel putin un centru consumator si fiecare centru consumator este aprovizionata de la cel putin, un centru producator.
- pot exista perechi producator - consumator intre care nu se poate face transfer;
- nu exista limitari in ceea ce priveste cantitatea transportata pe fiecare ruta;
- fiecarei rute i s-a asociat un cost care nu depinde de sensul de parcurgere;
Obiectivul probl de transport este gasirea cantitatilor care trebuie transportate pe fiecare ruta a.i. sa se asigure necesarul fiecarui centru consumator, in limitele cantitatilor aflate in centru producator, si aceasta cu costuri minime;
Teorema1. O probl de transport echilibrata admite intotdeauna programe(solutii); orice program este marginit daca valorile sale ai, bj sunt marginite (finite).
Numim model matematic echilibrat, daca cantitatea disponibila totala este egala cu cerea totala.Modelul matematic de mai sus se poate inlocui cu un model echivalent in care toate restrictiile sunt ecuatii.
In forma sa matematiea modelul probl de transport se scrie:
Astfel in urma acestor transformari se va obtine urmatorul model matematic echilibrat:Modelul matem de tip transport de forma standard sau echilibrata.
O astfel de probl s.n. probl de transp echilibrata.In practica pot exista urmat cazuri:
-Daca Σ(i=1,m)ai < Σ(j=1,n)bj , se poate adauga un depozit
fictiv Pm+1 care are un disponibil am+
de la depozitul Pm+l la centrele Cj sunt nule.
-Daca Σ(i=1,m)ai > Σ(j=1,n)bj , se poate adauga un centru fictiv Cn+l ce necesita bn+1 unitati, a.i. costurile sa fie nule.
Nr total de restrictii este de m+n si sunt o combinatie liniara de celelalte, deci nr celor independente este de m+n-1.Orice probl de transport admite solutii admisibile, adica sistemul de ecuatii este compatibil. O astfel de problema are solutia:
xij=aibj/ Σ(i=1,n)ai
Aplicarea algoritmului Simplex este dificila in acest caz datorita nr foarte mare de nec si a determinarii solutie admisibila de baza. Intr-o probl de transport nu poate aparea decat varianta de optim finit, existand intotdeauna solutii admisibile, iar minimul -infinit nu este posibil, tinand cont ca avem de minimizat o functie liniara cu toti
coef pozitivi pe o multime de solutii cu toate componentele pozitive.
Algoritmul specific probl de transport au urmatoarele etape:
Se det o solutie admisibila de baza de pomire X, prin folosirea uneia din urmatoarele metode : coltului N-V, metoda costului minimal,metoda costului minim pelinie ,metoda costului min pe coloana.
Determinarea solutiei optime pornind de la solutia X.
|
