Probleme de optim in retele de transport si distributie

Probleme de optim in retele de transport si distributie

Probleme extremale in teoria grafurilor:

Intr-o mare varietate de contexte practice apare urmatoarea situatie. O cantitate Q dintr-un anumit produs (materie prima, produs finit, informatii, etc) se afla disponibila intr-un numar de locuri - numite surse - si este solicitata pentru consum sau prelucrare in aceeasi cantitate in alte locuri numite destinatii. Unitatile indivizibile ale cantitatii Q se vor numi unitati de flux. intre surse si destinatii exista legaturi, unele directe, altele indirecte, prin intermediul unor puncte intermediare sau de tranzit. Aceste legaturi se numesc rute; unele pot fi parcurse in ambele sensuri altele numai intr-un anumit sens, specificat.

Este clar ca ansamblul surselor, destinatiilor si localitatilor intermediare precum si al rutelor ce unesc aceste localitati poate fi vizualizat intr-un graf (partial) orientat.

Pentru cercetarea operationala aceasta situatie va prezenta interes, in sensul producerii unor probleme de optimizare numai daca:

a) Orice sursa are posibilitatea de a aproviziona mai multe destinatii si orice destinatie se poate aproviziona de la mai multe surse;

b) Pe fiecare ruta este indicat un cost al deplasarii unei unitati de flux, de la o extremitate la cealalta. Acest cost poate depinde de sensul deplasarii in cazul in care ruta poate fi parcursa in ambele sensuri;

c) Pe fiecare ruta sunt precizate o limita inferioara si o alta superioara in ceea ce priveste volumul unitatilor de flux deplasate pe ruta respectiva. Aceste limite se numesc capacitati (inferioara si superioara). Nu este exclusa posibilitatea ca aceste limitari sa depinda de sensul deplasarii. In cele ce urmeaza vom avea in vedere in exclusivitate cazul in care capacitatile inferioare sunt egale cu zero, cele superioare fiind exprimate prin valori pozitive (posibil infinite).

In timp ce conditia a) va fi presupusa permanent, conditiile b) si c) pot avea loc separat sau impreuna. Astfel apar urmatoarele probleme de optimizare:

1) in prezenta conditiei b) si absenta conditiei c) - acesta insemnand ca pe o ruta se poate transporta orice volum de unitati de flux - se pune problema satisfacerii cerintelor in punctele de destinatie la un cost total de transport minim. Daca nu exista alte rute in afara celor care leaga direct sursele de destinatie si acestea sunt orientate in sensul sursa → destinatie (figura 1.1a)) obtinem problema clasica de transport.

Cazul mai general, in care exista si puncte de tranzit si rute care pot fi parcurse oricum este cunoscut sub numele de problema transferului (figura 1.1b)).

2) In situatia particulara in care exista o unica sursa, o unica destinatie si o singura unitate de flux se obtine problema drumului de cost minim.

3) In prezenta conditiei c) si absenta conditiei b) ne putem intreba daca limitarile impuse unitatilor de flux transportate pe diferite rute permit sau nu satisfacerea integrala a cerintelor in punctele de destinatie. Pentru a raspunde la intrebare vom determina volumul maxim Q_max de unitati de flux ce pot fi transferate de la surse la destinatii. Daca Q_max = Q toate cererile vor fi acoperite; daca Q_max < Q satisfacerea tuturor cerintelor nu va putea fi realizata fara cresterea capacitatilor anumitor rute. Problema descrisa mai sus se numeste problema fluxului maxim.

4) In prezenta ambelor conditii b) si c) se pune problema satisfacerii cererilor in punctele de destinatie la un cost total de transport minim. Ca mai sus vom determina mai intai volumul maxim Q_max de unitati de flux ce pot fi transportate de la surse la destinatii de-a lungul rutelor capacitate si apoi modul in care trebuie organizat transportul cantitatii Q_max astfel incat costul total al transportului sa fie minim. Aceasta este problema fluxului de cost minim. Daca Q_max - Q toate cererile vor fi acoperite (la costul cel mai mic); in caz contrar apare o alta chestiune interesanta: aceea a identificarii rutelor a caror capacitati urmeaza a fi marite in vederea satisfacerii cererilor restante astfel incat cheltuielile suplimentare de transport sa fie cat mai mici.

5) Exista numeroase situatii practice in care este necesar sa stim in cat timp se poate face transportul unitatilor de flux de la surse la destinatii si daca exista posibilitatea satisfacerii cererilor in timpul cel mai scurt cunoscand fireste "vitezele' de deplasare pe diferite rute. Alteori suntem interesati de a cunoaste volumul maxim de unitati de flux transferabile de la surse la destinatii intr-un interval de timp dat. Studiul acestor chestiuni impune utilizarea unui concept adecvat, acela de flux dinamic.

6) Toate problemele descrise au un evident caracter dinamic: un produs este deplasat intre niste "puncte' de-a lungul unor rute care unesc aceste puncte. Un mare numar de probleme de optimizare in grafuri, unele din ele neimplicand in mod necesar "deplasari in spatiu sau timp', sunt reductibile la una sau la alta dintre problemele de mai sus; de exemplu problemele de cuplaj maxim, problemele de afectare sau cele de ordonantare.

7) "Asemanatoare' problemei drumului de cost minim intre doua puncte dar cu mult mai grea este problema comis voiajorului: un numar de localitati (obiective turistice) trebuie vizitate, fiecare o singura data, intr-o anumita ordine astfel incat la revenirea la punctul de plecare, costul deplasarii sa fie minim.

8) Foarte importanta este si problema determinarii unei retele de comunicatii care sa conecteze un numar de "puncte' (localitati, locuinte, etc) astfel incat costul total (sau lungimea totala) a liniilor de legatura sa fie cat mai mic. Datorita proprietatilor speciale ale unei asemenea retele, problema descrisa este cunoscuta sub numele de problema arborelui de cost minim.

Exemplele prezentate nu epuizeaza nici pe departe portofoliul extrem de bogat si variat al problemelor de optimizare in grafuri. Ele sunt importante atat prin numeroasele aplicatii practice cat si pentru faptul ca studiul lor permite abordarea cu succes si a altor probleme.