Programmazione Lineare (LP)

La programmazione lineare è la classe di problemi max c^T x s.t. Ax ≤ b, x ≥ 0 in forma canonica, dove c ∈ R^n è il vettore dei costi, A ∈ R^(m×n) la matrice dei vincoli, b ∈ R^m il lato destro e x ∈ R^n le variabili decisionali reali continue. La regione ammissibile X = {x : Ax ≤ b, x ≥ 0} è un politopo convesso e un obiettivo lineare raggiunge l'ottimo in un vertice (soluzione basica ammissibile). La disciplina nacque con l'algoritmo del simplesso di George B. Dantzig nel 1947, motivato da problemi di pianificazione dell'aviazione statunitense (donde il termine 'programmazione', precedente al suo uso informatico). La teoria della dualità (von Neumann 1947) associa a ogni LP primale un LP duale; il teorema di dualità forte afferma che se entrambi sono ammissibili e limitati, i loro valori ottimi coincidono; i prezzi ombra si leggono dalle variabili duali. Complessità: Klee e Minty (1972) dimostrarono il caso peggiore esponenziale del simplesso; Khachiyan (1979) fornì il primo algoritmo polinomiale per LP mediante il metodo dell'ellissoide (teorico); Karmarkar (1984) introdusse un metodo dei punti interni polinomiale e di interesse pratico. I solver moderni combinano simplesso rivisitato e punti interni, con presolve, fattorizzazione LU sparsa e avvio crash, risolvendo problemi con milioni di variabili in pochi secondi. Applicazioni: pianificazione della produzione, problemi di miscelazione, trasporti, gestione dei flussi di cassa e problema della dieta.