Cap 3 _ Optimizarea Transportului in Retele Logistice

33

CAPITOLUL 3 OPTIMIZAREA TRANSPORTULUI N REELELE LOGISTICE

3.1 Cteva caracteristici ale activitii de distribuie

Aa cum am vzut n capitolele anterioare, sarcina logisticianului const n a coordona activitile efectuate de furnizori, ageni de achiziie, specialiti n marketing, membrii canalelor de distribuie i clieni. n timp ce teoria clasic referitoare la distribuie pornete de la premisa c bunurile se afl la productor i ncearc s identifice soluii de a le pune la dispoziia clienilor, cu costuri ct mai mici, specialitii n marketing prefer teoria cunoscut sub numele de logistic de pia, care analizeaz problema n sens invers, pornind de la situaia de pe pia i ajungnd n final la situaia din fabric.

Este clar c gndirea logistic nu pune doar problema distribuiei spre exterior (adic a bunurilor care se mic de la fabric la clieni), ci i problema distribuiei spre interior (adic a bunurilor care se mic de la furnizori la fabric). n cadrul firmelor situate pe poziii de frunte din punct de vedere al logisticii, directorii de distribuie controleaz att distribuia spre interior, ct i distribuia spre exterior.

De regul, firmele i coordoneaz lanurile ofertei cu ajutorul informaiilor. Creteri majore ale eficienei logisticii s-au nregistrat ca urmare a progreselor realizate n tehnologia informaiilor, n special datorit dezvoltrii performanelor calculatoarelor electronice, terminalelor de calculator situate n punctele de vnzare, codificrii unitare a produselor, urmririi prin satelit a distribuiei, transferului electronic de date i transferului electronic de fonduri. Aceste progrese au dat posibilitatea firmelor s fac sau s respecte promisiuni de genul: produsul va fi livrat mine la orele 10 a.m. i s in sub control onorarea acestor promisiuni prin intermediul informaiilor.

n cadrul distribuiei distingem dou mari categorii de activiti: transportul i depozitarea (incluznd aici i gestiunea stocurilor). Dac privim lucrurile din punct de vedere al unei firme productoare, ambele activiti apar att n faza de aprovizionare factori de producie, ct i n faza de desfacere a produselor finite. n ce privete firma specializat n distribuie, aceste activiti reprezint nsi domeniul su de activitate. n perioada actual conducerile firmelor sunt deosebit de preocupate de costul total implicat de realizarea distribuiei fizice, cost care, n unele cazuri se poate ridica la 30%-40% din costul produsului. Avnd n vedere c i costurile publicitare se ridic la nu mai puin de 3% din vnzri, este clar c directorii de marketing ar putea fi rspltii substanial dac ar putea gsi modalitile de a reduce costurile aferente distribuiei. Diminuarea costurilor implicate de activitatea de distribuie va permite firmelor s practice preuri de vnzare mai mici sau s obin marje mai mari ale profiturilor. Principalele elemente ale costului total aferent distribuiei sunt n viziunea lui Philip Kotler1): transportul (37%), stocarea (22%), depozitarea (21%), prelucrarea comenzilor, serviciile oferite clienilor i administrarea distribuiei (20%). Unii experi cred c pot fi realizate economii substaniale n activitatea de distribuie, domeniu care a fost descris ca fiind ultima frontier a economiilor legate de costuri i continentul neexplorat al economiei.

Distribuia nu reprezint numai un cost, ea este i un instrument puternic n cadrul marketingului concurenial. Firmele pot atrage clieni suplimentari oferind servicii mai bune, un ciclu de producie mai rapid sau preuri mai mici, toate acestea putnd fi realizate ca urmare a mbuntirilor aduse distribuiei, n timp ce, atunci cnd nu reuesc s livreze bunurile la timp, firmele pierd o parte important a clienilor. Meninerea pe o anumit pia, pstrarea clienilor actuali i atragerea altora noi poate fi realizat, din punct de vedere al distribuiei, numai prin mbuntirea continu a ambelor activiti specifice: transportul i depozitarea-stocarea.

1) KOTLER, Ph., Managementul marketingului, Editura Teora, Bucureti , 1997.

34

