Problema del flusso di costo minimo

Da Wikipedia, l'enciclopedia libera.
Jump to navigation Jump to search

Il problema del flusso di costo minimo (minimum-cost flow problem, abbreviato MCFP) è un problema di decisione e ottimizzazione che consiste nel trovare il modo meno costoso possibile di far passare un certo ammontare di flusso tramite una rete di flusso.

Definizione[modifica | modifica wikitesto]

Una rete di flusso è un grafo orientato con un nodo sorgente e un pozzo , in cui ogni arco ha capacità , flusso e costo (gli algoritmi di MCF supportano archi di costo negativo). Il costo di spedire questo flusso tramite un arco è . Il problema fissa un certo ammontare di flusso che deve essere spedito dalla sorgente al pozzo.

Il problema richiede di minimizzare il costo totale del flusso passante per tutti gli archi.

con i seguenti vincoli:

Vincolo di capacità:
Emisimmetria:
Conservazione del flusso:
Flusso imposto:

Relazioni con altri problemi[modifica | modifica wikitesto]

Una variante del problema è quella di trovare la soluzione al problema del flusso massimo che abbia costo minimo. Può risultare utile per trovare l'accoppiamento massimo di costo minimo.

Un altro problema correlato è quello della circolazione di costo minimo, che può essere sfruttato per risolvere il MCFP.

Inoltre, i seguenti problemi possono essere considerati casi particolari:

Soluzioni[modifica | modifica wikitesto]

Il problema del flusso di costo minimo può essere risolto tramite programmazione lineare. Esistono, inoltre, molti algoritmi combinatoriali.[1] Alcuni di essi sono generalizzazioni degli algoritmi per il flusso massimo, altri utilizzano approcci completamente differenti.

Gli algoritmi più conosciuti:

Note[modifica | modifica wikitesto]

  1. ^ (EN) Ravindra K. Ahuja, Thomas L. Magnanti e James B. Orlin, Network Flows: Theory, Algorithms, and Applications, Prentice-Hall, Inc., 1993, ISBN 0-13-617549-X.
  2. ^ (EN) Morton Klein, A primal method for minimal cost flows with applications to the assignment and transportation problems, in Management Science, vol. 14, 1967, pp. 205–220, DOI:10.1287/mnsc.14.3.205.
  3. ^ (EN) Andrew V. Goldberg e Robert E. Tarjan, Finding minimum-cost circulations by canceling negative cycles, in Journal of the ACM, vol. 36, n. 4, 1989, pp. 873–886, DOI:10.1145/76359.76368.
  4. ^ (EN) Jack Edmonds e Richard M. Karp, Theoretical improvements in algorithmic efficiency for network flow problems, in Journal of the ACM, vol. 19, n. 2, 1972, pp. 248–264, DOI:10.1145/321694.321699.
  5. ^ (EN) Andrew V. Goldberg e Robert E. Tarjan, Finding minimum-cost circulations by successive approximation, in Math. Oper. Res., vol. 15, n. 3, 1990, pp. 430–466, DOI:10.1287/moor.15.3.430.
  6. ^ Alessandro Agnetis, Flusso a costo minimo e simplesso su reti (PDF), su dii.unisi.it, Università degli Studi di Siena, Dipartimento di Ingegneria dell'Informazione. URL consultato il 4 settembre 2016 (archiviato il 20 settembre 2010).
  7. ^ (EN) James B. Orlin, A polynomial time primal network simplex algorithm for minimum cost flows, in Mathematical Programming, vol. 78, 1997, pp. 109–129, DOI:10.1007/bf02614365.

Voci correlate[modifica | modifica wikitesto]

Collegamenti esterni[modifica | modifica wikitesto]

  Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica