1

Cursul 6

Probleme de transport

Obiective: Acest capitol urmrete familiarizarea studenilor cu problemele de transport,

probleme ce prezint o importana deosebit n optimizarea numeroaselor procese economice. O

problem de transport poate consta n crearea unui plan de transport pentru unul sau mai multe

produse de la unul sau mai multe centre furnizoare(productoare, de depozitare), n scopul

satisfacerii cerinelor unor consumatori si cel al minimizrii cheltuielilor de transport.

Problemele de tip transport se ntlnesc n multe procese economice, ca de exemplu:

transporturi de bunuri; proiectarea de canale de energie sau informaii sau de ce nu de canale de

irigaii n agricultur; proiectarea de depozite n acelai spaiu productiv; repartiia optim a

sarcinilor de producie pe maini, secii, ntreprinderi, optimizarea unor probleme de producie i

stocaj etc.

Rezumat: Modelul matematic al problemelor de transport se ncadreaz n modelul

problemelor de programare liniar. Avnd n vedere numrul mare de variabile, rezolvarea unei

probleme de transport prin algoritmul simplex este n general puin eficient. De aceea, pentru

rezolvarea problemelor de tip transport se folosesc tehnici speciale. Acest capitol este dedicat

prezentrii acestor tehnici sub o form mai simpl.

6.1 Modelul matematic pentru o problem de transport

O problem de transport a fost formulat la Capitolul 1, problem pe care dorim n cele

ce urmeaz s o reformulm. Un produs (tip de marf) se afl n depozitele(magaziile) 1, 2,

..., n cantitile 1, 2, ..., i trebuie transportat() n porturile 1, 2, ..., n

cantitatile 1, 2, ..., . Cunoscnd costul transportului pe unitate de produs de la depozitul

(magazia) , = 1, la portul , j=1, , notat cu , se cere s se ntocmeasc un astfel de

plan de repartiie a produsului nct costul total al transportului s fie minim.

Dac notm cu cantitatea de produs ce se va transporta de la depozitul(magazia)

, = 1, , n portul , = 1, , atunci modelul matematic pentru problema de transport se

scrie astfel:

2

6.1

{

= , = 1,

=1

= ,

=1

= 1,

0, = 1, , = 1,

() =

=1

=1

.

Intuitiv, modelul matematic (6.1) al problemei de transport se poate reprezenta prin

Tabelul 6.1.

\ 1 2 ... Disponibil

1 11 12 ... 1 1 11 12 1

2 21 22 ... 2 2 21 22 2

...

1 2 ... 1 2

Necesar 1 2 ... T

Cuplul poart numele de csu.

Algoritmul de rezolvare a unui model de transport cere ca acest model s fie echilibrat, adic s

fie indeplinit condiia de echilibru

= ,

=1

=1

ceea ce inseamn c totalul disponibilului s fie egal cu totalul necesarului.Valoarea comun T a

acestui total se trece n csua (m+1, + 1).

n caz contrar, modelul se echilibreaz prin considerarea, fie a unei magazii fictive +1,

fie a unui port fictiv +1, care ofer sau cere, diferena dintre cele dou sume. Deoarece

3

cantitile transportate de la un depozit(magazie) arbitrar, respectiv la acest port fictiv, nu exista

n realitate, costurile de transport corespunztoare le considerm nule.

Se observ c ntr-o problem de transport cu m depozite(magazii) si n porturi modelul

matematic conine mn variabile necunoscute i cel mult m+n1 restricii independente(nu s-au

inclus condiiile de nenegativitate). Numrul variabilelor necunoscute fiind evident mai mare ca

cel al restruciilor, rezult c valorile variabilelor ce verific sistemul de restricii nu sunt unic

determinate.

O soluie posibil(realizabil) a problemei, care conine cel mult (m+n1) componente

strict pozitive, se numete soluie de baz. Soluia de baz cu exact (m+n1) componente

pozitive se numete soluie de baz nedegenerat, iar n caz contrar, degenerat.

Se constat c modelul matematic reprezint o problem de programare liniar de o form

special. Cu toate c n restricii coeficienii necunoscutelor sunt 0 sau 1, rezolvarea prin metoda

simplex cere un volum de calcule foarte mare. De aceea, se prefer pentru rezolvarea unei

probleme de transport o cale cu tehnic specific.

n general, pentru rezolvarea unei probleme de treansport se parcurg etapele:

a) Determinarea (aflarea) unei soluii iniiale (de baz, nedegenerat);

