Creeaza.com - informatii profesionale despre


Simplitatea lucrurilor complicate - Referate profesionale unice
Acasa » afaceri » transporturi
OPTIMIZAREA TRANSPORTULUI MARFURILOR INTRE PRODUCATORI SI CONSUMATORI

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.

Formularea problemei de transport este urmatoarea: se presupune ca exista un numar de n centre de productie notate Ai (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 Bj , la care 1 < j < m. Cunoscandu-se cantitatile disponibile ai in fiecare centru de productie i si cantitatile necesare bj ale fiecarui centru de consum j, precum si cheltuielile de transport cij (sau distantele dij), de la i la j, se cere sa se in tocmeasca un plan de transport xij , 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 Ai spre cele m centre de consum Bj trebuie sa fie egala cu disponibilul din Ai rezultand astfel sistemul:

xi1 xi2 xij xim =ai , i=1,2,.n (1)

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

X1j + x2j +.+ xij+. + xinj =bj , j=1,2,.m (2)

de m ecuatii liniare cu mn necunoscute;

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

xij > 0, i 1,2,,n; j= 1,2,., m 

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

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:

(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 xij valoarea:

xij = min   (25)

b) daca  ai < bj atunci

xij = ai (26)

se suprima linia i iar bj se va inlocui cu:

bj1 = bj - ai (27)

c) daca ai > bj , atunci

xij = bj  (28)

se suprima coloana j iar ai se inlocuieste cu :

ai1 = ai - bj (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 xij corespunzatoare celulei situata in prima linie si prima coloana (coltul de nord - vest a matricei de transport), fara a tine seama de costurile cij;

daca:

min = a1  (

atunci x11 = a1, iar

x12 = x13 =.= x1m = 0  (31)

si se suprima prima linie, iar x21 se determina cu relatia:

x21 = min   (32)

Daca

min = b1 (33)

atunci

x11 = b1

iar

x21 = x31 =.= xn1 = 0  (34)

si se suprima prima coloana, iar x12 se determina din relatia:

x12 = min   (35)

Procedeul se repeta determinand succesiv valorile xij 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 cij, solutia de baza obtinuta este destul de indepartata de solutia optima.

b) Metoda costului minim pe linie:

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

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

Se determina x1h din relatia:

x1h = min

Daca ai < bh, atunci x1h = a1 iar:

x11 = x12 =.= x1,h-1 = x1,h+1 =.= x1m = 0  (38)

si se suprima coloana h, procedeul continuand cu alegerea variabilei x1j situata pe linia ce corespunde costului minim ramas dupa suprimarea coloanei h. Procedeul se repeta pana cand toate valorile xij 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

Daca ar < b1, atunci x r 1 = ar iar:

Xr2 = Xr3 =.= xrm = 0   (41)

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

Daca ar > b1, atunci x r 1 = b1 iar:

x11 = x21 =.= xr-1,1= xr+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 xij ce corespunde celulei in care costul cij este minim.

Daca:

Crh = min   (43)

atunci se determina xrh din relatia:

x r h= min

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

e) Metoda preferintei duble:

are la baza ideea ca anumite celule din matricea de transport sunt de preferat altora, iar cantitatile xij 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 xij de pe fiecare linie si de pe fiecare coloana este egala cu disponibilul ai, respectiv necesarul bj.

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 sij pentru celulele tabelei de transport in care:

xij ≠ (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:

Ln = Cn1 + Cn2 + . + Cnm = 2n - 1  (46)

unde n reprezinta numarul de linii al matricii de transport.

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

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

Sh = Σai + Σbj ; h= 1, 2n - 1

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 Sh calculate la pasul anterior, astfel:

Smin = min

daca:

Smin ai = bj 

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

daca Smin care se obtine in urma parcurgerii etapelor anterioare este mai mica decat ai sau bj , 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 Smin;

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:

Smin = Σai = Σbj

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

o        se considera xij in celulele matricii finale in care:

cij ( 50)

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

cij ( 51)

o        din conditiile:

xij = ai si xij = bj  ( 52)

Se determina valoric necunoscutele xij

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 Smin = Σai.





Politica de confidentialitate


creeaza logo.com Copyright © 2024 - Toate drepturile rezervate.
Toate documentele au caracter informativ cu scop educational.