Metodo del simplesso

Enciclopedia della Scienza e della Tecnica (2008)

metodo del simplesso

Angelo Guerraggio

Uno dei metodi usati nella programmazione lineare per passare, con un numero finito di passi di calcolo numerico, da una soluzione ammissibile a una ottimale. Consideriamo un problema di programmazione lineare in cui si tratti di trovare il massimo o il minimo di una funzione lineare in una data regione ammissibile, quando le variabili decisionali (raccolte nel vettore x) sono soggette alle condizioni di non negatività sulle loro componenti e a m vincoli, anch’essi lineari, scritti nella forma matriciale compatta Ax=b. Supponiamo dunque che la matrice A sia di tipo (m,n) con mn e abbia rango uguale a m. Si chiama soluzione di base ogni vettore x che soddisfi i vincoli Ax=b e abbia solo m componenti non nulle (tante quanto sono i vincoli). Il teorema di base della programmazione lineare afferma che, se esiste una soluzione ottimale nella regione ammissibile, esiste anche una soluzione ottimale ammissibile di base. Su questo teorema si basa il metodo del simplesso che, reso ancora più spedito da opportuni algoritmi e implementato su computer, permette di ricavare in tempo molto rapido la soluzione ottimale. Il metodo inizia con una soluzione ammissibile e procede muovendosi verso un’altra soluzione ammissibile in cui il valore della funzione obiettivo sia maggiore (nel caso di problema di massimo) o minore (per i problemi di minimo) del valore precedente. Si itera poi il procedimento fino a quando non esiste alcuna soluzione ammissibile di base migliore di quella già trovata (o si verifica che l’obiettivo è illimitato).

Programmazione matematica

CATEGORIE
TAG

Programmazione matematica

Programmazione lineare

Calcolo numerico