metodo del simplesso
metodo del simplesso
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 m〈n 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).