Optimizarea transportului marfurilor intre producatori si consumatori

OPTIMIZAREA TRANSPORTULUI MARFURILOR INTRE PRODUCATORI SI CONSUMATORI

1.Consideratii generale

In activitatea de transport in general, dar mai ales in transportul feroviar, problema organizarii optime a activitatii este extrem de complexa datorita diversitatii factorilor tehnici si economici care influenteaza, fiecare din ei in mod diferit, volumul, ritmul, calitatea si eficienta economica a procesului de transport. Ca urmare, cunoasterea factorilor tehnici si economici de influenta precum si interdependenta dintre acestia, conduce la posibilitatea abordarii stiintifice a diferitelor fenomene si aspecte din activitatea de transport feroviar.

Unul din fenomenele caracteristice ale transportului feroviar consta in modul de existenta si de actiune al necesitatilor de transport ale clientilor, exprimate in tone marfa sau numar de calatori, intr-un sistem spatiu timp cunoscut. Ca urmare, transporturile pe calea ferata sunt o continuare evidenta a tuturor surselor de productie, de la locul de productie pana la cel de consum. In acest fel, necesitatile de transport de marfuri apar ca o consecinta a naturii, volumului si ritmului de productie, al unor sectoare economice sau agenti economici, problema de productie corelandu-se cu cea a consumului. Deci, a analiza necesitatile de transport inseamna a analiza traficul de calatori sau marfuri. Unul dintre parametri de baza ai traficului de marfuri il reprezinta curentii de trafic care se definesc a fi cantitatea de marfa transportata intr-un anumit interval de timp pe o anumita sectie. Fiecare curent de trafic de marfuri are o origine a traficului, un punct terminus si un sens al traficului. Originile si punctele terminus se pot repartiza in spatiu, fie sub forma unui punct de trafic (cazul unei singure origini de trafic ca de ex. o cariera de piatra, o balastiera, o mina de carbuni, conform figurii 1), fie sub forma unei retele de trafic (cazul mai multor origini de trafic, ca de ex. un sector agricol de productie, o exploatare forestiera sau un transport de colectare de marfuri, conform fig. 2).

2. Abordarea problemelor

2.1. Problema transportului

In esenta, o problema de transport clasica consta in determinarea unui plan de transport a unui produs omogen, de la anumite centre producatoare sau depozite, in scopul satisfacerii cerintelor mai multor consumatori si minimizarii cheltuielilor de transport.

Fig. 1

Fig. 2

Formularea problemei de transport este urmatoarea: se presupune ca exista un numar de n centre de productie notate A_i (fabrici producatoare, depozite, cariere, balastiere etc.), cu 1 < i < n, de unde urmeaza sa se transporte un produs omogen la m centre de consum (intreprinderi, santiere, magazine etc.) notate cu B_j , la care 1 < j < m. Cunoscandu-se cantitatile disponibile a_i in fiecare centru de productie i si cantitatile necesare b_j ale fiecarui centru de consum j, precum si cheltuielile de transport c_ij (sau distantele dij), de la i la j, se cere sa se in tocmeasca un plan de transport x_ij , 1 < i < n, 1 < j < m in asa fel incat totalul cheltuielilor de transport, sau totalul tone*km, sa fie minim si sa fie satisfacute integral sau in cea mai mare masura cererea de produs in centrele de consum.

2.2. Modele matematice ale problemei de transport

Luand in considerare enuntul problemei de transport se impun urmatoarele restrictii:

Cantitatea totala de produse expediate din centrul de productie A_i spre cele m centre de consum B_j trebuie sa fie egala cu disponibilul din A_i rezultand astfel sistemul:

x_i1 x_i2 x_ij x_im =a_i , i=1,2,.n (1)

Cantitatea totala de produse primita de centrul de consum B_j de la cele n centre de productie A_i trebuie sa fie egala cu necesarul de consum al centrului de consum B_j si se obtine sistemul:

