247

PROBLEME DE TRANSPORT CU CENTRE INTERMEDIARE

Dumitru ZAMBICHI, Dr. n t. fi z.-mat.,Conf. univ., ASEM

Iacob CIOBANU,Dr. n t. fi z.-mat.,Conf. univ., ATIC

Problema transporturilor este o problem de programare liniar de o structur particular, relativ simpl, fapt ce a permis crearea unor metode efective de rezolvare, aplicabile cu succes la probleme de dimensiuni mari.

I. Probleme de transport cu centre intermediare

Probleme de transport cu centre intermediare se pun de obicei atunci cnd se urmrete ntocmirea unui plan optim de transport a unor materiale care pe parcursul lor de la expeditor la consumator trebuie s se opreasc temporar n aceste centre, avnd la baz diverse motive. Spre exemplu, n calitate de centre intermediare pot servi locurile de schimbare a mijloacelor de transport, depozitele vamale etc. Probleme de transport cu centre inter-mediare pot avea urmtoarele aspecte:

1) cazul, cnd capacitatea centrelor intermediare este egal cu cantitile ce afl uiesc de la centrele de expediie (iniiale) i respectiv cu cantitile necesare centrelor de destinaie (de consum). n acest caz, rezolvarea pro-blemei se reduce la soluionarea a dou probleme obinuite de transport (o problem de transport de la centrele iniiale la centrele intermediare i o problem de transport de la centrele intermediare la centrele de consum);

2) cazul, cnd capacitatea centrelor intermediare sunt mai mari dect cantitile ce urmeaz s treac prin ele. Acest caz se poate subdivide i el n alte dou subcazuri:

a) capacitile centrelor intermediare sunt nelimitate;b) capacitile centrelor intermediare sunt limitate.Vom examina subcazul n care capacitile centrelor intermediare sunt

nelimitate. Datele iniiale ale problemei sunt incluse n tabelul 1.

248

Tabelul 1. Tabelul iniial al problemei de transport

Centre in-termediare

Expeditori ConsumatoriA1 A2 Am B1 B2 Bn

I1I2I k

c11c'21 c'k1

c12 c'22 c'k2

c1mc'2m c'km

c11c''21 c''k1

c12c''22 c''k2

c1nc''2n c''kn

ai a1 a2 am bj b1 b2 bn

Pentru a rezolva problema se stabilesc cheltuielile de transport de la fi ecare expeditor la fi ecare unitate consumatoare, astfel:

^ `^ `^ `^ `^ `^ `^ `.;;;min

.......................................................................;;;;min

........................................................................;;;;min

.......................................................................;;;;min;;;;min

.......................................................................;;;;min;;;;min

2211

12121111

22221122

122122111221

12211111

212221121112

112121111111

knkmnmnmmn

kkmmmm

knknnn

kk

knknnn

kk

kk

ccccccc

ccccccc

ccccccc

cccccccccccccc

cccccccccccccc

ccccccccc

ccccccccc

ccccccccc

ccccccccc ccccccccc

ccccccccc ccccccccc

Rezultatele obinute se nscriu n tabelul 2.

249

Tabelul 2. Tabelul problemei de transport dup stabilirea centrelor intermediare

BjAi

B1 B2 ... Bn ai

A1 11c 12c ... nc1 1a

A2 21c 22c ... nc2 2a

... ... ... ... ... ...

Am 1mc 2mc ... mnc ma

bj 1b 2b ... nb

n interiorul tabelului n fi ecare celul se arat costul cij de transport minim pentru o unitate de materie prim (de marf) de la fi ecare expeditor la fi ecare consumator prin centrele intermediare. n fi ecare celul se poate arta numrul centrului intermediar prin intermediul cruia s-a calculat cos-tul minim de transport pentru o unitate de materie prim.

Se rezolv problema ca orice problem de transport i ca rezultat obi-nem soluia optim.

Exemplul 1. Datele iniiale ale problemei sunt nscrise n tabelul 3.

Tabelul 3. Tabelul iniial al problemei de transport din exemplu1 1

Centre Expeditori Consumatori

A1 A2 A3 B1 B2 B3 B4I1I2

58

79

64

1215

1611

1810

1720

ai 120 220 280

bj 110 140 170 200

250

Avem: c11 = min{5+12; 8+15}=17; c21 = min{7+12; 9+15}=19;c12 = min{5+16; 8+11}=19; c22 = min{7+16; 9+11}=20;c13 = min{5+18; 8+10}=18; c23 = min{7+18; 9+10}=19;c14 = min{5+17; 8+20}=22; c24 = min{7+17; 9+20}=24;c31 = min{6+12; 4+15}=18; c32 = min{6+16; 4+11}=15;c33 = min{6+18; 4+10}=14; c34 = min{6+17; 4+20}=23;

Aadar, am obinut problema de transport, prezentat n tabelul 4.

Tabelul 4. Tabelul problemei de transport din exemplu1 1 dup stabilirea

centrelor intermediare

BjAi

B1 B2 B3 B4 ai

A1 1I 17 2I 19 2I 18 1I 22 120

A2 1I 19 2I 20 2I 19 1I 24 220

A3 1I 18 2I 15 2I 14 1I 23 280

bj 110 140 170 200620

620

Deteminm soluia optim a problemei prin una din metodele cunoscute (spre exemplu, metoda potenialelor):

11280;

0170110019003001000110

min

ZX .

n cazul cnd capacitile centrelor intermediare sunt limitate pentru a rezolva problema poate fi aplicat, cu unele modifi cri, metoda diferenelor comparate [1].

251

II. Probleme de transport cu centre intermediare i funcia scop (timpul maxim) examinat la minim

Datele iniiale a unei astfel de probleme sunt prezentate n tabelul 5.

Tabelul 5. Tabelul iniial al probleme de transport

Centre in-termediare

Expeditori Consumatori

A1 A2 Am B1 B2 Bn

I1I2I k

t11t'21 t'k1

t12 t'22 t'k2

t1mt'2m t'km

t11t''21 t''k1

t12t''22 t''k2

t1nt''2n t''kn

ai a1 a2 am

bj b1 b2 bn

Pentu a rezolva problema se determin timpul necesar de la fi ecare expeditor la fi ecare consumator, astfel:

^ `^ `^ `^ `^ `^ `^ `.;;;min

