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:

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

Le quantità b_i 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, b_i>0 indicherebbe che, nel periodo di riferimento per il sistema (es., un 1 min), nel nodo i si rendono disponibili b_i Gb di pacchetti che devono essere trasferiti in modo tale da soddisfare la domanda nello stesso arco di tempo dei nodi j con b_j<0.
Poiché i contributi di flusso nella rete sono dati dai b_i 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)

Σ b_i=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

x_ij∈R ∀(i,j)∈E

dove δ⁺(i) è la stella uscente da i e δ^–(i) la stella entrante.
1) Σ x_ij – Σ x_ij = b_j ∀i∈V con (i,j) ∈ δ⁺(i) (i,j) ∈ δ^–(i)
2) 0 ≤ x_ij ≤ d_ij ∀(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 Σ w_ijx_ij
(i,j)∈E
x_ij ∈ℜ ∀(i,j)∈E

……..