scritto da | on | Nessun commento

Il metodo del simplesso è una procedura algebrica utilizzata per la risoluzione di problemi di programmazione lineare, é stato il primo algoritmo pratico per la risoluzione di problemi di PL ed é tuttora il più usato e uno dei più efficienti in pratica. Il Metodo del Simplesso si applica a problemi di Programmazione Lineare “in forma standard”,ovvero a problemi che presentano una particolare struttura adatta ad essere sfruttata da un punto di vista algoritmico. Il metodo del simplesso si basa su un processo iterativo di calcolo del valore della funzione obiettivo nei vertici della soluzione ammissibile, fino a quando si trova il valore ottimale (o si verifica che tale valore non esiste). E importante notare come esso non prende in considerazione tutte le soluzioni ammissibili di base, che, anche se in numero finito, possono essere numerose, ma si limita a considerarne alcune e si arresta quando trova quella ottimale. Quando il valore ottimale esiste ed è finito, il procedimento consiste nello spostarsi ripetutamente da un vertice all’altro adiacente al primo, in modo da ottenere un valore di Z (funzione obiettivo) maggiore di quello ottenuto in un precedente vertice. La ricerca termina non appena si trova che in nessun vertice adiacente la funzione obiettivo assume un valore maggiore: in questo caso si è raggiunta la soluzione ottimale. La soluzione così trovata è ottimale per le proprietà dell’insieme delle soluzioni ammissibili e per la linearità della funzione obiettivo. In genere questo tipo di procedimento consente di determinare il valore ottimale della funzione obiettivo in un numero limitato di passi, in quanto il vertice successivo è sempre scelto in modo che accresca il valore della funzione obiettivo: così facendo è impossibile ritornare su un vertice già esaminato. Tanto più che, tra tutti i vertici, si determina sempre quello che incrementa maggiormente la funzione obiettivo. Il problema è dunque quello di tradurre un procedimento prettamente geometrico in un procedimento analitico. L’implementazione informatica dell’algoritmo passa attraverso la sua risoluzione in forma matriciale, è possibile reperire in rete diverse librerie alcune delle quali opensource che implementano l’algoritmo come http://www.gnu.org/software/glpk/, www.coin-or.org, http://sourceforge.net/projects/lpsolve/.

Lascia un Commento

News