X_1j + x_2j +.+ x_ij+. + x_inj =bj , j=1,2,.m (2)

de m ecuatii liniare cu mn necunoscute;

Cantitatile de produse transportate x_ij trebuie sa satisfaca conditiile de nenegativitate:

x_ij > 0, i 1,2,,n; j= 1,2,., m(3)

notite de la curs

Schema metodologca de determinare a curentilor optimi in traficul feroviar de marfa prin programare liniara are urmatoarele faze:

Precizarea datelor problemei

Intocmirea modelului matematic al problemei de transport care consta din:

Transpunerea datelor problemei in matricea de transport

Precizarea conditiilor de tratare si rezolvare a problemei de transport:

Rel. 7

Rel. 8

Rel. 9

(12)

sau

(13)

sau

(14)

Aplicarea uneia dintre metodele de programare liniara pentru determinarea solutiei initiale de baza, adecvata problemelor de transport

Determinarea unei solutii de baza initiale sau determinarea direct a solutiei optime

Aplicarea metodelor de programare liniara pentru imbunatatirea solutiei initiale de baza

Determinarea solutiei optime

Schema metodologca de determinare a curentilor optimi de marfa in TF utilizand teoria grafurilor cuprinde:

Precizarea datelor problemei

Intocmirea modelului matematic al problemei de transport care consta din:

Transpunerea datelor problemei in matricea de transport

Transpunerea datelor problemei in reteaua de transport

Precizarea conditiilor de tratare si rezolvare a problemei de transport:

Rel. 7

Rel. 8

Rel. 9

Rel. 12 sau Rel. 13 sau Rel. 14

Precizarea condisiilor de tratare si rezolvare a retelei de transport:

(15)

(16)

(17)

(18)

unde si - nodurile grafului

- arcele grafului

Aplicarea uneia dintre metodele retelelor de transport pentru determinarea solutiei initiale de baza: algoritmul pentru determinarea fluxului minim sau algoritmul pentru determinarea fluxului maxim;

Determinarea solutiei initiale de baza;

Aplicarea din nou a unuia din algoritmii initiali si elaborarea tabelelor de marcaje si de fluxuri ale iteratiilor

Stabilirea solutiei optime.

Schema metodologica de determinare a curentilor optimi de marfa in transportul feroviar prin programarea parametrica cuprinde urmatoarele faze:

Precizarea datelor problemei de transport;

Precizarea parametrilor problemei de transport, si anume:

nominalizarea parametrilor (

precizarea intervalelor de variatie a parametrilor.

Intocmirea modelului matematic al problemei de transport, care consta din:

transpunerea datelor problemei in tabela de transport;

precizarea conditiilor de tratare si rezolvare a problemei de transport pentru urmatoarele cazuri:

a)     transporturi cu costuri variabile:

(4)

(5)

(6)

(19)

b)     transporturi cu cereri si oferte variabile:

(20)

(21)

(6)

unde si reprezinta variatia ofertei si cererii, conditiile suplimentare fiind:

(22)

(23)

(24)

Aplicarea uneia din metodele de programare liniara pentru determinarea solutiei initiale de baza;

Determinarea solutiei initiale de baza pentru o valoare sau un sistem de valori atribuite parametrilor;

Determinarea solutiei optime a problemei de transport pentru o valoare sau un sistem de valori atribuite parametrilor;

Determinarea intervalelor de variatie a parametrului in care solutia gasita ramane optima;

Reoptimizarea solutiei in afara intervalului de optimalitate;

Intocmirea tabelei tabelei de solutii optime in functie de variatia parametrilor;

Analiza corelata a solutiilor optime a diferitilor parametri.

Obs.! Aplicarea schemelor metodologice prezentate mai sus (care permit determinarea solutiei optime a unei probleme de transport prin metodele de programare matematica) necesita cunoasterea in detaliu a specificului problemei ce urmeaza a se optimiza, cunoasterea perfecta a metodelor de programare matematica ce se utilizeaza si presupune corectitudinea datelor problemei, atat pentru situatia existenta de fapt cat si pentru cea de perspectiva. Orice modificari ale unor date de perspectiva luate in calcul atrag in mod automat schimbarea solutiei optime determinate initial.