.....................................................................;;;;min

.....................................................................;;;;min

.....................................................................;;;;min;;;;min

.....................................................................;;;;min;;;;min

2211

12121111

22221122

122122111221

12211111

212221121112

112121111111

knkmnmnmmn

kkmmmm

knknnn

kk

knknnn

kk

kk

ttttttt

ttttttt

ttttttt

tttttttttttttt

tttttttttttttt

ccccccccc

ccccccccc

ccccccccc

ccccccccc ccccccccc

ccccccccc ccccccccc

Ca rezultat, obinem tabelul 6.

252

Tabelul 6. Tabelul problemei de transport dup stabilirea centrelor intermediare

BjAi

B1 B2 ... Bn ai

A1 11t 12t ... nt1 1a

A2 21t 22t ... nt2 2a

... ... ... ... ... ...

Am 1mt 2mt ... mnt ma

bj b1 b2 ... bn

n interiorul tabelului n fi ecare celul se arat timpul tij necesar pentru a transporta marfa de la fi ecare expeditor la fi ecare consumator prin centrele intermediare.

Problema obinut de transport cu funcia-scop de a minimiza timpul maximal necesar de a transporta marfa se rezolv n felul urmtor [2]:

1. Determinm ( ) jijiji tt ;min11 = i notm prin 1 mulimea celulelor din tabel pentru care

11 jijitt > . Construim reeaua iniial cu vrfurile

121210 ,,,,,,,,, SBBBAAAS nm KK . Capacitatea arcului ( )iAS ,0 este miai ,1, = , iar a arcului ( )1, SB j respectiv njb j ,1, = . Capacitatea arcului ( )ji BA , ce nu aparine mulimii 1 este nemrginit;

2. Rezolvm problema determinrii fl uxului maximal n reeaua cu arce-le ce nu aparin mulimii 1 .

n cazul general, determinm mulimea celulelor 1, pentru care se inter-zice transportarea mrfi i i rezolvm problema determinrii fl uxului maxi-mal n reeaua cu arccele ce nu aparin mulimii 1 .

Este evident c dup un numr fi nit de iteraii, vom obine soluia optim a problemei de transport cu funcia-scop (timpul maxim) s fi e minimal.

Dac valoarea fl uxului maximal este egal cu oferta sumar, atunci am obinut soluia optim. n caz contrar, continum procesul de rezolvare.

253

Exemplul 2. S se rezolve problema de transport cu centre intermediare i funcia-scop (timpul maxim) s fi e minimal. Datele iniiale a problemei sunt date n tabelul 7.

Tabelul 7. Tabelul iniial al problemei de transport din exemplul 2

Centre intermediare

Expeditori ConsumatoriA1 A2 A3 B1 B2 B3 B4

I1I2

34

23

43

23

33

23

32

ai 65 160 95 bj 55 70 85 110

Determinm timpul necesar pentru a parcurge distana de la fi ecare ex-peditor la fi ecare consumator i ca rezultat obinem problema de transport cu funcia-scop (timpul maxim) s fi e minimal (tabelul 8).

Tabelul 8. Tabelul problemei de transport din exemplul 2 dup stabilirea

centrelor intermediare

BjAi

B1 B2 B3 B4 ai

A1 1I 5 1I 6 1I 5 2I 6 65

A2 1I 4 1I 5 1I 4 2I 5 160

A32I 6 2I 6 2I 6 2I 5 95

bj 55 70 85 110320

320

n aceast problem avem 4min),(11

== ijjiji tt i reeaua respectiv este:

254

95

A2 S1 S0

55

160

65

B4

B3

B1

B2

A3

A1

70

85

110

Deoarece valoarea fl uxului maximal n aceast reea nu este egal cu oferta sumar, rezult c procesul de rezolvare a problemei continu.

Pentru 522=jit avem reeaua respectiv:

S1 S0

55

95

160

65

B4

B3

B1

B2

A3

A2

A1

70

85

110

Deoarece valoarea fl uxului maximal n aceast reea este egal cu oferta sumar (cererea sumar), rezult c procesul de rezolvare a problemei s-a terminat.

Aadar, am obinut soluia optim a problemei, prezentat n tabelul 9.

Tabelul 9. Soluia optim a problemei de transport din exemplul 2

BjAi

B1 B2 B3 B4 ai

A155 5 6 10 5 6 65

A24 70 5 75 4 15 5 160

A3 6 6 6 95 5 95

bj 55 70 85 110320

320

255

Rspuns:

950001575700010055

*X , .5min =t

n cazul, cnd capacitatea centrelor intermediare este egal cu cantitile ce afl uiesc de la centrele de expediie i respectiv cu cantitile necesare consumatorilor, rezolvarea problemei se reduce la rezolvarea a dou probleme separate (o problem de la expeditor la centrele intermediare i o problem de la centrele intermediare la consumator).

Bibliografi e

Dumitru Pop. 1. Elemente de programare liniar cu aplicaii. Bucu-reti, 1972.. . , . . . -2. . , , 1967.