programmazione lineare
programmazione lineare
Insieme dei metodi di ottimizzazione di un criterio lineare con vincoli lineari di uguaglianza o disuguaglianza. Rappresenta un caso particolare del problema più generale dell’ottimizzazione non lineare con vincolo. La programmazione lineare è uno strumento di modeling matematico con molte applicazioni, in quanto offre una soluzione del problema sia teoricamente sia numericamente. Le applicazioni sono quelle comuni ai problemi di ottimizzazione: ricerca operativa, teoria del controllo, identificazione di modelli, ricerca del massimo rendimento, gestione e sfruttamento ottimale delle risorse. Uno dei risultati principali della programmazione lineare per problemi lineari continui (cioè a variabili continue) è l’algoritmo del simplesso, che rappresenta un’estensione del metodo di eliminazione di Gauss al caso delle disequazioni lineari. Per problemi lineari interi (cioè a variabili intere) l’algoritmo più noto è detto branch and bound. Per problemi lineari misti si impiega l’algoritmo branch and cut. Tutti e tre gli algoritmi rappresentano metodi di risoluzione esatti.