3. Rezolvarea problemei transporturilor prin utilizarea metodelor programarii liniare

3.1. Consideratii privind metodele programarii liniare

Programarea liniara este una dintre disciplinele matematice care constituie baza teoretica a cercetarii operationale. Problema generala a programarii liniare consta in minimizarea sau maximizarea unei functii liniare, ale carei variabile satisfac un sistem liniar si conditii de nenegativitate.

Dupa stabilirea modelului matematic al problemei de transport, se trece la rezolvarea problemei, rezolvare care se poate face pe doua cai:

cu metode exacte care conduc la solutia optima;

cu metode aproximative care nu asigura neconditionat solutia optima, dar care asigura obtinerea unor solutii foarte apropiate de cea optima si care au avantajul ca reduc in mod substantial volumul de calcul, fiind astfel mult mai expeditive.

3.2. Metodele programarii liniare utilizate pentru determinarea solutiilor initiale de baza

Pentru a rezolva o problema de transport data prin metode aproximative se porneste de la o solutie initiala de baza care se obtine astfel:

a)     se atribuie unei variabile oarecare x_ij valoarea:

x_ij = min                     (25)

b) daca a_i < b_j atunci

x_ij = a_i (26)

se suprima linia i iar b_j se va inlocui cu:

b_j¹ = b_j - a_i (27)

c) daca a_i > b_j , atunci

x_ij = b_j(28)

se suprima coloana j iar a_i se inlocuieste cu :

a_i¹ = a_i - b_j (29)

Ca urmare se obtine matricea de transport redusa cu o linie sau cu o coloana fata de matricea initiala. Procedeul se repeta pana cand toate centrele de consum au fost satisfacute.

Cele mai utilizate metode de programare liniara folosite pentru determinarea unei solutii initiale de baza a problemei de transport sunt:

a) Metoda nord - vest (G.B. Dantzig, metoda coltului de nord - vest, sau metoda distribuita in scara)

consta in alegerea variabilei x_ij corespunzatoare celulei situata in prima linie si prima coloana (coltul de nord - vest a matricei de transport), fara a tine seama de costurile c_ij;

daca:

min = a₁(30)

atunci x₁₁ = a_1, iar

x₁₂ = x₁₃ =.= x_1m = 0 (31)

si se suprima prima linie, iar x₂₁ se determina cu relatia:

x₂₁ = min (32)

Daca

min = b₁ (33)

atunci

x₁₁ = b₁

iar

x₂₁ = x₃₁ =.= x_n1 = 0(34)

si se suprima prima coloana, iar x₁₂ se determina din relatia:

x₁₂ = min (35)

Procedeul se repeta determinand succesiv valorile x_ij situate pe prima linie si prima coloana ramasa nesuprimata, din matricea de transport redusa.

Aceasta metoda este foarte expeditiva dar, deoarece nu tine seama de costurile c_ij, solutia de baza obtinuta este destul de indepartata de solutia optima.

b) Metoda costului minim pe linie:

consta in alegerea variabilei x_1j situata pe prima linie a matricei de transport, variabila ce corespunde celulei in care costul c_1j este minim:

c_1h = min ; h= 1,2, . , m(36)

Se determina x_1h din relatia:

x_1h = min (37)

Daca a_i < b_h, atunci x_1h = a₁ iar:

x₁₁ = x₁₂ =.= x_1,h-1 = x_1,h+1 =.= x_1m = 0 (38)

si se suprima coloana h, procedeul continuand cu alegerea variabilei x_1j situata pe linia ce corespunde costului minim ramas dupa suprimarea coloanei h. Procedeul se repeta pana cand toate valorile x_ij situate pe prima linie au fost determinate. In continuare, se procedeaza in mod analog si cu celelalte linii.

