AlgoritmoDelSimplesso

L'algoritmo del simplesso è un metodo ampiamente utilizzato per risolvere problemi di programmazione lineare. È un algoritmo iterativo che si basa su un processo di miglioramento graduale per trovare la soluzione ottimale di un problema di programmazione lineare.
Di seguito sono riportati i passaggi principali dell'algoritmo del simplesso:
Inizializzazione: L'algoritmo parte da una soluzione di base ammissibile, che è una soluzione iniziale che soddisfa i vincoli del problema di programmazione lineare. Se non viene fornita una soluzione di base ammissibile, l'algoritmo genera una soluzione di base iniziale.
Test di ottimalità: Viene eseguito un test per determinare se la soluzione corrente è ottimale. Questo viene fatto verificando se tutti i coefficienti delle variabili decisionali nella funzione obiettivo sono non negativi o se esiste una direzione di miglioramento.
Selezione della variabile di entrata: Se la soluzione corrente non è ottimale, viene selezionata una variabile di entrata per entrare nella base. La variabile di entrata è scelta in base a regole che cercano di migliorare la soluzione.
Selezione della variabile di uscita: Dopo aver selezionato la variabile di entrata, viene scelta una variabile di uscita da rimuovere dalla base. Questa scelta viene fatta considerando i vincoli del problema di programmazione lineare e cercando di migliorare la soluzione.
Aggiornamento della soluzione: Una volta selezionate la variabile di entrata e la variabile di uscita, la soluzione di base viene aggiornata in modo da migliorare il valore della funzione obiettivo. Questo viene fatto mediante calcoli che coinvolgono le matrici dei coefficienti del problema di programmazione lineare.
Ritorno al passo 2: Dopo l'aggiornamento della soluzione, l'algoritmo ritorna al passo 2 per verificare se la soluzione corrente è ottimale. Se non lo è, i passaggi 3-6 vengono ripetuti fino a quando non viene trovata una soluzione ottimale.
L'algoritmo del simplesso continua a iterare tra i passaggi 2-6 finché non si raggiunge una soluzione ottimale o si rileva che il problema di programmazione lineare è non limitato o non ha soluzione.
L'algoritmo del simplesso è stato sviluppato da George Dantzig negli anni '40 ed è tutt'ora uno dei metodi più utilizzati per la risoluzione di problemi di programmazione lineare grazie alla sua efficacia e robustezza.