b) Ameliorarea (mbuntirea) unei soluii;

c) Aflarea (determinarea) soluiei optime.

6.2 Determinarea unei soluii iniiale

Pentru aflarea unei soluii iniiale intr-o problem de transport se cunosc mai multe metode. n cele ce urmeaz vom prezenta trei metode.

6.2.1 Metoda colului Nord-Vest

Aceast metod const n a atribui, pe rnd , valori variabilelor necunoscute ncepnd cu

cea din colul Nord-Vest al tabelului. Astfel, mai nti lum 11 = min (1, 1). Dac

min (1, 1)=1, atunci 12 = = 1 = 0, iar dac min (1, 1)=1, atunci 21 = 31 = =

1 = 0. Metoda continu apoi cu 21 = min (2, 1 1) n prima situaie, respectiv cu

12 = min (1 1, 2) n cealalt situaie. Procesul se repet pn cnd este repartizat i

ultima cantitate disponibil.

Exemplul 6.2.1. Se consider trei furnizori 1, 2 3 care au disponibile corespunztor

cantitile de un anumit produs 1 = 50, 2 = 30 3 = 40. Acestea sunt solicitate de patru

porturi 1, 2 , 3 4 n cantitile 1 = 45, 2 = 15, 3 = 25 4 = 35. Cunoscnd costurile

unitare de transport 3,2,1,1;2,3,2,1 i 4,2,3,2 uniti monetare de la 1, 2 3, s se scrie

modelul matematic al problemei de transport, cnd se urmrete minimizarea costului total.

4

Utiliznd metoda colului Nord-Vest s se gseasc o soluie iniial.

Dac notm cu cantitatea de produs ce se va transporta de la furnizorul , = 1,2,3 la

portul , = 1,2,3,4, atunci obinem urmtorul model matematic :

11 +12 +13 +14 = 5021 +22 +23 +24 = 3031 +32 +33 +34 = 4011 +21 +31 = 45 12 +22 +32 = 15 13 +23 +33 = 25 14 +24 +34 = 35

0, = 1,2,3, = 1,2,3,4.

() = 311 + 212 + 13 + 14 + 221 + 322 +

+223 + 24 + 431 + 232 + 333 + 234

Sub form tabelar modelul matematic este:

\ 1 2 3 4 Disponibil

1 3 2 1 1 50 11 12 13 14

2 2 3 2 1 30 21 22 23 24

3 4 2 3 2 40 31 33 33 34

Necesar 45 15 25 35 120 Pentru aflarea soluiei iniiale cu metoda colului Nord-Vest procedm astfel: alegem

11 = min(45,50) = 45; atunci 21 = 31 = 0; apoi 12 =min(15,5)=5 i 13 = 14 = 0; n continuare 22 = min(10,30) = 10 i 32 = 0 i n final 33 = 5 i 34 = 35.

De obicei, se determin soluia iniial n tabel, micorndu-se de fiecare dat disponibilul i necesarul respectiv i scriind alturat cel rmas. Astfel avem

\ 1 2 3 4 Disponibil

1 3 2 1 1 50;5;0 45 5 0 0

2 2 3 2 1 30;20;0 0 10 20 0

3 4 2 3 2 40;35;0 0 0 5 35

Necesar 45 0

15 10 0

25 5 0

35 0

120

Tabelul 6.2.1

5

Valoarea funciei cost total pentru soluia iniial gsit este

= 3 45 + 2 5 + 3 10 + 2 20 + 3 5 + 2 35 = 300

Aceast metod este foarte simpl dar puin eficient deoarece nu ine cont de valorile

costurilor ci doar de cantitile disponibile si de cele necesare.

6.2.2 Metoda elementului minim

Metoda const n a atribui, pe rnd, valori variabilelor necunoscute, ncepnd cu aceea la

care costul unitar este minim.

Apoi din cele rmase se lucreaz tot cu aceea care corespunde costului minim. Dac sunt

mai multe costuri minime egale, atunci se va considera mai nti acea variabil care poate lua

valoarea mai mare. Valoarea variabilei se va afla ca i la metoda colului de Nord-Vest,

considernd minimul dintre disponibil si necesar.

Exemplul 6.2.2. Utiliznd metoda elementului minim s aflm o soluie iniial pentru problema

de transport de la Exemplul 6.2.1.

Deoarece 13 = 14 = 24 = 1 este costul minim, mai nti vom determina valoarea

variabilei 14 ntruct vom obine valoarea maxim (13 = 25; 14 = 35; 24 = 30). Aadar,