c) Metoda costului minim pe coloana:

consta in alegerea variabilei x _i1 situata pe prima coloana a matricei de transport, variabila ce corespunde celulei in care costul c _{i 1} este minim:

c _{r 1} = min ; r= 1,2, . , n(39)

Se determina x _{r 1} din relatia:

x _{r 1}= min (40)

Daca a_r < b₁, atunci x _{r 1} = a_r iar:

X_r2 = X_r3 =.= x_rm = 0(41)

si se suprima linia r, procedeul continuand cu alegerea variabilei x_i1 situata pe prima coloana si care corespunde costului minim ramas dupa suprimarea liniei r.

Daca a_r > b₁, atunci x _{r 1} = b₁ iar:

x₁₁ = x₂₁ =.= x_r-1,1= x_{r+1, 1} =.= x _{n 1} = 0(42)

si se suprima prima coloana, procedeul repetandu-se cu coloana a doua. Se continua in mod analog si cu celelalte coloane.

d) Metoda costului minim al matricei de transport:

se bazeaza pe posibilitatea logica de asociere a cantitatilor de marfa, disponibila sau necesara, cu costul cel mai redus din matricea de transport;

consta din alegerea variabilei x_ij ce corespunde celulei in care costul c_ij este minim.

Daca:

C_rh = min (43)

atunci se determina x_rh din relatia:

x _{r h}= min (44)

Procedeul se repeta in mod analog pana ce toate valorile x_ij au fost determinate.

e) Metoda preferintei duble:

are la baza ideea ca anumite celule din matricea de transport sunt de preferat altora, iar cantitatile x_ij corespunzatoare au prioritate de alocare ;

este necesar sa swe parcurga urmatoarele etape:

se determina in fiecare linie a matricei de transport elementul minim al costului pe linia respectiva si se marcheaza;

se determina in fiecare coloana a matricei de transport elementul minim al costului pe coloana respectiva si se marcheaza din nou celula;

se aloca in celulele dublu marcate volumul de transport maxim posibil de realizat, conform rel. 24;

restul volumelor de transport se repartizeaza in celulele marcate cu un singur marcaj, in ordinea crescatoare a costurilor, pana la epuizarea necesarului sau a disponibilului;

ultimele resturi ale volumelor de transport se repartizeaza in celulele nemarcate, in ordinea crescatoare a costurilor, pana la epuizarea necesarului, respectiv a disponibilului;

se verifica daca suma cantitatilor x_ij de pe fiecare linie si de pe fiecare coloana este egala cu disponibilul a_i, respectiv necesarul b_j.

f) Metoda diferentei minime (metoda Vogel):

consta in stabilirea pe fiecare linie si coloana a diferentelor dintre costurile minime, adica dintre costul cel mai mic si cel mai mic urmator;

in continuare se alege, din liniile sau coloanele matricei, cea mai mare diferenta dintre costurile minime si se afecteaza celulei corespunzatoare cu costul cel mai mic cantitatea maxima disponibila sau necesarul, dupa caz;

se suprima coloana sau linia completata astfel, iar procedeul continua pana la completarea tuturor celulelor matricii de transport, tinand cont de la o etapa la urmatoarea de necesitatea pastrarii echilibrului dintre cerere si disponibil.

Dupa determinarea unei solutii initiale de baza, prin metodele programarii liniare, se procedeaza la verificarea acesteia pentru a afla daca este optima sau nu. Aceasta presupune a arata ca oricare alta solutie conduce la o valoare mai mare a functiei de eficienta si in consecinta, aceasta valoare nu mai poate fi redusa. Pentru aceasta se calculeza evaluarea s_ij pentru celulele tabelei de transport in care:

x_ij ≠ 0 (45)

In cazul in care se constata ca solutia de baza initiala nu este optima se trece imbunatatirea ei, in pasi succesivi, micsorand sau majorandvaloarea functiei de eficienta.

