Articoli Taggati ‘algoritmo simplesso’

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/.

scritto da | on , | Nessun commento

Si definiscono come problemi di programmazione lineare tutti quei problemi di ottimizzazione in cui la funzione obiettivo è lineare ed i vincoli sono tutti espressi da disequazioni lineari, ovvero è quella classe di problemi che sono definiti con funzioni polinomiali di primo grado di cui bisogna ricercare il minimo od il massimo tenendo conto dei vincoli imposti. Per la risoluzione di tale classe di problemi è stato elaborato l’algoritmo del simplesso che permette di trovare la miglior soluzione ammissibile, qualora questa esista, che risolve il problema studiato. Diversi problemi che si presentano nella gestione logistica possono essere ricondotti alla classe di problemi di programmazione lineare come ad esempio come il bilanciamento dei depositi, l’ottimizzazione dell’assortimento, la gestione dei trasporti, lo scheduling della produzione ed altri. L’algoritmo del simplesso viene implementato all’interno del Risolutore di Excel, mentre esistono diverse librerie nei vari linguaggi di programmazione che consentono l’utilizzo dell’algoritmo nella risoluzione dei problemi di ottimizzazione.

ALLEGATI

ProgrammazioneLineare
Titolo: ProgrammazioneLineare (0 click)
Etichetta:
Filename: programmazionelineare.pdf
Dimensione: 740 kB

News