Modele de rețea (cercetare operațională)

Modelele de rețea (în cercetarea operațională; engl. Network models) reprezintă o clasă de modele matematice care descriu o problemă sub forma unui graf (rețea), unde vârfurile (nodurile) desemnează obiecte sau stări, iar muchiile (arcele) — relații sau procese dintre acestea. În contextul optimizării, prin rețea se înțelege adesea un graf orientat, care în analiza operațională este denumit direct „rețea"; vârfurile unei astfel de rețele se numesc noduri, iar muchiile — arce.

Modelele de rețea reprezintă un instrument puternic pentru analiza și optimizarea sistemelor complexe din domenii precum logistica, telecomunicațiile, managementul proiectelor și finanțele. Forța lor constă într-un nivel ridicat de abstractizare: un nod poate reprezenta un oraș, un router de calculator sau o etapă a unui proiect, iar un arc — un drum, un canal de comunicație sau o operație tehnologică.

Definiție și terminologie

Baza modelelor de rețea o constituie teoria grafurilor. Conceptele cheie sunt:

• Rețea de fluxuri (engl. flow network): un graf orientat în care fiecare muchie are o capacitate (capacity) și un flux (flow). În graf sunt evidențiate două vârfuri speciale: sursa (source), din care pornește fluxul, și destinația (sink), în care acesta intră.
• Legea conservării fluxului: Pentru orice vârf care nu este sursă sau destinație, fluxul total de intrare trebuie să fie egal cu fluxul total de ieșire. Această condiție reprezintă un analog discret al legilor fizice de conservare.
• Planificarea rețelei: Un model care reprezintă un proiect ca un ansamblu de operații interdependente (arce) și evenimente (noduri). Astfel de rețele sunt grafuri orientate aciclice, ceea ce reflectă ordinea de execuție a lucrărilor.

Proprietăți și teoreme fundamentale

Modelele de rețea posedă o serie de proprietăți speciale care permit aplicarea unor algoritmi de înaltă eficiență pentru rezolvarea lor.

• Integralitatea soluțiilor: Multe probleme de optimizare a rețelelor (de exemplu, fluxul maxim sau drumul cel mai scurt) au proprietatea de unimodularitate totală a matricei de restricții. Datorită acestui fapt, dacă parametrii problemei (capacitățile, lungimile) sunt întregi, atunci soluția optimă găsită prin metode de programare liniară va fi de asemenea întreagă, fără a fi necesare restricții suplimentare.
• Teorema fluxului maxim și a tăieturii minime: Rezultat central al teoriei fluxurilor. Afirmă că valoarea maximă a fluxului de la sursă la destinație este egală cu capacitatea minimă dintre toate tăieturile care separă sursa de destinație. Această teoremă stabilește criteriul de optimalitate pentru flux și stă la baza multor algoritmi.
• Principiul optimalității pentru drumurile cele mai scurte: Dacă drumul de la punctul A la punctul C este cel mai scurt, atunci orice segment al acestuia (de exemplu, de la punctul intermediar B la C) este de asemenea drumul cel mai scurt între vârfurile respective. Această proprietate, care stă la baza programării dinamice, justifică corectitudinea unor algoritmi precum algoritmul lui Dijkstra.
• Proprietățile arborelui de acoperire minim (AAM):
• Proprietatea tăieturii: Pentru orice tăietură a grafului, muchia cu ponderea minimă care traversează tăietura aparține cel puțin unui AAM.
• Proprietatea ciclului: În orice ciclu al grafului, muchia cu ponderea maximă nu aparține niciunui AAM.

Pe aceste proprietăți se întemeiază corectitudinea algoritmilor „greedy" ale lui Prim și Kruskal.

Principalele probleme de optimizare a rețelelor

• Problema drumului cel mai scurt: Găsirea drumului de lungime (pondere) totală minimă între două noduri date. Se rezolvă prin algoritmul lui Dijkstra (pentru ponderi nenegative) sau algoritmul Bellman-Ford (pentru ponderi arbitrare).
• Problema fluxului maxim: Determinarea fluxului maxim posibil de la sursă la destinație cu capacitățile arcelor date. Metoda clasică de rezolvare este algoritmul Ford–Fulkerson.
• Problema arborelui de acoperire minim: Găsirea unui subgraf care conectează toate vârfurile rețelei și are costul total minim al muchiilor.
• Metoda drumului critic (CPM): În modelele de planificare a rețelelor, determinarea celei mai lungi secvențe de lucrări, care stabilește durata minimă posibilă de realizare a întregului proiect. Lucrările de pe acest drum au rezervă de timp nulă.

Exemple

• Drumul cel mai scurt: Găsirea traseului optim de către un sistem de navigație între două puncte pe harta unui oraș, unde orașele sunt noduri, iar drumurile sunt arce cu ponderi egale cu lungimea sau timpul de parcurs.
• Fluxul maxim: Determinarea capacității maxime a unei rețele de conducte, unde stațiile de pompare sunt noduri, iar conductele sunt arce cu capacitate limitată.
• Arborele de acoperire minim: Proiectarea unei rețele de comunicații (de exemplu, instalarea unui cablu de fibră optică) pentru conectarea mai multor orașe cu lungimea totală minimă a cablului.
• Drumul critic: Într-un proiect de construcție a unei case, unde lucrările (turnarea fundației, ridicarea pereților, montarea acoperișului) au durate stabilite și dependențe tehnologice, drumul critic determină termenul minim de finalizare a construcției. Orice întârziere a unei lucrări de pe acest drum va duce la întârzierea întregului proiect.

Vezi și

• Cercetarea operațională
• Teoria grafurilor
• Problema de transport
• Metoda drumului critic
• PERT