Optimizarea unei solutii initiale de baza se poate realiza pe mai multe cai:

metoda distributiei modificata;

metoda variatiei costurilor.

3.4. Metodele programarii liniare folosite fara utilizarea solutiilor initiale de baza

a) Metoda acoperirii zerourilor

permite obtinerea unei solutii optime pentru o problema de transport, fara a mai fi necesara determinarea unei solutii initiale de baza;

aplicarea metodei presupune parcurgerea urmatoarelor etape:

pe fiecare linie a matricii de transport se determina elementul minim (costul minim, distanta minima etc.), care se scade din toate elementele liniei respective;

in mod identic se determina pe fiecare coloana a matricii de transport, modificata in urma pasului 1, elementul minim care se scade din toate elementele coloanei respective;

dupa parcurgerea etapei 2 se acopera elementele egale cu zero in matricea transporturilor modificata prin suprimarea unui numar de linii si coloane; se vor taia apoi prin cate o linie intrerupta coloanele si liniile ce contin zerouri, zerouri nesituate pe liniile sau coloanele suprimate. Petru o matrice de transport cu n linii si m coloane, numarul total al liniilor suprimate este dat de relatia:

L_n = C_n¹ + C_n² + . + C_n^m = 2ⁿ - 1 (46)

unde n reprezinta numarul de linii al matricii de transport.

Rezulta un numar de 2ⁿ - 1 posibilitati de suprimare a liniilor.

se calculeaza pentru toate cele 2ⁿ - 1 combinatii posibile de suprimare a liniilor cate o suma aferenta de forma:

S_h = Σa_i + Σb_j ; h= 1, 2ⁿ - 1(47)

unde i - liniile care au fost suprimate la acoperirea zerourilor pentru fiecare din cele h acoperiri;

j - coloanele care au fost suprimate la acoperirea zerourilor pentru fiecare din cele h acoperiri.

se determin[ cea mai mic[ valoare a sumelor S_h calculate la pasul anterior, astfel:

S_min = min (48)

daca:

S_min Σa_i = Σb_j(49)

atunci matricea de transport transformata, corespunzatoare combinatiei de acoperire a zerourilor care a determinat S_min, este matricea finala din care se va obtine solutia optima, trecundu-se la alta etapa;

daca S_min care se obtine in urma parcurgerii etapelor anterioare este mai mica decat Σa_i sau Σb_j , atunci se trece la imbunatatirea solutiei obtinutela sfarsitul celei de a treia etape; aceasta imbunatatire se realizeaza calculandu-se o noua matrice a transporturilor, matrice care se obtine astfel:

o      din matricea modificata obtinuta dupa etapa a treia se suprima liniile si coloanele care au determinat S_min;

o      in matricea redusa ce rezulta in urma parcurgerii pasului anterior, se determina elementul minim care se aduna la elementele taiate simultan atat pe linie cat si pe coloana (elemente dublu taiate) si se scade din elementele netaiate, restul elementelor taiate ramanand nemodificate;

in matricea obtinuta in urma parcurgerii etapei anterioare se repeta pasul 3, pasul 4, pasul 5 si pasii 6 si 7 dupa caz, pana cand se obtine matricea finala in care se indeplineste conditia:

S_min = Σa_i = Σb_j

in matricea finala, obtinuta in urma parcurgerii etapei 6 sau 8, necunoscutele x_ij se determina astfel:

o      se considera x_ij = 0, in celulele matricii finale in care:

c_ij ≠ 0 ( 50)

o      se trec literal necunoscutele x_ij in celulele matricii finale, in care:

c_ij 0 ( 51)

o      din conditiile:

Σ x_ij = a_i si Σ x_ij = b_j( 52)

Se determina valoric necunoscutelex_ij ≠ 0.

Daca solutia optima obtinuta in urma parcurgerii ultimei etape este degenerata, optimalitatea ei este justificata prin insasi faptul ca a fost dedusa din matricea finala in care S_min = Σa_i.