lum 14 = 35, ceea ce implic 24 = 0, 34 = 0. Apoi alegem 13 = 15 deoarece 13 = 1 este

costul minim din cele rmase. Avem 11 = 12 = 0. Considend costurile egale cu 2 alegem

21 = 30 i 22 = 23 = 0. Acum luam 32 = 15, 33 = 10 31 = 15.

Ilustrarea intuitiv prin tabel este dat n Tabelul 6.2.2.

Valoarea lui pentru aceast solutie este

= 1 15 + 1 35 + 2 30 + 4 15 + 2 15 + 3 10 =

= 50 + 60 + 60 + 60 = 230.

\ 1 2 3 4 Disponibil

1 3 2 1 1 50; 15; 0 0 0 15 35

2 2 3 2 1 30; 0

30 0 0 0 3 4 2 3 2 40; 25;15

15 15 10 0 Necesar 45

15 0

15 0

25 10 0

35 0

120

Tabelul 6.2.2.

6

6.2.3 Metoda diferenelor mixte

Valorile variabilelor se atribuie ca i n cazul metodelor precedente, dar ordinea de

atribuire se face dup o alt regul. Pentru stabilirea ordinii de urmat se calculeaz, pentru

fiecare linie, respectiv pentru fiecare coloan, diferena dintre cele mai mici dou

elemente(costuri). Apoi pe linia sau coloana cu diferena maxim se determin variabilele din

csu cu cost minim. Apoi procedeul se repet. La diferene maxime egale se consider mai

nti costul minim.

La lucrul cu tabelul diferenele pe linii se trec n dreapta tabelului, iar cele pe coloane

dedesubtul tabelului.

Exemplul 6.2.3. S se afle o soluie iniial cu metoda diferenelor maxime pentru problema de

transport din Exemplul 6.2.1.

Calculm diferenele pe linii i coloane. Avem urmtorul tabel cu diferene

calculate astfel: 2-1=1 pentru linia nti, 2-1=1 pe linia a doua, 3-2=1 pentru linia a treia, 3-2=1

pentru coloana nti, 3-2=1 pentru coloana a doua, 2-1=1 pentru coloana a treia i 2-1=1 pentru

coloana a patra.

Se observ c avem toate diferenele egale cu 1. Alegem 14 = 35 deoarece d cea mai

mare repartizare pentru preurile minime. Atunci 24 = 34 = 0.

Recalculm diferenele pe liniile i coloanele rmase, obtinem tabelul

3 2 1 1

2 3 2 1

4 2 3 1

1 1 1

3 2 1 1 1

2 3 2 1 1

4 2 3 2 1

1 1 1 1

7

Toate diferenele sunt egale. innd seama de costul minim alegem 13 = 15 i 11 =

12 = 0.

Pentru liniile i coloanele necompletate recalculm diferenele i obinem tabelul

2 3 2 1

4 2 3 1

2 1 1

Diferena maxim este 2 i corespunde coloanei nti. Alegem 21 = 30 i 22 = 23 = 0.

Acum, pe linia a treia lum 31 = 15, 32 = 15 i 33 = 10. Sub form de tabel calculele arat

astfel:

\ 1 2 3 4 Disponibil

1 3 2 1 1 50; 15; 0 0 0 15 35

2 2 3 2 1 30; 0

30 0 0 0 3 4 2 3 2 40; 25; 15

15 15 10 0 Necesar 45

15 0

15 0

25 10 0

35 0

120

Valoarea lui pentru aceast soluie iniial este

= 1 15 + 1 35 + 2 30 + 4 15 + 2 15 + 3 10 = 230

Se observ c s-a obinut aceeai soluie iniial ca i cea obinut utiliznd metoda

elementului minim.

Observaia 6.2.1 Toate cele trei soluii iniiale gsite pentru problema de transport din Exemplul

6.2.1 sunt soluii de baz nedegenerate, avnd 4+3-1=6 componente pozitive.

Bibliografia aferent cursului: Probleme de transport

[0] Acu, A.M., Acu D., Acu M., Dicu P., Matematici aplicate n economie Note de curs pentru

nvmntul la distan,

http://depmath.ulbsibiu.ro/chair/acu_mugur/manexe/MatematiciAplicateInEconomiePentruIDD.

pdf

[1] Acu, A.M., Acu D., Acu M., Dicu P., Matematici aplicate n economie - Volumul I,

Editura ULB, Sibiu, 2001.