Majoritatea firmelor declar c pentru ele, obiectivul distribuiei const n furnizarea bunurilor potrivite, n locurile potrivite, la momentul potrivit, cu costuri minime. Din nefericire, acesta definiie nu permite o orientare efectiv ctre rezolvarea problemei. Nici un sistem de distribuie nu poate realiza simultan maximizarea serviciilor oferite clientului i minimizarea costului aferent distribuiei. Un nivel maxim de servicii oferite clientului implic deinerea de stocuri mari, realizarea unui transport de nalt nivel calitativ i existena a numeroase depozite, toate acestea ducnd la creterea costului distribuiei. Un cost minim al distribuiei implic transporturi ieftine, stocuri reduse i depozite puine.

Merit remarcat faptul c o firm nu poate ajunge la eficien n realizarea distribuiei cernd pur i simplu fiecrui manager s minimizeze costurile proprii, deoarece adesea costurile distribuiei interacioneaz ntr-o manier invers: managerul de transporturi prefer s foloseasc transportul pe calea ferat, de exemplu, n locul celui aerian, deoarece astfel pltete mai puin pentru transport. Dar cum transportul pe calea ferat este mai lent, expedierea mrfurilor cu trenul imobilizeaz capitalul circulant pentru o perioad mai lung, ntrzie efectuarea plii de ctre client i i poate determina pe clieni s cumpere de la firmele concurente care ofer servicii mai rapide.

Compartimentul de expediie utilizeaz containere ieftine pentru a reduce la minimum costurile legate de expedierea mrfurilor. Acest fapt duce ns la o rat nalt de depreciere a bunurilor n timpul transportului, ceea ce produce o impresie proast asupra clienilor.

Coordonatorul activitii de stocare prefer s dein stocuri mici pentru a reduce costurile aferente. ns aceast politic duce la nmulirea situaiilor de lichidare a stocurilor i de imposibilitate a onorrii comenzilor, determin creterea numrului de documente i face necesar producerea de serii speciale din anumite produse, precum i expedierea produselor prin mijloace rapide, cu costuri ridicate.

Dat fiind faptul c activitile de distribuie implic acceptarea unor compromisuri, deciziile trebuie luate pe baza analizei efectuate asupra sistemului n totalitatea sa.

Punctul de pornire n proiectarea unui sistem eficient de distribuie l reprezint studierea a ceea ce doresc clienii i a ceea ce ofer firmele concurente. Clienii sunt interesai de livrarea bunurilor la timp, de disponibilitatea furnizorilor de a le ndeplini nevoile urgente, de manipulare atentat a mrfurilor de disponibilitatea furnizorilor de a-i recupera bunurile defecte i de a efectua repede reaprovizionarea cu alte bunuri precum i de disponibilitatea furnizorului de a stoca marfa pentru clieni.

Firma trebuie s determine importana relativ a serviciilor oferite i, de asemenea, i standardele serviciilor oferite de firmele concurente. n mod normal ea va dori s ofere cel puin acelai nivel de servicii ca i concurena, dar obiectivul su este de regul maximizarea profiturilor i nu a vnzrilor.

Din perspectiva celor dou activiti principale ale distribuiei n capitolul de fa am inclus o analiz a posibilitilor de optimizare a activitii de transport a bunurilor de la furnizori la clieni de-a lungul lanului ofertei.

3.2. Optimizarea fluxurilor de materii prime, materiale i produse finite

n cadrul acestui subcapitol vom prezenta o modalitate prin care poate fi modelat activitatea de deplasare a materiilor prime, materialelor i a produselor finite de la productorii acestora la consumatori. Pentru aceasta, considerm dat o reea de transport n cadrul creia o cantitate Q dintr-un anumit produs, disponibil ntr-un numr de puncte numite surse trebuie transportat n alte puncte, numite destinaii, a cror cerere total este tot Q. Reeaua poate conine i alte puncte prin care produsul este doar n trecere, de unde i denumirea de puncte intermediare sau de tranzit. n acest context, principalele probleme de optimizare care se pot formula sunt:

1) Din punct de vedere al costului. Cunoscnd costul transportului unei uniti de produs ntre dou puncte ale reelei se dorete reorganizarea transportului de aa manier

35

nct cererile din nodurile destinaie s fie satisfcute la un cost total minim. n acest caz, nu exist plafoane n ceea ce privete cantitatea transportat pe o rut sau alta. Modelarea matematic a acestui context a condus la problema generala de transfer al crei caz particular l constituie problema clasic de transport.

