Problemi di network flow

In generale le reti di flusso sono modelli utilizzati per prendere decisioni in vari contesti applicativi, es.:
– sistemi di telecomunicazioni;
– trasporti;
– sistemi idraulici e/o sistemi meccanici;
– sistemi economici;
È scontato dire che a noi interessa il primo esempio e che questi modelli vengono “rispolverati” soltanto in fase progettuale o in fase di debug, non bisogna dimenticare che dietro la formulazione dei modelli ci sono grandi studi e analisi.

Con i modelli di Network Flow (NF) si possono affrontare anche problemi in cui la decisione non consiste nel determinare un un vero e proprio flusso di dati in una rete ma consiste nel risolvere problematiche tipo:
– percorso minimo;
– assegnazione tickets;
– scheduling lavori;
– pianificazione contabili;
Per fare solo alcuni esempi, ma se ne potrebbero fare molti su altrettanti argomenti.

Per fare un esempio, definiamo un generico problema di flusso di dati in una rete G
• E’ dato un grafo G=(V, E) orientato
• Sui nodi ed archi (per archi si intendono le direttrici di unione dei nodi) di G sono definite le seguenti grandezze:

  • dij (i, j)∈E capacità dell’arco (i,j)
  • wij (i,j)∈E costo del flusso in (i,j);
  • bi i∈V flusso nel nodo i, dove:
    • bi >0 ⇒ nodo sorgente;
    • bi < 0 ⇒ nodo pozzo;
    • bi = 0 ⇒ nodo di transizione;

Le quantità bi rappresentano il contributo di flusso in ingresso o in uscita dalla rete, ad esempio, se la rete rappresentasse una rete per la distribuzione di contenuti audio/video, bi>0 indicherebbe che, nel periodo di riferimento per il sistema (es., un 1 min), nel nodo i si rendono disponibili bi Gb di pacchetti che devono essere trasferiti in modo tale da soddisfare la domanda nello stesso arco di tempo dei nodi j con bj<0.
Poiché i contributi di flusso nella rete sono dati dai bi non nulli, perché il flusso nella rete sia ammissibile deve essere verificata la seguente condizione:
(In pratica tutti i contributi di flusso da e verso l’esterno della rete devono compensarsi)

Σ bi=0
i∈V

Data una rete G(V, A) flusso ammissibile in G corrisponde ad un insieme di quantità associate agli archi di G tale che

xij∈R ∀(i,j)∈E

dove δ+(i) è la stella uscente da i e δ(i) la stella entrante.
1) Σ xij – Σ xij = bj ∀i∈V con (i,j) ∈ δ+(i) (i,j) ∈ δ(i)
2) 0 ≤ xij ≤ dij ∀(i,j)∈E

Detto questo il primo obbiettivo da raggiungere è capire come determinare il minor flusso dati:
Data la rete di flusso G e le quantità w, d e b prima definite si vuole determinare il flusso negli archi della rete in modo che il costo associato a tale flusso sia minimo
Matematicamente il problema del flusso a costo minimo (MCF) in una rete G(V, A) può essere formulato come problema di programmazione lineare (sempre grazie a Wikipedia) nel seguente modo:

min Σ wijxij
(i,j)∈E
xij ∈ℜ ∀(i,j)∈E

……..

Questa voce è stata pubblicata in informatica teorica. Contrassegna il permalink.
 

Lascia un commento

Il tuo indirizzo email non sarà pubblicato. I campi obbligatori sono contrassegnati *

verifica *