CAPITOLUL 1
TEORIA GRAFURILOR.
OPTIMIZARI IN RETELE DE TRANSPORT SI DISTRIBUTIE
1.1. Modelarea problemelor de transport si distributie
Intr-o mare varietate de contexte se pune problema deplasarii unei cantitati Q ce poate fi materie,
energie, informatie, etc. din unele locuri numite surse in alte locuri numite destinatii, aceasta deplasare
realizandu-se pe anumite rute de legatura. Unitatile indivizibile ale cantitatii Q care se deplaseaza de-a lungul
rutelor se vor numi unitati de flux.
O clasificare a problemelor de transport si distributie
Pentru Cercetarea Operationala, problema enuntata va prezenta interes numai daca respecta
urmatoarele ipoteze:
a) cel putin o sursa poate aproviziona mai multe destinatii si cel putin o destinatie poate primi unitati
de flux de la mai multe surse.
Rutele de legatura pot avea si alte puncte comune in afara surselor si destinatiilor, numite puncte
intermediare sau de tranzit. Nu sunt excluse legaturile directe intre surse sau intre destinatii. In principiu,
orice ruta poate fi parcursa in ambele sensuri, dar pot exista si rute cu sens unic.
Ansamblul surselor, destinatiilor, al punctelor intermediare si al rutelor de legatura se va numi retea
de transport; el se identifica cu un graf neorientat sau partial orientat ca in figura 1.1.
b) Unele rute de legatura pot avea limitari superioare si / sau inferioare pentru volumul unitatilor de
flux ce se deplaseaza intr-un sens sau altul. Aceste limitari poarta numele de capacitati (inferioare, respectiv
superioare). In continuare, vom avea in vedere numai cazul in care toate capacitatile inferioare sunt egale cu
zero, capacitatile superioare fiind exprimate prin numere pozitive.
c) Exista un cost al deplasarii unei unitati de flux de la un punct al retelei la altul,cost care poate fi
exprimat in bani, timp sau distanta. Sunt situatii in care acest cost poate semnifica profitul obtinut de pe
urma deplasarii. Pe aceeasi ruta, costurile si capacitatile pot fi diferite in functie de sensul de parcurgere al
rutei.
Ipoteza a) va fi intotdeauna presupusa in timp ce ipotezele b) si c) pot fiinta separat sau simultan.
1) In prezenta ipotezei c) si absenta conditiei b) se pune problema deplasarii cantitatii de flux Q de la
surse la destinatii la un cost total minim. Daca sursele sunt in legatura directa cu destinatiile obtinem
problema clasica de transport, care va face obiectul Capitolului 4 al cursului. Cazul general, in care exisa si
puncte intermediare, este cunoscut sub numele de problema transferului si el nu face obiectul cursului de
fata. In cazul particular al unei singure surse s, al unei singure destinatii t si a unei singure unitati de flux se
Figura 1.1.
b)
3
100
300 1
2
5
4
400 200
100
300
50
: sursa (furnizor)
: destinatie (consumator)
a)
F1
F2
C1
120
C2
C3 230
c11
c12
c13
c21
c22
c23
CURSUL 1
Capitolul 1 Teoria grafurilor. Optimizari in retele de transport si distributie
2
obtine problema drumului de cost minim de la s la t, problema de care ne vom ocupa in sectiunea 1.4 a
acestui capitol.
2) In prezenta ipotezei b) si absenta ipotezei c) se pune problema daca reteaua, ale carei rute sunt
capacitate, este capabila sa permita acoperirea integrala a cererilor in punctele de destinatie. Pentru
aceasta, se va rezolva problema determinarii volumului maxim Q* de unitati de flux ce pot fi deplasate de la
surse la destinatii. Daca Q* < Q vor exista destinatii a caror cerere este acoperita doar in parte si atunci se
ridica problema maririi capacitatii de transfer a retelei. Am descris succint problema fluxului maxim,
problema ce va fi abordata in cadrul cursului de Cercetari Operationale din anul 2.
3) In prezenta simultana a ipotezelor b) si c) se pune problema satisfacerii cererilor in punctele de
destinatie la un cost de transport minim. Ca si in cazul precedent vom avea in vedere o problema modificata:
vom determina mai intai cantitatea maxima de flux ce poate fi deplasata de la surse la destinatii si apoi modul
de organizare al deplasarii astfel incat costul operatiei sa fie minim. Aceasta este problema fluxului (maxim)
de cost minim, problema abordata, de asemenea, in cadrul cursului de Cercetari Operationale din anul 2.
In sectiunile urmatoare vom trata doua probleme de optimizare in retele de transport: problema
determinarii unui arbore maximali (de acoperire) de valoare (cost) minim si problema drumului de cost
minim de la s la t .
1.2 Concepte utilizate in teoria grafurilor
In sectiunea 1.1 am vizualizat elementele unei retele de transport printr-un desen compus din puncte
si arce care unesc unele din aceste puncte (vezi figura 1.1). Un asemenea desen constituie forma uzuala de
prezentare a unui concept deosebit de important, atat in sine cat si pentru studiul unei impresionante varietati
de probleme din cele mai diverse domenii, domeniul economic fiind prioritar.
Am socotit deci necesar sa includem aici cateva elemente privitoare la conceptul de graf, caci despre
el este vorba. Aceste elemente vor fi foarte utile pentru intelegerea consideratiilor teoretice dezvoltate in
legatura cu rezolvarea problemei de transport si de asemenea constituie cadrul natural de abordare si a
celorlalte probleme amintite in clasificarea data in sectiunea precedenta.
Un graf este un cuplu G = (V, E) format dintr-o multime nevida V, ale carei elemente se numesc
varfuri sau noduri si o multime E de elemente, zise muchii, cu proprietatea ca fiecarei muchii e I E ii sunt
asociate doua noduri x, y I V, nu neaparat distincte, numite extremitatile muchiei e. Un subgraf al grafului
G = (V, E) este un graf G' = (V', E') in care V' I V, E' I E si orice muchie eI E' are aceleasi extremitati
atat in G' cat si in G.
Dupa cum se vede, definitia generala nu exclude existenta muchiilor cu o singura extremitate (aceste
muchii se numesc bucle), nici existenta mai multor muchii cu aceleasi extremitati (figura 1.2.a)
a) b)
Figura 1.2.
Graful G se va numi simplu daca nu are bucle si oricare doua noduri sunt extremitati pentru cel mult o
muchie. Vom spune ca G este finit daca varfurile si muchiile sale sunt in numar finit.
In continuare, vom avea in vedere in exclusivitate grafuri finite si simple asa cum este cel reprezentat
grafic in figura 1.2.b).
Pentru a descărca acest document,
trebuie să te autentifici in contul tău.