2) Din punct de vedere al posibilitilor de transfer ale reelei. De aceasta dat sunt date capacitile de transfer ale diferitelor rute, capaciti ce nu pot fi depite i se pune problema dac reeaua permite satisfacerea n totalitate a cererilor n punctele de destinaie. Nici o referire la cheltuielile implicate de transportul produsului pe diferite rute nu este formulat explicit. n acest caz rezult o problem de flux maxim n reea. Dac valoarea fluxului este egal cu Q atunci cererile sunt integral acoperite, altfel cererile n unele puncte de destinaie sunt satisfcute parial.

3) Combinarea celor dou puncte de vedere formulate anterior se impune, ea fiind serios motivat de practica economic. Mai concret, cunoscnd costurile unitare de transport, precum i capacitile de transfer ale rutelor se pune problema de a satisface ct mai bine cererile n punctele de destinaie, la un cost total minim.

1. Formalizarea problemei

Reelei de transport considerat anterior i va corespunde un graf G = (X, E), finit, fr bucle, simplu i neorientat sau parial orientat (n caz c anumite rute pot fi parcurse ntr-un singur sens). Mulimea nodurilor X a grafului se va compune din:

surse a cror mulime o notm cu S; destinaii a cror mulime o notm cu T; puncte intermediare. Fiecare muchie e = {i, j}E va genera dou rute orientate notate (i, j) i (j, i)

corespunztoare celor dou sensuri de parcurgere a muchiei. Fiecrei rute orientate (i, j) i vor corespunde: o capacitate cij indicnd limita superioar a cantitii de produse ce pot fi transportate

de la i la j; un cost unitar de transport pij pltit pentru deplasarea unei uniti de produs de la i la

j.

n cazul cel mai general, cc jiij dup cum i costurile de transport pot depinde de sensul de parcurgere a rutei respective.

Fr a restrnge generalitatea consideraiilor anterioare vom putea presupune c orice muchie {i, j} a grafului poate fi parcurs n ambele sensuri. Dac ntr-un caz concret o anumit rut orientat, s zicem (i, j) este blocat, vom realiza acest lucru impunnd un cost unitar de transport foarte mare: pij = + sau o capacitate de transport nul, cij = 0.

Convenim ca toate capacitile rutelor orientate s fie exprimate prin numere ntregi pozitive (cij ) i toate costurile unitare de transport s fie date prin numere reale nenegative 0pij .

Pentru fiecare surs i S vom nota cu ai disponibilul su de produs. Cererea destinaiei j va fi notat cu bj .Convenim ca mrimile ai cu i S i bj cu j s fie numere ntregi pozitive.

n plus:

==

Tjj

SibaiQ . (3.1)

Introducem n graful G urmtoarele elemente noi: un nod s si rutele orientate (s, i), i S cu capacitile csi =ai i costurile unitare de

transport psi = 0; un nod t i rutele orientate (j, t), j cu cjt = bj , pjt = 0.

36

Procedura de determinare a fluxului maxim de cost minim nu necesit testarea prealabil a capacitii reelei de a permite satisfacerea cererilor de consum ale destinaiilor. Ea ofer cel mai mare flux posibil n reea ntre S i T realizabil la costul cel mai mic.

Pentru uniformizarea notaiei vom presupune c orice rut orientat ntre dou puncte ale reelei poate fi permis. Rutele (i, j) nepermise n realitate le vom bloca prin cij=0 , n acest fel operndu-se doar pe rutele permise.

2. Modelul matematic

