Algoritmo di rete simplex - Network simplex algorithm

In ottimizzazione matematica , la rete simplex algoritmo è un grafico teorica specializzazione del simplesso . L'algoritmo è solitamente formulato in termini di un problema di flusso a costo minimo . Il metodo simplex di rete funziona molto bene nella pratica, tipicamente da 200 a 300 volte più veloce del metodo simplex applicato a programmi lineari generali delle stesse dimensioni.

Storia

Per molto tempo, l'esistenza di un algoritmo simplex di rete dimostrabile efficiente è stato uno dei principali problemi aperti nella teoria della complessità, anche se erano disponibili versioni efficienti nella pratica. Nel 1995 Orlin ha fornito il primo algoritmo polinomiale con runtime di dove è il costo massimo di qualsiasi bordo. Successivamente Tarjan lo ha migliorato per utilizzare alberi dinamici nel 1997. Gli algoritmi simplex a doppia rete fortemente polinomiale per lo stesso problema, ma con una maggiore dipendenza dal numero di archi e vertici nel grafo, sono noti da più tempo.

Panoramica

Il metodo del simplex di rete è un adattamento dell'algoritmo del simplex primale della variabile limitata. La base è rappresentata come uno spanning tree radicato della rete sottostante, in cui le variabili sono rappresentate da archi e i moltiplicatori simplex dai potenziali dei nodi. Ad ogni iterazione, una variabile in entrata viene selezionata da una strategia di prezzo, basata sui doppi moltiplicatori (potenziali del nodo), e forma un ciclo con gli archi dell'albero. La variabile uscente è l'arco del ciclo con il minor flusso in aumento. La sostituzione dell'arco di entrata con quella di uscita e la ricostruzione dell'albero è chiamata perno. Quando nessun arco non di base rimane idoneo per entrare, la soluzione ottimale è stata raggiunta.

Applicazioni

L'algoritmo di rete simplex può essere utilizzato per risolvere molti problemi pratici tra cui,

Riferimenti

link esterno