Reti di flusso

Con il termine rete indichiamo un grafo $G=(N,A)$, di solito diretto, ai cui archi siano associati dei pesi.

• Gli archi sono i canali di comunicazione fra i nodi e possono essere rappresentati sia da grandezze discrete (ad esempio il numero di aerei) che continue (ad esempio un fluido);
• I nodi sono i punti di ingresso ed uscita della rete.

Nodi

Ad ogni nodo $i$ della rete è associato uno sbilanciamento $b_i$ che può essere:

• Positivo, quindi il nodo è un punto di uscita dalla rete e viene detto pozzo;
• Negativo, quindi il nodo è un punto di ingresso nella rete e viene detto sorgente;
• Nullo, il nodo è solamente un nodo di trasferimento.

Archi

Ogni arco $(i,j)$ della rete è caratterizzato da 3 parametri:

• Un costo $c_{ij}$ che indica il costo necessario per far attraversare il canale da un'unità;
• Una capacità inferiore $l_{ij}$, che è la quantità minima di bene che deve passare dall'arco;
• Una capacità superiore $u_{ij}$ che è la quantità massima di bene che può passare dall'arco.

Soluzione

Una soluzione di un problema di flusso è un assegnamento di valori reali agli archi di una certa rete $G=(N,A)$.

La soluzione viene indicata mediante un array $x$ i cui elementi $x_{ij}$ corrispondono ai singoli archi $(i,j)$.

Infine, il costo di un flusso è la sommatoria dei costi complessivi di tutta la rete:

$$ \sum_{(i,j)\in A} c_{ij}x_{ij} $$