S se determine n reeaua G = (X, E) un flux ( ) )0f ca (convenim ff iiXj,iij == , care satisface condiiile:

{ }

(3.5) 0

(3.4) re)intermedia nodurilen fluxului a conservare de conditiile(

(3.3) ,

(3.2)

cf

Qf

ts,X-) i,j(ff

Qf

ijij

Xjjt

Xjji

Xjij

Xjsj

=

=

=

i care minimizeaz funcia cost

(3.6) . min

=

Xi,jijij fp)P(f)(

Vom efectua urmtoarele dou modificri: constanta Q reprezentnd necesarul de deplasat de la s la t va fi privit n continuare

ca o variabil a modelului i va fi renotat cu v (Q = v); n loc de a minimiza obiectivul (3.6) vom maximiza expresia

0,1,2,... valorile lua va ceparametru un este unde

,fpv i,j

ijij

Se obine n acest fel urmtoarea colecie de probleme de maximizat:

37

( )

=+

=

=

)(3.6' max

)(3.5' 0

)(3.4' 0

)(3.3' 0

)(3.2' 0

fpv-

cf

vf-

ff

vf

Xi,jijij

ijij

Xjjt

Xjji

Xjij

Xjsj

Funcia obiectiv (3.6') introduce un premiu pentru fiecare unitate de flux transportat de la s la t, caz n care (3.6') are semnificaia unui profit net rezultat din transportarea a v uniti de produs la s la t. Acest profit se obine din premiul v din care se scad cheltuielile de transport

i jijij fp .

Pentru suficient de mare, problemele (3.2')-(3.6') rezolv problema (3.2)-(3.6) oferind fluxul de cost minim dintre toate fluxurile de valoare maxim de la s la t.

Cu ct este mai mare algoritmul de rezolvare urmrete s mreasc pe v, iar pentru un constant ofer valoarea maxim funciei obiectiv. Analiznd soluia modelului (3.2')-(3.6') observm c:

dac ,Qv problema original (3.2)-(3.6) are soluie;

dac ,Q v < reeaua de transport nu poate satisface cererile destinaiilor.

Rezolvnd problema (3.2') - (3.6') pentru = 0, 1, 2... obinem un ir de fluxuri succesive f(0), f(1), f(2),, ultimul fiind fluxul optim cutat.

Obinerea efectiv a unui flux maxim de cost minim, adic a unei soluii a modelului (3.2)-(3.6), se poate face n mai multe moduri (vezi Ciobanu, Gh., Nica, V., Musta, Fl., Mrcine, V. (1996), "Cercetri operaionale cu aplicaii n economie. Teoria grafurilor i analiza drumului critic"):

prin parcurgerea unui numr de iteraii succesive n cadrul crora, ntr-o prim etap se determin drumul de cost minim de la s la t, iar n etapa a doua de transport pe acesta fluxul maxim posibil;

construind un flux maxim de la s la t n reeaua de transport fr a ine seama de costuri, i apoi transformndu-l ntr-unul de cost minim prin eliminarea tuturor circuitelor de cost negativ corespunztoare fluxului maxim determinat n prim instan, prin reorientarea unora dintre fluxurile existente pe anumite muchii;

prin construirea dualului modelului (3.2)-(3.6) i utilizarea teoremei ecarturilor complementare pentru determinarea soluiilor celor dou probleme.

Deoarece prezentarea acestor algoritmi i euristici a fost deja fcut n cadrul cursurilor de Cercetri Operaionale, vom prezenta n continuare cteva studii de caz didactice referitoare la acoperirea cererii clienilor la un cost total de transport ct mai redus.

3.3 Aplicaii, Studii de caz

S3-1. Optimizarea distribuiei de produse finite a unei firme

38

O firm produce un anumit bun n centrele de producie situate n nodurile surs s1 i s2, clienii firmei fiind situai n nodurile t1, t2, t3 ale reelei din figura 3.7. Producia lunar a celor dou centre de producie este de a1 = 15 i respectiv a2 = 10 uniti de produs, n timp ce clienii firmei solicit lunar b1 = 10, b2 = 5 i respectiv b3 = 10 uniti de produs. ntre nodurile surs i cele destinaie se afl o reea de drumuri a cror capacitate de transport (n uniti de produs) este nscris n paranteze pe muchiile reelei din figura 3.1, costul unitar (n uniti monetare pe unitatea de produs) fiind nscris pe fiecare muchie a reelei n afara parantezei. Firma dorete s satisfac cererea clienilor situai n nodurile destinaie cu cele mai mic cost de transport posibil.

Soluie

Etapa 1. Construirea reelei standard

Pornind de la reeaua din Figura 3.1 construim reeaua standard adugnd un unic nod surs s i muchiile orientate (s, s1), (s, s2) i un unic nod destinaie t i rutele orientate (t1, t), (t2, t), (t3, t). Pe aceste rute fictive introduse capacitile vor fi egale cu oferta centrelor de producie (la intrarea n reea), respectiv cu cererile consumatorilor (la ieirea din reea). Deoarece aceste rute sunt fictive, costurile unitare de transport vor fi nule. Reeaua rezultat se afl n Figura 3.2. Soluia la problema pe care firma o are de rezolvat const n construirea unui flux maxim de cost minim de la s la t n reeaua standard. Vom realiza acest lucru progresiv, prin parcurgerea n etapa a doua a unui numr de iteraii n cadrul crora vom transporta uniti de flux de la s la t pe drumurile de cost minim.

Etapa 2. Construirea fluxului maxim de cost minim de la s la t.

s1

s2

t3

t2

t1 (5) (10)

(5)

1 (5) (6)

(8)

5

(7)

6 3

4

9

2

Figura 3.1 Reeaua de distribuie a firmei

a1 = 15

a2 = 10

b1 = 10

b2 = 5

b3 = 10

s1

s2

t3

t2

t1 (5) (10)

(5)

1 (5) (6)

(8)

5

(7)

6 3

4

9

2

Figura 3.2 Reeaua standard

(15)

(10)

(10)

(5) 0

(10)

t s

0

0 0

0

39

Iteraia 1

Pasul 1. n reeaua costurilor determinm printr-una din procedurile de etichetare cunoscute (Dijkstra sau Ford, de exemplu), drumul (drumurile) de cost minim de la s la t. n Figura 3.3 etichetele nodurilor reprezint cel mai mic cost al unui drum de la s la nodul respectiv, n timp ce orientarea reprezint precedenele.

Aa cum se observ din Figura 3.3, cel mai redus cost de transport a unei uniti de produs de la s la t este de 2 uniti monetare (eticheta nodului t) i corespunde drumului s s1 t1 t.

Pasul 2. Pe drumul de cost minim de la s la t determinat la pasul 1 transportm cantitatea maxim posibil de produs, cantitate egal cu minimul capacitilor reziduale ale arcelor reelei din Figura 3.2 (vezi algoritmul Ford-Fulkerson).

Drum / Capaciti reziduale ale arcelor Numr de uniti de produs (flux) transportate

s s1 t1 t

5

Prin transportul celor 5 uniti de flux ruta s1 t1 s-a saturat. Aceast rut se va bloca la iteraia urmtoare prin orientarea sa strict n sensul t1 s1. n reeaua din Figura 3.4 se afl fluxul f1 cu valoarea de 5 uniti de flux (produs).

s1

s2

t3

t2

t1

1

6 3

4

9

2

Figura 3.3 Determinarea drumului de cost minim de la s la t

0 t

s

0

0 0

0 p(s) = 0

p(s1) = 0

p(s2) = 0

5

p(t3) = 3

p(t2) = 4

p(t1) = 2

p(t) = 2

s1

s2

t3

t2

t1 (5) (10)

(5)

(5) (6)

(8)

(7)

Figura 3.4 Construirea fluxului f1

(15)

(10)

(10)

(5)

(10)

t s

5 5

5

15 5 10

40

Iteraia 2

Pasul 1. Determinm drumul de cost minim n reeaua costurilor adaptat fluxului din Figura 3.4. Drumul de cost minim este s s2 t3 t cu valoarea de 3 uniti monetare (vezi Figura 3.5).

Pasul 2. Construim noul flux pornind de la fluxul f1 din Figura 3.4.


s s2 t3 t

6

Valoarea noului flux este v(f2) = v(f1) + 6 = 11 uniti de flux.

n continuare se vor relua paii 1 i 2 n cadrul unor noi iteraii pn n momentul n care, n reeaua costurilor, nu mai putem pune n eviden nici un drum (succesiune de arce orientate n acelai sens).

Iteraia 3

Pasul 1. Determinarea drumului de cost minim n reeaua costurilor adaptat fluxului din Figura 3.6.

s1

s2

t3

t2

t1

1

6 3

4

9

2


0 t

s

0

0 0

0 p(s) = 0

p(s1) = 0

p(s2) = 0

5

p(t3) = 3

p(t2) = 4

p(t1) = 9

p(t) = 3

10 6 10

s1

s2

t3

t2

t1 (5) (10)

(5)

(5) (6)

(8)

(7)


(15)

(10)

(10)

(5)

(10)

t s

5 5

5

6

6 6

41

Drumul de cost minim este s s2 t2 t cu valoarea de 4 uniti monetare.

Pasul 2. Construim noul flux pornind de la fluxul f2.


s s2 t2 t

4


Iteraia 4

Pasul 1. Determinarea drumului de cost minim n reeaua costurilor adaptat fluxului din Figura 3.8.

s1

s2

t3

t2

t1

1

6 3

4

9

2


0 t

s

0

0 0

0 p(s) = 0

p(s1) = 0

p(s2) = 0

5

p(t3) = 10

p(t2) = 4

p(t1) = 9

p(t) = 4

4 5 5

s1

s2

t3

t2

t1 (5) (10)

(5)

(5) (6)

(8)

(7)


(15)

(10)

(10)

(5)

(10)

t s

5 5

5

10

6 6

4

4

s1

s2

t3

t2

t1

1

6 3

4

9

2


0 t

s

0

0 0

0 p(s) = 0

p(s1) = 0

p(s2) = 1

5

p(t3) = 11

p(t2) = 5

p(t1) = 10

p(t) = 5

42

Drumul de cost minim este s s1 s2 t2 t cu valoarea de 5 uniti monetare.



s s1 s2 t2 t

1


Iteraia 5

Pasul 1. Determinarea drumului de cost minim n reeaua costurilor adaptat fluxului f4.

Drumul de cost minim este s s1 t2 t1 t cu valoarea de 14 uniti monetare.


10 5 1 1

s1

s2

t3

t2

t1 (5) (10)

(5) 1

(5) (6)

(8)

(7)


(15)

(10)

(10)

(5)

(10)

t s

5 5

6

10

6 6

5

5

s1

s2

t3

t2

t1

1

6 3

4

9

2


0 t

s

0

0 0

0 p(s) = 0

p(s1) = 0

p(s2) = 1

5

p(t3) = 15

p(t2) = 9

p(t1) = 14

p(t) = 14

43


s s1 t2 t1 t

5


Iteraia 6


Drumul de cost minim este s s1 t2 t3 t cu valoarea de 15 uniti monetare.


9 10 8 5

s1

s2

t3

t2

t1 (5) (10)

(5) 1

(5) (6)

(8) 5

(7)

5


(15)

(10)

(10)

(5)

(10)

t s

5 10

11

10

6 6

5

5

s1

s2

t3

t2

t1 (5) (10)

(5) 1

(5) (6)

(8) 5

(7) 4

9


(15)

(10)

(10)

(5)

(10)

t s

5 10

15

10

6 10

5

5

s1

s2

t3

t2

t1

1

6 3

4

9

2


0 t

s

0

0 0

0 p(s) = 0

p(s1) = 0

p(s2) = 1

5

p(t3) = 15

p(t2) = 9

p(t1) = 14

p(t) = 15

44


s s1 t2 t3 t

4

Valoarea noului flux este v(f6) = v(f5) + 6 = 25 uniti de flux, egal cu cantitatea de produs oferit de centrele de producie, respectiv cerut de ctre beneficiari. Putem concluziona n acest moment c reeaua de transport permite satisfacerea cererilor clienilor firmei.

Iteraia 7


Din Figura 3.15 se observ c nu mai exist nici un drum compus din arce orientate de la s la t i nesaturate, prin urmare algoritmul se oprete. Fluxul f6 este fluxul maxim (v(f6) = 25 uniti de flux) de cost minim. Costul acestui flux, respectiv al transportrii celor 25 de uniti de produs de la centrele de producie la beneficiari se determin prin nsumarea produselor ntre fluxul corespunztor fiecrei rute i costul unitar de transport al acesteia:

==

E)j,i(ijij6 pf)f(C 179 uniti monetare.

Maximalitatea fluxului f6 este ilustrat prin aplicarea procedeului de marcaj n Figura 3.16. Se observ c putem marca doar nodul s, tietura de capacitate minim separnd acest nod de restul nodurilor reelei standard.

4 5 7 4

s1

s2

t3

t2

t1

1

6 3

4

9

2


0 t

s

0

0 0

0 p(s) = 0

5

s1

s2

t3

t2

t1 (5) (10)

(5) 1

(5) (6)

(8) 5

(7) 4

9

Figura 3.16 Testarea maximalitii fluxului f6

(15)

(10)

(10)

(5)

(10)

t s

5 10

15

10

6 10

5

5 [+]

45

S3-2. S presupunem c n reeaua din Figura 3.1 nu sunt precizate capacitile maxime de transport ale muchiilor. Care este capacitatea minim de transport cu care ar trebui dotate toate muchiile reelei de transport astfel nct s se poat asigura satisfacerea integral a cererilor n nodurile destinaie?

S3-3. Problema de cerere i ofert independent de costul de transport

Un produs este disponibil n punctele 1, 2, 3 n cantitile a1 = 16, a2 = 16, a3 = 18 i solicitat n punctele 7 i 8 n cantitile b7 = 20 i b8 = 30. ntre surse i destinaii exist rute de legtur conform reelei din figura 3.19. Toate rutele sunt neorientate. Capacitile rutelor sunt notate ntre paranteze i sunt valabile, acolo unde este cazul, n ambele sensuri de propagare. S se stabileasc n ce msur cererile pot fi satisfcute.

Se completeaz reeaua cu nodurile s i t i cu rutele orientate (s, 1), (s, 2), (s, 3) de capaciti 25, 15 i 30 i rutele orientate (7, t), (8, t), de capaciti 30 i 40. Se propag n reea un flux de la s la t. Dac valoarea acestui flux este egal cu 70 ( = 30 + 40) uniti de flux, atunci cererile sunt acoperite n ntregime.

Utiliznd varianta uzual a algoritmului Ford-Fulkerson, n prima etap se propag un flux nenul de valoare ct mai mare posibil i compatibil. Pentru aceasta vom identifica drumuri de la s la t pe care le saturm i, corespunztor, orientm arcele:

1 = (s, 1, 7, t) 1 = min (25, 8, 30) = 8 2 = (s, 1, 4, 7, t) 2 = min (17, 15, 15, 22) = 15 3 = (s, 1, 2, 4, 6, 7, t) 3 = min (2, 5, 7, 8, 8, 7) = 2 4 = (s, 2, 4, 6, 7, t) 4 = min (15, 5, 6, 6, 5) = 5 5 = (s, 2, 5, 4, 6, 8, t) 5 = min (10, 9, 5, 1, 15, 40) = 1 6 = (s, 2, 5, 6, 8, t) 6 = min (9, 10, 8, 14, 39) = 8 7 = (s, 2, 5, 8, t) 7 = min (1, 2, 12, 31) = 1 8 = (s, 3, 2, 5, 8, t) 8 = min (30, 8, 1, 11, 30) = 1 9 = (s, 3, 5, 8, t) 9 = min (29, 15, 10, 29) = 10 10 = (s, 3, 8, t) 10 = min (19, 10, 19) = 10

Figura 3.17

1 7

2

3 8

4

5

6

25

15

30

30

40

(8)

(5)

(8)

(15)

(7)

(11)

(15) (10)

(8) (8)

(8)

(12) (15)

(10)

(15)

(5)

Figura 3.18

1 7

2

3 8

4

5

6 61 61 (5

(8)

(5)

(8)

(15)

(7)

(11)

(15) (10)

(8)

(8) (12)

(10)

(15)

s t (15) 15.

2 +

1+

15.

7.

11.

10 +

1

10. 12.

15.

8.

8.

8.

46

Figura 3.19

1 7

2

3 8

4

5

6

[+] s t

[+s]

[+3]

[2] [+5]

[+3]

Noduri marcate Noduri nemarcate

Orice drum care unete intrarea s cu ieirea t conine cel puin o rut saturat. n acest fel, s-a propagat n reea un flux complet de-a lungul drumurilor marcate n reeaua din figura 3.18. Fluxul complet are valoarea:

v() = =

10

1ii = 61 uniti de produs.

n etapa urmtoare, pentru determinarea fluxului de valoare maxim, vom aplica procedeul de marcare, n reeaua din figura 3.18 se pot efectua urmtoarele marcaje (figura 3.19):

Fluxul curent, a crui valoare este de 61 uniti, este fluxul de valoare maxim pentru c nu poate fi marcat nodul final t. Valoarea sa fiind mai mic dect 70 nseamn c nu toate cererile sunt acoperite integral; destinaia 8 primete numai 31 uniti din cele 40 solicitate. Satisfacerea cererii restante se poate face numai prin mrirea capacitilor unor rute de legtur. Aceste rute le identificm n tietura de capacitate minim.

n etapa final se pune n eviden tietura de capacitate minim, separnd nodurile marcate de cele nemarcate. Avnd n vedere c S* = {s, 1, 2, 3, 4, 5} i T* = {6, 7, 8, t} tietura cuprinde arcele:

(S*, T*) = {(1, 7) , (4, 7) , (4, 6) , (5, 6) , (5, 8) , (3, 8)}

Suma capacitilor celor ase rute din tietur exact 61, ceea ce confirm faptul c fluxul curent este de valoare maxim.

Orice cantitate suplimentar de flux trebuie s treac prin una sau mai multe rute din cele ase ale tieturii minime. S presupunem c cele 9 uniti de flux necesare pentru a satisface cererea destinaiei 8 le repartizm pe muchii, crescnd capacitatea muchiei [1, 7] cu 2 uniti, capacitatea muchiei [5, 6] cu 6 uniti i capacitatea muchiei [4, 7] cu 1 unitate.

Algoritmul Ford Fulkerson se reia prin marcarea nodurilor. Se identific succesiv lanurile 11, 12 i 13 conform figurilor 3.20, 3.21 i 3.22.

1 7

2

3 8

[+] s t

[+s]

[+3]

[2] [+1]

[+7]

11 : [+8]

Figura 3.20

47

Avem: 3sc = 30 21 + 0 = 9, 32c = 8 1 + 0 = 7, 21c = 5 0 + 2 = 7,

17c = 10 8 + 0 = 2, 78c = 10, tc8 = 40 31 + 0 = 9 de unde:

11 = min (9, 7, 7, 2, 10, 9) = 2.

Avem: 3sc = 30 23 + 0 = 7, 35c = 15 10 + 0 = 5, 54c = 5 1 + 0 = 4,

47c = 8 7 + 0 = 1, 78c = 10 2 + 0 = 8, tc8 = 40 33 + 0 = 7 de unde:

12 = min (7, 5, 4, 1, 8, 7) = 1 Avem:

3sc = 30 24 + 0 = 6, 35c = 15 11 + 0 = 4, 56c = 14 8 + 0 = 6, 68c = 15 9 + 0 = 6, tc8 = 40 34 + 0 = 6

de unde: 13 = min (6, 4, 6, 5, 6) = 4. Repetarea marcrii duce la situaia din figura 3.23, n care nodul final t nu mai poate fi

marcat:

3 8

5

6

[+] s t

[+s]

[+3]

[+5]

[+6]

13 : [+8]

Figura 3.22

Figura 3.23

1 7

2

3 8

4

5

6 68 68 (5)

(10)

(5)

(8)

(15)

(7)

(11)

(15) (10)

(8)

(12)

(10)

(16)

s t (15) 15.

3+

15.

7.

11.

15.

1+ 1

+

10. 12.

16.

8.

12

8 +

+ 2 +

1

+

(14)

7

3 8

4

5

[+] s t

[+s]

[+3]

[+5]

[+4]

[+7]

12 : [+8]

Figura 3.21

48

Valoarea fluxului propagat n reea este:

v() = 61 + 11 + 12 + 13 = 68 70.

Noua tietur de capacitate minim are n componen arcele:

(S*, T*) = {(1, 7) , (1, 4) , (2, 4) , (2, 5) , (3, 5) , (3, 8)} i are valoarea c(S*, T*) = 68.

Pentru ca cererile s fie satisfcute, se mrete capacitatea muchiei [3, 5] cu 2 uniti. Relund algoritmul se identific lanurile de augmentare 14 i 15 conform figurilor 3.24 i 3.25:

Avem: 3sc = 30 28 + 0 = 2, 35c = 17 15 + 0 = 2, 56c = 14 12 + 0 = 2,

67c = 8 7 + 0 = 1, 78c = 10 3 + 0 = 7, tc8 = 40 38 + 0 = 2, de unde:

14 = min (2, 2, 2, 1, 7, 2) = 1

Avem: 3sc = 30 29 + 0 = 1, 35c = 17 16 + 0 = 1, 56c = 14 13 + 0 = 1,

68c = 15 13 + 0 = 2, tc8 = 40 39 + 0 = 1 de unde:

15 = min (1, 1, 1, 2, 1) = 1. n acest moment valoarea fluxului propagat este v() = 68 + 14 + 15 = 70. Cererea

este acoperit integral, iar n figura 3.26 sunt date valorile fluxurilor pe fiecare arc.

7

3 8

5

6

[+] s t

[+s]

[+3]

[+5]

[+6]

[+7]

14 : [+8

]

Figura 3.24

3 8

5

6

[+] s t

[+s]

[+3]

[+5]

[+6]

15 : [+8]

Figura 3.25

49

Figura 3.26

1 7

2

3 8

4

5

6

30

15 (5)

(10)

(5)

(8)

(15)

(7)

(11)

(17) (10)

(8)

(12)

(10)

(16)

3

15

7

11

17

2

10 12

16

8

14

10

4

(14)

25

30 40

(8) 8

(15) 14

Important:

1. n optimizarea activitii de transport n cadrul reelei logistice analizate n proiectele voastre, n determinarea drumurilor minime pe care se va face transportul bunurilor putei utiliza oricare dintre algoritmii sau euristicile cu care ai lucrat la cursul / seminarul de Cercetri Operaionale.

2. De asemenea, optimizarea transportului poate consta n rezolvarea unor probleme de comis-voiajor prin care se vor stabili traseele de livrare a bunurilor ctre mai muli clieni sau depozite.

Cap 3 _ Optimizarea Transportului in Retele Logistice

Documents

Transcript of Cap 3 _ Optimizarea Transportului in Retele Logistice